基于模糊匹配的板坯入库优化决策问题模型及求解

D010.13374斤.issn10153x.20l.03.00l 第33卷第3期 北京科技大学学报 Vo133 No 3 2011年3月 Journal ofUniversity of Science and Technobgy Bejjing Mar 2011 基于模糊匹配的板坯入库优化决策问题模型及求解 涂雪平123驱施灿涛12) 李铁克12) 1)北京科技大学经济管理学院.北京100832)钢铁生产制造执行系统技术教育部工程研究中心.北京100083 3)东方电气东方锅炉股份有限公司项目部.自贡643000 ☒通信作者，Emai1uepn的@126cm 摘要针对板坯入库优化决策问题，采用隶属度函数表示待入库板坯长度、宽度、厚度与各库位已存板坯对应属性的匹配 程度，建立了板坯入库模型.针对问题特征，借鉴遗传算法的交叉和变异操作，设计了一种混合离散粒子群算法(DP9)一QM 进行求解。基于企业实际生产数据的仿真实验验证了模型和算法的可行性和有效性. 关键词入库优化：板坯入库决策：模糊匹配：隶属度：粒子群算法 分类号TP273.1 Model and a lgorithm for the sb location optim ization decison problem based on fuzzy matching TU XuePing23 SHICan tad LITeke2) 1)SchoolofEcncmcs andManagement Unersit of Scence and Technopgy Beijing Beijing100083 China 2)Eng neerng Research Center ofMES Technokgy pr Iron&Seel Proluc tion Mnistry of Educatin ofChina Beijing 10083 China 3)PojectDeparment Dangfing BoilerG oup Co Ld,Zgang 643000 China Comespanding author Email txueping@6 co ABSTRACT For solving the sab pcaton decision problem wit hybrid sowage a slab pcationmodelusng a membership uinction was built to express he evel ofmatch ng a he relaed attrbu es of lengt width and thickness beeen he storing sabs and spred s abs n a warehouse According to he characteristics of the problm a hybrid discrete panicle swam algorithm called DPS)MC was proposed based on crossover and mu aation in genetic a goritlms Expermental results on a real case of a steel p lant demonstrate that themodel and algoritm are feasble and efective KEY WORDS nven pry optin izatipn slab locaton decis pp fuzzy matching membership functon partice swam algortm 随着钢铁企业计算机集成制造理论与技术的发 库位和垛位，以便于日常管理和出库作业，从而减少 展，炼钢一连铸一热轧一体化生产计划与调度问题 出库成本.针对钢铁企业生产计划与调度问题的研 得到了广泛的关注和研究1.板坯库在炼钢一连 究多着眼于炼钢、连铸和热轧等环节，而针对板坯库 铸一热轧生产流程中起着承前启后的作用：一方面 管理与控制，特别是对板坯入库优化的研究较为薄 要接收从连铸阶段送来的板坯，另一方面要为热轧 弱.在现有研究中，文献[5介绍了板坯库入库管理 阶段提供原料.因此板坯库在炼钢和轧钢工序 的基本原则，没有建立具体的数学模型：文献[6虽 的能力协调以及对整个生产过程的物流平衡方面均 然建立了板坯入库决策优化模型，且基于遗传算法 具有重要作用.对板坯库作业优化问题的研究具有 来进行求解但仅利用“0”和“1”两种取值来衡量板 重要的理论意义及实际价值， 坯长度、宽度、厚度与各库位的匹配程度 板坯库入库计划的编制是板坯库优化管理的核 为进一步提高板坯库利用率，本文针对板坯入 心，其主要内容是为入库批次中的板坯选择合适的 库优化决策问题建立了基于模糊匹配的优化决策模 收稿日期：2010-03-29 基金项目：国家自然科学基金资助项目(NQ70771008N970371057):中央高校基本科研业务费专项资金资助项目(N0 FRF-AS09-007B

第 33卷 第 3期 2011年 3月 北 京 科 技 大 学 学 报 JournalofUniversityofScienceandTechnologyBeijing Vol.33 No.3 Mar.2011 基于模糊匹配的板坯入库优化决策问题模型及求解 涂雪平 1, 2, 3) 施灿涛 1, 2) 李铁克 1, 2 ) 1) 北京科技大学经济管理学院, 北京 100083 2) 钢铁生产制造执行系统技术教育部工程研究中心, 北京 100083 3) 东方电气东方锅炉股份有限公司项目部, 自贡 643000 通信作者, E-mail:tuxueping1@126.com 摘 要 针对板坯入库优化决策问题, 采用隶属度函数表示待入库板坯长度、宽度、厚度与各库位已存板坯对应属性的匹配 程度, 建立了板坯入库模型.针对问题特征, 借鉴遗传算法的交叉和变异操作, 设计了一种混合离散粒子群算法 ( DPSO--CM) 进行求解.基于企业实际生产数据的仿真实验验证了模型和算法的可行性和有效性. 关键词 入库优化;板坯入库决策;模糊匹配;隶属度;粒子群算法 分类号 TP273 +.1 Modelandalgorithm fortheslablocationoptimizationdecisionproblem based onfuzzymatching TUXue-ping1 2, 3) , SHICan-tao1, 2) , LITie-ke1 2) 1) SchoolofEconomicsandManagement, UniversityofScienceandTechnologyBeijing, Beijing100083, China 2) EngineeringResearchCenterofMESTechnologyforIron＆SteelProduction, MinistryofEducationofChina, Beijing10083, China 3) ProjectDepartment, DongfangBoilerGroupCo.Ltd., Zigong643000, China Correspondingauthor, E-mail:tuxueping1@126.com ABSTRACT Forsolvingtheslablocationdecisionproblemwithhybridstowage, aslablocationmodelusingamembershipfunction wasbuilttoexpressthelevelofmatchingontherelatedattributesoflength, widthandthicknessbetweenthestoringslabsandstored slabsinawarehouse.Accordingtothecharacteristicsoftheproblem, ahybriddiscreteparticleswarmalgorithm, calledDPSO-MC, wasproposedbasedoncrossoverandmutationingeneticalgorithms.Experimentalresultsonarealcaseofasteelplantdemonstrate thatthemodelandalgorithmarefeasibleandeffective. KEYWORDS inventoryoptimization;slablocationdecision;fuzzymatching;membershipfunction;particleswarmalgorithm 收稿日期:2010--03--29 基金项目:国家自然科学基金资助项目 ( No.70771008;No.70371057) ;中央高校基本科研业务费专项资金资助项目 ( No.FRF--AS-09-007B) 随着钢铁企业计算机集成制造理论与技术的发 展, 炼钢—连铸—热轧一体化生产计划与调度问题 得到了广泛的关注和研究 [ 1--3] .板坯库在炼钢 —连 铸 —热轧生产流程中起着承前启后的作用:一方面 要接收从连铸阶段送来的板坯, 另一方面要为热轧 阶段提供原料 [ 4] .因此, 板坯库在炼钢和轧钢工序 的能力协调以及对整个生产过程的物流平衡方面均 具有重要作用, 对板坯库作业优化问题的研究具有 重要的理论意义及实际价值. 板坯库入库计划的编制是板坯库优化管理的核 心, 其主要内容是为入库批次中的板坯选择合适的 库位和垛位, 以便于日常管理和出库作业, 从而减少 出库成本 .针对钢铁企业生产计划与调度问题的研 究多着眼于炼钢、连铸和热轧等环节, 而针对板坯库 管理与控制, 特别是对板坯入库优化的研究较为薄 弱.在现有研究中, 文献[ 5] 介绍了板坯库入库管理 的基本原则, 没有建立具体的数学模型;文献 [ 6] 虽 然建立了板坯入库决策优化模型, 且基于遗传算法 来进行求解, 但仅利用“ 0”和“ 1”两种取值来衡量板 坯长度、宽度、厚度与各库位的匹配程度 . 为进一步提高板坯库利用率, 本文针对板坯入 库优化决策问题建立了基于模糊匹配的优化决策模 DOI :10 .13374 /j .issn1001 -053x .2011 .03 .001

