用于求解露天矿运输问题的改进差分进化算法.pdf

第第44卷 第卷 第4期期 2018年年4月月 工矿自动化 Industry and Mine Automation Vol. 44 No. 4 Apr 2018 文章编号671-251X201804-0104-05 DOI 10. 13272/j. issn. 1671-251x. 2017100044 用 于 求 解 露 天 矿 运 输 问 题 的 改 进 差 分 进 化 算 法 彭程，隋晓梅，王辉俊 华北科技学院信息与控制技术研究所， 河 北 三 河 065201 摘要针对露天矿运输问题， 以露天矿开采能力和运输能力为约束条件，以运输费用最小为目标函数， 建 立了露天矿运输问题的数学模型。针对智能优化算法用于求解露天矿运输问题时容易陷入局部最优解的问 题，提出了一种改进差分进化算法。该算法通过在差分进化算法中引入归一化操作， 使得运输问题中的等式 约束能自动成立， 有利于跳出局部最优解。应用结果表明， 该算法具有较好的可重复性， 利用该算法对露天 矿运输问题进行优化后，运输成本明显降低。 关键词 露天矿运输； 人工智能；差分进化算法；等式约束；归一化 中图分类号TD57 文献标志码A 网络出版时间018-03-20 159 网络出版地址http //kns. cnki. net/kcms/detail/32. 1627. TP. 20180320. 1335. 002. html 收 稿 日 期收 稿 日 期2017-10-20 ;修 回 日 期修 回 日 期2018-03-13 ;责 任 编 辑责 任 编 辑 盛 男 。 基 金 项 目基 金 项 目中 央 高 校 基 本 科 研 业 务 费 资 助 项 目 （3142015013;河 北 省 科 技 计 划 项 目 （15211830 。 作 者 简 介作 者 简 介 彭 程 （1978），男，山 东 日 照 人，高 级 工 程 师，博 士，主 要 研 究 方 向 为 系 统 建 模 、 优 化 与 控 制 ，E-mail pengCndSt. edu cn。通 信 作 者 隋 晓 梅 （1978 ， 女 ， 辽 宁 辽 阳 人 ， 副 教 授 ， 硕 士 ， 主 要 研 究 方 向 为 复 杂 系 统 建 模 与 优 化 ，E-mailunny7801。 引 用 格 式引 用 格 式 彭 程 ， 隋 晓 梅 ， 王 辉 俊 . 用 于 求 解 露 天 矿 运 输 问 题 的 改 进 差 分 进 化 算 法 工 矿 自 动 化 ，2018,444 04-108. PENG Cheng, SUI Xiaomei, WANG Huijun. Improved differential evolution algorithm for solving open-pit mine transportation problem[J]. Industry and Mine Automation, 2018,444 ；； 104-108. [ 8 ] 王大虎， 史艳楠， 陈文博.基 于Quest3D的煤矿副井提 升 机 虚 拟 实 操 系 统 的 开 发 制 造 业 自 动 化，2014, 36914-117. WANG Dahu, SHI Yannan, CHEN Wenbo. Development on the virtual operation system of mine hoist based on Quest3D [ R ]. Manufacturing Automation,2014,369 114-117. [ 9 ] 路朝龙. Quest3D从入门到精通[M ].北 京 中国铁道 出版社，2012. [ 1 0 ] 刘少华， 孟国营.基 于Quest3D的煤矿主扇风机虚拟 现 实 的 研 究 同 煤 科 技，20123-3. LIU Shaohua， MENG Guoying. Research on virtual reality of the mines main fan based on Quest3D[J]. Science and Technology of Datong Coal Mining Administration，20123 1-3. [ 1 ] 石智军， 田宏亮， 田东庄， 等.煤矿井下随钻测量定向 钻进使用手册[M ].北 京 地质出版社，201222-42. [ 2 ] 石智军， 胡少韵， 姚 宁 平 ， 等.煤矿井下瓦斯抽采（ 放 ） 钻孔施工新技术[M ].北 京煤 炭 工 业 出 版 社，2008 24-267 [ 1 3 ]吴海雁， 王天龙， 张旭辉， 等.基 于Quest3D和PL C的 采煤机远程监控系统[J ].工矿自动化，2015，4111 14-177 WU Haiyan，WANG Tianlong，ZHANG Xuhui，et l Remote monitoring system of shearer based on Quest3D and PLC [ J ]7Industry and Mine Automation，2015，4111 4-17. [ 4 ]袁 玲 ， 杜启亮.计 算 机 与FX2N系 列PL C串行通信的 几 种 方 法[ J ] .计 算 技 术 与 自 动 化 ，2011， 30 2 130-1347 YUAN Ling， DU Qiliang. Several ways of serial communication between computer and FX2N series PLC [J]. Computing Technology and Automation， 2011,302130-134. [ 1 5 ]周 立 冬 ， 陈 振 华 ， 丁 爱 东.上 位 计 算 机 与FX2N系列 PL C串 行 通 信 的 实 现[ J ] .机 械 与 电 子， 2004 8 71-73 ZHOU Lidong , CHEN Zhenhua , DING Aidong. The realization of serial communication between the super computer and PLC in FX2n series[J]. Machinery j Electronics，20048 71-73. 2 0 1 8 年 第 期彭 程 等 用 于 求 解 露 天 矿 运 输 问 题 的 改 进 差 分 进 化 算 法 105 Improved differential evolution algorithm for solving open-pit mine transportation problem PEN G C heng, SU I X iaom ei, W A N G H uijun Institute of In ation and C ontrol T echnology, N orth China Institute of Science and T echnology, Sanhe 065201, C hina A bstract A im ing at open-pit m ine transportation problem , a m athem atical m odel of the open-pit m ine transportation problem w as established w hich took production and transportation capacity of open-pit m ine as constraint conditions and them inim um transportation cost as objective function. In view of problem that intelligent optim ization algorithm for solving the open-pit m ine transportation problem w as easily getting trapped in local optim al solution, an im proved differential evolution algorithm w as proposed. N orm alization is introduced into differential evolution algorithm w hich m akes equality constraint in the transportation problem can be satisfied autom atically and is advantageous to jum p out of local optim al solution. T he application results show th at the algorithm has good repeatability, and transportation cost is significantly reduced by use of the algorithm to optim ize the open-pit m ine transportation problem . Key w ords open-pit m ine transportation; artificial intelligence; differential evolution algorithm ; equality constraint; norm alization 〇引 言〇引 言 运输优化对降低露天矿企业生产成本、 提升竞 争力具有重要意义[12]。随着人工智能技术的发展， 智能优化算法被用于求解露天矿运输问题[3] 智能 优化算法通常是针对无约朿或边界约朿优化问题提 出的， 而在露天矿运输问题中， 除了边界约朿之外还 存在等式约朿和不等式约朿） ]， 其中等式约朿为智 能优化算法的实施带来困难。因此， 必须将智能优 化算法与约朿处理方法） 8]相结合才能求解露天矿 运输问题。文献[9 ]利用运输问题的目标函数和约 朿条件构造霍普菲尔德神经网络， 使用遗传算法优 化神经网络权值。文献[1 0 ]使用多目标优化的思路 处理约朿条件， 利用带双引子的粒子群优化算法求 解与运输问题对应的多目标优化问题。上述文献采 用不同的智能优化算法和约朿处理方法， 取得了相 应的成果， 但存在容易陷人局部最优解的问题。 差分进化算法[11]具有操作简单、 求解精度高的 优点， 是进化计算领域最重要的优化算法之一， 已被 用于解决换热网络优化[12]、 并联机构位置正解[13]、 电动汽车排放优化[1]、 瓦斯涌出量预测[15]等问题。 本文在差分进化算法中引人归一化操作， 去掉了运 输问题中的等式约朿， 提出了 一种改进差分进化算 法， 并将其应用于露天矿运输问题的优化计算。 1露 天 矿 运 输 问 题 的 数 学 模 型露 天 矿 运 输 问 题 的 数 学 模 型 D和J个卸载点N“ 1， 2, ，J;装载点人所在 采区的开采能力为P,，,，m3,卸载点B, 的受矿能力为 Q, ，, ，m3;从 装 载 点 到 卸 载 点B,的单位运费和运 输量分别为C, ，, ，元/m3和 ，，m3 。3 。从降低运输成本 的角度考虑， 露天矿运输问题的目标函数可表示为 8 0 min Hx Ct]xt] ⑴ i-1 j-1 式中HX 为总运费，X [11 1 21〇〇21 22 20 1 2 U ] 。] 。 考虑到开采能力、、受矿能力和运输行为的特点，， 露天矿运输问题还需满足式（ 2 式定义的约朿 条件， 即装载点的矿石需要全部运出， 运送到卸载点 的矿石量不能大于其受矿能力， 从装载点到卸载点 的运 量 能为 。。 1 j F i j 1 2 8 . 〉 ij 2 7j i1 3 5 0⑷ 2差 分 进 化 算 法差 分 进 化 算 法 有边界约朿的函数优化问题定义为 m in fZ Z [ Z 1 Z2 wd ] Rd 5 1b 2.zd 2 Ud d 1,2,---,D 式中fZ为目标函数Z为决策向量〇〇为决策向 量的维数 『随 机 数 ; 『5为 随 机 整 数为 随 机 整 数，r5 {1，，2，，，，N} 。} 。 只 ，只 ，r ，，5配 合 用 以 控 制 试 验 向 量 各 分 量 的配 合 用 以 控 制 试 验 向 量 各 分 量 的 来 源 。来 源 。 3 选 择 操 作 。 若 试 验 向 量选 择 操 作 。 若 试 验 向 量[/否 则 对 试否 则 对 试 验 向 量 按 式 （验 向 量 按 式 （12 进 行 归 一 化 操 作 ， 得 到 归 一 化 后 的进 行 归 一 化 操 作 ， 得 到 归 一 化 后 的 个 体 ， 利 用 式 （个 体 ， 利 用 式 （14计 算 其 目 标 函 数 值 。计 算 其 目 标 函 数 值 。 6 进 行 选 择 操 作 。 若 归 一 化 后 的 个 体 优 于 当进 行 选 择 操 作 。 若 归 一 化 后 的 个 体 优 于 当 前 种 群 中 的 第前 种 群 中 的 第n个 个 体 ， 则 更 新 种 群 中 的 第个 个 体 ， 则 更 新 种 群 中 的 第n个 个个 个 体体;若 归 一 化 后 的 个 体 优 于 最 优 个 体 ， 则 更 新 最 优若 归 一 化 后 的 个 体 优 于 最 优 个 体 ， 则 更 新 最 优 。。 7 令令n n 1。 若。 若n 2 N， 返 回 步 骤， 返 回 步 骤3 。 。 2 0 1 8 年 第 期彭 程 等 用 于 求 解 露 天 矿 运 输 问 题 的 改 进 差 分 进 化 算 法 107 8 若 达 到 最 大 进 化 代 数 ， 结 朿 优 化 ， 输 出 最 优 个 体 ;否 则 令ra 1 ， 返 回 步 骤 3进 行 下 一 代 优 化 。 4算 法 在 露 天 矿 运 输 问 题 中 的 应 用算 法 在 露 天 矿 运 输 问 题 中 的 应 用 抚 顺 西 露 天 矿 共 有 9 个 装 载 点 2 A9 个卸 载 点N,B5， 装 载 点 所 在 采 区 的 开 采 能 力 、 卸 载 点 的 受 矿 能 力 及 从 装 载 点 到 卸 载 点 的 单 位 运 费 见 表 1 。经 试 验 ， 改 进 差 分 进 化 算 法 各 参 数 取 值 惩 罚 因 子 “ 1 000、种 群 大 小N 1 0 0、最 大 进 化 代 数 G 5 000、 交 叉 概 率 只 0. 9 、 缩 放 因 子F0. 5 。 表1露天矿运输相关数据 Table 1 Data related to open-pit mine transportation 卸载点 单 位 运 费/元 im 3 受 矿 能 力 / 万 m3A1 A2A3A4A5A6A7A8A9 Bi8737677. 59. 1475. 737672 850 b2578. 077877. 1678. 4979. 53 420 b33747372737576. 25737680 b44. 65. 86. 35757674. 23767750 b56. 43757674. 5373. 64747650 开 采 能 力 / 5404604303502 1001 850670980820 考 虑 到 改 进 差 分 进 化 算 法 是 一 种 随 机 优 化 算 法 ， 重 复 进 行 1 0 0 次 优 化 计 算 ， 1 0 0 组 优 化 结 果 中 最 优 总 运 费 最 大 值 为 1 22 9 3 万 元 ， 最 小 值 为 1 22 01万 元 ， 均 值 为 1 2 2 2 1 万 元 ， 标 准 差 为 0. 1 9 万 元 ， 表 明 改 进 差 分 进 化 算 法 具 有 较 好 的 可 重 复 性 。 利 用 文 献 [9-10]算 法 和 本 文 算 法 得 到 的 最 优 运 输 量 （ 四 舍 五 人 后 保 留 整 数 部 分 ） 见 表 2 。经 检 验 ， 表 2 中 3 组 最 优 运 输 量 均 满 足 式 （ 2 式 （ 定义的 约 朿 条 件 ， 但 文 献 [910 ]算 法 得 到 的 最 优 总 运 费 分 别 为 1 ; 1 ; 万 元 和 0 9 0 万 元 ， 均 大 于 本 文 算 法 得 到的 总运 明 分 化 法 到 了 更 好 的 运 输 方 案 。 表2不同算法得到的最优运输量 Table 2 Optimal transportation volume of different algorithms 算法算法 装载点到卸载点的运输量装载点到卸载点的运输量/万万m3 文献文献[9]算法]算法 工工12工工2132334352616274 81849395其他其他 54046042010350 2 1001 490360670 900802725480 文献文献[10]算法]算法 工工12工工1321314352616265 71818491他他 210330460430350 2 100 200 1 000650 6702307508200 文 法文 法 工工12工工2132334352616274 81849395他他 540460270160350 2 1001 490360670 900801706500 5结 语结 语 改 进 差 分 进 化 算 法 针 对 露 天 矿 运 输 问 题 中 等 式 约 朿 的 特 点 ， 引 人 归 一 化 操 作 去 除 了 等 式 约 朿 ， 有利 于 跳 出 局 部 最 优 解 。应 用 结 果 表 明 ， 该 算 法 具 有 较 好 的 可 重 复 性 ， 有 利 于 降 低 运 输 成 本 。 参考文献（References [1 ]李桂荣， 尹江艳， 郝全明.浅谈运筹学在矿业中的应用 [J ].黄 金，2008,29“25-27. LI Guirong， YIN Jiangyan， HAO Quanming. Application study of operational research in mining ] . Gold,2008,29“ 25-27. [2 ]方颜空， 张修玉， 邬艳礼.九架炉露天矿采掘带单元排 土 运 输 方 案 优 化 研 究[ J ] .矿 业 研 究 与 开 发， 2017 1199-101. FANG Yankong， ZHANG Xiuyu， WU Yanli. Optimization research on the dumping transportation of cutting zone unit in Jiujialu open-pit mine [ J]. Mining Research and Development， 2017 11 99-101. 108 工 矿 自 动 化2 0 1 8 年 第 4 4 卷 3 *苏楷， 门飞.露天矿运输调度问题求解的自适应果蝇 优化算法[J ].金属矿山，2017,4611 72-176. SU Kai, MEN Fei. Adaptive fruit fly optimization algorithm for solving open-pit hauling dispatching optimization problem ]. Metaf Mine, 2017,46 11 172-176. [4 ]仇旺令， 叶义成.露天矿运输问题优化及其算法[ ] . 化工矿物与加工，2005,34725-27. QIU Wangling, YE Yicheng. Optimization and arithmetic of the open-pit transportation problem ]. Industrial Minerals and Processing, 2005, 34 7 25-27. [5 ]李宜萱， 金 治 群 ， 程 军 蕊 ， 等.一 种 基 于A EA算法的 改 进 的 惩 罚 函 数 法[ ] .计 算 机 与 应 用 化 学 ，2014, 31121479-1484. LI Yixuan,JIN Zhiqun, CHENG Junrui, et al. Study on an improved penalty function for constraint problem based on AEA IA EA algorithm [ J ]. Computers and Applied Chemistry, 2014， 31 12 1479-1484. [6 ]刘衍民， 牛奔， 赵庆祯.求解约束优化问题的多目标粒 子 群 算 法[ J ] .计 算 机 应 用 研 究 ，2011， 28 3 851-853. LIU Yanmin, NIU Ben, ZHAO Qingzhen. Multi objective particle swarm optimizer for solving constraint optimization problems [J]. Application Research of Computers,2011,283 851-853. [ 7 ] 刘大莲， 张春花， 杜金玲.基于种群分类排序的约束优 化 遗 传 算 法[ J ] .数 学 的 实 践 与 认 识 ，2012,42 8 190-196. LIU Dalian, ZHANG Chunhua, DU Jinling. An evolutionary algorithm based on classification and sorting for solving constrained optimization problem [J]. Mathematics in Practice and Theory, 2012, 428190-196. [ 8 ] 郭中华， 金 灵 ， 郑彩英.人 工 神 经 网 络 求 解T S P问题 的 改 进 算 法 研 究[ J ] .计 算 机 仿 真 ，2014, 31 4 355-3587 GUO Zhonghua,JIN Ling,ZHENG Caiying. Study on improved of neural network to solve TSP[J]. Computer Simulation,2014,314 355-358. [9 ]鞠兴军， 李林， 刘光伟.基于遗传算法的神经网络在露 天矿卡车调度系统中的应用研究[J ].露天采矿技术， 2009,24631-33. JU Xingjun, LI Lin, LIU Guangwei. Application research on truck dispatching system based on neural network of genetic algorithm in surface mine [ J]. Opencast Mining Technology, 2009,246 31-33. [ 0 ]李 勇 ， 胡乃联， 李国清.基于改进粒子群算法的露天矿 运输调度优化[J].中国矿业，2013，22498-101. LIY ong， HU Nailian， LI Guoqing. Open-pit hauling dispatching optimization based on improved PSO algorithm[J]. China Mining Magazine，2013,22 4 98-1017 [11] STORN R ，PRICE K. Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J]. Journal of Global Optimization， 1997,114341-359. [ 2 ] 陈家星， 崔国民， 彭 富 裕 ， 等.基于种群多样性的改进 差分进化算法应用于换热网络优化[J ].热能动力工 程，2017，32429-37. CHEN Jiaxing, CUI Guomin, PENG Fuyu， et al. An improved differential evolution algorithm based on population diversity and its application in heat exchanger network synthes0s [ J ]. Journal of Engineering for Thermal Energy and Power，2017， 32429-37. [ 3 ] 彭程.平面并联机构正解的拥挤差分进化算法求解 [J].华北科技学院学报，2016，13294-97. PENG Cheng. Forward kinematics solutions of the planar parallll mechanism using crowding differential evolution algorithm [ J ]. Journal of North China Institute of Science and Technology，2016， 13 2 94-97. [ 4] 卜凡靖， 王耀南.电动汽车排放的改进差分进化算法 [J].智能系统学报，2017，121110-116. BU Fanjing , WANG Yaonan. Study of electric vehicle emissions by applying modified differential evolution algorithm [ J ]. CAAI Transactions on Intelligent Systems，2017 ,121 110-116. [ 5 ] 王江荣， 罗资琴， 赵睿.投影寻踪在瓦斯涌出量预测中 的应用[J ].工矿自动化，2015，41487-89. WANG Jiangrong， LUO Ziqin， ZHAO R i Application of projection pursuit in gas emission prediction[J]. Industry and Mine Automation , 2015， 41487-89.