改进遗传算法与粒子群优化算法及其对比分析

2002 年

南京师范大学学报 (工程技术版)

J OU RNAL O F NANJ IN G NORMAL U N IV ERSI T Y( EN GIN EER IN G AND T ECHNOL O GY)

Vol . 2 No . 2

2002

改进遗传算法与粒子群

优化算法及其对比分析

Ξ

任斌 ,丰镇平

( 西安交通大学叶轮机械研究所 ,710049 ,西安)

[ 摘要 ] 　进化算法作为一类新的优化搜索方法 ,广泛应用于各种优化问题. 现对简单遗传算法进行了改进 ,采用实值编码 , 并与模拟退火算法及基于适值排序和随机选择的方法相结合 ,形成了改进遗传算法. 同时还介绍了一种新的进化算法 —粒 子群优化算法. 将这两种优化算法应用于函数优化 ,并对优化结果进行了对比分析. 比较结果表明 ,改进遗传算法和粒子群 优化算法都可以在函数优化方面表现出较好的健壮性 ,但在找寻最优解的效率上 ,粒子群优化算法较好.

[ 关键词 ] 　函数优化 ,改进遗传算法 ,粒子群优化算法

[ 中图分类号 ] O224 ; 　[ 文献标识码 ]A ; 　[ 文章编号 ] 1672 - 1292 (2002) 02 -  0014 - 07

0 　引言

自然界经过数万年的演化 ,存在的方式 、规律都是最优的. 所以 ,人们总是在找寻自然界的优化规 律 ,发展形成所谓的进化算法 ,并应用到各类优化问题 ,如本文介绍的遗传算法以及近年兴起的粒子群 优化算法就是借鉴自然界优化规律而产生的进化算法.

遗传算法 ( Genetic Algo rit hm ,简称 GA) 是 20 世纪 70 年代由美国密歇根大学 J . H. Holland 教授提

出的[ 1 ]  ,它是一类基于自然选择和遗传学原理的有效寻优方法 ,目前在很多方面都有成功应用[ 1～4 ] . 粒 子群优化算法最初由 J im  Kennedy 于 1995 年提出并成功地用于连续非线性函数的优化[ 5 ]  ,它是对鸟群

觅食过程中的迁徙和聚集的模拟 ,也可以说是对社会心理学的一种模拟. 粒子群优化算法对优化问题求 解来说 ,最大特点就是收敛速度较快.

工程优化应用的大多数问题 ,都需要先对其进行数学建模 ,即向数学问题转化 ,然后对函数进行优 化. 工程优化所建立的数学函数 ,往往是带有多种约束条件的复杂函数 ,而且大都是既不连续 、也不可微

的隐函数. 对于这些复杂函数来说 ,用常规的数学方法很难或根本无法处理. 本文所涉及的这两种进化 算法都能处理这类复杂函数的优化问题 ,但由于算法的原理不同 ,在优化过程中所表现出来的特性和优

点也会不同. 为了了解两种算法的基本特点 ,本文在对简单遗传算法改进的基础上 ,通过一个较为典型

的数学问题的优化 ,对这两种进化算法的性态进行了对比分析 ,以此来检验它们在工程优化中的有效 性.

1 　简单遗传算法及其改进研究

遗传算法通过对参数的编码进行操作 ,而不是对参数本身进行操作 ,这使得它处理优化问题时 ,既 不要求函数连续 ,更不要求可微. 因此 ,这些函数既可以是数学解析式所表达的显函数 ,也可以是映射矩 阵甚至是神经网络等隐函数 ,因而应用范围较广. 进一步 ,该方法通过目标函数来计算适配值 ,不需要其

Ξ    收稿日期 :2002 - 09 - 111

基金项目 :教育部高校骨干教师资助计划资助 ( GG280721069821016) 1

作者简介 :任斌 ,1974 -  ,西安交通大学叶轮机械研究所博士研究生 ,从事叶轮机械气动热力学优化研究 1

— 14    —

任斌 ,等 :改进遗传算法与粒子群优化算法及其对比分析

它的推导和辅助信息 ,从而对问题的依赖较小. 遗传算法是从许多初始点开始并行操作 ,而不是从一个

