《人工智能及其應(yīng)用》課件第6章 智能計算

第6章

智能計算

有些人擔(dān)心人工智能的出現(xiàn)會令人類感到自卑，但任何有頭腦的人單是觀察花朵就應(yīng)該能感到自己的渺小?！瑐悺P6.1進(jìn)化算法6.1.1進(jìn)化算法的概念

進(jìn)化算法（EvolutionaryAlgorithms，EA）是基于自然選擇和自然遺傳等生物進(jìn)化機制的一種搜索算法。

進(jìn)化算法是以達(dá)爾文的進(jìn)化論思想為基礎(chǔ)，通過模擬生物進(jìn)化過程與機制的求解問題的自組織、自適應(yīng)的人工智能技術(shù)，是一類借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法。6.1.2進(jìn)化算法的生物機理

生物遺傳物質(zhì)的主要載體是染色體（Chromosome），DNA是其中最主要的遺傳物質(zhì)。

染色體中基因的位置稱作基因座，而基因所取的值又叫等位基因。

基因和基因座決定了染色體的特征，也決定了生物個體（individual）的性狀。如頭發(fā)的顏色是黑色、棕色或者金黃色等。6.1.3進(jìn)化算法的設(shè)計原則（1）適用性原則該算法所能適用的問題種類，它取決于算法所需的限制與假定。優(yōu)化問題的不同，則相應(yīng)的處理方式也不同。（2）可靠性原則算法對于所設(shè)計的問題，以適當(dāng)?shù)木惹蠼馄渲写蠖鄶?shù)問題的能力。因為演化計算的結(jié)果帶有一定的隨機性和不確定性，所以，在設(shè)計算法時應(yīng)盡量經(jīng)過較大樣本的檢驗，以確認(rèn)算法是否具有較大的可靠度。（3）收斂性原則

指算法能否收斂到全局最優(yōu)。在收斂的前提下，希望算法具有較快的收斂速度。6.1.3進(jìn)化算法的設(shè)計原則（4）穩(wěn)定性原則

指算法對其控制參數(shù)及問題的數(shù)據(jù)的敏感度。在設(shè)計算法時應(yīng)盡量使得算法對一組固定的控制參數(shù)能在較廣泛的問題的數(shù)據(jù)范圍內(nèi)解題，而且對一組給定的問題數(shù)據(jù)，算法對其控制參數(shù)的微小擾動不很敏感。（5）生物類比原則

因為進(jìn)化算法的設(shè)計思想是基于生物演化過程的，所以那些在生物界被認(rèn)為是有效的方法及操作可以通過類比的方法引入到算法中，有時會帶來較好的結(jié)果。6.2基本遺傳算法

6.2基本遺傳算法6.2.2編碼

遺傳算法中包含了五個基本要素：

參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計、遺傳操作設(shè)計和控制參數(shù)設(shè)定。

由于遺傳算法不能直接處理問題空間的參數(shù)，因此，必須通過編碼將要求解的問題表示成遺傳空間的染色體或者個體。6.2.2編碼

6.2.2編碼

6.2.2編碼2.實數(shù)編碼

為克服二進(jìn)制編碼的缺點，對問題的變量是實向量的情形，可以直接采用實數(shù)編碼。

實數(shù)編碼是用若干實數(shù)表示一個個體，然后在實數(shù)空間上進(jìn)行遺傳操作。采用實數(shù)表達(dá)法不必進(jìn)行數(shù)制轉(zhuǎn)換，可直接在解的表現(xiàn)型上進(jìn)行遺傳操作。從而可引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息來增加算法的搜索能力。3.多參數(shù)級聯(lián)編碼

對于多參數(shù)優(yōu)化問題的遺傳算法，常采用多參數(shù)級聯(lián)編碼。

把每個參數(shù)先進(jìn)行二進(jìn)制編碼得到子串，再把這些子串連成一個完整的染色體。

多參數(shù)級聯(lián)編碼中的每個子串對應(yīng)各自的編碼參數(shù)，所以，可以有不同的串長度和參數(shù)的取值范圍。6.2.3群體設(shè)定1.初始種群的產(chǎn)生

遺傳算法中初始群體中的個體可以是隨機產(chǎn)生的，但最好采用如下策略設(shè)定：①根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。②先隨機產(chǎn)生一定數(shù)目的個體，然后從中挑選最好的個體加入初始群體中。這種過程不斷迭代，直到初始群體中個體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。6.2.3群體設(shè)定

6.2.4適應(yīng)度函數(shù)

6.2.4適應(yīng)度函數(shù)

6.2.4適應(yīng)度函數(shù)

6.2.5選擇

1.個體選擇概率分配方法

在遺傳算法中，哪個個體被選擇進(jìn)行交叉是按照概率進(jìn)行的。

適應(yīng)度大的個體被選擇的概率大，但不是說一定能夠被選上。同樣，適應(yīng)度小的個體被選擇的概率小，但也可能被選上。所以，首先要根據(jù)個體的適應(yīng)度確定被選擇的概率。6.2.5選擇

6.2.5選擇

