求解不可微函数算法分析论文

时间:2022-07-14 10:58:00

求解不可微函数算法分析论文

摘要在浮点编码遗传算法中加入Powell方法,构成适于不可微函数全局优化的混合遗传算法。混合算法改善了遗传算法的局部搜索能力,显著提高了遗传算法求得全局解的概率。由于只利用函数值信息,混合算法是一种求解可微和不可微函数全局优化问题的通用方法。

关键词全局最优;混合算法;遗传算法;Powell方法

1引言

不可微非线性函数优化问题具有广泛的工程和应用背景,如结构设计中使得结构内最大应力最小而归结为极大极小优化(minmax)问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视,常用的算法有模式搜索法、单纯形法、Powell方法等,但是这些方法都是局部优化方法,优化结果与初值有关。

近年来,由Holland研究自然现象与人工系统的自适应行为时,借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法,是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快,在各种问题的求解与应用中展现了其特点和魅力,但是其理论基础还不完善,在理论和应用上暴露出诸多不足和缺陷,如存在收敛速度慢且存在早熟收敛问题[1,2]。为克服这一问题,早在1989年Goldberg就提出混合方法的框架[2],把GA与传统的、基于知识的启发式搜索技术相结合,来改善基本遗传算法的局部搜索能力,使遗传算法离开早熟收敛状态而继续接近全局最优解。近来,文献[3]和[4]在总结分析已有发展成果的基础上,均指出充分利用遗传算法的大范围搜索性能,与快速收敛的局部优化方法结合构成新的全局优化方法,是目前有待集中研究的问题之一,这种混合策略可以从根本上提高遗传算法计算性能。文献[5]采用牛顿-莱佛森法和遗传算法进行杂交求解旅行商问题,文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题,均取得良好的计算效果,但是不适于不可微函数优化问题。

本文提出把Powell方法融入浮点编码遗传算法,把Powell方法作为与选择、交叉、变异平行的一个算子,构成适于求解不可微函数优化问题的混合遗传算法,该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。

2混合遗传算法

编码是遗传算法应用中的首要问题,与二进制编码比较,由于浮点编码遗传算法有精度高,便于大空间搜索的优点,浮点编码越来越受到重视[7]。考虑非线性不可微函数优化问题(1),式中为变量个数,、分别是第个变量的下界和上界。把Powell方法嵌入到浮点编码遗传算法中,得到求解问题(1)如下混合遗传算法:

min(1)

step1给遗传算法参数赋值。这些参数包括种群规模m,变量个数n,交叉概率pc、变异概率pm,进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。

Step2随机产生初始群体,并计算其适应值。首先第i个个体适应值取为fi’=fmax-fi,fi是第i个个体对应的目标函数值,fmax为当前种群成员的最大目标函数值,i=1,2,…,m。然后按Goldberg线性比例变换模型[2]式(2)进行拉伸。

fi’=a×fi’+b(fi³0)(2)

step3执行比例选择算子进行选择操作。

step4按概率执行算术交叉算子进行交叉操作。即对于选择的两个母体和,算术交叉产生的两个子代为和,是[0,1]上的随机数,1,。

step5按照概率执行非均匀变异算子[8]。若个体的元素被选择变异,,则变异结果为,其中,

(3)

(4)

返回区间[,]里的一个值,使靠近0的概率随代数的增加而增加。这一性质使算子在初始阶段均匀地搜索空间,而在后面阶段非常局部化。是[,]之间的随机数,为最大代数,为决定非均匀度的系统参数。

step6对每个个体按照概率pPowell进行Powell搜索。若个体被选择进行Powell搜索操作,则以作为初始点执行Powell方法得,若则把所得计算结果作为子代,否则,若取=;若取=,1。

step7计算个体适应值,并执行最优个体保存策略。

step8判断是否终止计算条件,不满足则转向step3,满足则输出计算结果。

作为求解无约束最优化问题的一种直接方法,Powell法的整个计算过程由若干轮迭代组成,在每一轮迭代中,先依次沿着已知的n个方向搜索,得一个最好点,然后沿本轮迭代的初始点与该最好点连线方向进行搜索,求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一,开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的,保证算法的收敛性,对替换方向的规则进行改进,在混合法的计算步骤step6中采用文[9]中的改进Powell方法,其求解过程如下:

(1)变量赋初值,n个线性无关的n个方向,,…,,和允许误差ε>0,令k=1。

(2)令,从出发,依次沿方向,,…,作一维搜索,得到点,,…,求指标m,使得-=max{-},令。若ε,则Powell方法计算结束,否则,执行(3)。

