千手牛股2018-12-21 17:00:30一、粒子群演算法
粒子群演算法，也稱粒子群最佳化演算法（Particle Swarm Optimization），縮寫為 PSO， 是近年來發展起來的一種新的進化演算法（（Evolu2tionary Algorithm - EA）。PSO 演算法屬於進化演算法的一種，和遺傳演算法相似，它也是從隨機解出發，透過迭代尋找最優解，它也是透過適應度來評價解的品質，但它比遺傳演算法規則更為簡單，它沒有遺傳演算法的交叉（Crossover） 和變異（Mutation） 操作，它透過追隨當前搜尋到的最優值來尋找全域性最優。這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，並且在解決實際問題中展示了其優越性。
最佳化問題是工業設計中經常遇到的問題，許多問題最後都可以歸結為最佳化問題。為了解決各種各樣的最佳化問題，人們提出了許多最佳化演算法，比較著名的有爬山法、遺傳演算法等。最佳化問題有兩個主要問題：一是要求尋找全域性最小點，二是要求有較高的收斂速度。爬山法精度較高，但是易於陷入區域性極小。遺傳演算法屬於進化演算法（EvolutionaryAlgorithms）的一種，它透過模仿自然界的選擇與遺傳的機理來尋找最優解。遺傳演算法有三個基本運算元：選擇、交叉和變異。但是遺傳演算法的程式設計實現比較複雜，首先需要對問題進行編碼，找到最優解之後還需要對問題進行解碼，另外三個運算元的實現也有許多引數，如交叉率和變異率，並且這些引數的選擇嚴重影響解的品質，而目前這些引數的選擇大部分是依靠經驗。1995年Eberhart博士和kennedy博士提出了一種新的演算法；粒子群最佳化（ParticalSwarmOptimization-PSO）演算法。這種演算法以其實現容易、精度高、收斂快等優點引起了學術界的重視，並且在解決實際問題中展示了其優越性。
粒子群最佳化（ParticalSwarmOptimization-PSO）演算法是近年來發展起來的一種新的進化演算法（Evolu2tionaryAlgorithm-EA）。PSO演算法屬於進化演算法的一種，和遺傳演算法相似，它也是從隨機解出發，透過迭代尋找最優解，它也是透過適應度來評價解的品質。但是它比遺傳演算法規則更為簡單，它沒有遺傳演算法的交叉（Crossover）和變異（Mutation）操作。它透過追隨當前搜尋到的最優值來尋找全域性最優
二、遺傳演算法
遺傳演算法是計算數學中用於解決最佳化的，是進化演算法的一種。進化演算法最初是借鑑了進化生物學中的一些現象而發展起來的，這些現象包括遺傳、突變、自然選擇以及雜交等。遺傳演算法通常實現方式為一種模擬。對於一個最最佳化問題，一定數量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進化。傳統上，解用表示（即0和1的串），但也可以用其他表示方法。進化從完全隨機個體的種群開始，之後一代一代發生。在每一代中，整個種群的適應度被評價，從當前種群中隨機地選擇多個個體（基於它們的適應度），透過自然選擇和突變產生新的生命種群，該種群在演算法的下一次迭代中成為當前種群。
主要特點
遺傳演算法是解決搜尋問題的一種通用演算法，對於各種通用問題都可以使用。的共同特徵為：
① 首先組成一組候選解
② 依據某些適應性條件測算這些候選解的適應度
③ 根據適應度保留某些候選解，放棄其他候選解
④ 對保留的候選解進行某些操作，生成新的候選解。
在遺傳演算法中，上述幾個特徵以一種特殊的方式組合在一起：基於染色體群的並行搜尋，帶有猜測性質的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳演算法與其它搜尋演算法區別開來。
遺傳演算法還具有以下幾方面的特點：
（1）遺傳演算法從問題解的串集開始搜尋，而不是從單個解開始。這是遺傳演算法與傳統最佳化演算法的極大區別。傳統最佳化演算法是從單個初始值求最優解的；容易誤入區域性最優解。遺傳演算法從串集開始搜尋，覆蓋面大，利於全域性擇優。
（2）遺傳演算法同時處理群體中的多個個體，即對搜尋空間中的多個解進行評估，減少了陷入區域性最優解的風險，同時演算法本身易於實現並行化。
（3）遺傳演算法基本上不用搜索空間的知識或其他輔助資訊，而僅用適應度函式值來評估個體，在此基礎上進行遺傳操作。適應度函式不僅不受連續可微的約束，而且其定義域可以任意設定。這一特點使得遺傳演算法的應用範圍大大擴充套件。
（4）遺傳演算法不是採用確定性規則，而是採用機率的變遷規則來指導他的搜尋方向。
（5）具有自組織、自適應和自學習性。遺傳演算法利用進化過程獲得的資訊自行組織搜尋時，適應度大的個體具有較高的生存機率，並獲得更適應的基因結構。
三、貪婪演算法
概念：貪婪演算法是一種不追求最優解，只希望得到較為滿意解的方法。
貪婪演算法一般可以快速得到滿意的解，因為它省去了為找最優解要窮盡所有可能而必須耗費的大量時間。貪婪演算法常以當前情況為基礎作最優選擇，而不考慮各種可能的整體情況。例如平時購物找錢時，為使找回的零錢的硬幣數最少，不考慮找零錢的所有各種發表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先儘量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。這就是在使用貪婪演算法。這種方法在這裡總是最優，是因為銀行對其發行的硬幣種類和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪演算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優的解應是3個5單位面值的硬幣。
四、蟻群演算法
蟻群演算法（ant colony optimization， ACO），又稱螞蟻演算法，是一種用來在圖中尋找最佳化路徑的機率型技術。它由Marco Dorigo於1992年在他的博士論文中引入，其靈感來源於螞蟻在尋找食物過程中發現路徑的行為。
自然界的種群相當廣泛，但大部分都有以下的能力： 螞蟻們總能找到食物源和螞蟻窩之間的最短路徑。 一旦這條最短路徑被發現， 螞蟻們就能在這條路上排成一行， 在食物源和螞蟻窩之間搬運食物。 螞蟻們是怎麼做到的呢？
我們知道，2點間直線距離最短。 但螞蟻們顯然不具備這樣的視力和智慧。 它們無法從遠處看到食物源， 也無法計劃一個合適的路徑來搬運食物。 螞蟻們採用的方法是全體在老窩的周圍區域進行地毯式搜尋。而他們之間的是透過分泌化學物質在爬過的路徑上，這種化學物質叫（Pheromone）。
螞蟻們習慣選擇資訊素濃度高的路徑。 下面的圖解釋了螞蟻們的工作原理。
剛開始離開窩的時候， 螞蟻們有兩條路徑選擇： R1和R2。 這兩者機會相當。 螞蟻們在爬過R1和R2的時候都留下了資訊素。 但是， 由於R2的距離短， 所需要的時間就少， 而資訊素會揮發， 所以螞蟻們留在R2上的資訊素濃度就高。 於是，越來越多的螞蟻選擇R2作為最佳路徑， 即使它們是從R1來到食物源，也將選擇R2返回螞蟻窩。 而從老巢裡出發的螞蟻們也越來越傾向於R2。 在這樣的趨勢下， R1漸漸變的無人問津了
根據螞蟻們選擇路徑的方法而得到的啟發， Dr。 Dorigo在1991年發表了（Ant algorithm）。 十多年來， 螞蟻演算法，以及各種改進過的螞蟻演算法，被廣泛的應用在實際生活的各個方面。 在應用中，它可以作為網路路由控制的工具。 在交通控制中， 它也成功解決了車輛排程問題。在圖表製作中， 它被用來解決顏色填充問題。 此外， 它還可以被用來設計大規模的時刻表。 而問題，既在多個不同地點間往返的最佳路徑選擇問題， 應該算是螞蟻演算法最重要的用途了。
