智能优化算法的基本思想与操作

1.遗传算法的基本思想

遗传算法的基本思想是模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量——染色体，染色体群一代一代不断进化，包括复制、交叉和变异等操作，通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。

2.遗传算法的基本操作

遗传算法包括三种基本操作：选择、交叉和变异。这些基本操作又有许多不同的方法，下面逐一进行介绍。

（1）选择

选择就是决定以一定概率从群体中选择若干个体的操作。一般而言，选择的过程是一个基于优胜劣汰的过程。在进行选择之前，首先应计算适应度，然后按适应度进行父代个体的选择。通常采用的选择方法有：

①适应度比例方法。目前最基本也是最常用的选择方法是适应度比例方法，该方法也称为轮盘赌或蒙特卡罗（Monte Carlo）选择。在该方法中，各个体的选择概率和其适应度值成比例。设群体大小为n，其中个体i的适应度值为fi，则i被选择的概率pi为

概率pi反映了个体i的适应度在整个群体的个体适应度总和中所占的比例大小。显然，个体的适应度越大，其被选择的概率就越高，反之亦然。

②最佳个体保存方法。把群体中适应度最高的，个体不进行配对交叉而直接复制到下一代中。采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏。但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能陷于局部解。该方法的全局搜索能力差，比较适合单峰性质的空间搜索。

③排序选择方法。在计算每个个体的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率表按顺序分配给个体，作为各自的选择概率。这种方法的不足之处在于选择概率和序号的关系需事先确定。此外，该方法和适应度比例方法一样都是一种基于概率的选择，所以仍存在统计误差。

（2）交叉

遗传算法中起核心作用的是遗传操作中的交叉。所谓交叉是指把两个父代个体的部分加以替换重组而生成新个体的操作。通过交叉，遗传算法的搜索能力得以显著提高。

设计交叉算子应考虑以下几点：

①交叉算子需保证前一代中优秀个体的性状能在后一代的新个体中尽可能得到遗传和继承。

②由于编码设计和交叉设计是相互联系的，要使设计出的交叉算子能够满足上述评估准则，交叉算子设计和编码设计需协调操作。这也就是所谓的编码—交叉设计。(www.xing528.com)

③对于占主流地位的二值编码而言，各种交叉算子都包括两个基本内容：一是从由选择操作形成的配对库中，对个体随机配对并按预先设定的交叉概率来决定每对是否需要进行交叉操作；二是设定配对个体的交叉点，并对这些点前后的配对个体的部分结构（或基因）进行相互交换。

以字符串编码为基础的基本交叉方法有以下几种：

①一点交叉（one-point crossover）。一点交叉又称为简单交叉，即在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分进行互换，并生成两个新个体。如下例所示：

②二点交叉（two-point crossover）。二点交叉的操作与一点交叉类似，只是设置两个交叉点（依然是随机设定）。如下例所示：

③多点交叉（multi-point crossover）。多点交叉是前述两交叉的推广，又被称为广义交叉。一般来讲多点交叉较少采用，它在某种程度上会影响遗传算法的在线和离线性能。

④一致交叉。一致交叉是指通过设定屏蔽字来决定新个体的基因继承两个旧个体中哪个个体的对应基因。

遗传算法的收敛性主要取决于作为核心操作的交叉算子。交叉算子的收敛性是当今遗传算法研究的最重要的课题之一，目前仍无系统而全面的论述。但是，通过局部的理论分析对于交叉收敛已有若干共识。

（3）变异

变异算子的基本内容是对群体中的个体串的某些基因位上的基因值作变动。就基于［0，1］字符集的二进值码串而言，变异操作就是把某些基因位上的基因值取反，即l→0或0→1。变异操作同样也是随机进行的，变异概率pm一般取得很小。

遗传算法中引入变异的目的有两个。一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解领域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。显然，此种情况下的变异概率应取较小值，否则接近最优解的积木块会因变异而遭到破坏。二是使遗传算法可以维护群体多样性，以防止出现未成熟收敛现象。

遗传算法的基本变异算子是指，对群体中的个体码串随机挑选一个或多个基因位，并对这些基因位的基因值做变动（以变异概率pm做变动），［0，1］二进制码串的基本变异操作如下例：

其中变异点在第二、第四基因位共两个，变异使个体的该两处的值取反，形成一个新的个体。

遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异算子因其局部搜索能力而作为辅助算子，遗传算法通过交叉和变异这一对相互配合又相互竞争的操作，而使其具备兼顾全局和局部的均衡搜索能力，所谓相互配合，是指当群体在进化中陷入搜索空间中某个超平面而仅靠交叉不能摆脱时，通过变异操作可以有助于这种摆脱。所谓相互竞争，是指当通过交叉已形成所期望的积木块时，变异操作有可能破坏这些积木块。

在问题的求解过程中，遗传算法就这样不断进行选择、交叉、变异操作，不断地进行迭代处理，群体一代一代朝着最大适应度值的方向进化下去，最终将得到最优解或近似最优解。