第5章遗传进化算法课件.ppt

1、第第5 5章章 遗传进化算法遗传进化算法基本概念、基本原理、基本算法基本概念、基本原理、基本算法达尔文的生物进化论与遗传算法达尔文的生物进化论与遗传算法遗传生命之特征或性状的传承n 染色体（chromosome)n DNA(deoxyribonucleic acid)n RNA(ribonucleic acid)n 双螺旋结构n 基因(gene)n 四进制编码（A,T,C,G)n 复制(reproduction)n 交叉(crossover)n 变异(mutation)达尔文的生物进化论与遗传算法达尔文的生物进化论与遗传算法 进化进化“物竞天择，优胜劣汰，适者生存物竞天择，优胜劣汰，适者生存”

2、n遗传信息（基因）寓于染色体，染色体决定生物特征，遗传信息（基因）寓于染色体，染色体决定生物特征，特征决定对环境的适应度。特征决定对环境的适应度。n遗传与进化之过程均发生在遗传与进化之过程均发生在DNADNA之上。之上。n遗传通过繁殖完成，繁殖由基因复制实现，复制的基遗传通过繁殖完成，繁殖由基因复制实现，复制的基本方式是交叉重组。本方式是交叉重组。n交叉与变异产生新的物种，变异是物种进化的保证。交叉与变异产生新的物种，变异是物种进化的保证。n适应度决定物种的存活，适应性强者遗传机会更大。适应度决定物种的存活，适应性强者遗传机会更大。n竞争是物种进化的促进剂。竞争是物种进化的促进剂。n有竞争就有

3、选择，自然选择是进化的基本规律有竞争就有选择，自然选择是进化的基本规律遗传进化算法的基本概念遗传进化算法的基本概念n编码、个体与种群编码、个体与种群(encoding,individual and population)n适应度函数适应度函数(fitness function)n选择算子选择算子(selection operator)n交叉算子交叉算子(crossover operator)n变异算子变异算子(mutation operator)遗传编码遗传编码(genetic encoding)n二进制编码二进制编码n灰度编码灰度编码n可拼接可拼接/可分解编码可分解编码n实数编码实数编码n可

4、变精度实数编码可变精度实数编码n符号编码符号编码n混乱编码混乱编码n混合编码混合编码编码编码(encoding)与解码与解码(decoding)TnLxxxXaaaA,2121式中式中A A 所表示的有限字符串称为优化变量所表示的有限字符串称为优化变量X X 的遗传（染色体）的遗传（染色体）编码，记为编码，记为 ,A,A 中的中的字符称为基因，字符所有字符称为基因，字符所有可能的取值称为等位基因，可能的取值称为等位基因，L L 称为编码长度；称为编码长度；X X 称为称为A A 的解的解码，记为码，记为 。AeX1 XeA 编码的重要性：编码的重要性：1 1）基因的排列决定遗传操作的作用方式；

5、）基因的排列决定遗传操作的作用方式；2 2）决定搜索的难度与复杂性；）决定搜索的难度与复杂性；3 3）决定问题求解的精度。）决定问题求解的精度。个体空间与种群空间个体空间与种群空间LiaaaaAHiLL,2,1,21LaaaA21一个问题可行解的遗传编码称为个体，或者说一群染色体一个问题可行解的遗传编码称为个体，或者说一群染色体的组合称为个体的组合称为个体设设 表示等位基因，表示等位基因，为给定的编码长度，则所有基为给定的编码长度，则所有基因可能排列成的编码构成整个个体空间因可能排列成的编码构成整个个体空间对任何正整数对任何正整数 m，乘积，乘积 称称为为m 阶种群空间，其中的元素称为阶种群空

