基于遗传算法和模式搜索的混合优化方法

基于遗传算法和模式搜索的混合优化方法

钟 静 赖于树 吴鸿娟

（1.重庆三峡学院计算机科学与工程学院，重庆万州 404100） （2.重庆三峡学院电子与信息工程学院，重庆万州 404100）

摘 要：遗传算法具有快速随机的全局搜索能力，但当求解到一定范围时往往做大量无为的冗余迭代，求精确解效率低．模式搜索具有很强的细搜索能力，但是其搜索结果的好坏在很大程度上依赖于初始点的选择．本文提出了一种混合遗传-模式搜索算法，该方法是将种群分成两个子群，分别进行遗传算法与模式搜索算法，在每一步中两个子群的最佳结果收集起来，用于更新相互的最优个体．仿真结果表明遗传算法与模式搜索的混合优化方法取得了较好的效果．

关键词：优化；遗传算法；模式搜索法

中图分类号：TP301.6 文献标识码:A 文章编号：1009-8135（2011）03-0070-04

遗传算法(genetic algorithm，GA)是在模拟生物进化过程中优胜劣汰规则下，进行的随机搜索，处理复杂优化问题的方法．它能搜索解空间中的大量区域、复杂区域，为优化问题的目标函数或适应度函数提供近最优解．然而遗传算法局部寻优精度较差，使用单一的遗传算法并不能得到最优的路径．

模式搜索法[1] (Pattern Search Method，PS)是一种求解复杂非线性问题的常规优化算法，无需求导，具有较强的局部搜索能力．然而应用该方法需给定初值，如果初值选得好，则是一个简单、有效的方法．这就要求计算者具有丰富的经验才能得到“最优解”，通常只能得到局部极值解而非全局解．

为了克服遗传算法与模式搜索算法各自的缺点，本文将基于遗传算法和模式搜索算法结合起来,提出一种混合遗传-模式搜索方法（Hybrid Genetic Pattern Search Method, HGPSA）．

1

2

1

1 遗传算法

遗传算法模拟基因重组与进化的自然过程，把待解决问题的参数编码，形成个体（染色体），许多个体构成种群．初始时，随机建立一个种群，代表了在搜索空间中的不同点．与每一个个体相关联的目标函数与适应度函数表示了个体优秀的程度．基于适者生存的现象，只有少数的个体被选择，即在种群中选择生命力强即适应度值大的个体产生新种群．生物学中的交叉与变异也应用于这些个体．交叉又称重组，是按较大的概率从种群中选择两个个体，交换两个个体的某些基因产生新个体过程．产生的子代继承了父代的基本特征．变异是以较小的概率改变个体上的某些基因值，产生新个体的过程．选择、交叉和变异的运算，经过多次重复迭代直至得到最后的优化结果．它的本质是一种并行的全局优化算法．遗传算法的应用领域很广泛，如图像处理、神经网络、机器学习、作业调度等等．

收稿日期：2011-03-01

作者简介：钟 静（1976-），女，重庆市潼南县人，副教授，硕士，主要研究神经网络，优化算法.

赖于树（1976-），男，重庆万州人，副教授，博士，主要研究算法优化.

基金项目：本文系重庆市自然科学基金(2010BB7316)、重庆三峡学院青年项目(10QN-24)阶段性成果 -70-

重庆三峡学院学报 ２ 模式搜索

传统非线性优化分析，通常依赖于对n维空间

目标函数f的Taylor展式逼近．如拟牛顿法，假设一阶和二阶导存在，用二阶Taylor展式对f局部二次逼近；最速下降法，假设一阶导存在，用一阶Taylor展式对f线性逼近．0阶方法如直接搜索法，则不需要导数计算和对目标函数f的逼近．直接搜索算法是一种无需目标函数的梯度信息仍可以解决优化问题的方法．直接搜索算法在已知点（参考点）附近，搜索一系列的点，目的是获得一个更小值的点．

直接搜索法包含两种算法：一般的模式搜索法[2]

和网格自适应搜索[3]（Mesh Adaptive Search，MADS）．两种算法都叫模式搜索，都需要朝着最优点的方向计算一序列的点．不同之处在于构成网格的这些点是如何计算出来的．在PS算法中使用的是固定的方向向量，而在MADS中，是用随机选择的一组向量来定义网格．因为PS更稳定，本文使用的是PS算法．

2.1 模式

