第八章 群体智能

第八章群智能通过本书前面各章所介绍的人工智能实现途径所实现的均是单个个体的智能。虽然在进化主义中，牵涉到群体的进化，但最终在解决问题时依靠的还是单个个体的能力。群智能则不同，它通过多个智能实体之间的协作来解决问题，利用的是群体的智慧，而不是单个个体的能力。目前，在群智能上主要包括两大类工作。一类是多智能体系统，利用多个智能体之间的协调和协作，完成单智能体不能完成或难以有效完成的任务。另一类是群智能优化算法。与进化计算所要解决的问题类似，群智能优化算法也是用于搜索问题的全局最优解，并且其中同样体现了仿生的思想，它模拟了生物群体通过相互协作解决复杂问题的行为方式。目前，群智能优化算法主要包括蚁群优化算法和粒子群优化算法。其中，蚁群优化算法模拟了蚂蚁群体觅食的行为方式，粒子群优化算法则模拟了鸟群的群体性行为。本章首先介绍多智能体系统中核心的协调与协作机制以及相应的强化学习方法，然后阐述蚁群优化算法和粒子群优化算法的基本原理。8.1多智能体系统多智能体系统是在单智能体基础上发展起来的，它通过多个智能体相互之间的协调和协作，来解决单个智能体不能解决或者难以有效解决的复杂问题。其中，智能体之间的协调和协作是多智能体系统中的核心问题，有效的协调与协作方法是多智能体系统中的主要设计内容。8.1.1智能体之间的通信机制为了进行协调和协作，智能体之间需要彼此通信、交换信息。目前，智能体之间的主要通信机制包括黑板系统和消息系统。黑板系统黑板是黑板系统中的公共信息存储和交流区。在黑板系统中，各智能体之间不发生直接通信，而是通过黑板交换数据、信息和知识。智能体在需要时按照自身权限访问黑板，确定是否有新的信息，或者向黑板上添加自己的信息。黑板系统的主要问题是当系统中存在很多智能体时，黑板上的数据量会按指数率增长，难以进行高效的信息存储和检索。解决这一问题的一种思路是为每个智能体在黑板上分配一个单独的区域。消息系统消息通信机制是实现灵活复杂的协调策略的基础。相对于黑板系统，消息系统的通信方式更为灵活。在消息系统中，任意两个智能体之间可直接通过消息交换数据、信息和知识。一个智能体可以向另外一个智能体发送消息，也可以将消息广播给多个智能体。发送消息的智能体被称为发送者，接受消息的智能体被称为接受者。发送者在发送消息时指定消息的接受者，除了接受者以外的其它智能体不能读取消息。为了支持消息系统，消息的发送和接收需遵守预先定义的通信语言。目前，智能体通信语言的主要理论基础是英国哲学家和语言学家奥斯汀提出的言语行为理论。言语行为理论认为：通信语言是一种动作，和物理上的动作一样，发言者的目的是改变世界的状态，通常是指听众的某种心智状态。在智能体通信语言的研究中，言语行为理论主要被用来研究主体之间可以交互的信息类型。一种通用的分类方式是将言语行为分为表示型和知识型，还可进一步细分为断言型、指示型、承诺型、允许型、禁止型、声明型等类型。在言语行为理论基础上，目前国际上有一定影响的智能体通信语言包括美国国防部高级研究计划署(Advancedresearchprojectagency,ARPA)提出的知识查询与操纵语言(KnowledgeQueryandManipulationLanguage,KQML)、知识交换格式(KnowledgeInterchangeFormat,KIF)和欧洲智能体协会(foundationforintelligentphysicalagents，FIPA)提出的智能体通信语言(AgentCommunicationLanguage，ACL)语言。这里主要介绍KQML语言的基本内容。KQML分为通信、消息和内容三个层次。其中通信层是通信参数协议；消息层规定与消息有关的言语行为的类型，相应的消息被称为动作表达式。这些动作表达式主要是从言语行为理论演化而来的；内容层则规定了消息的内容。在KQML中，除了可以通过发送-接受方式进行智能体之间的通信外，还提供了基于通信服务器的消息交换方式。通信服务器类似于黑板系统中的黑板，但是其功能比黑板丰富，它将搜索信息的智能体与提供信息的智能体连接起来。8.1.2智能体之间的协调策略智能体之间的协调是指在开放、动态的多智能系统环境下，如何协调不同智能体之间的行为，解决其在目标规划、资源利用等方面可能存在的冲突，以保证多智能系统的正常运行；或者使各智能体以一致、和谐的方式共同工作。协调的一个主要方面是避免智能体的死锁和活锁问题。死锁是指各智能体互相等待，无法进入下一步工作；活锁是指智能体虽在不断工作，却无任何进展。目前，多智能体系统的协调策略主要分为四种：组织型：提供一个专门用于协调的、全面了解系统状况的智能体，由它按照某种特定的结构组织智能体之间的协调。合同型：通过订立合同的方式进行协调。在此过程中，每个智能体兼有管理者和投标者的双重职能。当智能体无法用本地资源解决问题时，将问题分解为若干子问题，并寻找合适的智能体来解决这些子问题。子任务分配通过投标和签订合同方式实现。规划型：通过规划智能体的行为实现协调，消除彼此间的冲突。具体分为集中式规划和分布式规划两种方式。在集中式规划方式中，各智能体将自己的规划发送给一个集中的协调者，由该协调者分析不同智能体的行为，判断并解决其中的潜在冲突；在分布式规划方式中，各智能体管理自己的规划，通过通信了解其他智能体的规划，并根据需要修改各自的规划，直到消除彼此间的冲突为止。法规型：为智能体制定一套行为法规，要求每个智能体必须遵守。这些法规一方面会限制每个智能体所能采取的行动，另一方面也可以使智能体在确定行动规划时，可以确定其他智能体的行为方式，从而确保智能体之间没有冲突。法规型适合于空中运输控制或城市交通控制等具有明确法规形式的多智能体系统。8・1・3智能体之间的协作策略智能体之间的协作是指如何在不同智能体之间建立合作关系，以完成某一共同任务。智能体之间的协调是其协作的基础，而协作则是协调的主要目的。有时，协调与协作是难以明确区分的，如上述合同式协调方式也可认为是一种协作过程。根据智能体之间的协作方式，可将多智能体系统划分为两种类型：合作型：各智能体为实现系统的共同利益而相互协作，设计目标是系统的整体性能，而不是针对其中单个智能体。竞争型：各智能体都是为着扩大自身利益而工作。为实现自身利益，各智能体可以与其它智能体达成一致，但也可能没有协作关系，甚至可能存在竞争和互斥关系。目前，智能体之间的协作主要通过两条途径来解决。一条途径是将博弈论、经典力学理论中有关多实体行为的方法和技术用于智能体之间的协作;另一条途径是基于智能体的目标、意图、规划等心智状态来研究智能体之间的协作。后一类方法应用更为广泛。一些典型的协作方法包括部分全局规划、基于约束传播的规划、基于生态学的协作与规划、基于博弈论的协作与规划、基于意图的协商和基于范例推理的合同网协商等8.1.4多智能体强化学习对于多智能体的强化学习，存在多种不同的分类方法。一种分类方法是根据学习的组织方式，将多智能体学习划分为三类：乘积形式(multiplication)＞分割形式(division)和交互形式(interaction)［92］。其中，乘积形式是将多智能体系统作为一个单独的学习型智能体;在分割形式中，每个智能体拥有独立的强化学习机制，并且不与其它智能体进行交互；在交互形式中，每个智能体有独立的强化学习机制，但通过与其它智能体的适当交互加快学习过程。另一种分类方法是根据智能体之间的协作方式，将多智能体强化学习方法划分为合作型学习、竞争型学习和半竞争型学习三类［77］。下面按后一种分类方法介绍多智能体的强化学习。合作型多智能体强化学习在合作型多智能体强化学习中，各智能体的目标与整体系统的目标是一致的。因此。可以将多智能体系统作为一个单智能体，多智能体系统的行为是其中所有单智能体的联合行为，在此基础上采用单智能体的强化学习方法进行合作型学习。竞争型多智能体强化学习在竞争型多智能体系统中，每个智能体目标与其它智能体目标是完全相反的。由于某一智能体所获得的奖励值取决于其它智能体的动作，因此传统的单智能体强化学习方法不再适用。根据博弈论，这种竞争型关系对应于零和决策，因此最简单的解决方法是极大极小策略。以两个竞争型智能体为例，对于其中一个智能体，其最优策略应是在另一智能体采取对于当前智能体而言最坏动作的情况下，选择奖励值最大的动作。当采用0学习方法时，极大极小策略可形式化地表示为：V(5)=maxminQ(s,a,b). (8-1)a^AbeB半竞争型多智能体强化学习在很多实际多智能体系统中，单个智能体所得奖励值并不是其它智能体所得奖励值的负数，即不是非零和决策问题，从而不能应用极大极小策略获得最优解。本质上非零和决策问题更能反映多智能体系统中个体理性与群体理性发生冲突的本质。有学者利用元博弈理论，在考虑智能体自身愿望的基础上，通过预测对手的策略来修正自己的策略。8.2蚁群优化算法蚁群优化算法是由意大利学者M.多利格在二十世纪九十年代提出的一种模拟蚂蚁群

