一种多蚁群伪并行优化算法

一种多蚁群伪并行优化算法

在大自然中实际寻找蚂蚁的行为的启发下，杜里格米在20世纪90年代初设计了第一种蚂蚁优化算法（as）。该算法是一种基于多主体的模拟进化全局搜索算法,它采用分布式控制,具有自组织性和正反馈性,优化过程不依赖于优化问题本身的严格数学性质,并且具有潜在的并行性。人们对蚁群算法的研究已经显示出该算法在求解复杂优化问题(特别是离散优化问题)方面的优越性。蚁群算法也存在一些不足,蚁群算法在构造解的过程中,随机选择策略使得算法的进化速度变慢,正反馈原理旨在强化性能较好的解,却容易出现停滞现象,从而以极大的概率引导蚁群走向局部最优解。1基本控制指导模型自然界中的蚁群具有自组织行为,在没有视觉的情况下,能够找出从食物源到蚁巢的最短路径。此外,蚁群还具有极强的环境适应能力,当原先最短的路径上出现障碍物时,能够再发现一条新的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“信息素(pheromone)”的物质进行间接通信、相互协作来发现最短路径。蚂蚁在运动过程中,不但能够在它所经过的路径上留下该物质,而且能够感知它的存在及强度,并朝着该物质强度高的方向移动,以此指导自己的运动方向。因为蚁群优化算法首先被应用于解决旅行商问题(travelingsalesmanproblem,TSP),所以基本蚁群优化算法模型一般使用TSP问题来进行描述,下面针对n个城市的TSP问题给出了基本蚁群的优化算法模型。蚂蚁从起始点开始按随机比例规则根据转移概率Pkij来选择将要移动到的城市。在t时刻,蚂蚁k在城市i选择城市j的转移概率为其中,allowedk={0,1,…,n-1}表示蚂蚁k下一步允许选择的城市;τij为边(i,j)上的信息素强度;ηij为边(i,j)的能见度;α为信息启发式因子,表示信息素对路径选择的重要性;β为期望启发式因子,表示启发信息对路径选择的重要性。经过n个时刻,蚂蚁完成一次循环,各路径上的信息素量根据下式进行调整:其中,ρ为信息素挥发因子;m为蚁群中蚂蚁的数目;Q为信息素强度,为常数;Lk为蚂蚁k在一次循环中走过的路径长度。2多昆虫群协同进化的算法不论是DorigoM提出的基本蚁群算法,还是大部分学者所提出的改进蚁群算法,都是基于单种蚁群、单种信息素的算法,主要模拟了实际蚁群信息系统的一部分。多蚁群伪并行优化算法的思想是将一个总的蚁群分成若干个子蚁群,不同的蚁群赋以不同的控制参数,对各蚁群分别进行相互独立的蚁群寻优,各蚁群在独立寻优过程中采用最大最小蚂蚁系统(max-minantcolony,MMAS)算法,并引入信息素平滑机制,以提高算法的全局寻优能力;各子蚁群在独立运行一定代数后,通过迁移算子联系,实现多蚁群的协同进化,最优解的获取是多个蚁群协同进化的综合结果。由于各蚁群采用不同的控制参数相对独立地执行寻优过程,具有不同的信息素分布模式,因此进化方向保持一定的差异,保证了搜索的充分性和收敛结果的全局最优性。迁移算子将各蚁群在寻优过程中出现的精英蚂蚁的寻优结果以信息素更新的形式,每隔一定的代数便引入到其他子蚁群,通过更新信息素矩阵,实现子蚁群之间的信息交换。此外,算法采取精英保留策略,保证每一进化代整个蚁群产生的最优结果不被破坏和丢失。整个寻优过程结束后,各子蚁群中的精英个体排序,得到待求解问题的最优规划方案及若干次优方案。因为此算法是在单机环境下模拟各子蚁群并行、协同寻优,所以把它称为“伪并行”。2.1局部最优解的变异蚁群算法是根据当前较好的路径更新路径信息素量,经过多次迭代后已有的最好路径上的信息素就会非常强,而较差的路径上的信息素就会很弱,这样蚂蚁就会集中在当前最好的路径上。随着计算步骤的增加,蚂蚁跳出现有最好路径的可能性会变小,这样算法就很容易早熟收敛到了局部最优解。针对此问题,文献给出了对最优个体进行变异的方法使算法跳出局部最优;文献设计了基于信息素的变异算子使算法跳出局部最优;文献提出了动态的调整信息素量的分配使算法跳出局部最优。本文通过引入信息素平滑机制,以达到使算法跳出局部最优的目的。当算法在寻优过程中某个子蚁群连续一定代数最优解没有变化时,则该子蚁群开始进行信息素平滑,信息素的平滑按下式进行:其中,τij为路径(i,j)上当前的信息素值;τmin为MMAS中各路径上的最小允许信息素值;δ为系数,用以控制信息素平滑作用的大小。当δ为0时,相当于关闭此操作;当δ为1时,各路径上信息素值置为最小。2.2多昆虫群伪并行优化算法人类文明的进步是一个优胜劣汰的过程,先进的文明征服和替代落后的文明。人类社会的优胜劣汰通过两种方式进行,一种是文化的交流和融合,另一种方式是战争和入侵。一般,在文明产生的早期,其发展比较快,等到一定时期后就会停滞不前,也就是内部优化已经无法前进,此时要么大量学习优秀文化得以生存,要么通过战争被新的文明替代。本文就是仿照这种社会进化过程设计了迁移算子。当多蚁群伪并行优化算法中的各子蚁群独立进化了一定代数后,各子蚁群中的精英蚂蚁的寻优结果以信息素更新的形式被迁移到其他子蚁群,精英蚂蚁所走过的路径在其他子蚁群中得到奖励,释放奖励信息素,其信息素的更新公式如下所示:其中,为子蚁群m中路径(i,j)上的信息素量(m≠n);Q0为奖励的信息素的总量;Ln为第n个子蚁群的精英蚂蚁所找到的最优路径的长度。多蚁群伪并行优化算法的具体算法步骤如下:步骤1指定各子蚁群的控制参数,指定开始进行精英蚂蚁迁移操作的子蚁群进化代数T,设置初始信息素,初始化各算法运行变量。步骤2各子蚁群按照MMAS算法开始独立寻优,在寻优过程中若子蚁群的最优解连续一定代数(算法参数中设置)没有进化,则进行信息素平滑,更新子蚁群信息素矩阵。步骤3若各子蚁群的最优解满足要求或算法运行代数大于参数设定值,则排列各子蚁群最优解并退出算法;否则执行步骤4。步骤4各子蚁群的精英蚂蚁在子蚁群间进行迁移操作,按照式(6)进行精英蚂蚁所走路径的信息素奖励,转向步骤2。3与其他昆虫群算法的研究比例本节在VC++6.0环境下用TSPLIB中的TSP算例来测试本文设计的算法,并与其他蚁群算法进行类比。沿用TSPLIB中的记法,算例中的数字表示城市的数目(如算例ch150的城市数目是150)。下面分别对算法参数的选取、算法的收敛性仿真和类比仿真进行说明。3.1仿真实验主要参数设计算法参数的选取了参考文献提出的“三步走”方法,具体步骤如下:(1)确定蚂蚁数目,按照(城市规模/蚂蚁数目)≈1.5的选择策略来确定蚂蚁的总数目;(2)参数粗调,调整取值范围较大的信息启发式因子α,期望启发式因子β,信息素强度Q等,以得到较理想的解。(3)参数微调,调整取值范围较小的信息素挥发因子ρ。通过“三步走”的方法最终确定的算法运行参数为:α=1.0,β=3.0,ρ=0.1。Q针对不同的问题取值不一样,对于后面仿真过程中用到的eil51和st70问题Q取125.0,ch150和a280问题Q取1000.0。对于本文设计的算法,各子蚁群在上面参数的基础上进行变动。仿真中还用到了MMAS算法,通过实验确定该算法的最大和最小约束信息素量为τmax=100.,τmin=0.01,其他参数同上。3.2实际最优解及其求解使用本文设计的多蚁群伪并行优化算法对TSPLIB中的eil51问题和st70问题进行仿真,检验算法的收敛性。算法设置5个子蚁群,每个子蚁群独立运行200代后进行精英蚂蚁迁移操作,如此反复6次(共计1200代),使用最优解绘制收敛图如图1、图2所示。eil51问题的实际最优解是426,st70问题的实际最优解是675。通过收敛过程图可以看到,算法在运行初期能够快速的收敛,在130代后趋于平稳,由于算法中的信息素平滑机制和子蚁群间精英蚂蚁的迁移操作,因此该算法仍然能够在解空间向接近最优解的方向继续搜索。最终,对eil51问题的仿真在第558代搜索到了最好解428.014236,对st70问题的仿真在第1069代搜索到了最好解676.507413。3.3算法仿真结果使用AS,MMAS和本文设计的多蚁群伪并行优化算法对TSPLIB中的eil51,ch150,a2803个问题进行类比仿真,其中AS算法使用蚁周模型。在使用AS算法和MMAS算法仿真时,每次运行1200代,共运行10次;在使用多蚁群伪并行优化算法仿真时,使用3个子蚁群,每个子蚁群独立寻优200代后进行精英迁移操作,如此反复6次(共计1200代),同样运行该算法10次。eil51问题的类比仿真结果(理论最优值为426),ch150问题的类比仿真结果(理论最优值为6528),a280问题的类比仿真结果(理论最优值为2579)见表1～表3。通过表1～表3的类比仿真结果可以看到