第6章

智能計(jì)算

有些人擔(dān)心人工智能的出現(xiàn)會(huì)令人類感到自卑，但任何有頭腦的人單是觀察花朵就應(yīng)該能感到自己的渺小。——艾倫·凱6.1進(jìn)化算法6.1.1進(jìn)化算法的概念

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

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

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

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

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

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

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

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

6.2基本遺傳算法6.2.2編碼

遺傳算法中包含了五個(gè)基本要素：

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

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

6.2.2編碼

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

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

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

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

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

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

遺傳算法中初始群體中的個(gè)體可以是隨機(jī)產(chǎn)生的，但最好采用如下策略設(shè)定：①根據(jù)問(wèn)題固有知識(shí)，設(shè)法把握最優(yōu)解所占空間在整個(gè)問(wèn)題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。②先隨機(jī)產(chǎn)生一定數(shù)目的個(gè)體，然后從中挑選最好的個(gè)體加入初始群體中。這種過(guò)程不斷迭代，直到初始群體中個(gè)體數(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.個(gè)體選擇概率分配方法

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

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

6.2.5選擇

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

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

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

2.選擇個(gè)體方法

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

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

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

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

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

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

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

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

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

一點(diǎn)交叉（Single-pointCrossover）又稱為簡(jiǎn)單交叉。

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

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

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

對(duì)交叉、變異等遺傳操作進(jìn)行適當(dāng)?shù)匦拚蛊錆M足優(yōu)化問(wèn)題的約束條件。

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

6.2.7變異

6.2.8遺傳算法的步驟

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

6.4群智能算法

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

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

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

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

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

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

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

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

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

6.4.2蟻群算法

6.4.2蟻群算法

6.4.2蟻群算法蟻群算法求解旅行商問(wèn)題

6.4.2蟻群算法蟻群算法求解旅行商問(wèn)題

6.4.2蟻群算法蟻群算法求解旅行商問(wèn)題的解：

6.5小結(jié)

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