《神经网络控制》课件第8章

第8章神经控制中的遗传进化训练8.1生物的遗传与进化8.2遗传算法概述8.3遗传算法中的模式定理8.4遗传算法中的编码操作8.5遗传算法中的适应度函数8.6遗传算法与优化解8.7遗传算法与预测控制8.8遗传算法与神经网络8.9神经网络的遗传进化训练8.10小结习题与思考题

8.1生物的遗传与进化

按照时下流行的观点，在距今约150亿年前，宇宙是由一个半径为3mm的球内炙热而又稠密的物质与能量经过“大爆炸”而形成的。茫茫宇宙、无边无际，用当代最为先进的手段观测，能察知宇宙间的星系约有800～1250亿个。而每一个星系中大约有1000亿个类似于太阳的恒星。悠悠岁月，无始无终，太阳系八大行星之一的地球年龄已有46亿年。具有生命特征的生物在地球上出现、进化与发展，距今约有36亿年。这种进化的直接结果是在200～500万年前出现了人类。人类大脑的发展已历经50万年，而人类有记载的文明史约有5000年，人们依靠科学技术，享受高质量生活水平的历史约200年左右，瓦特(JamesWatt，1736—1819)发明蒸汽机是现代人类文明开始的标志。

今天，当人们环顾浩渺宇宙空间及生物发展进化的36亿年时间长河时，虽然迄今为止人类还未解开生命如何起源，还未求证宇宙中亿万星球上是否还有其他生命，但是生物有36亿年的遗传进化发展史，还是给了人们无数有益的启示。8.1.1生物进化论的基本观点

19世纪以来，人们有意识地通过生物观察、选择实验、杂交育种等，对生物的遗传、进化、发展进行了有效的探讨，逐步形成了“生物进化论”这门学科。

1859年，英国生物学家达尔文(C．R．Darwin)发表《物种起源》一书，提出了物竞天演、适者生存、优胜劣汰的生物进化论学说，阐明了生物发展以自然选择为基础。达尔文的生物进化论具有划时代的意义。

1866年，奥地利植物学家蒙得尔(G．Mendel)在系统总结及概括前人实验的基础上，发表了论文《植物杂种实验》，开创了实验遗传学。此后，H．deVries提出了突变论。W．L．Johannse提出了基因概念、纯系理论。20世纪初，T．H．Morgen通过对遗传学和细胞学的研究建立了基因理论。1952年，A．D．Hershey在实验的基础上，成功地证明了DNA(脱氧核糖核酸，DesoxyribonucleicAcid)是遗传物质。今天，检测DNA已经成为亲子鉴定的科学手段。

生物进化论的基本观点是：生物的发展与进化有三种主要形态，这就是遗传、变异和选择。

自然界中的生命千姿百态，地球上的几百万种生物相互扶持、相互依存、相互成链。千奇百怪的各种生物在数十亿年的进化中，适应环境，繁衍后代，顽强地生存下来。在人与自然和谐相处中不难发现这一点。各种生物进化的方法和结果虽然不相同，但是仍然可以找到生物在进化过程中的共同点，这些共同点表现在如下几个方面：

(１)染色体(Chromosome)具有遗传功能，遗传功能的最小操作单位是基因(Gene)，DNA是遗传物质。对DNA的检测与鉴定，就是测定子女系中是否有父母亲的遗传物质，这是实现生物亲子鉴定的科学依据。

(２)染色体是信息的载体，它把父辈的信息传递给子辈。生物进化发生在信息载体(染色体)上，而不是发生在被编码的生物个体上。例如有人做过砍老鼠尾巴试验，人为连续地砍掉若干老鼠的尾巴，但它们新生出的老鼠照样有尾巴。这个实验明确告诉人们，什么东西会遗传，什么东西不会遗传。

(３)对于染色体最小遗传功能操作单位基因，可使用人为手段给予重构，形成转基因产品或产生新的动植物品种。近代遗传工程的两大任务是：对基因破译并重构。

(４)染色体具有变异功能，这种变异往往会突变，突变的结果是子代染色体不同于母代。变异功能带来两个结果：

一是生物能在进化的广大可能空间中，快速有效地选择繁衍后代的形式，适应复杂恶劣的生存空间；二是长期(几十亿年)的变异，原始生命历经大约1×1017s(约36×108年)的进化过程，形成千奇百怪、形态各异、有不同生存本领的动植物。

(５)染色体具有选择功能。这个染色体和那个染色体复制的机会并不均等，对于不同编码个体的染色体而言，成功适应环境的染色体存在更多机会复制，能孕育出更有优势的后代。例如某些病毒或细菌，就能复制产生有抗药性的后代，致使曾经杀菌能力极强的青霉素疗效减退，而那些无力抵抗青霉素的病毒个体或细菌个体被消灭。

(６)染色体的传递无记忆功能，导致生物的进化无法记忆。这一进化原则有三层含义：

①一代生物是否进化与上一代生物是否进化之间没有联系；②上一代生物的进化不会把记忆留给下一代，否则，今天的人类不仅能够记住500万年以前人类是如何产生的，还能记得36亿年前具有生命特征的生物是如何产生的；

③无论哪一代生物，进化的原则是那一代生物根据生存环境来获取更好的生存机会和繁殖条件。8.1.2进化计算

进化计算(EvolutionaryComputation)是20世纪60年代兴起的一门学科，它的研究内容是仿照生物进化过程，按照优胜劣汰的自然选择，探讨优化的规律与方法。

优化问题是数学中的一个重要研究分支。现代控制理论中的一个重要议题，就是在众多系统解中寻求一个最优解。进化计算的提出，给优化问题求解提供了一种用传统方法较难求解的新方法。

进化计算有三种不同的计算法，它们是遗传算法(GeneticAlgorithm)、进化规划(EvolutionaryProgramming)和进化策略(EvolutionaryStrategy)。１．遗传算法(ＧＡ)

遗传算法是一种模拟生物遗传理论建立起来的自适应、概率性迭代搜索算法，突出“适者生存、不适者淘汰”的竞争机制。

遗传算法的解题思路是从一组随机产生的初始解开始，沿着某一确定的方向搜索。这一组随机产生的初始解统称为“种解”，种解中的每一个个体，也就是每一个初始解都被称为“染色体”。在搜索中对每一个染色体适应环境的程度随时做出评价，以判断染色体的优劣。适应能力强的染色体被选择的几率大；适应能力弱的染色体被选择的几率小。被选择的染色体及时进入下一代，通过交叉、变异等遗传操作，形成新的染色体。这样经过若干代以后，算法最终收敛于最好的染色体，该染色体就是所求问题的最优解。

