一种基于蚁群优化和遗传算法的粗粒度并行算法

摘要

本发明公开了一种基于蚁群优化和遗传算法的粗粒度并行算法，初始化m只蚂蚁的起始城市；蚁群周游一次，将周游结果作为GA的初始种群；蚁群周游一次，计算并记录本次周游具有最短路径的蚂蚁；运行GA的选择算子、GA的杂交算子、GA的变异算子；若迭代过程达到预先设定的迭代条件，计算并输出运行时间，输出最优解。经过大量计算表明，该并行算法的计算速度优于同等串行算法。

主权项

一种基于蚁群优化和遗传算法的粗粒度并行算法，其特征在于，包括以下步骤：A、各进程初始化：A1初始化m只蚂蚁的起始城市；A2蚁群周游一次，将周游结果作为GA的初始种群；B、各进程实施遗传蚁群合作方法：B1蚁群周游一次，计算并记录本次周游具有最短路径的蚂蚁；B2运行GA的选择算子；B3运行GA的杂交算子；B4运行GA的变异算子；B5计算并记录本次GA的最小个体MinGet i；B6如果本次周游蚁群最优蚂蚁的最短路径小于GA的最小个体的适应值，并且，这两者之中的较小值比上一次迭代所得的最小值小，用蚁群最优路径更新GA最小个体的染色体序列；如果本次迭代GA的最小个体的适应值小于蚁群最好蚂蚁的最短路径，并且，这两者之中的较小值比上一次迭代所得的最小值小，用GA最小个体的染色体序列更新蚁群最优路径；B7)如果迭代次数是一个素数的倍数，主进程收集各进程最优解，计算截止此次迭代具有最小值的进程号，并且将这个最小值及路径广播；B8)主进程判断此次迭代若达到实例最优解，则输出最优解及计算时间，强制退出程序；否则输出本次迭代最优解；B9)各进程对蚁群进行全局信息素更新；B10)如果迭代次数是另一个素数的倍数，则用蚁群的部分路径更新GA的部分染色体序列；C、重复步骤B，若迭代过程达到预先设定的迭代条件，转步骤D；.D、计算并输出运行时间，输出最优解。