遗传算法编码及算子简介

遗传算法编码及算子简介遗传算法主要是通过遗传操作对群体中具有某种结构形式的个体施加结构重组处理，从而不断地搜索出群体中个体间的结构相似性，形成并优化积木块以逐渐逼近最优解。由此可见，必须把群体中的个体转化成按一定基因结构组成的染色体或个体，即编码。编码原则包括两条：1.有积极积木块编码规则，即所定编码应当易于生成所求问题相关的短距和低阶的积木块。2.最小字符集编码规则，即所定编码应用最小字符集以使问题得到自然的表示或描述。规则一是基于模式定理和积木块假设；规则二提供了一种更为实用的编码规则。评估编码策略常采用的规范有：1.完备性：问题空间中的所有点都能作为GA空间的点表现。2.健全性：GA空间中的染色体能对应所有问题空间中的候选解。3.非冗余性：染色体和候选解一一对应。这些评估规范是独立于问题领域的普遍准则。对某个具体的应用领域而言，应该客观化地比较和评估该问题领域中所用的编码方法。应用遗传算法进行优化，首先将问题描述成串的形式，以模拟染色体。选择何种编码方式对算法的运行有很大的影响。现在，流行的观点认为二进制编码能在相同的范围内表示最多的模式，能充分地体现所谓的隐含并行性。但是，二进制编码方式的精度依赖于染色体的基因位数及设计变量的范围。因而对于高精度、多变量问题，n值需很大，降低遗传算法的收敛速度。另外，二进制编码不直接反映真实的设计空间。其它的编码方式还有：格雷码编码、浮点编码、树结构编码、参数动态编码和多维编码等。遗传算法主要有选择、交叉和突变算子选择算子遗传算法使用选择算子或称复制算子来对种群中的个体进行优胜劣汰操作：选择算子使适应性高的个体在后代中生存的概率较大，而适应度低的个体生存的概率很小甚至被淘汰。遗传算法中的选择操作就是来确定如何从父代群体中按某种方法选取那些个体以传到下一代群体的一种遗传算法。选择操作是建立在群体中个体的适应度评价基础上的。选择操作的主要目的是为了避免基因缺失、提高全局收敛性和计算效率。在遗传算法中级很重要的作用。选择操作有多种方法，最常用的是轮盘赌法。在具体使用中，应根据问题求解的特点采用合适的方法或者混合使用。下面简单介绍各种选择算法：(1)比例选择算法基本思想是：各个个体被选中的概率与其适应度大小成正比，即适应度越高的个体被选中的概率也越大，反之则小。(2)最优选择算法在遗传算法的运行过程中，通过对个体进行交叉、变异等遗传操作而不断地产出新的个体。虽然随着群体的进化过程会产出越来越多的优良个体，但由于选择、交叉、变异等遗传操作的随机性，它们也有可能破坏掉当前群体中适应度最好的个体。由于随机操作的原因，这种选择方法的误差比较大，有时甚至连适应度较高的个体也选择不上，由此会降低群体的平均适应度，对算法的运行效率、收敛性都有不利的影响。一般说来，适应度最好的个体要尽可能地保留到下一代群体中。为此可以使用最优保留策略进化模型，即当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本代群体中经过交叉、变异等操作后所产生的是硬度最低的个体。最有选择算法的具体步骤是：1.找出当前群体中适应度最高的个体和适应度最低的个体。2.若当前群体中最佳个体的适应度比总的迄今为止最好的个体的适应度还高，则以当前群体中的最佳个体为新的迄今为止的最好个体。3.用迄今为止的最好个体替换掉当前群体中的最差个体。该方法可确保迄今为止所得到的最优个体不会被交叉、变异等遗传操作所破坏，它是遗传算法收敛性的一个重要条件。但另一方面，它也容易使得某个局部最优个体不易被淘汰掉反而快速扩散，导致算法的全局搜索能力下降。当然，该算法可以推广到在每一代的进化过程中保留多个最优个体不参加交叉、变异等遗传运算，而直接讲它们选择到下一代群体中。(3)确定式选择算法它是按照一种确定的方式来进行选择操作。(4)期望值选择算法根据每个个体在下一代群体中的生存期望值来进行随机选择运算。(5)无回放余数随机选择算法(6)排序选择算法主要思想是：对群体中的所有个体按期适应度大小进行排序，基于这个排序来分配各个个体被选中的概率。算法步骤为：1.对群体中的所有个体按其适应度的大小进行降序排序。2.根据具体求解问题设计一个概率分配表，将各个概率值按上述排列次序分配给各个个体。3.以各个个体所分配到的概率值作为其能够遗传到下一代的概率，基于这些概率值用比例选择的方法来产生下一代群体。该方法的实施必须根据对所研究问题的分析和理解情况预先设计一个概率分配表，这个设计过午一定规律可言。而且，虽然依据个体适应度之间的大小次序给各个个体分配了一个选择概率，但由于具体选择方法，所以排序选择方法仍具有较大的选择误差。(7)随机联赛选择算法它是一种基于个体适应度之间大小关系的选择算法。其基本思路是每次选取集各个体重适应度最高的一个个体遗传到下一代群体中。在联赛选择操作中，只有个体适应度之间的大小比较运算，而无个体适应度之间的算术运算。联赛选择中，每次进行适应度大小比较的个体数目称为联赛规模。交叉算子所谓交叉是指把两个父代个体的部分结构加以替换生成新个体的操作。这可以提高搜索力。在交叉运算之前还必须对群体中的个体进行配对。目前常用的配对策略是随机配对，即将群体中的个体以随机方式两两配对，交叉操作是在配对个体之间进行的。交叉算子主要有：一点交叉（不易破坏好的模型），双点交叉，多点交叉（又称广义交叉，一般不使用，随着交叉点的增多，个体结构被破坏的可能性逐渐增大，影响算法的性能），均匀交叉，算术交叉等。目前各种交叉操作形式上的区别是交叉位置的选取方式。下面简单介绍几种交叉方法。（1）单点交叉随机选取个体中的某基因位，从此位开始交换两亲本的后面部分序列，以产生两个子代。（2）两点交叉随机选取个体中的两个基因位，交换两亲本间部分。（3）OX交叉随机选择两个点，亲本在两个点间的部分被复制下来作为子代的一部分。子代的余下部分从对应亲本染色体的其余部分中，先选出第二个交叉点开始到它的最后一个基因位的基因按先后次序添入，然后再继续按次序取该染色体的第一基因位到第二交叉点的基因依次添入，其中跳过子代染色体中已含有的基因。此种方法能充分保留亲本代基因的相对次序。(4)PX交叉随机地选取几个位置，子代染色体的这些位置继承第一亲本的相应位置，子代染色体的其余位置按第二亲本中出现的次序添入，并跳过已含有的基因。此种方法保留有亲本的绝对位置信息。变异算子在生物的遗传和自然进化过程中，因为某些偶然的因素而导致生物的某些基因发生变异，从而产生出新的染色体，表现出新的生物性状。模仿生物遗传和进化过程中的变异环节，在遗传算法中也引入了变异算子来产生新的个体。变异运算就是将个体染色体编码串中的某些基因用其它的基因来替换。它是遗传算法中不可缺少的部分。目的就是改善遗传算法的局部搜索能力，维持群体的多样性，防止出现早熟现象。设计变异算子需要确定变异点的位置和基因值的替换，最常用的是基本位变异，它只改变编码串中个别位的基因值，变异发生的概率也小，发挥作用比较慢，效果不明显。变异算子主要有：均匀变异，它特别适于算法的初期阶段，增加群体的多样性；非均匀变异，随着算法的运行，它使得搜索过程更加集中在某一个重点区域中；边界变异，适用于最优点位于或接近于可行解边界的问题；高斯变异，改进了算法对重点搜索区域的局部搜索性能。算子的改进和新算子不断涌现。倒位操作，在染色体中选择两个倒位点，两点间的基因倒换位置。利用倒位作用的遗传算法能发现并助长有用基因的紧密形式。二倍体与显性操作，二倍体具有记忆能力，能解决动态环境下的复杂系统优化问题。显性操作具有鲁棒性，有利于提高算子的运算效率，维护好的搜索群体。针对不同的问题，人们研究出各种算子，不断的进行推广。遗传算法以个体的集合为运算对象，对个体所进行的各种操作都有一定的相互独立性，所以它具有一种天然的并行结构。对基本遗传算法的运行过程，为实现并行化，可以从个体适应度评价、整个群体中各个个体适应度评价、子代群体产生过程、群体分组几方面考虑。实现的方法可分为两类：标准型并行方法和分解性并行方法。前者并未改变串行遗传算法的基本特点，它需要一个全局存储器和一个统一的控制机构来协调群体的遗传进行过程及群体之间的通讯过程。这种方法对算法速度提高得不多，后者将整个群体分解为几个子群体，各个子群体分布在不同的处理机上进行基本的遗传算法，在适当的时候各处理机之间相互交换信息。对种群分组方法或模型有三种：踏脚石模型、岛屿邻近模型、邻接模型。