6、间，其中的元素称为 m 阶种群阶种群LmLLmLHHHH21个体空间中的一群个体称为一个种群个体空间中的一群个体称为一个种群L与编码相关的定义与编码相关的定义1 1）编码格式）编码格式 e e 是从是从H HL L 到到 的一个映射，且对任何的一个映射，且对任何 ，存存在唯一在唯一 与之对应的解与之对应的解码码 ；2 2）当且仅当任何）当且仅当任何 唯一对应一个个体唯一对应一个个体A A，则称编码，则称编码格式是正则的；格式是正则的；3 3）如果一个）如果一个L L 编码编码 和一个和一个K K 编码编码 的拼接的拼接 有意义且是一个有意义且是一个L+KL+K码，则称其码，则称其为是可拼接的；

7、反之则称之为是可分解的为是可拼接的；反之则称之为是可分解的 LiaaaaAHiLL,2,1,21设个体空间为：设个体空间为：nTnRxxxX,21其可行解空间为：其可行解空间为：LaaaA21KbbbB21KLbbbaaaBA2121 AeX1LHA AeX1二进制编码二进制编码二进制编码：以字符二进制编码：以字符0和和1为等位基因的定长字符串编码。为等位基因的定长字符串编码。对实数对实数xi 给定编码精度给定编码精度 ，取，取 mi 为满足为满足 的最小整数，则的最小整数，则 mi 长的长的0-1字符串字符串唯一对应实数唯一对应实数xi，定义为：，定义为：nibaxiii,2,1,12211

8、1iimiimjjjiiabbaAex121bbbbAiimmiTnxxxX,21设设且且niabimiii,2,1,12二进制编码示例二进制编码示例Xi 的的 二进制编码个体：二进制编码个体：0000000000000 0 0000000000001 0.0009767 0001000100010 1.0880438 1111111111111 8.0001497设设001.00009767.01819281208,001.0,0,813iix 则则mimi=13=13，从中任选从中任选n个个体可构成一个种群个个体可构成一个种群,任选任选m次就可构成次就可构成m个种群个种群二进制编码的优缺点