遗传算法求解问题的流程如图8-1所示。图8-1遗传算法求解流程图遗传算法运算过程归纳如下：

①随机产生初始种群Ｍ(t)。

②用适应度函数u(ｍ)评价Ｍ(t)中每个染色体ｍ，评价方法是计算每个染色体ｍ的适应度函数u(ｍ)，不同的染色体有不同的计算结果。

③通过选择、变异产生新的染色体进入下一代，染色体被选中的概率ｐ(ｍ)与该染色体的适应度函数u(ｍ)成正比：ｐ(ｍ)∝u(ｍ)。

④按概率大小由遗传算子进行选择，产生新的染色体形成新的种群Ｍ(t＋１)。

⑤重复②～④，直至完成事先预定的要进化的代数。

2．进化规划(eＰ)

进化规划是一种模拟生物自然进化的自上而下的优化设计方法。在自然界，每种动植物，从低等生物到高等智能生物，都要迎接生存的挑战，包括适应严酷的环境、寻求足够的食物、争取安全的场所、有效地繁衍后代。这种对环境的响应就是一种“规划行为”。

进化规划讨论的主要议题如下：

(１)生物进化是否成功要以整体行为作为衡量标准，不能以个别染色体是否成功为衡量标准，也不能从个别组成是否好坏来衡量整体。

(２)生物进化首要考虑的问题是对环境行为如何做出响应，而不必考虑这个响应是如何产生的。

(３)进化规划实质上是一个不断变异、不断再生的迭代过程，迭代是对进化过程的一种模拟。染色体作为一个个体，在不断变异、不断再生并优化的进程中，要从种群全局

角度去处理。因此，进化规划重点讨论的问题不是染色体的变异和选择，而是种群的变异和选择。进化规划的规则是：自上而下考虑整体的全局优化。

例如一曲音乐中，一个音符的优化要服从整个乐曲的要求。一个阿拉伯数字的价值不在它自身，而在它位于一个数的哪个位置上。

进化规划的运行规则是：自上而下考虑整体的全局优化。３．进化策略(eＳ)

进化策略是在1973年由德国数学家IngoRechenberg提出的。随后由HansPaulSchwefel发展并用于数字优化。

进化策略的含义是：

生物在长达36亿年的漫长进化岁月中，能够将完成进化所使用的方法等价成一个机智优化过程，这个过程中存在一个进化策略的理论。既然是“策略”，事实上就是生物从结构

及演化两个方面如何得到优化。

进化策略理论的最基本观点如下：

(1)进化过程优化了生物；

(2)进化自身是一个生物过程；

(3)进化必定将“进化”自身优化。

进化过程不仅对染色体的生存随时做出应有的贡献，而且更为重要的，是在若干代染色体的变异中选择较好的遗传策略，目的是为了更好地适应环境。

只有讲究策略，生物的进化过程才能形成优化过程。

４．进化计算的评价

无论是GA、EP，还是ES，它们都是围绕“优胜劣汰”的自然法则求解工程技术中的优化问题，它们的区别在于实施方法与步骤不同。表8-1列出了三种计算法的不同之处。

研究进化计算的意义，不仅仅在于思考３０多亿年来生物从原始到高级智能的变异过程，也不仅仅在于思考一种全新的优化模型和优化方法，更为重要的是认识在智能仿生

过程中自然界赋予生命的哲理和游戏规则，为人类进一步改造大自然，与大自然和谐相处提供科学的思维方法。对进化计算提出以下一些评价：

(１)进化计算的目的是求优化解，因此在工程技术中适用面广、移植性强。进化计算所遇到的遗传、交叉、变异操作，都是针对染色体编码序列中的基因进行的，而工程技

术中的计算都可以转化成编码序列模型来表示。

(２)进化计算是一种并行处理的运算，源自并行处理种群中各种染色体的变异，以及并行处理染色体中各基因组成成分的相关码元。并行处理功能使它对复杂优化问题有较

快的求解速度。

(３)进化计算中涉及到的适应度函数仅与优化问题相联系，对适应度函数自身的限制较少，这就对适应度函数的选择提供了较宽的范围，例如甚至不要求连续、可导等作为约束条件。

(４)遗传操作(如选择、交叉或变异)都是按概率在解空间进行有目标、有方向的启发式搜索，既不同于盲目的穷举，也不同于随机查询。

(５)选择操作通过粗调与微调有机结合进行，交叉操作是在足够大的范围内进行信息重组，变异操作则是通过基因突变实现优化。这些操作能有效避开求解空间的局部极小

点，以较快速度达到全局最优解。

(6)进化计算存在着三个问题：

第一个问题是进化计算是一门由人类创立的技术，是人们头脑中对生物进化过程的模拟思考，它不同于生物的实际进化过程——一种客观存在的历史发展。两者本质的区别决定了进化计算总会有误差。

第二个问题是按概率进行操作的进化计算优化算法，不能保证100％找到全局最优化解。能100%找到全局最优化解的只能用其它方法,例如穷举法(TryAll

Possibilities)。就目前已知的事实，肯定能找到全局最优解的唯一算法是穷举法。

第三个问题是进化计算不是求解最优的首选，只要能使用线性规划、动态规划、拟牛顿法等传统方法，就不要使用进化计算。

8.2遗传算法概述

8.2.1遗传算法中遇到的基本术语

染色体(Chromosome)：生物遗传、繁殖的基本单位，又称个体。

种群(Population)：多个染色体的集合，染色体与染色体之间存在生命特征的有机联结。进化之初的最原始种群称为初始种群。基因(Gene)：遗传、繁殖的最小单位，多个基因按一定的排列方式组成染色体。

编码(Coding)：将搜索空间的解映射到遗传空间时，解的按序组合称为编码。例如依次走访８个城市，从城市３开始，访问顺序为3→6→8→1→2→5→4→7，可以用编码36812547表示走访路线。

适应度(Fitness)：适应度函数的简称，解的目标函数值，能衡量染色体的好坏。8.2.2遗传算法的运算特征

１．遗传算法的特点

(１)遗传算法是对解集合的编码进行运算，而不是对解集合进行运算。

(２)遗传算法的搜索开始于解的一个种群，而不是其中的个别解。

(３)遗传算法只用适应度评价解的优劣。

(４)搜索方法用的是概率搜索，而不是路径搜索。２．遗传算法的基本操作

遗传算法的基本操作有三种：选择、交叉和变异。

１)选择(Selection)

所谓选择，是指从种群中按一定的标准选定适应做亲本的染色体。选择的目的是为了将适应的染色体交配后复制出子代。

