拟态物理学启发的群智能方法(txt+pdf+epub+mobi电子书下载)


发布时间:2020-05-12 03:13:13

点击下载

作者:谢丽萍

出版社:电子工业出版社

格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT

拟态物理学启发的群智能方法

拟态物理学启发的群智能方法试读:

前言

大自然是智慧的。蚁群觅食、大雁迁徙、鹿群逃避、蜂群筑巢等,这些群集智能行为通过个体间的简单交互和协作而涌现,是一个复杂动态的自组织、自学习和自适应过程。整个群体没有控制中心,具有稳健性;群体中相互协作的个体是分布的;每个个体的能力有限,具有简单性;个体之间可以通过直接或间接通信进行协作,具有良好的可扩充性;个体具有自学习能力,能自动获取知识;个体依据外部环境的变化进行自组织,从而实现个体的自适应,使得系统能适应外界的变化保持良好的性能。

大自然又是富有规律的。固体的结晶、液体流动时的自觉避障、气体分子的扩散、太阳系各天体有规律的运动等,这些整体行为都遵循一定的物理规律,如万有引力定律、库仑定律、分子间的作用规律等。这些物理规律用来阐释物理系统中的任意两个运动个体(如天体、电荷和分子等)之间存在某种作用力(如引力或斥力),所有个体在其他个体的作用力驱动下运动,从而呈现有规律的物理现象。

自然界的万事万物是相互联系的。生物群体表现出的自组织、自学习和自适应的智能特性恰恰是自然物理系统所呈现的基本规则。因而,群体智能中的很多问题都可以从自然物理规律中获得解答。因此,从物理学角度思考和阐释生物群集智能的涌现将为研究群体智能提供一种全新的思路。

本书从拟态物理学这一独特视角研究群智能方法,全面详述了作者近年来在群体智能领域的研究成果,是一本总结研究成果的学术专著。本书力图系统地从拟态物理学的角度构建群体行为模型、群体智能算法和群机器人模型,以丰富群体智能方法的研究,为从事相关群体智能和优化方法的科研工作者提供参考。

全书内容分为七章。

第1章:绪论,简要介绍了群体智能的主要研究分支,以及拟态物理学方法研究概况;就群体智能相关研究的局限性,提出从拟态物理学的视角开展群体智能方法研究。

第2章:从群体行为模型入手,借鉴拟态物理学的思想和概念,详细介绍了生物群体的群集模型和群集觅食模型的构建方法,以及这两种模型的内聚性与稳定性。

第3章:鉴于生物群体觅食与优化问题求解的相似性,详细论述了基于拟态物理学方法构造优化算法的可行性,分别介绍了拟态物理学优化算法的概念、基本框架、作用力规则、质量函数及速度上限V的选择策略。max

第4章:采用线性系统的稳定性理论和概率论的相关知识论证了拟态物理学优化算法的收敛性和全局收敛性,并对影响拟态物理学优化算法收敛的重要参数G给出了定常和自适应两种选择策略。

第5章:分别从借鉴群居性生物具有记忆能力、有效利用个体的搜索方向、引入种群多样性,以及引入PD控制器等方面探讨了拟态物理学优化算法的几种改进模型。

第6章:将拟态物理学优化算法用于求解约束优化问题,分别介绍了基于约束保持法和基于可行性规则法两种约束处理方法的拟态物理学优化算法。

第7章:详细阐述了将拟态物理学优化算法作为群机器人建模工具,构建全局感知和局部感知的群机器人目标搜索模型。

本书的完成得到了太原科技大学复杂系统与计算智能实验室、工业与系统工程研究所,以及计算机科学与技术学院各位同仁的大力支持,太原科技大学曾建潮教授对本书提出了很多宝贵的建议,在书稿出版过程中,电子工业出版社的徐蔷薇和赵娜编辑提供了多方面的帮助,在此一并致以诚挚的谢意。

本书研究工作得到了国家青年科学基金项目(项目编号:61403271)、国家自然科学基金项目(项目编号:61472269)、山西省青年科学基金项目(项目编号:2011021014-1)和太原科技大学博士后基金项目(项目编号:20142022)的资助,在此谨向有关部门表示深深的感谢并致以敬意。

由于作者水平有限,书中难免有不妥之处,恳请各位专家和广大读者给予批评指正。第1章 绪论1.1 问题的提出

现实世界问题不断增长的复杂性一直推动着计算机科学家寻找解决问题的有效方法。自然界是无尽灵感的来源。进化算法和基于群体智能的元启发式算法均是求解复杂优化问题的成功范例。进化计算模拟了生物进化过程与机制,以遗传算法为典型代表,其核心思想源于达尔文的优胜劣汰的自然选择学说和孟德尔的遗传变异理论,模拟了生物个体通过繁殖、选择、竞争和变异实现进化,其进化过程是一个适应环境的稳健的优化过程。群体智能算法以蚁群算法、微粒群算法为典型代表,模拟了简单生物个体通过信息交互和相互协作涌现复杂群体智能行为的特性,其过程也是一个适应环境的稳健的优化过程。两者的本质区别在于:前者强调“优胜劣汰”的自然选择,仅考虑到个体之间的竞争,适应值较差的个体会被适应值较好的个体取代而淘汰;而后者强调个体的“学习”与个体间的相互“协作”,个体通过感知和信息交互来协同完成任务。相比之下,个体通过遗传进化对智能的形成和推动远不及通过学习和协作所涌现的智能来得快。显然,群体智能计算在解决复杂优化问题方面具有突出的优势。

