一种改进操作算子的加速收敛遗传算法

摘 要：针对基本遗传算法效率低和易早熟的缺陷，提出了一种改进操作算子的遗传算法。该算法在种群初始化、选择、交叉、变异等基本算子的基础上加以改进，使算法具有更好的适应性。对3组不同函数的测试表明，改进算法较传统的遗传算法具有在种群很小的情况下收敛速度快稳定性高的优点，同时能有效地避免早熟现象。
关键词：遗传算法；变异；收敛速度；种群数

0 引 言
    遗传算法(Genetic Algorithm，GA)是一种宏观意义下的仿生算法，它模仿的机制是一切生命与智能的产生与进化过程，从一个初始种群出发，不断重复执行选择，杂交和变异的过程，使种群进化越来越接近某一目标。它通过模拟达尔文“优胜劣汰，适者生存”的原理激励好的结构；通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。经典遗传算法的求解步骤为：初始化种群；选择；交叉；变异；判断终止条件。由于它简单有效，具有很强的鲁棒性和通用性，所以被广泛应用于模式识别、神经网络、图像处理、机器学习、工业优化控制、自适应控制、生物科学、社会科学等多种领域。
    早熟和收敛时间过长是影响遗传算法效率的两个主要因素，而选择压力过大是导致早熟收敛的一个重要原因，为此不少学者对遗传算法做了改进，但仍存在一定局限性。在此对遗传算法个操作算子加以改进，通过对经典多极值测试函数的仿真研究表明，改进后的算法能够有效避免早熟且在种群规模较小的情况下具有较快的收敛速度。

l 改进操作算子的遗传算法
    经典遗传算法的把变异作为一种辅助手段，认为变异只是一个背景机制，这一观点与生物学中的实际观察是相符的，但作为设计人工求解问题方法的思想，他正受到理论与实践两方面的挑战。另外，从微观角度来讲，变异随时都有可能发生，如果突变向不好的方向进行．其“修复系统”立刻就能对其进行修复。基于以上两点，这里在选择与交叉算子中渗入不同的变异行为，且动态改进变异算子，使算法能快速达到全局最优。
1．1 初始化
    为了改善初始群体的效能，提高模式的优良度，采取如下方法：先随机产生一个父染色体，对其进行一定次数(20次左右)的逐位精英选择高频变异，方法如下：例如染色体为01001，先把第一位变异为1，成为11001。若适应度提高，则此位以很大的概率p(如O．98)转换为1，否则以很小的概率(如0．01)转换为1，以此类推。接着产生具有一定规模的染色体种群，随机使其中每个染色体的某段基因与之前父染色体相应基因段保持一致。如：假设父染色体为00110，随机产生个体10101，若以第一和第二位基因与父染色体一致，则该个体变为：00101。该方法把较优秀的模式分散到各个染色体中，使它一开始就具有一定概率的优秀短模式，从而有效提高算法的寻优效率。
1．2 选择操作
    经典遗传算法根据适者生存原则选择下一代个体。在选择时，以适应度为选择原则。适应度准则体现了适者生存，不适应者淘汰的自然法则。
    然而基于适应度的概率选择机制如轮盘赌选择法在种群中出现个别或极少数适应度相当高的个体时，就可能导致这些个体在群体中迅速繁殖，经过少数迭代后占满了种群的位置。这样，遗传算法的求解过程就结束了，也即收敛了。但这样很有可能使收敛到局部最优解，即出现早熟现象。为了从根本上避免早熟现象且加快收敛速度，采用基于高频精英变异的锦标赛选择法。其操作如下：假设竞赛规模为2，首先选取种群中第1和第2个个体X和Y
    如：X=100101，Y=011110
    从第1位开始比较适应值的大小，即当个体X与Y的第1位分别是1和O时，假设fitness(X)>fitness(Y)，于是把Y的第1位由0高频变异为1，此时：
    X=110101，Y=101110
此时，若fithess(X)<fithess(Y)，则把Y的第1位由1高频变异为O。如此下去，最终得到的为选择出的个体，其中较高位(如第1至L／3位，其中L为染色体长度)变异率为0．8，其他位变异率为0．95，理由是较高位的个体即使适应度低也有可能在附近变异成适应度更高的个体。
    然后选取种群中第2和第3个个体应用上法选择出第2个个体，这个过程重复进行，完成剩余个体的选择。这种算子在选择个体上就可以有方向性且极大地加快算法的收敛速度。
1．3 交叉操作
    交叉是把两个父个体的部分结构加以替换重组而生成新个体的操作，从而在下一代产生新的个体。它的目的是开发问题解空间中新的区域，寻找父个体已有的但未能合理组合的基因，尽量保证具有优良模式的个体不被交叉操作所完全破坏，同时增大种群的离散程度，产生新的搜索空间。所有交叉操作的一个共同特征是，不破坏两个父个体之间的公共串模式，允许继续搜索空间时保留好的模式。
    对于选中用于繁殖下一代的个体，随机地选择2个个体的相同位置，按交叉概率P在选中的位置实行交换。在选中的位置实行交换。这个过程反映了随机信息交换，目的在于产生新的基因组合，也即产生新的个体。在交叉时，可实行单点交叉或多点交叉。