人工智能

ArtificialIntelligence

6/3/20251安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院第四章計(jì)算智能4.1概述4.2神經(jīng)計(jì)算4.3模糊計(jì)算4.4粗糙集理論4.5遺傳算法4.6進(jìn)化策略4.7進(jìn)化編程4.8人工生命4.9粒群優(yōu)化4.10螞群算法4.11自然計(jì)算4.12免疫算法6/3/20252安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.1 概述信息科學(xué)與生命科學(xué)的相互交叉、相互滲透和相互促進(jìn)是現(xiàn)代科學(xué)技術(shù)發(fā)展的一個(gè)顯著特點(diǎn)。計(jì)算智能涉及神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進(jìn)化計(jì)算和人工生命等領(lǐng)域，它的研究和發(fā)展正反映了當(dāng)代科學(xué)技術(shù)多學(xué)科交叉與集成的重要發(fā)展趨勢。6/3/20253安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院什么是計(jì)算智能把神經(jīng)網(wǎng)絡(luò)（NN）歸類于傳統(tǒng)人工智能（AI）可能不大合適，而歸類于計(jì)算智能（CI）更能說明問題實(shí)質(zhì)。進(jìn)化計(jì)算、人工生命和模糊邏輯系統(tǒng)的某些課題，也都?xì)w類于計(jì)算智能。計(jì)算智能取決于制造者（manufacturers）提供的數(shù)值數(shù)據(jù)，不依賴于知識(shí)；另一方面，傳統(tǒng)人工智能應(yīng)用知識(shí)精品（knowledgetidbits）。人工神經(jīng)網(wǎng)絡(luò)應(yīng)當(dāng)稱為計(jì)算神經(jīng)網(wǎng)絡(luò)。6/3/20254安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算智能與人工智能的區(qū)別和關(guān)系A(chǔ)－Artificial，表示人工的（非生物的）；B－Biological，表示物理的＋化學(xué)的＋（？）＝生物的；C－Computational，表示數(shù)學(xué)＋計(jì)算機(jī)計(jì)算智能是一種智力方式的低層認(rèn)知，它與傳統(tǒng)人工智能的區(qū)別只是認(rèn)知層次從中層下降至低層而已。中層系統(tǒng)含有知識(shí)（精品），低層系統(tǒng)則沒有。6/3/20255安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算智能與人工智能的區(qū)別和關(guān)系輸入人類知識(shí)(＋)傳感輸入知識(shí)(＋)傳感數(shù)據(jù)計(jì)算(＋)傳感器C－數(shù)值的A－符號(hào)的B－生物的層次復(fù)雜性復(fù)雜性BNNBPRBIANNAPRAICNNCPRCI6/3/20256安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院當(dāng)一個(gè)系統(tǒng)只涉及數(shù)值（低層）數(shù)據(jù)，含有模式識(shí)別部分，不應(yīng)用人工智能意義上的知識(shí)，而且能夠呈現(xiàn)出：（1）計(jì)算適應(yīng)性；（2）計(jì)算容錯(cuò)性；（3）接近人的速度；（4）誤差率與人相近，則該系統(tǒng)就是計(jì)算智能系統(tǒng)。當(dāng)一個(gè)智能計(jì)算系統(tǒng)以非數(shù)值方式加上知識(shí)（精品）值，即成為人工智能系統(tǒng)。6/3/20257安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院1960年威德羅和霍夫率先把神經(jīng)網(wǎng)絡(luò)用于自動(dòng)控制研究。60年代末期至80年代中期，神經(jīng)網(wǎng)絡(luò)控制與整個(gè)神經(jīng)網(wǎng)絡(luò)研究一樣，處于低潮。80年代后期以來，隨著人工神經(jīng)網(wǎng)絡(luò)研究的復(fù)蘇和發(fā)展，對神經(jīng)網(wǎng)絡(luò)控制的研究也十分活躍。這方面的研究進(jìn)展主要在神經(jīng)網(wǎng)絡(luò)自適應(yīng)控制和模糊神經(jīng)網(wǎng)絡(luò)控制及其在機(jī)器人控制中的應(yīng)用上。4.2神經(jīng)計(jì)算

4.2.1人工神經(jīng)網(wǎng)絡(luò)研究的進(jìn)展6/3/20258安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院人工神經(jīng)網(wǎng)絡(luò)的特性并行分布處理非線性映射通過訓(xùn)練進(jìn)行學(xué)習(xí)適應(yīng)與集成硬件實(shí)現(xiàn)6/3/20259安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.2.2人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)-1

Wj1X1X2Wj2XnWjn···Σ

()Yi圖4.2神經(jīng)元模型6/3/202510安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

圖4.2中的神經(jīng)元單元由多個(gè)輸入xi，i=1,2,...,n和一個(gè)輸出y組成。中間狀態(tài)由輸入信號(hào)的權(quán)和表示，而輸出為 （4.1）式中，

j為神經(jīng)元單元的偏置，wji為連接權(quán)系數(shù)。n為輸入信號(hào)數(shù)目，yj為神經(jīng)元輸出，t為時(shí)間，f()為輸出變換函數(shù)，如圖4.3。

