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

1、    求解不可微函数优化的一种混合遗传算法    摘  要  在浮点编码遗传算法中加入Powell方法，构成适于不可微函数全局优化的混合遗传算法。混合算法改善了遗传算法的局部搜索能力，显著提高了遗传算法求得全局解的概率。由于只利用函数值信息，混合算法是一种求解可微和不可微函数全局优化问题的通用方法。 关键词  全局最优；混合算法；遗传算法；Powell方法 1  引言 不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（

2、minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。 近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题1,2。为克服这一问题，早在1989年G

3、oldberg就提出混合方法的框架2，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。近来，文献3和4在分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。文献5采用牛顿莱佛森法和遗传算法进行杂交求解旅行商问题，文献6把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。 本文提出把Powell方法融入浮点编码遗传算法，把

4、Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗传算法，该方法可以较好解决遗传算法的早熟收敛问题。数值算例对混合方法的有效性进行了验证。 2  混合遗传算法     编码是遗传算法应用中的首要问题，与二进制编码比较，由于浮点编码遗传算法有精度高，便于大空间搜索的优点，浮点编码越来越受到重视7。考虑非线性不可微函数优化问题(1)，式中 为变量个数， 、 分别是第 个变量 的下界和上界。把Powell方法嵌入到浮点编码遗传算法中，得到求解问题(1)如下混合遗传算法：     

5、         min            (1)     step1 给遗传算法参数赋值。这些参数包括种群规模m，变量个数n，交叉概率pc、变异概率pm，进行Powell搜索的概率pPowell和遗传计算所允许的最大代数T。        Step2 随机产生初始群体，并计算其适应值。首先第i个个体适应值取为fi=fmax

6、 - fi，fi是第i个个体对应的目标函数值，fmax为当前种群成员的最大目标函数值，i=1,2,m。然后按Goldberg线性比例变换模型2 式(2)进行拉伸。 fi= a×fi+b （ fi  ³ 0 ）                     (2)     step3 执行比例选择算子进行选择操作。   

7、60; step4 按概率 执行算术交叉算子进行交叉操作。即对于选择的两个母体 和 ，算术交叉产生的两个子代为 和 ， 是0，1上的随机数，1 ,    。     step5 按照概率 执行非均匀变异算子8。若个体 的元素 被选择变异， ，则变异结果为 ，其中 ，                        

8、60;      (3)                                (4) 返回区间 , 里的一个值，使 靠近0的概率随代数 的增加而增加。这一性质使算子在初始阶段均匀地搜索空间，而在后面阶段非常局部化。 是 , 之间的

9、随机数， 为最大代数， 为决定非均匀度的系统参数。     step6 对每个个体按照概率pPowell进行Powell搜索。若个体 被选择进行Powell搜索操作，则以 作为初始点执行Powell方法得 ，若    则把所得计算结果 作为子代 ，否则，若    取 = ；若    取 = ，1    。     step7 计算个体适应值，并执行最优个体保存策略。  

10、;   step8 判断是否终止计算条件，不满足则转向step3，满足则输出计算结果。 作为求解无约束最优化问题的一种直接方法，Powell法的整个计算过程由若干轮迭代组成，在每一轮迭代中，先依次沿着已知的n个方向搜索，得一个最好点，然后沿本轮迭代的初始点与该最好点连线方向进行搜索，求得这一阶段的最好点。再用最后的搜索方向取代前n个方向之一，开始下一阶段的迭代。为了保持算法中n个搜索方向是线性无关的，保证算法的收敛性，对替换方向的规则进行改进，在混合法的计算步骤step6中采用文9中的改进Powell方法，其求解过程如下：     (1) 变量

11、赋初值 ，n个线性无关的n个方向 , , ，和允许误差>0，令k=1。     (2) 令 ，从 出发，依次沿方向 , , 作一维搜索，得到点 , , 求指标m，使得 - =max - ，令 。若 ，则Powell方法计算结束，否则，执行(3)。     (3) 求 使得 =min ，令 = = ，若 ，则Powell方法计算结束，得点 ；否则，执行(4)。     (4) 若 ，令 ，否则令 ( )，然后置 ，转(2)。 3  算例    

12、0;   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示。程序编制和运行采用Fortran Power Station 4.0，随机数由内部随机函数产生，在奔腾133微机上运行。 采用改进的Powell方法计算100次，初值在区间-500,500内随

13、机产生，只有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）搜索到全

14、局最优，平均计算时间为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，

15、但是搜索到全局最优的概率却远远高于标准遗传算法。 表1  pPowell取不同值时混合法的计算结果    4  结束语 针对不可微函数的全局优化问题，本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点，提高求得全局解的概率。计算结果表明混合法优于遗传算法和Powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。参考文献 1

16、60; 周明，孙树林遗传算法原理及应用M北京：国防出版社，1999 2  Goldberg D E. Genetic algorithms in search, optimization and machine learningM. Reading, Ma: Addison Wesley,1989 3  孟庆春，贾培发关于Genetic算法的研究及应用现状J清华大学出版社，1995，35(5)：4448 4  戴晓晖，李敏强，寇纪松遗传算法理论研究综述J控制与决策，2000，15(3)：263268 5  Lin W，Delgado-Frias J GH

17、ybrid Newton-Raphson genetic algorithm for traveling salesman problemJ. Cybernetics and systems, 1995，26(5)：387-412 6  赵明旺连续可微函数全局优化的混合遗传算法J 控制与决策，1997，12(5)：589592 7  Goldberg D EReal-Code Genetic Algorithm,Virtual Alphabets and BlockingJ. Complex Systems，1991，5：139-167 8  Michalewic

18、z ZA modified genetic algorithm for optimal control problemsJComputers math. Application，1992，23（12）：83-94 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