遗传算法的设计与实现.ppt

遗传算法的设计与实现 湖南大学软件学院 欧阳柳波 0 引言 通过理论分析，我们对遗传算法有更深入的认识，为解决实际问题提供了很好的指导，但通常情况下，由于实际问题不能满足理论分析所要求的前提条件，一些理论结果往往不能直接应用于实际问题中。 我们需要根据待解决的问题设计不同的遗传算子，选取不同的参数，从而使算法更有效。 在遗传算法实现上，编码方法、遗传算子的选择、控制参数的选取等都是十分关键的问题。 1 编码原则与方法 把优化问题的解的参数形式转换成基因链码的表示形式，这一转换操作就叫做编码，也可以称作是问题的表示(representation)。 一般来讲，由于遗传算法的鲁棒性，其对编码要求并不苛刻。大多数问题可以采用基于{0,1}符号集的二值编码形式。 编码的策略或方法对于遗传操作，尤其是对交叉操作的功能影响很大，因而编码问题常被称为编码-交叉问题。 1.1 编码原则（1） 通过编码后，问题的解由某种基因链码形式表示。我们称该基因链码的所有个体构成了表达空间。因此编码问题实际是从问题空间到表达空间的映射问题。 个体因一次变异所能迁移到的局部空间叫做变异近邻(mutation neighborhood)。由两个体进行一次交叉所能迁移到的局部空间叫交叉近邻(crossover neighborhood)。在GA空间中，由于交叉近邻是由两个个体所决定的，所以它比变异近邻迁移要大些。 如果编码方法和交叉处理不当，在遗传算法中因交叉产生的个体有可能成为无用解或无效解。编码策略与交叉策略互为依存，恰当地设计编码和交叉策略或方法，对于发挥遗传算法的功能十分重要。 1.1 编码原则（2） 设计编码策略时，常考虑以下3个问题： （1）完备性(completeness)：对于问题空间中的任一点都有表达空间的一个点与之对应。即问题空间的所有可能解都能表示为所设计的基因链码形式。 （2）健全性(soundness)：对于表达空间中的任一点都有问题空间中的一个点与之对应。即任何一个基因链码都对应一个可能解。 （3）非冗余性(non-redundancy)：问题空间和表达空间一一对应。 对于一些问题，很难设计出同时满足上述3个性质的编码方案，但完备性是必须满足的一个性质。在有些情况下，允许生成无用解，也允许不满足非冗余性。 1.1 编码原则（3） 为使编码设计能有效地提高算法的搜索效率，De Jong提出更为客观明确的编码评估准则，称之为编码原理或编码规则： （1）有意义基因块编码规则：所设计的编码方案应当易于生成与所求问题相关的短定义距和低阶的基因块。 （2）最小字符集编码规则：所设计的编码方案应采用最小字符集以使问题得到自然的表示或描述。 1.1 编码原则（4） 前章中求f (x)=x2，x?[0,31]函数极值的例子，其采用的是二进制5位编码方法。我们也可给出另一种非二值编码。该编码建立在32个字符组成的字符集基础上，其中包括{A-Z}共26个字符和{1-6}中的6个数字。这两种编码的部分对应关系如下表1： 1.1 编码原则（5） 为什么通常情况下要采用二值编码方案？ （1）显然，在二值编码情况下，群体码串的相似性很容易找到。在非二值编码情况下，码串的相似性很难观察到。 （2）实际上，如果不限制基因链码的长度，可以证明，使用二进制能表达的模式数最多。根据模式理论，一个编码方案应该能提供最多的模式。 （3）二进制编码方案符合最小字符集的编码规则。 1.1 编码原则（6） 旅行商问题：一个有穷的“城市”集合C={C1,C2,…,Cm}。 对于任意一对城市Ci,Cj?C，有“距离”d(Ci,Cj)?R+，要求从某个城市出发经过每个城市一次，且只经过一次，找出距离之和最小的路径。 考虑5个城市的旅行商问题，如下图，给问题的一个可行解，给了出如下两种编码表示方法。 （1）ABCDE （2）PABPACPADPAEPBCPBDPBEPCDPCEPDE = 1000100101 1.2 编码方法（1） 一维编码是指搜索空间的参数转换到遗传空间后，其相应的基因呈一维排列构成基因链码。即表示个体的字符集中的要素构成了字符串。 1.2.1 二进制编码 即将原问题的解映射成为0，1组成的位串，然后在串空间上进行遗传操作。结果再通过解码过程还原其解空间的解，然后再进行适应度值的计算。 （1）二进制编码的优点 ①能表达的模式数最多； ②简单易行； ③符合最小字符集编码原则； ④便于用模式定理进行分析。 1.2 编码方法（2） （2）二进制编码的缺点，尤其在求解连续优化问题时 ①相邻整数的二进制编码具有较大的Hamming距离，如15和16的二进制表示为0111