选择的方法较多，常用的有适应度概率法、排序法、期望值法等多种，其中又以适应度概率法最为简洁有效，下面举例介绍。适应度概率法通过计算染色体被选中的概率来完成选择。设种群中染色体i的适应度函数为fi，种群中共有N个染色体，染色体i被选中做亲本的概率pi为：式中，k的取值可为正整数。例如N＝10，k＝1，2，3，按上式计算得到概率pi如表8-2所示。从k＝１，２，３的概率取值能观测到：

(1)适应度函数fi越大，被选中的概率越大；

(2)k值越大，适应度高的染色体概率越大；

(3)概率一旦确定，概率大的染色体有更多的机会参加交配，复制的遗传因子能在种群中扩大。

2)交叉(Crossover)

交叉又称重组(Recombination)，其含义为两个染色体的基因进行互换产生新的后代。交叉的方式有单点交叉、双点交叉、按序交叉和位置交叉等。

(1)单点交叉(Onepoint)：单点交叉是指在染色体中随机取某一基因位，从此位开始互换两父本后面的序列，产生两个子代，如表8-3所示，该表从a4、b4开始交换。

(2)双点交叉(Doublepoint)：双点交叉是指在染色体中随机选取两个基因位，交换选取两位之间的基因位置，如表8-4所示，该表将a2~a6与b2~b6交换。

(3)按序交叉(Orderbased):按序交叉是按照一定次序生成子代的交叉操作。有两个父本分别为父本1、父本2，它

们有相同的基因，但排序次序不同。将父本在两个交叉点间的部分复制，成为子代的一部分，如：可得子代1的一部分，子代1余下的4个基因应当从父本余下基因中去选择。从父本2中去掉a5a7a2和a9a1a4，从a3开始转至父本2的第1个基因a6继续。即子代1余下的4个基因为a3a6a8a10同理，子代2的10个基因为

子代2a9a1a4

a5a7a2

a6a10a8a3

由此形成的结果如表8-5所示。

(4)位置交叉(Positionbased)：设有两个父本分别为父本1、父本2，子代1的生成方法是：

在父本1中随机选几个位置的基因，子代1的位置继承父代1的相同位置基因，如：子代1余下的位置从父本2中的基因选取，但要从父本2中去掉85462，余下的按从左到右的顺序取出，即

还余1、3、7、10、9，填入得

子代2按此办理，由此形成的结果如表8-6所示。

与选择操作相比较，交叉操作能使基因排序变化更加灵活，实现真正意义上的人为重组，适于大范围操作。

3)变异(Mutation)

变异是使染色体中的基因按照概率的变化进行重新排列。以二进制编码方式为例，所谓变异就是将基因值取反，将“0”变“1”，将“1”变“0”。由于变值的范围有限，搜索范围小

于交叉操作。

现以解决TSP组和优化问题为例，设父本的基因为123456789，变异操作的种类较多，现列举其中的三种：

(1)SWAP为对调两个基因的位置；

(2)RAR为在新位置插入基因；

(3)Inversion为将一段基因逆转。

表8-7就是变异操作的一个例子。8.2.3遗传算法中的概率计算公式

在对父本的基因进行选择、交叉或变异的相关操作时，基因被复制的几率就是概率，概率越大，选做亲本的机会就会越多。为了计算不同操作情况下的概率，先做出如下一些

假设：

设表征基因组模式用一串二进制位(比特，bit)表示，其中每一位的取值用“０”、“１”或“*”表示，“*”指该位或者是０、或者是１。例如一个基因组模式的二进制序列为

1*0*01

表示它们4种可能取值：该序列的长度为6，序列长度常用L表示，基因模式常用H表示。在一个二进制序列中，经常要截取其中某些位。截取确定基因位置的长度用d表示，d又称为直径。例如基因组模式二进制序列

1*0*01取第4～6位*01，其直径d=3。设f为待优化的函数，定义在长度为L的二进制序列上，函数f又称为适应度函数，简称适应度。

选择、交叉或变异等遗传基本操作，都是对两个或两个以上的父本进行操作，生成若干不同的子代。一般情况下，每一个父本用一个二进制序列表示，考虑N个序列的操作。

从N个序列x1、x2、…、xN中选中xj为亲本序列的概率为上式表明，适应度函数大的序列被选中的概率大。

如果用f表示种群所有序列适应度的平均值，即则概率公式为

8.3遗传算法中的模式定理

遗传算法是模拟生物进化过程这一自然界运动规律的计算方法，由于进化过程的时间有数十亿年，使得模拟算法本身自然、直接且又朴素。它没有严密的数学推导作为理论基

础，总是围绕着选择、交叉、变异等基本操作进行。截至目前为止，尚无足够的基础理论来阐明遗传算法的运算特征。而其它计算算法，则需要严密的数学推导作为理论基础。

目前有几种描述遗传算法运算特征的方法，如“模式定理”、“基因块假设”、“Walsh模式变换”等几种，其中以“模式定理”较为成熟。8.3.1模式定义和模式的阶

模式定理最早由Holland提出，后经许多人不断完善，现已成为遗传算法最成熟的理论。模式定理的主要内涵是解释染色体编码结构在进化过程中的应用。

1.搜索空间的规模

设物体空间或搜索空间为Ω，在此空间内包含所有可能的染色体编码，设染色体采用k进制编码，染色体长度为L，则搜索空间的规模为kL。

例如对种群

f(x)=xsin(100x)－0.1

编码，x的取值范围［0，0.1］，函数图形如图8-2所示。图8-2f(x)=xsin(100x)－0.1对f(x)采用二进制编码，k=2。选用8位二进制数表示染色体，染色体长度L=8。搜索空间规模kL=256。

在整个搜索空间内随机选择若干个染色体，组成一个初始种群P，初始种群P内所含有的染色体个数要有足够的数量，目前尚无现成的公式计算P中所需要的染色体的精确数

量。

本例假设选择4个染色体，用Si(i=1，2，3，4)表示：

S1=00101010

S2=00101110

S3=01101010

S4=01101110将每个染色体转化成种群f(x)的自变量x表示，考虑到

S=00000000→x=0.0000

S=11111111→x=0.1000

x的取值精确到小数点后4位，有一般地，已知Si(二进制数染色体表示)求xi(十进制数染色体表示)的公式如下：式中，(Si)10是Si的十进制数值，b是xi的上限取值，a是xi的下限取值。

当染色体用十进制数书写时，便于进一步处理数据。

2.基因模式的定义

基因模式是用于描述染色体集合的模板。该模板之所以被命名为基因模式而不叫染色体模式，是因为集合体内在某些确定的位置上有相同的基因，而进行运算时又以基因为单位进行。

基因模式常用H表示。

基因模式H是与染色体等长的k进制串。

