啟發式算法研究小結探究啟發式算法的緣由在選《管理優化決策》這門課的時候，我抱著很強的好奇心和巨大的求知欲，試圖嘗試在這門課上學到我感愛好的知識點以及擬定我此后極有可能的研究領域和大方向。很幸運的是，我找到了。為什么這樣說呢？就在我選擇博士專業內選修課和專業外選修課的同時我發現了管理優化決策這門課和計算機學院那邊開的選修課——《啟發式優化》（由呂志鵬專家講授），有諸多是相通的，發現管理界特別是在管理科學與工程方向和計算機技術應用領域所探究的問題出奇的一致，已經很難分清，哪個是管理方面的問題，哪個是計算機技術應用的范疇了。正如各位都懂得的是，由于選修課最后擬定前一種月是能夠去試聽的，然而我并沒有由于兩者看上去內容有些相似就慌忙退選。通過對這兩門課的內容進行比較，它給了我很大的觸動，也帶給我巨大的好奇，究竟是管理方面的研究越來越偏向運用計算機等其它學科的知識和工具，還是計算機應用研究的方面越來越偏向實際的管理優化問題了呢？亦或者兩個學科的邊界正在走向含糊？我想學科交叉和融合的這一說法對于我來說可能并不是很新鮮，但這確實是我親身經歷的一種美妙體驗和發現。它帶給我新穎的同時也無疑給了我值得我深思幾點的啟示：首先，眾所周知，管理學科作為一門交叉的新興學科，它的辦法和工具都是依靠和借助其它領域和學科而來的，它本身并沒有或者幾乎沒有一種完完整整的只屬于管理學科的辦法和工具，幾乎是其它學科的知識演變而來的，這就是我們所懂得的學科交叉和學科融合；然而管理領域和傳統計算機研究等領域的視角并不完全同樣，其中對于計算機領域的研究者們而言，他們不僅在乎啟發式算法與否能夠解決問題、效率與否大幅提高（而管理領域的專家們更在乎這點，能用第一，好用第二，或者說管理專家們更在乎第一點——問題能夠得到的解決，至于第二點就不是那么迫切。而對計算機領域的向專家們而言，能夠說兩者都非常重要、規定非常苛刻），更在乎它所體現出來的優越特性（就時間、空間復雜度以及算法求解過程中保持一定的集中性和分散性而言的）。然而當管理領域的學者們求解類似問題，普通來說都是和我們生活中的管理者經常碰到且直接和的決策有關的問題，由于由于管理者的決策質量好壞會往往直接造成公司和團體的效率和績效和高低，進而造成公司和組織的競爭力強弱，因此普通公司或者個人都是基于一定的價值訴求來解決管理問題，進而提高工作效率。由于管理者們非常理解生活中并不存在完完全全的理性人和完全信息，因此他們很難也極少去嘗試尋找最優解，找到滿意解就能夠了，這一點和啟發式算法的設計思想不謀而合（由于時間、硬件資源有限，特別是碰到組合爆炸問題時短時間難于窮舉和難與求解出最優解，并且短時間還必須給出解。盡管兩者有所差別，但都有某些共同之處，都是資源受限）。總而言之，對于同一種因此在求解管理方面較為復雜的問題時，我們短時間很難給出精確地解析解時，這時考慮運用啟發式算法也不失為一種飛常有效的辦法，并且生活我們經常在用，也不停地被證明了啟發式算法優良的特性（簡樸、快速且解的質量較高）。另一方面，隨著社會經濟的高速發展，我們面對的管理問題逐步變得越來越復雜，并且超出了人們的求解和計算的能力范疇，例如：當我們求解典型的TSP問題時，我們會發現盡管我們能夠用很簡樸的數學加以描述和刻畫，但是對其進行求解特別是計算得到問題的最優解時，能夠說難于上青天，然而這類問題在我們的生活中普遍存在，并且甚至嚴重地影響到了公司和個人的效益和效率以及人們生活的便利性。在這個過程中還必須給出一定的滿意解，此時，我們不求助與啟發式算法，那尚有什么措施呢？這也是啟發式算法得以存在并高速發展的根本因素，這也是眾多管理學者相繼運用啟發式算法的技術和工具去探究某些飛常復雜的管理問題根本因素，這也是我想在前人深厚的啟發式算法研究的基礎上繼續嘗試探究啟發式算法在管理問題的根本目的。最后，其實啟發式算法的設計思想往往來源于某些樸素的哲學思想和觀點，例如：啟發式算法的設計過程中非常重視集中性和疏散性，從而實現某種平衡的狀態，這與古代中國哲人先賢們的思想如出一轍，隨機和擬定同時進行，現有隨機又有擬定，隨機存在擬定之中，擬定亦存在隨機之中。在確保全局最優的方向上引入隨機的思想，避免過于最優，從而陷入局部最優無法自拔。這對于每個人的人生也是同樣的道理，我們在人生的道路上，充滿多種選擇，此時，我們是時時抓住眼前的最優，解未必是最優的；還是心里早已有一種最優的安排后（人生目的），允許犧牲/放棄短暫的眼前收益呢？這一點發人深思，這也是我最感愛好的地方。并且這種思想還能夠延伸到我們研究的管理研究領域，也變化了過去諸多觀點和見解，例如：我曾經堅信運用數學模型、數據以及有關的數學量化的辦法和工具能夠實現管理問題的最優解，通過本次理解，我逐步變化了我的觀點（盡管原來學習博弈論課程探究完全和完美信息對決策的影響時就已有這種變化的趨勢，但這種趨勢并不明顯，由于它并不直觀和具體），諸多問題都有一定的復雜度，有時甚至超出了人們求解能力的范疇，因此把握問題求解可能性和解的質量兩者的平衡就尤為重要了。總之，到處需要平衡！什么是啟發式算法啟發式（Heuristics）是指“探索性的”，但是普通被翻譯為“啟發式”，然而我覺得發把Heuristics翻譯為探索性的更加簡樸直觀而易于理解。初學者對啟發式這個專業詞語有點摸不著頭腦或者第始終覺打不起愛好，因而耽擱了自己的學習愛好的發掘和最佳的學習機會。啟發式算法（heuristicalgorithm)是相對于HYPERLINK最優化算法提出的。一種問題的最優算法求得該問題每個實例的HYPERLINK最優解。啟發式算法能夠這樣定義：一種基于直觀或經驗構造的算法，在可接受的耗費（指計算時間和空間）下給出待解決組合優化問題每一種實例的一種HYPERLINK可行解，該可行解與最優解的偏離程度普通不能被預計。現階段，啟發式算法以仿自然體算法為主，重要有HYPERLINK蟻群算法、HYPERLINK模擬退火法、HYPERLINK神經網絡等。HYPERLINK計算機科學的兩大基礎目的，就是發現可證明其執行效率良好且可得最佳解或次佳解的算法。而啟發式算法則試圖一次提供一或全部目的。例如它常能發現很不錯的解，但也沒措施證明它不會得到較壞的解；它普通可在合理時間解出答案，但也沒措施懂得它與否每次都能夠這樣的速度求解。精確和啟發式算法有時候人們會發現在某些特殊狀況下，啟發式算法會得到很壞的答案或效率HYPERLINK極差，然而造成那些特殊狀況的數據組合，可能永遠不會在現實世界出現。因此現實世界中啟發式算法慣用來解決問題。啟發式算法解決許多實際問題時普通能夠在合理時間內得到不錯的答案。常見的啟發式算法以下表所示：傳統啟發式元啟發式超啟發式典型代表局部搜索爬山法貪心發蟻群算法遺傳算法粒子群算法禁忌算法模擬退火算法人工神經網絡進化方略進化規則變鄰域搜索基于貪心方略的超啟發式算法基于隨機選擇的超啟發式算法基于學習的超啟發式算法基于元啟發式算法的超啟發式算法可能本人介紹的不是很形象，因此摘抄了網上典型的一段描述幾個常見搜索算法的例子來作為總結：為了找出地球上最高的山，一群有志氣的兔子們開始想措施。（1）兔子朝著比現在高的地方跳去。他們找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山法，它不能確保局部最優值就是全局最優值。（2）兔子喝醉了。他隨機地跳了很長時間。這期間，它可能走向高處，也可能踏入平地。但是，他漸漸蘇醒了并朝他踏過的最高方向跳去。這就是模擬退火。（3）兔子們懂得一種兔的力量是渺小的。他們互相轉告著，哪里的山已經找過，并且找過的每一座山他們都留下一只兔子做記號。他們制訂了下一步去哪里尋找的方略。這就是禁忌搜索。（4）兔子們吃了失憶藥片，并被發射到太空，然后隨機落到了地球上的某些地方。他們不懂得自己的使命是什么。但是，如果你過幾年就殺死一部分海拔低的兔子，多產的兔子們自己就會找到珠穆朗瑪峰。這就是遺傳算法。啟發式算法的發展歷史談到啟發式算法，它已有很長的發展歷史，自從有了啟發式算法，人們能夠解決諸多之前很難求解的問題在很短的時間內，特別是隨著著計算機性能的飛速發展，啟發式的威力更加凸顯無疑。我們大致將啟發式算法的發展階段按照年代進行劃分以下：40年代：由于實際需要，人們已經提出了某些解決實際問題快速有效的啟發式算法。50年代：啟發式算法的研究逐步繁華起來。隨即，人們將啟發式算法的思想和人工智能領域中的多種有關問題的求解的收縮辦法相結合，提出了許多啟發式的搜索算法。其中貪婪算法和局部搜索等到人們的關注。60年代:隨著人們對數學模型和優化算法的研究越來越重視，發現以前提出的啟發式算法速度很快，但是解得質量不能確保。即使對優化算法的研究獲得了很大的進展，但是較大規模的問題仍然無能為力（計算量還是太大）。70年代：計算復雜性理論的提出。NP完全理論告訴我們，許多實際問題不可能在合理的時間范疇內找到全局最優解。發現貪婪算法和局部搜索算法速度快，但解不好的因素重要是他們只是在局部的區域內找解，得到的解不能確保全局最優性。由此必須引入新的搜索機制和方略，才干有效地解決這些困難問題，這就造成了超啟發式算法（meta-heuristicalgorithms）的產生。Holland模擬地球上生物進化規律提出了遺傳算法（GeneticAlgorithm），它的與眾不同的搜索機制引發了人們再次引發了人們研究啟發式算法的愛好，從而掀起了研究啟發式算法的熱潮。80年代后來：模擬退火算法（SimulatedAnnealingAlgorithm），人工神經網絡（ArtificialNeuralNetwork），禁忌搜索（TabuSearch）相繼出現。近來，演化算法（EvolutionaryAlgorithm）,蟻群算法（AntAlgorithms），擬人擬物算法，量子算法等油相繼興起，掀起了研究啟發式算法的高潮。由于這些算法簡樸和有效，并且含有某種智能，因而成為科學計算和人類之間的橋梁。啟發式算法特性和局限性盡管啟發式算法能力非常強大，幾乎能夠說每種啟發式算法都能獨當一面并獲得較好的效果。但是仍然存在某些客觀的局限以下：1.啟發式算法現在缺少統一而完整的理論體系。由于每種啟發式算法作用發揮好了都很強大，均能解決諸多問題，因而造成現階段啟發式算法山頭林立，其中研究的學者并沒有多少全部涉足研究的，因而造成啟發式算法缺少像其它成熟理論體系那樣的完整和體系化。2.由于NP理論，多種啟發式算法都不可避免的遭碰到局部最優的問題，如何判斷以及如何跳出局部最優。3.多種啟發式算法都有個自優點如何，如何將多種啟發式的有點互相借鑒和完美整合。4.啟發式算法中的參數對算法的效果起著至關重要的作用，如何有效設立參數。5.啟發算法缺少有效的迭代停止條件。6.啟發式算法收斂速度的研究等。幾個典型的啟發式算法首先，我們介紹一下爬山法，算法思想：爬山算法即是模擬爬山的過程，隨機選擇一種位置爬山，每次朝著更高的方向移動，直到達成山頂，即每次都在臨近的空間中選擇最優解作為現在解，直到局部最優解。這樣算法會陷入局部最優解，能否得到全局最優解取決于初始點的位置。初始點若選擇在全局最優解附近，則就可能得到全局最優解。爬山算法是一種局部擇優的辦法，采用啟發式辦法，是對深度優先搜索的一種改善，它運用反饋信息協助生成解的決策。屬于人工智能算法的一種。過程：從現在的節點開始，和周邊的鄰居節點的值進行比較。如果現在節點是最大的，那么返回現在節點，作為最大值(既山峰最高點)；反之就用最高的鄰居節點來，替代現在節點，從而實現向山峰的高處攀爬的目的。如此循環直達成到最高點。其優點：避免遍歷，通過啟發選擇部分節點，從而達成提高效率的目的。缺點：由于不是全方面搜索，因此成果可能不是最佳。爬山算法普通存在下列問題：1）局部最大：某個節點比周邊任何一種鄰居都高，但是它卻不是整個問題的最高點。2）高地：也稱為平頂，搜索一旦達成高地，就無法擬定搜索最佳方向，會產生隨機走動，使得搜索效率減少。3）山脊：搜索可能會在山脊的兩面來回震蕩，邁進步伐很小。另一方面，不得不提局部搜素算法，由于它吸取著爬山算法和貪心思想的精髓而背面有諸多算法都是在其的基礎上進行改善和擴展而來的，那么下面我們介紹一下局部搜素算法（LocalSearchAlgorithm簡稱LSA）。LSA是指為解決最優化問題的一種啟發式算法。對于某些計算起來非常復雜的最優化問題，例如多種NP完全問題，要找到最優解需要的時間隨問題規模呈指數增加，因此誕生了多種啟發式算法來退而求另一方面尋找次優解，是一種近似算法（Approximatealgorithms），以時間換精度的思想。局部搜索就是其中的一種辦法。鄰域動作是一種函數，通過這個函數，對現在解s，產生其對應的鄰居解集合。例如：對于一種bool型問題，其現在解為：s=1001，當將鄰域動作定義為翻轉其中一種bit時，得到的鄰居解的集合N(s)={0001,1101,1011,1000}，其中N(s)∈S。同理，當將鄰域動作定義為交換相鄰bit時，得到的鄰居解的集合N(s)={0101,1001,1010}。簡要談一下局部搜素的發展歷史，LSA是由爬山法改善而來的。更具體地說，局部搜索算法是一種簡樸的貪心搜索算法，該算法每次從現在解的臨近解空間中選擇一種最優解作為現在解，直達成到一種局部最優解。

