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