人工智能技術(shù)篇計(jì)算智能第六章本章導(dǎo)讀在計(jì)算機(jī)科學(xué)領(lǐng)域，人們模擬自然界生物的進(jìn)化規(guī)律設(shè)計(jì)了多種求解復(fù)雜問題的算法，如遺傳算法、蟻群算法、粒子群算法、人工神經(jīng)網(wǎng)絡(luò)、免疫算法等，這些算法統(tǒng)稱為計(jì)算智能。目前，計(jì)算智能已廣泛應(yīng)用于組合優(yōu)化、機(jī)器學(xué)習(xí)、智能控制、模式識(shí)別等領(lǐng)域?？梢姡?jì)算智能的研究是科學(xué)技術(shù)發(fā)展的重要方向。本章從計(jì)算智能的概念入手，先介紹計(jì)算智能的分類，然后詳細(xì)介紹進(jìn)化計(jì)算中的遺傳算法和群體智能中的蟻群算法。學(xué)習(xí)目標(biāo)熟悉計(jì)算智能的概念及分類。理解并掌握遺傳算法的基本思想和算法流程。理解并掌握蟻群算法的基本原理和算法流程。目錄

4計(jì)算智能概述進(jìn)化計(jì)算群體智能010203計(jì)算智能概述01計(jì)算智能putationalintelligence，CI）是人們受自然規(guī)律和生物智能機(jī)制的啟迪，根據(jù)其原理模仿設(shè)計(jì)的一組算法，用于解決復(fù)雜的現(xiàn)實(shí)世界問題。目前，計(jì)算智能還沒有統(tǒng)一的定義，下面列舉部分學(xué)者對(duì)計(jì)算智能的不同描述。（1）計(jì)算智能主要是借鑒仿生學(xué)的思想，基于人們對(duì)生物體智能機(jī)制和自然規(guī)律的認(rèn)識(shí)，采用數(shù)值計(jì)算的方法去模擬和實(shí)現(xiàn)人類智能、生物智能和自然規(guī)律。（2）計(jì)算智能是依靠生產(chǎn)者提供的數(shù)值數(shù)據(jù)進(jìn)行加工處理，而不是依賴于知識(shí)。什么是計(jì)算智能6.1.1（3）計(jì)算智能是一種智力方式的低層認(rèn)知，只處理數(shù)值數(shù)據(jù)，而人工智能是一種智力方式的中級(jí)認(rèn)知，可以處理符號(hào)形式的知識(shí)。（4）如果一個(gè)系統(tǒng)僅處理底層的數(shù)值數(shù)據(jù)，含有的模式識(shí)別部分，沒有使用人工智能意義上的知識(shí)，且具有計(jì)算適應(yīng)性、計(jì)算容錯(cuò)性、接近人的計(jì)算速度和近乎人的誤差率這4個(gè)特性，則該系統(tǒng)是智能計(jì)算系統(tǒng)。（5）計(jì)算智能是一種以模型（包括數(shù)字模型和計(jì)算模型）為基礎(chǔ)，以分布和并行計(jì)算為特征的自然智能模擬方法。計(jì)算智能的研究與發(fā)展反映了當(dāng)代科學(xué)技術(shù)多學(xué)科交叉融合發(fā)展的重要趨勢。

