改进蚁群算法在求解加权maxsat问题中的应用

《改进蚁群算法在求解加权maxsat问题中的应用》由会员分享，可在线阅读，更多相关《改进蚁群算法在求解加权maxsat问题中的应用（56页珍藏版）》请在金锄头文库上搜索。

1、分类号工P 鲤 。 U D C 全日制工程硕士学位论文 改进蚁群算法在求解加权M A X S A T 问 题中的应用 李炳慧 学科专业丑：篡扭这丕 指导教师廑云基副数援 论文答辩日期 2 Q ! ! ：2 1学位授予日期 答辩委员会主席王渔速数援 论文评阅人王渔速崔耀丕 2 0 1 1 7 1 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有，本人保证不以其它单位为第一署名单位发表或使用本论文 的研究内容。除已注明部分外，论文中不包含其他人已经发表过的研究成果，也不包含 本人为获得其它学位而

2、使用过的内容。对本文的研究工作提供过重要帮助的个人和集 体，均已在论文中明确说明并致谢。 论文作者签名：杏炳慈 学位论文使用授权说明 2 0 1 1 年f 月7 日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本： 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：专黼董导师签名：廖习砺 2 0 1 1 年

3、f 月中日 广西大学全日制工程硕士掌位论文舒口毛蚁群算法在求解加权M A X S A T 问题中的应用 改进蚁群算法在求解加权M A X S A T 问题中的应用 摘要 蚁群算法是一种智能仿生优化算法，具有正反馈性、天然的并行性和 较强的鲁棒性、自组织性等优点。蚁群算法是一种根据大自然中的蚂蚁觅 食规律形成的人工蚁群算法，根据蚂蚁通过最短路径寻找到食物的原理来 求解组合优化问题，利用信息素通信的特点，快速收敛到求解问题的最优 值。经过大量的实验研究表明在实际应用中蚁群算法具有很强的适应性和 发展前景。 可满足性问题S A T 属于命题逻辑中合取范式( C N F ) ，是一个N P 一难问 题

4、。如今S A T 问题是计算复杂性理论研究和人工智能领域研究中的一个核 心问题。现在很多领域的研究都离不开S A T 问题，比如地质勘探、天气预 报、卫星定位系统、机器学习、V L S I 集成电路的设计和检测、逻辑推理机 等都获得了应用，因此研究可满足性问题就显得具有极其重要的理论意义 和现实价值。最大可满足性问题S A T 是S A r 问题的一个扩展，有两 种形式：一种为满足子句数为研究对象，一种则是子旬加权情况为研究对 象。本文研究的重点是在加权最大化可满足问题w M S A T 中的应用。 本文结合蚁群算法在求解组合优化问题时的优越性，首先提出了运用 改进的蚁群算法( I A C A

5、 ) 在加权。S A r 问题中求解问题，将问题进行 重离散化，用取值概率代替信息素机制，提高算法求解的效率和质量，并 与经典的搜索算法w 札K S A T 算法的求解结果进行比较。实验结果表明， 广西大掌全日制工程硕士掌位论文彩睛龟蚁君# 算法在习 露加权M A X S A T 问题中的应用 改进后的蚁群算法在加权心S A T 问题中的应用是行之有效的。 其次，把蚁群算法进行并行化改进，让算法在多核环境下并行化的寻 找问题的最优值，再让算法求解加权M A X S A T 问题，并分析并行算法的 加速比和效率。和之前的实验结果进行比较，得出并行化的蚁群算法求解 问题的时间明显减少，取得了较好的

6、的加速比和效率。 关键字：蚁群算法，加权最大化可满足性问题，并行算法， 广西大学全日制工程硕士掌位论文改进蚁群算法在求解加权M A X S A T 问题中的应用 I m p r o V e da n tc o l o n ya l g o r i t h m i ns o I V i n gW e i g h t e dM A X S A T p r o b l e mo fa p p l i c a t i o n A b s t r a c t A n tc o l o n ya l g o r i m mi sak i n do fi n t e l l i g e n to p t i

7、 m i z a t i o nb i o n i ca l g o r i t h m ， h a ss e v e r a ls 仃o n g p o i n t ，s u c ha Sp o s i t i V ef e e d b a c k ，n a ：t u r a lp a r a l l e l i s m ，s t r o n g r o b u s t n e s sa n ds e l f o 曙a n i z i n g A n tc o l o n ya l g o r i m mi sah n do fm a 玎匹血l d a l g o r i t h m a c

