基本信息
- 项目名称：
- 求解最小费用流问题的蚁群算法
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 数理
- 大类：
- 自然科学类学术论文
- 简介：
- 本论文主要是提出了一种可行的模拟蚁群算法，并对此类问题进行了实验验证。因受蚁群算法思想的启发，故将路径上的信息素采用路径上的流量进行局部更新，在建立的最小费用流模型基础上编程求解，得到了受最小费用约束条件下的所有可行路径及对应的流量，然后将其分配得到了每条弧上可通过的最大流，并将所得结果与标号算法、调整圈法进行对比，其解比较理想，同时还对此模型进行了一定的推广。
- 详细介绍：
- 本文为了能快速有效地解决最小费用流问题，提出了一种可行的模拟蚁群算法.但因最小费用流问题是基于有向图上求解的，具有方向性，故针对此做了一些相应转化，并受蚁群算法思想的启发将蚂蚁在有向网络图中的信息素更新及选择下一条路径的概率公式做了相关改进.同时在最小费用流模型的基础上，利用从终点向始点反向寻找可行路径的思想求解。并将仿真实验的结果与标号算法、调整圈法进行对比，得到了较为理想、精确的解。
作品专业信息
撰写目的和基本思路
- 写作目的： 为了能快速有效地解决最小费用流问题，提出了一种可行的模拟蚁群算法，并对此类问题进行了实验验证，以便能解决实际生活中的众多相关问题。 基本思路： 通过掌握蚁群算法的基本原理，结合有向网络描述最小费用流的数学模型，再运用从终点向始点反向计算的思想求解在最大可行流的约束下的最小费用，然后仿真实验，最后调整圈法与标号算法验证。
科学性、先进性及独特之处
- 科学性、先进性和独特之处： 现阶段，关于求解最小费用流问题的传统算法较多，而用现代优化算法求解的研究较少，故在蚁群算法原理的启发下，提出了一种可行的蚁群算法，该算法试图将蚂蚁选择下一点的概率及路径上信息素更新进行了更改，在最小费用流模型做相应的转化下运用该算法求解。此蚁群算法在参数的选取合理恰当下进行仿真实验，将所得结果与调整圈法、标号算法进行对比，并对此模型进行了一定的推广。
应用价值和现实意义
- 实际应用价值和现实指导意义在于，它能较好的解决规模较大、非整数情况下的最小费用流问题，能应用于现实生活中的多媒体网络信息传播、产品的运输与调度、指派问题等方面，并还能在许多工程领域和物理、化学、生物及应用数学等科学领域有着广泛的研究。
学术论文摘要
- 为了运用蚁群算法解决最小费用流问题，首先掌握了蚁群算法的基本原理，结合有向网络描述了最小费用流的数学模型，并运用从终点向始点反向计算的思想求解在最大可行流约束下的最小费用，然后给出了其具体过程。最后通过仿真实验，调整圈法和标号算法验证表明：该算法是有效可行的。
获奖情况
- 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]倪庆剑．蚁群算法及其应用研究进...(查看更多)
同类课题研究水平概述
- 最小费用流问题是一个经典的组合优化问题，已有40多年的研究历史，人们已经建立了最大流问题较为完善的理论，同时开发了大量的算法，如Ford和Fulkson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法以及Goldberg和Rao的二分长度阻塞流算法等，这些经典算法及相关技术对网络最大流方面的问题应用与研究起到了非常重要的推动作用。尽管最大流问题在使用算法方面...(查看更多)