根據(jù)算法設(shè)計(jì)依據(jù)的原理不同，可將計(jì)算智能分為進(jìn)化計(jì)算、群體智能、神經(jīng)計(jì)算、模糊計(jì)算、免疫計(jì)算和人工生命等，它們的簡介如表所示。計(jì)算智能分類6.1.2類別簡介進(jìn)化計(jì)算指受生物界的自然遺傳規(guī)律和進(jìn)化機(jī)制的啟發(fā)而設(shè)計(jì)的算法，常見的進(jìn)化計(jì)算有遺傳算法、遺傳規(guī)劃等群體智能指受動(dòng)物群體的智能行為啟發(fā)而設(shè)計(jì)的算法，常見的群體智能有蟻群算法、粒子群算法、蜂群算法等神經(jīng)計(jì)算用于研究人工神經(jīng)網(wǎng)絡(luò)建模和信息處理。其中，人工神經(jīng)網(wǎng)絡(luò)是指由大量的處理單元（神經(jīng)元）互相連接而形成的復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)，是對(duì)人腦組織結(jié)構(gòu)和運(yùn)行機(jī)制的某種抽象、簡化和模擬。常用的網(wǎng)絡(luò)有前向網(wǎng)絡(luò)、反饋網(wǎng)絡(luò)等類別簡介模糊計(jì)算以模糊集理論為基礎(chǔ)，模擬人腦非精確、非線性的信息處理能力，通常將模糊推理、模糊邏輯、模糊系統(tǒng)等統(tǒng)稱為模糊計(jì)算免疫計(jì)算將免疫學(xué)中的免疫機(jī)理和模型廣泛引入到計(jì)算機(jī)智能、網(wǎng)絡(luò)科學(xué)、計(jì)算機(jī)控制與安全等研究與工程中，常見的免疫算法有克隆選擇算法、免疫遺傳算法等人工生命通過人工模擬生命系統(tǒng)，建造具有自然生命現(xiàn)象和特征的人造系統(tǒng)。目前，比較成功的研究和應(yīng)用有人工腦、細(xì)胞自動(dòng)機(jī)、人工核苷酸等計(jì)算智能分類進(jìn)化計(jì)算02生物群體的生存過程普遍遵循達(dá)爾文的進(jìn)化準(zhǔn)則，即物競天擇、適者生存。生物通過個(gè)體間的婚配、交叉、變異和競爭來適應(yīng)大自然的環(huán)境，如圖所示。進(jìn)化計(jì)算又稱演化計(jì)算，是一類模擬生物進(jìn)化機(jī)制設(shè)計(jì)的成熟的具有高魯棒性和廣泛性的全局優(yōu)化方法，具有自組織、自適應(yīng)、自學(xué)習(xí)的特性，能夠不受問題性質(zhì)的限制，有效地處理傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜問題。什么是進(jìn)化計(jì)算6.2.1生物進(jìn)化過程遺傳算法（geneticalgorithm，GA）是模仿生物遺傳學(xué)和自然選擇機(jī)理而設(shè)計(jì)的計(jì)算模型，是人工構(gòu)造的一種搜索最優(yōu)解的方法。它常用于處理傳統(tǒng)方法難以解決的復(fù)雜和非線性優(yōu)化問題。遺傳算法涉及的基本術(shù)語如表所示。遺傳算法的基本術(shù)語6.2.2術(shù)語說明問題的解空間遺傳算法主要用于尋找問題的最優(yōu)解或次優(yōu)解，通常問題的最優(yōu)解或次優(yōu)解是包含在一個(gè)龐大的有限可能的解集合中，將該解集合稱為問題的解空間種群用遺傳算法求解問題時(shí)，從初始給定的多個(gè)解開始搜索，該初始給定的多個(gè)解的集合稱為一個(gè)種群，種群是問題解空間的一個(gè)子集個(gè)體種群中的每個(gè)元素稱為個(gè)體。個(gè)體是一個(gè)數(shù)據(jù)結(jié)構(gòu)，用來描述基本的遺傳結(jié)構(gòu)染色體對(duì)個(gè)體進(jìn)行編碼后所得到的編碼串稱為染色體基因染色體中的每一位編碼稱為基因基因組染色體上由若干個(gè)基因構(gòu)成的一個(gè)有效信息段稱為基因組適應(yīng)度函數(shù)用來對(duì)種群中個(gè)體的環(huán)境適應(yīng)性進(jìn)行度量的函數(shù)稱為適應(yīng)度函數(shù)，其函數(shù)值是遺傳算法實(shí)現(xiàn)優(yōu)勝劣汰的主要依據(jù)。在優(yōu)化問題中，適應(yīng)度函數(shù)是一個(gè)估計(jì)函數(shù)遺傳操作作用于種群并產(chǎn)生新的種群的操作稱為遺傳操作，標(biāo)準(zhǔn)的遺傳操作包括3種基本形式，即選擇、交叉和變異基本術(shù)語遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇適應(yīng)度高的個(gè)體，并通過交叉、變異來產(chǎn)生新一代種群，新的種群既繼承了上一代的基因，又優(yōu)于上一代。如此迭代進(jìn)化，群體中個(gè)體的適應(yīng)度不斷提高，直到滿足目標(biāo)條件為止。遺傳算法的基本思想6.2.3

