当前位置:首页 >> 机械/仪表 >>

离散二进制粒子群算法分析


DOI:10.13232/j.cnki.jnju.2011.05.002

第4 7卷   第5期 V o l . 4 7,N o . 5    J OUR NA L O F NAN J I NG  UN I V E R S I T Y         2 0 1 1年9月 S e t .2 0 1 1 p ? ( ) NATUR A L S C I E N

C E S  

南京大学学报 ( 自然科学 )

离散二进制粒子群算法分析
* , 刘建华* 杨荣华 , 孙水华



( ) 福建工程学院计算机与信息科学系 , 福州 , 3 5 0 1 0 8 , 摘   要: 主要用优化计算实值的连续性问题 , 而离散 P a r t i c l e S w a r m  O t i m i z a t i o n P S O)   粒子群算法 (   p , 它扩展了 二进制 粒 子 群 算 法 ( B i n a r P a r t i c l e S w a r m  O t i m i z a t i o n B P S O)则 用 来 优 化 离 散 空 间 问 题 ,   y p   现已广泛应用到各种离散优化问题计算中 , 但目前对 B P S O 算法的应用 , P S O 算法的理论分析 研 究 还 很 少, 难以指导算法性能 . 本文从位改变概率和遗传算法的模式定理两方面对 B 分析得出, P S O 进行分析. 但不能收敛于粒 子 的 全 局 最 优 位 置 , 而且随 着 算 法 迭 代 运 行, B P S O 算法具有很强全局搜索能力 , B P S O 的随机性越来越强 , 缺乏后期的局部搜索能力 . 本文利用基准的函数 , 通过仿真实验计 算 , 验证本文的分 析结果 . 基于分析的结果 , 本文提出 B 新方法采用新的概率映射函数和混合遗传算法 P S O 的改进方 法 , 通过对基准函数的仿真试验 , 验证了改进方法的有效性 . 的方法 . 关键词 : 收敛性 , 位改变概率 , 模式定理   二进制粒子群算法 , 中图分类号 : P 1 8  T  

T h e a n a l s i s o f b i n a r a r t i c l e s w a r m o t i m i z a t i o n           y y p p  
L i u J i a n- H u a, Y a n R o n H u a, S u n S h u i- H u a     g  g-
( , , , ) D e a r t m e n t o f C o m u t e r a n d I n f o r m a t i o n S c i e n c e F u i a n U n i v e r s i t o f T e c h n o l o F u z h o u 3 5 0 1 0 8, C h i n a               p p j y g y   : A b s t r a c t a r t i c l e S w a r m  O t i m i z a t i o n( P S O) i s a n e v o l u t i o n a r c o m u t a t i o n i n s i r e d b s w a r m i n t e l l i e n c e .  P             p y p p y g     , C o m a r e d t o o t h e r e v o l u t i o n a r c o m u t a t i o n a l o r i t h m s P S O c a n n o t o n l s o l v e a v a r i e t o f d i f f i c u l t o t i m i z a t i o n                       p y p g y y p       , r o b l e m, b u t a l s o i s e a s e t o b e u s e d . S o P S O h a v e b e e n u s e d a c r o s s a w i d e r a n e o f a l i c a t i o n s . B u t P S O i s m a i n l                                     p g p p y , a l i e d i n t h e a r e a o f c o n t i n u o u s s a c e a n d r a r e l i n t h a t o f d i s c r e t e s a c e . I n o r d e r t o b e u s e d i n d i s c r e t e s a c e                                       p p p y p p   b i n a r P a r t i c l e S w a r m  O t i m i z a t i o n( B P S O) w a s d e v e l o e d t o m a k e P S O c a a b l e t o o t i m i z e t h e c o m b i n a t i o n                     y p p p p   r o b l e m,w a r t i c l e r o b l e m. h i c h e x t e n d e d s w a r m o t i m i z a t i o n a n d i s u s e d t o o t i m i z e t h e d i s c r e t e b i n a r s a c e                           p p p p p y p   A l t h o u h B P S O h a s b e e n r o o s e d f o r o v e r t e n e a r s a n d h a s b e e n u s e d i n m a n c o m b i n a t i o n o t i m i z i n r o b l e m s                               g p p y y p g p     , , a e r a n d a l i e d i n m a n a r e a s i t w a s r a r e l a n a l z e d . I n t h i s t h e b i n a r P a r t i c l e S w a r m  O t i m i z a t i o n( B P S O) i s                   p p p p y y y y p       , r o b a b i l i t a n a l z e d w i t h b i t c h a n e a n d s c h e m a t h e o r e m o f G e n e t i c A l o r i t h m( GA) . O n t h e o n e h a n d t h e c h a n e                           p y g g g y   r o b a b i l i t o f e v e r b i t o f B P S O i s c o m u t e d .A n d I t w a s f o u n d t h a t c h a n e r o b a b i l i t o f e v e r b i t o f B P S O i s                               p y p y y p g y         , b i e r a n d b i e r w i t h i t e r a t i o n o i n o n . O n t h e o t h e r h a n d B P S O u s t u s e s t h e m u t a t i o n o f GA i n t e r m o f t h e o r                                     g g g g g g j y   , o f G e n e t i c A l o r i t h m, a n d i s l a c k o f t h e o e r a t i o n a n d c r o s s o v e r o f s e l e c t i o n s o i t c a n n o t k e e t h e o t i m a l s c h e m a                                 g p p p  

) 福建省科技厅 K 类项目 ( J K 2 0 1 1 0 3 5 * 基金项目 : 收稿日期 : 2 0 1 1-0 5-2 0 : E-m a i l h l i u f n u. e d u. c n * * 通讯联系人 , @ j j

  第5期

刘建华等 : 离散二进制粒子群算法分析

·5 0 5·

, i n c r e a s e i n B P S O w i t h i t e r a t i o n o i n o n i n t e r m o f s c h e m a t h e o r e m o f GA. F r o m t h e t w o w a s i t w a s f o u n d t h a t                                     g g y   ,w , o w e r f u l l o b a l P S O i s m o r e a n d m o r e s t o c h a s t i c h i c h h a s t h e a b i l i t o f s e a r c h b u t c a n n o t c o n v e r e s t o b i n a r                             p g y g y     , , a r t i c l e o i n o w e r f u l t h e o t i m a l o f s w a r m.W i t h t h e i t e r a t i o n o n t h e r a n d o m n e s s o f B P S O i s m o r e a n d m o r e s o                               p g g p p   ,e t h e B i n a r P S O i s l a c k o f l o c a l e x l o r a t i o n w h i c h i n s t r u c t s t h e i m r o v e m e n t o f B P S O.A n d t h e n x e r i m e n t s                           y p p p   , c o n d u c t e d w i t h B e n c h m a r k f u n c t i o n h a v e t e s t e d t h e r e s u l t s i n t h i s a e r . B a s e d o n t h e a n a l s i s a n i m r o v e d B i n a r                               p p y p y P S O i s r o o s e d w h i c h c h a n e s t h e f o r m u l a o f i t s r o b a b i l i t m a i n a n d t h e f o r m u l a o f b i t o b t a i n i n v a l u e .T h e                             p p g p y p p g g       ’ a r t i c l e a r t i c l e n e w f o r m u l a s a r e f a v o r a b l e o f s c o n v e r e n c e t o t h e o t i m a l a n d i n t e n s i f t h e l o c a l e x l o r a t i o n o f                               p p g p y p   , a e r b i n a r P S O.W i t h B e n c h m a r k f u n c t i o n t h e e x e r i m e n t c o n d u c t e d i n t h i s i l l u s t r a t e s t h a t t h e i m r o v e d b i n a r                         p p y p p y   i s o u t e r f o r m e d t o o r i i n a l b i n a r P S O. P S O           p g y   : ,c ,s , a r t i c l e r o b a b i l i t K e w o r d s i n a r w a r m t i m i z a t i o n o n v e r e n c e c h e m a h e o r e m, b i t h a n e  b  s  o  t  c  p y y p g g y  p   e x e c t e d v a l u e   p

, P a r t i c l e S w a r m  O t i m i z a t i o n    粒 子 群 算 法 (   p 是由J P S O) . K e n n e d C. E b e r h a r t于1 9 9 5年 y和 R. 开发的智能优化算法
[ ] 1, 2

对离散二进制粒子群算法 的模式 定 理 两 方 向 , ( 进行分析 , 本文分析发现 B B P S O) P S O 具有过 强的随机的全局探索性 , 缺少后期局部探测性 , 进而改进了 B P S O 算法 .

, 它是受鸟群 、 鱼群等群

体社会智能而产生的灵感 . 后来 Y. S h i和 R. C. E b e r h a r t增加一个动态变化的 权 重 来 控 制 P S O [ ] 3 , 算法的探索性和探测性 形成现在的标准粒子 群算法 . 相比其它进化算法 , 粒子群算法有着参 数少 , 不需要编码 , 易于使用等优势 , 它已广泛应 例如 , 图像处理 , 模 用于各个领域的优化计算中 ,
] 4~8 电力规划 , 生 产 调 度 等 等[ 然 而, 标 式识别 , .

1  离散二进制粒子群算法
K e n n e d b e r h a r t开发出来离散二进制 y和 E P S O 算法的速度 更 新 公 式 与 原 始 P S O 算法一 首先粒子是由二进制编码组成 , 每个二制位 样, )式产生 速 度 , 利用 ( 而其速度值被转换成变 1 换的概率 , 也就是位变量取 1 值的机会 . ·v ( ) ·( v r a n d + p i d=ω i d+c 1· i d-x i d) · ( ) ·( ) ( ) c r a n d -x 1 p 2 i d d g 但没有原始 P 为 S O 的粒子位置更新公式 . 速度 了表 示 速 度 的 值 是 二 进 制 位 取 1 的 概 率 , ] , 的值被映射到区间 [ 映射的方法一般采用 0, 1 ( )式s 2 i m o i d 函数 : g 1 ( ( ) s v = 2 i d) 1+ e x -v p( i d) ( 这里 s 表示位置 x 粒子 v i d) i d取 1 的 概 率 , )式改变它的位值 : 通过 ( 3 ( ) ( a n d v 1 ≤s i d)  i fr 烄 ( ) x 3 i d= 烅 0 o t h e r w i s e 烆 ) 这里 r 是 一 个 随 机 数, 从区间[ a n d( 0, 1] ( 的统一分布 中 随 机 产 生 . 为了避免s 太靠 v i d) 近 1 或 0, 一个参数 Vm 用于 a x 作为最大速度值 , 限制 v 即v 速度的 -Vm Vm . i d的范围 , i d∈ [ a x, a x]

准P 对 S O 算法适应在连续 搜 索 空 间 进 行 计 算 , 于离散的搜索空间 , 其不能直接加以应用 , 必须 需要对标准 P 使其适合求解 S O 算法进 行 改 进 , 离散空间的问题 . 为了使 P S O 算法能解决离散组合优化问 题, J . K e n n e d C. E b e r h a r t在1 9 9 7年设计 y和 R. 一个 P S O 算法的离散二进制版本( B i n a r y [ 9] , ) , 用来 P a r t i c l e S w a r m  O t i m i z a t i o n B P S O   p 优化离散二进制空间的问题 , 扩展了 P S O 算法 大量文献 的应用 . B P S O 算法提出来有 十 多 年 , 将其应用于组合优化问题 , 获得广泛的应用 , 例 如, 生物信 息 , 背 包 问 题, 经济规划和图形图像
1 0~1 8] 标 准 粒 子 群 算 法 从 提 出 来 以 后, 有 等等 [ .

很多文 献 对 它 进 行 了 理 论 分 析 , 已获得一些成 果. 但很少有文献对离散二进制粒子群算法 ( B P S O)进 行 理 论 分 析 ,难 以 从 理 论 上 说 明 本文从位改变概率和遗传算法 B P S O 的性能 .

·5 0 6·

南京大学学报 ( 自然科学 )      

第4 7卷

限制最终是限制了位 x i d取 1 或 0 的概率 . ) ] 在( 式中 , 其函数值被映射成区间 [ 2 0, 1 . ) 根据 ( 式, 函 数 值 代 表 了 某 位 为 1 的 概 率. 需 3 要注意的是 : S i m o n d 函数值并不代表某位变 g 化概率 , 只 是 代 表 某 位 取 1 的 概 率. 所 以, 在分 析中 需 要 考 虑 某 位 变 化 的 概 率 是 多 少 , 本文将 对此进行分析 .

时, 位的改变绝对概率 最 大 , 最大值为0 这 . 2 5. 是 J. K e n n e d C. E b e r h a r t在文献[ 9] y 和 R. 的分析结果 , 其 分 析 方 式 不 严 格, 比 较 简 单, 下 节对此进一步分析 . ) 表示 2 . 2  位改变 率 的 进 一 步 分 析   设 v t i d( 第i粒子的第 t代在 d 维的速 度 . 第 t代 位 为 1 ( ) ) , 的概率为 S 而 位 为 0 概 率 是 1-S( v t v i d( i d ( ) ) 此外 , 如果第t 则第t t . -1 代位值已经是 0, ) ) ; 代将发生改 变 的 概 率 为 S( 同 样, 如果 v t i d( 第t 则 第 t代 发 生 改 变 的 -1 代 位 值 已 经 是 1, ( ) ) 概率为 1-S 而 第t v t . -1 代 位 值 是 0 的 i d( ( ) ) , 概率为 1-S 第t v t -1 -1 代位值是 1 的 i d( ( ) 因 此, 第 t代 位 发 生 改 变 概率为 S v t -1) . i d( ( ) 应该为 : 的概率 p t ( ) ( ) ) ) ( ) ) t =( 1-S v t -1 S v t + p i d( i d( ( ) ) ( ( ) ) ) ( ) S v t -1 1-S v t 7 i d( i d( ) ) 结合 ( 式与 ( 式, 得到下式 : 2 7 1 ( ) t = 1- p ) )× e x -v t -1 1+ p( i d(

2  二进制粒子群算法的分析
2 . 1  位变化概 率 的 分 析   文 献 [ 9]提 出 一 个 位变化概率的概念 , 这里据此对它进行分析 . 根 ) 式, 粒子 轨 迹 是 一 种 概 率 改 变 , 而单维的 据( 3 速度转 化 为 位 取 1 的 概 率 . 位为1的概率为 S ( ) , 而位为 概 率 是 如果位已经 v 0 1-S( v . i d i d) ; 是 0, 则位发生改 变 的 概 率 为 S( 如果位已 v i d) ( 经是 1, 则其发生改变的概率为 1-S 位发 v . i d) 生改变的绝对率为 : ( ( ( ( ) =S v 1-S v Δ) p i d) i d) 即 ( ( ( ( ) =S v -S v 5 Δ) p i d) i d) 公式表示为位给定一个速度 v 其发生改变 i d值 ,


( ) 4

的绝 对 概 率 . 所 以, v i d值 改 变 就 是 位 改 变 概 率 ) ) 的变化 . 结合 ( 式和 ( 式, 得到下式 : 2 5
2 1 1 ( = - Δ) p ( ) ( ) 1+ e x 1+ e x p -v p -v i d i d ( ) 6





( ) 1 ) ) e x -v ( t 1+ ( )+ p( 1 ) ) 1+ e x -v ( t -1 ( )× p( 1 1- ) ) e x -v ( t 1+ ( ) p(
i d i d i d

( ) 8

( ) 式是位 的 速 度 与 位 改 变 绝 对 概 率 之 间 6 关系 , 其关系图见图 1. 根 据 图 1, 当位速度为0

( ) 式就是第 t代位改变的概率 , 其与速度 8 , 关系如图 2. 根 据 图 2 第 t代 位 改 变 的 概 率 与 两代 的 速 度 有 关 , 但其最大改变的概率应该在

图 2  位两代速度与位的改变概率之间关系 图 1  位速度与位的改变概率之间关系 r o b a b i l i t F i . 1 R e l a t i o n o f b i t c h a n e t o b i t v e l o c i t             g g p y y   F i . 2 R e l a t i o n o f b i t c h a n e r o b a b i l i t t o t w o e n e r a t i o n             g g p y g   v e l o c i t o f b i t   y  

  第5期

刘建华等 : 离散二进制粒子群算法分析

·5 0 7·

两代速 度 都 为 0 时 , 而最大值为0 也就是 . 5. 说, 最大位改变概率不 超 过 0 作一个特殊假 . 5. ) ) , )式改为 : 即v 则( 设, t =v t -1 7 i d( i d( ( ) ( ( ) ) ) ( ) ) t =2 1-S v t S v t p i d( i d( ) 而( 式改变得到下式 : 8 1 ( ) t =2 1-   p ) )× e x -v t 1+ p( i d( ( ) 9

根据上面的分析 , 这里得到以两点结论 : ( 1)位 改 变 概 率 与 速 度 的 变 化 式 应 该 为 ( ) 式或( 式, 而不是( 式. 当速度v 8) 1 0) 5) t i d( 为0 时, 按文献[ 位改变概率是 9]分 析 , 而这里得到结果应该0 这个结论与 0 . 2 5, . 5. 分 J. K e n n e d C.E b e r h a r t在 文 献 [ 9] y 和 R. 这将在后面的实验中可以得 析结果有差别,

( ) 1 ) ) 1+ e x -v ( t ( ) p(
i d

( ) 1 0

到检验. ( ) 2 B P S O 算法粒子不太可 能 收 敛 于 全 局 最优粒子 , 因为如果其收敛到全局最优粒子 , 则 其速度为 0, 这反而位发 生 改 变 的 概 率 最 大 , 即 此 时, 搜 索 具 有 更 强 的 随 机 性, 缺乏方 为0 . 5. 向性 . 所 以, B P S O 算法是全局随机搜索性算 法, 算法本身 随 着 迭 代 运 行 , 其 随 机 性 更 强, 没 有收敛 . B P S O 算法是缺少局部探测性的随机 搜索算法 . 这 2 . 3  实验验证   为了验证上节分析的结论 , 里用实验判断 B 实验利用 B P S O 算法 . P S O算 法来求解基 准 函 数 J. 其函 D. S c h a e r 函 数, f f 数形式如下 :


) ( 式关系为图3 其图形类似一个抛物 1 0 . ) 线, 其最高点在速度v 为0 时 , 最大值为0 t . 5 . i d(

图 3  位改变的概率与速度关系 F i . 3 R e l a t i o n o f b i t c h a n e t o b i t v e l o c i t r o b a b i l i t             g g y p y  

2 s i n

) f x = 2(



i =1

2 . 5 ∑x i -0 n

+0 . 5

2 2 1+0 . 0 0 1× ( ∑x i ) ( ) i =1

-5 0<x 5 0 i< 这个 结 论 与 J. K e n n e d C.E b e r - y 和 R. ] 分析结 果 不 同 . 因 为, 当速度v h a r t 在文献 [ 9 i d ( ) 为 0 时, 按文献[ 分 析, 位改变概率是 t 9] 而这里得到结果应 该 是 0 这个结论将 0 . 2 5, . 5. 在后面的实验中可以得到检验 . ) 根据 ( 式, 1 x p i d、 i d及 p d分 别 是 二 进 制 位 , g ( 它们的取值为 0 或 1. 因 此, 和( p p i d -x i d) d- g ) ·( 可 能 为 -1, 所以c x 0, 1. r a n d( p i d) 1· i d- ) ·( 的值为区间[ x +c r a n d( - p i d) 2· i d) d -x g ( , ( ] 随 机 值. 假设( 式只有一 c c 1) 1 +c 2) 1 +c 2) ( ) ·( 项, 即v 如果 p r a n d . p i d=c 2· d -x i d) d= g g ; 则v 这意味位取1或0 x S( v =0 . 5. i d, i d=0 i d) ) 的概率分别是 一 样 . 由( 式, 意味 8) t =0. 5, p( 着粒子的位发生改变 的 概 率 为 0 因 此, 当粒 . 5. 子的位置都收敛到全局最优粒子位置 p 粒子 d, g 达到最高 . 的位改变概率为 5 0 %, 在二维上 , 利用离散二进制 P S O 算法优化 函数最小值 , 首先对搜索空间每一维编码 , 每一
1 0 维共 2 位 二 进 制 数 字 表 示, 迭代运行步数为

, , 粒子数为 2 最大限制速度 V 每个 1 0 0 0 0 .   m a x =9 1 0 , ] 粒子有二维 , 每一维区间 [ 被编码成2 - 5 0 5 0 位. 对某个 粒 子 的 位 平 均 速 度 随 迭 代 计 算 如 图 , 其粒子各位取 1 的平均概率迭代变化如图 5 4 . 图 6 是某粒子的位改变概率迭代变化 . 某粒子的
1 0 也可能不改变 , 一个粒子共 2×2 位可能改变 ,

二进制位 , 每次迭代计算其位改变数 , 再除以其
1 0 二进制位 , 得到粒子的位平均改变率 . 2 × 2 图 4 和图 5 表 明 粒 子 速 度 在 减 少 , 并慢慢

地趋 向 一 个 固 定 值 上 下 波 动 , 当然其取1的平 ) 均概率也是具有相同特征 . 图 6 更好地反映 ( 8 式及图 3 的特征 , 从图 6 可以看出 , 位的改变是 在慢慢增加 , 位改变概率在 0 图 4 显示 . 5 左右 ;

·5 0 8·

南京大学学报 ( 自然科学 )      

第4 7卷

速度随迭代而靠近 0. 再 结 合 图 6 可 得, 当速度 趋靠近 0 时 , 速度改变率基本靠近 0 这 . 5 左右 . ) 式的分析结论 . 些图的结果验证了对图 3 及 ( 8 图 7 显示某粒子到最优粒子平均距离的迭代变

化, 从图中可以到 , 粒子与最优粒子距离是慢慢 增加 , 而不趋向 0, 这图形 式 反 映 了 粒 子 不 收 敛 粒子随着迭代越来越具有随 于全 局 最 优 粒 子 , 机性 , 缺少局部探测性 .

3  二进制 P S O 的模式分析
从前面的分析可以知道 , 二进制 P S O 算法 每一 次 迭 代 主 要 是 对 二 进 制 串 位 进 行 改 变 , 因 此从遗传算法角度来理解 , 二进制 P S O 是一个 每一次迭代是对每一位求出其 特殊 变 异 操 作 , 变异概率 , 从而对某一位进行变异 . 其变异概率 就是 前 面 改 变 率 . 特殊性就在于其求解变异概

是根据当前速度和上代为 0 或 1 概率 . 速 率时 , ) ) 度为 ( 式, 而根据位的速度 , 利用 ( 式再转变 1 2 为位取 1 的概率 . P S O 算法就在于速度是根据粒子靠近最 优点和自身历史位置的距离来求解 . 因此 , 二进 制粒子变异与最优点和历史自身最优点有关. 但从上面分析可以知 , 粒子越靠近最优点时 , 其 速度越 靠 近 0, 位 变 异 率 也 就 越 高. 当速度为0

  第5期

刘建华等 : 离散二进制粒子群算法分析

·5 0 9·

时, 位变异概率高达到 0. 5. 根据遗传算法变异算子性质 , 模式 H 保持 概率为 :

为 0, 而粒子的位很可能为 1. 因此 , 位需要最大 可能转变为 0; 而速度为 正 , 最优粒子和历史最 粒 子 的 位 很 可 能 为 0, 位需 优位置 很 可 能 为 1, 要最大可能转变为 1. 4 . 1  公 式 的 变 换   为 了 让 速 度 和 位 改 变 的 关 系与上面分析相 符 , 对( 式 进 行 改 进. 当速度 2) 为 0, 希 望 新 的 概 率 映 射 函 数 值 为 0; 当速度小 于 0 与大于 0 时 , 概率映射函数关于 y 轴对称 , 即为偶函数 ; 当速度趋向正负无穷时 , 概率映射 直接对 s 函数值为 1. i m o n d 函数改为如下 : g 2 烄 当v 0 1- i d≤ ( 1+e x - v p i d) ( s v =烅 i d) 2 0 -1 当 v i d> ( 1+e x - v p i d) 烆 ( ) 1 1 ( ) 式的 演 示 图 为 图 8. 根 据 图 8, 当速度 1 1 ( ) 式概率映射函数为递减 ; 当速度为 为负时 , 1 1 ( ) 正时 , 式概率映射函数 为 递 增 ; 当速度为0 1 1 时, 函数为 0.

P 1-Pm ) ≈1- o( H) Pm s= ( 为模式的阶 . 从上 Pm 为位变异概率 , o( H) 式中分析可 , 位 变 异 概 率 Pm 越 小 , 模式 H 保
持不 变 概 率 越 大 . 从二进制编进化算法理论来 说, 变异有利于种群的多样性 , 增强算法全局探 测能力 . 而算法早期应该种群具有多样性 , 也就 但晚期算法的种 是增 强 算 法 的 全 局 探 测 能 力 . 群多样性减 性 , 有 利 于 算 法 局 部 探 索. 因 此, 进 化算 法 变 异 概 率 早 期 应 该 大 于 晚 期 , 才有利于 算法性能提高 . 从上一节分析可以知道 , 二进制 P S O 算法 其 位 变 异 的 概 率 越 高. 当速 度 越 为 0 时 , P S O 算法 思 想 是 粒 子 在 飞 行 中 , 粒子越来越靠近最 优粒子 , 也就 是 速 度 慢 慢 收 敛 于 0. 因 此, 其变 异概率越来 越 大 . 进 而, 种 群 多 样 性 越 来 越 强, 全局探测能力越来越增强 , 缺乏局部探索性 . 这 所以不少利用二进制 应该二进制 P S O 的缺点 , P S O 算法求 解 离 散 的 论 文 混 合 一 些 局 部 搜 索 这种改进策略在不少文献中可以 算法原 因 , 看到 . 此外 , 从遗传算理论原理分析来看 , 二进制 其缺少选择操 P S O 算法只是利用 了 变 异 算 子 . 作和 交 叉 操 作 , 并不能保持最优模式能呈指数 级增长 .

( o H)

4  二进制 P S O 算法的改进
)式 , 分析速度公式 ( 公式为三部分 , 第一 1 部分 w· 而 第 二 部 分c v i d 是速度惯 性 部 分 , 1· ) ·( ) · 和第三部分c r a n d( x r a n d( p i d- i d) 2· ( 分别为 自 身 认 知 部 分 和 社 会 认 知 部 x p d- i d) g 分. 而( 和( 取 值 分 别 -1, x x 0, p p i d- i d) i d) d- g 1. 0 意味 着 p -1 意 i d 或p d 与x i d 位 的 值 相 等; g , ; 味着 p 而x 1 意味着 p i d 或p d 为0 i d 的值为 1 i d g , 或p 而x 因 此, 速 度v . d为1 i d 的值为0 i d 的值 g 意味着最优粒子 可以理 解 为 ,当 速 度 为 0 时 , 和历史最优位值相等 , 位应该不需要变化 . 而当 速度 为 负 时 , 最优粒子和历史最优位置很可能
图 8  新概率映射函数 F i . 8 N e w m a i n f u n c t i o n o f r o b a b i l i t       g p p g p y  

) 对粒子的位值改变式 ( 改为如下形式 : 3 当v 0时 i d< ) ( r a n d( s v f 0 i ≤   i d) 烄 ( ) x 1 2 i d= 烅 x o t h e r w i s e i d 烆 当v 0时 i d> ) ( r a n d( s v f 1 i ≤   i d) 烄 ( ) x 1 3 i d= 烅 x o t h e r w i s e i d 烆 ) 同样 , 这里 r 是 一 个 随 机 数, 从区间 a n d(

·5 1 0·

南京大学学报 ( 自然科学 )      

第4 7卷

[ ] ( 的统一分布中随机产生 . 为 了 避 免s 0, 1 v i d) 太靠近 1, 一个参数 Vma 用于 x作 为 最 大 速 度 值 , 即v 限制 v - Vma Vma . i d 的范围 , i d ∈[ x, x] 新方法与原方法区别在于两个层次 . 首先 , 是概 率 映 射 函 数 与 s 目的是 i m o n d函 数 差 别. g 让速度趋 为 0 时 , 其 概 率 函 数 值 为 0. 第二层 次, 根据概率函数 值 让 位 取 0 和 1 形 式 为 ( 1 2) ) , 和( 这种形式能保证速度为 0 时 , 位的值不 1 3 变; 当速度为 负 时 , 位 只 能 改 变 为 0; 当速度为 位只能 改 变 为 1. 这 样 做 目 的, 可以让粒 正时 , 子群 最 终 很 容 易 靠 近 全 局 最 优 粒 子 , 当速度为 粒子的位改变率更 靠 近 0 的 概 率 增 大 . 这 0时, 种思想符合粒子群算法本质理念 . 为了检验上 述 改 进 思 想 , 利用新的二进制 粒子群算 法 来 求 解 基 准 函 数 J . D. S c h a f f e r函 数, 在二维 上 , 求基准函数J . D. S c h a f f e r的 最 小值 . 算法流程与原始二进制粒子群算法类似 , ) 只不过映射函数与位改变为新改进的形式 ( 1 1 ) 和( 式. 1 2 首 先, 对 搜 索 空 间 每 一 维 编 码, 每一维共 迭代运行步数为 3 粒 2 位二进制数字表示 , 0 0, 最大限制速度 Vma 每个粒子有 子数为 2 0, . x =9
1 0

代变化 . 对一个粒子每位其可能改变 , 也可能不
1 0 改变 , 一个粒子共 2×2 二进制位 , 每次迭代计

再 除 以 其 2×1 算其位 改 变 数 , 0 2 4 二 进 制 位,   得到粒子的位改变率 . 图 9 表明粒子速度在减少 , 并慢慢地趋向个 , 因此 , 粒 子 的 位 置 在 很 快 收 敛. 根据图1 粒 0 . 1 , 子到最优粒子的距离也慢慢地靠近 0 所以粒子 的位置趋向于最优粒子 . 图1 0 粒子取 1 的概率 , 慢慢靠近 0 这意味粒子的位为 1 或 0 的概率 . 5 , 图1 这 各为 5 0 %. 1 粒子的位改变率慢慢趋向 0 也意味着粒子在慢慢稳定 , 并且到了晚期 , 粒子 的位置并没有多少变异发生 . 因此 , 本节的改进 让粒子能够慢慢收 方法与思想符合粒子群思想 , , 敛于最优粒子的位置 . 根据图 1 位的改变在减 1 位改变概率非常低 , 最终不会高于 0 少, . 0 5 . ) 用 ( 式和( 式来代替原始 B 1 2 1 3) P S O算 ) 法( 式和 ( 式, 粒子会很快收敛于全局点而 2 3) 不动 , 算 法 效 果 会 很 不 理 想. 从上面分析可以 知, 原始 B 其更具有随 P S O 算法运行到最后时 , 这说明其是一种全局搜索能力 , 不具有局 机性 , 部搜索性 . 而新公式 ( 和( 式刚好与其相 1 2) 1 3) 收敛很快 , 因 此 是 局 部 搜 索 能 力 很 强, 而全 反, 局搜 索 能 力 很 弱 . 根据一般的启发式随机搜索 算法开始应该是需要全局搜索能力 , 算法原理 , 而晚期是需要局部搜索能力 . 根据这个道理 , 对 算法作如下改进 :

二维 , 每一维 区 间 [ 被 编 码 成 2 位, -5 0, 5 0]
1 0

与前 面 试 验 类 似 , 某个粒子的位平均速度随迭 代计算如图 9, 其粒子各位取1的平均概率迭 代变化如图 1 图1 0. 1是某粒子的位改变率迭

  第5期

刘建华等 : 离散二进制粒子群算法分析

·5 1 1·

i f i t e r a x I t e r      < γ* M ) ) 算法利用 ( 式和 ( 式 2 3 e l s e ) ) 算法采用新变公式 ( 式和 ( 式 1 1 1 2 e n d ] 这里γ 是一个参数 , 其取值为 [ 之间实 0, 1 数, 而I i t e r为当前运行的迭代步数 , t M a x 为算 法迭代运行最大步数 . 当其为 1 时 , 算法就是原 当为 0 时 , 其完全是新的变换公 始B P S O 算法 ; 式. 这里把这种算法叫做新 B 简称为 P S O 算法 , N B P S O. 4 . 2  与遗传算法混合的二进 制 P S O 算法 上 述改变思想能 保 证 二 进 制 P S O 算法能更好收 敛到全局最优点 , 速度为 0 时 , 位发生改变的概 率为 0. 二进制 P S O 算法实际可以看作一种特 殊变异操作 , 而且只有变异 . 新的二进制算法变 异率最终变成只有 0 这与遗传算法的变异 . 0 5, 概率取值基本相同 . 但只有变异操作 , 不能保证 要 算法 能 保 证 适 用 度 好 的 模 式 呈 指 数 级 增 加 , 保证 好 模 式 呈 指 数 级 增 加 , 应该存在遗传算法 的选 择 操 作 . 因 此, 把遗传算法与新二进制 , 也就是遗传算法的 P S O 算法混合 ( GA B P S O) 变异操作改为这里新的二进制 P S O 算法 . 4 . 2 . 1  混合算法   二进制 P S O 算法与遗传算 法的混合主要是把遗传算法中的变异操作更换

事实上就是对遗 为新改进的二进制 P S O 算法 , 其算法流程 传算法 引 进 一 种 新 的 变 异 操 作 . 如下 : 算法 S t e 1  随机产 生 一 个 由 确 定 长 度 的 二 进 p   制串组成的初始种群 . S t e 2  对 该 种 群 迭 代 地 执 行 下 面 的 步 p   骤, 直到满足某种停止条件 : )计算种群中每个个体的适用值 ; ( a )按由个体适应度值所决定的某个规则 ( b 选择将进入下一代的个体 ; ( )按概率 P c c 进行交叉操作 ; )执行二进制 P ( 执行改进 d S O 算 法 操 作: 的二进制 P S O 算法公式 . S t e 3  把在后 代 中 出 现 的 最 好 的 个 体 指 p   定为 遗 传 算 法 的 执 行 结 果 , 这个结果可以表示 问题的一个解 . 4 . 3  算 法 实 验 分 析   为 了 验 证 本 文 算 法 的 有 效性 , 分别采用原始 B P S O 算 法、 N B P S O算 法、 遗传算法 GA 算法和 GA B P S O 算法对下列 基准函数的最优问题进行实例计算并进行对 为了检验改进效果 , 先选两个多模态测试函 比. 数f f 2、 3 进行第一类实验 : ( )测试函数 2: 1 n 维的 R a s t r i i n 函数 g

2 ( ] x) =∑[ x 0 c o s 2 x +1 0 π f 2( i -1 i)

i=1

·5 1 2·

南京大学学报 ( 自然科学 )      

第4 7卷

-5 . 1 2<x 5 . 1 2 i< ( ) : 测试函数 维的 2 3n G r i e w a n k 函数

交叉比例为7 变异率为0 分别 9 0% , 0% ; . 5%. 用B 遗 传 算 法) 和 GA P S O、 N B P S O、 GA( P S O 进行优化 . 为了使计算较为准确 , 每个函数迭代 运行为 1 每种算法各自运算 5 表1 0 0 0代, 0次.   中分 别 列 出 两 函 数 用 不 同 算 法 算 出 5 0次平均 最优值 . 第一类实验数据如表 1. 从 表 中 可 以 看 出, 对于每 个 函 数 所 求 得 值 , N B P S O 算法优于原 始的 B P S O 算 法. GA P S O 与 遗 传 算 法 GA 基 但其结果也优于原始的 B 本一致 , P S O 算法 .

x i 1 n 2 n x) = c o s +1 ∑x f 3( i -∏ 1 4 0 0 01 i 槡

()

-6 0 0<x 6 0 0 i< …, , 上两函数 的 最 优 点 x* 为 ( 最优 0, 0) 值为 f( x* ) =0. 对于这两个基准函数的自变量维数及粒子 个数设置如表中所示 . 算法的参数设置 为 : c 1=

c . 4, wma . 2, wm . 4; N B P S O算 1 . 4, 2 =1 x=1 i n =0 ; 法的 参 数 γ =0 . 9 5 遗传算法的选择比例为

表 1  最小平均适应值和标准方差 T a b l e 1 T h e s m a l l e s t f i t n e s s a n d s t a n d a r d v a r i a n c e             维数 粒子规模 函数 G r i e w a n k 1 0   2 0 R a s t r i r i n g G r i e w a n k 2 0   4 0 R a s t r i r i n g G r i e w a n k 3 0   8 0 R a s t r i r i n g B P S O   7 0 . 0 9 5   1 9 . 2 5 2 5   0 . 0 3 6 2   9 0 . 4 4 1 8   7 0 . 0 1 5   1 6 0 . 7 4 5 0   GA  1 0 . 0 6 7   1 3 1 4 3   8 2 0 . 0 2 1   8 3 1 0 5   7 0 . 0 1 1   1 3 0 . 4 8 2 8   N B P S O   7 0 . 0 7 5   1 4 . 5 4 3 2   3 0 . 0 2 2   7 8 . 1 2 7 0   9 0 . 0 1 0   1 2 0 . 4 8 2 8   GA P S O 4 0 . 0 4 8   1 5 . 4 3 5 6   2 0 . 0 1 6   8 4 . 4 7 8 7 0 . 0 0 9   1 4 2 . 4 2 6

利用    为 了 进 一 步 验 证 本 文 算 法 的 有 效 性 , 基本 B P S O 算 法、 N B P S O 算 法、 GA 算 法 和 GA P S O 算法对 J . D. S c h a f f e r函 数 的 最 小 化 问 题进行实例计算并进行对比 . ( )测试函数 1: 3 2 维的 J . D. S c h a f f e r函数

2 s i n

-5 0<x 5 0 i< 实验数 据 如 表 2. 实验方法是在第一类实 验的条件 下 , 比较4个算法收敛最优的百分比 ( 在计 算 1 0 0次中有多少次在误差范围内收 , 以 及 收 敛 时 平 均 收 敛 代 数. 参数的设置与 敛) 上面相同 . 对上述问题进行了 1 0 0 次仿真计算 , 其计算结果如表 2 所示 .

x) = f 1(



i=1

2 . 5 ∑x i -0


2   i 2

+0 . 5

1+0 . 0 0 1× ( ∑x ) ( ) i=1
表 2  测试函数 f 在计算 1 1 的平均寻优结果比较 ( 0 0 次情况下 ) ) T a b l e 2 C o m a r i s o n o f m e a n o t i m a l r e s u l t s o f t e s t f u n c t i o n f 1( A b o u t c o m u t a t i o n o f 1 0 0t i m e s                         p p p 模群 体规 2 0   4 0   进化 代数 收敛 误差 平均收敛率 B P S O B P S O N B P S O P S O   GA  GA   B   2 0   7 0   2 1   7 4   2 4   7 3   2 8   8 2   平均收敛代数 GA  GA B P S O N B P S O

1 0 0 0 . 0 0 1     0   2 0 0 0 . 0 0 1     0  

5 6 . 7 1 1 2 . 5 4 7 1 . 6 4 3 9 . 3 6 4   5   5   4 6 8 . 8 6 9 3 . 5 7 8 3 . 9 4 4 0 . 4 6 7   5   5   5

  第5期

刘建华等 : 离散二进制粒子群算法分析

·5 1 3·

不论从平均收敛概率    从表 2 中可以看出 , 还是从平均收敛代数来看 , N B P S O 算法比基本 B P S O 算法 、 GA 算及 GA B P S O 算法有所提高 . 但性能 改 善 程 度 来 看 , 平均收敛率比平均收敛 代数改善程度更 好 .因 为 N B P S O 其主要改善 收敛问题 , 在尽量对探索能力不影响情况下 , 希 望能够 改 善 其 收 敛 性 能 , 更好性能是在粒子第 一次找到最优点时 , 不会飞出此邻域 , 而产生抖 动, 振荡现 象 . 从平均收敛代数性能提 高 中, 可 以发 现 N B P S O比B P S O 性 能 有 提 高 .说 明 不会轻易飞出 N B P S O 算法能更早收敛最优点 , 最优点 .

: E v o l u t i o n a r C o m u t a t i o n .N e w J e r s I E E E   y p y   , 1 9 9 8, 6 9~7 3. P r e s s [ ] , , a r t i c l e 4  W e i J X S u n Y  H S u X  N.A n o v e l             p s w a r m o t i m i z a t i o n b a s e d o n i m m u n e s e l e c t i o n .           p ( ) , J o u r n a l o f N a n i n U n i v e r s i t N a t u r a l S c i e n c e s       j g y   , ( ) : ( 魏建香 ,孙越泓 , 苏新宁 . 一 2 0 1 0 4 6 1 1~ 9 . 种基于免疫选择的粒子群优化算法 .南京大学学 , , ( ) : ) 报( 自然科学) 2 0 1 0 4 6 1 1~ 9 . [ a r t i c l e 5 ] L i u J H,L i u J W.A n e w s w a r m               p o t i m i z a t i o n a l o r i t h m a n d r e a l t i m e c o n t r o l o f       -     p g s i n a l i n u r b a n i n t e r s e c t i o n .S s t e m s t r a f f i c         g y , ( ) : ( 刘建华 , E n i n e e r i n 2 0 0 7, 2 5 7 8 3~ 8 7. g g 刘建伟 . 基于粒子群算法 的 城 市 单 交 叉 口 信 号 ( ) : ) 控制 .系统工程 , 2 0 0 7, 2 5 7 8 3~8 7 . [ ,A 6 ] A l e r B,V i n c e n t J n a k o h a C.A r e v i e w o f           y a r t i c l e w a r m t i m i z a t i o n .   s   o p p , ( ) : C o m u t i n 2 0 0 8, 7 3 1 0 9~1 2 4. p g [ a r t i c l e 7 ] L i u J H,F a n X P,Q u Z H.A n e w                 p t i m i z a t i o n l o r i t h m a s e d n s w a r m  o  a  b  o p g , 2 s i m i l a r i t . C o n t r o l n d e c e i o s n 0 0 7,  a  D y ( ) : ( 刘 建 华, 樊 晓 平, 瞿志 2 2 1 0 1 1 5 5~ 1 1 5 9. 华 .一种基于相似度的新型粒子群 算 法 .控 制 ( ) : ) 与决策 , 2 0 0 7, 2 2 1 0 1 1 5 5~1 1 5 9 . [ ] , , 8  L i u J H F a n X P Q u Z H.A n i m r o v e d               p w a r m t i m i z a t i o n i t h u t a t i o n a r t i c l e  s  o  w  m p p
r d b a s e d n i m i l a r i t .T h e n t e r n a t i o n a l  o  s  3   I y

5  总   结
本文对二 进 制 P S O 算法从位改变率和遗 两种分析结 传算法 的 模 式 概 念 两 方 面 作 分 析 . 论基本一致 , 那就是原始二进制 P S O 算法随机 能很好具有全局探索能力 , 但其不会收 性很强 , 敛到全局最优粒子 , 随着迭代运行 , 其随机反而 因 此, 离散二进制 P 会增强 . S O 算法是一个缺 乏局部 探 测 性 的 算 法 . 这个结论为二进制算法 的应用 提 供 改 进 的 指 导 意 义 . 本文基于上述分 析结论 , 提出两种改进方法 , 一种是改进原始离 散二进制 P S O 算法的概率变换公及其位的取 新的公式有助于粒子收敛于群体最优粒 值式 , 子, 增强局部探测性 . 另一种方法是让离散二进 制P 利用二进制 P S O 算法与遗传算法结合 , S O 算法代 替 遗 传 算 法 的 变 异 操 作 . 通过实验仿真 检测 , 新的改进方法有效实用 .
R e f e r e n c e s [ 1 ]  E b e r h a r t R,K e n n e d J .A n e w o t i m i z e r u s i n         y p g   a r t i c l e s w a r m t h e o r .P r o c e e d i n s f h e      o  t  6 p y g , , , S c i e n c e . N a o a J a a n 1 9 9 5 3 9~ 4 3 . H u m a n   g y p [ , E 2 ] K e n n e d b e r h a r t a r t i c l e w a r m  R. P  s y  J o t i m i z a t i o n .I E E E I n t e r n a t i o n a l C o n f e r e n c e     p ,N : N e u r a l N e t w o r k s . P i s c a t a w a e w J e r s o n       y y , I E E E S e r v i c e C e n t e r 1 9 9 5, 1 9 4 2~1 9 4 8.     [ , a r t i c l e 3 ] S h i Y E b e r h a r t R.A m o d i f i e d s a r m          w p o t i m i z e r .I E E E I n t e r n a t i o n a l C o n f e r e n c e o n       p
t h

N a t u r a l

, o n N a t u r a l C o m u t a t i o n .H a i k o u C o n f e r e n c e       p , C h i n a 2 0 0 7, 9: 8 2 4~8 2 8. [ , 9 ] K e n n e d J E b e r h a r t R. A d i s c r e t e b i n a r       y y   v e r s i o n f h e a r t i c l e w a r m l o r i t h m.  o  t  p  s  a g P r o c e e d i n o f t h e W o r l d M u l t i c o n f e r e n c e o n         g   ,C S s t e m i c s b e r n e t i c s a n d I n f o r m a t i c s .N e w     y y : , J e r s P i s c a t a w a 1 9 9 7, 4 1 0 4~4 1 0 9. y y [ ] ,A 1 0 a l m a n A, A h m a d I l a d a n i S.P a r t i c l e  S     -m   s w a r m t i m i z a t i o n o r a s k s s i n m e n t  o  f  t  a p g , r o b l e m.M i c r o r o c e s s o r s a n d M i c r o s s t e m s     p p y ( ) : 2 0 0 2, 2 6 8 3 6 3~3 7 1. [ ] , , a r t i c l e 1 1  L i a n Z G u X J i a o B .A n o v e l s w a r m             p e r m u t a t i o n o t i m i z a t i o n a l o r i t h m f o r f l o w s h o         - p p g p t o m i n i m i z e m a k e s a n .C h a o s S o l i t o n s s c h e d u l i n       g p   , , ( ) : a n d F r a c t a l s 2 0 0 8 3 5 5 8 5 1~ 8 6 1 .   [ ] , 1 2 i a o C J T s e n C T, L u a r n P .A d i s c r e t e v e r s i o n  L             g   a r t i c l e w a r m t i m i z a t i o n o r l o w s h o o f  p  s  o  f  f p p r o b l e m.C o m u t e r s s c h e d u l i n a n d O e r a t i o n s     p p g p  

I n t e r n a t i o n a l S m o s i u m o n M i c r o M a c h i n e a n d           y p

·5 1 4·

南京大学学报 ( 自然科学 )      

第4 7卷

, , ( ) : R e s e a r c h 2 0 0 7 3 4 1 0 3 0 9 9~ 3 1 1 1 . [ ] ,F 1 3 o r r e a E S r e i t a s A  A, J o h n s o n C G.P a r t i c l e  C           s w a r m o r t t r i b u t e e l e c t i o n n a e s i a n  f  a  s  i  B y :A r o t e i n c l a s s i f i c a t i o n n a l i c a t i o n t o f u n c t i o n         p p p o f r t i f i c i a l E v o l u t i o n a n d r e d i c t i o n .J o u r n a l    A     p , , ( ) : A l i c a t i o n s 2 0 0 8 8 2 1~ 1 2 . p p [ ] , , , 1 4  S h e n Q S h i W  M K o n W e t a l.A c o m b i n a t i o n         g  a r t i c l e o f m o d i f i e d s w a r m o t i m i z a t i o n a l o r i t h m           p p g s u o r t v e c t o r m a c h i n e f o r s e l e c t i o n a n d a n d e n e               p p g , , ( ) : t u m o r c l a s s i f i c a t i o n .T a l a n t a 2 0 0 7 7 1 4 1 6 7 9   6 8 3 . ~1 [ ] 1 5  Y i n P Y.A d i s c r e t e a r t i c l e s w a r m a l o r i t h m f o r               p g o t i m a l o l o n a l a r o x i m a t i o n o f d i i t a l c u r v e s .           p p y g p p g f i s u a l o m m u n i c a t i o n n d m a e J o u r n a l  o  V  C  a  I g , , ( ) : 2 0 0 4 1 5 2 2 4 1~ 2 6 0 . R e r e s e n t a t i o n p

[ ] ,H 1 6 h a n X  M,S u n L B a n J Q,e t a l. A n  Z           g   a r t i c l e o f s w a r m i n t e l l i e n c e b i n a r a l i c a t i o n         p g y p p   s w a r m t i m i z a t i o n  o p ( ) : X L 4 9 4 9~ 9 6 3 . [ ] 1 7 u h G C,L i n C Y,L i n Y S .A b i n a r a r t i c l e  L               y p   s w a r m t i m i z a t i o n o r o n t i n u u m t r u c t u r a l  o  f  c  s p , t o o l o o t i m i z a t i o n .A l i e d S o f t C o m u t i n     p g y p p p p g   , ( ) : 2 0 1 0 1 1 2 2 8 3 3~ 2 8 4 4 . [ ] , , 1 8 M o h d S M S i e r u O S a f a a i D, e t a l.P a r t i c l e          g   t i m i z a t i o n i t h o d i f i e d i m o i d s w a r m  o  w  a  m  s p g f u n c t i o n f o r e n e s e l e c t i o n f r o m e n e e x r e s s i o n             g g p , , ( ) : d a t a . A r t i f i c i a l L i f e a n d R o b o t i c s 2 0 1 0 1 5 1 2 1       4 . ~2 ( B P S O) a l o r i t h m o  t g , , m u l t i f o c u s i m a e f u s i o n . O t i c a A l i c a t a 2 0 1 0 -       g p p p


相关文章:
粒子群算法实现
粒子群算法实现_工学_高等教育_教育专区。粒子群优化算法,是西南科技大学计算机...因此,针对离散的优化问题, Kennedy 和 Eberhart[3]提出了二进制 PSO 算法,二...
粒子群算法介绍
(3)二进制粒子群算法 最初的 PSO 是从解决连续优化问题发展起来的.Eberhart 等又提出了 PSO 的离散 二进制版.用来解决工程实际中的组合优化问题。他们在提出的...
粒子群算法优化不同维数的连续函数以及离散函数的最小...
17 1 引言本文主要利用粒子群算法解决连续函数以及离散函数的最小值问题, 粒子...对于离散函数的 优化可以采用二进制编码和顺序编码来实现同时也可以使用基于遗传...
粒子群算法
第二部是是认知部分, 表明粒子自身的能力, 让粒子...[?4,4] 时的函数 离散粒子群算法的流程图如下图...3 粒子群优化算法的优缺点分析 3.1 粒子群算法的...
粒子群算法
粒子群算法简介 1.1 集群智能(Swarm Intelligence) Swarm 可被描述为一些相互...存在序结构如何表达以及约束条件如何处理等问题, 离散二进制版 PSO 算法不能完全...
粒子群算法
(3)二进制粒子群算法 最初的 PSO 是从解决连续优化问题发展起来的.Eberhart 等又提出了 PSO 的离散二进制版.用来解决工程实际中的组合优化问题。他们在提出的...
粒子群算法综述
粒子群聚类算法综述 9页 1下载券 离散粒子群优化算法...现状进行了全面分析,在论述粒子群算法基本思想 的...但是,任何科学的进步都受到历史条件的限制,直到二十...
粒子群算法matlab代码 吐血推荐
粒子群算法(1)---粒子群算法简介二、粒子群算法的具体表述 上面罗嗦了半天,那些都是科研工作者写论文的语气,不过,PSO 的历史就像上面说的那样。下面通俗的解释 ...
基于约束的离散粒子群算法求解大规模指派问题
基于约束的离散粒子群算法求解大规模指派问题 [ 摘要] 针对现有进化算法在求解传统指派问题时因取整而影响优化效果 的问题,采用了一种基于 AllDifferent 约束的置换...
粒子群算法解最短路径
但其应用大多是连续优化问题, 很少被用来解决离散...和改进粒子群算法进行了对比分析,并得出了改进算 法...(4)(2-4)式的第一项对应于多样化的特点,第二项...
更多相关标签: