AI人工智能的幾種常用算法概念

一、粒子群算法

?

粒子群算法，也稱(chēng)粒子群優(yōu)化算法（Particle Swarm Optimization），縮寫(xiě)為 PSO， 是近年來(lái)發(fā)展起來(lái)的一種新的進(jìn)化算法（（Evolu2tionary Algorithm - EA）。PSO 算法屬于進(jìn)化算法的一種，和遺傳算法相似，它也是從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，它也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)，但它比遺傳算法規(guī)則更為簡(jiǎn)單，它沒(méi)有遺傳算法的交叉（Crossover） 和變異（Mutation） 操作，它通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問(wèn)題中展示了其優(yōu)越性。

優(yōu)化問(wèn)題是工業(yè)設(shè)計(jì)中經(jīng)常遇到的問(wèn)題，許多問(wèn)題最后都可以歸結(jié)為優(yōu)化問(wèn)題。為了解決各種各樣的優(yōu)化問(wèn)題，人們提出了許多優(yōu)化算法，比較著名的有爬山法、遺傳算法等。優(yōu)化問(wèn)題有兩個(gè)主要問(wèn)題：一是要求尋找全局最小點(diǎn)，二是要求有較高的收斂速度。爬山法精度較高，但是易于陷入局部極小。遺傳算法屬于進(jìn)化算法（EvolutionaryAlgorithms）的一種，它通過(guò)模仿自然界的選擇與遺傳的機(jī)理來(lái)尋找最優(yōu)解。遺傳算法有三個(gè)基本算子：選擇、交叉和變異。但是遺傳算法的編程實(shí)現(xiàn)比較復(fù)雜，首先需要對(duì)問(wèn)題進(jìn)行編碼，找到最優(yōu)解之后還需要對(duì)問(wèn)題進(jìn)行解碼，另外三個(gè)算子的實(shí)現(xiàn)也有許多參數(shù)，如交叉率和變異率，并且這些參數(shù)的選擇嚴(yán)重影響解的品質(zhì)，而目前這些參數(shù)的選擇大部分是依靠經(jīng)驗(yàn).1995年Eberhart博士和kennedy博士提出了一種新的算法;粒子群優(yōu)化（ParticalSwarmOptimization-PSO）算法。這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的重視，并且在解決實(shí)際問(wèn)題中展示了其優(yōu)越性。

粒子群優(yōu)化（ParticalSwarmOptimization-PSO）算法是近年來(lái)發(fā)展起來(lái)的一種新的進(jìn)化算法（Evolu2tionaryAlgorithm-EA）.PSO算法屬于進(jìn)化算法的一種，和遺傳算法相似，它也是從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，它也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)。但是它比遺傳算法規(guī)則更為簡(jiǎn)單，它沒(méi)有遺傳算法的交叉（Crossover）和變異（Mutation）操作。它通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)

二、遺傳算法

遺傳算法是計(jì)算數(shù)學(xué)中用于解決最佳化的，是進(jìn)化算法的一種。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來(lái)的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。遺傳算法通常實(shí)現(xiàn)方式為一種模擬。對(duì)于一個(gè)最優(yōu)化問(wèn)題，一定數(shù)量的候選解（稱(chēng)為個(gè)體）的抽象表示（稱(chēng)為染色體）的種群向更好的解進(jìn)化。傳統(tǒng)上，解用表示（即0和1的串），但也可以用其他表示方法。進(jìn)化從完全隨機(jī)個(gè)體的種群開(kāi)始，之后一代一代發(fā)生。在每一代中，整個(gè)種群的適應(yīng)度被評(píng)價(jià)，從當(dāng)前種群中隨機(jī)地選擇多個(gè)個(gè)體（基于它們的適應(yīng)度），通過(guò)自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當(dāng)前種群。

?

主要特點(diǎn)

遺傳算法是解決搜索問(wèn)題的一種通用算法，對(duì)于各種通用問(wèn)題都可以使用。的共同特征為：

① 首先組成一組候選解

② 依據(jù)某些適應(yīng)性條件測(cè)算這些候選解的適應(yīng)度

③ 根據(jù)適應(yīng)度保留某些候選解，放棄其他候選解

④ 對(duì)保留的候選解進(jìn)行某些操作，生成新的候選解。

在遺傳算法中，上述幾個(gè)特征以一種特殊的方式組合在一起：基于染色體群的并行搜索，帶有猜測(cè)性質(zhì)的選擇操作、交換操作和突變操作。這種特殊的組合方式將遺傳算法與其它搜索算法區(qū)別開(kāi)來(lái)。

