论基于MPI的并行蚁群算法的应用研究

摘要：基于mpi的并行蚁群算法是一种新型、便捷的元启发式算法。并行蚁群算法具有天然的并行性，对于大量的优化数据的问题，并行蚁群算法能够最大程度的节省时间，也可以为蚁群算法的应用打好坚实的基础，该文从蚁群算法的相关定义及原理、基于MPI的并行蚁群算法的相关内容、蚁群算法并行化的可行性和必要性以及并行蚁群算法在日常生活中的应用。通过对这些问题的研究让人们对并行蚁群算法能够有更加细致全面的了解，将蚁群算法更好的发展，以便更好的运用到我们的实际操作中来。

关键词：基于MPI；并行蚁群算法；研究

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2012）32-7720-02

随着并行蚁群算法在人们日常生活中的运用，人们对并行蚁群算法的研究也越来越多，蚁群算法的优化具有相当优良的分布式计算机制以及和其它的计算方法相结合的特点。所以在很大程度上提高了我们对于算术的运用，蚁群算法对于其它算法的发展也有很大的帮助，自它出现，激发了其它算法的不断发展，丰富了我们日常的运用。同时，蚁群算法的的应用领域非常的广泛，已经扩展到我们的工程优化、经济管理、军事运筹等。并行蚁群算法以其自身的优势已经渗透到我们生活的方方面面，通过准确的研究可以让蚁群算法更好的得到运用和发展。

1　蚁群算法的相关定义及原理

1）蚁群算法是一种概率算法，这种形式的算法是将数据通过迭代的方式从而获得最优解，在不停的迭代过程中，当次数达到一定程度的时候，算法就会收敛，直到算法中的最优解的值保持稳定。　MPI，指的是一个工业化的标准，宽泛的意义上来讲只是某种规范的代表。并不是具体的物体的实现，是专门为了大规模的信息传递而制定的。

2）基本蚁群算法原理为蚂蚁在运动的前进过程当中，　凭借着在路径上的信息素浓度进行的路径选择。　于此同时，蚂蚁也会在所经过的路径上释放出大量的信息素，对应的在路径上经过的蚂蚁越多，释放的信息素浓度越高被蚂蚁选择的概率就越大，　因此可知，由多数蚂蚁组成的集体行为便可以表现出一种信息正反馈现象。蚂蚁群就是通过这种行为从而找到到达目的地的最佳方位。蚁群算法求解TSP问题的最优路径其实也就是求解一个完全加权的有向图中的最优路径问题。

2　基于MPI的并行蚁群算法的相关内容

1）并行蚁群算法的可行性和重要性。蚁群算法其实从本质上来讲就是一个并行系统。蚂蚁算法沿袭的是蚂蚁在搜集食物中的并行行为，在这种行为中慢慢的形成了蚂蚁寻找食物的最佳和最短的路线，蚁群算法就是运用了蚂蚁在运动过程中的这种并行机制。蚁群算法在现在可以说是一种智能化的优化算法，为我们的算术上带来了很多的便利，成功解决了多种复杂的问题。蚂蚁算法拥有的这种天然的并行性，让这种算法的每一次的迭代都是在独立的进行解的构建，也为蚂蚁算法的其它机能打下了良好的基础　但是并行蚂蚁算法现在的现实情况很大限度仅仅只能解决小规模的问题，然而对于大规模问题的蚁群优化算法的研究和应用却不太多。然而在很多地方，蚂蚁算法的实际应用问题却是针对大规模问题有的时候甚至是超大规模问题，可见，并行蚂蚁算法的发展是势在必行，这有利于我们简易我们的算法和对问题的理解，方便我们的日常生活。

2）并行蚂蚁算法的策略抉择。并行蚂蚁算法的策略是多种多样，而策略的选择也直接关系着最后的结果。所以说，并行策略的选择对于蚁群算法的并行实现至关重要。就目前所拥有的集中策略来说，可以说是各有千秋，例如：并行独立蚁群，这种方法的有点就在于各个处理器之间都不需要互联，方法简单，直观。每一个的蚁群的主参数的数值都有差别，其中任何一个参数都可以通过处理器进而加以更改。并行交互蚁群，这种方法和其它方法的最大不同之处就在于在特定的迭代中，蚁群可以通过相互之间的信息的交换将其中最好最准确的信息传递发哦其它的蚁群，然而由于不同的蚁群方法有不同的衡量标准，所以对于究竟哪个蚁群表现的最好没有具体的判定。还有呢就是并行蚂蚁，在这种方法里，每个蚂蚁都拥有一个自己的处理器来构建相应的解决方式，并行蚂蚁这种方法的通信量相对适中，如若遇到大量的通信量数据，就会相应的增加蚂蚁的个数。算法的每个步骤完成之后，其中的每一个蚂蚁都需要更新它的最新值。从而满足相应信息素的更新规则。

