2鄰域搜索演算法

⑴ 智能計算/計算智能、仿生演算法、啟發式演算法的區別與關系

我一個個講好了，
1）啟發式演算法：一個基於直觀或經驗構造的演算法，在可接受的花費（指計算時間和空間）下給出待解決組合優化問題每一個實例的一個可行解，該可行解與最優解的偏離程度不一定事先可以預計。意思就是說，啟發式演算法是根據經驗或者某些規則來解決問題，它求得的問題的解不一定是最優解，很有可能是近似解。這個解與最優解近似到什麼程度，不能確定。相對於啟發式演算法，最優化演算法或者精確演算法（比如說分支定界法、動態規劃法等則能求得最優解）。元啟發式演算法是啟發式演算法中比較通用的一種高級一點的演算法，主要有遺傳演算法、禁忌搜索演算法、模擬退火演算法、蟻群演算法、粒子群演算法、變鄰域搜索演算法、人工神經網路、人工免疫演算法、差分進化演算法等。這些演算法可以在合理的計算資源條件下給出較高質量的解。
2）仿生演算法：是一類模擬自然生物進化或者群體社會行為的隨機搜索方法的統稱。由於這些演算法求解時不依賴於梯度信息，故其應用范圍較廣，特別適用於傳統方法難以解決的大規模復雜優化問題。主要有：遺傳演算法、人工神經網路、蟻群演算法、蛙跳演算法、粒子群優化演算法等。這些演算法均是模仿生物進化、神經網路系統、螞蟻尋路、鳥群覓食等生物行為。故叫仿生演算法。
3）智能計算：也成為計算智能，包括遺傳演算法、模擬退火演算法、禁忌搜索演算法、進化演算法、蟻群演算法、人工魚群演算法，粒子群演算法、混合智能演算法、免疫演算法、神經網路、機器學習、生物計算、DNA計算、量子計算、模糊邏輯、模式識別、知識發現、數據挖掘等。智能計算是以數據為基礎，通過訓練建立聯系，然後進行問題求解。
所以說，你接觸的很多演算法，既是仿生演算法，又是啟發式演算法，又是智能演算法，這都對。分類方法不同而已。

這次樓主不要再老花了哈！

⑵ 什麼是局部搜索演算法

局部搜索演算法是從爬山法改進而來的。
簡單來說，局部搜索演算法是一種簡單的貪心搜索演算法，該演算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。
在計算機科學中，局部搜索是解決最優化問題的一種元啟發式演算法。局部搜索從一個初始解出發，然後搜索解的鄰域，如有更優的解則移動至該解並繼續執行搜索，否則返回當前解。
1、局部搜索演算法的基本思想：
在搜索過程中，始終選擇當前點的鄰居中與離目標最近者的方向搜索。
2、局部搜索的優點：
簡單、靈活及易於實現，缺點是容易陷入局部最優且解的質量與初始解和鄰域的結構密切相關。常見的改進方法有模擬退火、禁忌搜索等。
3、局部搜索廣泛應用：
計算機科學（主要是人工智慧）、數學、運籌學、工程學、生物信息學中各種很難找到全局最優解的計算問題。

⑶ 鄰域法人工神經網路礦產儲量計算

李裕偉

（中國地質礦產信息研究院，北京100812）

李林松

（北京計算機一廠，北京100083）

摘要人工神經網路（ANN）技術是一種可用於模式識別的新技術。本文介紹用ANN技術進行礦產儲量計算的方法，這種方法基於鄰域而不是整個研究區的信息，因而能保證迭代過程的成功。這一ANN方法在一個品位變化很大且樣品分布極不規則的金礦床應用後，取得了令人滿意的結果。本文還對ANN方法與克里格法的應用效果進行了對比。

關鍵詞儲量估計人工神經網路地質統計學鄰域

1引言

