遗传算法中的交叉运算与设计

遗传算法中的交叉运算，是指对两个互相配对的染色体以某种方式互相交换其部分基因，从而形成两个新的个体。遗传算法中，在交叉运算之前先对群体中的个体进行配对，最常用的配对策略是随机配对。交叉运算一般要求它既不要太多地破坏个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模式。另外，交叉算子的设计要和个体编码设计统一考虑。

交叉算子的设计包括两个方面的内容:如何确定交叉点的位置?如何进行部分基因交换?

1.单点交叉

单点交叉算子是最常用的交叉算子，它是指在个体编码串中只随机设置一个交叉点，然后在该点相互交换两个配对个体的部分染色体。单点交叉的重要特点是:若邻接基因座之间的关系能提供较好的个体性状和较高的个体适应度，则这种单点交叉操作破坏个体性状和降低个体适应度的可能性最小。

2.双点交叉与多点交叉

它是指在个体编码串中随机设置了两个交叉点，然后再进行部分基因交换。具体操作过程如下:

(1)在相互配对的两个个体编码串中随机设置两个交叉点。

(2)在所设定的两个交叉点之间交换两个个体的部分染色体。

将单点交叉和双点交叉的概率加以推广，可以得到多点交叉的概念。一般来说，不要使用多点交叉算子，它有可能破坏一些编码的模式。交叉点越多，优良模式被破坏的可能性越大。

3.均匀交叉

它是指两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新的个体。均匀交叉实际上可以归属于多点交叉的范围，其具体运算可通过设置一个屏蔽字来确定个体的各个基因是由哪一个父代个体来提供的。(www.xing528.com)

具体操作过程如下:

(1)随机产生一个与个体编码串长度等长的屏蔽字W＝w1w2…wi…wl，其中l为编码串长度。

(2)由下述规则从A，B两个父代个体中产生出两个新的子代A′，B′:若wi＝0，则A′在第i个基因座上的基因值继承A对应的基因值，B′在第i个基因座上的基因值继承B对应的基因值。

4.算术交叉

它是指由两个个体的线性组合而产生出两个新的个体，通常这类交叉操作的对象是浮点数编码所表示的个体。假设在两个个体之间进行算术交叉，则交叉运算后所产生出的两个新个体为

式中:α为一参数，它可以是一个常数，此时所进行的交叉运算称为均匀算术交叉；它也可以是一个由进化代数所确定的变量，此时称为非均匀算术交叉。

具体操作过程如下:

(1)确定两个个体进行线性组合时的系数α。

(2)依据上面公式生成两个新的个体。