计算机工程 ›› 2007, Vol. 33 ›› Issue (21): 189-191.doi: 10.3969/j.issn.1000-3428.2007.21.067

• 人工智能及识别技术 • 上一篇    下一篇

一种新的求解最小权三角划分的免疫算法

杨 捷,李德华,金良海,王祖喜   

  1. (华中科技大学图像识别与人工智能研究所图像信息处理与智能控制教育部重点实验室,武汉 430074)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-11-05 发布日期:2007-11-05

Novel Immune Algorithm for Minimum Weight Triangulation

YANG Jie, LI De-hua, JIN Liang-hai, WANG Zu-xi   

  1. (State Commission Research Laboratory of Image Processing and Intelligent Control, Institute of Pattern Recognition and Artificial Intelligence, Huazhong University of Science and Technology, Wuhan 430074)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-11-05 Published:2007-11-05

摘要: 提出了一种基于自适应免疫遗传算法的求解最小权三角划分(MWT)问题的方案,通过自适应地调整疫苗库的进化和有选择地注射疫苗,提高了新算法的收敛速度和全局搜索能力,结合具体的MWT问题,给出了疫苗更新与注射算子构造的具体方案。仿真实验表明,新算法能产生比免疫算法更好的划分效果,尤其适合大规模点集,有较大的实用价值。

关键词: 最小权三角划分, 免疫算法, 疫苗, 计算机视觉

Abstract: The problem of minimum weight triangulation (MWT) is one of the most important issues in computer vision. This paper proposes an adaptive immune genetic algorithm(AIGA) to solve the problem. Based on the analysis of immune algorithm(IA) properties, the convergence speed of AIGA is faster than IA and the global search capability is improved with a self-adaptive adjustment method to the vaccine pool together with selected vaccination. According to the practical MWT, the strategies of updating and injecting a vaccine for the problem are both provided in the paper. Simulation results show that the algorithm performs better than IA in terms of quality of MWT, especially for the large scale of point cluster, and has good practical value.

Key words: minimum weight triangulation(MWT), immune algorithm(IA), vaccine, computer vision

中图分类号: