非线性问题的求解及优化研究——基于遗传算法和混合遗传算法的分析

丁 李,崇金凤

(1.淮北职业技术学院 基础部, 安徽 淮北 235000;2.淮北师范大学 数学科学学院, 安徽 淮北 235000)

最优化就是在众多决策中挑选“最优”的,例如求最短路径、最少材料、最大利润和最少实验次数等。它在交通运输、大气海洋、城市规划、工程设计等方面有广泛的运用[1]。最优化数值问题是求解满足一些约束条件(例如等式约束条件、不等式约束条件,或仅带简单有界约束条件等)的函数的最小值或者最大值。判断一个点是否是最值点就要知道所有点的函数值,然而这样的点有无穷多个,所以要验证一个点的最优性是非常复杂的,进而需要近似算法,例如遗传算法[2]。遗传算法(GA)为优化规模庞大、变量多而复杂的非线性问题提供了一种解决方法,但是GA存在缺陷,例如收敛速度慢、局部寻优能力差、出现早熟现象和陷入局部最优情况等[3]。针对遗传算法的这些缺陷,将局部寻优能力强的传统算法与遗传算法结合,构造出混合遗传算法(HGA)[4-5],该算法在实际问题中有广泛的运用。文章将最速下降法变异算子和惩罚函数融入算法中构造了HGA,通过数值实验在有约束条件和无约束条件两类问题上验证了HGA的优越性。无约束优化问题以基于最速下降法的HGA和模拟退火遗传算法为例[6-7],约束优化问题以基于惩罚函数法的HGA[8]为例。采用测试函数,在Vs Studio 2010和Matlab中运行相关程序,对数值结果进行了分析,对比用本文算法的数值结果和文献中用GA工具箱的结果,验证了HGA具有更快的收敛速度和更好的最优解精度。

1 遗传算法和混合遗传算法的概述

1.1 遗传算法的描述

遗传算法(GA)来自计算机模拟生物系统的研究,模仿生物系统中染色体交叉及变异过程,利用多种不同编码方式来表示出问题的可行解。GA算法如下:1)编码:设定解数据是GA的表现形式,将表现型映射为基因型的过程称作编码,编码过程中产生基因串结构数据,结构串的随机组合可以构成不同点;2)生成初始种群:GA以N个初始点进行迭代,设定进化代数t=0,最大迭代次数为Maxgen,生成具有M个个体的初始种群;3)评估P(t)适应度值:评估各个个体的适应度值;4)选择:按照轮盘赌选择方式选择子代;5)交叉:将交叉算子Pc运用至群体中;6)变异:将变异算子Pm运用至群体中,得到下一代种群P(t+1);7)判断终止条件:当t≤Maxgen时,t++,转至3)步骤,否则,最大适应度值的个体作为输出的最优解并终止运算。

1.2 SHGA求解非线性无约束优化问题

规定无约束优化问题(会带有简单约束条件)的数学模型:

minf(X)

(1)

式中X=(x1,…,xn)T,X1

最速下降法变异算子与GA算子结合的HGA(SHGA),一方面加快算法的收敛速度,防止陷入局部最优;另一方面提高最优解的精度,产生精度较高的平均适应值和最佳个体。初始化后随机地生成初始种群,且初始种群含有M个个体,运用轮盘赌选择原则生成含有N个个体的中间种群(满足N>2M),依据w划分中间种群为子带种群I和子代种群II,对子代种群I和子代种群II分别运用随机点变异法和最速下降法变异,对两个种群个体适应度值排序,前M个个体完全复制到子代中,形成新种群。不断重复上述过程,一旦满足终止条件就停止。算法描述如下:1)初始化各个参数,令Gen=0;2)生成初始种群,初始种群中含有M个个体;3)当Gen>Maxgen迭代终止,同时输出结果,要不然就转入下一步;4)按照轮盘赌原则生成N个个体的中间种群;5)将中间种群划分为子代种群I和子代种群II,再用随机点变异法和最速下降法分别对子代种群I和子代种群II进行变异;6)对种群个体按照适应度值由高到低排序;7)前M个个体完全复制到子代中,形成新的子代种群,且令Gen++,转至步骤3)。

