第6章遗传算法及其应用(导论)报告

IntroductionofArtificialIntelligence第6章遗传算法及其应用教材：王万良《人工智能导论》（第3版）高等教育出版社，2011.22第6章遗传算法及其应用遗传算法(GA)是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的重要技术之一。本章首先详细介绍遗传算法的基本算法，然后介绍双倍体、双种群、自适应等比较典型的改进遗传算法，最后简单介绍了遗传算法在生产调度中的应用。在此基础上，读者可以进一步学习遗传算法以及其他进化算法的内容。3第6章遗传算法及其应用6.1遗传算法的产生与发展6.2遗传算法的基本算法6.3遗传算法的改进算法6.4遗传算法的应用4第6章遗传算法及其应用6.1遗传算法的产生与发展6.2遗传算法的基本算法6.3遗传算法的改进算法6.4遗传算法的应用56.1遗传算法的产生与发展遗传算法（geneticalgorithms，GA）：一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。66.1遗传算法的产生与发展6.1.1遗传算法的生物背景6.1.2遗产算法的基本思想6.1.3遗产算法的发展历史6.1.4设计遗产算法的基本原则与内容76.1.1遗传算法的生物学背景适者生存：最适合自然环境的群体往往产生了更大的后代群体。生物进化的基本过程：染色体(chromosome)：生物的遗传物质的主要载体。基因(gene)：扩展生物性状的遗传物质的功能单元和结构单位。基因座（locus）：染色体中基因的位置。等位基因（alleles）：基因所取的值。86.1.2遗传算法的基本思想生物遗传概念遗产算法中的应用适者生存目标值比较大的解被选择的可能性大个体（Individual）解染色体（Chromosome）解的编码（字符串、向量等）基因（Gene）解的编码中每一分量适应性（Fitness）适应度函数值群体（Population）根据适应度值选定的一组解（解的个数为群体的规模）婚配（Marry）交叉（Crossover）选择两个染色体进行交叉产生一组新的染色体的过程变异（Mutation）编码的某一分量发生变化的过程96.1.2遗传算法的基本思想遗传算法的基本思想：在求解问题时从多个解开始，然后通过一定的法则进行逐步迭代以产生新的解。最优化问题遗传算法目标函数可行解一组解适应度函数染色体种群106.1.3遗传算法的发展历史1962年，Fraser提出了自然遗传算法。1965年，Holland首次提出了人工遗传操作的重要性。1967年，Bagley首次提出了遗传算法这一术语。1970年，Cavicchio把遗传算法应用于模式识别中。1971年，Hollstien在论文《计算机控制系统中人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法。1975年，美国J.Holland出版了《自然系统和人工系统的适配》；DeJong完成了重要论文《遗传自适应系统的行为分析》。20世纪80年代以后，遗传算法进入兴盛发展时期。116.1.4遗传算法设计的基本内容编码方案：怎样把优化问题的解进行编码。适应度函数：怎样根据目标函数构建适应度函数。选择策略：优胜劣汰。控制参数：种群的规模、算法执行的最大代数、执行不同遗传操作的概率等。遗传算子：选择、交叉、变异。算法终止准则：规定一个最大的演化代数，或算法在连续多少代以后解的适应值没有改进。12第6章遗传算法及其应用6.1遗传算法的产生与发展6.2遗传算法的基本算法6.3遗传算法的改进算法6.4遗传算法的应用136.2遗传算法的基本算法遗传算法的五个基本要素：参数编码初始群体的设定适应度函数的设计遗传操作设计控制参数设定146.2遗传算法的基本算法6.2.1编码6.2.2群体设定6.2.3适应度函数6.2.4选择6.2.5交叉6.2.6变异6.2.7遗传算法的一般步骤156.2.1编码1.位串编码一维染色体编码方法：将问题空间的参数编码为一维排列的染色体的方法。二进制编码：用若干二进制数表示一个个体，将原问题的解空间映射到位串空间B={0，1}上，然后在位串空间上进行遗传操作。（1）二进制编码166.2.1编码(1)二进制编码（续）优点：类似于生物染色体的组成，算法易于用生物遗传理论解释，遗传操作如交叉、变异等易实现；算法处理的模式数最多。缺点：①相邻整数的二进制编码可能具有较大的Hamming距离，降低了遗传算子的搜索效率。15：0111116：10000②要先给出求解的精度。③求解高维优化问题的二进制编码串长，算法的搜索效率低。176.2.1编码1.位串编码（2）Gray编码Gray编码:将二进制编码通过一个变换进行转换得到的编码。二进制串n...21Grayn...21二进制编码Gray编码1111kkkkkGray编码二进制编码)2(mod1kiik186.2.1编码2.实数编码采用实数表达法不必进行数制转换，可直接在解的表现型上进行遗传操作。多参数映射编码的基本思想：把每个参数先进行二进制编码得到子串，再把这些子串连成一个完整的染色体。多参数映射编码中的每个子串对应各自的编码参数，所以，可以有不同的串长度和参数的取值范围。191.初始种群的产生6.2.2群体设定（1）根据问题固有知识，把握最优解所占空间在整个问题空间中的分布范围，然后，在此分布范围内设定初始群体。（2）随机产生一定数目的个体，从中挑选最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。202.种群规模的确定6.2.2群体设定模式定理表明：若群体规模为M，则遗传操作可从这M个个体中生成和检测个模式，并在此基础上能够不断形成和优化积木块，直到找到最优解。3M群体规模太小，遗传算法的优化性能不太好，易陷入局部最优解。群体规模太大，计算复杂。211.将目标函数映射成适应度函数的方法6.2.3适应度函数若目标函数为最大化问题，则若目标函数为最小化问题，则)())((xfxfFit)(1))((xfxfFit将目标函数转换为求最大值的形式,且保证函数值非负！若目标函数为最大化问题，则若目标函数为最小化问题，则minmin()()(())0fxCfxCFitfx其他情况maxmax()()(())0CfxfxCFitfx其他情况222.适应度函数的尺度变换在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题（deceptiveproblem）。6.2.3适应度函数过早收敛：缩小这些个体的适应度，以降低这些超级个体的竞争力。停滞现象：改变原始适应值的比例关系，以提高个体之间的竞争力。适应度函数的尺度变换（fitnessscaling）或者定标：对适应度函数值域的某种映射变换。232.适应度函数的尺度变换(续）（1）线性变换：baff6.2.3适应度函数minfffaavgavgminminffffbavgavgavgavgmultfffCamax)1(avgavgavgmultffffCfbmaxmax)(,avgavgffavgmultfCfmax满足满足最小适应度值非负242.适应度函数的尺度变换(续）（2）幂函数变换法：Kffaffe6.2.3适应度函数（3）指数变换法：256.2.4选择1.个体选择概率分配方法选择操作也称为复制（reproduction）操作：从当前群体中按照一定概率选出优良的个体，使它们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值：个体适应度越高，其被选择的机会就越多。266.2.4选择1.个体选择概率分配方法（1）适应度比例方法（fitnessproportionalmodel）或蒙特卡罗法（MonteCarlo）Miiisiffp1各个个体被选择的概率和其适应度值成比例。个体被选择的概率为：i276.2.4选择1.个体选择概率分配方法（2）排序方法（rank-basedmodel）①线性排序：J.E.Baker群体成员按适应值大小从好到坏依次排列：个体按转盘式选择的方式选择父体Nxxx,,,21iipx分配选择概率)1(MMbiapi286.2.4选择1.个体选择概率分配方法（2）排序方法（rank-basedmodel）②非线性排序：Z.Michalewicz将群体成员按适应值从好到坏依次排列，并按下式分配选择概率：MiMiqqqpMii1,,2,1)1()1(11296.2.4选择1.个体选择概率分配方法（2）排序方法（rank-basedmodel）可用其他非线性函数来分配选择概率，只要满足以下条件：Miip11)2(满足则且若iMMpxfxfxfxxxP),(...)()(,)1(212,1Mppp21306.2.4选择2.选择个体方法（1）转盘赌选择（roulettewheelselection）按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例。产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉。第1轮产生一个随机数：0.81第2轮产生一个随机数：0.32316.2.4选择2.选择个体方法（2）锦标赛选择方法（tournamentselectionmodel）锦标赛选择方法：从群体中随机选择个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。随机竞争方法（stochastictournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。326.2.4选择2.选择个体方法最佳个体（elitistmodel）保存方法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。（3）最佳个体保存方法336.2.5交叉1.基本的交叉算子（1）一点交叉（single-pointcrossover）一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。（2）二点交叉（two-pointcrossover）346.2.5交叉2.修正的交叉方法部分匹配交叉PMX：GoldbergD.E.和R.Lingle(1985)231765489A645932178B231932489A645765178B356.2.6变异（1）位点变异：群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动。（2）逆转变异：在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中。（3）插入变异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间。（4）互换变异：随机选取染色体的两个基因进行简单互换。（5）移动变异：随机选取一个基因，向左或者向右移动一个随机位数。366.2.7遗传算法的一般步骤问题初始化染色体种群计算每个个体的适应值根据适应值选择串进行复制交叉变异确定表示问题解答的染色体（编码）输出最优解是否满足终止条件376.2.7遗传算法的一般步骤（1）使用随机方法或者其它方法，产生一个有N个染色体的初始群体pop(1)，；1:t（2）对群体中的每一个染色体popi(t)，计算其适应值