設施選址問題與k-平均問題都是經(jīng)典NP-難問題,一直以來都是國內(nèi)外計算機科學領域和組合優(yōu)化領域許多專家和學者關注和研究的熱點問題.設施選址問題的實質(zhì)是對需求完成的分配任務進行合理安排以得到某種意義下的最優(yōu)解決方案,它不僅僅在工廠建址、網(wǎng)絡設施的安放等諸多方面有著大量的應用,還經(jīng)常作為基本聚類問題被別的問題的算法所調(diào)用,因此深受理論計算機科學、離散組合數(shù)學、運籌學、工程學、管理學的極大關注.在實際應用背景中,設施選址問題引申出諸多更廣義的問題,包括無容量設施選址、有容量設施選址、k-設施選址問題等,其中有容量選址問題又可以分為硬容量設施選址問題和軟容量選址問題.k-平均問題起源于信號處理,在數(shù)據(jù)挖掘、機器學習、人工智能等領域有非常廣泛的應用.與此同時,它作為經(jīng)典聚類問題,也吸引著來自理論計算機科學、統(tǒng)計和優(yōu)化等領域的研究.上世紀60年代提出的經(jīng)典的k-平均聚類作為最受重視而又最簡單易懂的一種聚類方法流行至今,并且一直被機器視覺、地質(zhì)統(tǒng)計學、天文學和農(nóng)業(yè)等領域的算法所調(diào)用.其理論研究在過去的幾十年中取得了較大的進展,但隨著科技的飛越和數(shù)據(jù)的爆炸性增長,實際應用中遇到的k-平均問題相比以前增... 

【文章來源】：北京工業(yè)大學北京市 211工程院校

【文章頁數(shù)】：84 頁

【學位級別】：博士

【部分圖文】：

圖１－１設施選址問題??Ｆｉｇ?１－１?Ｆａｃｉｌｉｔｙ?ｌｏｃａｔｉｏｎ?ｐｒｏｂｌｅｍ??

Ｆｉｇ?１－２?Ａ＞ｍｅａｎｓ?ｐｒｏｂｌｅｍ??ｕ要是能將問題刻畫成在一些候選解中以某種規(guī)則優(yōu)化的子問題，那么局部搜索技??巧就能派上用場．圖１－３描述了廚部搜索的基本思想．??：：??菌１－３貝部搜索技巧的由要思想??Ｆｉｇ?１－３?Ｍａｉｎ?ｉｄｅａ?ｏｆ?ｌｏｃａｌ?ｓｅａｒｃｈ?ｍｅｔｈｏｄ??如圖所示，我們從問題的任一可行解出發(fā)（菌中記為負），解厘圖的圈表示該??解的鄰域（不同算法對鄰域有不同定義）的范覆，；我們用＃（況）表示解負的鄰域．??在Ａ／？（氏）中，我們通過優(yōu)化某種規(guī)則得到了新的可行解為，子是我們又可以計尊??＃尚），如此迭代下蠢直到我們找到了可行解Ｓ，在Ａ／Ｘ３中即為優(yōu)化該準則得到??的點，那么我們稱我們得到了局部最優(yōu)解兄進而再通過我們定義鄰域的方式分析??這個局部最優(yōu)解的賡焉這就是ＩＩ部搜索的主要思想．??我們總結了局部搜索技巧在設計近似算祛中的優(yōu)勢：??？算法描述簡單：通常局部搜索算法用”Ｄ。Ｗｈｉｌｅ?Ｅｘｉｓｔ”就可描述，也就是“存在??就迭代下去；??？揭示問題結構：因扁部搜索本身是組合算法（僅包含簡單的加、減、乘、除、比??較運算），我們從預備知識也可看到，算法的每一步得到的都是可行解，我們目??睹”著解的費用的下降；??？收斂速度較快：局部搜索最開始以啟發(fā)式算法被人們熟知

圖２－２流分解７Ｋ意圖??Ｆｉｇ?２－２?Ｓｃｈｅｍａｔｉｃ?ｆｉｇｕｒｅ?ｆｏｒ?ｆｌｏｗ?ｄｅｃｏｍｐｏｓｉｔｉｏｎ??


本文編號：3211479