注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

lican8341的博客

霜剑如梦倚残翼,泊影难觅几何时!

 
 
 

日志

 
 

求解不可微函数优化的一种混合遗传算法  

2015-08-19 22:17:10|  分类: 嫦娥飞天——中华 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

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

1  引言

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

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

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

2  混合遗传算法

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

             min 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客     求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客        (1)

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

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

fi= a×fi+b ( f ? 0                      (2)

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

    step4 按概率 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 执行算术交叉算子进行交叉操作。即对于选择的两个母体 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客,算术交叉产生的两个子代为 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客[01]上的随机数,求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 , 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 

    step5 按照概率 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 执行非均匀变异算子[8]。若个体 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 的元素 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 被选择变异, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,则变异结果为 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,其中 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 

        求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客    求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客                    (3)

求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客                                (4)

求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 返回区间求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 , 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ]里的一个值,使 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 靠近0的概率随代数 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 的增加而增加。这一性质使算子在初始阶段均匀地搜索空间,而在后面阶段非常局部化。 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 , 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客]之间的随机数, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 为最大代数, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 为决定非均匀度的系统参数。

    step6 对每个个体按照概率pPowell进行Powell搜索。若个体 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 被选择进行Powell搜索操作,则以 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 作为初始点执行Powell方法得 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,若 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 则把所得计算结果 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 作为子代 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,否则,若 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 = 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ;若 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 = 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 

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

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

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

    (1) 变量赋初值 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 n个线性无关的n个方向 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 , 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,…, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,和允许误差ε>0,令k=1。

    (2)  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,从 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 出发,依次沿方向 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 , 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,…, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 作一维搜索,得到点 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 , 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,…, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求指标m,使得 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 - 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 =max { 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 - 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 },令 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 。若 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ε,则Powell方法计算结束,否则,执行(3)

    (3)  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 使得 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 =min 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,令 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 = 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 = 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,若 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,则Powell方法计算结束,得点 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ;否则,执行(4)

    (4)  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,令 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,否则令 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ( 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ),然后置 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,转(2)。

3  算例

求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客     求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 T  求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 [-500,500] 

 

求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客
函数f(x)特性示意图

函数f(x)有相当多的极小点,全局极小点是 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 =-420.97 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 =1,2,…, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,最优值为-837.97;次最优点为 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ={( 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 , 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,…, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ) 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 =-420.97, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 , 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客=302.52} 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 =1,2,…, 求解不可微函数优化的一种混合遗传算法 - 主席 - lican8341的博客 ,次优值-719.53。变量个数n=2时函数f(x) 特性如图1示。程序编制和运行环境采用Fortran Power Station 4.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.85pm=0.2T=100,进行Powell搜索的概率pPowell取不同值,混合法运行100次,计算结果见如表1。对于这个具有多极值的算例,多次计算表明pPowell=0.3时,混合法能以完全概率搜索到全局最优的准确值,但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法,取m=30pc=0.85pm=0.2T=100,运行100次,82次(以概率0.82)搜索到全局最优(如表1PPowell =0所示),计算时间约为标准遗传算法取T=500时计算时间的1/8,但是搜索到全局最优的概率却远远高于标准遗传算法。

 

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

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法,可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息,本文混合法不仅适用于不可微函数优化问题,也适合可微函数全局优化问题。


  评论这张
 
阅读(95)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017