群体智能(Swarm Intelligence)起源于对自然界群居性生物自组织行为的观察和研究。群居性生物令人惊奇之处在于:尽管单个个体行为简单、能力有限,却能与邻近同伴交互协作涌现出诸如觅食、筑巢、迁徙、御敌等复杂集体行为,使整个群体呈现一种协调、有序的自组织状态。群体智能正是建立在对这些大量简单生物涌现的群体行为的认知基础之上,是一群简单自治智能体涌现出的集体智能。它能够在没有集中控制且对全局环境不了解的情况下完成很多复杂任务,这为寻找复杂的分布式问题求解方案提供了很好的启发。群体智能经过短短十几年的发展已引起了多个学科领域研究人员的关注,目前已经成为人工智能、经济、社会、生物等交叉学科的热点和前沿领域。群体智能以其简单性、灵活性、分布性和健壮性的特点,在组合优化、通信网络、知识发现、机器人等研究领域展现出优异的性能和巨大的发展潜力。

自1999年,Bonabeau等人将群体智能的定义扩展为任何启发于群居性昆虫群体和其他动物群体的集体行为而设计的算法和分布式问[1]题解决装置以来,学术界分别从生物学、数学、机器人学及计算机科学等角度,对群体智能的三个重要方面[群体行为模型、群体智能算法和分布式装置(或群机器人)]开展了许多研究工作。群体行为模型的研究,包括对生物群体行为的建模与仿真,典型的建模方法有欧拉法、拉格朗日法和基于仿真的方法;群智能算法研究包括微粒群算法、蚁群算法和蜜蜂算法等;分布式装置的研究,是有关工程领域自动或半自动智能群体的协调合作行为的动态性能和控制问题的研究,即利用群体智能特有的分布式特点,结合机器人等先进设备,设计和研究带有一定自组织能力的装置系统,其研究方法分别有启发于生物系统、物理系统和社会系统的方法。群体智能这三方面的研究不是孤立进行的,它们相互影响、相互促进。群体行为模型的研究是构建群体智能理论的基础和关键,也是群智能计算和分布式装置研究的动力和源泉,许多工程系统的开发都将会从包括生物群体行为的建模、生物个体之间协作规则的制定和生物群体动态特性的分析等理论的研究中获益。群体智能算法的研究和应用是整个群体智能理论研究的核心,可以作为群体行为建模和分布式装置协调控制的工具。而分布式装置研究则可为生物群体行为的涌现机制产生新的理解和认识。由此可见,群体行为模型的研究,无疑对群体智能的理论构建和实际应用都具有重要意义。

然而,由于认知水平所限,人类对群体智能的本质还缺乏深刻的认识,至今仍未完全弄清群体智能行为涌现的内在机制。群居性生物个体之间究竟遵循怎样的交互和协作规律,以涌现群体智能行为?这一核心问题的探索为群体智能研究提供了广阔的发展空间。

在生物系统中,群集智能行为通过个体间的简单交互和协作而涌现,是一个复杂动态的自组织、自学习和自适应过程。整个群体没有控制中心,具有稳健性;群体中相互协作的个体是分布的;每个个体的能力有限,具有简单性;个体之间可以通过直接或间接通信进行协作,具有良好的可扩充性;个体具有自学习能力,能自动获取知识;个体依据外部环境的变化进行自组织,从而实现个体的自适应,使得系统能适应外界的变化保持良好的性能。生物系统这种自组织、自学习和自适应的智能特性恰恰是自然物理系统所呈现的基本规则。因而,群体智能中的很多问题都可以从自然物理规律中获得解答。因此,从物理学角度思考和阐释生物群集智能的涌现将为研究群体智能提供了一种全新的思路。

自然界很多富有规律的整体行为,如固体的结晶、液体流动时的自觉避障、气体分子的扩散、太阳系各天体有规律的运动等,这些整体行为都遵循一定的物理规律,如万有引力定律、库仑定律、分子间的作用规律等。这些物理规律用来阐释物理系统中的任意两个运动个体(如天体、电荷和分子等)之间存在某种作用力(如引力或斥力),这一作用力与个体的质量,以及与其他个体的距离等信息有关,所有个体在其他个体对其作用力的驱动下运动,从而呈现有规律的物理现象。

物理学原理和规律通过研究任意两个运动个体之间的物理作用力揭示了自然界所呈现的有规律的物理现象。那么,群居性生物个体之间是否也存在一种“虚拟”物理作用力,并在这种“虚拟”物理作用力的作用下,涌现出其特有的群体行为呢?也就是说,群居性生物所涌现的群体智能行为可否用物理学原理和规律加以阐释和建模是非常值得研究的问题。

本书从拟态物理学的角度思考和阐释生物群集智能的涌现,为研究群体智能提供一种全新的思路。拟态物理学(Physicomimetics or [2]Artificial Physics,AP)是美国怀俄明州立大学的Spear WM等人提出的一种模拟物体间存在虚拟力作用,以及物体运动遵循牛顿力学定律的方法。拟态物理学框架实现了从群机器人系统到物理系统的映射,机器人被抽象为在二维或三维空间运动的微粒。每个微粒都有质量、速度和位置属性。微粒在空间中的连续运动用多个极小离散时间片断内的位移量近似描述。拟态物理学将传统的物理分析技术用于群体行为的预测,期望其表现类似于固态、液态或气态物质的特性。该方法通过制定个体间的简单虚拟作用力规则涌现群体的复杂行为,实现整个系统分布式复杂控制,为分布式群机器人系统控制提供了一条有效途径。目前,该方法主要应用于群机器人的编队、覆盖和避障等问题的研究。

