基于ABC算法的逻辑推理题快速求解方法_李林菲

计算机技术与发展第21卷　第6期　　　　　　　　　　ol.21　No.6　　　　　　　　　　V

2011年6月June　2011COMPUTERTECHNOLOGYANDDEVELOPMENT

基于ABC算法的逻辑推理题快速求解方法

李林菲,马　苗

(陕西师范大学计算机科学学院,陕西西安710062)

摘　要:针对逻辑推理题求解空间大、求解时间长的问题,模仿自然界蜜蜂采蜜现象,利用操作系统的多线程并发机制,提出并实现了一种基于人工蜂群算法的逻辑推理题求解方法。该方法以各个线程作为不同角色的蜜蜂,将求解逻辑推理题的过程转化为人工蜂群寻找最优蜜源的过程,通过人工蜂群算法中侦查蜂、引领蜂和跟随蜂的分工协作快速完成逻辑推理题求解。在VC++6.0环境中,对10个组合问题求解的仿真实验表明,该方法求解速度明显优于未使用蜂群算法的单线程算法。

关键词:人工蜂群算法;多线程并发;组合优化

中图分类号:TP391.41　　　　　　文献标识码:A　　　　　　文章编号:1673-629X(2011)06-0125-03

ArtificialBeeColonyAlgorithmBasedSolution

MethodforLogicReasoning

LILin-fei,MAMiao

(SchoolofComputerScience,ShaanxiNormalUniversity,Xi'an710062,China)

Abstract:Asthesolutionspaceoflogicreasoningislargeandtheprocedureofreasoningistime-exhausting,proposeafastandefficientsolutionmethodbasedonartificialbeecolony,whichimitatesthephenomenonofbeeforagingandutilizesthemultithreadingconcurrentmechanismofoperatingsystem.Thismethodtakeseachthreadasabeewithacertainrole,andtheprocessofreasoningastheprocesstofindthebestnectarsourceinartificialbeecolony.InVC++6.0environment,ourexperimentalresultsona10constrainedproblemsshowthatthemethodisobviouslyfasterthanthesinglethreadmethodwithoutartificialbeecolonyalgorithm.Keywords:artificialbeecolonyalgorithm;multithreadconcurrency;combinatorialoptimization

0　引　言

丰富多彩而纷繁复杂的自然界启迪了无数的科学发明。群体智能来源于科学家们对群居生物的观察和研究,通过研究分散、自组织的动物群体和人类社会的智能行为,关注群居动物的社会习性,科学们提出了许多迥异于传统思路的智能算法

[1～5]

意见,然后通过投票决定。事实显示,几乎所有遵循蜜蜂法则的团体都能使自己变得更加聪明。

蜂群算法(BeeColonyAlgorithm)是建立在蜜蜂自组织模型和群体智能基础上提出的一种非数值优化计算方法。在Seeley提出的蜂群自组织模拟模型中,尽管每个社会阶层中的蜜蜂只完成单一任务,但蜜蜂相互间通过摇摆舞、气味等多种信息方式,使得整个蜂群能协同完成诸如构建蜂巢、收获花粉等多项任务

[1]

,例如:聚类算法、

遗传算法、蚁群算法、粒子群算法以及鱼群算法等,很好地解决了很多棘手复杂的工程问题。

通过对蜜蜂的长期观察,康奈尔大学的生物学家Seeley发现虽然在一个蜂房里的工蜂多达几万只,但它们仍可以“集思广益”、“各抒己见”,使得蜂群能够统一分歧,为群体谋得最大利益

[5]

。

2005年,Karaboga成功地把蜂群算法应用在函数的数值优化问题上,提出了比较系统的群体智能优化算法———ABC(ArtificialBeeColony,ABC)算法和粒子群算法具有更好的优化性能

[7]

[6]

,函数

。Seeley把从蜜蜂

优化测试表明,ABC算法比遗传算法、差分进化算法

。2007年

Karaboga和Basturk等人将人工蜂群算法理论应用到解决非限制性数值优化和限制性数值优化的问题上,均取得了较好的效果具有收敛速度快

[9]

[8]

身上学到的决策方法运用到一些会议上,模拟蜜蜂的决策,让与会者考虑所有的可能性,提出各自的想法或

收稿日期:2010-12-20;修回日期:2011-02-21

基金项目:陕西师范大学青年教师教学改革研究项目(2010063)作者简介:李林菲(1988-),女,研究方向为智能优化算法及其应用;马　苗,副教授,博士,主要研究方向为灰色理论、图像处理和数。

综上所述,鉴于人工蜂群算法在非数值优化方面

、求解质量高、鲁棒性好、通用性强

,,结

·　　　126·　　　　　　　　　　　　　　　　　　计算机技术与发展　　　　　　　　　　　　　　　　　　第21卷

合操作系统中的进程、线程、信号量、互斥锁等机关知识,实现一种快速求解逻辑推理题的新方法。

位置来代替:

x×φij=xijxijimin

max

m(3)

其中φ是取值在

0,之间的随机数。

1　人工蜂群算法

自然界中的蜜蜂总是可以很快发现优良蜜源,并通过自身的改变适应环境的变化。蜂群一般是由侦查蜂(scouts)、引领蜂(leader或employedforagers)和跟随蜂(follower或onlookers)组成。在人工蜂群算法中,首先蜜蜂均以侦查蜂身份搜索食物源,找到食物源后开始采蜜,并进行角色转换,由侦查蜂转变成引领蜂,同时它还利用自身的存储能力记录食物源的收益率。当引领蜂返回到蜂巢卸载下花蜜后,对等候在舞蹈区的跟随蜂进行招募。每一个跟随蜂观察所有引领蜂的舞蹈后,按照一定的概率选择引领蜂,之后跟随蜂也会像侦查蜂一样对食物源进行修正和进行角色转换,以便寻找更优的食物源。这样的行为反复进行直到最终找到最优的食物源。其中,当进行若干次搜索后,如果存在某些食物源的收益率未得到提高,则对应的引领蜂就转换为侦查蜂,同时再次在同一食物源附近进行搜索,从而避免搜索陷入局部最优

ABC算法的主要步骤可概括如下:

1)蜂群xi=1,2,…,n;j=1,2,…,的初ij 始化