9、二进制编码的优缺点优点：二进制编码简明、通用、易于各种进化操作。优点：二进制编码简明、通用、易于各种进化操作。缺点：不具备正则性，可能破坏可行解空间的拓扑连续性。缺点：不具备正则性，可能破坏可行解空间的拓扑连续性。NiigHaidyxD1min),(elseyxdiii01 对于高维、连续优化问题存在离散化误差，高精度要求对于高维、连续优化问题存在离散化误差，高精度要求 将产生很长的编码；不便于表达反映所求问题的特定知识。将产生很长的编码；不便于表达反映所求问题的特定知识。例如例如:在整数集在整数集0,100,10中的数中的数7 7和和8 8最邻近，但它们的二进制编码最邻近，但它们的二进制编码

10、01110111和和10001000的海明距离为的海明距离为4 4，最远，最远.海明距离：两染色体编码所有相应位置中取不同数值的位置数海明距离：两染色体编码所有相应位置中取不同数值的位置数灰度编码灰度编码n假定已有二进制编码：假定已有二进制编码：其修正（灰度）编码：其修正（灰度）编码：n两者相互转换公式：两者相互转换公式：n即：即：n其中其中 表示异或运算，即：表示异或运算，即：121aaaaALL121ggggGLL1,2,1,1LLiaagagiiiLL1,2,1,1LLigaagaiiiLLbababa,0,1GTATAG1或二进制与灰度编码转换示例二进制与灰度编码转换示例n二进制编码二

11、进制编码 0 1 1 1(7),1 0 0 0(8),1 0 1 1(11),1 1 0 0(12),前两前两个编码的海明距离为个编码的海明距离为4,后两个编码海明距离为后两个编码海明距离为3.n其相应灰度编码为其相应灰度编码为0 0 1 1,1 0 1 1,1 0 0 1,1 1 0 1,显然前后两个显然前后两个编码的海明距离均为编码的海明距离均为1,新编码保持了原空间的连续性新编码保持了原空间的连续性.n其灰度变换计算其灰度变换计算:其逆变换计算其逆变换计算:111111010011112122313344aagaagaagag111111100011112122313344gaagaag

12、aaga个基因，个基因，和和分别表示第分别表示第表示染色体，表示染色体，xixiiliui这里这里表示染色体的第表示染色体的第个基因解空间的上限和下限。个基因解空间的上限和下限。实数与二进制的混合编码实数与二进制的混合编码,.,21Nxxxx)(iiiilulx1,.,2.0,1.0,0设设采用混合编码产生初始种群的算法如下：采用混合编码产生初始种群的算法如下：(1)(1)随机产生一个随机数随机产生一个随机数 ，实数与二进制的混合编码实数与二进制的混合编码 1,.,2.0,1.0,0)(iiiilulx,.,21Nxxxx；(2),(2),重复重复 N N 次，就次，就产生一个染色体产生一个染

13、色体(3)(3)重复步骤重复步骤(1)(1)、(2)M(2)M次，就产生一个包含次，就产生一个包含 M M 个染色个染色 体的初始种群。体的初始种群。适应度函数适应度函数(fitness function)LAHAAFAJ)()(max1 1）对应某种生物群体在给定环境下的适应性度量；）对应某种生物群体在给定环境下的适应性度量；2 2）优化变量）优化变量X X对应生物群体中的个体；对应生物群体中的个体；3 3）遗传进化对应于实现该优化过程的演化过程。）遗传进化对应于实现该优化过程的演化过程。适应度函数是评价群体中个体好坏的标准，是模拟自适应度函数是评价群体中个体好坏的标准，是模拟自然选择的唯一

14、依据。从而适应度函数选取的优劣直接影然选择的唯一依据。从而适应度函数选取的优劣直接影响遗传算法的收敛速度及能否找到最优解。响遗传算法的收敛速度及能否找到最优解。适应度函数的设计原则适应度函数的设计原则n早熟现象早熟现象：遗传算法运行初期阶段，群体中或许会出：遗传算法运行初期阶段，群体中或许会出现适应度极好的个体，最终这些个体可能会充斥整个现适应度极好的个体，最终这些个体可能会充斥整个群体，使用于产生新个体作用较大的交叉操作失去作群体，使用于产生新个体作用较大的交叉操作失去作用，从而使得群体的多样性降低，遗传算法提前收敛用，从而使得群体的多样性降低，遗传算法提前收敛到某个局部最优解。到某个局部最

15、优解。n适应度函数的选取应尽量的避免早熟现象，即适应度函数的选取应尽量的避免早熟现象，即缩小缩小适适应度较高的个体与其他个体适应度之间的应度较高的个体与其他个体适应度之间的差异差异，限制，限制其复制数量以维护群体的多样性其复制数量以维护群体的多样性 适应度函数的设计原则适应度函数的设计原则n退化现象：退化现象：遗传算法运行后期阶段，群体越来越集中，遗传算法运行后期阶段，群体越来越集中，个体之间的差异减小，相互之间的竞争力也随即减弱。个体之间的差异减小，相互之间的竞争力也随即减弱。这必然造成个体被选择到下一代中的概率接近，使进这必然造成个体被选择到下一代中的概率接近，使进化过程失去竞争力，退化为

16、随机选择过程。化过程失去竞争力，退化为随机选择过程。n适应度函数的选取应该克服这种退化现象，使算法在适应度函数的选取应该克服这种退化现象，使算法在运行后期阶段能够运行后期阶段能够扩大扩大最佳个体适应度与其它个体适最佳个体适应度与其它个体适应度之间的应度之间的差异差异，提高个体之间的竞争性。，提高个体之间的竞争性。适应度函数的常用变换适应度函数的常用变换n线性尺度变换线性尺度变换n乘幂尺度变换乘幂尺度变换n指数尺度变换指数尺度变换 LHAAJAJ,LKHAAJAJ,LHAAJAJ,exp适应度函数设计举例适应度函数设计举例 设计一个分段的非线性变换的适应度函数设计一个分段的非线性变换的适应度函数

17、 这里这里 ,表示变换过后的适应度函数；表示变换过后的适应度函数；表示种群的适应度比例值表示种群的适应度比例值 、和和 均为常数。其均为常数。其中中 的主要作用一方面用于保证的主要作用一方面用于保证 恒为正，另一恒为正，另一方面调控不同个体被选择的概率；方面调控不同个体被选择的概率；为幂指数，可在为幂指数，可在1-1-1.21.2之间选择；之间选择；、为为0-10-1的实数，是不同函数的切换的实数，是不同函数的切换条件。条件。avgTavgavgfxffxffxfCxf)()()(log(10)(*)(*xfavgfCTC)(*xfT选择算子选择算子(selection operator)n模

18、拟模拟“优胜劣汰、适者生存优胜劣汰、适者生存”自然进化原理自然进化原理n决定父代种群中个体以多大可能被选中遗传到下一代的进化操作。决定父代种群中个体以多大可能被选中遗传到下一代的进化操作。n选择原则：选择原则：1 1）依据适应度评价；）依据适应度评价；2 2）选择最优个体；）选择最优个体；3 3）避免无效搜索；）避免无效搜索；4 4）快速搜索到最优解。）快速搜索到最优解。n定义：选择算子定义：选择算子 S S 是一个随机映射，它满足：是一个随机映射，它满足：0,2,1,)2:,)1XBMNXSBPNjXJXJXXBXNXBHHSXXSHXjiiMLNLNL有的种群对任何满足对任何选择算子选择算