与染色体串不同的是，基因模式的各位表示方法有两种：一种是k个字符，如五进制串，每一位允许有0，1，2，3，4；另一种是“*”，用于表示某一位上的非确定数。通常，用k个字符表示的位称为“确定位”，用“*”字符表示的位称为“非确定位”。“*”又称为通配符。以二进制基因为例，设基因模式由4位组成:

a3

a2

a1

a0

1*01

显然，a3

a1

a0为确定位，a2为非确定位。因此对染色体而言，每个位置允许有三种不同的字符：0、1和*。

一般地，对用k进制数表示的染色体，每个位置将允许有k+1个不同的字符，长度为L的染色体编码组成的基因模式共有(k+1)L个。例如长度为8位的二进制染色体共有(2+1)8=6561个基因模式。

通配符“*”不是一个真正的基因。在二进制染色体中，“*”既可以为0，也可以为1，是一个单独的符号。设存在一个基因模式：

H=0*101*10

以下有4个染色体与此基因模式匹配，它们组成了搜索空间的一个子集，分别是

S1=00101010

S2=00101110

S3=01101010

S4=01101110可见基因模式H和染色体子集之间的关系为：H中的“**”分别用“00”、“01”、“10”、“11”取代。由此可知，8位二进制串********代表了所有染色体串；而仅由“０”、“１”组成的８位二进制串，如

１1０1１１００

仅代表一个染色体串的基因模式。０*101*10就有4个染色体串与之相配。

一般地，基因模式中的“*”个数决定了与基因模式相匹配的染色体个数。设“*”的个数有n个，k进制染色体串将有kn个与之相匹配。另一方面,每一个长度为8位的二进制染色体串，能够匹配28个基因模式,例如染色体11010010可匹配的28个基因模式为每一个长度为L的k进制染色体串，能匹配kL个基因模式。长度为L的k进制染色体编码空间的基因模式数共有(k+1)L个。设由此形成的种群大小为P，则可能存在从kL到P·kL种不同的基因模式。

定义基因模式的意义在于：能够把搜索空间上的染色体进行结构化分类。考虑到每一个基因模式隐含一个基因子集，染色体之间的内在联系事实上是基因模式的联系。对染色体的遗传算法操作，实质上成了对基因模式的运算。

3.模式的阶

基因模式H中确定位的个数，称为模式的阶，用O(H)表示。例如模式1*1****0的阶为3，记为O(H)＝3。又如

H1=0101*0**

则

O(H)=5

基因模式

H=********

可表示整个搜索空间Ω，

Ω=********则

O(Ω)=0

一个基因模式的阶越大，确定位越多，所能代表染色体串的个数就越少，与之匹配的染色体子集元素就越少。

定义“模式的阶”的意义在于：用于计算变异中模式的存活率。

4.基因模式的定义长度

基因模式中第一个确定位到最后一个确定位之间的间隔，称为基因模式的定义长度，用δ(H)表示。定义长度又称为模式的距。

例如，“定义长度”用于计算基因模式交叉时的存活率。

以上分别给“模式的阶”及“定义长度”做了定义，这两个概念的引入有利于探讨基因模式在遗传操作过程中的变化情况。8.3.2模式定理(Schema)

20世纪60年代，美国Michigan大学的Holland教授在他的著作《AdaptationinNaturalandArtificialSystems》中创建了遗传算法，该算法是一种基于二进制表达的搜索算法。算

法的基本概要是：种群中的染色体通过信息交换重新组合新的染色体串；根据评价条件，按照概率选择适应能力强的染色体串进入下一代；经过多代进化后，种群最终将稳定在适

应性最好的染色体串上。由Holland提出的模式定理概括了搜索过程。定理表述为：在三个遗传算子的作用下，平均适应度高、模式的阶低、定义长度短的模式，其个数在遗传算法的进化中按几何级数增长。

遗传算法的进化过程是一种迭代过程，通过种群中的迭代算法，品质优秀的基因模式得以重组，高质量的染色体得以产生。

定理中表述的三个遗传算子分别是选择、交叉、变异。模式定理揭示了平均适应度、模式的阶、定义长度与迭代进程之间的联系。

1.选择算子

选择算子在搜索空间内不会产生新的染色体串，但适应度高的染色体串被选中的概率大，品质优良模式的数量将增多，选择算子的功能就是在种群中复制质量优良的模式。

设种群P内有N个染色体，且每个染色体串的长度为L；

m(H，t)表示第t代种群P中与模式H匹配的串数；对于第t代种群P中与模式H匹配的染色体串，用f(H，t)表示所有这些染色体串的平均适应度(又称平均适应值)；J为种群的平均适应度。

设种群关系仍用f(x)=xsin(100x)－0.1，种群规模P=20，串长L=8，假定第t代种群由如下染色体串组成：

S1=11010110

S2=00111111→f(x2)=0.117562

S3=10100101

S4=10010001

S5=01001000

S6=01100100

S7=01000111

S8=00110100→f(x8)=0.109392

S9=10011110

S10=01111100→f(x10)=0.064463

S11=10111101→f(x11)=0.182725

S12=10100000

S13=01100001

S14=00110111→f(x14)=0.108649

S15=01011011

S16=10111000→f(x16)=0.142433

S17=11000010

S18=11000011

S19=10010000

S20=01100110其中，f(xi)仍由函数曲线确定，为各xi的适应度，xi的计算与上节相同。考察三个模式：

H1=**

1

1****

H2=****

**1

1

H3=

0***1*0

0

与模式H1匹配的有S2、S8、S10、S11、Ｓ14、S16，则

m(H1，t)=6

模式H1的阶

O(H1，t)=2

定义长度

δ(H1)=1同理，

m(H2，t)=5(与H2匹配的有S2、S7、S1４、S15、S18)

O(H２，t)=2

δ(H２)=1

m(H３，t)=２(与H３匹配的有S５、S１０)

O(H３，t)=４

δ(H３)=７

一般地，若t代种群中与模式匹配的染色体串有ｐ个：St1，Ｓt２，…，Ｓtｐ，则平均适应度为染色体串Si被选中的概率为式中，f(Si)是染色体Si的适应度；N是种群P所含的染色体串数；fsum(Si)是种群P的总适应度。种群的平均适应度为由于选择操作是种群的N个染色体放入选择池，每一个与模式Ｈ匹配的染色体串进入下一代的概率为f(H，t)/f(t)，其中，f(t)是种群在t代所有染色体适应度之和。交配后第t＋１代模式Ｈ的数量为

上式表明：

(1)种群中染色体串生长的数量是模式适应度与种群平均适应度之比。

(2)模式适应度高于种群平均适应度，该模式Ｈ的数量将增加，或者下一代中所匹配的染色体串数会增加；模式适应度低于种群平均适应度，该模式Ｈ的数量将减少，或者下一代中所匹配的染色体串数会减少；接近于种群平均适应度的模式，数量在下一代中保持不变或基本不变。