第3期 涂雪平等：基于模糊匹配的板坯入库优化决策问题模型及求解 。377° 型，采用隶属度函数描述各板坯对应属性与各库位 己存板坯的相应属性的匹配程度.针对问题的特 10 征，以离散粒子群优化算法作为算法框架，借鉴遗传 0.8 算法中的交叉和变异思想进行问题求解。最后通 过仿真实验对本文提出的模型及算法的可行性和有 0.4 效性进行验证， 0.2 1问题描述与模型建立 13601380140014201440146014801500 板述长度m 1.1问题描述 图2基于长度属性的隶属程度 基于钢铁企业管理实际和己有研究板坯入库 Fg 2 Membership degree for kcatians based an length 优化决策问题应考虑的基本原则可以归纳为以下几 个方面9：(1)属于同一区的板坯尽量堆放在一起； 批次中所有板坯综合匹配程度最高的库位，以便于 (2)属于同一轧制计划的板坯尽量堆放在一起；(3) 日常管理和出库作业，使出库时的倒垛量、天车的行 同规格同材质的板坯尽量堆放在一起：(4)不能超 驶距离和起停次数最少，从而减少出库成本. 过垛位所允许存放的高度且尽量使各库位中的堆垛 1.2板坯入库优化模型 高度保持均衡：(5)固定匹配的板坯尽量堆放在 1.2.1符号定义 一起. 为了便于描述，定义符号和变量如下. 在上述原则的基础上，为了更加有效地利用板 (1)符号.N为入库批次中的板坯总数：M为 坯库存储空间，提升板坯库运转效能，可以考虑允许 库位总数；为板坯序号，飞={123，N:为 一定程度的混合堆垛.在板坯库中，各库位所存板 库位序号，庄上{123：M；h为库位中现有 坯根据长度、宽度、厚度取值的不同，其数量分布也 库存量；Q为库位所允许存放板坯的最大数量；P 不相同.以长度为例，从图1中可以看出：当板坯长 为第块板坯最终所选垛位的适应值，年yP为第 度在“1431m”(该值为对称轴附近时，该库位所 块板坯存放在库位时的适应值：S为第块板坯 存该类板坯最多；离对称轴“1431m越远，即长度 的候选库位集合，且S≠心，4~马分别为板坯长 过长或过短。该种板坯在该库位中所存数量越小. 度、宽度、厚度、硬度、是否属于同一轧制计划、是否 因此考虑利用模糊数学中的正态分布型隶属函数来 属于同一种牌号的钢种、板坯出库时间、是否属于固 描述板坯长度、宽度和厚度分别与库位中已存板坯 定匹配板坯的权重系数；↓W和号分别表示库位j 相应属性的隶属程度.图1中各种长度的板坯针对 中己存板坯的平均长度、平均宽度和平均厚度； 某库位的隶属度如图2所示.板坯的长度越接近对 W和G分别为板坯嘱于库位的长度隶属程度、 称轴“1431m,则该板坯隶属与该库位的隶属程 宽度隶属程度和厚度隶属程度，其值随着板坯的入 度也越大. 库是动态变化的：b和为常数，与库位所存 120 板坯的长度、宽度和厚度范围有关，取值应根据库位 100 所存板坯的历史数据统计获得：RKT和H分 80 别为板坯与库位中的板坯是否属于同一个轧制 计划、是否属于同一种钢种、轧制时间是否早于库位 中的板坯、硬度等级是否与库位对应 三20- (2)变量. 3601380140014201440146014801500 ↓板坯存放在库位中，其中年I在S 板坯长度mm X三 0否则 图1基于长度属性划分的板坯数量分布 1.2.2数学模型 Fg1 Quantity distrbuton of slbs based on length 基于以上论述和符号定义，建立板坯入库模型 综上所述，本文考虑的板坯入库优化问题可以 如下： 描述为：根据每块板坯的各种属性，确定每块板坯与 max∑PX (1) 各库位己存板坯的综合匹配程度，最后选择使整个

第 3期 涂雪平等:基于模糊匹配的板坯入库优化决策问题模型及求解 型, 采用隶属度函数描述各板坯对应属性与各库位 已存板坯的相应属性的匹配程度.针对问题的特 征, 以离散粒子群优化算法作为算法框架, 借鉴遗传 算法中的交叉和变异思想, 进行问题求解.最后通 过仿真实验对本文提出的模型及算法的可行性和有 效性进行验证. 1 问题描述与模型建立 1.1 问题描述 基于钢铁企业管理实际和已有研究, 板坯入库 优化决策问题应考虑的基本原则可以归纳为以下几 个方面 [ 6] :( 1)属于同一区的板坯尽量堆放在一起 ; ( 2)属于同一轧制计划的板坯尽量堆放在一起;( 3) 同规格同材质的板坯尽量堆放在一起;( 4)不能超 过垛位所允许存放的高度且尽量使各库位中的堆垛 高度保持均衡;( 5)固定匹配的板坯尽量堆放在 一起. 在上述原则的基础上, 为了更加有效地利用板 坯库存储空间, 提升板坯库运转效能, 可以考虑允许 一定程度的混合堆垛.在板坯库中, 各库位所存板 坯根据长度 、宽度 、厚度取值的不同, 其数量分布也 不相同 .以长度为例, 从图 1中可以看出:当板坯长 度在“ 1431 mm” (该值为对称轴 )附近时, 该库位所 存该类板坯最多 ;离对称轴 “1 431 mm”越远, 即长度 过长或过短, 该种板坯在该库位中所存数量越小 . 因此考虑利用模糊数学中的正态分布型隶属函数来 描述板坯长度、宽度和厚度分别与库位中已存板坯 相应属性的隶属程度 .图 1中各种长度的板坯针对 某库位的隶属度如图 2所示 .板坯的长度越接近对 称轴“ 1431 mm”, 则该板坯隶属与该库位的隶属程 度也越大. 图 1 基于长度属性划分的板坯数量分布 Fig.1 Quantitydistributionofslabsbasedonlength 综上所述, 本文考虑的板坯入库优化问题可以 描述为 :根据每块板坯的各种属性, 确定每块板坯与 各库位已存板坯的综合匹配程度, 最后选择使整个 图 2 基于长度属性的隶属程度 Fig.2 Membershipdegreeforlocationsbasedonlength 批次中所有板坯综合匹配程度最高的库位, 以便于 日常管理和出库作业, 使出库时的倒垛量、天车的行 驶距离和起停次数最少, 从而减少出库成本 . 1.2 板坯入库优化模型 1.2.1 符号定义 为了便于描述, 定义符号和变量如下. ( 1) 符号 .N为入库批次中的板坯总数;M为 库位总数 ;i为板坯序号, i∈ I={1, 2, 3, …, N};j为 库位序号, j∈ J={1, 2, 3, …, M};hj为库位 j中现有 库存量;Qj为库位 j所允许存放板坯的最大数量;Pi 为第 i块板坯最终所选垛位的适应值, i∈ N;Pij为第 i块板坯存放在库位 j时的适应值;Si为第 i块板坯 的候选库位集合, 且 Si≠ ;a1 ～ a8 分别为板坯长 度、宽度 、厚度 、硬度、是否属于同一轧制计划、是否 属于同一种牌号的钢种 、板坯出库时间 、是否属于固 定匹配板坯的权重系数;lj、wj和 gj分别表示库位 j 中已存板坯的平均长度、平均宽度和平均厚度 ;Lij、 Wij和 Gij分别为板坯 i属于库位 j的长度隶属程度、 宽度隶属程度和厚度隶属程度, 其值随着板坯的入 库是动态变化的;blj、bwj和 bgj为常数, 与库位 j所存 板坯的长度、宽度和厚度范围有关, 取值应根据库位 j所存板坯的历史数据统计获得 ;Rij、Kij、Tij和 Hij分 别为板坯 i与库位 j中的板坯是否属于同一个轧制 计划 、是否属于同一种钢种、轧制时间是否早于库位 j中的板坯 、硬度等级是否与库位 j对应. ( 2) 变量 . Xij= 1, 板坯 i存放在库位 j中, 其中 i∈ I, j∈ Si 0, 否则 1.2.2 数学模型 基于以上论述和符号定义, 建立板坯入库模型 如下 : f=max∑ N i=1 ∑ M j=1 PijXij ( 1) · 377·

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

第3期 涂雪平等：基于模糊匹配的板坯入库优化决策问题模型及求解 。379 X1=☒g式g)=12,pCp(16) 式(16)中1可由下式确定： Step1粒子根据自身的速度调整位置，即 Gg). arK￡ 式(14，式中w为惯性权重，其中￥b(X)表示粒 X=⑧Ggg)= ran c 子的速度，M表示粒子经过自身速度调整后的位 k=1 2 ..pap (19) 置，其实现过程借鉴了遗传操作中的变异操作.具 式中，n是针对粒子产生的随机数，且ar∈ 体过程为将第k个粒子的第维（即第块板坯）， [01]. 由现在的候选板坯库位变为b其中b是通过随 2.3启发式突变算子 机方式产生，且a:S对于M的计算，用公式表 当经过若干次迭代后，大部分粒子将趋于同一 示为 化，种群失去多样性，易陷入局部最优，此时有必要 Mg=☒￥b(X)= 将群体中的部分个体通过随机产生的方式进行 当b(X),ak<WaS 变换. X ranw 具体过程为：假设第代群体中最大适应度值 YE,I k=1 2 ..pop (17) 为s最小适应度值为，种群的平均适应度值为 式中，是针对粒子的第维产生的随机数，且 {g当盂n/a>a且e/话>B(一般a取04~ rak∈[01]. 0.8较为合适，B取05~1比较合适)时，将种群中 SeP2粒子根据个体极值调整位置，即式 20%的个体通过随机产生的方式进行变换. (15),式中F表示自身认知系数，Ck表示粒子根据 2.4参数设置 个体极值调整之后的位置，此步借鉴了遗传算法中 (1)对于惯性权重因子WW越大表示全局寻 的交叉操作.式中PM)的实现过程是：首先随 优能力越强局部寻优能力越弱；越小，则反之 机产生粒子的两交换位置a即和ana然后按以下 在算法的迭代过程中全局寻优能力应由强转弱，而 四种情况处理. 局部寻优能力应由弱转强即W应该由大逐步减 Case1如果a与a同为偶数，则从M中 小.本文采用线性递减权值策略来动态改变的取 取出r与anu之间的维替换对应的个体极值式 值川，其公式为 相同的段. hnax一n Case2如果an与ranu同为奇数时，则从M W=(Wga一成a)Xnhx +w(20) 中取出r之前和ra之后对应的维替换相同 式中：w为第n代的惯性权重；Wegin Wend分别为初 的维. 始惯性权重和迭代到最大代时的惯性权重，典型取 Case3如果a为奇数，ra为偶数则只从 值为gn=0.9wd=04而对于本文的问题，经 M中取出an之前的维替换对应的相同的维. 过实验测试Yc=03和wd=0.1时，结果较为 Case4如果an为奇数且a为偶数，则只 理想；为最大迭代次数. 从M中取出an之后的维替换对应的相同维. (2)社会认知系数￡表示粒子飞向全局极值 例如，M为(13245)，R为(23421，如果 g的步长.当粒子与莒的距离较大时（粒子的距离 产生的随机数马<6然后随机产生两交换位置为 是指两个粒子在各维上取值的差异度，对于本文的 rn=2a即=4则粒子替换后的结果为(134 问题，由于各维的取值直接关系到目标函数，所以可 25). 以用目标函数值直接表示，￡应该取大值，使粒子 其中， 加速向全局极值靠近：当粒子与g距离较接近时， PM R). ran<c Ck=☒M)= ￡应该取小值，使粒子减速向全局极值飞行，以保证 M ranf 种群的多样性.其表示为 k-1 2..,pop (18) (21) 式中，是针对粒子k产生的随机数，且an∈ [0]. 式中：【为在第代时，第k个粒子对应的目标函数 SteP3粒子根据全局极值调整位置，即 值；为第代时的全局极值；为社会认知系数的 式(16)其中S表示社会认知系数，该步将SeP2 初始值.对与自身认知系数S可以采取同样的方 中的个体极值换为全局极值. 式进行

