互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

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


□ 喻学才 张田文

   (哈尔滨工业大学 计算机科学与技术学院, 哈尔滨 150001)
  
  摘 要:
  用蚁群优化求解组合优化问题时, 信息素模型及其规则可能使问题的各组件之间的竞争失衡, 从而有可能使蚁群搜索停滞在最差解。 研究了蚁群优化求解k-最小生成树问题时的信息素模型及其更新规则对性能的影响,对原有的信息素模型作出了新的解释:直接表示k-最小生成树问题的边被选择的概率。基于新的信息素模型设计了一种新的解的构造过程,这种过程不仅产生可行解, 也产生不可行解;同时研究了使用可行解和全部解更新信息素模型时算法的迭代期望质量随时间的增减情况,其结果表明, 只使用可行解时迭代期望质量随时间连续降低, 而使用全部解时算法最终收敛到最优解。为了使用全部解, 定义不可行解的不可行量及扩展目标函数使可行解的目标值不变而不可行解的目标值大于任何一个可行解。
  关键词:蚁群优化; 扩展信息素更新; 组合优化; k-最小生成树问题; 扩展目标函数
  中图分类号:TP301.6文献标志码:A
  文章编号:1001-3695(2009)04-1311-02
  
  Expected performance of ant colony optimization model
  
  YU Xue-cai, ZHANG Tian-wen
  
  (School of Computer Science & Technology, Harbin Institute of Technology, Harbin 150001, China)
  
  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. ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
摘自:计算机应用研究 Tags:蚁人
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017