·76· 智能系统学报 第2卷 第P期 按顺序串接起来，得到子代个体（见图3）.这种遗传 操作的优点是，换位完成后，子代个体仍然是合法个 体，因为基因换位只是在每个单期布局子串上进行 (而每个单期布局子串都是一个合法的静态设备布 局方案)，而且实现起来十分便捷 461532 ×10 88r 8.6 …平均总成本 图2编码方法 最优总成本 8.4 Fig 2 Code 82 8.0 2.2评价函数 78 由于DPLP求的是目标函数的极小值.而GA 7.6 7.4 选择操作是保留适应度最大的个体，因而目标函数 72 不能直接作评价函数.因此，评价函数fw(v),如式 7.0 2030 40 50 (5)定义： 进化代数/代 1 fx(vA)=1+F(vA) (5) 图36台设备5期问题的收敛过程 "是一个染色体，代表某一种设备布置方案， Fig 3 Convergence of 6 plant 5period problem F(v代表布置v的总成本（包括每期的物流成本 这里提出的基因换位遗传操作与CVGA及 和设备移动成本). NLGA的交叉遗传操作完全不同.CVGA对2个个 2.3初始种群的产生 体用单点交叉(single point crossover)a).首先，从 本算法初始种群随机产生，具体过程如下： 父代染色体中随机选择2个，然后随机选择一个点 1)构造一维自然数数组a1a=123…n],(1, 进行交叉.尽管这种交叉操作很简单而且容易执行， 2,n代表设备编号)； 但可能会生成不可行的个体，必须改成可行的.例 2)随机选择a中一个元素存入v1x的1位置； 如：对于2个个体123456和125643，如果在第6个 3)删除a1×m中被选中的元素及其存储空间，即 位置交叉，就会产生2个新个体123453和125646. 变为a1×刘m.v=134…n](例如上一步选中元素 第1个个体中设备3出现2次，第2个个体中设备6 2. 出现2次，还要进行进一步的交换使它们可行，这无 重复执行，直到a为空，得到一个合法单期设备 疑增加了算法的复杂度.NLGA使用点对点交叉 布局子串ⅴ，然后把P(时期数)个单期布局子串按 (point-to-point crossover)s),2个串中每个位置上 顺序串接起来即得到DPLP的一个初始布局染色 的相应设备交换，生成许多子代设备布局(child lay 体 out),这样的结果是有些子代非法，但能保证部分子 2.4单期布局子串的基因换位操作 代可行，同样需要进行可行性检验（而且检验的运算 PGA的遗传操作包括基因换位、基因倒位、基 量很大).HGA采用DP方法进行交叉1，虽然保证 因移位等.单点基因换位是一次在一个个体上随机 了子代的可行性，当问题规模较大时，同样会遇到 选择2个位置的基因进行交换；多点基因换位是指， Rosenblatt提出的DP启发式算法遇到的问题，也 对预先给定的正整数w,取随机数i1(1≤)一次 就是将所有可行的单期静态布局全部纳入考虑范围 交换i对基因.该算法采用多点基因换位算子，w取 会很困难：不但操作较复杂，而且当选出的父代个数 int[设备台数/3]经验值) 为S=10时，一次DP交叉就要比较900个结果，交 I)基于PGA的单期布局子串基因换位 叉1000次的计算量可想而知，虽然这样交叉产生的 由于动态设备布局问题(DPLP)的特殊性，基 子代质量更好，但耗费的时间成本较高」 于PGA基因换位的原理，算法提出了一种适用于 2)单期布局子串基因换位概率的选择 DPLP的染色体单期布局子串的基因换位操作算 这里说的换位概率与传统GA中的交叉概率有 子.这种基因换位操作是先把一个DPLP的染色体 所不同，甚至与一般的PGA中的基因换位概率也 (父代个体)分解为单期的子串，然后在每个单期子 不尽相同.因为DPLP问题的特殊性，为了保证子 串上进行基因换位操作，换位完成后再把单期子串 代的可行性，在父代个体的每个单期子串上进行基 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 P 期 4 6 1 5 3 2 ↓ 4 6 1 5 3 2 图 2 编码方法 Fig12 Code 212 评价函数 由于 DPL P 求的是目标函数的极小值 ,而 GA 选择操作是保留适应度最大的个体 ,因而目标函数 不能直接作评价函数. 因此 ,评价函数 f N ( vk ) ,如式 (5) 定义 : f N ( vk ) = 1 1 + F( vk ) . (5) vk 是一个染色体 ,代表某一种设备布置方案 , F( vk ) 代表布置 vk 的总成本 (包括每期的物流成本 和设备移动成本) . 213 初始种群的产生 本算法初始种群随机产生 ,具体过程如下 : 1) 构造一维自然数数组 a1 ×n = [1 2 3 …n] , (1 , 2 , …, n 代表设备编号) ; 2) 随机选择 a 中一个元素存入 v1 ×n的 1 位置; 3) 删除 a1 ×n中被选中的元素及其存储空间 ,即 变为 a1 ×( n - 1) = [1 3 4 … n ] (例如上一步选中元素 2) . 重复执行 ,直到 a 为空 ,得到一个合法单期设备 布局子串 v,然后把 P(时期数) 个单期布局子串按 顺序串接起来即得到 DPL P 的一个初始布局染色 体. 214 单期布局子串的基因换位操作 PGA 的遗传操作包括基因换位、基因倒位、基 因移位等. 单点基因换位是一次在一个个体上随机 选择 2 个位置的基因进行交换 ;多点基因换位是指 , 对预先给定的正整数 uc ,取随机数 i(1 ≤i ≤uc ) 一次 交换 i 对基因. 该算法采用多点基因换位算子 , uc 取 int[设备台数/ 3 ](经验值) . 1) 基于 PGA 的单期布局子串基因换位 由于动态设备布局问题 (DPL P) 的特殊性 ,基 于 PGA 基因换位的原理 ,算法提出了一种适用于 DPL P 的染色体单期布局子串的基因换位操作算 子. 这种基因换位操作是先把一个 DPL P 的染色体 (父代个体) 分解为单期的子串 ,然后在每个单期子 串上进行基因换位操作 ,换位完成后再把单期子串 按顺序串接起来 ,得到子代个体(见图 3) . 这种遗传 操作的优点是 ,换位完成后 ,子代个体仍然是合法个 体 ,因为基因换位只是在每个单期布局子串上进行 (而每个单期布局子串都是一个合法的静态设备布 局方案) ,而且实现起来十分便捷. 图 3 6 台设备 5 期问题的收敛过程 Fig13 Convergence of 6 plant 5period problem 这里提出的基因换位遗传操作与 CV GA 及 NL GA 的交叉遗传操作完全不同. CV GA 对 2 个个 体用单点交叉 (single point crossover) [4 ] . 首先 ,从 父代染色体中随机选择 2 个 ,然后随机选择一个点 进行交叉. 尽管这种交叉操作很简单而且容易执行 , 但可能会生成不可行的个体 ,必须改成可行的. 例 如 :对于 2 个个体 123456 和 125643 ,如果在第 6 个 位置交叉 ,就会产生 2 个新个体 123453 和 125646. 第 1 个个体中设备 3 出现 2 次 ,第 2 个个体中设备 6 出现 2 次 ,还要进行进一步的交换使它们可行 ,这无 疑增加了算法的复杂度. NL GA 使用点对点交叉 (point2to2point crossover) [5 ] ,2 个串中每个位置上 的相应设备交换 ,生成许多子代设备布局(child lay2 out) ,这样的结果是有些子代非法 ,但能保证部分子 代可行 ,同样需要进行可行性检验(而且检验的运算 量很大) . H GA 采用 DP 方法进行交叉[ 6 ] ,虽然保证 了子代的可行性 ,当问题规模较大时 ,同样会遇到 Rosenblatt 提出的 DP 启发式算法遇到的问题 ,也 就是将所有可行的单期静态布局全部纳入考虑范围 会很困难 ;不但操作较复杂 ,而且当选出的父代个数 为 S = 10 时 ,一次 DP 交叉就要比较 900 个结果 ,交 叉1 000次的计算量可想而知 ,虽然这样交叉产生的 子代质量更好 ,但耗费的时间成本较高. 2) 单期布局子串基因换位概率的选择 这里说的换位概率与传统 GA 中的交叉概率有 所不同 ,甚至与一般的 PGA 中的基因换位概率也 不尽相同. 因为 DPL P 问题的特殊性 ,为了保证子 代的可行性 ,在父代个体的每个单期子串上进行基 · 67 · 智 能 系 统 学 报 第 2 卷