聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽 首页聽|聽简介聽|聽编委会聽|聽征稿简则聽|聽英文刊聽|聽稿件流程聽|聽致读者聽|聽下载区聽|聽常见问题说明
拉丁超立方体抽样遗传算法求解图的二划分问题
Solving 2-way graph partitioning problem using genetic algorithm based on Latin hypercube sampling
摘要点击聽聽32聽聽全文点击聽聽21聽聽投稿时间:2008-5-17聽聽最后修改时间:2008-11-27
查看全文聽聽查看/发表评论聽聽下载PDF阅读器
DOI编号聽聽
聽聽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.
 
  聽聽聽聽聽聽聽聽聽 您是第292365位访问者  

主办单位:华南理工大学 中国科学院数学与系统科学研究院聽聽聽聽聽 单位地址:广州市天河区五山路381号

服务热线:020-87111464聽聽 传真:020-87111464聽聽 邮编:510640 聽聽Email: aukzllyy@scut.edu.cn
 

聽聽聽聽本系统由北京勤云科技发展有限公司设计