到目前為止，主要有兩種用於儲量計算的空間插值方法：距離倒數法和克立格法。前者簡便易行，但忽略地質因素的變化；後者不僅考慮到樣品的空間構形，而且還考慮到礦床的地質條件變化。在應用克立格法時地質學家往往遇到一些難題，如建立不起合適的變差函數、存在非平穩性等。吳希平和周迎新（1993）曾使用人工神經網路技術估計礦產儲量。這顯然是一個很好的開端，因為ANN技術同時具備距離倒數法和克立格法的優點：既簡便易行，又考慮了地質條件變化。此外，在用ANN方法估計儲量時，無需考慮諸如變差函數、平穩性之類的問題。吳希平和周迎新使用ANN方法的范圍是整個研究區，全部樣品只有48件。如果樣品數增加，如超過100件，或者數據構形比較復雜，則將很難達到一個ANN的儲量估計解。為了解決上述問題，筆者設計了一個新的估計儲量的ANN方案，這種方案基於鄰域信息而不是全區信息。

2領域定義

在使用ANN方法估計礦床儲量時，之所以使用鄰域信息而不是全區信息有兩點考慮。其一是對塊段的估值只受其鄰域樣品的影響，因而不需要利用全區樣品；其二是只有在一個小的樣品集的條件下，ANN迭代作業才有可能取得成功。當使用的樣品太多時，ANN的迭代過程可能難以收斂；而當樣品數較少時，收斂的可能性加大。據筆者的經驗，當樣品數少於50時，ANN作業可以順利地進行。簡言之，我們之所以需要一個鄰域，是為了從全部樣品集中抽取一個有效的數據子集，以便用ANN方法成功地進行塊段儲量的估計。

在用ANN方法進行儲量估計時，鄰域的定義與克立格法相似。首先，設計一個由規則塊段組成的網路系統。這樣問題就化為據某塊段鄰域內若干樣品的觀測值來估計該塊段的值。為簡化起見，可將鄰域定義為一個矩形（圖1）。該矩形鄰域中的樣品被用於進行被估塊段的儲量估計。為了更精確地進行塊段估值，可在被估塊段中設置若干個估值點。ANN程序對該塊段的每個估值點返回一個值。這些估值點的平均值即為該塊段的估值（圖2）。

圖1鄰域定義

圖2樣品及估值

對鄰域的大小可以調整，直到其包含50件樣品為止。影響塊段估值精度的因素有三個。其一是鄰域中樣品的數據構形。如果樣品分布比較均勻，則可能得到一個令人滿意的ANN估值。其二是樣品的密度。當鄰域內有較多樣品時，ANN程序將返回一個具有較小誤差的估值。其三是輸入變數的空間變化。一個空間高度波動起伏的變數將導致較大的估值誤差。

3ANN模型

人工神經網路方法是近年來迅速發展的人工智慧技術之一，它已被成功地用於模式識別。這一技術的吸引力在於：應用ANN的地質學家需要做的事僅僅是對輸入層和輸出層進行分析。換句話說，人們無需去研究在輸入層和輸出層之間所發生的事情，因為那些隱蔽層可以被視為一個「黑箱」。這樣一來，需要人們做的僅僅是理解輸入與輸出的事件，這對地質學家來說恰恰是比較熟悉、比較容易的事；而在輸入與輸出之間存在的那些極復雜的非線性關系及巨量的計算任務，則交給計算機去處理，這些工作恰恰是人所難以承擔的。從這一觀點出發，使用ANN技術進行儲量估計的地質學家就可以避免遇到許多使用克立格法時所難以解決的問題。

塊段估值是一個空間模式識別過程。考慮到上述的ANN技術的優點和前人的啟發性工作，本文嘗試使用這一新的模式識別技術進行二維儲量估計。

所設計的ANN結構包含一個輸入層、兩個隱蔽層和一個輸出層。輸入層包含三個變數：x坐標、y坐標和鄰域的品位平均值。所謂鄰域的品位平均值指的是用最近的四個樣品據距離倒數法計算的平均值。在兩個隱蔽層中，每層均含有5個神經元。輸出層只包含一個變數，即所估計點的礦石品位。圖3表示了這一ANN結構。

圖3ANN結構

令x_i為下一層第i個神經元的輸入值，x_j為上一層第j個神經元的初始輸出值，w_ij為下一層第i個神經元和上一層第j個神經元的聯結權，則可建立起m個輸入神經元和第j個輸出神經元之間的關系。

