智能蚁群算法（共7篇）
智能蚁群算法 篇1
随着社会经济的不断进步, 汽车数量不断攀升, 交通问题已经成为制约我国社会发展的一个重要因素。智能交通系统 (Intelligent Transportation System, ITS) 就为我们解决现代社会交通需求与供给之间的矛盾提供了一个良好的途径。有利于缓解不断增长的机动车数量与缓慢的社会道路基础设施建设之间的矛盾。智能交通系统涵盖了多方面的交通因素, 选择最优路径就是其中重要的组成部分, 我们通常采用蚁群算法 (ACA) 来解决这个最优组合问题。
一、算法简介
M.Dorigo等人在对蚁群搜索食物的过程进行了探索之后, 于1991年提出了蚁群算法 (Ant Colony Algorithm, ACA) , 并将其应用于著名的旅行商问题 (TSP) 并获得了成功, 得到了人们的广泛关注。因其利用的是蚁群搜索食物的过程, 因此将这个算法取名为“人工蚁群算法”[1]。
蚁群算法利用的是对于种群进化行为的模拟, 具有随机性、全局化、多反馈、分布广的特点。作为一种模拟进化算法, 蚁群算法的原理就是在多个可行解组成的种群中进行进化, 最后得出最大概率的最优解。上述过程又可分为适应阶段和协作阶段两个阶段。在适应阶段, 针对各种信息可行解进行自身结构的调整;在协作阶段, 各个可行解通过交流而产生更优解。在一群可行解中, 蚁群搜索得到并记录其中的最优解。[2]此外, 蚂蚁在这一轮中的搜索信息将被保留到之后的各轮搜索中, 有利于其做出更好的选择。算法蚁群的这些特征使其有较强的自组织机制, 能够从无序的状态, 利用外力成为有序状态。[3]
二、蚁群算法在智能交通系统中的应用
我们的智能交通系统的最后效果应该满足以下几个方面:首先, 要降低交通的拥挤程度, 尽可能实现道路的畅通;其次, 在报道交通实况的基础上, 尽快解决交通事故;最后, 充分利用公共交通设施, 降低车辆尾气的排放。
随着智能时代的到来, 智能交通系统的实现有了较好的硬件基础, 当前实施的关键就是选择一个合适的算法。在交通拥挤的问题中牵涉到了物、人、信息等各方面因素, 交通优化很大程度上就是为了解决拥塞问题。[4]我们选择As—BTJ算法应用到智能交通系统中, 其中, 两地距离为权值, 人就像是蚂蚁, 要在最短时间内达到目的地, 在道路的权值和信息浓度的基础上找到最优的道路。但是这一过程还会受到许多其他因素的影响, 如多路径交通问题。我们的算法的目标是找到最短的路径, 但是在实际生活中, 还有许多因素是随着时间变化而变化的。人类作为出行者, 我们首先会选择最短路径, 但是当实际路况发生改变的时候, 我们会受到实践空间的限制而选择其他路径。因此, 仅仅考虑最短路径, 出行者很难在最短时间内达到目的地。当最短路径变成了最快路径, 提高各条路径的利用率, 合理配置交通流量, 有利于大大缓解当前的交通拥挤问题。
(一) 信息元素的选择
通过对道路上的车辆数量进行统计, 为了解决道路拥挤的问题, 我们可以得到最理想的状态是道路上车辆数量为0, 最不理想的状态是道路上车辆数量为无限大。
(二) 新信息元素的更新
在算法的初期阶段, 蚂蚁运动过程中留下的痕迹就是我们要的信息元素, 这些痕迹能够指引蚂蚁回巢, 因此更多的蚂蚁选择了这一路径, 信息元素的浓度不断上升。因此, 我们要选择的最优路径就是这个信息元素浓度最大的那个路线。我们不能够一会的追求最大的信息元素的浓度, 因此要为其设置一定阂值, 若是信息浓度超过这个值, 也就是说这条道路超过了他的最大利用率, 若浓度继续增加, 就会造成交通的拥堵, 也就是说要重新换一条路径。通过这种手段, 就会使超过阂值的那条路线的信息元素浓度逐渐降低, 最终小于阀值, 那么这条路线又成为了可行路线之一, 再通过一系列的算法进行最优路线的选择。
参考文献
[1]吴庆洪, 张纪会, 徐心和.具有变异特征的蚁群算法[J].计算机研究与发展, 2013, 36 (10) :1240-1245.
[2]侯云鹤, 鲁丽娟, 熊信艮等.广义蚁群与微粒群结合算法在电力系统经济负荷分配中的应用[J].电网技术, 2014, 28 (21) :34-38.
[3]段海滨, 王道波.一种快速全局优化的改进蚁群算法及仿真[J].信息与控制, 2014, 33 (02) :241-244.
[4]刘力军, 马红霞.混沌理论在交通领域中的应用前景初探[J].江西师范大学学报 (自然科学版) , 2013, 30 (04) :346-349.
智能蚁群算法 篇2
基于蚁群算法的配电网在进行线路搜索时, 需要考虑多方面的因素。首先要考虑的就是要确定搜索线路上的权值 (权值是确定线路上最短路径的值) , 权值包括网络接线方式、无功消耗、线路长度、线路重要性 (是否急需供电的重要性, 例如医院最优) 。网络的接线方式不仅要考虑投资额和投资时间安排, 还要考虑每年所需的连续消耗的费用 (如系统运行的线损费用和维护费用) 等[1]。目前该算法已成功应用于密山生物质发电小型配网中, 实现了最优配电, 改变了传统配电的利用率、效率低的问题。
1 蚁群算法的配电网规划方法
用优化算法来求解配电网电力分配问题, 实质上是在问题空间进行某种搜索。不同的是, 在各种方法中, 问题解的表示形式 (即问题解的编码) 不同, 以及算法所采用的搜索策略不同。一个好的编码能缩小问题解空间, 使算法在一个较小的空间里进行搜索, 从而提高算法的效率[2]。另一方面, 好的搜索策略, 能控制算法有效地朝着最优解方向搜索。搜索策略主要包括两部分:①控制策略。控制策略实质上是一个概率形式的函数, 它依据当前搜索状况, 以某种概率机制产生搜索方向。②评估函数。算法每进行一次搜索, 都要对搜索结果进行评价, 以此来影响下次循环的搜索方向。
2 蚁群算法搜索的数学模型
2.1 蚁群算法的控制策略
蚁群优化算法主要是由转移规则和信息素更新规则组成, 在这里以求解典型的配电网为背景, 来说明蚁群算法的搜索原理。假设有N个变电站, 配电网问题的目标是寻找一条路径最短的、最优的路线, 电流从电厂出发经过所有变电站并回到原出发变电站, 除出发变电站外每个变电站只允许经过一次, 配电网问题的可行解即为除出发变电站外所有变电站的一个无重复序列。
假设将m只蚂蚁放入到给定的n个变电站中, dij (i, j=1, 2, …, n) 表示变电站i到变电站j之间的距离;bi (t) 表示t时刻位于变电站i的蚂蚁个数;
式中, allowedk={0, 1, …, n-1}。tabuk表示蚂蚁k下一步允许选择的变电站。这一点与真实蚂蚁系统不同, 人工蚁群系统具有记忆的功能tabuk (k=1, 2, …, m) 用来记忆蚂蚁k已经走过的变电站。为了避免过早收敛到局部最优解, 对信息素采取挥发机制, ρ为信息素残留系数, 1-ρ则为信息素挥发系数, 经过n个时刻, 蚂蚁完成一次循环, 各条线路上的信息素按照式 (2) 进行调整。
τij (t+m) =ρ×τij (t) +Δτij (2)
式中, Δτ
Δτ
, 若蚂蚁k在此次循环中经过ij (4)
式中, Q表示常数;Lk表示蚂蚁k在本次循环中所经过的路径长度, 在初始时刻, Δτij=0;α, β蚂蚁在运动过程中积累的信息在蚂蚁选择的路径中所起的不同作用;p
2.2 评价蚂蚁的搜索游程
蚁群算法的搜索游程的评价, 实际上是以概率的形式给出的, 算法在选择搜索方向时, 较大的可能朝着已发现的较好解域, 同时, 对其它方向也可能选取[4]。由此, 算法不易陷入局部最优。蚂蚁k在t时刻从集合E
式中, ηj表示从集合E
当m只蚂蚁都完成如图1所示过程后, 记录本次循环m次游程中的最优方案。同时对各边上的信息素量根据下式进行修正:
式中, 0<ρ<1, 参数ρ反映了对以前搜寻结果的遗忘程度, 因为随着时间的推移, 以前留下的信息逐渐消失, 1-ρ就是信息素的消失程度。Δτ
当上述过程完成后, 则蚂蚁完成了一次循环。重复执行这些过程, 当n<Nmax且无退化行为。Nmax为预先设定的最大循环次数。
3 算法评价
在程序搜索中得出如下结论, 如图2所示, 蚁群算法在迭代150次之前, 由于信息素的密度积累较少算法的正反馈机制没有充分发挥, 过程最优解的个数基本没有减少;迭代次数150和200之间时, 状况有了较大改善, 具体表现为过程最优解的个数值下降迅速;迭代次数200和400之间时, 过程最优解的个数下降平缓, 趋于最优解;迭代次数超过400次后, 过程最优解的个数基本不再变化, 算法停顿与最优解, 最终最优解和次优解的个数停留在20个左右。
4 结束语
本文主要是对蚁群算法在配电网中搜索最优路径的方法进行深入的分析, 通过蚂蚁游程释放信息素来找到最优路径, 同时, 当蚂蚁走过的游程比较少时则信息素会自动释放。通过n次遍历来确定最优配电网路径。但是蚁群算法的易早熟和停滞现象, 还有待于进一步改进, 这可以通过与其它算法混合来加以改善。
摘要：深入介绍了蚁群算法在配电网的数学模型的建立, 在搜索算法中首先确定的是权值, 在配电网中权值是由无功消耗、线路重要性、线路长度和线路成本来确定的。通过权值分析了蚂蚁从原点到终点的搜索模型, 蚂蚁在游程中会释放信息素, 权值大的说明支路最短, 蚂蚁释放的信息素也会增多, 最后通过蚂蚁在反复游程中释放信息素的多少会寻找到最优解或者次优解的最优路径。把蚁群算法应用在配电网中能够有效的搜索出最优解或次优解, 大量的减少了最优解的搜索时间。
关键词：配电网,蚁群算法,信息素
参考文献
[1]张学松, 陈竟成.配电网络潮流算法比较研究[J].电网技术, 2007, 22 (4) :45-49.
[2]Liang Y C, Smith A E.An ant colony optimization al-gorithm for theredundancy allocation problem (RAP) [J].IEEE Trans on Reliabi-lity, 2004, 53 (3) :417-423.
[3]张纪会, 徐心和.一种新的进化算法——蚁群算法[J].系统工程理论与实践, 1999 (3) :84-87.
智能蚁群算法 篇3
在算法选择过程中,如果仅采用简单的循环遍历各个元素以避免冲突的方法,排课效率低下;简单的随机散列方法,又难以有效控制找到合理方案。并且二者通常情况下得到课表的适应度都非常低。可能产生:一位老师或一个班级一天内连续上课,之后一天又没有课;同一门课程一天内持续上,以后几天又没有这门课程;采用遗传算法,理论上能够得到较为合理地排课方案,也存在因为过早收敛得不到解决方案或者得不到最优方案的情况。为了解决这些问题,将蚁群算法与遗传算法相结合使用,可以有效地减少搜索空间,并能够得到比较满意的结果。
1 高校排课问题的描述
Carter和Laporte提出:高校排课问题是一个多元分配问题,它研究的就是如何把学生和老师分配给课程,课程单元或者班级,如何把事件(上课事件)分配给教室和时间[1]。从上述定义来看,高校排课问题研究的就是如何把一系列的课程分配给有限的教室和一周内有限的上课时间单元,以及如何把学生和老师分配给课程。
1.1 排课问题所涉及的元素
课程的编排不仅涉及参与课程的主体学生和教师,时间和教室也是在课程编排过程中的重要因素。所以排课问题所设计的元素主要有以下5种(排课问题概念模型见图1):
班级集:R={r1,r2,r3,…,rn};教师集:T={t1,t2,…,tn};教室集:S={s1,s2,…,sn};课程集:C={c1,c2,…,cn};时间集:M={m1,m2,…,mn}
它们组成一个授课任务集合D={r,t,s,c,m},r∈R,t∈T ,s∈S,c∈C,m∈M。
1.2 排课过程中所要遵循的约束条件
一个可用的课表,应当完全遵循以下的基本约束:
(1) 班级约束:一个班级在一个时间内最多只能有一门课程;
(2) 教师约束:一位教师在一个时间内最多只能有一门课程;
(3) 教室约束:一个教室在一个时间内最多只能有一门课程。
另外除了以上的基本约束条件外,一个完美的课程表还应该考虑以下的“人性化”约束条件:
(1) 班级的每周上课时间分布均匀;
(2) 教师的每周授课时间分布均匀;
(3) 同一班级相邻时间段的上课地点不能相距太远;
(4) 同一教师相邻时间段的上课地点不能相距太远。
2 应用蚁群遗传算法解决排课问题
2.1 遗传算法
遗传算法(genetic algorithm,GA)是近几年发展起来的一种崭新的全局优化算法。1962年霍兰德(Holland)教授首次提出了GA算法的思想,它借用了仿真生物遗传学和自然选择机理,通过自然选择、遗传、变异等作用机制,提高各个个体的适应性[2]。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。
这一点体现了自然界中“物竞天择、适者生存”进化过程[3]。与自然界相似,遗传算法对求解问题的本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体,并基于适应值来选择染色体,使适应性好的染色体有更多的繁殖机会。并且在执行遗传算法之前,给出一群染色体,也即是假设解。然后把这些假设解置于问题的“环境”中,也即一个适应度函数中来评价。并按适者生存的原则,从中选择出较适应环境的染色体进行复制,淘汰低适应度的个体,再通过交叉,变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化,直到最适合环境的值。
遗传算法的运行过程是典型的迭代过程,其必须完成的工作内容和基本参数步骤如图2所示。
(1) 选择编码策略,把参数集合和数域转换为位串结构空间;
(2) 定义适应值函数;
(3) 确定遗传策略,包含选择群体大小,选择、交叉、变异方法,以及确定交叉概率pe变异概率pm等遗传参数;
(4) 随机初始化生成群体;
(5) 计算群体中个体位串解码后的适应值;
(6) 按照遗传策略,运用选择、交叉和变异算子作用于群体,形成下一代群体。
2.2 蚁群算法
蚁群算法是模拟真实蚁群觅食过程寻求最短路经的原理,由意大利学者M Dorigo等人首先提出的[4]。最初的蚁群算法称为蚂蚁系统(ant system),对于解决旅行商问题(TSP)及二次分配问题取得了较好的效果。经过改进后称为蚁群算法。
自然界中的蚂蚁是以外激素(pheromone)为媒进行信息传递的,从而蚂蚁个体能相互协作,完复杂的任务。蚁群的行为表现出一种信息正反馈现象:某一路径上经过的蚂蚁越多,则后到者选择该路径的概率就越大[5]。
2.3 蚁群遗传算法
遗传算法、蚁群算法作为2大仿生优化算法,有其各自的优点和不足。
遗传算法具有大范围快速全局搜索能力,但对系统中的反馈信息利用不够,当求解到一定范围时往往做大量无用的冗余迭代,求精确解效率低。蚁群算法原理是一种正反馈机制,但初期信息素匮乏,求解速度慢。
将遗传算法与蚁群算法的融合[6],采用遗传算法生成信息素分布,利用蚁群算法求精确解,优势互补,期望获得优化性能和时间性能的双赢。将遗传算法与蚁群算法的混合来解决排课问题,不仅采用遗传算法生成初始信息素分布,在蚁群算法寻优中,采用交叉和变异的策略,改善解的质量。
解决排课问题的蚁群遗传算法如下:
(1) 初始化群体,利用遗传算法随机产生排课问题的一个解;矩阵A表示一个染色体,每个染色体就是一个排课方案。
undefined
(2) 计算排课问题随机解上每个个体的适应度值。
(3) 引入蚁群算法的思想,将解矩阵等分成若干空间,在各个空间“喷洒”信息素[7]。建立适应度与信息素的相应关系,使得适应度强的染色体,在所属区间内留下较强的信息素;信息素强的区间内,染色体所选取的概率较大[8]。
(4) 采用适应度排序方法,选择将进入下一代的个体。
(5) 分别按照概率Pc对下代个体进行交叉操作,按照概率Pm对下代个体进行变异操作。
(6) 判断新的染色体是否满足满足排课问题约束条件,是则结束迭代,否则进入步骤(2)。
(7) 解得排课问题的较优解。
2.4 效果评估
分别在任务数为100,500,1000时利用仿真技术对循环遍历算法、遗传算法、蚁群遗传算法所应用的时间和适应度进行模拟实验。其中设定条件:
(1) 循环遍历算法以得到可行解为结束条件;
(2) 遗传算法和蚁群遗传算法需要完成150次循环迭代;
(3) 教室为无差别教室。
得到运行时间结果如表1所示。
得到适应度结果比较如表2所示。
3 结 语
在求解过程中的选择交叉步骤中,普通的遗传算法直接从上一代中选取2个染色体进行交叉,这样可能因为局部收敛而得不到较优解。在此引入了蚁群算法的思想,将信息素的浓度关联到个体适应度,在选取下一代个体操作中,能够更全面地选取适应度高的个体进行交叉变异操作,达到全局选取,更快地选取最优个体,改善了解得质量。另外在考虑教室之间的容量大小,电教室与普通教室之间的差别上,还需要做更加深入的研究。
参考文献
[1]CARTER M W,LAPORTE G.Recent developments inpractical course ti metabling[M]//BURKE E K,CARTERW.The Practice and Theory of Automated Ti metabling.Berlin:Springer-Verlag,1997:3-19.
[2][日]玄光南.遗传算法与工程设计[M].程润伟,江定伟,译.北京:科学出版社,2000.
[3]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.
[4]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001.
[5]徐宁,李春光,张健.几种现代优化算法的比较研究[J].系统工程与电子技术,2002(12):100-103.
[6]刘秋红,寒枫,张任.基于分层的自适应遗传算法在UTP中的应用研究[J].贵州大学学报:自然科学版,2007,2(24):154-157.
[7]余样宣,崔国华,邹海明.计算机算法基础[M].2版.武汉:华中科技大学出版社,2000.
[8]丁建立,陈增强,袁著扯.遗传算法与蚂蚁算法的融合[J].计算机研究与发展,2003,40(9):1351-1356.
[9]杨为民.使用遗传算法编排课程表的研究与应用[D].合肥:安徽大学,2003.
蚁群算法概述 篇4
1、蚁群算法的基本原理
在自然界真实的蚁群觅食过程中, 蚁群在没有视觉的情况下通过个体之间交换信息素, 能够在较短的时间内找到食物和蚁巢之间的最短路径。生物学家的研究已经表明, 一只蚂蚁的记忆和智能是非常有限的, 但是, 由于蚂蚁之间可以通过一些信息素进行协同作用, 实现蚂蚁之间的信息交流和传递, 可以共同做出令人惊讶的行为。
为了阐述蚁群算法的机理[2], 下面以蚂蚁搜索食物的过程为例, 分析蚂蚁是如何通过上述的信息交流和传递的协同作用, 最终找到从蚁穴到食物源的最短路径的。
图1.1中, A为蚁穴, E为食物源, 从A到E有两条路径可走, ABE是长路径, ACE是短路径。蚂蚁走过一条线路以后, 在其路径上会留下信息素气味, 后来的蚂蚁就是根据留在各路径上的这种气味的强度选择应该移动的方向。图1.1 (a) 表示起始时的情况, 假定蚁穴中有4只蚂蚁, 分别用1, 2, 3, 4表示。开始时蚁穴中蚂蚁1, 2向食物源E移动, 由于线路ABE和ACE均没有蚂蚁通过, 在这两条路径上都没有原始的信息素气味, 因此蚂蚁1和2选择这两条线路的机会均等。假设蚂蚁1选择ABE线路, 蚂蚁2选择ACE线路, 并且假定各个蚂蚁行走的速度相同, 当蚂蚁2到达食物源E时, 蚂蚁1还在途中, 如图1.1 (b) 所示。蚂蚁2到达食物源以后就返回, 这时从B点返回也有两条线路的选择, 而哪一条线路上的信息素气味重, 就选择哪一条。因为蚂蚁1还在途中, 没有到达终点, 即此时在EBA线路上靠近B端处, 蚂蚁1还没有留下信息素气味, 所以蚂蚁2返回蚁穴的路径只有一个选择, 就是由原路返回。当蚂蚁2返回到A端时, 蚂蚁3开始出发, 蚂蚁3的线路选择将必定是ACE, 因这时ACE线路上信息素的气味比ABE线路上重 (ACE路径上已有蚂蚁两次通过) , 如图1.1 (c) 所示。当蚂蚁1到达食物源B点时, 由于同样的理由, 蚂蚁1所选择的返回线路必将是ECA, 如图1.1 (d) 所示。如此继续下去, 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:沿路径ACE移动的蚂蚁越多, 则后来者选择该路径的概率就越大, 这正是蚁穴到食物源的最短路径。蚂蚁个体之间就是通过这种信息的交流达到最佳食物搜索的目的[3]。
在自然界中, 蚁群的这种寻找路径的过程表现为正反馈的过程, 与人工蚁群的寻优算法极为一致。如果我们将在优化求解中那些只具备简单功能的单元看作"蚂蚁", 那么上述寻找路径的过程可以用于解释人工蚂蚁的寻优过程。[4]
由以上分析可知, 人工蚁群和自然界蚁群的相似之处在于:两者优先选择的都是含"信息素"浓度较大的路径;人工蚁群和自然界蚁群的区别在于:
(1) 人工蚂蚁具有记忆或智能功能, 它能够记忆已经访问过的节点。
(2) 人工蚂蚁具有一定的视觉, 人工蚁群在选择下一条路径的时候, 并不是完全盲目的, 而是按一定的算法规律有意识得寻找最短路径。
(3) 人工蚂蚁的生活环境是时域离散的。
2、蚁群算法的特点
从蚁群算法的原理不难看出, 蚁群的觅食行为实际上是一种分布式的协同优化机制。单只蚂蚁虽然能够找到从蚁巢到食物源的一条路径, 但找到最短路径的可能性极小, 只有当多只蚂蚁组成蚁群时, 其集体行为才表现出蚂蚁的智能 (发现最短路径的能力) 。在寻找最短路径的过程中, 蚁群使用了一种间接的通信方式, 即通过向所经过的路径上释放一定量的外激素, 其它蚂蚁通过感知这种物质的强弱来选择下一条要走的路。
在蚁群的觅食行为中, 另一个重要的方面是自催化机制和解的隐式评估。自催化机制实际上是一种正反馈机制, 解的隐式评估指蚁群将先走完较短的路径。自催化机制和解的隐式评估相结合, 极大地提高了问题的求解效率。即对于越短的路径, 蚂蚁将越早走完, 从而使更多的蚂蚁将会选择该路径。当然在使用自催化机制时, 要努力避免早熟现象。在蚁群算法中, 使用外激素蒸发和随机状态转移来弥补自催化机制的缺陷。蚁群算法的主要特点概括如下:
(1) 采用分布式控制, 不存在中心控制。
(2) 每个个体只能感知局部的信息, 不能直接使用全局信息。
(3) 个体可改变环境, 并通过环境来进行间接通讯。
(4) 具有自组织性, 即群体的复杂行为是通过个体的交互过程中突现出来的。
(5) 是一类概率型的全局搜索方法, 这种非确定性使算法能够有更多的机会求得全局最优解。
(6) 其优化过程不依赖于优化问题本身的严格数学性质, 诸如连续性、可导性, 及目标函数和约束函数的精确数学描述。
(7) 是一类基于多主体的智能算法, 各主体间通过相互协作来更好的适应环境。
(8) 具有潜在的并行性, 其搜索过程不是从一点出发, 而是同时从多个点同时进行。这种分布式多智能体的协作过程是异步并发进行的, 分布并行模式将大大提高整个算法的运行效率和快速反应能力。
3、蚁群算法的应用
对蚁群算法的应用研究一直非常活跃。由于蚁群算法不依赖于问题的具体领域, 所以在很多学科有广泛的应用。
(l) 组合优化
继M.Dorigo首先将蚁群算法应用于TSP问题之后, V Maniezzo[5]等人将蚁群算法应用于QAP。最近几年, Gambardella[6], Taillard[7]和Stutzle[8]也发表了一些用蚁群算法求解QAP问题的文章。目前, ACO己是求解QAP问题最有效的算法之一。A Colomi[9]等人首先将蚁群算法应用于车间作业调度问题 (Jobshop Scheduling Problem, 简称JSP) 。Costa和Herz[10]提出增强的蚁群算法, 并将其应用于分配类型的问题。该算法在求解图的作色问题时, 得到了完全可以和其它启发式算法相媲美的结果。
(2) 通讯领域
蚁群算法在通讯网络领域 (特别是解决网络路由问题) 方面的应用研究受到越来越多学者的关注。由于网络中信息的分布式性、动态性、随机性和异步性与蚁群算法一非常相似, 如利用局部信息发现解, 间接的通讯方式和随机状态的转换。Di Caro和Dorigo己在相关的文献中将蚁群算法应用于网络路由问题, 并称这种算法为Ant Net[11]。
(3) 大规模集成电路的线网布局
在大规模集成电路的线网布局中, 需要根据电路和工艺的要求完成芯片上单元或功能模块的布局, 然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent根据启发策略, 像蚂蚁一样在开关盒网格上爬行, 所经之处便设置一条金属线, 历经一个线网的所有引脚之后, 线网便布通了[12]。应用蚁群算法, 可以找到成本最低、最合理的线网布局, 而且由于其本身的并行性, 比较适合于解决此类问题。
(4) 函数优化
虽然蚁群算法在离散空间的寻优能力十分突出, 但是对于连续空间的优化也是蚁群算法应用的领域之一, 也是评价蚁群算法性能的主要方法[13,14]。
此外, 蚁群算法在计算机领域、机器人设计与控制领域、数据挖掘、系统辨识、化工领域等方面也有广泛应用。特别需要指出的是:由于蚁群算法在求解复杂组合优化问题方面具有并行化、正反馈、鲁棒性强等先天优越性, 所以在解决一些组合优化问题时所取得的结果无论是在解的质量上, 还是在收敛速度上都要优于或至少等效于模拟退火以及其它一些启发式算法[2]。
摘要：本世纪50年代中期创立了仿生学, 人们从生物进化的机理中受到启发, 提出了许多用于解决复杂优化问题的新方法, 如遗传算法、蚁群算法、进化规划、进化策略等。研究成果已经显示出这些算法在求解复杂优化问题 (特别是离散优化问题) 方面的具有很强的优越性。本文将对蚁群算法做详细的介绍。
蚁群算法参数分析 篇5
蚁群算法是受生物进化论的影响产生的,20世纪90年代初,意大利学者M Dorigo等人提出了最基本的蚁群算法(Ant Colony Algorithm,ACA),他们受到真实世界的蚁群的行为的影响,在观察蚁群集体觅食的过程中,发现蚁群寻找食物的特征,能迅速有效地找到食物,和我们所研究的寻优类问题极其相似,有助于对这类问题的求解。通过研究蚁群觅食得出的蚁群算法虽然能有效地找到问题的最优解和它比较强的鲁棒性,但是还存在着很多不足,比如收敛速度较慢、容易出现停滞等现象,基于上述问题,不少学者提出了改进的蚁群算法。由于算法当中涉及到多类参数,这些参数的数值对该算法的影响非常之大,一直得不到最佳的参数组合,这个问题困扰了不少学者,现对蚁群算法中所涉及的各个参数进行分析,以探寻解决旅行商问题的最优参数组,找到最佳的参数组合,使算法运行效率更高[1]。
1 旅行商问题
旅行商问题(Traveling Saleman Problem,TSP)一般译为旅行推销员问题、又称为货郎担问题,简称为TSP问题,是基本的线路问题,该问题是指某旅行者由起点出行,通过所有给定的城市,最后回到起点的最短路径。该问题的最早数学规划是由Dantzig(1959)等人所提出。在指定的n个城市之中,确定一条经过每个城市并且只有一次的最短路径。其图论描述为:给定一个图G=(V,A),其中V是所有城市的点集合,A为各个点之间相互连接构成的边的集合,已经知道每个点之间边的距离,要求确定一条路径最短的哈密顿回路,即遍历所有的点当且仅当一次的最短的路径。
2 蚁群算法的基本原理
通过模拟自然界中的蚁群所得到的蚁群算法主要思想来源于对现实世界蚂蚁在搜索食物的过程之中发现食物的合理路径的行为,表现出了较强的寻找最优路径的能力。在整个觅食的过程之中,蚂蚁之间互相散播信息素,相互交换所走过路径的信息,它们有着对信息素的敏感反映,感知到信息素的多少,来决定所要选择的路径。分析蚁群算法,以常见的旅行商问题为例,算法设计的主要步骤有如下[2]。
以n和m分别表示城市的数量和蚂蚁的数量,城市i和城市j间的直线路径我们用dij(i,j=1,2,…,n)表示,计算结果由欧式距离得出,t时刻,e(i,j)边上的信息素的量们用τij(t)表示。
1)初始化,每条路径上的信息素量设置成一样,设τij(0)=W(W为常数),在蚂蚁k(k=1,2,…,m)运动时,根据如下概率公式决定选择的路径。
式(1)中有:α表示运动轨迹相对重要程度,反应了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用,其值越大,则该蚂蚁越倾向于选择其他蚂蚁经过的路径,β作为期望启发因子,表示路径可见程度的相对重要程度,其值越大,则该状态转移概率越接近于贪心规则,也就是说,越倾向于往能见度程度高的路径上行走;ηij则表示路径边e(i,j)的能见度程度;所求的概率(t)表示为在t时刻蚂蚁k由位置i转移到位置j的概率数,tabuk(k=1,2,…,m)表示蚂蚁k已经走过城市的集合,allowedk={1,…,n-tabuk}表示不在tabuk中的那些城市的集合,也就是允许下一步继续寻找的城市集合。
2)蚂蚁在运动中,当完成一次周游即到达所有城市之后,每条路径上的信息量按照以下的更新公式进行更新[3]。
式(2)中有:ρ的范围在0到1之间,它用来表示信息素τij(t)随时间而减少的量的程度,Δτij表示在循环之中路径e(i,j)上的信息变化量。
Δτkij(t)表示蚂蚁k在这次循环之中城市i和城市j路径之间留下的信息变化量。
式(4)中有Lk为蚂蚁k在这次循环之中所走路径总长;Q是常数,表示的是每只蚂蚁周游一次后所留下信息量。
陈一昭,等:蚁群算法参数分析
3)依次循环以上各步骤,循环次数达到算法给定最高次数后停止,得到最优解。
3 蚁群算法中的主要参数介绍
通过上面对蚁群算法的介绍,在整个算法的实现过程之中,有不少重要参数需要设定其初值,参数初值的设定对算法的性能影响很大,如何选取这些参数的数值,为提高算法性能有很大帮助,不仅可以提高算法的收敛能力,而且有利于寻找最优值。
首先介绍一些主要参数对算法的影响,需要分析的主要参数有α、β、m、Q、ρ[4]。
3.1 α对算法的影响
α是启发因子中的一个,它表现的是蚂蚁在搜索路径的运动过程之中对所积累的信息量指导蚁群搜索当中的相对重要度,α值越大,蚂蚁选择之前走过的路径可能性就越大,搜索路径的随机性自然就减弱,α越小,蚁群搜索范围就会减少,陷入了局部最优。
3.2 β对算法的影响
β是指的期望启发因子,它反映的是启发式信息在影响蚁群搜索的过程当中的相对重要度,它的大小影响着蚁群在整个寻优的过程中的先验性和确定性。β值越大,蚁群就越容易选择局部较短路径,这时算法的收敛速度是加快了,但是随机性却不高,容易得到局部的相对最优。
3.3 m对算法的影响
m是指的蚁群数量,蚁群数目在表面上来看,数目越多,得到的最优解就越精确,但是会产生不少重复解,随着算法接近最优值的收敛,继续循环只能是越来越接近最优解,信息正反馈作用降低,大量的重复工作,消耗了资源,增加了时间复杂度,所以一定要找到合适的蚁群数量。
3.4 Q对算法的影响
Q所指的是信息强度,信息强度表示的是蚂蚁所释放的信息量大小,蚂蚁在循环一次之后在所经过的路径上面所留下的信息素总量,这些信息量影响到算法的正反馈功能,让算法在正反馈作用下,能够有效的找到问题的最优解。
3.5 ρ对算法的影响
信息素挥发因子用ρ表示,则1-ρ表示所留下的信息素。ρ对蚁群算法的搜索能力和收敛速度的有影响。所以对ρ值的选择需要相当的谨慎,ρ过小时,在各路径上残留的信息素过多,导致无效的路径继续被搜索,影响到算法的收敛速率;ρ过大时,无效的路径虽然可以被排除搜索,但是不能保证有效的路径也会被放弃搜索,影响到最优值的搜索,使得收敛速率降低,并且影响到算法的全局搜索的能力[5]。
4 蚁群算法的实现步骤及程序结构流程
4.1 蚁群算法实现步骤
根据以下的基本蚁群算法,通过对算法中的各个主要参数进行分析调试,以求寻找到算法中各主要参数的最佳配置,算法具体实现如下。
1)参数初始化过程,时间t循环次数NC为0,且设置最大循环次数NCmax,将m个蚂蚁置于n个顶点上,n是城市的个数,蚂蚁禁忌表中索引号tabuk为1,初始时有向图上每边(i,j)的初始化信息量τij(t)为常数W,初始时刻Δτij(t)=0。
2)蚂蚁个体根据概率转移公式(1),得到概率,根据概率大小选择下一个城市j,寻找到了下一个城市j,此时j∈{C-tabuk}。
3)选择好下一个城市j之后,将蚂蚁移动到下一个城市j,并把j移动到蚂蚁个体的禁忌表中,ta-buk=tabuk+1。
4)在整个城市集合Z中元素未完全遍历完,则继续执行第2步,若已全部遍历,则执行第5步。
5)根据路径上信息量更新公式式(2)和信息量变化公式式(3)更新每条路径e(i,j)上信息量。
6)循环次数NC←NC+1。
7)根据结束条件,如果循环次数NC≥NCmax,则循环结束,输出程序计算的最佳结果,否则对禁忌表进行清空,跳转到第2步。
4.2 蚁群算法程序结构流程
5 各个参数对蚁群算法性能的影响
为对蚁群算法参数进行优化,首先利用仿真实验讨论分析参数值的选择对算法运行结果的影响,并据此确定参数的初始合理范围。由于算法中的参数选择尚无严格的理论依据,至今还没确定最优参数的数学解析方法,对于算法中的参数α、β、m、Q、ρ等主要是基于统计方法进行实验确定其取值范围。首先通过大量实验得到合理的参数值,然后分别讨论蚁群算法最优解与各个参数值之间的关系。试验中所用到的TSP数据都来源于TSBLIB中的Oliver30TSP,坐标如表1所示。根据实验将蚁群算法参数设置为如表2所示。
根据表2中设置的参数数值,通过单机实验,改变其中一种参数的数值,寻找该参数的最佳数值范围,以保证算法求得最短路径的稳定性,即平均路径,经过大量实验,统计实验结果,对实验结果数据求平均,得到平均路径值,如表3所示。
5.1 对启发因子α的分析
由表3可知,启发因子α的数值的改变,所求得平均路径值随之变化,它表现的是蚂蚁在搜索路径的运动过程之中对所积累的信息量指导蚁群搜索当中的相对重要度,对算法的随机性有影响,并且可以导致算法过早陷入局部的最优。从表3中α与平均路径之间的关系,可以看出当α等于0.8的时候,所求得的平均路径值最佳,进一步分析得到表4,α∈[0.7,1.1]之间时,可以保证算法求得最佳数值的稳定性。
5.2 对期望启发因子β的分析
由表3可知:期望启发因子β的数值的改变,所求得的平均路径随之变化,它表现的是启发式信息在指导蚁群搜索过程之中相对重要的程度,它的大小影响着蚁群在整个寻优的过程中的先验性和确定性。从表3中β与平均路径之间的关系,当β等于3.8的时候,所求平均路径值最佳,进一步分析得到表5,β∈[3.8,4.5]之间时,对算法的求解性能最好。
5.3 对蚁群数目m的分析
m是指的蚁群数量,蚁群数目在表面上来看,数目越多,得到的最优解就越精确,但是会产生不少重复解,随着算法接近最优值的收敛,继续循环只能是越来越接近最优解,信息正反馈作用降低,大量的重复工作,消耗了资源,增加了时间复杂度。从表3中m与平均路径之间的关系,当m等于60时,所求平均路径值最佳,进一步分析得到表6,当蚁群数目m等于58时,能够得到全局最优解,虽然蚁群数目增加也能得到最优解,但是增加了算法的运行时间,并且对算法的改进也起不到作用。
5.4 对信息强度Q的分析
信息强度Q表示的是蚂蚁所释放的信息量大小,蚂蚁在循环一次之后在所经过的路径上面所留下的信息素总量,这些信息量影响到算法的正反馈功能,让算法在正反馈作用下,能够有效地找到问题的最优解。从表3中Q与平均路径之间的关系,当Q等于400、500、600这些数值的时候,所求平均路径值最佳,进一步分析得到表7,当Q∈[400,950]时,能够得到全局最优解,若Q大于950,算法的求解性能会随之变差。
5.5 对信息素挥发因子ρ的分析
ρ对蚁群算法的搜索能力和收敛速度有影响。所以对ρ值的选择需要相当地谨慎,ρ过小时,在各路径上残留的信息素过多,导致无效的路径继续被搜索,影响到算法的收敛速率;ρ过大时,无效的路径虽然可以被排除搜索,但是不能保证有效的路径也会被放弃搜索,影响到最优值的搜索,使得收敛速率降低,并且影响到算法的全局搜索的能力。从表3中ρ与平均路径之间的关系,当ρ等于0.75时,所求平均路径值最佳,进一步分析得到表8,当ρ∈[0.7,0.9]时,能够得到全局最优解,算法性能也最好。
6 结论
近来年,不少学者了解到蚁群算法在智能寻优求解这类问题上的优越性,使之在很多领域有了广泛的以后,但是蚁群算法中参数的数值选择,一直没有权威的认证。采用Ant2Cyele模型,对蚁群算法中的主要参数进行了分析。通过大量的实验分析,研究参数的最初设置对蚁群算法求解性能的影响,找到最佳的参数数值范围,对以后深入蚁群算法的研究有深刻影响,从统计学角度,对数据进行处理,通过多次实验分析,验证和确定了数值范围,由以上实验结果可以看出,参数的初始设置对算法的影响非常之大。
参考文献
[1]彭喜元,彭宇,戴毓.群智能理论及应用.电子学报,2003;31(12A):1982—1988
[2]段海滨.蚁群算法原理及其应用.北京:科学出版社,2005
[3]李士勇,陈永强,李妍.蚁群算法及其应用.北京:科学出版社,2005
[4]尹莹莹,孙亮.一种进化型蚁群算法及其在TSP问题中的检验.计算机仿真,2006;23(4):167—173
蚁群算法与粒子群算法的比较研究 篇6
由简单个体组成的群落与环境以及个体之间的互动行为称群智能(swarm intelligence)。群智能算法作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点,群智能在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题求解方案提供了基础。目前,群智能理论研究领域主要有两种算法:蚁群算法(Ant Colony Optimization,ACO)和粒子群算法(Particle Swarm Algorithm,PSO),前者是蚂蚁群落食物采集过程的模拟,后者是鸟群觅食过程的模拟。本文对这两种算法的原理、模型、应用等方面进行比较分析,并对这两种算法的改进以及与其它算法的混合做出总结。
一、蚁群算法
蚁群算法是由Colorni、Dorigo和Maniezzo通过对蚁群觅食行为的研究,于1991年提出的一种仿生进化算法[1],利用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中的问题。蚂蚁是一种社会性昆虫,通过一种特有的通信机制,其群体行为展现出高度协作性,能够完成复杂的任务,并且,蚂蚁还能够适应环境变化随时调整搜索路径。作为一种随机搜索处算法,与其他模型进化算法一样,ACO也是通过侯选解组成的群体的进化过程来寻求最优解。
蚁群算法首先被成功应用于旅行商问题(TSP)上,以此为例算法的寻优过程[2]:设有m只蚂蚁,每只蚂蚁根据信息素浓度选择下一个城市(tij(t)为t时刻城市i和j之间路径上残留的信息素浓度,dij(i,j=1,2,...,n)表示城市i和j之间的距离),规定蚂蚁走合法路线,除非周游完成,不允许转到已访问城市。完成周游后,更新蚂蚁访问过的每一条边上的信息素。
初始时刻,各路径的信息量tij(0)相等,m只蚂蚁被放置到不同的城市上。蚂蚁k(k=1,2...,m)在运动过程中,根据各条路径上信息量决定转移方向,表示在t时刻蚂蚁k由位置i转移到j的概率。
其中,allowedk表示蚂蚁k下一步允许转移到的城市集合,随k的行进而改变;信息量τij(t)随时间的推移会逐步衰减,用1-ρ表示它的衰减程度;α,β分别表示蚂蚁在运动过程中积累信息量及启发式因子在蚂蚁选择路径中所起的不同作用;ηij为由城市i转到j的期望程度,可根据某种启发算法而定。
经过n个时刻,蚂蚁k走完所有城市,完成一次循环。此时,根据式(2)一(4)更新各路径的信息素:
其中:ρ表示信息素挥发系数,Δtij表示本次循环中路径ij上的信息量增量,表示蚂蚁k在本次循环中在城市i和j之间留下的信息量,其计算方法根据不同模型而定,最常用的是ant-cycle system:
其中:Lk表示蚂蚁k环游一周的路径长度,Q为常数。
算法流程如图1所示:
二、粒子群算法
Kennedy和Eberhart于1995年受鸟群觅食行为的启发提出了粒子群优化算法(Particle Swarm Optimization,PSO)[3]。PSO中,每个优化问题的解视为d维搜索空间中的一个粒子,粒子在搜索空间中以一定速度飞行,所有的粒子都有一个由被目标函数决定的适应值,并且知道自己到目前为止发现的最好位置,每个粒子利用个体和全局最好位置更新位置和速度。
假设m个粒子组成一个种群并在D维空间搜索,第i个粒子在第t代的位置表示为一个D维的向量Xi(t)=(xi1,,xi2,…,xD),飞翔速度为Vi(t)=(vi1,vi2,...,vD),粒子本身历史最佳位置为Pi(t)=(pi1,pi2,...,pD),群体历史最佳位置为Pg(t)=(pg1,pg2,...,pD)。PSO算法迭代公式如下:
其中,w为惯性权重,使粒子保持运动的惯性,使其有扩展搜索空间的趋势;c1和c2为加速系数,代表了将每个粒子拉向Pi和Pg的随机加速项的权重;r1和r2是两个独立的介于[0,1]之间的随机数,t为进化代数。
算法流程如图2所示:
三、两种算法的比较分析
1算法各自优缺点
(1)由于群智能算法采用的是概率搜索算法,ACO和PSO具有共同的优点[4]:
①鲁棒性:由于算法无集中控制约束,不会因个别个体的故障而影响整个问题的求解。
②扩展性:信息交流方式是非直接的,通信开销少。
③并行分布性:可充分利用多处理器,适合于网络环境下的工作状态。
④优化过程无需依赖具体问题的数学特性,例如可微、线性等。
⑤算法简单容易实现:系统中个体能力简单,执行时间短。
另外,PSO还具有如下优点:
①群体搜索,并具有记忆功能,保留个体和全局的最优信息;
②协同搜索,同时利用个体和全局的最优信息指导进一步搜索。
(2)ACO和PSO也存在着局限性:
①优化性能在很大程度上依赖于参数设定,受初始值影响较大。
②容易产生早熟收敛。
另外,ACO收敛速度慢,只有小部分的ACO算法能够被证明是值收敛的,并且在实际应用中常常出现一种有害的搜索偏向现象,即二级欺骗现象。
PSO局部搜索能力差,搜索精度不高,并在理论研究上尚未完善,缺少算法设计的指导原则。
2应用领域
●ACO本质上适合于求解离散组合优化问题,在旅行商问题上取得成功应用后陆续渗透到其它领域。在指派、调度、子集、带约束满足等组合优化问题时达到了高效的优化性能。并在图着色、电路设计、二次分配问题、数据聚类分析、武器攻击目标分配和优化、大规模集成电路设计、网络路由优化、数据挖掘、车辆路径规划、区域性无线电频率自动分配、集合覆盖等优化领域得到了成功应用。
●PSO本质上适合于处理连续优化问题,但如果对求解问题进行变形或修正速度和位置更新公式也能将其应用于离散优化问题上。并且,鉴于其通用性和有效性,在解决一些典型优化问题时,其性能甚至超过了遗传算法,已成功应用于训练人工神经网络、函数优化、约束优化、多目标优化、动态优化、参数优化、组合优化、模糊系统控制、电力系统、信号处理、模式识别、生物医学等领域中。
3与其它算法混合
由于ACO与PSO具有容易与其它算法结合的特点,根据各算法的优缺点,在算法中结合其它优化技术,以提高算法的优化性能。
①蚁群算法与差分演化结合:针对蚁群算法对参数控制的依赖性、早熟和停滞等现象,以及易与其他算法结合的特点,将差分演化算法应用到蚁群算法的参数选取中,将蚁群算法的参数作为差分演化算法解空间的向量元素,自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。
②蚁群算法与粒子群算法结合:针对蚁群算法容易出现早熟现象以及算法执行时间过长的缺点,将粒子群算法引入到蚁群算法中,让蚂蚁也具有粒子的特性。
③粒子群算法与模拟退火结合:先利用PSO算法的快速搜索能力得到一个较优的群体,然后利用SA的突跳能力对部分较好的个体进行优化。
④粒子群算法与遗传算法结合:针对PSO容易早熟的缺点,在PSO中引入启发性变异机制,以扩展了算法的搜索区域,提高了算法的速度和精度且不容易陷入局部最优。
⑤粒子群算法与差分演化结合:针对粒子群算法易陷入局部极小点、搜索精度不高等缺点,在算法改进方面引用差分演化算法的变异操作,从而避免算法收敛到局部。
四、展望
群智能算法采用分布式计算机制、鲁棒性强、可扩充性好、优化效率高、并且简单易于实现,为解决实际优化问题提供了新的途径和方法。除了本文提出的ACO和PSO,群智能算法还包括研究蜜蜂通过与环境之间的信息交互实现安排工作的蜂群算法[5]、李晓磊博士通过模拟鱼群觅食行为和生存活动提出的鱼群算法[6]。作为一门新兴领域,群智能算法尚缺乏系统的分析和坚实的数学基础,实现技术不规范,在适应度函数选取、参数设置、收敛理论等方面还需要做进一步研究与探索。在此基础上,对算法加以改进或混合其他技术,以提高算法优化性能也是值得深入研究的一个方向。并且需不断拓宽其应用领域,以进一步推广群智能算法的应用。
参考文献
[1]A.Colorni,M.Dorigo,G.Theraulaz.Swarm intelligence: From natural to artificial systems[M].New York:Oxford Universyty Press,1999.
[2]宋雪梅,李兵.蚁群算法及其应用[J].河北理工学院学报,2006年2月,第28卷第1期:42-45.
[3]Kennedy J,Eberhart R.Particle Swarm Optimization[R].In:IEEE International Conference on Neural Networks,perth,Australia 1995:1942-1948.
蚁群算法优化策略综述 篇7
蚁群算法源于1992年一篇博士论文提出的模拟蚂蚁寻找食物所选路径的概率型找寻最优解的方案,这种算法本质是基于一定规则的随机运行来寻找最优方案,模仿蚂蚁寻找和搬运食物时释放信息素的机理,不断优化行走路线,在算法实现中执行时间越长,所获得的路径就越可能接近最优路径。
蚁群优化算法已应用于许多组合优化问题,例如二次分配问题,还有很多实变量动力学问题、随机问题、多目标并行的实现等方面,但在实际算法中需要避免的一个问题是过早收敛的问题,算法在执行中很快陷入到了局部最优解的搜索,难以实现广度搜索。因此,在标准算法基础上出现了优化算法,这些优化算法主体通过对于信息素的调节,防止过早收敛问题。在优化算法中核心在于平衡广度搜索与深度搜索, 保证算法的执行效率、有效性。本文通过对目前常见的蚁群优化算法进行综合分析与比较, 较为清晰的梳理出常见优化算法的特点,有助于在解决实际问题中选择合适方法以及算法优化。
2常见蚁群算法的优化算法
标准蚁群算法存在收敛慢、易停滞、运算时间长等缺陷,后续对其做了一系列的改进,以解决该算法存在的问题,产生了许多改进型算法。下面将介绍三种最典型的改进算法:蚁群系统算法(ACS)、最大最小蚁群系统算法(MMAS)、具有变异特征的蚁群算法。
2.1蚁群系统算法
蚁群系统算法(ACS)是对蚁群算法(AC)的改进,这些改进包括:蚂蚁选择的状态转移规则;全局最优更新规则仅运用于属于最优解路径上的信息素;对所有的路径的信 息量进行 局部更新 规则 (Local UpdatingRule)。在ACS中 ,全局更新只是运用在每一次循环中走最优解路径的蚂蚁,而不再运用与所有的蚂蚁。在所有的蚂蚁搜完成了一次循环后,全局更新才会执行。
2.2最大最小蚁群系统算法
最大最小 蚁群系统 算法 (Max-Min Ant System,MMAS) 是解决TSP、QAP等问题的经典蚁群优化算法之一,其结果要优于一般的蚁群算法。MMAS与ACS一样都只允许在每次迭代中表现最好的蚂蚁更新其路径上的信息素, 这样做可以防止算法过早的出现停滞现象。而MMAS与ACS相比不同的地方在于防止这种停滞现象的方法。MMAS的做法为:限定信息素浓度允许值的上下限,并且采用平滑机制。在算法启动时,MMAS将所有路径上的信息素浓度初始化为最大值。在每次循环之后, 只有在最佳路线上的蚂蚁进行信息素的更新,并将其保持在一个高的水平上,其他之路上的信息素将会按照信息素残留度降低浓度。
2.3与变异结合的蚁群算法
吴庆洪等人提出了一种优化蚁群算法———具有变异特征的蚁群算法。其核心思想为采用逆转变异方式,随机地进行变异,以增大进化时所需的信息量,从而克服传统蚁群算法收敛较慢的问题。这种变异机制之所以会具有较快的收敛速度,是因为它充分利用了2-OPT交换法简洁高效的特点。
3蚁群算法优化的新策略
对蚁群算 法所作的 优化是在 已有的改 进型算法———ACS算法的基础上进行的,下文即将描述的优化途径也都是在前人所做改良(即ACS已有的改良途径)的基础上作的更进一步的改进。
3.1路径选择机制的改良
在ACS的路径选择策略中, 我们需要对ij边上已有的信息进行有效的利用,而对于变量q的设定,存在着很大的偶然性使得我们不能很有效地利用已有信息。对此,为了进一步对已有知识加以充分利用,新变量(∑ijk)/m被引入用以替代变量q,其中∑ijk表示上一次循环中选择路径ij的蚂蚁个体的总数。在q0确定的情况下,∑ijk将伴随着算法的运行而随之增大,从而使蚂蚁个体能在下一次路径选择中优先利用已有的信息来选择将要前往的城市,进一步地提高了算法的搜索性能。
3.2全局信息素更新机制的改进
对于信息素的全局更新,我们不仅仅要运用在每一次循环中走最优解路径的蚂蚁,还要运用与每一次循环中最差的蚂蚁使用。但是对于最差蚂蚁的全局更新规则与走最优解路径蚂蚁的规则不同,其更新规则采用如下的公式
τij(t)←(1-ε)×τij(t)+ε×△τij(t) ;
其中,ε为区间(0,1)上的参数;而△τij(t)则用如下的公式计算:
△τij(t)= Q/L - Q/L’若ij路径是算法已求出的最差路径的一部分
或 = 0若ij路径不是已求出的最差路径的一部分 ;
在ACS算法的基础上, 增加对最差的蚂蚁采用以上的更新机制,能更有效地模拟蚂蚁在自然界的觅食过程中分泌的信息素,能准确得出路径长度与时间之间的关系,可使得更多的已有知识被利用,同时在后续的循环中能够增加好的路径被选择的概率并减少差的路径被选择的概率,这样算法的性能可以大大提高。
3.3增加最小信息素浓度设置
MMAS给每一条支路都设置了一个最小信息素浓度,在算法运行过程中,各个支路的信息素浓度不会降到τmin以下。这样保证了即使没有任何一只蚂蚁选择走某条路径,在再一次的循环中这条路径依然有一定的概率被选中,从而避免了一些可能存在的好的路径被过载地抛弃,同时也避免了算法过早地收敛。设置了一个最小信息素浓度τmin,它的计算公式为:
τmin = 1/[2n?(1-ρ)?L] ;
n表示当前问题的城市节点数 ,ρ为信息素残留度 ,L为算法运算到当前为止,已求出的最优路径的长度 ;为了保证所有路径上的信息素浓度不低于τmin,每当一次循环中的信息素局部及全局更新完成后,就需要比较τij和τmin,如果τij<τmin,则将τij强行设置为τmin。
3.4杂交算子的引入
遗传算法具有良好的搜索能力,引入了杂交算子来对现有的所有解进行重组,这样可以发现潜在的更好的解。我们现在尝试一种新的增强解的方法:杂交算子被引入到ACS算法中, 以对在算法运行过程中产生的新的解进行杂交, 并充分利用当前所知的所有路径信息,两者结合可以发现更好的解,从而对最终我们希望得到的结起了增强作用。
4结束语
蚁群算法作为组合优化的经典算法,在实际问题的应用中仍然存在一些问题,这些问题需要进一步研究。
(1)正反馈机制的建立 ,启发函数的定义 ,求解问题增式的进行,以及最优解与问题定义中的现实世界的况相对应等问题需要考虑。
(2)在开始运行蚁群算法求解问题时 ,需要对大量的变量进行初始化,这些变量的初始值会对算法的性能产生较大的影响。然而这些变量初始值的选取方法和原则在目前还没有一个理论上的依据,只能在多次实验中积累经验从而选择比较好的值。因此在初始化变量的最佳值设置问题上还有待进一步的研究。
摘要：对于求解TSP问题,新型的启发式算法——蚁群算法,是成功解决此类问题核心的算法之一。本文简要介绍了几种启发式算法并引出蚁群算法,并对蚁群算法基本原理、常用算法进行了深入的研究,并介绍了一种新的优化策略。