带容量的设施选址和k-平均问题的局部搜索算法

发布时间：2021-06-05 04:56

　　设施选址问题与k-平均问题都是经典NP-难问题,一直以来都是国内外计算机科学领域和组合优化领域许多专家和学者关注和研究的热点问题.设施选址问题的实质是对需求完成的分配任务进行合理安排以得到某种意义下的最优解决方案,它不仅仅在工厂建址、网络设施的安放等诸多方面有着大量的应用,还经常作为基本聚类问题被别的问题的算法所调用,因此深受理论计算机科学、离散组合数学、运筹学、工程学、管理学的极大关注.在实际应用背景中,设施选址问题引申出诸多更广义的问题,包括无容量设施选址、有容量设施选址、k-设施选址问题等,其中有容量选址问题又可以分为硬容量设施选址问题和软容量选址问题.k-平均问题起源于信号处理,在数据挖掘、机器学习、人工智能等领域有非常广泛的应用.与此同时,它作为经典聚类问题,也吸引着来自理论计算机科学、统计和优化等领域的研究.上世纪60年代提出的经典的k-平均聚类作为最受重视而又最简单易懂的一种聚类方法流行至今,并且一直被机器视觉、地质统计学、天文学和农业等领域的算法所调用.其理论研究在过去的几十年中取得了较大的进展,但随着科技的飞越和数据的爆炸性增长,实际应用中遇到的k-平均问题相比以前增... 

【文章来源】：北京工业大学北京市 211工程院校

【文章页数】：84 页

【学位级别】：博士

【部分图文】：

图１－１设施选址问题??Ｆｉｇ?１－１?Ｆａｃｉｌｉｔｙ?ｌｏｃａｔｉｏｎ?ｐｒｏｂｌｅｍ??

Ｆｉｇ?１－２?Ａ＞ｍｅａｎｓ?ｐｒｏｂｌｅｍ??ｕ要是能将问题刻画成在一些候选解中以某种规则优化的子问题，那么局部搜索技??巧就能派上用场．图１－３描述了厨部搜索的基本思想．??：：??菌１－３貝部搜索技巧的由要思想??Ｆｉｇ?１－３?Ｍａｉｎ?ｉｄｅａ?ｏｆ?ｌｏｃａｌ?ｓｅａｒｃｈ?ｍｅｔｈｏｄ??如图所示，我们从问题的任一可行解出发（菌中记为负），解厘圖的圈表示该??解的邻域（不同算法对邻域有不同定义）的范覆，；我们用＃（况）表示解负的邻域．??在Ａ／？（氏）中，我们通过优化某种规则得到了新的可行解为，子是我们又可以计尊??＃尚），如此迭代下蠢直到我们找到了可行解Ｓ，在Ａ／Ｘ３中即为优化该准则得到??的点，那么我们称我们得到了局部最优解兄进而再通过我们定义邻域的方式分析??这个局部最优解的赓焉这就是ＩＩ部搜索的主要思想．??我们总结了局部搜索技巧在设计近似算祛中的优势：??？算法描述简单：通常局部搜索算法用”Ｄ。Ｗｈｉｌｅ?Ｅｘｉｓｔ”就可描述，也就是“存在??就迭代下去；??？揭示问题结构：因扁部搜索本身是组合算法（仅包含简单的加、减、乘、除、比??较运算），我们从预备知识也可看到，算法的每一步得到的都是可行解，我们目??睹”着解的费用的下降；??？收敛速度较快：局部搜索最开始以启发式算法被人们熟知

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


本文编号：3211479