數學地質和地質信息

然後使用以下特性函數

數學地質和地質信息

將初始輸出值x_j轉換為適配輸出值x_j。

所使用的學習演算法為簡單的反向傳播法（BP），其權系數調整方程為

數學地質和地質信息

此方程被用來修改權系數，使其從當前值被修改成下一步的值。式中k為當前所處的迭代次數，η為學習率，δ_j為第j個輸出神經元的當前值同其目標值之差，x_j為第j個神經元在第k次迭代中獲得的適配輸出值。

雖然還可採用一些改進的BP演算法或其他更復雜的學習演算法，但由於簡單的BP演算法已能很好地解決本文的問題，因此就不打算再討論和使用其他的學習演算法。

4實例研究

上述的ANN方法被用於研究河南的J礦床。這是一個石英脈型金礦床，以坑探為主，輔之少量鑽孔控制。共取得250件樣品（圖4）。樣品分布極不均勻，金品位變化很大。因此，這是一個難以用一般插值方法進行空間描述的礦床。為便於對比，用克立格法和人工神經網路方法對礦床的品位按同一塊段系統進行了估計。塊段系統由25×9個克立格塊段組成，每個克立格塊段的大小為50m×50m。被估塊段加上由50個樣品構成鄰近塊段組成鄰域。每個被估塊段有3×3個估值點。根據這些鄰域參數與樣品數據，我們可以用前面定義的ANN模型來逐個塊段地估計金品位。達到指定精度的迭代次數變化范圍很大，取決於鄰域中樣品的數目、構形和變數的空間變化。所設置的臨界迭代誤差為0.001。當實際的迭代誤差小於該臨界誤差時，迭代過程結束。大多數迭代過程在迭代10000～30000次時終止，但最大迭代次數可達100000次。ANN程序對每個塊段的3×3個離散估值點各返回一個金品位估值，再由它們生成塊段的平均值。離散點估值及塊段平均值都是ANN品位估值的重要結果。

圖4樣品點點陣圖

圖2顯示了該金礦床的一個塊段。為了便於清晰地了解樣品與估值點的關系，只顯示了其鄰域的一部分。這個部分鄰域包含了11個樣品，但它們對該塊段的估值無疑是最重要的。圖中9個小矩形代表估值點。可以看出，ANN程序對每個估值點都返回了一個合理的值。每個估值點的值均同其最近的樣品值吻合得很好。由圖2還可以看出，用ANN方法所求得的點上的估值僅由最鄰近的幾個樣品所確定，遠離該估值點的樣品對估值的影響可忽略不計。這就是為什麼在使用ANN方法對一個點或塊段進行估值時只需鄰域而無需整個研究區的理由。對圖2所示塊段鄰域的ANN學習信息列於表1。在通過學習得到權值後，將每個估值點的x坐標、y坐標及鄰域平均值代入公式（1）計算初始輸出值；然後再將初始輸出值代入公式（2）求得適配輸出值。對該塊段的點估值列於表2。

表1圖2所示塊段的學習信息

圖5和圖6分別顯示了對整個礦床的點估值與塊段估值。可以看出，圖6的點估值更好地刻畫了該礦床的金品位分布細節。這一點同克立格法的估值結果有很大的區別。一般說來，克立格法的點估值同塊段估值區別不大，這是因為克立格法無論是對點估值還是塊段估值都會產生很強的圓滑效應，但ANN塊段估值卻不會產生這么強的圓滑效應。將ANN塊段估值（圖5）同克立格塊段估值（圖7）進行對比，雖然全礦床的平均品位非常接近，據ANN法為2.59375，據克立格法為2.49658，但可明顯看到克立格法的估值圖像被大大地圓滑了。我們知道，地質統計學提供了兩種研究空間數據的模型：其一是克立格法模型，它被用來估計一個區域化變數的局域平均值，但不忠實於其空間的變化細節；其二是條件模擬模型，它被用來仔細地刻畫一個區域化變數的空間變化，但不能保證得到一個最優的、無偏的局域平均值。ANN方法看來綜合了這兩種模型的優點，對點估計而言尤其如此。一個ANN制圖過程所產生的點估值的空間變化同實際樣品的空間變化十分相近。當然，樣品點愈密集，點估值的特徵與實際特徵就愈接近。

