基于搜索算法的煤矿生产系统可靠性优化研究.pdf

致 谢 致 谢 本论文受到国家自然科学基金“矿井火灾时期通风系统可靠性、稳定性、安全性理论 研究（50704019）”的资助，该论文是课题的部分研究成果。 本论文是在导师贾进章教授的悉心指导和关心下完成的。在两年半的时间里，导师对 学科发展方向的把握和远见卓识，激发了我对科学研究的热情；导师深厚的科研功底和渊 博的学识，使我深深折服；导师严谨的治学态度和一丝不苟的科研作风，改变了我对科学 研究的认识；导师对事业的执著投入，激励着我时刻努力。在此谨向导师贾进章教授致以 我最深的敬意和最衷心的感谢 感谢在完成硕士论文期间对我给予极大帮助和指导的安全科学与工程学院的领导和 老师。同时也向曾给我提供帮助而未提及的所有朋友、老师和同学表示感谢。 在论文的编写过程中，参考了有关的优秀教材、专著、科研论文、学位论文，有关网 站和应用成果，在此向论文参考文献中的各位编著者表示最真诚的谢意。 最后，感谢为评审本文而付出辛勤劳动的专家学者。 摘 要 由于近年来煤矿安全事故频繁发生，因此对煤矿生产系统来说，从设计到生产 管理阶段都要求较高的可靠性。随着煤炭科学技术的不断发展和装备的更新，以及 矿山生产集中程度和机械化程度的提高，其生产系统的可靠性也必须随之提高。而 一般来说，系统的可靠性提高，系统的生产费用随之提高。如何使系统的可靠性尽 量的高，而又使其生产费用尽量的低，由此涉及到了对煤矿生产系统进行可靠性优 化的问题。 煤矿生产系统可靠性优化的目标是在达到可靠度改造目标的前提下，使改造费 用尽可能最少，降低成本，追求生产系统总体最优。由于生产系统比较复杂，则子 系统比较多，传统的优化方法解决此类问题很困难，甚至于无法求解。针对这个问 题，人们提出了一类模拟自然界生物系统行为或过程的仿生智能优化算法，为解决 此类问题提供了新的思路和手段。 本论文总结并分析了煤矿生产系统可靠性优化问题，根据可靠性优化理论建立 了可靠性优化的最少成本模型。本论文在一个设定的场景中，将遗传算法、捕食搜 索算法和蚁群算法这三种搜索算法应用到一个虚拟的煤矿生产系统，进行了可靠性 优化计算，并计算出生产系统可靠性优化的近似最优解。最后对这三种搜索算法进 行了比较。本文研究成果对基于搜索算法的煤矿生产系统可靠性优化研究具有一定 的理论意义和参考价值。 关键词煤矿；生产系统；可靠性；搜索算法；优化 Abstract Abstract As the frequent occurrence of coal mine safety accidents in recent years, the coal mine production systems requires a higher reliability from design to production management phase.With the development of coal science and technology and equipment updating, as well as the elevation of coal mine production concentration and mechanization, reliability of its production system also must increase accordingly. Generally speaking, reliability of the system improves when production cost increases. Therefore, how to increase reliability of coal mine production system as high as possible, while reducing production cost as much as possible is the problem that must be taken into account for the reliability optimization of coal mine production system. On condition that achieving the goal of reliability re, the goal of reliability optimization of coal mine production system is to reduce re cost as much as possible and optimize production system maximally. As the production system is relatively complex, which has more subsystems, traditional optimization s have difficulties in solving such problems, even can not be solved. To this problem, people propose a class of biological intelligence optimization algorithm that simulates the behavior or process of natural biological systems, providing new ideas and means for such problems. This paper summarizes and analyzes reliability optimization problems of coal mine production system, establishes reliability optimization model based on reliability optimization theory. This paper studies the application of Genetic Algorithms, Predatory Search Algorithm and Ant Colony Algorithm in virtual coal mine production system in a virtual scene, carries out reliability optimization calculation, and gets an approximate optimal solution. At last, a comparison is made with these three kinds of search algorithms. The research results herein have certain theoretical significance and reference value for study on reliability optimization of coal mine production system based on search algorithm. Key WordsCoal Mine；Production System；Reliability；Search Algorithm；Optimization 目 录 目 录 摘 要 Abstract 1 绪论...........................................................................................................................................1 1.1 引言................................................................................................................................1 1.2 研究背景与意义............................................................................................................2 1.3 系统可靠性优化国内外研究现状................................................................................3 1.3.1 国外研究现状.....................................................................................................4 1.3.2 国内研究现状.....................................................................................................4 1.4 搜索算法国内外研究现状............................................................................................4 1.4.1 国外研究现状.....................................................................................................5 1.4.2 国内研究现状.....................................................................................................6 1.5 论文的研究内容............................................................................................................8 2 矿井生产系统及可靠性优化的理论......................................................................................9 2.1 矿井生产系统及可靠性概述........................................................................................9 2.1.1 矿井生产系统.....................................................................................................9 2.1.2 矿井系统可靠性...............................................................................................11 2.2 可靠性优化的基本理论..............................................................................................12 2.2.1 可靠性框图.......................................................................................................13 2.2.2 典型系统及其可靠度模型...............................................................................13 2.2.3 系统可靠性优化的过程...................................................................................16 2.3 矿井生产系统可靠性优化模型..................................................................................17 2.3.1 矿井生产系统可靠性框图...............................................................................17 2.3.2 煤矿生产系统可靠度改造的最少成本模型...................................................19 3 基于遗传算法的煤矿生产系统可靠性优化研究.................................................................20 3.1 标准遗传算法..............................................................................................................20 3.1.1 编码方法...........................................................................................................22 3.1.2 适应值函数.......................................................................................................22 3.1.3 选择算子...........................................................................................................23 3.1.4 交叉算子...........................................................................................................25 3.1.5 变异算子...........................................................................................................26 3.1.6 控制参数...........................................................................................................26 3.2 遗传算法在煤矿生产系统可靠性优化中的应用......................................................27 3.2.1 编码方法...........................................................................................................27 3.2.2 初始化过程.......................................................................................................28 3.2.3 适应值函数.......................................................................................................28 3.2.4 遗传算子及控制参数设置...............................................................................29 3.2.5 遗传算法优化结果...........................................................................................29 4 基于捕食搜索算法的煤矿生产系统可靠性优化研究.........................................................30 4.1 基本原理......................................................................................................................30 4.1.1 捕食搜索算法的基本思想...............................................................................30 4.1.2 算法的实现.......................................................................................................31 4.2 捕食搜索算法在煤矿生产系统可靠性优化中的应用..............................................33 4.2.1 可靠性优化模型及算法解的形式...................................................................33 4.2.2 邻域定义...........................................................................................................33 4.2.3 限制的选取.......................................................................................................34 4.2.4 评价函数...........................................................................................................34 4.2.5 参数设置...........................................................................................................36 4.2.6 捕食搜索算法优化结果...................................................................................36 5 基于蚁群算法的煤矿生产系统可靠性优化研究.................................................................37 5.1 基本蚁群算法..............................................................................................................37 5.1.1 基本蚁群算法原理...........................................................................................37 5.1.2 基本蚁群算法数学模型...................................................................................39 5.1.3 基本蚁群算法的具体实现...............................................................................41 5.2 蚁群算法在煤矿生产系统可靠性优化中的应用......................................................42 5.2.1 可靠性优化模型及算法解的空间构成...........................................................42 5.2.2 转移概率及信息素更新方程...........................................................................44 5.2.3 可靠性优化的蚁群算法流程...........................................................................44 5.2.4 参数设置...........................................................................................................48 5.2.5 蚁群算法优化结果...........................................................................................48 结 论.......................................................................................................................................49 参考文献.......................................................................................................................................52 附录 A 遗传算法 GA 部分源代码.............................................................................................55 附录 B 捕食搜索算法 PSA 部分源代码....................................................................................65 附录 C 蚁群算法 ACS 部分源代码 ...........................................................................................71 作 者 简 历.................................................................................................................................75 学位论文数据集...........................................................................................................................76 - 1 - 1 绪论 1 绪论 1.1 引言 人类一切活动的实质不外乎是“认识世界，建设世界”。认识世界靠的是建立 模型，简称建模；建设世界靠的是优化决策，所以“建模与优化”可以说无处不在， 它们始终贯穿在一切人类活动的过程之中。认识世界的目的是为了建设世界，同样 建模的目的就是为了优化。建设世界首先必须认识世界，同样一切优化都离不开模 型[1]。比如，建设一个水电站首先要认识河流的水文规律，而只有综合考虑淹没损 失、水坝造价和发电效益，选择最优的建设方案，才能保证水电站建设的成功。 优化技术是一种以数学为基础，用于解决各种实际问题的应用技术。作为一个 重要的科学分支一直受到人们的重视，并在很多领域得到了广泛应用[2]。国内外的 实践表明，在同样条件下，经过优化技术的处理，对系统效率的提高、能耗的降低、 资源的合理利用以及经济效益的提高均有显著的效果，而且随着处理对象规模的增 大，这种效果也更加明显。 研究优化技术的重要前提就是设计具有普遍实用价值的优化算法。所谓优化算 法，其实就是一种搜索过程或规则，它是基于某种思想和机制，通过一定的途径或 规则来得到满足用户要求的解[3]。优化算法与理论的研究是一个同时具有理论意义 和应用价值的重要课题。 对于具有离散变量的问题，从有限个解中寻找最优解的问题就是组合最优化问 题。煤矿生产系统可靠性优化问题即属于组合优化问题。组合优化问题的计算模型 可以用状态空间来描述，依靠搜索技术在状态空间中搜索解答或解答路径[4]。组合 优化问题是科学研究与工程计算中最基本的问题之一，很多情况下它表现为非线 性、不可微的，同时含有连续变量和离散变量的问题[5]。这类问题至今仍然没有找 到非常有效的算法解决。 以遗传算法 （GA） 、 捕食搜索算法 （PSA） 、 蚁群算法 （ACS） 等为代表的搜索算法的出现，为组合优化问题的求解提供了一条新的途径，并在各 种工程应用领域得到了广泛的应用。 - 2 - 1.2 研究背景与意义 煤矿生产系统是多工序、多环节、多设备组成的复杂系统，加之地下作业的特 殊环境和作业场所的动态性，因而存在着大量影响生产的随机因素，致使我国多数 矿井生产不平衡、单产低、效益差，其重要原因之一就是其可靠性受制于多种随机 因素。在矿井生产的设计、管理上缺乏科学依据，很少考虑系统的可靠性及提高可 靠性的对策。随着高产高效矿井建设的发展及科技进步的不断提高，矿井生产系统 可靠性的研究就显得更为重要和十分必要。目前，我国已出现不少“一矿一面”或 “一矿两面”的高产高效矿井，如果系统的可靠性不高，经常发生故障而影响生产， 其影响的则不只是一个工作面的生产，而是影响整个矿井的生产问题。 为了增加系统的可靠性，系统在重量、体积、经费等方面要付出较多的“代价” 以满足系统高可靠性的要求。因此涉及到了对煤矿生产系统进行可靠性优化的问 题。 现今，科学技术正处于多学科相互交叉和融合的年代。特别是，计算机科学与 技术的迅速发展，从根本上改变了人类的生产与生活。同时，随着人类生存空间的 扩大以及认识与改造世界范围的拓展，人们对科学技术提出了新的和更高的要求， 其中对高效的优化技术和智能计算的要求日益迫切。 系统可靠性设计有时并不等于优化设计。在规定的使用条件和使用时间内，可 靠性设计虽然可以确保可靠性指标实现，但它不能保证系统具有最佳的工作性能、 最低的成本和最大的效益[6]。系统优化设计也并不包含可靠性设计。因此，要使系 统既达到可靠性要求，又需要其具有最优化的设计结果，就必须将可靠性设计理论 和最优化技术相结合，即采用可靠性优化方法[7]。按照这种方法进行设计，既能定 量地给出系统在使用中的可靠性，又能得到在功能、成本等方面的最优解。 可靠性优化理论是随着可靠性在系统工程中的重要程度日益增加而逐渐兴起 的。人们在研制系统时，尤其某些精密的系统（航天器、精密电子设备等），对于 可靠性的要求非常高，因此在可靠性设计中，人们就提出了一种方案，即通过提高 系统元件的可靠性或者增加并联冗余元件的方法来提高系统的可靠性，由于在这一 - 3 - 过程中，系统往往需要满足某些约束条件（成本、体积和重量等），所以这使人们 联想到了利用数学规划方法中的最优设计理论来解决这类问题[8]。最初的尝试始于 20 世纪 60 年代， 研究者将已有的优化方法应用到了简单的元件可靠性分配问题中， 获得了很好的效果，随后越来越多的研究者投身到这一领域的研究中。经过将近 50 年的发展，可靠性优化已经成为提高系统可靠性的一个非常重要有效的手段，在可 靠性设计中占据越来越重要的地位。 作为可靠性优化重要组成部分的优化算法的发展也促使可靠性优化的广泛应 用。在可靠性优化起步阶段，由于传统优化算法绝大部分是精确算法（Accurate algorithms），它们大多要求系统函数具有连续、可微等较好的数学性质，可是大部 分的可靠性系统函数却是非线性的，二者的冲突导致那时研究的可靠性模型较为简 单，应用范围也很狭窄，可靠性优化理论发展缓慢[9]。为此，人们尝试提出了启发 式算法（Heuristics algorithms）。这种算法针对具体的问题进行优化，但这些算法 一般都比较复杂、难于理解，得到的结果也不理想，并且通用性很差，一般只能用 于特定的问题。 近些年来，出现了一类仿生智能算法，这类算法一般是指利用自然界的生物系 统与优化过程的某些相似性而逐步发展起来的优化算法，它们通过对搜索空间中的 一组解按某些概率规则操作得到下一组解， 实现在整个解空间中对优良解的探索[7]， 具有代表性的算法包括遗传算法，捕食搜索算法，蚂蚁算法等。 1.3 系统可靠性优化国内外研究现状 可靠性优化方法是在常规优化设计方法的基础上，结合可靠性设计理论，发展 起来的一种有效的优化设计方法。它将可靠性分析理论与数学规划方法有机地结合 在一起，也就是将可靠性作为追求的目标或者约束条件，运用最优化方法得到在概 率意义下的最佳设计的一种数值计算方法[7]。从工程实用的角度来看，可靠性优化 设计方法是有着比传统的优化设计方法更为合理的设计模式，并且它可明显地提高 设计质量和获得明显的经济效益。因此对它的研究已成为目前国内外学者积极探索 和研究的重要领域之一。 - 4 - 1.3.1 国外研究现状 1959 年 Charnes 和 Cooper 首先提出利用随机规划方法解决工程中具有随机设 计参数的优化设计问题，之后被众多学者广泛地应用于结构的安全设计中[10-11]。 1960 年 Hilton 和 Feigen 最早提出了基于可靠性的重量最小的优化公式，开创 了可靠性优化设计研究的先河[12]。随后许多学者都在这一领域做出了重要贡献。 文献[13-15]提出了利用可靠性指标来建立可靠性优化模型，再利用优化算法进 行求解，取得了良好的效果。 1.3.2 国内研究现状 1984 年国内学者程耿东利用可靠性对航空材料进行优化设计， 实现了既能省料 又具有较大可靠性的一个折衷方案[16]。 1985 年陈立周等提出基于可靠性分析的零件优化设计的一般方法， 以零件可靠 度不低于给定水平作为设计依据[17]。 1987 年冯元生提出以残余结构可靠度指标为约束的设计原则、 理论和相应的优 化设计方法[18]。 2000 年宋笔峰提出了利用大系统设计方法进行大型结构可靠性设计， 该思想是 从结构方案阶段既考虑结构可靠度指标又考虑重量指标的最优分配[19]。 2004 年郭书祥提出基于能度可靠性的优化设计方法， 是用模糊变量来描述结构 的不确定性[20]。 1.4 搜索算法国内外研究现状 20 世纪 80 年代以来，一些新颖的仿生智能算法，如人工神经网络、遗传算法、 模拟退火算法、蚁群算法、捕食搜索算法等，通过模拟或揭示某些自然现象或过程 而得到发展，为解决复杂问题提供了新的思路和手段[21]。仿生智能算法作为新兴的 搜索算法，一般是指利用自然界的生物系统与优化过程的某些相似性而逐步发展起 来的优化算法[22]，它们通过对搜索空间中的一组解按某些概率规则操作得到下一组 解。 - 5 - 这类新的优化算法一般都是建立在生物智能或物理现象基础上的随机搜索算 法，目前在理论上还远不如传统优化算法完善，往往也不能确保解的最优性。但这 些优化算法在搜索策略中引入了随机因素，可同时在大量方案中按特定策略随机搜 索，以一定的概率求得全局最优解。 该类算法对求解问题的要求低、适应性广，可同时处理整数变量和连续变量， 对于大规模组合优化等复杂问题也有较好的性能。由于这些独特的优点和机制，这 些算法引起了国内外学者的广泛重视并掀起了该领域的研究热潮，且在诸多领域中 得到了广泛应用，展示出强劲的发展势头[7]。系统工程、自动化、计算机、采矿、 机械等许多专业的学者和学生都在广泛地采用。比如，遗传算法、禁忌搜索算法、 模拟退火算法、蚁群算法和捕食搜索算法等在国民经济的各个行业中都得到了广泛 的应用。 1.4.1 国外研究现状 （1） 遗传算法国外研究现状 遗传算法是 20 世纪 60 年代，美国密执安大学的 John Holland 教授[23]在研究自 然和人工系统自适应性行为的过程中， 认识到生物的自然遗传现象与人工自适应系统行 为的相似性，并提出在研究和设计人工自适应系统时，可以借鉴生物遗传的基本原理，模 仿生物自然遗传的基本方法。 1975 年，Holland 出版了经典著作Adaptation in Nature and Artificial System ，该书是 系统论述遗传算法和人工自适应性系统的专著，提出了一整套具有不可估量指导作用的模 拟生物自适应性系统理论[23]。 1983 年，Goldberg 将遗传算法应用于实际的工程煤气管道的优化。并于 1989 年，Goldberg 出版了专著Genetic Algorithms in Search, Optimization and Machine Learning ，该书系统总结了遗传算法的主要研究成果，全面而完整地论述 了遗传算法的基本原理及其应用[24]。 1991 年，Davis 编辑出版了Handbook of Genetic Algorithm ，书中包括了遗传算法在 科学计算、工程技术和社会经济中的大量应用实例[25]。 - 6 - 目前，关于遗传算法研究的热潮仍在持续，越来越多从事不同领域的研究人员已经或 正在置身于有关遗传算法的研究或应用之中[8]。 （2） 捕食搜索算法国外研究现状 捕食搜索算法 （Predatory Search Algorithm， 简称 PSA） 是由巴西学者 Alexandre Linhares 在 1998 年提出来的一种新的仿生计算方法。Alexandre Linhares 把捕食搜 索策略分别应用于解决旅行商问题（TSP）和超大规模集成电路设计（VLSI）问题， 都取得了较好的