点开始 ,因而可以有效的防止搜索过程收敛于局部最优 ,而且有较大的可能求得全部的最优解. 遗传算 法具有并行计算的特点 ,因而可通过大规模并行计算来提高计算速度. 上述特点使得遗传算法较适合复 杂问题的优化.

111 　简单遗传算法

简单遗传算法一般由编码机制 、适应值函数 、遗传算 子 、控制参数等四个部分组成[ 1 ] . 简单遗传算法由 0 和 1 进 行编码 ,0 和 1 称为基因 ,由基因组成二进制串 ,二进制串 称为染色体 (或称之为个体) ,染色体与优化问题的解相对 应 ,并通过编码和解码过程实现基因空间和解空间的转换.

遗传算法中的优胜劣汰的评价标准是通过适应值函数来体 现的 ,通过适应值函数的好坏可以判断解的好坏 ,从而判断 染色体的优劣. 对于优化问题 ,适应值函数是目标函数. 遗 传算法中的遗传算子 (genetic operato r) 主要有三种 :交叉算 子 (cro ssover ) 、变异算子 ( mutatio n) 、选择算子 ( selectio n) .

交叉和变异算子就是在算法中采用何种交叉和变异策略 , 即采用单点或是多点交叉或变异. 选择算子也称复制算子 ( rep ro ductio n) ,它的作用在于根据个体的优劣程度决定它 在下一代是被复制还是被淘汰. 一般来说 ,通过选择 ,适应 值较高的个体有较大的复制机会 ; 而适应值较小的个体即

低劣的个体在下一代中存在的几率也就较小. 简单遗传算

法中的 控 制 参 数 包 括 , 染 色 体 的 串 长 ( st ring) 、种 群 大 小

图 1 　简单遗传算法( S GA) 计算流程图

(pop    size) 、交叉概率 (pc) 、变异概率 (p m) 、最大遗传代数 ( maxgen) 等.

1 . 2 　改进遗传算法

本文在简单遗传算法的基础上 ,通过采用实数编码机制 ,并在遗传算子的改进等策略方面对简单遗 传算法进行了改进.

采用实数编码机制 ,即直接在优化问题的解空间进行编码 ,不但省去了基因空间与解空间之间的编

码和解码过程 ,而且可以提高解的精度及减少优化过程的计算量. 相应地 ,本文优化的二元函数采用如 下的交叉和变异算子.

交叉算子 :α3     = α + (β - α)  3 ω;

β3     = β + (α - β)  3 ( 1 -  ω)

变异算子 :α3     = α3 ( 1 -  ω 3 ( 1 -  gen/ maxgen)  3 3 2) ;

β3     = β3 ( 1 -  ω 3 ( 1 -  gen/ maxgen)  3 3 2) .

以上算子中 ,ω 为 [ 0 , 1 ] 之间的随机数 , gen 、maxgen 分别为进化的当前代数和最大代数. 以此实现 从上代染色体 (α,β) 到下代染色体 (α3   ,β3 )  的进化.

在对选择算子的改进方面 ,本文采用如下的选择方法产生下代种群.

①将杂交和变异产生的新染色体和父代所有染色体组合成新的被选种群 ;

②对被选种群按升序排列 ;

③删去所有重复的染色体 ;

④在被选种群中按顺序挑选两个染色体 ,计算其概率 min{1 ,exp ( - Δf /  T k ) } 当概率大于 rando m

[ 0 ,1 ]时 ,接受前一染色体进入新种群 ,否则 ,接受后一染色体进入新种群 ,按照这种选择 ,直到选择 pop

— 15    —

南京师范大学学报 (工程技术版)  　　　　　　　　　　　　　　　　　　　　　　　　　　第 2 卷第 2 期 (2002 年)

   size 个染色体组成新的种群.

改进后的遗传算法 ,由于采用了实数编码 ,避免了编码和解码的过程 ,有利于提高计算效率. 又由于 采用了合并种群的排序 、剔除重复染色体以及在这个基础上的模拟退火原理的概率接受机制选择下代

染色体[ 6 ]  ,这样 ,就可以以一定的概率接受较差解 ,即适应值较差的染色体. 遗传算法在原理上是一种 概率搜索方法 ,所以 ,只要所给的种群足够大 ,遗传代数足够多 ,原则上它是可以找到最优值的 ,但这必