,n为人工蜂群的规模,d为搜索空间维数,xi=只蜜蜂所在位置。xj=1,2,…,表示第iij

2)计算蜂群中各侦查蜂的适应度函数值,记录当前群中的最大花蜜量及其蜜源位置。

3)引领蜂根据记忆的信息在其邻域附近进行搜索,产生新位置vj=1,2,…,:ivij

v×φij=xijx

ij-1,之间的随机数。

4)计算新位置v的适应度函数值,并根据贪婪准i

则,若v优于x否则不变。ii,则更新xi;

5)根据x的适应度函数值fitii,计算概率Pi:Pifitiit∑f

i=1n

10)重复步骤3)～9),直到达到最大迭代次数,输出最佳蜜源位置,即最优值。

2　基于ABC算法的逻辑推理题求解方法

2.1　方法描述

逻辑推理题的求解过程与蜜蜂的采蜜行为有许多相似之处:

(1)由蜂群中的多只蜜蜂联想到逻辑推理题求解中调用的多个线程;

(2)由侦查蜂随机寻找食物源,联想到逻辑推理题随机生成解空间;

(3)由侦查蜂通过摇摆舞与引领蜂共享食物源信息,联想到逻辑推理题求解中通过一个存储空间实现线程之间的信息共享;

(4)由引领蜂根据侦查蜂的搜寻结果,寻找搜寻结果中高收益率食物源,联想到在逻辑推理题的求解中,先从解空间中通过淘汰率最高的条件判断,淘汰一部分明显错误的解,减少程序误运行的次数;

(5)由引领蜂通过摇摆舞为食物源招募采蜜蜂,联想到在逻辑推理题的求解中,通过索引表来向其他线程传达信息;

(6)由跟随蜂采集花蜜的过程联想到逻辑推理题求解中依条件判断可能解的过程。有花蜜,采集;可能解符合所有条件,将其打印出。采集完毕,丢弃食物源;检测完毕,释放相应的存储空间。

综上所述,蜜蜂与环境之间的信息交流模型可以被用于逻辑推理题的求解中,以实现动态的、自适应的求解过程。

下面给出将人工蜂群算法应用到逻辑推理题求解的主要思路:

1)遍历函数模拟侦查蜂,通过遍历法动态生成解空间(舞蹈区)data been,由于随机生成和顺序生成的结果相同,所以为简单起见,使用顺序生成;

2)创建线程模拟引领蜂,引领蜂从舞蹈区(data been)获取食物源信息,通过问题2,淘汰收益率较低的解(一部分明显错误的可能解),通过计算可知,不被淘汰的概率,即食物源的收益率为5×4/5100%=0.8×100%=40.96%;

3)创建线程模拟跟随蜂,跟随蜂从舞蹈区(index)获取引领蜂的招募信息,以及相应的食物源信息,进行采蜜。为了防止线程之间出现死锁,引入了操作系统中关于信号量机制方面的一些知识,充分利用CPU,实[11,12]

[10]

。

(1)

其中k是i附近的一个值,且k≠i,φ是取值在

(2)