(3)种群中的任何一种模式都按此规律变化，这一性质称为遗传算法隐含的并行性。

(4)考察模式适应度高于种群平均适应度的相对变化，设a为常数，令代入到m(H，t)中，有从t＝0开始，有

m(H，t)＝m(H，０)(a＋１)t

a＞０，模式的适应度高于平均水平，在下一代中所匹配的染色体串数将按几何级数增加(或按指数规律增长)；

a＜０，模式的适应度低于平均水平，在下一代中所匹配的染色体串数将按几何级数减少(或按指数规律减少)。

(5)把讨论结果用于本节用例。对H1而言，在t代有6个染色体与之匹配，该模式的适应度为种群的平均适应度为模式H1的适应度与种群平均适应度之比为结果表明，模式H1高于平均值，在下一代中与模式H1匹配的染色体串数将按几何级数增加。如果计算出来的比值结果小于１，则表示与该模式匹配的染色体串数将按几何级数减少。

2.交叉算子

交叉运算将破坏原有的染色体模式，产生新的染色体模式，破坏概率与定义长度成正比，以下例说明。

设种群P中的染色体为

基因位1234

5678

S

=1101

0000

同时与下面两个模式匹配：

H4

=

1

1**

****

H5

=

1

1**

**0

0假设交叉位置S=4，则交叉后子代中仍有一个染色体串与模式H4匹配，模式H4得以存活，而模式H5被破坏，H5的始端“11”与末端“00”分别置于不同的后代上。

模式的死亡概率pd(H)和存活概率ps(H)与模式的定义长度δ(H)及基因点位置有关。

设模式H4、H5的定义长度分别为δ(H4)、δ(H5)：

δ(H4)=1

δ(H5)=7

对于单点交叉，可以作为断点的位置有L－1个，某一位置能被选为断点的可能性为，那么模式H的死亡概率为模式H的存活概率为用于模式H4和H5，则死亡概率为存活概率为可见模式H4得以生存，模式H5被淘汰。

交叉运算中只有部分染色体串参加，因此还有一个指标称为交叉率，常用pc表示，其大小为参加交叉的染色体串数与全部染色体之比。在引进交叉率pc以后，一个模式的实际

存活概率公式修改为

设pc=0.7，H4和H5的实际存活率将分别为说明H5仍有存活机会，其原因是所有的染色体没有全部参加交叉。

现在考察交叉位置发生在一个模式的固定位置之间，结果表明该模式仍有存活机会。例如有下面两个染色体：

基因位1234

5678

S1=

1110

1001

S2=

1100

1000

当交叉位置发生在第2、3、4、5、6、7基因位前，模式H5仍能存活。相应的染色体串如下：

交叉位置在第2基因位前：11001000；

交叉位置在第3基因位前：11001000；交叉位置在第4基因位前：11101000；

交叉位置在第5基因位前：11101000；

交叉位置在第6基因位前：11101000；

交叉位置在第7基因位前：11001000。

考虑到上述可能性较小，模式存活概率公式可修改成

综合选择与交叉两种运算，模式复制增长方程式为上式表明，经过选择与交叉产生下一代模式的数量，与上一代的数量、定义长度、模式适应度、存活概率有关。m(H，t)越多，f(H)越大，δ(H)越小，下一代模式数量越多。

3.变异算子

变异操作按变异概率pm随机改变一个染色体串上的某一位，例如对二进制编码，将0变为1，或将1变为0。

若变异概率为pm，则1－pm为不被改变的概率，或称为保持概率。

要想模式经过变异后还能存活，条件是该模式上所有固定位保持不变。以染色体S5为例，设

S5=11001000

它与

H3=11****00相匹配。如果变异后要求H3不变，那么只能是H3中所有固定位保持不变。H3存活的概率可写成该式可写成一般式：式中，1－pm就是保持概率，O(H)是模式的阶。通常pm<<1，上式能近似写成

ps(H)≈1－pmO(H)设

H1

=*1

1*****

H2

=

1

1******

H3

=

1

1****0

0

则

ps(H1)=1－pmO(H1)=1－0.005×2=0.99

ps(H2)=1－pmO(H2)=1－0.005×2=0.99

ps(H3)=1－pmO(H3)=1－0.005×4=0.98

综合选择、交叉和变异算子，模式H复制后增加的数量为上述不等式是模式H复制后增长数量的方程式，它是在适应度函数为正的前提下导出的。模式匹配的染色体串数是增加还是减少，也能由上述不等式预测。如果选用的适应度函数不能保证全为正值，需要进行映射操作，确保映射后的适应度数值为正。

本节小结如下：

(1)模式的平均适应度是决定模式增减的主要因素；

(2)选择算子不能产生新的模式，交叉算子和变异算子通过结构化方式利用随机交换基因位产生新的模式；

(3)模式的定义长度用于描述交叉算子对模式生存的影响，定义长度短的模式容易生存；

(4)模式的阶用于描述变异算子对模式生存的影响，低阶的模式容易生存；

(5)模式定理阐明了遗传算法的运行机理，通过短的、低阶的模式交叉或变异进行空间搜索，在种群中迭加运算，让高品质的模式得以组合，最终获得高质量的染色体，完成

优化过程。

8.4遗传算法中的编码操作

所谓编码是一种转换操作，将问题空间中的解变量转换成遗传空间中的染色体，这些染色体由基因按一定排列方式组成。这个转换过程就是编码。以染色体为一串二进制数为例，基因就是其中的二进制位，编码就是将实际问题的解转变成一定规律的二进制串。

解码是编码的逆操作，表述成将染色体的编码映射到问题空间的操作。8.4.1遗传算法设计流程

遗传算法面对两个空间：一个是问题空间，或称解空间，在此空间内完成对解的评价与选择；另一个是遗传空间，或称编码空间，在此空间内对染色体实施遗传运算。

讨论遗传算法设计流程的意义在于如何利用遗传算法达到实际需要的精度。算法本身没有任何物理意义，它仅仅只是一种数学表达，那么在书写数学表达式的时候，必然存

在三个问题需要解决：

(1)如何选择合适的编码方式；

(2)如何确定适应度函数、概率、遗传算子及相关参数；

(3)如何将求解问题转化成算法所能接受的模型。8.4.2遗传算法中的编码规则

编码方案需要达到两个目的：必须完备和完全对立。

(1)必须完备：问题空间中的所有点均为候选解，都必须作为遗传空间中的点来表现，缺一不可。遗传空间的这些点就是染色体。

(2)完全对立：遗传空间中的染色体能对应所有问题空间中的候选解，且染色体与候选解能一一对应。