1.3 PHGA处理非线性约束问题

规定非线性约束的数学模型:

(2)

式中X=(x1,…,xn),X∈Rn。其中约束条件分别对应着不等式约束、等式约束、约束域,目标函数和约束条件中至少有一个是非线性的。将式(2)的数学模型简化为一般非线性约束模型:

(3)

取适应值函数为:

eval(X)=f(X)+pentlyf(X)

(4)

式中pentlyf(X)表示惩罚项函数。对(4)中的惩罚项pentlyf(X)采用形式(5):

(5)

式中ri表示约束gi(X)的惩罚系数,则构造出目标函数:

(6)

引入惩罚函数能够适当地增加非可行解进行下一次迭代,同时,减少了严重违反约束条件的不可行解,搜索过程在不可行解区域内展开。本文用的是外点惩罚函数的思想,即从不可行解区域逐渐逼近到可行解的最优解,而内点惩罚函数法要求起始点在可行域内,所以外点惩罚函数法的要求更宽松。在GA运行的过程中融入惩罚函数,可以提高解的精度,便于搜索到全局最优值。基于惩罚函数法的HGA步骤如下:1)初始化各个参数,生成初始种群;2)令迭代数Gen=0,计算目标函数值F(X);3)分配适应度值,对当前种群p(t)进行选择、交叉、变异遗传操作;4)计算子代目标函数值,将子代重插入,Gen++;5)判断Gen

2 数值实验结果分析

2.1 SHGA的数值实验结果

选取测试函数camel和shubert,利用GA工具箱和Visual Studio 2010软件运行SHGA算法进行数值实验,理论测试结果如表1所示。

表1 测试函数和理论结果

其中,数值实验中种群规模数为40,poposize选为20,woposize选为50,flip选为0.4,w选为5,计算结果如表2所示。

表2 SHGA求解结果

首先对比SHGA求解结果和理论最优值、最优点,可以发现SHGA算法在精度上十分逼近甚至达到最优值、最优点,可见SHGA在精准性上展示了较好的性能。对比SHGA结果和GA工具箱所求的结果,在最大迭代数同为180的情况下,camel函数和shubert函数的SHGA最优值、最优点结果精度明显比GA工具箱求解结果优越。

2.2 PHGA的数值实验结果

为了测试算法在非线性约束问题模型的效果,通过非线性约束算例进行实验,其中算例如表3所示。在Matlab中,分别运行PHGA算法和GA工具箱,设定最大迭代数为50,选择父辈中90%的个体进入子代,交叉算子Pc为0.7,用排序法挑选适应度值高的子代个体进行数值实验,结果如表4所示。在收敛代数为20时,PHGA最优值、最优点结果精度明显比GA工具箱求解结果优越,且耗时更短。

表3 算例与约束条件

表4 基于惩罚函数法的求解结果

从PHGA的解和理论最优解比较(见表4),可以看出这种混合算法的最优值十分逼近理论最优值,展现了比较好的最优值精度。

在惩罚因子为50,将对应的适应度曲线展示出来,曲线如图1所示。

图1 适应度曲线

从图1可知大约在第8代左右,该算法收敛到全局最小值点,随后曲线逐渐平稳;再观察图中种群个体均值的变化曲线,在第15代以前,种群均值下降得很快且变化较大,第15代以后,种群均值趋于平稳,展现了比较好的收敛性和稳定性。

3 结论

针对传统遗传算法收敛速度慢、精度低和容易陷入局部最优的缺陷,结合了传统算法(最速下降法和惩罚函数法)的优点,将两类算法结合构造了新的混合算法,新的混合算法能加快收敛速度、提高最优解精度。为验证混合遗传算法的优点,比较两种方法的实验结果。在Visual Studio 2010中采用基于最速下降法的混合遗传算法运行了C语言程序;在Matlab 2014中采用模拟退火遗传算法和基于惩罚函数法的HGA运行了Matlab程序。实验结果验证了混合遗传算法具有很好的收敛性能和最优解精度,在很大程度上提高了计算效率。