第 3期 涂雪平等:基于模糊匹配的板坯入库优化决策问题模型及求解 X n+1 k =c2 g( F n k, g n ), k=1, 2, …, pop( 16) Step1 粒子根据自身的速度调整位置, 即 式 ( 14), 式中 w为惯性权重, 其中 va, b( X n ki)表示粒 子的速度, M n k表示粒子经过自身速度调整后的位 置, 其实现过程借鉴了遗传操作中的变异操作.具 体过程为:将第 k个粒子的第 i维 (即第 i块板坯 ), 由现在的候选板坯库位 a变为 b, 其中 b是通过随 机方式产生, 且 a, b∈ Si.对于 M n k的计算, 用公式表 示为 M n k =w va, b(X n ki) = va, b(X n ki), ranki<w, a, b∈ Si, X n ki, ranki≥w, i∈ I, k=1, 2, …, pop ( 17) 式中, ranki是针对粒子 k的第 i维产生的随机数, 且 ranki∈ [ 0, 1] . Step2 粒子根据个体极值调整位置, 即式 ( 15), 式中 c1 表示自身认知系数, C n k表示粒子根据 个体极值调整之后的位置, 此步借鉴了遗传算法中 的交叉操作 .式中 p( M n k, p n k)的实现过程是:首先随 机产生粒子的两交换位置 rankc和 rankd, 然后按以下 四种情况处理. Case1 如果 rankc与 rankd同为偶数, 则从 M n k中 取出rankc与 rankd之间的维替换对应的个体极值 p n k 相同的段. Case2 如果 rankc与 rankd同为奇数时, 则从 M n k 中取出 rankc之前和 rankd之后对应的维替换 p n k相同 的维. Case3 如果 rankc为奇数, rankd为偶数, 则只从 M n k中取出 rankc之前的维替换对应的 p n k相同的维 . Case4 如果 rankd为奇数, 且 rankc为偶数, 则只 从 M n k中取出 rankd之后的维替换对应的 p n k相同维 . 例如, M n k为 ( 1, 3, 2, 4, 5), p n k 为 ( 2, 3, 4, 2, 1), 如果 产生的随机数ran2 <c1, 然后随机产生两交换位置为 ranc =2, rand =4, 则粒子替换后的结果为 ( 1, 3, 4, 2, 5) . 其中, C n k =c1 g( M n k, p n k) = p(M n k, p n k), rank <c1 M n k, rank≥c1 k=1, 2, …, pop ( 18) 式中, rank是针对粒子 k产生的随机数, 且 rank∈ [ 0, 1] . Step3 粒 子根据 全局极 值调整 位置, 即 式 ( 16), 其中 c2 表示社会认知系数, 该步将 Step2 中的个体极值换为全局极值. 式 ( 16)中 X n+1 k 可由下式确定: X n+1 k =c2 g( C n k, g n ) = g( C n k, g n ), ran′k <c2 C n k, ran′k≥c2 k=1, 2, …, pop ( 19) 式中, ran′k是针对粒子 k产生的随机数, 且 ran′k∈ [ 0, 1] . 2.3 启发式突变算子 当经过若干次迭代后, 大部分粒子将趋于同一 化, 种群失去多样性, 易陷入局部最优, 此时有必要 将群体中的部分个体通过随机产生的方式进行 变换 . 具体过程为:假设第 n代群体中最大适应度值 为 fmax, 最小适应度值为 fmin, 种群的平均适应度值为 favg.当 fmin/fmax >α且 favg/fmax >β(一般 α取 0.4 ～ 0.8较为合适, β取 0.5 ～ 1比较合适 )时, 将种群中 20%的个体通过随机产生的方式进行变换. 2.4 参数设置 ( 1) 对于惯性权重因子 w, w越大表示全局寻 优能力越强, 局部寻优能力越弱 ;w越小, 则反之. 在算法的迭代过程中全局寻优能力应由强转弱, 而 局部寻优能力应由弱转强, 即 w应该由大逐步减 小.本文采用线性递减权值策略来动态改变 w的取 值 [ 11] , 其公式为 wn =( wbegin -wend) × nmax -n nmax +wend ( 20) 式中 :wn为第 n代的惯性权重 ;wbegin、wend分别为初 始惯性权重和迭代到最大代时的惯性权重, 典型取 值为 wbegin =0.9, wend =0.4, 而对于本文的问题, 经 过实验测试, wbegin =0.3和 wend =0.1 时, 结果较为 理想 ;nmax为最大迭代次数 . ( 2) 社会认知系数 c2 表示粒子飞向全局极值 g n的步长.当粒子与 g n的距离较大时 (粒子的距离 是指两个粒子在各维上取值的差异度, 对于本文的 问题, 由于各维的取值直接关系到目标函数, 所以可 以用目标函数值直接表示 ), c2 应该取大值, 使粒子 加速向全局极值靠近;当粒子与 g n距离较接近时, c2 应该取小值, 使粒子减速向全局极值飞行, 以保证 种群的多样性 .其表示为 c n 2 = f n k f n g ·c 0 2 ( 21) 式中 :f n k为在第 n代时, 第 k个粒子对应的目标函数 值;f n g为第 n代时的全局极值;c 0 2 为社会认知系数的 初始值.对与自身认知系数 c1, 可以采取同样的方 式进行. · 379·