6/3/202511安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院(a)xf(x)1x00圖4.3神經(jīng)元中的某些變換（激發(fā)）函數(shù)(a)二值函數(shù) (b)S形函數(shù)(c)雙曲正切函數(shù)(c)xf(x)1-1

(b)f(x)x1

06/3/202512安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院人工神經(jīng)網(wǎng)絡(luò)的基本特性和結(jié)構(gòu)人工神經(jīng)網(wǎng)絡(luò)是具有下列特性的有向圖：對于每個(gè)節(jié)點(diǎn)i存在一個(gè)狀態(tài)變量xi；從節(jié)點(diǎn)j至節(jié)點(diǎn)i，存在一個(gè)連接權(quán)系統(tǒng)數(shù)wij；對于每個(gè)節(jié)點(diǎn)i，存在一個(gè)閾值

i；對于每個(gè)節(jié)點(diǎn)i，定義一個(gè)變換函數(shù)fi；對于最一般的情況，此函數(shù)取形式。6/3/202513安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院遞歸（反饋）網(wǎng)絡(luò):在遞歸網(wǎng)絡(luò)中，多個(gè)神經(jīng)元互連以組織一個(gè)互連神經(jīng)網(wǎng)絡(luò)，如圖4.4。圖4.4反饋網(wǎng)絡(luò)x1x2xnV1V2Vn輸入輸出x1’x2’xn’6/3/202514安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院前饋網(wǎng)絡(luò):前饋網(wǎng)絡(luò)具有遞階分層結(jié)構(gòu)，由同層神經(jīng)元間不存在互連的層級(jí)組成，如圖4.5。x1x2輸入層輸出層隱層y1ynw11w1m圖4.5前饋網(wǎng)絡(luò)反向傳播6/3/202515安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院人工神經(jīng)網(wǎng)絡(luò)的主要學(xué)習(xí)算法有師學(xué)習(xí)算法：能夠根據(jù)期望的和實(shí)際的網(wǎng)絡(luò)輸出（對應(yīng)于給定輸入）間的差來調(diào)整神經(jīng)元間連接的強(qiáng)度或權(quán)。無師學(xué)習(xí)算法：不需要知道期望輸出。強(qiáng)化學(xué)習(xí)算法：采用一個(gè)“評論員”來評價(jià)與給定輸入相對應(yīng)的神經(jīng)網(wǎng)絡(luò)輸出的優(yōu)度（質(zhì)量因數(shù)）。強(qiáng)化學(xué)習(xí)算法的一個(gè)例子是遺傳算法（GA）。6/3/202516安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院人工神經(jīng)網(wǎng)絡(luò)的典型模型6/3/202517安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院續(xù)前表：6/3/202518安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.2.5基于神經(jīng)網(wǎng)絡(luò)的知識(shí)表示與推理基于神經(jīng)網(wǎng)絡(luò)的知識(shí)表示在這里，知識(shí)并不像在產(chǎn)生式系統(tǒng)中那樣獨(dú)立地表示為每一條規(guī)則，而是將某一問題的若干知識(shí)在同一網(wǎng)絡(luò)中表示。例如，在有些神經(jīng)網(wǎng)絡(luò)系統(tǒng)中，知識(shí)是用神經(jīng)網(wǎng)絡(luò)所對應(yīng)的有向權(quán)圖的鄰接矩陣及閾值向量表示的。6/3/202519安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院基于神經(jīng)網(wǎng)絡(luò)的推理基于神經(jīng)網(wǎng)絡(luò)的推理是通過網(wǎng)絡(luò)計(jì)算實(shí)現(xiàn)的。把用戶提供的初始證據(jù)用作網(wǎng)絡(luò)的輸入，通過網(wǎng)絡(luò)計(jì)算最終得到輸出結(jié)果。一般來說，正向網(wǎng)絡(luò)推理的步驟如下：把已知數(shù)據(jù)輸入網(wǎng)絡(luò)輸入層的各個(gè)節(jié)點(diǎn)。利用特性函數(shù)分別計(jì)算網(wǎng)絡(luò)中各層的輸出。用閾值函數(shù)對輸出層的輸出進(jìn)行判定，從而得到輸出結(jié)果。6/3/202520安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院定義4.1模糊集合(FuzzySets)論域U到[0,1]區(qū)間的任一映射，即，都確定U的一個(gè)模糊子集F；稱為F的隸屬函數(shù)或隸屬度。在論域U中，可把模糊子集表示為元素u與其隸屬函數(shù)的序偶集合，記為： (4.12)4.3模糊計(jì)算

4.3.1模糊集合、模糊邏輯及其運(yùn)算6/3/202521安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院定義4.2模糊集的截集、支集和核若模糊集是論域U中所有滿足μF(u)≥λ的元素u構(gòu)成的集合，則稱該集合為模糊集F的截集。若模糊集是論域U中所有滿足μF(u)>0的元素u構(gòu)成的集合，則稱該集合為模糊集F的支集。當(dāng)u滿足μF(u)