在HYPERLINK計算機科學中，局部搜索是解決最優化問題的一種元啟發式算法。局部搜索從一種初始解出發，然后搜索解的鄰域，如有更優的解則移動至該解并繼續執行搜索，否則返回現在解。

1、局部搜索算法的基本思想：在搜索過程中，始終選擇現在點的鄰居中與離目的近來者的方向搜索。

2、局部搜索的優點：簡樸、靈活及易于實現，缺點是容易陷入局部最優且解的質量與初始解和鄰域的構造親密有關。常見的改善辦法有模擬退火、HYPERLINK禁忌搜索等。

3、局部搜索廣泛應用：HYPERLINK計算機科學（重要是人工智能）、數學、運籌學、工程學、HYPERLINK生物信息學中多種很難找到全局最優解的計算問題。為了克服局部搜素的局限性（容易陷入局部最優且解的質量與初始解的位置及其鄰域構造非常有關），因此眾多計算機科學家在局部搜索算法的基礎上構造了變鄰域搜索算法（VNSA）、禁忌算法、模擬退火算法。首先，禁忌算法（TS）通過增加一種靈活的存儲構造和對應的禁忌規則從而實現規避在局部搜索中造成陷入局部最優下重復搜索以至于陷入死循環，不能自拔。舉一種例子：當你有一天早上正打算出門，這時你發現你的鑰匙居然不見了，此時你可能會努力地回想，鑰匙究竟在哪個角落（可能在床上、床頭柜上、沙發上亦或者在廚房）此時此刻，你會開始你的搜尋工作流程，首先你把存在的可能性進行排序，然后逐個排查，最后，你發現通過你的查找居然還是沒有找到，如果你不假思考你可能會一遍又一遍地重復地查找下去（由于可能你會認為是自己檢查地不認真），從而始終在原地打轉，而其實鑰匙可能就放在家門旁邊的鞋柜上（可能是你換鞋的時候，把鑰匙臨時放在上面忘了拿起來而已）。而如果你夠機智的話，你會找完這些你最有可能放在的地方后重新搜尋新的地方，擴大搜尋面積，從而有助于最后能夠找到你的鑰匙。如果仍舊沒有找到，那你再繼續搜尋原來查找過的地方。（有可能真的是自己大意或者查找的不認真而無視了鑰匙就放在床頭柜上）這就是禁忌算法的核心思想，并且這個例子告訴我們不能死盯著某些老地方，要靈活一點，一沒查找到，就要考慮換位置（但是仍然沒找到的狀況下能夠以一定的周期返回來找），能夠用網絡流行語概括：“在不忘老情人的狀況下，盡量地雨露均沾”。對搜索性能有影響的因素禁忌長度控制其它變量，單就禁忌長度的選擇而言，禁忌長度越短，機器內存占用越少，解禁范疇更大（搜索范疇上限越大），但很容易造成搜索循環（實際去搜索的范疇卻很小），過早陷入局部最優。禁忌長度過長又會造成計算時間過長。特赦規則通俗定義：對于在禁忌的對象，如果出現下列狀況，不管現在對象的禁忌長度如何，均設為0。（1）基于評價值的規則，若出現一種解的目的值好于前面任何一種最佳候選解，可特赦；（2）基于最小錯誤的規則，若全部對象都被禁忌，特赦一種評價值最小的解；（3）基于影響力的規則，能夠特赦對目的值影響大的對象。候選集候選集的大小，過大增加計算內存和計算時間，過小過早陷入局部最優。候選集的選擇普通由鄰域中的鄰居構成，能夠選擇全部鄰居，也能夠選擇體現較好的鄰居，還能夠隨機選擇幾個鄰居。評價函數評價函數分為直接評價函數和間接評價函數。直接評價函數：上述例子，均直接使用目的值作為評價函數。間接評價函數：反映目的函數特性的函數（會比目的函數的計算更為簡便，用以減少計算時間等）。終止規則禁忌算法是一種啟發式算法，我們不可能讓搜索過程無窮進行，因此某些直觀的終止規則就出現了（1）擬定步數終止，無法確保解的效果，應統計現在最優解；（2）頻率控制原則，當某一種解、目的值或元素序列的頻率超出一種給定值時，終止計算；（3）目的控制原則，如果在一種給定步數內，現在最優值沒有變化，可終止計算。另一方面，變鄰域搜索算法（VNSA）就是一種改善型的局部搜索算法。它運用不同的動作構成的鄰域構造進行交替搜索，在集中性和疏散性之間達成較好的平衡。其思想能夠概括為“變則通”。變鄰域搜索算法依賴于下列事實：1)一種鄰域構造的局部最優解不一定是另一種鄰域構造的局部最優解。2)全局最優解是全部可能鄰域的局部最優解。變鄰域搜索算法重要由下列兩個部分構成：1)VARIABLENEIGHBORHOODDESCENT(VND)1.1)當在本鄰域搜索找不出一種比現在解更優的解的時候，我們就跳到下一種鄰域繼續進行搜索。如圖中虛黑線所示。1.2)當在本鄰域搜索找到了一種比現在解更優的解的時候，我們就跳回第一種鄰域重新開始搜索。如圖中紅線所示。2)SHAKINGPROCEDURE其實，說白了就是一種擾動算子，類似于鄰域動作的這樣一種東西。通過這個算子，能夠產生不同的鄰居解。即使名詞諸多看起來很高大上，擾動、抖動、鄰域動作這幾個本質上還是沒有什么區別的。都是通過一定的規則，將一種解變換到另一種解而已。模擬退火算法（SAA）是指模擬統計物理中固體物質的結晶過程。模擬退火來自HYPERLINK\o"冶金學"冶金學的專有名詞HYPERLINK\o"退火"退火。退火是將材料加熱后再經特定速率冷卻，目的是增大HYPERLINK\o"晶體"晶粒的體積，並且減少晶格中的缺點。材料中的原子原來會停留在使HYPERLINK\o"內能"內能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機在其它位置中移動。退火冷卻時速度較慢，使得原子有較多可能能夠找到內能比原先更低的位置。模擬退火的原理也和金屬退火的原理近似：我們將熱力學的理論套用到統計學上，將搜索空間內每一點想象成空氣內的分子；分子的能量，就是它本身的動能；而搜索空間內的每一點，也像空氣分子同樣帶有“能量”，以表達該點對命題的合適程度。算法先以搜索空間內一種任意點作起始：每一步先選擇一種“鄰居”，然后再計算從現有位置達成“鄰居”的概率。在退火的過程中，如果搜索到好的解接受；否則，以一定的概率接受不好的解（即實現多樣化或變異的思想），達成跳出局部最優解得目的。然而，模擬退火本質上也是一種貪心算法，但是它的搜索過程引入了隨機因素。在迭代更新可行解時，以一定的概率來接受一種比現在解要差的解，因此有可能會跳出這個局部的最優解，達成全局的最優解。下列圖為例，假定初始解為左邊藍色點A，模擬退火算法會快速搜索到局部最優解B，但在搜索到局部最優解后，不是就此結束，而是會以一定的概率接受到左邊的移動。可能通過幾次這樣的不是局部最優的移動后會達成全局最優點D，于是就跳出了局部最小值。模擬退火算法的優缺點模擬退火算法的應用很廣泛，能夠高效地求解NP完全問題，如貨郎擔問題(TravellingSalesmanProblem，簡記為TSP)、最大截問題(MaxCutProblem)、0-1背包問題(ZeroOneKnapsackProblem)、圖著色問題(GraphColouringProblem)等等，但其參數難以控制，不能確保一次就收斂到最優值，普通需要多次嘗試才干獲得（大部分狀況下還是會陷入局部最優值）。觀察模擬退火算法的過程，發現其重要存在以下三個參數問題：(1)溫度T的初始值設立問題溫度TT的初始值設立是影響模擬退火算法全局搜索性能的重要因素之一、初始溫度高，則搜索到全局最優解的可能性大，但因此要耗費大量的計算時間；反之，則可節省計算時間，但全局搜索性能可能受到影響。(2)退火速度問題，即每個TT值的迭代次數模擬退火算法的全局搜索性能也與退火速度親密有關。普通來說，同一溫度下的“充足”搜索是相稱必要的，但這也需要計算時間。循環次數增加必然帶來計算開銷的增大。(3)溫度管理問題溫度管理問題也是模擬退火算法難以解決的問題之一。實際應用中，由于必須考慮計算復雜度的切實可行性等問題，常采用以下所示的降溫方式：T=α×T.α∈(0,1).注：為了確保較大的搜索空間，α普通取靠近于1的值，如0.95、0.9。遺傳算法（GA）是從代表問題可能潛在的解集的一種種群（population）開始的，而一種種群則由通過基因（gene）編碼的一定數目的個體(individual)構成。每個個體事實上是染色體(chromosome)帶有特性的實體。染色體作為遺傳物質的重要載體，即多個基因的集合，其內部體現（即基因型）是某種基因組合，它決定了個體的形狀的外部體現，如黑頭發的特性是由染色體中控制這一特性的某種基因組合決定的。因此，在一開始需要實現從體現型到基因型的映射即編碼工作。由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼。初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，并借助于自然遺傳學的遺傳算子（geneticoperators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將造成種群像自然進化同樣的后生代種群比前代更加適應于環境，末代種群中的最優個體通過解碼（decoding），能夠作為問題近似最優解。大致實現過程遺傳算法中每一條染色體，對應著遺傳算法的一種解決方案，普通我們用適應性函數（fitnessfunction）來衡量這個解決方案的優劣。因此從一種基因組到其解的適應度形成一種映射。遺傳算法的實現過程事實上就像自然界的進化過程那樣。下面就簡樸介紹一下具體流程，以方便大家理解：1.首先尋找一種對問題潛在解進行“數字化”編碼的方案。（建立體現型和基因型的映射關系）2.隨機初始化一種種群，種群里面的個體就是這些數字化的編碼。3.接下來，通過合適的解碼過程之后。4.用適應性函數對每一種基因個體作一次適應度評定。5.用選擇函數按照某種規定擇優選擇（每隔一段時間，刪除某些解的質量較差的一批解，以總體解的數目持平）。6.讓個體基因變異。7.然后產生子代（但愿留下來的都是質量較好的解，這樣它們就能夠產生更多后裔）。輪盤賭思想：染色體交叉：二進制交叉：變異--基因突變(Mutation)遺傳算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座上的其它等位基因來替代，從而形成新的個體。例以下面這串二進制編碼：001通過基因突變后，可能變成下列這串新的編碼：001下列變異算子合用于二進制編碼和浮點數編碼的個體：1.基本位變異（SimpleMutation）：對個體編碼串中以變異概率、隨機指定的某一位或某幾位僅因座上的值做變異運算。2.均勻變異（UniformMutation）：分別用符合某一范疇內均勻分布的隨機數，以某一較小的概率來替代個體編碼串中各個基因座上的原有基因值。（特別合用于在算法的初級運行階段）3.邊界變異（BoundaryMutation）：隨機的取基因座上的兩個對應邊界基因值之一去替代原有基因值。特別合用于最優點位于或靠近于可行解的邊界時的一類問題。4.非均勻變異：對原有的基因值做一隨機擾動，以擾動后的成果作為變異后的新基因值。對每個基因座都以相似的概率進行變異運算之后，相稱于整個解向量在解空間中作了一次輕微的變動。5.高斯近似變異：進行變異操作時用符號均值為Ｐ的平均值，方差為P**2的正態分布的一種隨機數來替代原有的基因值。優點：(1)遺傳算法從問題解的串集開始搜索，而不是從單個解開始。這是遺傳算法與傳統優化算法的極大區別。傳統優化算法是從單個初始值HYPERLINK迭代求最優解的；容易誤入局部最優解。遺傳算法從串集開始搜索，覆蓋面大，利于全局擇優。(2)遺傳算法同時解決群體中的多個個體，即對搜索空間中的多個解進行評定，減少了陷入局部最優解的風險，同時算法本身易于實現并行化。(3)遺傳算法基本上不用搜索空間的知識或其它HYPERLINK輔助信息，而僅用HYPERLINK適應度HYPERLINK函數值來評定個體，在此基礎上進行HYPERLINK遺傳操作。HYPERLINK適應度函數不僅不受HYPERLINK持續可微的約束，并且其HYPERLINK定義域能夠任意設定。這一特點使得遺傳算法的應用范疇大大擴展。(4)遺傳算法不是采用擬定性規則，而是采用概率的變遷規則來HYPERLINK指導他的搜索方向。(5)含有自組織、自適應和自學習性。遺傳算法運用進化過程獲得的信息自行組織搜索時，HYPERLINK適應度大的個體含有較高的生存概率，并獲得更適應HYPERLINK環境的HYPERLINK基因構造。(6)另外，算法本身也能夠采用動態自適應技術，在進化過程中自動調節算法控制參數和編碼精度，例如使用含糊自適應法。缺點與局限性：(1)編碼不規范及編碼存在表達的不精確性。(2)單一的遺傳算法編碼不能全方面地將優化問題的約束表達出來。考慮約束的一種辦法就是對不可行解采用閾值，這樣，計算的時間必然增加。(3)遺傳算法普通的效率比其它傳統的優化辦法低。(4)遺傳算法容易過早收斂。(5)遺傳算法對算法的精度、可行度、計算復雜性等方面，還沒有有效的定量分析辦法。最后總結：正如我們看見的那樣，遺傳算法，每次迭代都會從整個集合中去計算選擇，然后通過交叉變異去產生新的種群，這樣的好處顯而易見，不會像梯度下降，貪心這類算法會陷入局部最優,至于其編碼的選擇，我想編碼的好壞決定了適應函數的簡樸還是復雜的程度，適應函數設計的好壞決定了，整個算法與否能更快更加好的收斂于近似最優。注意這里，遺傳算法不能確保會得到最優解，但是在整個迭代過程，它會不停的靠近于最優。值得一提的是，遺傳算法是基于圖式理論的，其基因型從各個特性進行描述，這樣就隱含了其搜索過程是并行解決的，對于隱含并行能力，現在已經給出了證明，每次迭代，對于n的種群，大致解決了O(n^3)個狀態，這個解決能力還是相稱吃驚的。蟻群算法（ACOA），為什么提到蟻群算法呢？這是由于蟻群算法盡管只是作為一種高效的元啟發式算法，但它卻與背面強化學習等人工智能智能算法有著非常相似的特性。首先介紹一下蟻群算法的發展背景和歷史，蟻群系統(AntSystem或AntColonySystem)是由意大利學者Dorigo、Maniezzo等人于20世紀90年代首先提出來的。他們在研究螞蟻覓食的過程中，發現單個螞蟻的行為比較簡樸，但是蟻群整體卻能夠體現某些智能的行為。例如蟻群能夠在不同的環境下，尋找最短達成食物源的途徑。這是由于蟻群內的螞蟻能夠通過某種信息機制實現信息的傳遞。后又經進一步研究發現，螞蟻會在其通過的途徑上釋放一種能夠稱之為“信息素”的物質，蟻群內的螞蟻對“信息素”含有感知能力，它們會沿著“信息素”濃度較高途徑行走，而每只路過的螞蟻都會在路上留下“信息素”，這就形成一種類似正反饋的機制，這樣通過一段時間后，整個蟻群就會沿著最短途徑達成食物源了。算法的思想：用螞蟻的行走途徑表達待優化問題的可行解，整個螞蟻群體的全部途徑構成待優化問題的HYPERLINK解空間。途徑較短的螞蟻釋放的信息素量較多，隨著時間的推動，較短的途徑上累積的信息素濃度逐步增高，選擇該途徑的螞蟻個數也愈來愈多。最后，整個螞蟻會在正反饋的作用下集中到最佳的途徑上，此時對應的便是待優化問題的HYPERLINK最優解。蟻群算法的設計規則：1、覓食規則螞蟻感知范疇是一種3*3的格子，也就是說，他這個格子中有食物就直接過去。2、移動規則螞蟻會朝著信息素濃的地方移動，如果沒有感知到信息素，就會按著慣性始終走下去，別忘了，螞蟻會創新呦！3、避障規則螞蟻在碰到障礙物的時候會選擇隨機方向移動，同時遵照上面兩個規則。4、信息素規則螞蟻在剛發現食物的時候揮灑的信息素會多，距離越遠，信息素越少。缺點和存在的問題：通過親自動手做實驗，你會發現，當螞蟻在一條途徑上覓食很久時，你再放置一種近的食物基本沒啥效果，你也能夠理解為當一只螞蟻找到一條途徑時，過了很久的時間，大多數螞蟻都選擇了這條途徑，就在這時候，忽然有一只螞蟻找到了較近的食物，但由于時間過得太久，兩條途徑上濃度相差太大（濃度越大，被選擇的概率就越大），整個系統基本已經停滯了，陷入了局部最優。因此簡樸的螞蟻系統是存在某些問題的，如：1.搜索到一定程度，會出現停滯狀態，陷入局部最優的狀況2.盲目的隨機搜索，搜索時間較長而影響螞蟻與否能夠找到好的最優解，依賴這幾個核心因素：1.信息素怎么灑播（例如維持在一種特地范疇的值等）2.信息素怎么揮發（除了全局揮發，能夠讓螞蟻本身進行局部揮發等手段）3.通過如何的方式讓螞蟻選擇運動方向，減少盲目性和不必要性（給螞蟻一點點智能和經驗）4.給螞蟻和環境一定的記憶能力能夠協助減少搜索空間蟻群算法尚有諸多變形和改善，諸如：最大最小蟻群算法、排序蟻群算法、基于遺傳算法的蟻群算法等一系列在基本蟻群系統上的優化和改善，他們對于信息素的使用、螞蟻方向選擇等都有一套成熟的數學模型和經驗優化參數。