为了达到编码的目的，还需要具体的编码规则，因为能达到上述目的的所有编码设计不一定能有效地提高搜索效率，而在迭代过程中速度缓慢的搜索，在实时生产环节中没有任何用处。为此，经DeJong提出，具有可操作性的两条编码规则如下：基因块有意义:编码生成、距短、阶低。

使用最小字符集:编码采用最小字符集，求解问题能易于表示与描述，目前所用的最小字符集当属二进制数，它只有“0”、“1”两个字符。

使用二进制编码，有利于在计算机上操作运行。

编码技术有多种，这里仅介绍一维染色体和二维染色体的编码技术。8.4.3一维染色体的编码方法

当问题空间的候选解转换到遗传空间形成染色体后，若染色体呈一维排列展现基因链，这种编码方法称为一维染色体编码。常见的这种编码技术有二进制编码、灰码编码和浮点编码等。

1.二进制编码

二进制编码的主要任务是将问题空间的候选解转换成遗传空间的二进制字符串。转换时需要用到如下已知条件：

(1)初始种群在问题空间中的分布情况；

(2)变量的取值范围；

(3)种群函数的精确程度。

转换需要根据变量取值空间计算二进制串的长度。

至于染色体的个数如何选择，目前尚无确定的方法。例如初始种群函数为

f(x)=20+x+10sin(4x)+8cos(3x)

要确定在x=[0，10]区间的最大值，要求精确到小数点后6位。

其函数图形如图8-3所示。图8-3初始种群分布f(x)=20+x+10sin(4x)+8cos(3x)考虑到区间长10，按精度要求，至少将取值空间分成

10×1000000

|←6个0→|

份，设二进制染色体v的串长度为m，应有：

2m－1＜10000000≤2m－1

不难确定

m=24

染色体可供选择的范围如下：

位23～16

15～8

7～0

最小00

00

00H

最大FF

FF

FFH选染色体个数5个(选少了，可能不包括最大解在内)，如：

V1

=4

E

8

3

E

0

H

V2

=4

E

7

8

0

A

H

V3

=D

8

5

8

3

6

H

V4

=1

E

6

9

4

E

H

V5

=3

A

7

B

E

6

H

经过计算，可将染色体二进制数转换成实数变量。计算公式为式中，v=v1，v2，v3，v4，v5的十进制数；［a，b］是x的取值区间。由此算得

x1=3.067608

x2=1.815192

x3=7.825960

x4=1.187943

x5=0.756131

二进制编码的优点如下：

以最小字符集的编码原则为出发点。

代码简单，便于交叉、变异操作。

便于使用模式定理进行分析与预测。二进制编码的缺点如下：

编码数字不能直观反映所求问题的模拟量特征。

染色体长度直接与问题空间解的精度有关。如果长度较短，二进制数的位数较少，无法反映所求问题的精确度；如果长度较长，二进制数的位数较多，搜索空间必然增大，搜索的时间增长，搜索的难度也将增大。

相邻二进制编码之间可能存在较大的Hamming距离，致使算子的搜索效率降低。这一问题有时称为Hamming悬崖。例如4与5的二进制数分别为0100与0101，相邻两变量的Hamming距离为2，表示问题空间两个近点在遗传空间内有较大的Hamming距离。

2.灰码编码

灰码编码的结果也是一个二进制串，通过将二进制编码进行一次转换而获得。由于实行了一种有效的转换，从而避免了问题空间两个近点在遗传空间内有较大Hamming距离这

一缺陷，使得问题空间的两个近点在遗传空间内，也相互靠近。

设二进制编码结果为b0b1b2…bn-1，相应的灰码二进制串为a0

a1

a2…an－1，转换公式为式中，运算符号为模2加法。

反之，有从灰码转换成二进制码的转换公式表8-8列出了二进制编码和灰码编码的一一对应关系。考察十进制数0～15的灰码编码，不难发现相邻两码的二进制数串中，仅有1位发生变化，如从7→8，灰码改变为从0100→1100，仅第一位改变。而在二进制码中，从

0111→1000，4位均发生了改变。由此可知，在问题空间相邻的两个点(如7和8)，在遗传空间内仅a0位发生了改变。参数值增加一步，相应代码仅改变一位。

3.浮点编码

浮点编码是由灰码编码转换而来的一种编码方法，它的编码来源与灰码编码相同，仅采取小数点浮动的方式。当采用浮点编码时，每一个染色体串都可以编码成一个与解向量

等长度的浮点数向量。

这样一来，在执行算法的时候，遗传空间就是问题空间，染色体串自身反映了待求问题的规律。因此当遗传空间不是问题空间的时候，采用浮点编码能缩短遗传空间与问题空间之间的差距。浮点编码的编码方法如下：

(1)已知初始种群的函数分布f(x)；

(2)在自变量x的取值区域内均匀随机产生若干个浮点数，长度应满足一定的精度要求；

(3)计算种群及各个染色体的适应度；

(4)将随机产生的浮点数转化为二进制数。

浮点编码有如下优点：

(1)精度与编码本身无关，仅取决于所用机器，显得比二进制灵活、方便；

(2)浮点数表示数的范围比定点数广,从而表达区域大;

(3)设计封闭动态的遗传算子及处理非常规约束都比较容易。8.4.4二维染色体编码

在现实生活中，许多系统的解本身不是一维解，常以二维或多维的形式出现，这时应采用二维或多维染色体编码。

以图像识别为例，系统就是以二维矩阵的形式记载一幅图像。图8-4绘出了用黑白10×10像素表示英文字母“A”的图形，为编码方便，设黑色像素为1，白色像素为0。图8-410×10像素表示“A”像素划分得越细，图像越清晰，例如100×100像素表示的图，远比10×10像素的图清晰度要高得多。

A的二维染色体编码为

A=

8.5遗传算法中的适应度函数

适应度函数在遗传算法中有两个功能：评价染色体和做运算的选择依据。

适应度函数之所以有如此功能，是因为按照生物进化优胜劣汰的原则，遗传算法总朝向适应值增加的方向进化，目标函数的优化方向总与适应度函数增加的方向相同。

为了理论上分析问题方便起见，应使适应度函数非负。若适应度函数值为负，需要进行适宜的转换。

本节讨论两个问题：

(1)目标函数与适应度的转换；

(2)适应度函数如何标定。8.5.1将目标函数转换成适应度函数

针对“将目标函数转换成适应度函数”这一问题，可归结为两种不同情况：

(1)目标函数本身就是求最大值；

(2)目标函数为求最小值。

如果目标函数本身就是求最大值，适应度函数可直接写出。例如求目标函

f(x)=xsin(10x)x∈［0，5］

