基本信息
- 项目名称：
- 求解最小费用流问题的蚁群算法
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 数理
- 大类：
- 自然科学类学术论文
- 简介：
- 本论文主要是提出了一种可行的模拟蚁群算法，并对此类问题进行了实验验证。因受蚁群算法思想的启发，故将路径上的信息素采用路径上的流量进行局部更新，在建立的最小费用流模型基础上编程求解，得到了受最小费用约束条件下的所有可行路径及对应的流量，然后将其分配得到了每条弧上可通过的最大流，并将所得结果与标号算法、调整圈法进行对比，其解比较理想，同时还对此模型进行了一定的推广。
- 详细介绍：
- 本文为了能快速有效地解决最小费用流问题，提出了一种可行的模拟蚁群算法.但因最小费用流问题是基于有向图上求解的，具有方向性，故针对此做了一些相应转化，并受蚁群算法思想的启发将蚂蚁在有向网络图中的信息素更新及选择下一条路径的概率公式做了相关改进.同时在最小费用流模型的基础上，利用从终点向始点反向寻找可行路径的思想求解。并将仿真实验的结果与标号算法、调整圈法进行对比，得到了较为理想、精确的解。
作品专业信息
撰写目的和基本思路
- 写作目的： 为了能快速有效地解决最小费用流问题，提出了一种可行的模拟蚁群算法，并对此类问题进行了实验验证，以便能解决实际生活中的众多相关问题。 基本思路： 通过掌握蚁群算法的基本原理，结合有向网络描述最小费用流的数学模型，再运用从终点向始点反向计算的思想求解在最大可行流的约束下的最小费用，然后仿真实验，最后调整圈法与标号算法验证。
科学性、先进性及独特之处
- 科学性、先进性和独特之处： 现阶段，关于求解最小费用流问题的传统算法较多，而用现代优化算法求解的研究较少，故在蚁群算法原理的启发下，提出了一种可行的蚁群算法，该算法试图将蚂蚁选择下一点的概率及路径上信息素更新进行了更改，在最小费用流模型做相应的转化下运用该算法求解。此蚁群算法在参数的选取合理恰当下进行仿真实验，将所得结果与调整圈法、标号算法进行对比，并对此模型进行了一定的推广。
应用价值和现实意义
- 实际应用价值和现实指导意义在于，它能较好的解决规模较大、非整数情况下的最小费用流问题，能应用于现实生活中的多媒体网络信息传播、产品的运输与调度、指派问题等方面，并还能在许多工程领域和物理、化学、生物及应用数学等科学领域有着广泛的研究。
学术论文摘要
- 为了运用蚁群算法解决最小费用流问题，首先掌握了蚁群算法的基本原理，结合有向网络描述了最小费用流的数学模型，并运用从终点向始点反向计算的思想求解在最大可行流约束下的最小费用，然后给出了其具体过程。最后通过仿真实验，调整圈法和标号算法验证表明：该算法是有效可行的。
获奖情况
- 2010年6月内江师范学院 发表在《内江师范学院学报》（双月刊） 中图分类号：TP183 文献标识码：A 文章编号：1671-1785（2010）06-0030-03
鉴定结果
- 学报编辑部及导师评定结果： 本文具有较灵活的理论性和实务性，对解决最小费用流类问题有一定的实际意义和应用价值。
参考文献
- [1]Dorigo M，Maniezzo V，Colorni A，The ant system：Optimization by a Colony of Cooperating Agents[J]．IEEE Transactions on Systems，Man，and Cybernetics-part B，1996，26(1):29¬—41． [2]倪庆剑．蚁群算法及其应用研究进展[J]．计算机应用与软件，2008，25(8):12-18． [3]吴斌，史忠植．一种基于蚁群算法的TSP问题分段求解算法[J]．计算机学报，2001，24（12）：1328-1333． [4]谢民，高利新．蚁群算法在网络最大流问题中的应用[J]．计算机工程与应用，2008,44(22):113-115． [5]张新敬，李刚，邱学绍．最小费用最大流算法实现[J]．自然科学报，2005，20(3):132-134． [6]韩明亮．求解最小费用最大流问题的一种方法[J]．中国民航学院学报，2000，18(1):49-53． [7]赵静，但琦．数学建模与数学实验(第三版) ．高等教育出版社[M]．2009，225—227．
同类课题研究水平概述
- 最小费用流问题是一个经典的组合优化问题，已有40多年的研究历史，人们已经建立了最大流问题较为完善的理论，同时开发了大量的算法，如Ford和Fulkson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法以及Goldberg和Rao的二分长度阻塞流算法等，这些经典算法及相关技术对网络最大流方面的问题应用与研究起到了非常重要的推动作用。尽管最大流问题在使用算法方面取得了许多突破性研究进展，但到目前人们对最小费用流问题的研究却不够成熟，值得探索。最小费用流问题有着广泛的实际应用背景，如现实生活中的铁路网、通信网、运输网等，所以研究如何解决最小费用流问题有着十分重要的实用意义。 蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型、新型的模拟进化算法．它由意大利学者Marco Dorigo于1992年通过模拟自然界中蚂蚁群体寻径的行为而提出的一种基于种群的启发式仿生进化系统。在提出蚁群算法后，Dorigo等人应用该算法求解了旅行商问题(traveling salesman problem，TSP)、二次分配问题、Job-Shop调度问题，在AS算法基础上，ColorniA等人又提出了改进的ACS(AColonySystem)模型，并在1999年将AS、ACS纳入蚁群优化的框架，称为ACO(AntColonyOptimization)，在各个领域取得了较好的实验结果。 蚁群算法是通过模拟真实蚁群的觅食机理求解优化问题，引入信息素概念及相关的信息素更新机制。蚁群算法利用其基本原理适应性地搜索问题的最优解，在解决许多复杂优化问题方面已经展现出其优异的性能和巨大的发展潜力，该算法具有较强的鲁棒性、优良的并行计算机制和易于与其他方法相结合等优点，不论在搜索效率还是在时间的复杂度方面都有着令人满意的效果。蚁群算法的思想已经应用到各个研究领域，取得了大量的研究成果。但其也存在一些不足，如搜索时间长、算法收敛最优解速度迟缓、易于陷入局部最优、易于停滞不能对空间进行进一步搜索。 当然，本文的形成正是建立在蚁群算法领域专家前辈们的研究成果基础上的，可以说如果没有他们的研究成果是不会有本文的初步启发和探索，故在此衷诚地对前辈专家们和导师表示感激之意！