(3)求使得=min,令==,若,则Powell方法计算结束,得点;否则,执行(4)。

(4)若,令,否则令(),然后置,转(2)。

3算例

T[-500,500]

图1函数f(x)特性示意图

函数f(x)有相当多的极小点,全局极小点是=-420.97,=1,2,…,,最优值为-837.97;次最优点为={(,,…,):=-420.97,,=302.52},=1,2,…,,次优值-719.53。变量个数n=2时函数f(x)特性如图1示。程序编制和运行环境采用FortranPowerStation4.0,随机数由内部随机函数产生,在奔腾133微机上运行。

采用改进的Powell方法计算100次,初值在区间[-500,500]内随机产生,只有6次(即以概率0.06)搜索到全局最优,计算成功的概率极低。

Holland建立的标准(或简单)遗传算法,其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30,交叉概率pc=0.95、变异概率pm=0.05,最大进化代数T=1000,每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低,对于标准遗传算法以目标函数小于-800为搜索成功,标准遗传算法运行100次。当取最大进化代数为T=200时,40次(以概率0.40)搜索到全局最优,平均计算时间为0.51秒;当取T=500时,51次(以概率0.51)搜索到全局最优,平均计算时间为1.13秒。

采用本文混合法计算,取m=30,pc=0.85、pm=0.2,T=100,进行Powell搜索的概率pPowell取不同值,混合法运行100次,计算结果见如表1。对于这个具有多极值的算例,多次计算表明pPowell=0.3时,混合法能以完全概率搜索到全局最优的准确值,但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法,取m=30,pc=0.85、pm=0.2,T=100,运行100次,82次(以概率0.82)搜索到全局最优(如表1中PPowell=0所示),计算时间约为标准遗传算法取T=500时计算时间的1/8,但是搜索到全局最优的概率却远远高于标准遗传算法。

表1pPowell取不同值时混合法的计算结果

PPowell

0.0

0.02

0.05

0.1

0.2

0.3

求得最优解的次数

82

85

89

94

98

100

求得最优解的概率

0.82

0.85

0.89

0.94

0.98

1.00

平均计算时间/秒

0.14

0.20

0.31

0.47

0.68

0.87

4结束语

针对不可微函数的全局优化问题,本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法,该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点,提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法,可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息,本文混合法不仅适用于不可微函数优化问题,也适合可微函数全局优化问题。

参考文献

[1]周明,孙树林.遗传算法原理及应用[M].北京:国防工业出版社,1999.

[2]GoldbergDE.Geneticalgorithmsinsearch,optimizationandmachinelearning[M].Reading,Ma:AddisonWesley,1989.

[3]孟庆春,贾培发.关于Genetic算法的研究及应用现状[J].清华大学出版社,1995,35(5):44-48.

[4]戴晓晖,李敏强,寇纪松.遗传算法理论研究综述[J].控制与决策,2000,15(3):263-268.

[5]LinW,Delgado-FriasJG.HybridNewton-Raphsongeneticalgorithmfortravelingsalesmanproblem[J].Cyberneticsandsystems,1995,26(5):387-412.

[6]赵明旺.连续可微函数全局优化的混合遗传算法[J].控制与决策,1997,12(5):589-592.

[7]GoldbergDE.Real-CodeGeneticAlgorithm,VirtualAlphabetsandBlocking[J].ComplexSystems,1991,5:139-167.

[8]MichalewiczZ.Amodifiedgeneticalgorithmforoptimalcontrolproblems[J].Computersmath.Application,1992,23(12):83-94.

[9]陈宝林.最优化理论与算法[M].北京:清华大学出版社,1989.

[10]俞红梅.全过程系统能量综合方法的研究[D].大连理工大学博士学位论文,1998.

Hybridapproachforglobaloptimaofindifferentiablenonlinearfunction

AbstractAhybridcomputationalintellectivealgorithmforlocatingtheglobaloptimaofindifferentiablenonlinearfunctionwasputforwardbysettingthePowellalgorithminreal-codegeneticalgorithm.Thehybridapproachimprovedthelocalsearchingabilityofthegeneticalgorithmandpromotedtheprobabilityfortheglobaloptimagreatly.Becauseonlytheobjectivevaluesareused,thehybridapproachisageneralizedgeneticalgorithmforglobaloptimaofdifferentiableandindifferentiablenonlinearfunctions.

Keywordsglobaloptima;hybridapproach;geneticalgorithms;Powellalgorithm