遗传算法详细讲解1

1遗传算法(简介)GeneticAlgorithms2第七章遗传算法§1基本概念§2实现的技术问题§3在组合优化中的应用3第七章遗传算法近代科学技术发展的显著特点之一是生命科学与工程科学的相互交叉、相互渗透、相互促进.蚁群算法、微粒群算法etc.遗传算法是20世纪60~70年代主要由美国Michigon大学JohnHolland教授提出.其内涵哲理启迪于自然界生物从低级、简单到高级、复杂，乃至人类这样一个漫长而绝妙的进化过程.借鉴Darwin的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理.其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解.4§1基本概念§1基本概念GA的基本思想：从一初始化的群体出发，通过随机选择(复制)（使群体中优秀的个体有更多的机会传给下一代），交叉（体现了自然界中群体内个体之间的信息交换），和变异（在群体中引入新的变种确保群体中信息的多样性）等遗传操作，使最具有生存能力的染色体以最大可能生存,群体一代一代地进化到搜索空间中越来越好的区域.5第七章遗传算法生物遗传概念在遗传算法中的对应关系生物遗传概念遗传算法中的作用适者生存最优目标值的解有最大可能留住个体解染色体解的编码（字符串、向量等）基因解中每一分量的特征（如分量的值）适应性适应函数值群体选定的一组解种群根据适应函数值选取的一组解交叉（基因重组）通过交叉原则产生一组新解的过程变异编码的某一个分量发生变化的过程6§1基本概念Example1某快餐店要作出以下三项决定：价格汉堡包的价格应定在1美元还是50美分;饮料和汉堡包一起供应的应该是酒还是可乐;服务速度饭店应提供慢的还是快的服务速度.Solution:编码有3个决策变量共有23=8种方案用三位0-1数串，表示一个方案1230,1iaaaa染色体基因a1表示价格0——高价格1——低价格a2表示饮料0——酒1——可乐a3表示速度0——慢1——快7第七章遗传算法适应函数即目标函数就取每种方案实行后的利润，为简单起，每种方案所对应的利润（适应值）恰为这三位二进制所对应的十进制数值.确定群体规模NGA不是一个个的考虑方案，而是同时考虑N个方案，体现了并行性.取N=4，在8个方案中随机抽取4个方案作为初始群体（第0代）.xi011001110010f(xi)3162总和12最小值1平均值3最大值68§1基本概念选择算子把当前群体中的个体按与适应值成比例的概率复制到新的群体中（适者生存）.()()iifxfx希望110在新的群体中出现次,类似希望011、010各出现1次，而001消失.因GA是随机的,按概率随机选择，以上只是期望.642126321如随机数5选择的个体1102129011010110轮盘赌选择：步骤：1、求群体中所有个体的适应值的总和S;2、产生一个在0与S之间的随机数m;3、从群体中编号为1的个体开始，将其适应值与后继个体的适应值相加，直到累加和等于或大于m,则停止.其中那个最后加进去的个体即为选择的个体.由选择算子产生的新群体（可能有重复）称为种群，其规模仍为N.01100111001003410129第七章遗传算法xi110011010110f(xi)6326总和17最小值2平均值4.25最大值6选择算子作用的效果是提高了群体的平均适应值及最差的适应值，低适应值的个体趋于被淘汰，高适应值的个体趋于被复制.但是以损失群体的多样性为代价，选择算子并没有产生新的个体，当然群体中最好个体的适应值不会改进.10§1基本概念交叉（杂交）算子交叉算子每次作用在种群中随机选取的两个个体上,产生两个不同的子个体，它们一般与父个体不同，但又包含两个父个体的遗传物质.介绍一个最简单的方法.首先，产生一个1到l-1（其中l为染色体分量的个数）的随机数i(交叉点),然后配对的两个个体相互交换从i+1到l的位子.如对x1，x2配对且交叉点选在2，则110111011010对种群要确定交叉概率Pc,随机选择N×Pc个个体进行交叉，其余不变.假设Pc=50%xi111010010110f(xi)7226总和17最小值2平均值4.25最大值711第七章遗传算法显然，利用选择、交叉算子可以产生具有更高平均适应值和更好个体的群体.但如果仅仅如此，很容易近亲繁殖，会早熟（局部最优解）.骗问题（遍历性差）变异算子以一个很小的变异概率Pm(=0.02)随机地改变染色体上的某个基因,具有增加群体多样性的效果.0110如：选择x3第2位，则得到新的群体.010000称为第1代，再进行选择、交叉、变异….12§1基本概念Example2Solution:用GA求2()10,1maxfxxx对连续变量求解，要解决如何编码问题.假设对解的误差要求是，则可采用4位二进制编码，对应关系11624816abcdabcd一次迭代的结果.(交叉概率Pc=1，变异概率Pm=0.02)x值共有16种方案群体规模为4群体xif(xi)概率分布种群交叉位交叉结果变异？误差要求是g，区间为，如何处理？,ab新群体x值f(xi)1/161/43/167/800010100001111100.990.930.960.230.3180.2990.3080.075000101000001001100010100000100110000010100010011NYNN0000110100010011013/161/163/1610.340.990.96第0代总和3.133最小值0.234平均值0.7833最大值0.996;第1代总和3.301最小值0.340平均值0.8253最大值1.13第七章遗传算法遗传算法的步骤：step1选择问题解的一个编码，给出一个有N个染色体的初始群体pop(1)，t=1;step2对群体中每一个染色体popi(t)计算它的适应函数值fi=fitness(popi(t));step3若停止规则满足,则算法停止,否则计算概率11iiNjjfpiNf并以此概率分布，从pop(t)中随机选N个染色体构成一个种群，;()newpopt14§1基本概念step4通过交叉(交叉概率)为Pc,得到有N个染色体的crosspop(t+1);step5以较小的概率（变异概率）Pm使得某染色体的一个基因发生变异，形成新的群体mutpop(t+1)令t=t+1pop(t)=nutpop(t)gotostep2.15第七章遗传算法遗传算法的优越性：1、作为数值求解方法，具有普适性.对目标函数几乎没有要求，总能以极大的概率找到全局最优解；2、GA在求解很多组合优化问题时，不需要很高的技巧和对问题有非常深入的了解，在给问题的决策变量编码后，其计算过程是比较简单的，且可较快地得到一个满意解；3、与其他启发式算法有较好的兼容性，易与别的技术相结合，形成性能更优的问题求解方法.可以不连续、不规则、伴有噪声，甚至不一定要显式写出.这是关键.Goback16§2实现的技术问题§2实现的技术问题GA的主要问题之一是算法如何实现的技术问题，以下的一些技术方法，有的借助于直观，有的则有一定的理论，在此仅给出技术细节.一、编码编码是GA中的基础工作之一，GA不能直接处理解空间的解数据，必须通过编码表成遗传空间的基因型数据.比较直观和常规的方法是0、1二进制编码,称为常规码.这种编码方法使算法的三个算子构造比较简单.这与人类的染色体成对结构类似.17第七章遗传算法如0–1背包问题的解是一个0-1向量，可以按(x1，x2,…,xn)的取值形成一个自然编码.11..01njjjnjjjjmaxzcxstaxbxor▲采用0–1编码可以精确地表示整数.如2()031maxfxxxxZ则可用5位二进制编码.1000016010019.精确表示a到b整数的0–1编码长度n满足：21log()2nbanba即18§2实现的技术问题▲连续变量也可采用二进制编码,但要考虑精度.对给定的区间[a,b]，设采用二进制编码长为n，则任何一个变量122222nnbababaxaxxx对应一个二进制码（x1,x2,…,xn）,二进制码与实际变量的最大误差为.2nba▲常规码在表示有些组合优化问题会显得无效或不方便如TSP问题n个城市二进制编码（x1,x2,…,xn(n-1)）编码长为n(n-1)所有解的个数2n(n-1)可行解的个数(n-1)!n=10编码长为90，但可行解只有10个基因取1其余取零.可行解占所有解的极小比例，大量的计算浪费，且对非可行解通过约束限制也增加计算量.19第七章遗传算法对TSP的一个自然的表示方法是n个城市的序号的排列.n=109408712536、3802617945etc.理论上而言，编码应该适合要解决的问题，而不是简单的描述问题.编码是一个很值得研究的问题.二、评价GA的常用方法GA的最优性效果的理论分析是一种趋势讨论，或无穷代的概率结果.用一个方法监察计算过程中解的变化趋势，可以了解进化的程度以便决定是否继续下去.GA求解最优化问题的一个目的是得到最优解，于是需要了解GA求最优解的功效.有一些测试函数,见[2]p21Goon20约束机器排序(CapacitatedMachineScheduling)n个加工量为的产品在一台机器上加工，机器在第t个时段的工作能力为Ct，求出所有产品得以加工的最少时段数.1,2,...,idin数学模型：11..1110,1,1;1TittniittiitminTstxindxCtTxintT111min..111,0,1,1.njjnijjniijjjiijjzwstxindxCwjnxwijn区别？21一个自然的编码——决策变量的0–1码问题：1、T的估计；2、可行性.是一个n×T的向量每个解用一个nT的向量表示，解空间中共有2nT个解，若假设每个时段最多可以加工P个产品，则至少有2(n-P)T-1个解是不可行.一个有效的编码方法是给产品（1，2，…，n）一个加工序（i1，i2，…，in）,由加工序按能力约束以最小的剩余能力依次安排时段加工,在加工的过程中不允许改变产品的加工序.如产品需求为(d1=5，d2=3，d3=10，d4=4)，前五个时段可提供能力为(3，9，10，5，20)，若按（1，2，3，4）顺序加工，各时段加工的产品为：第一个时段不加工，第二个时段加工产品1和2，第三个时段加工产品3，第四个时段加工产品4.最优解为第一时段加工产品2，第二时段加工产品1和4，第三时段加工产品3，最优序为(2，1，4，3).22§2实现的技术问题1、当前最好解（best–so–far）方法在每一代的进化中,记录下最好的解,通过这个最好解展示算法的效果.这个最好解可以用于不同算法的横向比较；如果知道问题的界，也可以自身比较它的功效.2、在线（on–line）比较法用进化过程中的每一个解来了解进化趋势其计算公式：11()()(*)TonlinetvTvtT其中T为当前计算中群体中出现的染色体总数,v(t)为第t个染色体的目标值.23第七章遗传算法2、离线（off–line）比较法*11()()(**)TofflinetvTvtT其中T为当前计算中出现的遗传代数，v*(t)为第t代前（包括第t代）时，所得最优值.即*()*(1),*(2),...,*(1),*(())vtmaxvvvtvpopt*(())vpopt表示中的最优目标值.()poptNote(*)与(**)中t的区别：在（*）中t表示第t个染色体；而（**）中t表示第t代.(**)的另一种理解方法是v*(t)为第t代时所得的最优目标值，即()*()()(***)ipoptvtmaxvi这与best–so–far方法类似.24§2实现的技术问题从直观可以看出，当优化问题是