智能算法初步(chūbù)第一頁，共104頁。5/16/2023數學(shùxué)建模十大算法蒙特卡羅算法數據擬合(nǐhé)、參數估計、插值等數據處理算法線性規劃等規劃類問題圖論算法動態規劃、回溯搜索、分支定界等計算機算法模擬退火、神經網絡、遺傳算法等最優化理論算法網格算法和窮舉法一些連續離散化方法數值分析算法圖像處理算法第二頁，共104頁。5/16/20233人工智能(rénɡōnɡzhìnénɡ)優化算法遺傳算法(suànfǎ)模擬退火人工神經網絡算法(suànfǎ)粒子群算法(suànfǎ)蟻群算法(suànfǎ)第三頁，共104頁。5/16/2023認識(rènshi)“人工智能”人工智能(ArtificialIntelligence,AI)概念是JohnMcCarthy（約翰.麥克斯）于1956年在Dartmouth學會上提出的。美國計算機科學家，因在人工智能領域(lǐnɡyù)的重大貢獻，被稱為“人工智能之父”，并因此獲得圖靈獎他于1948年獲得加州理工學院數學學士學位，1951年獲得普林斯頓大學數學博士學位JohnMcCarthy第四頁，共104頁。5/16/2023認識(rènshi)“人工智能”（續）人工智能——讓機器像人一樣思考人工智能是計算機科學的前沿學科(xuékē)，是研究、開發用于模擬、延伸和擴展人的智能的理論、方法、技術及應用系統的一門新的技術科學.計算機編程語言和其它計算機軟件都因為有了人工智能的進展而得以存在。人工智能涉及學科(xuékē)：哲學和認知科學，數學，神經生理學，心理學，計算機科學，信息論，控制論，不定性論，仿生學等第五頁，共104頁。5/16/2023認識(rènshi)“人工智能”（續）人工智能的目的：通過研究人腦的組成機理和思維方式，企圖了解智能的實質，并生產出一種能以人類智能相似的方式做出反應的智能機器——讓機器具有智慧(zhìhuì)，像人一樣思考.計算機的出現——人類開始真正有了一個可以模擬人類思維的工具人工智能的領域研究：包括機器人、語言識別、圖像識別、自然語言處理和專家系統等.第六頁，共104頁。5/16/2023意識(yìshí)和人工智能的區別人工智能就其本質而言，是對人的思維的信息過程的模擬.對于人的思維模擬可以從兩條道路進行：結構模擬：仿照人腦的結構機制，制造出“類人腦”的機器；功能模擬：暫時撇開人腦的內部結構，而從其功能過程進行模擬。現代電子計算機的產生便是對人腦思維功能的模擬，是對人腦思維的信息過程的模擬.人工智能不是人的智能，更不會(bùhuì)超過人的智能.第七頁，共104頁。5/16/2023意識和人工智能(rénɡōnɡzhìnénɡ)的區別（續）“機器思維”同“人類思維”的本質區別：1.人工智能純系無意識的機械的物理的過程，人類智能主要(zhǔyào)是生理和心理的過程.2.人工智能沒有社會性.3.人工智能沒有人類的意識所特有的能動的創造能力.4.兩者總是人腦的思維在前，電腦的功能在后.第八頁，共104頁。5/16/2023經典(jīngdiǎn)的人工智能成果人機對弈*1996年2月10-17日,GarryKasparov以4:2戰勝“深藍”(DeepBlue)*1997年5月3-11日,GarryKasparov以3.5:2.5輸于改進(gǎijìn)后的“深藍”*2003年2月GarryKasparov3:3戰平“小深”(DeepJunior)*2003年11月GarryKasparov2:2戰平“X3D德國人”(X3D-Fritz)模式識別指紋識別、人臉識別、語音識別、文字識別、圖像識別、車牌識別等第九頁，共104頁。5/16/2023經典的人工智能(rénɡōnɡzhìnénɡ)成果(續)電影中文名：人工智能片名：AI年代：2001國家：美國相關著作《視讀人工智能》、《人工智能的未來》、《人工智能哲學》、《人工智能：一種現代(xiàndài)的方法》……第十頁，共104頁。5/16/2023遺傳算法(suànfǎ)(GeneticAlgorithm，GA)人工神經網絡算法(suànfǎ)(ArtificicalNeuralNetwork,ANN)模擬退火(SimulatedAnnealing,SA)粒子群優化算法(suànfǎ)(ParticalSwamOptimizationAlgorithm,PSOA)蟻群優化算法(suànfǎ)(AntColonyOptimizationAlgorithm,ACOA)人工智能(rénɡōnɡzhìnénɡ)優化算法第十一頁，共104頁。5/16/202397年A題用模擬退火算法00年B題用神經網絡分類算法01年B題這種難題也可以使用神經網絡美國89年A題也和BP算法有關系美國03年B題伽馬刀問題也是目前(mùqián)研究的課題，目前(mùqián)算法最佳的是遺傳算法。遺傳算法(GA)、模擬退火法(SA)、神經網絡(NN)、近幾年的賽題越來越復雜，很多問題沒有什么很好的模型可以(kěyǐ)借鑒，于是這三類算法很多時候可以(kěyǐ)派上用場。最優化理論的三大非經典(jīngdiǎn)算法:第十二頁，共104頁。5/16/2023遺傳算法(suànfǎ)(GeneticAlgorithm，GA)人工神經網絡算法(suànfǎ)(ArtificicalNeuralNetwork,ANN)模擬退火(SimulatedAnnealing,SA)粒子群優化算法(suànfǎ)(ParticalSwamOptimizationAlgorithm,PSOA)蟻群優化算法(suànfǎ)(AntColonyOptimizationAlgorithm,ACOA)人工智能(rénɡōnɡzhìnénɡ)優化算法第十三頁，共104頁。5/16/2023遺傳算法(GeneticAlgorithm)進化(jìnhuà)算法(EvolutionaryAlgorithm)第十四頁，共104頁。5/16/2023遺傳算法是一類模擬達爾文生物進化論的自然選擇和遺傳算法機理的生物進化過程的計算模型，借鑒生物界的進化規律（適者生存，優勝劣汰遺傳機制）演化而來的隨機化搜索最優化方法。遺傳算法最初由美國密歇根大學J.Holland（霍蘭德）教授于1975年首先(shǒuxiān)提出來的，并出版了頗有影響的專著《AdaptationinNaturalandArtificialSystems》,遺傳算法這個名稱才逐漸為人所知，通常稱為“簡單遺傳算法”。遺傳算法(GeneticAlgorithm,GA)第十五頁，共104頁。5/16/2023直接對結構對象進行操作，不存在求導和函數連續性的限定；具有內在的隱并行性和更好的全局尋優能力；采用概率(gàilǜ)化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則。遺傳算法的這些性質，已被人們廣泛地應用于組合優化、機器學習、信號處理、自適應控制和人工生命等領域。它是現代有關智能計算中的關鍵技術。遺傳算法的主要(zhǔyào)特點第十六頁，共104頁。5/16/2023遺傳算法的定義(dìngyì)遺傳算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特征的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現(biǎoxiàn)（即基因型）是某種基因組合，它決定了個體的形狀的外部表現(biǎoxiàn)，如黑頭發的特征是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現從表現(biǎoxiàn)型到基因型的映射即編碼工作。第十七頁，共104頁。5/16/2023遺傳算法的定義(dìngyì)（續）由于仿照基因編碼的工作很復雜，我們往往進行簡化，如二進制編碼，初代種群產生之后，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解。在每一代，根據問題域中個體(gètǐ)的適應度（fitness）大小選擇（selection）個體(gètǐ)，并借助于自然遺傳學的遺傳算子（geneticoperators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體(gètǐ)經過解碼（decoding），可以作為問題近似最優解。第十八頁，共104頁。5/16/2023遺傳算法流程圖由于遺傳算法的整體搜索策略和優化搜索方法在計算是不依賴于梯度信息或其它輔助知識，而只需要影響(yǐngxiǎng)搜索方向的目標函數和相應的適應度函數，所以遺傳算法提供了一種求解復雜系統問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性。第十九頁，共104頁。5/16/2023遺傳算法的一般(yībān)算法遺傳算法是由進化論和遺傳學機理而產生的搜索算法。1.創建一個隨機的初始狀態：初始群是從解中隨機選擇出來的，將這些解比喻為染色體或基因，該種群被稱為第一代。2.評估適應度：對每一個解(染色體)指定一個適應度的值，根據問題(wèntí)求解的實際接近程度來指定(以便逼近求解問題(wèntí)的答案)。不要把這些“解”與問題(wèntí)的“答案”混為一談，可以把它理解成為要得到答案，系統可能需要利用的那些特性。第二十頁，共104頁。5/16/2023遺傳算法的一般(yībān)算法(續)3.繁殖(包括子代突變)帶有較高適應度值的那些染色體更可能產生后代(后代產生后也將發生突變)。后代是父母的產物，他們由來自父母的基因結合而成，這個過程被稱為“雜交”。4.下一代如果新的一代包含一個解，能產生一個充分接近或等于期望答案的輸出，那么問題就已經(yǐjing)解決了。如果情況并非如此，新的一代將重復他們父母所進行的繁衍過程，一代一代演化下去，直到達到期望的解為止。第二十一頁，共104頁。5/16/2023遺傳算法的一般(yībān)算法(續)5.并行計算*非常容易將遺傳算法用到并行計算和群集環境中。*一種方法是直接把每個節點當成一個并行的種群看待。然后有機體根據不同的繁殖方法從一個節點遷移到另一個節點。*另一種方法是“農場主/勞工”體系結構，指定一個節點為“農場主”節點，負責選擇有機體和分派適應度的值，另外的節點作為(zuòwéi)“勞工”節點，負責重新組合、變異和適應度函數的評估。第二十二頁，共104頁。5/16/2023遺傳算法模擬自然選擇和自然遺傳過程中發生的繁殖、交叉和基因突變現象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產生新一代的候選解群，重復此過程，直到滿足(mǎnzú)某種收斂指標為止。遺傳算法的搜索(sōusuǒ)機制第二十三頁，共104頁。5/16/2023局部全局遺傳算法(GA)第二十四頁，共104頁。5/16/2023Wehaveadream!!IamatthetopHeightis...Iamnotatthetop.Myhighisbetter!Iwillcontinue遺傳算法(GA)GA-----第0代第二十五頁，共104頁。5/16/2023DeadoneNewone遺傳算法(GA)GA----第1代第二十六頁，共104頁。5/16/2023Notatthetop,ComeUp!!!遺傳算法(GA)GA----第?代第二十七頁，共104頁。5/16/2023IamtheBEST!!!遺傳算法(GA)GA----第N代第二十八頁，共104頁。5/16/2023生物進化與遺傳算法對應(duìyìng)關系生物進化遺傳算法適者生存適應函數值最大的解被保留的概率最大個體問題的一個解染色體解的編碼基因編碼的元素群體被選定的一組解種群根據適應函數選擇的一組解交叉以一定的方式由雙親產生后代的過程變異編碼的某些分量發生變化的過程環境適應函數第二十九頁，共104頁。5/16/2023遺傳算法的基本操作選擇(selection):根據各個個體的適應(shìyìng)值，按照一定的規則或方法，從第t代群體P(t)中選擇出一些優良的個體遺傳到下一代群體P(t+1)中。交叉(crossover):將群體P(t)內的各個個體隨機搭配成對，對每一個個體，以某個概率Pc(稱為交叉概率，crossvoerrate)交換它們之間的部分染色體。變異(mutation):對群體P(t)中的每一個個體，以某一概率Pm(稱為變異概率，mutationrate)改變某一個或一些基因座上基因值為其它的等位基因。第三十頁，共104頁。5/16/2023如何(rúhé)設計遺傳算法如何進行編碼？如何產生(chǎnshēng)初始種群？如何定義適應函數？如何進行遺傳操作(復制、交叉、變異)？如何產生(chǎnshēng)下一代種群？如何定義停止準則？第三十一頁，共104頁。5/16/2023編碼(biānmǎ)(Coding)表現型空間編碼(Coding)解碼(Decoding)基因型空間={0,1}L0111010010100010011001001010010001第三十二頁，共104頁。5/16/2023編碼(biānmǎ)設某一參數的取值范圍為（L，U），使用(shǐyòng)長度為k的二進制編碼表示該數，則共有種不同的編碼。第三十三頁，共104頁。5/16/2023解碼(jiěmǎ)解碼的目的(mùdì)是為了將不直觀的二進制數據串還原成十進制。設某一個(yīɡè)體的二進制編碼為則對應的解碼公式為：第三十四頁，共104頁。5/16/2023適應(shìyìng)函數(FitnessFunction)GA在搜索中不依靠外部信息，僅以適應函數為依據，利用群體中每個染色體(個體)的適應值來進行搜索。以染色體適應值的大小來確定該染色體被遺傳到下一代群體中的概率。染色體適應值越大，該染色體被遺傳到下一代的概率也越大；反之，染色體的適應值越小，該染色體被遺傳到下一代的概率也越小。因此適應函數的選取至關重要，直接影響到GA的收斂速度(sùdù)以及能否找到最優解。群體中的每個染色體都需要計算適應值適應函數一般由目標函數變換而成第三十五頁，共104頁。5/16/2023適應(shìyìng)函數(FitnessFunction)適應函數常見(chánɡjiàn)形式：直接將目標函數轉化為適應函數若目標函數為最大化問題：Fitness(f(x))=f(x)若目標函數為最小化問題：Fitness(f(x))=-f(x)第三十六頁，共104頁。5/16/2023適應(shìyìng)函數(FitnessFunction)界限(jièxiàn)構造法目標函數為最大化問題其中Cmin為f(x)的最小估計值目標函數為最小化問題其中Cmaxn為f(x)的最大估計值第三十七頁，共104頁。5/16/2023選擇(xuǎnzé)(Selection)選擇(復制)操作把當前種群的染色體按與適應值成正比例的概率復制到新的種群中主要(zhǔyào)思想:適應值較高的染色體體有較大的選擇(復制)機會設種群(zhǒnɡqún)的規模為Nxi是種群(zhǒnɡqún)中第i個染色體染色體xi被選概率第三十八頁，共104頁。5/16/2023選擇(xuǎnzé)(Selection)實現1：”輪盤賭”選擇(Roulettewheelselection)