遺傳算法還具有以下幾方面的特點(diǎn)：

（1）遺傳算法從問(wèn)題解的串集開(kāi)始搜索，而不是從單個(gè)解開(kāi)始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開(kāi)始搜索，覆蓋面大，利于全局擇優(yōu)。

（2）遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。

（3）遺傳算法基本上不用搜索空間的知識(shí)或其他輔助信息，而僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。

（4）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)他的搜索方向。

（5）具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過(guò)程獲得的信息自行組織搜索時(shí)，適應(yīng)度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)的基因結(jié)構(gòu)。

三、貪婪算法

概念：貪婪算法是一種不追求最優(yōu)解，只希望得到較為滿(mǎn)意解的方法。

貪婪算法一般可以快速得到滿(mǎn)意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪算法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況。例如平時(shí)購(gòu)物找錢(qián)時(shí)，為使找回的零錢(qián)的硬幣數(shù)最少，不考慮找零錢(qián)的所有各種發(fā)表方案，而是從最大面值的幣種開(kāi)始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。這就是在使用貪婪算法。這種方法在這里總是最優(yōu)，是因?yàn)殂y行對(duì)其發(fā)行的硬幣種類(lèi)和硬幣面值的巧妙安排。如只有面值分別為1、5和11單位的硬幣，而希望找回總額為15單位的硬幣。按貪婪算法，應(yīng)找1個(gè)11單位面值的硬幣和4個(gè)1單位面值的硬幣，共找回5個(gè)硬幣。但最優(yōu)的解應(yīng)是3個(gè)5單位面值的硬幣。

?

四、蟻群算法

蟻群算法（ant colony optimization， ACO），又稱(chēng)螞蟻算法，是一種用來(lái)在圖中尋找優(yōu)化路徑的機(jī)率型技術(shù)。它由Marco Dorigo于1992年在他的博士論文中引入，其靈感來(lái)源于螞蟻在尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為。

自然界的種群相當(dāng)廣泛，但大部分都有以下的能力： 螞蟻們總能找到食物源和螞蟻窩之間的最短路徑。 一旦這條最短路徑被發(fā)現(xiàn)， 螞蟻們就能在這條路上排成一行， 在食物源和螞蟻窩之間搬運(yùn)食物。 螞蟻們是怎么做到的呢？

我們知道，2點(diǎn)間直線(xiàn)距離最短。 但螞蟻們顯然不具備這樣的視力和智慧。 它們無(wú)法從遠(yuǎn)處看到食物源， 也無(wú)法計(jì)劃一個(gè)合適的路徑來(lái)搬運(yùn)食物。 螞蟻們采用的方法是全體在老窩的周?chē)鷧^(qū)域進(jìn)行地毯式搜索。而他們之間的是通過(guò)分泌化學(xué)物質(zhì)在爬過(guò)的路徑上，這種化學(xué)物質(zhì)叫（Pheromone）。

剛開(kāi)始離開(kāi)窩的時(shí)候， 螞蟻們有兩條路徑選擇： R1和R2. 這兩者機(jī)會(huì)相當(dāng)。 螞蟻們?cè)谂肋^(guò)R1和R2的時(shí)候都留下了信息素。 但是， 由于R2的距離短， 所需要的時(shí)間就少， 而信息素會(huì)揮發(fā)， 所以螞蟻們留在R2上的信息素濃度就高。 于是，越來(lái)越多的螞蟻選擇R2作為最佳路徑， 即使它們是從R1來(lái)到食物源，也將選擇R2返回螞蟻窩。 而從老巢里出發(fā)的螞蟻們也越來(lái)越傾向于R2. 在這樣的趨勢(shì)下， R1漸漸變的無(wú)人問(wèn)津了

根據(jù)螞蟻們選擇路徑的方法而得到的啟發(fā)， Dr. Dorigo在1991年發(fā)表了（Ant algorithm）。 十多年來(lái)， 螞蟻算法，以及各種改進(jìn)過(guò)的螞蟻算法，被廣泛的應(yīng)用在實(shí)際生活的各個(gè)方面。 在應(yīng)用中，它可以作為網(wǎng)絡(luò)路由控制的工具。 在交通控制中， 它也成功解決了車(chē)輛調(diào)度問(wèn)題。在圖表制作中， 它被用來(lái)解決顏色填充問(wèn)題。 此外， 它還可以被用來(lái)設(shè)計(jì)大規(guī)模的時(shí)刻表。 而問(wèn)題，既在多個(gè)不同地點(diǎn)間往返的最佳路徑選擇問(wèn)題， 應(yīng)該算是螞蟻算法最重要的用途了