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

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

Expected performance of ant colony optimization model

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.