基于遗传算法和粒子群优化的混合算法*
时小虎 1；韩世迁 2；闵克学 3；梁艳春 1*
（1. 吉林大学 计算机科学与技术学院，长春 130012；2. 沈阳化工学院 数理系，沈阳 110142；3. 通化师
范学院 数学系，通化 134002）
摘要：本文从进化计算的框架角度，比较分析了遗传算法与粒子群算法的个体、特征以及相关操作的异同，互相
取长补短，构造了基于实数编码遗传算法与粒子群算法的混合算法。并通过对若干标准测试函数的计算对所提算
法进行了检验。计算结果验证了本文提出的混合算法方法的有效性。
关键词：计算机应用，进化计算，混合算法，遗传算法，粒子群优化
中图分类号：TP18
The hybrid algorithm based on genetic algorithm
and particle swarm optimization
Shi Xiao-hu1；Han Shi-Qian2；Min Ke-Xue3；Liang Yan-chun1*
(1. College of Computer Science and Technology, Jilin University, Changchun 130012, China; 2. Department of
Mathematics and Physics of Shenyang Institute of Chemical Technology, Shenyang 110142, China; 3. Department
of Mathematics of Tonghua Teachers College, Tonghua 134002 )
Abstract：The similarities and differences of the individuals, characteristics and operations of Genetic Algorithm (GA) and Particle
Swarm Optimization (PSO) are compared and analyzed on the view of the framework of evolutionary computing. A hybrid algorithm
based on the GA using real coding and PSO is developed in this paper. Simulations using some standard functions are performed to
examine the effectiveness of the proposed method. Numerical results show the hybrid method is superior to GA and PSO.
Key words：Computer Application, Evolutionary Computation, Hybrid Algorithm, Genetic Algorithms, Particle Swarm Optimization
0 前言*
遗传算法（Genetic Algorithm, GA）是一类以达
尔文自然进化论和孟德尔遗传变异理论为基础的求
解复杂全局优化问题的仿生型算法，它是由美国 .
Holland 教授首次提出的[1,2]。遗传算法采用基于适
者生存，优胜劣汰的进化原则，对包含可能解的群
体反复使用遗传学的基本操作，不断地生成新的群
体，使种群不断进化，同时以全局并行搜索技术来
搜索优化群体中的最优个体，以求得满足要求的最
优解或准最优解。目前遗传算法已成功地应用于许
基金项目：教育部博士点基金项目（20030183060），国家自然科学基金技
资助项目(60433020)，吉林省科技发展国际合作项目（20050705-2），吉林
大学研究生创新基金（503041）
作者简介：时小虎（1974-），男，讲师。研究方向：计算智能。E-mail:
shixh@
* 通讯联系人：梁艳春（1953-），男，教授，研究方向：计算智能，生物
信息学。
多领域，例如：优化设计、模糊逻辑控制、神经网
络、专家系统、时序预测等[3-5]，成为 21 世纪有关
智能计算中的关键技术之一。
粒子群优化（Particle Swarm Optimization，PSO）
算法是一种基于群智能的演化计算技术，它是由
Kennedy 和 Eberhart 受人工生命研究结果的启发，
于 1995 年提出的[6-7]。PSO 算法与遗传算法类似，
也是一种基于群体的优化工具。粒子群优化算法具
有收敛速度快，容易实现，而且又具有深刻智能背
景的优点。目前，它已被国际进化计算会议列为讨
论的专题，并且广泛应用于函数优化，神经网络训
练，模式分类，模糊系统控制等多个领域[8-12]。
遗传算法和粒子群优化算法都有自身的特点和
优势，同样也都有某些缺陷和不足。因此人们自然
会想到通过充分利用不同算法的各自优势，取长补
短，研究它们之间的混合算法。如 Shi 将遗传算法
和粒子群算法通过并联和串联的方式混合起来，提
1
出了两种混合算法[13]； Settles 提出了一种自适应的
基于遗传算法和粒子群优化的混合算法[14]。本文在
比较分析遗传算法与粒子群算法的个体、特征以及
相关操作的异同的基础上，对两种算法取长补短，
将实数编码遗传算法的相关操作引入到粒子群算法
中，构造了基于这两种算法的混合算法，并用一些
标准测试函数进行了验证。结果表明所提出方法与
标准遗传算法和粒子群算法相比有一定的优势。
1 遗传算法简介
对于某一特定问题，遗传算法将每个解编码为
一个染色体个体。这样在解空间中定义一个初始群
体，此群体中的所有个体即表示解空间中的某一区
域。所有搜索空间即定义为整个解空间，在搜索空
间中，每一个可能的解都可以被编码为一个染色
体。在搜索开始之前，从搜索空间中随机地选择一
组染色体来形成初始群体。接下来由某一特定的目
标函数计算群体中所有个体的适应度值，根据它们
的适应度值，采取某种竞争的方式来选择个体，进
行遗传操作。
通过不断地使用选择、交叉、变异等遗传操作，
获得的染色体从总体质量上来说必然是一代比一代
更好。反复执行遗传操作直到满足终止条件为止，
最后一代中的最优染色体将解码为最终解。
2 粒子群优化算法简介
设在一个 D 维的搜索空间中，由 m 个粒子组成
一个群落。其中第 i 个粒子表示一个 D 维的向量，
记为 Xi=(xi1,xi2, …,xid),i=1,2,…,m，即第 i 个粒子在 D
维的搜索空间中的位置是 Xi。每个粒子的位置就是
一个潜在的解，将 Xi 带入某个为了满足问题而构造
的目标函数中可计算出其适应度值，然后根据适应
度值的大小衡量 Xi 的优劣。第 i 个粒子的速度也是
一个 D 维向量，记为：Vi=(vi1，vi2，…，viD)，第 i
个粒子迄今为止搜索到的最优位置为 Pi=(Pi1，
Pi2，…，PiD )，也称为 Pbest，整个粒子群迄今为止
搜索到的最优位置记为 Pg=(pg1，pg2，…，pgD)，也
称为 gbest。PSO 算法的计算公式如下：
tkVkXkX iii ∆++=+ )1()()1( (1)
tkXPrc
tkXPrckwVkV
ig
iiii
∆−+
∆−+=+
))((
))(()()1(
22
11 (2)
式中： mi ,,2,1 L= ；学习因子 C1 和 C2 是非负常
数；r1 和 r2 是介于[0，1]之间的随机数；w 为惯性
权重，是一个位于区间[0，1]中的常数；k 为迭代次
数；xi 为第 i 个粒子的位置向量；vi 为速度向量； t∆
为时间间隔，常取为单位时间。
3 遗传算法与粒子群优化算法的比较
遗传算法和粒子群算法都是作用在由若干个个
体（individuals）所构成的群体（population）上的，
每个个体代表一个潜在解（solution），或是潜在解
的 一 部 分 。 每 个 个 体 又 是 由 一 个 特 征
（characteristics）集合所构成的，正是这些特征将
个体映射到某个特定解上。这个特征集合定义了群
体中所有个体所处的一个状态空间。算法的目标是
通过个体的亲合度（affinity，或适应度），找到状态
空间的一个“好”位置。遗传算法的个体为染色体
（chromosomes）；特征为基因（gene）。而粒子群算
法的个体为鸟（bird）或粒子（particle）；特征为位
置（position），速度（velocity）和邻居（neighbourhood
group）。
两种算法在每次迭代中都要对群体中的个体进
行各种操作，虽然不同算法操作不尽相同，但大致
都包含着进化算法的下面几个步骤[15,16]：
1. 产生：生成群体中的新个体。
在第一代要生成整个种群的所有个体，并且初
始化所有个体的相关特征；在以后各代中，如果需
要的话，产生足够的个体将种群加满。
遗传算法：各染色体的基因都是随机产生的，
这样可以尽可能多的覆盖搜索空间。
粒子群算法：各个粒子（鸟）的位置、速度都
是随机生成的，其相关的个体最佳位置设定为初始
位置，群体最佳位置通过搜索得到。
2. 评价：评价每个个体与解的亲合度。
亲合度是用来度量每个个体所代表解的好坏程
度的，它是由使用者定义的关于个体特征的一个函
数。该函数要求能够将特征空间比较理想地映射到
反映解空间好坏程度的实数域上，然而这并非总是
能够做到的。
遗传算法：亲合度是适应度（fitness）函数，
即关于基因的一个函数；
粒子群算法：亲合度或者说适应度函数是关于
当前粒子位置的函数。
3. 测试：测试终止条件是否满足。
测试条件一般都选为是否找到了足够好的解或
是迭代次数到达限定值。
2
4. 选择：依据当前种群中个体的亲合度大小，
从中选择特定的个体，选择出的个体将要用来生成
下一代的新个体；
按照“适者生存”的生物基本原理，在选择过
程中，高亲合度的个体总是倾向于被选中。常见的
选择算法主要有以下几种：1. 最佳个体选择法：从
当前个体中选择 n 个亲合度最高的个体；阈值选择
法：选择那些亲合度值高于某一给定阈值的个体；
赌轮选择法：随机地选择一定数目的个体，个体被
选中的概率与其适应度值成正比；竞赛选择法：将
个体随机编成若干个队，按各队的平均适应度值随
机选择某队。
遗传算法：上面提到各种方法都有使用；
粒子群算法：整个群体都被选择。
5. 繁殖：生成下一代的新个体。
繁殖新个体一般涉及到对选择出的个体的特征
进行重新组合。
遗传算法：将选出的两个父代个体的特征通过
交叉操作进行重组；
粒子群算法：新个体是通过单个个体与群体中
亲合度最高的个体繁殖得到的，使得产生的新个体
趋向于向最优个体的方向移动。新的位置还受到父
代个体的位置速度和速度的影响，速度朝着最优个
体的方向改变。
6. 变异：改变选择出来的个体。
变异涉及到群体中单个个体特征的改变。变异
的概率可以是整个群体都一致的，也可以按亲合度
的不同而变化的。对特征的改变方式取决于特征的
形式：如果特征是布尔型的，则直接进行反转即可；
如果特征是数值型的，则可以由一增加剂控制其增
加或减少。
遗传算法：个体的变异是随机的，这样能够重
新引入那些已经丢掉的特征。
粒子群算法：不发生变异。
知道了两种算法个体与特征以及各操作的不同
表现形式，我们就可以根据不同算法的特点，互相
取长补短，构造它们的混合算法。
3 基于遗传算法和粒子群优化的混合
算法
通过上节的介绍可以看出遗传算法与粒子群算
法的不同点主要体现在两个方面。首先，遗传算法
是通过某种选择策略选出若干个个体两两配对进行
繁殖，而粒子群算法是将所有的个体与群体最佳个
体进行繁殖，生成下一代个体；第二，遗传算法有
变异操作，而粒子群没有变异操作。本文提出的混
合算法是以粒子群算法为模版，针对这两点不同设
计得到的。因为粒子群算法在连续空间是实数编码
的，所以遗传算法也相应地考虑实数编码遗传算法。
对于第二点比较简单，只需要在粒子群算法中增加
一个变异操作即可。对于第一点，我们在粒子群原
来的繁殖操作基础上增加类似遗传算法的一个选
择、交叉过程。下面我们详细讨论这两个步骤。
选择、交叉过程：首先，按照某种选择策略选
出 M（偶数）个个体，这里可以是上面提到过的任
一种选择算法，本文选用赌轮选择法。然后对选出
的个体两两配对，执行交叉操作，即随机生成一个
[0，1]区间的实数 r，以概率 pc执行下面的交叉：
gapgapgap xrxrx 211 )1(ˆ ⋅−+⋅= (3)
gapgapgap xrxrx 122 )1(ˆ ⋅−+⋅= (4)
gapgapgap vrvrv 211 )1(ˆ ⋅−+⋅= (5)
gapgapgap vrvrv 122 )1(ˆ ⋅−+⋅= (6)
式中：gap 代表迭代次数，x1gap，x2gap和 v1gap，v2gap
分别代表选出的两个父代个体的位置向量和速度向
量， gapx1ˆ ，
gapx1ˆ 和
gapv1ˆ ，
gapv1ˆ 分别代表经过交叉后
得到的子代个体的位置向量和速度向量。
变异操作：以概率 pm对每个执行完交叉操作的
个体 gapkxˆ 执行下面的变异操作：
⎩⎨
⎧ >++=+
otherwisex
xfitnesscxfitnessifcx
x gap
k
gap
kk
gap
kk
gap
kgap
k ˆ
)ˆ()ˆ(ˆ1
(7)
gap
k
gap
k vv ˆ
1 =+ (8)
式中：ck是区间[xL- gapkxˆ , xU-
gap
kxˆ ]上均匀分布的随
机数， xL和 xU分别是搜索区间的上下限；fitness(﹒)
是适应度函数。
下面我们给出该算法的流程：
1. 初始化粒子群中所有 N 个个体位置及其速度，搜
索群体最佳个体位置 Pg，将个体的历史最佳位置
Pi 设定为初始位置，设置迭代次数 gap=0；
2. 按式（2）和（1）更新每个粒子的速度和位置，
并计算它们的适应度值；
3. 如果满足终止条件输出最优解，终止程序，否则
继续 4；
3
4. 按适应度值随机选出 M 个个体，对它们执行交
叉操作，得到 M 个新个体；
5. 对所有个体执行变异操作，在 M+N 中选择适应
度高的个 N 个体进入下一代，转 2。
算法的流程如图 1 所示。
表 1 测试函数的详细信息
Table 1 Details of test functions
Fun.
No. Test Function
Global
Optimum fitness
F1
)]273648123218(
)32(30[)]36
1431419()1(1[min
2
2212
2
11
2
21
2
221
2
2
11
2
21
xxxxxx
xxxxx
xxxxxF
+−++−×
−+×++
−+−+++=
X[0,-1],
F=3 1/(F-3+)
F2 221
2
21 )3/)10(()(min −++−= xxxxF X[5,5], F=0 1/(F+)
F3 21
2
2
2
1 )1()(100min xxxF −+−= X[1,1], F=0 1/(F+)
F4 ∑
=
+ −+−=
3
1
22
1
2 )1()(100min
i
iii xxxF
X[1,1,1,1],
F=0 1/(F+)
F5 ∑
=
=
30
1
2min
i
ixF X[0,…,0], F=0 1/(F+)
图 1 遗传算法与粒子群算法的混合算法流程图
Fig. 1 Flow chart of the hybrid algorithm based on GA and PSO
初始化粒子群所有 N
个个体，gap=0
No
更新每个粒子的速度和位
置，计算它们的适应度值
满足结束条件？
对所有 M+N 个个体执行变异操
作，在 M+N 个新个体中选择
N 个适应度高的进入下一代
输出最优解，
终止程序
Yes
按适应度值随机选出 M 个
个体，对它们执行交叉操
作。得到 M 个新个体
4
4 数值计算及结果比较
选择 5 个测试函数对本文提出的混合算法进行
测试，并将结果与标准遗传算法和粒子群优化算法
进行比较。所有的计算都是在 2GHZ Pentium PC 机
上用 C++语言进行的模拟。表 1 列出了用来检验的
5 个标准测试函数，它们的维数从 2 维到 30 维不等，
Global Optimum 给出了各函数的全局极值点和所取
极值，fitness 为计算过程中所取的适应度值，按照
表 1 中 fitness 的定义，已经将原极小值问题全部转
化为最大值为 100 的极大值问题。表 2 列出了比较
结果，每种算法都是计算 100 次之后的统计结果，
每次运行迭代到 10000 步停止（混合算法的总迭代
次数为 10000 次）。当计算结果满足 fitness< 时，
我们认为模拟计算是成功的。在各表中，Success (%)
表示成功率，Average 表示计算出来的适应度的平
均值。
从表 2 可以看出，对于 F1 和 F2，混合算法的
计算结果在成功率和平均适应度值方面都与粒子群
算法相差不大，但明显好于遗传算法；而对于 F3，
三种算法的计算结果都比较差，这主要是因为 F3
的强病态性质所致，混合算法的成功率虽略低于遗
传算法，但这是在较低水平上比较，而它的平均适
应度值则远高于遗传算法，略高于粒子群算法；对
于 F4，混合算法的成功率为 71%，低于遗传算法的
100%，而高于粒子群算法的 65%，它的适应度值也
略高于粒子群算法，且维持在 以上的较高水平
上；对于 F5，三种算法的结果都比较好，混合算法
在成功率和平均适应度值方面都与粒子群算法相
当，而稍好于遗传算法。图 2 给出了三种算法对于
5 个测试函数计算结果的统计柱状图。由图中可以
看出，混合算法的成功次数要高于其它两种算法；
而其适应度在 之间的较高水平次数以及适
应度在 20-95 之间的次数都与粒子群算法相差不
大，要明显高于遗传算法；适应度在 20-1 和<1 的
较低水平次数也与粒子群算法相当，而明显低于遗
传算法。
5 结论
本文通过比较和分析遗传算法与粒子群算法的
个体、特征以及各操作的相同点与不同点，互相取
长补短，通过将实数编码遗传算法的选择、交叉和
变异操作引入到粒子群算法中，构造了基于两种算
法的混合算法。通过对 5 个标准测试函数的计算对
该算法进行了检验，并与标准遗传算法和粒子群算
法的结果进行了比较。结果表明，从整体来看，不
论是在成功率方面还是在平均适应度值方面，混合
算法的计算结果都要稍好于粒子群算法，而明显强
于遗传算法。计算结果验证了本文所提出混合算法
的有效性。
表 2 各算法对测试函数的计算结果比较
Table 2 Comparisons of the results of different methods
Functions Methods Success (%) Average
GA 62
PSO 100 F1
HYBRID 100
GA 54
PSO 100 F2
HYBRID 100
GA 3
PSO 0 F3
HYBRID 0
GA 100 100
PSO 65 F4
HYBRID 71
GA 99
PSO 100
HYBRID 100
5
0
100
200
300
400
su
cc
es
se
d
95
-9
9.
9
20
-9
5
20
~1 <1
适应度值
次
数
GA
PSO
GA+PSO
图 2 三种算法对于 5 个测试函数统计结果的柱状图
Fig. 2 Histogram of statistical results of three methods for five test functions
参考文献
[1] Holland ., Adaptation in Natural and
Artificial System, The University of Michigan
Press, Ann Arbor, 1975.
[2] Goldberg ., Genetic Algorithms in Search,
Optimization & Machine Learning,
Addison-Wesley, Reading MA, 1989.
[3] Stender J., Parallel Genetic Algorithms: Theory
and Applications, IOS Press, Amsterdam, 1993.
[4] Back T., Evolutionary Algorithms in Theory
and Practice, Oxford University Press, Oxford,
1996.
[5] Schwefel ., Evolution and Optimum Seeking,
John Wiley & Sons, New York, 1994.
[6] Kennedy J. and Eberhart ., Particle swarm
optimization, Proceedings of the IEEE
International Conference on Neural Networks,
1995，–1948.
[7] Eberhart . and Kennedy J., A new optimizer
using particle swarm theory, Sixth International
Symposium on Micro Machine and Human
Science, 1995, pp. 39-43.
[8] Kennedy J., The Particle Swarm: social
adaptation of knowledge, in: Proceedings of
IEEE International Conference on Evolutionary
Computation, Indianapolis, Indiana, IEEE
Service Center, Piscataway, NJ, 1997, pp.
303-308.
[9] Shigenori N., Takamu G., Toshiki Y. and
Yoshikazu F., A hybrid particle swarm
optimization for distribution state estimation,
IEEE Transactions on Power Systems, 18 (1)
(2003) 60-68.
[10] Ge . and Liang . A Hidden Markov
Model and Immune Particle Swarm
Optimization-Based Algorithm for Multiple
Sequence Alignment, Lecture Notes in Artificial
Intelligence, 2005, Vol. 3809: 756–765.
[11] Thomas M., Misra ., Kambhamettu C. and
Kirby . Dynamic open contours using
particle swarm optimization with application to
fluid interface extraction. Lecture Notes in
Computer Science, 2006, Vol. 3851: 643–652.
[12] Omran ., Salman A. and Engelbrecht .
Dynamic clustering using particle swarm
optimization with application in image
segmentation. Pattern Analysis and Applications,
2006, 8 (4): 332-344.
[13] Shi ., Lu ., Zhou ., Lee ., Lin
. and Liang . Hybrid evolutionary
algorithms based on PSO and GA. Proceedings
of the 2003 Congress on Evolutionary
Computation, Canberra, Australia, 2003, 4:
2400-2405.
[14] Settles M. and Soule T. Breeding swarms: A
GA/PSO hybrid. GECCO 2005 - Genetic and
Evolutionary Computation Conference, 2005,
161-168.
[15] Eiben ., Schoenauer M., Evolutionary
computing, Information Processing Letters,
2002, 82 (1): 1-6.
[16] John N. and Susan S., A Generic Framework for
Population-Based Algorithms2005, Lecture
Notes in Computer Science, 3627, 43–55.
6