须以牺牲时间为代价 ;而且 ,遗传算法作为一种优化算法 ,虽然其健壮性较好 ,但遇到多峰函数的时候 ,

有时候也难免收敛到局部最优值 ,而不是全局最优值. 存在这两种问题的原因 ,往往是在选择的过程中 ,

发生了有价值的染色体信息的丢失. 所以 ,以一定的概率接受较差解 ,就保证了种群的多样性 ,也保存了 有价值的染色体信息 ,从而可以使搜索最优解的时间缩短且可以防止遗传算法收敛到局部最优解 ,同时

也增强了其健壮性.

2 　粒子群优化算法

粒子群优化算法是对鸟群觅食过程中的迁徙和群集的模拟[ 5 ,7 ,8 ] . 鸟群在觅食时 ,在它们找到有食 物的地方之前的迁徙过程中 ,既有分散又有群集的特点. 所谓鸟语花香 ,鸟也有鸟的语言 ,它们总是通过 自己一套独有的方式在无时无刻地相互传递着信息 ,其实 ,这种个体之间信息的交换在群居的生物群体 中都存在 ,如蜜峰 、蚂蚁 ,也包括人类. 对于鸟群来说 ,在它们找到食源之前的从一地到另一地的迁徙过 程中 ,总是有那么一只鸟对食物的嗅觉较好 ,即对食源的大致方面具有较好的洞察力 ,从而 ,这只鸟就拥 有食源的较好信息. 由于在找寻食源的途中 ,它们又在无时无刻地相互传递信息 ,特别是这种较好的信 息. 所以 ,在这种“好消息”的指引下 ,最终导致了鸟群“一窝蜂”的奔向食源 ,达到了在食源的群集. J im Kennedy 从这种自然现象中受到启发 ,提出了粒子群优化算法. 解群相当于一个鸟群 ,一地到另一地的

迁徙相当于解群的进化 “,

好消息”相当于解群每代进化中的最优解 ,食源相当于全局最优解.

粒子群优化算法的数学抽象和实现步骤如下 :

设定有 N 个解的解群 X i [ d ] , i  ∈[ 1 , N ] , d  ∈[ 1 , M ] , d 为每个解的维数 , 即每个解可以是个解向 量. 然后 , 对每个解定义一个速度矢量 V i   , 该速度矢量相当于 ΔX i   , 该速度矢量在第一代中与解群一样 ,

是随机初始生成的. 对于进化的第 k 代来说 , 对于每一个解向量来说 , 通过如下关系式生成下代解向量.

X i  ( k  + 1)   =   X i  ( k)  +  V i  ( k) .     ( 1) 其次 ,定义 p best (perso nal best ) 和 gbest ( glo bal best ) 分别代表个体 k - 1 代和 k 代的较好值和 k 代 解群中的最好值 ,即 Xp best ,i和 X gbest ,i . 而 Xp best ,i -  X i  和 X gbest ,i -  X i  分别表示每代个体解向量位置和个

体最优位置及每代中最优个体位置的距离. 这种距离在速度矢量中体现. 如下式 :

V i  ( k + 1)   =  V i  ( k )  + η( Xp best , i     -   X i )    ( 2) V i  ( k + 1)   =  V i  ( k )  + η( X gbest , i     -   X i )    ( 3)

综合 ( 2)  式和 ( 3)  式可得到速度矢量的迭代变化 :

V i  ( k + 1)   = ωV i  ( k )  +  C1    ×η( Xp best ,  i   -   X i )  +  C2    ×η( X gbest ,  i   -   X i )    ( 4)

这样 , 新解可以这样产生 :

X i  ( k + 1)   =  X i  ( k)  +  V i  ( k + 1) .    ( 5) 以上各表达式中 : k 为进行代数 ; C1  , C2  分别为自定义常数 ;ω,η分别为 [ 0 , 1 ] 之间的随机数. 以本文函数优化为例 ,粒子群优化算法可以通过流程图来实现 (见图 2) . 粒子群优化算法具有和遗传算法某些相似的特征 ,所以 J im  Kennedy 也称之为一类进化算法. 该算

法的最大特点就是对函数优化显示了较高的效率 ,据本文作者的理解 ,是因为它借鉴了梯度优化方面的 一些理念.

