智能优化算法(蚁群算法和粒子群算法)

7.1蚁群优化算法概述•7.1.1起源•7.1.2应用领域•7.1.3研究背景•7.1.4研究现状•7.1.5应用现状7.1.1蚁群优化算法起源20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。背景：人工生命•“人工生命”是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容。•研究如何利用计算技术研究生物现象。•研究如何利用生物技术研究计算问题。•现在关注的是第二部分的内容，现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。•现在我们讨论另一种生物系统－社会系统。更确切的是，在由简单个体组成的群落与环境以及个体之间的互动行为，也可称做“群智能”(swarmintelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为（如鱼群和鸟群的运动规律），主要用于计算机视觉和计算机辅助设计。•在计算智能(computationalintelligence)领域有两种基于群智能的算法。蚁群算法(antcolonyoptimization)和粒子群算法(particleswarmoptimization)。前者是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上。•作为一种新兴演化计算技术,群智能已成为新的研究热点,它与人工生命,特别是进化策略和遗传算法有着极为特殊的联系,已完成的理论和应用研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法.••更为重要的是,群智能的潜在并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证.•因此无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。7.1.2蚁群优化算法应用领域这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。7.1.3蚁群优化算法研究背景群智能理论研究领域有两种主要的算法：蚁群算法(AntColonyOptimization,ACO)和粒子群算法（ParticleSwarmOptimization,PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。粒子群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的，主要表现在以下几个方面：•1无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性•2以非直接的信息交流方式确保了系统的扩展性•3并行分布式算法模型，可充分利用多处理器•4对问题定义的连续性无特殊要求•5算法实现简单群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。7.1.4蚁群优化算法研究现状最初提出的AS有三种版本：Ant-density、Ant-quantity和Ant-cycle。在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素。而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比，在不大于75城市的TSP中，这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时，AS的解题能力大幅度下降。因此，其后的ACO研究工作主要都集中于AS性能的改进方面。较早的一种改进方法是精英策略(ElitistStrategy)，其思想是在算法开始后即对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记为全局最优行程，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会。•这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞。为了进一步克服AS中暴露出的问题，提出了蚁群系统(AntColonySystem,ACS)。ACS与AS之间存在三方面的主要差异：首先，ACS采用了更为大胆的行为选择规则；其次，只增强属于全局最优解的路径上的信息素。其中，0ρ1是信息素挥发参数，是从寻路开始到当前为止全局最优的路径长度。再次，还引入了负反馈机制，每当一只蚂蚁由一个节点移动到另一个节点时，该路径上的信息素都按照如下公式被相应的消除一部分，从而实现一种信息素的局部调整，以减小已选择过的路径再次被选择的概率。随着群智能理论和应用算法研究的不断发展，研究者已尝试着将其用于各种工程优化问题，并取得了意想不到的收获。多种研究表明，群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。•蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络路由优化、数据挖掘以及一些经典的组合优化问题。7.2.1蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激素浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。7.2.2简化的蚂蚁寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。•信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。7.2.3一般蚁群算法的框架一般蚁群算法的框架有三个组成部分：蚁群的活动；信息素的挥发；信息素的增强；主要体现在前面的算法中步骤2和步骤3中的转移概率公式和信息素更新公式。•算法的步骤•(a)初始化信息素矩阵；•(b)将n只蚂蚁置于出发点；•(c)每只蚂蚁根据转换规则寻找下一节点，并保存起来，直到到达终点；•(d)计算性能指标；•(e)根据性能指标和信息素调整规则，对每一节点的信息素值进行调整；•(f)判断是否满足迭代条件，若不满足，返回(b)，直到满足条件；•(g)找出只蚂蚁中性能指标最优的解。粒子群优化算法(PSO)是一种进化计算技术(evolutionarycomputation)，有Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究，PSO同遗传算法类似，是一种基于叠代的优化工具。粒子群优化算法引言•系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)，而是粒子在解空间追随最优的粒子进行搜索。•同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。•目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。PSO算法介绍•PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。•那么让鸟找到食物的最优策略也就是最简单有效的方法是搜寻目前离食物最近的鸟的周围区域。•PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。•所有的例子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。•PSO初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。•第一个就是粒子本身所找到的最优解。这个解叫做个体极值，另一个极值是整个种群目前找到的最优解。这个极值是全局极值。•另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。pbestgbest•在找到这两个最优值时,粒子根据如下的公式来更新自己的速度和新的位置()()[][]1*()*[][]2*()*[][]vvcrandpbestpresentcrandgbestpresent=+−+−[][][]vpresentpresent+=[]v是粒子的速度，[]present是当前粒子的位置，[]pbest和[]gbest如前定义()rand是介于（0，1）之间的随机数。1c,2c是学习因子。通常1c=2c=2。•在每一维粒子的速度都会被限制在一个最大速度，如果某一维更新后的速度超过用户设定的，那么这一维的速度就被限定为。maxVmaxVmaxV遗传算法和PSO的比较大多数演化计算技术都是用同样的过程1.种群随机初始化2.对种群内的每一个个体计算适应值(fitnessvalue)。适应值与最优解的距离直接有关3.种群根据适应值进行复制4.如果终止条件满足的话，就停止