[1]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.
Copy

Solving the 2-way graph partitioning problem using a genetic algorithm based on randomized uniform design

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 4 Number of periods: 2009 1 Page number: 91-94 Column: 学术论文—人工智能基础 Public date: 2009-02-25
Title:
Solving the 2-way graph partitioning problem using a genetic algorithm based on randomized uniform design
Author(s):
ZHOU Ben-da1; CHEN Ming-hua2
1.Department of Mathematics and Physics, West Anhui University, Lu’an 237012, China; 2.Department of Computer Science and Technology, West Anhui University, Lu’an 237012, China
Keywords:
2-way graph partitioning;  genetic algorithm;  randomized uniform design
CLC:
TP18
DOI:
-
Abstract:
2-way graph partitioning is a typical NPhard 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/.
Similar References:

Memo

-

Last Update: 2009-03-24

Copyright © CAAI Transactions on Intelligent Systems