智能计算方法model

研究生课程论文课程名称： 智能计算方法论文题目： 蚁群优化算法及其应用研究指导教师： 段鹏飞学 院： 计算机科学与技术学院班 级： 姓 名： 学 号： 蚁群优化算法及其应用研究摘要：文章在介绍了蚁群算法的基本原理和算法模型的基础上. 关键词：蚁群算法;1引言自然界中的许多自适应优化现象不断给人以启示：生物体和自然生态系统可通过自身的演化就使许多在人类看起来高度复杂的优化问题得到完美的解决。近些年来，一些与经典的数学规划原理截然不同的，试图通过模拟自然生态系统机制以求解复杂优化问题的仿生优化算法相继出现，大大丰富了现代优化技术，也为那些传统最优化技术难以处理的组合优化问题提供了切实可行的解决方案。伴随着模拟自然与生物机理为特征的仿生优化算法时代的悄然兴起，一些仿生优化算法已经在经典NP-C问题的求解和实际应用中显示出强大的生命力和进一步发展的潜力。蚁群优化算法就是其中的一个典型例子。 蚁群算法由意大利学者M.Dorigo等人首先提出，称之为蚁群系统(Ant Colony System,ACS)，并用该方法来解决旅行商问题、指派问题、Job-shop调度问题等，取得了一系列较好的实验结果。 蚁群算法的主要特点是:正反馈、分布式计算。与某种启发式算法相结合，正反馈过程使得该方法能很快发现较好解;分布式易于并行实现，与启发式算法相结合，使得该方法易于发现较好解。初步的研究表明，蚁群算法是一种基于种群的鲁棒性较强的算法，具有许多优良的性质，为求解复杂的组合优化问题提供了一种新思路。2 基本蚁群算法2.1基本原理人工蚁群算法是模仿真实的蚁群行为而提出的。仿生学家经过大量细致的观察研究发现，蚂蚁个体之间是通过一种称之为外激素(pheromone)的物质进行信息传递的。蚂蚁在运动过程中，能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向。因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。M.Dorigo对基本蚁群算法的论述如下：如图1(a)所示，设A是巢穴，E是食物源,HC为一障碍物。由于障碍物存在，蚂蚁要想由A到达E，或者由E返回A，只能由H或C绕过障碍物。各点之间的距离，如图1所示。设每个时间单位有30只蚂蚁由A到达B，有30只蚂蚁由E到达D点，蚂蚁过后留下的激素物质量(以下我们称之为信息素)为1。为方便，设该物质停留时间为1。在初始时刻，由于路径BH,BC,DH,DC上均无信息存在，位于B和E的蚂蚁可以随机选择路径。从统计的角度可以认为它们以相同的概率选择BH,BC,DH,DC，如图1(b)所示。经过一个时间单位后，在路径BCD上的信息量是路径BHD上信息量的二倍。T=1时刻，将有20只蚂蚁由B和D到达C，有10只蚂蚁由B和D到达H。随着时间的推移，蚂蚁将会以越来越大的概率选择路径BCD，最终完全选择路径BCD，如图1(c)所示。从而找到由蚁巢到食物源的最短路径。由此可见，蚂蚁个体之间的信息交换是一个正反馈过程。 图1蚁群算法原理2.2算法模型为了便于理解，通过蚁群算法来求解平面上n个城市的TSP问题(0,1, ,n-1表示城市序号)，以此来说明图搜索蚁群算法具体的实现步骤。对于其它问题，可以对此模型稍作修改便可应用。 旅行商问题的简单形象描述是：给定n个城市，有一个旅行商从其中的某一个城市出发，访问各城市一次且仅有一次最后回到原来出发的城市，要求找出一条最短的巡回路径。其图论描述为：给定图G=(V,A),其中V为顶点集，A为各顶点相互连接组成的边集，已知各顶点间的连接距离，要求确定一条长度最短的汉密尔顿回路，即遍历所有顶点当且仅当一次的最短回路。3 基本蚁群算法实验及结果分析4改进型蚁群算法4.1具有随机扰动特征的蚁群算法 蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。但是，一般信息素更新方式，所有通过路段(i,j)的搜索路径对应的候选解均会对该路段带来信息素的增量。而实际上，候选解并非都是最好解，这样计算信息素的增量会导致错误的引导信息，从而造成大量的无效搜索，使系统出现停滞现象。故可以采用可变的扰动因子，使系统跳出局部最优4.2混合蚁群算法 5蚁群算法的应用虽然蚁群算法的研究时间还不是很长，还没有形成完整的理论体系，但已经显示出了其在求解复杂问题方面的优势。下面是该算法的一些主要应用。5.1 生产调度多目标分配问题生产调度是一个复杂的动态管理优化问题。因为蚁群算法机制可以不断从过去的加工经历中学习，能自然地适应车间内外部环境的变化，从