毕业设计（论文）蚁群算法用于函数优化研究.doc

论文题目: 蚁群算法用于函数优化研究 系 ： 信息与机电工程系 专业年级： 计算机科学与技术2007级 学 号： 姓 名： 指导教师、职称： 2011 年 5 月 16 日Ant Colony AlgorithmFor Function OptimizationCollege: Information and Electrical Engineering Specialty and Grade: Computer Science and Technology, 2007Number: Name: Advisor: Submitted Time: May 16, 2011 目录摘要IAbstractII1引言11.1蚁群算法的研究背景11.2 蚁群算法简介11.2.1 蚁群算法的概述11.2.2 蚁群算法的优缺点12蚁群算法的原理及其基本模型32.1 蚁群算法的工作原理32.2 蚁群算法的基本模型42.3 基本模型的实现62.3.1 基本模型的实现步骤62.3.2 基本模型的程序流程73用于连续空间优化问题的蚁群算法83.1 连续空间优化问题83.2 算法基本思想84实验结果分析105结束语14致谢16摘要本文主要研究蚁群算法。函数优化问题一般为求极值问题，其中包括极大值或极小值。通过对目标函数的自适应来调整蚂蚁的搜索行为，同时通过路径选择过程中的多样性来保证得到更多的搜索空间，从而快速的得到函数全局的最优解。本论文采用了蚁群算法，针对几个函数进行测试，求解能够得到满意的结果，很好的说明了蚁群算法在函数优化上的优越性。关键词：蚁群算法；函数优化；函数极值；连续空间优化AbstractThis articles main is reserarch for ant colony algorithm.The question of function optimization in order to resolve the extremal problem, include maximun and minimum. By adaptive objective function to adjust the search behanior of ants, at the same time, through the diversity of the path selection process to ensure that more of the search space, and quickly get the global optimal solution. Paper uses the ant colony algotithm, for several functions to test, and solution can be satisfied with the results, it good shows the ant colony algorithm on the function optimizatiom has superiority.Keywords: ant colony algorithm; function optimizatiom; function extremum; continuous space optimization1引言1.1蚁群算法的研究背景蚁群算法是近几年优化领域中新出现的一种启发式仿生类并行智能进化算法，它是受到人们对自然界中真实的蚁群集体行为的研究成果的启发而提出的一种基于种群的模拟进化算法，属于随机搜索算法。由意大利学者M.Dorigo等人充分利用了蚁群搜索食物的过程与著名的旅行商问题(TSP)之间的相似性，通过人工模拟蚂蚁搜索食物的过程(即：通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径)来求解TSP，为了区别于真实蚂蚁群体系统，人们称这种算法为“人工蚁群算法”，并用该方法求解TSP问题1、分配问题、job-shop调度问题2等，取得了较好的实验结果。1.2 蚁群算法简介1.2.1 蚁群算法的概述蚂蚁是自然界中常见的一种生物，在昆虫世界，蚂蚁是一种群居的世袭大家庭，我们称之为蚁群（ant colony）。人们对蚂蚁的关注大都是因为“蚂蚁搬家，天要下雨”之类的民谚。然而随着近代仿生学的发展，这种似乎微不足道的小东西越来越受到学者们的关注。1991年意大利学者M.Dorigo等人首先提出了蚁群算法(ant colony algorithm)，人们开始了对蚁群的研究：相对弱小，功能并不强大的个体是如何完成复杂的工作的(如寻找到食物的最佳路径并返回等)，因此在此基础上，蚁群算法从对蚁群行为的研究中产生且逐渐发展起来。蚁群具有高度组织的社会性，彼此间的沟通不仅可以借助触觉、视觉的联系，在大规模的协调行动上可以借助外激素（pheromone）之类的生产化信息介质。蚁群的觅食行为是最易观察的，每只蚂蚁具有如下的职能：平时在巢穴附近作无规则行走，一旦发现食物，如果独自能搬的就往回搬，否则就回巢搬兵，一路上它会留下外激素的嗅迹，其强度通常与食物的品质和数量成正比；若其他蚂蚁遇到嗅迹，就会循迹前进，但也会有一定的走失率（选择其他路径），走失率与嗅迹的强度成反比，从而相互协作，完成复杂的任务。人工蚂蚁算法就是受到人们对自然界中真实的蚁群集体行为研究成果的启发，而提出的一种基于种群的模拟进化算法，属于随机搜索全局优化算法。与其它模拟进化算法一样，通过多个候选解组成的群体的进化过程并以最大概率逼近问题的最优解。1.2.2 蚁群算法的优缺点 蚁群算法是一种随机搜索算法。诸多研究证明，蚁群算法具有很强的寻优能力，不仅利用正反馈原理，在一定程度上加快了寻优过程，而且是一种本质并行算法，不同个体之间进行信息交流和传递，从而相互协作，有利于发现更好解。它具有以下优点3：（1）较强的鲁棒性（即通用性）：对基本蚁群算法模型稍加修改，便可以应用于其他问题。（2）分布式计算：蚁群算法是一种基于种群的进化算法，具有本质并行性，易于并行实现。（3）易于与其它方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。蚁群算法也有一些缺陷：（1）需要较长的搜索时间：由于蚁群中多个个体的运动是随机的，虽然通过信息的交流能够向着最优路径进化，但是当群体规模较大时，很难在短时间内从复杂无章的路径中找出一条较好的路径。（2）容易出现停滞现象（stagnation behavior）：即在搜索进行到一定程度后，所有个体所发现的解完全一样，不能对解空间进一步进行搜索，不利于发现更好的解。（3）难以处理连续空间的优化问题4：由于每个蚂蚁在每个阶段所作的选择总是有限的，它要求离散的解空间，因而它对组合优化等离散优化问题很适用，而对线性规划等连续空间优化问题的求解不能直接应用。对于上述三个问题，已经引起许多研究者的关注，并提出了一些改进措施，如为了充分利用时间，强化最优信息的反馈，Dorigo等人在基本的蚁群算法的基础上提出了称为Ant-Q System的更一般的蚁群算法，仅让每一次循环中最短的路径上的信息量更新 5，6。为了克服可能出现的停滞现象，Stuzzle 等人提出了MAX-MIN Ant System，允许各个路径上的信息量在一个限定的范围内变化7。吴庆洪等人在蚁群算法中引入变异机制，即可克服停滞现象，又可取得较快的收敛速度8。Gambardella 等人提出了一种混合型蚁群算法HAS，在每次循环中蚂蚁建立各自的解后，再以各自的解为起点，用某种局部搜索算法求局部最优解，以此作为相应蚂蚁的解，这样可以迅速提高解的质量9。针对蚁群算法难以处理连续空间的优化问题，Bilchev 等人曾在使用遗传算法解决工程设计中连续空间的优化问题时，配合使用了蚁群算法，对遗传算法所得到的初步结果进行精确化，取得了较好的效果10，但是使用蚁群算法本身去解决连续空间的优化问题的能力是相对较弱的。2蚁群算法的原理及其基本模型2.1 蚁群算法的工作原理蚁群算法最初是模拟蚂蚁的觅食行为与TSP问题(旅行商问题)的相似性提出的，蚂蚁的行为与组合优化问题的对比，如表2.1所示。表2.1 蚂蚁觅食与组合优化问题的对比组合优化问题蚂蚁觅食各个状态要环游的各个城市解蚂蚁的环游最优解最短环游各状态的吸引度信息数的数量状态更新信息数更新目标函数路径长度在蚂蚁找到食物时，它们总能找到一条从食物到巢穴之间的最优路径11。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素(pheromone)。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激素浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大，这样形成了一个正反馈。最优路径上的激素浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减，最终整个蚁群会找出最优路径。不仅如此，蚂蚁还能够适应环境的变化，当蚁群运动路线上突然出现障障碍物的，蚂蚁能够很快地重新找到最优路径，这个过程和前面所描述的方式是一致的。在整个寻径过程中，虽然单个蚂蚁的选择能力有限，但是通过激素的作用，整个蚁群之间交换着路径信息，最终找出最优路径。M.Dorigo对基本蚁群算法的论述如下3：如图2.1(a)所示，设A是巢穴，E是食物源，HC为一碍物。由于障碍物存在，蚂蚁要想由A到达E，或者由E返回A，只能由H或C绕过障碍物。各点之间的距离，如图2.1所示。设每个时间单位有30只蚂蚁由A到达B，有30只蚂蚁由E到达D点，蚂蚁过后留下的激素物质量（以下我们称之为信息素）为1。为方便，设该物质停留时间为1。在初始时刻,由于路径BH、BC、DH、DC上均无信息存在，位于B和E的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择BH、BC、DH、DC，如图2.1(b) 所示。经过一个时间单位后，在路径BCD上的信息量是路径BHD上信息量的二倍。T=1时刻将有20只蚂蚁由B和D到达C，有10只蚂蚁由B和D到达H。随着时间的推移，蚂蚁将会以越来越大的概率选择路径BCD，最终完全选择路径BCD，如图2.1(c) 所示。从而找到由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息交换是一个正反馈过程。d=2d=2d=1d=1HABDEC （a） 15151515HABDEC 10102020HABDEC t=0 t=1 (b) (c) 图2.1 蚁群算法基本原理2.2 蚁群算法的基本模型为了便于理解，以下以TSP问题为例说明蚁群算法的基本模型12，对于其它问题，可以对此模型稍作修改，便可应用。首先引入以下符号：蚁群中蚂蚁的总数目；TSP规模（即城市数目）；城市i和城市j之间的距离（i，j=1，2，3，n）；t时刻，位于城市i的蚂蚁数；t时刻，蚂蚁从城市i转移到城市j的期望度，为启发式因子。在TSP 问题中，称为能见度；t时刻，在城市i和城市j之间的路径上的信息素量。在算法的初始时刻，将只蚂蚁随机放在个城市，并设各条路径上的信息素量=C （C为常数）；t时刻，蚂蚁k从城市i转移到城市j的概率。位于城市i的蚂蚁k（k=1，2，3，m）选择路径时按概率决定转移方向，即 （2.1） 式中和分别表示路径上的信息素量和启发式因子的重要程度。用表示当前蚂蚁k已走过的城市，=1，2，3，n-，表示蚂蚁k下一步允许选择的城市（人工蚂蚁有记忆功能，这是实际蚂蚁所不具备的）。为了避免残留信息素过多而引起启发信息被淹没，在每只蚂蚁走完一步或者完成对n个城市的遍历后，要对各条路径上的信息素进行调整： （2.2） （2.3）式中表示信息素残留系数，为了防止信息的无限积累，的取值范围应在0到1之间，表示在本次循环后留在i到j路径上的信息素增量，表示第k只蚂蚁在本次循环中留在路径（i，j）上的信息素量。根据信息素更新策略的不同，Dorigo M曾给出三种不同的实现方法13，分别称之为AntCycle模型、Ant Quantity模型及AntDensity模型，其差别就在于的求法不同。在AntCycle模型中否则 若第k只蚂蚁在本次循环中经过路径（i，j） （2.4）在Ant Quantity模型中若第k只蚂蚁在t和t+1之间经过路径（i，j）否则 （2.5）在AntDensity模型中否则若第k只蚂蚁在t和t+1之间经过路径（i，j） （2.6）式中Q表示信息素强度，在一定程度上影响算法的收敛速度，Lk表示第k只蚂蚁在本次循环中所走路径的总长度。区别：式（2.5）、（2.6）利用的是整体信息，即蚂蚁完成一次周游后，更新所有路径上的信息素；而式（2.4）利用的是局部信息，即蚂蚁每走一步都要进行信息素的更新。由于在求解TSP问题中，式（2.4）的性能较好，所以通常将式（2.4）作为蚁群算法的基本模型。2.3 基本模型的实现从蚁群算法的模型中，我们可以看出，蚁群寻找最短路径实际上是一个递推过程，便于在计算机上实现。2.3.1 基本模型的实现步骤为了便于理解，下面以TSP问题为例来阐述蚁群算法的具体实现步骤。第一步：初始化。令时间 t=0，循环次数Nc=，设置最大迭代次数Nc_max的值。将m只蚂蚁随机放到n个城市，并将每只蚂蚁的出发点城市号放入禁忌表中。令(c为常数)，设定、的值；第二步：NcNc+1；第三步：对所有蚂蚁，以当前城市为起点，选择下一个要去的城市。首先从n-1个城市中找到每只蚂蚁未走过的城市（即），蚂蚁个体根据状态转移概率公式（2.1）计算概率，选择概率最大的城市号前进；第四步：修改禁忌表指针，即将每只蚂蚁到达的新城市号移到该蚂蚁个体的禁忌表中；第五步：若禁忌表未满，即城市未遍历完，则跳到第三步继续执行，否则执行第六步；第六步：根据式（2.2）和式（2.3）更新每条路径上的信息量；第七步：若满足结束条件，即如果Nc>=Nc_max，则循环结束，输出最佳路径，否则，清空禁忌表并转到第二步继续执行。2.3.2 基本模型的程序流程以TSP为例，基本蚁群算法的程序流程如图2.2所示。开始初始化Nc=1 K=1NY按照转移概率公式选择下一城市修改禁忌表k=k+1Nk>mNNc=Nc+1tabu(k)清空按式(2.2)、(2.3)更新信息素Y将m只蚂蚁随机放到n个城市，并将每只蚂蚁的出发点城市号放入tabu(k)中Nc>Nc_max结束Y输出最佳路径Tabu(k)满吗？ 图2.2 基本蚁群算法的程序流程图3用于连续空间优化问题的蚁群算法3.1 连续空间优化问题在优化过程中，所遇到的大都是连续优化问题，即函数的极值问题，因此研究蚁群算法在函数优化问题很有价值。在离散域组合优化问题中，蚁群算法的信息量留存、增减和最优解的选取都是通过离散的点状分布求解方式来进行的；而在连续域优化问题的求解中，其解空间是一种区域性的表示方式，而不是以离散的点集来表示的。因此，连续域寻优蚁群算法与离散域（以TSP为例）寻优蚁群算法之间主要存在着以下不同之处。（1）从优化目标来说，求解TSP的蚁群算法要求所搜索出的路径最短且封闭；而用于连续域寻优问题的蚁群算法则是要求所求问题的目标函数值达到最优，且目标函数中包含各蚂蚁所走过的所有节点的信息以及系统当前的性能指标信息。（2）从信息更新策略来说，求解TSP的蚁群算法是根据路径长度来修正信息量，在求解过程中，信息素是遗留在两个城市之间的路径上，每一步求解过程中的蚁群信息素留存方式只是针对离散的点或点集分量；而用于连续域寻优问题的蚁群算法将根据目标函数值来修正信息量，在求解过程中，信息素物质则是遗留在蚂蚁所走过的每个节点上，每一步求解过程中的信息素留存方式在对当前蚁群所处点集产生影响的同时，对这些点的周围区域也产生相应的影响。（3）从行进方式来说，蚁群在连续空间的行进方式不同于离散空间集之间跳变的行进方式，而应是一种微调式的行进方式。3.2 算法基本思想蚁群算法的优化过程主要包括选择、更新以及协调三个过程。整个优化过程将分为粗搜索过程和精搜索过程，并且每一个过程设置不同类的蚂蚁。在粗搜索过程中，首先将待求问题的多约束函数通过最小二乘法及惩罚函数法转换为统一的目标函数，也可以在蚁群操作过程中通过特定的子程序判断候选解是否满足约束条件来处理，对标准的目标函数将待求问题的独立变量依据该变量的要求不同划分为不同的等份小单元，尤其对设计中需要最终变量的值是整数值的变量，对该类变量就划分成等份整数单元，以便优化的结果直接可用而无须后续二次取整处理。这样处理极大地缩小了搜索空间，提高了搜索效率。整个粗搜索即是完成每只蚂蚁以走完所有的独立变量中的某一值而构成一个可行解，然后修改所有路径上的信息素。在精搜索过程中，将上述粗搜索得到的可行解进行单元细化，以可行解构成初始群体，依据某种概率进行交叉和变异操作，并采用另一类蚂蚁执行蚁群算法，最终找到多变量优化问题的全局最优解14。具体如下：首先将函数的解空间等分成n个小区间（称为区域），然后将m只蚂蚁随机放在这些区域上，蚂蚁将按如下规则进行最优解的搜索：在一次循环中，首先计算出每只蚂蚁向各区域的转移概率，如果符合相应的转移条件（即搜索到的新位置的目标函数值大于当前蚂蚁所在位置的目标函数值），则蚂蚁按一定规则进行转移。如果不符合，蚂蚁则在区域内进行遍历搜索。在新的循环开始前，更新各个区域的信息素。在此基础上再计算每只蚂蚁的转移概率，按类似转移规则进行新一轮的搜索。主要步骤如下15：步骤1 nc=0 (nc为迭代步数或搜索次数)，和的初始化，将 m个蚂蚁置于n个顶点上； 步骤2 将各蚂蚁的初始出发点置于当前解集，对每个蚂蚁 k ( k=1， m)，按概率移至下一顶点j，将顶点j置于当前解集； 步骤 3 计算各蚂蚁的目标函数值 ( k=1， m)，记录当前的最好解； 步骤 4 按更新方程修改轨迹强度 ； 步骤 5 对各边弧( i，j)，置， nc= nc+1； 步骤 6 若nc <预定的迭代次数，则转步骤2 该算法全局上是在人先验知识和启发信息的引导下进行优化搜索的，在局部上采用的是遍历性搜索策略。接下来本文将对二维函数优化后结果进行简单说明。4实验结果分析 目标函数一： 根据原理，各数值首先随机分布在坐标上如图4.1(a)，经过多次搜索最终得到最优解如图4.1(b)，所得极大值为0.9997如图4.1(c)，并得出最优函数值的变化趋势图。图4.1(a)图4.1(b)图4.1(c)目标函数二：通过蚁群算法，各数值首先随机分布在坐标上如图4.2(a)，经过多次搜索最终得到最优解如图4.2(b)，得出复杂的数的极大值：2.0000如图4.2(c)，并得到最有函数值变化趋势图。图4.2(a)图4.2(b)图4.2(c)5结束语蚁群算法虽然研究时间不长，还不像其它的启发式算法那样已经形成系统的分析方法和具有坚实的数学基础。参数的选择更多的是依靠实验和经验，没有定理来确定，缺乏理论分析，而且它在理论和实践方面尚有许多问题需要更深入的研究与解决，还存在着一些缺陷，如：收敛速度慢，计算时间长，易于过早地陷入局部最优，在求解连续优化问题上相对较弱等。但它却采用了正反馈机制，有很强的发现较好解的能力，具有很强的并行性和鲁棒性等许多优点。从当前的研究和应用情况来看，不论从算法的理论研究还是应用领域方面都取得了突破性的进展，它具有强大的生命力，可以预料，随着研究的深入，蚁群算法将给我们展示一个求解复杂组合优化问题的优秀寻优算法，其发展前景十分光明。因此，怎样用蚁群算法更好、更有效的解决各类优化问题，怎样形成一套较完备的蚁群算法模型，是今后值得进一步去关注的热点和研究的前沿课题。参考文献1Lew is W A. Econom ic development w ith unlim ited supply of labor J. JOF the M anchester School, 1954,(4): 32-36.2Magnusson.Evolutionary and Neo-Schumpeterian Approaches to Econom ics M.Boston: Kluwer Acadmic Publishers, 1994.3王剑，李平，杨春节蚁群算法的理论与应用A浙江：浙江大学 工业控制技术研究所，2003，20(5):126-1294段海滨蚁群算法原理及其应用M北京：科学出版社，2005，21(2):175-2095何桂良，潘久辉蚁群算法的小改进J现代计算机，2005，21(205):76-796 Bonabeau E，Dorigo M and Theraulaz GInspiration for optimization from social insect behaviourJNature, 2000，406(6):39-427 Dorigo，M.，Luca，MA study of some properties of Ant-QTechnical Report，TR/IRIDA/1996-4，IRIDIA，Universite Libre de Bruxelles，19968 Stutzle，T.，Hoos，H.HImprovements on the ant system：introducing the Max-MIN ant systemIn：Smith，G.D.，Steele，N.C.，Albrecht，R.F.，edsProceedings of the Artificial Neural Nets and Genetic Algorithms 1997Wien：Springer-Verlag，1998，245-2499 Wu，Qing-hong，Zhang，Ji-hui，Xu，Xin-he，An ant colony algorithm with mutation featuresJournal of Computer Research & Development，1996，36(10)：1240-1245 (in Chinese)10陈崚，沈洁蚁群算法求解连续空间优化问题的一种方法A扬州大学软件学报，2002,13(12):2317-232311肇勇，卢晓刚连续优化问题的蚁群算法研究进展A达县师范高等专科学校学报（自然科学版），2004,14(5):41-4312丁海军，陈佑健蚁群算法的现状与研究进展A江苏：河海大学常州分校学报，2005,19(1):5-913 沈洁，秦岭蚁群算法求解连续空间优化问题的一种方法J软件学报，2002，13(12)：2317-232314原思聪，刘道华等基于蚁群算法的多维有约束函数优化研究A西安：西安建筑科技大学，2008,25(6):1682-168415熊伟清，余舜浩等具有分工的蚁群算法及应用A宁波大学信息科学与工程学院，2003,16(3):328-333致谢本论文是在林晓宇老师的亲切关怀和悉心指导下完成的。他认真的教学态度，严谨的治学精神，精益求精的工作作风，深深地感染和激励着我，使我受益匪浅。从毕业论文的选题到论文的撰写，林老师始终给予我细心的指导和不懈的支持，在此谨向林老师致以诚挚的谢意和崇高的敬意。同时感谢其他老师在学习和生活中给予我的支持和帮助，感谢周围同学对我的帮助。我在金山学院不仅学到了许多知识，而且从各位老师那里学到了严谨的治学态度、踏实认真的工作精神和为人正直的作风，这都将使我终身受益。现在我即将离开母校，走向各自的工作岗位了。我不会忘记恩师们平时教给我们做人的道理，更不会忘记母校对我的栽培。此外，我还要感谢我的父母，是他们在背后一直默默无闻地给予我精神、物质的支持，激励着我不断奋进！最后，向百忙中抽出时间参加本次论文评阅和答辩的各位老师致以诚挚的谢意！谢谢你们！