http://www.ma-xy.com

第一章智能优化 1

1.1 问题的引入与分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 遗传算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.1 GA 的基本思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2.2 GA 的算法步骤 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.3 遗传框架的改进 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.2.4 GA

工具箱介绍

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.2.5 附：GA 算法的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1.2.6 多目标规划中的遗传算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

1.3 粒子群算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

1.3.1 基本思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

1.3.2 基本步骤 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

1.3.3 PSO 改进策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

1.3.4 PSO 工具箱 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

1.4 蚁群算法 ACA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

1.4.1 基本思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

1.4.2 抽象描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

1.4.3 基本步骤 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

1.4.4 ACA 改进策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

1.4.5 连续域蚁群算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

1.5 模拟退火 SA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

1.5.1 基本思想 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

1.5.2 基本步骤 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

1.5.3 SA 工具箱 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

1.6 其他智能优化算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

1.6.1 鱼群算法 AFSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

1.6.2 萤火虫算法 GSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

1.6.3 萤火虫算法 FA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

1.6.4 蝙蝠算法 BAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

http://www.ma-xy.com

1.6.5 布谷鸟算法 CUCKOO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

1.6.6 蜂群算法 ABC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

1.6.7 蛙跳算法 SFLA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

http://www.ma-xy.com 2 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化

1.1 问题的引入与分析

考虑如下 2 个最优化问题：1. 只有边界约束 (1.1)；2. 有边界约束和不等式约束 (1.2)。引例

1：

min

x,y

f(x, y) = x cos(2πy) + y sin(2πx) (1.1)

s.t. − 0.5 ⩽ x ⩽ 3.5

− 2 ⩽ y ⩽ 3

用 MATLAB 求解上述引例 1(1.1) 的程序如下

1 %% 智能优化引例 1 : 无约束

2 % max f ( x , y )=y* s in (2* pi *x)+x* cos (2* pi *y)

3 % s . t.−0.5<=x<=3.5; −2<=y<=3;

4 %目标函数

5 fun = @(x) x (1) * cos (2* pi *x(2) ) + x ( 2) * si n (2* p i *x ( 1) ) ;

6 [X, Y] = meshgrid ( −4:0.0 3 5:4 , − 4 :0.035:4 ) ;

7 Z = arrayfun (@(x , y ) fun ( [ x y ] ) , X, Y) ;

8 domain = [−3 5 . 5 −4 5 ] ;

9 % f i g u r e

10 % s ur f (X, Y, Z, ’ EdgeColor ’ , ’ none ’ )

11 % x l ab e l x , y l ab e l y , z l a b e l z

12 f i g u r e ;

13 h (1) = ezcontour (@(X,Y) arra yfun (@(x , y ) fun ( [ x y ] ) ,X,Y) , domain , 1 50) ;

14 hold on

15 % Plot bounds

16 l b = [ −0.5 −2];

17 ub = [ 3 . 5 3 ] ;

18 h (2) = l i n e ( [ l b (1 ) l b (1) ] , [ lb ( 2 ) ub ( 2 ) ] , ’ LineStyle ’ , ’−−’ ) ;

19 h (3) = l i n e ( [ ub ( 1) ub ( 1) ] , [ lb (2 ) ub( 2) ] , ’ L i n e S t y le ’ , ’−−’ ) ;

20 h (4) = l i n e ( [ l b (1 ) ub(1) ] , [ lb ( 2 ) l b (2) ] , ’ LineStyle ’ , ’−−’ ) ;

21 h (5) = l i n e ( [ l b (1 ) ub(1) ] , [ ub( 2 ) ub(2) ] , ’ Line S t y l e ’ , ’−−’ ) ;

22 t i t l e ( ’ 目标函数及约束条件 ’ )

23 x0 = [ 3 −1];

24 opts = optimoptions ( ’ fmincon ’ , ’ Algorithm ’ , ’ sqp ’ ) ;

25 problem = createOptimProblem ( ’ fmincon ’ , ’ o b j e c ti ve ’ , . . .

26 @(x ) −fun ( x) , ’ x0 ’ , x0 , ’ lb ’ , lb , ’ub ’ ,ub , . . .

27 ’ nonlcon ’ , [ ] , ’ opti o n s ’ , opts ) ;

http://www.ma-xy.com

1.1 问题的引入与分析第一章智能优化

28 t i c

29 [ xl o cal , f v a l l o c a l ] = fmincon ( problem )

30 toc

31 %找最大值

32 ind1 = fi n d (X( 1 , : )<=ub (1) & X( 1 , : )>=lb ( 1 ) ) ;

33 ind2 = fi n d (Y( : , 1 )<=ub (2) & Y( : , 2 )>=lb ( 2 ) ) ;

34 [ a , row ] = max(Z( ind2 ’ , ind1 ) ) ;%a 为各列的最大值

35 [ fv a l g lo ba l , co l ] = max( a ) ;%col 为最大列

36 row = row( c o l ) ;%最大行

37 maxIdx1 = c o l + ind1 (1 ) − 1 ;

38 maxIdx2 = row + ind2 (1) − 1;

39 % i f Z( maxIdx2 , maxIdx1) == fmax , dis p ( ’ r i g h t ’ )

40 %最大值

41 fv a l g l o b a l

42 xglobal = [X(1 , maxIdx1) ,Y( maxIdx2 , 1 ) ]%最大值点

43 h (6) = plot ( x l o c a l ( 1 ) , x l o c a l ( 2 ) , ’ r * ’ , ’ MarkerSize ’ ,1 6 ) ;

44 text ( x l o c a l (1) , x l o c al ( 2 ) , ’ 局部极大值 ’ )

45 h (7) = plot ( xglobal (1) , xglobal (2) , ’mp’ , ’ MarkerSize ’ , 1 6) ;

46 text ( x g l o b a l ( 1 ) , xglobal ( 2) , ’ 全局极大值 ’ )

47 %使用全局搜索方法求解

48 % 1 、 Construct a GlobalSearch o b j ect

49 gs = GlobalSearch ;

50 % 2 、Run GlobalSearch

51 t i c ;

52 [ xgs , ~ ,~ ,~ , so l s g s ] = run ( gs , problem) ;

53 toc

54 xgs

55 % 3 、 Plot GlobalSearch r e s u l t s us ing the ’ * ’ marker

56 xGS = cell2m at ({ s o l s g s ( : ) .X} ’) ;

57 h (8) = s c a t t e r (xGS( : , 1 ) ,xGS( : , 2 ) , ’ s ’ , ’ MarkerEdgeColor ’ , [ 0 0 1 ] , ’ LineWidth ’ , 1 .2 5) ;

58 %使用多初始点方法求解

59 % 1 、 Construct a MultiSt art obj e c t based on our GlobalSearch a t t r i b u t e s

60 ms = Multi Star t ;

61 rng ( 4 , ’ t w i s t e r ’ ) % f o r r e p r o d u c i b i l i t y

62 % 2 、 Run the s o l v e r with 15 randomly generated poin t s

63 t i c ;

64 [ xms,~ , ~ , ~ , solsms ] = run (ms, problem , 1 5 ) ;

65 toc

66 xms

67 % 3 、 Plot M ultiS tart r e s u l t s using a c i r c l e marker

68 xMS = cell2 mat ({ solsms ( : ) .X} ’ ) ;

69 h (9) = s c a t t e r (xMS( : , 1 ) ,xMS( : , 2 ) , ’o ’ , ’MarkerEdgeColor ’ , [ 0 0 0 ] , ’LineWidth ’ , 1. 2 5 ) ;

70 legend ( [ h (1) , h ( 2 ) ,h ( 6 ) ,h (7) , h ( 8) ,h ( 9 ) ] , ’ I n t e n s it y ’ , ’Bound ’ , ’ Local ’ , . . .

71 ’ Global ’ , ’ GlobalSearch ’ , ’ M ultiStart ’ , ’ l o c a t i o n ’ , ’ bes t ’ )

72 t i t l e ( ’ GlobalSearch and Multi Star t Resul t s ’ )

上述引例 1(1.1) 只考虑了边界约束，这是容易处理的。下面，我们在上面的模型中，添加不

http://www.ma-xy.com 2 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.1 问题的引入与分析

等式约束：引例 2

min

x,y

f(x, y) = x cos(2πy) + y sin(2πx) (1.2)

s.t. (x − x

)

+ (y − y

)

⩽ r

(x − x

)

+ (y − y

)

⩽ r

(x − x

)

+ (y − y

)

⩽ r

− 0.5 ⩽ x ⩽ 3.5

− 2 ⩽ y ⩽ 3

用 Matlab 求解引例 2(1.2) 的程序如下

1 %% 智能优化引例 2 ：有约束

2 % max f (x , y )=y* s in (2* pi *x)+x*cos (2* p i *y)

3 % s . t . −0.5<=x<=3.5; −2<=y<=3;

4 % (x−xcoords (1) ) . ^ 2 + ( y−ycoords (1) ) .^2 <= 9 ;

5 % (x−xcoords (2) ) . ^ 2 + ( y−ycoords (2) ) .^2 <= 9 ;

6 % (x−xcoords (3) ) . ^ 2 + ( y−ycoords (3) ) .^2 <= 9 ;

7 %目标函数

8 fun = @(x) x (1) * cos (2* pi *x(2) ) + x ( 2) * si n (2* p i *x ( 1) ) ;

9 [X, Y] = meshgrid ( −4:0.0 3 5:4 , − 4 :0.035:4 ) ;

10 Z = a rrayfun (@(x , y ) fun ( [ x y ] ) , X, Y) ;

11 %约束条件

12 xcoords = [ 2. 4 11 2 0.2 064 1 . 6 7 8 7 ] ;

13 ycoords = [ 0. 3 95 7 0.3 927 0 . 9 8 7 7 ] ;

14 domain = [−3 5 . 5 −4 5 ] ;

15 f i g u r e ;

16 f (1 ) = ezcontour (@(X,Y) arrayfun (@(x , y ) fun ( [ x y ] ) ,X,Y) , domain , 1 50) ;

17 hold on

18 % Plot c o ns t r a i n ts

19 g1 = @(x , y) (x−xcoords ( 1 ) ) .^2 + (y−ycoords ( 1 ) ) .^2 − 9 ;

20 g2 = @(x , y) (x−xcoords ( 2 ) ) .^2 + (y−ycoords ( 2 ) ) .^2 − 9 ;

21 g3 = @(x , y) (x−xcoords ( 3 ) ) .^2 + (y−ycoords ( 3 ) ) .^2 − 9 ;

22 f (2 ) = e zpl o t ( g1 , domain) ;

23 f (2 ) . Color = [ 0 . 8 0.7 0 . 1 ] ; % yell ow

24 f (2 ) . LineWidth = 1 . 5 ;

25 f (3 ) = e zpl o t ( g2 , domain) ;

26 f (3 ) . Color = [ 0 . 3 0.7 0 . 5 ] ; % green

27 f (3 ) . LineWidth = 1 . 5 ;

28 f (4 ) = e zpl o t ( g3 , domain) ;

29 f (4 ) . Color = [ 0 . 4 0.4 0 . 6 ] ; % blue

30 f (4 ) . LineWidth = 1 . 5 ;

31 % Plot bounds

32 l b = [ −0.5 −2];

33 ub = [3 . 5 3 ] ;

34 f (5 )=l i n e ( [ lb ( 1 ) lb ( 1 ) ] , [ l b (2) ub( 2 ) ] , ’ L i neStyle ’ , ’−−’ ) ;

35 f (6 )=l i n e ( [ ub ( 1 ) ub(1) ] , [ lb ( 2 ) ub ( 2 ) ] , ’ LineStyl e ’ , ’−−’ ) ;

36 f (7 )=l i n e ( [ lb ( 1 ) ub ( 1 ) ] , [ lb (2 ) l b (2) ] , ’ LineStyl e ’ , ’−−’ ) ;

37 f (8 )=l i n e ( [ lb ( 1 ) ub ( 1 ) ] , [ ub( 2 ) ub ( 2 ) ] , ’ L i n eStyle ’ , ’−−’ ) ;

38 t i t l e ( ’ 目标函数及约束条件 ’ )

39 % f u nction [ c , ceq ] = aperture C onstrain t ( x , xcoords , ycoords )

http://www.ma-xy.com 3 http://www.ma-xy.com

http://www.ma-xy.com

1.1 问题的引入与分析第一章智能优化

40 % ceq = [ ] ;

41 % c = ( x (1) − xcoords ) . ^ 2 + ( x (2 ) − ycoords ) .^2 − 9 ;

42 % end

43 %构建约束条件函数

44 FunConstraint = @(x ) aper t u reConst r a int (x , xcoords , ycoords ) ;

45 x0 = [ 3 −1];

46 opts = optimoptions ( ’ fmincon ’ , ’ Algorithm ’ , ’ sqp ’ ) ;

47 problem = createOptimProblem ( ’ fmincon ’ , ’ o b j e c ti ve ’ , . . .

48 @(x ) −fun ( x) , ’ x0 ’ , x0 , ’ lb ’ , lb , ’ub ’ ,ub , . . .

49 ’ nonlcon ’ , FunConstraint , ’ op t i ons ’ , opts ) ;

50 t i c

51 [ xl o cal , f v a l l o c a l ] = fmincon ( problem )

52 toc

53 %找最大值

54 ind1 = fi n d (X( 1 , : )<=ub (1) & X( 1 , : )>=lb ( 1 ) ) ;

55 ind2 = fi n d (Y( : , 1 )<=ub (2) & Y( : , 2 )>=lb ( 2 ) ) ;

56 [ a , row ] = max(Z( ind2 ’ , ind1 ) ) ;%a 为各列的最大值

57 [ fv a l g lo ba l , c o l ] = max( a ) ;%c o l 为最大列

58 row = row( c o l ) ;%最大行

59 maxIdx1 = c o l + ind1 (1 ) − 1 ;

60 maxIdx2 = row + ind2 (1) − 1;

61 % i f Z( maxIdx2 , maxIdx1) == fmax , dis p ( ’ r i g h t ’ )

62 %最大值

63 f v a l g l o b a l

64 xglobal = [X(1 , maxIdx1) ,Y( maxIdx2 , 1 ) ]%最大值点

65 f (9 ) = p l ot ( x l o ca l (1) , x l oc a l ( 2) , ’ r * ’ , ’ MarkerSize ’ ,16) ;

66 text ( x l o c a l (1) , x l o c al ( 2 ) , ’ 局部极大值 ’ )

67 f (10) = plot ( x g l ob al ( 1 ) , xglobal (2) , ’mp’ , ’ MarkerSize ’ , 1 6) ;

68 text ( x g l o b a l ( 1 ) , xglobal ( 2) , ’ 全局极大值 ’ )

69 %使用全局搜索方法求解

70 % 1 、 Construct a GlobalSearch o b j ect

71 gs = GlobalSearch ;

72 gs = GlobalSearch ( gs , ’ StartPointsToRun ’ , ’ bounds−ineqs ’ , . . .

73 ’MaxWaitCycle ’ ,3 , ’ BasinRadiusFactor ’ , 0 . 3 ) ;

74 % 2 、Run GlobalSearch

75 t i c ;

76 [ xgs , ~ ,~ ,~ , so l s g s ] = run ( gs , problem) ;

77 toc

78 xgs

79 % 3 、 Plot GlobalSearch r e s u l t s usin g the ’* ’ marker

80 xGS = cell2m at ({ s o l s g s ( : ) .X} ’) ;

81 f (11) = s c a t t e r (xGS ( : ,1 ) ,xGS ( : , 2 ) , ’ s ’ , ’ MarkerEdgeColor ’ , [ 0 0 1 ] , ’ LineWidth ’ , 1. 2 5 ) ;

82 %使用多初始点方法求解

83 % 1 、 Construct a MultiSt art obj e c t based on our GlobalSearch a t t r i b u t e s

84 ms = Multi Star t ;

85 rng ( 4 , ’ t w i s t e r ’ ) % f o r r e p r o d u c i b i l i t y

86 ms = Multi Star t (ms, ’ U s e P aral l e l ’ , true ) ;% Set the UseP a r allel property o f MultiStar t

87 t r y

88 demoOpenedPool = f a l s e ;

89 % Create a p a r a l l e l pool i f one does not al ready e x i s t

90 % ( r e q u i r e s P a r a l l e l Computing Toolbox )

91 i f max( s i z e ( gcp) ) == 0 % i f no pool

92 parpool

http://www.ma-xy.com 4 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

93 demoOpenedPool = t r u e ;

94 end

95 catch ME

96 warning ( message ( ’ globaloptim : globaloptimdemos : o p t i calInterfe r e n ceDemo :noPCT ’ ) ) ;

97 end

98 %2 、 Run the s ol ve r with 15 randomly generated points

99 t i c ;

100 [ xms,~ , ~ , ~ , solsms ] = run (ms, problem , 1 5 ) ;

101 toc

102 xms

103

104 i f demoOpenedPool

105 % Make sure to d e le te the pool i f one was c reated in t h i s example

106 d e le te ( gcp ) % d e l e t e the pool

107 end

108 %3 、 Plot Multi Star t r e s u l t s us ing a c i r c l e marker

109 xMS = cell2 mat ({ solsms ( : ) .X} ’ ) ;

110 f (12) = s c a t t e r (xMS( : , 1 ) ,xMS( : , 2 ) , ’o ’ , ’ MarkerEdgeColor ’ , [ 0 0 0 ] , ’ LineWidth ’ , 1 . 2 5 ) ;

111 legend ( [ f ( 1) , f (2 ) , f (5 ) , f (9 ) , f ( 1 0) , f (11) , f ( 1 2 ) ] , . . .

112 ’ In te n s i t y ’ , ’ C onstrai n ts ’ , ’Bound ’ , ’ GlobalSearch ’ , ’ Mu ltiS tart ’ , ’ Location ’ , ’ best ’ )

113 t i t l e ( ’ GlobalSearch and Multi Star t Resul t s ’ )

114

前面几章，我们所讨论的优化算法都是基于 x

k+1

= x

+ α

，并且都有明确的步长 α

，明

确的方向 d

，也即 α

, d

并不存在随机性。这一部分，我们要介绍的方法都是随机化方法，也

称为智能优化方法。

1.2 遗传算法

1.2.1 GA 的基本思想

1975 年，Michigan 大学的 J.Holland 教授提出” 遗传算法” 的概念，并出版了著作《Adaptation

in Netural and Articial systems》。J.Holland 提出的遗传算法属于简单遗传算法，还处于遗传

算法发展初期。大约在同一时期，FoegL 和 Rechenberg 以及 Schwefel 引入了另两种基于自然演

化原理的算法；演化程序和演化策略。这三种算法构成了目前演化计算领域的三大分支。

Holland 不仅设计了遗传算法，更重要的是，他运用统计决策理论对 GA 的搜索机理进行了

理论分析，建立了著名的 Schema 定理和隐含并行性原理，为遗传算法的发展奠定了基础。De

Jong 在他的博士论文中将 GA 算法应用到函数优化问题，并设计了一系列遗传算法的执行策略

和性能评价指标。De Jong 的实时 (Ontime) 和非实时 (Otime) 指标仍是 GA 性能的主要评价

指标，并且论文中挑选了 5 个试验函数，也是目前 GA 数值实验中使用最多的试验函数。

GA 的发展高潮开始于 20 世纪 80 年代末，这里简略介绍 GA 在神经网络、机器学习中的应

用。神经网络的学习包含两个过程：网络连接权重和网络拓扑结构。其中，权重的优化方法最著

名的是 Rumelhart 提出的基于梯度下降法的反向传播算法 (BP)。BP 算法的最大弱点是局部极

小问题和无法学习网络拓扑结构。GA 应用于 ANN 的学习可以分为三个方面：连接权重、拓扑

结构以及网络学习规划。目前，GA 已广泛应用与 BP 网络、RBF 网络、ANN 网络和 Kohonen

http://www.ma-xy.com 5 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

特征映射等等。Holland 最初设计 GA 的目的是在自适应学习统计中设计一种有效的搜索机制，

遗传算法用于机器学习系统仍是目前 GA 应用上十分活跃的领域。这一方面最著名的例子就是

所谓的分类系统，它是遗传算法与机器学习中经典的生产系统相结合的产物，并成功应用于石油

管道设计和视觉系统的控制等。

1.2.2 GA 的算法步骤

基本定义

定义 (个体) 如果就最优化问题而言，个体指 x ∈ R

，也即为优化问题的解。当然，有些个

体 (解) 在约束内，我们称这样的个体为许可个体或可行个体，否则称为不许可个体

。例：就引

例 (1.1) 而言，个体为 x = (x

, x

)，记个体长度为 n(n = 2)。

定义 (染色体) 我们将个体进行一定的编码，编码后的个体称为染色体。例：对 x = (x

, x

)，

我们可以对

∈