=1，稱為核。也就是λ=1的截集。1λ核支集λ截集6/3/202522安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院定義4.3模糊集的運(yùn)算設(shè)A和B為論域U中的兩個(gè)模糊集，其隸屬函數(shù)分別為μA和μB，則對于所有u

U，存在下列運(yùn)算：A與B的并（邏輯或）記為A∪B，其隸屬函數(shù)定義為：

μA∪B(u)=μA(u)

μB(u)=max{μA(u),μB(u)} (4.15)A與B的交（邏輯與）記為A∩B，其隸屬函數(shù)定義為：

μA∩B(u)=μA(u)

μB(u)=min{μA(u),μB(u)} (4.16)A的補(bǔ)（邏輯非）記為?，其傳遞函數(shù)定義為：

μ?

(u)=1-μA(u) (4.17)6/3/202523安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院定義4.4直積（笛卡兒乘積，代數(shù)積）若A1,A2,…,An分別為論域U1,U2,…,Un中的模糊集合，則這些集合的直積是乘積空間U1,U2,…,Un中一個(gè)模糊集合，其隸屬函數(shù)為：定義4.5模糊關(guān)系若U，V是兩個(gè)非空模糊集合，則其直積U×V中的模糊子集R稱為從U到V的模糊關(guān)系，表示為： (4.19)(4.18)6/3/202524安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.3.2模糊邏輯推理模糊邏輯推理是建立在模糊邏輯基礎(chǔ)上的不確定性推理方法，是在二值邏輯三段論基礎(chǔ)上發(fā)展起來的。這種推理方法以模糊判斷為前提，動(dòng)用模糊語言規(guī)則，推導(dǎo)出一個(gè)近似的模糊判斷結(jié)論。廣義取式(肯定前提)假言推理法(GMP)推理規(guī)則可表示為： 前提1：x為A’

前提2：若x為A，則y為B 結(jié)論：y為B’6/3/202525安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院廣義拒式(否定結(jié)論)假言推理法(GMT,GeneralizedModusTollens)的推理規(guī)則可表示為： 前提1：y為B

前提2：若x為A，則y為B 結(jié)論：x為A’模糊變量的隱含函數(shù)基本上可分為三類，即模糊合取、模糊析取和模糊蘊(yùn)涵。6/3/202526安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.3.3模糊判決方法在推理得到的模糊集合中取一個(gè)相對最能代表這個(gè)模糊集合的單值的過程就稱作解模糊或模糊判決（Defuzzification）。模糊判決可以采用不同的方法：重心法、最大隸屬度方法、加權(quán)平均法、隸屬度限幅元素平均法。下面介紹各種模糊判決方法，并以“水溫適中”為例，說明不同方法的計(jì)算過程。這里假設(shè)“水溫適中”的隸屬函數(shù)為：={X:0.0/0+0.0/10+0.33/20+0.67/30+1.0/40+1.0/50+0.75/60+0.5/70+0.25/80+0.0/90+0.0/100}6/3/202527安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院重心法就是取模糊隸屬函數(shù)曲線與橫坐標(biāo)軸圍成面積的重心作為代表點(diǎn)。理論上應(yīng)該計(jì)算輸出范圍內(nèi)一系列連續(xù)點(diǎn)的重心，即 (4.40)但實(shí)際上是計(jì)算輸出范圍內(nèi)整個(gè)采樣點(diǎn)的重心，用足夠小的取樣間隔來提供所需要的精度，即：=48.21.重心法6/3/202528安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院這種方法最簡單，只要在推理結(jié)論的模糊集合中取隸屬度最大的那個(gè)元素作為輸出量即可。要求這種情況下其隸屬函數(shù)曲線一定是正規(guī)凸模糊集合（即其曲線只能是單峰曲線）。例如，對于“水溫適中”，按最大隸屬度原則，有兩個(gè)元素40和50具有最大隸屬度1.0，那就對所有取最大隸屬度的元素40和50求平均值，執(zhí)行量應(yīng)?。?.最大隸屬度法6/3/202529安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.系數(shù)加權(quán)平均法系數(shù)加權(quán)平均法的輸出執(zhí)行量由下式?jīng)Q定：

(4.41)式中，系數(shù)的選擇要根據(jù)實(shí)際情況而定，不同的系統(tǒng)就決定系統(tǒng)有不同的響應(yīng)特性。ki=μN(yùn)(xi)就是重心法。6/3/202530安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4

粗糙集理論粗糙集理論(RoughSettheory)是1982年由波蘭數(shù)學(xué)家Z.Pawlak提出的，當(dāng)時(shí)沒有引起國際計(jì)算機(jī)學(xué)界和數(shù)學(xué)界的重視，研究僅限于東歐的一些國家，直到20世紀(jì)80年代末才逐漸引起各國學(xué)者的注意。

