[1]周本达,陈明华.随机化均匀设计混合遗传算法求解图的二划分问题[J].智能系统学报,2009,4(1):91-94.
ZHOU Ben-da,CHEN Ming-hua.Solving the 2-way graph partitioning problem using a genetic algorithm based on randomized uniform design[J].CAAI Transactions on Intelligent Systems,2009,4(1):91-94.
点击复制
ZHOU Ben-da,CHEN Ming-hua.Solving the 2-way graph partitioning problem using a genetic algorithm based on randomized uniform design[J].CAAI Transactions on Intelligent Systems,2009,4(1):91-94.
随机化均匀设计混合遗传算法求解图的二划分问题
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
4
期数:
2009年第1期
页码:
91-94
栏目:
学术论文—人工智能基础
出版日期:
2009-02-25
- Title:
- Solving the 2-way graph partitioning problem using a genetic algorithm based on randomized uniform design
- 文章编号:
- 1673-4785(2009)01-0091-04
- 分类号:
- TP18
- 文献标志码:
- A
- 摘要:
- 图的二划分问题是一个典型的NP-hard组合优化问题，在许多领域都有重要应用.近年来，传统遗传算法等各种智能优化方法被引入到该问题的求解中来，但效果不理想.基于理想浓度模型的机理分析，利用随机化均匀设计抽样的理论和方法, 对遗传算法中的交叉操作进行了重新设计，并在分析图的二划分问题特点的基础上，结合局部搜索策略，给出了一个解决图的二划分问题的新的遗传算法.通过将该算法与简单遗传算法和佳点集遗传算法进行求解图的二划分问题的仿真模拟比较, 可以看出新的算法提高了求解的质量、速度和精度.
- Abstract:
- 2-way graph partitioning is a typical NPhard combinatorial optimization problem, and has widespread applications in many domains. Many intelligent optimization methods, including traditional genetic algorithms, were recently introduced to solve this problem, but the results have not been ideal. Following analysis of the mechanisms of the ideal density model, the genetic algorithm (GA) crossover operation was redesigned using the principles and methods of randomized uniform sampling design. Furthermore, a new GA for solving 2-way graph partition was formulated. Simulations which compared results from this method with simple GA and Good Point GA for solving the 2-way graph partitioning problem showed that the new GA has superior speed, accuracy, and precision.
- 参考文献/References:
-
［1］KANG S J, MOON B R.A hybrid genetic algorithm for multi-way graph partitioning［C］//Proc Genetic & Evolutionary Computation Conf(GECCO-2000). San Francisco，USA: Morgan Kaufmann, 2000: 159-166.
［2］HENDRICKSON B, KOLDA T G. Graph partitioning models for parallel computing［J］. Parallel Compute, 2000, 26(12): 1519-1534.
［3］张 铃,张 钹. 遗传算法机理的研究［J］.软件学报，2000, 11(7): 945-952.
ZHANG Ling，ZHANG Bo. Research on the mechanism of genetic algorithms［J］. Journal of Software, 2000, 11(7): 945-952.
［4］张 铃,张 钹. 佳点集遗传算法［J］.计算机学报，2001, 24(9): 917-922.
ZHANG Ling， ZHANG Bo. Good point set based genetic algorithm［J］. Chinese Journal of Computers, 2001, 24(9): 917-922.
［5］华罗庚, 王 元. 数论在近似分析中的应用［M］. 北京: 科学出版社，1978.
［6］SOPER A J, WALSHAW C, CROSS M.A combined evolutionary search and multilevel optimization approach to graph partitioning［J］. Journal of Global Optimization, 2000, 29(2): 225-241.
［7］王兆军, 张润楚. 均匀设计抽样的偏差［J］. 数学物理学报，1997，17（2）：207-217.
?WANG Zhaojun, ZHANG Runchu. Descripency of uniform desingn sampling［J］. Acta Mathematica Scientia, 1997，17（2）：207-217.
［8］WALSHAW C.The graph partitioning archive［EB/OL］. ［2008-04-15］. http://staffweb.cms.gre.ac.uk/~wc06/partition/.
- 相似文献/References:
-
[1]康 琦,汪 镭,刘小莉,等.基于群体智能框架理念的遗传算法总体模式描述[J].智能系统学报,2007,2(5):42.
KANG Qi,WANG Lei,LIU Xiao-li,et al.General mode description genetic algorithms based on a framework of swarm intelligence[J].CAAI Transactions on Intelligent Systems,2007,2():42.
[2]马 炫,张亚龙.基于遗传算法的大规模矩形件优化排样[J].智能系统学报,2007,2(5):48.
MA Xuan,ZHANG Ya-long.A genetic algorithm for the layout of large scale rectang ular parts[J].CAAI Transactions on Intelligent Systems,2007,2():48.
[3]徐 雄.人工情感的进化控制系统实现[J].智能系统学报,2008,3(2):135.
XU Xiong.Implementation of an evolutionary control system based on artificial emotion[J].CAAI Transactions on Intelligent Systems,2008,3():135.
[4]刘 胜,李高云,孙天英.一种基于种群多样度的实数编码并行遗传算法[J].智能系统学报,2008,3(5):423.
L IU Sheng,L I Gao-yun,SUN Tian-ying.A real coding parallel genetic algorithm based on diversity of population[J].CAAI Transactions on Intelligent Systems,2008,3():423.
[5]张 涛,费树岷,李晓东.基于GARBF神经网络及边界不变特征的车辆识别[J].智能系统学报,2009,4(3):278.
ZHANG Tao,FEI Shu-min,LI Xiao-dong.Vehicle recognition using boundary invariants and a genetic algorithm trained radial basis function neural network[J].CAAI Transactions on Intelligent Systems,2009,4():278.
[6]秦世引,高书征.面向救援任务的地面移动机器人路径规划[J].智能系统学报,2009,4(5):414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
QIN Shi-yin,GAO Shu-zhen.Path planning for mobile rescue robots in disaster areas with complex environments[J].CAAI Transactions on Intelligent Systems,2009,4():414.[doi:10.3969/j.issn.1673-4785.2009.05.005]
[7]周树德,孙增圻.遗传算法中的联结关系[J].智能系统学报,2009,4(6):483.[doi:10.3969/j.issn.1673-4785.2009.06.003]
ZHOU Shu-de,SUN Zeng-qi.Linkage in genetic algorithms[J].CAAI Transactions on Intelligent Systems,2009,4():483.[doi:10.3969/j.issn.1673-4785.2009.06.003]
[8]程显毅,巩向普.改进的模糊C-均值算法在医学图像分割中的应用[J].智能系统学报,2010,5(1):80.
CHENG Xian-yi,GONG Xiang-pu.An improved fuzzy Cmeans algorithm for segmentation of medical images[J].CAAI Transactions on Intelligent Systems,2010,5():80.
[9]王斐,闻时光,吴成东,等.基于模糊逻辑的多移动机器人自适应协作围捕[J].智能系统学报,2011,6(1):44.
WANG Fei,WEN Shiguang,WU Chengdong,et al.Adaptive cooperative hunting for multiple mobile robots based on fuzzy logic[J].CAAI Transactions on Intelligent Systems,2011,6():44.
[10]夏琳琳,张健沛,初妍.计算智能在移动机器人路径规划中的应用综述[J].智能系统学报,2011,6(2):160.
XIA Linlin,ZHANG Jianpei,CHU Yan.An application survey on computational intelligence for path planning of mobile robots[J].CAAI Transactions on Intelligent Systems,2011,6():160.
备注/Memo
收稿日期：2008-05-12.
基金项目：安徽省高校省级自然科学研究资助项目(KJ2007B152)；安徽省教育厅自然科学研究资助项目（2005KJ222，2006KJ046B）；安徽省高校青年教师资助计划资助项目（2007jql180）.
作者简介：
周本达，男，1974生，副教授.主要研究方向为遗传算法、多Agent系统.发表学术论文10余篇.
陈明华，男，1954生，教授，主要研究方向为遗传算法、统计建模中的大样本理论.
更新日期/Last Update:
2009-03-24