表2圖2所示塊段的點估值

圖5ANN法金品位塊段估值品位單位：g/t

圖6ANN法金品位點估值品位單位：g/t

圖7克立格法金品位塊段估值品位單位：g/t

為了說明ANN估計的優點，可將圖6的ANN點估值同圖4的實際樣品點點陣圖進行對比。在仔細地研究圖上的ANN點估值及其鄰域的樣品值之間的關系後可以看出，它們之間是非常吻合的。這就表明，ANN可以作為估計礦產儲量的一個非常有效的工具。

5結論

人工神經網路技術是一種新的、有效地估計礦產儲量的方法。在整個研究區內定義一個估計局域品位的ANN作業可能遭到失敗；但如果定義在一個較小的鄰域內則可以取得成功。同地質統計學相比，ANN產生的品點陣圖由於圓滑效應很小，更接近於品位空間分布的實際情況。此外，地質學家不再需要為諸如非平穩性、非正態性、非線性、各向異性、不良變差函數等問題而煩惱。應用ANN技術估計礦產儲量的主要問題是無法通過ANN方法本身提供估值誤差。

參考文獻

[1]J.Hertz,A.Krogh,R.G.Palmer.Introction to the Theory of Neural Computation.Addison-Wesley Publ.co.,Redwood City,California,1991.

[2]Xiping Wu and Yingxin Zhou.Reserve Estimation Using Neural Network Techniques.Computers ＆ Geosciences,1993,19（4）.

⑷ LKH（Lin-Kernighan heuristic ）一種求TSP的鄰域搜索策略

PART I 引入

題主應該指的是1973年的針對TSP的LKH演算法。LKH演算法類似於k-opt方法，常見的2-opt作為一種local search的思想題主應該是知道的，（2-opt的基本變換2-interchange如下圖）。

那麼k-opt的過程，也可以element by element，也就可以通過不計順序的δ-path之間的uv-switch來實現，每個合適的k-opt裡面的exchange都是總和為正的增益值，那麼其每一個合適的exchange的一部分都可以被uv-switch達到，所以可以令每次的G*都大於0，作為stoppingcriteria，從邏輯上來說是合理的，符合作者的element by element，在啟發式所謂的exploitation上也有好的表現力。END

P.S element by element這種思想在其他的演算法也有體現，比如遺傳演算法的改進上也有比如單位點交叉防止收斂解震動。

其他演算法效能上的提升考慮，請依次閱讀文獻[2][1]及其他相關的資料。

綜上，LKH是可以認為基於k-opt成功的改進，無論是運行的速度上，還是搜索的精度上。它在解決TSP問題上，速度和精度上仍舊有較好的表現。

水平有限，隨緣回答，若有錯誤，請指出評論，謝謝！

參考文獻：

理解演算法框架內容，文獻[1]是較好的參考資料，理解演算法細節、討論，可以參考文獻[2]，其指出了backtracking的要求（從數值實驗/作者思考的philosophy上指出：應該從最多幾層開始backtracking，每層y_1, y_2contenders的數量如何，如何進一步refinements，每一次δ-path 變換中y_i怎麼高效選取等問題）

[1] Cook W.J., Cunningham W.H., Pulleyblank W.R., Schrijver A.Combinatorial Optimization

[2] S. Lin, B. W. Kernighan,An effective heuristic algorithm for the traveling salesman problem

⑸ 極小，怎麼造句

極小，亦稱為最小，最小值。在數學分析中，在給定范圍內（相對極值）或函數的整個域（全局或絕對極值），函數的最大值和最小值被統稱為極值（極數）。按照該詞義造句有：

1, 他臉上的鬍子捲成許多極小的圓圈，像是沼地上的青苔。

2，幸福不表現為造成別人的哪怕是極小的一點痛苦，而表現為直接促成別人的快樂和幸福。照我看來，它在這一方面可以最為簡明地表達為：幸福在於勿惡、寬恕和熱愛他人。托爾斯泰

