啟發(fā)式算法簡(jiǎn)談（一）
引言：
解決實(shí)際的問(wèn)題，要建模型，在求解。求解要選擇算法，只有我們對各種算法的優(yōu)缺點(diǎn)都很熟悉后才能根據實(shí)際問(wèn)題選出有效的算法。但是對各種算法都了如指掌是不現實(shí)的，但多知道一些，會(huì )使你的選擇集更大，找出最好算法的概率越大?，F在研一，要開(kāi)題了些點(diǎn)文獻綜述，愿與大家分享。
大自然是神奇的，它造就了很多巧妙的手段和運行機制。受大自然的啟發(fā)，人們從大自然的運行規律中找到了許多解決實(shí)際問(wèn)題的方法。對于那些受大自然的運行規律或者面向具體問(wèn)題的經(jīng)驗、規則啟發(fā)出來(lái)的方法，人們常常稱(chēng)之為啟發(fā)式算法（HeuristicAlgorithm）?，F在的啟發(fā)式算法也不是全部來(lái)自然的規律，也有來(lái)自人類(lèi)積累的工作經(jīng)驗。
啟發(fā)式算法的發(fā)展：
啟發(fā)式算法的計算量都比較大，所以啟發(fā)式算法伴隨著(zhù)計算機技術(shù)的發(fā)展，取得了巨大的成就。
40年代：由于實(shí)際需要，提出了啟發(fā)式算法（快速有效）。
50年代：逐步繁榮，其中 貪婪算法和局部搜索 等到人們的關(guān)注。
60年代: 反思，發(fā)現以前提出的啟發(fā)式算法速度很快，但是解得質(zhì)量不能保證，而且對大規
模的問(wèn)題仍然無(wú)能為力（收斂速度慢）。
70年代：計算復雜性理論的提出，NP問(wèn)題。許多實(shí)際問(wèn)題不可能在合理的時(shí)間范圍內找到全局最優(yōu)解。發(fā)現貪婪算法和局部搜索算法速度快，但解不好的原因主要是他們只是在局部的區域內找解，等到的解沒(méi)有全局最優(yōu)性。
由此必須引入新的搜索機制和策略………..
Holland的遺傳算法出現了（Genetic Algorithm）再次引發(fā)了人們研究啟發(fā)式算法的
興趣。
80年代以后：
模擬退火算法（Simulated Annealing Algorithm），人工神經(jīng)網(wǎng)絡(luò )（Artificial Neural Network），禁忌搜索（Tabu Search）相繼出現。
最近比較熱或剛熱過(guò)去的：
演化算法（Evolutionary Algorithm）, 蟻群算法（Ant Algorithms）， 擬人擬物算法，量子算法等。
各個(gè)算法的思想這就不再詳細給出（以后會(huì )給出一些，關(guān)注我的blog），為什么要引出啟發(fā)式算法，因為NP問(wèn)題，一般的經(jīng)典算法是無(wú)法求解，或求解時(shí)間過(guò)長(cháng)，我們無(wú)法接受。這里要說(shuō)明的是：?jiǎn)l(fā)式算法得到的解只是近似最優(yōu)解（近似到什么程度，只有根據具體問(wèn)題才能給出）. 二十一世紀的最大的數學(xué)難題NP？=P，如果NP=P啟發(fā)式算法就不在有存在的意義。
啟發(fā)式算法的不足和如何解決方法：
（水平有限 僅僅提出6點(diǎn)）
啟發(fā)式算法目前缺乏統一、完整的理論體系。
很難解決！ 啟發(fā)式算法的提出就是根據經(jīng)驗提出，沒(méi)有什么堅實(shí)的理論基礎。
由于NP理論，啟發(fā)式算法就解得全局最優(yōu)性無(wú)法保證。
等NP？=P有結果了再說(shuō)吧，不知道這個(gè)世紀能不能行。
各種啟發(fā)式算法都有個(gè)自?xún)?yōu)點(diǎn)如何，完美結合。
如果你沒(méi)有實(shí)際經(jīng)驗，你就別去干這個(gè)，相結合就要做大量嘗試，或許會(huì )有意外的收獲。
啟發(fā)式算法中的參數對算法的效果起著(zhù)至關(guān)重要的作用，如何有效設置參數。
還是那句話(huà)，這是經(jīng)驗活但還要悟性，只有try again………..
啟發(fā)算法缺乏有效的迭代停止條件。
還是經(jīng)驗，迭代次數100不行，就200，還不行就1000…………
還不行估計就是算法有問(wèn)題，或者你把它用錯地方了………..
啟發(fā)式算法收斂速度的研究等。
你會(huì )發(fā)現，沒(méi)有完美的東西，要快你就要付出代價(jià)，就是越快你得到的解也就遠差。 (待續)
聯(lián)系客服