遺傳算法流程可用左圖描述，其中主要包含了5個(gè)基本要素，即參數(shù)編碼、群體設(shè)定、適應(yīng)度函數(shù)、遺傳操作（選擇、交叉和變異）和控制參數(shù)。（1）確定實(shí)際問題的參數(shù)集

在實(shí)際的應(yīng)用中，遺傳算法是從問題的有限解中尋找最優(yōu)解或次優(yōu)解，因此，構(gòu)造算法之前首先要確定包含問題最優(yōu)解或次優(yōu)解的解空間，然后確定問題的參數(shù)集。遺傳算法流程6.2.4遺傳算法流程（2）參數(shù)編碼，采用某一編碼方法將問題參數(shù)表示成遺傳空間的個(gè)體。（3）設(shè)定初始種群，即使用隨機(jī)方法或其他方法，產(chǎn)生一個(gè)個(gè)體數(shù)量為N的初始種群。（4）根據(jù)適應(yīng)度函數(shù)f計(jì)算種群中個(gè)體的適應(yīng)度。（5）判斷個(gè)體是否滿足終止條件，若滿足，則將個(gè)體轉(zhuǎn)化為參數(shù)（即解碼），輸出最優(yōu)解，算法終止。若不滿足，則轉(zhuǎn)向（6）。（6）根據(jù)選擇概率Pr和選擇方法選擇個(gè)體。其中，適應(yīng)度高的個(gè)體更容中，適應(yīng)度低的個(gè)體汰。（7）按照一定的交叉概率Pc和交叉方法進(jìn)行交叉，產(chǎn)生新的個(gè)體，得到新的種群。（8）按照一定的變異概率Pm和變異方法，使個(gè)體染色體的一個(gè)基因發(fā)生變異，產(chǎn)生新的染色體，得到新的種群，轉(zhuǎn)向（4）。高手點(diǎn)撥遺傳算法不能直接處理問題空間的參數(shù)，因此，須通過編碼將要求解的問題表示成遺傳空間的染色體或個(gè)體。常用的編碼方法有二進(jìn)制編碼、格雷碼編碼、實(shí)數(shù)編碼和排列編碼等。同時(shí)，還要根據(jù)編碼方法確定解碼的方法。用遺傳算法求解問題時(shí)，必須建立目標(biāo)問題的實(shí)際表示與遺傳算法染色體結(jié)構(gòu)之間的對(duì)應(yīng)關(guān)系，以便于編碼與解碼。高手點(diǎn)撥遺傳算法的操作對(duì)象是種群，所以必須為遺傳算法設(shè)定一個(gè)初始種群。設(shè)定種群時(shí)主要考慮兩方面內(nèi)容，一是初始種群的產(chǎn)生，二是種群規(guī)模的確定。遺傳算法初始種群中的個(gè)體可以采用隨機(jī)方式產(chǎn)生，也可以采用某種策略設(shè)定。例如，從問題最優(yōu)解所在的范圍內(nèi)設(shè)定初始種群；先隨機(jī)產(chǎn)生一些個(gè)體，然后從中挑選最好的個(gè)體加入初始種群中。種群規(guī)模是指種群中個(gè)體的數(shù)量N，種群規(guī)模一般取值為20～100。遺傳算法是一種基于空間搜索的算法，它通過選擇、交叉、變異等操作模擬生物進(jìn)化過程尋找所求問題的答案，可見，遺傳算法的求解過程是優(yōu)化的過程。遺傳算法的特點(diǎn)有以下幾點(diǎn)。（1）遺傳算法從多個(gè)問題解開始搜索，而不是從單個(gè)解開始