在模式搜索算法中，使用一组向量{Vi},即模式，以确定在每一次迭代中使用哪些点进行搜索．向量{Vi}是根据目标函数中的变量、N以及正基集定义的．在模式搜索算法中通常使用的两个正基集分别是具有2N个向量的最大基和具有N+1个向量的最小基．

例如：如果在优化问题上有3个变量,2N个基包含有以下的模式向量：

V1=[1 0 0] V2=[0 1 0] V3=[0 0 1] V4=[-1 0 0] V5=[0 -1 0] V6=[0 0 -1]

对于N+1个基，则有如下的模式向量： V1=[1 0 0] V2=[0 1 0] V3=[0 0 1] V4=[-1 -1 -1] 根据筛选方法的选择，可选择的向量数将是2N或N+1．

2.2 网格

在每一步搜索过程中，模式搜索算法搜索的点的集合称为网格，其目的是为了找到一个点，用以改善目标函数．可用来在迭代过程中控制模式如何变化．网格的形成有如下两个步骤：

（1）用一个标量Δm去乘以每一个模式向量Vi得到一组向量{di}．Δm称为网格大小．

（2）将{di}与当前点相加．当前点即是在上一步搜索过程中找到的具有最佳目标函数值的点．

2.3 筛选 在每一步搜索过程中，模式搜索算法通过计算目标函数的值来筛选当前网格中的点．筛选有两种方法．

全筛选：模式搜索算法用网格中的所有点来计算目标函数．

不完全筛选：当算法使用网格中的点计算目标函数时，一旦找到一个点，使目标函数值比当前点的小，就停止筛选．

如果筛选时找到了一个点，使得目标函数值比当前点的值小，筛选就是成功的．该点将作为下一次迭代时的当前点．全筛选方法效果更好，但是需要耗费更多的时间．而不完全筛选方法易找到局部最优解．

2.4 扩展和收缩

筛选完成以后，模式搜索算法将改变网格大小Δm的值．默认的方法是，在一次成功筛选后，将Δm乘以2，筛选失败则将Δm乘以0.5．

3 混合遗传和模式搜索算法

遗传算法具有全局搜索能力，并能跳出局部最优，但是收敛速度太慢．模式搜索算法适于局部搜索，但是对初始值的选择很敏感，易陷入局部最优．本文将具有强大全局搜索能力的遗传算法与具有细搜索能力的模式搜索算法相结合提出了新算法：混合遗传-模式搜索算法HGPSA．其思想是首先将种群分成两个子群，一个子群使用遗传算法，另一个子群使用模式搜索算法．每一步计算后，将两个子群最好的结果收集起来，用以更新各自的优胜个体．算法流程图如下所示：

图1中，PE，PC和PM分别表示优胜概率、交叉概率和变异概率．优胜个体是指在种群中最好的个体，通常直接遗传给下一代以保证遗传算法能收敛到全局最优．在HGPSA算法中，将由遗传算法计算得到的最优子代与模式搜索算法计算得到的临时点进行比较，选择最好的个体以更新优胜子代和临时点．

-71-

钟 静 赖于树 吴鸿娟：基于遗传算法和模式搜索的混合优化方法 种群 旧种群 旧点 执行GA算法 执行PS算法 PM PC PE 临时点 临时 种群 选择最优点 更新GA算法中的参数PE和PS算法中的临时点 新种群 新点 图1 HGPSA算法的结构图 测试函数

函数公式

4 仿真实验 4.1 实验 为了验证HGPSA算法的有效性，选择了三个典型的测试函数Rosenbrock，Powell，Schaffer[4,5]，进行仿真测试，如表1所示．这些函数常被用于优化方法的测试．通过试错（trial-and-error）的学习方法来设置遗传算法和模式搜索的相关参数．参数设置为：遗传算法的种群规模为20，优良的子辈个数为2，交叉概率为0.8，变异因子为0.2．模式搜索法的种群规模为2N，初始网格大小为1.0，扩展因子为2.0，收缩因子为0.5，迭代终止条件见表2．HGPSA算法的参数是结合遗传算法和模式搜索算法的参数来设置的． 表1 测试函数 初始点

最佳点

Powell minF=(x1+10x2)2+5(x3-x4)2+(x2-x3)4+10(x1-x4)4 [-5 -5 -1 -1] F(0,0,0,0)=0 Rosenbrock minF=100(x12- x2)2+(1- x1)2 [3 3] F(1,1)=0 Schaffer minF={[sin(x12+ x22)1/2]2-0.5}/[1+0.001(x12+ x22)]2 [1 1] F(0,0)= -1

