第1期 李波，等：基于单亲遗传算法的动态设备布局仿真研究 ·77 因换位操作，在此，基因换位概率是针对每个单期布 5)PGA 局子串的，而不是针对一个父代个体.试验证明单期 ①精华选择策略：②提出染色体单期布局子串 布局子串换位概率P.取在[0.2,0.4]时较好，而且 基因换位操作算子，可避免不可行解；③没置单期子 在此区间变化时，算法效果差异不大 串基因换位概率，增加种群多样性：④变异功能类似 P取0.2并不是意味着父代种群中只有大约 于NLGA外层循环的功能 20%个体进行上面所说的基因换位操作，而是所有 单期布局子串中约有20%要进行基因换位，例如对 3仿真试验 5期的问题，种群大小为100，P.=0.2,并不是只有 仿真试验分3个部分，包括试验1：Rosenb- 20个左右的个体进行基因换位，而是有100×5× latt21中的算例，一个6台设备(23)5期的动态布 0.2=l00个单期布局子串上要进行基因换位，而约局问题；试验2：Conway和Venkataramanan4中的 100个单期布局子串，随机出现在100个个体的共算例，一个9台设备(33)5期的布局问题；以及试 500个单期布局子串上 验3：对从Dr.Jaydeep Balakrishnan处取得的数据 2.5选择操作 集进行仿真试验.测算时用Matlab编程，在PMl.5 本算法选择操作包括2个部分： 600MHz的机器上运行 )从上一代群体中的N个个体和本次遗传操 3.1试验1 作产生的N个新个体共2N个体中选择适应性较 此问题已知最优解的总成本为71187，文中提 强的N个个体，类似于截断选择法： 出的基于PGA的算法（种群大小400，进化代数50） 2)把1)中选出的N个个体按其适应度值排序， 可以成功搜索到该解（见图3），图4是PGA随机运 最好的个体直接进入下一代（精华策略），其余N- 行20次得到的结果，其中7次得到71187而且得到 1个个体通过轮盘赌进行选择，适应度值高的个体 了更多的最优布置方案.CVGA从随机初始种群无 有更大的机率被选择进入下一代种群 法得到71187的解.Rosenblatt的DP方法得到的 这种选择方法虽然在一定程度上损失了种群的 最优解为71984 多样化，但可以提高算法的搜索效率 72200 2.6变异操作 71800 变异操作是随机产生新的染色体个体，以概率 71400 Pm小于0.1)替换种群中较差的个体，然后进入下 71000 68101214161820 一代. 运行次数/次 2.7各种启发式方法在搜索操作策略方面的异同 图46台设备5期问题PGA20次运行结果 1)CVGA Fig 4 Result of PGA to 6 plant 5 period problem ①遗传操作采用单点交叉；②精华选择策略；③ 由图3的一次收敛过程看到，PGA算法在迭代 抑制性可行性判断 25代前收敛，图4中7次收敛于71187的平均收敛 2)NL GA 代数小于35代，说明了算法的效率.对于此问题 ①基于内外嵌套循环，内层实现GA操作，外层 CVGA在文献中没有给出其最优解对应的布局方 随机产生新个体来替换内层遗传操作后的差的个 案，SA得到的最优布局染色体为：p=135246 体，②GA操作采用点对点交叉；③交叉后采用抑制 135246153246153246653214,PGA算法得到了更 性方法检查可行性，④辅助小概率变异 多的最优布局方案，除了p还有：p1=642531 3)HGA 642531642351642351412356,p=642531642531 ①采用联赛选择方法；②采用乐观交叉方法，③ 642351462351412356等 考虑交叉操作范围：④双亲唯一替代法，⑤启发式 3.2试验2 CRAFT变异方法 此问题最优解未知，CVGA得到的最优总成本 4)SA 为608904（选择较好的个体组成初始种群），文中提 ①采用交换方法生成相邻布局方案；②深用冷 出的算法在初始种群随机产生的情况下可以得到总 却进度表来控制寻优过程，选择合适的初始温度和 成本为608619的布局方案（取种群大小400，进化 冷却率；③2层循环，外层确定参数，内层进行相邻 代数100)，收敛过程见图5.对此问题PGA运行20 布局方案的实现；④Metroplis准则的替代方法 次，得到结果见图6 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net因换位操作 ,在此 ,基因换位概率是针对每个单期布 局子串的 ,而不是针对一个父代个体. 试验证明单期 布局子串换位概率 Pc 取在[ 012 ,014 ]时较好 ,而且 在此区间变化时 ,算法效果差异不大. Pc 取 012 并不是意味着父代种群中只有大约 20 %个体进行上面所说的基因换位操作 ,而是所有 单期布局子串中约有 20 %要进行基因换位 ,例如对 5 期的问题 ,种群大小为 100 , Pc = 012 ,并不是只有 20 个左右的个体进行基因换位 ,而是有 100 ×5 × 012 = 100 个单期布局子串上要进行基因换位 ,而约 100 个单期布局子串 ,随机出现在 100 个个体的共 500 个单期布局子串上. 215 选择操作 本算法选择操作包括 2 个部分 : 1) 从上一代群体中的 N 个个体和本次遗传操 作产生的 N 个新个体共 2 N 个体中选择适应性较 强的 N 个个体 ,类似于截断选择法; 2) 把 1) 中选出的 N 个个体按其适应度值排序 , 最好的个体直接进入下一代(精华策略) ,其余 N - 1 个个体通过轮盘赌进行选择 ,适应度值高的个体 有更大的机率被选择进入下一代种群. 这种选择方法虽然在一定程度上损失了种群的 多样化 ,但可以提高算法的搜索效率. 216 变异操作 变异操作是随机产生新的染色体个体 ,以概率 Pm (小于 011) 替换种群中较差的个体 ,然后进入下 一代. 217 各种启发式方法在搜索操作策略方面的异同 1) CV GA ①遗传操作采用单点交叉 ; ②精华选择策略 ; ③ 抑制性可行性判断. 2) NL GA ①基于内外嵌套循环 ,内层实现 GA 操作 ,外层 随机产生新个体来替换内层遗传操作后的差的个 体 ; ②GA 操作采用点对点交叉 ; ③交叉后采用抑制 性方法检查可行性 ; ④辅助小概率变异. 3) H GA ①采用联赛选择方法 ; ②采用乐观交叉方法 ; ③ 考虑交叉操作范围 ; ④双亲唯一替代法 ; ⑤启发式 CRA F T 变异方法. 4) SA ①采用交换方法生成相邻布局方案 ; ②采用冷 却进度表来控制寻优过程 ,选择合适的初始温度和 冷却率 ; ③2 层循环 ,外层确定参数 ,内层进行相邻 布局方案的实现 ; ④Metroplis 准则的替代方法. 5) PGA ①精华选择策略 ; ②提出染色体单期布局子串 基因换位操作算子 ,可避免不可行解 ; ③设置单期子 串基因换位概率 ,增加种群多样性 ; ④变异功能类似 于 NL GA 外层循环的功能. 3 仿真试验 仿真试验分 3 个部分 ,包括试验 1 : Rosenb2 latt [ 2 ]中的算例 ,一个 6 台设备(2 ×3) 5 期的动态布 局问题 ;试验 2 :Conway 和 Venkataramanan [4 ] 中的 算例 ,一个 9 台设备(3 ×3) 5 期的布局问题 ;以及试 验 3 :对从 Dr1 J aydeep Balakrishnan 处取得的数据 集进行仿真试验. 测算时用 Matlab 编程 ,在PM2115 600 M Hz 的机器上运行. 311 试验 1 此问题已知最优解的总成本为 71187 ,文中提 出的基于 PGA 的算法(种群大小 400 ,进化代数 50) 可以成功搜索到该解(见图 3) ,图 4 是 PGA 随机运 行 20 次得到的结果 ,其中 7 次得到 71187 而且得到 了更多的最优布置方案. CV GA 从随机初始种群无 法得到 71187 的解. Rosenblatt 的 DP 方法得到的 最优解为 71984. 图 4 6 台设备 5 期问题 PGA20 次运行结果 Fig14 Result of PGA to 6 plant 5 period problem 由图 3 的一次收敛过程看到 ,PGA 算法在迭代 25 代前收敛 ,图 4 中 7 次收敛于 71187 的平均收敛 代数小于 35 代 ,说明了算法的效率. 对于此问题 CV GA 在文献中没有给出其最优解对应的布局方 案 , SA 得 到 的 最 优 布 局 染 色 体 为 : p = 135246 135246 153246 153246 653214 ,PGA 算法得到了更 多的 最 优 布 局 方 案 , 除 了 p 还 有 : p1 = 642531 642531 642351 642351 412356 , p2 = 642531 642531 642351 462351 412356 等. 312 试验 2 此问题最优解未知 ,CV GA 得到的最优总成本 为 608904 (选择较好的个体组成初始种群) ,文中提 出的算法在初始种群随机产生的情况下可以得到总 成本为 608619 的布局方案 (取种群大小 400 ,进化 代数 100) ,收敛过程见图 5. 对此问题 PGA 运行 20 次 ,得到结果见图 6. 第 1 期 李 波 ,等 :基于单亲遗传算法的动态设备布局仿真研究 · 77 ·