8、 c o r d i n gt o a n tf o r a g i n gr e g u l 撕t yo fn a ：t u r e ，a n di ts o l V e s c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sa c c o r d i n gt om eo r i g i n a lo fs h o 他s tp a t ho f a n t sg r o u pf m d i I l gf o o d B yp h e r o m o n ec o m m u n i c a t i o n 诧a

9、t u r e s ，t h ea l g o r i t l l m c a nr 印i d l yc o n V e r g e n c et oo p t i m a lV a l u eo fp r o b l e m A g r e a t d e a lo f e x p e r i m e n t a lr e s e a r c hs h o w sm a ta n tc o l o r l ya l g o r i t h mh a ss 仃o n ga d 印t a b i l i 够 a n dd e v e l o p m e n tp r o s p e c t si

10、 na C t u a l 印p l i c a t i o n S a t i s f i a b i l i 够p r o b l e m ，o rS A r ，b e l o n g st op r o p o s i t i o nl o g i cb yt h eC N F p a r a d i g I I l ，a J l di ti sa I lN P d i 伍c u l tp r o b l e m N o wS A Tp r o b l e mi sac e n t r a li s s u e t o c o m p u t a t i o n a lc o m p l

11、 e x i 够t 量l e o 巧 r e s e a r c ha n dt l l ef i e l do fa r t i f i c i a l i n t e l l i g e n c er e s e a r c h N o wm a n y a r e a so fr e s e a r c ha r ei n s e p a r a b l e 自o mt h eS A r p r o b l e m ，s u c ha sm eg e o l o g i c a lp r o s p e c t i n g ，w e a t h e rf o r e c a s t i

12、n g ，G P S ，m a c h i n e l e 锄i n g ，D F Mi n t e g r a t e dc i r c u i td e s i g na n dt e s t i n g ，l o g i c a lr e a s o I l i n gm a c h i n e e t c S ot h es t u d yo fS A Tw o u l dh a v ei r n p o r t a n tm e o r e t i c a la n dp r a c t i c a lV a l u e M a x i m u ms a t i s f i a b

13、i l i 够p r o b l e m ，o rM AX S A r ，i sa ne 殖e n d e dS A Tp r o b l e m ， a n dh a st w ob n d so ff o m O n ef o rt h em a xn 1 且m b e ro fs a t i s f i e dc l a u s e s ，a n dm e 3 广西大掌全日制工程硕士掌位论文 改进蚁群算法在求解加权 & A X S A T 问题中的应用 o m e rf o rm 觚s u mw e i g h to fs a t i s f i e dc l a u s e s T h

14、 i ss t u d yf o c u s e so nt h es e c o n d O n e B a s e do nn l e s u p e r i o r i t y o fs o l V i n gm ec o m b i n a t I D r i a lo p t i m i z a t i o n p r o b l e m s ，m i sp a p e rp r o p o s e da I li m p r o V e da n tc o l o n ya l g o r i t h m ( I A C A ) f o r w e i 曲t e d M A X S

15、 A T I th a st 、舳f e a ：t u r e sf o r i m p r o V i n gt h eq u a l i t y 髓d e 伍c i e n c yt oo u ra l g o r i t h m F i r s t ，i tm a d ed i s c r e t i z a t i o nf o rt h ep r o b l e m t om a k e i tt ob es o l V e dm o r en 舭d l y A n dt h e ni tr e p l a c e dp h e r o m o n em e c h a I l i

16、s mw i t h V a l u ep r o b a b i l 咄A n dw eh a v ec o m p a r e dw i t hc l a S s i c a l 础正K S A Ti ns o l V i n g e a e c t E x p e r i m e n t mr e s u l t ss h o wm a tt h ei m p r o V e da n tc o l o n ya l g o r i t hf o r w e i 曲t e dM - A X S A Tp r o b l e mi sm o r e e f r e c t i V e N e x t ，t h i sp 印e ra c c e l e r a t e dt h ea l g o r i t h mb yp a r a l l e l i z m g b a s e do n m u n i c o r ee n V i r o 啪e n ta I