— 16    —

任斌 ,等 :改进遗传算法与粒子群优化算法及其对比分析

3 　两种进化算法的对比分析

311 　数学问题

本文中为了对改进遗传算法和粒子群优化算 法进行对比分析 ,采用了以下数学问题[ 9 ] .

min f ( x , y )  = ( x - 10) 3   + ( y - 20) 3

s . t . ( x - 5) 2   + ( y - 5) 2   - 100 ≥

0 -  ( x - 6) 2   -  ( y - 5) 2   + 82 . 81 ≥0

13 ≤x ≤100 , 　0 ≤y ≤100

该问题为一带边界约束和非线性约束的二元 函数的 优 化 问 题. 已 知 全 局 最 优 解 为 ( x , y )  =

( 14 . 095 , 0 . 84296)  , F ( x , y )  = - 6 961 . 813 381 .

3 . 2 　两种进化算法的优化对比

在两种进化优化方法对上述函数结果的对比 作图中 ,为了清楚地看出解群随进化代数的变化

图 2 　粒子群优化算法流程图

情况 ,作者有意使其图形的坐标刻度随着进化代数的增加 ,逐渐减小 ,类似于一个解群变化的放大过程.

图中标号 ( gen) 表示进化代数. (见图 3 ,图 4) 1

3 . 2 . 1 　对改进遗传算法的考查

对于改进遗传算法而言 , 作如下的控制参数设定 : 群体规模大小 (pop     size) 为 20 ; 个体串长度

( st ring) 为 2 ;杂交概率 ( pc) 为 0 . 98 ,变异概率 ( p m) 为 0 . 01 ; 最大遗传代数 ( maxgen) 为 500 ; 初始温度

( T 0 ) 为 100 .

3 . 2 . 2 　对粒子群优化算法的考查

对于粒子群优化算法而言 ,作如下的参数设定 :粒子群的最大进化代数为 20 ;粒子群的种群大小为

20 ,维数为 2 ;粒子群算法速度矢量中的参数为 : C1  :3 . 0 ,C2  :3 . 0 ω,

3 . 2 . 3 　对比分析

:3 . 0 .

对于这两种进化算法对上述数学问题的优化 ,采用的计算机配置为 : CPU : 赛扬 1 G ; 内存 : 128 Mb ;

在这种配置下 ,两种算法的对比如表 1 所示.

表 1 　两种进化算法的性能对比

最优解. 从这两种进化算法的解群随进化代数的变化情况可以看出 ,粒子群优化算法在较少的进化代数 内 ,其解群就向最优解的方向收敛 ,这说明粒子群优化算法的优化效率较高. 改进遗传算法花费了较长

的计算时间 ,进行了较多的进化迭代 ,最终找到了最优解 ,其解群是逐渐收敛到最优解的 ,收敛速度较 慢. 这也正是遗传算法这种随机搜索算法的“特点”所在. 从数学算例的考查来看 ,粒子群优化算法和改

进遗传算法都表现了较好的健壮性.

从两种进化算法的原理看来 ,粒子群优化算法优化初期 ,其解群随进化代数而言表现了更强的随机 性 ,正是由于其产生下一代解群的较大的随机性 ,以及每代所有解的“信息”的共享性和各个解的“自我 素质”的提高 ,如解群随进化代数的变化过程中存在“掉队”个体的“归队”现象 ,这样 ,就使得每代种群中

— 17    —

南京师范大学学报 (工程技术版)  　　　　　　　　　　　　　　　　　　　　　　　　　　第 2 卷第 2 期 (2002 年)

图 3 　改进遗传算法的解随遗传代数的变化情况

的解具有“自我”学习提高和向“他人”学习的双重优点 ,这样 ,使得其下代解有针对性的从“先辈”那里继 承更多的信息. 在这种“自我提高”和“取人之长 ,补己所短”的前提下 ,很快就达到了群体最优 ,从而能在 较少的代数内找到最优解.

4 　结论

本文提出了一种改进的遗传算法 ,介绍了一种新的进化算法 —粒子群优化算法 ,并用相同的二元函 数数学问题对其进行了对比分析. 结果表明 ,改进遗传算法和粒子群优化算法在带约束条件数学函数的 优化方面都显示了较好的优化特性. 改进遗传算法和粒子群优化算法在函数优化方面显示的特征不同 , 前者耗时较长 ,在算法的改进方面还有待于做进一步工作 ,以提高其优化效率 ;后者的优化效率较高 ,但