从行为上看,生物群集行为和群机器人行为具有许多相同之处。两者都是由简单个体组成的群体,单个个体无智能特性,个体行为受群体内部其他个体的影响,个体之间通过某种交互机制相互协作,整体表现出智能特性,所有个体共同完成某项单个个体难以完成的任务。本书采用拟态物理学方法对生物群体的群集行为进行建模与仿真研究,从拟态物理学的视角阐释群居性生物个体之间的交互和协作机制,启发和构造了一种基于拟态物理学的优化算法,为求解复杂优化问题开辟了新的途径。1.2 群体智能[3]“群体智能”一词最早出现在有关元胞机器人控制一文中,用于描述众多简单机器人像机体细胞那样通过与相邻个体交互产生自组织。群居性生物群体普遍存在于自然界中,如鸟群、鱼群、蚂蚁、蜜蜂等,这些群体中没有领导者协调众多个体的行为,也没有整体部署,尽管单个个体行为能力有限,却能与邻近同伴交互协作完成诸如觅食、筑巢、迁徙、御敌等复杂集体智能行为,使整个群体呈现一种协调、有序的自组织状态。这种自组织本质上是全局形式的,却完全是由局部信息交互产生的。个体通过交互能够使个体获得的信息远比通过自身感官所取得的多。个体根据获得的环境和邻近同伴的信息改变自身的行为模式以适应环境,使得整个群体涌现出单个个体所不具备的能力和特性。

群体智能的思想就是建立在对这些大量简单生物个体涌现的群体行为认知基础上,可被定义为一群简单自治智能体(Agent)涌现出[4]的集体智能。这些自治智能体与其所处环境构成了一个完整的系统,整个系统中没有领导者,也没有集中控制机制,每个智能体可被看做一个子系统,其行为与其他成员相对独立,仅有有限的能力和行为,可以从环境中获取信息,通过与环境和其他成员交互,并协作涌现自组织。此类系统中的个体具有相同的控制结构,可以互相替换,而且个体单元的增减不需要系统外部重新组织,大大增强了系统的灵活性[5]和稳健性。

Mark Millonas针对如何采用计算机构建具有合作行为的群集人工生命系统,提出了群体智能应该遵循如下5条基本原则。(1)邻近原则(Proximity Principle):群体应该能够进行简单的空间和时间计算。(2)质量原则(Quality Principle):群体应该能够对环境中的质量因素的变化做出响应。(3)多样性反应原则(Principle of Diverse Response):群体不应将获取资源的的途径限制在狭窄的范围内。(4)适应性原则(Adaptability Principle):环境发生变化时,若群体有值得付出代价的改变机会,则群体应该改变其行为模式。(5)稳定性原则(Stability Principle):群体不应在每次环境变化时都改变自身的行为模式。稳定性是群的一个基本属性,它刻画了群中个体在移动过程中的内聚特性。国内外研究不同群集行为稳定性的学者有Beni G、Gazi、王龙和陈世明等人。

显而易见,群体智能模拟了简单生物群体所表现的智能涌现行为,通过简单个体间的交互和协作凸显复杂群体智能行为的特性。群体智能具有如下几个特点:(1)控制是分布式的,不存在中心控制,因而它更能够适应当前网络环境下的工作状态,并且具有较强的稳健性,即不会由于某一个或几个个体出现故障而影响群体对整个问题的求解。(2)群体中的每个个体都能够改变环境,这是个体之间间接通信的一种方式,这种方式被称为“Stigmergy”。由于群体智能可以通过非直接通信的方式进行信息的传输与合作,因而随着个体数目的增加,通信开销的增幅较小,因此,它具有较好的可扩充性。(3)群体中每个个体的能力或遵循的行为规则非常简单,因而,群体智能的实现比较方便,具有简单性的特点。(4)群体表现出来的复杂行为是通过简单个体的交互过程凸显出来的智能,因此,群体具有自组织性。

群体智能强调个体行为的简单性、群体的涌现特性及自下而上的研究策略。群体智能利用群体的优势,在没有集中控制并且不提供全局模型的前提下,为寻找复杂问题的解决方案提供了新思路。群体智能是当前人工智能,以及经济、社会、物理、生物等交叉学科的研究热点和前沿领域,已逐渐形成了群体行为模型、群体智能算法和群机器人技术研究三大分支。1.2.1 群体行为模型

在对自然界特殊规律的认识过程中,人们发现自然界中的许多简单生物个体往往聚集在一起形成群体,这些群体在寻找食物和躲避天敌等过程中会涌现出智能行为。从而使得整个群体在自然界的竞争中获得相较于单个个体更高的生存机会。这种由简单个体通过局部交互而使得整体涌现出不可预见的全局智能行为被称作群集行为。

群集行为广泛存在于从细菌到哺乳动物等众多生物种群当中,是生物群体活动的一个重要现象。生物学家经过长期的观察和研究认为,生物的群集行为有两种不同的产生机制。一种是个体直接面向局部吸引源(如食物的集中区域或其他个体释放的信息素等)而产生的个体行为,如细菌及昆虫等的群集行为。另一种是个体直接面向群体中的其他个体行为而产生各自行为,多见于一些高级生物种群,如鱼类、鸟类等生物的群集行为。通过个体之间的合作和协调,群体生物在逃避天敌和寻找食物等诸多方面都显示出巨大的优势。

目前,对生物群体动态行为的研究是复杂性科学研究的一个焦点。对生物系统中的群集及其动态行为进行数学建模与分析,对理论研究和实际应用都具有重要意义。许多工程群体系统的开发都将会从包括生物群体行为的建模、生物个体之间协作规则的制定和生物群体动态特性的分析等理论的研究中获益。基于此,许多学者建立模型对生物的群集行为进行了深入的分析和研究。