1991年，Pawlak發(fā)表了專著《RoughSet：TheoreticalAspectsofReasoningaboutData》，奠定了粗糙集理論的基礎(chǔ)。1992年，在波蘭召開了第一屆國際粗糙集研討會(huì)，這次會(huì)議著重討論了集合近似的基本思想及其應(yīng)用，其中粗糙環(huán)境下的機(jī)器學(xué)習(xí)的基礎(chǔ)研究是這次會(huì)議的四個(gè)專題之一。1993年在加拿大召開了第二屆國際粗糙集與知識(shí)發(fā)現(xiàn)研討會(huì)，這次會(huì)議積極推動(dòng)了國際上對粗糙集應(yīng)用的研究。由于這次會(huì)議正值知識(shí)發(fā)現(xiàn)成為熱門研究話題，一些著名的知識(shí)發(fā)現(xiàn)學(xué)者參加了這次會(huì)議，并且介紹了許多應(yīng)用擴(kuò)展粗糙集理論的數(shù)據(jù)挖掘的方法與系統(tǒng)。1996年在日本東京召開了第五屆國際粗糙集研討會(huì)以及2001年在我國舉行的研討會(huì)推動(dòng)了亞洲地區(qū)和我國對粗糙集理論與應(yīng)用的研究?，F(xiàn)在，美國、加拿大、波蘭、日本都有粗糙集研究的專門機(jī)構(gòu)。6/3/202531安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4

粗糙集理論1.粗糙集理論的基本概念Rough集的基礎(chǔ)概念有一個(gè)表示文獻(xiàn)資料的對象集合U和U上的等價(jià)關(guān)系R，R是由對象的屬性(這里是指標(biāo)引詞)集Ω派生的U集合的劃分，R={X1,X2,…,Xn}。我們稱<U,R>為近似空間(Approximationspace)。對于P

R并且P≠φ，這是指P是由Ω的子集派生的，那么∩P(所有P中等價(jià)關(guān)系的交集)也是一種等價(jià)關(guān)系，在Rough集中，我們常稱∩P為P上的不可分辨關(guān)系(Indiscernibilityrelation)，記作Ind(P)。按照形狀分類4.4.1

粗糙集理論的基本概念和特點(diǎn)6/3/202532安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4

粗糙集理論按照大小分類按照顏色分類6/3/202533安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4

粗糙集理論按照“形狀”和“大小”分類按照“顏色”和“大小”分類6/3/202534安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4.1粗糙集理論的基本概念和特點(diǎn)定義4.17對于每個(gè)集合X

U和一個(gè)等價(jià)關(guān)系R，A=(U,R)稱為知識(shí)庫，定義兩個(gè)子集:

X=∪{[x]|[x]

X}={x

U|[x]

X}為X的下近似空間(Lowerapproximation)。

X=∪{[x]|[x]∩X≠φ}={x

U|[x]∩X≠φ}為X的上近似空間(Upperapproximation)

。BN(X)=

6/3/202535安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4.1粗糙集理論的基本概念和特點(diǎn)甲甲甲甲甲甲甲按照“形狀”和“大小”分類甲甲甲甲甲甲甲6/3/202536安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4.1粗糙集理論的基本概念和特點(diǎn)

6/3/202537安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4.1粗糙集理論的基本概念和特點(diǎn)

定義4.18X關(guān)于A的近似質(zhì)量，定義為:

定義4.19X關(guān)于A的粗糙性測度，定義為:

0≤ρA(X)≤1；ρA(X)=0時(shí)，X是可以確定的；ρA(X)>0時(shí)，X是可以粗糙的，ρA(X)是粗糙程度。6/3/202538安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4.1粗糙集理論的基本概念和特點(diǎn)

定義4.20設(shè)F={X1,X2,…,Xn}，XiU，則F關(guān)于近似空間A的下近似和上近似，定義為:

定義4.21F關(guān)于A的近似精度αA(X)和近似質(zhì)量γA(X)分別定義為:

6/3/202539安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.4.1粗糙集理論的基本概念和特點(diǎn)

2.粗糙集理論的特點(diǎn)不需要先驗(yàn)知識(shí)強(qiáng)大的數(shù)據(jù)分析和約簡能力：求知識(shí)的最小表達(dá)；識(shí)別數(shù)據(jù)之間的依賴關(guān)系粗糙集側(cè)重分類；模糊集側(cè)重個(gè)體的含糊性6/3/202540安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.5遺傳算法遺傳算法是模仿生物遺傳學(xué)和自然選擇機(jī)理，通過人工方式所構(gòu)造的一類優(yōu)化搜索算法，是對生物進(jìn)化過程進(jìn)行的一種數(shù)學(xué)仿真，是進(jìn)化計(jì)算的最重要的形式。遺傳算法為那些難以找到傳統(tǒng)數(shù)學(xué)模型的難題指出了一個(gè)解決方法。進(jìn)化計(jì)算和遺傳算法借鑒了生物科學(xué)中的某些知識(shí)，這也體現(xiàn)了人工智能這一交叉學(xué)科的特點(diǎn)。

6/3/202541安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.5.1遺傳算法的基本機(jī)理霍蘭德的遺傳算法通常稱為簡單遺傳算法(SGA)?，F(xiàn)以此作為討論主要對象，加上適應(yīng)的改進(jìn)，來分析遺傳算法的結(jié)構(gòu)和機(jī)理。

編碼與解碼適應(yīng)度函數(shù)

遺傳操作