— 18    —

任斌 ,等 :改进遗传算法与粒子群优化算法及其对比分析

图 4 　粒子群优化算法的解随进化代数的变化情况

还未见在实际的优化问题中广泛应用 ,所以还有待于与不同的实际优化问题相结合 ,以此验证其在实际 优化应用中的广泛性和健壮性.

[ 参考文献 ]

[ 1 ] 任平. 遗传算法 (综述) [J ] . 工程数学学报 ,1999 ,16 (1) :1～8 .

[ 2 ] 丰镇平 ,李军 ,沈祖达 1 遗传算法及其在透平机械化设计中的应用 [J ] . 燃气轮机技术 ,1997 ,11 (2) :13～22 .

[ 3 ] Li J un , Feng Zhenping , et  al . Aerodynamic Op timum Design of  Transo nic Turbine Cascades U sing  Genetic Algorit hms[J ] .

— 19    —

南京师范大学学报 (工程技术版)  　　　　　　　　　　　　　　　　　　　　　　　　　　第 2 卷第 2 期 (2002 年)

Journal of  Thermal Science ,1997 ,6 (2) :3～368 .

[ 4 ] 童彤 ,丰镇平 ,李军 1 遗传算法在透平叶栅多目标优化设计中的应用 [J ] . 中国电机工程学报 ,1999 ,19 (6)  :74～76 .

[ 5 ] V . Tando n. NC End Milling Opimizatio n U sing Evolutio nary Co mp utatio n [J ] . Internatio nal Journal of  Machine  Tools and

Manufact ure ,2001 ,42 :595～605 .

[ 6 ] 王雪梅 ,王义和 1 模拟退火算法和遗传算法的结合 [J ] . 计算机学报 ,1997 ,20 (4)  :381～384 .

[ 7 ] F Zhang ,D Xue. Op timal Co ncurrent Design Based upo n Dist ributed Product Develop ment Life2cycle Modeling[J ] . Robotics and Co mp uter Integrated Manufact uring ,2001 ,17 :469～486 .

[ 8 ] A R Cockshot t ,B E Hart man. Imp roving t he Fermentatio n Medium for Echinocandin B Productio n Part   Ⅱ: Particle Swarm

Op timizatio n [J ] . Process Biochemist ry ,2001 ,36 :661～669 .

[ 9 ] [ 美 ] Z. 米凯利维茨 ,著. 演化程序 ———遗传算法和数据编码的结合 [ M ] . 周家驹 ,等译. 北京 :科学出版社 ,2000 ,103 .

Improved Genet ic Algorithm and Part icle Swarm

Opt imizat ion a s well a s Comparison bet ween Them

Re n Bin , Fe ng Zhe nping

( Instit ute of  Turbo machinery , Xiπan J iaoto ng U niversit y ,710049 , Xiπan , PRC)

Abstract :As a new kind of op timizatio n search techniques , t he evolutio nary algorit hms are widely used to  solve different p rob2 lems in op timal  areas.  Af ter  a  caref ul  research ,  t he  simple  genetic  algorit hm  has  been  imp roved  by  adop ting float2coding met hod , simulated annealing algorit hm and sorted stochastic fit ness selectio n st rategy ; and has been applied to mat hematic f unc2 tio n op timizatio n.  In additio n , a new evolutio nary algorit hm2Particle Swarm Op timizatio n is int roduced and applied to t he same mat hematic f unctio n op timizatio n. The op timizatio n result s are co mpared wit h each ot her in t his paper . The co mparative result indicates t hat t he Imp roved Genetic Algorit hm and Particle Swarm Op timizatio n are bot h robust . But Particle Swarm Op timiza2 tio n can obtain t he op timum solutio ns more easily t han t he  Imp roved  Genetic Algorit hm ,and it is a good op timizatio n met hod wit h st ro ng co mpetitiveness.

Key words :f unctio n op timizatio n , imp roved genetic algorit hm , particle swarm op timizatio n

[ 责任编辑 :刘健 ]

— 20    —