目前研究群集行为的主要建模方法有3种:仿真建模方法、欧拉[6]法和拉格朗日法。

1.仿真建模法

在基于仿真的建模方法中,模型无须建立具体的群体密度分布或个体运动方程,而是通过为群体中的个体制定模拟生物个体动态行为规则来研究群集行为。

较为典型的仿真建模如Morale为群体内部每个个体制定3条简单的行为规则:①聚集规则(个体向其视线范围内较远的个体聚集);②排斥规则(个体远离其视线范围内距其过近的个体);③扩散规则(为个体设计一个随机运动的行为系数,使得个体视线范围内其他个[7]体数量较多时该随机行为发生的概率较小,反之亦然)。经过仿真实验表明,在这3种行为规则的控制下,群体涌现出集结行为。

目前,为了能够方便、准确地对群体行为进行研究,许多研究机构和团体设计了专门针对群体系统的软件仿真平台。其中较为著名的[8][9]是Swarm系统和StarLogo系统。Swarm系统是针对建立复杂自适应系统而设计的软件平台,其建模思想是让一系列独立个体通过独立事件进行交互。用以研究由多个个体组成的群体系统的各种动态行为。StarLogo系统采用基于主体的建模思想,可以同时对上千个主体的行为进行控制,并为每一个主体制定不同的行为模式。其最大的优点是可以将仿真的结果用图形化的方式直观地表现出来。

2.欧拉法

在欧拉法中,群集模型是使用通量(某一区域的个体密度)来描述的连续集模型。模型不以单个实体为研究对象,而是通过密度概念将整个群体作为一个连续集,用欧拉方程描述群体的密度分布。方程中可以添加来自环境等的吸引或排斥作用项。

欧拉法的理论基础为费克提出的经典扩散理论:假设二维空间中单位时间单位面积内在x方向上粒子的迁移量为J,粒子浓度为ρ,扩x撒率为D,由费克定律,粒子的扩散方程为。随后Okubo A在文献[10]中分析了在一维空间中由M个粒子组成的群体做随机扩散运动的情况,得出粒子随机运动的扩散方程。通过对扩散方程进行泰勒级数展开和求极限,Okubo A获得了由粒子随机运动形成的群体分布的概率密度函数,证明了它与基于费克定律的粒子扩散方程具有一致性。

Skellam J.G.在建立生物群集模型时不仅考虑个体的随机运动因素,同时还考虑了群集个体之间或个体对环境的反应。一维情况下,群体通过垂直于x轴的通量需包含两部分:随机扩散项和非随机对流项。设u为群体的平移,扩散项和对流项分别表示为和up。模型方程为。Mogilner和Edelstein-Keshet在此基础上增加了群集个体之间的相互作[7]用项:u´p=up+AK·p-RpK·p。其中,,arj=a,r;up描述群体受环境作用产生的漂移量;K(x)、K(x)分别表ar示群体中距离为x的个体相互之间的吸引力和排斥力作用。其他一些基于欧拉法的群集研究大都是基于以上模型的基础上进行一些扩充性的研究。

欧拉法建立群集模型无须对群体所处环境进行空间离散化处理,使用偏微分方程(欧拉方程)描述群体的密度分布。由于偏微分方程理论相对完善,从而使得对由偏微分方程构建的群集模型的理论分析相对容易。欧拉建模法对于描述大规模密集而没有明显不连续分布的群集行为非常有效。但它忽略了个体的特性,对于很多由有限数量的大体积或强调个体智能特性的个体组成的群体而言,欧拉法建立的连续集模型不太适用,如鸟群、鱼群等的群集行为。也正因为如此,基于个体控制的拉格朗日法越来越受到人们的关注。

3.拉格朗日法

拉格朗日法以群体内部单个个体为研究对象,使用基于个体决策的方法作为控制群体运动和集结的规则,以拉格朗日方程描述每个个体的受力和运动方程。拉格朗日法相较于前两种建模方法而言,能够更加准确地描述个体的智能特性,其使用范围也更为广泛。因此,本书也采用拉格朗日法对群集行为进行研究。

基于拉格朗日方法建立的群集模型一般可以理解为:群集行为的产生是群体内部个体之间交互作用的结果,这种交互作用一般包括使个体聚集的吸引力作用和使个体之间避免碰撞的排斥力作用。通过这种交互作用,个体在避免由于相互之间过度接近而导致碰撞的同时集结在某一较小的区域。

Breder首先提出了一种由简单的吸引力/排斥力函数组成的群集

[11]模型。受电磁学库仑定律的启发,Breder选择了一个保持为常量的吸引力作用项,选择了一个与两个相互作用的个体间距离的平方成反比的排斥力作用项来描述个体的运动。通过与鱼群的集结实验比较,他得出了恰当的模型参数。Warburton等人在此基础上研究了一系列[12]吸引力对群集行为的影响。通过仿真实验和理论分析,Warburton指出一组由凸函数形式组成的吸引力/排斥力函数可使模型具有较好的集结效果。同时得到结论:个体之间存在一个使吸引力与排斥力相互抵消的平衡距离,且群体的规模越大,平衡距离越小。

Gazi等人将群集模型的研究推广到n维连续空间中,建立了一类[13]以连续时间形式描述的群集模型。假设群体系统由n维欧式空间中的N个个体组成,所有个体同步运动,并且每个个体能够检测到所有其他个体的位置信息,每个个体的运动方程为ij