6)根据从引领蜂那里获得的信息,跟随蜂依概率P选择一个蜜源位置,在该位置附近搜索,从而产生一i个新位置,并计算该位置下适应度函数值。

7)根据贪婪准则,比较新位置和记忆中位置的花蜜量,并且总是记住花蜜量大的位置。

8)记录迄今为止所获得的最大花蜜量,以及拥有最大花蜜量的位置。

9)判断是否有蜜源经过限定的循环次数limit未

,×

　第6期　　　　　　　　　　　　　李林菲等:基于ABC算法的逻辑推理题快速求解方法

·127·

基于蜂群算法的求解逻辑推理题的过程如图1,主要步骤描述如下:

step1运用遍历法,模拟侦查蜂寻找食物源,并将食物源信息动态保存到data been中;

step2若data been不空,引领蜂从解空间中获取食物源信息,并对相应食物源判断其花蜜量,通过高淘汰率的逻辑题(实例中为第2题)淘汰花蜜量低的解,并将高花蜜量解保存到index;否则,执行step5;

step3若index不满,引领蜂根据索引值寻找相应的食物源,并将信息通过索引表index与跟随蜂共享,即引领蜂进入舞蹈区,招募跟随蜂;否则,执行step2;

step4跟随蜂采集食物源,若是最优解,将其打印出;否则执行step3;

step5程序结束

。

答案相差几个字母?(a)4;(b)3;(c)2;(d)1;(e)0(注:a和b相差一个字母)

8)答案是元音字母的问题的个数是?(a)2;(b)3;(c)4;(d)5;(e)6(注:a和e是元音字母)

9)答案是辅音字母的问题的个数是?(a)一个质数;(b)一个阶乘数;(c)一个平方数;(d)一个立方数,(e)5的倍数

10)本问题的答案是?(a)a;(b)b;(c)c;(d)d;(e)e

综上可知,每道题的答案之间联系紧密,有着严密的逻辑推理关系。每个题有5种可能的答案,因此,从排列组合的角度来看,整个题的解空间为5

9765625种可能解。每一个可能解需要用上述的10个条件来检测,只有同时符合10个条件的才是正确解。

在WindowsXPVC++6.0环境下,将文中方法与未使用蜂群算法的单线程算法进行比较,结果是两者对逻辑推理题的求解结果完全相同均为“c,d,e,b,e,e,d,c,b,a”的情况下,单线程的求解算法运行时间为73.687s,基于人工蜂群算法的而提出的多线程算法运行时间为5.391s,大大缩短了求解时间。

3　结束语

文中提出的基于ABC算法的逻辑推理题求解方法不是简单地用宏观控制的多线程来减少时间,而是让线程之间用少量信息交流来自主实现整体运算的计算最优化,明显缩短了推理求解的时间。潜在应用包括基于机器人群体的各类工作,例如根据人的生命体征寻找地震中的幸存者、由面部特征清除恐怖分子或

图1　基于ABC算法的逻辑推理题求解流程图2.2　求解实例与结果分析

下面结合一个目前比较流行的逻辑推理题实例进行文中方法的验证,问题描述如下:

1)第一个答案是b的问题是哪一个?(a)2;(b)3;(c)4;(d)5;(e)6

2)唯一的连续两个具有相同答案的问题是?(a)2,3;(b)3,4;(c)4,5;(d)5,6;(e)6,7

3)本问题答案和哪一个问题的答案相同?(a)1;(b)2;(c)4;(d)7;(e)6

4)答案是a的问题的个数是?(a)0;(b)1;(c)2;(d)3;(e)4

5)本问题答案和哪一个问题的答案相同?(a)10;(b)9;(c)8;(d)7;(e)6

6)答案是a的问题的个数和答案是什么的问题的个数相同?(a)b;(b)c;(c)d;(d)e;(e)以上都不是

,参考文献:

[1]　王艳玲,李龙澍,胡　哲.群体智能优化算法[J].计算机

技术与发展,2008,18(8):114-117.

[2]　黄德双.智能计算研究进展与发展趋势[J].科学发展,

2006,21(1):50-56.

[3]　王宇庆,刘维亚.群体智能在图像处理中的应用[J].计

算机应用,2007,27(7):1647-1650.

[4]　王丽丽,苏德富.基于群体智能的选择性决策树分类器集

成[J].计算机技术与发展,2006,16(12):55-57.[5]　方陵生.蜂群理论与群体智慧[J].世界科学,2007(11):

37-39.

[6]　KarabogaD.Anideabasedonbeeswarmfornumericalopti-mization[R].[s.l.]:[s.n.],2005.

[7]　KarabogaD,BasturkB.Ontheperformanceofartificialbee

追查在逃案犯、根据化学特性查找化学物渗漏处以及垃圾分类等。

(下转第230页)