產生一個在0與總和之間的的隨機數m從種群中編號為1的染色體開始(kāishǐ)，將其適應值與后續染色體的適應值相加，直到累加和等于或大于m第三十九頁，共104頁。5/16/2023選擇(xuǎnzé)(Selection)染色體的適應(shìyìng)值和所占的比例輪盤(lúnpán)賭選擇第四十頁，共104頁。5/16/2023選擇(xuǎnzé)(Selection)隨機數23491338627所選號碼262514所選染色體110000001111000011000111010010染色體編號123456染色體011101100000100100100110000011適應度81525128被選概率0.160.30.040.10.240.16適應度累計8

23

253042

50染色體被選的概率(gàilǜ)被選的染色體第四十一頁，共104頁。5/16/2023選擇(xuǎnzé)(Selection)輪盤上的片分配給群體的染色體，使得每一個片的大小與對于染色體的適應值成比例從群體中選擇一個染色體可視為旋轉(xuánzhuǎn)一個輪盤，當輪盤停止時，指針所指的片對于的染色體就時要選的染色體。模擬“輪盤賭”算法：r=rand(0,1)，s=0，i=0；如果s≥r，則轉(4)；s=s+p(xi)，i=i+1,轉(2)xi即為被選中的染色體，輸出I結束第四十二頁，共104頁。5/16/2023選擇(xuǎnzé)(Selection)其他(qítā)選擇法：隨機遍歷抽樣(Stochasticuniversalsampling)局部選擇(Localselection)截斷選擇(Truncationselection)競標賽選擇(Tournamentselection)特點：選擇操作得到的新的群體稱為交配池，交配池是當前代和下一代之間的中間群體，其規模為初始群體規模。選擇操作的作用效果是提高了群體的平均適應值(低適應值個體趨于淘汰，高適應值個體趨于選擇)，但這也損失了群體的多樣性。選擇操作沒有產生新的個體，群體中最好個體的適應值不會改變。第四十三頁，共104頁。5/16/2023交叉(jiāochā)(crossover,Recombination)遺傳交叉(雜交、交配、有性重組)操作發生在兩個染色體之間，由兩個被稱之為雙親的父代染色體，經雜交以后，產生兩個具有雙親的部分基因的新的染色體，從而檢測搜索(sōusuǒ)空間中新的點。選擇(復制)操作每次作用在一個染色體上，而交叉操作每次作用在從交配池中隨機選取的兩個個體上(交叉概率Pc)。交叉產生兩個子染色體，他們與其父代不同，且彼此不同,每個子染色體都帶有雙親染色體的遺傳基因。第四十四頁，共104頁。5/16/2023單點交叉(jiāochā)(1-pointcrossover)在雙親的父代染色體中隨機產生一個(yīɡè)交叉點位置在交叉點位置分離雙親染色體互換交叉點位置右邊的基因碼產生兩個子代染色體交叉概率Pc一般范圍為(60%,90%)，平均約80%11111111父代1111000000000000子代111100000000000011111111交叉點位置(wèizhi)第四十五頁，共104頁。5/16/2023交叉(jiāochā)(crossover,Recombination)單點交叉操作可以產生與父代染色體完全(wánquán)不同的子代染色體；它不會改變父代染色體中相同的基因。但當雙親染色體相同時，交叉操作是不起作用的。假如交叉概率Pc＝50%,則交配(jiāopèi)池中50%的染色體(一半染色體)將進行交叉操作，余下的50%的染色體進行選擇(復制)操作。GA利用選擇和交叉操作可以產生具有更高平均適應值和更好染色體的群體第四十六頁，共104頁。5/16/2023變異(biànyì)(Mutation)以變異概率Pm改變染色體的某一個基因,當以二進制編碼時，變異的基因由0變成1，或者由1變成0。變異概率Pm一般介于1/種群規模與1/染色體長度(chángdù)之間，平均約1-2%11010100父代01010101子代變異(biànyì)基因變異基因第四十七頁，共104頁。5/16/2023變異(biànyì)(Mutation)比起選擇和交叉操作，變異操作是GA中的次要操作，但它在恢復群體中失去的多樣性方面具有潛在的作用。在GA執行的開始階段，染色體中一個特定位上的值1可能與好的性能緊密聯系，即搜索空間中某些初始染色體在那個位上的值1可能一致產生高的適應值。因為越高的適應值與染色體中那個位上的值1相聯系，選擇操作就越會使群體的遺傳多樣性損失。等到達一定程度時，值0會從整個群體中那個位上消失，然而全局最優解可能在染色體中那個位上為0。如果搜索范圍縮小到實際包含(bāohán)全局最優解的那部分搜索空間，在那個位上的值0就可能正好是到達全局最優解所需要的。第四十八頁，共104頁。5/16/2023停止(tíngzhǐ)準則(TerminationCriteria)種群中個體的最大適應值超過預設定值種群中個體的平均適應值超過預設定值種群中個體的進化(jìnhuà)代數超過預設定值第四十九頁，共104頁。5/16/2023基本(jīběn)步驟(StepbyStep)(1)隨機產生初始種群;(2)計算(jìsuàn)種群體中每個個體的適應度值,判斷是否滿足停止條件，若不滿足，則轉第(3)步,否則轉第(6)步;(3)按由個體適應值所決定的某個規則選擇將進入下一代的個體;(4)按交叉概率Pc進行交叉操作,生產新的個體;(5)按變異概率Pm進行變異操作,生產新的個體;(6)輸出種群中適應度值最優的染色體作為問題的滿意解或最優解。第五十頁，共104頁。5/16/2023假設按無約束問題那樣求解，在搜索過程中計算目標函第十三頁，共104頁。交叉(jiāochā)(crossover,Recombination)需其他方式的交叉(重組)操作,------初始種群的生成函數染色體的適應(shìyìng)值和所占的比例3)有些方法(fāngfǎ)，如Davison-Fletcher-Powell直接依賴于至少一階導數；隨機選取個體中兩個編碼，然后把第二個編碼放在第一結構模擬：仿照人腦的結構機制，制造出“類人腦”的機器；遺傳算法的應用(yìngyòng)設某一個(yīɡè)體的二進制編碼為個向量中正好出現一次,不能有重復。直接將目標函數轉化為適應函數城市編號(biānhào)1,2,…,40《MATLAB遺傳算法工具箱及應用(yìngyòng)》(雷英杰等,西安電子科技大學出版社,2005)基于此工具箱selectOps-------傳遞個選擇函數的參數,如[0.流程圖(FlowChart)第五十一頁，共104頁。5/16/2023基本(jīběn)遺傳算法基本遺傳算法（SimpleGeneticAlgorithms,簡稱SGA）是一種統一的最基本的遺傳算法，它只使用選擇、交叉、變異這三種基本遺傳算子，其遺傳進化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎，它不僅給各種遺傳算法提供了一個基本框架，同時(tóngshí)也具有一定的應用價值。第五十二頁，共104頁。5/16/2023SGA偽碼描述(miáoshù)ProcedureGeneticAlgorithmbegint=0;%遺傳代數初始化P(t);%初始化種群或染色體計算P(t)的適應值;while(不滿足停止(tíngzhǐ)準則)dobegint=t+1;從P(t-1)中選擇P(t);%selection重組P(t);%crossoverandmutation計算P(t)的適應值;endend第五十三頁，共104頁。5/16/2023遺傳算法的應用(yìngyòng)函數優化函數優化是遺傳算法的經典應用領域，也是對遺傳算法進行性能測試評價的常用算例。對于一些非線性、多模型、多目標的函數優化問題，用其他優化方法較難求解，而遺傳算法卻可以方便(fāngbiàn)地得到較好的結果。遺傳算法提供了一種求解復雜系統優化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性，所以廣泛應用于很多學科(xuékē)。下面列舉一些遺傳算法的主要應用領域。第五十四頁，共104頁。5/16/2023遺傳算法的應用(yìngyòng)組合優化遺傳算法是尋求組合優化問題滿意解的最佳工具(gōngjù)之一，實踐證明，遺傳算法對于組合優化問題中的NP完全問題非常有效。例如，遺傳算法已經在求解旅行商問題(TravelingSalesmanProblem,TSP)、背包問題(KnapsackProblem)、裝箱問題(BinPackingProblem)等方面得到成功的應用。生產調度問題生產調度問題在很多情況下所建立起來的數學模型難以精確求解，即使經過一些簡化之后可以進行求解也會因簡化得太多而使求解結果與實際相差太遠。現在遺傳算法已經成為解決復雜調度問題的有效工具(gōngjù)。第五十五頁，共104頁。5/16/2023遺傳算法的應用(yìngyòng)自動控制遺傳算法已經在自動控制領域中得到了很好的應用，例如基于遺傳算法的模糊控制器的優化設計、基于遺傳算法的參數辨識、基于遺傳算法的模糊控制規則的學習、利用遺傳算法進行人工神經網絡的結構優化設計和權值學習等。機器人智能控制機器人是一類復雜的難以精確建模的人工系統，而遺傳算法的起源就來自于對人工自適應系統的研究，所以(suǒyǐ)機器人智能控制自然成為遺傳算法的一個重要應用領域。第五十六頁，共104頁。5/16/2023遺傳算法的應用(yìngyòng)圖象處理和模式識別圖像處理和模式識別是計算機視覺中的一個重要研究領域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地存在一些誤差，這些誤差會影響圖像處理的效果。如何使這些誤差最小是使計算機視覺達到實用化的重要要求，遺傳算法在這些圖像處理中的優化計算方面得到了很好的應用。人工生命人工生命是用計算機、機械等人工媒體模擬或構造出的具有自然生物系統特有行為的人造系統。自組織能力和自學習能力是人工生命的兩大重要特征。人工生命與遺傳算法有著密切的關系，基于(jīyú)遺傳算法的進化模型是研究人工生命現象的重要理論基礎。第五十七頁，共104頁。5/16/2023遺傳算法的應用(yìngyòng)遺傳程序設計Koza發展了遺傳程序設計的概念，他使用了以LISP語言所表示的編碼方法，基于對一種樹形結構所進行的遺傳操作來自動生成計算機程序。機器學習基于遺傳算法的機器學習，在很多領域中都得到了應用。例如基于遺傳算法的機器學習可用來調整人工神經網絡的連接(liánjiē)權，也可以用于人工神經網絡的網絡結構優化設計。分類器系統在多機器人路徑規劃系統中得到了成功的應用。第五十八頁，共104頁。5/16/2023SGA實例(shílì)1：函數最值SGA參數:編碼方式:二進制碼e.g.000000;0110113;1111131種群規模:4隨機(suíjī)初始群體“轉盤賭”選擇一點雜交,二進制變異求函數f(x)=x2的最大值，x為自然數且0≤x≤31.手工(shǒugōng)方式完成演示SGA過程第五十九頁，共104頁。5/16/2023SGA實例(shílì)1maxx2:選擇操作第六十頁，共104頁。5/16/2023SGA實例(shílì)1maxx2:交叉操作第六十一頁，共104頁。5/16/2023SGA實例(shílì)1maxx2:變異操作第六十二頁，共104頁。5/16/2023SGA實例(shílì)2:連續函數最值求下列(xiàliè)函數的最大值：第六十三頁，共104頁。5/16/2023SGA實例(shílì)2:編碼高精度

編碼(biānmǎ)[x,y]{0,1}L必須(bìxū)可逆(一個表現型對應一個基因型)

解碼算子：:{0,1}L

[x,y]

染色體長度L決定可行解的最大精度長染色體(慢進化)

實數問題：變量z為實數，如何把{a1,…,aL}

{0,1}Lz∈[x,y]第六十四頁，共104頁。5/16/2023SGA實例(shílì)2:編碼設定求解精確(jīngquè)到6位小數，因區間長度位2-(-1)=3,則需將區間分為3X106等份。因2097152＝221<3X106≤222＝4194304。故編碼的二進制串長L=22。將一個(yīɡè)二進制串(b21b20…b0)轉化為10進制數：e.g.<0000000000000000000000>-1;<1111111111111111111111>2<1110000000111111000101>1.6278881.627888=-1+3x(1110000000111111000101)2

/(222-1)=-1+3x3674053/(222-1)第六十五頁，共104頁。5/16/2023SGA實例2:初始化種群(zhǒnɡqún)、適應函數隨機初始化種群適應函數本實例目標函數在定義域內均大于0，且是求函數最大值，故直接引用(yǐnyòng)目標函數作為適應函數：f(s)=f(x)其中二進制串s對于變量x的值。e.g.s1=<0000001110000000010000>x1=-0.958973適應值:f(s1)=f(x1)=1.078878s2=<1110000000111111000101>x2=1.627888適應值:f(s2)=f(x2)=3.250650第六十六頁，共104頁。5/16/2023SGA實例(shílì)2:遺傳操作選擇操作(“輪盤賭”選擇)交叉操作(單點交叉)交叉前(父):s1=<00000|01110000000010000>s2=<11100|00000111111000101>交叉后(子):s’1=<00000|00000111111000101>s’2=<11100|01110000000010000>適應(shìyìng)值:f(s’1)=f(-0.998113)=1.940865f(s’2)=f(1.666028)=3.459245s’2的適應(shìyìng)值比其雙親個體的適應(shìyìng)值高。第六十七頁，共104頁。5/16/2023SGA實例(shílì)2:遺傳操作變異操作(cāozuò)變異前(父):s2=<1110000000111111000101>變異后(子):s’2=<1110100000111111000101>適應值f(s’2)=f(1.721638)=0.917743比f(s2)小變異前(父):s2=<1110000000111111000101>變異后(子):s”2=<1110000001111111000101>適應值f(s”2)=f(1.630818)=3.343555比f(s2)大變異操作有”擾動”作用，同時具有增加(zēngjiā)種群多樣性的效果。第六十八頁，共104頁。5/16/2023SGA實例(shílì)2:模擬結果遺傳算法的參數:種群規模(guīmó):50染色體長度:L=22最大進化代數:150交叉概率:Pc=0.25變異概率:Pm=0.01第六十九頁，共104頁。5/16/2023SGA實例2:模擬結果(jiēguǒ)(最佳個體進化情況)世代數染色體編碼變量x適應值141117344054718915010001110000101100011110000011011000101001111011010101110011100111111101010111111010011111100001101111011001111110100100010001100111110001101101000110011110100110110001011001111110100111111001100111111010011111100110011111.8316241.8424161.8548601.8475361.8532901.8484431.8486991.8508971.8505491.8505493.5348063.7903623.8332863.8420043.8434023.8462323.8471553.8501623.8502743.850274第七十頁，共104頁。5/16/2023最優化問題(wèntí)(OptimizationProblem)最優化問題(wèntí):組合優化問題(wèntí)(CombinatorialOptimizationProblem):最優化問題(wèntí)中的解空間X或S由離散集合構成。第七十一頁，共104頁。5/16/2023最優化問題(wèntí)算法傳統的優化方法(fāngfǎ)(局部優化方法(fāngfǎ))共軛梯度法、牛頓法、單純形方法(fāngfǎ)等特點:1)依賴于初始條件。2)與求解空間有緊密關系，促使較快地收斂到局部解，但同時對解域有約束，如連續性或可微性。利用這些約束，收斂快。3)有些方法(fāngfǎ)，如Davison-Fletcher-Powell直接依賴于至少一階導數；共軛梯度法隱含地依賴于梯度。第七十二頁，共104頁。5/16/2023最優化問題(wèntí)算法全局優化方法下降軌線法、Monte-Carlo隨機試驗法、模擬退火法、GA等特點：1)不依賴于初始條件；2)不與求解空間有緊密關系,對解域無可微或連續的要求;容易實現，求解穩健。3)但收斂(shōuliǎn)速度慢,能獲得全局最優;適合于求解空間不知的情況。4)GA可應用于大規模、多峰多態函數、含離散變量等全局優化問題;求解速度和質量遠超過常規方法。第七十三頁，共104頁。5/16/2023無約束最優化問題(wèntí)GA編碼：X=(x1,x2,…,xn)的各個變量可以按二進制編碼方法分別(fēnbié)編碼。對于變量xi的上、下限約束li≤xi≤ui(i=1,2,…,n)，依據解的精度要求(有效位數)求得各個變量X=(x1,x2,…,xn)的二進制碼位數(m1,m2,…,mn)(確定方法類似于SGA實例2)，因此將n個二進制位串順序連接起來，構成一個個體的染色體編碼，編碼的總位數m＝m1+m2+…+mn。無約束最優化問題(wèntí):第七十四頁，共104頁。5/16/2023無約束最優化問題(wèntí)GA解碼：解碼時仍按各個變量的編碼順序分別(fēnbié)實現常規的二進制編碼解碼方法。二進制遺傳編碼示意圖如下：第七十五頁，共104頁。5/16/2023約束(yuēshù)最優化問題常規解法：(1)把約束問題轉化為無約束問題，在用無約束問題方法求解，如罰函數法(2)改進無約束問題的方法，再用于約束問題，如梯度投影法、廣義(guǎngyì)簡約梯度法約束(yuēshù)最優化問題:第七十六頁，共104頁。5/16/2023約束(yuēshù)最優化問題遺傳算法求解關鍵:約束條件的處理等式約束可以包含到適應函數，僅考慮不等式約束。假設按無約束問題那樣求解，在搜索過程中計算目標函數值，并檢查是否有約束違反。如果沒有違反，則表明是可行(kěxíng)解，就根據目標函數指定一適應值；否則，就是不可行解，因而沒有適應值(適應值為0)。這樣的處理實際不可行，因為找到一個可行(kěxíng)解幾乎與找到最優解一樣困難。第七十七頁，共104頁。5/16/2023一般解法：通過引入罰函數，從不可行解中得到一些信息。將罰函數包含到適應函數中。關鍵是如何(rúhé)設計罰函數；不同問題需要設計不同的罰函數；對一般的約束處理，通常很困難。約束(yuēshù)最優化問題第七十八頁，共104頁。5/16/2023組合(zǔhé)最優化問題典型問題：巡回旅行商問題(TravelingSalesmanProblem)作業調度問題(JobShopSchedulingProblem)背包(bèibāo)問題(KnapsackProblem)圖著色問題………很多組合最優化問題是NP難問題或NP完全問題第七十九頁，共104頁。5/16/2023巡回旅行(lǚxíng)商問題(TSP)TSP，也稱貨郎擔問題，是一個NP完全問題。TSP描述：圖論:設圖G=(V,E),其中V是頂點集，E是邊集。設C=(cij)是與E相聯系的距離矩陣。尋找一條通過所有頂點且每個頂點只通過一次的最短距離回路(Hamilton回路)。實際(shíjì)應用中，C也可解釋為費用或旅行時間矩陣。實際(shíjì):一位推銷員從自己所在城市出發，必須遍訪所有城市之后又回到原來的城市，求使其旅行費用最少的路徑。第八十頁，共104頁。5/16/2023巡回旅行(lǚxíng)商問題(TSP)中國貨郎擔問題:城市數:40城市編號(biānhào)1,2,…,40尋找一條最短路徑第八十一頁，共104頁。5/16/2023TSP復雜性搜索空間龐大TSP涉及求多個變量的函數的最小值，求解很困難。其可能的路徑條數隨著城市數目n成指數增長，如，5個城市對應12條路徑；10個城市對應181440條路徑；100個城市對應4.6663X10155條路徑。如此(rúcǐ)龐大的搜索空間，常規解法和計算工具都遇到計算上的困難。只能尋找近似解法，如神經網絡方法、模擬退火法、遺傳算法等。第八十二頁，共104頁。5/16/2023TSP編碼:路徑(lùjìng)表示染色體表示(biǎoshì)成所有城市的一個排列，若有n個城市，一條可能路徑編碼為長度為n的整數向量(i1,i2,…,in),其中ik表示(biǎoshì)第ik個城市。例如:路徑編碼向量(517894623)直接表示(biǎoshì)一條旅行路程(5->1->7->8->9->4->6->2->3)。此向量是1到n的一個排列，即從1到n的每個整數在這個向量中正好出現一次,不能有重復。這樣，基本遺傳算法的基因操作生成的個體不能滿足這一約束條件，需尋求其他遺傳操作。第八十三頁，共104頁。5/16/2023TSP交叉(jiāochā)需其他方式的交叉(重組)操作,如部分(bùfen)匹配交叉(PartiallyMatchedCrossover,PMX)、順序交叉(OrderedCrossover,OX)、循環交叉(CycleCrossover,CX)、邊重組(EdgeRecombination)。12345543211232154345一般(yībān)的交叉操作會產生不合適的解，如第八十四頁，共104頁。5/16/2023TSP交叉1:部分(bùfen)匹配交叉(PMX)雙親(shuāngqīn)P1,P2隨機選取兩個交叉點，得到一個匹配段,根據交叉點中間段給出映射關系。123456789937826514xxx4567xxxxx8265xxP1P2映射(yìngshè)關系：48、52、75c1c2交換兩個交叉點之間的編碼,(X表示未定碼)第八十五頁，共104頁。5/16/2023TSP交叉(jiāochā)1:部分匹配交叉(jiāochā)(PMX)子個體(gètǐ)C1，C2分別從其父個體(gètǐ)中繼承未映射城市碼12345678993782651493x45671x1x38265x9P1P2c1c2映射(yìngshè)關系：48、52、75932456718173826549c1c2