表2 迭代终止条件

最大数

最大适应度评价

变量界限

适应度界限

停止迭代

网格精度

2000

2×104 10-6 10-6 50 10-6

4.2 实验结果

在实验中，每一种算法都运行了10次．分别计算出成功率、平均消耗时间、适应度评估数和平

均迭代次数，其结果如表3所示．

表3 三种测试函数的结果比较

函数

成功率（100%）

GA PS HGPSA

平均消耗时间（/s） GA PS HGPSA

2.20101.62110.0973

1220

适应度评估数 GA PS HGPSA

14543

13655

11061040

迭代次数 GA PS HGPSA 63 2002 2003

2002 2003

Powell 0 0 70 0.1024 2.2329

Rosenbrock

10 0 40 0.0965 1.73017527 5780 55.3

Schaffer 80 0 80 0.0 0.0425161 410 52 45 .6

表3给出三种测试函数分别在遗传算法、模式

搜索算法和HGPSA算法下的相关结果．从实验成功率来看，遗传算法在Powell，Rosenbrock 这两个测试函数中都末能收敛，并出现中停现象．而模式

-72-

搜索算法在三个测试函数中均末能收敛．综合比较，本文提出的HGPSA算法与遗传算法和模式搜索算法比较，能迅速收敛，且平均成功率要高的多．实验表明该算法是有效的．

重庆三峡学院学报 [5]Abdel-Rahman Hedar. Test Functions for 5 结 论 本文提出的混合遗传模式搜索算法结合了全

局优化方法和局部优化方法的优点，在每一步迭代过程中，通过将遗传算法与模式搜索算法的最好结果相结合的方法来更新优胜个体，提高了算法的成功率，并减少了陷入局部最优的可能，是一种有效的优化算法．但该算法收敛速度较慢，后期的工作中将努力提高HGPSA算法的收敛速度．

参考文献：

[1]薛毅.最优化原理与方法[M].北京：北京工业大学出版，2001．

[2]Leiws R M，Torczon v，Trosset M W．Direct search methods: then and now [J].Journal of Computational and Applied Mathematics，2000，124(12)：191-207．

[3]Audet C，Dennis J E．Mesh adaptive direct search algorithms for constrained optimization [J]. SIAM Journal on Optimization，2006，17(2)：188-217．

[4]杨春，倪勤.变步长非单调模式搜索法[J].高等学校计算数学学报，2005，27(2)：160-168．

Unconstrained Global Optimization [EB/OL].http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO_files/Page3.htm．

[6]黄天云.约束优化模式搜索法研究进展[J].计算机学报，2008，Vol.31 No7：1200-1215．

[7]Park C H，Lee I W, Han W S, etc．Improved genetic

algorithm

for

multidisciplinary

optimization of composite laminates [J].Computers & Structures， 2008，Vol.86：14-1903．

[8]Bogani C，Gasparo M G， Papini A． Generalizes Pattern Search methods for a class of nonsmooth optimization problems with structure [J].Journal of Computational and Applied Mathematics．2009，Vol.229：283-293．

[9]Kolda T G，Lewis R M,，Torczon V． Optimization by direct search: New perspectives on some classical and modern methods [J].SIAM Review，2003，45(3)：385-482．

（责任编辑：郑宗荣）

A Hybrid Optimization Method Based on Genetic Algorithm and Pattern Search

ZHONG Jing1 LAI Yu-shu2 WU Hong-juan1

(1. College of Computer Science and Engineering, Chongqing Three Gorges University, Wanzhou 404100，China) (2. College of Electronic and Information Engineering, Chongqing Three Gorges University, Wanzhou 404100, China)

Abstract: Genetic algorithm has a global quick and stochastic ability of searching．But it has to do a large redundancy repetition when solving problems to a certain extent, so the precision efficiency is reduced．Pattern search method has excellent local search ability；however its search result mostly depends on the initial point．A novel algorithm-hybrid genetic pattern search algorithm (HGPSA) is proposed where the population is divided into to two sub-populations. One performs the genetic algorithm and the other the pattern search. The best results of the two sub-populations at each step are collected to update the elite individual of each other. The simulation results show that very nice effects are obtained．

Keywords: optimization；genetic algorithm；pattern search algorithm

-73-