智能控制技术(第7章-遗传算法).ppt

7.3.5交叉算子 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体， 从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环 节。模仿这个环节，在遗传算法中也使用交叉算子来产生新的个体。 遗传算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交 换其部分基因，从而形成两个新的个体。 交叉算子的设计和实现与所研究的问题密切相关，一般要求它既不要太多地破 坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的 新个体模式。另外，交叉算子的设计要和个体编码设计统一考虑。 交叉算子的设计包括以下两方面的内容: (1) 如何确定交叉点的位置? (2) 如何进行部分基因交换? 单点交叉 ( One-point Crossover ) (1) 单点交叉：又称为简单交叉，它是指在个体编码串中只随机设置一个交叉点， 然后在该点相互交换两个配对个体的部分染色体。 (2) 特点：若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度 的话，则这种单点交叉操作破坏这种个体性状和降低个体适应度的可 能性最小。 双点交叉与多点交叉 (1) 双点交叉 ( Two-point Crossover )： 指在个体编码串中随机设置了二个交叉点，然后再进行部分基因交换。 (2) 双点交叉的具体操作过程 Ⅰ. 在相互配对的两个个体编码串中随机设置两个交叉点。 Ⅱ. 交换两个个体在所设定的两个交叉点之间的部分染色体。 例如： (3) 多点交叉 ( Multi-point Crossover )： 指在个体编码串中随机设置多个交叉点，然后进行基因交换。多点交叉又称为 广义交叉。 (4) 操作过程：与单点交叉和双点交叉相类似。 例如，三个交叉点时的交叉操作示例： (5) 说明： 一般不大使用多点交叉算子，因为它有可能破坏一些好的模式。事实上， 随着交叉点数的增多，个体的结构被破坏的可能性也逐渐增大。 均匀交叉 ( Uniform Crossover ) (1) 均匀交叉：指两个配对个体的每一个基因座上的基因都以相同的交叉概率进 行交换，从而形成两个新的个体。均匀交叉实际上可归属于多点 交叉的范围。 (2) 操作过程： Ⅰ. 随机产生一个与个体编码串长度等长的屏蔽字 W = w1 w2 … wi … wl , 其中l为个体编码串长度。 Ⅱ. 由下述规则从A、B两个父代个体中产生出两个新的子代个体 A’ 、B’ : ? 若 wi = 0，则A’ 在第i个基因座上的基因值继承A的对应基因值，B’ 在第i个 基因座上的基因值继承B的对应基因值； ? 若 wi＝l，则A’ 在第i个基因座上的基因值继承B的对应基因值，B’ 在第i个 基因座上的基因值继承A的对应基因值。 例如，均匀交叉操作的示例如下: 算术交叉 ( Arithmetic Crossover ) (1) 算术交叉：由两个个体的线性组合而产生出两个新的个体。 (2) 进行算术交叉的条件：为了能够进行线性组合运算，算术交叉的操作对象一 般是由浮点数编码所表示的个体。 (3) 算术交叉产生的新个体： 式中： x 为个体； ?为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀 算术交叉； 它也可以是一个由进化代数所决定的变量，此时所进