·　　　230·　　　　　　　　　　　　　　　　　　计算机技术与发展　　　　　　　　　　　　　　　　　　第21卷

-100010

00000

0-1001100000

00-100100000

000-100010000.890

00000-1010000

0000-10000010

0000000-11000

000000-10100T

00000000-01

5　结束语

从以上内容可知,新定义的面向故障诊断的模糊Petri网能够较好描述故障的动态产生过程和传播过程,且针对故障诊断系统建模相对容易。文中给出的状态方程及其分析方法涵盖了多种运算形式,易于建模和计算机编程实现。从某设备控制系统故障诊断的实例分析来看,分析结果与图形分析方法完全吻合。

参考文献:

[1]　Manyari-RiveraM,BasilioJC,BhayaA.Integratedfault

diagnosisbasedonPetrinetmodels[C]∥16IEEEInterna-tionalConferenceonControlApplicationsPartofIEEEMulti-conferenceonSystemsandControl.Singapore:[s.n.],2007:958-963.

[2]　DingCaihong.ApplicationofPetrinettofaultdiagnosisin

satellite[J].Journalofsystemsengineeringandelectronics,2001,12(2):92-96.

[3]　ZhouChunlai,JiangZhongchng.FaultdiagnosisofTVtrans-mittersbasedonfuzzyPetrinets[C]∥IMACSMulticonfer-enceonComputationalEngineeringinSystemsApplications(CESA).Beijing,China:[s.n.],2006:2003-2009.[4]　付阶辉.基于Petri网的故障诊断方法研究[D].南京:东

南大学,2004.

[5]　宗　群,王　波,牙淑红.模糊Petri网在电梯故障诊断中

的应用[J].起重运输机械,2004(4):44-47.

[6]　NazarethDL.InvestigatingtheapplicabilityofPetrinetsfor

rule-basedsystemverification[J].IEEETransactionson

U00

2)M0=[000.8900000000],N=dia[.72.76.83.85.77.80.89.90.86];,调用状态方程公式(1)生3)T3发生,TS成新的状态:

M1=[000.89000.738700000];4)由M1知T3、T5使能,搜索TS知T5可以发生;故:

U10

0.7837

调用状态方程公式(1),生成新的状态:M2=[000.89000.738700.603000]故:

U20依次得:U30

0.T

由M2知T3、T5、T7使能,搜索TS知T7可以发生;

0.603

M3=[000.89000.738700.6030.53700]

KnowledgeandDataEngineering,1993,5(3):402-415.[7]　向永生,刘　武,乐晓波,等.基于模糊Petri网的汽车故障

诊断仿真研究[J].计算机工程与科学,2009(3):86-88.[8]　张白一,崔尚森.基于模糊Petri网的汽车故障诊断方法

[J].长安大学学报,2008(3):93-96.

[9]　孙　健,杨润生,朱新华.Petri网技术在火控系统故障诊

断中的应用[J].军械工程学院学报,2007(4):23-27.[10]张　炜.一种面向故障诊断的故障Petri网[J].甘肃联合

M4=[000.89000.738700.6030.53700.462]束。

最后得:

M4=[000.89000.738700.6030.53700.462],

T,无变迁可以触发,推理结ST3,T5,T7,大学学报,2010(5):18-21.

[11]袁崇义.Petri网原理与应用[M].北京:电子工业出版社,

2005.

[12]徐晶明,杜宝珠.基于Petri网化简技术的工作流过程模型

结构验证[J].计算机技术与发展,2009,19(6):51-54.

顶事件P11对应模糊值为0.462,按模糊等级为“很可能”,说明底事件P3很可能导致顶P11发生,计算结果与图2中最终分析结果完全一致。

(上接第127页)

　　colony(ABC)algorithm[J].AppliedSoftComputing,

2008,8(1):687-697.

[8]　KarabogaD,BasturkB.ArtificialBeeColony(ABC)Optimi-zationAlgorithmforSolvingConstrainedOptimizationProb-lems[J].LNCS:AdvancesinSoftComputing:FoundationsofFuzzyLogicandSoftComputing,2007,4529:789-798.[9]　胡中华,赵　敏.基于人工蜂群算法的无人机航迹规划研

,([10]梁西安.分层蜂群算法的研究[EB/OL].2009.http://

www.paper.edu.cn/index.php/default/releasepaper/con-tent/20091-479.

[11]牛欣源.进程同步的资源管理模型构建与应用[J].计算

机技术与发展,2010,20(6):9-12.

[12]王文磊,徐汀荣.多线程编程技术实现经典进程同步问题

[J].计算机技术与发展,2006,16(3):110-112.

基于ABC算法的逻辑推理题快速求解方法_李林菲

相关文章