這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的，因此容局部最優(yōu)解。遺傳算法從多個(gè)問題解開始搜索，覆蓋面大，利于全局擇優(yōu)。遺傳算法的主要特點(diǎn)6.2.5（2）遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身現(xiàn)并行化。（3）遺傳算法基本上不用搜索空間的知識(shí)或其他輔助信息，而僅用適應(yīng)度來評(píng)估個(gè)體，并在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大幅度擴(kuò)大。（4）遺傳算法是采用概率的變遷規(guī)則來指導(dǎo)它的搜索方向，而不是采用確定性規(guī)則。遺傳算法是解決搜索問題的一種通用算法，它不僅在函數(shù)優(yōu)化、組合優(yōu)化、車間調(diào)度等傳統(tǒng)領(lǐng)域有著較好的應(yīng)用，還在人工智能和大數(shù)據(jù)計(jì)算等領(lǐng)域得到了廣泛應(yīng)用，其具體的應(yīng)用領(lǐng)域舉例如表所示。遺傳算法的應(yīng)用6.2.6遺傳算法的應(yīng)用領(lǐng)域舉例應(yīng)用領(lǐng)域簡介機(jī)器人技術(shù)機(jī)器人技術(shù)用于創(chuàng)造具有特定用途的機(jī)器人，且不同用途的機(jī)器人設(shè)計(jì)也不同。通過遺傳算法進(jìn)行編程，可以針對(duì)機(jī)器人的特定用途，搜索出一系列的機(jī)器人設(shè)計(jì)方案和組件，并為計(jì)算機(jī)計(jì)算模擬出多種可能操作。隨著遺傳算法的改進(jìn)，未來人們將看到更多具有特定功能的機(jī)器人，如掃地機(jī)器人、看家機(jī)器人、管理機(jī)器人等線路規(guī)劃航空路線規(guī)劃、旅行路線規(guī)劃、最短路線規(guī)劃，以及如何避免交通阻塞等都是人們經(jīng)常面臨的問題。遺傳算法可以通過程序在后臺(tái)對(duì)所有問題進(jìn)行建模，并將最佳線路規(guī)劃反饋給人們電腦游戲使用遺傳算法進(jìn)行游戲編程，程序可以吸收人類決策，促使游戲智能化，提高人類體驗(yàn)感應(yīng)用領(lǐng)域簡介汽車設(shè)計(jì)使用遺傳算法可以為賽車和常規(guī)運(yùn)輸工具（包括航空）設(shè)計(jì)復(fù)合材料和符合空氣動(dòng)力學(xué)的形狀，可以搭配出最佳材料和最佳工程技術(shù)的組合，可以為車輛提供更快、更某省市油和更安全的保證。使用遺傳算法進(jìn)行計(jì)算機(jī)建模，可以隨意返回多種設(shè)計(jì)方案供設(shè)計(jì)師挑選，可以提高汽車設(shè)計(jì)效率工程設(shè)計(jì)遺傳算法可以充分利用各種材料的特點(diǎn)來優(yōu)化建筑物、工廠、機(jī)器等架構(gòu)，如優(yōu)化機(jī)器人抓臂、衛(wèi)星吊桿、建筑桁架、飛輪及渦輪機(jī)等加密解密在安全方面，遺傳算法既可用于加密敏感數(shù)據(jù)，也可用于解密這些數(shù)據(jù)投資策略現(xiàn)在人們?cè)絹碓揭蕾囉谌斯ぶ悄軄磉M(jìn)行投資，利用遺傳算法輔助的投資策略模型，是指導(dǎo)或者說影響人們財(cái)富匯聚的重要因素

函數(shù)求解案例：函數(shù)求解6.2.7群體智能03群體智能是一種受自然界生物群體的智能現(xiàn)象啟發(fā)而提出的智能優(yōu)化方法，是計(jì)算智能領(lǐng)域的關(guān)鍵技術(shù)之一。群體智能的概念來自對(duì)螞蟻、蜂蜜等自然界中群居生物群體行為的觀察和模擬。

