遗传算法基本原理说课讲解.ppt

《遗传算法基本原理说课讲解.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第四章遗传算法的基本原理4.1遗传算法的基本描述4.2遗传算法的模式理论4.3遗传算法与其他搜索算法的比较4.4遗传算法的高级实现4.1.1标准遗传算法流程：1．编码2．初始群体的生成3．适应度评估检测4．WHILE<未满足迭代终止条件>DO1.      选择2.      交叉3.      变异4.适应度评估检测5．ENDDO4.1遗传算法的基本描述选择交叉当前代中间代下一代4.1遗传算法的基本描述4.1.3遗传编码定义：由问题空间向GA编码空间的映射称为编码，而由编码空间向问题空间的映射成为译码。问题编码一般应满足以下三个原则：1）完备性（completeness）：问

2、题空间中的所有点都能能成为GA编码空间中的点的表现型2）健全性（soundness）：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解。3）非冗余性（non-redundancy）：染色体和潜在解必须一一对应。4.1遗传算法的基本描述4.1.3遗传编码根据模式定理，DeJong进一步提出了较为客观明确的编码评估准则，称之为编码原理。具体可以概括为两条规则：1）有意义积木块编码规则：编码应易于生成与所求问题相关的短距和低阶的积木块。2）最小字符集编码规则：编码应采用最小字符集，以使问题得到自然、简单的表示和描述。4.1遗传算法的基本描述1．二进制编码1）连续实函数的二进制

3、编码设一维连续实函数采用长度维L的二进制字符串进行定长编码，建立位串空间：k=1,2,…,K;l=1,2,…,L;K=2L表示精度为。将个体又从位串空间转换到问题空间的译码函数的公式定义为：4.1遗传算法的基本描述对于n维连续函数，各维变量的二进制编码位串的长度为li,那么x的编码从左到右依次构成总长度为的二进制编码位串。相应的GA编码空间为：，K=2L该空间上的个体位串结构为对于给定的二进制编码位串sk,位段译码函数的形式为，i=1,2,…,n4.1遗传算法的基本描述2．其他编码1)    大字符集编码（相对于二进制编码）2)    序列编码（TSP）3)    实数编码4)

4、    树编码5)    自适应编码6)    乱序编码4.1遗传算法的基本描述4.1.4群体设定1。初始群体的设定一般来讲，初始群体的设定可以采用如下的策略：根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始群体中个体数达到了预定的规模。4.1遗传算法的基本描述4.1.4群体设定2。群体规模的设定根据模式定理，若群体规模为M，则遗传操作可从这M个个体中生成和检测O(M3)个模式，并在此基础上不断形成和优化积木块，直到找到最优解。群体规

5、模N，模式阶i，被采样的模式数量的期望Mi(i=1,2,…,)之间满足如下关系：群体规模一般不随迭代而变化，但也不绝对。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）这三个算子的操作都是随机化操作，因此，群体中个体向最优解迁移

6、的规则是随机的。需要强调的是，这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无向搜索。（2）遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。（3）三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。4.1.6遗传算子一、选择（selection）算子从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子（reproductionoperator）。选择即从当前群体中选择适应度值高的个体以生成配对池（matingpool）

7、的过程。4.1.6遗传算子一、选择（selection）算子1、适应度比例选择首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想。对于给定的规模为n的群体，个体的适应度值为，其选择概率为：问题：易出现未成熟收敛4.1.6遗传算子一、选择（selection）算子2、Boltzmann选择在群体进化过程中，不同阶段需要不同地选择压力。早期阶段选择压力较小，我们希望较差地个体