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

遗传算法,理学院应用数学系,立体化教学资源系列工程应用软计算,工程应用软计算遗传算法,序言,3.1 遗传算法的生物学背景,3.2 遗传算法,3.3 遗传算法Matlab应用举例,3.4 遗传算法应用实例,工程应用软计算遗传算法,序言,遗传算法起源于对生物系统所进行的计算机模拟研究。它是借鉴生物学的自然选择和遗传机制，以种群搜索和种群中个体（染色体）之间的信息交换为策略的随机搜索优化算法。,一、遗传算法的发展,60年代后，美国密执安大学的Holland教授及其学生们受到这种启发，创造出基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术-遗传算法。下面列出关键人物及主要贡献。,20世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术。,工程应用软计算遗传算法,（1）60年代，Holland提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。,70年代初，Holland提出了遗传算法的基本定理-模式定理，从而奠定了遗传算法的理论基础。,1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著自然系统和人工系统的自适应性(Adaptation in Natural and Artificial Systems),80年代，Holland 实现了第一个基于遗传算法的机器学习系统-分类器系统（CS）。,工程应用软计算遗传算法,（2）1967年，Holland的学生Baglay在其博士论文中首次提出了“遗传算法”一词，并发表了第一篇应用论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，使用了双倍体个体编码方法。这些都与目前的算子与方法相类似。创立了自适应遗传算法的概念。,（3）Jong 1975年De Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。,（4）。1989年，Goldberg出版了专著搜索、优化和机器学习中的遗传算法（Genetic Algorithms in Search,Optimization and Machine Learning）。奠定了现代遗传算法的科学基础。,工程应用软计算遗传算法,（5）L.Davis 1991年，Davis出版了遗传算法手册(Handbook of Genetic Algorithms)，包含了在科学计算、工程技术和社会经济中的大量应用实例。本书为推广和普及遗传算法的应用起到了重要的指导作用。,（6）1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念GP(Genetic Programming)。成功地应用于人工智能、机器学习、符号处理等方面。,综观整个遗传算法的发展历程，20世纪70年代是开始阶段，20世纪80年代是发展阶段，20世纪90年代是高潮阶段。,工程应用软计算遗传算法,二、遗传算法的应用,遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。应用领域：,（1）函数优化。这是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。利用几何特性各具特色的各类函数评价算法性能，更能反映算法的本质效果。而对于其它优化方法难于求解的非线性、多模型、多目标的函数优化问题，遗传算法可方便地得到较好的结果。,（2）组合优化。成功地用于求解旅行商问题、背包问题、装箱问题、图形划分问题等组合优化NP完全问题。,工程应用软计算遗传算法,（3）生产调度问题。解决复杂调度问题：单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面。（4）自动控制。航空控制系统优化、参数辨识等。（5）图像处理。模式识别、图像恢复、图像边缘特征提取等方面。（6）机器人学。成功地用于移动机器人路径规划、关节机器人运动轨迹规划、细胞机器人的结构优化和行为协调等方面。（7）人工生命。用于进化模型、学习模型、行为模型、自组织模型等方面。（8）遗传编程。成功地用于人工智能、机器学习等。（9）机器学习。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。,工程应用软计算遗传算法,3.1 遗传算法的生物学背景,一、生物遗传与进化,从生物进化论和遗传学角度看，主宰地球生物演化的因素主要有两方面:,（1）生命物质自身具有的遗传与变异功能。,（2）自然界为生命存在方式提供的条件资源有限。,遗传能力使得物种得以延续，自然界的环境与资源限制会使生存能力弱的生物遭到淘汰；变异会使生物的生存能力产生差异，使生物进化或产生新的物种。,地球上的生物的发展与进化，是生命物质自身具有的功能与自然界相互作用的结果。,工程应用软计算遗传算法,二、DNA复制与生物的遗传,细胞是组成生命的最小单元，细胞通常由细胞膜、细胞质和细胞核三个部分组成。,其中，细胞核内的染色体中的DNA分子是生物体携带遗传信息的基本物质。,DNA分子结构图:,工程应用软计算遗传算法,工程应用软计算遗传算法,DNA分子的主要功能：,（1）控制和指导各种蛋白质（包括各种酶）的合成。,（2）DNA本身的复制增生。,DNA的自我复制也为遗传密码复制，按照碱基互补配对原则，当生物体的一个母细胞有丝分裂成两个子细胞时，其中每个DNA分子也自体复制为两个一模一样的子分子分存于两个子细胞中。,基因：一个有特定遗传功能的DNA节段。,基因是控制生物遗传的物质单元，含成百上千的核苷酸，在染色体上的排列次序代表遗传密码信息。,工程应用软计算遗传算法,三、DNA重组与生物的进化,地球上的生物都是经过了长期的进化而形成的。,复制形成的遗传不可能实现生物的进化。,较高等生物的体细胞中，染色体都是成对存在的，即染色体个数是双数，称为二倍体。,有性生殖生物的生殖细胞只含半数染色体-单倍体。,减数分裂：使得次级细胞由精细胞或卵原细胞分裂成生殖细胞（精子或卵）的过程。,（1）产生的细胞只得到半数染色体，即只获得每对基因中的一个；,（2）减数分裂中,每对染色体中的一个染色单体与它并排的同源染色体的一个染色单体发生交叉-差异；,工程应用软计算遗传算法,工程应用软计算遗传算法,（3）在减数分裂过程中出现染色体对间的随机组合,引起生殖细胞的多样性。,有性生殖物种内部大量的变异现象对于物种进化起了极其重要的作用。,减数分裂中,染色单体的交换和随机组合是使生物生殖细胞发生变异的主要原因。,综上，生物在遗传过程中发生的变异（主要是基因重组、基因突变和染色体变异）与自然界生存条件的结合，导致了世界生物的进化。,基因的突变也是使生物得以变异进化的重要因素。,工程应用软计算遗传算法,工程应用软计算遗传算法,四、生物遗传与进化对组合优化问题的启发,组合优化问题可以用二元集(S,f)描述。其中S是解空间：由一切可能的解组成的有限集，f目标函数。,凸情况：目标函数在S上只有一个最小（或最大）值。非凸情况：目标函数在S上存在多个极值点。,即在S中找一个解，使目标函数值达最小（或最大）。,遗传算法的基本思想：模仿生物遗传进化的机制，将组合优化问题的一组可行解视为染色体，该解对应的目标函数值视为生物种群的优劣。,复制可以使优异解得以保留，交换可行解中部分变元，或采用突变手段使部分变元置换，可以产生新的可行解。这种复制、交换、突变等操作，不断执行下去，逐渐会逼近全局最优解。,3.2 遗传算法,一、遗传算法的基本步骤,例：用遗传算法求二次函数最大值。,工程应用软计算遗传算法,工程应用软计算遗传算法,解：（1）编码,对于变量x，不妨限定其仅取031间的整数。,随机地产生几个初始值，假设得到4个点 00101，01100，10011，11101，组成初始群体，其数值分别为5，12，19，29。,工程应用软计算遗传算法,工程应用软计算遗传算法,（2）计算个体适应度,【注】3号个体相对适应度最高，4号个体适应度最低。,按照生物进化的“自然选择，适者生存”原则，复制3号个体，删除4号个体。得新的群体 00101,01100,10011,10011，重新编为1,2,3,4号个体。,（3）遗传算子（复制、交换、突变）变换,a 复制：,选择1号和3号个体进行交换，2号和4号个体进行交换，每个个体对第3位以后的字符片段与其配对个体的相应字符进行交换。,工程应用软计算遗传算法,工程应用软计算遗传算法,b 交换:,交换前的旧个体 交换后的新个体,交换后个体适应度,工程应用软计算遗传算法,工程应用软计算遗传算法,c、突变,将1号个体字符串的最后1位进行突变，,（4）运算终止准则判断,10000已为最优解。故原问题的最大值为 x=16。,1号：10001 10000,工程应用软计算遗传算法,工程应用软计算遗传算法,遗传算法的基本步骤：,步骤1 对研究的变量或对象进行编码（形成字符 串），并随机地建立一个初始群体。步骤2 计算群体中诸个体的适应度。步骤3 执行产生新群体的操作，包括：a 复制：将适应度高的个体进行复制后添入 到新群体中，删除适应度低的个体；b 交换：随机选出个体对，进行片段交叉换 位，产生新个体对；c 突变：随机改变某个体的某个字符，而得 到新个体。步骤4 根据某种条件判断计算过程是否可以结 束，如果不满足结束条件，则返回到步骤 2，直到满足结束条件为止。,工程应用软计算遗传算法,工程应用软计算遗传算法,遗传算法是模仿生物遗传与进化过程而得到的一种随机优化方法，对非线性、多极值的寻优是一种有效方法。,遗传算法对问题的可行解编码，表示成“染色体”，随机产生的一群“染色体”组成初始种群。,由适应度构成优胜劣汰、适者生存的“自然环境”。,种群通过遗传、交换、突变等不断演化，产生出新的更加优良的种群。,经过若干代的进化，最终求得适合问题的最优解。,工程应用软计算遗传算法,工程应用软计算遗传算法,二、遗传算法的编码,编码是应用遗传算法中首先要解决的问题。是指将优化问题的可行解设计成字符串（视为染色体）的过程。,1、编码的主要方法,1)遗传因子用0/1码表示。,2)实数编码（即字符串的每个位置都取实数）。,3)符号编码（一般用整数序号1,2,k表示的字符进行编码）,利用二进制的0/1双字符编码具有一定优点，所以，除非受到某些问题限制，一般采用二进制编码。,工程应用软计算遗传算法,（1）数值型单变元,2、不同变元形式的二进制编码方法,如果变元的取值是整数，则用二进制数表示。例，整数1-31表示为00001-11111。串的长度即位数。,如果变元并非取整数，而且最小值不是零时，假设变元的取值为区间xmin,xmax，需离散化。,选取的2N个点分别为：,用N位二进制数表示：,工程应用软计算遗传算法,（2）开关型多变元,开关型变元:变元的状态只取两种情况。例:性别。,例：选择服装。,【注】在开关型变元的编码中，字符串的长度即为优化问题中变元的个数。,有的优化问题中，变元尽管本质上并不是开关的，但为了研究的方便，也可将其简化为开关型变元。,取面料、价格和样式三个变元，均取0和1开关型。,面料状态用好、坏描述，价格状态用高、低描述，样式状态用流行、陈旧描述。,每个可行策略可用一个三位二进制数表示。,例如111,101,000,。,工程应用软计算遗传算法,（3）符号型变元,变元的状态只是一些事物名称，如职业变元的状态由公务员、教师、医生、律师、工人、农民等组成。,符号型单变元优化问题，与整数单变元问题具有相同性，即将变元的所有状态（事物名称）与正整数建立起对应关系。然后将正整数用二进制表示，构成了对变元状态的0/1编码。,性别（2类）职业（7种）年龄（32岁以下）,0 111 10000,1 101 11111,若有多个符号型变元，采用顺序分段的编码方式。,工程应用软计算遗传算法,在多元编码中，一个变元编码在字符串中所占据的位数对遗传操作中该变元的遗传性质有一定的影响。,起重要作用的变元占字符串中的位数要短些。,因为个体间的交叉换位及字符的突变都具有随机性，当某个变元在字符串中所占位数较少时，换位和突变对该变元已取得的状态破坏的可能性就较小。,一旦该变元已处于较佳状态时，该状态也就容易被遗传下来。反之，若变元状态所占位数太大，也极容易在换位或突变中被破坏，好的性质也不易被遗传。,另外，为防止起重要作用的变元在遗传操作中遭到破坏，可以采用交叉编码方法。,工程应用软计算遗传算法,3、初始群体的产生,初始群体产生方式随机，也可人为给出。,如果计算个体的适应度时需花费代价较高，则数目不宜太大；若代价极小，则尽量取数目较大些。,初始群体个体数目由实际问题的性质决定，原则：,如果字符串长，则数目大些；反之，数目可小些。,所研究问题的因素（变元）多时，数目则大些，以保证每个变元都能在初始群体中出现不同的状态。,一般，群体中个体越多，越容易搜索到全局最优解。,遗传算法向全局最优解的逼近程度和逼近速度与初始群体中个体数目有关，且与在S中的分布状态有关。,当无法使群体规模选得太大时，为提高初始种源的质量，应该使初始群体在S中尽量均匀的分布开。,适应度是描述群体中个体优劣的尺度，在优化问题中，适应度是可行解的目标函数值。,工程应用软计算遗传算法,1、无约束条件极值问题的适应度函数,设g(x)是无约束极值问题的目标函数，xX,X是所有可行解的集合，x是X上的n维向量。,三、个体的适应度,极值问题有最大值和最小值问题，同时目标函数g(x)既可以取正值，也可以取负值。规定：,个体y（字符串）对应的可行解x（实值向量或符号组）的适应度f(x)只能取正值；,f(x)值越大，表明相应个体y的性能越优。,工程应用软计算遗传算法,对于可能产生负值的最大值问题，取适应度函数:f(x)=|m|+g(x),其中m=ming(x)|xX0,对于最小值问题，取适应度函数:f(x)=k-g(x)其中kmaxg(x)|xX。,2、有约束条件极值问题的适应度函数,有约束条件的极值问题：,取适应度函数为,其中为惩罚函数，为惩罚系数，取,工程应用软计算遗传算法,1、复制算子,遗传算子是遗传算法中对群体中个体所进行的操作，目的是通过这些操作得到新的个体。,遗传算法的基本算子，体现“适者生存”的自然选择原则，同时新一代群体与原来群体个体数相同。,四、遗传算子,最主要的三个算子是复制、交换和突变。,遗传算法采用随机抽样的方法来选择复制对象。,“适者生存”:保证适应度高的个体被抽到的机会大于适应度低的个体。,轮盘选择法:采用一种轮盘方式来选择复制对象。满足适者生存原则的随机抽样方案-J.Holland,工程应用软计算遗传算法,轮盘选择法,设x1,x2,xn为给定的n个个体组成的一个群体，其中xi 是具有相同长度的0/1字符串。xi 的适应度值 f(xi)0。定义,称Pi 为个体xi 的生存概率。,若f(xi)f(xj)，则PiPj。,取周长为1个单位长度的圆盘，按X的概率分布律将圆周分成n个区间。当转动轮盘停止后，箭头所指位置代表的个体被选中。,工程应用软计算遗传算法,实际操作中，通常采用与上述操作等价的方法：,设：,可以看出：,为选择复制个体，在0,1区间内产生一个均匀分布的随机数R，若有FiRFi+1，则确定个体xi+1为复制对象。只要连续重复这个过程，就可以选出多个复制对象，直至满足所需要的个体数目为止。,每代群体中被复制的个体数目通常占总体的10%20%，称这个数值为复制概率。群体中被复制的个数也就是被淘汰的个体数，这样可以保证群体中的个体数目不变。,工程应用软计算遗传算法,2、交换算子,复制算子每次仅作用在一个个体上，而交换算子每次作用在从群体中随机选取的两个个体上。,称群体中执行交换的个体数目与群体中个体总数之比为交换概率，记为Pc，一般取为0.50.8。,1）确定实行交换的个体数目nPc，采用轮盘选择法，从群体中随机选取被交换的个体实行交换操作。,2）交换点的选择也是随机的，交换分为单点交换、两点交换和多点交换几种方式。,两个个体的交换可以产生两个新的个体，称为子代。子代与父代不同，但却包含着两个父代的遗传信息。,单点交换,两点交换,通常，当字符串长度较短时，采用单点交换，字符串较长时则采用两点交换方式。,工程应用软计算遗传算法,如果字符串非常长时，还可以进行多点交换，即对字符串实行多段交换。,工程应用软计算遗传算法,3、突变算子,突变是对个体中某一位字符进行运算。,执行突变的方式：字符决定法和个体决定法。,一种是补运算，即把0变成1，或把1变为0，进而产生一个新的个体。,一种是随机变化，当字符选定后，不论该字符原来是什么，按0.5的概率随机产生一个0或1代替原字符。,字符决定法。突变的个体及位置由字符决定。,设群体有n个长度为L的个体，则字符总数为n*L。,首先确定一个突变概率Pm，一般为0.001-0.01。,然后对每一个字符在0,1上产生均匀分布的三位有效随机数，若小于Pm，则对该字符实行突变操作。,工程应用软计算遗传算法,【注】交换和突变都能产生新个体，但交换的作用更重要，因此，交换概率远比突变概率大得多。,个体决定法,首先给定一个概率，按此概率在群体中随机选出突变的个体。,对于每个被选中的个体，在个体字长范围内按均匀分布随机选出突变的字符。,再按照前面讲过的方法（补运算或随机变化）对该字符实施操作。,工程应用软计算遗传算法,五、遗传操作中的个体可行性与惩罚策略,1、个体可行性与维持策略,应用优化的典型问题-非线性规划:,可行个体（可行解）：每个个体都满足约束条件。,不可行个体（可行解）：不满足约束条件的个体。,保证可行的方案：,抛弃策略；修复策略；改进遗传算子策略。,工程应用软计算遗传算法,2、惩罚函数,核心思想:将有约束的问题变化为无约束的问题。,惩罚技术:对不可行个体X赋予一个相应的惩罚值P(X)，它是对不可行性程度的一种度量值。,个体的评估函数:将个体的目标函数f(x)和惩罚函数P(x)相结合，构造一个新的适应度函数F(x)。,遗传的复制操作，利用评估函数值取代适应度值。,如果个体X是可行解，则对X不做惩罚，个体X的评估函数值仅取决于目标函数f(x)；,如果X是不可行解，则给予X适当的惩罚，使其评估函数值得到减小。,X越不可行，惩罚量越大，评估函数值越小。,工程应用软计算遗传算法,评估函数构造：,1)加法形式:F(X)=f(x)+P(X),对于极大化问题，取 P(X)=0 若X可行 P(X)0 若X不可行,对于极小化问题，取 P(X)=0 若X可行 P(X)0 若X不可行,2)乘法形式：F(X)=f(x)P(X),对于极大化问题，取 P(X)=1 若X可行 0=P(X)=1 若X不可行,对于极小化问题，则取 P(X)=1 若X可行 P(X)1 若X不可行,为避免F(X)产生负值，取,工程应用软计算遗传算法,几个求解非线性规划的惩罚函数例子,工程应用软计算遗传算法,工程应用软计算遗传算法,六、遗传算法运算终止准则,如果目标函数的最优值（适应度最大值）是知道的，当某代群体中这个最优值一旦出现，就停止，相应的个体就是所求的最优解。,由于遗传运算是一种迭代搜索方法，通过反复的迭代搜索，可以逐渐逼近最优解，但不一定能达到最优解，所以还可以按照逼近误差确定是否终止。即事先指定一个误差值0，若某一代群体中最大的适应度值与已知的最大适应度值之差小于，则终止运算。该代群体中具有最大适应度的个体即为所求最优解的近似解。,工程应用软计算遗传算法,有些工程优化问题，最优解的适应度是不知道的。在这种情况下，可以依据人的经验或对问题的期望提出一个理想适应度值，一旦某代最优个体的适应度超过了这个理想值，则迭代运算停止。,规定迭代次数，当迭代达到这个次数时即停止，在整个遗传操作中得到的最好结果作为最优解。,事先规定一个最小迭代次数，当迭代次数超过该值后，开始检查每代群体中最优个体适应度的变化情况。一旦最优个体适应度不再增长或增长的非常缓慢时，即可终止计算。,工程应用软计算遗传算法,定理：基本遗传算法收敛于最优解的概率小于1。,为保证群体中最优个体的适应度值逐代提高，采取的基本措施：,定理：实施最优保存策略的遗传算法是收敛的。,七、遗传算法的收敛性,最优个体保存策略：在每一代群体中找出适应度最优的个体，使之复制保留一个种源，种源不参与交换和突变运算。直到后代种群中又出现一个更好的个体来替代其作为保留种源。,工程应用软计算遗传算法,八、遗传算法的特点,遗传算法实质上是一种随机搜索寻优技术，与传统的优化方法相比，不同之处：,在遗传算法中需要对优化问题的参变量进行编码，故而，算法不是直接面对参变量，而是面对一种新的信息载体字符串；,遗传算法的搜索不是从一点出发，而是从一个初始点的群体出发，不断迭代计算，逐步逼近最优解；,遗传算法是利用适应度信息的随机搜索，它既不是盲目的也不是穷举式的，它的突出特点就是把注意力集中到搜索空间中适应度最高的部分，无须导数或其他辅助信息；,工程应用软计算遗传算法,遗传算法利用概率转移规则，而非确定性规划。,遗传算法的独特优点：,智能性寻优。,通用性强。,全局优化。,隐含并行式算法。,遗传算法的缺点：收敛速度问题、早熟问题。,工程应用软计算遗传算法,控制参数的性能分析,1）群体规模n的确定。2）复制个体数目M的确定。3）交换概率pc的确定。4）突变概率pm的确定。,遗传算子的改进,主要算子：复制、交换、突变算子。其它算子：1）倒序算子。2）换序算子。3）移序算子。4）小生态环境技术。,工程应用软计算遗传算法,九、遗传算法性能的测试与评价,为了对一种算法的性能进行测试和评价，人们提出了一些用以检测算法性能的测试函数和用以分析算法性能好坏的评价指标。,（1）测试算法性能的常用函数,工程应用软计算遗传算法,工程应用软计算遗传算法,工程应用软计算遗传算法,工程应用软计算遗传算法,工程应用软计算遗传算法,工程应用软计算遗传算法,（2）遗传算法性能评价指标 De Jong提出两个评价遗传算法性能的指标，分别为在线性能指标和离线性能指标，这也是目前评价一个算法收敛性能的主要指标。定义3-1 称Xe(S)为S算法在某研究对象e中的在线性能。定义为 其中fe(t)是所研究对象e的第t代群体的平均适应度值。由定义知，在线性能表示算法在直到当前时刻为止所得到的历代群体平均适应度的平均值，它反映了算法的动态性能。,工程应用软计算遗传算法,是所研究对象e从初始种群（t=0）到第t代群体所得到的最大适应度。,定义3-2 称 为算法S在某研究对象e中的离线性能，定义为,其中,工程应用软计算遗传算法,算法的离线性能表示了算法在执行过程中所得到的最优性能的平均值，它反映了算法的收敛性。,工程应用软计算遗传算法,3.3 遗传算法Matlab应用举例,例：用遗传算法求二次函数最大值。,1、一元非线性函数优化实例,1）编码采用二进制编码；2）种群的个体（染色体）数目设为10个；3）染色体长度为20；4）复制概率为0.9；5）交换概率为0.7；6）突变概率为0.7/Lind（Lind为假定的个体长度，程序用默认值）；7）最大遗传代数为50代。,程序运行结果显示为：最大值为:256.0000，对应的解为:16.0001。（实际上迭代到十几代的时候已经得到最优值）,工程应用软计算遗传算法,1）编码采用二进制编码，即将可行解 编码为一个二进制串；2）种群的个体（染色体）数目设为40个；3）染色体中每个变量对应的二进制串的长度为20；4）复制概率为0.9；5）交换概率为0.7；6）突变概率为程序默认值；7）最大遗传代数为500代；8）变量个数为2个。,2、二元非线性函数的优化实例,利用遗传算法寻找下面二元函数的最优解,工程应用软计算遗传算法,工程应用软计算遗传算法,目标函数图象 初始种群分布图,工程应用软计算遗传算法,500代所对应的个体分布情况 性能分析图,程序运行结果显示为：,利用遗传算法得到的近似最优值:38.3777。,对应的变量值:11.6255 5.2548。,3、图象分割实例,图象分割是将图象中的象素按灰度值用阈值分成两类图象，一类为目标图象C1，另一类为背景图象C2；两个图象的灰度值被阈值所分开。利用遗传算法进行图象分割就是建立一个有关阈值的适应度值函数，利用遗传操作找到满足适应度函数值取最大值的阈值。下面我们来考察一个具体的图象分割问题，分割Matlab中的clown图象，采取图象的灰度级为256，编码方式为将这些正整数编成8位0-1代码，适应度函数为：,工程应用软计算遗传算法,其中Sum_C1为目标图象C1的象素总数，Sum_C2为背景图象C2的象素总数；Mean1(Y)为目标图象C1中所有象素数的平均灰度值，Mean2(Y)为背景图象C2中所有象素数的平均灰度值。,问题可以描述为如下数学公式：,可知，此问题实际上是一元离散函数优化问题。1）二进制编码，每一个0-1字符串均是可行解；2）种群的个体（染色体）数目设为20个；3）染色体中每个变量对应的二进制串的长度为8；,工程应用软计算遗传算法,4）复制概率为0.9；5）交换概率为0.7；6）突变概率为程序默认值；7）最大遗传代数为50代。,最终结果显示为：最优结果为：33。,工程应用软计算遗传算法,工程应用软计算遗传算法,3.4 遗传算法应用,1、机组发电耗水率函数拟合,某水库库水位、出库流量及机组发电耗水率数据：,工程应用软计算遗传算法,工程应用软计算遗传算法,工程应用软计算遗传算法,根据每个未知数所对应的码长，逐一求出十进制数：,利用公式,工程应用软计算遗传算法,适应度函数求解 由于规定适应度函数值越大，则这一个体的品质越好。此实例中通过模型所求值与实际值之差的平方和的倒数来构造适应度函数:,十组数所对应的适应度值为:,工程应用软计算遗传算法,复制 计算出每个染色体的生存概率分别为:,计算累计生存概率:,采用轮盘选择法,在01中按均匀分布随机产生10个数r，若FirFi+1则vi+1复制,得出新的群体：,工程应用软计算遗传算法,我们可以看出,初始群体的位置分别被,代替。,工程应用软计算遗传算法,交换 规定交换概率为0.6，在01中随机产生10个数，若其中随机数小于0.6则规定此染色体为交换的双亲之一。经过程序的随机选择交换个体i=2,3,4,7,8,10.交换的位置通过随机选取确定为15到23位，交换后得出新的群体:,工程应用软计算遗传算法,突变 设突变概率为0.01，种群中有280个基因，则2.8个基因需要突变，在1280中产生3个随机整数作为突变位置。经过计算机的随机选取，确定第8行的第11位，第7行的18位，第2行的第9位进行突变。突变形成的最终群体为:,工程应用软计算遗传算法,上述群体为第二代群体。求出第二代群体中每个染色体所对应的十进制值:,工程应用软计算遗传算法,找出适应度函数值最大的一项，这一项染色体也就是第二代群体中的最优个体。此次搜索中最优解为(378.8189,-4.7595,0.6600)。将以上步骤反复循环进行，可以得出适应度函数值更好的群体。在本例中，要求迭代1000次。经过1000次的迭代运算，在第42代中就得到了最优解为（371.9685,-4.9785,0.7956）。故而得到拟合方程为：,并求得适应度函数值:,工程应用软计算遗传算法,2、水泥强度预测（李晓东，杨波，董吉文）,影响水泥强度的相关参量有：水泥的细度X1，比表面积X2，质量分数X3，质量分数X4，一天抗压强度X5，一天抗折强度X6等六个参数作为自变量值，将水泥28天的强度Y作为预测的因变量值。建立强度Y与参量Xi的非线性关系模型:,其中，bi,ai和c为寻求的拟合参数.我们的任务是要通过遗传算法寻求最佳的一组拟合参数:,工程应用软计算遗传算法,选取13个实数作为一个染色体，采取十进制编码。即每个染色体（个体）写成,选用30例水泥的实测样本数据(见表)，每个样本数据代入到预测公式中可得到预测值，其实测值为.建立个体的适应度函数为,工程应用软计算遗传算法,随机产生80个染色体作为初始种群，个体复制采用轮盘选择法；采用单点交换，交换概率为0.8；突变概率取0.05；迭代运算10000次停止。,工程应用软计算遗传算法,工程应用软计算遗传算法,3、城市煤气管网优化（彭世尼等）,(1)城市煤气管网优化建模,城市煤气管网优化的实质是，在水力约束的条件下，确定费用最小的管径问题。从技术经济观点看，任何煤气输配系统方案均可用工程造价和运行费用来评价。因此，以折算到每年的管网造价和管网运行费用之和作为目标函数，以最小压力保证以及水力平衡条件为约束条件，求解最优方案的数学规划问题。目标函数表达式为：,工程应用软计算遗传算法,式中：t为标准偿还年限；g为管网运行费用（包括管理费用，维修费用）与管网造价的比例；Di为第i段管网的外径，i=1,2,n；li为第i个管段的长度，i=1,2,n。,公式:,表示单位长度的外径为D的管网造价,其中a,b,c可以通过回归分析方法得到。,管网优化须满足的水力平衡约束条件为：,工程应用软计算遗传算法,式中：Qij为与节点i相连管道的流量 qi为节点i的节点流量 pi为管段的压力降。,管网优化须满足的边界约束条件为：pi=pmin,式中：pi为管网非气源点压力；pmin节点最低允许压力.,(2)管径编码,城市燃气管网的压力级制分为低压、中压、次高压和高压，管材分为聚乙烯管、铸铁管和钢管。参照中压管网的通常做法，取8种规格的钢管进行编码,工程应用软计算遗传算法,(3)初始种群的产生,遗传算法中个体二进制字符串的长度取决与管网的管段数，假设管网的管段数为m，每段用3位二进制字符串，则每个个体用3m位二进制字符串。于是，利用计算机随机产生一组3m位二进制字符串，作为初始群体，每个个体代表不同的管径选择方案,工程应用软计算遗传算法,(4)约束条件与惩罚 水力约束条件可以通过调用燃气管网水力计算程序，在程序设计中取适当的数值来表示计算参数是否符合工程要求。当参数满足水力计算程序时，令K为0；当在规定的范围内水力计算失败时，令K为一个足够大的值，然后将K叠加到费用函数中，使其适应度降低。边界约束条件的满足通过引入惩罚函数来实现。,于是，构造评估函数为,其中，p为管网非气源点中小于最低允许压力的节点压力，pE为惩罚因子，K为水力计算参数。,工程应用软计算遗传算法,由于评估函数F(X)越大表示费用越高，而我们追求的目标是费用最低，所以，在遗传操作中取个体的适应度函数为评估函数F(X)的倒数。通过一个具有15个节点，22根管段，8个环的天然气中压管网，进行遗传算法寻优设计。最终得到一个年计算费用为102.74104万元，工程造价为482.67104万元的设计方案。与传统设计方法相比，年计算费用节省7.63104万元。,工程应用软计算遗传算法,谢谢！,工程应用软计算遗传算法,