论文部分内容阅读
当人们使用传统寻优方法求解复杂组合优化问题遇到极大困难时,一些研究者另辟蹊径,开创性地通过模仿生物体或者生态系统的生态机制构造出了新的算法,这些算法包括进化算法(遗传算法、遗传规划、进化策略),人工神经网络,人工免疫系统,微粒群算法等,我们统称为智能优化算法。经过近半个世纪的实践已经证明,智能优化算法在解决复杂组合优化、复杂控制等问题时,具有一些传统方法不能比拟的优点:鲁棒性好,无需问题本身的详细信息,较好的搜索全局性等特点。蚁群算法是由意大利学者M.Dorigo等人提出的一种智能优化算法,它具有智能优化算法的优点,但它本身也存在着一些固有的不足,比如说易陷入局部收敛,收敛速度慢等。本文针对蚁群算法的这些不足,对以下几个方面进行了研究。(1)针对蚁群算法实现中有关参数取值对算法整体性能影响很大这一问题,我们对参数的合理取值区间进行了实验研究,通过保持其他参数值不变,只改变一个参数值的方法,我们统计得出了利于算法性能提高的参数取值;(2)对蚁群算法的收敛性进行了分析和证明,得出了几个可以改善算法整体性能的途径,如调整信息素的更新方式和调整蚂蚁选择路径的方式。(3)蚁群算法实现中,信息素挥发度系数太大与太小都不利于算法搜索整体性能的提高,为了改善搜索性能,我们引入了信息熵概念,在每次迭代完成后计算解种群的信息熵值,用此值来动态调整信息素挥发度系数的大小,调节算法搜索全局性与收敛速度的问题;基于此原理我们提出了一种动态自适应蚁群算法,通过对TSP问题的求解验证了其有效性。(4)提出了一种贪心蚁群算法来解决联盟生成问题,通过与解决此问题的几种其他算法进行实验比较,证明用贪心蚁群算法来解决Agent联盟生成问题是可行的和有效的,为联盟生成问题的求解提供了新的途径。