英语原文共 12 页
蚁群优化对露天矿的长期生产规划
Masoud Soleymani Shishvan, JavadSattarvand
1.代尔夫特理工大学土木工程与地球科学院资源工程，荷兰代尔夫特2600 GA邮政信箱5048号
2. 伊朗大不里士萨克森理工大学采矿工程系
3. 德国亚琛工业大学表面采矿与钻井研究所（BBKIII）
文章信息
文章历史：2012年12月3日收到
2014年7月25日接收
2014年8月4日在线可提供
【摘要】露天矿的长期生产规划问题是一个很大的组合问题。由于大量的决策变量，数学编程方法的应用遭受降低的计算效率。本文提出了一种基于蚁群优化（ACO）的新的启发式近似方法，用于解决露天矿生产计划问题。它是一种三维优化程序，具有考虑任何类型的目标函数，非线性约束和实际技术限制的能力。通过在真实规模的铜金矿床上应用，对拟议的工艺进行编程和测试。该研究表明，ACO方法能够提高初始采矿计划的价值，该价用被视为当前商业工具在合理的计算时间内考虑处罚而没有处罚。检查了几种ACO变体，以找到最兼容的变体和最佳参数范围。结果表明，Max-Min Ant系统（MMAS）和蚁群系统（ACS）基于所需的较少内存量的可能变体是最好的。事实也证明了MMAS就是这样最具探索性的变体，而ACS是最快的方法。
【关键词】：启发式、露天矿、组合优化、计划生产、蚁群优化
1.介绍
矿坑开采是一种矿物开采方法，通过挖掘地表面的大开口（称为矿坑）来进入矿床，露出矿石。 采矿作业最初从一个小坑开始，并发展到一个较大的坑，封闭前一个坑。该过程一直持续到矿山的最终形状称为“最终坑限”（UPL）。 这些坑的序列称为挖掘序列或推回。过去30年来，在采矿业应用数值方法方面发生了广泛宣传的革命，以便在更复杂且通常更低等级的矿床上制定更好的采矿计划。最近在露天优化领域的研究一直致力于开发新的算法(Sattarvand, 2009):
1.在可理解性和编程方面首先不那么复杂;
2.要求高计算效率才能适用于大型矿床;
3.允许结合真实的采矿复杂性，如可变斜率，工作斜率，货币时间价值，计划材料的质量和数量以及相关的不确定性。
解决这种复杂和大规模优化问题的核心概念是块模型，其中矿体被离散化为常规尺寸块的三维阵列。 该模型可能具有数百万个块，这取决于沉积物的大小和块的大小。 使用不同地质统计技术和经济参数的一组属性（例如吨位和等级）被分配给每个块。
长期露天矿生产计划问题可以定义为指定块作为某种材料类型从矿井中移除的顺序，以便在受制于经济和物理限制的基础上最大限度地提高矿山的总折扣率。
本文提出了一种基于蚁群优化（ACO）的新的启发式近似方法，用于解决露天矿生产计划问题。 考虑到多目标目标和复杂约束，该过程具有优化UPL和长期规划问题的效率。 它融合了约束成目标函数是对目标偏差的一组惩罚。 下一节简要回顾了现有技术，对元启发式算法的简短描述，并回顾了露天矿优化领域以前开发的元启发式方法。 此后，描述了ACO建模的基本结构及其在露天矿场优化中的适用变型。 最后，阐述了长期露天矿计划的拟议程序，并提出并讨论了其在实际规模的铜金矿上的应用结果。
2. 问题陈述
2.1数学公式
在60年代后期，研究人员只专注于UPL问题。基于图论的Lerchs和Grossmann算法（Lerchs＆Grossmann，1965）和基于网络流概念的最大流算法（Johnson，1969）是解决这一问题的第一次尝试。随后的研究推动了一个更普遍的问题，即生产计划问题。 Gershon（1983）提出了一种混合整数线性规划（MILP）模型。该模型具有二元变量，其目标函数可表示为采矿作业的净现值（NPV）的最大化。 MILP模型受到各种技术限制。例如，提取材料的总吨位，每种材料类型的数量和每个生产要素的平均等级应在预定的限制范围内。此外，排序约束是必要的，如果所有可提取块被删除，确保后继块都具有块。最后，应用保留约束以在数学上保证块仅被挖掘一次。
文献中已经提出了几种方法来解决这个MILP模型。 Dagdelen和Johnson（1986）以及Caccetta，Kelsey和Giannini（1998）使用拉格朗日参数化来放松采矿和铣削约束到目标函数。 因此，问题可以通过重复任何UPL算法来处理，例如（Lerchs＆Grossmann，1965）基于图论的算法。后来Caccetta和Hill（2003）提出了一种分支定界技术来解决制定的调度问题。 Dowd和Onur（1993）以及Onur和Dowd（1993）将该问题表述为动态规划模型。 Ramazan（2007）描述了基本树算法的应用，以重建挖掘块并减少调度问题中的变量数量，而不会降低模型的分辨率或结果的最优性。 他们将基本树定义为可以根据斜率约束进行合理开采的块的任意组合。Boland，Dumitrescu，Froyland和Gleixner（2009）提出了一种迭代分解方法，该方法将聚合（关于处理）重新定义，直到为处理定义的聚合聚合产生线性编程（LP）松弛的相同最优解决方案。 MILP作为LP松弛的最佳解决方案，具有单独的块处理。Bley，Boland，Fricke和Froyland（2010）提出了一个整数规划公式，通过加入由优先级和生产约束相结合得到的不等式来加强。这些不等式的加入降低了获得最优整数解的计算要求。Chicoisne，Espinoza，Goycoolea，Moreno和Rubio（2012）基于众所周知的整数规划公式开发了一种新算法，该公式称为C-PIT方法。 在每个时间段有一个容量限制的时候，所提出的方法使用新的分解过程来解决C-PIT的线性规划松弛。他们表示这只是一个概念的证明，下一步是将关键乘数方法扩展为明确地使用多个边约束。
所有这些确切的方法都受到决策变量数量的限制，并且可以解决相对较小的问题，排除了许多实际意义。
2.2启发式
元启发式是一组算法概念，可用于改进启发式方法以适用于困难问题。 这些概念通常受生物学和自然的启发。 在合理的时间内，元启发式的使用具有重要意义，增加了为大型组合问题（通常易于陈述但很难解决）找到高质量解决方案的能力。 对于难以理解的大问题尤其如此。 元启发式的族包括但不限于遗传算法（GA），模拟退火（SA），禁忌搜索（TS），ACO和粒子群优化（PSO）。
Denby和Schofield（1994）描述了GA在优化图1a所示的露天矿生产计划中的应用过程。他们的方法的主要优点是能够同时解决最终的坑限和长期规划问题。通过选择适当的遗传参数值，该方法能够在可接受的时间内为小块模型产生良好的结果。后来Denby和Schofield（1995）继续在其调度过程中考虑风险评估。他们还将算法从2D扩展到3D（Denby＆Schofield，1996）并将其用于灵活的调度操作（Denby，Schofield，＆Surme，1998）。
Kumral和Dowd（2002,2005）通过SA研究了露天矿生产调度问题的解决方案，如图1b所示。 该例程的主要优点是它利用了由三个最小化组件组成的多目标函数。另一方面，UPL和生产计划的单独确定将被视为该方法的缺点。Godoy和Dimitrakopoulos（2004）使用模拟退火方法对废物开采和矿体等级不确定性进行有效管理。它们的目标函数可以最大限度地减少在不同情况下每个时期偏离生产目标的可能性。最近Lamghari和Dimitrakopoulos（2012）针对金属不确定性领域的露天矿生产调度问题提出了一种多样化的禁忌搜索方法。他们使用两种不同的多样化策略来生成多个初始解决方案，然后使用TS方法优化这些解决方案。
2.3蚁群优化
ACO受到蚂蚁群落觅食行为的启发，由Dorigo和Stuuml;tzle（2004）开发。在自然界中，蚂蚁随意行走，一旦发现食物返回其殖民地，同时放下称为信息素的化学路径。信息素踪迹将信息传递给殖民地的其他成员。其他蚂蚁可能跟随踪迹而不是随机旅行。如果他们最终找到了食物，那么通过沉积更多的信息素来加强这种追踪。随着时间的推移，信息素的踪迹开始蒸发并降低其吸引力。显然，较长路径中蒸发的幅度高于较短路径。因此，相比之下，在最短路径上铺设的信息素的强度逐渐增加到与蒸发速率平衡的水平。这使得最短的路径被几乎所有的蚂蚁行进和跟随。蚁群优化的方法通过考虑一系列变量来模拟这种自然行为，这些变量代表并基于所找到的解决方案的质量不断更新信息素值（Dorigo＆Stuuml;tzle，2004）。
3. ACO长期露天矿场规划方法
大多数数学规划方法受限于决策变量的数量，因为长期露天矿问题的应用变得非常大并且遭受降低的计算效率。这一事实鼓励研究人员针对这个问题使用不同的求解器。在领先的优化问题中，例如旅行销售人员（TSP），车辆路线和分配问题，（Dorigo＆Stuuml;tzle，2003），ACO方法应用于找到最优或接近最优的解决方案。以下描述了ACO在露天矿规划领域的应用方法。图2显示了使用ACO的长期露天矿生产计划的流程图。
3.1初步解决方案
该算法包括为模型的每个块保存P变量，tau;ip其表示与第p个周期中的第i个块的挖掘相关的信息素值。保存的信息素的大小代表了一个区块成为该时期矿山最深点的可取性。这些变量的初始值是根据传统算法生成的次优矿井时间表来分配的。然后根据初始信息素构建随机采矿计划。这些计划存储与其经济质量（适合度值）成比例的额外信息素。这个动作以及考虑算法中的信息素蒸发，导致采矿后推的最佳边界。
3.2信息素初始化
实验表明，使用均匀的初始信息素模式，运行时间急剧增加。因此，使用针对长期露天调度问题的次优解决方案，并且根据该次优解决方案将初始信息素路径分配给块。通常，期望的后推的形状不会从次优解决方案显著改变到最佳解决方案。因此，将较高信息素分配给次优凹坑深度周围的少数块可足以使算法朝向最优解。在信息素初始化过程中，在初始溶液中接近凹坑形状的矿块的信息素值（图3中突出显示的块）被设置为相对较高的值。
3.3时间表的构建
为了构建矿山调度解决方案，应该创建一系列与不同采矿推回相关的可行坑形。这些凹坑中的每一个都由一系列块柱组成，每个凹坑的形状可以通过确定这些柱上的凹坑深度来定义。信息素值是确定色谱柱凹坑深度的主要因素。但是，考虑到块的经济价值等启发式信息有时也可以帮助提高方法的效率。
3.3.1深度确定的过程
在每个深度确定步骤中，蚂蚁k利用概率选择规则（称为随机比例规则）来确定该列中凹坑的深度。式（1）显示了蚂蚁k选择i作为坑的概率：
= （1）
其中是块i的信息素值，是启发式信息，可以是块值或任何导致算法获得更好解的信息，alpha;和beta;是两个参数，用于确定信息素路径和启发式的相对影响。 信息，是蚂蚁k的可行选择集。 表1中说明了深度确定过程的数值示例。
该组可行选择由允许的凹坑深度的上边界和下边界表示。最大允许深度定义了该柱上最深的采矿深度，而最小深度是根据早期后推中矿井的形状确定的，图4。
应该注意的是，深度定位的过程仅针对包含至少一个矿石块的柱进行。完全废物柱中的坑的深度将基于相邻的选定深度来定义。另一个需要考虑的重要概念是初始信息素仅分配给矿石块。因此，选定的深度将始终在矿块上重合。同样，废物块也不会有信息素更新（蒸发或沉积）。
3.3.2正常化
通常，由于所需的倾斜角度，每列中独立深度确定的结果并不总是可行的。 因此，基于所选择的深度的归一化阶段是必要的，以便产生可行的凹坑形状。该
在确定深度之后实施归一化步骤，以确保构造的凹坑形状覆盖所有确定的深度以及早期后推的轮廓。图5b中所示的可行凹坑形状基于所确定的深度和图5a中显示的早期形状。
规范化过程按以下步骤实现：
1.从块模型的最深层开始，检查此级别中的所有块。如果任何列的计算深度等于此级别，则将该块和所有上部块作为坑内块。
2.移到上一级并检查所有块。 如果满足以下条件中的至少一个条件，则将任何块标记为坑内块
（1）如果包含该块的任何列中的计算深度等于或低于当前级别。
（2）如果包含该块的任何列中的最小深度等于或低于当前级别。
（3）如果该块中至少有一个潜在的直接后继块，Shishvan和Sattarvand（2012）更细节地将这些块称为坑内块。
3.重复上一步到最高级别。
3.3.3从生成的矿坑开采矿井计划
最后，将不同采矿期的单个标准化坑组合在一起，形成一个采矿计划，如图6所示。
3.4信息素更新（蒸发和沉积）
ACO模块分两步操纵黑色的初始信息素值。第一步，称为信息素蒸发，包括统一减少所有的价值信息素以帮助ACO模型忽视不良解决方案。在此阶段，对应于所有生产计划的所有块的信息素值应减少一定百分比。下一步，信息素沉积，包括向块中添加额外的信息素，这有助于构建时间表。应注意，沉积作用仅应用于矿石块。在凹坑深度落在废物块上的情况下，额外的信息素被分配到地面上的假想块。这一行动创造了一个想象的区块，以与其他矿石区块竞争，而这些区块在建设时间表方面没有真正贡献。
通常，ACO的信息素更新过程可以以多种方式实现。蚁群系统（AS）是第一种也是最简单的方法，允许所有构建的时间表对信息素沉积做出贡献。在第二种方法的每次迭代中，Elitist Ant系统（EAS），在该迭代（最好的迄今为止的时间表）之前找到的最佳时间表也被允许存放信息素。基于排名的Ant系统（ASrank）是第三种方法，其中只有少数良好的时间表能够添加信息素。其他变体
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
