引用本文:陈明华,任哲,周本达.拉丁超立方体抽样遗传算法求解图的二划分问题[J].控制理论与应用,2009,26(8):927~930.[点击复制]
CHEN Ming-hua,REN Zhe,ZHOU Benda.Solving 2-way graph partitioning problem using genetic algorithm based on Latin hypercube sampling[J].Control Theory and Technology,2009,26(8):927~930.[点击复制]
拉丁超立方体抽样遗传算法求解图的二划分问题
Solving 2-way graph partitioning problem using genetic algorithm based on Latin hypercube sampling
摘要点击 2054  全文点击 2400  投稿时间：2008-05-17  修订日期：2008-11-27
查看全文  查看/发表评论  下载PDF阅读器
DOI编号  10.7641/j.issn.1000-8152.2009.8.CCTA080480
  2009,26(8):927-930
中文关键词  图的二划分  遗传算法  拉丁超立方体抽样  拉丁超立方体抽样遗传算法
英文关键词  2-way graph partitioning  genetic algorithm(GA)  Latin hypercube sampling(LHS)  genetic algorithm based on Latin hypercube sampling(LGA)
基金项目  安徽省高校省级自然科学研究项目(KJ2007B152); 安徽省教育厅自然科学研究项目(2005KJ222, 2006KJ046B); 安徽省高校青年教师资助计划项目(2007jql180).
作者单位E-mail
陈明华* 皖西学院计算机科学与技术系 mhchen@wxc.edu.cn 
任哲 合肥学院数理系  
周本达 皖西学院 数理系, 安徽 六安 237012  
中文摘要
      图的二划分问题是一个典型的NP-hard组合优化问题, 在许多领域都有重要应用. 近年来, 传统遗传算法等各种智能优化方法被引入到该问题的求解中来, 但效果不理想. 基于理想浓度模型的机理分析, 利用拉丁超立方体抽样的理论和方法, 对遗传算法中的交叉操作进行了重新设计, 并在分析图二划分问题特点的基础上, 结合局部搜索策略, 给出了一个解决图二划分问题的新的遗传算法, 称之为拉丁超立方体抽样遗传算法. 通过将该算法与简单遗传算法和佳点集遗传算法进行求解图二划分问题的仿真模拟比较, 可以看出新的算法提高了求解的质量、速度和精度.
英文摘要
      The 2-way graph partitioning problem is a typical NP-hard combination optimization, and is significantly applied to many fields of science and engineering. Recently, many intelligent optimization methods including the traditional genetic algorithm(GA) are employed to solve this problem, but the result is not effective as we desired. Based on the ideal density model, we redesign the crossover operation in GA by using the Latin hypercube sampling, and combined the result with the local search strategy of the 2-way graph partitioning problem; thus, presenting a new genetic algorithm based on Latin hypercube sampling for solving the 2-way graph partitioning problem. Comparison of simulation results in solving the 2-way graph partitioning problem with this new GA, the simple GA and the good point GA shows that this new method has superiority in speed, accuracy and precision.