曹辛鑫，全海燕

(昆明理工大学 信息工程与自动化学院，云南 昆明 650500)

摘要：针对经典遗传算法的早熟及精度问题进行了研究，提出了一种基于随机基因实数交叉与多倍体策略的遗传算法。借鉴生物界中多倍体的概念，采用了实数编码并利用多倍体分别保存最优单体、保留单体及变异单体，从而组成多样性种群；选择操作采用了轮盘赌算法；交叉操作引入随机基因交叉概念。最后应用测试函数对算法进行测试，并与经典遗传算法进行了比较。仿真实验结果表明，该改进算法不仅保持了种群的多样性，有效抑制了早熟收敛，还降低了算法的复杂度，提高了搜索精度，使得算法能以较高的精度达到复杂高维度函数的全局最优。

0引言

遗传算法（GA）是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型［1］。 其搜索不依赖于梯度信息，不要求被优化对象，具有连续、可导、单峰等特性［23］。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域［47］。

然而，基本遗传算法会遇到早熟收敛现象［810］。为防止过早陷于局部最优，本文提出了多倍体概念，增加了种群中个体的多样性。其次，本文搜索过程是通过随机的基因交叉完成并通过多倍体策略保留的。

1随机基因实数交叉

本算法中寻优搜索过程是通过随机基因交叉完成的。在本文中设种群大小为m，个体上每个维度的变量用基因表示，每个染色体包含的基因数量为n。基因随机选取概率为p。根据p×n确定选取基因个数k，从每个染色体上随机选出k个（Ckn）做算术交叉。若设随机从父代染色体中选取出的一组基因为xir(t)，xis(t)；交叉操作后对应的基因xir(t+1)，xis(t+1)（1≤i≤n）由式（1）得出：

其中，λ是［0,1］间的随机数，并且每次交叉操作中的λ不同。

采用此种交叉操作可以有效提高局部勘探能力，并改善算法的搜索效率。

2多倍体搜索保存策略

本文引入生物学中的多倍体概念，即在个体中含有3个或3个以上的染色体组；提出的多倍体是由携带不同功能基因的染色体构成的，包括最优种群、保留种群和变异种群。每次搜索后多倍体保存的策略为：交叉后对得到的配子进行适应度值的计算，再根据以下步骤进行配子的保存：

（1）如果配子的适应度值优于最优单体，则用配子替换最优单体。而此时配种二倍体中保留的单体和变异单体保持不变，以保留父代信息，使优秀的信息不被破坏。

（2）如果配子的适应度值劣于最优单体，则最优单体保持不变，确保搜索方向不变。随机选取一个子代配子替换保留单体，而另一子代配子进行变异操作后替换变异单体，以增加种群的多样性。变异操作如下：

设变异概率为pm,xij(t)为父代第j个染色体中第i个基因，变异操作后得到的子代第j个染色体中第i个基因xij(t+1)，1≤i≤n,1≤j≤m，由式（2）得出：

其中，xmax表示搜索空间内基因的允许的最大值，xmin表示搜索空间内基因的允许的最小值，rand、rand’均表示［0,1］间的随机数。

3基于随机基因交叉与多倍体策略的遗传算法

根据以上描述的基本思想，本文对遗传算法进行了改进，以下是改进遗传操作的详细描述。

本文采用实数编码［10］，便于大空间搜索，可以减少算法的复杂度。并采用轮盘赌选择［11］，但同时，为了防止适应度值高的个体被淘汰，本文最优种群不参与选择操作，直接进入子代种群。在保留种群与变异种群组成的配种二倍体中进行轮盘赌选择操作，在选中的二倍体中随机选出一个染色单体，使之与最优种群个数相匹配并进入子代种群，从而与最优种群进行随机基因交叉操作。交叉概率通过实验确定，并将在4.1节中讨论不同概率的实验结果。产生的子代按照多倍体搜索策略进行取舍。具体步骤如下：

（1）设置控制参数，初始化进化种群，设定迭代次数变量t=0,最大迭代次数为T。

（2）计算所有个体的适应度值，保存最优种群，剩余的作为配种二倍体。

（3）检测t<T。若满足，继续；若不满足，则输出最优解，结束。

（4）最优种群中最优单体与配种二倍体进行随机基因交叉，产生新配子。

（5）计算新配子适应度值，排序。