19、子(selection operator)n比例选择（轮盘赌选择）比例选择（轮盘赌选择）n变尺度比例选择变尺度比例选择n杰出者选择杰出者选择n期望生存数选择期望生存数选择n确定式采样选择确定式采样选择n排序选择排序选择nBoltzmannBoltzmann局部退火选择局部退火选择n种群偏差度选择种群偏差度选择n排除算子选择排除算子选择n基于正交表的选择基于正交表的选择比例选择比例选择 01,2,1,2,1,11211NIjNkkjjjiMjjNkkjjjiNLXJXJXnNIIjMiXYPXBMNYBPXXSYYYXSYMXXXXnXJXJXnXYPHX不是齐次种群，则总有，因为个个体组成中选

20、择独立、重复地从中重复的次数在表示以概率：给定种群轮盘赌选择轮盘赌选择（Roulette Wheel Selection）n每一个染色体适应度函数值决定其在轮盘上面积的大小。此面积大小与轮盘总面积的比率就染色体被挑选至下一代之概率，也就是在轮盘上任意取n点，面积比率较大者，选择并复制至交叉池（Mating Pool）的个体数相对较多。P1P2PNPN-1轮盘赌选择示例轮盘赌选择示例设有四个染色体Cll，C24，C310，C415，其适应度函数（Fitness Function）为 F（X）X，相应之适应函数值为f11，f24，f310，f415，占据轮盘的面积，Pcl1/300.03，Pc24

21、/300.13，Pc310/300.33，Pc415/300.51，其中Cl与C2所占比率较小，可能在下一代被C3及C4所取代。交叉算子交叉算子(crossover operator)定义：模拟生物的自然进化过程中，两个同源染色体通定义：模拟生物的自然进化过程中，两个同源染色体通过交配重组形成新染色体，产生新个体和物种的进化操过交配重组形成新染色体，产生新个体和物种的进化操作，称为交叉算子。作，称为交叉算子。交叉操作步骤：交叉操作步骤：1.1.从种群个体中分别任意选取两个个体组成母体对。从种群个体中分别任意选取两个个体组成母体对。2.2.对任一母体对独立重复实施交叉操作生成子代个体。对任一母体

