遗传算法又叫GA算法

1、智能优化算法(:遗传算法之一)，太原科技大学张学良，大自然充满了奇迹和活力，生命的繁衍更加神奇。人类从自身进化中学习提高决策问题的能力是因为自然进化过程的本质就是学习和优化的过程。这个优化过程的目的是使生命符合环境的最佳结构和效果。1.1遗传算法的起源和生物学基础，统治地球的恐龙因为巨大的身躯赶不上环境的变化而灭绝了；长颈鹿为了寻找食物，伸长了脖子；老鼠的机敏是为生存而奋斗的结果。青蛙的生存归功于两栖动物的能力。人类多亏了类人猿的生存努力，解放了强大的双手。与其他动物不同，这双手不再用于散步，使人类成为这个世界的主宰。自然进化遵循达尔文发现的自然进化规律事物和适者生存的惊人规律。自然界，特别是

2、生物界神奇的进化过程是不断优化的过程。现代基因工程的研究成果不断暴露出这一过程的本质机制。为什么人们不能引自然界为师，把生物学进化的一些基本概念和机制引入工程问题研究？1975年，霍兰德提出了基于人工适应系统中设计的一种自然进化原理的搜索机制基因遗传优化计算机模拟遗传算法的基本概念和技术。遗传算法是基于自然选择和遗传机制在计算机上模拟自然生物进化过程和机制的优化搜索仿生智能算法，其机制是所有生命和智能的生成和进化过程。模拟达尔文自然进化规律的原理，激励好的结构，模拟孟德尔的遗传变异理论，在迭代过程中保持现有结构，寻找更好的结构。是一种自我配置、自适应的人工智能技术。自然界的生物从他们的父母那里

3、继承特征或形态，这种生命现象称为遗传，研究这种生命现象和机制的科学是遗传学。自然有稳定的物种，人们种植甜瓜，种大豆，鱼还在水里游来游去，这也是原因。自然界不不断重复、稳定持久的原因，也能从这点得益。构成生物的基本结构和功能单位是细胞(Cell)。细胞的小思想化合物叫做染色体，生物的所有遗传信息都包含在这个复杂的小染色体里。遗传信息由基因(Gene)组成，生物的各种特性由该基因决定，基因是该遗传的基本单位。细胞通过分裂具有自我复制能力，在细胞分裂的过程中，其遗传基因也同时复制到下一代，其性状也继承到下一代。遗传学被封装在所有细胞内作为一个指令遗传代码，每个细胞都有特殊的位置，以调节特定特性的基因

4、形式包含在基因中，认为每个基因产生的个体对环境有一定的适应性。细胞分裂时，遗传物质DNA通过复制(Reproduction)转移到新生成的细胞，新细胞就会继承旧细胞的基因。这就是子代与父代类似的主要原因。此外，细胞复制过程中的概率很低，但DNA中的特定基因发生变异，可能产生新的染色体。这就是子代与父代相似，但不完全相同的原因。否则，它可能不是所谓的遗传，而是克隆。这个新染色体显示了新的特性。这样的话，遗传基因或染色体在遗传过程中会因多种原因而变形。生物在继续生存的过程中逐渐适应自己的生活环境，持续改善其质量的生命现象称为进化。生物的进化是以集体的形式一起进行的，这些组织称为人口或群体，组成群体

