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

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

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

【學(xué)位級(jí)別】：博士

【部分圖文】：

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

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

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


本文編號(hào)：3211479