(

= 1

，设计编码长度为

，则编码后的染色体长度为

。

定义 (基因) 染色体中每一分量的特征，如各分量的值。

定义 (种群) 多个个体的集合，记为 X。如果设种群大小为 N ，则 X 为 N × n 矩阵



。

定义 (适应度) 个体对环境 (要求的目标函数) 或者规划问题 (整体) 的适应度，适应度越大，

说明个体越好。由于我们一般要求最小化，所以适应度往往取目标函数的倒数或负。对于新个体

的产生，我们可以通过改变个体的基因来形成新个体。而且，我们又要求新个体是优的，这与达

尔文的“适者生存，优胜劣汰”的思想相吻合。

下面，我们给出生物进化论的基本过程：

图 1.1: 生物进化示意图

从上图 (1.1) 中，可以看出，如果我们先给定一个初始种群要生产新个体 (子群) 而需要婚配，而

子群则继承了父母双方的优良血统。那么，我们可以选择同一种群中的 2 个适应度高的个体进行

基因交叉，以形成子群。

例：选择适应度大的多个个体，两两配对，进行基因交叉以生成新个体，多个新个体称为子

群。子个体的产生如图 (1.2) 所示

图 1.2: 子个体产生示意图

注：1. 我们允许个体在约束外；2. 如何设计约束。



考虑：1. 如何生成新解 (新个体)？2. 如何说明新个体是优的，或者如何生产优良的新个体？

http://www.ma-xy.com 6 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

当然，对于基因交叉，会有各种各样的方法。根据基因编码的不同，我们会有浮点数编码和

二进制编码。我们可以选择以下交叉方法：

1. 适用于浮点数的交叉方法：离散重组、中间重组、线性重组等。

2. 适用于二进制编码的交叉方法：单点交叉、多点交叉、均匀交叉、洗牌交叉、缩小代理交叉

等。

但新群体的产生不仅仅是婚配后形成子群，而且还在子群的基础上进行了一定的基因变异操

作。基因突变是易于处理的，我们可以在生成的子群中选择某些个体进行基因突变，以形成群体。

这样，较优良的个体也就产生了。

产生新个体之后，我们要想办法把新个体混合到原种群，以形成新的种群。然后再在新的种

群上重复上述过程。对于如何将新个体混合到原种群中，有很多方法，可自行思考。我们一般要

求混合后的新种群大小仍为 N ，这样便于处理。

基本流程

我们将上述过程归纳为以下流程：

step1. 初始化：初始种群及参数。

step2. 选择：选择种群中的个体，以便进行交叉。

step3. 交叉：交叉以产生新个体，子种群。

step4. 变异：对种群中的个体进行基因突变。

step5. 形成新种群 (重组)：突变后的子种群与原种群进行竞争以生成新种群。

step6. 终止条件；不终止则返回 step2。

值得一提的是，交叉变异是在个体的染色体 (即编码后的个体) 上进行的。选择、重组是就

个体而言。所以，我们要先将原种群计算适应度，然后进行选择。在编码的基础上进行交叉，变

异。然后解码形成子种群，子种群与原种群重组以形成新种群。

上述 GA 算法是基本的遗传算法，只有选择、交叉、变异三个算子。当然，由于编码方式、

选择方法、交叉方法、变异方法、重组方法的不同，又会派生出许多不同的算法。并且，如果我

们不仅限于选择、交叉、变异三个算子，再设计其它算子，就形成了新的遗传框架。

下面，我们将简单介绍一些 GA 的实现方法：如何编码、解码、选择、交叉变异，然后再介

绍一些改进的遗传算法 (框架的改进)。最终，我们将讨论一些实际的问题：例如约束条件的处理、

整数变量的处理、多目标的处理等。

基本实现

编码方法编码是应用遗传算法时首要解决的问题，它决定了交叉变异等基因位操作的难易。同

时，也决定了编码方式。De Jong 曾提出了以下两种编码原则：¬在使用易于产生与所求问题相

关的且具有低阶、短定义长度模式的编码方案；应使用能使问题得到自然表示或描述的具有最

小编码字符的编码方案。De Jong 仅仅给出了一个指导性的大纲。当然，针对具体问题我们要具

体分析。

http://www.ma-xy.com 7 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

1) 二进制编码方法

二进制编码方法是常用的编码方法。编码后的二进制染色体长度与问题的求解精度有关。假

设某一参数 x 的取值范围是 x

min

⩽ x ⩽ x

max

，用长度为 l 的二进制编码该参数 (优化变量、决

策变量)，则它共能产生 2

种不同的组合，其对应关系如表 (1.1) 所示

表 1.1: 二进制编码

自变量二进制十进制实际值

000001010100101001 5417 -2.687969

101111011111110 24318 5.361653

则二进制编码的精度为

δ =

max

− x

min

− 1

假设一个参数 x 的编码为

x = b

l−1

···b

则对应的解码公式为：

x = x

min





i=1

· 2

i−1



max

− x

min

− 1

注：个体 X = (x

, x

)，其中 x

, x

称为参数。

二进制的编码、解码易于操作，交叉和变异操作易于实现，且符合 De Jong 编码原则。但二

进制编码不利于反应问题的特征。为此，产生了格雷码。

2) 格雷码 (Gray Code)

格雷码是连续的两个整数所对应的编码值之间仅有一个码位不同，其余码位值完全相同。例

如：0 编码为 0000，1 编码 0001 等等。

假设有一参数的格雷码编码为：

x = g

m−1

···g

其二进制编码为

x = b

m−1

···b

由二进制编码到格雷码的转换公式为







= b

i+1

⊕ b

i = m −1, m − 2, ··· , 1

由格雷码到二进制码的转换公式为







= g

= b

i+1

⊕ g

i = m −1, m − 2, ··· , 1

http://www.ma-xy.com 8 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

其中：⊕ 表示异或运算符。

格雷码的一个特点是：任意两个整数的差是这两个整数所对应的格雷码之间的海明距离，并

且格雷码有助于加强 GA 的局部搜索能力，亦符合 De Jong 编码原则。

3) 浮点数编码

如果个体长度 (优化变量 x 的维度) 较长：X = (x

, x

, ··· , x

)，使用二进制编码会使染色

体长度过长，会增大操作量 (交叉变异)。对于这一类问题，我们有时直接使用其参数值作为编码

值，所以浮点数编码亦称为真值编码。它适用于优化变量较多，精度要求高的优化问题，便于与

经典优化方法结合，并且便于处理复杂约束条件。

4) 级联编码

我们可以将一个个体中的不同参数 (变量)x

, x

用不同的编码方式进行编码，之后再组和拼

接起来。一定要注意，在交叉变异操作过后解码的拼接。如果编码之后就拼接，则不利于交叉、

变异操作。假设其 n 个优化变量 (参数)，每个参数的编码长度为 l

(i = 1, 2, . . . , n)，则染色体长

度为 l =



i=1

。在对种群进行编码后，我们要进行选择、交叉变异等操作。

选择选择操作并不是在编码后的染色体上进行的，而是在原参数上根据个体的适应度进行的。

一般而言，种群中的适应度越大的个体越容易被选择。

¬比例选择 (轮盘赌选择)：比例选择是一种有放回的随机选择，设种群大小为 M ，个体 i 的

适应度为 F

，则个体 i 被选中的概率 P

为：

= F





i=1

随机选择；®截断选择；¯排序选择；

°最有保存策略：当前种群中适应度最高的个体不参与交叉变异运算，而是用它来替换子种

群中适应度较优的个体。

±随机联赛选择：其基本思想是每次选取几个个体之中适应度最高的一个个体。其中，每次

进行适应度比较的个体数目称为联赛规模 N 。即从种群中随机选取 N 个个体，比较适应度，选

取适应度最大的个体，将上述过程重复多次。

交叉

在选择一定的个体之后，我们要利用这些个体产生新的个体。我们通过交叉变异操作来

再生成新个体 (子代)。交叉操作是通过变换两个个体的基因来形成新个体的。那么，我们自然要

考虑：¬在哪个交叉点进行交换；交换多长的基因段。根据编码的方式不同，我们会有不同的

基因交叉方法:

¬针对浮点数编码

父 2.3 4.5 6.7

母 2.8 4.6 1.5

注：要在个体中以交叉概率 P

选择部分个体进行交叉操作。

http://www.ma-xy.com 9 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

我们可以从父母的共 6 个基因中随机等概率挑选 3 个基因组成新的个体。也可以应用一定的公

式进行组合，如：子个体 = 父 +α (父 − 母)、子 = 父 + 母等。

针对二进制编码

父 000010101

母 001010010

单点交叉：随机选取一个交叉点，然后在此变换父母的基因。例如在上面的第 3 个位置，有子代

为 000010010 和 001010101 两个子代 (当然可以省略去一个)。由单点交叉，我们可以很容易推

广到多点交叉，常用的多点交叉是两点交叉方法。

变异在 GA 中，变异算子有 2 个重要作用：¬改善局部搜索能力；维持种群个体多样性，防

止收敛到局部解。变异算子通过个体基因发生突变而改变个体，因此，我们有必要思考：1. 如何

确定变异点位置；2. 如何变异。

¬基本位变异：基本位变异是指对个体编码中以变异概率 P

随机指定某一位或某几位基因

座上的值做基因突变。

边界变异：当然，对于浮点数编码，我们可以使变异基因组变为该参数的边界值。当然，我

们也可以用一个集合的某部分的随机数来替换原有的基因值。

®大变异操作：当某代中的所有个体集中在一起时 (个体距离)，我们以一个远大于通常的变

异概率，使种群中更多个体可能发生变异，以避免” 早熟”。大变异操作的具体过程为：当某一代

的最大适应度 F

max

与平均适应度 F

avg

表现为如下关系时

α · F

max

< F

avg

α ∈ [0.5, 1]

表明个体集中，我们就将通常的变异概率

变大。

下面，我们总结一下遗传算法中的参数：参数个数 n，某一参数的编码长度 l

(i = 1, 2, ··· , n)，

编码后染色体长度 l =



i=1

，种群大小 M ，个体长度，最大进化代数 T

max

，交叉概率 P

，变异

概率 P

，代沟 G。其中：代沟 G 表示各代种群之间个体重叠度的一个参数，它表示每代种群

中因子代被替换掉的个体在全部个体中所占的比率，即每一代种群中有 M ×G 个个体被替换掉，

它决定了子代的大小。

约束条件的处理上面介绍了基本遗传算法的实现，下面，我们讨论如何处理含约束规划中的约

束。对于边界约束 U

⩽ x ⩽ U

而言，在前面的编码方式中，我们已经看到了对于边界约束的处

理。对于一般的约束条件而言，如果直接采用 GA 进行求解，那么种群中的个体很有可能不在约

束范围内。对此，承继前面的罚函数思想，我们仍会将约束罚进目标函数，使得当个体逃出约束

时，其适应度极低。这样，我们就可以将不满足约束的个体淘汰掉。

min

x∈R

f(x)

s.t. h(x) = 0

g(x) ⩽ 0

http://www.ma-xy.com 10 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

构建相应的罚目标为

min f (x) + M

|h(x)| + M

max{g(x), 0}

其中：M

, M

是足够大的常数。当 h(x) = 0 时，M

项为 0；当 h(x) = 0 时，M

项足够大；当

g(x) ⩽ 0 时，M

项为 0; 当 g(x) > 0 时，M

项足够大。所以 GA 的求解目标就变为上面的罚

目标函数。

交叉概率和变异概率交叉变异操作是在选择的种群中进行的，以生成子种群 (新种群)。但交叉

和变异操作都是针对部分个体而言，即我们要在选择的种群中，选取部分进行交叉变异。选取的

概率分别为交叉概率和变异概率。交叉概率越大，新个体产生的速度越快，但如果交叉概率过大

时，会使具有高适应度的个体很快被破坏掉。对于变异概率而言，如果其取值较小，则不易于克

服” 早熟”。因此，选取适当的交叉概率和变异概率是至关重要的。一般而言，二者都是确定的，

并且是固定的。Srinvivas 等提出一种自适应遗传算法，交叉概率 P

和变异概率 P

可以自适应

确定。当种群适应度趋于一定时，二者增加；当种群适应度分散时，二者减小。其计算公式如下：











max

− F )

max

− F

avg

F ⩾ F

avg

F < F

avg











max

− F

′

)

max

− F

avg

′

⩾ F

avg

′

⩽ F

avg

其中：F

max

为种群中最大适应度，F

avg

为平均适应度，F 为要交叉的两个个体较大的适应度，F

′

为要变异个体的适应度值，k

, k

为常数。

下面，我们给出遗传算法的伪代码 (1) 以及一个具体的示例。

算法 1 遗传算法 GA

1: 初始化：M, n, l, T, P

, P

, G；t := 1。

2: 种群编码。

3: while t < T do

4: 计算种群的适应度；

5: 根据种群适应度和代沟 G 来选择交叉变异的个体序号 (子代)；

6: 交叉：在子代中，通过交叉概率 P

生成新的个体；

7: 变异：在子代中，通过变异概率 P

生成新的个体；

8: 重组 (合并)：将原种群和自带种群进行合并，并使合并后的种群大小为 M ；

9: 解码；

10: t := t + 1；

11: end while

http://www.ma-xy.com 11 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

具体示例

下面这个例子是来自《MATLAB 在数学建模中的应用》卓金武中的 GA 部分。在这个例子

中，我们会详细展示 GA 的每一步的变化，当然，如果你已经非常熟悉 GA，可以跳过这一部分。

我们用 GA 求解如下优化问题

max f(x

, x

) = 21.5 + x

sin(4πx

) + x

sin(20πx

)

s.t.







−3.0 ⩽ x

⩽ 12.1

4.1 ⩽ x

⩽ 5.8

(1) 编码：首先要进行编码工作，即将变量转换成二进制数串。数串的长度取决于所要求的

精度。例如，变量

的区间是

(

L, U

)

，要求的精度是小数点后

位，也就意味着每个变量应该被

分为至少 (L, U ) × 10

个部分。对一个变量的二进制数串位数用以下公式计算

−1

< (U, L) ×10

⩽ 2

− 1

在示例中，精度要求保留小数点后 4 位，则目标函数的两个自变量 x

, x

所构成的染色体数

串可以表示如下











− 3.0 ⩽ x

⩽ 12.1

[12.1 − (−3.0)] × 10

= 151000

−1

< 151000 ⩽ 2

− 1

= 18

4.1 ⩽ x

⩽ 5.8

(5.8 − 4.1) × 10

= 17000

−1

< 170000 ⩽ 2

− 1

= 15

m = m

+ m

= 18 + 15 + 33

本例中任一染色体数串都是 33 位，即 000001010100101001101111011111110。以上编码前

18 位表示 x

，后 15 位表示 x

，如表 (

1.2) 所示

表 1.2: 染色体编码

自变量二进制十进制实际值

000001010100101001 5417 -2.687969

101111011111110 24318 5.361653

则二进制转化十进制位

= −3.0 + 5417 ×

12.1 − (−3.0)

− 1

= −2.687969

= 4.1 + 24318 ×

5, 8 − 4.1

= 5.361653

http://www.ma-xy.com 12 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

假设初始种群中有 10 个个体，其染色体可随机生成，如下

= [000001010100101001 101111011111110]

= [001110101110011000 000010101001000]

= [111000111000001000 010101001000110]

= [100110110100101101 000000010111001]

= [000010111101100010 001110001101000]

= [111110101011011000 000010110011001]

= [110100010111110001 001100111011101]

= [001011010100001100 010110011001100]

= [111110001011101100 011101000111101]

= [111101001110101010 000010101101010]

相对应的十进制的实际值 [x

, x

] 为

= [−2.687969, 5.361653] U

= [0.474101, 4.170144]

= [10.419457, 4.661461] U

= [6.159951, 4.109598]

= [−2.301286, 4.477282] U

= [11.788084, 4.174346]

= [9.342067, 5.121702] U

= [−0.330256, 4.694977]

= [11.671267, 4.873501] U

= [11.446273, 4.171908]

(2) 评价个体适应度：对一个染色体数串的适应度的评价由下列三个步骤组成

1. 将染色体数串进行反编码 (解码)，转换成真实值，即 x

= (x

, x

), k = 1, 2, . . . ；

2. 评价目标函数 f (x

)；

3. 将目标函数值转化为适应度。对于极大值问题，适应度可作为目标函数值 eval(U

) = f (x

)。

在遗传算法中，评价函数扮演自然进化中环境的角色，它通过染色体的适应度对其进行评价。

http://www.ma-xy.com 13 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

上述染色体的适应度值如下：

eval(U

) = f (−2.687969, 5.361653) = 19.805119

eval(U

) = f (0.474101, 4.170144) = 17.370896

eval(U

) = f (10.419457, 4.661461) = 9.590546

eval(U

) = f (6.159951, 4.109598) = 29.406122

eval(U

) = f (−2.301286, 4.477282) = 15.686091

eval(U

) = f (11.788084, 4.174346) = 11.900541

eval(U

) = f (9.342067, 5.121702) = 17.958717

eval(U

) = f (−0.330256, 4.694977) = 19.763190

eval(U

) = f (11.671267, 4.873501) = 26.401669

eval(U

) = f (11.446273, 4.171908) = 10.252480

依照染色体的适应度值进行新种群的复制，步骤如下

¬计算染色体 U

的适应度值

eval(U

) = f (x

), k = 1, 2 . . .

计算种群的适应度值总和

F =

pop

size



k=1

eval(U

)

®计算每个染色体被复制的概率

eval(U

)

¯计算每个染色体被复制的累计概率



j=1

(3) 新种群复制：依照轮盘选择法，转动轮盘 10 次（种群中有 10 条染色体），每次选择一

个作为新种群的染色体。假设 10 次中产生的 0 ∼ 1 随机数序列如下：

0.301431 0.322062 0.766503 0.881893 0.350871

0.538392 0.177618 0.343242 0.032685 0.197577

根据以上的计算方法，可以先计算出种群中每个染色体的适应度和概率，如表 (1.3) 所示

http://www.ma-xy.com 14 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

表 1.3: 种群每条染色体的适应度、被复制概率和被复制的累积概率

染色体适应度值 P

19.805119 0.111180 0.111180

17.370896 0.097515 0.208695

9.590546 0.053839 0.262534

29.406122 0.165077 0.427611

15.686091 0.088057 0.515668

11.900541 0.066806 0.582475

17.958717 0.100815 0.683290

19.763190 0.110945 0.794234

17.370896 0.097515 0.942446

10.252480 0.057554 1.000000

利用计算机模拟轮盘选择法，假设计算机产生 10 个 [0, 1] 区间的随机数列如下：第 1 个随

机数为 0.301431，大于 Q

小于 Q

，所以 U

被选中；第 2 个随机数为 0.322062，大于 Q

小于

，所以 U

再次被选中；第 3 个随机数位 0.766503，大于 Q

小于 Q

，所以 U

被选中；.....

第 10 个随机数为 0.197577，大于 Q

小于 Q

，所以 U

被选中；

依照轮盘选择法，新种群的染色体组成如下

= [100110110100101101 000000010111001](U

)

= [100110110100101101 000000010111001](U

)

= [001011010100001100 010110011001100](U

)

= [111110001011101100 011101000111101](U

)

= [100110110100101101 000000010111001](U

)

= [110100010111110001 001100111011101](U

)

= [001110101110011000 000010101001000](U

)

= [100110110100101101 000000010111001](U

)

= [000001010100101001 101111011111110](U

)

= [001110101110011000 000010101001000](U

)

这种轮盘选择法的机理是；染色体的适应度大，意味着 [Q

, Q

k+1

] 区间跨度就大，随机数发

生器产生的均匀随机数就会有更大的概率落在较大长度的 [Q

, Q

k+1

] 区间里，这样具有较大 P

值的染色体自然更有机会复制到下一代。

(4) 新种群交配

¬交配染色体数量的确定：交配染色体的数量等于染色体总量乘以交配概率，这里假设交配

概率 P

为 0.25，染色体总量为 10 条，所以参加交配的染色体数量为 [2.5] 条。符号 [] 表示取整，

这里取整数 2，即交配的染色体数目为 2 条。

http://www.ma-xy.com 15 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

交配染色体对向的确定：用计算机产生 [0, 1] 区间的 10 个随机数如下

0.625721 0.266823 0.288644 0.295114 0.163274

0.567461 0.085940 0.392865 0.770714 0.548656

假设其分别对应 U

∼ U

这 10 个个体，则其中低于交配概率 0.25 的 U

和 U

参加交配。这样

操作的原因是：交配率越低，低于交配率的随机数的数量就较少，所以参加交配的染色体数量与

交配概率可能会成正比。

®在交配池发生交配

染色体 U

和 U

被选中作为交配的父辈，交配点的选择以随机数产生。交配的种类有单点

交配和多点交配，这里取单点交配。计算机随机生成一个介于 0 ∼ 32 的整数 (因为整个染色体

数串的长度为 33)。假设所产生的整数为 1，那么两个染色体自 1 位置 (即二进制串的第二位) 开

始分割，在染色体 1 位置右端部分进行交换而生成新的子悲染色体，即

= [1 0011 0110 1001 0110 1000 0000 1011 1001]

= [0 0111 0101 1100 1100 0000 0101 0100 1000]

⇓

∗

= [1 0111 0101 1100 1100 0000 0101 0100 1000]

∗

= [0 0011 0110 1001 0110 1000 0000 1011 1001]

(5) 基因突变

依照突变运算规则并假设突变几率 P

为 0.01，亦即种群内所有基因都有 0.01 的概率进行

突变。在本例中共有

10 = 330

个基因，即希望每一代中有

3.3

个突变基因，每个基因的突

变几率是均等的。因此，将产生 330 个介于 0 ∼ 1 之间的随机数 (需编号)，然后将该随机数小

于 0.01 者选出，并将其对应的基因值加以翻转。假设 330 次中产生 0 ∼ 1 之间的随机数，其值

小于 0.01 者如表 (1.4) 所示

表 1.4: 基因突变位置

基因位置染色体位置基因位数随机数

105 ÷ 33 = 4 ···6 4 6 0.009857

164 ÷ 33 = 5 ···32 5 32 0.003113

