（计算机软件与理论专业论文）粒子群优化算法在maxsat上的应用研究.pdf

粒子群优化算法在m a x - s a t 上的应用研究 专业：计算机软件与理论 硕士生：靳峰 导师：苏开乐教授 摘要 命题逻辑中的可满足性问题( s a t ) 是判断给定的命题公式是否存在模 型的问题。s a t 问题是第一个被证明是n p 完全的问题，在理论计算机研究 领域中具有非常重要的地位。m a x - s a t 是s a t 问题的一种最优化形式的变 形。目前针对m a x - s a t 的不完全算法中，元启发式算法的研究相对比较活 跃。粒子群优化算法( p s o ) 作为一种群体智能算法，具有简单、高效的特 点，在连续优化问题上有非常广泛的应用，但是在离散域上的组合优化问题 应用得很少，特别在m a x s a t 问题上的研究还是一片空白。 本文首先对m a x - s a t 问题上的局部搜索算法和元启发式算法的 研究现状做了比较全面的介绍。在分析粒子群算法和m a x - s a t 问题 特点后，引入粒子群的模糊化和量子化模型，提出相应的解决算 法q t p s o 和i h z z y p s o ，并与经典遗传算法进行比较分析。 随后本文在重新定义粒子运动方式后提出一种新的算法p s o s a t 。在 粒子速度低且稳定时，算法表现为局部搜索形式，在收敛速度和求解质量上 有不错的表现。接着针对p s o s a t 提出了相应的改进策略，并在混合禁忌搜 索后，与当前流行的一些局部搜索算法进行全面的比较分析。 最后本文从并行化角度讨论提高性能的方法，针对p s o s a t 算法提出 独立式、合作式和分治式三种并行化策略。 在实验结果上，本文中的f u z z y p s o 在收敛速度和寻解质量都明显优于 经典的遗传算法。同时，在随机实例上p s o s a t 相比其他一些局部搜索算法 也有相对优越的寻解能力。 关键词m a x - s a t ，粒子群算法，遗传算法，局部搜索，禁忌搜索，并行化 r e s e a r c ho nm a x - s a t u s i n gp a r t i c l e s w a r mo p t i m i z a t i o n m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：j i nf e n g s u p e r v i s o r ：p r o f k a l l es u a b s t r a c t t h es a t i s f i a b i l i t yp r o b l e mi np r o p o s i t i o n a ll o g i c ( s a t ) i st h et a s kt o d e c i d ef o rag i v e np r o p o s i t i o n a lf o r m u l aw h e t h e ri th a sam o d e l s a tw a s t h ef i r s tp r o b l e mt ob ep r o v e nn p - c o m p l e t e t h i sp r o b l e mi sa m o n g s tt h e c e n t r a lp r o b l e m si nt h e o r e t i c a lc o m p u t e rs c i e n c e m a x - s a ti st h eo p t i - m i z a t i o nv a r i a n to fs a t g i v e nas e to fc l a u s e s ，m a x - s a ti st h ep r o b l e m t of i n dav a r i a b l ea s s i g n m e n tt h a tm a x i m i z e st h en u m b e ro fs a t i s f i e dc l a u s e s c u r r e n t l ya m o n gt h ei n c o m p l e t ea l g o r i t h m s ，t h er e s e a r c ho fm e t a - h e u r i s t i c a l g o r i t h mf o rm a x - s a ti sr e l a t i v e l yf u l lo fa c t i v i t y p a r t i c l es w a r mo p t i - m i z a t i o n ( p s o ) a sak i n do fs w a r m - i n t e l l i g e n ta l g o r i t h mf e a t u r e dw i t hs i m p l i c i t ya n de f f i c i e n c yh a sb e e nw i d e l ya p p l i e dt om a n yp r a c t i c a lc o n t i n u o u s o p t i m i z a t i o np r o b l e m s b u tf e we f f o r t sw e r em a d et os o l v et h ec o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m su s i n gp s o ，a n dp r o p e r l yn o t h i n gh a sb e e nd o n et o m a ) ( - s a t a tf i r s t ，a no v e r v i e wo fe x i s t i n ga l g o r i t h m i ca p p r o a c h e st ot a c k l et h e m a x - s a tp r o b l e mi sg i v e ni nt h i sp a p e r i n c l u d i n gl o c a ls e a r c hm e t h o d a n dm e t a - h e u r i s t i ca p p r o a c h a f t e rs o m ea n a l y s i so nt h ec h a r a c t e r i s t i co f p s oa n dm a x - s a t ，t w op s o v a r i a t i o nm o d e l sh a v eb e e ni n t r o d u c e d ( q u a n r u mb e h a v e dm o d e la n df u z z yd i s c r e t em o d e l ) t w op s o - b a s e da l g o r i t h m s ( q t p s oa n df u z z y p s o ) f o rm a x - s a th a v eb e e nf o r w a r d e da n di m p l e - m e n t e d ，a n dt h e nc o m p a r e dw i t ht h ec l a s s i c a lg e n e t i ca l g o r i t h m 粒子群优化算法在m a x s a t 上的应用研究 s e c o n d l y , a f t e rr e d e f i n et h ep a r t i c l e sm o v em o d e ，an e w l o c a l - s e a r c h - l i k e a l g o r i t h mi sf o r w a r d e d n a m e dp s o s a t i nt h ec o n d i t i o no fl o wa n ds t e a d y v e l o c i t y , p s o s a tb e h a v e dl i k el o c a ls e a r c hp r o c e d u r ea n dp e r f o r m e dw e l l i nt h ee x p e r i m e n t i nt h ef o l l o w i n g ，s o m ee f f o r t sh a v em a d et oi m p r o v et h e p s o s a t sc o n v e r g e n tr a t ea n ds e a r c hq u a l i t y n e x t ad e t a i l e dc o m p a r i s o n i sm a d eb e t w e e np s o s a t + t a b uf p s o s a tm i x e dw i t ht a b u ) a n ds o m eo t h e r w i d e l yu s e dl o c a ls e a r c hm e t h o d s f i n a l l y , s o m ei n v e s t i g a t i o n sa r ed o n et oi m p r o v et h ep e r f o r m a n c ei nt h e p a r a l l e l i z e da p p r o a c h t h r e ep a r a l l e ls t r a t e g i e sa r ei n t r o d u c e df o rp s o s a t i n c l u d i n gi n d e p e n d e n t ，c o o p e r a t i v ea n dd e c o m p o s e dw a y s t h ep e r f o r m a n c e so ft h er e l e v a n ta l g o r i t h m si n t r o d u c e di nt h i sp a p e ra r e s a t i s f i e d f u z z y p s oi ss u p e r i o rt ot h eg e n e t i ca l g o r i t h mb o t ho nc o n v e r g e n t r a t ea n ds e a r c hq u a l i t y m e a n w h i l e ，t h ep s o s a ti so u t s t a n d i n ga m o n ga l l t h el o c a ls e a r c hm e t h o d so nr a n d o mi n s t a n c e s k e yw o r d sm a x - s a t ，p s o ，g e n e t i ca l g o r i t h m ，l o c a ls e a r c h ，t a b u s e a r c h ，p a r a l l e l l z e 第1 章引言 命题可满足性问题( s a t ) 是计算机科学中的一个非常重要的研究课题， 属于经典的n p 完全问题，m a x - s a t 是s a t 的最优化形式的变种。无权重m a x - s a t 问题的目标是找到一组变量的真值分配使得一个给定的c n f 公式中所能满 足最大的子句数量，而带权重的m a x s a t 问题则对每个子句赋予一个权值，目 标是找到能使满足子句权值和最大的真值分配。m a x s a t 属于n p h a r d 组合优 化问题，由于问题描述相对简单，使其具有很强的理论分析和实际研究价值。很 多应用相关问题，比如规划问题或者b a y e s 网络中的m p e 问题等等，都可以转化 为m a x s a t 问题来求解。 m a x - s a t 的完全算法是指能准确且稳定地找出问题空间中最优解的算法， 但是由于m a x - s a t 问题的计算复杂性，随着问题规模的增大，完全算法的运行 时间也呈指数级增长。对于大规模的问题实例，如果考虑在可接受的时间内找 出尽可能接近最优的解时，就可以发挥不完全算法的作用。另外，混合不完全 算法也是提高完全算法效率的一个非常重要的途径【1 】。 目前m a x s a t 的不完全算法主要分为两大类，局部搜索算法和元启发式 算法。局部搜索算法的基本结构比较固定，相互区别主要体现在变量的选取策 略上。而现阶段其研究相对成熟，研究方向主要集中在改进局部策略和混合算 法上。 m s a t 元启发式( m e t a h e u r i s t i c ) 算法的研究领域则相对比较活跃，不 断有新的算法思想被引入。这里“元启发式”的意思是指一种引导其他启发式 搜索的一般性策略，使之更有效的寻找最优解，比如禁忌搜索，模拟退火，遗传 算法等。禁忌搜索在很有高效算法中都可以找到其身影；模拟退火可以很有效 的解决陷入局部最优的问题；遗传算法在m a x - s a t 上的改进策略和理论分析 方面也是成果不断，基于遗传算法的g a s a t 在0 4 年的s a t 比赛上也取得了不错 的成绩。 粒子群优化算法( 简称p s o ) 属于群体智能算法的一种。它和遗传算法有很 多共同之处，两者都随机初始化种群，而且都使用适应值来评价系统，都根据适 应值来进行一定的随机搜索。但同遗传算法相比，p s o 的优势在于简单容易实 现并且没有许多参数需要调整。目前己广泛应用于函数优化，神经网络训练，模 2 粒子群优化算法在m a x - s a t 上的应用研究 糊系统控制以及其他遗传算法的应用领域。并且在某些连续域问题上，p s o 表 现出更优越的性能。但p s o 算法还较少涉足离散域问题，在m a x - s a t 问题上更 没有发现相关研究情况。 本文的研究正是针对这个问题而展开的，本文的目的则是想通过m a x - s a t 问题，将p s o 在连续域上的优势体现在离散域上的组合优化问题上，说明 此算法的研究价值，并且尝试不同的优化措施。 本文的结构大致如下：第二章对m a x s a t 及其不完全算法作出全面的介 绍，对主流的搜索算法相关特点进行分析；第三章介绍基本的p s o 算法和其行 为分析方法；第四章引入两种离散域上的p s o 改进模型( 模糊算法和量子算法) 针对m a x - s a t 设计搜索算法过程( f u z z y p s o 和q t p s o ) ，实现相应算法后，在 随机实例上对两种算法进行实验和比较分析。接着将f u z z y p s o 与遗传算法进 行比较分析：第五章利用p s o 算法思想，结合局部搜索算法的搜索方式，提 出p s o s a t 算法，并通过改进初始位置和加入禁忌机制来对其优化。最后将加 入禁忌后的p s o s a t 算法与主流的一些局部搜索算法进行比较分析；第六章则 从并行的角度提出针对p s o s a t 算法的优化策略，包括独立并行，合作并行和 分治并行策略；第七章对全文工作进行总结，并展望该领域今后的研究方向。 第2 章m a x s a t 及其不完全算法 2 1 问题介绍 命题逻辑中的可满足性问题( s a t ) 是判断给定的命题公式是否存在模型 的问题。这个问题在计算机科学的很多研究领域扮演着非常重要的角色，比如 逻辑推理和人工智能，还有一些实际应用，比如异步电路综合【2 】，演绎推理 3 】， 数据库完整性 4 】，硬件排错等等。s a t 问题是第一个被证明是n p 完全的问题【5 】， 在理论计算机研究领域中具有非常重要的地位。 每个可满足性问题都可以表示成一种标准形式，这就是合取范式( c n f ) ， 即表示成一些子旬相互合取的形式，每个子句由一些文字相互析取组成，每个 文字是指一个变量的肯定或否定形式。 其形式化的定义是，令c = c i ，q ，c 为m 个子句的集合，其中包 括n 个变量，z 1 ，0 2 z 。，每个变量只能取值为0 或者1 ( t r u e 或者f a l s e ) 。每个 子句g 表示为m 个文字析取形式： ( 2 1 ) 这里的每个文字为变量或者，。不失一般性，假设每个子句中最大只含有 一个变量( 包括其肯定与否定式) ，如果一个子句中有一个文字被满足，那么这 个子旬就是可满足的。这样，s a t 问题也可以说是找到一组变量的真值分配，使 得所有的子句同时可满足，也既是命题公式： 西= 八v 岛 i = i j = 1 ( 2 2 ) 是否可满足。实际上，不仅是要判断这种分配是否存在，当其存在时候还需要 找到此分配形式，这样也就是s a t 问题的一种寻找模型的过程，属于n p h a r d f , 题。m a x - s a t 是s a t 的一种最优化形式的变种。给定一个子句的集合，m a x - s a t 问题就是找到这个集合中能同时被满足的子句的最大数量。在带权重 的m a x s a t 问题中，对每个子句q 都加入一个权重因子叫t ，其目标则是找到 幻 m v m = g 4粒子群优化算法在m a x - s a t 上的应用研究 同时可满足子句的权重和最大值( 换句话说，其目标函数的定义为使不满足子 句的权重和最小) 。这里令毗为g 子旬的权重。目标函数则定义为： m ，( z ) = ：毗，( q ) ( 2 3 ) = 1 这里函数，( g ) 当g 可满足时取值1 ，否则为0 。对于无权重的问题，则是坝= 1 ，v i = 1 ，m ，这种就称为无权重的m a x - s a t 问题。 针对s a t 和m a x s a t 的局部搜索方法基本上可以等同。当需要找到一 个s a t 公式的模型时，实际上等同于为一个m a x - s a t 实例，寻找一组变量分配 来满足所有的子句。如果这组分配可以找到，那么就找到此公式的模型。针对 这两个问题的局部搜索方法有很紧密的联系，所以本文中对p s o 的研究也同样 可以针对s a t 问题。注意对于s a t 和m a x - s 觚的一些特殊的情况，在处理难度 上面有一些不同。比如，对于2 - s a t 问题，即限定s a t 问题中的子句长度为2 ，此 问题是可以在多项式时间内解决的，但是m a x - 2 - s a t 问题还是n p h a r d 问题。 在介绍不完全算法前，还是有必要提一下m a x - s a t 的完全算法和- 近似算 法的研究情况。 2 1 1 争近似算法 m a x _ s a t 的一近似算法表示一个多项式时间算法，它可以在多项式时间内 找到最优解的倍的真值分配，其中o 1 ，e 一般称做为性能比率。 第一个这种近似算法在 6 】中提出，其中的两个算法的性能比率为一 a ) k 和( 2 2 1 ) 2 ，其中k 是子句所含最少的文字数。对于k = 1 的情况，它们都 转化成1 2 - 近似算法，并且在文献 7 】中指出第二种算法实际上是2 譬近似算法。 在文献【8 中提出的基于网络流理论的算法是3 冬近似算法。目前最好的确定多 项式时间内的近似算法其性能比率达到了0 7 5 8 。如果对一些特殊的加入约束的 例子，比如限制每个子句最大的文字数或者加入子句满足的限制条件，可以得 到更好性能的近似算法。 在 9 】中提到，在每个子句只能包含三个文字的m a x - s a t 问题上，除非 p = p ，否则不可能有性能比率高于7 8 的多项式时间近似算法。 2 1 2 完全算法 大部分m a x - s a t 的完全算法都是扩展i 刍d a v i s - l o g e m a n - l o v e l a n d ( d l l ) 回 溯过程的，比如分支界定( b r a n c h & b o u n d ) 和整数规划( i n t e g e r p r o g r a m m i n g ) 第2 章m a x - s a t 及其不完全算法5 方法。 目前基于d l l 过程的完全算法基本都使用了增加回溯性能的技术，比如 单子句传播( u n i tp r o p a g a t i o n ) 等。对于m a x - s a t f 司题，记录并在找到更优 解后更新一个可满足子句的下限值胁。并且记录当前变量分配下的不满足子 句权重和删。令为所有子旬权重和w = 三1w t ，如果在某个分支点上满 足w u w 2 6 ，则此分支下不可能找到更好的解，可以丢弃，这样可以减少搜 索空间。 文献f 1 1 中提出的t w o - p h a s e 算法首次在d p l l 算法上使用g s a t 搜索算法来 计算下限值2 b ，并加入u n i tc l a u s et r a c k i n g 技术，在m a x - 3 - s a t 实例上比整数 规划算法有更好的表现。 而在基于整数规划算法方面，文献f 10 1 中提出的m a x s o l v e r 算法，集合子句 传播、预测式启发和动态变量排序等技术，通过实验说明此算法在当时是最优 的完全算法。 目前最优秀的完全算法之一，是在2 0 0 5 年s a t 比赛上涌现的m i n i s a t 1 1 ， 它使用s a t e l i t e 做为预处理工具，比较新的技术是在自包含分解( s e l b s u b s u m i n g r e s o l u t i o n ) 上提出的基于冲突子句最小化方法。一般在冲突子句中有多于3 0 的 文字是可以省略的。在遍历过程中移除这些文字可以有效的减少内存消耗并且 降低d p l l 搜索过程中的分支数。 2 2m a x - s a t 的局部搜索算法 目前大部分针对m a x - s a t 问题的局部搜索算法可以归为两大类( s a 叨孓同 样) ，g s a t 和w a l k s a t 类。这些算法最初都是只用来解决s a t 实例的，但他们 都可以直接应用在m a x - s a t 问题上。最早应用在s a t 问题上的算法是在1 9 9 2 年 提出的g s a t 算法，但在这之前h a n s e n 和j a u m a r d 已经针对m ( - s a t 提出了一 种局部搜索算法，s t e e p e s ta s e n t m i l d e s td e s c e n t 方法f 12 1 ，使用的是类似的搜 索技术。下面对这两大类算法和其他局部搜索算法做一个比较全面的介绍。 2 2 1 基本结构 在m a x _ s a t 和s a t 的局部搜索算法中，搜索空间是由问题实例中的变量所 ， 有真值分配组合构成的，问题的解即是分配的最优组合。搜索空间的大小则就 是变量数量的指数阶大小。 6柱子群优化算法在m a x - s a t 上的应用研究 大多数针对m a x s a t 的局部搜索算法中，两组真值分配，如果它们只有一 个变量取值不同，则称为相邻解( n e i g h b o r h o o dr e l a t i o n ) 。这样每个搜索步中只 修改真值表中一个变量的值，把这种移动称为f l i p 。另外后面会介绍有些算法考 虑在每步中变动多个变量的值，例如2 - f l i p 和3 - f l i p 。 这些搜索算法使用在当前分配下满足予句的权重合作为目标函数，用局部 搜索处理m ( _ s a t 问题的思想就是在搜索空间中选择某条路径来找到满足孵 子旬权重最大。针对s a t 和m a x - s a t 的搜索算法最主要的区别是在移动函数 上，即选择下一个变动变量的策略上。 局部搜索算法是典型的不完全算法，一般地，它们不能保证在有限时间内 找到最优解。在s a t 问题上，这就意味着对于可满足的实例，它们不能确保能找 到解。这可能就是搜索本身不具有系统性的特点。再者，局部搜索可能陷入搜索 空间中局部最优点或平坦区域【1 3 ，1 4 】，使得搜索处于早期停滞状态。最简单的 机制来防止过早停滞的策略之一就是随机重置，即在一个固定步数内没有找到 更好的解后重新初始化搜索过程。实际上，这一策略也是应用在很多算法中。 a l g o r i t h m1 是大部分对于m a x - s a t 的局部搜索算法结构。程序最开始初 始化一些真值分配序列，并迭代地变动变量的值，对于下一个选择要变动的变 量是根据公式圣和当前分配情况来决定的。程序在达到预定的最大步后停止。 a l g o r i t h m1 ：l o c a l s e a r c hf o rm a x - s a t i n p u tc n ff o r m e df o r m u l a 垂a n dm a x f l i p n u m ； s = i n i t a s s i g n ( 圣) ； s h b 时= s ； f o rj = 1 ，m a x f l i p n u md o i f ，( 8 ) o 此算法允许任意的 随机步序列，具体在17 1 中有说明这就表明从任意真值分配开始都可以找到模 型( 如果存在) ，即算法具有概率上的近似完全性( p a c ) 。 2 2 2 3 加入禁忌搜索的的g s a t ( g s a t t a b u ) 另一种防止陷入局部最优点的机制就是禁忌搜索 1 8 ，1 2 】。主要思想是 在t l 步内防止进行重复运动，参数t l 称为禁忌期限。这种机制可以很方便的加入 到g s a t 中f 1 2 ，1 9 ，2 0 1 。这样的效果则是在某步中改变变量z 后的t l 步内不能再 改变其值。 其实g s a t t a b u 算法基本原同h a n s e n 等提出的s t e e p e s ta s c e n t - m i l d e s t d e s c e n t 算法1 2 1 比较相同，但g s a t t a b u 是很多年后才在s a t 问题上提出的。 8粒子群优化算法在m a x - s a t 上的应用研究 2 2 2 4h s a t g s a t 的另一个变种则是h s a t ，其搜索步利用了历史信息。但如果某搜索 步时待选择的变量有多个，h s a t 选择近期最少变动的变量，即最早前变动的变 量。在搜索初始化以后，如果有变量值没有改变，则进行类似g s a t 的一种随机 选择行为。在文献 2 1 】中说明了在加入基于历史解禁规则来限制搜索轨迹的条 件下，h s a t 更容易陷入局部最优点，但h s a t 相比一般的g s a t 还是有比较明 显的优势。因此类似g w s a t ，加入一些随机步机制来扩展h s a t 还是比较有吸 引力的，比如f 2 2 】中提出的h w s a t ，和g w s a t 一样具有p a c 属性。 2 2 3w a l k s a t 算法类 w a l k s a t 算法结构最早是出现在s e l m a n ，k a u t z 等在1 9 9 4 年的f 1 6 1 中，后来 被定义为一种算法框架，见m c a l l e s t e r ，s e l m a n 和k a u t z 在1 9 9 7 年所著f 2 3 1 。它具 有两个变量选择时期，集中在当前未满足子句包含的变量上。每次搜索步中 前期随机选择一个当前不满足的子句g ，后期选择c 其中一个变量，并改变 其值得到新的分配。在g s a t 中，相邻的搜索结点之间是海明距离( h a m m i n g d i s t a n c e ) 为1 的固定关系，而w 砒k s a t 算法则是动态确定并且依赖于此关系的 子集。 2 2 3 1w a 】k s a t w 柚( s a t 算法最不同于其他局部搜索方法就是其评价函数8 c o r e 6 ( z ) ，它只 记录被破坏的子句权重，定义为改变某变量值后子旬变为不满足的的所有权重 和。利用这个评价函数，可以采用下面的选择方式：如果在前期选择的子句中 的某个变量的8 c o r e 6 ( x ) = 0 ，由于前期选择的都是不满足的子句，所以这就表 示如果此变量改变其值后，g 7 可以满足，其他子句没有影响。如果没有这种变 量，那么就以概率p 选择具有最大值的变量，其他则从中的变量中随机选择。 w a l k s a t 似乎类似g w s a t 算法，但它们还是有一些明显的区别，特别 在应用于s a t 上，w a l k s a t 有比较优越的表现。虽然两种算法都使用同种随 机步策略，但w a l k s a t 只将其运用在没有变量满足8 c o r e b ( o ) = 0 的情况下。 在g w s a t 中，随机步则是无条件随机方式进行的。w a l k s a t 中的随机步，只有 在被选择子旬中在所有变量改变后破坏其他子旬的条件下，才可能增加不满足 子句的总权重，从这方面w a l k s a t 要更贪婪一些。另外，由于选择的是不同的 第2 章m a x - s a t ) 及其不完全算法 9 评价函数，在某些时候，g w s a t 又显得比w 甜k s a t 更贪婪的行为：在g s a t 迭 代步中，它可能会选择破坏某些子句但又满足其他子句的变量，但在同样情况 下，w a l k s a t 会选择评价函数值较小的变量。 2 2 3 2 w a l l 2 、，伍，其特征值为实根，幅值小于1 意味着一1 a 1 ，2 1 。 则有一2 1 + u 一妒 1 0 时推导出矛盾，系统不稳定。 2 当i 妒一u 一1 i 2 、，行，其特征值为两个复根，其幅值为a = 可干万= 河q 1 万i 万 二面2 ，系统稳定的条件是幅值a 1 。则 推导可得1 + u 一r 砸五 妒 1 + u + 、厄干互五。即当u ，妒同时满足这 些条件时，系统稳定。 3 当l 妒一u 一1 l = 2 扣，有a 1 = a 2 = 1 ，则系统处于临界稳定状态。 综上可知，系统渐进稳定，也就是p s o 算法收敛的条件是： 妒一u 一1 i 2 、五 a 1 + u v 2 + 2 w 妒 1 + u + 、虿而 ( 3 1 4 ) 此时由于g 的特征根幅值a 1 ，有 = c ，一g ，一1 b ： = 。妒，a + 乙。约，妒 ( 3 1 5 ) 鼽如 日og 伽 量i + 仇 吼 g 二垦i = 仇 吼 鲤 2 0粒子群优化算法在m a x _ s a t 上的应用研究 也就是说，在鼽，岛固定不变时，t c o ，佻( t ) 一。有( t ) 一( 妒1 a + 妒2 鳓) 加， 此值为a 与连线上的某一点，而豫趋于鳓，因此在固定时，p s o 在上溯条件 满足下可以保证戤( t ) 一p 。 ( i i ) 假设u ，妒为t 变化的时变函数时，公式3 8 则表示为线形时变系统，即： ：嚣：若 = g c ：罱 + b c ： c 3 s ， 此方程为齐次系统方程，根据离散时变系统的渐进稳定判别：如果存在一个对 于可( t ) 的标量函数口( ( t ) ) ，且任意y ( t ) 满足： 0 ( t ) ) 为正定 ( 封( ) ) = 钉( 封0 + 1 ) 一t j ( ( t ) ) 为负定 i i y ( t ) l i o o 时，有口( 可( t ) ) 一o 。 则系统在原点平衡状态y = o 为大范围渐进稳定。 设可( 亡) 一 薹暑 ，定义一标量函数 ( 箩( 啪= 恼( 驯| ，则有： ( ! ，( t ) ) 为正定 a v ( y ( t ) ) = 白 + 1 ) ) 一 ( t ) ) = j l y ( t + 1 ) 1 1 - i l y ( t ) l i ( i l c ( t ) l i - 1 ) i l y ( t ) l l ， 所以只要u ，满足式3 8 ，g ( t ) 特征根的幅值均小于1 ，因此面( ( t ) ) 负定。 i i v ( t ) l l o 。时，显然有t ，( 可( t ) ) 一o o ，所以，即使，妒为时变函数，只要满 足式3 8 ，即可保证p s o 渐进收敛。 上述分析只能保证渐进收敛，没有保证收敛于全局最优或者局部最优。实 际上基本粒子群即不能保证收敛于全局最优也不能保证收敛于局部最优。并且 上述分析中均假设不变，所以基本粒子群只能保证搜索到全局最优解则粒子 群渐进收敛于该点。 在上面的分析中，假设n ，如是固定的j 由于粒子群正是由于和在跌代中变 化才找到最优解，基本粒子群不能满足随机算法收敛准则，不是全局收敛算 法。f v a nd e nb e r g h 提出具有局部收敛的改进粒子群算法，并指出该算发布具 有全局收敛的性能【4 5 】。 第3 章粒子群优化算法 2 1 3 3p s o 算法的发展 通过上面的介绍，可以看到基本粒子群算法收敛性并不太理想，所以在其 之上提出了很多改进与优化方法。主要包括有对收敛速度的改进，增加多样性 的改进和其他改进策略。 收敛速度的改进主要是通过改变参数的控制，比如s h i 等提出惯性权重的 方法。惯性权重“，是与前一次速度有关的一个比例因子。s h i 等随后提出用模糊 控制器来动态自适应地改变惯性权重的技术【4 6 】o 控制器的输入是当前惯性权 重u 和当前最好性能评价值，输出是u 的改变量。c l e r c 得出压缩因子有助于确 保p s o 算法收敛 4 7 1 。a n g e l i n e 提出的混和p s o 主要应用p s o 的基本机制以及演 化计算所采用的自然选择机制。l v b j e r g 等人将遗传算法中的复制和重组这些 称为繁殖的操作加入到全局版p s o 中。 在改进多样性方面，s u g a n t h a n 提出了基于粒子的空间位置划分的方 案。k e n n e d y 通过对拓扑结构测试结果表明，拓扑非常影响算法的性能，且最佳 的拓扑形式因问题而定，并且提出了混和空间邻域和环形拓扑方法的另一个局 部p s o 版本，称为社会趋同法。 全局方法包括，b e a s l e y 等提出的最初使用在遗传算法中的序列生境 技术可以系统地访问每一个全局极值。为了减小定位所有全局极值的花 费，p a r s o p o u l o s 等将自适应改变目标函数方法应用到了p s o 中。 其他一些方法，比如文献 4 8 】中提出一种确保p s o 收敛到局部最优的改进方 法。文献 4 9 1 提出了一种协同p s o ，该方法是将n 维向量分n n 个粒子群中，每个 粒子群优化一维向量，评价适应值时将分量合成一个完整向量。 3 4p s o 算法的应用 p s o 的优势在于算法的简洁性，易于实现，没有很多参数需要调整，且不需 要梯度信息。p s o 是非线性连续优化问题、组合优化问题和混合整数非线性优 化问题的有效优化工具。目前已经广泛应用于函数优化、神经网络训练、模糊 系统控制以及其他遗传算法的应用领域。p s 0 最初应用到神经网络训练上，在 随后的应用中，p s o 又可以用来确定神经网络的结构。作为演化神经网络的例 子，e b e r h a r t 等已经成功用p s o 来分析人类的帕金森综合症等颤抖类疾病。文 献f 5 0 1 中用改进的速度更新方程训练模糊神经网络。p a r s o p o u l o s 等将p s o 用于 粒子群优化算法在m a x - s a t 上的应用研究 解决多目标优化问题、最小最大化问题、整数规划问题和定位所有全局极值等 问题。 除了以上领域外，p s o 在多目标优化、自动目标检测、生物信号识别、决策 调度、系统辨识以及游戏训练等方面也取得了一定的成果。 第4 章离散域上的粒子群算法 考虑到粒子群算法具有较强的全局和局部搜索能力，算法实现的简洁和稳 定表现，本文下面将重点讨论将粒子群算法应用在m a x - s a t 问题上所碰到的 问题和相应的解决方法。如前所述，m a x - s a t 问题属于离散域上的一种组合优 化问题，群体智能算法在此问题上的研究起步较晚，目前在遗传算法，蚁群算 法等上的研究比较活跃。粒子群优化算法虽然在连续域上表现出其独有的优势， 但在离散域上应用得还比较少，而且在m a x s a t 问题上的应用更是个空白。 解决此问题的前提是先找到一种离散化的方法，实现以粒子群算法为思想 的处理机制。基于基本的粒子群算法，最近已提出不少此模型的变种，本文选 取其中两种来处理m a x - s a t 问题，量子粒子群算法( q u a n t u mp s o ) 和模糊粒 子群算法( f u z z yp s o ) 。它们的基本思路就是根据问题的特点来重新定义粒子 的速度位置表示方法，运算法则，模拟粒子在离散空间中的运动。 下面分别介绍两种算法思想，针对m a x s a t 问题特点设计算法过程，研究 相应的处理方法并且比较分析实验结果。 4 1 量子粒子群算法( q u a n t u mp s o ) 物理学由于有现代科学技术的牢固基础，其发展带来了一些对自然的新 的认识。在研究”生物进化机制”的同时，”模拟事物”的想法也同样激发着人们 的新思想。这两种思想相互渗透并且产生了许多成功的新理论，比如遗传算 法、模拟退火算法( s a a ) 【5 1 】等。在此类进化类算法中，定义粒子是基于量子 位( q u b i t ) 并通过观察确定位置的，称此为量子粒子群算法。 4 1 1运动形式 在量子理论中，携带信息的最小单元是q u b i t ，它可以处于0 或者1 的位置状 态上。定义量子化的粒子信息如下： q ( t ) = q i ( t ) ，q 2 ( t ) ，( t ) 】( 4 1 ) q j ( t ) = 【g ( t ) ，馥( t ) ，磊( t ) 】 ( 4 2 ) 粒子群优化算法在m a x s a t 上的应用研究 其中0 酲( t ) 1 ( i = 1 ，) ，m 表示粒子的维度，表示粒子总 数，酲( ) 表示第j 个粒子的第i 位在第t 步时为0 的概率。通过随机观察来得到粒 子精确的离散值醒( t ) 。 具体如下：对于每个醇( t ) 0 = 1 ，m ，j = 1 ，) ，随机产生一个 o ，1 】 区间的实数，如果大于西( t ) ，则醒( t ) = 1 ；，否贝嵫( t ) = 0 ( 这里理( t ) 表示量 子化粒子磊( t ) 的离散值) 。其运动过程可以表示如下 量子化方程： 。婶k n ( 蔚) = q 盼。姊6 e 韩( 七) + p ( 1 一孙唧k 鲋( 七) ) q 蒯，k “( 南) = q p s e l ，6 e 。( 七) + 卢( 1 一p s e t f b e 武( 七) ) ( 4 3 ) ( 4 4 ) 运动方程： q ( k + 1 ) = c l - q ( k ) + c 2 q 。d ，k 。t ( k ) + c 3 q 扩咄“( 七)( 4 5 ) 其中a + p = 1 ，0 q ，p 1 称作控制参数，表示对q 的控制程度，q 值越大表示观察值与p ，。k “相同的几率越大，相当于使粒子向其方向运 动。c 1 + c 2 + c 3 = 1 ，0 ，。抛“) t h e n l 缱。m “= g ( k4 - 1 ) b 咖玷e 。t = 9 e t b e s t ( 只e i ，k “) r e t u r n 珞k s t 这里需要注意的是，自身和全局最优解仇e l ，6 e 时和p f f r o u 出“保存的是精确 解，所以计算前应该对其量子化。运动迭代的每步根据p 。，o 。p b e “精确值通过量 子化方程得到蛎o u p 6 e “。同样对每个粒子的挑。l m “也要计算相应的吼。f ，k m 然后 根据运动公式计算当前粒子的下一个量子化位置矿( + 1 ) ，通过观察，也就是 将矿( 七4 - 1 ) 与随机数比较得到位置的离散值，在新位置下计算适应值并择优更 新p ，。，6 e 。和仇。r ，k 。最后进入下一个运动过程直到达到最大迭代次数为止。 4 2 模糊粒子群算法( f u z z yp s o ) q u a n t u mp s o 中并没有把位置和速度分开计算，只是统一使用概率值来表 示，相比之下，f u z z yp s o 依然维持了基本粒子群算法的公式形式，但是为了使 粒子在离散空间上的运动更自然一些，在基本p s o 算法之上，重新定义位置速 度以及运算方式。 粒子群优化算法在m a x - s a t 上的应用研究 4 2 1 位置和速度的重新定义 在此模型下，粒子的位置向量中的元素并不是用一个数值来表示，而是表 示为一些可能值的模糊集，既是说，对于一个位置向量的第i 个元素是一个集合， 集合的大小h l 是指第i 个元素所有可能取值的个数，集合中的元素属于【0 ，1 1 区 间，称为确定系数，一般使用矩阵来表示。 对于m a x - s a t 问题，设原位置为p = ( m p n ) ，那么其模糊态位置为： p ：f 期m1 ( 4 6 )= ii【4 b j p 1 2 p