体觅食行为的优化算法。该算法思路新颖，具有鲁棒、并行性等优点，已得到人们的广泛关注和应用，并在应用中表现出优异的性能和广阔的应用前景，成为人工智能和最优化领域中的研究热点和前沿性课题之一。8.2.1蚁群觅食行为对计算的启示蚂蚁是群居性昆虫。研究群居型昆虫的科学家们发现：昆虫在群落一级的合作基本上是自组织的，似乎没有集中的指挥。而且在许多场合下昆虫的合作形式是很简单的，但它们却可以通过简单的合作解决许多复杂的问题。以蚂蚁为例，它们在其合作寻找食物的过程中，总能找到从蚁巢到食物源的最短路径，表现出惊人的群体性智能。这正是蚁群优化算法的思想源泉。那么，为什么蚂蚁能够通过群体的合作找到从蚁巢到食物源的最短路径呢？原因在于：蚂蚁在运动时，会分泌并在经过的路径上留下一种被称为信息素的化学物质。所有蚂蚁都能感知信息素的存在及其浓度，并在其指导下倾向于朝着信息素浓度高的方向移动。下面以图8-1所示例子，详细说明蚂蚁的觅食过程。图8-1(a)中，蚁巢与食物源之间没有障碍，蚂蚁选择直线行走。一旦在其行走路线上出现障碍物时，如在图8-1(b)所示情况下，蚂蚁将如何处理呢？显然，蚂蚁有两条路径可供选择。路径1为“巢穴-障碍物上方-食物”；路径2为“巢穴-障碍物下方-食物”。起初，蚂蚁等概率地选择从障碍物的上方或下方绕过障碍物，如图8-1(c)所示。由于路径1的长度小于路径2的长度，因此单位时间内绕过障碍物上方行走的蚂蚁数量将多于绕过障碍物下方行走的蚂蚁数量。这意味着蚂蚁们在路径1上遗留的信息素的浓度逐渐会高于在路径2遗留的信息素的浓度。这样，根据蚂蚁倾向于朝着信息素浓度高的方向移动的特性，通过路径1的蚂蚁数量将越来越多，而通过路径2的蚂蚁数量将越来越少，这又反过来增大了两条路径上信息素浓度的差异，使得不仅蚂蚁选择路径1的概率不断增加，而且相应概率的增长率也不断增加，表现出信息的正反馈现象。最终使得每个蚂蚁个体都能找到蚁巢与食物源之间的最短路径，即路径1，如图8-1(d)所示。(d)(d)图8-1蚂蚁觅食过程示例综上所述，在整个路径寻优过程中，单只蚂蚁的寻优能力有限，但蚁群具有高度的自组织性，通过信息素交换路径信息，形成集体自催化行为，找到最优路径。根据蚂蚁觅食原理和过程，可构造人工蚂蚁，使其按照类似于真实蚂蚁的觅食过程寻找问题的最优解。人工蚂蚁应具有真实蚂蚁的如下特性：人工蚂蚁之间应能够相互通信和影响。真实蚂蚁通过信息素互相影响，人工蚂蚁也应能够在所经过的解的路径上留下数字信息素，该信息素记录了人工蚂蚁当前解和历史解的性能状态，而且可以被后继人工蚂蚁读取。数字信息素的浓度也是人工蚂蚁选择路径的启发式信息。此外，真实蚂蚁的信息素具有挥发特性，即随着时间推移信息素逐渐挥发，减小历史遗留信息对蚁群的影响。同样，人工蚂蚁的数字信息素也应具有挥发性。使人工蚂蚁逐渐忘却历史遗留信息，在选择路径时不局限于以前人工蚂蚁的残留经验。在当前信息的引导下应采用随机选择策略。真实蚂蚁的路径选择行为是随机性的，信息素的作用是提高了蚂蚁对路径的偏爱，但选择仍然是随机的。人工蚂蚁对解的路径的选择也应具有这种特性，这样才有可能跳出局部最优解。8.2.2蚁群优化算法的基本原理根据上述蚂蚁觅食过程的启示，蚁群优化算法是采用人工蚂蚁的行走路线来选择问题最优解的一种算法。每只人工蚂蚁独立地在问题解空间中搜索(行走)，当碰到解的分支路径时，随机地选择某条路径行走，其中信息素浓度更高的路径具有更大的选择概率。人工蚂蚁在行走的路径上释放出与路径长度有关的信息素。路径越短，信息素浓度越高。随着时间的推移，路径长度短的路径上的信息素浓度越来越高，引导更多的人工蚂蚁通过最优的求解路径，释放出更多的信息素，而其他路径上的信息素在挥发特性的作用下却逐渐消失，从而形成正反馈效应。最终整个蚁群在正反馈的作用下集中到代表最优解的路径上，表明找到了最优解。最初提出的蚁群优化算法被称为蚂蚁系统。下面以蚂蚁系统解决旅行商问题的过程为例，详细说明蚁群优化算法的数学模型和实现过程。对下面所描述的解决TSP问题的蚁群优化算法稍加修改，即可应用于其它组合优化问题。关于TSP问题的说明，请见第4.5.3节中的相应内容。解决TSP问题的蚂蚁系统首先给出解决TSP问题的蚂蚁系统中的如下符号及其意义：七--第i座城市气-城市c与Cj之间路径距离m--蚁群中蚂蚁的数量七Q--第t时刻在路径c.-%上残留的信息素量，初始时刻各条路径上七Q相同Tjt)--第t时刻第k只蚂蚁在路径C.-\上释放的信息素量门G)--第t时刻在路径c-c上问题所提供的启发式信息，通常取为1/d，表示优jijij先选择局部距离短的路径Nk(t)--第t时刻在c处允许第k只蚂蚁访问的下一个城市的集合i ipk(t)--第t时刻第k只蚂蚁在路径c-c上的移动概率，ij ij

