·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卷