《遗传算法的基本原理参考学习培训课件》由会员分享，可在线阅读，更多相关《遗传算法的基本原理参考学习培训课件（70页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 遗传算法的基本原理遗传算法的基本原理 4.1 4.1 遗传算法的基本描述遗传算法的基本描述 4.2 4.2 遗传算法的模式理论遗传算法的模式理论4.3 遗传算法与其他搜索算法的比较遗传算法与其他搜索算法的比较4.4 4.4 遗传算法的高级实现遗传算法的高级实现4.1.1标准遗传算法流程：标准遗传算法流程：1编码编码2初始群体的生成初始群体的生成3适应度评估检测适应度评估检测4WHILEDO1.选择选择2.交叉交叉3.变异变异4.适应度评估检测适应度评估检测5ENDDO4.1遗传算法的基本描述遗传算法的基本描述选择选择交叉交叉当前代当前代中间代中间代下一代下一代4.1遗传算法的基本
2、描述遗传算法的基本描述4.1.3遗传编码遗传编码定定义义：由由问问题题空空间间向向GA编编码码空空间间的的映映射射称称为为编编码码，而而由由编码空间向问题空间的映射成为编码空间向问题空间的映射成为译码译码。问题编码一般应满足以下三个原则：问题编码一般应满足以下三个原则：1）完完备备性性（completeness）：问问题题空空间间中中的的所所有有点点都都能能能成为能成为GA编码空间中的点的表现型编码空间中的点的表现型2）健健全全性性（soundness）：GA编编码码空空间间中中的的染染色色体体位位串串必须对应问题空间中的某一潜在解。必须对应问题空间中的某一潜在解。3）非非冗冗余余性性（non
3、-redundancy）：染染色色体体和和潜潜在在解解必必须须一一对应。一一对应。4.1遗传算法的基本描述遗传算法的基本描述4.1.3遗传编码遗传编码根根据据模模式式定定理理，DeJong进进一一步步提提出出了了较较为为客客观观明明确确的的编编码码评评估估准准则则，称称之之为为编编码码原原理理。具具体体可可以以概概括括为为两两条规则：条规则：1）有有意意义义积积木木块块编编码码规规则则：编编码码应应易易于于生生成成与与所所求求问问题题相关的短距和低阶的积木块。相关的短距和低阶的积木块。2）最最小小字字符符集集编编码码规规则则：编编码码应应采采用用最最小小字字符符集集，以以使使问题得到自然、简单
4、的表示和描述。问题得到自然、简单的表示和描述。4.1遗传算法的基本描述遗传算法的基本描述1二进制编码二进制编码1）连续实函数的二进制编码）连续实函数的二进制编码设一维连续实函数设一维连续实函数采采用用长长度度维维L的的二二进进制制字字符符串串进进行定长编码，建立位串空间：行定长编码，建立位串空间：k=1,2,K;l=1,2,L;K=2L表示精度为表示精度为。将个体又从位串空间转换到问题空间的译码函数将个体又从位串空间转换到问题空间的译码函数的公式定义为：的公式定义为：4.1遗传算法的基本描述遗传算法的基本描述对于对于n维连续函数维连续函数，各各维维变变量量的的二二进进制制编编码码位位串串的的长
5、长度度为为li,那那么么x的的编编码码从从左左到到右右依依次次构构成总长度为成总长度为的二进制编码位串。相应的的二进制编码位串。相应的GA编码空间为：编码空间为：，K=2L该空间上的个体位串结构为该空间上的个体位串结构为对于给定的二进制编码位串对于给定的二进制编码位串sk,位段译码函数的形式为位段译码函数的形式为，i=1,2,n4.1遗传算法的基本描述遗传算法的基本描述2其他编码其他编码1)大字符集编码（相对于二进制编码）大字符集编码（相对于二进制编码）2)序列编码（序列编码（TSP）3)实数编码实数编码4)树编码树编码5)自适应编码自适应编码6)乱序编码乱序编码 4.1遗传算法的基本描述遗传
6、算法的基本描述4.1.4群体设定群体设定1。初始群体的设定。初始群体的设定一般来讲，初始群体的设定可以采用如下的策略：一般来讲，初始群体的设定可以采用如下的策略：1)根根据据问问题题固固有有知知识识，设设法法把把握握最最优优解解所所占占空空间间在在整整个个问问题题空空间间中中的的分分布布范范围围，然然后后，在在此此分分布布范范围围内内设设定定初始群体。初始群体。2)先先随随机机生生成成一一定定数数目目的的个个体体，然然后后从从中中挑挑出出最最好好的的个个体体加加入入到到初初始始群群体体中中。这这一一过过程程不不断断重重复复，直直到到初初始始群体中个体数达到了预定的规模。群体中个体数达到了预定的
7、规模。4.1遗传算法的基本描述遗传算法的基本描述4.1.4群体设定群体设定2。群体规模的设定。群体规模的设定根根据据模模式式定定理理，若若群群体体规规模模为为M，则则遗遗传传操操作作可可从从这这M个个个个体体中中生生成成和和检检测测O(M3)个个模模式式，并并在在此此基础上不断形成和优化积木块，直到找到最优解。基础上不断形成和优化积木块，直到找到最优解。群群体体规规模模N N，模模式式阶阶i i，被被采采样样的的模模式式数数量量的的期期望望M Mi i(i=1,2,)(i=1,2,)之间满足如下关系：之间满足如下关系：群体规模一般不随迭代而变化，但也不绝对。群体规模一般不随迭代而变化，但也不绝
8、对。4.1遗传算法的基本描述遗传算法的基本描述4.1.5适应度函数（评价函数）适应度函数（评价函数）1。目标函数映射成适应度函数。目标函数映射成适应度函数2。适应度函数定标。适应度函数定标1）线性定标线性定标（linearscaling）f=af+b2）截断截断（sigmatruncation）3）乘幂标乘幂标f=fK4）指数定标指数定标f=exp(-bf)4.1遗传算法的基本描述遗传算法的基本描述4.1.6遗传算子遗传算子包包括括三三个个基基本本遗遗传传算算子子（geneticoperator）：选选择择，交交叉叉和和变变异异。这三个遗传算子具有一些特点：这三个遗传算子具有一些特点：（1）这
9、这三三个个算算子子的的操操作作都都是是随随机机化化操操作作，因因此此，群群体体中中个个体体向向最最优优解解迁迁移移的的规规则则是是随随机机的的。需需要要强强调调的的是是，这这种种随随机机化化操操作作和和传传统统的的随随机机搜搜索索方方法法是是有有区区别别的的。遗遗传传操操作作进进行行的的是是高高效效有有向向的的搜搜索索，而不是如一般随机搜索方法所进行的无向搜索。而不是如一般随机搜索方法所进行的无向搜索。（2）遗遗传传操操作作的的效效果果和和所所取取的的操操作作概概率率、编编码码方方法法、群群体体大大小小，以以及适应度函数的设定密切相关。及适应度函数的设定密切相关。（3）三三个个基基本本算算子子
10、的的操操作作方方法法和和操操作作策策略略随随具具体体求求解解问问题题的的不不同同而而异。或者说，是和个体的编码方式直接相关。异。或者说，是和个体的编码方式直接相关。4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子从从群群体体中中选选择择优优胜胜个个体体，淘淘汰汰劣劣质质个个体体的的操操作作叫叫选选择择。选选 择择 算算 子子 有有 时时 又又 称称 为为 再再 生生 算算 子子（reproductionoperator）。选选择择即即从从当当前前群群体体中中选选择择适适应应度度值值高高的的个个体以生成体以生成配对池配对池（matingpool）的过程。的过程。4.1.6
11、遗传算子遗传算子一、选择一、选择（selection）算子算子1、适应度比例选择、适应度比例选择首首先先计计算算每每个个个个体体的的适适应应度度值值，然然后后计计算算出出此此适适应应度度值值在在群群体体适适应应度度值值总总和和中中所所占占的的比比例例，表表示示该该个个体体在在选选择择过过程程中中被被选选中中的的概概率率。选选择择过过程程体体现现了了生生物物进进化化过过程程中中“适适者者生生存存，优优胜胜劣劣汰汰”的的思想。思想。对对于于给给定定的的规规模模为为n的的群群体体 ，个个体体 的的适适应应度值为度值为 ，其选择概率为：，其选择概率为：问题：易出现未成熟收敛问题：易出现未成熟收敛4.1
12、.6遗传算子遗传算子一、选择一、选择（selection）算子算子2、Boltzmann选择选择在在群群体体进进化化过过程程中中，不不同同阶阶段段需需要要不不同同地地选选择择压压力力。早早期期阶阶段段选选择择压压力力较较小小，我我们们希希望望较较差差地地个个体体也也又又一一定定地地生生存存机机会会，使使得得群群体体保保持持较较高高地地多多样样性性；后后期期阶阶段段，选选择择压压力力较较大大，我我们们希希望望GA缩缩小小搜搜索索邻邻域域，加加快快当当前前最最优优解解的的改改善善速速度度。为为了了动动态态调调整整群群体体进进化化过过程程中中的的选选择择压压力力，Goldberg设设计计了了Bolt
13、zmann选选择择方方法法。个个体体选择概率为：选择概率为：4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子3、排序选择、排序选择排排序序选选择择方方法法是是将将群群体体中中个个体体按按其其适适应应度度值值由由大大到到小小的的顺顺序序排排成成一个序列，然后将事先设计好的序列概率分配给每个个体。一个序列，然后将事先设计好的序列概率分配给每个个体。排排序序选选择择不不利利用用个个体体适适应应度度值值绝绝对对值值的的信信息息，可可以以避避免免群群体体进进化化过程中的适应度标度变换。过程中的适应度标度变换。4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子
14、3、排序选择、排序选择对对于于给给定定的的规规模模为为n n的的群群体体 ，并并且且满满足足个个体体适适应应度值降序排列度值降序排列 。假假设设当当前前群群体体最最佳佳个个体体a a1 1在选择操作后的期望数量为在选择操作后的期望数量为 ，即，即；最最差差个个体体a an n在在选选择择操操作作后后的的期期望望数数量量为为 。其其它它个个体体的的期期望望数数量量按按等等差差序序列计算列计算，故现在排序选择概率为故现在排序选择概率为 4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子4、联赛选择、联赛选择（tournamentselection）基基本本思思想想：从从当当前
15、前群群体体中中随随机机选选择择一一定定数数量量的的个个体体（放放回回或或者者不不放放回回），将将其其中中适适应应值值最最大大的的个个体体放放入入配配对对池池中中。反反复复执执行行这这一一过过程，直到配对池中的个体数量达到设定的值。程，直到配对池中的个体数量达到设定的值。联赛规模用联赛规模用q q表示，也称表示，也称q q-联赛选择。联赛选择。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。联赛选择与个体的适应度值由间接关系，注重适应度值大小的比较。联赛规模一般取联赛规模一般取q q=2=2。4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子5、精英选择、精英选
16、择如如果果下下一一代代群群体体的的最最佳佳个个体体适适应应度度值值小小于于当当前前群群体体最最佳佳个个体体的的适适应应度度值值，则则将将当当前前群群体体最最佳佳个个体体或或者者适适应应度度值值大大于于下下一一代代最最佳佳个个体体适适应应度度值值的的多多个个个个体体直直接接复复制制到到下下一一代代，随随机机替替代代和和替替代代最最差差的的下一代群体中的相应数量的个体。下一代群体中的相应数量的个体。精英选择是群体收敛到全局最优解的一种基本保障。精英选择是群体收敛到全局最优解的一种基本保障。4.1.6遗传算子遗传算子一、选择一、选择（selection）算子算子6、稳态选择、稳态选择稳稳态态选选择择操操作作中中，仅仅有有少少量量个个体体按按适适应应度度值值比比例例选选择择方方法法被被选选择择，通通过过遗遗传传操操作作生生成成新新的的个个体体。新新个个体体放放回回到到群群体体中中时时，随随机机替替代代等量的旧个体，或者替代等量的最差的旧个体。等量的旧个体，或者替代等量的最差的旧个体。Holland将将稳稳态态选选择择方方法法应应用用于于分分类类器器规规则则学学习习中中，最最大大程程度度继继承承
