一个蚁群优化模型的期望性能分析

摘要：

用蚁群优化求解组合优化问题时, 信息素模型及其规则可能使问题的各组件之间的竞争失衡, 从而有可能使蚁群搜索停滞在最差解. 研究了蚁群优化求解k-最小生成树问题时的信息素模型及其更新规则对性能的影响,对原有的信息素模型作出了新的解释:直接表示k-最小生成树问题的边被选择的概率.基于新的信息素模型设计了一种新的解的构造过程,这种过程不仅产生可行解, 也产生不可行解;同时研究了使用可行解和全部解更新信息素模型时算法的迭代期望质量随时间的增减情况,其结果表明, 只使用可行解时迭代期望质量随时间连续降低, 而使用全部解时算法最终收敛到最优解.为了使用全部解, 定义不可行解的不可行量及扩展目标函数使可行解的目标值不变而不可行解的目标值大于任何一个可行解.

关键词：蚁群优化、扩展信息素更新、组合优化、k-最小生成树问题、扩展目标函数

所属期刊栏目：26

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2009-05-15（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：1311-1312,1315