22、对独立重复实施交叉操作生成子代个体。交叉算子交叉算子(crossover operator)n单点交叉单点交叉n多点交叉多点交叉n均匀交叉均匀交叉n洗牌交叉洗牌交叉n部分匹配交叉部分匹配交叉n顺序交叉顺序交叉n循环交叉循环交叉单点交叉单点交叉n在母体个体变量排序中任选一交叉点，并以该点为分界在母体个体变量排序中任选一交叉点，并以该点为分界相互交换交叉点后的变量，形成新的子代个体。例如：相互交换交叉点后的变量，形成新的子代个体。例如：母个体对：母个体对：1 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 1 0 子代个体对：子代个体对：1 0 1 1 0 1 1 1 1 0

23、0 1 0 0 1 0 0 1 0 1顺序交叉顺序交叉n两个母体交叉时，通过选择母体两个母体交叉时，通过选择母体1 1的一部分，并保留母体的一部分，并保留母体2 2中相应码位中相应码位的相对顺序，而生成子个体。顺序交叉操作能保留母体的排列并融合的相对顺序，而生成子个体。顺序交叉操作能保留母体的排列并融合不同排列的有序结构单元。不同排列的有序结构单元。母个体对：母个体对：1 2 3 4 5 6 7 8 91 2 3 4 5 6 7 8 9 4 5 2 1 8 7 6 9 3 4 5 2 1 8 7 6 9 3 子代个体对的两个交叉点之间的中间段保持不变：子代个体对的两个交叉点之间的中间段保持不变

24、：X X X|4 5 6 7|X XX X X|4 5 6 7|X X X X X|1 8 7 6|X X X X X|1 8 7 6|X X 子个体子个体1 1由由2 2的排序的排序9393-45452-182-187676中去掉中间段中去掉中间段45674567获得获得 2 12 1 8 8|4 5 6 7|4 5 6 7|9 39 3 子个体子个体2 2由由1 1的排序的排序8 89 9-1 1234234-5 56767之间去掉中间段之间去掉中间段18761876获得获得 3 43 4 5 5|1 8 7 6|1 8 7 6|9 9 2 2 可变精度的交叉可变精度的交叉n在实数编码的两