1.個體選擇概率分配方法(2）排序方法

排序方法(Rank-based-Model）是計算每個個體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個體進(jìn)行排序，然后把事先設(shè)計好的概率按排序分配給個體，作為各自的選擇概率。

在排序方法中，選擇概率僅僅取決于個體在種群中的序位，不是實際的適應(yīng)度值。排在前面的個體有較多的被選擇的機會。6.2.5選擇

2.選擇個體方法

選擇操作是根據(jù)個體的選擇概率確定哪些個體被選擇進(jìn)行交叉、變異等操作，基本的選擇方法如下。（1）輪盤賭選擇

輪盤賭選擇（RouletteWheelSelection）策略在遺傳算法中使用得最多。

在輪盤賭選擇方法中先按個體的選擇概率產(chǎn)生一個輪盤，輪盤每個區(qū)的角度與個體的選擇概率成比例，然后產(chǎn)生一個隨機數(shù)，它落入轉(zhuǎn)盤的哪個區(qū)域就選擇相應(yīng)的個體交叉。6.2.5選擇(3）最佳個體保存方法

最佳個體保存方法或稱為精英選拔方法（ElitistModel）是把群體中適應(yīng)度最高的一個或者多個個體不進(jìn)行交叉而直接復(fù)制到下一代中，保證遺傳算法終止時得到的最后結(jié)果一定是歷代出現(xiàn)過的最高適應(yīng)度的個體。

使用這種方法能夠明顯提高遺傳算法的收斂速度，但可能使種群過快收斂，從而只找到局部最優(yōu)解。

保留種群個體總數(shù)的2%~5%的適應(yīng)度最高的個體，效果最為理想。在使用其他選擇方法時，一般都同時使用最佳個體保存方法，以保證不會丟失最優(yōu)個體。6.2.6交叉

當(dāng)兩個生物機體配對或者復(fù)制時，它們的染色體相互混合，產(chǎn)生一對由雙方基因組成的新的染色體。這一過程稱為交叉（Crossover）或者重組（Recombination）。

交叉得到的后代可能繼承了上代的優(yōu)良基因，其后代會比它們的父母更加優(yōu)秀，但也可能繼承了上代的不良基因，其后代則會比它們的父母差，難以生存，甚至不能再復(fù)制自己。

越能適應(yīng)環(huán)境的后代越能繼續(xù)復(fù)制自己并將其基因傳給后代。由此形成一種趨勢：每一代總是比其父母一代生存和復(fù)制得更好。6.2.6交叉1.基本的交叉算子（1）一點交叉

一點交叉（Single-pointCrossover）又稱為簡單交叉。

在個體串中隨機設(shè)定一個交叉點，實行交叉時，該點前或后的兩個個體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個新的個體。（2）二點交叉

二點交叉(Two-pointCrossover）的操作與一點交叉類似，只是設(shè)置了兩個交叉點(仍然是隨機設(shè)定），將兩個交叉點之間的碼串相互交換。

類似于二點交叉，可以采用多點交叉（Multiple-pointCrossover）。6.2.6交叉2.修正的交叉方法

對交叉、變異等遺傳操作進(jìn)行適當(dāng)?shù)匦拚?，使其滿足優(yōu)化問題的約束條件。

例如，在TSP問題中采用部分匹配交叉（PartiallyMatchedCrossover，PMX），順序交叉（OrderCrossover，OX）和循環(huán)交叉（Cyclecrossover，CX）等。這些方法對于其他一些問題也同樣適用。6.2.7變異

6.2.7變異

6.2.8遺傳算法的步驟

6.3遺傳算法的應(yīng)用

6.4群智能算法

由簡單個體組成的群落與環(huán)境以及個體之間的互動行為，稱為群體智能。受動物群體智能啟發(fā)的算法稱為群智能（SwarmIntelligence，SI）算法。

群智能算法包括：粒子群優(yōu)化算法、蟻群算法和人工免疫算法。

粒子群優(yōu)化算法起源于對簡單社會系統(tǒng)的模擬。最初設(shè)想是用粒子群優(yōu)化算法模擬鳥群覓食的過程，但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。

蟻群算法是對螞蟻群采集食物過程的模擬，已經(jīng)成功地運用在很多離散優(yōu)化問題上。6.4.1粒子群優(yōu)化算法

6.4.1粒子群優(yōu)化算法

6.4.1粒子群優(yōu)化算法

6.4.2蟻群算法1蟻群算法基本模型

蟻群優(yōu)化算法的第一個應(yīng)用是著名的旅行商問題（TSP），Dorigo等人充分利用了蟻群搜索食物的過程與旅行商問題之間的相似性通過人工模擬螞蟻搜索食物的過程。

通過個體之間的信息交流與相互協(xié)作最終找到從蟻穴到食物源的最短路徑，來求解旅行商問題。6.4.2蟻群算法

6.4.2蟻群算法

6.4.2蟻群算法

6.4.2蟻群算法蟻群算法求解旅行商問題

6.4.2蟻群算法蟻群算法求解旅行商問題

6.4.2蟻群算法蟻群算法求解旅行商問題的解：

6.5小結(jié)

遺傳算法主要借用生物進(jìn)化中“適者生存”的規(guī)律。遺傳算法的設(shè)計包括編碼、適應(yīng)度函數(shù)選擇、控制參數(shù)、交叉與變異等