基于差分进化算法的煤矿选址问题的研究

编 号 ：（ ）字 号本 科 生 毕 业 设 计 （ 论文 ）题目： 姓名： 学号： 班级： 基于差分进化算法的煤矿选址问题的研究李曙光 22091615信电系 自动化 09-3 班二一二年六月中 国 矿 业 大 学本 科 生 毕 业 设 计姓 名：_李曙光_ 学 号： 22091615_学 院： 徐海学院 专 业： 自动化 设计题目： 基于差分进化算法的煤矿选址问题的研究 专 题： 指导教师： 张勇 职 称： 教授 2013 年 6 月 徐州中国矿业大学毕业设计任务书学院 徐海学院 专业年级 自动化 09-3 学生姓名 李曙光 任 务 下 达 日 期 ： 年 月 日毕业设计日期： 2013 年 2 月 20 日 至 2013 年 6 月 20 日毕业设计题目：基于差分进化算法的煤矿选址问题的研究毕业设计专题题目：毕业设计主要内容和要求：针对煤矿选址问题，设计一种动态差分进化方法，主要要求如下：1） 掌握差分进化算法及其研究现状；2） 建立问题的数学模型；3） 将差分进化算法用于模型求解，给出设计方案；4） 实验、仿真院长签字： 指导教师签字：中国矿业大学毕业设计指导教师评阅书指导教师评语（基础理论及基本技能的掌握；独立解决实际问题的能力；研究内容的理论依据和技术方法；取得的主要成果及创新点；工作态度及工作量；总体评价及建议成绩；存在问题；是否同意答辩等）：成 绩： 指导教师签字：年 月 日中国矿业大学毕业设计评阅教师评阅书评阅教师评语（选题的意义；基础理论及基本技能的掌握；综合运用所学知识解决实际问题的能力；工作量的大小；取得的主要成果及创新点；写作的规范程度；总体评价及建议成绩；存在问题；是否同意答辩等）：成 绩： 评阅教师签字：年 月 日中国矿业大学毕业设计答辩及综合成绩答 辩 情 况回 答 问 题提 出 问 题 正 确基 本正 确有 一般 性错 误有 原则 性错 误没 有回 答答辩委员会评语及建议成绩：答辩委员会主任签字： 年 月 日学院领导小组综合评定成绩：学院领导小组负责人： 年 月 日摘 要选址问题是实际工程中普遍存在的一类优化组合问题，其目的是：在保证某些评价指标同时最优的基础上为多个服务设施或工厂在指定的区域内选定它们的位置。由于该类问题具有很强的应用背景，因此其研究一直备受学者的关注。本文研究用于项目选址的差分进化算法。由于选址问题是个离散化的模型问题，而传统差分进化算法多用来节约连续问题，因此，首先通过定义等效概率矩阵，将多目标选址这一离散变量多目标组合优化问题转化为连续变量多目标组合优化问题；然后，利用差分进化算法优化确定模型，给出离散变量连续化、微粒位置归一化、微粒位置解码等关键问题的解决方法。最后，应用于煤矿设施选址问题中，验证所提方法的有效性。通过系统仿真证明了改进差分进化算法在实际的工程项目选址中具有较强的实用性。综上所述，本文简要分析了差分进化算法和煤矿选址问题，将差分进化算法引入煤矿选址问题中，建立基于差分进化算法的煤矿选址的模型。通过采用差分进化算法进行计算，更加简单、有效，更具全局寻优能力，增加了决策的科学性、规范性。关键词：多目标优化；差分进化算法；煤矿；选址AbstractLocation problem is common in practical engineering problems of optimum combination, its purpose is: to guarantee certain evaluation index on the basis of the optimal for multiple services at the same time or the factory where they are selected in the specified area. Because this problem has a strong application background, so its research has been under the attention of scholars. This study used in the project location of differential evolution algorithm. Due to the location problem is a discretization of the model problem, the traditional differential evolution algorithm is used to save more continuous problems, therefore, first of all, by defining the equivalent probability matrix, the multi-objective location this multi-objective combinatorial optimization problems of discrete variable multi-objective combinatorial optimization problem is transformed into continuous variables; Then, differential evolution algorithm is used to determine the model of discrete variables are continuous, normalization of particle position, such as particle position decoding key solution of the problem. Finally, applied to coal mining facility location problem, verify the validity of the proposed method. Through system simulation proves that the improved differential evolutionary algorithm in the actual project site selection has stronger practicability. To sum up, this paper analyzes the differential evolution algorithm and coal mine site selection problem, the differential evolution algorithm was introduced to mine site selection problem, the location of the coal mine based on differential evolution algorithm model is established. Through calculated, using differential evolution algorithm is more simple and effective, more global optimization ability, and increases the decisions more scientific and normative. Key words: multi-objective optimization; Differential evolution algorithm; Coal mine; Site selection目 录1 绪 论1.1 课题研究的背景和意义众所周知，煤炭作为我国的主要能源，是国民经济和社会发展不可缺少的物资基础。作为基础能源工业的煤炭工业历经近半个多世纪的发展后正趋于大型化、现代化、集团化、智能化的方向发展，随着如此发展趋势，很大影响了煤炭工业的规模和收益，故而在煤矿建设方面的改进也当变化巨大。通过如何现代化方法来完成对煤矿建设初始的煤矿选址问题的优化，来加强矿井建设,将为煤矿建设管理的提出更高要求。但是由于一些不确定性因素的影响 ,当前煤矿的建设管理模式,相对落后于其它建设工程领域, 在煤矿建设项目选址优化研究方面与其它行业也存在着一定的差距，但近几年来对此类问题的研究也得到了很大的重视，其研究成果必将得到重大突破。作为煤矿建设过程中首要解决的煤矿选址问题是实际工程中普遍存在的一类组合优化问题，其目的是：在保证某些评价指标同时最优的基础上为多个服务设施或工厂在指定区域内选定它们的位置，如变电设施地址的选择问题，物流交换中心的选址，灾害救援中心的确定，交通换乘中心的选址以及煤矿企业各个井上设施的选址问题等。由于具有很强的实际应用背景，因此其研究一直备受学者的关注，在很多类似模型的研究中也取得了很大的研究成果和突破。差分计划算法1(Differential Evolution, DE)是一种基于群体智能理论新兴的进化计算技术，该算法主要用于解决那些利用常规的数学规划方法不能求解的复杂环境下的优化问题，所实现的群体智能的指导优化搜索功能由基于群体智能理论的群体内个体间的合作、竞争过程所产生, 在保留了种群全局搜索功能的前提下，利用实数编码基于差分的简单变异操作以及一对一的竞争生存策略，降低了操作的复杂过程, 无需依赖于问题的本征特点，且具有明显优胜的鲁棒性和全局收敛能力。差分计划算法可以为煤矿选址提供一种可行测求解方法，因此，具有一定的实际指导价值和理论意义。1.2 研究内容及方法本文主要研究利用差分进化算法解决基于多目标多项目模型的煤矿选址问题，换而言之为研究用于多项目选址问题的智能优化方法（本文中主要指 DE）。通过本次简单的研究，给出一种用于求解离散变量多项目选址问题的差分进化的优化方法，并将其用于煤矿选址问题这一典型选址问题。其主要研究内容包括：熟悉差分进化算法的原理和特点，概述项目选址已有方法；给出离散多项目选址问题的模型，以及离散变量优化模型的连续型转化方法；用于问题求解的差分进化方法以及在选址问题上的应用。本文主要采用的研究方法有：通过采用差分进化算法把离散变量多项目选址问题转化为连续变量优化问题，进一步利用差分进化算法解决此问题，最终用于解决煤矿选址问题。1.3 论文框架本文针对离散变量多项目选址问题的差分进化算法及其在实际工程项目中的应用展开研究，提出了相应的解决方法：首先定义约束条件和处理策略，把含离散变量多目标优化模型转化为离散变量单目标优化命题；接着，利用差分进化算法优化该模型，优化该模型，给出离散变量连续化、粒子位置归一化、粒子位置解码等关键问题的解决。最后用于煤矿井上设施选址这一具体现实问题，证实了用于离散变量多项目选址问题的差分优化算法的切实有效性。本文具体结构安排如下：第 1 章简要地概括本论文研究意义、研究内容、研究方法和框架。第 2 章概述差分进化算法和多目标多项目选址问题的研究现状。第 3 章是本文的主要内容，重点介绍用于离散变量多项目选址问题的改进差分进化方法及其在煤矿井上设施选址问题上的应用。第 4 章总结了论文取得的研究成果，并对未来研究前景及发展进行了展望。1.4 本章小结本章在简要说明论文的研究背景和意义后，给出了论文的研究内容及目标，最后，给出了论文的框架。2 差分进化算法本章主要介绍与研究课题相关的基础工作，主要包括差分进化算法的综述，以及多项目选址问题的发展现状。2.1 差分进化算法2.1.1 差分进化算法的来源和背景 在诸多实际工程和科研领域中存在很多目标函数为非线性不可微的连续空间数值优化问题2，在使用纯铜优化方法来解决此类为题时效果多为不佳。于上世纪五十年代创立的仿生学就能完美解决现实中的自适应和自组织问题，此类研究学方法在解决此类问题中的完美呈现使得越来越多的人们开始逐步开始对自然演化过程进行了大量研究，期望得出解决其他复杂问题的自然模型和方法，例如作为计算机科学领域中的一个重要分支的演化计算方法正是利用这种方法所得到的重要研究方法。由近半个多世纪的研究证明，诸多具有完美鲁棒性的计算方法多可以从自然进化搜索过程中演化产生，对于自然界中较为简单常见的演化过程中或许都存在着某种潜在的重要的数学模型存在，例如较早从此类进化过程中所研究得到的进化规划(Evolutionary Programming)、遗传算法(Genetic Algorithm)等经典优化算法，当然利用这种思想所能演化出来的算法相信未来还会有很多很多，此类研究对于优化问题及其他方面的贡献非常之大。并且这些算法在赋予演化算法自组织、自适应、自学习等特征的同时，不受搜索空间限制性条件(如是否可微、是否连续等)的约束，也不需要其他辅助信息(如梯度)，不仅能获得较高的效率，而且具有易于操作和通用等特点。1997 年，Rainer Storn 和 Kenneth Price 在遗传算法等进化思想的基础上3，提出了一种新颖进化算法：差分进化算法（DifferentialEvolution Algorithm，DEA）9-10。该算法同样是模拟自然界生物进化机制的一种仿生智能算法，它最主要的操作思想是基于种群内的个体差异度生成临时个体，然后随机重组实现种群进化。差分进化算法(Differential Evolution, DE)是一种新兴的进化计算技术，其最初的设想是用于解决切比雪夫多项式问题,后来发现 DE 也是解决复杂优化问题的有效技术。DE 与人工生命,特别是进化算法有着极为特殊的联系。DE 和微粒群算法( PSO,也称粒子群算法)一样,都是基于群体智能理论的优化算法,通过群体内个体间的合作与竞争产生的群体智能指导优化搜索。差分计划算法是一种新兴的进化计算技术，是基于群体智能理论的优化算法，通过群体内个体间的合作与竞争产生的群体智能指导优化搜索, 保留了基于种群的全局搜索策略，采用实数编码基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性, 具有较强的全局收敛能力和鲁棒性，且不需要借助问题的特征信息，适于求解一些利用常规的数学规划方法所无法求解的复杂环境中的优化问题。该算法具有较好的全局收敛性和鲁棒性，适合于求解各种数值最优化问题，使得该算法迅速成为了当前优化领域的一个研究热点DE算法从某一随机产生的初始群体开始，并通过选择、交叉、变异等循环迭代计算来实现种群的进化，并通过适应度选择对粒子进行优胜劣汰，来实现种群向最优状态进化。DE的原理简单，且受控参数少，其操作过程容易实现和理解，更适用于解决多目标多项目的选址问题。当下对于DE的参数设置、进化机制、实际研究应用研究及与其它算法的融合机制的研究等方面的研究成为对该算法的主要研究方向。综上所述，目前，已成为一种求解非线性、不可微、多极值和高维的复杂函数的一种有效和鲁棒的方法4。目前，差分进化算法已引起了人们的关注，在国外的各项研究领域得到了广泛的应用，已成为进化算法（）的一个重要分支。但目前，在国内的研究和应用较少。2.1.2 差分进化算法的原理基本DE算法差分演化算法是基于实数编码的进化算法，最初的群体是随机均匀产生的，每个个体为搜索空间中的一个实向量。令 是第g个代的第i个个体， ，则 （1） 形成初始种群（Initialization）在维空间随机产生个 NP个体，实施措施如下： )(1,0()0( LijUijLijij xrandxx （式2-2）（2） 变 异 操 作 （Mutation）变异操作是差异演化的关键步骤，是从种群中随机选择3个个体： 则 F为缩放因子。 )(gXi ）1-2（ 式,21;,21),(),( max21 TNPgxxXinii 为 最 大 进 化 代 数 。 为 种 群 规 模 ，为 个 体 的 上 、 下 界 ，、maxTNPUL 数 。上 服 从 均 匀 分 布 的 随 机1,是randippXp 321且,321 ）3-2（ 式)()(jjij xFxghXUL图2-1 变异操作过程二维原理图（3） 交 叉 操 作（Crossover ）交叉操作可以增加群体的多样性，使之跳出局部最优点，具体操作如下： ,1,1,()()2-4ijGijGijvfrandbjCRorjnbriux （ 式 ）randb()为0,1上服从均匀分布的随机数rnbr(i)为0,D之间的随机整数；CR为交叉因子如此交叉操作可保证 中至少有一个是由 中的相应分量所提,1ijGu,1ijGv供。交叉过程如下图所示：图2-2 交叉过程示意图（4） 选择操作 ( Selection )由评价函数对向量 和向量 进行比较。 反复执行2) 到4) ，直到达到最大进化代数，或达到所要求的收敛精度 DE算法流程5（1） 确定DE控制参数和所采用的具体策略 ,DE控制参数包括 :种群数量、变异算子、交叉算子、最大进化代数、终止条件等;（2） 随机产生初始种群 ,进化代数K=1;（3） 对初始种群进行评价 , 即计算初始种群中每个个体的目标函数值;（4） 判断是否达到终止条件或进化代数达到最大来决定是否继续进行进化操作;（5） 执行变异、交叉操作 , 并对边界条件进行处理 ,得到临时种群;（6） 对临时种群进行评价 , 计算临时种群中每个个体的目标函数值;（7） 执行选择操作 ,得到新种群;（8） 进化代数 K=K+1 转步骤 (4)(1igv()igx,)()(1) -()i ii iffgx （ 式 25）图 2-3 DE 算法流程图2.1.3 差分进化的参数设置由于 DE 算法的很多优点，在近些年很受关注并且在很多方面得到了应用和研究，对于算法本身很多方面的研究如与 DE 算法相关的进化研究及 DE 算法的参数设置方面的研究也取得了很大的突破，DE 算法的主要参数有种群规模 NP、变异算子 F 以及交叉算子 CR，这些参数对 DE 算法的全局优化性能有着很大的影响，综合对这些控制参数的选择经验和规则，总结如下：种群规模 NP 的选择总结很多对于种群规模的研究结果中，在一般情况下 NP 越大，虽然所要处理的计算过程越大故而要增加很多计算时间，但是在 NP 增大到一定程度以后所得到的优化结果并非继续向最优化过程发展，很多情况下而是保持一定的优化程度没有变化，故在超越一定的 NP 后会浪费很多计算过程，增加算法计算过程和计算时间，对优化结果并非一定有好处。在一般的处理情况下，NP 取 5 至10 之间，且 NP 不小于 4，从而确保 DE 过程得到足够的变异过程来满足充分的多样性。变异算子 F综合很多研究，当 0.5F1 时算法能得到较好的优化结果，当 F1 时所得到优化结果相对不佳。在 F 较大的情况下能产生较大的扰动从而更有效地保持了种群的多样性，但是算法的搜索功能退化从而使得算法优化和求解精度降低，产生不良影响；反之在 F 较小的情况下能减少扰动从而实现局部细化搜索的作用，但是算法的多样性优化过程难以实现，使得算法过早收敛。可见 F 对群体的多样性具有有效的调节作用。综上，F 对算法的局部搜索和全局搜索起到了一定的调节作用。F 较大，有利于保持种群多样性和全局搜索；F较小，有利于局部搜索和提高收敛速度。交叉算子6通过研究可知，当 CR 的值较小时，所需的函数评价次数较大，收敛速度较慢，但成功率较高，算法的稳定性好；CR 的值较大时，常常会加速收敛，但易于陷入局部最优，发生早熟现象，达到给定精度的成功率低，稳定性差。可见，成功率和收敛速度是一对矛盾。因此，为了同时保证较高的成功率和较快的收敛速度，对于单峰函数，CR 取值相对较大些在0.6,0.8之间；对其它复杂、多峰函数 CR 取值应相对小些在0.1,0.5之间。新子代个体 U 是由变异个体 V 和父代个体 X 分量间相互交叉而产生的。CR的值越大，则 V 对配 U 的贡献越多，有利于开拓新空间，从而加速收敛，但在后期变异个体趋于同一。不利于保持多样性，从而易于早熟，稳定性差；CR 的值越小，则置 X 对 U 的贡献越多，这样就减弱了算法开拓新空间的能力，收敛速度相对较慢，但有利于保持种群多样性，从而能有较高的成功率。上述参数中 F、CR、与 N 在搜索过程中是常数，其中 F 和 CR 主要影响搜索过程的收敛速度和鲁棒性，它们的优化值不仅依赖于目标函数的特性，还与N 有关。通常可以通过在不同值做一些试验之后利用实验和结果误差找到 F、CR和 N 的合适值。2.1.4 差分进化算法的应用差分进化计算目前在国内外引起了很多学者的重视，由最初的针对解决高维函数求解而提出到目前在原来基础上所得到的很多改进研究成果以及在解决很多实际问题中所取得的很多突破，差分进化越发趋近于成熟发展道路，尤其在解决很多经典实际问题中DE算法所取得的研究成果令人欣慰不已。其中Mehmet Tunckanat，Veysel Aslantas在伤口图像的分割技术中成功应用了DE算法，并成功实现了在聚类问题处理中可实现并行搜索且对初始情况不敏感等特点的聚类算法由DE算法的进化过程，进一步推进了DE算法的深化发展过程 。另外T.Sum-Im等人在应用DE算法在解决膨胀计划问题中得到突破性进展，DE算法在解决该问题时评价其自身的算法特点克服了再解决此类复杂的问题中所要面临的大规模数据处理及对位置复杂度、时间复杂度的高难度处理过程，将过程优化到期望程度。P.N.Suganthan ，M.Fatih Tasgetiren等人研究了将差分进化算法应用于解决非具体的任务指派问题（GAP），着重对离散差分进化算法以及连续差分进化算法做了深刻研究。通过改进离散差分进化算法混合的可变相邻种群区搜索机制（VNS）和连续差分进化算法，并实现了VNST局部搜 索机制。当然DE算法还在很多其它问题的应用中取得了卓越的成就，再次就不一一叙述了。DE算法主要通过实数编码来解决连续剧的优化问题，例如公交车辆调度问题、选择类问题以及很多离散优化问题都属于离散域优化问题，虽然在这方面的研究中很多学者提出了很多不同的研究方法和途径且多采用函数映射方式，相比较于DE算法解决该类问题存在很多弊端。当然，对于DE算法的研究和应用还处于初始阶段，相比那些成熟的早起就比较智能算法DE算法还有很长的路要走路还很长很长，如何从当前较小的研究领域中如何将DE算法逐步推向成熟化道路还需要诸多学者的不懈努力了。2.1.5 算法小结 差分进化计算作为继多种较成熟经典算法（即遗传算法、蚁群算法及微粒子群算法等）之后的又一个进化性的完整解决优化问题的算法，在学术界引起了空前的研究热潮，在对于很多数学模型的优化方面取得了很大的进步，其研究进步也在不断地实现。相比而言，差分进化算法虽然起步较晚，需要发展和完善的地方也是确实存在的，进一步的研究工作还需要很多。当下关于该算法产生了很多的改进新算法，并通过很多实验证明了其有效性，但在证明其寻优收敛必然性、科学性和可行性等方面还缺少比较权威的解释，故在这方面的研究将成为而后对DE算法的主要研究方向，也成为对DE算法发展的重要分支方向。另外目前对通过DE算法与其他智能算法的融合来生成新的混合算法方面的研究也非常多，但基本上都是限于简单的组合，主要是针对如何保持种群多样性方面进行的研究。这种融合方式虽然在保持种群多样性方面的效果比较好，但是由于增加了额外的计算，使得混合后的算法效率并不高，研究如何深层次地有效融合，也是未来重要的研究方向之一。2.2 项目选址问题多目标选址问题是实际工程中普遍存在的一类组合优化问题，其目的是，在保证某些评价指标同时最优的基础上为多个服务设施或工厂在指定区域内选定它们的位置，如基于环境污染和运输代价的废弃物回收设施选择问题；兼顾运行成本和覆盖率的无线通讯网基站的选址等。 多项目选址作为典型的多目标选址问题，通常给定一个有限点集作为项目的备选位置集合，并以经济效益、社会效益、环境污染等作为评价指标去选择多个给定项目的位置。解决此类问题，学者们已经给出很多行之有效的方法, 根据所采用的方式可以分为两类：传统数值计算方法和智能优化方法2.2.1 传统数值计算方法（1）基于模糊指派的多目标选址决策模型11：这个模型提出了一种新的多个工程选址的多目标决策方法。运用模糊关系合成矩阵将各种情况下的多目标工程选址问题转化为模糊指派或模糊广义指派问题，并用传统的匈牙利算法来求解。（2）基于奖优罚劣原则的多目标多项目选址决策模型：针对多目标多项目选址问题，构造出一种新的效用转换函数，并根据该转换函数将原始属性矩阵归一化到效用矩阵上，在此基础上，提出一种新的基于“奖优罚劣”原理的多目标多项目选址决策模型和实施步骤，提高了分辨精度，使决策更加科学。（3）基于网络最大流寻优的模糊网络图决策方法：根据多目的模糊决策理论，首先提出了接近度的概念，其次计算模糊关系矩阵并将其转化为接近度网络图。在此基础上，建立了基于网络最大流寻优的多目标有约束关系的模型来解决相应的问题。2.2.2 智能优化方法由于启发式智能优化技术不需要问题的特征信息，可以快速找到问题的理想解或次优解，目前智能优化技术已广泛用于各类复杂工程优化问题。利用智能优化技术处理项目选址问题，相关工作包括：（一）基于混合遗传算法选址问题：基于区域配送体系中的多配送中心选址模型中的主要问题研究方案，首先构建确定性规划模型，规划出混合遗传算法的完整解决途径。该算法结合了多种遗传算法的优点，使部分种群择优进化的同时整体种群的解全局收敛。（二）基于层次遗传算法选址问题：在遗传算法的基础上，首先构建了层次遗传算法，即集成两个改进的遗传算法分别求解上下两层的规划问题，再通过二者之间的交互迭代博弈达到平衡状态，以此来求解物流配送中心的选址问题。（三）基于改进遗传算法选址问题：为了防止遗传算法在迭代过程中破坏种群优良个体，首先设定自适应交叉率，对种群所有个体进行优化，然后设置自适应变异率，处理种群中存在的较劣个体。该算法较好地保留种群的优良个体，能够较稳定地获取全局最优值。（四）基于遗传算法的 Pareto 多目标选址模型7： 该模型采用了栅格单元行列号组合的编码方法及多种重组方式的遗传算子，可求解大规模数据范围的多目标空间选址问题。（五）基于“分步逼近”策略的蚁群智能的优化选址8：首先对搜索区域进行尺度转换，利用蚁群算法在转换后的低分辨率的空间中搜索出初步的最优目标栅格。再把低分辨率的空间还原为原来尺度的空间。随后，在原来尺度空间中利用蚁群算法对初步选出的目标栅格在进行一次更精确的优化搜索，以获取最终的目标栅格。（六）基于多叉树蚁群算法的区位选址优化方法：首先对地理空间进行多叉树划分，然后在多叉树的层上构造蚂蚁路径(ant path)，让蚂蚁在多叉树的搜索路径上逐步留下信息素，借助信息素的通讯来间接协作获得理想的候选解。2.3 本章小结本章系统的介绍了粒子群优化算法的原理及研究现状相关知识，以及项目选址问题已有技术，进一步肯定了论文研究的必要性，明确了本文研究的内容和重点。为第四第三章离散变量多项目选址问题的差分进化方法研究做铺垫。3 用于项目选址的差分进化算法上一章给出了差分进化算法等相关工作，本章将其用于项目选址问题，设计一种改进的差分进化算法。首先，给出多项目多位置选址问题的数学模型；解决该模型，接着，设计一种改进的差分进化算法，给出算法的详细步骤；最后，通过用于煤矿设施选址这一实际问题，验证所设计方法的可行性。本章结构如下：3.1 引言在工程设计中,常遇到多项目选址问题9。一个项目能否建在某个位置上,通常要考虑很多因素,这是典型的多目标决策问题。在这类问题中,一般是先提出一个有限位置集备选,再对各方案进行多目标(或因素)比较和评价,确定项目的建设位置,以使整个系统的效益达到相对最佳,例如经济效益、社会效益最大,环境污染最小。由于具体广泛的应用背景，该类问题的研究显得极为重要。本章采用差分进化算法解决离散变量多项目多位置选址这一类复杂组合优化问题。首先，给出问题的优化模型；其次，定义约束违反条件，将离散变量多目标优化模型转化为一般连续型单目标优化命题；接着，利用差分进化算法优化连续型模型，给出离散变量连续化、粒子位置归一化、粒子位置解码等关键问题的解决方法。最后，通过煤矿井上设施选址问题，验证本文所提差分进化算法的可行性。3.2 多项目多位置选址问题103.2.1 问题的描述多项目多位置选址问题是实际工程中普遍存在的一类组合优化问题，其目的是：在保证某些评价指标同时最优的基础上为多个服务设施或工厂在指定区域内选定它们的位置，如废弃物回收设施选择问题，无线通讯网基站的选址，灾害救援中心的确定，连锁门店-配送中心的选址以及煤矿企业各个部门的建址问题等。由于该类问题具有很强的应用背景，因此其研究一直备受学者的关注。在实际的工程项目中，由于决策者只能确定建与不建这两种情形，因此建立的模型是离散化的，而粒子群算法只能处理连续模型，这样我们便只能想办法将离散变量的选址模型转化为连续型的模型11 。命题：对多项目位置优化派对问题 Q，在加权系数 Z 已知，要求一个位置至多只能配置一个项目的条件下，寻找的优化配置，.使总配置系统 Q 的综合效益最佳设 待 建 项 目 集 合备选位置集合；优化指标集合；指标权重集合；3.2.2 模型的建立U,V 是多目标系统的两个有限论域。由 U 和 V 中元素搭配构成关于指标的笛卡儿乘积集。元素对搭配后构成关于目标的属性值矩阵为:(3.2.1)其中，表示项目建在时关于指标的评估值（或属性值，效益值），;，一般。首先考虑优化指标，选址的目的就是寻找的优化配置，使函数(3.2.2)的值达到最优，其中为所对应优化指标属性值矩阵中的元素；而为问题解矩阵中元素。对 中元素有 。X因此,要满足一个位置至多只能配置一个项目的约束条件，有；同样,要满足一个项目只能建在一个位置的约束条件，有。考虑整个优化指标集，多目标多项目选址问题的目的是, 寻找的优化配置,使中所有元素尽量到达最优值。以最小化为例，其数学表达式如下：(3.2.3)(3.2.4)3.2.3 所建模型的转换多目标规划的目标函数是相互冲突的，一般不存在使得所有目标函数取得最优的最优解，而本文研究的是一个最终的优化方案，以便决策者做出决策。这样我们便需要一个就多目标问题变化为单目标问题的方法12。众所周知，线性加权法是针对目标函数的重要性不同，给定一组与各目标对应的非负数，然后将与做线性组合。首先为每个子目标函数赋予一定的权重，然后对各子目标函数进行线性加权求和。因此，上述多目标优化问题可以转换为如下单目标最优问题： (3.3.5)本文只考虑经济效益和环境污染两个指标，因此本文优化的目标函数可以描述如下：1,k2,lmnkijifxa其中，f1 和 f2 分别为经济效益和环境污染两个指标；z1+z2=13.3 改进的差分进化算法13本节给出用于多项目选址问题的改进差分进化算法，其思想如下：首先通过等效概率矩阵把离散变量选址问题转换为连续变量优化问题；利用 DE 解决连续问题，从而得到不确定多项目选址问题的最优解。在 DE 的多种进化方案中，以随机变量为基向量的变异方案其变异基向量也为随机选择个体，无需任何适应值信息，有利于保持种群的多样性，寻优能力强，但收敛速度非常慢。以当前最优个体为基向量的变异方案，随着进化的进行，算法出现早熟收敛现象，寻优能力较弱。针对以上两个缺点，以下提出了一种新的变异策略和自适应重构交叉概率因子策略，使其既具有较好的收敛速度又有较高的收敛精度。3.3.1 离散变量的连续化解矩阵 在离散空间中很好地描述了项目及位置的配对关系，但差分进化X算法优化算法不能直接解决该问题.因此本文提出等效概率矩阵的概念，完成多目标多项目选址问题的编码。定义（等效概率矩阵）如果矩阵满足（1）（2）表示项目 建立在备选位置的概率，iU则称 P 为等效概率矩阵。3.3.2 改进的变异操作14DErand1 方案变异个体 由三个互不相同的随机个体组成，无需任何适tiv应值信息，有利于保持种群的多样性，因而全局搜索能力强，但收敛速度慢。DEbest1 版本变异个体 由 作引导，因而局部搜索能力强，精度高，收敛titbesx速度快。本文将这两种不同变异方式结合起来，取长补短，其变异操作方程为15： 1 23()()tttttirgbesrvxFx式中， ，设置为线性退货因子15。0,，式中， 为最大迭代次数，t 为当前迭代次数。maxax()TtmaxT在搜索过程中由 1 逐渐变化为 0，使得 的权重逐渐减小而 的权重1rxtbesx逐渐增加，从而保证算法既有较强的全局搜索又有较快的收敛速率和搜索精度。3.3.3 自适应交叉算子16由式可看出，CR 越otherwisgx jorCRandfvguij randij ,1,01,大，则 对 的贡献越多，有利于局部搜索和加速收敛速率；CR 越小，则1tivtiu对 的贡献越多，有利于保持种群多样性和群居搜索。由此可见，在保持tixti种群多样性与收敛速率之间是矛盾的。为了提高 DE 算法的优化性能，加入了一种指数递增交叉概率策略，交叉概率因子的更新状态如下：，式中，a=30,b=3; 参数 由式minaxmin()ep()bCRCRa 决定，；参数 。axa()Ttimax0.1;.9CR该交叉概率能良好地平衡全局搜索能力和局部搜索能力，使算法快速收敛到最优解。 3.3.4 算法步骤17以待寻优的 Kp(比例系数)、Ki (积分时间常数)、Kd(微分时间常数)三个参数为分量构成一个三维行向量，进行浮点数编码，组成差分进化算法的个体。以 Ziegler-Nichols 法获得的参数为基准，向两边扩展作为算法的搜索空间。以系统性能指标的倒数作为差分进化算法的适应度函数。算法的终止条件有很多，算法采用最大进化代数做为终止条件。当运行到指定的进化代数之后就停止运行，并将当前群体中的最佳个体作为 PID 参数的最优解。 基于差分进化算法的 PID 控制参数整定方法流程如下：对比例系数、积分时间常数和微分时间常数进行浮点数编码，设计种群个体。以 Ziegler-Nichols 法获得的参数为基准，设计搜索空间。根据系统性能指标要求，设计适应度函数。设置差分进化算法的种群规模 NP、变异因子 F、交叉因子 CR 以及最大迭代次数等参数。利用公式 3-1 对种群进行初始化，便产生了最初的 Kp,Ki,Kd。计算种群个体适应度，求出最优适应度和最优个体。判断是否达到最大迭代次数，若是，则退出，否则，执行下一步。对第 g 代个体 xi(g)进行变异操作，由公式 3-2 得到变异个体 vi(g+1)。对 xi(g)和 vi(g+1)进行交叉操作，根据公式 3-3 得到实验个体 ui(g+1)。 在 ui(g+1)和 xi(g)中进行选择。当 ui(g+1)的适应度比 xi(g)更好时被选作子代，否则，直接将 xi(g)作为子代（公式 3-4）。 迭代次数加 1，返回至（4）。初始化种群解码并计算适应值 ：利用 评价新粒子 (1)(,1)(iiiifPtftPt则 变异 ： 为 中互不相等任意整数且不等于 i , F 为变异因子 ， 若 不满足边界条件 ， 则此步骤重复交叉 ：选择 ：归一化 ： 避免更新后的 不满足等效 概率矩阵的约束条件解码并计算适应值,1(),12,LULijijxrandxNPjD 生成初始化粒子等效概率矩阵 P,1,2,3,()iGirGvPF123r2N ,1,()()ijijGfrandbjCRoriu,12,mi(n)ttsjsktijttirikP (1),()iiiiugffPgPotherwsg结束,1)lmnkijkiza,i差 分 进 化 流 程 图达到最大进化代数 T m a x否是3.4 煤矿选址问题的求解综合以上对差分进化算法及模型的建立，本节主要具体分析差分进化算法用于解决煤矿选址问题，首先阐述煤矿选址问题及其特殊性，而后给出本文方法的具体执行方法，最后，通过实验及仿真验证该算法解决此问题的可行性。3.4.1 煤矿选址问题总所周知，选址问题作为煤矿建设中要解决的首要问题，其直接影响到资源的有效开发利用和企业的安全经济运行，其意义深远：首先，煤矿的合理选址是煤矿系统中具有战略意义的投资决策问题。煤矿的建设投资规模大，占用土地而且建成后不易调整，对企业经营具有长期性的影响。另外煤矿选址的合理性也影响着资源的充分开发利用和环境的有效保护等方面，合理选址对整个经济系统也有着十分重要的现实意义；其次，合理选址有助于合理界定划分政府与企业对其承担的职能，促进系统规划与建设的有效运行机制的制定；最后，根据煤矿选址的客观规律，认真研究、分析所对应的相关政策文件，深刻探究国家相关调控方向，密切关注大形势下各种对企业发展的各种利弊影响因素，使优胜劣汰手段利用到各个关键点，另外更要加强与政府以及先进企业的充分沟通交流，将煤矿选址问题进一步优化解决，在建设过程中实现煤矿系统的全面优化、区域整体投资环境的进一步改善，使链接产业优良发展、合理布局，提高经济运行质量和效益，促进经济结构调整，进一步使经济体制和经济增长方式得到根本性改变，实现可持续发展战略。本课题针对煤矿企业在煤矿选址问题中，选址的主观随意比较大，准确性不高的问题，传统的选址往往不考虑保护周边的自然环境，设计了煤矿选址的模型。用来有效的指导煤矿选址工作，降低煤矿选址对环境的破坏，从而实现效益的最大化。采用本文所提出的差分进化方法，以经济收益、社会收益、环境污染等作为评价指标，来确定煤矿的选址，使其充分发挥其自身的作用，完成企业的最优生产，获得最大的收益，且对环境污染达到最低。3.4.2 问题描述及参数设置以上本文内容综合叙述了关于煤矿选址问题研究的背景，提出了针对解决该问题的方法，综合对以上内容的进一步延伸，以下内容针对所要解决的煤矿选址问题通过建立多项目多目标18模型来解决，具体方法如下：设某煤矿需修建 8 个建设项目，记为 ，共有 10 个备选位置，记为 ,其中本文主要考虑对此过程的主要影响因素有经济收益和环境保护指标两个方面，设其属性值矩阵分别为 ，初始化情况下的 、如下：.084.6312.45.3784170980A10.2.864980624.032768 2.730.862.41.7856425415930.7..1A .88276291310.012599 算法参数设置如下表19：差分过程参数设置表相关参数 参数值 相关参数 参数值F 0.6 DE 50CRNP？0.4T（迭代次数） 500 2Z 算法性能分析初步考虑在参数设置如上表的情况下，利用本课题方法连续处理上述问题20 次，其处理结果如下表，并给出了相应的变化曲线：优化方案表编号方 案经济 指标环境 指标综合 效益1 1921324854657387(,),(),(,),(,),uvvuvuvu139.1700 43.6100 63.83402 5 9 136.8600 43.9600 67.12003 162134854657987(,),(),(,),(,),vvvv148.0800 11.1400 65.91004 2 3uuuu146.0400 43.4700 66.49805 16213248596571087(,),(),(,),(,),uvvuvuvu145.6400 12.4300 65.71406 47 35139.4800 15.0000 64.78807 16231485965787(,),(,)(,),(,),vvvv145.6400 13.1600 66.15208 2 3uuuu146.8600 13.9600 67.12009 1621348596571087(,),(),(,),(,),vvvv145.6400 12.4300 65.714010 2 3147.5700 12.6900 66.642011 162134854657987(,),(),(,),(,),uvvuvuvu148.0800 11.1400 65.912012 2103146.1400 12.3000 65.836013 16213485965787(,),(),(,),(,),vvvv146.8600 13.9600 67.120014 496uuuu148.0800 11.1400 65.916015