工程应用软计算课件第3章遗传算法.ppt

第三章第三章遗传算遗传算法法理学院应用数学系理学院应用数学系立体化教学资源系列立体化教学资源系列工程应用软计算工程应用软计算工程应用软计算工程应用软计算遗传算法遗传算法序言序言 3.1 遗传遗传算法的生物算法的生物学背景学背景 3.2 遗传遗传算法算法3.3 遗传遗传算法算法MatlabMatlab应应用用举举例例 3.4 遗传遗传算法算法应应用用实实例例 工程应用软计算工程应用软计算遗传算法遗传算法序言序言 遗传算法起源于对生物系统所进行的计算机模拟研遗传算法起源于对生物系统所进行的计算机模拟研究。它是借鉴生物学的自然选择和遗传机制，以种群究。它是借鉴生物学的自然选择和遗传机制，以种群搜索和种群中个体（染色体）之间的信息交换为策略搜索和种群中个体（染色体）之间的信息交换为策略的随机搜索优化算法。的随机搜索优化算法。一、一、遗传遗传算法的发算法的发展展 6060年代后，美国密执安大学的年代后，美国密执安大学的HollandHolland教授及其学生教授及其学生们受到这种启发，创造出基于生物遗传和进化机制的们受到这种启发，创造出基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术适合于复杂系统优化计算的自适应概率优化技术-遗传遗传算法。下面列出关键人物及主要贡献。算法。下面列出关键人物及主要贡献。20 20世纪世纪4040年代，就有学者开始研究如何利用计算机年代，就有学者开始研究如何利用计算机进行生物模拟的技术。进行生物模拟的技术。工程应用软计算工程应用软计算遗传算法遗传算法 （1 1）6060年代，年代，HollandHolland提出在研究和设计人工自适应系统提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。在自适应系统中的重要性。7070年代初，年代初，HollandHolland提出了遗传算法的基本定理提出了遗传算法的基本定理-模模式定理，从而奠定了遗传算法的理论基础。式定理，从而奠定了遗传算法的理论基础。1975 1975年，年，HollandHolland出版了第一本系统论述遗传算法和出版了第一本系统论述遗传算法和人工自适应系统的专著人工自适应系统的专著自然系统和人工系统的自适自然系统和人工系统的自适应性应性(Adaptation in Natural and Artificial(Adaptation in Natural and Artificial Systems)Systems)80 80年代，年代，Holland Holland 实现了第一个基于遗传算法的机实现了第一个基于遗传算法的机器学习系统器学习系统-分类器系统（分类器系统（CSCS）。）。工程应用软计算工程应用软计算遗传算法遗传算法 （2 2）1967 1967年，年，HollandHolland的学生的学生BaglayBaglay在其博士论文中首次在其博士论文中首次提出了提出了“遗传算法遗传算法”一词，并发表了第一篇应用论文。一词，并发表了第一篇应用论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，他发展了复制、交叉、变异、显性、倒位等遗传算子，使用了双倍体个体编码方法。这些都与目前的算子与使用了双倍体个体编码方法。这些都与目前的算子与方法相类似。创立了自适应遗传算法的概念。方法相类似。创立了自适应遗传算法的概念。（3 3）Jong Jong 1975 1975年年De JongDe Jong在其博士论文中结合模式定理进行了在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。工作框架，得到了一些重要且具有指导意义的结论。（4 4）。）。19891989年，年，GoldbergGoldberg出版了专著出版了专著搜索、优化搜索、优化和机器学习中的遗传算法（和机器学习中的遗传算法（Genetic Algorithms in Genetic Algorithms in Search,Optimization and Machine LearningSearch,Optimization and Machine Learning）。奠定了现代遗传算法的科学基础。奠定了现代遗传算法的科学基础。工程应用软计算工程应用软计算遗传算法遗传算法 （5 5）L.DavisL.Davis 1991 1991年，年，DavisDavis出版了出版了遗传算法手册遗传算法手册(Handbook of(Handbook of Genetic Algorithms)Genetic Algorithms)，包含了在科学计算、工程技，包含了在科学计算、工程技术和社会经济中的大量应用实例。本书为推广和普及术和社会经济中的大量应用实例。本书为推广和普及遗传算法的应用起到了重要的指导作用。遗传算法的应用起到了重要的指导作用。（6 6）1992 1992年，年，KozaKoza将遗传算法应用于计算机程序的优化设将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念计及自动生成，提出了遗传编程的概念GP(Genetic GP(Genetic Programming)Programming)。成功地应用于人工智能、机器学习、符。成功地应用于人工智能、机器学习、符号处理等方面。号处理等方面。综观整个遗传算法的发展历程，综观整个遗传算法的发展历程，2020世纪世纪7070年代是开年代是开始阶段，始阶段，2020世纪世纪8080年代是发展阶段，年代是发展阶段，2020世纪世纪9090年代是年代是高潮阶段。高潮阶段。工程应用软计算工程应用软计算遗传算法遗传算法二、二、遗传遗传算法的应算法的应用用 遗传算法提供了一种求解复杂系统优化问题的通用遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。应用领域：很强的鲁棒性，所以广泛应用于很多学科。应用领域：（1 1）函数优化。）函数优化。这是遗传算法的经典应用领域，也这是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。利用几何特是对遗传算法进行性能评价的常用算例。利用几何特性各具特色的各类函数评价算法性能，更能反映算法性各具特色的各类函数评价算法性能，更能反映算法的本质效果。而对于其它优化方法难于求解的非线性、的本质效果。而对于其它优化方法难于求解的非线性、多模型、多目标的函数优化问题，遗传算法可方便地多模型、多目标的函数优化问题，遗传算法可方便地得到较好的结果。得到较好的结果。（2 2）组合优化。）组合优化。成功地用于求解旅行商问题、背包成功地用于求解旅行商问题、背包问题、装箱问题、图形划分问题等组合优化问题、装箱问题、图形划分问题等组合优化NPNP完全问完全问题。题。工程应用软计算工程应用软计算遗传算法遗传算法 （3 3）生产调度问题。）生产调度问题。解决复杂调度问题：单件生产解决复杂调度问题：单件生产车间调度、流水线生产车间调度、生产规划、任务分车间调度、流水线生产车间调度、生产规划、任务分配等方面。配等方面。（4 4）自动控制。）自动控制。航空控制系统优化、参数辨识等。航空控制系统优化、参数辨识等。（5 5）图像处理。）图像处理。模式识别、图像恢复、图像边缘特模式识别、图像恢复、图像边缘特征提取等方面。征提取等方面。（6 6）机器人学。）机器人学。成功地用于移动机器人路径规划、成功地用于移动机器人路径规划、关节机器人运动轨迹规划、细胞机器人的结构优化和关节机器人运动轨迹规划、细胞机器人的结构优化和行为协调等方面。行为协调等方面。（7 7）人工生命。）人工生命。用于进化模型、学习模型、行为模用于进化模型、学习模型、行为模型、自组织模型等方面。型、自组织模型等方面。（8 8）遗传编程。）遗传编程。成功地用于人工智能、机器学习等。成功地用于人工智能、机器学习等。（9 9）机器学习。）机器学习。基于遗传算法的机器学习，特别是基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。分类器系统，在很多领域中都得到了应用。工程应用软计算工程应用软计算遗传算法遗传算法3.1 遗传遗传算法的生物算法的生物学背景学背景 一、一、生物遗传与生物遗传与进化进化 从生物进化论和遗传学角度看，主宰地球生物演化从生物进化论和遗传学角度看，主宰地球生物演化的因素主要有两方面的因素主要有两方面:（1 1）生命物质自身具有的生命物质自身具有的遗传遗传与与变异变异功能。功能。（2 2）自然界为生命存在方式提供的条件）自然界为生命存在方式提供的条件资源有限资源有限。遗传遗传能力使得物种得以延续，自然界的环境与资源能力使得物种得以延续，自然界的环境与资源限制会使生存能力弱的生物遭到淘汰；限制会使生存能力弱的生物遭到淘汰；变异变异会使生物会使生物的生存能力产生差异，使生物进化或产生新的物种。的生存能力产生差异，使生物进化或产生新的物种。地球上的生物的发展与进化，是生命物质自身具有地球上的生物的发展与进化，是生命物质自身具有的功能与自然界的功能与自然界相互作用的结果相互作用的结果。工程应用软计算工程应用软计算遗传算法遗传算法二、二、DNADNA复制与生复制与生物的遗传物的遗传 细胞是组成生命的最小单元，细胞通常由细胞膜、细胞是组成生命的最小单元，细胞通常由细胞膜、细胞质和细胞核三个部分组成。细胞质和细胞核三个部分组成。其中，细胞核内的染色体中的其中，细胞核内的染色体中的DNADNA分子是生物体携带分子是生物体携带遗传信息的基本物质。遗传信息的基本物质。DNA分子结构图分子结构图:工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法 DNA分子的主要分子的主要功能功能：（1 1）控制和指导各种蛋白质（包括各种酶）的合成。）控制和指导各种蛋白质（包括各种酶）的合成。（2 2）DNADNA本身的复制增生。本身的复制增生。DNA的自我复制也为遗传密码复制，按照碱基互补配的自我复制也为遗传密码复制，按照碱基互补配对原则，当生物体的一个母细胞对原则，当生物体的一个母细胞有丝分裂有丝分裂成两个子细成两个子细胞时，其中每个胞时，其中每个DNA分子也自体复制为两个一模一样的分子也自体复制为两个一模一样的子分子分存于两个子细胞中。子分子分存于两个子细胞中。基因：基因：一个有特定遗传功能的一个有特定遗传功能的DNADNA节段。节段。基因是控制生物遗传的物质单元，基因是控制生物遗传的物质单元，含成百上千的核苷酸，在染色体上含成百上千的核苷酸，在染色体上的排列次序代表遗传密码信息。的排列次序代表遗传密码信息。工程应用软计算工程应用软计算遗传算法遗传算法三三、DNADNA重组与重组与生物的进化生物的进化 地球上的生物都是经过了长期的进化而形成的。地球上的生物都是经过了长期的进化而形成的。复制形成的遗传不可能实现生物的进化复制形成的遗传不可能实现生物的进化。较高等生物的体细胞中，染色体都是成对存在的，较高等生物的体细胞中，染色体都是成对存在的，即染色体个数是双数，称为即染色体个数是双数，称为二倍体二倍体。有性生殖生物的生殖细胞只含半数染色体有性生殖生物的生殖细胞只含半数染色体-单倍体单倍体。减数分裂减数分裂：使得次级细胞由精细胞或卵原细胞分裂：使得次级细胞由精细胞或卵原细胞分裂成生殖细胞（精子或卵）的过程。成生殖细胞（精子或卵）的过程。（1 1）产生的细胞只得到半数染色体，即只获得每对）产生的细胞只得到半数染色体，即只获得每对基因中的一个；基因中的一个；（2 2）减数分裂中）减数分裂中,每对染色体中的一个染色单体与每对染色体中的一个染色单体与它并排的同源染色体的一个染色单体发生交叉它并排的同源染色体的一个染色单体发生交叉-差异；差异；工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法 （3 3）在减数分裂过程中出现染色体对间的随机组合）在减数分裂过程中出现染色体对间的随机组合,引起生殖细胞的多样性。引起生殖细胞的多样性。有性生殖物种内部大量的变异现象对于物种进化起有性生殖物种内部大量的变异现象对于物种进化起了极其重要的作用。了极其重要的作用。减数分裂中减数分裂中,染色单体的交换和随机组合是使生物染色单体的交换和随机组合是使生物生殖细胞发生变异的主要原因。生殖细胞发生变异的主要原因。综上，生物在遗传过程中发生的变异（主要是基因综上，生物在遗传过程中发生的变异（主要是基因重组、基因突变和染色体变异）与自然界生存条件的重组、基因突变和染色体变异）与自然界生存条件的结合，导致了世界生物的进化。结合，导致了世界生物的进化。基因的突变也是使生物得以变异进化的重要因素。基因的突变也是使生物得以变异进化的重要因素。工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法四四、生物遗传与生物遗传与进化对组合优化进化对组合优化问题的启发问题的启发 组合优化问题可以用二元集组合优化问题可以用二元集(S,f)(S,f)描述。其中描述。其中S S是解是解空间：由一切可能的解组成的有限集，空间：由一切可能的解组成的有限集，f f目标函数。目标函数。凸情况：凸情况：目标函数在目标函数在S S上只有一个最小（或最大）值。上只有一个最小（或最大）值。非凸情况：非凸情况：目标函数在目标函数在S S上存在多个极值点。上存在多个极值点。即在即在S S中找一个解，使目标函数值达最小（或最大）。中找一个解，使目标函数值达最小（或最大）。遗传算法的基本思想遗传算法的基本思想：模仿生物遗传进化的机制，：模仿生物遗传进化的机制，将组合优化问题的一组可行解视为染色体，该解对应将组合优化问题的一组可行解视为染色体，该解对应的目标函数值视为生物种群的优劣。的目标函数值视为生物种群的优劣。复制复制可以使优异解得以保留，可以使优异解得以保留，交换交换可行解中部分变可行解中部分变元，或采用元，或采用突变突变手段使部分变元置换，可以产生新的手段使部分变元置换，可以产生新的可行解。这种复制、交换、突变等操作，不断执行下可行解。这种复制、交换、突变等操作，不断执行下去，逐渐会逼近全局最优解。去，逐渐会逼近全局最优解。3.2 遗传遗传算法算法一、遗传算法一、遗传算法的基本步骤的基本步骤 例：例：用遗传算法求二次函数最大值。用遗传算法求二次函数最大值。工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法 解：解：（1 1）编码）编码 对于变量对于变量x x，不妨限定其仅取，不妨限定其仅取031031间的整数。间的整数。随机地产生几个初始值，假设得到随机地产生几个初始值，假设得到4 4个点个点 00101 00101，0110001100，1001110011，1110111101，组成初始群体，其数值分别为组成初始群体，其数值分别为5 5，1212，1919，2929。工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法（2 2）计算个体适应度）计算个体适应度 【注注】3 3号个体相对适应度最高，号个体相对适应度最高，4 4号个体适应度最低。号个体适应度最低。按照生物进化的按照生物进化的“自然选择，适者生存自然选择，适者生存”原则，复制原则，复制3 3号个体，删除号个体，删除4 4号个体。得新的群体号个体。得新的群体 00101,01100,10011,1001100101,01100,10011,10011，重新编为，重新编为1,2,3,41,2,3,4号个体。号个体。（3 3）遗传算子（复制、交换、突变）变换）遗传算子（复制、交换、突变）变换 a a 复制：复制：选择选择1 1号和号和3 3号个体进行交换，号个体进行交换，2 2号和号和4 4号个号个体进行交换，每个个体对第体进行交换，每个个体对第3 3位以后的字符片段与其位以后的字符片段与其配对个体的相应字符进行交换。配对个体的相应字符进行交换。工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法 b b 交换交换:交换前的旧个体交换前的旧个体 交换后的新个体交换后的新个体 交换后个体适应度交换后个体适应度工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法 c c、突变、突变 将将1 1号个体字符串的最后号个体字符串的最后1 1位进行突变，位进行突变，（4 4）运算终止准则判断）运算终止准则判断 10000 10000已为最优解。故原问题的最大值为已为最优解。故原问题的最大值为 x=16=16。1 1号：号：100010001 1 1000 10000 0 工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法 遗传算法的基本步骤遗传算法的基本步骤：步骤步骤1 1 对研究的变量或对象进行编码（形成字符对研究的变量或对象进行编码（形成字符 串），并随机地建立一个初始群体。串），并随机地建立一个初始群体。步骤步骤2 2 计算群体中诸个体的适应度。计算群体中诸个体的适应度。步骤步骤3 3 执行产生新群体的操作，包括：执行产生新群体的操作，包括：a a 复制：将适应度高的个体进行复制后添入复制：将适应度高的个体进行复制后添入 到新群体中，删除适应度低的个体；到新群体中，删除适应度低的个体；b b 交换：随机选出个体对，进行片段交叉换交换：随机选出个体对，进行片段交叉换 位，产生新个体对；位，产生新个体对；c c 突变：随机改变某个体的某个字符，而得突变：随机改变某个体的某个字符，而得 到新个体。到新个体。步骤步骤4 4 根据某种条件判断计算过程是否可以结根据某种条件判断计算过程是否可以结 束，如果不满足结束条件，则返回到步骤束，如果不满足结束条件，则返回到步骤 2 2，直到满足结束条件为止。，直到满足结束条件为止。工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法 遗遗传传算算法法是是模模仿仿生生物物遗遗传传与与进进化化过过程程而而得得到到的的一一种种随随机机优优化化方方法法，对对非非线线性性、多多极极值值的的寻寻优优是是一一种种有有效效方法。方法。遗遗传传算算法法对对问问题题的的可可行行解解编编码码，表表示示成成“染染色色体体”，随机随机产产生的一群生的一群“染色体染色体”组组成初始种群。成初始种群。由适由适应应度构成度构成优胜优胜劣汰、适者生存的劣汰、适者生存的“自然自然环环境境”。种种群群通通过过遗遗传传、交交换换、突突变变等等不不断断演演化化，产产生生出出新新的更加的更加优优良的种群。良的种群。经过经过若干代的若干代的进进化，最化，最终终求得适合求得适合问题问题的最的最优优解。解。工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法二、遗传算法的编码二、遗传算法的编码 编编码码是是应应用用遗遗传传算算法法中中首首先先要要解解决决的的问问题题。是是指指将将优优化化问问题题的的可可行行解解设设计计成成字字符符串串（视视为为染染色色体体）的的过过程。程。1 1、编码的主要方法、编码的主要方法 1)1)遗传遗传因子用因子用0/10/1码码表示。表示。2)2)实实数数编码编码（即字符串的每个位置都取（即字符串的每个位置都取实实数）。数）。3)3)符符号号编编码码（一一般般用用整整数数序序号号1,2,1,2,k表表示示的的字字符符进进行行编码编码 ）利利用用二二进进制制的的0/10/1双双字字符符编编码码具具有有一一定定优优点点，所所以以，除非受到某些问题限制，一般采用二进制编码。除非受到某些问题限制，一般采用二进制编码。工程应用软计算工程应用软计算遗传算法遗传算法 （1 1）数）数值值型型单变单变元元 2 2、不同变元形式的二进制编码方法、不同变元形式的二进制编码方法 如果如果变变元的取元的取值值是整数，是整数，则则用二用二进进制数表示。制数表示。例，例，整数整数1-311-31表示表示为为00001-1111100001-11111。串的长度即位数串的长度即位数。如如果果变变元元并并非非取取整整数数，而而且且最最小小值值不不是是零零时时，假假设设变元的取值为区间变元的取值为区间 xmin,xmax，需离散化。，需离散化。选取的选取的2 2N N个点分别为：个点分别为：用用N N位二进制数表示位二进制数表示：工程应用软计算工程应用软计算遗传算法遗传算法 （2 2）开关型多变元）开关型多变元 开关型变元开关型变元:变元的状态只取两种情况。例变元的状态只取两种情况。例:性别。性别。例：例：选择服装。选择服装。【注注】在在开开关关型型变变元元的的编编码码中中，字字符符串串的的长长度度即即为为优优化问题中变元的个数。化问题中变元的个数。有有的的优优化化问问题题中中，变变元元尽尽管管本本质质上上并并不不是是开开关关的的，但为了研究的方便，也可将其简化为开关型变元。但为了研究的方便，也可将其简化为开关型变元。取面料、价格和取面料、价格和样样式三个式三个变变元，均取元，均取0 0和和1 1开关型。开关型。面面料料状状态态用用好好、坏坏描描述述，价价格格状状态态用用高高、低低描描述述，样样式状式状态态用流行、用流行、陈陈旧描述。旧描述。每个每个可行策略可行策略可用一个三位二可用一个三位二进进制数表示。制数表示。例如例如111,101,000,111,101,000,。工程应用软计算工程应用软计算遗传算法遗传算法 （3 3）符号型变元）符号型变元 变变元元的的状状态态只只是是一一些些事事物物名名称称，如如职职业业变变元元的的状状态态由公务员、教师、医生、律师、工人、农民等组成。由公务员、教师、医生、律师、工人、农民等组成。符符号号型型单单变变元元优优化化问问题题，与与整整数数单单变变元元问问题题具具有有相相同同性性，即即将将变变元元的的所所有有状状态态（事事物物名名称称）与与正正整整数数建建立立起起对对应应关关系系。然然后后将将正正整整数数用用二二进进制制表表示示，构构成成了了对变元状态的对变元状态的0/10/1编码。编码。性性别别（2 2类类）职业职业（7 7种）种）年年龄龄（3232岁岁以下）以下）0 111 100000 111 10000 1 101 11111 1 101 11111 若有多个符号型变元，采用顺序分段的编码方式若有多个符号型变元，采用顺序分段的编码方式。工程应用软计算工程应用软计算遗传算法遗传算法 在在多多元元编编码码中中，一一个个变变元元编编码码在在字字符符串串中中所所占占据据的的位数对遗传操作中该变元的遗传性质有一定的影响。位数对遗传操作中该变元的遗传性质有一定的影响。起重要作用的起重要作用的变变元元占字符串中的位数要短些。占字符串中的位数要短些。因因为为个个体体间间的的交交叉叉换换位位及及字字符符的的突突变变都都具具有有随随机机性性，当当某某个个变变元元在在字字符符串串中中所所占占位位数数较较少少时时，换换位位和和突突变变对该变对该变元已取得的状元已取得的状态态破坏的可能性就破坏的可能性就较较小。小。一一旦旦该该变变元元已已处处于于较较佳佳状状态态时时，该该状状态态也也就就容容易易被被遗遗传传下下来来。反反之之，若若变变元元状状态态所所占占位位数数太太大大，也也极极容容易在换位或突变中被破坏，好的性质也不易被遗传。易在换位或突变中被破坏，好的性质也不易被遗传。另另外外，为为防防止止起起重重要要作作用用的的变变元元在在遗遗传传操操作作中中遭遭到到破坏，可以采用交叉破坏，可以采用交叉编码编码方法。方法。工程应用软计算工程应用软计算遗传算法遗传算法 3 3、初始群体的产生、初始群体的产生 初始群体产生方式随机，也可人为给出。初始群体产生方式随机，也可人为给出。如如果果计计算算个个体体的的适适应应度度时时需需花花费费代代价价较较高高，则则数数目不宜太大；若代价极小，则尽量取数目较大些。目不宜太大；若代价极小，则尽量取数目较大些。初始群体个体数目由实际问题的性质决定，原则：初始群体个体数目由实际问题的性质决定，原则：如果字符串如果字符串长长，则则数目大些；反之，数目可小些。数目大些；反之，数目可小些。所所研研究究问问题题的的因因素素（变变元元）多多时时，数数目目则则大大些些，以保证每个变元都能在初始群体中出现不同的状态。以保证每个变元都能在初始群体中出现不同的状态。一般，群体中个体越多，越容易搜索到全局最优解。一般，群体中个体越多，越容易搜索到全局最优解。遗遗传传算算法法向向全全局局最最优优解解的的逼逼近近程程度度和和逼逼近近速速度度与与初初始群体中个体数目有关，且与在始群体中个体数目有关，且与在S S中的分布状中的分布状态态有关。有关。当当无无法法使使群群体体规规模模选选得得太太大大时时，为为提提高高初初始始种种源源的的质质量，量，应该应该使初始群体在使初始群体在S S中尽量均匀的分布开。中尽量均匀的分布开。适适应应度度是是描描述述群群体体中中个个体体优优劣劣的的尺尺度度，在在优优化化问问题题中，适应度是可行解的目标函数值。中，适应度是可行解的目标函数值。工程应用软计算工程应用软计算遗传算法遗传算法 1 1、无约束条件极值问题的适应度函数、无约束条件极值问题的适应度函数 设设g(x)g(x)是是无无约约束束极极值值问问题题的的目目标标函函数数，xX,XxX,X是是所所有可行解的集合，有可行解的集合，x x是是X X上的上的n n维向量。维向量。三、三、个体的适应度个体的适应度 极极值值问问题题有有最最大大值值和和最最小小值值问问题题，同同时时目目标标函函数数g(x)g(x)既可以取正值，也可以取负值。既可以取正值，也可以取负值。规定规定：个个体体y y（字字符符串串）对对应应的的可可行行解解x x（实实值值向向量量或或符符号组）的适应度号组）的适应度f(x)f(x)只能取正值；只能取正值；f(x)f(x)值越大，表明相应个体值越大，表明相应个体y y的性能越优。的性能越优。工程应用软计算工程应用软计算遗传算法遗传算法 对于可能产生负值的最大值问题，取适应度函数对于可能产生负值的最大值问题，取适应度函数:f(x)=|f(x)=|m|+g(x),|+g(x),其中其中m=ming(x)|xX0=ming(x)|xXf(x)f(xj j)，则，则P Pi iPPj j。取取周周长长为为1 1个个单单位位长长度度的的圆圆盘盘，按按X X的的概概率率分分布布律律将将圆圆周周分分成成n n个个区区间间。当当转转动动轮轮盘盘停停止止后后，箭箭头头所所指指位位置置代表的个体被选中。代表的个体被选中。工程应用软计算工程应用软计算遗传算法遗传算法 实际操作中，通常采用与上述操作等价的方法：实际操作中，通常采用与上述操作等价的方法：设设：可以看出：可以看出：为为选选择择复复制制个个体体，在在0,10,1区区间间内内产产生生一一个个均均匀匀分分布布的的随随机机数数R R，若若有有F Fi iR RF Fi+1i+1，则则确确定定个个体体x xi+1i+1为为复复制制对对象象。只只要要连连续续重重复复这这个个过过程程，就就可可以以选选出出多多个个复复制对象，直至满足所需要的个体数目为止。制对象，直至满足所需要的个体数目为止。每每代代群群体体中中被被复复制制的的个个体体数数目目通通常常占占总总体体的的10%10%20%20%，称称这这个个数数值值为为复复制制概概率率。群群体体中中被被复复制制的的个个数数也也就就是是被被淘淘汰汰的的个个体体数数，这这样样可可以以保保证证群群体体中中的的个个体体数目不变。数目不变。工程应用软计算工程应用软计算遗传算法遗传算法 2 2、交换算子、交换算子 复复制制算算子子每每次次仅仅作作用用在在一一个个个个体体上上，而而交交换换算算子子每每次作用在从群体中随机选取的两个个体上。次作用在从群体中随机选取的两个个体上。称称群群体体中中执执行行交交换换的的个个体体数数目目与与群群体体中中个个体体总总数数之之比为比为交换概率交换概率，记为，记为P Pc c，一般取为，一般取为0.50.80.50.8。1 1）确确定定实实行行交交换换的的个个体体数数目目nPnPc c，采采用用轮轮盘盘选选择择法法，从群体中随机从群体中随机选选取被交取被交换换的个体的个体实实行交行交换换操作。操作。2 2）交交换换点点的的选选择择也也是是随随机机的的，交交换换分分为为单单点点交交换换、两点交两点交换换和多点交和多点交换换几种方式。几种方式。两两个个个个体体的的交交换换可可以以产产生生两两个个新新的的个个体体，称称为为子子代代。子代与父代不同，但却包含着两个父代的遗传信息。子代与父代不同，但却包含着两个父代的遗传信息。单点交换单点交换 两点交换两点交换 通常，当字符串长度较短时，采用单点交换，字符通常，当字符串长度较短时，采用单点交换，字符串较长时则采用两点交换方式。串较长时则采用两点交换方式。工程应用软计算工程应用软计算遗传算法遗传算法 如果字符串非常长时，还可以进行多点交换，即对如果字符串非常长时，还可以进行多点交换，即对字符串实行多段交换。字符串实行多段交换。工程应用软计算工程应用软计算遗传算法遗传算法 3 3、突、突变变算子算子 突变突变是对个体中某一位字符进行运算。是对个体中某一位字符进行运算。执行突变的方式：字符决定法和个体决定法。执行突变的方式：字符决定法和个体决定法。一一种种是是补补运运算算，即即把把0 0变变成成1 1，或或把把1 1变变为为0 0，进进而而产产生一个新的个体。生一个新的个体。一一种种是是随随机机变变化化，当当字字符符选选定定后后，不不论论该该字字符符原原来来是什么，按是什么，按0.50.5的概率随机的概率随机产产生一个生一个0 0或或1 1代替原字符。代替原字符。字符决定法字符决定法。突变的个体及位置由字符决定。突变的个体及位置由字符决定。设群体有设群体有n个长度为个长度为L的个体，则字符总数为的个体，则字符总数为n*L。首先确定一个突首先确定一个突变变概率概率Pm，一般一般为为0.001-0.01。然然后后对对每每一一个个字字符符在在0,10,1上上产产生生均均匀匀分分布布的的三三位位有效随机数，若小于有效随机数，若小于Pm ，则对该字符实行突变操作。，则对该字符实行突变操作。工程应用软计算工程应用软计算遗传算法遗传算法 【注注】交交换换和和突突变变都都能能产产生生新新个个体体，但但交交换换的的作作用用更重要，因此，交换概率远比突变概率大得多。更重要，因此，交换概率远比突变概率大得多。个体决定法个体决定法 首首先先给给定定一一个个概概率率，按按此此概概率率在在群群体体中中随随机机选选出出突突变的个体。变的个体。对对于于每每个个被被选选中中的的个个体体，在在个个体体字字长长范范围围内内按按均均匀匀分布随机选出突变的字符。分布随机选出突变的字符。再再按按照照前前面面讲讲过过的的方方法法（补补运运算算或或随随机机变变化化）对对该该字符实施操作。字符实施操作。工程应用软计算工程应用软计算遗传算法遗传算法五、遗传操作中的个体可行性与惩罚策略五、遗传操作中的个体可行性与惩罚策略 1、个体可行性与维持策略个体可行性与维持策略 应应用用优优化的典型化的典型问题问题-非非线线性性规规划划:可行个体（可行解）：每个个体都满足约束条件。可行个体（可行解）：每个个体都满足约束条件。不可行个体（可行解）：不满足约束条件的个体。不可行个体（可行解）：不满足约束条件的个体。保证可行的方案：保证可行的方案：抛弃策略；抛弃策略；修复策略；修复策略；改进遗传算子策略。改进遗传算子策略。工程应用软计算工程应用软计算遗传算法遗传算法 2、惩罚函数惩罚函数 核心思想核心思想:将有约束的问题变化为无约束的问题。将有约束的问题变化为无约束的问题。惩惩罚罚技技术术:对对不不可可行行个个体体X赋赋予予一一个个相相应应的的惩惩罚罚值值P(X)，它是对不可行性程度的一种度量值。它是对不可行性程度的一种度量值。个体的个体的评估函数评估函数:将个体的目标函数将个体的目标函数f(x)和惩罚函和惩罚函数数P(x)相结合相结合，构造一个新的适应度函数构造一个新的适应度函数F(x)。遗传的复制操作，利用评估函数值取代适应度值。遗传的复制操作，利用评估函数值取代适应度值。如果个体如果个体X是可行解，则对是可行解，则对X不做惩罚，个体不做惩罚，个体X的评的评估函数值仅取决于目标函数估函数值仅取决于目标函数f(x)；如果如果X是不可行解，则给予是不可行解，则给予X适当的惩罚，使其评估适当的惩罚，使其评估函数值得到减小。函数值得到减小。X越不可行，惩罚量越大，评估函数值越小。越不可行，惩罚量越大，评估函数值越小。工程应用软计算工程应用软计算遗传算法遗传算法 评估函数构造：评估函数构造：1)1)加法形式加法形式:F(X)=f(x)+P(X)对于极大化问题，取对于极大化问题，取 P(X)=0 若若X可行可行 P(X)0 若若X不可行不可行 2)2)乘法形式：乘法形式：F(X)=f(x)P(X)对于极大化问题，取对于极大化问题，取 P(X)=1 若若X可行可行 0=P(X)1 若若X不可行不可行为避免为避免F(X)产生负值，取产生负值，取 工程应用软计算工程应用软计算遗传算法遗传算法 几个求解非线性规划的惩罚函数例子几个求解非线性规划的惩罚函数例子 工程应用软计算工程应用软计算遗传算法遗传算法工程应用软计算工程应用软计算遗传算法遗传算法六、六、遗传算法运算终止准则遗传算法运算终止准则 如如果果目目标标函函数数的的最最优优值值（适适应应度度最最大大值值）是是知知道道的的，当当某某代代群群体体中中这这个个最最优优值值一一旦旦出出现现，就就停停止止，相相应的个体就是所求的最优解。应的个体就是所求的最优解。由由于于遗遗传传运运算算是是一一种种迭迭代代搜搜索索方方法法，通通过过反反复复的的迭迭代代搜搜索索，可可以以逐逐渐渐逼逼近近最最优优解解，但但不不一一定定能能达达到到最最优优解解，所所以以还还可可以以按按照照逼逼近近误误差差确确定定是是否否终终止止。即即事事先先指指定定一一个个误误差差值值00，若若某某一一代代群群体体中中最最大大的的适适应应度度值值与与已已知知的的最最大大适适应应度度值值之之差差小小于于，则则终终止止运运算算。该该代代群群体体中中具具有有最最大大适适应应度度的的个个体体即即为为所所求求最最优优解解的的近似解。近似解。工程应用软计算工程应用软计算遗传算法遗传算法 有有些些工工程程优优化化问问题题，最最优优解解的的适适应应度度是是不不知知道道的的。在在这这种种情情况况下下，可可以以依依据据人人的的经经验验或或对对问问题题的的期期望望提提出出一一个个理理想想适适应应度度值值，一一旦旦某某代代最最优优个个体体的的适适应应度度超超过了这个理想值，则迭代运算停止。过了这个理想值，则迭代运算停止。规规定定迭迭代代次次数数，当当迭迭代代达达到到这这个个次次数数时时即即停停止止，在整个遗传操作中得到的最好结果作为最优解。在整个遗传操作中得到的最好结果作为最优解。事事先先规规定定一一个个最最小小迭迭代代次次数数，当当迭迭代代次次数数超超过过该该值值后后，开开始始检检查查每每代代群群体体中中最最优优个个体体适适应应度度的的变变化化情情况况。一一旦旦最最优优个个体体适适应应度度不不再再增增长长或或增增长长的的非非常常缓缓慢慢时，即可终止计算。时，即可终止计算。工程应用软计算工程应用软计算遗传算法遗传算法 定理定理：基本遗传算法收敛于最优解的概率小于：基本遗传算法收敛于最优解的概率小于1 1。为为保保证证群群体体中中最最优优个个体体的的适适应应度度值值逐逐代代提提高高，采采取取的基本措施：的基