6/3/202542安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.5.1遺傳算法的基本機(jī)理編碼與解碼 將問題結(jié)構(gòu)變換為位串形式編碼表示的過程叫編碼；而相反將位串形式編碼表示變換為原問題結(jié)構(gòu)的過程叫解碼或譯碼。 把位串形式編碼表示叫染色體(chromosome)，有時(shí)也叫個(gè)體。 “甲”的編碼：0100111010100011

染色體的每位稱為基因(gene)。

“甲”染色體的第5個(gè)基因取值為1。6/3/202543安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.5.1遺傳算法的基本機(jī)理適應(yīng)度函數(shù)

為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)(fitnessfunction)。

適應(yīng)度函數(shù)要有效反映每一個(gè)染色體與問題的最優(yōu)解染色體之間的差距。適應(yīng)度函數(shù)的取值大小與求解問題對象的意義有很大的關(guān)系。 TSP的目標(biāo)是路徑總長度為最短，自然地，由路徑總長度就可導(dǎo)出TSP問題的適應(yīng)度函數(shù)。 f(w1,w2,…,wn)=

6/3/202544安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.5.1遺傳算法的基本機(jī)理遺傳操作:選擇、交叉、變異1.選擇(selection)適應(yīng)度較大的個(gè)體有較大的生存機(jī)會(huì)。 賭輪選擇機(jī)制：fi/

fj

6/3/202545安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.5.1遺傳算法的基本機(jī)理遺傳操作:選擇、交叉、變異2.交叉(crossover)將兩個(gè)個(gè)體的部分編碼進(jìn)行交換。

10001110 P1 11011001 P2

10001110 10001001

11011001 110111103.變異(mutation)改變某位的值。

例如：10100110

10100110 101101106/3/202546安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.5.2遺傳算法的求解步驟1.遺傳算法的特點(diǎn)

(1)遺傳算法是對參數(shù)集合的編碼而非針對參數(shù)本身進(jìn)行進(jìn)化；(2)

遺傳算法是從問題解的編碼組(群體)開始而非從單個(gè)解開始搜索；(3)

遺傳算法利用目標(biāo)函數(shù)的適應(yīng)度這一信息而非利用導(dǎo)數(shù)或其它輔助信息來指導(dǎo)搜索；(4)

遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規(guī)則進(jìn)行隨機(jī)操作。6/3/202547安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

一般遺傳算法的主要步驟如下：(1)隨機(jī)產(chǎn)生一個(gè)由確定長度的特征字符串組成的初始群體。(2)

對該字符串群體迭代的執(zhí)行下面的①和②步，直到滿足停止標(biāo)準(zhǔn)：①計(jì)算群體中每個(gè)個(gè)體字符串的適應(yīng)值；②應(yīng)用復(fù)制、交叉和變異等遺傳算子產(chǎn)生下一代群體。(3)

把在后代中出現(xiàn)的最好的個(gè)體字符串指定為遺傳算法的執(zhí)行結(jié)果，這個(gè)結(jié)果可以表示問題的一個(gè)解。

6/3/202548安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2.遺傳算法的流程圖(圖4.18)(1)初始化群體;(2)計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值;(3)按由個(gè)體適應(yīng)度值所決定的某個(gè)規(guī)則選擇將進(jìn)入下一代的個(gè)體;(4)按概率Pc進(jìn)行交叉操作;(5)按概率Pm進(jìn)行突變操作;(6)若沒有滿足某種停止條件，則轉(zhuǎn)第(2)步，否則進(jìn)入下一步。(7)輸出群體中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。6/3/202549安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院初始化種群變異操作計(jì)算適應(yīng)度值選擇操作交叉操作輸出適應(yīng)度最優(yōu)個(gè)體終止條件開始圖4.18遺傳算法流程圖是否結(jié)束6/3/202550安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院產(chǎn)生初始群體是否滿足停止準(zhǔn)則計(jì)算每個(gè)個(gè)體的適應(yīng)值i=M?GEN:=GEN+1依概率選擇遺傳操作執(zhí)行復(fù)制選擇一個(gè)個(gè)體選擇交叉位置選擇兩個(gè)個(gè)體選擇一個(gè)個(gè)體執(zhí)行變異i:=0GEN:=0復(fù)制到新群體i:=i+1將兩個(gè)后代插入新群體插入到新群體執(zhí)行雜交指定結(jié)果結(jié)束是否是否變異復(fù)制交叉6/3/202551安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院3.遺傳算法求解舉例設(shè)，用SGA求

