第4卷第1期 智能系统学报 Vol 4 Na 1 2009年2月 CAA I Transactions on Intelligent Systems Feb 2009 随机化均匀设计混合遗传算法求解图的二划分问题 周本达，陈明华2 (1.皖西学院数理系，安微六安237012：2皖西学院计算机科学与技术系，安徽六安237012) 摘要：图的二划分问题是一个典型的NP-had组合优化问题，在许多领域都有重要应用.近年来，传统遗传算法等 各种智能优化方法被引入到该问题的求解中来，但效果不理想.基于理想浓度模型的机理分析，利用随机化均匀设 计抽样的理论和方法，对遗传算法中的交叉操作进行了重新设计，并在分析图的二划分问题特点的基础上，结合局 部搜索策略给出了一个解决图的二划分问题的新的遗传算法.通过将该算法与简单遗传算法和佳点集遗传算法进 行求解图的二划分问题的仿真模拟比较，可以看出新的算法提高了求解的质量速度和精度 关键词：图的二划分；遗传算法；随机化均匀设计 中图分类号：TP18文献标识码：A文章编号：1673-4785(2009)01009104 Solving the 2-way graph partition ing problem using a genetic a lgorithm ba sed on random ized un iform design ZHOU Ben-da,CHEN M ing-hua (1 Deparment ofMathematics and Physics,West AnhuiUniversity,Lu'an 237012,China;2 Deparment of Computer Science and Technobgy,WestAnhuiUniversity,Lu'an 237012,China) Abstract:2way graph partitioning is a typicalNP-hard combinarial op ti izaton problem,and has widepread ap- plications in many domains Many intelligent optm ization methods,including traditonal genetic algorithm s,were recently introduced to solve this problem,but the results have not been ideal Following analysis of the mechaniss of the ideal density model,the genetic algorithm (GA)crossover operation was redesigned using the principles and methods of random ized unifom sampling design Furthemore,a new GA for solving 2way graph partition was for mulated Smulations which compared results from this method with smple GA and Good Point GA for solving the 2way graph partitioning problem showed that the new GA has superior speed,accuracy,and precision Keywords:2way graph partitioning genetic algorithm;random ized unifom design 图的二划分在数字电路系统的芯片划分、网络 能性较大.近年来，各种智能优化方法被引入到 管理，插件划分、分布式系统的数据流划分、并行系 该问题的求解中来。 统的信息流划分等许多领域有着重要应用.众所周 遗传算法四作为一种全局优化搜索算法，由于 知，图的二划分问题是一个NP-hard组合优化问题， 其本身所具有的全局收敛性和隐并行性，加之其简 因此精确求出最优解是不可能的，较为实际的方法 单易用、鲁棒性强，能够轻易地获得问题的全局最优 是尽快地发现其近似最优解.对于图的二划分向题， 解；，且问题越复杂，它相对于其他算法的优越性越明 己提出了许多启发式的搜索算法，其基本思想是寻 显，故十分适合解决这类问题.但应用经典遗传算法 找当前二划分子集中与其他各节点连接最少的节 求解图的划分问题时，求解时间长、成功率低.因而， 点，将其移动到另外的子集中，如此反复移动，直到 有必要针对具体问题的特点，对经典的遗传算法加 可行集不能改进为止.这种方法求解质量相对较高， 以改进 但对初始划分的依赖性很强，陷入局部最优解的可 文献[3对遗传算法(genetic algorithm,GA)中 的两个理论基石“模式定理”和“隐性并行性进行 收稿日期：200805-12 了分析，指出GA的本质是一个具有定向制导的随 基金项目：安徽省高校省级自然科学研究资助项目(K2007B152): 安徽省教育厅自然科学研究资助项目(2005KJ222, 机搜索技术，其定向制导的原则是：导向以高适应度 2006KJ046B);安徽省高校青年教师资助计划资助项目 (2007jq180). 模式为祖先的家族”方向.文献[4根据此机理，利 通信作者：周本达.Emai止bendazhou@l63cm 用数论中的佳点集理论和方法5)设计了一个新的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 4卷第 1期 智 能 系 统 学 报 Vol. 4 №. 1 2009年 2月 CAA I Transactions on Intelligent System s Feb. 2009 随机化均匀设计混合遗传算法求解图的二划分问题 周本达 1 ,陈明华 2 (1. 皖西学院 数理系 ,安徽 六安 237012; 2. 皖西学院 计算机科学与技术系 ,安徽 六安 237012) 摘 要 :图的二划分问题是一个典型的 NP2hard组合优化问题 ,在许多领域都有重要应用. 近年来 ,传统遗传算法等 各种智能优化方法被引入到该问题的求解中来 ,但效果不理想. 基于理想浓度模型的机理分析 ,利用随机化均匀设 计抽样的理论和方法 , 对遗传算法中的交叉操作进行了重新设计 ,并在分析图的二划分问题特点的基础上 ,结合局 部搜索策略 ,给出了一个解决图的二划分问题的新的遗传算法. 通过将该算法与简单遗传算法和佳点集遗传算法进 行求解图的二划分问题的仿真模拟比较 , 可以看出新的算法提高了求解的质量、速度和精度. 关键词 :图的二划分 ;遗传算法 ;随机化均匀设计 中图分类号 : TP18 文献标识码 : A 文章编号 : 167324785 (2009) 0120091204 Solving the 22way graph partition ing problem using a genetic algor ithm based on random ized un iform design ZHOU Ben2da 1 , CHEN M ing2hua 2 (1. Department ofMathematics and Physics, W est Anhui University, Lu’an 237012, China; 2. Department of Computer Science and Technology, W est Anhui University, Lu’an 237012, China) Abstract: 22way graph partitioning is a typ icalNP2hard combinatorial op tim ization p roblem, and haswidesp read ap2 p lications in many domains. Many intelligent op tim ization methods, including traditional genetic algorithm s, were recently introduced to solve this p roblem, but the results have not been ideal. Following analysis of the mechanism s of the ideal density model, the genetic algorithm ( GA) crossover operation was redesigned using the p rincip les and methods of random ized uniform samp ling design. Furthermore, a new GA for solving 22way graph partition was for2 mulated. Simulations which compared results from this method with simp le GA and Good Point GA for solving the 22way graph partitioning p roblem showed that the new GA has superior speed, accuracy, and p recision. Keywords: 22way graph partitioning; genetic algorithm; random ized uniform design 收稿日期 : 2008205212. 基金项目 :安徽省高校省级自然科学研究资助项目 ( KJ2007B152) ; 安徽 省 教 育 厅 自 然 科 学 研 究 资 助 项 目 ( 2005KJ222, 2006KJ046B) ;安徽省高校青年教师资助计划资助项目 (2007 jql180). 通信作者 :周本达. E2mail: bendazhou@163. com. 图的二划分在数字电路系统的芯片划分、网络 管理 ,插件划分、分布式系统的数据流划分、并行系 统的信息流划分等许多领域有着重要应用. 众所周 知 ,图的二划分问题是一个 NP2hard组合优化问题 , 因此精确求出最优解是不可能的 ,较为实际的方法 是尽快地发现其近似最优解. 对于图的二划分向题 , 已提出了许多启发式的搜索算法 ,其基本思想是寻 找当前二划分子集中与其他各节点连接最少的节 点 ,将其移动到另外的子集中 ,如此反复移动 ,直到 可行集不能改进为止. 这种方法求解质量相对较高 , 但对初始划分的依赖性很强 ,陷入局部最优解的可 能性较大. 近年来 ,各种智能优化方法 [ 122 ]被引入到 该问题的求解中来. 遗传算法 [ 1 ]作为一种全局优化搜索算法 ,由于 其本身所具有的全局收敛性和隐并行性 ,加之其简 单易用、鲁棒性强 ,能够轻易地获得问题的全局最优 解 ;且问题越复杂 ,它相对于其他算法的优越性越明 显 ,故十分适合解决这类问题. 但应用经典遗传算法 求解图的划分问题时 ,求解时间长、成功率低. 因而 , 有必要针对具体问题的特点 ,对经典的遗传算法加 以改进. 文献 [ 3 ]对遗传算法 ( genetic algorithm, GA )中 的两个理论基石“模式定理 ”和“隐性并行性 ”进行 了分析 ,指出 GA 的本质是一个具有定向制导的随 机搜索技术 ,其定向制导的原则是 :导向以高适应度 模式为祖先的“家族 ”方向. 文献 [ 4 ]根据此机理 ,利 用数论中的佳点集理论和方法 [ 5 ]设计了一个新的