199 ÷ 33 = 7 ···1 7 1 0.000946

329 ÷ 33 = 10 ···32 10 32 0.001282

表 (1.4) 第 1 列显示的是具体在哪些染色体以及在染色体的什么位置进行突变。例如第 1 行

105 ÷ 33 = 4 ···6 表示的是在第 4 条染色体第 6 个基因上发生了突变，因为第 4 条染色体第 6

http://www.ma-xy.com 16 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

个基因对应得基因标号是 33 ×(4 − 1) + 6 = 105。在突变后，最终新种群的染色体组成如下

= [100110110100101101 000000010111001]

= [001011010100001100 010110011001100]

= [111111001011101100 011101000111101]

= [100110110100101101 000010010111001]

= [110100010111110001 001100111011101]

= [101110101110011000 000010101001000]

= [100110110100101101 000000010111001]

= [000001010100101001 101111011111110]

= [001110101110011000 000010101001010]

新一代的相对应实际值 [x

, x

] 和适应度值如下

eval(U

) = f (6.159951, 4.109598) = 29.406122

eval(U

) = f (6.159951, 4.109598) = 29.406122

eval(U

) = f (−0.330256, 4.694977) = 19.763190

eval(U

) = f (11.907206, 4.873501) = 5.702781

eval(U

) = f (8.024130, 4.170248) = 19.910251

eval(U

) = f (9.342067, 5.117020) = 17.958717

eval(U

) = f (6.159951, 4.109598) = 29.40122

eval(U

) = f (6.159951, 4.109598) = 29.40122

eval(U

) = f (−2.687969, 5.361653) = 19.805119

eval(U

) = f (0.474101, 4.170248) = 17.370896

至此，已完成遗传算法的第一代流程。依此迭代，在第 451 代得到对应的最大目标函数值的

染色体

best

= [111110000000111000 11101001010110]

相应实际值 [x

, x

] = [11.631407, 5.724824]，适应度值 eval(U ) = f(11.631407, 5.724824) =

38.818208。

从以上实例可以得出两点结论：¬遗传算法本质上是一种启发式的随机搜索算法，所以由遗

传算法得出的结果每次都不尽相同。自变量在给定的约束条件下进行了无缝编码 (即这种编码

方法能够表达解空间中的所有可行解)，所以从理论上讲，遗传算法总有很多机会得到全局最优

结果而不是局部最优结果。

http://www.ma-xy.com 17 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

1.2.3 遗传框架的改进

前面所提到的遗传框架都是选择、交叉和变异三个算子来形成的个体 (新的解)。不同的只是

方法而已。下面，我们来试着改进一下遗传框架。

分层遗传算法

对于一个问题，首先随机的生成 N × n 个样本 (N ⩾ 2, n ⩾ 2)，然后将它们分成 N 个子种

群，每个子种群包含 n 个样本，对每个子种群独立的运行各自的遗传算法，记它们为 GA

(i =

1, 2, . . . , N)。这 N 个遗传算法最好在设置特性上有较大的差异，这样就可以为将来的高层遗传

算法产生更多种类的优良模式。

在每个子种群的遗传算法运行到一定代数后，将 N 个遗传算法的结果记录到二维数组

R[1 ···N, 1 ···n] 中，则 R[i, j](i = 1 ···N, j = 1 ···n) 表示 GA

的结果种群的第 j 个个体。

同时，将 N 个结果种群的平均适应度记录到数组 A[1 ···N ] 中，A[i] 表示 GA

的结果种群平均

适应度值。

上述改进的遗传算法称为分层遗传算法 (hierarchic Genetic Algorithm, HGA)。N 个低层遗

传算法中的每一个在经过一段时间后均可以获得位于个体串上的一些特定位置的优良模式。

CHC 算法

CHC 算法是 Eshelman 于 1991 年提出的一种改进的遗传算法的缩写，第一个 C 代表跨

世代精英选择 (Cross generational elitist selection) 策略，H 代表异物种重组 (Heterogeneous

recombination)，第二个 C 代表大变异 (Cataclysmic mutation)。CHC 算法与基本遗传算法 SGA

不同点在于：SGA 的遗传操作比较简单，简单地实现并行处理，而 CHC 算法牺牲这种简单性，

换取更好的遗传效果，并强调优良个体的保留。下面分别介绍其改进之处：(1) 选择：在 CHC 算

法中，上世代种群与通过新的交叉方法产生的个体混合起来，从中按一定概率选择较优的个体。

这一策略称为跨世代精英选择。(2) 交叉：CHC 算法使用重组操作是对均匀交叉的一种改进。均

匀交叉对服个体位值得各位位置以相同的概率进行交叉操作，这里改进之处是：当两个父个体位

值相异的位数为 m 时，从中随机选择 m/2 个位置，实行父个体位值的互换。显然，这样的操作

对模式具有很强的破坏性，因此，确定一阀值，当个体间的海明距离低于该阀值时，不进行交叉

操作，在种群进化收敛的同时，逐渐减小阀值。(3) 变异：CHC 算法在进化前期不采取变异操作，

当种群进化到一定的代数时，从优秀个体中选择一部分个体进行初始化。初始化的方法是选择一

定比例的基因座，随机地决定它们的位值。这个比例值称为扩散率，一般取 0.5。

messy GA

在生物进化过程中，染色体的长度并不是固定不变的。另一方面，在遗传算法的实际应用中，

有时为简化描述问题的解，也需要使用不同长度的编码串。例如，用遗传算法对神经网络进行优

化设计时，如果各层的节点数目是未知的，则个体染色体长度是变化的。

messy GA 将常规的遗传算法的染色体编码串中各基因座位置及相应的基因值组成一个二元

组，把这个二元组按一定顺序排列起来，就组成一个变长度染色体的一种编码方式。一般的它可

http://www.ma-xy.com 18 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

以表示为

: (i

, v

)(i

, v

) ···(i

, v

) ···(i

, v

)

上述变长度染色体描述形式中，i

是所描述的基因在原常规染色体中的基因座编号，v

为对应

的基因值。对于所需要求解的问题，若使用常规遗传算法时的染色体长度固定为 l，个体基因值

取自集合 V ，则有

1 ⩽ i

⩽ l (k = 1, 2, . . . , n)

∈ V (k = 1, 2, . . . , n)

小生境遗传算法

生物学上，小生境

(niche)

是指特定环境中的一种组织功能。在自然界中，往往特征相似的

物种相聚在一起，并在同类中交配繁衍后代。在 SGA 中，交配完全是随机的，虽然这种随机化

的杂交形式在寻优的初级阶段保持了解的多样性，但在进化的后期，大量个体集中于某一极值点

上，它们的后代造成了近亲繁殖。在遗传算法求解多峰极值函数的优化计算时，经常陷入局部极

值。

De Jong 在 1975 年提出了基于排挤机制的选择策略，其基本思想源于在一个有限的生存空

间中，各种不同的生物为了能够延续生存，它们之间必须相互竞争各种有限的生存资源。因此，

在算法中设置一个排挤因子 CF (一般取值 2 或 3)，由群体中随机地选取得 1/CF 个个体组成排

挤成员，然后依据新产生的个体与排挤成员的相似性来排挤一些与排挤成员相似的个体，个体之

间的相似性可用个体编码串之间的海明距离度量。随着排挤过程的进行，群体中的个体逐渐被分

类，从而形成一个个的小生存环境，并维持了群体的多样性。

共享法的选择策略是 Goldberg 等于 1987 年提出的。其基本做法是通过个体之家的相似程

度的共享函数来调整群体中各个个体的适应度，从而在群体的进化过程中，算法能够依据这个

调整后的新适应度来进行选择操作，以维护群体的多样性，创造出小生境的进化环境。共享函数

(sharing function) 是表示群体中两个个体之间密切关系程度的一个函数，可以记为 S(d

)，其中

表示个体 i 与个体 j 之间的某种关系。例如，个体基因型之间的海明距离就可以定义为一种

共享函数。这里个体之间的密切程度主要体现在个体基因型的相似性或者个体表现型之间的相似

性上。当个体之间比较相似时，其共享函数值就比较大，反之，当个体之间不大相似时，其共享

函数就比较小。

适应度共享函数的直接目的是将搜索空间的多个不同峰值在地理上区分开来，每一个峰值处

接受一定笔记数目的个体，比例大小与峰值高度有关。为了实现这样的分布，共享法将个体的目

标适应度降低，即适应度值 f

除以一个 niche 技术 m

获得共享函数，niche 计数 m

作为个体

邻集密集程度的估计



j∈P op

Sh[d

]

其中：d

是个体 i 和 j 的距离，Sh[d] 是共享函数，它是一个递减函数，Sh[0] = 1 和 Sh[d ⩾

http://www.ma-xy.com 19 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

] = 0。下面是一个典型的三角共享函数

Sh(d) =











1 −

, d ⩽ σ

0, d > σ

这里 σ

是 niche 半径 r，由使用者自己给定，它是较好峰值之间个体的最小距离。在距离为

的范围内的个体彼此消减适应度。因为这些个体 niche 大小相同，因此收敛在一个 niche

内，避免了整个种群的收敛。当一个 niche 添满时，其 niche 计数增大，是共享函数低于其他的

niche。Goldberg 和 Richardson(1987) 指出，当所有 niche 的共享函数相等时，就达到一种平衡

状态

i, j为 niche 序号

适应度函数共享或多或少独立于使用的选择方法。当共享法与比较流行的竞争选择法结合起来，

这种遗传算法就会出现混沌现象 (Goldberg,1991)。Goldberg 建议将连续变化的共享法语竞争选

择法结合起来，niche 计数的计算采用当前种群，而不是采用部分添满的下世代种群。

为了定义一个 niche，我们采用一种将海明距离测度 (基因型差异) 与适应度距离 (表现型差

异) 相结合的方法。若 d

, x

) 为任意两个个体 x

, x

的海明距离，d

, x

) 是适应度距离，这

是共享函数可以定义为

S(x

) =











1 −

, x

)

, d

, x

) < σ

, d

, x

) ⩾ σ

1 −

, x

)

, d

, x

) ⩾ σ

, d

, x

) < σ

1 −

, x

)

, d

, x

) < σ

, d

, x

) < σ

0, 其它

这里 σ

, σ

是 niche 半径，即分别为基因型和表现型的作为一个 niche 内个体的最大距离。个体

的适应度函数在共享后变为如下形式

′

) =

f(x

)



j=1

s(x

, x

)

混合遗传算法

我们知道，梯度法、爬山法、模拟退火法等优化算法具有较强的局部搜索能力，而 GA 等启

发式算法有较强的全局搜索能力和运行效率。将二者结合，我们称结合后的算法为混合算法，特

别地，如果是和遗传算法结合，则称为混合遗传算法。

1.2.4 GA 工具箱介绍

GA 工具箱有许多，下面，我们主要介绍 gatbx 和 GADST。

http://www.ma-xy.com 20 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

gatbx

首先，我们来介绍谢菲尔德大学研发的遗传工具箱 gatbx。《MATLAB 遗传工具箱及应用》(雷

英杰) 一书详细介绍了这个工具箱 (但此工具箱并不是我们首推的工具，虽然把它放在 MATLAB

自带的工具箱之前)。下面，我们主要介绍 gatbx 的安装、函数和示例:

1 %安装：将 gatbx 解压到 s t r 后再运行下面的命令

2 s t r =[matlabroot , ’ \toolbox \gatbx ’ ] ;

3 addpath( s t r )

4 %测试

5 ver ( ’ gatbx ’ )

gatbx 工具箱的主要函数如表 (1.5) 所示

http://www.ma-xy.com 21 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

表 1.5: gatbx 工具箱的主要函数

函数分类函数功能

创建种群

crtbase 创建基向量

crtbp 创建任意离散随机种群

crtrp 创建实值初始种群

适应度计算

ranking 基于排序的适应度分配

scaling 比率适应度计算

选择函数

reins

一致随机和基于适应度的重

插入

rws 轮盘选择

select 高级选择例程

sus 随机遍历采样

交叉算子

recdis 离散重组

recint 中间重组

recline 线性重组

recmut 具有变异特征的线性重组

recombin 高级重组算子

xovdp 两点交叉算子

xovdprs 减少代理的两点交叉

xovmp 通常多点交叉

xovsh 洗牌交叉

xovshrs 减少代理的洗牌交叉

xovsp 单点交叉

xovsprs 减少代理的单点交叉

变异算子

mut 离散变异

mutate 高级变异函数

mutbga 实值变异

子种群的支持 migrate 在子种群间交换个体

实用函数

bs2rv 二进制串到实值的转换

rep 矩阵的复制

testfns 文件夹下的测试函数如表 (1.6) 所示

http://www.ma-xy.com 22 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

表 1.6: gatbx 测试函数说明

序号 M 文件名说明

1 objfun1 De Jong’s 函数 1

2 objfun1a axis parallel hyper-ellipsoid(轴并行超球体)

3 objfun1b rotated hyper-ellipsoid(旋转超球体)

4 objfun2 Rosenbrock’s valley(banana function)

5 objfun6 Rastrigin’s function

6 objfun7 Schwefel’s function

7 objfun8 Griewangk’s function

8 objfun9 sum of dierent powers(不同权的总和)

9 objdopi double integrator(双积分)

10 objharv harvest problem(收获问题)

11 objlinq discrete linear-quadratic problem(离散二次线性问题)

12 objlinq2 continuous linear-quadratic problem(连续二次线性问题)

13 objpush push-cart problem(装载问题)

gatbx 的一个应用实例：我们来 gatbx 来求前面的引例 1(1.1)，求解程序如下

1 %% 用 gatbx 工具箱求解 “ 智能优化 ” 章节的引例

2 % max f (x , y )=y* s in (2* pi *x)+x* cos (2* pi *y)

3 % s . t.−0.5<=x<=3.5; −2<=y<=3;

4 c l c , c l e a r

5 %% 画出函数图

6 f i g u r e (1 ) ;

7 lbx = −0.5;ubx = 3 . 5 ;

8 lby = −2;uby = 3 ;

9 ezmesh ( ’ y* s i n (2* pi *x)+x*cos (2* p i *y) ’ , [ lbx , ubx , lby , uby ] , 5 0 ) ; % 画出函数曲线

10 hold on ;

11 %% 定义遗传算法参数

12 NIND = 4 0 ; % 个体数目

13 MAXGEN =50; % 最大遗传代数

14 PRECI = 2 0; % 变量的二进制位数

15 GGAP = 0. 9 5 ; % 代沟

16 px = 0 . 7 ; % 交叉概率

17 pm = 0 . 0 1 ; % 变异概率

18 t rac e = z e ros (3 ,MAXGEN) ; % 寻优结果的初始值

19 FieldD = [PRECI PRECI; lbx lby ; ubx uby ; 1 1 ; 0 0;1 1 ; 1 1 ] ; % 区域描述器

20 Chrom=crtbp (NIND,PRECI*2) ; % 初始种群

21 %% 优化

22 gen = 0; % 代计数器

23 XY = bs2rv (Chrom, FieldD ) ; % 计算初始种群的十进制转换

24 X = XY( : , 1 ) ;Y = XY( : ,2 ) ;

25 ObjV = Y.* s i n (2* pi *X)+X. * c os (2* pi *Y) ; % 计算目标函数值

26 while gen < MAXGEN

27 FitnV = ranking(−ObjV) ; % 按照目标函数值ObjV从小到大的顺序对个体进行排序，并返回个

体的适应度列向量

28 SelCh = s e l e c t ( ’ sus ’ , Chrom, FitnV , GGAP) ; % 选择

http://www.ma-xy.com 23 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

29 SelCh = recombin ( ’ xovsp ’ , SelCh , px) ; % 重组

30 SelCh = mut( SelCh , pm) ; % 变异

31 XY = bs2rv ( SelCh , FieldD ) ; % 子代个体的十进制转换

32 X=XY(: , 1 ) ; Y=XY(: , 2 ) ;

33 ObjVSel = Y.* s in (2* pi *X)+X.* cos (2* pi *Y) ; % 计算子代的目标函数值

34 [ Chrom , ObjV] = r e i n s (Chrom , SelCh , 1 , 1 , ObjV , ObjVSel) ; % 重插入子代到父代，得到

新种群

35 XY = bs2rv (Chrom, FieldD ) ;

36 gen = gen + 1; % 代计数器增加

37 % 获取每代的最优解及其序号，Y为最优解 , I 为个体的序号

38 [Y, I ] = max(ObjV) ;

39 tr a c e ( 1 : 2 , gen) = XY( I , : ) ; % 记下每代的最优值

40 tr a c e ( 3 , gen ) = Y; % 记下每代的最优值

41 end

42 plot3 ( tr a c e ( 1 ,: ) , tra c e ( 2 ,: ) , tra c e ( 3 ,: ) , ’ bo ’ ) ; % 画出每代的最优点

43 g r id on ;

44 plot3 (XY( : ,1 ) , XY( : ,2 ) , ObjV, ’ bo ’ ) ; % 画出最后一代的种群

45 hold o f f

46 %% 画进化图

47 f i g u r e (2 ) ;

48 p l ot (1 : MAXGEN, t r ace ( 3 ,: ) ) ;

49 g r id on

50 x l a be l ( ’ 遗传代数 ’ ) y l ab e l ( ’ 解的变化 ’ ) t i t l e ( ’ 进化过程 ’ )

51 bestZ = trac e ( 3 , end ) ; bestX = trac e ( 1 , end ) ; bestY = tra c e ( 2 , end ) ;

52 f p r i n t f ( [ ’ 最优解 : \nX=’ , num2str ( bestX ) , ’ \nY=’ , num2str ( bestY ) , ’ \nZ=’ , num2str ( bestZ ) , ’ \n

’ ] )

matlab 自带的 GA 工具箱 GADST

MATLAB 用 ga 函数来实现 ga 算法，其调用格式为

[x,fval,exitag,output,population,scores]=ga(tness,nvar,A,b,Aeq,beq,lb,ub,nonlcon,Intcon,

options) 其中：Intcon 为标明了整数变量；Population 为最终的种群；scores 为最终种群的适应

度。

GADST 可以创建均匀、可行的初始种群。可选择的适应度尺度变换有：基于等级、比例、裁

断、移位线性。采用的选择方法：轮盘赌、随机均匀 (sus)、锦标赛、均匀、余数。采用的交叉方

法有：算术、启发式、中间、分散、单点、两点；采用的变异方式有：自适应可行、高斯、均匀；

可以绘制的图形有：最佳适应度、最佳个体、个体间距、群体多样性、个体预期、最大约束、范

围、选择指数、停止条件。

Global Optimization Toolbox 还可以指定参数：种群大小，优良子辈数量，交叉片段，子群

体迁移；优化问题的边界、线性、非线性约束。同时，还支持整数规划、混合整数规划、分类型

数据和复数。可将适应度函数向量化以提高效率，并且支持并行计算目标函数和约束函数。

用 ga 函数求解引例 1(1.1)，求解程序如下

1 %% matlab 自带的GA求解 “ 智能优化引例 ”

2 % max f (x , y )=y* s in (2* pi *x)+x* cos (2* pi *y)

3 % s . t.−0.5<=x<=3.5; −2<=y<=3;

http://www.ma-xy.com 24 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

4 c l c , c l e a r

5 f i t n e s s f c n = @(x) −(x( 1 ) * cos (2* pi *x( 2 ) ) + x(2) * s i n (2* pi *x (1) ) ) ; % 适应度函数句

柄

6 nvars = 2; % 个体的变量数目

7 A = [ ] ; b = [ ] ;

8 Aeq = [ ] ; beq = [ ] ;

9 lb = [ −0.5 , −2];

10 ub = [ 3 . 5 , 3 ] ;

11 nonlcon = [ ] ;

12 Intcon = [ ] ;

13 options = gaoptimset ( ’ Po pulati onSiz e ’ ,100 , ’ EliteCount ’ , 1 0 , ’ Cros sove rFra ctio n ’ , 0. 7 5 , ’

Generations ’ ,500 , ’ StallGenLimit ’ ,500 , ’ TolFun ’ ,1 e −100, ’ PlotFcns ’ ,{ @gaplotbestf ,

@g aplotbest indiv }) ; % 参数设置

14 [ x_best , f v a l ] =ga ( f i t n e s s f c n , nvars ,A, b , Aeq , beq , lb , ub , nonlcon , Intcon , o p t i o ns ) ; % 调

用 ga函数

用 ga 函数求解引例 2(1.2)，求解程序如下

1 %% ga 函数的示例

2 % 1 、基本示例

3 a = 1; b = 1 ;

4 fun = @(x , a , b) −(a*x(1) * c os (2* pi *x(2 ) ) + b*x (2 ) * s in (2* pi *x(1) ) ) ;

5 pl o t o b j ec t i v e ( fun ,[−4 4; −4 4 ] ) ;

6 f i t n e s s f c n = @(x) fun (x , a , b) ;

7 nvars = 2;

8 [ x , f v a l ] = ga ( f i t n e s s f c n , nvars )

9 % 2 、向量化目标函数

10 fun = @(x , a , b) −(a*x ( : , 1 ) .* c os (2* pi *x ( : , 2 ) ) + b*x ( : , 2 ) .* s in (2* pi *x ( : , 1 ) ) ) ;

11 f i t n e s s f c n = @(x) fun (x , a , b) ;

12 options = gaoptimset ( ’ Ve ctorized ’ , ’ on ’ ) ;

13 [ x , f v a l ] = ga ( f i t n e s s f c n , nvars , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , op t ions )

