基于并行计算的遗传算法优化与应用开题报告

1. 研究目的与意义

在 1991 年法国巴黎召开的第一届人工智能会议上，意大利科学家 dorigo m 等人首次提出了蚁群算法的基本模型，经过了 5 年更深入的研究，他们发表了蚁群系统的相关文章[1]，着眼于蚁群算法的原理和模型,并与其它人工智能算法进行了比较。

后来，大量学者通过更周密的分析，发现蚁群算法具有诸如自组织、正反馈和分布式计算等方面的系统学特征，并以对称 tsp 为背景进行了模型方面的深入分析，进而为实际生产生活中遇到的大量问题提供了许多巧妙地可行性解决方案，也因此受到学术界和工业界的广泛关注。

自从 20 世纪 60 年代开始，并行计算的概念进入人们的视野，单纯依靠增加处理器个数提高性能的方式已经行不通了，应该采取其他措施来解决这一问题，于是并行计算显示出它独特的优势，一方面可以最大化发挥硬件的计算能力，减少延迟和提高吞吐量；另一方面成功实现了在高并发情况下同时满足多用户请求的处理[2].为了将并行计算更好的应用到解决更多实际问题中，尤其是集群环境下的高性能计算[3]，需要对给定算法和程序的并行性能进行分析，这也为下一步研究工作指明了前进道路。

2. 研究内容和预期目标

蚁群算法是一种仿生优化算法，因其鲁棒性强、易于与其他方法相结合以及优良的分布式计算机制等特点，从开始用于解决单一的旅行商问题，到现在已经逐渐渗透到更多领域。但是，该算法的最优解质量以及收敛性问题始终影响算法的效率和性能，基于强化信息素更新机制和新型信息素平滑机制的 ACOI 算法，在信息素更新阶段优化处理路径信息素浓度，提高蚁群算法得到的最优解质量，并提高其过程中的收敛速度。

3. 国内外研究现状

对于并行计算领域的不断深入研究于探索，使得各种适用于并行计算的并行编程环境更加完善，并且结合应用方向的不同体现出各自的优势，比如 MPI、Open MP、CUDA以及 Open CL 等，于是将并行计算应用于蚁群算法改进方面的研究引起更多学者的关注。

随着现代高性能计算中作业任务规模及复杂程度的剧增，这时再使用基本蚁群算法去解决这些问题，极有可能会导致其陷入局部最优解或运行时间过长，甚至会陷入死循环。ThiruvadyD 等人为了更好地实现资源约束调度问题，基于采矿供应链提出了两种元启发式算法，研究如何在由多个核心组成的共享内存架构上更好地并行化这些方法。#350;aban Glc等人为了应对自然资源约束调度问题，提出了蚁群优化算法和模拟退火算法，并研究如何最好的并行化这些方法及共享内存架构组成的几个核心。Xin S 等人通过对现代生活中出租车调度问题的考虑，提出并行蚁群优化算法对该模型进行优化。HuoY 等人为了优化有限机器可用性的置换 Flowshop 调度问题，提出了并行蚁群算法和并行蚁群局部搜索算法。当然，并行蚁群算法在其他方面的研究也收获了相当不错的成果。Zhang M 等人提出了一种改进的蚁群算法 3D-PACA。Ye N 等人提出了一种结合梯度下降局部搜索和分解并行计算框架的蚁群优化算法，从观测数据中构建大规模 FCM，进一步提高了现有 FCM 学习算法的效率。黄震华等人为了解决最大最小蚁群算法大规模和多迭代问题中运行时间长的缺点，以并行策略为基础实现了 MMAS 在 CPU-GPU 协同异构计算环境平台上的并发。Raam K V J 等人实现了基于 friss 自由空间传播模型算法，使得检测最优路径的速度更快，网络寿命更长。

4. 计划与进度安排

(1)针对基本蚁群算法易于陷入局部最优解致使算法停滞、收敛速度慢等问题，本文在其信息素更新阶段做出相应优化，在优化过程中，首先判断算法是否接近停滞，然后调整信息素浓度改变停滞状态。本文提出了一种基于基本蚁群算法的改进后的 acoi算法。

(2)针对 acoi 算法在单机环境下运行时间长、执行效率低的问题，提出了一种基于 open mp 并行框架的蚁群算法并行化方法，旨在提高在单机情况下执行效率，缩短算法执行时间。

(3)针对 open mp 在解决大规模问题时可扩展性受限的现状，利用 mpi 可以实现节点间并行的优势，在集群环境下提出基于mpi的acoi算法并行化方法，解决可扩展性问题的同时利用节点更强的计算能力减少算法执行时间。

5. 参考文献

[1] dorigom,maniezzov,colornia.theantsystem:optimizationbyacolonyof cooperating agents. ieee transactions on systems, man, and cybernetics，1996:29 – 41p.

[2] smariww,bakhouyam,fiores,etal.newadvancesinhighperformance computingandsimulation:parallelanddistributedsystems,algorithms,and applications.concurrencyamp;computationpracticeamp;experience,2016, 28(7):2024-2030p.

[3] 陈国良. 并行算法实践.高等教育出版社, 2004.