第4章 遗传算法

第四章遗传算法第四章遗传算法4．1从生物进化到进化计算4．2标准遗传算法(SGA)4．3遗传算法的特点4．4遗传算法理论研究4．5遗传算法的应用一个人的战争，嗨呀嗨呀人多力量大吼吼吼优化搜索问题简介—单个体搜索优化搜索问题简介—单个体搜索优化搜索问题简介—单个体搜索优化搜索问题简介—群体搜索优化搜索问题简介—群体搜索优化搜索问题简介—群体搜索优化搜索问题简介—群体搜索优化搜索问题简介—群体搜索如何实现高效的群体搜索呢？初始群体的产生新解的产生机制（如何根据老解产生新解？）新解的接受策略（贪心接受or概率接受？）个体间协作机制（如何共享知识？）生物圈是一个自然进化（趋优）的系统。•什么是进化？•生物为什么会进化？（生物是如何进化的？）•只有生物能自然进化吗？•人工系统能否自然进化？如何实现？4.1从生物进化到进化计算达尔文的进化论：自然选择，适者生存孟德尔与摩根的遗传学理论：基因是决定生物特征的最基本的物质单元，基因在染色体上以一定的顺序和结构排列，每个基因有特殊的位置并控制生物的某些特性。基因组合的特异性决定了生物体的多样性，基因结构的稳定性保证了生物物种的稳定性，而基因的杂交和变异使生物进化成为可能。4.1从生物进化到进化计算生物进化过程的发生需要四个基本条件：1）存在由多个生物个体组成的种群；2）生物个体之间存在着差异，或群体具有多样性；不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。3）生物能够自我繁殖；4）存在竞争（资源有限，优胜劣汰）。4.1从生物进化到进化计算生物群体的进化机制包括三种基本形式：1)自然选择2)杂交3)突变外界对生物的评价反映了生物的生存价值和机会。4.1从生物进化到进化计算生物进化过程本质上是一种优化过程。进化计算（EvolutionaryComputation,EC）包括四个重要分支：1）遗传算法（GeneticAlgorithm，GA），由JohnH.Holland教授等提出；2）进化规划（EvolutionaryProgramming,EP），由LawrenceJ.Fogel等人提出；3）进化策略（EvolutionaryStrategies,ES），由IngoRechenberg和Hans-PaulSchwefel提出。4）遗传规划（GeneticProgramming，GP），由JohnR.Koza教授提出。4.1从生物进化到进化计算4.2标准遗传算法产生背景：模拟自然物种进化过程的人工系统遗传算法的6个基本要素：1）编码策略；2）初始群体的产生；3）适应度函数的设计；4）遗传算子设计；5）控制参数设定6）迭代终止条件4.2标准遗传算法标准遗传算法流程：1．编码（问题解在算法中的表示形式）2．产生设定规模的初始群体3．评估每个个体的适应度4．WHILE未满足迭代终止条件DO1.选择2.交叉3.变异4.适应度评估5．ENDDOrecombination10001010111001101001mutationxfphenotypespaceGeneticAlgorithm00111110011000101011populationofgenotypescodingschemefitnessselection110011000101011100011011101001100100101110010010111001101001遗传算法的基本描述遗传编码定义：由问题空间向GA编码空间的映射称为编码，而由编码空间向问题空间的映射成为译码。问题编码一般应满足以下三个原则：1）完备性（completeness）：问题空间中的所有点都能能成为GA编码空间中的点的表现型2）健全性（soundness）：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解。3）非冗余性（non-redundancy）：染色体和潜在解必须一一对应。遗传算法的基本描述遗传编码根据模式定理，DeJong进一步提出了较为客观明确的编码评估准则，称之为编码原理。具体可以概括为两条规则：1）有意义积木块编码规则：编码应易于生成与所求问题相关的短距和低阶的积木块。2）最小字符集编码规则：编码应采用最小字符集，以使问题得到自然、简单的表示和描述。遗传算法的基本描述1．二进制编码•连续实函数的二进制编码设一维连续实函数采用长度维L的二进制字符串进行定长编码，建立位串空间：k=1,2,…,K;l=1,2,…,L;K=2L表示精度为。将个体又从位串空间转换到问题空间的译码函数的公式定义为：],[),(vuxxfKLxxxS,,,21),,,(21kLkkkaaax1,0kla)12/()(Luvx],[}1,0{:vuL)2(12),,,(121LjjLkjLkLkkkauvuaaax4.1遗传算法的基本描述2．其他编码1)大字符集编码（相对于二进制编码）2)序列编码（TSP）3)实数编码4)树编码5)自适应编码6)乱序编码遗传算法的基本描述群体设定1。初始群体的设定一般来讲，初始群体的设定可以采用如下的策略：1)根据问题固有知识，设法把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。2)先随机生成一定数目的个体，然后从中挑出最好的个体加入到初始群体中。这一过程不断重复，直到初始群体中个体数达到了预定的规模。遗传算法的基本描述群体设定2。群体规模的设定•根据模式定理，若群体规模为M，则遗传操作可从这M个个体中生成和检测O(M3)个模式，并在此基础上不断形成和优化积木块，直到找到最优解。•群体规模N，模式阶i，被采样的模式数量的期望Mi(i=1,2,…,)之间满足如下关系：•群体规模一般不随迭代而变化，但也不绝对。iiNM2遗传算法的基本描述适应度函数（评价函数）1。目标函数映射成适应度函数2。适应度函数定标1）线性定标（linearscaling）f’=af+b2）截断（sigmatruncation）3）乘幂标f’=fK4）指数定标f’=exp(-bf))('cfff遗传算法的基本描述遗传算子包括三个基本遗传算子（geneticoperator）：选择，交叉和变异。这三个遗传算子具有一些特点：（1）这三个算子的操作都是随机化操作，因此，群体中个体向最优解迁移的规则是随机的。这种随机化操作和传统的随机搜索方法是有区别的。遗传操作进行的是高效有向的搜索，而不是如一般随机搜索方法所进行的无向搜索。（2）遗传操作的效果和所取的操作概率、编码方法、群体大小，以及适应度函数的设定密切相关。（3）三个基本算子的操作方法和操作策略随具体求解问题的不同而异。或者说，是和个体的编码方式直接相关。遗传算子一、选择（selection）算子从群体中选择优胜个体，淘汰劣质个体的操作叫选择。选择算子有时又称为再生算子（reproductionoperator）。选择即从当前群体中选择适应度值高的个体以生成配对池（matingpool）的过程。遗传算子一、选择（selection）算子1、适应度比例选择首先计算每个个体的适应度值，然后计算出此适应度值在群体适应度值总和中所占的比例，表示该个体在选择过程中被选中的概率。选择过程体现了生物进化过程中“适者生存，优胜劣汰”的思想。对于给定的规模为n的群体，个体的适应度值为，其选择概率为：问题：易出现未成熟收敛},,,{21naaaPPaj)(jafnjafafapniijjs,,2,1,)()()(1遗传算子一、选择（selection）算子2、Boltzmann选择在群体进化过程中，不同阶段需要不同地选择压力。早期阶段选择压力较小，我们希望较差地个体也有一定的生存机会，使得群体保持较高地多样性；后期阶段，选择压力较大，我们希望GA缩小搜索邻域，加快当前最优解的改善速度。为了动态调整群体进化过程中的选择压力，Goldberg设计了Boltzmann选择方法。个体选择概率为：njeeapniTafTafjsij,,2,1,)(1/)(/)(遗传算子一、选择（selection）算子3、排序选择排序选择方法是将群体中个体按其适应度值由大到小的顺序排成一个序列，然后将事先设计好的序列概率分配给每个个体。排序选择不利用个体适应度值绝对值的信息，可以避免群体进化过程中的适应度标度变换。遗传算子一、选择（selection）算子3、排序选择对于给定的规模为n的群体，并且满足个体适应度值降序排列。假设当前群体最佳个体a1在选择操作后的期望数量为，即；最差个体an在选择操作后的期望数量为。其它个体的期望数量按等差序列计算，故排序选择概率为},,,{21naaaP)()()(21nafafaf1pnnpn11njj)1(1)()1(jnjjnjjnnapjs,,2,1)),1(1)((1)(遗传算子一、选择（selection）算子4、联赛选择（tournamentselection）•基本思想：从当前群体中随机选择一定数量的个体（放回或者不放回），将其中适应值最大的个体放入配对池中。反复执行这一过程，直到配对池中的个体数量达到设定的值。•联赛规模用q表示，也称q-联赛选择。•联赛选择与个体的适应度值有间接关系，注重适应度值大小的比较。•联赛规模一般取q=2。遗传算子一、选择（selection）算子5、精英选择•如果下一代群体的最佳个体适应度值小于当前群体最佳个体的适应度值，则将当前群体最佳个体或者适应度值大于下一代最佳个体适应度值的多个个体直接复制到下一代，随机替代和替代最差的下一代群体中的相应数量的个体。•精英选择是群体收敛到全局最优解的一种基本保障。遗传算子一、选择（selection）算子6、稳态选择•稳态选择操作中，仅有少量个体按适应度值比例选择方法被选择，通过遗传操作生成新的个体。新个体放回到群体中时，随机替代等量的旧个体，或者替代等量的最差的旧个体。•Holland将稳态选择方法应用于分类器规则学习中，最大程度继承已获得的规则，实现增量学习。•DeJong将下一代群体中生成的与上一代不同的新个体所占的比例称为“代沟”（generationgap）。代沟越大，说明新个体的生成比例越高，群体搜索新的编码空间的能力（探索）越强。遗传算子二、交叉（Crossover）算子•交叉算子是模仿自然界有性繁殖的基因重组过程，其作用在于将已有的优良基因遗传给下一代个体，并生成包含更复杂基因结构的新个体。•交叉操作一般分为以下几个步骤：1）根据交叉概率，从配对池中随机取出要配对的一对个体；2）根据位串长度L，对要交叉的一对个体，随机选取[1,L-1]中一个或多个整数k作为交叉位置；3）实施交叉操作，配对个体在交叉位置处，相互交换各自的部分内容，从而形成新的一对个体。遗传算子二、交叉（Crossover）算子1、一点交叉（one-pointcrossover）位串A：1101|1010位串B：1011|0101位串A’：1101|0101位串B’：1011|1010遗传算子二、交叉（Crossover）算子1、两点交叉（two-pointcrossover）位串A：11|011|010位串B：10|110|101位串A’：11|110|010位串B’：10|011|101遗传算子二、交叉（Crossover）算子1、多点交叉（multi-pointcrossover）位串A：11|01|10|10位串B：10|11|01|01位串A’：11|11|10|01位串B’：10|01|01|10遗传算子二、交叉（Crossover）算子1、一致交叉一致交叉即染色体位串上的每一位按相同概率进行随机均匀交叉。一致交叉算子生成的新个体位：操作描述如下：：，x是取值为[0，1]上符合均匀分布的随机变量。Laaas112111''''Laa