14 %3 、添加边界和约束

15 % max f (x , y )=y* s in (2* pi *x)+x* cos (2* pi *y)

16 % s . t . −0.5<=x<=3.5; −2<=y<=3;

17 % (x−xcoords (1) ) . ^ 2 + ( y−ycoords (1) ) .^2 <= 9 ;

18 % (x−xcoords (2) ) . ^ 2 + ( y−ycoords (2) ) .^2 <= 9 ;

19 % (x−xcoords (3) ) . ^ 2 + ( y−ycoords (3) ) .^2 <= 9 ;

20 xcoords = [2 . 41 1 2 0.2064 1 . 6 7 8 7 ] ;

21 ycoords = [0 . 39 5 7 0.3927 0 . 9 8 7 7 ] ;

22 domain = [−3 5 . 5 −4 5 ] ;

23 % f u nction [ c , ceq ] = aperture C onstrain t ( x , xcoords , ycoords )

24 % ceq = [ ] ;

25 % c = ( x (1) − xcoords ) . ^ 2 + ( x (2 ) − ycoords ) .^2 − 9 ;

26 % end

27 FunConstraint = @(x) ap ertureCo n straint (x , xcoords , ycoords ) ;%非线性约束

28 nvars = 2;

29 LB = [ −0.5 −2];

30 UB = [ 3 . 5 3 ] ;

31 options = gaoptimset ( options , ’ MutationFcn ’ , @mutationadaptfeasible ) ;

32 options = gaoptimset ( options , ’ PlotFcns ’ ,{ @gaplotbestf , @gaplotmaxconstr ,

@gaplotstopping } , ’ Display ’ , ’ i t e r ’ ) ;

33 X0 = [ 0 . 5 0 . 5 ] ; % 提供一个初始点

34 options = gaoptimset ( options , ’ I n i t i a l P o p u l a t i o n ’ ,X0) ;

http://www.ma-xy.com 25 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

35 options = gaoptimset ( options , ’ Pop ulati onSiz e ’ ,1 0 ) ;%种群大小

36 options = gaoptimset ( options , ’ Generations ’ ,150 , ’ StallGenLimit ’ , 100) ;%停止准则

37 options = gaoptimset ( options ’ Selection Fcn ’ , @selectiontournament , . . .

38 ’ Fitne s s Scaling F c n ’ , @f i tsc a lin g pro p ) ;%设置选择、交叉、变异等方法

39 [ x , f v a l ] = ga ( f i t n e s s f c n , nvars , [ ] , [ ] , [ ] , [ ] , LB,UB, FunConstraint , [ ] , o p t i o ns )

40 % 4 、让结果一致

41 t he s ta t e = rng ;% 多次运行 ga 时，使多次的结果一致。

42 % 你可能没有意识到你会想尝试复制之前运行遗传算法的结果。在这种情况下 , 只要你有输出结构

, 你可以重置随机数发生器如下

43 strm = RandStream . getGlobalStream ;

44 strm . Stat e = Output . rng s t ate . s ta te ;

45 % 5 、混合遗传算法

46 fminuncOptions = optimoptions ( @fminunc , ’ Display ’ , ’ i t e r ’ , ’ Algorithm ’ , ’ quasi−newton ’ ) ;

47 options = gaoptimset ( options , ’ HybridFcn ’ ,{ @fminunc , fminuncOptions }) ;%Adding a Hybrid

Function

48 [ x , f v a l ] = ga ( f i t n e s s f c n , nvars , [ ] , [ ] , [ ] , [ ] , LB,UB, FunConstraint , [ ] , o p t i o ns )

49 % 6 、非光滑目标函数

50 Objfcn = @nonSmoothFcn ;

51 X0 = [ 2 −2];

52 range = [−6 6;−6 6 ] ; % Range used to p l o t the o b j e c t i v e f u n ction

53 rng (0 , ’ t w i st e r ’ ) % Reset the gl o bal random number g e n erator

54 f i g = f i g u r e ( ’ Color ’ , ’w ’ ) ;

55 [ ah , sh ] = showNonSmoothFcn( Objfcn , range ) ;

56 ah . CameraPosition = [ −36.9991 62.6267 2 07 .3 6 2 2 ] ;

57 ah . CameraTarget = [0. 1 059 −1.8145 2 2 . 3 6 6 8 ] ;

58 ah . CameraViewAngle = 6 . 09 2 4;

59 % Plot of the s t a r t i n g point ( not used by the GA s o l v e r )

60 ph = [ ] ;

61 ph(1) = plot3 (X0( 1 ) ,X0( 2 ) , Objfcn (X0) , ’ ob ’ , ’ MarkerSize ’ ,10 , ’ MarkerFaceColor ’ , ’b ’ ) ;

62 % F i l t e r out FaceColor warning

63 ws = warning ( ’ o f f ’ , ’MATLAB: legend : UnsupportedFaceColor ’ ) ;

64 oc = onCleanup (@( ) warning (ws ) ) ;

65 % Add legend to p lot

66 leg endLa bels = { ’Non−d i f f e r e n t i a b l e r egi o ns ’ , ’Smooth re g ion s ’ , ’ S t a r t poin t ’ } ;

67 lh = legend ( [ sh , ph ] , legendLabels , ’ Location ’ , ’ SouthWest ’ ) ;

68 lp = lh . P o sition ;

69 lh . Pos i t i on = [ 0 .0 05 0.005 lp (3) lp ( 4) ] ;

70 FitnessFcn = @nonSmoothFcn ;

71 numberOfVariables = 2;

72 optionsGA = gaoptimset ( ’ PlotFcns ’ , @gaplotbestfun , ’ P l ot I nt e rv a l ’ ,5 , . . .

73 ’ PopInitRange ’ ,[ −5 ; 5 ]) ;

74 [ Xga, Fga ] = ga ( FitnessFcn , numberOfVariables , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , [ ] , optionsGA)

75 f i g u r e ( f i g )

76 hold on ;

77 ph(2) = plot3 (Xga( 1 ) ,Xga(2) , Fga , ’vm ’ , ’ MarkerSize ’ ,10 , ’ MarkerFaceColor ’ , ’m’ ) ;

78 leg endLa bels = [ legendLabels , ’GA s o l u ti on ’ ] ;

79 lh = legend ( [ sh , ph ] , legendLabels , ’ Location ’ , ’ SouthWest ’ ) ;

80 lp = lh . P o sition ;

81 lh . Pos i t i on = [ 0 .0 05 0.005 lp (3) lp ( 4) ] ;

82 hold o f f ;

83 % 混合方案

84 optHybrid = gaoptimset ( optionsGA , ’ Generations ’ ,15 , ’ P lo t In t er v al ’ , 1 , . . .

85 ’ HybridFcn ’ ,{ @fminunc , optimoptions ( @fminunc , ’OutputFcn ’ , @fminuncOut ) }) ;

http://www.ma-xy.com 26 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

86 [ Xhybrid , Fhybrid ] = ga ( FitnessFcn , 2 , optHybrid ) ;

87 f i g u r e ( f i g ) ;

88 hold on ;

89 ph(3) = plot3 ( Xhybrid ( 1 ) , Xhybrid ( 2 ) , Fhybrid+1, ’ ^g ’ , ’ MarkerSize ’ ,10 , ’ MarkerFaceColor ’ ,

’ g ’ ) ;

90 leg endLa bels = [ legendLabels , ’GA−FMINUNC so lu t i o n ’ ] ;

91 lh = legend ( [ sh , ph ] , legendLabels , ’ Location ’ , ’ SouthWest ’ ) ;

92 lp = lh . P o sition ;

93 lh . Pos i t i on = [ 0 .0 05 0.005 lp (3) lp ( 4) ] ;

94 hold o f f ;

95 % 7 、优化随机目标函数

96 X0 = [ 2 . 5 −2.5]; % S tart i n g point .

97 LB = [−5 −5]; % Lower bound

98 UB = [5 5 ] ; % Upper bound

99 range = [LB(1 ) UB( 1 ) ; LB(2 ) UB(2) ] ;

100 Objfcn = @smoothFcn ; % Handle to the ob j e c t i v e fu n c t i on .

101 % Plot the smooth obj ec t i v e f unction

102 f i g = f i g u r e ( ’ Color ’ , ’w ’ ) ;

103 showSmoothFcn ( Objfcn , range ) ;

104 hold on ;

105 t i t l e ( ’Smooth o b j e c t i v e f u n ction ’ ) ;

106 ph = [ ] ;

107 ph(1) = plot3 (X0( 1 ) ,X0( 2 ) , Objfcn (X0)+30, ’ or ’ , ’ MarkerSize ’ , 1 0 , ’ MarkerFaceColor ’ , ’ r ’ ) ;

108 hold o f f ;

109 ax = gca ;

110 ax . CameraPosition = [ −31.0391 −85.2792 −281.4265];

111 ax . CameraTarget = [0 0 −50];

112 ax . CameraViewAngle = 6 .7 9 3 7;

113 % Add legend i nforma tion

114 leg endLa bels = { ’ Start poi nt ’ } ;

115 lh = legend (ph , legendLabels , ’ Location ’ , ’ SouthEast ’ ) ;

116 lp = lh . P o sition ;

117 lh . Pos i t i on = [1−l p (3 ) −0.005 0.005 lp (3) lp ( 4) ] ;

118 % 添加噪音

119 rng (0 , ’ t w i st e r ’ ) % Reset the gl o bal random number g e n erator

120 pe aknoise = 4 . 5 ;

121 Objfcn = @(x) smoothFcn(x , peaknoise ) ; % Handle to the ob je ct i v e f u n c tion .

122 % Plot the ob j e c t i v e fu n c t i on (non−smooth )

123 f i g = f i g u r e ( ’ Color ’ , ’w ’ ) ;

124 showSmoothFcn ( Objfcn , range ) ;

125 t i t l e ( ’ S t och a s tic o b j e c t i v e f u n c tion ’ )

126 ax = gca ;

127 ax . CameraPosition = [ −31.0391 −85.2792 −281.4265];

128 ax . CameraTarget = [0 0 −50];

129 ax . CameraViewAngle = 6 .7 9 3 7;

130 GAoptions = gaoptimset ( ’ Display ’ , ’ i t e r ’ ) ;

131 [ Xps , Fps ] = p a t t e r n s e a rch ( Objfcn , X0, [ ] , [ ] , [ ] , [ ] , LB,UB, GAoptions )

132 f i g u r e ( f i g ) ;

133 hold on ;

134 ph(3) = plot3 (Xps ( 1 ) ,Xps(2) ,Fps , ’ dc ’ , ’ MarkerSize ’ ,10 , ’ MarkerFaceColor ’ , ’ c ’ ) ;

135 % Add legend to p lot

136 leg endLa bels = [ legendLabels , ’GA’ ] ;

137 lh = legend (ph , legendLabels , ’ Location ’ , ’ SouthEast ’ ) ;

http://www.ma-xy.com 27 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

138 lp = lh . P o sition ;

139 lh . Pos i t i on = [1−l p (3 ) −0.005 0.005 lp (3) lp ( 4) ] ;

140 hold o f f

141

1.2.5 附：GA 算法的收敛性

下面，我们用马氏链来分析标准遗传算法 SGA 的收敛性。我们先来进行符号规定：S = {0, 1}

为个体染色体空间；S

为种群空间；Ω 为母体空间；x = (x

, x

, ··· , x

) ∈ R

为个体，它可以

经过编码函数 F 投影到 S 空间上，所以 X = (x

, x

, ··· , x

) ∈ R

∈ S。将 N 个个体 x

放在

一起形成种群，X = (x

, x

, ··· , x

) ∈ R

N×n

，如果是编码后的种群，X ∈ R

N×l

。用 X(0) 表示

初始种群，X(n) 表示第 n 代种群，用 f : S → R

−1

表示适应度函数，则标准遗传算法 SGA 可

表述为：

(1) 给出初始条件 X(0)，n = 0

(2) 对第 n 步，在 X(n) 中按以下分布独立地选择 N 个母体

P {T

(X(n)) = (Y

(k)

, Y

(k)

)}













(k)

, Y

(k)







x∈X(n)

f(x)



(k)

; Y

(k)



∈ X(n)

0 否则

其中：

= 1

, . . . , N

，

为选择算子。

(3) 对 (2) 中选择的 N 个母体进行单点随机杂交，即

P {T

, Y

) = x

(n + 1)}











/l X

′

(n + 1) = Y

(k)

且X

′

(n + 1) = AY

(k)

+ (I − A)Y

(1 − P

) +

′

(n + 1) = Y

(k)

0 否则

其中：P

为交叉概率，A 是一个对角矩阵，前 r 个对角元素为 1，其它为 0，r 为单点杂交的交

叉点。

(4) 设变异概率为 P

，通过

′

(n + 1) = (x

(n + 1), ··· , x

(n + 1))

产生

X(n + 1) = (x

(n + 1), ··· , x

(n + 1))

http://www.ma-xy.com 28 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

的概率为

P {T

′

(k)(n + 1)) = x

(n + 1)}

= P

d(x

′

(n+1),x

(n+1))

(1 − P

)

I−d(x

′

(n+1),x

(n+1))

(k ⩽ N )

若满足终止准则，则终止，否则转到 step(2)。我们记 T = T

◦ T

，则标准的遗传算法

(SGA) 表述为

X(n) = T (X(n −1)) = T

◦ T

· (X(n −1))

从 X(0) 出发，通过 SGA 可得到种群进化 {X(n)|n ⩾ 0}，称 T 为遗传算法状态转移矩阵。

X(n) 称为种群的状态，记种群的状态空间为 G ≜ S

。其中，每一个种群 X(n) 为一个状态。

定理标准遗传算法 SGA 的种群序列 {X(n)|n = 0} 是有限齐次不可约非周期的马尔科夫

链。

证明由于 S = {0, 1}

中有 2

个个体，所以种群空间 S

中有 2

个个体，S

为有限的。

由于

X(n + 1) = T (X(n)) = T

◦ T

· (X(n))

而其中的 T

, T

均与 n 无关 (因为 P

, P

皆为预设)，因此，X(n + 1) 仅与 X(n) 有关，即

{X(n)} 是有限状态的马尔科夫链，由于

P {(T (X(n))

= x

(n + 1)}



(n+1)∈S



(n),Y

(n))∈S

P {T

(X(n)) =



(n), Y

(n)



} ·





(n), Y

(n)



= x

′

(n + 1)



P {T

′

(n + 1)) = x

(n + 1)}

以及对于任意

X(n) ∈ S

，均存在 (Y

(n), Y

(n) ∈ S

) 及 x

′

(n + 1) 使得

P {T

(n)) = (Y

(n), Y

(n))} > 0 (1.3)





(n), Y

(n)



= (x

′

(n + 1))



> 0 (1.4)

对于任意 x

′

(n + 1) 及 x

(n + 1)，有

P {T

′

(n + 1)) = x

(n + 1)} > 0 (1.5)

于是

P {(T (X(n))

= x

(n + 1)} > 0 (1.6)

http://www.ma-xy.com 29 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

由于 (1.3)(1.4)(1.5) 与 n 无关，所以 (1.6) 也与 n 无关。从而

P {(T (X(n)) = X(n + 1)} =



k=1

P {(T (X(n))

= x

(n + 1)} > 0

也与 n 无关。综上，标准遗传算法 SGA 的种群序列 {X(n)} 是 S

正的其次不可约非周期马尔

科夫链。

定理 SGA 的种群马尔科夫链 {X(n)} 存在极限分布。

证明

lim

n→∞

P {X(n) = Y }

= lim

n→∞



X(0)∈S

P {X(n) = Y /X(0)} ·P {X(0)} = π(Y )

此 π(Y ) 是 S

上的分布，且



Y ∈S

π(Y ) · P {X(n) = Z/X(0) = Y } = π(Z)

□

上述定理说明 SGA 的种群马氏链 {X(n)} 是分布收敛的，它不依赖于初始种群 X(0) 的选

取，即

π(Z) = lim

n→∞

P {X(n) = Z/X(0) = Y }

假设 f 是 S 上的适应度函数，记

M = {x

∈ S, 使f(x

) = max

x∈S

f(x)}

若 Y ∩ M = ϕ，则

lim

n→∞

P {X(n) ∩ M = ϕ/X(0) = Z} ⩽ 1 −π(Y ) < 1

即不能保证当 n → ∞ 时，X(n) ∩ M = ϕ，因此，SGA 不能保证得到全局最优解。但是，由于

SGA 的状态空间是正常返的，它以概率 1 保证 {X(n)} 可以达到 S

中任何状态无限多次。特

别地，X ∈ M 也可以达到无限多次，所以，从实用角度来讲是有效的。在上述 2 个定理中我们

使用的单点交叉，事实上，定理适用于任何交叉方式。

定理设 {X(n)} 是 SGA 的种群马氏链，P

= 0，H 为齐次种群条件，即

H = {(x, x, ··· , x)|x ∈ S}

则 ∀n ⩾ 1，有

¬P {X(n) ∈ H/X(0) ∈ H} = 1

http://www.ma-xy.com 30 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

{X(n)} 以概率收敛到 1，即

lim

n→∞

P {X(n) ∈ H} = 1

®{β(X(n))|n > 1} 以概率 1 单调不增，即

P {β (X(n + 1)) ⩽ β (X(n))} = 1

¯{β(X(n))} 以正概率单调减，即

P {β (X(n + 1)) < β (X(n))} > 0

°{β(X(n))} 几乎处处收敛到 0，即

P { lim

n→∞

β (X(n)) = 0} = 1

其中：β (X(n)) 表示 X(n) 的成熟度。

定理每代在选择操作后保留最优个体的

SGA

以概率

收敛到全局解

。

定理每代在选择操作前保留最优个体的 SGA 以概率 1 收敛到全局解。

1.2.6 多目标规划中的遗传算法

基本理论

在前面的最优化基础当中，我们已经讨论过多目标优化问题，考虑一般形式的多目标问题：

min

t∈R

f(x) = (f

(x), f

(x), ··· , f

(x))

s.t. h(x) = 0

g(x) ⩽ 0

其中：f, h, g 为向量值函数，f

, h

, g

: R

→ R，x ∈ R

为决策变量。

在 GA 中，我们称 x 为个体。下面，我们再次引入 Pareto 可行解的概念：∀x

, x

∈ R

，

如果 f (x

) ≜ (f

(x), f

(x), ··· , f

(x)) > f (x

) ≜ (f

(x), f

(x), ··· , f

(x))，则记 x

≻ x

；如果

f(x

) ⩾ f (x

)，则记 x

⪰ x

，说明个体 x

至少有一个目标比个体 x

要好，且 x

的所有目标

皆不比 x

差，称 x

支配 x

。用 x

∼ x

表示 x

与 x

互不支配。

以一个二目标规划问题为示例，其可能的 pareto 前端如图 (1.3) 所示

上述定理的证明可以参考《智能优化算法及应用》王凌 P42 或者《遗传算法原理及应用》P117-P119.

http://www.ma-xy.com 31 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

图 1.3: 二目标规划问题 pareto 前端示意图

图中 x

, x

为 Pareto 最优解，阴影部分中的解为被 x

支配的解，所有 Pareto 最优

解形成 Pareto 前端。

GA 在多目标规划问题中的应用始于 Schaer(1985) 提出的向量估计遗传算法 (UEGA)。多

目标进化算法 (MOEA) 经过了以下三个阶段。1) 1985-1994 年缓慢发展期：该阶段的算法包括

非 Pareto 方法和 Pareto 方法。其中，非 Pareto 方法没有直接使用 Pareto 最优解的基本概念，

具有高效且易实现的特点，但不能产生 Pareto 最优前端的某些部分 (片段)。而 Pareto 方法则利

用劣排序和选择，使整个种群毕竟 Pareto 最优前端。第一代算法的代表有 UEGA、多目标遗传

算法 (MOGA)、小生境技术 (NPGA) 和非劣排序遗传算法 (NSGA)。2) 1994-2003 快速发展期：

从 1994 年 Zitzler 和 Thiele 提出强度 Pareto 进化算法 (SPEA) 开始，许多研究者开始把外部档

案式外部种群结合到多目标进化算法中，精英保留策略成为第二阶段的基本设计步骤。代表算法

有 NSGAXXXV1、Pareto 档案进化策略 (PAES)、Pareto 包络选择算法 (PESA) 以及 SPEA2

等。3) 2003 年至今：从 2003 年开始，多目标进化算法进入到一个新的阶段，混合策略、并行策

略、协同进化策略、动态进化策略和动态多目标优化问题也有初步发展。

多目标算法设计的基本要求：¬提供一组尽可能大的非劣解；要使这组解逼近问题的全局

Pareto 前端；®解集合尽可能均匀分布在整个全局最优前端上。

多目标算法的性能指标：世代距离 GD、收敛性指标 γ 和多样性指标 ∆ 等，主要用来评价

所求解与全局 Pareto 前端的逼近程度和收敛性。下面，我们给出多目标算法的一些性能指标。

定义 (收敛性指标) 设多目标优化问题的 Pareto 最优集是已知的，在问题的 Pareto 最优前

端上均匀的取一些点 (如 500 个)，计算由算法获得的解与这些点之间距离的最小值，所有这些最

小值的平均值就是收敛性指标 γ。

定义 (多样性指标) 将算法获得的所有非劣解按某个目标函数值的大小有序的分布在目标空

间上，h

为相邻两点间距离，

h 为 h

的均值，h

, h

分别是算法获得的边界解与相应极端解的

http://www.ma-xy.com 32 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