5、的个别生物称为个体。每个生物个体对自己的生活环境有不同的适应能力，称为个人适应能力。达尔文的自然选择说，通过不同生物之间的交配及其他几个原因，生物的基因变异，产生新的生物基因，这部分变异的基因也遗传到下一代。这种变化的概率是可以预测的，但有些个体发生变化是偶然的。这个新基因根据适应环境的程度决定增殖能力，有利于生存环境的基因越来越多，对生存环境不利的基因越来越少。多亏了这种自然的选择机制，物种将逐渐向适应生存环境的方向进化，创造出越来越适应环境的物种。不符合环境的物种也会逐渐灭绝，消失无踪。这是“自然选择，适者生存”的原则。1染色体上有生物的所有遗传信息(基因)，染色体上有个人的生物学特性(表

6、现型)，表现型决定了个人对环境的适应能力。2有机体的基因在染色体上呈线性排列，可以认为所有遗传和进化过程都发生在染色体上。3生物的繁殖是克隆该基因，交叉重组是性生殖基因克隆的基本形式。4同源染色体之间的交叉或染色体上基因的突变(突变)，产生新的物种，使有机体呈现新的形态，变异从根本上保证了物种的进化。5大自然根据个体数的适应度决定是否在群体中生存。适应环境的基因或染色体比不适应的基因或染色体更有可能遗传到下一代。6竞争存在于生物群落、人口和种群之间，其竞争是无限扩张趋势下的生物除以有限资源的直接结果，也是物种进化的促进剂。7竞争必须有选择，自然选择是生物进化最基本的法则。1.2遗传算法的基本原

7、理，遗传算法是基于自然选择和遗传机制在计算机上模拟生物进化机制的优化搜索仿生智能算法，仿真机制是所有生命和智能的生成和进化过程。生物体在自然界的进化过程中，通过遗传(与祖先、后代、双亲非常相似)、变异(后代与双亲不完全相似)适应外界环境，一代和一代通过适者生存、繁殖而进化。GA模拟这种进化现象，并将搜索空间(问题解答的归属空间)映射到遗传空间。也就是说，将每个可能的解决方案编码为一个矢量(二进制或十进制数字或字符串)，一个染色体或对象，矢量中的每个元素称为基因，所有染色体组成组或对象，按预定目的函数(或特定评价指标)评估每个染色体，并根据该评价结果给出适当值。算法最初随机生成一些染色体(即所需

8、问题的侯解决方案)，计算其适应性，根据适应性图选择各种染色体，通过交叉(杂交)、变异等遗传操作，消除不适应(性能不好，不适合环境)的染色体，适应性高(性能好，适合环境)的染色体新组的成员是上一代的优秀人员，继承了上一代的优秀性能，比上一代的优秀。GA重复这种重复操作，并朝着更好的解决方案方向进化，直到满足某个预定的优化收敛指标。1.3遗传算法的一些基本概念，个体、人口和人口大小、适合函数、生物群体的染色体、设计向量映射到遗传空间的一个编码串。具体来说，是许善池。一个生物群是一个群体，其中生物的总数就是个体大小。编码字符串的总数。，适应度在评价生物个体适应环境生存能力的大小或个体性能优劣的指标和

9、染色体之间有一定的关系。1.4遗传算法的默认操作符“选择操作符”(Selection)也称为生殖、再生或克隆操作符，用于模拟生物界良好的自然选择现象。它是从古老的个体中挑选适应能力好的(适应度高的)特定的个体(染色体)，通过染色体交叉和变异，加入一组匹配(交配或交配)来创造新的群体。适应度越高的染色体被选择，其遗传基因在下一代中分布得越多，其后代(后代)在下一代中出现得越多。选择是遗传算法中最主要的运算符(机制)，也是影响遗传算法性能的最主要因素。但是选择只能从旧的群体中挑选优秀者，不能制造新的染色体。“选取压力”(Selection Pressure)说明了选取操作符从群体中选择其他对象作为

10、母体的概率大小的差异。如果选择压力太大，一些更好的可行解决方案(不一定是全局最优解决方案)将迅速占据整个总体。如果把选择按得太小，算法就会显示出纯粹的随机漫步行为。选择各种方法，如适合比例方法、顺序方法、可变性函数的比例转换、出色的选择。其中适合度比方法是具有选择压力过大或太小的缺点的比较普遍的战略。也称为旋转法，适应度比率选择法将人口中所有染色体的适应度视为一圈的圆周，每条染色体根据其适应度在整个过程中所占的比例占车轮的一个扇区。每条染色体的选择可以看作是轮子的随机旋转，如果哪个扇区停止了，那么选择哪个扇区对应的染色体呢？这个选择是随机的，但与每个染色体的适应度成正比。因为适应性大的染色体占