其中,f为引斥力函数,决定了个体之间的交互作用,x、x分别表示个体i、j所处空间的位置向量。由式(1.1)可以看出,每个个体在单位时间的运动方向和运动幅度是由此时所有其他个体施加在该个体上的吸引力和排斥力共同作用的结果。Gazi构造的吸引力/排斥力函数为

其中,a,b,c为常数;2-范数。由函数(1.2)可以看出,群体内部个体之间的引斥力作用取决于个体之间的距离,当个体之间距离较大时,表现为吸引力;距离较小时,表现为排斥力,并且存在一个平衡距离使得f(y)=0。也就是说,个体之间的作用力与个体所处的位置有关。要使式(1.2)所描述的引斥力有意义,参数a,b需满足b>a,否则,对于群体中的任意两个个体来说,不管它们如何靠近都不会产生排斥力作用。

另外,Gazi在文献[14]中对模型作了进一步研究。他在式(1.1)的基础上增加了环境作用项,用来描述个体趋向目标的行为。此时个体的运动方程包括群体中其他个体对其作用与个体所处环境对其的作用两项:

其中,σ可以看做环境势能场函数,可以是环境中吸引源或排斥源产生的势场,表示势函数的负梯度。假设个体趋向于向势能较小的位置运动,可以定义σ(y)<0的位置表示环境中的吸引源,σ(y)=0表示势场为零的平衡位置,σ(y)>0的位置为环境中的排斥源。

王龙及其合作者研究了个体之间的引斥力作用为各项异性的群集[15]模型,其特点是不同个体之间的相互作用由不同的加权系数描述,每个个体所受作用力为其他个体对其作用力的加权和。陈世明等采用最小外接圆方法建立了一种基于个体局部感知情况下的群集模型[16]。

Durret等对不同情况下用上述几种建模方法所建立的模型进行了[17]比较研究,通过比较得出结论:用不同的建模方法所得到的模型对群集行为研究的结果不总是相同,并指出考虑空间的基于个体的拉格朗日模型较有优越性。1.2.2 群体智能算法

群体智能算法是基于群体智能而产生的一种新型智能计算模式,目前已成为群体智能研究领域中的一个重要分支。群体智能算法是受蚂蚁、蜜蜂、鸟、鱼等群居性生物群体智能行为的启发,建立的各种基于群体智能的优化算法,包括蚁群算法(Ant Colony [18]Optimization,ACO)、微粒群算法(Particle Swarm [19]Optimization,PSO)、人工蜜蜂算法(Artificial Bee Colony [20]algorithm,ABC)等,其中以ACO和PSO算法最为典型。

1.蚁群算法

蚂蚁是一种典型的极具智慧的群居性生物群体。尽管单个蚂蚁不具有思维能力、智能不高、生存能力非常弱小,但是,蚂蚁群体却能完成诸如收集食物、修建蚁巢、抵御外敌等极高的复杂智能行为,表现出高度的自组织能力和极强的生存能力。蚂蚁群总是能够找到从巢穴到食物源之间的一条最短路径。这是因为每当蚂蚁发现了一条通往食物源的路径时,它就会向该路径上释放一定量的化学物质——信息素,该物质会随时间逐渐挥发。随后的蚂蚁通过感知信息素的浓度大小来选择它将要移动的方向。蚂蚁倾向于选择信息素浓度较高的方向移动。在发现的较短路径上,蚂蚁来回一次的时间较短,信息素挥发的较慢,残留的信息素浓度就较大,选择此路径的蚂蚁就会越多,洒下的信息素自然也会越多,自然会有更多的蚂蚁被吸引过来,从而洒下更多的信息素。这样,越来越多的蚂蚁聚集到较短的路径上来,最短的路径就近似找到了。蚂蚁个体间通过这种信息交流寻求通向食物的最短路径。蚁群觅食这种优化过程的本质在于:信息素越多的路径,被选择的概率越大;路径上的信息素会随蚂蚁的经过而增长,同时也随时间的推移逐渐挥发、消失;蚁群利用信息素为媒介进行间接通信和协同搜索,最终发现觅食的最短路径。

受蚂蚁群体觅食行为及其内在机制的启发,意大利学者Dorigo M于20世纪90年代初在法国巴黎召开的第一届人工生命会议上首次提出了蚁群算法(Ant Colony Optimization,ACO)。在蚁群算法中,引入了正反馈并行机制,通过个体之间的信息交流与相互协作最终找到最优解,使其具有很强的发现较优解的能力。下面以n个城市的TSP问题为例,简要介绍求解最短回路的蚁群算法。

设共有m个蚂蚁,在t代,第i个城市有蚂蚁a(t)个,在第i、j两i城市间的道路上留下的信息素为b(t)。假设每个蚂蚁在未完成一个ij回路时,不重复已走过的城市,则第k个蚂蚁从城市i到城市j的概率为-ct

其中,信息素b(t)可定义为b(t)=e,c>0;或定义为ij

其中,L是第k只蚂蚁求得的回路长度。k

这样,每只蚂蚁经过n次迁移后就得到一条回路,其长度为L。k再利用式(1.4)~式(1.7)重新计算各条路径的信息素浓度,进行下一步搜索。

有关蚁群算法的研究成果在国际学术杂志Nature、Future Generation Computer Systems和IEEE Transactions on Evolutionary Computation上曾相继进行过报道。国内对蚁群算法的研究始于20世纪末,最先研究蚁群算法的是东北大学的张纪会和徐心和。尔后,段海滨的著作《蚁群算法原理及其应用》则为国内第一本系统介绍蚁群算法的学术著作。王常青采用蚁群算法求解做作业车间调度问题,杨勇采用蚁群算法求解连续空间优化问题。目前,蚁群算法已被应用到很多领域,如车间调度问题、旅行商问题、车辆路径问题、数据挖掘、聚类分析、图像处理、网络路由问题等。