25、个母体交叉时，首先选择一个交换点，然后将母体两在实数编码的两个母体交叉时，首先选择一个交换点，然后将母体两个染色体交叉点右边的部分交换，接着再计算交换点的线性组合，这个染色体交叉点右边的部分交换，接着再计算交换点的线性组合，这样产生两个新的子代个体。即：样产生两个新的子代个体。即：母体对：母体对：子代个体对：子代个体对：其中：其中：,.,.,21Nixxxxx,.,.,21Niyyyyy,.,.,121Niiyyxxxx,.,.,121Niixxyyyy)(iiiixyxx)(iiiiluly1,.,2.0,1.0,0iliuixixiy分别表示第分别表示第i个基因解空间的上限和下限，个基因解

26、空间的上限和下限，是一个随机数，是一个随机数，iy新的基因新的基因由随机变量由随机变量和和产生，产生，由于在不同的代中，它的值是不同的，所以基因取值精度就可以扩展。由于在不同的代中，它的值是不同的，所以基因取值精度就可以扩展。变异算子变异算子(mutation operator)n定义：模拟种群内部分个体染色体中基因发生突变，产生定义：模拟种群内部分个体染色体中基因发生突变，产生新的个体和物种的进化操作，称为变异（突变）算子。新的个体和物种的进化操作，称为变异（突变）算子。n变异的作用是可以恢复一些在遗传进化过程中丢失的部分变异的作用是可以恢复一些在遗传进化过程中丢失的部分基因，增加种群内个体

27、的多样性，避免进化的早熟和局部基因，增加种群内个体的多样性，避免进化的早熟和局部收敛。收敛。n操作步骤：操作步骤：1）在母体经过交叉产生的子代个体中按一定（极小的）在母体经过交叉产生的子代个体中按一定（极小的）概率挑选出少量的个体；概率挑选出少量的个体；2）对挑选出的个体中的部分基因，按一定的方式进行变）对挑选出的个体中的部分基因，按一定的方式进行变异，产生新的物种。异，产生新的物种。变异算子变异算子(mutation operator)n点变异点变异n均匀变异均匀变异n正态变异正态变异n非一致变异非一致变异n大规模反馈式突变大规模反馈式突变二进制编码的点变异二进制编码的点变异n按某一概率独立

28、地改变个体的某几位基因的进化操作按某一概率独立地改变个体的某几位基因的进化操作 变异前的个体变异前的个体 1 1 0 0 1 0 1 1 1 0 1 1 变异后的个体变异后的个体 1 1 1 1 1 1 1 1 0 0 1 0 种群中选择进行变异的个体的概率一般很小大约种群中选择进行变异的个体的概率一般很小大约0.01-0.001,因此对优秀的个体的影响较小因此对优秀的个体的影响较小.实数编码的高精细变异实数编码的高精细变异n变异时，单个染色体的两个基因被随机地选择进行凸组合变异时，单个染色体的两个基因被随机地选择进行凸组合的变异。假设染色体的变异。假设染色体:的第的第i个基因和第个基因和第k

29、个基因被选择进行变异，变异生成新的个基因被选择进行变异，变异生成新的染色体为染色体为:其中其中 ，两个基因分别为：两个基因分别为：这里这里 为随机数，为随机数，。这种变异方式的目的就是为了增强变异的精细调节能力。这种变异方式的目的就是为了增强变异的精细调节能力。,.,.,.,2Nkiixxxxxx,.,.,.,2Nkiixxxxxx kiixxx)1(kikkxx)1(ixkx1,.,2.0,1.0,0大规模反馈式突变大规模反馈式突变n采用轮盘赌选择和最优个体保存策略，随着进化的进行，采用轮盘赌选择和最优个体保存策略，随着进化的进行，某些好的个体产生的后代越来越多，整个种群适应度也越某些好的个

30、体产生的后代越来越多，整个种群适应度也越来越高，这时种群中基因的多样性变得越来越差来越高，这时种群中基因的多样性变得越来越差,以至于以至于进化进行非常缓慢甚至完全停滞，种群陷入早熟。进化进行非常缓慢甚至完全停滞，种群陷入早熟。n大规模反馈式突变大规模反馈式突变,就是用随机生成的新的个体代替通过就是用随机生成的新的个体代替通过突变被消灭的个体，可以大大提高种群的多样性，同时保突变被消灭的个体，可以大大提高种群的多样性，同时保持了种群大小的稳定持了种群大小的稳定。n假设通过反馈式突变的产生的新的染色体的数目为假设通过反馈式突变的产生的新的染色体的数目为L L，那，那么就利用混合编码的方式随机产生么

31、就利用混合编码的方式随机产生L L个新的染色体，代替个新的染色体，代替种群中原来适应度值排在最后的种群中原来适应度值排在最后的L L个染色体。个染色体。Step1.Step1.（编码与初始化）确定种群规模，交叉与变异概率，（编码与初始化）确定种群规模，交叉与变异概率，初始种群随机生成；初始种群随机生成；Step2.Step2.（个体评价）估计种群中各个体的适应度；（个体评价）估计种群中各个体的适应度；Step3.Step3.（种群进化）（种群进化）3.1 3.1 选择（母体）选择（母体）3.2 3.2 交叉交叉 依交叉概率形成中间个体；依交叉概率形成中间个体；3.3 3.3 变异变异 对中间个

32、体依变异概率执行变异，形成候选对中间个体依变异概率执行变异，形成候选个体；个体；3.4 3.4 选择（子代）从候选个体中依适应度选择合适个体选择（子代）从候选个体中依适应度选择合适个体组成新种群；组成新种群；Step4.Step4.（终止校验）满足终止准则，输出最优解，否则继（终止校验）满足终止准则，输出最优解，否则继续转步续转步3 3。标准遗传进化算法的基本运算过程标准遗传进化算法的基本运算过程Holland1969,De Jong1975,Goldberg1989n计算的典型执行技巧研究：计算的典型执行技巧研究：n搜索机理研究：搜索机理研究：n收敛性理论研究：收敛性理论研究：n复杂性理论研

33、究；复杂性理论研究；n有效性理论研究。有效性理论研究。在原始的遗传算法中存在着早熟收敛、收敛速度慢、在原始的遗传算法中存在着早熟收敛、收敛速度慢、计算效率低、精度不高、搜索能力弱、容易陷入局部计算效率低、精度不高、搜索能力弱、容易陷入局部最优等问题，因此展开如下众多基本理论研究。最优等问题，因此展开如下众多基本理论研究。遗传计算的典型执行技巧遗传计算的典型执行技巧n适应值共享策略适应值共享策略n并行（群体分组、搜索空间分解）实现并行（群体分组、搜索空间分解）实现策略策略n混合（神经网络、梯度下降、列表寻优、混合（神经网络、梯度下降、列表寻优、贪婪变换）策略贪婪变换）策略n自适应（稳态、动态、混

34、合编码、选择）自适应（稳态、动态、混合编码、选择）策略；策略；杰出者选择遗传算法杰出者选择遗传算法Step1.Step1.（初始化）确定交叉与变异概率，初始种群随机生成（初始化）确定交叉与变异概率，初始种群随机生成,置置t=0t=0；Step2.Step2.（个体评价）估计种群中各个体的适应度；（个体评价）估计种群中各个体的适应度；Step3.Step3.（种群进化）（种群进化）3.1 3.1 独立从当前种群中选择出独立从当前种群中选择出(N-1)(N-1)对母体对母体 3.2 3.2 依交叉概率对依交叉概率对(N-1)(N-1)对母体进行交叉运算对母体进行交叉运算,形成形成(N-1)(N-1

35、)对中间个体；对中间个体；3.3 3.3 对对(N-1)(N-1)个中间个体依变异概率执行变异，形成个中间个体依变异概率执行变异，形成t+1t+1代种群的前代种群的前 (N-1)(N-1)候选个体；候选个体；3.4 3.4 从候选个体中依适应度选择一个最优个体从候选个体中依适应度选择一个最优个体 ,并令并令t+1t+1代代种群的第种群的第N N个个体个个体Step4.Step4.（终止校验）满足终止准则，输出最优解（终止校验）满足终止准则，输出最优解 ，否，否则继续转步则继续转步3 3。NLnHxxxX0,0,00211,1,1121txtxtxN txtxN 1 tx1tx结合神经网络的混合

36、遗传算法结合神经网络的混合遗传算法(1)n对于一类组合优化问题对于一类组合优化问题n已知已知H0pfield神经网络神经网络,收敛的稳定态对应该问题的局部最优解收敛的稳定态对应该问题的局部最优解 nnninjniiijiijxxxXCxbxxXE1,1,21min21111 0mod0mod,mod00,1,1sgn,sgn11ntntNnttIxxxtIitxtIibtxtxinjijiji其中结合神经网络的混合遗传算法结合神经网络的混合遗传算法(2)nStep1(初始化初始化)随机生成初始种群随机生成初始种群 ,指定交叉和变指定交叉和变异概率及终止规则异概率及终止规则,设设t=0并定义适应

37、度函数并定义适应度函数nStep2(种群进化种群进化)2.1 依初始种群的适应度从初始种群中选择依初始种群的适应度从初始种群中选择N对母体对母体;2.2 对所选出的每一对母体执行交叉运算对所选出的每一对母体执行交叉运算,生成生成N个中间个体个中间个体;2.3 对交叉生成的中间个体执行变异对交叉生成的中间个体执行变异,生成生成N个候选个体个候选个体;2.4 依每一个候选个体为初始态激活依每一个候选个体为初始态激活Hopfield神经网络神经网络,产生出产生出N个局部最优态个局部最优态,并构成新一代种群并构成新一代种群;nStep3(终止校验终止校验)如满足终止准则如满足终止准则,停止计算并输出最佳个体得到近停止计算并输出最佳个体得到近似全局最优解似全局最优解.XEXJ NX1,10