3，在顯微鏡下，極小的細菌也是歷歷可數的。

12，首先，給出整數規劃問題的離散局部極小解的定義，並設計找離散局部極小解的鄰域搜索演算法。

13，極小值時間剖面可直接作時深轉換。

14，吉事多專櫃有不少圓形或長圓形盆，配合極小的檯面，非常秀氣。

15, 即使極小的錯誤都可能會破壞整個項目。例如，過梁裁剪錯誤就不能正確的安放在石頭上面。

16，本文給出了極小化最大函數問題的一個可行方向演算法，它把問題歸結為求解線性規劃問題，並證明了該演算法的收斂性。

⑹ 鄰域的定義是唯一的嗎鄰域的定義與搜索效率及結 果有關聯嗎簡要說明你的結

不是。有關聯。
鄰域：鄰域是指集合上的一種基礎的拓撲結構。在集合論中，它是以點a為中心的任何開區間，記作：U(a)。在拓撲學和相關的數學領域中，鄰域是拓撲空間中的基本概念。有鄰域公理（鄰域公理是現代數學拓撲結構的基礎概念）、開鄰域和閉鄰域、去心鄰域等相關研究的著作。
廣義鄰域搜索演算法的統一結構：
1.對優化過程作兩方面分解處理：方面1、基於優化空間的分層（原問題分解為子問題求解，最後將各子問題的解逆向綜合為原問題的解）方面2、基於優化進程的分層（進程層次分為若干階段，各階段採用不同的搜索演算法或鄰域函數進行優化）目前混合演算法的結構類型主要可歸納為串列、鑲嵌、並行及混合結構。
串列結構。
鑲嵌結構。
並行結構（又分為同步式並行、非同步式並行、網路結構）。
同步式：各子演算法相對獨立但與主過程的通訊必須同步。
非同步式：子演算法與主過程的通訊不受其他子演算法的限制。
網路結構：各演算法分別在獨立的存儲器上執行獨立的搜索，演算法間的通信是通過網路相互傳遞的。

⑺ 搜索演算法和j2ee開發兩個方向選哪個

局部搜索演算法是從爬山法改進而來的。
簡單來說，局部搜索演算法是一種簡單的貪心搜索演算法，該演算法每次從當前解的臨近解空間中選擇一個最優解作為當前解，直到達到一個局部最優解。
在計算機科學中，局部搜索是解決最優化問題的一種元啟發式演算法。局部搜索從一個初始解出發，然後搜索解的鄰域，如有更優的解則移動至該解並繼續執行搜索，否則返回當前解。
1、局部搜索演算法的基本思想：
在搜索過程中，始終選擇當前點的鄰居中與離目標最近者的方向搜索。
2、局部搜索的優點：
簡單、靈活及易於實現，缺點是容易陷入局部最優且解的質量與初始解和鄰域的結構密切相關。常見的改進方法有模擬退火、禁忌搜索等。
3、局部搜索廣泛應用：
計算機科學（主要是人工智慧）、數學、運籌學、工程學、生物信息學中各種很難找到全局最優解的計算問題。

⑻ 基於R、SA和ICP的混合鄰域搜索演算法的TSP-D路徑優化問題代碼

摘要 還是要說一點，隨機產生兩點，塞進新排列頭部。其餘的按順序往後逐個塞進去。嗯，來看圖片~

⑼ 用極小造句怎麼造呀

極小，亦稱為最小，最小值。在數學分析中，在給定范圍內（相對極值）或函數的整個域（全局或絕對極值），函數的最大值和最小值被統稱為極值（極數）。按照該詞義造句有：

1，臨界點可能是局部極小，局部極大，或者鞍點。

2，首先，給出整數規劃問題的離散局部極小解的定義，並設計找離散局部極小解的鄰域搜索演算法。

3，極小值時間剖面可直接作時深轉換。

4，吉事多專櫃有不少圓形或長圓形盆，配合極小的檯面，非常秀氣。

5, 即使極小的錯誤都可能會破壞整個項目。例如，過梁裁剪錯誤就不能正確的安放在石頭上面。