可以认为lQ是由蚁群所提供的启发式信息，气Q则是由问题本身所提供的启发式信息。研究表明：如果仅考虑信息素，而不考虑任何有效的由问题本身所提供的启发式信息，算法的效果将变得非常糟糕。在下面的叙述中，启发式信息专指由问题本身所提供的启发式信息，即气Q，蚂蚁系统中，每个人工蚂蚁根据各条允许路径上的信息素量和启发式信息随机确定其移动方向。一种合理的方式是优先选择信息素量大且局部距离短的路径，相应地有TOC\o"1-5"\h\z3）1"U （）（t）」~rmEeNP—5iiii , （8-2）j 。） /、0, j任Nk（t）其中a和P为参数，分别反映了信息素和启发式信息的影响程度。在蚂蚁走完一步或完成对所有城市的遍历后，要对路径信息素进行更新，其更新基本公式为(8-3)(8-4)蜃()-*蜃k(),

jj(8-3)(8-4)k—1七(t+1)—(1_P).TjQ+竺(t)公式（8-4）中P是信息素挥发系数，要求0<P<1。在公式（8-3）、（8-4）所表示的基本信息素更新公式基础上，有三种不同的信息素更新策略，分别对应于蚂蚁系统的三种版本：蚁密模型，蚁量模型，蚁周模型。其中，在蚁密模型和蚁量模型中，蚂蚁每走一步就更新路径上的信息素；而在蚁周模型中，蚂蚁完成一次城市的遍历后才更新所有路径上的信息素。蚁周模型的效果优于蚁密模型和蚁量模型。现在所说的蚂蚁系统一般是指对应于蚁周模型的蚂蚁系统。设己为常量，Lk为第k只蚂蚁遍历城市的路径长度和，则蚁周模型对应的Atj（t）如下：求k（）—[Q/B，第次只蚂蚁在本次遍历中经过路径勺一“j[。，其他 ^根据路径选择方法和信息素更新公式，蚂蚁系统解决旅行商问题的算法流程如表8-1所示。表8-1解决TSP问题的蚂蚁系统算法Stepl参数初始化Step2将m只蚂蚁随机放在n个城市上Step3针对每只蚂蚁执行以下步骤：Step3.1根据公式（8-2）计算蚂蚁选择城市的概率Step3.2使蚂蚁移动到具有最大转移概率的城市Step3.3重复Step3.1-Step3.2，直到蚂蚁遍历所有城市Step4按照公式（8-4）更新所有路径上的信息素。Step5如果满足终止条件，算法停止，输出当前最优结果；否则返回Step3。表8-1所示算法流程中的核心步骤是Step3和Step4，分别完成解路径的构建和信息素的更新。包括蚂蚁系统在内的所有蚁群优化算法都可认为是由解路径构建和信息素更新两个关键过程构成的。8.2.3蚁群优化算法的改进对蚂蚁系统的改进包括两个方面。一个方面的改进是提高其性能，改善其寻优的效果与效率；另一个方面的改进是扩大其应用领域，使其不仅可以应用于离散的组合优化问题，也可应用于连续优化问题，如函数优化问题等。本节仅讨论第一个方面的改进，关于第二个方面的改进，请读者参考有关文献。在性能的改善上存在两种策略。一种策略是在蚂蚁系统上进行扩展，使用与蚂蚁系统相同的解路径构建过程和信息素更新过程，但在信息素更新细节方面有所区别。这一类扩展算法包括精化蚂蚁系统，基于排列的蚂蚁系统和最大最小蚂蚁系统。另一种策略是对蚂蚁系统进行较大幅度的修改。这一类改进算法包括蚁群系统，近似非确定树搜索算法和超立方体框架。精化蚂蚁系统EAS的主要改进思想是对算法迄今为止找到的最优路径给与额外的正反馈，或者说使找到当前最优路径的蚂蚁向相应路径释放额外的信息素。设b表示找到当前最优路径的蚂蚁，。为加权系数，则信息素更新公式为：(8-6)T'+1）=G-p）«）+章'）+赤%（t）.(8-6)基于排列的蚂蚁系统在ASran算法中，蚂蚁释放的信息素大小随着蚂蚁在排列中的先后次序逐渐减小。此外，与EAS算法类似，找到当前最优路径的蚂蚁会在相应路径上释放更多的信息素。在更新信息素之前，蚂蚁按照其对应路径长度的递增关系排序。只有排列在最前面的（w-1）只蚂蚁和找到当前最优路径的蚂蚁才能释放信息素（当前最优路径可能不是在本次循环中发现的）。蚂蚁释放的信息素将按照其排列顺序赋予权值。具体权值更新公式如下：(8-7)T(t+1)=G-p).TQ+Uj-思"0+泓"(t).

jjjj(8-7)r=1最大最小蚂蚁系统在最大最小蚂蚁系统中，同样只允许找到最优路径的蚂蚁释放信息量，但此处最优路径

可以是在本轮循环中发现的最优路径，也可以是在当前已发生的所有循环中找到的最优路径。设b表示对应上述两种最优路径中任一种的蚂蚁，则信息素更新公式为：(8-8)T司(t+1)=G-p).T司Q+章b；Q(8-8)在MMAS中，对应两种不同最优路径的蚂蚁轮流使用，其轮换频率可随迭代次数而改变。为了避免算法过早陷入局部最优，MMAS将每条路径上的信息素量限制在一个区间内，并在初始时将路径上的信息素量设定为区间的上界，使算法能在搜索初步阶段探索尽可能多的路径。MMAS被认为是目前解决TSP等离散组合优化问题的最好蚁群算法之一。蚁群系统ACS算法对蚂蚁系统的改进集中在以下两点：（1）采用伪随机比例规则（Pseudo-RandomProportionalRule）确定蚂蚁的移动方向。在这种规则下，存在一个参数q0£[0,1]。第k只蚂蚁在确定移动方向时，首先产生一个[0,1]t (t)1h G)1il il(8-9)范围内的随机数q，如果t (t)1h G)1il il(8-9)=argmaxleNki否则仍按公式（8-2）确定移动方向。公式（8-9）表示的是按确定方式选择当前最优移动方向，公式（8-2）则表示的是按随机方式选择移动方向，但对当前最优移动方向有所偏爱。因此伪随机比例规则是综合了确定性选择和随机性选择的策略。同时在这种规则下，还可以通过调整％，达到均衡集中搜索当前最优路径与探索其他区域的目的。（2）在信息素更新方式上采用全局更新与局部更新相结合的方式。蚂蚁每移动一步，就根据局部信息对路径上的信息素进行更新。当所有蚂蚁的路径构建完毕后，再进行一次全局更新。在全局更新时仅考虑当前所找到的最优路径。局部更新规则：匕（t+1）=（1―头Q+孕0,（8-10）其中&为常数，满足0…1，'0是信息素量的初始值。全局更新规则：(8-11)t'+1)=(1-p>户+pM%(t).(8-11)8.3粒子群优化算法1995年，詹姆斯•肯尼迪和鲁塞尔•埃伯哈特提出了粒子群优化算法。粒子群优化算法的优点包括：（1）算法简单，易于实现；（2）实数编码方式适合于处理实值优化问题；（3）与进化计算方法一样，只要函数值即可进行优化，无需函数的梯度信息，适应面较广;（4）优化性能良好;。近年来，粒子群优化算法已成为国际上人工智能与优化计算领域的热点问题之一。8.3.1鸟群飞行方式对计算的启示动物学家雷诺兹和海珀乐分别在1987年和1990年发表论文，讨论在鸟群群体运动中蕴含的美学。他们发现：由数目庞大的个体组成的鸟群可以在飞行中进行方向改变，队形散开或队形重组等行动。在鸟群的群体性行为中，有某种潜在的能力或规则保证了鸟群中各个个体采取同步的行为。海珀乐提出了一个模仿鸟群飞行行为的模型。肯尼迪和埃伯哈特对海珀乐的模型进行了修正，使得粒子在解空间中飞行，并在最好解处降落，从而得到了粒子群优化算法。8.3.2粒子群优化算法的基本原理在粒子群优化算法中，由m个粒子组成的群体在d维解空间中以一定速度飞行。粒子飞过的每个位置都对应于问题的一个解，粒子飞行的过程就是搜索的过程。粒子的飞行速度受限于最大速度vmax。粒子的位置和速度一般在连续实数空间中取值。每个粒子在飞行时，根据自己飞过的历史最优点和群体邻域内其他粒子飞过的历史最好点，对自己的位置和速度进行调整。算法停止后，选择群体内所有粒子飞过的历史最好点作为最优解。TOC\o"1-5"\h\z粒子位置和速度的调整是粒子群优化算法的关键。设x=G,X,…,X），ii1i2 idv=（v,v,…,v），p=（p,p,…,p）分别表示第i个粒子的位置、速度和当前飞过ii1i2 idii1i2 id的历史最优点，P=\,P，…,P）表示群体邻域内所有粒子飞过的历史最优点，t表g g1g2 gd示迭代次数，则常用的速度和位置更新公式如下：vt+1=^vt+cg^pt-xtXc门^pt-xt）k=1,2，…，d, （8-12）ik ik1ikik2gkikXt+1=Xt+vt+1,k=1,2,…，d, （8-13）ikikik其中，&和门是［0,1］区间内服从均匀分布的伪随机数，c1和c2被称为学习因子或加速系数，«被称为惯性权重。公式（8-12）、（8-13）表明，粒子在修正自身速度和位置时，考虑了三个方面的因素：公式（8-12）右侧第一项，表示前次迭代时自身的飞行速度，即飞行中的惯性，这是粒子能够进行飞行的基本条件；公式（8-12）右侧第二项，代表自我认知的部分，粒子在飞行中考虑到自身的经验，尽量向曾经飞过的历史最优点靠近；公式（8-12）右侧第三项，代表社会经验的部分，粒子在飞行中还考虑到社会的经验，向粒子中其他粒子学习，尽量向所有粒子曾经飞过的历史最优点靠近基于速度和位置更新公式，粒子群优化算法的一般流程如表8-2所示。表8-2粒子群优化算法流程Stepl采用随机方法初始化粒子群中各粒子的位置和速度。Step2计算每个粒子的适应值（目标函数值）。Step3确定每个粒子的历史最优点和所有粒子的历史最优点。Step4按公式（8-12）更新各粒子的位置和速度。Step5如达到停止条件，算法结束，否则转Step2。这里，停止条件一般为预设的最大迭代次数或找到可以接受的满意解。8.3.3粒子群优化算法中的有关参数上述粒子群优化算法中存在一些参数，其意义和设定方法分别阐述如下。最大速度vmaxV决定了粒子在一次飞行中最大的飞行距离。该值较大，则算法的广域搜索能力强，max但粒子容易飞过最优解；该值较小，则算法的局部搜索能力强，但容易陷入局部最优。分析和实验表明，Vmax的作用可以通过惯性权重来实现。因此，现在Vmax一般仅用于限定分量的变化范围，无需细致的选择和调整。群体邻域拓扑结构群体邻域有不同定义策略，相应定义策略被称为邻域拓扑结构。可将邻域拓扑结构分为两大类。第一类方法是将群体中所有粒子定义为邻域，相应算法为全局粒子群优化算法；第二类是取群体中部分粒子为邻域，相应算法为局部粒子群优化算法。全局粒子群优化算法收敛速度快，但存在陷入局部最优的可能；而局部粒子群优化算法收敛速度慢，但不易陷入局部最优。在局部粒子群优化算法中，可以按位置相邻或按索引号相邻两种原则确定邻域。（1） 基于位置的邻域拓扑结构在每次迭代时，计算一个粒子与其他粒子之间的距离，根据距离远近确定该粒子的邻域。一种具体的实现方法被称为动态邻域拓扑结构。在动态邻域拓扑结构中，初始时粒子的邻域只有自己，随着迭代次数的增加，邻域范围逐渐增大，直至最后将群体中所有粒子作为自己的邻域。这样可以使初始迭代有较好的局部搜索性能，而在迭代后期有较好的广域搜索性能。（2） 基于索引号的邻域拓扑结构基于索引号的邻域确定方法按照粒子之间的固定拓扑结构确定其邻域，避免了计算粒子间距离的过程，因而效率较高。固定拓扑结构类型有环形结构、轮形结构、星形结构和随机结构。在环形结构和轮形结构中还可加入捷径，形成带捷径的环形结构和带捷径的轮形结构。学习因子c和c1 2学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而在飞行中向自己的历史最优点和群体邻域内历史最优点靠近。匕和c2通常取为2。但为了提高算法性能，也可以使学习因子动态变化，如同步时变方法、异步时变方法等。在同步时变方法中，两个学习因子同步线性减小；而在异步时变方法中，随着迭代次数不断减小自我学习因子C和不断增1大社会学习因子C，以达到在优化初期加强自我全局搜索，而在后期促使粒子收敛于群体2全局最优解的目的。惯性权重惯性权重决定了速度更新时当前速度对未来速度的影响程度。合适的选择使粒子群优化算法具有均衡的局部探索能力和全局开发能力。较大的惯性权重使粒子在自己原来的方向上具有更大的速度，从而在原方向上飞行更远，具有更好的局部探索能力；而较小的惯性权重则使粒子继承的原方向的速度较小，从而飞行范围更广，具有更好的全局开发能力。在例子群优化算法的原始版本中，并没有惯性权重，或者说其惯性权重始终为1。这样的例子群优化算法被称为基本粒子群优化算法，而带有惯性权重的粒子群优化算法则被称为标准粒子群优化算法。此外，人们还提出一种带收缩因子的粒子群优化算法。其实，基本粒子群优化算法和带收缩因子的粒子群优化算法均可视为标准粒子群优化算法的特例。惯性权重是粒子群优化算法中的重要参数，对算法的成败有重要影响。目前，设置惯性权重的常用方法包括固定权重、时变权重、模糊权重和随机权重。（1） 固定权重：赋予惯性权重以［0,