再根據映射關系，對以上未定碼，使用最初雙親碼，得到子個體的對應碼。映射關系存在傳遞關系，則選擇未定碼交換。第八十六頁，共104頁。5/16/2023TSP交叉(jiāochā)2:順序交叉(jiāochā)(OX)雙親(shuāngqīn)P1,P2隨機選取兩個交叉點123456789937826514P1P2xxx4567xxxxx8265xxc1c2兩個交叉點間的中間(zhōngjiān)段保存不變

子個體C1的未定碼的確定需要父個體P2的未選定城市碼，子個體C2的未定碼的確定需要父個體P1的未選定城市碼。第八十七頁，共104頁。5/16/2023TSP交叉(jiāochā)2:順序交叉(jiāochā)(OX)記取父個體P2從第二個交叉點開始城市碼的排列順序(shùnxù)，當到達表尾時，返回表頭繼續記錄，直到第二個交叉點。937826514P2xxx4567xxc1382456719c1347826591c2得到父個體P2的排列順序1-4-9-3-7-8-2-6-5,并將C1已有城市碼4,5,6,7從中去掉(qùdiào)，得到排列順序1-9-3-8-2，再將此順序復制到C1，復制點也是從第二個交叉點開始，得到C1。同理的C2，第八十八頁，共104頁。5/16/2023TSP交叉(jiāochā)3:循環交叉(jiāochā)(CX)CX操作中子個體中的城市碼順序根據任一父個體產生確定(quèdìng)循環編碼復制(fùzhì)循環編碼到子個體第八十九頁，共104頁。5/16/2023TSP變異(biànyì)InsertMutation隨機選取個體中兩個編碼，然后把第二個編碼放在第一個編碼之后，其他編碼順次調節(tiáojié)位置。Swapmutation隨機(suíjī)選取個體中兩個編碼，然后交換它們的位置。第九十頁，共104頁。5/16/2023TSP變異(biànyì)Inversionmutation隨機選取(xuǎnqǔ)個體中一段編碼，然后顛倒這段編碼的順序。Scramblemutation隨機(suíjī)選取個體上一段編碼,然后打亂這段編碼的順序。選取的編碼不一定是鄰接編碼第九十一頁，共104頁。5/16/2023TSP的GA過程(guòchéng)從N個隨機起點開始產生N條路徑，N為種群(zhǒnɡqún)的規模;利用最優方法搜索每條路徑的局部最優解;選擇交叉對使在平均性能之上的個體得到更多的子代;交叉和變異;搜索每條路徑得到其極小解，如果不收斂，則回到第3步；否則，停止。第九十二頁，共104頁。5/16/2023GA的MATLAB實現(shíxiàn)軟件平臺(SoftwarePlatforms):MATLAB7.xGeneticAlgorithmandDirectSearchToolbox

2.0.1MATLAB6.x(or7.x)+GAOTGAOT:GeneticAlgorithmOptimizationToolbox美國NorthCarolinaStateUniversity開發MATLAB6.x(or7.x)+GEATbxGEATbx:GeneticandEvolutionaryAlgorithmToolbox