啟發式算法的實際應用正如上述介紹的同樣，啟發式算法種類繁多，思想各異但都相通，這里就不能一一列舉，就只展示2種啟發式算法在不同問題的應用。其中，蟻群算法應用廣泛，如旅行商問題(travelingsalesmanproblem,簡稱TSP)、指派問題、Job-shop調度問題、車輛途徑問題（vehicleroutingproblem）、圖著色問題(graphcoloringproblem)和網絡路由問題（networkroutingproblem）等等。首先，介紹一下蟻群算法的在典型TSP問題當中的應用，問題描述和參數設立描述以及構建對應的數學模型以下：標注：具體的C++代碼在附件內。第二個算法，重要是遺傳算法（GA），眾所周知，遺傳算法作為一種高效的算法設計框架，它不局限于任何問題，因此這里就簡樸介紹一下它在函數求極值上的運用。題目和條件以下：實驗成果以下：結合網上博客大咖的某些觀點和見解，得到的一點啟示：遺傳算法看似隨機，但背后卻是非隨機的，是隨機中朝最優解的一種方略。其過程有做了確保朝優值的方向的方略，一種是變異，另外一種是基因保存。不停的能夠確保種群朝著最優方向進化。同時遺傳算法的適應度函數的設計規定普通需要滿足單值、持續、非負、最大化、計算量小、通用性強，因此適應度函數的設計需要根據結合實際的問題本身的特點而定。遺傳算法設計的幾個核心參數：種群規模、交配率、變異率、進化代數；這幾個參數的設計對函數的最后收斂性有著關系。標注：具體的代碼在背面附件內。C++代碼附件//蟻群算法（ACO，有關TSP問題的C++源代碼）#include<bits/stdc++.h>usingnamespacestd;//constconstintINF=0x3f3f3f3f;#definesqr(x)((x)*(x))#defineeps1e-8//variablesstringfile_name;inttype;//type==1全矩陣,type==2二維歐拉距離intN;//都市數量double**dis;//都市間距離double**pheromone;//信息素double**herustic;//啟發式值double**info;//info=pheromone^delta*herustic^betadoublepheromone_0;//pheromone初始值，這里是1/(avg*N)其中avg為圖網中全部邊邊權的平均數。intm;//種群數量intdelta,beta;//參數doublealpha;int*r1,*s,*r;//agentk的出發都市，下一種點，現在點。intMAX,iteration;//最大迭代次數，迭代計數變量set<int>empty,*J;structvertex{doublex,y;//都市坐標intid;//都市編號intinput(FILE*fp){returnfscanf(fp,"%d%lf%lf",&id,&x,&y);}}*node;typedefpair<int,int>pair_int;structTour{//途徑vector<pair_int>path;//path[i]，存儲一條邊(r,s)doubleL;voidclean(){L=INF;path.clear();path.shrink_to_fit();}//清空voidcalc(){L=0;intsz=path.size();for(inti=0;i<sz;i++){L+=dis[path[i].first][path[i].second];}}//計算長度voidpush_back(intx,inty){path.push_back(make_pair(x,y));}intsize(){return(int)path.size();}intr(inti){returnpath[i].first;}ints(inti){returnpath[i].second;}voidprint(FILE*fp){intsz=path.size();for(inti=0;i<sz;i++){fprintf(fp,"%d->",path[i].first+1);}fprintf(fp,"%d\n",path[sz-1].second+1);}booloperator<(constTour&a)const{returnL<a.L;}//重載}*tour,best_so_far;doubleEUC_2D(constvertex&a,constvertex&b){returnsqrt(sqr(a.x-b.x)+sqr(a.y-b.y));}voidio(){//輸入printf("inputfile_nameanddatatype\n");cin>>file_name>>type;FILE*fp=fopen(file_name.c_str(),"r");fscanf(fp,"%d",&N);node=newvertex[N+5];dis=newdouble*[N+5];doubletmp=0;intcnt=0;if(type==1){for(inti=0;i<N;i++){dis[i]=newdouble[N];for(intj=0;j<N;j++){fscanf(fp,"%lf",&dis[i][j]);tmp+=i!=j?dis[i][j]:0;//i==j的時候dis不存在，因此不考慮。cnt+=i!=j?1:0;//i==j的時候dis不存在，因此不考慮。}}}else{for(inti=0;i<N;i++)node[i].input(fp);for(inti=0;i<N;i++){dis[i]=newdouble[N];for(intj=0;j<N;j++){dis[i][j]=EUC_2D(node[i],node[j]);//計算距離tmp+=i!=j?dis[i][j]:0;//i==j的時候dis不存在，因此不考慮。cnt+=i!=j?1:0;//i==的時候dis不存在，因此不考慮。}}}pheromone_0=(double)cnt/(tmp*N);//pheromone初始值，這里是1/(avg*N)其中avg為圖網中全部邊邊權的平均數。fclose(fp);return;}voidinit(){//初始化alpha=0.1;//evaporationparameter，揮發參數，每次信息素要揮發的量delta=1;beta=6;//delta和beta分別表達pheromones和herustic的比重m=N;pheromone=newdouble*[N+5];herustic=newdouble*[N+5];info=newdouble*[N+5];r1=newint[N+5];r=newint[N+5];s=newint[N+5];J=newset<int>[N+5];empty.clear();for(inti=0;i<N;i++){pheromone[i]=newdouble[N+5];herustic[i]=newdouble[N+5];info[i]=newdouble[N+5];empty.insert(i);for(intj=0;j<N;j++){pheromone[i][j]=pheromone_0;herustic[i][j]=1/(dis[i][j]+eps);//加一種小數eps，避免被零除}}best_so_far.clean();iteration=0;MAX=N*N;}doublepower(doublex,inty){//快速冪，計算x^y，時間復雜度O(logn),感愛好能夠百度doubleans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}returnans;}voidreset(){tour=newTour[m+5];for(inti=0;i<N;i++){tour[i].clean();r1[i]=i;//初始化出發都市，J[i]=empty;J[i].erase(r1[i]);//初始化agenti需要訪問的都市r[i]=r1[i];//現在在出發點}for(inti=0;i<N;i++)for(intj=0;j<N;j++){info[i][j]=power(pheromone[i][j],delta)*power(herustic[i][j],beta);}//選擇公式}intselect_next(intk){if(J[k].empty())returnr1[k];//如果J是空的，那么返回出發點都市doublernd=(double)(rand())/(double)RAND_MAX;//產生0..1的隨機數set<int>::iteratorit=J[k].begin();doublesum_prob=0,sum=0;for(;it!=J[k].end();it++){sum+=info[r[k]][*it];}//計算概率分布rnd*=sum;it=J[k].begin();for(;it!=J[k].end();it++){sum_prob+=info[r[k]][*it];if(sum_prob>=rnd){return*it;}}//根據概率選用下一步都市}voidconstruct_solution(){for(inti=0;i<N;i++){for(intk=0;k<m;k++){intnext=select_next(k);//選擇下一步的最優決策J[k].erase(next);s[k]=next;tour[k].push_back(r[k],s[k]);r[k]=s[k];}}}voidupdate_pheromone(){Tournow_best;now_best.clean();//初始化for(inti=0;i<m;i++){tour[i].calc();if(tour[i]<now_best)now_best=tour[i];//尋找現在迭代最優解}if(now_best<best_so_far){best_so_far=now_best;//更新最優解}for(inti=0;i<N;i++)for(intj=0;j<N;j++)pheromone[i][j]*=(1-alpha);//信息素揮發intsz=now_best.size();for(inti=0;i<sz;i++){pheromone[now_best.r(i)][now_best.s(i)]+=1./(double)now_best.L;pheromone[now_best.s(i)][now_best.r(i)]=pheromone[now_best.r(i)][now_best.s(i)];//對稱}//更新信息素含量}intmain(){srand((unsigned)time(0));//初始化隨機種子io();init();doublelast=INF;intbad_times=0;for(;iteration<MAX;iteration++){if(bad_times>N)break;//進入局部最優reset();//初始化agent信息construct_solution();//對于全部的agent構造一種完整的tourupdate_pheromone();//更新信息素printf("iteration%d:best_so_far=%.2lf\n",iteration,best_so_far.L);if(last>best_so_far.L)last=best_so_far.L,bad_times=0;elsebad_times++;//統計現在未更新代數，若迭代多次未更新，認為進入局部最優}printf("best_so_far=%.2lf\n",best_so_far.L);//輸出目的值best_so_far.print(stdout);//輸出途徑}//實驗測試數據以下：輸入文獻格式為：File_nameFile_typesalesman.in150122320342320413450524140輸出成果為：opt_solution:11//遺傳算法（GA，求函數極值的C++源代碼）//Genetic.h頭文獻#ifndef_GENETIC_H_#define_GENETIC_H_usingnamespacestd;#definePI3.//遺傳算法參數，種群規模（0~100）、繁殖代數、函數變量個數、交叉概率、編譯概率#defineGROUP_SCALE50#defineMAX_GENS500#defineN_VARS2#defineP_MATING0.8#defineP_MUTATION0.15structIndividual{doubleXn[N_VARS];//寄存變量值doubleFitness;//適應值doubleReFitness;//適應值概率密度doubleSumFitness;//累加分布，為輪盤轉};structX_Range{doubleUpper;//變量的上界取值doubleLower;//變量的下界取值};template<typenameT>TrandT(TLower,TUpper);//產生任意類型隨機數函數voidcrossover(int&seed);voidelitist();//基因保存voidevaluate();voidinitGroup(int&seed);voidselectBest();voidmutate(int&seed);doubler8_uniform_ab(doublea,doubleb,int&seed);inti4_uniform_ab(inta,intb,int&seed);voidreport(intXnration);voidselector(int&seed);voidshowTime();voidXover(intone,inttwo,int&seed);#endif//!_GENETIC_H_//Genetic.CPP#include<cstdlib>#include<iostream>#include<iomanip>#include<fstream>#include<iomanip>#include<cmath>#include<ctime>#include<cstring>#include"Genetic.h"http://申請種群內存，其中多加1個是放置上一代中最優秀個體structIndividualPopulation[GROUP_SCALE+1];X_RangeXnRange[N_VARS]={{-3.0,12.1},{4.1,5.8}};//有交配權的全部父代進行交叉voidcrossover(int&seed){constdoublea=0.0;constdoubleb=1.0;intmem;intone;intfirst=0;doublex;for(mem=0;mem<GROUP_SCALE;++mem){x=randT(0.0,1.0);//x=r8_uniform_ab(a,b,seed);//產生交配概率if(x<P_MATING){++first;if(first%2==0)//交配{Xover(one,mem,seed);}else{one=mem;}}}return;}//對最差的一代和最優的一代的解決，起到優化的目的voidelitist(){inti;doublebest;intbest_mem;doubleworst;intworst_mem;best=Population[0].Fitness;worst=Population[0].Fitness;for(i=0;i<GROUP_SCALE-1;++i){if(Population[i+1].Fitness<Population[i].Fitness){if(best<=Population[i].Fitness){best=Population[i].Fitness;best_mem=i;}if(Population[i+1].Fitness<=worst){worst=Population[i+1].Fitness;worst_mem=i+1;}}else{if(Population[i].Fitness<=worst){worst=Population[i].Fitness;worst_mem=i;}if(best<=Population[i+1].Fitness){best=Population[i+1].Fitness;best_mem=i+1;}}}//對于現在代的最優值的解決，如果現在的最優值不大于上一代則將上一代的值最優個體取代現在的最弱個體//基因保存if(Population[GROUP_SCALE].Fitness<=best){for(i=0;i<N_VARS;i++){Population[GROUP_SCALE].Xn[i]=Population[best_mem].Xn[i];}Population[GROUP_SCALE].Fitness=Population[best_mem].Fitness;}else{for(i=0;i<N_VARS;i++){Population[worst_mem].Xn[i]=Population[GROUP_SCALE].Xn[i];}Population[worst_mem].Fitness=Population[GROUP_SCALE].Fitness;}return;}//計算適應度值voidevaluate(){intmember;inti;doublex[N_VARS+1];for(member=0;member<GROUP_SCALE;member++){for(i=0;i<N_VARS;i++){x[i+1]=Population[member].Xn[i];}Population[member].Fitness=21.5+x[1]*sin(4*PI*x[1])+x[2]*sin(20*PI*x[2]);}return;}//產生整形的隨機數inti4_uniform_ab(inta,intb,int&seed){intc;constinti4_huge=;intk;floatr;intvalue;if(seed==0){cerr<<"\n";cerr<<"I4_UNIFORM_AB-Fatalerror!\n";cerr<<"InputvalueofSEED=0.\n";exit(1);}//確保a不大于bif(b<a){c=a;a=b;b=c;}k=seed/127773;seed=16807*(seed-k*127773)-k*2836;if(seed<0){seed=seed+i4_huge;}r=(float)(seed)*4.E-10;////ScaleRtoliebetweenA-0.5andB+0.5.//r=(1.0-r)*((float)a-0.5)+r*((float)b+0.5);////UseroundingtoconvertRtoanintegerbetweenAandB.//value=round(r);//四舍五入//確保取值不越界if(value<a){value=a;}if(b<value){value=b;}returnvalue;}//初始化種群個體voidinitGroup(int&seed){inti;intj;doublelbound;doubleubound;////initGroupvariableswithinthebounds//for(i=0;i<N_VARS;i++){//input>>lbound>>ubound;for(j=0;j<GROUP_SCALE;j++){Population[j].Fitness=0;Population[j].ReFitness=0;Population[j].SumFitness=0;Population[j].Xn[i]=randT(XnRange[i].Lower,XnRange[i].Upper);//Population[j].Xn[i]=r8_uniform_ab(XnRange[i].Lower,XnRange[i].Upper,seed);}}return;}//挑選出最大值，保存在種群數組的最后一種位置voidselectBest(){intcur_best;intmem;inti;cur_best=0;for(mem=0;mem<GROUP_SCALE;mem++){if(Population[GROUP_SCALE].Fitness<Population[mem].Fitness){cur_best=mem;Population[GROUP_SCALE].Fitness=Population[mem].Fitness;}}for(i=0;i<N_VARS;i++){Population[GROUP_SCALE].Xn[i]=Population[cur_best].Xn[i];}return;}//個體變異voidmutate(int&seed){constdoublea=0.0;constdoubleb=1.0;inti;intj;doublelbound;doubleubound;doublex;for(i=0;i<GROUP_SCALE;i++){for(j=0;j<N_VARS;j++){//x=r8_uniform_ab(a,b,seed);x=randT(a,b);//突變概率if(x<P_MUTATION){lbound=XnRange[j].Lower;ubound=XnRange[j].Upper;Population[i].Xn[j]=randT(