距离，则多样性指标 ∆ 为

∆ =

− h



n−1

i=1

−

+ h

+ (n −1)

定义 (SP 指标) 指标 SP 描述非劣解在目标空间上的分布范围

SP =







n − 1



i=1

(

d − d

)

式中，d

= min

j=1,2,...,n





k=1

− f



，

d =



i=1

。

定义 Zitzler 等给出了 3 个用于度量算法求解质量的指标

∗

(NP ) =

|NP |



p∈NP

min{||p −

p||,

p ∈ P

}

∗

(NP ) =

NP − 1



p∈NP

|{q ∈ N P, ||q − p||

∗

> σ

∗

(NP ) =









i=1

max{||p

− q

∗

, p, q ∈ N P }

其中，NP 为算法获得的非劣解集；P

为问题的 Pareto 最优前端。

∗

确定非劣解集 N P 与 P

之间的平均距离。分布性指标 M

∗

则反映了 σ

∗

-niches 的数量，

其值取在区间 [0, |N P |] 内，且其值越大，反应算法获得的非劣解分布越均匀。M

∗

测量 N P 中

非劣解在 Pareto 最优前端的分布范围。

定义 (误差比 ER) 误差比 ER 用来描述在算法产生的非劣解中，不属于真实 Pareto 前端

的解所占的百分比

ER =



i=1

其中：n 为所获得的非劣解的个数，若解 i 属于 Pareto 最优解集，则 e

= 0；否则，e

= 1。ER

值越小，属于 Pareto 最优解集的非劣解所在比例越高。ER = 0 表示所在非劣解都位于真实的

Pareto 前端上。

定义 (GD 距离) GD 用来描述算法所获得的非劣解与问题的真实 Pareto 前端之间的距离

GD =





i=1

dist

其中：dist

表示第 i 个非劣解与真实 Pareto 前端之间的最短距离。

多目标算法的测试函数：如果想测试一下设计的多目标算法的求解性能，可以用一些函数来

测试。关于多目标算法的测试函数，可以参考网址

。

http://www.xuebuyuan.com/2224684.html

http://www.ma-xy.com 33 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

第一代多目标进化算法

由于很多第二代 MOEA 都是在第一代 MOEA 的基础上发展起来的，因此，我们先简要介

绍第一代多目标进化算法。

1) 向量估计遗传算法 (VEGA) VEGA 具体的过程如下：设有 p 个目标函数，针对每个目标

利用比例选择法，分别产生 p 个子种群，每个子种群的规模为 N/p。这 p 个子种群分别得到进

化后，再将他们合并为一个大小为 N 的种群，再执行遗传操作。重复上述过程，直到收敛。

2) 多目标遗传算法 (MOGA) 在 MOGA 中，个体的秩等于当前种群中支配他的染色体数目加

1，所有非劣个体的秩均为 1(所有这样的个体适应度都相同，以便能以相同的概率别选择使用)，

而被支配的个体依据属于他们所在区域的种群密度被惩罚 (适应度共享用于验证个体区域的拥挤

程度)。适应度赋值方式如下：¬基于个体的秩将种群排序；利用线性或非线性的插值方法在最

低序号 (非劣最优个体) 与最高序号之间进行插值；®具有相同序号的个体的适应值共享，即通过

除以相同序号的个体数得到新的适应值。可以给不同序号的个体分配固定不变得适应值。

MOGA 的优点是算法执行相对容易且效率高，缺点是算法易受小生境大小的影响。值得一

提的是，Fonseca 等已经从理论上解决了小生境大小的计算问题。

3) 非劣排序遗传算法 (NSGA) 基于 Goldberg 的方法，NSGA 对个体分类，形成多个层次。

具体过程为，在选择操作之前，个体基于 Pareto 最优进行排序：所有非劣的个体归为一类，并

引进决策向量空间的共享函数法，保持种群的多样性；然后，忽略这些已经分类的个体，考虑另

一层非劣的个体；这个过程一直持续，直到将所有个体分类。由于最先得到的非劣个体有最大的

适应度，他们被复制的机会更多。

NSGA 的优点是最优目标个数任选，非劣最优解分布均匀，允许存在多个不同等效解；缺点

是由于 Pareto 排序要重复多次，计算效率较低。计算复杂度为 O(MN

)，未采用精英保留策略，

共享参数 σ

需要预先确定。

4) 小生境 Pareto 遗传算法 (NPGA) NPGA 使用基于 Pareto 支配的锦标赛选择模式，其基

本思想非常巧妙：随机选择两个个体，与来自种群的一个子集比较 (典型的，子集占整个种群的

10%)，若其中一个个体支配自己，而另一个个体被子集支配，则非劣个体获胜；若两个个体都不

受或都受子集支配，则采用共享机制来选取其中之一参与下一代进化。因为该算法的非劣解选择

是基于种群的部分而非全体，所以其优点是能很快找到一些好的 Pareto 最优解域，并能维持一

个较长的种群更新期。缺点是除了需要设置共享参数外，还需要选择一个适当的锦标赛规模，因

而限制了该算法的实际应用效果。

第二代多目标进化算法

这一部分，我们将介绍精英策略、共享策略、分级策略以及 SPEA、SPEA2、NSGAXXXV1、

IENSGAXXXV1 等多目标进化算法。

http://www.ma-xy.com 34 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

精英策略 Elitist srtategy 精英策略就是在算法的迭代过程中，从上一代保留优秀的潜在解至

下一代的过程，简单地从上一代中直接拷贝相应的解至下一代是常用的方法。早在 1975 年，精

英策略已经被认为是一种改进 EA 算法效率的有效手段，当前在多目标优化领域的一些研究也显

示该策略能有效改善 MOEA 算法的效率。对于单目标优化，精英策略的应用是非常简单和显而

易见，因为在种群中仅有一个最优个体, 对于多目标优化，该策略的使用却要复杂很多。可以定

义当前种群的所有非劣的个体的集合为精英解集或称为归档，但是显然，随着运行代数的增加,

该解集的个体数量会趋于原种群的个体数量，无改变地拷贝大量的精英进入下一代会妨碍整个种

群的进一步进化。

可以总结，多目标优化的精英策略面临两个问题：1. 怎样控制精英种群的大小；2. 怎样使用

精英策略更好地指导搜索。Zitzler 和 Thiele 提出了一种简单有效的 MOEA 精英策略，并在此

基础上得到了 SPEA 算法。该算法的成功使精英策略在 MOEA 领域得到了新的重视。Deb 也于

2000 年提出了采用精英策略的 NSGAXXXV1 算法。简单地可将精英策略划分为两种：在线归

档 (no-line) 和离线归档 (o-line)。在线归档和离线归档的区别在于虽然离线归档也在每一代中

不断更新, 但归档中的精英个体不显式地用于产生下一代。

共享策略 (sharing strategy) 多目标演化算法的目标之一是要在可行区域中获得一个适当分

布的候选解集供决策者使用。在演化算法的整个种群中形成各个子种群簇的方法可用来达到这个

目的，该类技术也被称为小生境技术。适应值共享是小生境技术的一个较成功的实现，在该方法

中，每个候选解的原始适应值需要根据其局部种群密度进行校正。这里所说的局部种群的密度一

般是指在可行区域内度量，其直接体现了保持解的较好分布的目标。适应值共享策略较好地解决

了 gneeticdrt 的问题，避免算法陷入局部最优，使算法更有可能获得一个分布合适的 Paerot 阵

面。

分级策略 (Ranking strategy) 大多数现代的多目标演化算法都是基于 Pareot 支配的概念的，

并且大致可以分为以下的两种具体的分级策略:

1. Non-dominated sorting(NDS)

2. Multi-objectiv ranking(M0R)

两种方法的思想都非常简单，对于 NDS 方法，考虑需要比较的候选解集和其对应的目标向

量，Goldberg 把解集分成不同的非支配层次: 初始时，候选解集的全局非支配解被赋予最高的级

别，如用 0 表示，然后将这些非支配解暂时从考虑的解集中移走；考虑剩下的解集中的解，对其

中的非支配解又赋予较高的级别，如用 1 表示，再移去这些非支配解；如此类推，直到剩下的解

集为空为止。

MOR 方法并不产生一系列的非支配阵面，对于每一个个体，仅仅计算在候选的解集中支配

它的个体的数量。这样，全局非支配的个体赋予为 0 的较高的等级，其它个体次之。两种方法都

能达到这样的基本目标目的：所有的首选解被赋予相同的等级 0；更好的解被赋予更高的等级。

不同的现代算法采用不同的方法，例如 SPEA 算法采用 MOR 算法，而 NSGAZ 算法采用 NDS

算法，没有明显的证据表明哪种算法更优。

http://www.ma-xy.com 35 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

强度 Pareto 进化算法 (SPEA) SPEA 算法使用一个规则群体和一个在线归档。开始时初始

化一个种群和一个空的在线归档，以下步骤重复进行。首先，将种群中未被支配的个体成员拷贝

到在线归档中；在在线归档中去除任意被支配的个体或者重复个体，如果这个被不断更新的在线

归档大小超过了预先定义的大小，那么为了保持未被支配阵面的特征，在在线归档上采用簇方法

去除多余的个体成员；然后对在线归档和种群中的成员进行适应值赋值，并将群体和在线归档中

的个体通过锦标赛选择再经过杂交和变异替代父代群体成为下一代群体，SPEA 算法具体步骤如

下：

Step1. 产生初始种群 P 和空的外部非劣解集 N P 。

Step2. 将种群 P 中的非劣个体拷贝考非劣解集 N P 。

Step3. 剔除集合 N P 中受种群 P 中个体支配的解。

Step4. 如果保留在集合 NP 中的非劣解的个数超过事先给定的最大值，则通过聚类分析对集合

NP 进行修剪，提出多余的解。

Step5. 计算种群 P 和集合 N P 中的每个个体的适应度值。

Step6. 利用二元锦标赛方法从 P ∪ N P 中选择个体进入下一代。

Step7. 对个体实施交叉和变异操作。

Step8. 终止条件。不终止则返回 Step2.

下面我们详细介绍适应度赋值过程和聚类分析过程。¬适应度赋值分为两个阶段，首先对

非劣解集 N P 中的个体进行赋值，然后对种群中的个体赋值。具体描述如下：(1) 对于每个解

∈ NP ，赋予一个强度值 s

∈ [0, 1)，s

= h

/(N + 1) ，其中 h

表示种群中受个体 x

支

配的个体数，N 为种群规模。个体 x

的适应度值 f

= s

；(2) 每个个体 x

∈ P 的适应度值

= 1 +



i,x

≻x

，即所有支配解 x

的解 x

∈ N P 的强度秩和再加 1。

聚类分析：通常情况下，非劣解集大小必须受限，必须为其规定最大规模，即保留在其中的

解的最大个数，主要原因有 4 个方面 (1)MOP 的非劣解集大小可能非常大，甚至是无穷大；(2)

实现算法的计算资源是有限的；(3) 档案维数的复杂性会随档案规模变大而显著增加；(4) 遗传漂

移可能出现，因为在均匀采样过程中搜索空间中过度代表的区域总是优先被选择。

前三点意味着必须限制档案的大小，而第四点表示对档案进行修剪可能对算法性能有利。

SPEA 采用如下聚类算法对非劣解集进行修剪：

Step1. 初始化聚类集 C，该集合由非劣解集 N P 的解构成，每个解对应一个聚类。

Step2. 如果 |C| ⩽

N，转到 Step5；否则转到 Step3.

Step3. 计算所有聚类之间的距离，两个聚类 c

, c

∈ C 之间的距离 d =

||c



∈c

||i

−i

||，

其中 ||i

− i

|| 表示两个个体在目标空间上的欧式距离。

Step4. 确定具有最小距离的两个聚类 c

, c

∈ C，然后调整聚类集 C = C/{c

, c

} ∪ {c

∪ c

}，

转到 Step2.

Step5. 确定每个聚类的代表个体。通常选择和同一聚类的其他个体之间的平均距离最小的个体

作为该聚类的代表。其中

N 为外部非劣解集的最大大小。

http://www.ma-xy.com 36 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

强度 Pareto 进化算法 2(SPEA2) 在 SPEA2 算法中，它去除了原有算法的弱点并且加入了

一些新的方法，SPEA2 算法使用的是细粒度赋值策略，它组合进了密度信息。在这个算法中，

每一个解，不论它是 Pareto 大于还是 Pareto 小于其他解，表示这个解的个体总是被考虑进来。

SPEA2 的算法步骤如下：

Step1. 产生初始种群 P

和空的外部档案 A

，令 t := 0。

Step2. 计算种群 P

和外部档案 A

内个体的适应度值。

Step3. 确定 A

t+1

= {x

∈ P

∪A

非劣}，如果 A

t+1

的大小超过

N，则修剪 A

t+1

；如果 A

t+1

的大小小于

N，则将 P

和 A

中的受支配解加入到 A

t+1

中，直到其大小等于

N。

Step4. 如果 t > T ，则输出外部档案 A

t+1

，并停止搜索。

Step5. 对外部档案 A

t+1

采用替代的二元锦标赛方法选择个体进入交配池。

Step6. 对交配池和种群 P

t+1

实施交叉和变异操作，t = t + 1 转到 Step2.

下面描述适应度赋值和外部档案维护的具体过程。¬适应度赋值为了避免被同样的外部档案

成员支配的个体具有相同的适应度值，在 SPEA2 中，每个个体的所支配的解和支配它的解都被

考虑在内。种群和外部档案中的个体 i 都被赋予一个强度值 S(i)，表示受该个体支配的解的数量