2.微粒群算法

微粒群算法(Particle Swarm Optimization,PSO)是由美国社会心理学家Kennedy J和电气工程师Eberhart RC于1995年共同提出的一种基于种群寻优的随机搜索算法。微粒群算法模拟鸟群和鱼群等的群体觅食行为,群体中每个微粒通过学习自身和其他微粒的经验不断改变其搜索方向,以使整个群体飞向问题空间的最优解。

在PSO中,群体中的鸟被抽象为没有质量和体积的“微粒”,每个微粒代表解空间中的一个解,解的优劣程度由适应函数决定,其中,适应函数由优化目标来决定的。微粒之间可以相互协作和信息共享,其运动速度受自身和群体的飞行经验的影响,即通过参考自身和群体的历史最优位置来调整自身当前的运动速度方向和大小,从而使得整个群体有飞向更好搜索区域的能力。

考虑全局优化问题:

这里,。

设微粒i的位置为X=(x,x,…,x),速度为V=(v,v,…,v),其ii1i2inii1i2in历史最优位置为P=(P,P,…,P),群体历史最优位置为ii1i2inP=(P,P,…,P)n,则标准微粒群算法的速度和位置进化方程分gg1g2g别为

式中,x(t),v(t)——分别为微粒i在t代第k维的位置和速度;ikik

w——惯性权重;

c,c——分别为认知系数和社会系数;12

r,r——服从(0,1)上均匀分布且相互独立的两个随机数;12

P(t),P(t)——分别为在t代群体历史最优位置和微粒i历史gkik最优位置在第k维的坐标。

个体历史最优位置P(t)表示微粒i在前t代搜索到的最优位置,i更新规则为

群体历史最优位置P(t)表示整个种群在前 t 代搜索到的最优g位置,定义为

式中,m表示种群规模大小,即种群所含微粒的个数。

由微粒的更新方程可以看出,c,c分别调节微粒向自身历史最好12位置和全局历史最好位置飞行的最大步长,若太小,则粒子可能远离目标区域,若太大则会导致突然向目标区域飞去,或飞过目标区域,适当的c,c可以加快收敛且不易陷入局部最优。为减少种群微粒在搜12索过程中飞出搜索空间的可能性,算法定义了一个最大速度上限V,用以限制微粒移动的大小,即V∈[-V、V]。maxmaxmaxmax

标准微粒群算法的流程如下:

Step1:种群初始化,包括参数m,n,w,c,c,V等初始化,各微12max粒的初始位置和速度在问题空间内随机选择;计算每个微粒的适应值,并选出适应值最好的微粒;微粒的个体历史最优位置P(0)等i于各微粒初始位置,群体最优位置P(0)为适应值最好的微粒所对g应的位置,进化代数t置为0。

Step2:根据式(1.9)计算微粒下一代的速度。

Step3:根据式(1.10)计算微粒下一代的位置。

Step4:计算每个微粒的适应值,并选出适应值最好的微粒。

Step5:根据式(1.11)和式(1.12)更新各微粒的个体历史最优位置与群体历史最优位置。

Step6:如果没有达到结束条件,代数t=t+1,并返回步骤Step2;否则,停止计算,并输出最优结果。

自从微粒群算法提出以来,由于其概念简单,实现容易,能有效解决复杂优化问题,因此获得了飞速发展。学者们已经从算法的收敛性、参数设计、拓扑结构、与其他算法的混合算法研究、应用研究等多个方面进行了深入研究,并提出许多改进方法。在算法的收敛性方面,Bergh从理论上已经证明,标准微粒群算法既不是局部收敛算法,也不是全局收敛算法,并设计了具有局部收敛性能的改进微粒群算法。在此基础上,曾建潮等人提出了保证全局收敛的随机微粒群算法。在参数设计方面,惯性权重的设计包括线性递减策略、指数方式调整策略、抛物线型的调整策略、随机调整策略等;认知系数和社会系数的设计有 Kennedy建议取2.0,Ozcanand建议取1.494,随时间动态调整策略及引入生物学情感模型的调整策略等。在拓扑结构研究方面,已有PSO算法的Gbest模型(全局最好模型)与Lbest模型(局部最好模型),Kennedy提出的环形结构(Ring Topology)、轮形结构(Wheel Topology)、VonNeumann结构及它们的推广等几种基本的邻域结构,王芳提出了基于小世界模型的PSO算法拓扑结构等。有关与其他算法的混合算法研究方面,已有的混合策略有与模拟退火算法的混合策略、与混沌搜索的混合策略、与单纯形法的混合策略、与微分进化算法的混合策略及量子微粒群算法等。目前,PSO算法已被广泛应用于约束优化、多目标优化、动态环境优化、离散优化、组合优化等各种优化问题,以及图像处理、模式识别、数据挖掘、电力系统控制等大量的工程应用领域。1.2.3 群机器人

群机器人是目前群体智能的一个重要应用领域,它研究由大量机[21]器人组成的系统的控制。从20世纪80年代后期开始,国外就有了对移动多机器人系统的研究,如美国学者Beni G等研究的SWARMS[22][23]系统、日本的Asama H 学者提出的ACTRESS 系统和Fukuda教[24]授提出的CEBOT系统。国内有关这方面的研究有中国科学院、上海交通大学、哈尔滨工业大学、东北大学等已先后投入相当的人力物力介入群机器人的研究。近年来有关群机器人研究的会议,有2004年开始的一年一度的Swarm Robotics会议、2006年开始的一年一度的IEEE Swarm Intelligence会议。国外很多有关的项目,如由比利时布鲁赛尔大学Dorigo M博士主持的The Swarm-bots project项目、美国Payton D教授主持的Pheromone Robotics项目、由德国卡尔斯鲁厄大学Worn H教授主持的The I-Swarm project项目,等等。