11、轮扇区区域，选择概率高(机会多)，而适应性小的染色体占扇区区域面积小(机会少)，选择的概率低。例如，交叉(Crossover，也称为hybrid)运算符，选择运算符虽然在旧群体中可以选择优秀的人，但不能创造新的染色体，遗传算法的创始人提出交叉运算符。交叉算子用于模拟生物进化过程中的生殖杂交现象，通过两个染色体的交叉结合生成新的染色体。也就是说，在重合集中随机选择两个染色体(也称为双亲)的一个交点(称为单点交点，单点交点)，交换双亲染色体交点的右侧部分，得到两个新的染色体(后代)。交叉结果有可能互补个体的优点，产生更好的后代。交叉运算符可以创造新的染色体，测试搜索空间中发生的新点，因此反映了自然

12、界信息交换的思想。变异运算符、选择运算符和交叉运算符实现了遗传算法的广泛搜索过程，而变异的目的是提高遗传算法的最佳解决方案搜索能力。突变运算符用于在各种偶然因素的自然遗传环境下模拟生物的基因突变，以极小的概率随机改变基因(代表染色体的数字串之一)的值。在染色体以二进制编码的系统中，随机将染色体上的一个基因从1变为0，或者从0变为1。如果只有选择和交叉运算符，没有变异运算符，则不能在初始基因组合以外的空间进行搜索，因此在进化过程的早期，陷入局部解决方案，进化过程结束，解决方案的质量受到极大限制。通过突变运算符，可以确保组内基因类型的多样性，使搜索尽可能多的空间进行，防止搜索中有用的遗传信息丢失并

13、落入本地解决方案中，从而获得更好质量的优化解决方案。变异操作符从单个空间随机映射到单个空间，其工作方式是将单个组件的值独立更改为概率Pm。Pm称为变异概率。遗传算法的上述三个基本运算符(选择、交叉和变异运算符)各有其功能。通过选择，可以找到局部最优值，通过变异，搜索空间可以分布在整个空间中，并且相交结果可能依赖于初始分布。因此，完整的遗传算法必须由选择、交叉和变异运算组成。1.5遗传算法实现例如，假设快餐店追求的目标是最高利润，要实现这一目标，必须选择适当的经营战略。一个可能的策略是对以下三个问题做出决定：1)每盘炒饭价格为5韩元或10韩元2)配米粉的饮料提供可乐或椰子汁3)快速时间或缓慢的线

14、路服务下面介绍用遗传算法解决这个决策问题的方法和过程。(1)用染色体数字字符串(问题代码)表示问题的可能解法。因为这个问题有三个决定变量，可以用是或否、1或0表示，所以可能的业务策略可以用三个二进制数字表示，答案的搜索空间是23=8，也就是8个业务策略。表3显示了快餐店经理知道的4种经营战略(早期解决方案)。表中数字字符串的前0表示高价格，1表示低价格。第二个0表示椰子汁，1表示非常可乐。第三个0为慢服务排队，1表示快服务。a)求出每条染色体的适应性。在这个问题上，一条染色体的适合性恰好等于其二进制字符串的十进制数，也是相应经营战略的收益。b)选择进入交叉集的染色体在表4中可见，所有染色体串的

15、适应度总和为12，数字串110的适应度为6，适应度也表示总和的1/2。也就是说，有两次选择该字符串的机会，其概率是1/2；选择字符串011、001和010的概率分别为3/12=1/4、1/12、2/12=1/6。根据上述适宜性比例方法，进入交叉集的染色体字符串及其适合性值见表5。从表5看，选择运算符的作用是提高群体的平均适应度，使其从原来的3到4.25，最差的适应度从原来的1到2，性能最低的染色体从群体中删除。但是选择不能创造新的染色体，为了改善这个缺点，为了在搜索空间内找到新的检测点，必须进行交叉操作。c)在交叉运算中使用单点交叉运算符随机生成的交叉是2，在交叉集中取一对染色体(例如011和110)，交换第三位以获得后代(后代)染色体010和111。其中，111是通过交叉操作符操作而形成的新染色体。在这个例子中，由于交叉概率为0.5，所以交叉集中剩下的两个染色体不再参与交叉运算，与交叉操作后获