摘要
遗传算法(GA)的运行机理及特点是具有定向制导的随机搜索技术,其定向制导的原则是:导向以高适应度模式为祖先的"家族"方向。以此结论为基础,利用均匀设计抽样(UDS)的理论和方法,对遗传算法中的交叉操作进行重新设计,并在分析图二划分问题特点的基础上,结合局部搜索策略,给出了一个求解图二划分问题的新遗传算法,称之为基于均匀设计抽样的混合遗传算法。最后将该算法与简单遗传算法和佳点集遗传算法进行比较。通过模拟比较,可以看出新算法不但提高了算法的求解速度和精度,而且避免了常有的早期收敛现象。
Genetic Algorithm （GA） is a guided random search and the guiding direction always aims at the family whose ancestors have schemata with high fitness. Based on the results, the crossover operation in GA was redesigned by using the principle of random uniform design sampling and combining the locale search strategy. Then a new GA called Genetic Algorithm based on Uniform Design Sampling （UDS） was presented. The new GA was applied to solve the 2-way graph partitioning problem. Compared to simple GA and good point GA for solving this problem, the simulation results show that the new GA has superiority in terms of speed and accuracy and overcomes premature convergence.
出处
《计算机应用》
CSCD
北大核心
2008年第11期2850-2852,共3页
journal of Computer Applications
基金
安徽省高校省级自然科学研究项目(KJ2007B152)
安徽省教育厅自然科学研究项目(2005KJ2222006KJ046B)
安徽省高校青年教师资助计划项目(2007jql180)
关键词
图的二划分
遗传算法
均匀设计抽样
均匀设计遗传算法
2-way graph partitioning
Genetic Algorithm （GA）
Uniform Design Sampling （UDS）
genetic algorithm based on uniform design sampling （UGA）
