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

【Abstract】 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 continuously 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.更多还原