基于改进遗传算法的互补问题研究

董立娇

互补问题是数学规划中的一个重要分支，互补问题的求解对于实际问题有着重要的现实意义，但求解互补问题需要计算梯度信息，还需要给定准确的初始点［1］；并且大多数互补问题的解不唯一，应用传统的数学方法求解互补问题不能一次性得出解.因此，求解互补问题存在一定的困难，但随着近年来智能优化算法的广泛应用，如遗传算法、模拟退火算法、人工神经网络等，将这些智能优化算法［2］应用到求解互补问题中成了广大学者关注的问题，本文应用改进的遗传算法来求解互补问题，避免了传统的遗传算法在求解最优解时易陷于局部最优、过早收敛等问题，最后通过计算实例来验证算法的效率.

1　互补问题的光滑化

所谓互补问题是指，对于任意的向量x∈Rn，当 x≥0,F(x)≥0时，xTF(x)=0，其中F:Rn→Rn，表示两个决策变量之间呈现互补的关系，当F为线性函数（F(x)=Mx+q(M∈Rn×n,q∈Rn））时，称为线性互补问题，记为LCP()M,q；反之称为非线性互补问题，记为NCP()F.

常见的NCP函数有

为了求解上述非线性互补问题，基于上述式子不可微的特性，传统的数学方法对初始点的依赖较高，计算起来复杂困难，因此不能用传统的牛顿法、内点法来计算；为了克服非光滑性［3］，可以应用罚函数方法、乘子法等对其进行光滑化［4］.

为求解互补问题x≥0,f(x)≥0,xTf(x)=0的解，我们对其进行如下光滑逼近.

其中，μ＞0.

同样通过光滑化，可将（1）式光滑化为

其中，ε＞0.

同时引入凝聚函数将非线性互补问题转化为无约束优化方程组，应用凝聚函数.

利用极小值方法，可将上述求解非线性互补问题转化为下式.

所以求解非线性互补问题可以转化为求解下列光滑方程组问题.

用式（8）来近似代替方程组（6）.

2　基于互补问题的改进遗传算法

2.1　标准遗传算法

遗传算法是由达尔文的自然选择学说和孟德尔的遗传学说而来，通过生物界中适者生存、优胜劣汰的遗传机制演化为计算机语言的随机优化搜索方法，遗传算法在求解优化问题时不需要借助其他影响因素直接对问题进行求解，没有要求所求函数是否连续以及对函数进行求导分析等；与其他算法相比，遗传算法适合大量数据的全局搜索，在搜索过程中自动产生搜索空间，并适当地调整搜索方向，通过计算概率对染色体进行选择、交叉、变异，通过不同的编码技术来模仿不同环境中的自然选择，通过在搜索过程中获取和积累相关遗传信息，自适应地控制搜索过程以求得近似最优解.

由于遗传算法在整体搜索过程中无需梯度信息和初始点，只需列出所求互补问题的目标函数和约束条件，对互补问题进行光滑化处理，将互补问题转化为无约束优化问题，继而应用遗传算法求出互补问题的最优解，应用遗传算法计算互补问题可以提高传统数学方法在计算互补问题时的效率和稳定性.

2.2　改进的遗传算法

遗传算法作为近年来研究优化问题的智能算法，虽然存在着自身的优势，不过在计算优化问题时还存在着一些不足：

①编码形式种类繁多，编码形式不规范以及编码表示的不确定性；

②遗传算法在进行优化求解时，应用所选编码形式不能全方位地表示问题的约束条件，需要考虑的是对于所求问题的不可行解采用限制阈值的形式，导致算法在求解问题时所消耗时间过长；

③由于遗传算法在计算优化问题时计算量大，所以解决问题的效率没有别的优化算法高；

④遗传算法在求解问题时，对搜索空间进行全局搜索，但是受其他因素影响，极易导致过早收敛的状况；

⑤由于优化问题的可行解有可能不唯一，所以我们在应用遗传算法来求解优化问题近似解时，对于解的精度、可信度等因素，还没有统一的方法进行定量分析.

为了避免上述遗传算法在求解互补问题时的不足，本文将遗传算法和粒子群算法相结合，在搜索空间D上，有n个可行解X=(X1,X2,…,Xn)，对于第i个可行解有位置向量Xi=[xi1,xi2,…,xiD]T（每个位置都是问题的可行解），用Vi=[Vi1,Vi2,…,ViD]T表示个体的速度向量，通过计算所有位置的适应度值，选出个体最优值；同理，经过群体优化过程，比较所有个体最优值得出群体中最好的解作为群体极值；在速度更新、位置更新之后，进行选择、交叉、变异，将遗传算法同粒子群算法相结合，尽量避免遗传算法在求解互补问题时陷入局部寻优、过早收敛.

在进行优化搜索时，对个体的速度和位置进行更新迭代，公式如下.

3　实例分析

通过改进遗传算法，将遗传算法与粒子群算法相结合，提高算法的收敛速度和效率，选取经典互补问题的实例，应用Matlab软件运行改进的遗传算法计算互补问题，减少了求解互补问题对初始点选取和对梯度信息的依赖，大大提高求解互补问题近似解的效率.

应用改进遗传算法求解互补问题时，选取初始种群规模为100，进化次数选为100，个体的速度范围为[-1,1]，位置范围为[-5,5]，交叉概率Pc=0.6，变异概率Pm=0.2，容许误差e＜0.1.

例1求解线性互补问题F(x)=Mx+q.其中矩阵M和向量q由下式给出.

此线性互补问题的解为xT=()0.5,0,0.5,0,0.5，分别应用遗传算法和将遗传算法与粒子群算法相结合的方法计算例题，通过进行100次运算，运算结果如表1所示.

表1　验证结果分析

从表1可以看出，在标准遗传算法的基础上引入粒子群算法，将两种智能优化算法相结合，明显地提高了算法的准确率，并且可以看出由于遗传算法自身的缺陷，在求解互补问题时准确率不是很高，通过引入粒子群算法，可以避免遗传算法在求解问题时过早收敛和陷入局部寻优，同时，在应用改进遗传算法计算互补问题时不需要了解初始点和梯度的信息，大大缩减了求解互补问题的难度.

4　结论

本文借助极大熵函数法对互补问题进行光滑化，将互补问题转化为无约束的优化问题，并通过改进遗传算法，将遗传算法和粒子群算法相结合来求解互补问题.此方法不仅深化了遗传算法在互补问题方面的应用，同时也扩展了智能优化算法在互补问题方向的领域.实验结果表明，改进的遗传算法准确率高、解的稳定性好，是求解互补问题的一种有效算法.

参考文献：

［1］杨泰山，姜兴武，王秀玉.线性互补问题解的存在性［J］.吉林大学学报，2013，51（6）：1063-1067.

［2］匡芳君.群智能混合优化算法及其应用研究［D］.南京：南京理工大学，2014.

［3］孙菊贺，纪东辰，王琪.求解非线性互补问题的一类光滑牛顿算法［J］.沈阳航空航天大学学报，2016，33（5）：74-81.

［4］Huang Z H，Gu W Z.A Smoothing-Type Algorithm for Solving Linear Complementarity Problems with Strong Convergence Properties［J］.Applied Mathematics&Optimi⁃zation，2008，57（1）：17-29.