基于遺傳算法的設(shè)施選址問題算法研究.pdf

1、本文討論的主要內(nèi)容是設(shè)施選址問題。論文首先簡單介紹了設(shè)施選址問題在現(xiàn)代社會生活中的作用和發(fā)展進(jìn)程，然后介紹了一些經(jīng)典的設(shè)施選址問題和求解算法。常見的設(shè)施選址問題包括 p-中位問題、p-中心問題、經(jīng)典的無容量限制設(shè)施選址問題等。多數(shù)設(shè)施選址問題屬于NP-Hard問題，目前已有很多方法來求解這類問題，主要分為精確算法與啟發(fā)式算法。常見的精確算法有分支定界法、拉格朗日松弛算法等；啟發(fā)式算法主要有遺傳算法、粒子群優(yōu)化算法、禁忌搜索算法等。隨后給

2、出了本文的研究意義和主要工作。
　　論文主要研究了兩類設(shè)施選址問題，一類是經(jīng)典的無容量限制設(shè)施選址問題（Uncapacitated Facility Location Problem，簡稱UFLP）；另一類為無容量限制的可靠性設(shè)施選址問題（Reliability for the Uncapacitated Facility Location Problem，簡稱RUFLP）。針對上述兩類設(shè)施選址問題，本文分別給出了基于遺傳算法的求

3、解方法，因此論文第二部分對傳統(tǒng)的遺傳算法進(jìn)行了介紹。
　　針對UFLP，提出了一種改進(jìn)的遺傳算法，該算法較之傳統(tǒng)的遺傳算法有如下改進(jìn)：（1）提出了新的自適應(yīng)交叉概率，并與均勻交叉相結(jié)合，使交叉算子不僅更有針對性，而且具有自適應(yīng)性，從而提高進(jìn)化效率；（2）在已有的自適應(yīng)變異概率設(shè)計(jì)方法下進(jìn)行改進(jìn)，設(shè)計(jì)出一種更合理的自適應(yīng)變異算子。最后通過數(shù)值試驗(yàn)說明本文提出的遺傳算法在求解大規(guī)模UFLP時(shí)具有很好的效果。
　　隨著設(shè)施選址問題