3）基于并行蚁群算法的火力分配优化。基于MPI并行蚁群的火力分配优化是最新研究发现的一种算法，主要问题是针对高端军事化的一个解决范畴，旨在解决的是在面对各式各类的外界威胁时可以及时的想出解决的方法，及时应对。火力分配优化的结果可以在有限的时间内处理大量的问题。所以说，对火力开发的细致研究是至关重要的，相对于传统的蚁群解决方法，通常很难在短时间里面得到结果，而且对于性对复杂的问题也很难在快的时间里解决，而且，蚁群优化算法正是应对这种问题而存在的，它兼具了并行计算，信息的正面反馈和启发式搜索的特点，但是在它的实际研发上还是存在着大量的困难的，相信在以后的道路上以后一定会越来越好。

3　基于MPI的并行蚁群算法的应用

1）基于MPI的并行蚁群算法在交通系统中的应用，随着社会的快速发展，一系列的社会问题也随之浮出水面，城市拥挤、交通拥堵情况日益严重。如何解决交通道路的拥挤问题关系到人、物、信息各个方面。严重影响到我们的日常生活。VRP也就是车辆路径问题是现在出现最多的问题，通过蚂蚁算法与VRP的具体应用，将蚂蚁算法的特性，在觅食过程中会选择从蚁穴出发到达食物源最短的路径。在此之中，也要考虑到多方面的因素，诸如多条道路的交通问题。通过使用并行蚁群算法我们可以将道路的选择看作是如火热选择最快的道路。这也就要求我们在运用的过程中药充分的利用道路的利用率，合理的分配交通的流量。这也就能在最大程度的缓解交通的压力，便民便利。

2）基于MPI的并行蚁群算法在数据挖掘中的应用，利用蚂蚁算法的特性可以解决数据挖掘中的各式各样的问题，例如聚类问题、分类问题以及关联规则方面的问题等等，通过将蚂蚁算法里的蚂蚁当作是搬运工，将一系列的数据搬运到合适的地点从而形成聚类，通过这一类的方法，将数据排列的有自组织、自适应、高效率等等特点。而对于分类问题，则是将当前所面临的不同问题进行了不同的分析，利用蚂蚁算法的并行化策略，对信息数据进行深入的挖掘，得到数据也更加的准确。在针对聚类问题的信息挖掘上，数据对象在空间的分布状态对聚类的结果会产生一定的影响，假设网格中的两个对象A和B之间的距离为D，则可以用欧式距离进行计算，假若A和B是同一类型的对象，那么他们的距离D就是0，如果对象不一样，距离D则是1，这样我们就可以得到二进制的相异度的矩阵。这种方法可以通过蚂蚁之间对象的空间分布状态从而达到信息相互作用的目的。

4　总结

基于MPI的并行蚁群算法的发展在不断的提升，对我们的生活品质和生活结构有着巨大的改变。随着社会的告诉发展，无论是科技还是学术都在不断的发展，不断的向前，我们对于蚂蚁算法也要有一个细致的了解，才能更好的掌握这门技术为自己找取更大的便利。通过这篇文章我们整体的概括了并行蚂蚁算法的理论知识，相应的内容以及它的广泛应用。让我们从整体上对蚂蚁算法进行了解，再逐步的进行深入的了解，将知识运用到实际的生活当中，给我们的生活增添色彩。

参考文献：

[1]　段海滨.蚁群算法原理及其应用[M].北京：科学出版社，2005.

[2]　张静乐.具有新型遗传特征的蚁群算法[J].微计算机信息，2006，2（2）：261-263.

[3]　章春芳.自适应的并行蚁群算法及其应用[D].扬州：扬州大学，2006.

[4]　段海滨，王道波，朱家强，等.蚁群算法理论及应用研究的进展[J].控制与决策，2004（12）.

[5]　陈云飞，刘玉树，范杰，等.火力优化分配问题的小生境遗传蚂蚁算法[J].计算机运用，2005（1）.