S(i) = |{j|x

∈ P

+ A

, x

≻ x

在 S(i) 的基础上，个体 i 的原始适应度值 R(i) 等于支配该个体的所有个体的强度值之和，即

R(i) =



∈P

≻x

S(j)

与 SPEA 不同的是，计算 R(i) 时，种群和外部档案内的个体都考虑在内，而且原始适应度值越

小，说明支配该个体的个体少，R(i) = 0 表示个体 i 为非劣解。

原始适应度赋值过程提供了一个非劣排序，但仅仅非劣排序还不够，必须引入密度信息以区

分具有相同原始适应度值得个体。SPEA2 采用 k 近邻方法来计算个体 i 的密度值 D(i)

D(i) =

+ 2

其中：σ

为个体 i 与第 k 个近邻个体在目标空间上的距离，k =

√

N +

N。最终，个体 i 的适应

度值 F (i) 为原始适应度值和密度值之和

F (i) = R(i) + D(i)

外部档案维护 SPEA2 的档案维护过程与 SPEA 存在两个点差异：(1) 档案大小始终是一个常

数；(2) 档案维护避免了边界解从档案中移出。具体过程如下：

Step1. 将种群 P

和外部档案 A

的所有非劣解拷贝到 A

t+1

中，如果 A

t+1

的大小刚好等于

N，

则接受。

Step2. 如果 |A

t+1

N|，则将 P

和 A

最好的

N − |A

t+1

| 个受支配解加入到 A

t+1

中。

Step3. 如果 |A

t+1

N|，则不断的将档案 A

t+1

中的解移出直到 |A

t+1

| =

N，在修剪档案过程

中，根据如下原则决定哪个解从档案中移出，如果个体 i 满足如下条件则从 A

t+1

中剔除。对所

有个体 j，i < dj，其中，i < dj 当且仅当 ∀0 < k < |A

t+1

|，有 σ

= σ

，或者 ∃0 < k < |A

t+1

|，

有 σ

< σ

，且对 ∀0 < l < k 有 σ

= σ

。

http://www.ma-xy.com 37 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

NSGAXXXV1 Deb.et 和他的学生们于 2000 年提出了一种精英策略的非劣分类遗传算法

NSGAXXXV1。在大多数方面，该算法与初始的 NSGA 没有太多的相似性，创始者为了强调它

的起源而保持了 NSGAXXXV1 这个名字。

在 NSGAXXXV1 中，首先用亲代种群 P

产生子代种群 Q

，并将两个种群联合在一起形

成大小为 2N 的种群 R

。然后使用非劣分类将整个种群 R

分等级。尽管与只对 Q

进行非劣

分类相比，它需要做更多的工作，但是它允许在整个子代和亲代进行全局的非劣检验。一旦结束

非劣分类，新种群 P

t+1

由不同的非劣等级的个体填充。填充过程从最优非劣等级开始，接着是

第二非劣等级，依此类推。由于整个种群凡的种群大小为 2N ，新种群的 N 个位置不能容纳所

有的非劣等级。当考虑被允许的最后一等级中的解时，该非劣等级可能存在比新种群剩下位置更

多的个体。在这种情况下，使用密度估计的方法从最后一等级选择位于该等级较稀疏区域的个体

填充满该种群。这里着重要指出的是 R

的非劣分类过程和种群 P

n+1

的填充过程可以一起执行。

这样，每次找到一个非劣等级并检查它的大小，看它是否能被新种群容纳，如果不能，那么就不

必再进行非劣分类，这样能减少该算法的运行时间。NSGAXXXV1 的具体过程描述如下：

Step1. 随机生成初始种群 P

，然后对种群进行非劣排序，每个个体被赋予秩；再对初始种群执

行二元锦标赛选择、交叉和变异，得到新种群 Q

，令 t = 0。

Step2. 形成新的群体 R

= P

∪ Q

，对种群 R

进行非劣排序，得到非劣前端 F

, F

, ···。

Step3. 拥挤度选择操作。对所有 F

按排挤比较操作 ≺

进行排序，并选择其中最好的 N 个个

体形成种群 P

t+1

。

Step4. 对种群 P

t+1

进行复制、交叉和变异，形成种群 Q

t+1

。

Step5. 终止条件。不终止，则 t := t + 1 返回 Step2.

下面介绍上述算法中所使用的快速非劣分类方法、拥挤距离尺度以及拥挤选择算子。(一) 快

速非劣分类方法：首先，对于每一个解我们计算两个量：¬支配解 i 的解的个数 n

；i 支配的一

组解 S

。这两个量的计算时间为 O(MN

)。随后，将所有 n

= 0 的解放入解集 F

中。对于当

前解集 F

中的解 i，观察它的 S

集，将 S

集中每个解 j 的 n

数减 1，作完上述步骤后，如果

支配 j 的解个数 n

= 0，这也就意味着 j 是仅次于第一等级中解的个体。此时把 j 放入 F

中。

重复上述过程，最终将所有的解按照非劣关系分为多个等级。其中 F

中的解是最好的，也就是

前面所提到的精英解，它只支配解而不被其他任何解支配，凡中的解只被 F

中的解支配，不被

其它解支配，依次类推。

每次迭代时间为 O(N)，由于最多有 N 个解集，那么最坏情况下这个循环的时间为 O(N

)。

总时间复杂度为 O(MN

) + O(N

) 或者 O(MN

)。

(二) 拥挤距离：种群中某个个体 i 的拥挤距离 d

是一个在个体 i 周围不被种群中任何其它

的个体所占有的搜索空间的度量。为了估计种群中某个个体 i 周围个体的密度，取个体 i 沿着每

个目标的两边的两个个体 (i − 1), (i + 1) 的水平距离，数量 d

作为 M 个距离之和的估计值，称

之为拥挤距离。拥挤度距离的求解步骤为 (1) 每个点的拥挤距离 d

设置为 0；(2) 设 f

为目标

函数 m = 0, 1, . . . , M ，设 d

= d

= ∞，并且对其他所有个体 i = 1, 2, . . . , l − 1，分配



m=0



i+1

− f

i−1



http://www.ma-xy.com 38 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

其中：d

表示第 i 个点的拥挤距离，f

i+1

表示第 i + 1 个点的第 m 个目标函数值。

(三) 拥挤选择算子：在 NSGAXXXV1 中，定义拥挤比较算子 ≺

如下

if(i

rank

< j

rank

)or((i

rank

= j

rank

)and(i

diatance

> j

diatance

))

⇒

≺

(

解

优于解

)

它假设每个个体 i 有两个属性：1. 种群中的非劣等级 r

；2. 种群中的局部拥挤距离 d

。依据这

两个属性，可以定义拥挤度选择算子如下

定义 (拥挤选择算子) 个体 i 与另一个个体 j 进行比较，只要下面任意义个条件成立，则个

体 i 获胜：1. 如果个体 i 所处等级优于个体 j 所处等级，即 r

< r

；2. 如果他们有相同的等级，

且个体 i 比个体 j 有一个更大的拥挤距离，即 r

= r

& d

> d

。

第一个条件确保被选择的个体属于较优的非劣等级。第二个条件根据它们的拥挤距离选择

由于在同一非劣等级而不分胜负的两个个体中位于较不拥挤区域的个体 (有较大的拥挤距离 d

)。

在联赛选择和新种群填充阶段都使用了拥挤比较过程，通过使用拥挤比较过程引入了非劣解集内

个体的多样性分布。由于个体通过它们的拥挤距离 (邻近个体密度度量) 来竞争，因此，这里不

需要专门的小生境参数 (例如在 MOGAs、NSGAs 或 NPGAs 中需要的参数 σ

)。尽管是在

目标函数空间计算拥挤距离，但是，如果需要的话，也能在参数空间实现拥挤距离的计算。

IENSGAXXXV1 在试验过程中，我们发现 NSGAXXXV1 算法仍然有一定的缺陷：保留精

英也就意味着强调子代中的最优解。在许多情况下，一个种群主要由当前最好的非支配解组成，

那么，这些解都是精英，当前种群也就不能再接纳一些新的解参与下一代的操作，搜索过程将中

止并过早的收敛到局部的 Pareto 解。在 NSGAXXXV1 中，由于没有限制精英解的范围，使得

NSGAXXXV1 在六个测试问题 (ZDTI,ZDTZ,ZDT3,ZDTI4,ZDT6,KUR) 上的仿真结果显示大

概在 20 代以后，种群中的所有解都是精英，随后各代的操作都将在精英解中进行，非精英解无法

参与其中，降低了解的多样性。由于精英操作导致绝大多数的非精英解不能参与遗传操作，使得

全局解的搜索速度减慢并最终导致种群过早收敛到局部 Pareto 解。为了确保搜索向全局 Pareto

优解收敛，一种确保解的多样性的改进的精英策略被提出，在改进精英策略方面我将重点放在了

控制精英范围上，取得了很好的效果。将这种改进精英策略 (ImporvedElitist) 的 NSGAXXXV1

算法称为 IENSGAXXXV1。

在改进的算法中，我们的目标是确保个体的多样性从而得到较好的收敛性。因此，自适应的

限制当前精英解集的范围从而使非精英解集也能平等的参与到新种群的操作就显得尤为重要。分

布函数如下

= N

1 − r

1 − sin(r

)

/(sin r)

+ share (1.7)

其中：n

(m ⩽ i ⩽ 1) 是当权等级中允许的最大个体数，i 是当前种群级别，N 是种群规模，m 是

当前种群 (合并后的规模为 2N 的种群) 中非劣等级的数目，r(0 < r < 1) 是一个可以由用户来

自定义的参数。IENSGAXXXV1 的算法流程如下：

Step1. 对种群 R

= P

∪ Q

进行快速非支配排序，并对每个个体计算拥挤距离。

http://www.ma-xy.com 39 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

Step2. 根据公式 (1.7)，计算出每个等级中所允许的最大个体数目，由于 r < 1，因此等级 1(i = 1)

中允许的个体数是最多的，而等级 1 中的解是当前种群中最好的非劣解，也就是所谓的精英解。

这充分照顾到了精英解，使得较多的精英解参与遗传操作中。由公式不难看出，随着等级数即 i

值的增大，各个等级中所允许的个体数目依次减少，这对于各个等级都是公平的，也体现了“适

者生存，优胜劣汰”的思想。

Step3. 与 NSGAXXXV1 类似，按照第二步的方法将 N 个符合条件的解放入下一代中，继续对

其执行选择、交叉、变异等遗传操作。

多目标混合进化算法

防止过早收敛的有效方法之一是进化算法与局部搜索混合，这样的混合算法叫 memetic

算法。Ishibuchi 等最早于 1998 年提出了多目标遗传局部搜索 (MOGLS)，记为 IM-MOGLS。

Ishibuchi 等于 2003 年修改了 IM-MOGLS 的局部搜索过程，得到 IM-MOGLS2。在简单 MOGLS(S-

MOGLS) 中，遗传搜索和局部搜索之间有四种可能组合，遗传搜索可能根据标量适应度值或根

据 Pareto 排序与拥挤距离选择父代个体，而局部搜索可能根据 Pareto ranking 或标量适应度值

决定是否接受新解。

Jaszkiewicz 设计一种 MOGLS：J-MOGLS，在每一次迭代中，算法随机确定一个效用函数，

然后构造一个临时种群，该种群包含很多选定的效用函数值最好的解，然后从临时种群中选出一

对个体进行重组，局部搜索作用于重组得到的新解。Talbi 等提出了一种简化的遗传局部搜索，该

算法先用遗传算法搜索，GA 停止后，再应用多目标局部搜索。在 Arroyo 等提出的 AA-MOGLS

中，精英策略、保持种群多样性以及并行多目标局部搜索被引入到 MOEA 中。

M-PAES 是在局部搜索多目标优化算法 (1+1)PAES 基础上建立起来的。在 M-PAES 中存

在两个档案：全局档案 G 和局部档案 H，全局档案为非劣解的有限集，局部档案作为比较集用在

局部搜索阶段即 (1+1)PAES 中。雷德明等利用混沌现象的内在特性，将混沌搜索引入到 MOEA

中，在每一代，当种群完成一次进化 (复制、交叉和变异) 之后，在外部档案的部分个体附近进

行混沌搜索以产生更多非劣解，引导 MOEA 新的进化。郭秀萍等将基于加权函数的局部搜索

和基于 Pareto 支配关系的交叉、变异和网格微扰动算法相结合，提出了一种混合自适应多目标

memetic 算法。

多目标遗传局部搜索：IM-MOGLS 在 IM-MOGLS 中，具有随机权值的标量适应度函数用于

父代种群的选择和局部搜索，遗传搜索产生的种群的每个个体都参与局部搜索，当不能从当前解

的领域中随机选择的 k 个领域解中找到更好的解时，局部搜索中止。IM-MOGLS 具体描述如下：

Step1. 初始化。

Step2. 计算当前种群中每个个体对应的目标向量，并对临时非劣解进行升级。

Step3. 选择：重复执行如下过程选择 N − N

elite

对父代个体。

¬随机确定各目标函数权值 w

= rand



j=1

rand

。

根据选择概率选择一对父代个体。

Step4. 交叉和变异，对 N − N

elite

对父代个体的每对执行交叉操作，每队父代个体通过交叉产

http://www.ma-xy.com 40 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

生一个新个体，然后对新个体执行变异操作。

Step5. 从临时非劣解集中随机选出 N

elite

个个体与前面产生的 N − N

elite

个个体一起构成新的

群体。

Step6. 对群体中的所有解进行局部搜索，局部搜索方向由 Step3 父代个体选择时确定的权值决

定，并用局部搜索产生的 N 新解替代当前种群。

Step7. 若终止条件成立，结束；否则转到 Step2。

上述算法中，N 为种群规模，N

elite

为精英个体数，每个个体的选择概率为

p(x) =

f(x) − f

min



x∈P

{f(x) − f

min

}

(1.8)

其中，f

min

为种群 P 中最劣个体的适应度值，f

min

= min{f (x)|x ∈ P }。

在 Step3 中，各个目标函数的取值随机确定，每一组权值都将对应一种搜索方向。因此，局

部搜索的方向是多样的。

混合算法对新群体中的每个解进行局部搜索，局部搜索具体过程如下：

Step1. 确定一个初始解 x。

Step2. 产生当前解 x 的邻域解 y。

Step3. 如果 y 优于当前解 x，则取代之。

Step4. 如果当前解 x 的随机选择的 k 个邻域解都不能优于当前解，则结束；否则转到 Step2。

当当前解的 k 个邻域解都不能优于当前解时，算法结束。k 太小，局部搜索会很快结束；k

太大，局部搜索过程将很大。

IM-MOGLS 包含两个解集：当前种群和临时非劣解集。局部搜索完毕后，当前种群被局部

搜索产生的新解替代，同时临时非劣解集也得到了更新，即将不受当前种群中其他个体和临时非

劣集中的个体支配的种群个体加入到临时集中，同时剔除临时解集中的受支配解局部搜索的部分

初始解来自临时非劣解集，非劣解的局部搜索方向由其父代个体选择时所使用的权值决定，如果

非劣解没有父代如非劣解为非劣解为随机产生的初始解，则随机产生一个搜索方向。

多目标遗传局部搜索：IM-MOGLS2 Ishibuchi 等修改了 IM-MOGLS 的局部搜索过程，为每个

被选中的解的拷贝确定了固定的局部搜索概率，而且只有锦标赛选择过程中获胜的个体才能作为

局部搜索的初始解，并为每个初始解规定了合适的局部搜索方向。为描述方便，记为 IM-MOGLS2，

计算结果表明，IM-MOGLS2 性能明显优于 IM-MOGLS。

IM-MOGLS2 与 IM-MOGLS 的唯一差别在于 Step6，即局部搜索过程。改进过程如下：

重复如下三步骤 N 次，然后用这 N 个解去替代当前种群。

Step1. 随机确定权值 w

, w

, ··· , w

，其中，w

≥ 0, i = 1, 2, ··· , M,



i=1

= 1。

Step2. 利用根据 Step1 的权值而得到的标量函数，使用带放回的锦标赛选择策略，从当前

种群中选中一个解，对其进行拷贝后，将其放回种群。

Step3. 利用现有权值，根据局部搜索概率 p

，对选中解的拷贝实施局部搜索。局部搜索的

具体过程与原始 MOGLS 的相应过程相同。如果局部搜索得到实施，将最终得到的解加入另一

个种群中；如果局部搜索没有进行，则将拷贝加入到另一个种群中。

http://www.ma-xy.com 41 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

上述局部搜索的基本思想是尽量不为每个解规定一个适合的局部搜索方向，而是为随机确定

的局部搜索方向选择一个适合的解；而且，不对所有选中的解进行局部搜索。使用局部搜索概率

的目的在于减少局部搜索的解的个数。

S-MOGLS S-MOGLS 中，遗传搜索和局部搜索之间存在四种可能组合，具体步骤如下：

Step1. 随机产生具有 N 个解的初始种群。

Step2. 遗传搜索。重新执行如下三个步骤 N 次以产生子代种群：

¬随机确定一个权值向量；

利用根据步骤¬的权值而得到的标量函数使用锦标赛选择策略，从种群中选中一对父代个

体；

®对选出的父代个体进行交叉和变异，以产生一个子代个体。

Step3. 局部搜索。通过循环执行如下三个步骤 N 次以得到改进后的种群；

¬随机确定一组权值；

利用根据步骤¬的权值而得到的标量函数，使用锦标赛选择策略，子代种群中选中局部搜

索的一个初始解；

®利用现有权值，根据局部搜索概率 P

进行局部搜索，与修改 MOGLS 不同，只有当初

始解通过局部搜索得到改进，局部搜索的最终解才加入到改进后的种群中。

Step4. 采用与 NSGA2 相同的非劣排序过程，从父代种群、子代种群和改进后的种群中选择个

体，构成下一代父代种群。

Step5. 如果终止条件成立，则停止搜索；否则转到 Step2。

当遗传搜索和局部搜索使用不同方法进行选择操作时，可以得到 S-MOGLS 的不同变形，例

如遗传搜索和局部搜索都利用标量适应度函数选择个体，或遗传搜索根据 Pareto 排序结果，而

局部搜索根据标量函数选择个体等。实验结果表明，局部搜索和遗传搜索之间的平衡对混合算法

的性能有很大的影响；而且，S-MOGLS 的不同变形的选择压力不同，但局部搜索初始解的高选

择压力对 S-MOGLS 的性能改善有利。

J-MOGLS 关于 MOGLS，除了 Ishibuchi 等系列工作之外，还有 J-MOGLS 和 AA-MOGLS

等算法。下面详细介绍 J-MOGLS，先定义效用函数，然后描述算法流程。

效用函数 u : R

→ R 将目标空间映射为效用值，它描述决策者的偏好。考虑如下两种两种

效用函数。

定义 (加权 Tchebyche 效用函数) 加权 Tchebyche 效用函数定义如下：

∞

(y, y

∗

, Λ) = −max

{λ

∗

− f

)} (1.9)

其中，Λ = {λ

, λ

, ··· , λ

}，∀j, λ

≥ 0 为权向量；y

∗

= {f

∗

, f

∗

, ··· , f

∗

}，f

∗

= max{f

|y ∈

Y }, j = 1, 2, ··· , M ; y = (f

, f

, ··· , f

)。

上述效用函数至少有一个全局最优解是 Pareto 最优解。对于每个 Pareto 最优解 x，存在一

个加权 Tchebyche 效用函数 u，使 x 为 u 的全局最优解。

http://www.ma-xy.com 42 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

定义 (加权线性效用函数) 加权线性效用函数定义如下：

(y, Λ) = −



j=1

如果存在一组非负权值 Λ = {λ

, λ

, ··· , λ

}，使 x 如下最大化问题的唯一全局最优解：

max u

(y, Λ)

s.t. x ∈ D

则 x 为 Pareto 最优解。

由于加权 Tchebyche 或加权线性效用函数在 Pareto 最优解达到最优，J-MOGLS 将多目标

优化算法的目的转化为寻找所有加权 Tchebyche 或加权线性效用函数的最优解。它通过选取效

用函数来实现所有效用函数的同时优化，即改善每次迭代时随机选取的效用函数的值来实现。具

体描述如下：

Step1. 初始化：令非劣解集 NP 为空，当前解集 CS 为空。

Step2. 重复如下过程 N 次：

¬随机取效用函数 u，随机构造一个新的可行解 x；

以效用函数 u 为目标，对 x 进行局部搜索，得到 ¯x；

®对 ¯x 加入到当前解集 CS 中并利用 ¯x 更新 NP。

Step3. 随机选取效用函数 u。

Step4. 从 CS 中选取 K 个不同解，根据效用函数 u，这些解最佳；然后由这些解构成临时种群

TP。

Step5. 随机地从 TP 中选取两个解 x

和 x

。

Step6. 重组 x

和 x

，得到解 x

。

Step7. 以效用函数 u 为目标，对 x

进行局部搜索，得到 ¯x。

Step8. 如果 ¯x

优于 TP 中的最差解且在决策空间上 ¯x

与 TP 中的任意解不同，则将 ¯x

加入

到当前解集 CS。

Step9. 利用 ¯x

对集合 NP 进行更新。

Step10. 如果终止条件成立，则停止搜索；否则转到 Step3。

所谓归一化权值向量指所有非负权值的和为 1。在 J-MOGLS 的每一次迭代过程中，都必须

随机选取效用函数，也就是要随机选取如下归一化加权向量：

= 1 −

M−1



rand(), λ



1 −

j−1



l=1



(1 −

M−1−j



rand()), ··· , λ

= 1 −

M−1



l=1

其中，rand() 为区间 [0, 1] 上均匀分布的随机数。

为了降低计算量，只利用局部搜索产生的解对 NP 进行更新和升级，具体步骤如下：如果

NP 中没有支配 ¯x

，则将 ¯x

加入到 NP 中，同时剔除 NP 中所有受 ¯x

支配的解。

M-PAES M-PAES 是在局部搜索多目标优化算法 (1+1)PAES 基础上，通过利用种群和周期

性利用交叉对 PAES 获得的不同局部最优解进行组合等过程，而建立起来的。M-PAES 的建档

http://www.ma-xy.com 43 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

过程比 PAES 复杂一些。回顾 PAES 的算法流程，可以发现，PAES 的核心是如何维护一个由

有限个非劣解组成且其所能保留的非劣解最大数固定的档案，档案成员是算法搜索过程获得的

最好非劣解的代表。(1+1)PAES 的档案用于如下两个目标：记录搜索过程中获得的解；用作比

较集以确定新的候选解的支配秩。为了在 M-PAES 中实现上述两个目的，需要两个档案：全局

档案 G 和局部档案 H，全局档案为非劣解的有限集，局部档案作为比较集用在局部搜索阶段即

(1+1)PAES 中。每次局部搜索开始时，H 被清空，并从 G 中选择不能支配候选解 c 的部分解，然

后用在 (1+1)PAES 中以改进 c；而 G 在整个搜索过程中得到连续不断地升级和更新。M-PAES

具体过程如下：

Step1. 随机产生规模为 N 的初始种群 P 并将 P 中所有非劣解加入到全局档案 G 中。

Step2. 对于种群 P 中的每个候选解 c，执行如下过程：

¬设置当前局部档案 H = Ω(空集)；

将全局档案 G 中所有不能支配 c 的个体加入到 H 中，同时也将 c 加入到 H 中；

®执行局部搜索过程 PAES(c,G,H)，并将改进后的解 c 放回种群 P 。

Step3. 设置种群为空：n

= 0, P

= Ω。

Step4. 执行如下重组过程：

¬令重组次数 r = 0；

从 P ∪ G 随机选择两个父代个体，然后通过重组产生子代 c；

®将 c 与 G 中个体进行比较，如果必要的话，利用 c 更新 G；

¯r = r+1，如果 c 被 G 支配或者 c 位于比两个父代更拥挤的区域且 r < recomb_trial_max，

则转到；否则，转到°；

°如果 c 被 G 支配，则丢弃 c 并利用二元锦标赛方法从 G 中选择一个新的 c；

±将 c 加入到中间种群 P

中，n

= n

+ 1；

²如果 n

< N ，则转到¬；否则，转到 Step5。

Step5. 利用中间种群 P

替代种群 P 。

Step6. 如果终止条件成立，则结束；否则，转到 Step2。

上述算法中，recomb_trial_max 为最大重组次数，PAES(c,G,H) 与 (1+1)PAES 类似，只

是终止条件不同。

PAES(c,G,H) 具体描述如下：

#fails = 0, #moves = 0;

while(#fails < l_fails, #moves < l_opt)

对 c 进行变异，得到解 x 并计算 x 对应的目标函数值；

if c ≻ x

丢弃 x；

#fails = #f ails + 1;

else if x ≻ c

利用 x 替代 c；

并将 x 加入到局部档案 H;

#fails = 0;

http://www.ma-xy.com 44 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.2 遗传算法

else if x 受 H 中任意一个成员支配，丢弃 x；

else 应用 test(c,x,H) 以决定 c 和 x 谁成为新的当前解以及是否将 x 加入到 H 中；

else if

利用 x 对全局档案 G 进行维护;

#moves = #moves + 1;

end while

其中，l_opt 为全局搜索最大次数，l_fails 为局部搜索失败的最大次数。test(c,x,H) 与 (1+1)PAES

中的 test(c,d,A) 一样。

MATLAB 应用实例

MATLAB 中使用 gamultiobj 命令来求解多目标优化问题，下面给出 gamultiobj 的命令格

式及其示例。gamultiobj 可用于求解平滑或非平滑的优化问题，不需要函数可微或连续。它可

以创建均匀、可行的初始种群；适应度尺度变换有：基于等级、比例、顶部、线性定标、移位；

选择方法有：锦标赛 (Tournament)；交叉方法有：scatterd(分散)、sigle(单点)、intermediate(中

间)、Heuristic(启发式)、arithmetic(算术)、两点；变异方法为：adaptic feasible(自适应可行)、

uniform(均匀)、gausian(高斯)；可以绘制：平均 Pareto 距离、平均 Pareto 散布度、个体间距、

个体多样性、个体预期、Pareto front、等级柱状图、选择指数和终止条件。此外，我们还可以指

定：群体大小、交叉片段、Pareto 片段、个体间的距离测量、子群体迁移、边界约束和线性非线

性约束。优化变量可以是整数、混合整数、分类型数和复数。gamultiobj 的应用实例如下

1 %% 1 、简单的多目标优化问题

2 % min y

3 % y (1) = ( x+2)^2 − 10 ;

4 % y (2) = ( x−2)^2 + 20 ;

5 % s ubj e c t to −1.5 <= x <= 0

7 % Plot two obj ec t i v e fu n cti o ns on the same ax is

8 x = −10: 0 . 5:10;

9 f 1 = (x+2).^2 − 10;

10 f 2 = (x−2).^ 2 + 20 ;

11 p l ot (x , f1 ) ; hold on ; pl o t (x , f2 , ’ r ’ ) ; gr id on ;

12 t i t l e ( ’ Plot of o b j e c t i v e s ’ ’ ( x+2)^2 − 10 ’ ’ and ’ ’ ( x−2)^2 + 20 ’ ’ ’ ) ;

13 %Minimizing Using gamultiobj

14 Fitnes sFuncti on = @( x ) ( ( x+2)^2 − 1 0; ( x−2)^2 + 20) ;

15 numberOfVariables = 1;

16 A = [ ] ; b = [ ] ;

17 Aeq = [ ] ; beq = [ ] ;

18 lb = −1.5;

19 ub = 0;

20 options = gaoptimset ( ’ PlotFcns ’ ,{ @gaplotpareto , @gap l ots c o red i vers i ty }) ;

21 [ x , Fval , exitF l ag , Output , Population , Score ] = gamultiobj ( FitnessFunction ,

numberOfVariables ,A, b , Aeq , beq , lb , ub , o p tions ) ;

22 s i z e ( x ) , s i z e ( f v a l )

23 %% 2 、向量化目标函数（ V ectorizin g Your Fitnes s Function ）

24 f u n c tion s co re s = v ectori z e d _multi o b j ectiv e ( pop)

25 popSize = s i z e ( pop , 1 ) ; % Population s i z e

http://www.ma-xy.com 45 http://www.ma-xy.com

http://www.ma-xy.com

1.2 遗传算法第一章智能优化

26 numObj = 2 ; % Number of o bj e c t i v es

27 % i n i t i a l i z e s c o r es

28 sc or e s = ze r os ( popSize , numObj) ;

29 % Compute f i r s t o bj e c t i v e

30 sc or e s ( : , 1 ) = (pop + 2) .^ 2 − 10 ;

31 % Compute second obecti v e

32 sc or e s ( : , 2 ) = (pop − 2) .^2 + 20 ;

33 end

34 Fitnes sFuncti on = @( x ) v e c torize d _ m ultiob j e c tive ( x ) ;

35 options = gaoptimset ( ’ Ve ctorized ’ , ’ on ’ ) ;

36 options = gaoptimset ( options , ’ PlotFcns ’ , @gaplotpareto ) ;

37 gamultiobj ( FitnessFunction , numberOfVariables , [ ] , [ ] , [ ] , [ ] , lb , ub , op t ions ) ;

38 %%3、多目标混合遗传算法

39 f u n c tion y = kur_multiobjective (x)

40 %KUR_MULTIOBJECTIVE O bjec tive functio n f o r a m ult i ob j ect i ve problem .

41 y = zer o s ( 2 ,1) ;

42 % Compute f i r s t o bj e c t i v e

43 f o r i = 1: 2

44 y (1) = y (1) − 10*exp(−0.2* s qrt (x( i )^2 + x( i +1)^2) ) ;

45 end

46 % Compute second o bj e c t i v e

47 f o r i = 1: 3

48 y ( 2 ) = y(2) + abs ( x( i ) ) ^0.8 + 5* s i n ( x ( i ) ^3) ;

49 end

50 Fitnes sFuncti on = @kur_multiobjective ;

51 numberOfVariables = 3;

52 lb = [−5 −5 −5];

53 ub = [5 5 5 ] ;

54 A = [ ] ;

55 b = [ ] ;

56 Aeq = [ ] ;

57 beq = [ ] ;

58 options = gaoptimset ( ’ PlotFcns ’ , @gaplotpareto ) ;

59 options = gaoptimset ( options , ’ DistanceMeasureFcn ’ ,{ @distancecrowding , ’ genotype ’ }) ;

60 options = gaoptimset ( options , ’ ParetoFraction ’ , 0 . 5 ) ;

61 options = gaoptimset ( options , ’TolFun ’ ,1 e−3, ’ StallGenLimit ’ , 150) ;

62 options = gaoptimset ( options , ’ HybridFcn ’ , @fgoalattain ) ;

63 % Reset the random s ta t e ( only to compare with pr evious run )

64 RandStream . getGlobalStream . State = Output . rn g state . s t a t e ;

65 options = gaoptimset ( options , ’ HybridFcn ’ , @fgoalattain ) ; % f g o a l a t t a i n hybrid functio n

66 % Provide i n i t i a l population and s c o r es

67 options = gaoptimset ( options , ’ I n i t i a l P o p u l a t i o n ’ , Population , ’ I n i t i a l S c o r e ’ , Score ) ;

68 [ x , Fval , exitF l ag , Output ] = gamultiobj ( FitnessFunction , numberOfVariables ,A, . . .

69 b , Aeq, beq , lb , ub , options ) ;

70 f p r i n t f ( ’The number o f point s on the Pareto fr o nt was : %d\n ’ , s i z e ( x , 1 ) ) ;

71 f p r i n t f ( ’The average dist a n ce measure of the s o l u t i on s on the Pareto fr o nt was : %g\n ’

, Output . a v e r a g e d i s t a n c e ) ;

72 f p r i n t f ( ’The spread measure of the Pareto f ro n t was : %g\n ’ , Output . spread ) ;

http://www.ma-xy.com 46 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.3 粒子群算法

1.3 粒子群算法

1.3.1 基本思想

粒子群算法 (PSO) 是智能优化中的群体智能优化，后继有蚁群、蜂群、鸡群等各种各样的

群体智能。值得一提的是，虽然 GA 等也是群体作战，但 GA 是基于进化思想的。PSO 最早由

Kennedy 和 Eberhart 于 1995 年提出，灵感来源于分类觅食行为：我们假设一只鸟为一个解，鸟

类觅食行为即是我们搜寻最优解的行为。一只鸟的位置即为解 x

，该位置上的食物是用适应度

衡量。该鸟也会有相应的速度 v

(速度是矢量)，x

会以速度 v

去寻找更多的食物。那么，我们

自然要考虑如何更新 v

。我们通过跟踪个体极值 pbest 和群体极值 gbest 来更新个体的速度。另

外，个体极值是个体 x

经过的最佳位置 x，群体极值是整个鸟群的最佳位置。

设鸟群共 m 只鸟 (粒子个数为 m)，优化变量个数为 n，第 i 只鸟表示为 x

= (x

, x

, ··· , x

) ∈

(i = 1, 2, ··· , n)，整个鸟群表示为 X ∈ R

m×n

= (x

, x

, ··· , x

)；每只鸟都有速度 v

∈ R

, v

, ··· , v

)，记整体速度为 V ∈ R