群机器人是由多个结构和功能相对简单的自治移动机器人组成的人工群体系统。在自组织机制下,通过有限感知和局部交互涌现群体智能,协同完成单个机器人无法完成或难以完成的复杂任务。群机器人系统符合群体智能的的基本特征,有大量个体机器人组成,可达成百上千个以上;个体机器人是自治的,是能够与环境交互的独立实体,其能力有限,行为简单,只有局部感知能力,通过与附近其他成员的局部交互来通信;需要大量个体机器人协作完成任务;方便增加和减少机器人,稳健性强。

群机器人的研究方法可以从普遍存在群体智能的自然界和人类社会中得到启发,其启发方法可归结为:基于物理系统的方法、基于生[25]物系统的方法和基于社会系统的方法。基于物理系统的方法是启发于物质世界很多富有规律的整体行为,如固体的结晶、液体流动时的自觉避障、气体分子的扩散、太阳系各天体有规律的运动等,这些整体行为都遵循物理规律,由此借用物理学原理和方法构建群机器人的行为,如拟态物理学方法模拟物理学的引力和斥力研究群机器人的编队、避障和覆盖等问题。基于生物系统的方法是模拟大量群居性生物个体通过局部交互凸显群体智能行为来求解复杂问题,如蚁群算法和微粒群算法分别模拟蚂蚁和鸟群的觅食行为已成功应用于求解很多复杂优化问题,同时也被应用于群机器人的控制设计中。基于社会系统的方法是仿真协调有序的人类社会的行为方式,如英国Essex大学研究的EOS项目。

群机器人的主要研究内容包括个体机器人的设计、群体通信及群体控制三个方面。设计适合群机器人系统的单个机器人要考虑机器人应具备怎样的传感功能,是局部感知还是全局感知;应采用怎样的控制体系结构,是慎思型还是反应式,等等。群体通信应考虑交互的范围,如个体机器人与其他哪些个体进行交互;交互的媒介是虚拟力(场)、信息素还是通信协议;交互的性质是显性交互还是隐性交互或混合交互等。根据群体智能中分布式控制的特点,群机器人系统不需要集中控制器协调众多机器人,每个机器人都是完全自治智能体,与其周围环境,以及其邻域范围内的其他个体进行交互,执行有限的几项简单动作,众多机器人的简单行为组合涌现一种群体协作行为。

群机器人的应用前景广阔,尤其适合在人力不可达或有危险的环境中执行任务,如森林火灾监控、未知环境探索、危险品的检查、收集和搬运、定位有害气体的泄漏源等。这其中涉及的主要问题有群机器人的队形控制、区域覆盖、目标搜索、合作搬运、定位等。1.3 模拟物理学原理的启发式算法

模拟物理学原理的启发式算法通过模拟物理学原理和规律制定优化算法的搜索策略,实现寻优的目的。这类算法有模拟退火算法、类电磁机制算法和中心力算法等。1.3.1 模拟退火算法[26]

模拟退火算法(Simulated Annealing,SA)是一种启发式单点随机搜索优化算法,其思想来源于热力学中固体退火过程。固体退火过程是先将固体加温至充分高,再让其徐徐冷却,加温时,固体内部分子随温度升高变为无序状,内能增大,而徐徐冷却时分子渐趋有序,最后在常温时达到基态,内能减为最小。模拟退火算法模拟该物理退火过程,由一个给定的初始高温开始,利用一种具有概率突跳特性的Metropolis准则的邻域移动方法在解空间随机搜索,伴随着温度的不断下降重复搜索过程,最终得到问题的全局最优解。

Metropolis准则的邻域移动方法,是实现模拟退火算法进行全局搜索的关键因素。根据Metropolis准则,粒子在温度T时趋于平衡的概-ΔE/(KT)率为e,其中E为温度T时的内能,ΔE为其改变量,K为Boltzmann常数。将内能看做目标函数值,若新粒子的目标函数值小于当前粒子目标函数值,即表示新状态的内能小于当前状态的内能,则进行无条件移动,否则,根据该平衡概率进行有条件移动。

模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率1收敛于全局最优解的全局优化算法。它的应用很广泛,典型的如求解组合优化问题、0-1背包问题、调度问题,等等。1.3.2 类电磁机制算法[27]

类电磁机制(Electromagnetism-like Mechanism,EM)算法是由Birbil和Fang于2003年提出的一种基于种群的随机优化算法。该算法受电磁场中带电粒子间吸引和排斥机制的启发,将所优化问题的每个样本解看做一个点电荷,按一定的吸引和排斥准则使得搜索粒子朝最优解移动。这种吸引和排斥准则与电磁理论中的吸引与排斥机制类似,但有一定的差异,故称为类电磁机制。

EM算法将初始化的一群搜索粒子想象成空间中的一群带电粒子,每个带电粒子都被看做一个具有电荷、位置属性且没有体积的粒子,每个粒子的电荷由待优化的目标函数的适应值决定,适应值越优,i粒子的电荷就越大。设带电粒子i的电荷为q,则其计算表达式如下:

式中,n表示问题维数,m表示种群规模大小,f(x)为最优best粒子的适应值。

按照库仑定律,粒子的电荷大小决定了该粒子对其他粒子吸引或排斥的强弱,粒子电荷越大,吸引或者排斥力就越强。每个粒子的运动方向由其他粒子对它的吸引或排斥力的合力方向来确定,运动步长i随机。设带电粒子i所受其他粒子吸引或排斥的合力为F,其计算表达式如下:

粒子的位置迭代方程如下:

由式(1.15)可以看出,作用在每个粒子上的合力都被“归一化”了,即粒子运动仅参考合力的方向。式中,λ为在[0,1]上均匀分布的随机变量,说明粒子将沿着合力的方向以一个随机步长移动。RNG为一个向量,其分(向)量表示对应的朝上边界u或者下边界lkk移动的可行步长。

EM算法包括初始化、局部搜索、计算合力和移动粒子4个组成部分,具体的算法流程如下。

Step1:初始化种群。在问题可行域内随机选取m个粒子;计算粒子适应值,并选出种群中的最优粒子;进化代数t=0。

Step2:局部搜索。局部搜索主要用于在单个粒子的邻域范围内进行精细搜索,以增强EM算法的局部搜索能力,提高解的精度。

Step3:根据式(1.13)和式(1.14)计算粒子所带电量及所受合力。

Step4:根据式(1.15)更新粒子的位置信息。

Step5:计算粒子适应值,更新种群最优粒子及其适应值。

Step6:判断是否满足结束条件,若满足,则停止计算,并输出最优结果;若不满足,进化代数t=t+1,返回Step2。

Birbil和Fang针对进行局部搜索的粒子个数不同,给出了3个版本的EM算法:①对所有粒子都不进行局部搜索;②对所有粒子都进行局部搜索;③只对当前最优粒子进行局部搜索。所使用的局部搜索是最简单的线性搜索,对每个粒子的每一维按照一定的步长进行搜索,一旦找到一个更好的解就停止搜索。作者对典型的难优化低维函数试验测试表明,版本①的局部搜索能力很弱,说明EM算法自身几乎没有局部搜索能力;版本②求得解的精度较高,但搜索效率很低,而版本③可以有效平衡解的精度和搜索效率这对矛盾。因此,对于自身缺乏局部搜索能力的EM算法而言,局部搜索在该算法中起着非常重要的作用。

EM算法的寻优机理简单,收敛速度较快,是一种有潜力的启发式算法。目前,EM算法已受到国内外很多学者的关注,相关的研究[28~30]有算法的改进、算法的收敛性证明以及算法在组合优化问题、约束优化、工程调度、多目标优化问题等方面的应用研究。1.3.3中心力算法[31]

中心力算法(Central Force Optimization,CFO)是由美国学者FormatoR于2007年提出的一种受自然启发的基于种群的确定性搜索算法。中心力算法是一种基于万有引力定律的隐喻,以在三维物理空间受万有引力作用下飞行的行星来类比在目标函数的决策空间搜索最大值的过程。一群飞入太阳系的行星,如果时间足够长,大多数行星将会聚集在具有最大万有引力的行星的周围,以此来类推搜索目标函数的最大值。CFO算法将所优化问题的种群看做一群飞入太阳系的行星,行星的质量是其适应值的正比例函数(求解全局最大化问题)。行星通过万有引力作用彼此之间相互吸引,其运动遵循动力学规律,最终各行星会停留在各自的平衡位置,且大部分行星聚集在质量最大的行星(称为最大行星)周围,最大行星则占据目标函数适应值最优的位置,由此求得目标函数的最优解。

在物理学中,个体i和j之间的万有引力的表达式为

根据牛顿第二定律,个体i在个体j的引力作用下产生的加速度ai的表达式为

CFO算法通过借鉴万有引力定律和牛顿第二定律,将搜索粒子看做具有质量、加速度和位置属性的物理个体,其寻优过程可分为3个部分:初始化种群、个体运动、逐步收缩问题空间。初始化种群要求初始种群在问题空间内均匀分布。个体之间具有相互吸引力,每个个体在其他个体引力的合力作用驱动下运动。假设在j-1代,个体p的适应值为,其加速度计算表达式为

式中,N为种群个体数量,为个体k的质p量。由于物理实体的质量都为正数,因此,作者构造了阶跃函数使得个体质量为非负数。显然,个体k的质量是有关个体k与个体p的适应值之差的正比例函数。指数参数α>0,β>0,在实际的物理空间,按照万有引力定律,这两个指数参数应取值为:α=1,β=3,但在CFO算法空间,α和β则可以灵活取值。仿真实验表明α和β的取值对CFO算法是否收敛敏感度比较高。

个体p在j代的位置记为,则其位置迭代方程为

在种群运动过程中,会出现某些超出问题空间的个体,称为越界个体。对越界个体,作者按不同的规则将其映射回问题空间。其中一种方法如下:

式中,F为重定位因子,且F=0.5。reprep

在最早提出的CFO算法框架中,仅有初始化种群、个体运动两部分;在后期的版本中,为提高该算法的收敛速度,作者加入了“逐步收缩问题空间”这部分内容,即在算法执行到某一代后,每隔一定代数围绕最优个体(适应值最大个体)位置R缩小问题空间;且将越best界个体拉回

当前的问题空间,具体的收缩问题空间的计算表达式如下:

CFO算法具体的实现流程如下。

Step1:初始化种群。按照种群个体在问题空间均匀分布的原则,计算个体的初始位置及对应的适应值,设置每个个体的初始速度为零;进化代数t=0。

Step2:个体运动。根据式(1.18)和式(1.19)更新个体的位置信息;并根据式(1.17)对越界个体进行越界处理。

Step3:计算个体适应值,并更新种群最优个体及其适应值。

试读结束[说明:试读内容隐藏了图片]

下载完整电子书


相关推荐

最新文章


© 2020 txtepub下载