例如，通過觀察螞蟻尋找路徑的行為提出蟻群算法，通過觀察蜜蜂繁殖、采蜜等行為提出蜂群算法，通過觀察鳥群的捕食行為提出粒子群算法，等等。常見的群體智能算法還有很多，如左圖所示。群體智能什么是群體智能6.3.1

群體智能是在模擬自然界群體生存現(xiàn)象的基礎(chǔ)上，運(yùn)用一定的數(shù)學(xué)手段和計(jì)算工具，設(shè)計(jì)相應(yīng)的算法模型，為解決系統(tǒng)中的復(fù)雜行為提供了新的思路。它主要有以下4個(gè)特點(diǎn)。（1）控制是分布式的，不存在控制中心。它能夠適應(yīng)當(dāng)前網(wǎng)絡(luò)環(huán)境下的工作狀態(tài)，并且具有較強(qiáng)的魯棒性，同時(shí)不會(huì)由于某一個(gè)或幾個(gè)個(gè)體出現(xiàn)故障而影響整個(gè)問題的求解。（2）擴(kuò)充性較好。群體中個(gè)體通過改變環(huán)境實(shí)現(xiàn)相互通信，隨著個(gè)體數(shù)目的增加，這種非直接通信的方式緩解了通信開銷的增幅。因此，群體智能具有較好的擴(kuò)充性。（3）具有簡單性。群體中每個(gè)個(gè)體的能力或遵循的行為規(guī)則非常簡單，因而群體智能的實(shí)現(xiàn)比較方便和簡單。（4）具有自組織性。群體表現(xiàn)出來的復(fù)雜行為是通過簡單個(gè)體的交互過程突顯出來的智能。因此，群體具有自組織性。

蟻群算法是通過模擬自然界螞蟻尋找路徑的方式而提出的一種算法，它是群體智能研究領(lǐng)域的一種主要算法。下面通過模擬自然蟻群的尋路過程來解釋蟻群算法的基本原理。6.3.2蟻群算法的基本原理1．自然螞蟻尋路過程在螞蟻尋找食物時(shí)，它們總能找到一條從食物到巢穴的最優(yōu)路徑。假設(shè)兩只螞蟻分別選擇了不同的兩條路徑，每分鐘爬0.5米且留下一個(gè)信息素，路徑ABD和ACD的距離分別是4米和8米。（1）經(jīng)過8分鐘后，螞蟻的運(yùn)動(dòng)情況及路徑上信息素的分布如圖所示。選擇路徑ABD的螞蟻到達(dá)終點(diǎn)D，并在路徑ABD上留下8個(gè)信息素；選擇路徑ACD的螞蟻剛好到達(dá)中點(diǎn)C處，并在路徑ACD上也留下8個(gè)信息素。

8分鐘時(shí)路徑信息素分布（2）經(jīng)過16分鐘后，螞蟻的運(yùn)動(dòng)情況及路徑上信息素的分布如圖所示。

選擇路徑ABD的螞蟻到達(dá)終點(diǎn)D后獲得食物并返回到起點(diǎn)A，在路徑ABD上共留下16個(gè)信息素；選擇路徑ACD的螞蟻剛好到達(dá)終點(diǎn)D后取得食物，并在路徑ACD上也留下16個(gè)信息素。

16分鐘時(shí)路徑信息素分布（3）按照信息素的指導(dǎo)，螞蟻更大概率地選擇信息素濃度高的路徑，所以出現(xiàn)的第3只螞蟻選擇路徑ABD，則該路徑上增加至2只螞蟻，而路徑ACD上仍然為1只螞蟻。再經(jīng)過16分鐘后，兩條路徑上每一處信息素分別累計(jì)為6和2，其比值為3∶1。（4）按照信息素的指導(dǎo)，出現(xiàn)的第4只螞蟻還是選擇路徑ABD，則該路徑上增加至3只螞蟻，而路徑ACD上仍然為1只螞蟻。再經(jīng)過16分鐘后，兩條路徑上每一處信息素分別累計(jì)為12和3，其比值為4∶1。綜上所述，根據(jù)信息素的指導(dǎo)，更多的螞蟻不斷地選擇路徑ABD，越來越少的螞蟻選擇路徑ACD，且隨著時(shí)間的推移，路徑ABD上信息素濃度越來越高，而路徑ACD上信息素濃度將會(huì)降低，直至完全消除。因此，最終所有的螞蟻都會(huì)選擇路徑ABD，放棄路徑ACD。2．基本原理蟻群算法的基本原理就是通過模擬自然蟻群的尋路過程實(shí)現(xiàn)的，其具體描述如下。（1）螞蟻在路徑上釋放信息素。（2）當(dāng)螞蟻遇到還沒有走過的路口時(shí)，就隨機(jī)挑選一條路前行，同時(shí)，釋放與路徑長度有關(guān)的信息素。信息素濃度與路徑長度成反比。（3）后來的螞蟻再次遇到該路口時(shí)，就更大概率地選擇信息素濃度較高的路徑。（4）最優(yōu)路徑上的信息素濃度越來越高。（5）最終蟻群找到最優(yōu)路徑。