的最大值，适应度函数直接写成

fit(x)=f(x)=xsin(10x)为保证适应度函数非负，可加上一个较大的数，如

fit(x)=f(x)+6=xsin(10x)+6

一般有

fit(x)=f(x)+c

其中，c为正数。

目标函数为求最小值，可将目标函数映射成适应度函数，公式是

fit(x)=c－f(x)

如果目标函数f(x)为负，也可以用下式转换：例如求函数

f(x)=x2+1－1≤x≤1

的最小值，适应度函数可设计成

fit(x)1=2－f(x)=1－x28.5.2标定适应度函数

对适应度函数进行标定的意义在于让染色体适应值之间在进化过程中既保持一定差异，又避免差异过大。

生物进化过程中没有差异是不可能进化的。“差异过大”将使进化过程夭折，因为在遗传算法的初始阶段，当种群规模较小，且某些染色体的适应度过强时，由于它或它们远比

其它染色体的适应值高，那么这种染色体被选中的概率就非常大，它或它们将很快充斥整个种群，导致遗传算法极快收敛但陷入局部极小点，所得的解未必是最优解。由此可见，在进化的初始阶段应避免差异过大，适当限制较高适应值染色体的过快繁殖。在进化后期，情况恰好相反，种群中绝大多数染色体都有较高的适应值，或种群的平均适应值与最大适应值已接近，使得其中品质优秀的染色体失去了竞争力，无法从众多的染色体中脱颖而出。显然此时应尽量突出染色体之间的差异。

遗传算法要考虑到进化初期和后期对染色体差异不同的要求。

8.6遗传算法与优化解

现以求旅行商(TSP)最短路径来说明遗传算法的应用。

TSP问题描述为：旅行商在几个城市旅行，令L为旅行商巡回闭合路径，旅行商从一个城市出发，一个一个城市路过，每个城市只经过一次，最终回到出发城市。显然，TSP问题就是要求解Lmin。8.6.1适应度函数的确定

为解题方便计，把几个城市的旅行过程用ai的数字序列表示：

ai∈Z+

其中，1≤i≤n，i从1到n的取值表示巡回的次序。

设进化到了第n代用t表示，t将意味着种群进化到了第t代。第t代的种群为

pt=(a1t，a2t，…，ant)

t=0时表示种群为初始种群，用p0表示：

p0=(a10，a20，…，an0)初始种群的性能将直接对算法产生影响，例如初始种群的物种多样性，往往直接影响算法的收敛快慢及寻优结果。

用f表示求解问题的适应度函数，设计适应度函数应考虑如下因素：

①选择每个巡回路径个体之和L的倒数，问题变成求解1/Lmin的最大值；

②也可以使期望路径长度减去巡回路径长度之差为最小；

③进化初期要防止差异过大，避免某些染色体繁殖能力过强，因适应值过高陷入局部极小点；④进化后期要防止差异过小，使算法陷入缓慢进化，致使优秀的染色体在相对均匀的随机选择中无法脱颖而出。

结论是：在设计适应度函数时要注意，各个体入选父本的概率不应当与目标函数成正比，仅仅与种群中目标函数值的降序排列有关。

通常按种群线性分级策略进行计算。8.6.2线性分级策略

适应度函数的计算策略如下：

(1)首先将个体按目标函数值的优劣排队，设N为种群规模，排队为

F1≥F2≥…≥FN

(2)把N个染色体按排序结果分成m类，每类有k个染色体：

(3)给每类个体赋予公差b1＜b2＜…＜bm，则第i个染色体的适应度为以n=10为例，有10个城市供旅行，取N=20(适当增多为好)，m=3，k=int(20/3)=6，b1=1，b2=3，b3=6。随机产生一组初始种群后，每个染色体的函数值及适应度可计算出来，如表8-9所示。从初始种群中选择几个个体作父本，采用轮转选择法选择个体，方法如下：

将区间［0，1］划分成s个小区间，划分依据是种群个体的适应度占总适应度的百分比，用δ表示：式中，k=1，2，…，s；s是种群的个数。选中个体的方法随机进行，在单位区间内用均匀随机变量产生试验值，落在哪个小区间内，那个小区间内的个体将被选中。当个体过于集中在某些小区内时，陷入局部极值的可能性较大，为了避免这一情况出现，种群规模越大越好。但过大的种群规模，将增大计算工作量。实践证实，n个城市的

种群规模宜在n～2n之间确定。8.6.3算法流程

算法流程如下：

初始化，确定种群规模s、交叉概率p0，变异频率pm

随机产生初始种群P0

0→t

while未结束

do0→新种群pL+1的个体数

fori=1tos

dof(ai′)→fi

max(fi)对应的个体→当前最优解

whilek＜s

do从

pL中选择双亲(用亲本代选择)

ifpc＞Random［0，1］

then使用交叉操作产生子代

ifpm＞Random［0，1］

then使用变异操作改变子代

将生成的子代存入pt+1

k+1→k

endwhile

t+1→t

endwhile

输出当前最优解

8.7遗传算法与预测控制

预测控制是利用当前控制量及系统输出量，对系统下一时刻的运行实施优化的一种控制方式，既然是预测，未来的控制效果只能推断，遗传算法起因于生物的进化，恰好在已知过去发展的基础上推知未来的发展趋势，显然，遗传算法用于预测控制，有其独特的优势。

从计算方法的角度观察，预测是一种离散优化的计算方法。

由于对未来的无知，预测控制需要在线求解一个系列的方程组，用数学式子表述成求解有约束非线性规划：

minJ=J［Ui，Yi］式中，J是目标函数，Ui和Yi分别是优化域上的控制序列和输出序列，且

Ui∈E

Yi∈Ω

yi+k=f[yi+k－1，ui+k－1]

Ui={ui，ui+1，…，ui+p－1}

Yi={yi+1，yi+2，…，yi+p}

目标函数J表达了优化区间内的控制变量及输出变量的性能指标，ui和yi分别是Ui和Yi的元素，f[·]表示对象的预测模型,Ω是输出序列的约束条件，E是控制序列的约束条件。有约束非线性规划体现在：性能指标、预测模型和约束条件可以是线性的，但通常是非线性的。

预测模型如果是比较复杂的非线性结构，就无法直接用控制量求出输出的解析表示，只能通过惩罚函数将模型约束引入到目标函数中，把控制量和输出量当做优化变量求解。考虑到约束个数与优化长度有关，优化规模将被扩大。

在用遗传算法求解优化问题时，首先要解决编码问题。如果优化问题位于多维连续性空间内，码长就显得较大，不利于编程计算。为此，本例提供了两层浮点遗传算法，这是一种改进了的遗传算法。两层浮点遗传算法的基本思路是产生多个有相同数目的种群，它们分别具有不同的初始条件和操作参数。每个种群各自独立完成一定数量的遗传计算，种群内使用浮点方式处