。380 北京科技大学学报 第33卷 2.5算法步骤 于隶属度的板坯入库优化问题，采用标准粒子群算 根据以上论述，本文提出的混合离散粒子群算 法BPS)进行求解得到的实验结果收敛性较差，计 法步骤描述如下， 算效果不佳因此实验部分将DPS)-CM与传统遗 Sep0参数设置：种群大小py初始惯性权 传算法GA进行比较. 重和最大代时惯性权重w初始自身认知系 对于解决本问题的传统遗传算法G)采取自 数和初始社会认知系数 然数编码方式，用入库板坯对应的板坯序号构造染 SeP1初始化：给粒子种群赋初始值，同时设 色体，染色体中的每一个基因与入库板坯序号一一 置迭代次数-Q 对应，如入库批次中共有块板坯，则染色体的长 SeP2计算每个粒子的适应度，如果满足终 度为y每个基因值由其对应板坯的候选库位集中 止准则（采用自适应终止准则，即如果算法在连续d 的库位号构成，每块板坯对应的候选库位集构成对 次之内，解的质量始终没有提高，则终止迭代，则 应基因的搜索空间，采用此编码方式的每一条染 输出最优粒子：否则，令：叶1 色体都对应一个可行解，目标函数式(1)作为适应 Step3判断条件n/a>a且/a>B是 值函数，则每条染色体都对应目标函数的一个适 否被满足，如果满足则实施算法的重启，否则转 应值. Step4 选择算子采用滚动轮策略.交叉方式采用两点 SeP4根据式更新粒子的位置： 交叉方式，其过程为：根据随机产生的两个交叉点 SeP41根据式(14)更新各个粒子，参数w 两个随机配对的染色体在两交叉点之间进行基因值 由式(20)计算： 互换，形成两个新的染色体.变异方式采用单点变 Sep42根据式(15)更新各个粒子，参数P 异，其过程为：随机选择染色体中需进行变异的基 采用与参数的变化策略： 因，其基因值随机取对应板坯的候选库位集中的一 Sp4.3根据式(16)更新各个粒子，参数？个库位编号.终止准则采用与DP)-M相同的自 由式(21)计算 适应终止准则. SteP5将更新后的种群作为新的种群，转 3.2数据及参数 Step2 实验中使用的板坯数据均来自于某热轧厂板坯 库的信息，总共选择10组板坯数据进行实验，共选 3数值实验 择了五种牌号的板坯，分别标记为1、23、4和5每 3.1实验设计 组板坯数分别是2040.6080100120140160 为验证本文提出的模型及算法的可行性和有效 180和200所选板坯的长、宽、厚、硬度等级、所属轧 性，从解的质量和算法的收敛速度对DPS)CM算 制计划、牌号以及是否被固定匹配的取值范围见表 法进行考查.同时，如前文所述对于本文考虑的基 1(注：当板坯固定库位取值为0时表示不被固定. 表1所选板坯各属性的取值范围 Table 1 Variable ranges of attrbutes for slabs 长度/m 宽度mm 厚度/m 硬度等级 所属轧制计划 牌号 固定库位编号 L30008000 [9501500 【5001130.99 [13 【520] [1 [09月 板坯库包含9个库位，每个库位包含10个垛 态分布隶属函数曲线的平缓或陡峭程度，越大，曲 位，每个垛位最大堆垛量为20块板坯.根据各库位 线越平缓，反之越陡峭，在概率论中b=了26（σ为 已存板坯信息，统计得各库位所存板坯的厚度、宽度 长度对应的标准差：根据统计学原理，其概率 和长度平均值如表2所示.根据专家知识得到的板 P(}-3o<X+3o)=0.9973所以应根据库位 坯各属性的权值4~号分别取10.5.55202015 中己存板坯的具体情况，选择合适的σ值.经多次 和20 实验，采用式(22)计算参数。，此时正态分布的概 在式(6)表示的正态分布型隶属函数中，参数} 率密度曲线的陡峭程度较为理想 表示对应隶属函数的核，即正态分布密度曲线图的 a=(has-dn)/36 (22) 对称轴，在概率论中称为数学期望：参数b决定正 根据上文中提到的h=2可得到：

北 京 科 技 大 学 学 报 第 33卷 2.5 算法步骤 根据以上论述, 本文提出的混合离散粒子群算 法步骤描述如下 . Step0 参数设置 :种群大小 pop;初始惯性权 重 wbegin和最大代时惯性权重 wend;初始自身认知系 数 c 0 1 和初始社会认知系数 c 0 2. Step1 初始化:给粒子种群赋初始值, 同时设 置迭代次数 n=0. Step2 计算每个粒子的适应度, 如果满足终 止准则 (采用自适应终止准则, 即如果算法在连续 d 次之内, 解的质量始终没有提高, 则终止迭代 ), 则 输出最优粒子;否则, 令 n∶=n+1. Step3 判断条件 fmin/fmax >α且 favg/fmax >β是 否被满足, 如果满足则实施算法的重启, 否则转 Step4. Step4 根据式更新粒子的位置 : Step4.1 根据式 ( 14)更新各个粒子, 参数 wn 由式 ( 20)计算 ; Step4.2 根据式 ( 15)更新各个粒子, 参数 c n 1 采用与参数 c n 2 的变化策略 ; Step4.3 根据式 ( 16)更新各个粒子, 参数 c n 2 由式 ( 21)计算 . Step5 将更新后的种群作为新的种群, 转 Step2. 3 数值实验 3.1 实验设计 为验证本文提出的模型及算法的可行性和有效 性, 从解的质量和算法的收敛速度对 DPSO--CM算 法进行考查 .同时, 如前文所述, 对于本文考虑的基 于隶属度的板坯入库优化问题, 采用标准粒子群算 法 BPSO进行求解得到的实验结果收敛性较差, 计 算效果不佳, 因此实验部分将 DPSO--CM与传统遗 传算法 GA进行比较. 对于解决本问题的传统遗传算法 GA, 采取自 然数编码方式, 用入库板坯对应的板坯序号构造染 色体, 染色体中的每一个基因与入库板坯序号一一 对应, 如入库批次中共有 N块板坯, 则染色体的长 度为 N, 每个基因值由其对应板坯的候选库位集中 的库位号构成, 每块板坯对应的候选库位集构成对 应基因的搜索空间, 采用此编码方式的每一条染 色体都对应一个可行解, 目标函数式 ( 1)作为适应 值函数, 则每条染色体都对应目标函数的一个适 应值. 选择算子采用滚动轮策略 .交叉方式采用两点 交叉方式, 其过程为:根据随机产生的两个交叉点, 两个随机配对的染色体在两交叉点之间进行基因值 互换, 形成两个新的染色体 .变异方式采用单点变 异, 其过程为 :随机选择染色体中需进行变异的基 因, 其基因值随机取对应板坯的候选库位集中的一 个库位编号.终止准则采用与 DPSO--CM相同的自 适应终止准则 . 3.2 数据及参数 实验中使用的板坯数据均来自于某热轧厂板坯 库的信息, 总共选择 10组板坯数据进行实验, 共选 择了五种牌号的板坯, 分别标记为 1、2、3、4和 5.每 组板坯数分别是 20、 40、60、80、100、120、140、 160、 180和 200, 所选板坯的长 、宽、厚 、硬度等级、所属轧 制计划、牌号以及是否被固定匹配的取值范围见表 1(注 :当板坯固定库位取值为 0时表示不被固定 ) . 表 1 所选板坯各属性的取值范围 Table1 Variablerangesofattributesforslabs 长度 /mm 宽度 /mm 厚度 /mm 硬度等级 所属轧制计划 牌号 固定库位编号 [ 3 000, 8 000] [ 950, 1 500] [ 50.01, 130.99] [ 1, 3] [ 5, 20] [ 1, 5] [ 0, 9] 板坯库包含 9个库位, 每个库位包含 10个垛 位, 每个垛位最大堆垛量为 20块板坯.根据各库位 已存板坯信息, 统计得各库位所存板坯的厚度 、宽度 和长度平均值如表 2所示.根据专家知识得到的板 坯各属性的权值 a1 ～ a8 分别取 10、5、5、5、20、20、15 和 20. 在式 ( 6)表示的正态分布型隶属函数中, 参数 lj 表示对应隶属函数的核, 即正态分布密度曲线图的 对称轴, 在概率论中称为数学期望;参数 blj决定正 态分布隶属函数曲线的平缓或陡峭程度, blj越大, 曲 线越平缓, 反之越陡峭, 在概率论中 blj = 2σ( σ为 长度对应的标准差 ) ;根据统计学原理, 其概率 P( lj-3σ<X<lj+3σ) =0.997 3.所以应根据库位 中已存板坯的具体情况, 选择合适的 σ值 .经多次 实验, 采用式 ( 22)计算参数 σ, 此时正态分布的概 率密度曲线的陡峭程度较为理想 . σ=(l j max -l j min) /36 ( 22) 根据上文中提到的 blj= 2σ可得到 : · 380·