m×n

。假设有适当的适应度函数 f : R

→ R，则 n 只鸟

会有 m 个适应度。用 gbest 表示鸟群中适应度最高的个体位置，pbest

表示第 i 只鸟经过的最

佳位置，P best ∈ R

m×n

。用下列公式更新 X, V 。

k+1

= w · V

+ c

· r

· (P best

− X

) + c

· r

· (gbest

− X

)

其中：w, c

, c

∈ R 为常量，r

, r

∈ R 为随机量，gbest − X 表示 R

− R

m×n

k+1

= X

+ V

k+1

1.3.2 基本步骤

下面，给出 PSO 算法的基本步骤：

Step1: 初始化参数。

粒子群大小 m，变量个数 n，学习因子 c

, c

∈ R，惯性因子 w ∈ R，最大迭代次数 T

max

，

迭代次数 k := 1，粒子的初始位置矩阵 X

∈ R

m×n

，粒子的初始速度矩阵 V

∈ R

m×n

，各粒子

经历过的最佳位置矩阵 pbest

∈

m×n

，迭代过程中粒子群的最佳位置 gbest ∈ R

。

Step2: 计算粒子群的适应值

= f (X

) ∈ R

m×1

Step3: 更新 pbest

, gbest

。

对每个粒子，更新其 pbest

：如果 k 时的适应度更高，则更新其 pbest

，否则不变；对种群

更新其 gbest：如果 k 时种群中最佳适应度更高，则更新 gbest，否则不变。

Step4: 更新位置 X 和速度 V

k+1

= wV

+ c

(pbest

− X

) + c

(gbest

− X

)

k+1

= X

+ V

k+1

http://www.ma-xy.com 47 http://www.ma-xy.com

http://www.ma-xy.com

1.3 粒子群算法第一章智能优化

Step5: 终止条件：不终止，则置 k := k + 1，返回 Step2。

PSO 的 MATLAB 程序“可能”如下 (并没有运行测试)

1 %%基本的粒子群算法PSO

2 %初始化参数（输入）

3 m = 1 0 0 ;%粒子群大小

4 n = 5 ;%变量个数

5 c1 = 0 . 1 ;%学习因子

6 c2 = 0 . 1 ;%学习因子

7 w = 0 . 3 ;%惯性因子

8 t = 1;%迭代次数

9 Tmax = 200;%最大迭代次数

10 X = rand (m, n) ;%初始位置

11 V = rand (m, n)%初始速度

12 %预存空间（输出）

13 Fit = ze ros (m, n) ;%适应度

14 best_Fit = z e ros (Tmax, 1) ;%各代最佳适应度

15 mean_Fit = zero s (Tmax, 1) ;%各代平均适应度

16 Pbest = zer o s (m,n) ;

17 Gbest = z e ros (1 ,n) ;

18 whil e t <=Tmax

19 %1 、计算适应度

20 Fit_old = Fit ;%用于适应度比较（上一代适应度）

21 Fit = obj (X) ;

22 %2 、更新 Pbest 和 Gbest

23 i f t == 1

24 Pbest = X；

25 e l s e

26 Pbest ( Fit>Fit_old , : ) = X( Fit>Fit_old , : ) ;

27 end

28 [ best_Fit ( t ) , a ] = max( Fi t ) ;%记录该代种群中最大的适应度及其个体

29 Gbest = X(a , : ) ;

30 mean_Fit ( t ) = mean( F it ) ;

31 %3 、更新速度和位置

32 V = w*V + c1 *rand*( Pbest − X) + c2*rand ( Gbest − X) ;

33 X = X + V;

34 t = t + 1;

35 end

36 f i g u r e

37 polt ( best_Fit , ’ r−’ ) , hold on

38 plot ( mean_Fit , ’ c . ’ ) , hold o f f

39 xl a be l ’ 进化代数 ’ , yla b e l ’ 适应度 ’

40 legend ( ’ 最佳适应度 ’ , ’ 平均适应度 ’ )

1.3.3 PSO 改进策略

上面介绍的 PSO 只是最基本的粒子群算法的基本框架，像 GA 一样，PSO 也有许多可以改

进的地方：框架不变，量的改进；框架的改进。下面，我们介绍一些简单的 PSO 改进策略。在此

之后，有许多问题需要读者仿照 GA 来自行解决：约束问题、多峰问题、多目标问题、收敛性等。

http://www.ma-xy.com 48 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.3 粒子群算法

1). 权重 w 的改进：我们可以将 w 的计算公式改为如下几种形式，¬线性权重：

w = w

max

−

t(w

max

− w

min

)

max

通常 w

max

= 0.9, w

min

= 0.4。非线性权重：

w =











min

−



max

− wmin(f − f

min

)

avg

− f

min



f ⩽ f

avg

max

®随机权重：







w = µ + σ

∗

N(0, 1)

µ = µ

min

+ (µ

max

− µ

min

)rand

2). 学习因子 c

, c

的改进：¬同步学习因子

= c

max

−

max

− c

min

max

异步学习因子

= c

(0) +

(fin) − c

(0)

max

(0) +

(fin) − c

(0)

max

其中：可以设置 c

(0) = 2.5, c

(fin) = 0.5，c

(0) = 0.5, c

(fin) = 2.5。

3). 速度更新公式的改进：

(t + 1) = v

(t) + c

· rand

(pbest

− 2x

(t) + x

(t − 1))

· rand

(pgbest

− 2x

(t) + x

(t − 1))

1.3.4 PSO 工具箱

PSOt

PSOt 工具箱由美国 Brian Birge 教授开发。工具箱主要函数如表 (1.7) 所示

表 1.7: PSOt 工具箱函数表

函数名称函数功能函数名称函数功能

goplotpso 绘图函数 Normmat 格式化矩阵数据函数

pso_Trelea_vectorized 从粒子群优化主函数 linear_dyn,spiral_dyn 时间计算函数

forcerow.m,forcecol 向量转化函数

该工具箱的主要函数是 pso_Trelea_vectorized，其调用格式为

[optOUT, tr, te] = P SO_Trelea_vectorized(functname,D,mv,VarRange,minmax,PSOparams,plotfcn,

http://www.ma-xy.com 49 http://www.ma-xy.com

http://www.ma-xy.com

1.3 粒子群算法第一章智能优化

PSOseedValue)。其中：functname 为目标函数；D 为自变量维数；mv 为最大速度取值范围；Var-

Range 为 x 取值范围；minmax 表示待优化问题的类型，取值为 0 时表示最小优化，取值为

1 时表示最大优化问题，取值为 2 时表示寻找目标值与 PSOparams 中的第 12 个参数最接近；

PSOparams 是一个 13 维的数组，例如：[100,2000,24,2,2,0.9,0.4,1500,1e-25,250,NaN,0,0]，100 表

示每迭代 100 次，在窗口显示一下结果；2000 表示最大迭代次数；24 为个体数；2,2 为加速度参数；

0.9 表示 w(begin)；0.4 表示 w(end)；1500 表示当迭代次数超过此值时，w 取 w(begin), w(end)

中的小值；1e-25 表示连续两次迭代过程中，最优值变化的终止界；250：连续 250 次迭代中函数

梯度无变化则终止；NaN 表示优化问题是否有约束条件；0 表示粒子群算法类型；0 表示初始化

时是否采用指定的随机种子，取值 0 时表示随机产生种子，取值 1 时表示用户自定义种子。

用 PSOt 求解引例 1(1.1) 的程序如下

1 f u n c tion z=test_func ( in )

2 nn=s i z e ( i n ) ;

3 x=in (: , 1 ) ;

4 y=in (: , 2 ) ;

5 nx=nn ( 1 ) ;

6 f o r i =1:nx

7 temp = y ( i ) * s in (2* pi *x( i ) ) + x( i ) * cos (2* pi *y( i ) ) ;

8 z ( i , : ) = −temp ;

9 end

10 end

11 %% 用PSOt求解 “ 智能优化引例 ”

12 % max f (x , y )=y* s in (2* pi *x)+x* cos (2* pi *y)

13 % s . t.−0.5<=x<=3.5; −2<=y<=3;

14 % 参数初始化

15 c l c , c l e a r

16 x_range=[ −0.5 , −2]; % 参数 x 变化范围

17 y_range = [ 3 . 5 ,3 ] ; % 参数 y 变化范围

18 range = [ x_range ; y_range ] ; % 参数变化范围 ( 组成矩阵 )

19 Max_V = 0 .2* ( range ( : , 2 )−range ( : , 1 ) ) ; % 最大速度取变化范围的 10%~20%

20 n = 2; % 待优化函数的维数，此例子中仅x 、 y两个自变量，故为 2

21 PSOparams = [2 5 2000 24 2 2 0.9 0 . 4 1500 1e−25 250 NaN 0 0 ] ;

22 % 粒子群寻优

23 pso_Trelea_vectorized (@PSOt_func, n ,Max_V, range , 0 , PSOparams) % 调用PSO核心模块

MATLAB 自带的 PSO 工具箱

MATLAB 自带的用于 PSO 的目标函数有 rastringinsfcn 和 multiwsembrack，可以使用 help

particleswarm 命令来查看帮助。目前为止，MATLAB 提供的用于 PSO 的函数命令有：PSO.m，

psocreationuniform.m，psoptimget.m，psoptimset.m，psoutputfcntemplate.m，psoutputle.m，

psolotbestf.m，psplotbestx.m，psplotfunctrent.m，psplotmaxconstr.m，psplotmeshsize.m，Ran-

dormStartPointSet.m。

Matlab 中用 particleswarm 函数实现 PSO 算法，用其求解引例 1(1.1) 的程序如下

1 %% matlab 自带的PSO求解 “ 智能优化引例 ”

2 % max f (x , y )=y* s in (2* pi *x)+x* cos (2* pi *y)

http://www.ma-xy.com 50 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.4 蚁群算法 ACA

3 % s . t.−0.5<=x<=3.5; −2<=y<=3;

4 c l c , c l e a r

5 f i t n e s s f c n = @(x) −(x( 1 ) * cos (2* pi *x( 2 ) ) + x(2) * s i n (2* pi *x (1) ) ) ;% 适应度函数句柄

6 nvars = 2 ;% 个体的变量数目

7 lb = [ −0.5 , −2];

8 ub = [ 3 . 5 , 3 ]

9 options = optimoptions ( ’ particleswarm ’ , ’ MinNeighborsFraction ’ , 1 ) ;

10 options . SwarmSize = 200;%粒子群大小

11 options . SelfAdjustmentWeight = 1 . 9 ;

12 x0 = ze r o s ( 0 ,0 ) ;

13 options . InitialSwarmMatrix = x0 ; %初始点

14 options . UseVectorized = true ;%向量化

15 options = optimoptions ( options , ’ PlotFcn ’ , @pswplotbestf ) ;

16 options . HybridFcn = @fmincon ;%混合粒子群（PSO+fmincon ）

17 [ x , fval , e x i t f l a g , output ] = particleswarm ( f i t n e s s f c n , nvars , lb , ub , options ) ;

1.4 蚁群算法 ACA

1.4.1 基本思想

PSO 的灵感来源于鸟群觅食。下面，我们再来介绍一种群体智能优化算法-蚁群算法 (ACA)。

蚁群算法来源于蚂蚁觅食活动，Goss.S 等曾于 1989 年做过著名的“双桥”实验，发现如果有两

条蚂蚁通径食物的路线，经过一定时间后，蚂蚁都使用短路径去寻找食物。这与我们寻找最短路

径以及寻优问题的目标不谋而合，因此，ACA 算法被发展用来解决 TSP 等路径问题。蚁群算法

(ant colong algorithm) 由意大利学者 M.Dorigo 等人于 20 世纪 90 年代初提出，用于解决 TSP

问题，并取得了较好的结果。

ACA 的基本思想：用蚂蚁走过的路径表示待优化问题的可行解，整个蚂蚁群体的所有路径

构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径

上积累的信息素浓度逐渐增高，选择给路径的蚂蚁个数也愈来愈多，最终收敛到最短路径。

1.4.2 抽象描述

设共有 n 个城市 (i = 1, 2, . . . , n)，第 i, j 个城市之间的距离为 d

。我们要求从出发城市 1

开始，走遍所有城市且每个城市仅走一遍，最后回到出发城市 1 的最短路径。设蚂蚁种群大小为

m，变量个数 (城市数) 为 n，第 i 个蚂蚁的路径记为 x

= (x

, x

, . . . , x

)，x

即为一条可行的

行走路线。就个体 k 而言，如果我们已经知道了个体 k 的第 i 个城市，如何确定第 i + 1 个城

市 j 呢？当然，我们的选择必须依据目前城市 i 和可选城市 j 之间的距离 d

，此外，我们也必

须依据前蚂蚁留下来的信息。设 t 时刻 i, j 城市之间的信息素为 τ

(t)，蚂蚁 k 要依据 d

(t) 和

http://www.ma-xy.com 51 http://www.ma-xy.com

http://www.ma-xy.com

1.4 蚁群算法 ACA 第一章智能优化

(t) 来决定第 i + 1 个城市 j。以 p

(t) 表示 t 时刻，蚂蚁 k 从 i 转移到 j 的概率











[τ

(t)]



(t)





s∈allow

[τ

(t)]



(t)



s ∈ allow

0 s /∈ allpw

其中：allow

中包含 n −1 个元素，包含除蚂蚁 k 出发城市以外的其他所有城市；α, β 为常量。

当然，在蚂蚁释放信息素 τ

的同时，各城市路径上的信息素也在消失。设参数 ρ 表示信息

素挥发程度，因此，当所有蚂蚁完成一次循环后，各城市上的信息素要更新

(t + 1) = (1 − ρ)τ

(t) + ∆τ

∆τ



k=1

∆τ

其中：∆τ

表示第 k 个蚂蚁在城市 i, j 路径上释放的信息素量。对于 ∆τ

的计算，M.Dorigo 等

人提出了三种不同的计算方法:

¬ant cycle system

∆τ







Q/L

第 k 只蚂蚁走过 i 到 j

其中：Q 为常量，L

表示第 k 只蚂蚁经过的路径长度。

ant quantity system

∆τ







Q/d

®ant density system

∆τ







一般而言，选择¬是恰当的，因为蚂蚁 k 更过的路径 L

越短，则释放的信息素量越大。

1.4.3 基本步骤

下面给出 ACA 解决 TSP 问题的算法步骤：

Step1: 初始化

。

蚁群规模 m，城市数量 n，初始蚁群 X

∈ R

m×n

，初始信息素矩阵 τ

(0) ∈ R

n×n

，参数

α, β, ρ, Q，城市距离矩阵 d = (d

)

n×n

，最大迭代数 T

max

，迭代数 t := 1。

注意：我们可能要求起点是固定的。

http://www.ma-xy.com 52 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.4 蚁群算法 ACA

Step2: 从第 t 代开始，每个蚂蚁 x

开始走。蚂蚁 x

从一个城市 i 转移到下一个城市 j 的概率

(t) 与 i, j 的距离 d

以及信息素 τ

(t) 有关。

Step3: 当所有蚂蚁走完所有城市 n 时，计算各蚂蚁经过的路径长度 L

，记录 t 代的最优解。

Step4: 更新信息素

(t + 1) = (1 − ρ)τ

(t) + ∆τ

∆τ



k=1

∆τ







Q/L

Step5: 终止条件。不终止，则置 t := t + 1 返回 Step2.

注 1：在求解概率 p

之后，如何根据概率 p

选择城市？方法：¬轮盘赌随机概率®最大

概率。注 2：在每时间 t，一个蚂蚁先完成 n 次行走后，再另一只蚂蚁走。

ACA 的时间复杂度

对 n 维的 TSP 问题，m 为蚁群大小，循环变量为 t，最大循环次数为 T

max

，我们可以逐

步分析出其时间复杂度：Step1 中，初始化参数的时间复复杂度为 O(n

+ m)；Step2 中，每

只蚂蚁单独构造解的时间复杂度为 O(n

m)；Step3 中，解的评价和轨迹更新量的计算 O(n

n)；

Step4 中，信息素更新的时间复杂度为 O(n

)；Step5 中，判断是否终止的时间复杂度为 O(nm)。

当 n 足够大时，低次幂的影响可以忽略不计，基本蚁群算法中 m 只蚂蚁遍历 n 个城市，经过

max

次循环，则整个 ACA 的时间复杂度为 T (n) = O(T

max

m)。基本蚁群算法的空间复杂度

为 S(n) = O(n

) + O(nm)。由此可见，基本蚁群算法是易于存储易于实现的。

ACA 的性能评价指标

为了较全局分析 ACA 的优劣程度，引入下面 3 个基本的评价指标：

(1) 最佳性能指标

定义相对误差 E

为最佳性能指标

− C

∗

× 100%

其中：

表示算法多次运行所得到的最佳最优值，

∗

表示所求问题的理论最佳值。

(2) 时间性能指标

定义时间性能指标 E

为

max

× 100%

其中：I

表示算法多次运行后，满足终止条件时的迭代次数平均值；I

max

表示给定的最大迭代

次数，T

表示算法一次迭代的平均计算时间。

http://www.ma-xy.com 53 http://www.ma-xy.com

http://www.ma-xy.com

1.4 蚁群算法 ACA 第一章智能优化

(3) 鲁棒性能指标

定义基本蚁群算法的鲁棒性能指标 E

如下

− C

× 100%

其中：C

表示算法多次运行所得的最佳值的平均值，C

表示理论最佳值。

此外，还可以构造上述 3 个指标的加权形式

E = w

+ w

E 越小则算法的综合性能越好。

1.4.4 ACA 改进策略

(1) 自适应挥发因子 ρ(t)：ρ(t

) = 1，当求得最优解在 N 次循环内无明显变化时，ρ 进行改

