拉丁超立方体抽样遗传算法求解图的二划分问题

摘要：

图的二划分问题是一个典型的NP-hard组合优化问题,在许多领域都有重要应用.近年来,传统遗传算法等各种智能优化方法被引入到该问题的求解中来,但效果不理想.基于理想浓度模型的机理分析,利用拉丁超立方体抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,并在分析图二划分问题特点的基础上,结合局部搜索策略,给出了一个解决图二划分问题的新的遗传算法,称之为拉丁超立方体抽样遗传算法.通过将该算法与简单遗传算法和佳点集遗传算法进行求解图二划分问题的仿真模拟比较,可以看出新的算法提高了求解的质量、速度和精度.

关键词：图的二划分、遗传算法、拉丁超立方体抽样、拉丁超立方体抽样遗传算法

所属期刊栏目：26

分类号：TP301(计算技术、计算机技术)

资助基金：安徽省高校省级自然科学研究项目KJ2007B152;安徽省教育厅自然科学研究项目2005KJ222,2006KJ046B;安徽省高校青年教师资助计划项目2007jq1180

在线出版日期：2009-11-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：927-930