《基于遗传算法设施选址问题算法的研究》由会员分享，可在线阅读，更多相关《基于遗传算法设施选址问题算法的研究（60页珍藏版）》请在金锄头文库上搜索。
1、论文题目：基于遗传算法的设施选址问题算法研究作者姓名：李岳佳入学时间： 2009年 9月专业名称：运筹学与控制论研究方向：运筹与管理科学指导教师：赵茂先职称：教授论文提交日期：2012年 4月论文答辩日期：2012年 6月授予学位日期：年月STUDY ON THE ALGORITHMS FOR THE FACILITYLOCATION PROBLEM BASED ON GENETICALGORITHMA Dissertation submitted in fulfillment of the requirements of the degree ofMASTER OF SCIENCEfromS
2、handong University of Science and TechnologybyLiYuejiaSupervisor：Professor Zhao MaoxianCollege of Information Science and EngineeringMay 2012声明本人呈交给山东科技大学的这篇硕士学位论文，除了所列参考文献和世所公认的文献外，全部是本人在导师指导下的研究成果。该论文资料尚没有呈交于其它任何学术机关作鉴定。硕士生签名：日期：AFFIRMATIONI declare that this dissertation， submitted in fulfillment
3、 of the requirementsfor the award of Master of Science in Shandong University of Science andTechnology， is wholly my own work unless referenced of acknowledge. Thedocument has not been submitted for qualification at any other academicinstitute.Signature：Date：山东科技大学硕士学位论文摘要摘要本文讨论的主要内容是设施选址问题。论文首先简单介绍
4、了设施选址问题在现代社会生活中的作用和发展进程，然后介绍了一些经典的设施选址问题和求解算法。常见的设施选址问题包括 p-中位问题、p-中心问题、经典的无容量限制设施选址问题等。多数设施选址问题属于 NP-Hard问题，目前已有很多方法来求解这类问题，主要分为精确算法与启发式算法。常见的精确算法有分支定界法、拉格朗日松弛算法等；启发式算法主要有遗传算法、粒子群优化算法、禁忌搜索算法等。随后给出了本文的研究意义和主要工作。论文主要研究了两类设施选址问题，一类是经典的无容量限制设施选址问题（Uncapacitated Facility Location Problem，简称 UFLP）；另一类为无容
5、量限制的可靠性设施选址问题（Reliability for the Uncapacitated Facility Location Problem，简称 RUFLP）。针对上述两类设施选址问题，本文分别给出了基于遗传算法的求解方法，因此论文第二部分对传统的遗传算法进行了介绍。针对 UFLP，提出了一种改进的遗传算法，该算法较之传统的遗传算法有如下改进：（1）提出了新的自适应交叉概率，并与均匀交叉相结合，使交叉算子不仅更有针对性，而且具有自适应性，从而提高进化效率；（2）在已有的自适应变异概率设计方法下进行改进，设计出一种更合理的自适应变异算子。最后通过数值试验说明本文提出的遗传算法在求解大规模
6、 UFLP时具有很好的效果。随着设施选址问题的不断发展，新的选址模型也不断涌现，尤其是可靠性设施选址问题的提出具有非常重要的意义。国外对可靠性设施选址问题的研究模型大多基于 p-中位问题而提出的，其假设条件比较严格，模型比较复杂。本文提出的无容量限制的可靠性设施选址模型放宽了假设条件，降低了问题的复杂度。针对 RUFLP，提出了基于遗传算法的分阶段近似算法，并证明了该算法对求解 RUFLP是可行的。最后，对论文进行了总结，并对设施选址问题以后的研究进行了展望。关键词：设施选址问题；无容量限制设施选址问题；启发式算法；遗传算法；自适应；可靠性；近似算法山东科技大学硕士学位论文AbstractAb
7、stractThe main content discussed in this paper is the facility location problem. In this thesis, wefirst briefly introduce the role of the facility location problem in the modern society and itsdevelopment process, and then introduce some classical facility location problems and solvingalgorithms. C
8、ommon facility location problems include p-median problem, p-center problem,the classic uncapacitated facility location problem, and so on. The majority of the facilitylocation problems are NP-Hard problems. There are many methods to solve this kind ofproblem, which can be mainly divided into exact
9、algorithms and heuristic algorithms.Common exact algorithms include branch and bound method, Lagrange relaxation algorithm,etc. Heuristic algorithms mainly include genetic algorithm, particle swarm optimizationalgorithm, tabu search algorithm, and so on. Subsequent we presented the significance stud
10、y inthis thesis and the main work.This thesis mainly studied two kinds of facility location problems. One kind of them isclassic Uncapacitated Facility Location Problem (UFLP). Another kind is Reliability for theUncapacitated Facility Location Problem (RUFLP). In view of the above two types of facil
11、itylocation problem, this paper presented solving method based on genetic algorithm respectively,so the second part of the thesis introduced traditional genetic algorithm.For the UFLP, we proposed an improved genetic algorithm. Compared to the traditionalgenetic algorithm the algorithm has the follo
12、wing differences: The first, proposed a newadaptive crossover probability, and combined it with uniform crossover, thus make thecrossover operator is not only more targeted but also adaptive, so as to improved the efficiencyof evolution. The second, improved the existing adaptive mutation probabilit
13、y, and developeda more reasonable adaptive mutation operator. Finally, through the numerical test proof thatthe genetic algorithm is put forward in this paper have a very good effect in solving large-scaleUFLP.Along with the development of the facility location problem, the new location modelsalso emerging, especially the come up with the reliability of the facility location problem has avery important significance. The study of reliability facility location model in foreign mostbased on the p-median problem, but the assumptions