參數(shù)設(shè)置二進(jìn)制編碼種群大小為4染色體長為4位6/3/202552安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院遺傳算法歸納為五個(gè)基本組成部分方案表示用一個(gè)二進(jìn)制矢量表示一個(gè)染色體，由染色體來代表變量x的實(shí)數(shù)值，每個(gè)染色體的每一位二進(jìn)制數(shù)稱為遺傳因子。群體初始化隨機(jī)產(chǎn)生一定數(shù)量的染色體，每個(gè)染色體為若干位字節(jié)的二進(jìn)制數(shù)。適應(yīng)度函數(shù)適應(yīng)度函數(shù)必須有能力計(jì)算搜索空間中每個(gè)確定長度的特征字符串的適應(yīng)值。遺傳操作采用的遺傳操作分別是復(fù)制、交叉和變異。交叉相對于復(fù)制和變異的不同之處在于：交叉需要兩個(gè)父代染色體配合進(jìn)行，而復(fù)制和變異只需要一個(gè)父代染色體即可進(jìn)行。變異可根據(jù)一定的變異率來改變一個(gè)或多個(gè)遺傳基因。算法參數(shù)遺傳算法的主要參數(shù)有群體規(guī)模和算法執(zhí)行的最大代數(shù)目，次要參數(shù)有復(fù)制概率、雜交概率和變異概率等參數(shù)。6/3/202553安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.6進(jìn)化策略進(jìn)化策略(EvolutionStrategies，ES)是一類模仿自然進(jìn)化原理以求解參數(shù)優(yōu)化問題的算法。它是由雷切伯格（Rechenberg）、施韋費(fèi)爾（Schwefel）和彼得·比納特（PeterBienert）于1964年提出的，并在德國共同建立的。6/3/202554安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.6.1進(jìn)化策略的算法模型尋求與函數(shù)極值關(guān)聯(lián)的實(shí)數(shù)n維矢量x， F(x):Rn

R。隨機(jī)選擇父矢量的初始群體。父矢量xi,i=1,…,p通過算法產(chǎn)生子代矢量xi。對誤差F(xi)(i=1,…,p)排序以選擇和決定保持哪些矢量。擁有最小誤差的P矢量成為下一代的新的父代。

繼續(xù)產(chǎn)生新的試驗(yàn)數(shù)據(jù)以及選擇最小誤差矢量，找到符合條件的誤差為止。6/3/202555安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.6.2進(jìn)化策略和遺傳算法的區(qū)別進(jìn)化策略和遺傳算法有著很強(qiáng)的相似性，它們都是一類模仿自然進(jìn)化原理的算法。兩者也存在著區(qū)別，其中最基本的區(qū)別是它們的研究領(lǐng)域不同。進(jìn)化策略是一種數(shù)值優(yōu)化的方法，它采用一個(gè)具有自適應(yīng)步長和傾角的特定爬山方法。遺傳算法從廣義上說是一種自適應(yīng)搜索技術(shù)。(1)進(jìn)化策略和遺傳算法表示個(gè)體的方式不同，進(jìn)化策略在浮點(diǎn)矢量上運(yùn)行，而遺傳算法一般運(yùn)行在二進(jìn)制矢量上。GA是對變量的編碼串操作,而ES是對變量本身操作。(2)進(jìn)化策略和遺傳算法的選擇過程不同。進(jìn)化策略優(yōu)等個(gè)體機(jī)會(huì)均等(3)進(jìn)化策略和遺傳算法的復(fù)制參數(shù)不同，遺傳算法的復(fù)制參數(shù)(交叉和變異的可能性)在進(jìn)化過程中保持恒定，而進(jìn)化策略時(shí)時(shí)改變它們。6/3/202556安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.7進(jìn)化編程進(jìn)化編程(EvolutionaryProgramming，EP)，又稱為進(jìn)化規(guī)劃（EvolutionaryPlanning），是由福格爾（Fogel）在1962年提出的一種模仿人類智能的方法。進(jìn)化編程根據(jù)正確預(yù)測的符號(hào)數(shù)來度量適應(yīng)值。通過變異，為父代群體中的每個(gè)機(jī)器狀態(tài)產(chǎn)生一個(gè)子代。父代和子代中最好的部分被選擇生存下來。它的提出是受自然生物進(jìn)化機(jī)制的啟發(fā)。6/3/202557安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.7.1進(jìn)化編程的機(jī)理與表示進(jìn)化編程的過程，可理解為從所有可能的計(jì)算機(jī)程序形成的空間中，搜索具有高的適應(yīng)度的計(jì)算機(jī)程序個(gè)體。進(jìn)化編程設(shè)計(jì)強(qiáng)調(diào)群體行為的變化。進(jìn)化編程系統(tǒng)的表示自然地面向任務(wù)級(jí)。一旦選定一種適應(yīng)性表示，就可以定義依賴于該表示的變異操作，在具體的父輩行為上創(chuàng)建后代。

6/3/202558安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.7.2進(jìn)化編程的步驟進(jìn)化編程分為三個(gè)步驟：產(chǎn)生出初始群體。迭代完成下述子步驟，直至滿足選種標(biāo)準(zhǔn)為止：執(zhí)行群體中的每個(gè)程序。應(yīng)用變異等操作創(chuàng)造新程序群體。在后代中適應(yīng)值最高的計(jì)算機(jī)程序個(gè)體被指定為進(jìn)化編程的結(jié)果。6/3/202559安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院變異和創(chuàng)造子代評估已存在的FSM用最好的狀態(tài)機(jī)預(yù)測和添加符號(hào)選擇父代初始化觀測順序是否是否預(yù)測初始化群體圖5.6進(jìn)化編程的基本過程有限狀態(tài)機(jī)FiniteStateMachineFMS6/3/202560安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.8人工生命自然界是生命之源。自然生命千千萬萬，千姿百態(tài)，千差萬別，巧奪天工，奇妙無窮。人工生命（ArtificialLife，AL）試圖通過人工方法建造具有自然生命特征的人造系統(tǒng)。人工生命是生命科學(xué)、信息科學(xué)和系統(tǒng)科學(xué)等學(xué)科交叉研究的產(chǎn)物，其研究成果必將促進(jìn)人工智能的發(fā)展。

