遗传算法的基本原理与交叉方式

目前，遗传算法被广泛应用于函数优化、组合优化、图像处理等多个学科领域，是一类鲁棒性强的搜索算法。基本原理为：从可能潜在解集的一个包含多个基因编码个体的种群开始，按照适者生存和优胜劣汰的原理，逐代进化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群，致使后代种群比前代更加适应环境，且末代种群的最优个体通过解码可作为优化问题的近似最优解。在算法的运算过程中，主要涉及以下七个重要概念。

1.种群

种群中染色体（也称为基因个体）个数即种群规模。设种群的目标搜索空间为n维，则每个染色体由n个遗传基因组成。若种群空间表示为X，种群中第i（i＝1，2，…，m）个染色体表示为Xi＝（xi1，xi2，…，xin），xig（g＝1，2，…，n）则表示遗传基因。种群规模的大小直接影响算法的计算速度，一般种群规模不宜过大。

2.编码

通过编码方法可以将问题的可行解从解空间转换到遗传算法的搜索空间内。常用的编码方法有二进制编码、格雷码编码和浮点数编码等。

3.适应度

适应度指各个个体对生存环境的适应程度，是度量群体中各个个体在优化搜索中有可能达到或接近最优解的优良程度。表现适应度优劣的函数称为适应度函数，且适应度必须为正数或零。

4.选择(www.xing528.com)

通过选择操作，使当代群体中一些比较优良的个体复制到下一代群体中。常用的选择方式有比例选择、最优保存、采样选择等，个体被选中遗传到下一代的概率与适应度大小成正比。

5.交叉

群体内各个个体按一定的交叉概率互换部分染色体，构成新的种群个体。常用的交叉方式有单点交叉、多点交叉、均匀交叉等，交叉运算体现了遗传算法的全局搜索能力，交叉概率一般取为0.4～0.99。

6.变异

群体内各个个体按一定的变异概率改变某一个或一些基因值，产生新的个体。常用的变异方式有基本位变异、均匀变异、边界变异等，变异运算则体现了局部搜索能力，变异概率一般取为0.0001～0.1。

7.解码

将末代选出的最优个体通过之前的编码方式进行解码并映射到解空间，输出最优结果。