第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 ]设计了一个新的
·92 智能系统学报 第4卷 交叉操作，提高了GA的效率，这种算法称为佳点集 3,4,5,6,7,8划分为1=13,7}和2=2.4,5， 遗传算法.但在佳点个数n取定后，佳点集的选取是 6,8两个子集 确定的，不带随机性.为了克服此不足，在充分分析 22适应度函数 文献[3]中理想浓度模型的基础上，基于随机化均 根据图的二划分定义及划分原则，因为图中所 匀设计理论对遗传算法中的交叉操作进行重新设 有边的权值和是一个常量，求属于不同分块的顶点 计，并结合图的二划分问题的局部优化技术]，提 之间的边的权值之和的最小值问题，实际上也就是 出了解决图的二划分问题的基于随机化均匀设计的 求同一分块内各顶点之间的边的权值之和的最大值 混合遗传算法.为了表明算法的有效性，对图划分测 问题，据此定义适应度函数如下： 试网站提供的标准测试算例进行了计算机仿真，结 fx)=g(x)-r·u·gx) (4) 果表明新算法在收敛速度和最优解的质量上均优于 其中：8W二是”化.以，与y同属于同个分 简单遗传算法和佳点集遗传算法， 块；w(,y)表示顶点，与y间的权值，在简单无向 1随机化均匀设计方法 图中定义为 号与y间有边； 随机化均匀设计过程如下☑ .0 否则 1)对于固定的和n∈N,选取均匀设计的生成 式(4)中第2项为惩罚函数，0<r<1为惩罚系数 向量(n:h,h,…,h; 它根据个体违反约束条件的程度而定，越大，约束 0 1… 条件要求越严格，否则约束条件比较宽松；“为解是 2)从多项分布 1 1 中抽取 否为合法解的判定系数，可定义为 nn n 0x为合法解： 1-个独立同分布样本1,2，…几.1，并令几，=0 否则 3)令X=(x,x2,…x,k=l,2.n其中 23选择算子 k·h,+n ,k=1,…nj=1,1(1) 采用轮盘赌选择算子.即将所有染色体的适应 这里{x表示取x的小数部分，称式1)给出的点集 值之和看作一个轮盘，每个染色体根据其适应值的 Xk=X=(x,…,),k=1,n}2) 大小划分在轮盘中所占据的范围.然后旋转轮盘，当 为随机化均匀设计点集」 轮盘停下来时，指针所对应的染色体即被选中，完成 称这种方法为在1维单位立方体C=0,11 一次选择.重复上述过程，直到选择到所需要的染色 体个数为止 中选n个点的随机化均匀设计(random ized un而m design,RUD)方法 24基于随机化均匀设计的杂交算子 设在传统的G4算法基础上，在进行过复制后 若记ag =1,nj=1,,t则称 对池中的染色体随机选择两个A1、A,进行随机化 点集 均匀设计交叉操作.一般情况下是令： An={as=(a1,…,a),k=1,n} 3 A =(d.ad), 为均匀设计点集) A2=(G,6,G, 实际上，这种随机化均匀设计是通过对均匀设 J=fila≠a,1≤i≤4 计进行模1随机平移而得到的.这种平移总共有n 不妨设A1,A2的前t个分量不同，后1-个分 个，而每组样本点个数为n这样正好将全体n个格 量相同，令模式 子都以同等机会抽到，因此，它具有较好的搜索能 H=%,为，|i∈J,x=*:i连J,=d 力.而且文献[7的定理22证明了随机化均匀设 由A、A2进行交叉不管是单点交叉或是多点交 计点集的偏差比佳点集小，并且它能随机地取到所 叉)，其子孙必属于H,于是要在“高适应度模式为 有的格子，所以其搜索能力更强，故会有比佳点集更 祖先的家族方向”上搜索出更好的样本，就是要在 好的表现 H中搜索出更好的样本.随机化均匀设计交叉操作 就是要在H上利用随机化均匀设计方法找出好样 2遗传算子 本来 21染色体编码 对图的二划分问题，由于码串0101与1010表 基于图的二划分问题，这里采用二进制编码.例 示的划分相同，在这里对于两个染色体A1、A2首先 如x=01011101表示将顶点集合V=(1,2, 直接比较，记录下不同值的位置存于J:然后将A2 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
交叉操作 ,提高了 GA的效率 ,这种算法称为佳点集 遗传算法. 但在佳点个数 n取定后 ,佳点集的选取是 确定的 ,不带随机性. 为了克服此不足 ,在充分分析 文献 [ 3 ]中理想浓度模型的基础上 ,基于随机化均 匀设计理论对遗传算法中的交叉操作进行重新设 计 ,并结合图的二划分问题的局部优化技术 [ 6 ] ,提 出了解决图的二划分问题的基于随机化均匀设计的 混合遗传算法. 为了表明算法的有效性 ,对图划分测 试网站提供的标准测试算例进行了计算机仿真 ,结 果表明新算法在收敛速度和最优解的质量上均优于 简单遗传算法和佳点集遗传算法. 1 随机化均匀设计方法 随机化均匀设计过程如下 [ 7 ] : 1)对于固定的 t和 n∈N,选取均匀设计的生成 向量 ( n∶h1 , h2 , …, ht ) ; 2)从多项分布 0 1 … n - 1 1 n 1 n … 1 n 中抽取 t - 1个独立同分布样本 η1 ,η2 , …,ηt - 1 ,并令 ηt = 0; 3)令 Xk = ( xk1 , xk2 , …, xk t ) , k = 1, 2, …, n. 其中 xk j = k·hj +ηj n , k = 1, …, n, j = 1, …, t. (1) 这里 { x}表示取 x的小数部分 ,称式 (1)给出的点集 χk = { Xk = ( xk1 , …, xk t ) , k = 1, …, n} (2) 为随机化均匀设计点集. 称这种方法为在 t维单位立方体 C t = [ 0, 1 ] t 中选 n个点的随机化均匀设计 ( random ized uniform design, RUD)方法. 若记 ak j = k·hj n , k = 1, …, n, j = 1, …, t,则称 点集 An = { ak = ( ak1 , …, ak t ) , k = 1, …, n} (3) 为均匀设计点集 [ 7 ] . 实际上 ,这种随机化均匀设计是通过对均匀设 计进行模 1随机平移而得到的. 这种平移总共有 n t 个 ,而每组样本点个数为 n,这样正好将全体 n t 个格 子都以同等机会抽到 , 因此 , 它具有较好的搜索能 力. 而且文献 [ 7 ]的定理 2. 2证明了随机化均匀设 计点集的偏差比佳点集小 ,并且它能随机地取到所 有的格子 ,所以其搜索能力更强 ,故会有比佳点集更 好的表现. 2 遗传算子 2. 1 染色体编码 基于图的二划分问题 ,这里采用二进制编码. 例 如 x = [0 1 0 1 1 1 0 1 ]表示将顶点集合 V = { 1, 2, 3, 4, 5, 6, 7, 8}划分为 V1 = { 1, 3, 7}和 V2 = { 2, 4, 5, 6, 8}两个子集. 2. 2 适应度函数 根据图的二划分定义及划分原则 ,因为图中所 有边的权值和是一个常量 ,求属于不同分块的顶点 之间的边的权值之和的最小值问题 ,实际上也就是 求同一分块内各顶点之间的边的权值之和的最大值 问题 ,据此定义适应度函数如下 : f ( x) = g ( x) - r·u·g ( x). (4) 其中 : g ( x) = ∑1≤i≤j≤n w ( vi , vj ) , vi 与 vj 同属于同个分 块; w ( vi , vj )表示顶点 vi 与 vj间的权值 ,在简单无向 图中定义为 w ( vi , vj ) = 1 vi 与 vj间有边; 0 否则. 式 (4)中第 2项为惩罚函数 , 0 < r < 1为惩罚系数 , 它根据个体违反约束条件的程度而定 , r越大 ,约束 条件要求越严格 ,否则约束条件比较宽松; u为解是 否为合法解的判定系数 ,可定义为 u = 0 x为合法解; 1 否则. 2. 3 选择算子 采用轮盘赌选择算子. 即将所有染色体的适应 值之和看作一个轮盘 ,每个染色体根据其适应值的 大小划分在轮盘中所占据的范围. 然后旋转轮盘 ,当 轮盘停下来时 ,指针所对应的染色体即被选中 ,完成 一次选择. 重复上述过程 ,直到选择到所需要的染色 体个数为止. 2. 4 基于随机化均匀设计的杂交算子 设在传统的 GA算法基础上 ,在进行过复制后 , 对池中的染色体随机选择两个 A1、A2 进行随机化 均匀设计交叉操作. 一般情况下是令 : A1 = ( a 1 1 , a 1 2 , …, a 1 l ) , A2 = ( a 2 1 , a 2 2 , …, a 2 l ) , J = { i | a 1 i ≠ a 2 i , 1 ≤ i ≤ l}. 不妨设 A1 , A2 的前 t个分量不同 ,后 l - t个分 量相同 ,令模式 H = { (x1 , x2 , …, xl ) | i ∈J, xi = 3 ; i | J, xi = a 1 i }. 由 A1、A2 进行交叉 (不管是单点交叉或是多点交 叉 ) ,其子孙必属于 H ,于是要在“高适应度模式为 祖先的家族方向 ”上搜索出更好的样本 ,就是要在 H 中搜索出更好的样本. 随机化均匀设计交叉操作 就是要在 H 上利用随机化均匀设计方法找出好样 本来. 对图的二划分问题 ,由于码串 0101与 1010表 示的划分相同 ,在这里对于两个染色体 A1、A2 首先 直接比较 ,记录下不同值的位置存于 J1 ;然后将 A2 ·92· 智 能 系 统 学 报 第 4卷
第1期 周本达，等：随机化均匀设计混合遗传算法求解图的二划分问题 ·93· 各位取反，再同A,进行比较，记录下不同值的位置 法终止并返回Ube 存于2，取、中长度小的为J,不妨令对应的模 局部搜索算法通过对当前的顶点的适应值的比 式仍为H不同值的位置构成一个维立方体，记为 较来选择交换，对于顶点的适应值的定义既考虑了 H,然后在H上进行随机化均匀设计抽样，即要在t 顶点在同一个子集中连接的边数又考虑了顶点的 维单位立方体C'=0,1了中进行选n个点的随机 度.这样可以避免过早地陷入局部最优解，有利于在 化均匀设计交叉操作，具体如下： 更大的范围内搜索全局最优解 1)对于固定的t和n∈N,选取均匀设计的生成 向量(n:h,h,h,: 4求解图的二划分问题的随机化均匀 01…n- 设计混合遗传算法 2)从多项分布11 1 中抽取t- nn n 给定交叉概率R和突变概率A后，随机化均 1个独立同分布样本1,2，…，.1，并令几，=0 匀设计混合遗传算法(genetic algorithm based on ran- 3令X=(x1,2,x,k=1,2,n dom ized unif6 m design,RGA)如下： k·h+n ,k=1,…n,j=1…t 1)每次进行遗传操作，以概率/∑方复制A, 其中是A,的适应度值 令交叉后产生的n个后代中第k个染色体 2以概率R对其进行随机化均匀设计交叉操 B=(,…),其中： 作产生n个后代，n为待定参数 4n, m年J 5 3)以概率进行变异遗传操作 ((%）,m=5∈J,1≤j≤1 4)对新产生的染色体进行局部搜索操作， 式(5)中：1≤k≤nm,1≤m≤l(a)表示：若a的小数 5)把经过上述操作后得到的染色体都放到染 部分小于05，则(a〉=0：否则(a〉=1 色体池中，对新得到的染色体，计算其适应度值.若 这样在其“家族中，产生了n个后代依次取 假定染色体的容量一定，当染色体的个体超过容量 k=1,2,n所得)，取其中适应值最大者域最大 时，就将适应度小的染色体从池中删去或按a%进 的几个)，作为交叉后的后代.上述交叉操作，称为 行删除人. 随机化均匀设计交叉操作」 6)进行上述的遗传算法至第T代(T是预先给定 25变异算子 的常数)，在算法执行过程中记录适应度最大的染色 变异操作为：取染色体A,随机整数iA=(a, 体，即为所求的染色体，再进行解码得到最优解 ,,a)变异成新的染色体B=(a,,a.1, b,a+1,a,其中b=a 5 实验结果及分析 3局部搜索技术 为了表明算法的有效性，分别用简单遗传算法、 佳点集遗传算法和随机化遗传算法在同样条件下， 顶点的适应值定义为：一个顶点的适应值 即在P43.0GPC机器上，采用Matlab7.0计算平台 入=g/(g+),其中：g为与顶点同一个子集中 对国际标准数据库中的算例（见表1）进行仿真， 的顶点与连接的边的权值和数，b为与不同的另 结果如表2所示. 一个子集中的顶点与连接的边的权值和数.如果 表1算例数据 g+b=0,那么设定入，=1则求解图的二划分问题 Table 1 Exam ple data 的局部搜索算法如下： 顶点 顶点 顶点 1)对于一个划分y,2),其中：V1U3=V, 问题 顶点数边数目 平均度最大度最小度 V1∩'2=0令Ue=(W1,V2）. Queen5 5 25 160 640 16 12 2)计算V中各个顶点的适应值 David 3)选择V中适应值最小的顶点设为m,再在不 少 406 467 82 1 Miles250 128 387 302 含m的子集中随机地选取另一个顶点n交换m和 16 0 Queen10 10 100 1470 1470 35 27 n,改写1和2.若新得的划分好于U,则改写 Queen13 13 169 3328 1803 48 36 Ube女 Queen15 15 225 51802302 56 42 4)若没达到设定的交换次数，则转2)，否则算 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
各位取反 ,再同 A1 进行比较 ,记录下不同值的位置 存于 J2 ,取 J1、J2 中长度小的为 J,不妨令对应的模 式仍为 H. 不同值的位置构成一个 t维立方体 ,记为 H ′,然后在 H ′上进行随机化均匀设计抽样 ,即要在 t 维单位立方体 C t = [ 0, 1 ] t 中进行选 n个点的随机 化均匀设计交叉操作 ,具体如下 : 1)对于固定的 t和 n∈N,选取均匀设计的生成 向量 ( n∶h1 , h2 , …, ht ) ; 2)从多项分布 0 1 … n - 1 1 n 1 n … 1 n 中抽取 t - 1个独立同分布样本 η1 ,η2 , …,ηt - 1 ,并令 ηt = 0; 3)令 Xk = ( xk1 , xk2 , …, xk t ) , k = 1, 2, …, n, xk j = k·hj +ηj n , k = 1, …, n, j = 1, …, t. 令交叉后产生的 n 个后代中第 k 个染色体 , B k = ( b k 1 , b k 2 , …, b k l ) ,其中 : b k m = a 1 m , m | J, 〈xk j〉, m = tj ∈ J, 1 ≤ j ≤ t. (5) 式 (5)中 : 1≤k≤n, 1≤m ≤l,〈a〉表示 :若 a的小数 部分小于 0. 5,则〈a〉= 0;否则〈a〉= 1. 这样在其“家族 ”中 ,产生了 n个后代 (依次取 k = 1, 2, …, n所得 ) ,取其中适应值最大者 (或最大 的几个 ) ,作为交叉后的后代. 上述交叉操作 ,称为 随机化均匀设计交叉操作. 2. 5 变异算子 变异操作为 :取染色体 A,随机整数 i, A = ( a1 , a2 , …, al ) 变异成新的染色体 B = ( a1 , a2 , …, ai - 1 , bi , ai + 1 , …, al ) ,其中 bi = ai . 3 局部搜索技术 顶点的适应值定义为 :一个顶点 j的适应值 λj = gj / ( gj + bj ) ,其中 : gj 为与顶点 j同一个子集中 的顶点与 j连接的边的权值和数; bj为与 j不同的另 一个子集中的顶点与 j连接的边的权值和数. 如果 gj + bj = 0,那么设定 λj = 1. 则求解图的二划分问题 的局部搜索算法如下 : 1) 对于一个划分〈V1 , V2 〉,其中 :V1 ∪V2 = V, V1 ∩ V2 = ª. 令 Ubest =〈V1 , V2 〉. 2) 计算 V中各个顶点的适应值. 3) 选择 V中适应值最小的顶点设为 m ,再在不 含 m 的子集中随机地选取另一个顶点 n. 交换 m 和 n,改写 V1 和 V2 . 若新得的划分好于 Ubest , 则改写 Ubest . 4) 若没达到设定的交换次数 ,则转 2) ,否则算 法终止并返回 Ubest . 局部搜索算法通过对当前的顶点的适应值的比 较来选择交换 ,对于顶点的适应值的定义既考虑了 顶点在同一个子集中连接的边数又考虑了顶点的 度. 这样可以避免过早地陷入局部最优解 ,有利于在 更大的范围内搜索全局最优解. 4 求解图的二划分问题的随机化均匀 设计混合遗传算法 给定交叉概率 pc 和突变概率 pm 后 ,随机化均 匀设计混合遗传算法 ( genetic algorithm based on ran2 dom ized uniform design, RGA)如下 : 1)每次进行遗传操作 ,以概率 fi /∑fi 复制 Ai , 其中 fi 是 Ai 的适应度值. 2)以概率 pc 对其进行随机化均匀设计交叉操 作 (产生 n个后代 , n为待定参数 ). 3)以概率 pm 进行变异遗传操作. 4)对新产生的染色体进行局部搜索操作. 5)把经过上述操作后得到的染色体都放到染 色体池中 ,对新得到的染色体 ,计算其适应度值. 若 假定染色体的容量一定 ,当染色体的个体超过容量 时 ,就将适应度小的染色体从池中删去 (或按 a%进 行删除 ). 6)进行上述的遗传算法至第 T代 (T是预先给定 的常数 ) , 在算法执行过程中记录适应度最大的染色 体,即为所求的染色体,再进行解码得到最优解. 5 实验结果及分析 为了表明算法的有效性 ,分别用简单遗传算法、 佳点集遗传算法和随机化遗传算法在同样条件下 , 即在 P4 3. 0G PC机器上 ,采用 Matlab7. 0计算平台 对国际标准数据库 [ 8 ]中的算例 (见表 1)进行仿真 , 结果如表 2所示. 表 1 算例数据 Table 1 Exam ple da ta 问题 顶点数 边数目 顶点 平均度 顶点 最大度 顶点 最小度 Queen5_5 25 160 6. 40 16 12 David 87 406 4. 67 82 1 M iles250 128 387 3. 02 16 0 Queen10_10 100 1 470 14. 70 35 27 Queen13_13 169 3 328 18. 03 48 36 Queen15_15 225 5 180 23. 02 56 42 第 1期 周本达 ,等 :随机化均匀设计混合遗传算法求解图的二划分问题 ·93·
·94- 智能系统学报 第4卷 表2SGA、GGA和UGA的实验结果比较 问题的特点，结合局部搜索技术，提出了新的解决图 Table 2 Experien tal result of SGA,GGA and UGA 二划分问题的混合遗传算法，克服了佳点集遗传算 问题 算法Nc 0 法中佳点选取不带随机性的缺点，实例仿真得出的 SGA 60 6312293 51.31 结果表明了新算法的有效性和先进性.今后的工作 Queen5 5 GGA 60 60681.85 11.48 是进步分析该方法的深层次的数学基础以及该方法 RGA 60 6000000 1.40 在组合优化问题中的有效性和先进性， SGA 83 9401 590 149.72 David GGA 82 91.08 477 6263 参考文献： RGA 82 87.88 3.26 2396 [1]KANG S J,MOON B R.A hybrid genetic algorithm or SGA 14 35.20 994 13819 multiway graph partitoning [C]//Proc Genetic Evolu- Miles250 GGA 18 47.14 13.57 6534 tionary Computation Conf(GECCO-2000).San Francisco, RGA 4 1030 420 2089 USA:Morgan Kaufann,2000:159-166 SGA 49551568218115619 [2 ]HENDR CKSON B,KOLDA T G Graph partitioning mod- Queen10 10 GGA 50051564 292 47.90 els for parallel computing[J]Parallel Compute,2000,26 RGA 49549500000 376 (12):1519-1534 SGA1188127920420917473 [3张铃，张钱.遗传算法机理的研究[J]软件学报， Queen1313GGA1232013642047.0712579 2000,11(7):945-952 RGA10921092301.711874 ZHANG Ling,ZHANG Ba Research on the mechanis of SGA193020663057.4417608 genetic algorithms[J].Joumal of Sofware,2000,11(7): Queen1515GGA2148226480324412358 945-952 RGA168016853011741537 [4]张铃，张钱.佳点集遗传算法[J]计算机学报， 2001,24(9):917-922 ZHANG L ing ZHANG Ba Good point set based genetic 其中：SGA为简单遗传算法；GGA为佳点集遗 algorithm [J ]Chinese Joumal of Computers,2001,24 传算法；RGA为基于随机化均匀设计的混合遗传算 (9):917-922 法.算法参数为：群体规模为100交叉和变异概率： [5华罗庚，王元.数论在近似分析中的应用M]北京 P。=09,Pm=005:最大迭代代数为200算法中惩 科学出版社，1978 [6]SOPER A J,WALSHAW C,CROSS M.A combined evolu- 罚系数： tionary search and multilevel optm ization approach o graph r=1.)I max(1.)n. partitioning[J]Joumal of Gbbal Opti ization,2000,29 (2):225-241 n为顶点个数；当(max|y,l,|2)-n/2)≤5时 [7正兆军，张润楚.均匀设计抽样的偏差[J]数学物理 u=0,否则u=1为避免遗传算法的随机性，对每个 学报，1997,17(2)：207-217 标准算例在同一台机器上进行连续100次计算，记 WANG Zhaojun,ZHANG Runchu Descrpency of unifm 录如下结果： desingn sampling[J].Acta Mathematica Scientia,1997,17 (2):207-217. 1)100次运行中求得的最好解记为Ne)和 [8 ]WALSHAW C.The graph partitioning archive EB/OL ] 100次运行所得解的平均值记为Ve;2)100次运 [2008-04-15 ]http:/staftweb ans gre ac uk/~wc06/ 行求得解的标准差记为·；3)100次运行中每次 partition/. 收敛时代数的平均值记为N) 作者简介 由表2可以得出：随机化均匀设计混合遗传算 周本达，男，1974生，副教授.主要 法每次得到的解均好于简单遗传算法和佳点集遗传 研究方向为遗传算法、多Agent系统.发 表学术论文10余篇 算法：而且在解的平均值、平均收敛代数、标准差等 指标上均好于简单和佳点集遗传算法.由此说明随 机化均匀设计混合遗传算法在搜索能力、收敛速度 以及避免早熟等各项指标上均好于简单遗传算法和 佳点集遗传算法， 陈明华，男，1954生，教授，主要研 6结束语 究方向为遗传算法、统计建模中的大样 本理论 文章以遗传算法的理想浓度模型”为基础，充 分分析其运行机理，利用统计抽样的理论和方法对 算法中的交叉操作进行了重新设计.分析图二划分 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved. http://www.cnki.net
表 2 SGA、GGA和 UGA的实验结果比较 Table 2 Exper im en ta l result of SGA, GGA and UGA 问题 算法 Nbest Vavg σ Navg SGA 60 63. 12 2. 93 51. 31 Queen5_5 GGA 60 60. 68 1. 85 11. 48 RGA 60 60. 00 0. 00 1. 40 SGA 83 94. 01 5. 90 149. 72 David GGA 82 91. 08 4. 77 62. 63 RGA 82 87. 88 3. 26 23. 96 SGA 14 35. 20 9. 94 138. 19 M iles250 GGA 18 47. 14 13. 57 65. 34 RGA 4 10. 30 4. 20 20. 89 SGA 495 515. 68 21. 81 156. 19 Queen10_10 GGA 500 515. 64 2. 92 47. 90 RGA 495 495. 00 0. 00 3. 76 SGA 1 188 1 279. 20 42. 09 174. 73 Queen13_13 GGA 12 320 1 364. 20 47. 07 125. 79 RGA 1 092 1 092. 30 1. 71 18. 74 SGA 1 930 2 066. 30 57. 44 176. 08 Queen15_15 GGA 2 148 2 264. 80 32. 44 123. 58 RGA 1 680 1 685. 30 11. 74 15. 37 其中 : SGA 为简单遗传算法 ; GGA 为佳点集遗 传算法 ; RGA为基于随机化均匀设计的混合遗传算 法. 算法参数为 :群体规模为 100;交叉和变异概率 : Pc = 0. 9, Pm = 0. 05;最大迭代代数为 200. 算法中惩 罚系数 : r = 1 - ( 1 2 ) | max( | V1 | , | V2 | ) - n /2 | , n为顶点个数; 当 (max | V1 | , | V2 | ) - n /2 ) ≤5时 u = 0,否则 u = 1. 为避免遗传算法的随机性 ,对每个 标准算例在同一台机器上进行连续 100次计算 ,记 录如下结果 : 1) 100次运行中求得的最好解 (记为 Nbest )和 100次运行所得解的平均值 (记为 Vavg ) ; 2) 100次运 行求得解的标准差 (记为 σ ) ; 3) 100次运行中每次 收敛时代数的平均值 (记为 Navg ). 由表 2可以得出 :随机化均匀设计混合遗传算 法每次得到的解均好于简单遗传算法和佳点集遗传 算法;而且在解的平均值、平均收敛代数、标准差等 指标上均好于简单和佳点集遗传算法. 由此说明随 机化均匀设计混合遗传算法在搜索能力、收敛速度 以及避免早熟等各项指标上均好于简单遗传算法和 佳点集遗传算法. 6 结束语 文章以遗传算法的“理想浓度模型 ”为基础 ,充 分分析其运行机理 ,利用统计抽样的理论和方法对 算法中的交叉操作进行了重新设计. 分析图二划分 问题的特点 ,结合局部搜索技术 ,提出了新的解决图 二划分问题的混合遗传算法 ,克服了佳点集遗传算 法中佳点选取不带随机性的缺点 ,实例仿真得出的 结果表明了新算法的有效性和先进性. 今后的工作 是进步分析该方法的深层次的数学基础以及该方法 在组合优化问题中的有效性和先进性. 参考文献 : [ 1 ] KANG S J, MOON B R. A hybrid genetic algorithm for multi2way graph partitioning [ C ] / /Proc Genetic & Evolu2 tionary Computation Conf ( GECCO22000). San Francisco, USA: Morgan Kaufmann, 2000: 1592166. [ 2 ]HENDR ICKSON B, KOLDA T G. Graph partitioning mod2 els for parallel computing[J ]. Parallel Compute, 2000, 26 (12) : 151921534. [ 3 ]张 铃 ,张 钹. 遗传算法机理的研究 [J ]. 软件学报 , 2000, 11 (7) : 9452952. ZHANG Ling, ZHANG Bo. Research on the mechanism of genetic algorithms[J ]. Journal of Software, 2000, 11 (7) : 9452952. [ 4 ]张 铃 ,张 钹. 佳点集遗传算法 [ J ]. 计算机学报 , 2001, 24 (9) : 9172922. ZHANG L ing, ZHANG Bo. Good point set based genetic algorithm [ J ]. Chinese Journal of Computers, 2001, 24 (9) : 9172922. [ 5 ]华罗庚 , 王 元. 数论在近似分析中的应用 [M ]. 北京 : 科学出版社 , 1978. [ 6 ] SOPER A J, WALSHAW C, CROSSM. A combined evolu2 tionary search and multilevel op timization app roach to graph partitioning[J ]. Journal of Global Op tim ization, 2000, 29 (2) : 2252241. [ 7 ]王兆军 , 张润楚. 均匀设计抽样的偏差 [J ]. 数学物理 学报 , 1997, 17 (2) : 2072217. WANG Zhaojun, ZHANG Runchu. Descripency of uniform desingn samp ling[J ]. Acta Mathematica Scientia, 1997, 17 (2) : 2072217. [ 8 ]WALSHAW C. The graph partitioning archive [ EB /OL ]. [ 2008204215 ]. http: / /staffweb. cms. gre. ac. uk /～wc06 / partition /. 作者简介 : 周本达 ,男 , 1974生 ,副教授. 主要 研究方向为遗传算法、多 Agent系统. 发 表学术论文 10余篇. 陈明华 ,男 , 1954生 ,教授 ,主要研 究方向为遗传算法、统计建模中的大样 本理论. ·94· 智 能 系 统 学 报 第 4卷