遗传算法的基本理论

遗传算法的基本理论一、起源：早在20世纪50年代和60年代，就有少数人几个计算机科学家独立地进行了所谓的“人工进化系统”研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。早期的研究形成了遗传算法的雏形，如大多数系统都遵循“适者生存”的仿自然法则，有些系统采用了基于群体（population）的设计方案，并且加入了自然选择与变异操作，还有一些系统对生物染色体编码进行了抽象处理，应用二进制编码。由于缺乏一种通用的编码方案，人们只能依赖变异而非交叉来产生新的基因结构，早期的算法收敛甚微。20世纪60年代中期，美国Michigan大学的JohnHolland在A.S.Fraser和H.J.Bremermann等人工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉（即杂交）操作。并且强调将交叉作为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行为的研究中，并于1975年出版了其开创性著作“AdaptioninNaturalandArtificialSystem”。以后，Holland等人将该算法加以推广，应用到优化及机器学习等问题中，并正式定名为遗传算法。遗传算法的通用编码技术和简单有效的遗传操作作为其广泛、成功地应用奠定了基础。Holland早期有关遗传算法的许多概念一直沿用至今，可见Holland对遗传算法的贡献之大。他认为遗传算法本质上是适应算法，应用最多的是系统最优化的研究。二、发展：年份贡献者内容1962Holland程序漫游元胞计算机自适应系统框架1968Holland模式定理的建立1971Hollstein具有交配和选择规则的二维函数优化1972Bosworth、Foo、Zeigler提出具有复杂变异、类似于遗传算法的基因操作1972Frantz位置非线性和倒位操作研究1973Holland遗传算法中试验的最优配置和双臂强盗问题1973Martin类似遗传真法的概率算法理论1975DeJong用于5个测试函数的研究基本遗传算法基准参数1975Holland出版了开创性著作《AdaptationinNaturalandArtificialSystem》1981Bethke应用Walsh函数分析模式1981Brindle研究遗传算法中的选择和支配问题1983Pettit、Swigger遗传算法应用于非稳定问题的粗略研究1983Wetzel用遗传算法解决旅行商问题(TSP)1984Mauldin基本遗传算法小用启发知识维持遗传多样性1985Baker试验基于排序的选择方法1985Booker建议采用部分匹配计分、分享操作和交配限制法1985Goldberg、LingleTSP问题个采用部分匹配交叉1985Grefenstette、Fitzpattrick对含噪声的函数进行测试1985Schaffer多种群遗传算法解决多目标优化问题1986Goldberg最优种群大小估计1986Grefenstette元级遗传算法控制的遗传算法1987Baker选择中随机误差的减少方法1987Goldberg复制和交叉时最小欺骗问题(MDP)1987Goldberg、Richardson借助分享函数的小生境和物种归纳法之后，遗传算法发展的趋势是遗传算法的改进（如自适应遗传算法、分层遗传算法、并行遗传算法、基于小生境技术的遗传算法等）和基于遗传算法与其他算法相结合的混合智能优化算法（如量子遗传算法、协同遗传算法、免疫遗传算法等）。三、基本原理：1、生物进化论与遗传学的相关原理达尔文进化论主要有四个学说：一般进化论、共同祖先学说、渐变论和自然选择学说。其中自然选择学说的主要内容为：自然选择来自繁殖过剩和生存斗争。由于弱肉强食的生存斗争不断地进行，其结果是适者生存，具有适应性变异的个体被保留下来，不只有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，物种变异被定向着一个方向积累，于是性状逐渐和原先的祖先种不同，演变为新的物种。这种自然选择过程是一个长期的、缓慢的、连续的过程。关于达尔文的进化论有很多的争议，可以参考文献[1]。孟德尔遗传定律：分离规律和自由组合定律。种群遗传学：这是一种以种群为单位而不是以个体为单位的遗传学，是研究种群中基因的组成及其变化的生物学。在一定地域中，一个物种的全体成员构成一个种群(population)，种群的主要特征是种群内的雌雄个体能够通过有性生殖实现基因的交流。生物的进化实际上是种群的进化，个体总是要消亡，但种群则是继续保留，每一代个体基因型的改变会影响种群基因库(genepool)的组成。而种群基因库组成的变化就是这一种群的进化，没有所谓的生存斗争问题、单是个体繁殖机会的差异也能造成后代遗传组成的改变，自然选择也能够进行。综合进化论对达尔文式的进化给予了新的更加精确的解释。至于基本概念的定义详见参考文献[2]中的“遗传算法扼要”。2、遗传算法的基本思想遗传算法模拟的是怎样的生物进化模型呢?假设对相当于自然界中的一群人的一个种群进行操作，第一步的选择是以现实世界中的优胜劣汰现象为背景的；第二步的重组交叉则相当于人类的结婚和生育；第三步的变异则与自然界中偶然发生的变异是一致的。我们用专业术语来更好地描述遗传算法的基本思想。遗传算法是从代表问题可能潜在解集的一个种群(population)开始的，而一个种群则由经过基因(gene)编码(coding)的一定数目的个体(individual）组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现(即基因型)是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代(generation)演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度(fitness)大小挑选(selection)个体，并借助于自然遗传学的遗传算子(geneticoperators)进行组合交叉(crossover)和变异(mutation)．产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码1987Goldberg、Segrest复制和交叉的有限马尔可夫链1987Goldberg、Smith双倍染色体遗传算法应用于非稳定函数优化1987Oliver、Smith、Holland排列重组算于的模拟和分析1987Schaffer、Morishima串编码自适应交叉试验1987Whitley子孙测试应用于遗传算法的选择操作(decoding)，可以作为问题近似最优解。3、遗传算法的基本步骤第l步随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码；第2步计其个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第3步；第3步依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；第4步按照一定的交叉概率和交叉方法，生成新的个体；第5步按照一定的变异概率和变异方法，生成新的个体；第6步由交叉和变异产生新一代的种群，返回到第2步c注：遗传算法中的优化准则，一般依据问题的不同有不同的确定方式。例如，可以采用以下的准则之—，作为判断条件：①种群中个体的最大适应度超过预先设定值；②种群中个体的平均适应度超过预先设定值；③世代数超过预先设定值。四、实例：例1、采用遗传算法与非线性规划的方法求解如下函数的极小值：1234512345()5sinsinsinsinsinsin5sin5sin5sin5sin58fxxxxxxxxxxx其中，12345,,,,xxxxx是0~0.9之间的实数。该实数的最小值为-2，最小值位置为(/2,/2,/2,/2,/2)。解：a、算法流程非线性规划遗传算法的算法流程如下图所示：其中，种群初始化模块根据求解问题初始化种群，适应度值计算模块根据适应度函数计算种群中染色体的适应度值，选择、交叉和变异为遗传算法的搜索算子，N为固定值，当进化种群初始化适应度值计算选择交叉变异进化次数是N的倍数？非线性满足终止条件？结束YYNN次数为N的倍数时，则采用非线性寻优的方法加快进化，非线性寻优利用当前染色体值采用函数fmincon寻找问题的局部最优值。b、遗传算法实现1、种群初始化由于遗传算法不是直接处理问题空间的参数，因此必须通过编码把要求问题的可行解表示成遗传空间的染色体或者个体。常用的编码方法有位串编码、Grey编码、实数编码（浮点法编码）、多级参数编码、有序串编码、结构式编码等。实数编码不必进行数值交换，可以直接在解的表现型上进行遗传算法操作。因此本题采用该方法编码，每个染色体为一个实数向量。2、适应度函数适应度函数是用来区分群体中个体好坏的标准，是进行自然选择的唯一依据，一般是由目标函数加以变换得到。本题是求函数的最小值，把函数值的倒数作为个体的适应度值。函数值越小的个体，适应度值越大，个体越优。适应度计算函数为1[()]()Ffxfx3、选择操作选择操作从旧群体中以一定概率选择优良个体组成新的种群，以繁殖得到下一代个体。分体被选中的概率适应度值有关，个体适应度越高，被选中的概率越大。遗传算法选择操作有轮盘赌法、锦标赛法等多种方法，本题选择轮盘赌法，即基于适应度比例的选择策略，个体i被选中的概率为1iiNjjFpF其中，iF为个体i的适应度值；N为种群个体数目。4、交叉操作交叉操作是指从种群中随机选择两个个体，通过两个染色体的交换组合，把父串的优秀特征遗传给子串，从而产生新的优秀个体。由于个体采用实数编码，所以交叉操作采用实数交叉法，第k个染色体ka和第l个染色体la在j位的交叉操作方法为(1)(1)kjkjljljljkjaababaabab其中，b为[0,1]区间的随机数。5、变异操作变异操作的主要目的是维持种群多样性。变异操作从种群中随机选取一个个体，选择个体的一点进行变异以产生更优秀的个体。第i个个体的第j个基因ija进行变异的操作方法为其中，maxa是基因ija的上界；mina是基因ija的下界；22max()(1/)fgrgG，2r是一个随机数，g是当前迭代次数，maxG是最大进化次数，r为[0,1]区间的随机数。6、非线性寻优遗传算法每进化一定代数后，以所得到的结果为初始值，采用MATLAB优化工具箱中线性规划函数fmincon进行局部寻优，并把寻找到的局部最优值作为新个体染色体继续进化。c、MATLAB程序实现%%遗传算法参数maxgen=200;%进化代数，即迭代次数sizepop=20;%种群规模pcross=0.6;%交叉概率选择，0和1之间pmutation=0.01;%变异概率选择，0和1之间lenchrom=[11111];%每个变量的字串长度，如果是浮点变量，则长度都为1bound=[00.9*pi;00.9*pi;00.9*pi;00.9*pi;00.9*pi];%%个体初始化individuals=struct('fitness',zeros(1,sizepop),'chrom',[]);%种群结构体%初始化种群fori=1:sizepop%随机产生一个群体individuals.chrom(i,:)=unifrnd(0,0.9*pi,[1sum(lenchrom)]);%随机产生染色体x=individuals.chrom(i,:);individuals.fitness(i)=fun(x);%染色体的适应度end%找最好的染色体[bestfitnessbestindex]=min(individuals.fitness);bestchrom=individuals.chrom(bestindex,:)