《人工蜂群算法分析与实现毕业论文.doc》由会员分享，可在线阅读，更多相关《人工蜂群算法分析与实现毕业论文.doc（21页珍藏版）》请在三一办公上搜索。
1、人工蜂群算法分析与实现李林菲(陕西师范大学 计算机科学学院，西安 710062)摘 要：在了解蜜蜂采蜜原理和蜂群优化算法的基础上，分析基本的人工蜂群算法，结合操作系统的相关知识，将求解智力题的过程转化为蜂群寻找最优蜜源的过程。针对智力题求解实例，用线程模拟不同角色的蜜蜂，模仿人工蜂群算法(ABCA)中各个蜜蜂并行地完成智力题求解。在VC+6.0环境中的仿真实验表明，该算法全局搜索能力强，运算效率比单线程的算法明显高出十余倍。关键词：人工蜂群算法；群体智能；组合优化1 绪论群集智能优化算法起源于研究者们对自然界的生物进化过程和觅食行为的模拟。它将搜索或者优化过程模拟为个体的觅食或者进化过程，使用
2、搜索空间中的点模拟自然界中的个体；把求解问题的目标函数转化成个体对环境的适应能力；将个体的优胜劣汰过程或觅食过程类比为在搜索和优化过程中用较好的可行解取代较差可行解的迭代过程，从而形成了一种以“生成+检验”特征的迭代搜索算法，是一种求解极值问题的仿生学自适应人工智能技术。1.1群体智能的产生针对自然界中一些社会性昆虫群体行为的不解，如蚂蚁和蜜蜂群体智能的来源，个体简单行为如何形成复杂的群体行为，成百上千的蜜蜂如何协调做出某个重要决定，是什么让一群鲱鱼在一瞬间改变行动方向，为什么蚂蚁数量会随着周围环境的变化而变化等群体行为，在过去的数十年里，研究人员有了一些有趣的发现。图1 蚂蚁群体斯坦福大学的
3、生物学家黛博拉M戈登( Deborah M. Gordon)9博士在亚利桑那州沙漠对红蚁的观察和研究中发现，单个的蚂蚁并不聪明，聪明的是它们的群体。蚂蚁通过触觉和嗅觉互相交流信息，后再做出决策。对于下一步工作如何安排，则由整个蚁群决定，而不是某个特定的个体。这就是蚂蚁“群体智慧”的工作原理。它们遵循简单的经验法则，个体以局部信息为行动依据，没有一个蚂蚁能够通观全局，也没有一只蚂蚁知道其他蚂蚁在做什么。对于它们来说，复杂的行为是通过个体间简单的接触完成的，它们不需要带头者。就个体而言，蚂蚁微小得不堪一击，但是从群体来看，它们能够对不同的环境做出迅速而有效的反应，其“武器”就是群体智能。图2 蜜蜂
4、群体康奈尔大学的生物学家托马斯西利( ThomasSeeley) 9经过长期观察蜜蜂,发现在一个蜂房里的工蜂虽然多达50000之多，但它们依然能统一分歧，为蜂群谋得最大的利益。它们依据“集思广益”、“各抒己见”的法则做出决策，使用一种有效的机制使选择最小化。同时，西利把从蜜蜂身上学到的决策方法运用到一些会议上，模拟蜜蜂的决策，让与会者考虑所有的可能性，提出各自的想法或意见，然后通过投票决定。事实证明，几乎所有遵循蜜蜂法则的团体都能使自己变得更加聪明，例如股票市场的投资者们，从事研究的科学家们，甚至猜测罐中豆子数量的小孩们，如果他们是一个多样化的、有着各自独立见解的群体，并使用表决、求平均值之类
5、的办法来获得决策，都可能成为聪明的群体。图3 鸽子群体克雷格 雷诺兹( CraigReynolds)9对鸽子的群体行为研究，以及成功创建的计算机模拟程序，不仅展示了动物的自组织模式，同时也为机器人工程拓展了道路。一组能够协调工作的机器人就像鸟群一样，比单一的机器人聪明。如果机器人群体遭遇某些意外的情况，即使它们的智能化程度不是很高，也能较为迅速地做出反应并进行调整。如果群体中一个机器人出现故障，其他机器人会替代它的位置。而且群体机器人的控制权是分散的，不依赖某个特定的领袖。正如宾夕法尼亚大学机械工程学教授维嘉库马尔( Vijay Kumar)9 所说，在生物中有大批成员的群体极少有中心领导的情
6、况。图4 鹿群由赫乌尔9对鹿群长达5个月的研究中可知，每只驯鹿都知道其邻伴将要做什么，没有预见性，无因无果，一切就在瞬间发生了。尤其是鹿群遭遇狼时，就更显示出典型的群体智慧：驯鹿知道什么时候该跑，应该往哪个方向跑。整个过程中没有一头驯鹿去安排鹿群该往何处跑，它们仅仅遵循着数千年养成的简单的经验法则。华盛顿大学的生物学家丹尼尔格伦鲍姆(DanielGrnbaum)9对海洋中的鱼群研究，发现也有类似的行为。这就是动物群体智能的非凡魅力。不论是蚂蚁、蜜蜂、鸽子、驯鹿，还是鱼群，这些智能群体基于自身经验的简单法则，为人类提供了解决复杂问题的策略，群体智能也由此产生。因此，把群体智能(Swarm Int
7、elligence)定义为：指由众多无智能的简单个体组成群体，通过相互之间简单的合作，表现出智能行为的特性。自然界中的动物、昆虫，常以集体的力量进行觅食生存，单个个体所表现出的行为是缺乏智能的，但由个体组成的群体却表现出了一种有效的复杂的智能行为。群集智能可以在适当的进化机制引导下，通过个体间交互，以某种突现的形式发挥作用，这是个体以及可能的智能个体难以做到的。因此，可以将自然界中这些呈现群体行为特征的生物的行为，用简单的几条规则在计算机中建模，动物以群落形式生存觅食时一般遵循三个规则12：1) 分隔规则：尽量避免与临近的伙伴过于拥挤；2) 对准规则：尽量与临近的伙伴的平均方向保持一致，向目的
8、地运动；3) 内聚规则：尽量地朝临近伙伴的中心移动。 以上规则可归结为个体信息和群体信息两类，前者对应于分隔规则，也就是个体根据自身当前的状态进行决策；后者对应于对准规则和内聚规则，即个体根据群体的信息进行决策。另外，由于动物的行为一般具有适应性、盲目性、自治性和突现性以及并行性等特征，因此自组织性、突现性成为群集智能优化算法的两大基本特征。群居性的动物涌现出的群集智能正越来越受到人们的重视，一些启发于群居性生物的觅食、筑巢等行为而设计的优化算法吸引了大量的国内外学者的研究，成为解决传统结构优化问题的新方法。1.2 群体智能的现状丰富多彩而又纷繁复杂的自然界启迪了无数的科学发明，群体智能来源于
9、科学家们对群体性生物的观察和研究。作为近年来发展迅速的人工智能学科领域，利用群体智能解决各种问题的研究，越来越受到人们的重视。学者们通过研究分散的、自组织的动物群体和人类社会的智能行为，关注群居动物的社会习性，提出了许多迥异于传统思路的智能算法，例如：聚类算法、遗传算法、蚁群算法、粒子群算法以及鱼群算法等，很好地解决了不少原来非常棘手的复杂工程问题，在某些领域得到了广泛的运用。1.2.1主要的群体智能算法介绍(1)蚁群算法20世纪90年代初有意大利学者Dorigo ,Mahiezzo ,Colorni等人13受到人们对自然界中真实蚁群的群集智能行为的研究成果的启发提出来的一种新型的模拟进化算法
10、，并称为蚁群系统(AS)。蚁群算法充分利用蚂蚁寻找食物的过程与著名的旅行商问题(TSP)之间的相似性，通过模拟蚂蚁个体间的信息交流与相互协作，最终找到从蚁穴到食物源的最短路径来求解TSP问题。由于蚂蚁能适应环境的变化，诸如路上突然遇到障碍物，能快速重新找到最优路径；信息素不仅通过量反映路径被选择的概率，也随时间的推移逐渐挥发消失，因此，蚁群算法随后也在求解job-shop调度问题、指派问题等经典优化问题中取得了较好的效果，在求解离散优化问题中显示出优越性。然而，由于基本蚁群算法进化收敛速度慢，且易陷入局部最优或者出现停滞现象等缺陷，学者们也相继提出了各种改进的蚁群算法，具有代表性的主要有:19
11、96 年Gambardella 和Dorig 提出了采用伪随机选择机制对AS的蚂蚁选择策略进行改进的自适应蚁群算法(AAS)；随后，Stutzle等人就信息素更新机制进行改进提出了最大最小蚁群算法(MMAS)。(2)鱼群算法由李晓磊、邵之江13等提出，算法中采用了自上而下的寻优模式魔法自然界的鱼群觅食行为，主要利用鱼的觅食、聚群和追尾行为，构造出了个体的底层行为；通过鱼群中各个体的局部寻优，实现全局最优值在群体中突现出来的目的。在基本的鱼群算法中引入鱼群的生存机制、竞争机制以及协调行为，能够提高算法的优化效率。李晓磊等据此采用分解协调的思想又构造了一种改进的人工鱼群算法，并以换热器系统为例，验
12、证该算法，结果表明该算法具有较好的收敛性13。因此，人工鱼群算法,是又一类基于群集智能的有效寻优模式。(3)粒子群算法受人工生命研究结果的启迪，粒子群算法( PSO) 的基本概念来源于对鸟群和鱼群捕食行为的简化社会模型的模拟，1995 年由Kenndy 和Eberhart 13等人提出。由于PSO 算法在函数优化等领域具有广泛的应用前景，因此PSO 算法自提出以来，引起了国际上相关领域众多学者的关注。目前国内外研究现状大致可分为三个方向：算法的改进、算法的分析和算法的应用13。在PSO 算法中，每个优化问题的解都是搜索空间中的一只鸟(粒子)，解群相当于一个鸟群，鸟群从一地飞行到另一地相当于解群
13、的进化，“好消息”相当于解群每代中的最优解，食物源相当于全局最优解。PSO 算法中的每个粒子均视为解空间中的一个解。它根据自己的飞行经验与同伴的飞行经验来调整自己的飞行。每个粒子在飞行过程中所经过的最好位置,就是粒子本身找到的最优解，称为个体极值( Pbest)；整个群体所经历过的最好位置，就是整个群体目前所找到的最优解，称为全局极值( Gbest)。每个粒子都是通过上述两个极值不断来更新自己，从而产生新一代的群体。在实际操作中，由优化问题所决定的适应度值(fitness),来评价粒子的“好坏”程度。每个粒子还有一个速度决定它们飞行的方向和距离，然后粒子就追随当前的最优粒子在解空间中搜索。群体
14、智能算法经历了十多年的发展，逐渐凸现出其广泛的用途与强大的生命力。它本身所固有的并行性特征，正是目前基于网络的海量信息的分布式处理所需要的有效解决方法。它的开放性使得各种优化方法可以互相补充、优化算法的性能，使算法在处理不同问题的时候具有较强的适应能力与灵活性，这些优点正是群体智能优化算法研究不断取得进步与发展的原因。作为一类新型的进化算法，群体智能算法的主要特点是利用群体搜索策略和群体之间的信息交换。这类算法对目标函数的形态没有特殊要求，特别适合用于传统方法解决不了的大规模复杂结构优化问题。1.2.2 存在的问题群体智能算法产生的灵感来源于自然界中生物群体的生活现象，没有成熟、严格的数学理论
15、为指导，还有一些方面需要研究者去发展和完善13：算法模型本身，算法的收敛性分析与证明以及如何提高解空间的搜索效率等算法的基本原理方面缺乏严格的数学理论基础；参数对算法性能影响太大，其选择和设置没有普遍适用的方法，往往依靠经验得出，这使得参数的设置对实际的问题依赖性过强；优化算法的思想来源于自然界，是模拟生物习性得到的计算方法。由于要解决的问题千差万别，在求解实际问题的时候已陷入固有的模拟框架，使得一些问题在采用这些算法时表现得无能为力。因此，群体智能优化算法的发展，首先要从生物群体的基本生命自然机理进行深入研究，结合严谨的数学推理，使得算法具有坚实可靠的理论基础，建立算法的一整套理论体系，使得
16、算法在使用过程中有章可循。然后，突破传统的算法模型的束缚，设计出新的更加智能化的算法模型。此外，还要深入研究群体智能优化算法之间以及群体智能优化算法与其它智能优化方法之间的互相结合，探讨一种或几种算法融和的统一机制，提高算法的性能，加深算法的应用研究，扩大其适用范围。综上所述，本文以“人工蜂群算法分析与实现”为题，将群体智能方法中的蜂群算法应用到智力题的求解中，采用多个线程模拟多只蜜蜂，多个线程并行运行，同时对不同的可能答案进行检测模拟多只采蜜蜂采蜜，并通过考虑所选智力题的特征和结合一些操作系统相关知识(进程、线程、信号量、互斥锁等)来设计算法模型，以提高程序的运行速度。在本文的算法中，通过在
17、线程之间添加一些限制条件，使多个智能性不高的线程协作共同完成了一项大任务。由此，可考虑把各个线程实现的功能分别转移到不同角色的机器人，让它们同时去做一些事情。比如：通过生命体征寻找地震受难者、通过面部特征识别追查逃案犯、根据化学特性查寻某些有毒的化学泄露处、通过红外检测救火、根据垃圾的某些特性实现机器人打扫卫生、垃圾分类等。因此，对蜂群算法应用的研究具有重要意义。1.3 本文工作本文在分析和掌握原有算法的基础上，结合操作系统方面的相关知识，将其应用到智力题的求解中，达到能够更加快速求解的目的。具体包括：(1)阅读文献，理清人工蜂群优化算法的基本原理和数学模型；(2)回顾操作系统中关于进程、线程
18、、信号量、互斥锁方面的知识；(3)构造基于人工蜂群算法的智力题求解模型，画出处理过程的基本流程图；(4)在VC+6.0环境中，实现算法，进行性能测试和比较。2人工蜂群算法蜂群算法(Bee Colony Algorithm)是建立在蜜蜂自组织模型和群体智能基础上提出的一种非数值优化计算方法.SeelyError! Reference source not found.于1995年第一个提出了蜂群的自组织模拟模型。在模型中，尽管每个社会阶层中的蜜蜂只完成单一任务，但蜜蜂相互间通过摇摆舞、气味等多种信息方式，使得整个蜂群能协同完成诸如构建蜂巢、收获花粉等多项任务。D.KarabogaError! R
19、eference source not found.于2005年成功地把蜂群算法应用在函数的数值优化问题上，提出了比较系统且新颖的群体智能优化算法ABCA算法(Artificial Bee Colony Algorithm,简称ABCA)Error! Reference source not found.，算法主要模拟了蜂群的智能采蜜行为，蜜蜂根据各自分工进行各自的采蜜活动，并且通过蜜源信息的共享和交流，从而找到问题的最优解。Basturk等人Error! Reference source not found.于2006年又进一步将人工蜂群算法理论应用到解决限制性数值优化的问题上，并取得了较好
20、的测试效果。人工蜂群在寻优等方面具有收敛速度快、求解质量高、鲁棒性好、通用性强等优点，但也可能有早熟收敛和后期容易陷入局部极值等不足。2.1 ABCA的描述在人工蜂群系统中，每一个备选解称之为食物源(food source)，蜜蜂采蜜(寻找食物源)的过程即为搜寻最优解的过程。在算法中，食物源的价值由收益度(nectar amount)体现。蜜蜂的基本行为有：search(搜索食物源)、recruit(为食物源招募)和abandon(放弃食物源)。蜜蜂包含三种角色，即侦察蜂、引领蜂和采蜜蜂。采蜜蜂与正在采集的食物源相对应，食物源是采蜜蜂的引导目标。引领蜂与采蜜蜂分享信息，招募更多的采蜜蜂采集相应
21、的食物源。信息的分享程度与食物源的收益度相关。侦察蜂随机搜索蜂巢附近的新食物源，增强了算法跳出局部最优的能力。采蜜蜂由引领蜂处获得食物源的收益度信息。蜂群算法中的各种蜜蜂在舞蹈区交流信息，侦察蜂通过摇摆舞完成食物源信息的分享，引领蜂通过摇摆舞完成为食物源的招募工作。所有采蜜蜂都等候在舞蹈区，根据观察到的舞蹈选择相应的食物源采集。2.2 各种参数对算法结果的影响本小节重点分析摇摆舞算法和觅食算法中的参数，及其对ABCA的影响8。(1) 摇摆舞算法算例中的目标函数是最大完工期，令定义一个觅食蜂的收益率，计算公式为 (1)式(1)中，为觅食蜂对应调度的最大完工期。蜂群的平均收益率为 (2)式(2)中
22、，为时刻摇尾舞的次数；为跳摇尾舞的觅食蜂 对应调度的最大完工期。摇尾舞持续时间的计算公式为 (3)(2) 觅食算法觅食算法在蜂群中定义了一个觅食蜂群,这些觅食蜂迭代地构造出作业车间调度的解。觅食蜂在拓扑图中沿着节点之间的边行进，一次性地访遍图中从起点到终点所有的节点，由此得到的路径即代表了可行解。觅食蜂只能基于工序的优先权按照既定的可选节点清单选择下一节点，这样的移动准则表示为 (4)式(4)中，为路径从节点扩展至节点的概率；为节点和节点之间连边的等级数；为节点和节点之间的启发式距离。节点至节点之间有向边的等级数 (5)式(5)中，为偏好路径赋值，；为可选节点数；为偏好路径数，或0。由于首次觅
23、食的觅食蜂的值等于0，则所有可选节点的赋值相同。3人工蜂群算法的多线程并行实现技术在如今的信息社会，计算机需要处理的信息量越来越庞大，需要解决的问题越来越复杂，使得计算量暴增。通过提高单个处理器的计算速度和采用传统的“顺序(串行)”计算技术已难以胜任。因此，需要功能更加强大的计算机系统和高效计算技术来支撑，并行计算机和并行计算技术由此应运而生。加上第四代编程语言的出现，比如面向对象编程语言C+、JAVA等都提供了多线程技术，不仅可以使编程者在单处理机上模拟并行计算，还可以在多处理机上实现并行计算。3.1进程、线程与多线程进程、线程和多线程都是操作系统的概念。进程是程序在一个数据集合上运行的过程
24、，它是系统进行资源分配和调度的一个独立单位，是应用程序的执行实例。进程在运行过程中创建的资源随着进程的终止而被销毁，所使用的系统资源在进程终止时被释放或关闭,即具有动态性，从被创建到被撤销有一个生命周期；是程序的一次执行，即在指定内存中的一组指令序列的执行过程。每个进程由私有的虚拟地址空间、代码、数据和其它各种系统资源组成。一个进程至少包括一个线程(称为主线程)，并且每个进程都由主线程开始，在运行过程中可以建立新的执行线程。线程是程序执行的基本单位，通过线程可以实现程序执行的并发性、独立性和异步性。每个线程都有自己的一套设备(CPU、寄存器和堆栈)，操作系统给每个独立的线程安排一些CPU时间片
25、，通过操作系统的调度，实现不同线程的切换。因此，为了充分利用CPU，引入了多线程。多线程是指程序中包含多个执行流，即在一个程序中可以同时运行多个不同的线程来执行不同的任务，也就是说允许单个程序创建多个并行执行的线程来完成各自的任务。多线程是为了同步完成多项任务，不是为了提高运行效率，而是为了提高资源使用效率来提高系统的效率。线程是在同一时间需要完成多项任务的时候实现的。多线程技术的主要优势在于充分利用CPU的空闲时间片，用尽可能少的时间来对用户的要求作出响应，使系统整体运行效率得到一定的提高，增加了应用程序的灵活性。多线程提高了系统响应能力及平滑的后台处理。例如，一个字处理程序(进程)可以通过
26、使用多线程来加强操作并简化与用户的交互。该应用程序可以包含3 个线程，第1 个线程可以用于响应用户的键盘输入消息，将字符放入文档中；第2 个线程可以执行拼写检查及分页等后台操作；第3 个线程可以在后台将文档送到打印机打印。3.2互斥锁临界资源是指在系统中有很多资源是多个进程共享的资源中一次仅允许一个进程使用的那部分资源。互斥(间接相互制约关系)指多个进程都想使用一个临界资源，但是不能同时使用，于是只好一个进程用完了，才能给其他的进程用。 加锁法是对临界区加锁以实现互斥。当某个进程进入临界区后，就锁定临界区直到它退出临界区，其他进程要进入时，需要不断测试临界区是否被用着，直到临界区空着时才能进入
27、。在编程中，引入了对象互斥锁的概念，来保证共享数据操作的完整性。每个对象都对应于一个可称为“互斥锁”的标记，这个标记用来保证在任一时刻，只能有一个线程访问该对象。通常，互斥锁通过确保一次只有一个线程执行代码的临界段来同步多个线程。3.3信号量信号量S为可用临界资源数量，取值只允许为“0”和“1”的信号量称为二元信号量，主要用作互斥变量(mutex)；取值允许为整数的信号量称为一般信号量(semaphore)，主要用于进程间的同步问题。操作：最初是由芬兰学者Dijkstra 于1965年提出的两个原子操作概念，信号量除初始化外仅能通过这两个标准的原子操作和来访问。原子操作在执行时是不可中断的，即
28、当一个进程在修改某信号量时，没有其他进程可同时对该信号量进行修改，以解决进程间同步和互斥的问题。 操作：对某资源信号量作操作，表示申请资源，可用资源数；如果，表示无资源可用，本进程挂起，变成等待资源的“等待”状态。操作：对某资源信号量作操作，表示释放资源，可用资源数；如果，表示有进程在等待该资源，则释放该进程，即将等待该资源的首进程的状态变为“就绪”状态，去等待CPU继续运行。根据对互斥信号量mutex的不同设置方式，基于信号量的生产者-消费者问题算法7有两种，(1) 生产者、消费者共同使用一个互斥信号量mutex，即生产者进程间、消费者进程间和生产者、消费者进程均互斥，同一时刻只能有一个进程
29、访问缓冲区；(2)为生产者、消费者分别设置各自的互斥信号量，即生产者进程间使用producerMutex进行互斥，消费者进程间使用consumerMutex进行互斥，而生产者进程与消费者进程间不互斥。一旦有可用的资源，两类进程就可以同时访问缓冲区，同一时刻最多允许两个进程访问缓冲区，由于本文的算法中，借鉴的是第二种算法的思想，所以此处只演示算法(2)的流程图。图5 生产者-消费者分别设置互斥量的流程图由于算法2中同一时刻最多允许两个进程访问缓冲区，所以需要有两个指针ptop 、pbottom 来分别指向生产者、消费者的下一个写入、读取位置。4基于人工蜂群算法的智力题求解本文以“人工蜂群算法分析
30、与实现”为题，在分析蜂群基本算法的基础上，将其在智力题的求解中实现。本文算法中采用多个线程并行技术模拟多只蜜蜂在同一时刻各司其职，完成各自的任务。通过考虑所选智力题的特征和结合操作系统方面的相关知识(诸如进程、线程、多线程、信号量、互斥锁等)提出数学模型，并在线程与线程之间添加一些限制条件来更好地模拟蜂群，从而使多个智能性不高的线程也能像蜂群中不是很聪明的个体一样，通过一定的信息交流、协作共同完成智力题的求解。4.1智力题求解问题概述1、第一个答案是b的问题是哪一个？ (a)2; (b) 3; (c)4; (d)5; (e)6 2、唯一的连续两个具有相同答案的问题是？ (a)2，3; (b)3
31、，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)以上都不是 7、按照字母顺序，本问题的答案和下一个问题的答案相差几个字母？ (a)4; (b)3; (c)2; (d)1; (e)0(注:a和b相差一
32、个字母) 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本题目共10题，每道题的答案之间联系紧密，有着严密的逻辑推理关系。从排列组合的角度来看，每个题有5种可能的答案，则10个题的解空间为9765625()种可能解。每一个可能解需要用上述的10个题来检测，只有同时符合10个条件的才是正确解。因此，从某种意义上来说，本
33、题属于组合优化问题。参考近10年来一些学者对群体性生物行为的研究结果提出的组合优化问题的求解算法和理论，例如蚁群算法、蜂群算法等，结合本文所选智力题的特殊性(对可能解的判断需经过多次)和共性(都是组合优化问题)，本文将利用群体智能中蜂群算法的思想来解决智力题求解问题，设计一个新的动态检测算法，并对其性能进行分析。4.2现有的方法4.2.1穷举法穷举法(Exhaustive Attack method)，又称为强力法 (Brute-force method)，完全试凑法(complete trial-and error method)。顾名思义，完全试凑法是用时间上的牺牲来换解的全面性保证，特别
34、是随着计算机运算速度的飞速发展，穷举法给人们的印象已经不再是最低等和最原始的无奈之举，而是一种针对于类似密码的破译方法。这种方法和数学上的“完全归纳法”很像，并在密码破译和求解一些组合优化问题方面得到了广泛的应用。简单地来说，就是把组合优化问题中的可能解进行逐个推算，直到找到真正的解为止。在本文所选的智力题求解中，可能解有9765625()种组合，也就是说我们最多会尝试9765625次就能找到真正的解。根据这种思路我们可以使用计算机来进行逐个推算，把每个问题视为判断可能解对错的一个条件，只要检测出不符合其中的一个条件，就将其丢弃，继续下一个。4.2.2单线程的智力求解算法本文中提到的单线程的智
35、力题求解算法是在穷举法基础上的一个优化算法。在该算法中，与穷举法类似，把智力题的每一个问题看作是一个判断条件，依次进行判断。不同的是，此处调整了判断条件(即问题)的顺序，淘汰率越高的判断条件越在前面先检测，越低的就放在越后面来检测(注：淘汰率的高低可通过对问题的分析计算得出，也可通过实验测出)。通过这样的调整，在很大程度上有效减少了对可能解的检测次数，从而明显缩短程序的运行时间。4.3 基于人工蜂群算法的智力题求解设计与实现4.3.1算法的描述 如前2.1中对蜂群算法的描述和4.1中对智力题的分析中所述，可知智力题的求解过程与蜜蜂的采蜜行为有许多相似之处：(1)由蜂群中的多只蜜蜂联想到智力题求
36、解中调用的多个线程；(2)由侦察蜂随机寻找食物源，联想到智力题随机生成解空间；(3)由侦察蜂通过摇摆舞与引领蜂共享食物源信息，联想到智力题求解中通过一个存储空间实现线程之间的信息共享；(4)由引领蜂根据侦察蜂的搜寻结果，寻找搜寻结果中高收益度食物源，联想到在智力题的求解中，先从解空间中通过淘汰率最高的条件判断，淘汰一部分明显错误的解，减少程序误运行的次数；(5)由引领蜂通过摇摆舞为食物源招募采蜜蜂，联想到在智力题的求解中，通过索引表来向其他线程传达信息；(6)由采蜜蜂采集花蜜的过程联想到智力题求解中依条件判断可能解的过程。有花蜜，采集；可能解符合所有条件，将其打印出。采集完毕，丢弃食物源；检测
37、完毕，释放相应的存储空间。综上所述，蜜蜂与环境之间的信息交流模型可以被用于智力题的求解中，以实现动态的、自适应的求解过程。 在本文算法中，将人工蜂群算法应用到智力题求解中的具体设计思路：(1)遍历函数模拟侦查蜂，通过遍历法动态生成解空间(舞蹈区)data_been，由于随机生成和顺序生成的结果相同，所以为简单起见，使用顺序生成；(2)创建线程模拟引领蜂，引领蜂从舞蹈区(data_been)获取食物源信息，通过问题2，淘汰收益度较低的解(一部分明显错误的可能解)，通过计算可知，不被淘汰的概率，即食物源的收益度为40.96% ();(3)创建线程模拟采蜜蜂，采蜜蜂从舞蹈区(index)获取引领蜂的
38、招募信息，以及相应的食物源信息，进行采蜜；另外，在算法中，为了防止线程之间出现死锁，引入了操作系统中关于信号量机制方面的一些知识，充分利用CPU，实现了人工蜂群算法的多线程并行运行。为了便于理解，可参考下面的模拟图：图6 智力题求解模拟蜂群图4.3.2算法的步骤基于蜂群算法的求解智力题的步骤可描述如下：step 1 运用遍历法，模拟侦查蜂寻找食物源，并将食物源信息动态保存到data_been中；step 2 data_been若不空，引领蜂从解空间中获取食物源信息，并对相应食物源判断其收益度，通过问题2淘汰收益率低的解，并将高收益度解信息保存到index；否则，执行step5；step 3 i
39、ndex若不空，采蜜蜂根据索引值寻找相应的食物源；否则，执行step2；step 4 采蜜蜂采集食物源，若是最优解，将其打印出；否则执行step3；step 5 程序结束。图7 流程图4.3.3仿真实现与性能分析本算法使用的是C语言，编译器为VC+6.0，在Windows XP环境下进行仿真。动态生成的解空间中的可能解代表当前执行摇摆舞的侦察蜂分享给引领蜂的信息，索引表中的解列表代表当前引领蜂执行摇摆舞分享给采蜜蜂的信息。为了评估所提出的使用蜂群模型的算法性能，将其与未使用蜂群算法的单线程算法进行比较。由运行结果可看出，使用蜂群算法，明显缩短了程序运行时间。C语言提供了多线程技术的强大支持。线
40、程作为进程内部的一个执行单元，系统创建好进程后，实际上就是启动了该进程的主执行线程，主执行线程以函数地址形式，比如说main或WinMain函数，将程序的启动点提供给Windows系统，主执行线程终止了，进程就随之终止。(1)单线程的求解算法：图8单线程求解算法的运行结果(0对应A；1对应B；2对应C；3对应D；4对应E)在该运行结果中：第一行：程序运行的起始时间(以毫秒为单位)；第二行：打印出的符合条件的可能解，即运行结果；第三行：结束时间(以毫秒为单位)；第四行：运行的时间(已换算为秒)；第五行：程序运行结束。(2)基于人工蜂群算法的而提出的多线程算法：图9 基于人工蜂群算法的多线程求解算
41、法的结果(0对应A；1对应B；2对应C；3对应D；4对应E)在运行结果中，第一行：程序运行的起始时间是0ms；第二行：侦察蜂完成可能解空间的初始化，9765625是可能解的个数；第三行：引领蜂线程创建完毕，引领蜂开始工作；第四行：采蜜蜂线程0号创建，采蜜蜂0号开始工作；第五行：所有线程创建完毕，开始工作；第六行：采蜜蜂线程2号创建，采蜜蜂2号开始工作；第七行：采蜜蜂线程1号创建，采蜜蜂1号开始工作；第八行：采蜜蜂线程3号创建，采蜜蜂3号开始工作；(注：此处由于线程是随机的，抢占到显示器的顺序不定，所以并不是按顺序打印出的。)第九行：0号采蜜蜂采集到了最优解；第十行：引领蜂线程结束；第十一行：结
42、束时间(以毫秒为单位)；第十二行：整个程序运行的时间(单位已转换为秒)；第十三行：程序彻底运行结束。在此算法中，并非简单的用宏观控制的多线程来减少时间，而是让线程之间用少量信息交流来自主实现整体运算的计算最优化。由实验结果可看出，基于人工蜂群算法的求解方法的运行时间明显高出单线程求解算法十余倍。5 结束语人工蜂群算法作为一种新的群集智能优化算法，优点是显著的，在本文的算法中主要表现在：(1)适应范围宽，能够适用于多种类型的组合优化问题；(2)易于实现并行性；(3)分工明确，各司其职，相互协作，共同完成一项大的任务。(4) 处理不同问题的时候具有较强的适应能力与灵活性。由实验结果可看出，使用蜂群
43、算法明显缩短了程序的整体运行时间。由此，在未来的研究中，可考虑将其应用到机器人群体中，比如根据人的生命体征寻找地震中的幸存者、根据面部特征清除恐怖分子或追查在逃案犯、根据化学特性查找化学物渗漏处以及垃圾分类等领域。不足之处也是因为本文所选实例的自身限制：没有实现侦察蜂与采蜜蜂之间的角色转换，但这并没有影响到算法效率。Analysis and Implementation of Artificial Bee Colony AlgorithmLI Linfei(College of Computer Science, Shaanxi Normal University, Xian 710062)A
44、bstract：On the basis of understanding the principles of bees collecting nectar and bee colony optimization algorithm, we analyze the basic artificial bee colony algorithm. Combining with the knowledge of operating system, we convert the process of solving puzzle into the process of honey bees findin
45、g the optimal nectar source. In order to solve the puzzle, we use threads to simulate bees of different roles, we imitate artificial bee colony algorithm (ABCA) to complete each bees duty in parallel. In VC + +6.0 environments, the simulation experiment shows the algorithm is stronger in the global
46、search ability and operation efficiency is ten times higher than the one of single thread.Key words: artificial bee colony algorithm; swarm intelligence; combinatorial optimization参考文献1 方陵生. 蜂群理论与群体智慧J. 世界科学,2007,(11): 37-39.2 张统华，鹿晓阳. 群体智能优化算法的研究进展与展望J.山西建筑, 2007,33(1):14-16.3 胡中华,赵敏,撒鹏飞. 基于人工蜂群算法的
47、JSP的仿真与研究J. 机械科学与技术,2009,28(7): 851-856.4 罗钧,樊鹏程. 基于遗传交叉因子的改进蜂群优化算法J. 计算机应用研究,2009,26(10): 3716-3717+3753.5 康飞,李俊杰,许青. 混合蜂群算法及其在混凝土坝动力材料参数反演中的应用J. 水利学报,2009,40(6): 736-742.6 丁海军,李峰磊. 蜂群算法在TSP问题上的应用及参数改进J. 中国科技信息,2008,(3): 241-243.7 刘晓平,石慧,凌实,杜琳,田卫东. 基于信号量的生产者2消费者问题设计与分析(社会科学版),2008,22(5):84-88.8 吴晶晶. 基于蜂群算法的作业车间调度优化J. 郑州轻工业学院学报(自然科学版),2007,22(6): 51-53.9 Gonzales R C, Woods R E. Digital Image Processing M. Beijing: Publishing House of Electronics Industry, 2002: 460507.
