翻新时间：2013-12-18
求解不可微函数优化的一种混合遗传算法
摘 要 在浮点编码遗传算法中加入Powell方法，构成适于不可微函数全局优化的混合遗传算法。混合算法改善了遗传算法的局部搜索能力，显著提高了遗传算法求得全局解的概率。由于只利用函数值信息，混合算法是一种求解可微和不可微函数全局优化问题的通用方法。
关键词 全局最优；混合算法；遗传算法；Powell方法
1 引言
不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。
本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。
2 混合遗传算法
编码是遗传算法应用中的首要问题，与二进制编码比较，由于浮点编码遗传算法有精度高，便于大空间搜索的优点，浮点编码越来越受到重视[7]。考虑非线性不可微函数优化问题
(1)，式中
(1)如下混合遗传算法：
min
(1)
step1 给遗传算法参数赋值。这些参数包括种群规模m，变量个数n，交叉概率pc、变异概率pm，进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。
Step2 随机产生初始群体，并计算其适应值。首先第i个个体适应值取为fi’=fmax - fi，fi是第i个个体对应的目标函数值，fmax为当前种群成员的最大目标函数值，im。然后按Goldberg线性比例变换模型[2] 式
(2)进行拉伸。
fi’= a×fi’+b （ fi ³ 0 ）
(2)
step3 执行比例选择算子进行选择操作。
step4 按概率
step5 按照概率
(3)
(4)
step6 对每个个体按照概率pPowell进行Powell搜索。若个体
step7 计算个体适应值，并执行最优个体保存策略。
step8 判断是否终止计算条件，不满足则转向step3，满足则输出计算结果。
作为求解无约束最优化问题的一种直接方法，Powell法的整个计算过程由若干轮迭代组成，在每一轮迭代中，先依次沿着已知的n个方向搜索，得一个最好点，然后沿本轮迭代的初始点与该最好点连线方向进行搜索，求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一，开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的，保证算法的收敛性，对替换方向的规则进行改进，在混合法的计算步骤step6中采用文[9]中的改进Powell方法，其求解过程如下：
(1) 变量赋初值
(2) 令
(3)。
(3) 求
(4)。
(4) 若
(2)。
3 算例
图1 函数f(x)特性示意图
函数f(x)有相当多的极小点,全局极小点是
采用改进的Powell方法计算100次，初值在区间[-500,500]内随机产生，只有6次（即以概率0.06）搜索到全局最优，计算成功的概率极低。
Holland建立的标准（或简单）遗传算法，其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=30，交叉概率pc=0.
9
5、变异概率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.
8
5、pm=0.2，T=100，进行Powell搜索的概率pPowell取不同值，混合法运行100次，计算结果见如表1。对于这个具有多极值的算例，多次计算表明pPowell=0.3时，混合法能以完全概率搜索到全局最优的准确值，但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。对应的浮点编码遗传算法，取m=30，pc=0.
8
5、pm=0.2，TPPowell =0所示），计算时间约为标准遗传算法取T=500时计算时间的1/8，但是搜索到全局最优的概率却远远高于标准遗传算法。
表1 pPowell取不同值时混合法的计算结果
4 结束语
针对不可微函数的全局优化问题，本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点，提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。
参考文献
[1] 周明，孙树林．遗传算法原理及应用[M]．北京：国防出版社，1999．
[2] Goldberg D E. Genetic algorithms in search, optimization and machine learning[M]. Reading, Ma: Addison Wesley,1989．
[3] 孟庆春，贾培发．关于Genetic算法的研究及应用现状[J]．清华大学出版社，1995，35
(5)：44－48．
[4] 戴晓晖，李敏强，寇纪松．遗传算法理论研究综述[
[5] Lin W，Delgado-Frias J G．Hybrid Newton-Raphson genetic algorithm for traveling salesman problem[J].
[7] Goldberg D E．Real-Code Genetic Algorithm,Virtual Alphabets and Blocking[J]. Complex Systems，1991，5：139-167．
[8] Michalewicz Z．A modified genetic algorithm for optimal control problems[J]．
[9] 陈宝林．最优化理论与算法[M]．北京：清华大学出版社，1989．
[10] 俞红梅．全过程系统能量综合方法的研究[D]．大连理工大学博士学位论文，1998．
Hybrid approach for global optima of indifferentiable nonlinear function
Abstract A hybrid computational intellective algorithm for locating the global optima of indifferentiable nonlinear function was put forward by setting the Powell algorithm in real-code genetic algorithm. The hybrid approach improved the local searching ability of the genetic algorithm and promoted the probability for the global optima greatly. Because only the objective values are used, the hybrid approach is a generalized genetic algorithm for global optima of differentiable and indifferentiable nonlinear functions.
Key words global optima；hybrid approach；genetic algorithms；Powell algorithm
(9)
下载文档
网友最新关注
- 捉知了
- 我爱我家
- 我们班的女生
- 游常州恐龙园
- 观《闪闪的红星》有感
- 蚕
- 游寒山寺
- 我是“批萨小专家”
- 社区多变化
- 我爱秋雨
- 西瓜的自述
- 游动物园---熊
- 今非昔比——记社区变化
- 看降落伞比赛
- 我成为小学生啦
- 宽带接入合作协议书
- 有线电视节目播送系统合同
- 贴身顾问服务协议
- 互联网接入服务协议
- 北京市移动电话入网合同（适用于签约后付费项目）
- 工程咨询服务协议书
- 肿瘤治疗协议书
- ADSL宽带接入合同
- 融资与引进风险投资顾问协议
- 电视及声音广播服务批给合同
- 有线数字电视服务协议
- 员工福利保障保险顾问协议书
- 虚拟网用户宽带上网协议
- 包治协议
- 数据通信业务合作协议
- 自尊：心理健康的核心
- 电子商务网站的设计及其实现
- 城市出租车现状分析与远景预测
- 儿童心理理论研究对社会性发展的启示
- 购车问题的数学模型
- 科学发展观的形成与三个代表重要思想分析
- 公司外派人员安排最佳方案
- 按照三个代表的要求全面加强中心文化建设
- 深化“三个代表”重要思想树立新的执政理念
- 关于事件相关电位测谎的心理测量学要素分析
- 基于C的数据加密标准DES算法的实现
- 三个代表，各有心结
- 浅谈教师心理健康与学生健康教育
- “三个代表”重要思想与中共党史学
- 办公自动化系统
- 《我的伯父鲁迅先生》教学设计
- 《我的伯父鲁迅先生》教学设计
- 《我的伯父鲁迅先生》教学设计
- 《一面》教学设计
- 《我的伯父鲁迅先生》教学设计
- 《我的伯父鲁迅先生》第一课时教学设计
- 《一面》教学设计
- 《我的伯父鲁迅先生》教学设计
- 《我的伯父鲁迅先生》教学设计
- 《我的伯父鲁迅先生》教学设计
- 《我的伯父鲁迅先生》第一课时教学设计
- 《我的伯父鲁迅先生》教学设计
- 《我的伯父鲁迅先生》教学设计
- 《我的伯父鲁迅先生》第一课时教学设计
- 《一面》教学设计