。378 北京科技大学学报 第33卷 St 知识获得. P=L+马W十马G十4H十 马R,十4K十4T十F (2) 2求解算法 宫x-1y: 板坯入库决策优化问题是一种离散型组合优化 (3) 问题，其规模大、约束多，属于P难题，很难用精确 Xi=0 V,i JS (4) 的方法进行求解.粒子群优化算法(PSO)源于对鸟 会X≤Q-hvj (5) 群捕食行为的研究，是一种进化计算技术 (evo lutionary con putation).该算法的实质是根据个 Ley V.i j (6) 体极值和全局极值来调整自己的飞行方向，从而寻 Wi-El,yij (7) 找到问题的最优解，算法通过速度更新公式和位置 G=Yij (8) 更新公式进行迭代演进.标准四算法主要运用于 H= 连续空间函数的优化，Kennedy等在1997年提出了 1 板坯的硬度等级属于库位的硬度等级 针对离散优化问题的二进制粒子群算法 Vij 0 否则， (BPSO)191 (9) 对于本文考虑的板坯入库优化问题，采用标准 Ri= 粒子群算法进行求解得到的实验结果显示出较差的 板坯与库位中的板坯属于同一轧制计划 V.ij 收敛性，计算效果不佳.因此，本文借鉴文献[10中 0 否则， 利用带交换子和交换序的离散粒子群算法求解置换 (10) 流水车间的算法结构，同时引入遗传算法中的交叉 Ki- 和变异操作，构造了适合求解该问题的一种混合离 板坯与库位中的板坯属于同一种钢种 散粒子群算法(DPS)CM.该算法不需要经过遗 0 否则， 传算法中的选择过程、交叉配对过程，比传统遗传算 (11) 法更为简单、易实现，实验结果显示DPSO-(M算法 T- 不但具有良好的收敛性，其解的质量也一致性地优 板坯的轧制时间早于库位止的板坯 Vij 于普通遗传算法(GA. 0 否则， 2.1粒子编码 (12) 采用自然数编码方式.假设粒子种群数为PO? Fi- 入库批次中共有映板坯则粒子的每一维表示入 1 板坯库位的板坯属于固定匹配板坯 Vij 库批次中某一板坯的所选库位编号.每一块板坯对 0 否则， 应一个候选库位集合S假设集合S的个数为 (13) 目标函数(1)表示最大化入库批次中所有板坯 则第k个粒子可以表示为X=(,,,； 的综合匹配程度；式(2)表示板坯存放在库位中 ,),其中=12；P9∈S={↓2； 以.采用上述编码方式的每一个粒子都对应一个 的综合匹配程度；式(3)表示每块板坯都有且仅有 一个库位存放该板坯：式(4)表示每块板坯不能存 可行解，目标函数(1)作为适应值函数，则每个粒子 放在其候选库位集之外的库位中：式(5)保证每个 都对应目标函数的一个适应值. 库位所存板坯不能超过库位所允许存放的最大板坯 2.2粒子更新公式 数：式(6)式(8)分别表示板坯嘱于库位的长 粒子新位置由粒子自身速度、个体极值和全局 度隶属程度、宽度隶属程度和厚度隶属程度，其值将 极值决定，结合板坯入库优化问题自身的特点，借鉴 随着每块板坯的入库而发生动态变化，这里采用正 遗传算法中变异和交叉操作的思想，重新定义了位 态分布型隶属函数，其中参数和根据库位 置更新公式.其位置更新公式分三步完成每一步用 中己存板坯在长度、宽度和厚度的数量分布情况决 公式表示如下： 定：式(9)~式(13)分别表示HRKT和F的 M=☒￥b(XH在Il=l2,pop 取值情况：式(2)中权重系数4~的取值直接关 (14) 系到库位和垛位的选择是否合理，其值应根据专家 C=☒PE),=12；poP(15)北 京 科 技 大 学 学 报 第 33卷 s.t. Pij=a1 Lij+a2Wij+a3 Gij+a4Hij+ a5Rij+a6 Kij+a7 Tij+a8 Fij ( 2) ∑ M j=1 Xij=1, i ( 3) Xij=0, i, j∈ J, j Si ( 4) ∑ N i=1 Xij≤Qj-hj, j ( 5) Lij=e -( ( li -lj ) /blj ) 2 , i, j ( 6) Wij=e -( ( wi-wj) /bwj) 2 , i, j ( 7) Gij=e -( ( gi-gj) /bgj) 2 , i, j ( 8) Hij= 1 板坯 i的硬度等级属于库位 j的硬度等级 0, 否则, i, j ( 9) Rij= 1, 板坯 i与库位 j中的板坯属于同一轧制计划 0, 否则, i, j ( 10) Kij= 1 板坯 i与库位 j中的板坯属于同一种钢种 0, 否则, i, j ( 11) Tij= 1, 板坯 i的轧制时间早于库位 j上的板坯 0, 否则, i, j ( 12) Fij= 1, 板坯 i库位 j的板坯属于固定匹配板坯 0, 否则, i, j ( 13) 目标函数 ( 1)表示最大化入库批次中所有板坯 的综合匹配程度 ;式 ( 2)表示板坯 i存放在库位 j中 的综合匹配程度 ;式 ( 3)表示每块板坯都有且仅有 一个库位存放该板坯 ;式 ( 4)表示每块板坯不能存 放在其候选库位集之外的库位中;式 ( 5)保证每个 库位所存板坯不能超过库位所允许存放的最大板坯 数 ;式 ( 6) ～式 ( 8)分别表示板坯 i属于库位 j的长 度隶属程度 、宽度隶属程度和厚度隶属程度, 其值将 随着每块板坯的入库而发生动态变化, 这里采用正 态分布型隶属函数, 其中参数 blj、bwj和 bgj根据库位 中已存板坯在长度、宽度和厚度的数量分布情况决 定 ;式 ( 9) ～式 ( 13)分别表示 Hij、Rij、Kij、Tij和 Fij的 取值情况;式 ( 2)中权重系数 a1 ～ a8 的取值直接关 系到库位和垛位的选择是否合理, 其值应根据专家 知识获得 . 2 求解算法 板坯入库决策优化问题是一种离散型组合优化 问题, 其规模大 、约束多, 属于 NP难题, 很难用精确 的方法进行求解.粒子群优化算法 ( PSO)源于对鸟 群捕食行 为的研究 [ 7--8] , 是 一种 进化 计 算技 术 ( evolutionarycomputation).该算法的实质是根据个 体极值和全局极值来调整自己的飞行方向, 从而寻 找到问题的最优解, 算法通过速度更新公式和位置 更新公式进行迭代演进 .标准 PSO算法主要运用于 连续空间函数的优化, Kennedy等在 1997年提出了 针对 离 散 优 化 问 题 的 二 进 制 粒 子 群 算 法 ( BPSO) [ 9] . 对于本文考虑的板坯入库优化问题, 采用标准 粒子群算法进行求解得到的实验结果显示出较差的 收敛性, 计算效果不佳.因此, 本文借鉴文献[ 10]中 利用带交换子和交换序的离散粒子群算法求解置换 流水车间的算法结构, 同时引入遗传算法中的交叉 和变异操作, 构造了适合求解该问题的一种混合离 散粒子群算法 ( DPSO--CM) .该算法不需要经过遗 传算法中的选择过程、交叉配对过程, 比传统遗传算 法更为简单、易实现, 实验结果显示 DPSO--CM算法 不但具有良好的收敛性, 其解的质量也一致性地优 于普通遗传算法 ( GA) . 2.1 粒子编码 采用自然数编码方式, 假设粒子种群数为 pop; 入库批次中共有 N块板坯, 则粒子的每一维表示入 库批次中某一板坯的所选库位编号.每一块板坯对 应一个候选库位集合 Si, 假设集合 Si的个数为 ni, 则第 k个粒子可以表示为 Xk =( xk1, xk2, xk3, …, xki, …, xkN ), 其中 k=1, 2, …, pop, xki∈ Si ={1, 2, …, ni}.采用上述编码方式的每一个粒子都对应一个 可行解, 目标函数 ( 1)作为适应值函数, 则每个粒子 都对应目标函数的一个适应值. 2.2 粒子更新公式 粒子新位置由粒子自身速度 、个体极值和全局 极值决定, 结合板坯入库优化问题自身的特点, 借鉴 遗传算法中变异和交叉操作的思想, 重新定义了位 置更新公式, 其位置更新公式分三步完成, 每一步用 公式表示如下 : M n k =w va, b(X n ki), i∈ I, k=1, 2, …, pop ( 14) C n k =c1 p( E n k, p n k), k=1, 2, …, pop ( 15) · 378·