6，本文給出了極小化最大函數問題的一個可行方向演算法，它把問題歸結為求解線性規劃問題，並證明了該演算法的收斂性。

9，由於遍歷性可作為避免搜索過程陷入局部極小的有效機制，因此混沌理論已成為一種新穎且有潛力的優化工具。

10，需要大量的煙，但極小量的明火。

11，我家有一隻小花貓，它圓圓的腦袋上有一雙明亮的眼睛，使它晚上能看清東西。它還有一雙靈活的耳朵，極小的聲音它都能辨別出來。它的身後長著一條長長的尾巴，走路時總是高高的翹著。

12，因為宇宙的結構是最完善的而且是最明智的上帝的創造，因此，如果在宇宙里沒有某種極大的或極小的法則，那就根本不會發生任何事情。

13，紫鵑道：＂我只當是寶二爺再不上我們這門了，誰知這會子又來了。＂寶玉笑道：＂你們把極小的事倒說大了。好好的為什麼不來？我便死了，魂也要一日來一百遭。妹妹可大好了？＂

14, 有一種殺人利器「激光槍，」它一次能射出500英里，這種槍體形極小，能隨時帶在身上。而且不象21世紀的槍，有防彈衣可以配用，現在這種槍只要射中哪裡，哪裡就會煙消雲散。

⑽ 採用准確優化技術和啟發式優化技術解決一個問題會存在什麼不同

採用准確優化技術和啟發式優化技術解決一個問題會存在的不同之處：

①確定性演算法和隨機性演算法是目前求解優化問題的方法。隨機性演算法一般是對社會行為和自然現象的模擬，具有對優化函數的解析性質要求低的特點，甚至對無顯示解析表達式的問題也可以求解，能較好解決優化中的雜訊、不可微、高維等問題。

②啟發式演算法作為隨機性演算法的一種，其良好的應用更加快了人們對各種優化方法的探索腳步。 近些年來不斷有學者將分形應用於優化中來，試圖運用分形思想來處理復雜的優化問題。

③其中，分形演算法通過對可行域的分形分割來尋優，是一種新穎的確定性演算法，但其局限性較大，只適用於低維簡單的問題，對於當今社會中高維復雜問題則幾乎無能為力，也使得該演算法的影響力微乎其微。

④啟發式技術是基於特徵值掃描技術上的升級,與傳統反病毒特徵值掃描技術相比,優點在於對未知病毒的防禦.是特徵值識別技術質的飛躍。

(10)2鄰域搜索演算法擴展閱讀

啟發式：簡化虛擬機和簡化行為判斷引擎的結合 Heuristic(啟發式技術=啟發式掃描+啟發式監控) 重點在於特徵值識別技術上的更新、解決單一特徵碼比對的缺陷.目的不在於檢測所有的未知病毒,只是對特徵值掃描技術的補充.主要針對：木馬、間諜、後門、下載者、已知病毒(PE病毒)的變種。

一、啟發式發展方向

現代啟發式演算法的研究,在理論方面還處於不斷發展中,新思想和新方法仍不斷出現。分析目前的現狀和發展方向,其發展方向有如下幾個方面:

①整理歸納分散的研究成果,建立統一的演算法體系結構。

②在現有的數學方法(模式定理、編碼策略、馬爾可夫鏈理論、維數分析理論、復制遺傳演算法理論、二次動力系統理論、傅立葉分析理論、分離函數理論、Walsh函數分析理論)的基礎上尋求新的數學工具。

③開發新的混合式演算法及開展現有演算法改進方面的研究。

④研究高效並行或分布式優化演算法。

二、啟發式演算法演算法機制特點

現代啟發式演算法在優化機制方面存在一定的差異,但在優化流程上卻具有較大的相似性,均是一種「鄰域搜索」結構。演算法都是從一個(一組)初始解出發,在演算法的關鍵參數的控制下通過鄰域函數產生若干鄰域解,按准則(確定性、概率性或混沌方式)更新當前狀態,而後按關鍵參數修改准則調整關鍵參數，一直優化到最優結果。