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

摘  要  在浮点编码遗传算法中加入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，交叉概率p_c、变异概率p_m，进行Powell搜索的概率p_Powell和遗传计算所允许的最大代数T。

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

f_i^’= a×f_i^’+b （ f_i  ³ 0 ）                     (2)

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

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

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

                              (3)

                               (4)

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

    step6 对每个个体按照概率p_Powell进行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)。

（科教范文网http://fw.NSEAC.com编辑发布）

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示。程序编制和运行采用Fortran Power Station 4.0，随机数由内部随机函数产生，在奔腾133微机上运行。

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

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

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

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

4  结束语

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

（科教范文网http://fw.nseac.com）

参考文献

[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]  戴晓晖，李敏强，寇纪松．遗传算法理论研究综述[J]．控制与决策，2000，15(3)：263－268．

[5]  Lin W，Delgado-Frias J G．Hybrid Newton-Raphson genetic algorithm for traveling salesman problem[J]. Cybernetics and systems, 1995，26(5)：387-412．

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

[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]．Computers 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 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

       ^T   -500:2:500       (9)