求包含多边形的最小圆的遗传算法  

Genetic Algorithm for Finding the Smallest Circle Containing a Polygon

作　　者：朱平[1] 刘昌鑫[1] 

机构地区：[1]井冈山学院信息科学与传媒学院

出　　处：《微计算机信息》2007年第01S期313-314,共2页Control & Automation

基　　金：江西省教育厅资助项目(编号:赣教高字[2005]95)

摘　　要：对求包含平面多边形的最小圆问题提出了一种基于遗传算法的求解方法。文章讨论了遗传算法求解过程中的编码方案,算法中的个体是圆,个体表现型是一个三元数(x,y,r),其中x、y是圆心的两个坐标,r是圆半径,个体基因型编码方案对x,y采用二进制编码。文章还讨论了圆心的范围界定和适应度函数选取等方案,提出了加快收敛的方法。文章用实例验证了算法是有效的。A genetic algorithm for finding the smallest circle that contains a given plane polygon is presented in this paper. The scheme used in the algorithm on coding is discussed,the individual discussed in the algorithm is a circle, the corresponding phenotype of the individual is a triad （x,y,r）, with x,y are the coordinates of the center of the circle,and r is the radius of the circle, and the genotype coding of the individual is the binary coding ofx,y.The schemes used in the algorithm on obtaining the definite scope of the center of the circle and selecting fitness function are discussed, so is the method of the accelerating convergence. The results of a computational example show that the algorithm is effective.

关 键 词：遗传算法 最小圆 多边形 编码 

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