第1期 李波，等：基于单亲遗传算法的动态设备布局仿真研究 ·75 备4的运距为2，设备1到6的运距为3) 物流量而言最优的单期静态布局方案从多期的角度 来说很可能不是最优的.其他的一些方法比Rosen- blatt提出的DP启发式方法更好一些.如Urban提 出的一种最速下降成对交换(steepest-descent pair- wise exchange)启发式算法，这种方法类似于 图16台设备单期布局图例 CRAFT(Armour和Buffa)算法.Kusiak和Hera Fig.I 6 plant single period layout example gu1对不同的数学规划方法进行了研究.Conway 根据以上假设，结合Koopmans和Beckman的 和Venkataramanan,Balakrishnan和Cheng)用 二次分配模型四给出DPLP的数学模型： 遗传算法解决DPLP问题，Kaku和Mazzola使用了 minZ 禁忌搜索法(tabu search)l61.Baykasoglu和 Gindy!)针对DPLP问题提出一种模拟退火算法， 4Yan. 1) 利用Balakrishnan等的试验问题，他们证明这种算 法比Conway和Venkataramanan Balakrishnan和 S T. Xg=1J=1,m,1=1,“P,2 Cheng的GA算法要好.SA算法中的参数设置涉及 到确定初始温度(initial temperature)(可能在邻域 X=11=1,…n1=1“…P (3) 搜索neighborhood search中，会接受一个较差的解 Yul X(vgXsI, 决方案)，温度下降速度（一个较差方案的接受概率 ij,1=1,n,1=2,…,P (4) 下降)，以及反复次数(the number of iterations). 式中：P是总的时期数：n是设备台数；i,k代表布置 Balakrishnan等8)提出了一种混合遗传算法对 中的设备；j,1代表位置；f代表在第1期设备1到 DPLP进行优化计算 k物流运输成本（由于假设单位物流成本为1，f也 文中基于单亲遗传算法(partheno~genetic al- 就是设备间的物流量)；d是位置j到1间的运输距 gorithm,PGA)的机理提出一种针对DPLP优化算 离；X是0,1变量，代表在第t期将设备i定位于j 法，该算法采用在一条染色体进行遗传操作的进化 位置：Y是0,1变量，代表在第1期初将设备i从 方法.并使用前人曾用的算例对算法进行测算，同时 位置j移动到位置1；A代表在第1期将设备i从 与己有算法进行比较分析 位置j移动到位置1的移动成本。 2 基于单亲遗传算法的DPLP方法 模型是在规划的总时间内，最小化每期物流成 本与设备移动成本之和.式(1)是最小化目标函数： 单亲遗传算法(PGA)是李茂军、童调生等)提 约束(2)、(3)表示在每期中每台设备都要定位于一 出的一种序号编码遗传算法(GA).PGA不同于传 个位置，每个位置都有一台设备：约束(4)表示只有 统遗传算法的是取消了传统遗传算法(TGA)序号 在连续的2期中设备的位置发生改变时，0,1变量 编码的交叉算子，代之以仅在一条染色体上操作的 Y才能取到1. 基因重组等遗传算子，简化了遗传操作，提高了计算 在n设备、t时期问题中，要计算(n)'个布局 效率，并且不要求初始群体的多样性，也不存在“早 方案的总成本才能得出最佳的解决方法.即使6设 熟收敛”问题，并且李茂军等对PGA的全局收敛性 备5期的问题也有多于1.910“种布置方案.对于 进行了研究：文献证明PGA在列车占线问题、模式 这种大规模问题，最优化方法是不适用的，需要使用 聚类问题、车辆路径问题和物流配送问题等组合优 启发式算法来得到优化解决方案」 化问题的求解中明显优于传统遗传算法(TGA). Rosenblatt(1986)用动态规划(dynamic pro 2.1编码方案 gramming,DP)方法来解决DPLP问题).他把每 单亲遗传算法采用序号编码方式，对于n台设备t 一期视为DP中的阶段(stage),一个具体的单期布 时期的动态设备布局问题(DLP),先把单期的多行静 局方案(SPLP方案)则为DP中的状态变量(state). 态布局按照设备从上到下从左到右的顺序进行编码， 由于DP方法不适用于大规模的问题，所以他又提 然后再按时期数将各期的静态布局编码顺序串接起 出了启发式DP方法，但也不是十分有效.选择一些 来.以6台(23)设备P期为例，v=[2361451123 物流成本较低的单期布局方案来构成DP可能会有 45(叶461532]代表一个动态设备布局的染色体 更好的效果，但是，由于要考虑移动成本，对于固定 串，图2描述了其编码方法（以第P期为例） 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net备 4 的运距为 2 ,设备 1 到 6 的运距为 3) . 2 3 6 1 4 5 图 1 6 台设备单期布局图例 Fig. 1 6 plant single period layout example 根据以上假设 ,结合 Koopmans 和 Beckman 的 二次分配模型[1 ]给出 DPL P 的数学模型 : min Z = ∑ P t =1 ∑ n i =1 ∑ n j = 1 ∑ n k = 1 ∑ n l = 1 f tik d tjl X tij X tkl + ∑ p t =2 ∑ n i = 1 ∑ n j = 1 ∑ n k = 1 ∑ n l =1 A tijl Ytijl , (1) S1 T1 ∑ n i =1 Xtij = 1 , j = 1 , …, n , t = 1 , …, P , (2) ∑ n j = 1 Xtij = 1 , i = 1 , …, n , t = 1 , …, P, (3) Ytijl = X( t- 1) ij X til , i , j , l = 1 , …, n , t = 2 , …, P. (4) 式中 : P 是总的时期数; n 是设备台数; i , k 代表布置 中的设备; j , l 代表位置; f tik代表在第 t 期设备 i 到 k 物流运输成本(由于假设单位物流成本为 1 , f tik也 就是设备间的物流量) ; dtjl是位置 j 到 l 间的运输距 离; Xtij是 0 ,1 变量 ,代表在第 t 期将设备 i 定位于 j 位置; Ytijl 是 0 , 1 变量 ,代表在第 t 期初将设备 i 从 位置 j 移动到位置 l ; A tijl 代表在第 t 期将设备 i 从 位置 j 移动到位置 l 的移动成本. 模型是在规划的总时间内 ,最小化每期物流成 本与设备移动成本之和. 式 (1) 是最小化目标函数 ; 约束(2) 、(3) 表示在每期中每台设备都要定位于一 个位置 ,每个位置都有一台设备 ;约束 (4) 表示只有 在连续的 2 期中设备的位置发生改变时 ,0 ,1 变量 Ytijl才能取到 1. 在 n 设备、t 时期问题中 ,要计算 ( n !) t 个布局 方案的总成本才能得出最佳的解决方法. 即使 6 设 备 5 期的问题也有多于 119 ×10 14种布置方案. 对于 这种大规模问题 ,最优化方法是不适用的 ,需要使用 启发式算法来得到优化解决方案. Rosenblatt ( 1986) 用动态规划 ( dynamic p ro2 gramming ,DP) 方法来解决 DPL P 问题[ 2 ] . 他把每 一期视为 DP 中的阶段 (stage) ,一个具体的单期布 局方案(SPL P 方案) 则为 DP 中的状态变量(state) . 由于 DP 方法不适用于大规模的问题 ,所以他又提 出了启发式 DP 方法 ,但也不是十分有效. 选择一些 物流成本较低的单期布局方案来构成 DP 可能会有 更好的效果 ,但是 ,由于要考虑移动成本 ,对于固定 物流量而言最优的单期静态布局方案从多期的角度 来说很可能不是最优的. 其他的一些方法比 Rosen2 blatt 提出的 DP 启发式方法更好一些. 如 Urban 提 出的一种最速下降成对交换 (steepest2descent pair2 wise exchange ) 启 发 式 算 法 , 这 种 方 法 类 似 于 CRAF T (Armour 和 Buffa) 算法. Kusiak 和 Hera2 gu [3 ]对不同的数学规划方法进行了研究. Conway 和 Venkataramanan [4 ] ,Balakrishnan 和 Cheng [5 ] 用 遗传算法解决 DPL P 问题 , Kaku 和 Mazzola 使用了 禁 忌 搜 索 法 ( tabu search ) [6 ] . Baykasoglu 和 Gindy [7 ]针对 DPL P 问题提出一种模拟退火算法 , 利用 Balakrishnan 等的试验问题 ,他们证明这种算 法比 Conway 和 Venkataramanan、Balakrishnan 和 Cheng 的 GA 算法要好. SA 算法中的参数设置涉及 到确定初始温度 (initial temperat ure) (可能在邻域 搜索 neighborhood search 中 ,会接受一个较差的解 决方案) ,温度下降速度 (一个较差方案的接受概率 下降) ,以及反复次数 (the number of iterations) . Balakrishnan 等[8 ] 提出 了一种 混 合 遗 传 算 法 对 DPL P 进行优化计算. 文中基于单亲遗传算法 (part heno2genetic al2 gorithm ,PGA ) 的机理提出一种针对 DPL P 优化算 法 ,该算法采用在一条染色体进行遗传操作的进化 方法. 并使用前人曾用的算例对算法进行测算 ,同时 与已有算法进行比较分析. 2 基于单亲遗传算法的 DPL P 方法 单亲遗传算法(PGA) 是李茂军、童调生等[9 ] 提 出的一种序号编码遗传算法 ( GA) . PGA 不同于传 统遗传算法的是取消了传统遗传算法 ( T GA) 序号 编码的交叉算子 ,代之以仅在一条染色体上操作的 基因重组等遗传算子 ,简化了遗传操作 ,提高了计算 效率 ,并且不要求初始群体的多样性 ,也不存在“早 熟收敛”问题 ,并且李茂军等对 PGA 的全局收敛性 进行了研究 ;文献证明 PGA 在列车占线问题、模式 聚类问题、车辆路径问题和物流配送问题等组合优 化问题的求解中明显优于传统遗传算法( TGA) . 211 编码方案 单亲遗传算法采用序号编码方式 ,对于 n台设备 t 时期的动态设备布局问题(DPLP) ,先把单期的多行静 态布局按照设备从上到下从左到右的顺序进行编码 , 然后再按时期数将各期的静态布局编码顺序串接起 来.以 6 台(2 ×3)设备 P期为例 ,v= [2 3 6 1 4 5| 1 2 3 4 5 6| …| 4 6 1 5 3 2]代表一个动态设备布局的染色体 串 ,图 2 描述了其编码方法(以第 P期为例) . 第 1 期 李 波 ,等 :基于单亲遗传算法的动态设备布局仿真研究 · 57 ·