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

Expected performance of ant colony optimization model

作　　者：喻学才[1] 张田文[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机应用研究》2009年第4期1311-1312,1315,共3页Application Research of Computers

摘　　要：用蚁群优化求解组合优化问题时,信息素模型及其规则可能使问题的各组件之间的竞争失衡,从而有可能使蚁群搜索停滞在最差解。研究了蚁群优化求解k-最小生成树问题时的信息素模型及其更新规则对性能的影响,对原有的信息素模型作出了新的解释:直接表示k-最小生成树问题的边被选择的概率。基于新的信息素模型设计了一种新的解的构造过程,这种过程不仅产生可行解,也产生不可行解;同时研究了使用可行解和全部解更新信息素模型时算法的迭代期望质量随时间的增减情况,其结果表明,只使用可行解时迭代期望质量随时间连续降低,而使用全部解时算法最终收敛到最优解。为了使用全部解,定义不可行解的不可行量及扩展目标函数使可行解的目标值不变而不可行解的目标值大于任何一个可行解。When applying ant colony optimization metaheuristic to combinatorial problems, the combination of an ant colony optimization algorithm and a problem instance may be not a CBS and the pheromone model and its updating rule may make the algorithm converge at the worst solution. This paper developed an ant colony optimization model for solving the k-minimum spanning tree problem which was NP-hard and analyzed the influence of two updating rules of the pheromone model over the performance of the ant colony optimization algorithm. AnaLysis showed that the iteration expected quality of the algorithm con- tinuously decreased with the former while increasing with the latter. To utilize all solutions produced, the augmented objective of each infeasible solution was defined in such way that the objective value of each feasible solution was not altered and that of each infeasible solution must be greater than that of the worst feasible solution.

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]