6/3/202561安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.8.1

人工生命研究的起源和發(fā)展

人類長期以來一直力圖用科學(xué)技術(shù)方法模擬自然界，包括人腦本身。1943年麥卡絡(luò)奇和皮茨提出了M－P神經(jīng)學(xué)網(wǎng)絡(luò)模型。人工生命的許多早期研究工作也源于人工智能。20世紀(jì)70年代以來，康拉德（Conrad）等提出不斷完善的“人工世界”模型。80年代，人工神經(jīng)網(wǎng)絡(luò)再度興起促進(jìn)人工生命的發(fā)展。正式提出人工生命的概念，建立起人工生命新學(xué)科。

90年代，迅速發(fā)展6/3/202562安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.8.2人工生命的定義和研究意義人工生命是一項(xiàng)抽象地提取控制生物現(xiàn)象的基本動(dòng)態(tài)原理，并且通過物理媒介（如計(jì)算機(jī)）來模擬生命系統(tǒng)動(dòng)態(tài)發(fā)展過程的研究工作。通俗地講，人工生命即人造的生命，非自然的生命。然而，要對人工生命做出嚴(yán)格的定義，卻需要對問題進(jìn)行深入研究。6/3/202563安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院人工生命系統(tǒng)

1987年蘭德提出的人工生命定義為：“人工生命是研究能夠演示出自然生命系統(tǒng)特征行為的人造系統(tǒng)”。通過計(jì)算機(jī)或其它機(jī)器對類似生命的行為進(jìn)行綜合研究，以便對傳統(tǒng)生物科學(xué)起互補(bǔ)作用。蘭德在計(jì)算機(jī)上演示了他們研制的具有生命特征的軟件系統(tǒng)，并把這類具有生命現(xiàn)象和特征的人造系統(tǒng)稱為人工生命系統(tǒng)。6/3/202564安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院自然生命的共同特征和現(xiàn)象自繁殖、自進(jìn)化、自尋優(yōu)自成長、自學(xué)習(xí)、自組織自穩(wěn)定、自適應(yīng)、自協(xié)調(diào)物質(zhì)構(gòu)造能量轉(zhuǎn)換信息處理6/3/202565安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院研究人工生命的意義

人工生命是自然生命的模擬、延伸與擴(kuò)展，其研究開發(fā)有重大的科學(xué)意義和廣泛的應(yīng)用價(jià)值。開發(fā)基于人工生命的工程技術(shù)新方法、新系統(tǒng)、新產(chǎn)品

為自然生命的研究提供新模型、新工具、新環(huán)境

延伸人類壽命、減緩衰老、防治疾病擴(kuò)展自然生命，人工進(jìn)化、優(yōu)生優(yōu)育

促進(jìn)生命、信息、系統(tǒng)科學(xué)的交叉與發(fā)展6/3/202566安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.8.3人工生命的研究內(nèi)容和方法

1.人工生命的研究內(nèi)容人工生命的研究內(nèi)容大致可分為兩類：(1)構(gòu)成生物體的內(nèi)部系統(tǒng)，包括腦、神經(jīng)系統(tǒng)、內(nèi)分泌系統(tǒng)、免疫系統(tǒng)、遺傳系統(tǒng)、酶系統(tǒng)、代謝系統(tǒng)等。(2)在生物體及其群體的外部系統(tǒng)，包括環(huán)境適應(yīng)系統(tǒng)和遺傳進(jìn)化系統(tǒng)等。6/3/202567安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院人工生命的科學(xué)框架生命現(xiàn)象仿生系統(tǒng)生命現(xiàn)象的建模與仿真

進(jìn)化動(dòng)力學(xué)

人工生命的計(jì)算理論和工具

進(jìn)化機(jī)器人

進(jìn)化和學(xué)習(xí)等的結(jié)合

人工生命的應(yīng)用,機(jī)器人6/3/202568安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院2.人工生命的研究方法（1）信息模型法根據(jù)內(nèi)部和外部系統(tǒng)所表現(xiàn)的生命行為來建造信息模型。（2）工作原理法生命行為所顯示的自律分?jǐn)?shù)和非線性行為，其工作原理是混沌和分形，以此為基礎(chǔ)研究人工生命的機(jī)理。6/3/202569安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院人工生命的研究技術(shù)途徑

(1)工程技術(shù)途徑利用計(jì)算機(jī)、自動(dòng)化、微電子、精密機(jī)械、光電通信、人工智能、神經(jīng)網(wǎng)絡(luò)等有關(guān)工程技術(shù)方法和途徑，研究開發(fā)、設(shè)計(jì)制造人工生命。通過計(jì)算機(jī)屏幕，以三維動(dòng)畫，虛擬現(xiàn)實(shí)的軟件方法或采用光機(jī)電一體化的硬件裝置來演示和體現(xiàn)人工生命。