蟻群算法中主要包含兩個(gè)過程，即狀態(tài)轉(zhuǎn)移和信息素更新。其中，涉及的參數(shù)如表所示。蟻群算法涉及的參數(shù)6.3.3蟻群算法的主要過程

知識(shí)庫一般情況下，在蟻群算法中，參數(shù)的設(shè)定需要遵循以下3條準(zhǔn)則。（1）盡可能在全局上搜索最優(yōu)解，保證解的最優(yōu)性。（2）算法盡快收某省市尋優(yōu)時(shí)間。（3）盡量反映客觀存在的規(guī)律，保證仿生算法的真實(shí)性。

遺傳算法流程6.3.4蟻群算法流程

添磚加瓦終止條件的設(shè)定需要根據(jù)問題具體分析，常見的終止條件有3種。（1）給定一個(gè)循環(huán)的最大數(shù)目N，若Nc>N，則循環(huán)終止，表明已經(jīng)有足夠的螞蟻尋找到路徑。（2）給定一個(gè)整數(shù)M，若當(dāng)前最優(yōu)解連續(xù)M次相同，則循環(huán)終止，表示算法已經(jīng)收斂，不需要再繼續(xù)執(zhí)行。（3）根據(jù)目標(biāo)值控制規(guī)則判斷是否終止循環(huán)。也就是說，給定優(yōu)化問題的一個(gè)下界和一個(gè)誤差值，當(dāng)算法得到的目標(biāo)值與下界之差小于給定的誤差值時(shí)，循環(huán)終止。蟻群算法本質(zhì)上是一種并行的算法。每只螞蟻搜索的過程彼此獨(dú)立，僅通過信息素進(jìn)行通信。蟻群算法是一種自組織的算法。算法開始的初期，單個(gè)螞蟻無序地尋找解，經(jīng)過一段時(shí)間的演化之后，通過信息素的作用，螞蟻?zhàn)园l(fā)地趨向于尋找接近最優(yōu)解的一些解，這就是一個(gè)無序到有序的過程。蟻群算法是一種基于多主體的智能算法，不是單個(gè)螞蟻搜索，而是多個(gè)螞蟻同時(shí)搜索，具有分布式的協(xié)同優(yōu)化機(jī)制。蟻群算法具有較強(qiáng)的魯棒性。蟻群算法對(duì)初始路線要求不高，而且在搜索過程中不需要進(jìn)行人工的調(diào)整。其次，蟻群算法的參數(shù)數(shù)目少，設(shè)置簡單，其應(yīng)用到其他組合優(yōu)化問題的求解中。6.3.5蟻群算法的主要特點(diǎn)目前，蟻群算法已從單純地求解組合優(yōu)化問題拓展到了網(wǎng)絡(luò)路由、線路規(guī)劃、圖像處理、數(shù)據(jù)挖掘、圖的著色問題等多個(gè)應(yīng)用領(lǐng)域，如表所示。蟻群算法的應(yīng)用領(lǐng)域舉例6.3.6蟻群算法的應(yīng)用應(yīng)用領(lǐng)域簡介網(wǎng)絡(luò)路由優(yōu)化蟻群算法可解決受限路由問題，并優(yōu)化