基于遗传算法的智能蚁群算法优化设计
2023-03-26胡明蔡传军童绪军
胡明 蔡传军 童绪军
摘 要:为提升蚁群算法的寻优求解能力,文章使用Logistic函数对遗传算法进行了优化。在优化后的遗传算法中,对蚁群进行了交叉和变异操作,以实现蚁群算法的智能优化。为验证改进算法的性能,选择了100个城市进行寻优测试。实验结果表明,在采用遗传算法优化后,该方法使种群平均适应度得到了较好的提升。在寻优求解过程中,蚁群算法中蚂蚁信息素的分布密集浓度明显增加,具备较好的收敛性。同时,在相同迭代次数下,该方法获得的寻优路径也最短,具有较为显著的应用效果。
关键词:遗传算法;蚁群算法;交叉变异;遗传算子
中图分类号:TB472-4 文献标识码:A 文章编号:2095-9699(2023)06-0016-05
蚁群算法是群集智能与演化算法中的一种[1-2],用于模拟蚂蚁群在寻找巢穴到食物源之间最短路径的过程。蚁群算法通过模拟蚂蚁个体之间的协作来解决复杂的优化问题。在实际应用中,蚁群算法具有并行性和正反馈性等优点。然而,蚁群算法在应用时需要较多的参数[3],且缺乏先验知识指导,导致初始信息素匮乏,寻找最佳路径的时间较长,并且容易出现收敛过早或陷入局部极值的情况[4-5]。
为避免蚁群算法出现上述情况,许多学者研究了优化蚁群算法的方法。例如,侯军燕等[6]人提出了一种将评价权系数和权重系数引入蚁群算法的布局优化方法,通过添加优化参数来实现蚁群算法的智能优化。薛波等[7]人改进了蚁群算法与最短路优化方法,利用反馈搜索智能优化方法调整蚁群算法的全局信息素更新规则,实现蚁群算法的智能优化。虽然这两种方法都能实现蚁群算法的智能优化,但都存在运算时间过长的问题[8]。为了更好地提升蚁群算法的应用效果,本文设计了一种基于遗传算法的智能蚁群算法优化方法。
1 智能蚁群算法优化设计
1.1 蚁群算法运行机制
在自然环境中,蚂蚁的视力有限,但它们能够以最短路径找到食物源,即使路径中存在遮挡物,蚂蚁仍然能够绕过它们并到达食物源。单个蚂蚁在寻找食物时行为简单,但整个蚁群通过蚂蚁之间的协作可以完成复杂的任务[9]。研究表明,在蚁群运动过程中,蚂蚁会释放信息素,并通过信息素的浓度来引导蚂蚁朝着信息素浓度高的地方移动,最终到达食物源。图1展示了蚁群路径搜索的原理和机制。
以遗传算法种群的平均适应度作为衡量指标,测试优化前后适应度曲线的趋势,结果如图2所示。优化后的遗传算法种群的平均适应度值要高于优化前的,这表明本文方法对遗传算法进行了有效的优化处理。
以7个城市问题的信息素分布作为衡量指标,给出智能优化后蚁群算法寻优求解时的信息素分布图,结果如图3所示。优化后的蚁群算法在寻优求解时,城市3-6和3-5之间的信息素浓度明显不同于其他城市之间,可有效输出最优解。
验证本文方法寻优能力,以寻优最短距离作为指标,测试智能优化前后算法路径的变化情况,结果如图4所示。分析图4可知,智能优化后的蚁群算法蚂蚁行走路径简单且没有交叉绕远的现象,而未经优化的蚁群算法蚂蚁行走路径明显较多,这说明本文方法智能优化的蚁群算法可以选择最短路径,实现最优解。
进一步验证寻优求解效果,以最短路径作为指标,在不同迭代次数测试最短路径的数值。为了充分比较实验结果,同时与文献[6][7]的方法进行对比实验。实验结果如表1所示,三种方法的最短路径数随着迭代次数的增加而增加,但在迭代次数相同的情况下,本文方法得到的最优路径始终低于文献[6]和文献[7]的方法,这说明本文方法获取的寻优结果最佳。
以时间复杂度作为指标,验证三种方法在应用时的复杂性,结果如表2所示。结果表明,本文方法在应用过程中寻找最优解速度较快,所需时间较短。
测试三种方法在应用过程中的收敛性,结果如图5所示。在三种方法中,本文方法在寻优求解时其损失函数随着迭代次数的增加而降低,降低幅度最大。当迭代次数超过60次后,本文方法寻优求解的损失函数值趋近于0,说明本文方法得到的结果最为准确。
3 结论
文章针对蚁群算法存在的收敛和容易陷入局部极值情况,设计一种基于遗传算法的智能优化蚁群算法,通过对蚁群进行交叉和变异的操作来更新蚁群位置,使其能够准确快速地寻找最优解。经过实验验证,文中所使用的方法具有良好的应用效果,未来可以有效解决TSP问题。
参考文献:
[1]周天清,胡海琴,曾新亮. NOMA-