理多维连续优化，然后实施种群间的遗传运算。

优化时域上的控制变量是求解问题的优化值，每当产生一个控制序列，便能获得一个相应的输出序列。每个控制序列事实上形成了遗传算法中的染色体，控制量必然存在一个

上限及下限，即

ui∈［umin，umax］

上下限区间形成了遗传算法的搜索空间。对于遗传算法中的适应度函数，处理依据如下：

遗传算法的进展方向总是使优化过程向适应度增加的方向。如果是极小化，应当使控制输入量作用下的性能指标减小，则相应个体的适应度增大。约束越限的处理方法是使用惩罚函数，越限越严重，适应度越小。当前约束宜紧，后续约束宜松。

预测控制遗传算法在线求解最优的步骤如下：

(1)随机产生N×n组控制序列形成初始种群。

(2)计算各种群内个体适应度，计算的参数有：

①根据预测模型及控制序列，计算被控对象的响应；

②根据控制序列和响应，计算性能指标；③计算控制序列和响应是否满足约束条件；

④根据性能指标和约束条件计算适应度。

(3)检查适应度是否满足要求，若满足要求则结束计算过程，若不满足则转(2)，继续遗传操作。

考虑的预测控制目标为预测控制对象为

y1k=0.6y1(k－1)+sin(y2(k－1))+u1(k－1)u2(k－1)

y2k=0.7y1(k－1)+0.5y2(k－1)+0.6y1(k－1)u1(k－1)+u2(k－1)约束条件是

|u1k|≤1

|u2k|≤1

|y1k|≤2

|y2k|≤2

式中，k=1，2，…，p，初始条件是

y10=y20=0

本例预测控制是一个双输入双输出非线性过程，希望输出能跟踪设定值。遗传算法所用初始值设定如下：

种群个体数为100，分成10×10组，预估步数p=3，交叉概率p=取0.7～1之间的随机数，变异概率pm取0～0.1之间的随机数，例如pc=0.9，pm=0.05，适应值函数选择为f=0.75x。

仿真计算70个采样周期，每隔10个采样周期就改变一次设定值，用以考察算法的跟踪效果。可取的设定值[y1set，y2set]分别有：

[1，1]，[0.5，1]，[0.5，1.5]，[0，1.5]，[1，0.5]仿真中用两层遗传算法和普通浮点遗传算法分别计算50次的平均最优适应值，将适应值与相应进化代数之间的关系绘制成曲线，如图8-5所示。从进化过程图可以看到，两层遗传算法的寻优率高一些，尤其在种群个体小的时候更为明显。图8-5进化过程在两层遗传算法直接优化作用下，能够获得两条曲线，一条是控制作用u随时间的变化曲线，另一条是输出响应y随时间的变化曲线，两条曲线分别如图8-6和图8-7所示。从

图中可以看到，控制量能够按照下列变化及时得到调整：

一个变化是设定值的变化；另一个变化是被控对象结构参数的变化。

仿真结果表明，用遗传算法实施预测控制具有策划简单、计算效率高的优点，对于实际工业过程的复杂性与适时性要求，遗传算法是一种较好的选择。图8-6控制作用曲线图8-7输出响应曲线

8.8遗传算法与神经网络

物流网络中的配送中心，是货物从产生企业到批发零售商之间的中转站，是集中或分散货物，使货物流转的中间存储仓库。考虑到配送中心所处的地理位置，交通便利条件、

运费成本低廉等因素，货物周转过程中存在一个配送中心选址的问题。

本节试图用遗传算法与神经网络求解此类问题的最优解。

选用的神经网络模型为Hopfield模型。该模型在求解组合优化问题方面有明显的优势。设物流网络中心有n个用户s1，s2，…，sn。选其中k个确定各自配送范围，使配送费用最小，由此确定的数学模型为

式中，

表示配送中心si到用户j处所需单位运输费用；表示si到用户j处的配送量；

表示设置配送中心所需固定费用及管理费用；dj是用户j的需求数量；是配送中心si的容量；Z是配送总费用，minZ是使Z为最小，是算法求解的最终目标。

上述三个式子中，第一个是目标管理，使经费为最小，第二、三个是约束条件，表示配送网络的总供给往往不等于总的需求，但不宜差别过大，否则将造成积压与浪费。为此可考虑设置一个虚拟用户，设为第n+1个用户，存在一个虚拟配送中心sk+1。好处是相应数学模型可全部使用等号：运费

需求量

存储容量

用等号书写的目的，在于将约束条件不等式改写成约束条件等式，但对总费用目标函数没有任何影响。

现构造Hopfield能量函数(用E表示)，令式中，A为目标系数，B、C为惩罚项系数。有了能量函数，遗传算法可按以下步骤进行：第一步，产生初始种群。对于n个用户的物流网络，使用n位二进制位串表示不同的染色体个体。例如第i位的值，为0表示该用户未被选中成为配送中心；为1就表示该位地址是配送中心选中的地址。随机产生L个染色体Gi(i=1，2，…，L)，每个染色体彼此并不相同。

第二步，判断停止进化。

对染色体Gi组成的种群求最小配送费用Zi，取Gi的适应度函数fi反映了Gi在优胜劣汰过程中的优劣程度。判断迭代的代数是否达到要求的代数。如果不是，继续往下执行；如果是，停止进化，选择性能好的染色体作为结果。第三步，优胜劣汰。

将种群中L个染色体的适应度按从大到小的顺序排列。排在最前面的S个染色体性能优越，各产生两个子代。排在中间的染色体将产生一个染色体。排在最后面的S个染色体性能最差，将被淘汰。

第四步，交叉变异。

选择交换率Lc=0.6L，Lc个染色体随机产生且在种群中均匀分布。将Lc个染色体交叉：对选中的Gi、Gj，随机取两点交换元素，产生两个新的子代，检查新子代值为1的位数，如果它与初始种群中染色体值为1的位数不相等，则看谁大谁小，进行不同的变异操作。若前者大后者小，将差值中为1的位置0，反之将为0的位置1，同时返回第二步。现有物流配送网络实例如下。设12个需求点的距离列于表8-10中，题目要求从中选择3个作为配送中心地址。各配送中心的容量假设均为13个单位。从第1点到第12点设置成配送中心的费用各不相同，经过预测算，相对费用分别为15、21、13、10、15、10、10、10、10、24、10、10。用遗传算法确定的配送方案如表8-11所示，其优化配送中心为2、6、10，最终综合费用为177。

使用常规优化方法进行迭代，算得的配送中心为4、