当前位置: 论文资料 >> 理学论文 >> 数学 >> 求解不可微函数优化的一种混合遗传算法
求解不可微函数优化的一种混合遗传算法

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

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

fi= a×fi+bfi  ³ 0 )                     (2)

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

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

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

                              (3)

                               (4)

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

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

[1] [2] [3] 下一页  


相关文章列表:
  • 基于遗传算法的OD分布