（6）判断新配子与父代个体适应度值的优劣，依照多倍体保存策略进行个体替换。

（7）判断新个体数量是否小于种群个体个数。若小于种群个体个数，则转到步骤（4）,继续循环；若已经等于种群个体个数，则转到步骤（2），更换新种群。

4测试结果

本文选用了3个测试函数用MATLAB对多倍体遗传算法进行测试实验，实验中，设定参数为：实数编码，根据不同函数，染色体长度分别为f1=10、f2=2、f3=2。进化代数为1 000，种群个数为70，对每个测试函数，独立运行50次。

这3个测试函数在点（0,0,0,…,0）处取全局最优解为0。

4.1基因交叉概率实验分析

首先对算法本身的参数进行实验讨论。实验中选取的基因交叉概率分别为0.2、0.3以及0.4，而此时种群个数为70保持不变，进化代数为1 000。独立运行50次后，平均最优解的进化结果如图1~图3所示。

由图1~图3组可知，当维度低时，基因交叉概率越小，算法搜寻最优解速度稍快，但效果不是非常明显；当染色体维度较高时，基因交叉概率越小，算法搜寻最优解的速度明显越快，搜寻精度也有提高。

4.2对比实验结果

将多倍体遗传算法与经典遗传算法的搜索结果进行比较。

表1列出了两种不同方法的实验结果，其中SRGA为基本实数编码的遗传算法，RGPGA为本文提出的随机基因交叉和多倍体策略的遗传算法。表1中Optima表示寻到的最优解，AVG表示进行50次实验得到最优解的平均值，σ表示进行50次实验得到最优解的方差。

从表1中3个函数的实验结果可知，本文算法在搜索精度上有明显改进。无论函数维数的高低，本文算法都可以或近似搜寻到最优解，并且搜索结果相对稳定，未有大的波动。

5结论

通过对经典遗传算法的研究，得知算法中的交叉操作具有重要作用，决定了算法的最终收敛结果，并且影响着算法的收敛速度。与此同时，种群的多样性以及新个体获取信息的多样性又与交叉操作的效率有着密切关系。根据以上分析，提出了一种改进的遗传算法。引入多倍体概念，利用不同的种群保存不同功能的染色单体，从而增加种群的多样性。并且在多倍体的基础上提出了随机基因实数交叉以及多倍体搜索保存策略。通过3个测试函数对该算法进行了测试。仿真测试表明，该改进遗传算法有效抑制了早期收敛，提高了搜索的效率；从与标准遗传算法的比较也可以看出，该改进算法可以更加有效地求解高维度复杂函数的优化问题。

参考文献

［1］ HOLLAND J H. Adaptation in nature and artificial systems［M］. Cambridge MIT Press,1975.

［2］ 周明,孙树栋. 遗传算法原理及应用［M］. 北京：国防工业出版社，1999.

［3］ 陈国良,王熙法,庄镇泉，等. 遗传算法及其应用［M］. 北京：人民邮电出版社，1996.

［4］ NEBRO A J, DURILLO J J, LUNA F, et al. A cellular genetic algrithm for multiobject optimization［J］. International Journal of Intelligent Systems,2009,24:726746.

［5］ 吴永明, 吴晟. 改进的遗传算法在神经网络结构优化中的应用［J］. 微型机与应用, 2011, 30(3):7981.

［6］ 杜雯超, 陈其松, 周莹. 基于分段自适应遗传算法的图像阈值分割［J］. 微型机与应用, 2015, 34(3):5859.

［7］ 屈波. 基于GA优化的入口匝道可调模糊控制器设计［J］. 微型机与应用, 2014,33(8):9092.

［8］ PHOLDEE N, BUREERAT, S. Hybrid realcode populationbased incremental learning and approximate gradients for multiobjective truss design［J］. Engineering Optimization, 2014, 46(8):10321051.

［9］ 申晓宁，郭毓，陈庆伟，等. 一种保持群体多样性的多目标遗传算法［J］. 控制与决策，2008,23（12）：14351440.

［10］ 齐畅，王东霞，韩颖. 多种遗传算法在函数优化方面的性能比较分析［J］.辽宁工业大学学报（自然科学版），2013,33（5）：290293.

［11］ 王小平,曹立明.遗传算法——理论、应用与软件实现［M］.西安: 西安交通大学出版社，2002.