变

ρ(t) =







0.95ρ(t − 1)

min

(2) 多蚁群模式 PACA：在基本蚁群中增设侦察蚁和工蚁。¬侦察蚁：

Step1: 将 n 个侦察蚁放在 n 个策划功能是中，侦察其他 n −1 个城市，构成侦察素











若 j 在 i 的侦察范围内

其中：

表示以城市 i 为中心，到其他 n −1 个城市的最小距离。

Step2: 初始化信息素

(0) =











if S

= 0

else if

其中：

表示以城市 i 为中心，到其他 n

个城市的最大距离，C 为初始时刻各路径上的信息素

量。

搜索蚁：蚂蚁 k 在 t 时刻从 i 到 j 的概率为 p

，信息素调整

(t + 1) =







ρτ

(t) + (1 − ρ)∆τ

if S

= 0

ρτ

(t) else if

∆τ



k=1

∆τ

表示第 k 蚂蚁在本次循环中，在路径 i 到 j 上的信息量，其中

∆τ











)

k过ij且S

= 0

http://www.ma-xy.com 54 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.4 蚁群算法 ACA

1.4.5 连续域蚁群算法

上面介绍的蚁群算法 ACA 是用于求解 TSP 等组合优化问题的基本蚁群算法，那么，我们

应该如何将其引入到函数优化问题中呢？下面，我们就来介绍连续域中的蚁群算法。

Bilchev 等最早将 ACA 应用到连续函数优化问题当中，先用 GA 算法对解空间进行全局搜

索，然后再利用 ACA 算法对所得到的结果进行局部优化。高尚等提出一种基于网格划分策略的

连续域蚁群算法。Li Y J 等提出一种用于求解连续域优化问题的自适应蚁群算法。陈等提出一种

基于交叉变异操作的连续域蚁群算法。Dreo J 等提出一种基于密集非逆的连续交互式蚁群算法

(CIACA)，该算法通过修改信息素的留存方式和行走规划，并运用信息素交流和直接通信两种方

式来指导蚂蚁寻优。张勇德提出用于求解有约束条件的多目标函数优化问题的连续域蚁群算法。

网格划分策略

要将 ACA 算法直接引入到连续域当中近乎是不可能的，因为对于蚂蚁 k，我们在知道其当

前位置 x

值，要想办法决定它下一个位置，但是由于问题的连续型，下一个位置会有无穷多个。

这使得问题难以解决。一种可行的方法是将连续区域进行划分，这样，原本的无穷就变为有限，

我们在各网格点上求约束函数和目标函数值，对于满足约束条件的点，再比较其目标函数的大小，

并留下信息量，每个网格点对应一个状态。蚂蚁在各网格点之间移动。循环一段时间后，相邻节

点间的目标函数差值小的网格点信息量比较大，然后找出信息量大的空间网格点，并给小变量范

围，在此点附近进行蚁群移动，不断重复这一过程，直到收敛。

嵌入确定性搜索

对连续域优化问题，设有 m 只蚂蚁随机分布在定义域内，每只蚂蚁都有一个邻域 B(x

, r)，

每只蚂蚁在自己的邻域内进行搜索，当所有蚂蚁完成局部搜索后，蚂蚁个体根据信息素强度和启

发式函数在全局范围内进行移动。

全局搜索设 Act(i) 为第 i 只蚂蚁选择的动作，f avg 为 m 只蚂蚁的目标函数平均值，则有

Act(i) =







全局搜索当f(x

) > f avg, q < q

s 否则

其中：0 < q < 1, 0 < q

< 1，S 按如下规则选择动作

p(i, j) =

−d



−d

其中：d

= f (x

) − f(x

)，且当 i = j 时 d

> 0，当 i = j 时 d

= 0。

上述公式保证了第 i 只蚂蚁按概率在其它目标函数值更小的蚂蚁 j 的邻域移动。蚂蚁向某个

信息素高的地方移动时，可能随机发现新的食物源，第 i 只蚂蚁向第 j 只蚂蚁的邻域移动的公式

为







的邻域取随机值 ρ ⩽ ρ

αx

+ (1 −α)x

http://www.ma-xy.com 55 http://www.ma-xy.com

http://www.ma-xy.com

1.5 模拟退火 SA 第一章智能优化

信息素更新全局搜索结束后，如果有 n 只蚂蚁向蚂蚁 j 处移动，则有

τ(j) = βτ (j) +



i=1

∆τ

其中：∆τ

= 1/f (x

)，0 < β < 1。

确定性搜索我们在局部搜索过程中引入确定性搜索。确定性搜索包括：网格法、模式搜索法、

坐标轮换法。搜索规则为：如果 v < v

，则用确定性搜索方法进行局部搜索，否则饭随机搜索方

法进行搜索。下面给出嵌入确定性搜索的蚁群算法:

Step1: 初始化。

Step2: 在第 t 次迭代中，每只蚂蚁进行局部搜索，直到所有蚂蚁完成局部搜索。

Step3: 每只蚂蚁进行全局搜索。按上述方法选择要进行的动作，直到所有蚂蚁完成全局搜索。

Step4: 更新信息素。

Step5: 终止条件，否则置 t := t + 1 返回 Step2.

1.5 模拟退火 SA

1.5.1 基本思想

模拟退火算法 (SA) 最早由 Metropolic 等于 1953 年提出，1983 年 Kirkpa trick 等奖 SA 应

用到组合优化问题当中。SA 算法是基于 Mente Carlo 迭代求解策略的一种随机寻优算法。在某

一初始温度下，伴随温度的不断下降，结合概率在解空间随机的寻找目标函数的全局最优解，即

使在局部最优解出，也可以以一定的概率逃离。

模拟退火算法源于固体退火原理，将固体加温至充分高，再让其逐渐冷却，加温时，固体内

部的粒子随升温而变为无序状，内能增大，而冷却时粒子渐渐趋于有序，每个温度都达到平衡状

态。最后，在常温时达到基态，内能减小到最小。根据 Metropolis 准则，在温度 T 时，粒子区域

平稳的概率为 exp(−∆E/kT )，其中 E 为温度 T 时的内能，∆E 为内能改变量，k 为 Bortzmann

常数。很明显，在优化问题中，内能 E 代表目标函数，我们要使内能足够小。

加温过程对应初始高温，等温过程对应在某个温度下的 Metropolis 采样，冷却过程代表温

度下降过程。

1.5.2 基本步骤

SA 的一般步骤如下

Step1. 初始化。初始温度 T ，终止温度 T

end

，Metropolis 抽样次数 L，迭代次数 t := 0。

Step2. 对当前温度 T ，和 k = 1, 2, . . . , L，运行 Step3-Step5.

Step3. 对当前解 x

随机扰动产生一个新解 x

Step4. 计算内能增量 ∆E = f (x

) − f(x

)。

Step5. 判断是否接受新解 x

。如果 ∆E < 0，则接受新解 x

；否则，以概率 exp(∆E/T ) 接受

http://www.ma-xy.com 56 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.5 模拟退火 SA

。

Step6. 终止条件。若连续若干个 Metropolis 链中 x

都没有接受，则终止，或者在 T

end

终止；

否则，置 t := t + 1 转到 Step2.

SA 的伪代码如 (2) 所示

算法 2 模拟退火算法 SA

1: 初始化：T, T

end

, L, t。

2: while T > T

max

3: t = t + 1

4: for k = 1 : L do

5: 扰动函数 F

产生新解 x

= F

)；f

= f(x

), f

= f(x

)；计算内能变化量

∆E = f

− f

。

6: 判断是否接受新解 x

：如果 ∆E < 0，则接受新解；否则以概率 exp(∆E/T ) 接受 x

。

7: end for

8: 找到 L 次采样中的最优解，标记为温度 T 下的解。

9: 判断是否接受 T 时刻的目标值。如果当前温度 T 的最优值小于上一最优值，则接受当前

温度的最优值。

10: T

= F

)，F

为降温函数。

11: end while

下面讨论算法中的扰动函数 F

，降温函数 F

。¬扰动函数 F

应该尽可能保证产生的候选

解遍布全部解域，候选新解的产生方式由问题的性质决定，通常在当前解的邻域内，以一定概率

方式产生。比较常用的降温函数为 T

k+1

= αT

，其中，0 < α < 1 为降温系。

1.5.3 SA 工具箱

ASA 自适应模拟退火工具箱

ASA 包由美国学者 Lester Ingber 编写，使用时应该标明出处 LIR(Lester ingber resarch)。

ASA 包可以在 LI 的主页

上下载。ASA 包用 C 语言编写，Shinichi Sakata 编写 ASA 对 MATLAB

接口 ASAMIN

。

ASA 安装步骤：¬运行 MATLAB 语句 mex - setup 将 ASA 中的 asa.c,asa.h,asa_usr_asa.h

复制到 ASAMIN 所在文件夹；®在 cmd 中输入

1 cd E: \ work\asamin

2 %MATALB%\bin \win32\mex asamin .c_DUSER_ACCEPTANCE_TEST#TRUE − DUSER_ASA_OUT#TRUE

¯在 MATLAB 中运行

http://www.ingber.com

http://econ.arts.ubc.ca/ssakata/public-html/software/下载

http://www.ma-xy.com 57 http://www.ma-xy.com

http://www.ma-xy.com

1.5 模拟退火 SA 第一章智能优化

1 cd E: \ work\asamin

2 as a te st

°移动 ASAMIN 的 mex 文件 (asamin.dll) 和 asamin.m 到 MATLAB 的搜索目录下完成安装。

MATLAB 自带的 SA 工具箱

MATLAB 中使用 simulannealbnd 函数来实现模拟退火算法，其调用格式为

[x,fval,exitag,output] = simulannealbnd(fun,x0,lb,ub,options)

模拟退火可用于处理无约束或边界约束的优化问题，且不要求函数连续或可微。SA 可以实

现自适应模拟退火、boltzmann 退火和快速退火。并且可以自定义退火过程、接受准则和温度函

数等。亦可以实现混合模拟退火，可以用 optimtool(’simulannealbnd’) 打开 GUI。SA 工具箱中

有的函数如表 (1.8) 所示

表 1.8: SA 函数表

函数文件用途

sanewpoint.m 扰动函数，产生新解

annealingfast.m 退火函数

sahonorbounds.m 界限约束

acceptancesa.m 接受新解的准则

saupdates.m 对迭代次数、最优解、温度的更新

temperatureexp.m 降温函数

此外还有函数：saacceptancefentempate.m，saannelingfcntemplate.m，saoptionget.m，saop-

tionset.m，saoutputfcntemplate.m，saplotbestf.m，saplotbestx.m，saplotf.m，saplotstopping.m，

saplottermperature.m，saplotx.m，satemperaturecntemplate.m，satooloutput.m。

MATLAB 自带的 SA 工具箱求解引例 1(1.1) 的程序如下

1 %% matlab 自带的SA求解 “ 智能优化引例”

2 % max f (x , y )=y* s in (2* pi *x)+x* cos (2* pi *y)

3 % s . t.−0.5<=x<=3.5; −2<=y<=3;

4 c l c , c l e a r

5 f i t n e s s f c n = @(x) −(x( 1 ) * cos (2* pi *x( 2 ) ) + x(2) * s i n (2* pi *x (1) ) ) ; % 适应度函数句柄

6 nvars = 2 ;% 个体的变量数目

7 lb = [ −0.5 , −2];

8 ub = [ 3 . 5 , 3 ] ;

9 options = optimoptions ( @simulannealbnd , ’ Initial T e m p erature ’ ,[3 0 0 5 0] ) ;

10 options = saoptimset ( options , ’ PlotFcns ’ ,{ @sap lotbe stf , @saplottemperature , @saplotf ,

@saplotstopping }) ;

11 options . In itialTempera t u r e = 1 0 0;

12 options . TemperatureFcn = @temperaturefast ;

13 options . Reann ealIn terva l = 50;

14 x0 = ze r o s ( 0 ,0 ) ;

15 options . InitialSwarmMatrix = x0 ; %初始点

http://www.ma-xy.com 58 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.6 其他智能优化算法

16 options . HybridFcn = @fmincon ;% 混合粒子群（SA+fmincon ）

17 [ x , fval , e x i t f l a g , output ] = particleswarm ( f i t n e s s f c n , nvars , lb , ub , options )

1.6 其他智能优化算法

1.6.1 鱼群算法 AFSA

Articial Fish Swarm Algorithm(AFSA) 是李晓磊于 2002 年博士论文提出的一种智能优化

算法。AFSA 步骤如下：

Step1. 初始化参数。

鱼群大小 N，变量维数 m，鱼群状态矩阵 X ∈ R

N×m

，鱼群适应度 Y ，最大迭代次数 t

max

，

迭代次数 t，感知距离 v，拥挤度 δ，移动步长 d；迭代过程中的最大解记录 bestX ∈ R

max

×m

，

bestf ∈ R

max

×1

，当前觅食次数 n。

Step2. 觅食行为 prey。

人工鱼 x

在其感知范围内随机选择一个状态 x

，如果 f (x

) < f(x

) 则 x

向 x

方向移动

一步；否则，在重新选择一个 x

。在尝试 try_number 次后，仍不前进的话，则随机移动一步。

Step3. 聚群行为 Swarm。

搜索当前领域内 (d

< d) 的鱼数目 n

以及中心位置 X

center

。如果

center

> δY

，x

向

center

移动一步；否则执行觅食行为 Step2.

Step4. 追尾行为 follow。

搜索当前邻域内的伙伴数 n

，及 Y

best

, X

best

(可搜索的最优值)。如果

best

> δY

，则 x

向 x

移动一步；否则执行觅食行为 Step2.

Step5. 随机行为 rand.

在视野中随机选择下一个状态，然后移动。

1.6.2 萤火虫算法 GSO

GSO 的算法流程如下：

Step1. 初始化参数。

萤火虫群大小 N ，变量维数 m，迭代次数 t，最大迭代数 t

max

，荧光素挥发系数 ρ，萤光素

增强因子 γ，移动步长 s，领域变化率 β，邻域阈值 n

；初始荧光素 l

，初始决策半径 r

，初始

种群 X ∈ R

N×m

，初始值 Y ∈ R

N×1

，bestx, besty, meany。

Step2. 计算 t 次迭代时，萤火虫的荧光素值。

(t) = (1 −ρ)l

(t − 1) + γy

Step3. 对萤火虫 x

创建邻域集 N

(t)。

Step4. 计算萤火虫 x

向邻域 N

(t) 中的 x

移动的概率 p

。

http://www.ma-xy.com 59 http://www.ma-xy.com

http://www.ma-xy.com

1.6 其他智能优化算法第一章智能优化

Step5. 利用轮盘赌选择萤火虫 x

，再更新 x

的位置

(t + 1) = x

(t) + s

− x

||x

− x

Step6. 更新萤火虫 x

的感知半径

(t + 1) = min







max{0, r(t) + β(n −|N

(t)|}

Step7. 终止条件。

1.6.3 萤火虫算法 FA

FA 在模拟萤火虫的行为时，引入亮度和吸引度的概念。亮度是由人工萤火虫对应的位置的

目标决定的，而吸引度是用以表示移动的距离。萤火虫之间的相对亮度、吸引度都与距离成反比，

通过更新亮度和吸引度来间接控制萤火虫的移动方向与移动距离。如此反复进行，实现最优问题

的求解。

算法的步骤如下：

Step1. 初始化参数。

萤火虫种群大小 N，变量个数 m，迭代数 t，最大迭代数 t

max

，步长因子 s ∈ [0, 1]，最大吸引

度 β

，光强吸收系数 γ，初始种群 X ∈ R

N×m

，初始值 Y ∈ R

N×1

, I

= Y ，bestx, besty, meany。

Step2. 对个体 x

，计算 x

对 x

的吸引度即相对亮度

β = β

−d

I = I

−r

Step3. 利用吸引度和相对亮度确定 x

移向个体 x

。

方法 1：随机在 I, β 中挑选；方法 2：结合 I, β；方法 3：轮盘赌。

Step4.x

位置的更新

(

−

) +

(

rand

−

α = α

Step5. 终止条件。

1.6.4 蝙蝠算法 BAT

蝙蝠算法由 Tang.X.S 开发，其算法流程如下：

Step1. 初始化参数。

蝙蝠种群大小 N ，变量个数 m，迭代次数 t，最大迭代次数 t

max

，最大脉冲频率 Q

max

，最

小脉冲频率 Q

min

；初始脉冲响度 A

= 0.5，脉冲下降程度 α = 0.9，初始发射速度 r

= 0.5，

r = 0.9，X ∈ R

N×m

, Y ∈ R

N×1

，bestx, besty, meany。

http://www.ma-xy.com 60 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.6 其他智能优化算法

Step2. 对每个个体 x

，更新位置

= Q

max

+ (Q

max

− Q

min

)rand

= v

+ (x

− x

∗

其中：x

∗

为当前全局最优解。

= x

+ v

Step3. 再生成一个新解 x

。如果 rand > r(i)，则 x

= x

+ εA(i)。

Step4. 判断使用 x

还是 x

。如果 rand < A(i) 并且 y

< y

，则使用 x

。

Step5. 更新 A(i), r(i)。

A(i) = αA(i)

r(i) = r(i)[1 − exp(−γt)]

Step5. 终止条件。

1.6.5 布谷鸟算法 CUCKOO

布谷鸟算法步骤如下：

Step1. 初始化参数。

CS 种群大小 N(鸟巢)，变量个数 m，迭代次数 t，最大迭代次数 t

max

，劣解删除概率 p，初

始步长 α

；X ∈ R

N×m

, Y ∈ R

N×1

，bestx, besty, meany。

Step2. 对于每个鸟巢 x

，利用莱维分布来更新位置。for i = 1 : N ：

= x

+ αLevy(β)

α = α

− X

best

(t))

Levy (β) =

ϕu

|v|

ϕ =







Γ(1 − β) sin(πβ/2)



[

1+β

]β2π

β−1









u, v

∼

β = 1.5

= f (x

)

Step3. 判断是否保留 x

。如果 y

< y

则保留。

Step4. 将种群 X 的一些劣质解以概率 p 随机丢弃，并用偏好随机游动残生新解代替丢掉的解。

Step5. 终止条件。

http://www.ma-xy.com 61 http://www.ma-xy.com

http://www.ma-xy.com

1.6 其他智能优化算法第一章智能优化

1.6.6 蜂群算法 ABC

Articial Bee Colony(ABC) 算法由 Karabogce 等于 2005 年为优化代数问题提出，其基本

流程如下：

Step1. 初始化。

蜂群大小 N，变量个数 m，迭代次数 t，最大迭代次数 t

max

，不更新限度 limit，；X ∈

N×m

, Y ∈ R

N×1

，bestx, besty, meany。

Step2. 对每只蜜蜂 x

为蜜蜂 i 的位置)，在 x

附近找到一个新的位置 x

，并计算其花蜜量

(越大越好)，并判断是否保留 x

(如果花蜜量 y

> y

，则保留 x

)。

Step3. 在所有 x

都完成遍历后，依据 y

的大小选择一个 x

作为更新对象。

//Step4. 在 N 次随机选择的过程中，对位置 x

进行计分：如果 x

更新 1 次，分数 C(i) 增加

1。N 次循环结束后，对 C(i) < limit 的个体 x

丢弃，并在解空间中随机生成一个新解来代替。

Step5. 对每个解 x

，如果在 limit 次迭代过程中 x

未改变，记录 x

，并将 x

变为 rand。

Step6. 终止条件。

1.6.7 蛙跳算法 SFLA

蛙跳算法由 Eus 和 Lansey(2003) 为解决组合优化问题提出。种群由很多青蛙组成，每只青

蛙代表一个解，种群被分为多个子群，每个子群包括一定数量的青蛙，称为一个 memeplex。不

同 memeplex 可以看作是具有不同文化的青蛙群，分别执行局部搜索。在每个 memeplex 中，每

只青蛙都有自己的想法，并且受其它青蛙的影响。通过 memetic 进化来发展，这样经过一定的

memetic 进化以及跳跃过程，这些想法思路就会在各个 memeplex 中传播开来，然后，继续局部

搜索和跳跃，直到终止。SFLA 的算法步骤如下：

Step1. 初始化参数。

种群大小 N ，变量个数 m，迭代次数 t，最大迭代次数 t

max

，子种群数目 nC，子种群最大

迭代次数 Ct

max

，子种群迭代次数 Ct；X ∈ R

N×m

, Y ∈ R

N×1

，bestx, besty, meany。

Step2. 计算 X 的适应度 Y ，依据 Y 对种群个体进行排序，并记录最优个体。

Step3. 将排序后的 X

sort

分成 nC 个子群。

Step4. 对每个子群 Xchild 进行进化 (局部搜索)。

4.1：找到子种群 Xchild(i) 的最优个体 P b 和最差个体 P w；

4.2：更新最差个体

D = rand(P b − P w)

P w

= P w + D

4.3：判断是否接受 P w

。不接受时，再次更改 P w

D = rand(P g − P w)

P w

= P w + D

4.4：判断是否接受 P w

。不接受时，随机生成 P w 来替代原来的 P w。

http://www.ma-xy.com 62 http://www.ma-xy.com

http://www.ma-xy.com

第一章智能优化 1.6 其他智能优化算法

4.5：判断是否终止。未终止则返回 4.1。

Step5. 将子种群 Xchild 重新合并为 X，并计算 Y 。

Step6. 终止条件。

http://www.ma-xy.com 63 http://www.ma-xy.com