可變鄰域搜索技術(shù)的原理及應(yīng)用
作者：Pierre Hansen, Nenad Mladenovic
摘要：
一個可能的隨機系統(tǒng)的鄰域搜索算法的系統(tǒng)改變?yōu)榻M合問題和全局最優(yōu)解問題產(chǎn)生一個簡單而且有效的直接推斷法，它被稱為可變鄰域搜索法（VNS）。我們?yōu)榱诉@個目的介紹一種能夠被任何局部搜索算法作為子程序容易實施的基本方案，他的功用已經(jīng)在解決一些傳統(tǒng)組合全局最優(yōu)化問題得到闡明。此外，它的一些擴展也被建議用來解決大的問題場合：在逐步近似法中使用VNS產(chǎn)生了一個被稱為可變鄰域分解搜索法的二級VNS(VNDS)；修改基本方案去開發(fā)脫離限制的簡單領(lǐng)域產(chǎn)生了一種有效歪斜的VNS(SNVS)直接推理法。最后，我們將在VNS的幫助下展示如何穩(wěn)定繼承父代的算法，和討論用各種方法在圖線理論下去使用VNS，如說明，證明或者給出線索去證實如何證明猜想，在那種超啟發(fā)式?jīng)]有出現(xiàn)而之前卻已經(jīng)被運用。
關(guān)鍵詞：啟發(fā)式，超啟發(fā)式；可變鄰域搜索技術(shù)；VNS
1緒論
從很早開始啟發(fā)式已經(jīng)在解決大量的實際問題中得到廣泛使用。確實模仿綜合問題經(jīng)常產(chǎn)生困難的問題。這類問題在最差的事情中很難處理，但在一般事情或者研究中也許不是這樣。然而，現(xiàn)在一大套工具對正確地解決他們很有用（分支界限，剖面，分解，拉格朗日緩和，直代遺傳，…）可能不能夠去解決很大的問題，從而給了啟發(fā)式一個回復(fù)。此外，這些可以被以下的圖解，啟發(fā)式可能在準(zhǔn)確的算法中非常的有用。
啟發(fā)式另一個有用發(fā)面是局部搜索。它的處理是從初始化的局部次序解決，這樣改善每一次客觀因素的價值，直到找出最優(yōu)解。近些年，許多超啟發(fā)式被提了出來，這個方案擴大了各種方式而且可以避免陷入局部最優(yōu)解從而失去意義（見【56】）這些超啟發(fā)式，例如：適應(yīng)的 交叉開始【4】，各種深度搜索【47，55】，模擬退火【42】，禁忌搜索技術(shù)（TS）[23-27,30],領(lǐng)會【14】還有如遺傳搜索技術(shù)【38】與螞蟻群體【11】，在許多實際文章中已經(jīng)引起了很大的改良。
在這篇文章里，我們調(diào)查了相關(guān)未調(diào)查的接近接近啟發(fā)式的設(shè)計：在搜索中鄰域的變化。用系統(tǒng)的這個想法或者稍多點，也就是，只有鄰域搜索技術(shù)導(dǎo)致一種新的超啟發(fā)式，它具有廣泛的可適用性。我們稱這種逼近可變鄰域搜索技術(shù)（VNS）.與其它基于鄰域搜索技術(shù)方法相反，VNS不沿著一定軌道但向著遠的附近可行域搜索解答，還從這個解答跳向新的解答，只要而且只能是逼近最優(yōu)解，這種方法的可行域的有力特征將被保持并被用來獲得更接近最優(yōu)解的解答，舉例來說，就是很多變量都已經(jīng)得到最佳解。此外，鄰域搜索程序是被再三的用來獲得臨近較優(yōu)解的，從而獲得最優(yōu)解。這個程序也或許使用于個別領(lǐng)域，因此，要構(gòu)建不同的鄰域組織去完成系統(tǒng)的搜索，這就需要一個方法找出任意兩個解答之間的差距，也就是需要提供一定的如米制的（或類似米制）解答空間，然后引導(dǎo)附近鄰域接近這個空間。在下一個運用部分，我們解答這類特殊問題當(dāng)作每一個被認為的難題。