6/3/202570安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院(2)生物科學(xué)途徑利用生物科學(xué)方法和技術(shù)，通過人工合成、基因控制，無性繁殖過程，培育生成人工生命。由于倫理學(xué)、社會(huì)學(xué)、人類學(xué)等方面的問題，通過生物科學(xué)途徑生成的人工生命，如克隆人引起了不少爭論。需要研究和制訂相應(yīng)的社會(huì)監(jiān)督、國家法律和國際公約。6/3/202571安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.8.4人工生命的實(shí)例人工腦波蘭人工智能和心理學(xué)教授安奇·布勒（AndrzejBuller）及一些日本學(xué)者在日本現(xiàn)代通訊研究所進(jìn)化系統(tǒng)研究室對人工腦的研究，已取得重要進(jìn)展。計(jì)算機(jī)病毒計(jì)算機(jī)進(jìn)程細(xì)胞自動(dòng)機(jī)人工核苷酸6/3/202572安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.9粒群優(yōu)化

4.9.1群智能和粒群優(yōu)化概述1.群智能(swarmintelligence)概念群智能中的群體指的是“一組相互之間可以進(jìn)行直接通信或者間接通信(通過改變局部環(huán)境)的Agent，這組Agent能夠合作進(jìn)行分布式的問題求解”，而群智能則是指“無智能的Agent通過合作表現(xiàn)出智能行為的特性”。群智能在沒有集中控制且不提供全局模型的前提下，為尋找復(fù)雜的分布式問題求解方案提供了基礎(chǔ)。6/3/202573安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.9粒群優(yōu)化

4.9.1群智能和粒群優(yōu)化概述2.粒群優(yōu)化(particleswarmoptimization)概念群體優(yōu)化算法，微粒群算法也是起源于對簡單社會(huì)系統(tǒng)的模擬,最初是模擬鳥群覓食的過程,但后來發(fā)現(xiàn)它是一種很好的優(yōu)化工具。微粒群算法是起源于對簡單社會(huì)系統(tǒng)的模擬,現(xiàn)在其應(yīng)用領(lǐng)域已擴(kuò)展到多目標(biāo)優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識(shí)別、電信管理、生物系統(tǒng)建模、流程規(guī)劃、信號(hào)處理、機(jī)器人控制、決策支持以及仿真和系統(tǒng)辯識(shí)等方面,群智能理論和方法為解決這類應(yīng)用問題提供了新的途徑。6/3/202574安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.9粒群優(yōu)化

4.9.1群智能和粒群優(yōu)化概述2.粒群優(yōu)化與進(jìn)化計(jì)算的比較

相似：優(yōu)化算法；模擬自然種群適應(yīng)性；搜索空間。

區(qū)別：粒群優(yōu)化有存儲(chǔ)器；粒子是學(xué)習(xí)不是進(jìn)化；粒子是社會(huì)交互的整體作用。6/3/202575安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.9粒群優(yōu)化

4.9.2粒群優(yōu)化算法

xi(t)=xi(t-1)+vi(t)

xi(t)表示t時(shí)刻Pi粒子在超空間的位置。個(gè)體最佳算法初始化粒群P(t)，t=0；Pi

P(t)；xi(t)為隨機(jī)由每個(gè)粒子的位置xi(t)評價(jià)性能F如果F(xi(t))<pbesti，那么pbesti=F(xi(t))；xpbesti

=xi(t)改變每個(gè)粒子的速度矢量：vi(t)=vi(t-1)+(xpbesti

-xi(t))每個(gè)粒子移到新位置：xi(t)=xi(t-1)+vi(t)；t=t+1轉(zhuǎn)2，重復(fù)遞歸到收斂6/3/202576安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.9粒群優(yōu)化

4.9.2粒群優(yōu)化算法全局最佳算法初始化粒群P(t)，t=0；Pi

P(t)；xi(t)為隨機(jī)由每個(gè)粒子的位置xi(t)評價(jià)性能FIFF(xi(t))<pbesti

THENpbesti=F(xi(t))；xpbesti

=xi(t)IFF(xi(t))<gbesti

THENgbesti=F(xi(t))；xgbesti

=xi(t)改變每個(gè)粒子的速度：vi(t)=vi(t-1)+

1(xpbesti-xi(t))+2(xpbesti-xi(t))每個(gè)粒子移到新位置：xi(t)=xi(t-1)+vi(t)；t=t+1轉(zhuǎn)2，重復(fù)遞歸到收斂6/3/202577安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.10蟻群優(yōu)化

4.10.1蟻群算法理論蟻群算法基本原理螞蟻能夠在食物和巢穴之間發(fā)現(xiàn)最短路徑，不是什么可見的線索，而是根據(jù)其釋放的稱為信息素(pheromone)的物質(zhì)。當(dāng)螞蟻在地面上爬行時(shí)，就在其爬行的路徑上釋放信息素。

6/3/202578安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院4.10蟻群優(yōu)化

4.10.1蟻群算法理論2.蟻群系統(tǒng)模型