第二講-計(jì)算智能-進(jìn)化計(jì)算課件

計(jì)算智能是信息科學(xué)、生命科學(xué)、認(rèn)知科學(xué)等不同學(xué)科相互交叉的產(chǎn)物。它主要借鑒仿生學(xué)的思想，基于人們對(duì)生物體智能機(jī)理的認(rèn)識(shí)，采用數(shù)值計(jì)算的方法去模擬和實(shí)現(xiàn)人類的智能。計(jì)算智能主要研究領(lǐng)域包括：神經(jīng)計(jì)算、進(jìn)化計(jì)算、模糊計(jì)算、免疫計(jì)算、DNA計(jì)算、粗糙集等。

2.1概述

2.1.1什么是計(jì)算智能

2.1.2計(jì)算智能的產(chǎn)生與發(fā)展

2.1.3計(jì)算智能與人工智能的關(guān)系

2.2進(jìn)化計(jì)算第2講計(jì)算智能之進(jìn)化計(jì)算1計(jì)算智能是信息科學(xué)、生命科學(xué)、認(rèn)知科學(xué)等不同學(xué)科相2.1.1什么是計(jì)算智能

概念解釋

計(jì)算智能（ComputationalIntelligence，CI）目前還沒(méi)有一個(gè)統(tǒng)一的的定義，使用較多的是美國(guó)科學(xué)家貝慈德克（J.C.Bezdek）從計(jì)算智能系統(tǒng)角度所給出的定義。從計(jì)算智能系統(tǒng)角度如果一個(gè)系統(tǒng)僅處理低層的數(shù)值數(shù)據(jù)，含有模式識(shí)別部件，沒(méi)有使用人工智能意義上的知識(shí)，且具有計(jì)算適應(yīng)性、計(jì)算容錯(cuò)力、接近人的計(jì)算速度和近似于人的誤差率這4個(gè)特性，則它是計(jì)算智能的。從學(xué)科范疇看計(jì)算智能是在神經(jīng)網(wǎng)絡(luò)（NeuralNetworks,NN）、進(jìn)化計(jì)算（EvolutionaryComputation,EC）及模糊系統(tǒng)（FuzzySystem,FS）這3個(gè)領(lǐng)域發(fā)展相對(duì)成熟的基礎(chǔ)上形成的一個(gè)統(tǒng)一的學(xué)科概念。22.1.1什么是計(jì)算智能

概念解釋計(jì)算智能（Com2.1.1什么是計(jì)算智能

研究領(lǐng)域神經(jīng)網(wǎng)絡(luò)

是一種對(duì)人類智能的結(jié)構(gòu)模擬方法，它是通過(guò)對(duì)大量人工神經(jīng)元的廣泛并行互聯(lián)，構(gòu)造人工神經(jīng)網(wǎng)絡(luò)系統(tǒng)去模擬生物神經(jīng)系統(tǒng)的智能機(jī)理的。進(jìn)化計(jì)算

是一種對(duì)人類智能的演化模擬方法，它是通過(guò)對(duì)生物遺傳和演化過(guò)程的認(rèn)識(shí)，用進(jìn)化算法去模擬人類智能的進(jìn)化規(guī)律的。模糊計(jì)算

是一種對(duì)人類智能的邏輯模擬方法，它是通過(guò)對(duì)人類處理模糊現(xiàn)象的認(rèn)知能力的認(rèn)識(shí)，用模糊邏輯去模擬人類的智能行為的。綜合解釋從貝慈德克的定義和上述學(xué)科范疇可以看出以下兩點(diǎn)：第一，計(jì)算智能是借鑒仿生學(xué)的思想，基于生物神經(jīng)系統(tǒng)的結(jié)構(gòu)、進(jìn)化和認(rèn)知對(duì)自然智能進(jìn)行模擬的。第二，計(jì)算智能是一種以模型（計(jì)算模型、數(shù)學(xué)模型）為基礎(chǔ)，以分布、并行計(jì)算為特征的自然智能模擬方法。

32.1.1什么是計(jì)算智能

研究領(lǐng)域神經(jīng)網(wǎng)絡(luò)32.1.2計(jì)算智能的產(chǎn)生與發(fā)展

1992年，貝慈德克在《ApproximateReasoning》學(xué)報(bào)上首次提出了“計(jì)算智能”的概念。

1994年6月底到7月初，IEEE在美國(guó)佛羅里達(dá)州的奧蘭多市召開(kāi)了首屆國(guó)際計(jì)算智能大會(huì)(簡(jiǎn)稱WCCI’94)。會(huì)議第一次將神經(jīng)網(wǎng)絡(luò)、進(jìn)化計(jì)算和模糊系統(tǒng)這三個(gè)領(lǐng)域合并在一起，形成了“計(jì)算智能”這個(gè)統(tǒng)一的學(xué)科范疇。在此之后，WCCI大會(huì)就成了IEEE的一個(gè)系列性學(xué)術(shù)會(huì)議，開(kāi)始是4年舉辦一次，現(xiàn)在是每2年舉辦一次。1998年5月，在美國(guó)阿拉斯加州的安克雷奇市又召開(kāi)了第2屆計(jì)算智能?chē)?guó)際會(huì)議WCCI’98。2002年5月，在美國(guó)夏威夷州首府火奴魯魯市又召開(kāi)了第3屆計(jì)算智能?chē)?guó)際會(huì)議WCCI’02。WCCI’2014在北京召開(kāi)。此外，IEEE還出版了一些與計(jì)算智能有關(guān)的刊物:IEEETrans.NeuralNetworks,IEEETrans.FuzzySystems,IEEETrans.EvolutionaryComputation。目前，計(jì)算智能已成為智能科學(xué)技術(shù)一個(gè)重要的研究領(lǐng)域。42.1.2計(jì)算智能的產(chǎn)生與發(fā)展1992年，貝慈德2.1.3計(jì)算智能與人工智能的關(guān)系

目前，對(duì)計(jì)算智能與人工智能的關(guān)系有2種觀點(diǎn)，一種認(rèn)為計(jì)算智能是人工智能的一個(gè)子集，另一種認(rèn)為計(jì)算智能和人工智能是不同的范疇。第一種觀點(diǎn)的代表人物是貝慈德克。他把智能（Intelligence，I）和神經(jīng)網(wǎng)絡(luò)（NeuralNetwork，NN）都分為計(jì)算的（Computational，C）、人工的（Artificial，A）和生物的（Biological,B）3個(gè)層次，并以模式識(shí)別（PR）為例，給出了下圖所示的智能的層次結(jié)構(gòu)。在該圖中，底層是計(jì)算智能（CI），它通過(guò)數(shù)值計(jì)算來(lái)實(shí)現(xiàn)，其基礎(chǔ)是CNN；中間層是人工智能（AI），它通過(guò)人造的符號(hào)系統(tǒng)實(shí)現(xiàn)，其基礎(chǔ)是ANN；頂層是生物智能（BI），它通過(guò)生物神經(jīng)系統(tǒng)來(lái)實(shí)現(xiàn)，其基礎(chǔ)是BNN。按照貝慈德克的觀點(diǎn)，CNN是指按生物激勵(lì)模型構(gòu)造的NN，ANN是指CNN+知識(shí)，BNN是指人腦，即ANN包含了CNN，BNN又包含了ANN。對(duì)智能也一樣，貝慈德克認(rèn)為AI包含了CI，BI又包含了AI，即計(jì)算智能是人工智能的一個(gè)子集。52.1.3計(jì)算智能與人工智能的關(guān)系目前，對(duì)計(jì)算智能CNNCPRCIANNAPRAIBNNBPRBI人類知識(shí)(+)傳感輸入知識(shí)(+)傳感數(shù)據(jù)計(jì)算(+)傳感器B~生物的A~符號(hào)的C~數(shù)值的復(fù)雜性復(fù)雜性輸入層次

貝慈德克的智能的3個(gè)層次2.1.3計(jì)算智能與人工智能的關(guān)系6CNNCPRCIANNAPRAIBNNBPRBI人類知識(shí)知識(shí)

第二種觀點(diǎn)是大多數(shù)學(xué)者所持有的觀點(diǎn)，其代表人物是艾伯哈特（R.C.Eberhart）。他們認(rèn)為：雖然人工智能與計(jì)算智能之間有重合，但計(jì)算智能是一個(gè)全新的學(xué)科領(lǐng)域，無(wú)論是生物智能還是機(jī)器智能，計(jì)算智能都是其最核心的部分，而人工智能則是外層。事實(shí)上，CI和傳統(tǒng)的AI只是智能的兩個(gè)不同層次，各自都有自身的優(yōu)勢(shì)和局限性，相互之間只應(yīng)該互補(bǔ)，而不能取代。大量實(shí)踐證明，只有把AI和CI很好地結(jié)合起來(lái)，才能更好地模擬人類智能，才是智能科學(xué)技術(shù)發(fā)展的正確方向。2.1.3計(jì)算智能與人工智能的關(guān)系7第二種觀點(diǎn)是大多數(shù)學(xué)者所持有的觀點(diǎn)，其代表人物是艾伯

2.1概述

2.2進(jìn)化計(jì)算

2.2.1進(jìn)化計(jì)算概述

2.3.2遺傳算法第2講計(jì)算智能之進(jìn)化計(jì)算82.1概述第2講計(jì)算智能之進(jìn)化計(jì)算8

進(jìn)化計(jì)算（EvolutionaryComputation,EC）是在達(dá)爾文（Darwin）的進(jìn)化論和孟德?tīng)枺∕endel）的遺傳變異理論的基礎(chǔ)上產(chǎn)生的一種在基因和種群層次上模擬自然界生物進(jìn)化過(guò)程與機(jī)制的問(wèn)題求解技術(shù)。它主要包括遺傳算法（GeneticAlgorithm，GA）進(jìn)化策略（EvolutionaryStrategy,ES）進(jìn)化規(guī)劃（EvolutionaryProgramming,EP）遺傳規(guī)劃（GeneticProgramming,GP）四大分支。其中，第一個(gè)分支是進(jìn)化計(jì)算中最初形成的一種具有普遍影響的模擬進(jìn)化優(yōu)化算法。因此我們主要討論遺傳算法。2.2進(jìn)化計(jì)算9進(jìn)化計(jì)算（EvolutionaryComputat

進(jìn)化計(jì)算是一種模擬自然界生物進(jìn)化過(guò)程與機(jī)制進(jìn)行問(wèn)題求解的自組織、自適應(yīng)的隨機(jī)搜索技術(shù)。它以達(dá)爾文進(jìn)化論的“物竟天擇、適者生存”作為算法的進(jìn)化規(guī)則，并結(jié)合孟德?tīng)柕倪z傳變異理論，將生物進(jìn)化過(guò)程中的繁殖（Reproduction）變異（Mutation）競(jìng)爭(zhēng)（Competition）選擇（Selection）引入到了算法中。2.2.1進(jìn)化計(jì)算概述1.進(jìn)化計(jì)算及其生物學(xué)基礎(chǔ)(1/3)(1)什么是進(jìn)化計(jì)算10進(jìn)化計(jì)算是一種模擬自然界生物進(jìn)化過(guò)程與機(jī)制進(jìn)行問(wèn)題(2)進(jìn)化計(jì)算的生物學(xué)基礎(chǔ)

自然界生物進(jìn)化過(guò)程是進(jìn)化計(jì)算的生物學(xué)基礎(chǔ)，它主要包括遺傳(Heredity)、變異(Mutation)和進(jìn)化(Evolution)理論。

①遺傳理論

遺傳是指父代（或親代）利用遺傳基因?qū)⒆陨淼幕蛐畔鬟f給下一代（或子代），使子代能夠繼承其父代的特征或性狀的這種生命現(xiàn)象。在自然界，構(gòu)成生物基本結(jié)構(gòu)與功能的單位是細(xì)胞（Cell）。細(xì)胞中含有一種包含著所有遺傳信息的復(fù)雜而又微小的絲狀化合物，人們稱其為染色體（Chromosome）。在染色體中，遺傳信息由基因（Gene）所組成，基因決定著生物的性狀，是遺傳的基本單位。染色體的形狀是一種雙螺旋結(jié)構(gòu)，構(gòu)成染色體的主要物質(zhì)叫做脫氧核糖核酸(DNA)，每個(gè)基因都在DNA長(zhǎng)鏈中占有一定的位置。一個(gè)細(xì)胞中的所有染色體所攜帶的遺傳信息的全體稱為一個(gè)基因組。2.2.1進(jìn)化計(jì)算概述1.進(jìn)化計(jì)算及其生物學(xué)基礎(chǔ)(2/3)11(2)進(jìn)化計(jì)算的生物學(xué)基礎(chǔ)2.2.1進(jìn)化計(jì)算概述11②變異理論

變異是指子代和父代之間，以及子代的各個(gè)不同個(gè)體之間產(chǎn)生差異的現(xiàn)象。變異是一種隨機(jī)、不可逆現(xiàn)象，是生物多樣性的基礎(chǔ)。

引起變異的主要原因：雜交，是指有性生殖生物在繁殖下一代時(shí)兩個(gè)同源染色體之間的交配重組。復(fù)制差錯(cuò)，是指在細(xì)胞復(fù)制過(guò)程中因DNA上某些基因結(jié)構(gòu)的隨機(jī)改變而產(chǎn)生出新的染色體。

③進(jìn)化論

進(jìn)化是指在生物延續(xù)生存過(guò)程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良的這種生命現(xiàn)象。遺傳和變異是生物進(jìn)化的兩種基本現(xiàn)象，優(yōu)勝劣汰、適者生存是生物進(jìn)化的基本規(guī)律。

達(dá)爾文的自然選擇學(xué)說(shuō)：在生物進(jìn)化中，一種基因有可能發(fā)生變異而產(chǎn)生出另一種新的基因。這種新基因?qū)⒁罁?jù)其與生存環(huán)境的適應(yīng)性而決定其增殖能力。通常，適應(yīng)性強(qiáng)的基因會(huì)不斷增多，而適應(yīng)性差的基因則會(huì)逐漸減少。通過(guò)這種自然選擇，物種將逐漸向適應(yīng)于生存環(huán)境的方向進(jìn)化，甚至?xí)葑兂蔀榱硪粋€(gè)新的物種，而那些不適應(yīng)于環(huán)境的物種將會(huì)逐漸被淘汰。2.2.1進(jìn)化計(jì)算概述1.進(jìn)化計(jì)算及其生物學(xué)基礎(chǔ)(3/3)12②變異理論2.2.1進(jìn)化計(jì)算概述12

進(jìn)化計(jì)算自20世紀(jì)50年代以來(lái)，其發(fā)展過(guò)程大致可分為三個(gè)階段。

(1)萌芽階段這一階段是從20世紀(jì)50年代后期到70年代中期。20世紀(jì)50年代后期，一些生物學(xué)家在研究如何用計(jì)算機(jī)模擬生物遺傳系統(tǒng)中，產(chǎn)生了遺傳算法的基本思想，并于1962年由美國(guó)密執(zhí)安（Michigan）大學(xué)霍蘭德（Holland）提出。1965年德國(guó)數(shù)學(xué)家雷切伯格（Rechenberg）等人提出了一種只有單個(gè)個(gè)體參與進(jìn)化，并且僅有變異這一種進(jìn)化操作的進(jìn)化策略。同年，美國(guó)學(xué)者弗格爾（Fogel）提出了一種具有多個(gè)個(gè)體和僅有變異一種進(jìn)化操作的進(jìn)化規(guī)劃。1969年美國(guó)密執(zhí)安（Michigan）大學(xué)的霍蘭德（Holland）提出了系統(tǒng)本身和外部環(huán)境相互協(xié)調(diào)的遺傳算法。至此，進(jìn)化計(jì)算的三大分支基本形成。

(2)成長(zhǎng)階段這一階段是從20世紀(jì)70年代中期到80年代后期。1975年，霍蘭德出版專著《自然和人工系統(tǒng)的適應(yīng)性（AdaptationinNaturalandArtificialSystem）》，全面介紹了遺傳算法。同年，德國(guó)學(xué)者施韋費(fèi)爾（Schwefel）在其博士論文中提出了一種由多個(gè)個(gè)體組成的群體參與進(jìn)化的，并且包括了變異和重組這兩種進(jìn)化操作的進(jìn)化策略。1989年，霍蘭德的學(xué)生戈?duì)柕虏瘢℅oldberg）博士出版專著《遺傳算法----搜索、優(yōu)化及機(jī)器學(xué)習(xí)（GeneticAlgorithm----inSearchOptimizationandMachineLearning）》，使遺傳算法得到了普及與推廣。2.2.1進(jìn)化計(jì)算概述2.進(jìn)化計(jì)算的產(chǎn)生與發(fā)展(1/2)13進(jìn)化計(jì)算自20世紀(jì)50年代以來(lái)，其發(fā)展過(guò)程大致可分(3)發(fā)展階段

這一階段是從20世紀(jì)90年代至今。1989年，美國(guó)斯坦福（Stanford）大學(xué)的科扎（Koza）提出了遺傳規(guī)劃的新概念，并于1992年出版了專著《遺傳規(guī)劃----應(yīng)用自然選擇法則的計(jì)算機(jī)程序設(shè)計(jì)（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》該書(shū)全面介紹了遺傳規(guī)劃的基本原理及應(yīng)用實(shí)例，標(biāo)志著遺傳規(guī)劃作為計(jì)算智能的一個(gè)分支已基本形成。進(jìn)入20世紀(jì)90年代以來(lái)，進(jìn)化計(jì)算得到了眾多研究機(jī)構(gòu)和學(xué)者的高度重視，新的研究成果不斷出現(xiàn)、應(yīng)用領(lǐng)域不斷擴(kuò)大。

2.2.1進(jìn)化計(jì)算概述2.進(jìn)化計(jì)算的產(chǎn)生與發(fā)展(2/2)14(3)發(fā)展階段2.2.1進(jìn)化計(jì)算概述14

進(jìn)化計(jì)算盡管有多個(gè)重要分支，但它們卻有著共同的進(jìn)化框架。若假設(shè)P為種群(Population，或稱為群體)，t為進(jìn)化代數(shù)，P(t)為第t代種群,則進(jìn)化計(jì)算的基本結(jié)構(gòu)可粗略描述如下：

{確定編碼形式并生成搜索空間；初始化各個(gè)進(jìn)化參數(shù)，并設(shè)置進(jìn)化代數(shù)t=0；初始化種群P(0);

對(duì)初始種群進(jìn)行評(píng)價(jià)（即適應(yīng)度計(jì)算）；

while（不滿足終止條件）do{t=t+1;

利用選擇操作從P(t-1)代中選出P(t)代群體；對(duì)P(t)代種群執(zhí)行進(jìn)化操作；對(duì)執(zhí)行完進(jìn)化操作后的種群進(jìn)行評(píng)價(jià)（即適應(yīng)度計(jì)算）；

}}

可以看出，上述基本結(jié)構(gòu)包含了生物進(jìn)化中所必需的選擇操作、進(jìn)化操作和適應(yīng)度評(píng)價(jià)等過(guò)程。2.2.1進(jìn)化計(jì)算概述3.進(jìn)化計(jì)算的基本結(jié)構(gòu)15進(jìn)化計(jì)算盡管有多個(gè)重要分支，但它們卻有著共同的進(jìn)化

遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者生存的自然法則選擇個(gè)體，并通過(guò)雜交、變異來(lái)產(chǎn)生新一代種群，如此逐代進(jìn)化，直到滿足目標(biāo)為止。遺傳算法所涉及到的基本概念主要有以下幾個(gè)：種群（Population）：種群是指用遺傳算法求解問(wèn)題時(shí)，初始給定的多個(gè)解的集合。遺傳算法的求解過(guò)程是從這個(gè)子集開(kāi)始的。個(gè)體（Individual）：個(gè)體是指種群中的單個(gè)元素，它通常由一個(gè)用于描述其基本遺傳結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)來(lái)表示。染色體（Chromos）：染色體是指對(duì)個(gè)體進(jìn)行編碼后所得到的編碼串。其中的每1位稱為基因，若干個(gè)基因構(gòu)成的一個(gè)有效信息段稱為基因組。適應(yīng)度（Fitness）函數(shù)：適應(yīng)度函數(shù)是一種用來(lái)對(duì)種群中各個(gè)個(gè)體的環(huán)境適應(yīng)性進(jìn)行度量的函數(shù)。遺傳操作（GeneticOperator）：遺傳操作是指作用于種群而產(chǎn)生新的種群的操作。標(biāo)準(zhǔn)的遺傳操作包括以下3種基本形式：選擇（Selection）交叉（Crosssover）變異（Mutation）2.2.2遺傳算法1.遺傳算法的基本概念16遺傳算法的基本思想是從初始種群出發(fā)，采用優(yōu)勝劣汰、適者

遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)設(shè)定、遺傳操作設(shè)計(jì)等幾大部分所組成，其算法主要內(nèi)容和基本步驟可描述如下：

(1)選擇編碼策略，將問(wèn)題搜索空間中每個(gè)可能的點(diǎn)用相應(yīng)的編碼策略表示出來(lái)，即形成染色體；

(2)定義遺傳策略，包括種群規(guī)模N，交叉、變異方法，以及選擇概率Pr、交叉概率Pc、變異概率Pm等遺傳參數(shù)；

(3)令t=0，隨機(jī)選擇N個(gè)染色體初始化種群P(0)；

(4)定義適應(yīng)度函數(shù)f（f>0）；

(5)計(jì)算P(t)中每個(gè)染色體的適應(yīng)值；

(6)t=t+1；

(7)運(yùn)用選擇算子，從P(t-1)中得到P(t)；

(8)對(duì)P(t)中的每個(gè)染色體，按概率Pc參與交叉；

(9)對(duì)染色體中的基因，以概率Pm參與變異運(yùn)算；

(10)判斷群體性能是否滿足預(yù)先設(shè)定的終止標(biāo)準(zhǔn)，若不滿足則返回(5)。2.2.2遺傳算法2.遺傳算法的基本過(guò)程(1/2)17遺傳算法主要由染色體編碼、初始種群設(shè)定、適應(yīng)度函數(shù)計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度，并進(jìn)行評(píng)價(jià)滿足終止條件嗎？終止選擇交叉變異Y圖2-18基本遺傳算法的算法流程圖編碼和生成初始種群N選擇

其算法流程如圖2-18所示。2.2.2遺傳算法2.遺傳算法的基本結(jié)構(gòu)(2/2)18計(jì)算種群中各個(gè)個(gè)體的適應(yīng)度，并進(jìn)行評(píng)價(jià)滿足終止條件嗎？終止選

常用的遺傳編碼算法有霍蘭德二進(jìn)制碼、格雷碼（GrayCode）、實(shí)數(shù)編碼和字符編碼等。(1)二進(jìn)制編碼（Binaryencoding）

二進(jìn)制編碼是將原問(wèn)題的結(jié)構(gòu)變換為染色體的位串結(jié)構(gòu)。在二進(jìn)制編碼中，首先要確定二進(jìn)制字符串的長(zhǎng)度l，該長(zhǎng)度與變量的定義域和所求問(wèn)題的計(jì)算精度有關(guān)。例5.5

假設(shè)變量x的定義域?yàn)閇5，10]，要求的計(jì)算精度為10-5，則需要將[5，10]至少分為6×105個(gè)等長(zhǎng)小區(qū)間，每個(gè)小區(qū)間用一個(gè)二進(jìn)制串表示。于是，串長(zhǎng)至少等于20，原因是：

524288=219<600000<220=1048576這樣，對(duì)應(yīng)于區(qū)間[5，10]內(nèi)滿足精度要求的每個(gè)值x，都可用一個(gè)20位編碼的二進(jìn)制串<b19,b18,…,b0>來(lái)表示。

二進(jìn)制編碼存在的主要缺點(diǎn)是漢明（Hamming）懸崖。例如，7和8的二進(jìn)制數(shù)分別為0111和1000，當(dāng)算法從7改進(jìn)到8時(shí)，就必須改變所有的位。

2.2.2遺傳算法3.遺傳編碼(1/3)19常用的遺傳編碼算法有霍蘭德二進(jìn)制碼、格雷碼（Gray2.2.2遺傳算法3.遺傳編碼(2/3)(2)格雷編碼（Grayencoding）

格雷編碼是對(duì)二進(jìn)制編碼進(jìn)行變換后所得到的一種編碼方法。這種編碼方法要求兩個(gè)連續(xù)整數(shù)的編碼之間只能有一個(gè)碼位不同，其余碼位都是完全相同的。它有效地解決了漢明懸崖問(wèn)題，其基本原理如下：設(shè)有二進(jìn)制串b1,b2,…,bn，對(duì)應(yīng)的格雷串為a1,a2,…,an，則從二進(jìn)制編碼到格雷編碼的變換為：

(2.9)其中，⊕表示模2加法（等同于異或運(yùn)算）。而從一個(gè)格雷串到二進(jìn)制串的變換為：

(2.10)

例2.6

十進(jìn)制數(shù)7和8的二進(jìn)制編碼分別為0111和1000，而其格雷編碼分別為0100和1100。202.2.2遺傳算法(2)格雷編碼（Grayencodi(3)實(shí)數(shù)編碼（Realencoding）

實(shí)數(shù)編碼是將每個(gè)個(gè)體的染色體都用某一范圍的一個(gè)實(shí)數(shù)（浮點(diǎn)數(shù)）來(lái)表示，其編碼長(zhǎng)度等于該問(wèn)題變量的個(gè)數(shù)。這種編碼方法是將問(wèn)題的解空間映射到實(shí)數(shù)空間上，然后在實(shí)數(shù)空間上進(jìn)行遺傳操作。由于實(shí)數(shù)編碼使用的是變量的真實(shí)值，因此這種編碼方法也叫做真值編碼方法。實(shí)數(shù)編碼適應(yīng)于那種多維、高精度要求的連續(xù)函數(shù)優(yōu)化問(wèn)題。

2.2.2遺傳算法3.遺傳編碼(3/3)21(3)實(shí)數(shù)編碼（Realencoding）2.2.2遺

適應(yīng)度函數(shù)是一個(gè)用于對(duì)個(gè)體的適應(yīng)性進(jìn)行度量的函數(shù)。通常，一個(gè)個(gè)體的適應(yīng)度值越大，它被遺傳到下一代種群中的概率也就越大。(1)常用的適應(yīng)度函數(shù)

在遺傳算法中，有許多計(jì)算適應(yīng)度的方法，其中最常用的適應(yīng)度函數(shù)有以下兩種：

①原始適應(yīng)度函數(shù)它是直接將待求解問(wèn)題的目標(biāo)函數(shù)f(x)定義為遺傳算法的適應(yīng)度函數(shù)。例如，在求解極值問(wèn)題時(shí)，f(x)即為x的原始適應(yīng)度函數(shù)。采用原始適應(yīng)度函數(shù)的優(yōu)點(diǎn)是能夠直接反映出待求解問(wèn)題的最初求解目標(biāo)，其缺點(diǎn)是有可能出現(xiàn)適應(yīng)度值為負(fù)的情況。

2.2.2遺傳算法4.適應(yīng)度函數(shù)(1/5)22適應(yīng)度函數(shù)是一個(gè)用于對(duì)個(gè)體的適應(yīng)性進(jìn)行度量的函數(shù)。②標(biāo)準(zhǔn)適應(yīng)度函數(shù)在遺傳算法中，一般要求適應(yīng)度函數(shù)非負(fù)，并其適應(yīng)度值越大越好。這就往往需要對(duì)原始適應(yīng)函數(shù)進(jìn)行某種變換，將其轉(zhuǎn)換為標(biāo)準(zhǔn)的度量方式，以滿足進(jìn)化操作的要求，這樣所得到的適應(yīng)度函數(shù)被稱為標(biāo)準(zhǔn)適應(yīng)度函數(shù)fNormal(x)。例如下面的極小化和極大化問(wèn)題：極小化問(wèn)題對(duì)極小化問(wèn)題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為

(2.11)其中，fmax(x)是原始適應(yīng)函數(shù)f(x)的一個(gè)上界。如果fmax(x)未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最大值來(lái)代替?？梢?jiàn)，fmax(x)是會(huì)隨著進(jìn)化代數(shù)的增加而不斷變化的。

2.2.2遺傳算法4.適應(yīng)度函數(shù)(2/5)23②標(biāo)準(zhǔn)適應(yīng)度函數(shù)2.2.2遺傳算法23

極大化問(wèn)題對(duì)極大化問(wèn)題，其標(biāo)準(zhǔn)適應(yīng)度函數(shù)可定義為

(2.12)其中，fmin(x)是原始適應(yīng)函數(shù)f(x)的一個(gè)下界。如果fmin(x)未知，則可用當(dāng)前代或到目前為止各演化代中的f(x)的最小值來(lái)代替。

2.2.2遺傳算法4.適應(yīng)度函數(shù)(3/5)24極大化問(wèn)題2.2.2遺傳算法24(2)適應(yīng)度函數(shù)的加速變換在某些情況下，需要對(duì)適應(yīng)度函數(shù)進(jìn)行加速速度。適應(yīng)度函數(shù)的加速變換有兩種基本方法線性加速的適應(yīng)度函數(shù)的定義如下：

f’(x)=αf(x)+β其中，f(x)是加速轉(zhuǎn)換前的適應(yīng)度函數(shù)；f’(x)是加速轉(zhuǎn)換后的適應(yīng)度函數(shù)；α和β是轉(zhuǎn)換系數(shù),它們應(yīng)滿足如下條件：

①變化后得到的新的適應(yīng)度函數(shù)平均值要等于原適應(yīng)度函數(shù)的平均值。即

（2.13）其中，xi(i=1,…,n)為當(dāng)前代中的染色體。2.2.2遺傳算法4.適應(yīng)度函數(shù)(4/5)25(2)適應(yīng)度函數(shù)的加速變換2.2.2遺傳算法25

②變換后所得到的新的種群個(gè)體所具有的最大適應(yīng)度要等于其平均適應(yīng)度的指數(shù)倍數(shù)。即有關(guān)系：（2.14）式中，xi(i=1,…,n)為當(dāng)前代中的染色體，M是指將當(dāng)前的最大適應(yīng)度放大為平均值的M倍。目的是通過(guò)M拉開(kāi)不同染色體適應(yīng)度值的差距。非線性加速冪函數(shù)變換方法

f’(x)=f(x)k(2.15)

指數(shù)變換方法

f’(x)=exp(βf(x))(2.16)2.2.2遺傳算法4.適應(yīng)度函數(shù)(5/5)26②變換后所得到的新的種群個(gè)體所具有的最大適應(yīng)度要等于

遺傳算法中的基本遺傳操作包括選擇、交叉和變異3種，而每種操作又包括多種不同的方法，下面分別對(duì)它們進(jìn)行介紹。(1).選擇操作

選擇（Selection）操作是指根據(jù)選擇概率按某種策略從當(dāng)前種群中挑選出一定數(shù)目的個(gè)體，使它們能夠有更多的機(jī)會(huì)被遺傳到下一代中。常用的選擇策略可分為比例選擇、排序選擇和競(jìng)技選擇三種類型。

①比例選擇

比例選擇方法（ProportionalModel）的基本思想是：各個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。常用的比例選擇策略包括輪盤(pán)賭選擇繁殖池選擇2.2.2遺傳算法5.基本遺傳操作(1/11)27遺傳算法中的基本遺傳操作包括選擇、交叉和變異3種，而②輪盤(pán)賭選擇

輪盤(pán)賭選擇法又被稱為轉(zhuǎn)盤(pán)賭選擇法或輪盤(pán)選擇法。在這種方法中，個(gè)體被選中的概率取決于該個(gè)體的相對(duì)適應(yīng)度。而相對(duì)適應(yīng)度的定義為：其中，P(xi)是個(gè)體xi的相對(duì)適應(yīng)度，即個(gè)體xi被選中的概率；f(xi)是個(gè)體xi的原始適應(yīng)度。輪盤(pán)賭選擇算法的基本思想是：根據(jù)每個(gè)個(gè)體的選擇概率P(xi)將一個(gè)圓盤(pán)分成N個(gè)扇區(qū)，其中第i個(gè)扇區(qū)的中心角為：再設(shè)立一個(gè)移動(dòng)指針，將圓盤(pán)的轉(zhuǎn)動(dòng)等價(jià)為指針的移動(dòng)。選擇時(shí)，假想轉(zhuǎn)動(dòng)圓盤(pán)，若靜止時(shí)指針指向第i個(gè)扇區(qū)，則選擇個(gè)體i。其物理意義如圖2-19所示。2.2.2遺傳算法5.基本遺傳操作(2/11)28②輪盤(pán)賭選擇2.2.2遺傳算法28P(x1)P(x2)P(xN)……P(xi)2πp(xi)圖2-19輪盤(pán)賭選擇

從統(tǒng)計(jì)角度看，個(gè)體的適應(yīng)度值越大，其對(duì)應(yīng)的扇區(qū)的面積越大，被選中的可能性也越大。這種方法有點(diǎn)類似于發(fā)放獎(jiǎng)品使用的輪盤(pán)，并帶有某種賭博的意思，因此亦被稱為輪盤(pán)賭選擇。2.2.2遺傳算法5.基本遺傳操作(3/11)29P(x1)P(x2)P(xN)……P(xi)圖2-19輪盤(pán)(2)交叉操作

交叉（Crossover）操作是指按照某種方式對(duì)選擇的父代個(gè)體的染色體的部分基因進(jìn)行交配重組，從而形成新的個(gè)體。交配重組是自然界中生物遺傳進(jìn)化的一個(gè)主要環(huán)節(jié)，也是遺傳算法中產(chǎn)生新的個(gè)體的最主要方法。根據(jù)個(gè)體編碼方法的不同，遺傳算法中的交叉操作可分為二進(jìn)制交叉和實(shí)值交叉兩種類型。

①二進(jìn)制交叉

二進(jìn)制交叉（BinaryValuedCrossover）是指二進(jìn)制編碼情況下所采用的交叉操作，它主要包括單點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和均勻交叉等方法。2.2.2遺傳算法5.基本遺傳操作(4/11)30(2)交叉操作2.2.2遺傳算法30

單點(diǎn)交叉

單點(diǎn)交叉也稱簡(jiǎn)單交叉，它是先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定一個(gè)交叉點(diǎn)，然后對(duì)這兩個(gè)父代個(gè)體交叉點(diǎn)前面或后面部分的基因進(jìn)行交換，并生成子代中的兩個(gè)新的個(gè)體。假設(shè)兩個(gè)父代的個(gè)體串分別是：

X=x1x2…xkxk+1…xnY=y1y2…ykyk+1…yn

隨機(jī)選擇第k位為交叉點(diǎn)，若采用對(duì)交叉點(diǎn)后面的基因進(jìn)行交換的方法，但點(diǎn)交叉是將X中的xk+1到xn部分與Y中的yk+1到y(tǒng)n部分進(jìn)行交叉，交叉后生成的兩個(gè)新的個(gè)體是：

X’=x1x2…xk

yk+1…yn

Y’=y1y2…yk

xk+1…xn

例2.7

設(shè)有兩個(gè)父代的個(gè)體串A=001101

和B=110010

，若隨機(jī)交叉點(diǎn)為4，則交叉后生成的兩個(gè)新的個(gè)體是：A’=001110

B’=110001

2.2.2遺傳算法5.基本遺傳操作(5/11)31單點(diǎn)交叉2.2.2遺傳算法31

兩點(diǎn)交叉

兩點(diǎn)交叉是指先在兩個(gè)父代個(gè)體的編碼串中隨機(jī)設(shè)定兩個(gè)交叉點(diǎn)，然后再按這兩個(gè)交叉點(diǎn)進(jìn)行部分基因交換，生成子代中的兩個(gè)新的個(gè)體。假設(shè)兩個(gè)父代的個(gè)體串分別是：

X=x1x2…xi…xj…xnY=y1y2…yi…yj…,yn

隨機(jī)設(shè)定第i、j位為兩個(gè)交叉點(diǎn)（其中i<j<n），兩點(diǎn)交叉是將X中的xi+1到xj部分與Y中的yi+1到y(tǒng)j部分進(jìn)行交換，交叉后生成的兩個(gè)新的個(gè)體是：

X’=x1x2…xi

yi+1…yjxj+1…xn

Y’=y1y2…yi

xi+1

…

xjyj+1…yn

例2.8

設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，若隨機(jī)交叉點(diǎn)為3和5，則交叉后的兩個(gè)新的個(gè)體是：A’=001011B’=1101002.2.2遺傳算法5.基本遺傳操作(6/11)32兩點(diǎn)交叉2.2.2遺傳算法32

多點(diǎn)交叉多點(diǎn)交是指先隨機(jī)生成多個(gè)交叉點(diǎn)，然后再按這些交叉點(diǎn)分段地進(jìn)行部分基因交換，生成子代中的兩個(gè)新的個(gè)體。假設(shè)交叉點(diǎn)個(gè)數(shù)為m，則可將個(gè)體串劃分為m+1個(gè)分段，其劃分方法是：當(dāng)m為偶數(shù)時(shí)，對(duì)全部交叉點(diǎn)依次進(jìn)行兩兩配對(duì)，構(gòu)成m/2個(gè)交叉段。當(dāng)m為奇數(shù)時(shí)，對(duì)前(m-1)個(gè)交叉點(diǎn)依次進(jìn)行兩兩配對(duì)，構(gòu)成(m-1)/2個(gè)交叉段，而第m個(gè)交叉點(diǎn)則按單點(diǎn)交叉方法構(gòu)成一個(gè)交叉段。下面以m=3為例進(jìn)行討論。假設(shè)兩個(gè)父代的個(gè)體串分別是X=x1x2…xi…xj…xk…xn和Y=y1y2…yi…yj…yk…yn，隨機(jī)設(shè)定第i、j、k位為三個(gè)交叉點(diǎn)（其中i<j<k<n），則將構(gòu)成兩個(gè)交叉段。交叉后生成的兩個(gè)新的個(gè)體是：

X’=x1x2…xiyi+1…yj

xj+1…xk

yk+1…yn

Y’=y1y2…yi

xi+1…xjyj+1…yk

xk+1…xn

例2.9

設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，若隨機(jī)交叉點(diǎn)為1、3和5，則交叉后的兩個(gè)新的個(gè)體是：A’=010100

B’=101011

2.2.2遺傳算法5.基本遺傳操作(7/11)33多點(diǎn)交叉2.2.2遺傳算法33

均勻交叉均勻交叉（UniformCrossover）是先隨機(jī)生成一個(gè)與父串具有相同長(zhǎng)度，并被稱為交叉模版（或交叉掩碼）的二進(jìn)制串，然后再利用該模版對(duì)兩個(gè)父串進(jìn)行交叉，即將模版中1對(duì)應(yīng)的位進(jìn)行交換，而0對(duì)應(yīng)的位不交換，依此生成子代中的兩個(gè)新的個(gè)體。事實(shí)上，這種方法對(duì)父串中的每一位都是以相同的概率隨機(jī)進(jìn)行交叉的。例2.10

設(shè)有兩個(gè)父代的個(gè)體串A=001101和B=110010，若隨機(jī)生成的模版T=010011，則交叉后的兩個(gè)新的個(gè)體是A’=011010和B’=100101。即

A：001101B：110010T：010011A’：01111

0

B’：10000

12.2.2遺傳算法5.基本遺傳操作(8/11)34均勻交叉2.2.2遺傳算法34②實(shí)值交叉實(shí)值交叉是在實(shí)數(shù)編碼情況下所采用的交叉操作，主要包括離散交叉和算術(shù)交叉，下面主要討論離散交叉（部分離散交叉和整體離散交叉）。部分離散交叉是先在兩個(gè)父代個(gè)體的編碼向量中隨機(jī)選擇一部分分量，然后對(duì)這部分分量進(jìn)行交換，生成子代中的兩個(gè)新的個(gè)體。整體交叉則是對(duì)兩個(gè)父代個(gè)體的編碼向量中的所有分量，都以1/2的概率進(jìn)行交換，從而生成子代中的兩個(gè)新的個(gè)體。以部分離散交叉為例，假設(shè)兩個(gè)父代個(gè)體的n維實(shí)向量分別是X=x1x2…xi…xk…xn和Y=y1y2…yi…yk…yn，若隨機(jī)選擇對(duì)第k個(gè)分量以后的所有分量進(jìn)行交換，則生成的兩個(gè)新的個(gè)體向量是：

X’=x1x2…xk

yk+1…ynY’=y1y2…yk

xk+1…xn例2.11

設(shè)有兩個(gè)父代個(gè)體向量A=201619321826和B=362538122130，若隨機(jī)選擇對(duì)第3個(gè)分量以后的所有分量進(jìn)行交叉，則交叉后兩個(gè)新的個(gè)體向量是：A’=20161912

21

30B’=36253832

18

26

2.2.2遺傳算法5.基本遺傳操作(9/11)35②實(shí)值交叉2.2.2遺傳算法35

(3)變異操作

變異（Mutation）是指對(duì)選中個(gè)體的染色體中的某些基因進(jìn)行變動(dòng)，以形成新的個(gè)體。變異也是生物遺傳和自然進(jìn)化中的一種基本現(xiàn)象，它可增強(qiáng)種群的多樣性。遺傳算法中的變異操作增加了算法的局部隨機(jī)搜索能力，從而可以維持種群的多樣性。根據(jù)個(gè)體編碼方式的不同，變異操作可分為二進(jìn)制變異和實(shí)值變異兩種類型。

①二進(jìn)制變異當(dāng)個(gè)體的染色體采用二進(jìn)制編碼表示時(shí)，其變異操作應(yīng)采用二進(jìn)制變異方法。該變異方法是先隨機(jī)地產(chǎn)生一個(gè)變異位，然后將該變異位置上的基因值由“0”變?yōu)椤?”，或由“1”變?yōu)椤?”，產(chǎn)生一個(gè)新的個(gè)體。例2.12

設(shè)變異前的個(gè)體為A=001101，若隨機(jī)產(chǎn)生的變異位置是2，則該個(gè)體的第2位由“0”變?yōu)椤?”。變異后的新的個(gè)體是A’=011101。2.2.2遺傳算法5.基本遺傳操作(10/11)36(3)變異操作2.2.2遺傳算法36

②實(shí)值變異當(dāng)個(gè)體的染色體采用實(shí)數(shù)編碼表示時(shí)，其變異操作應(yīng)采用實(shí)值變異方法。該方法是用另外一個(gè)在規(guī)定范圍內(nèi)的隨機(jī)實(shí)數(shù)去替換原變異位置上的基因值，產(chǎn)生一個(gè)新的個(gè)體。最常用的實(shí)值變異操作有:

基于位置的變異方法該方法是先隨機(jī)地產(chǎn)生兩個(gè)變異位置，然后將第二個(gè)變異位置上的基因移動(dòng)到第一個(gè)變異位置的前面。例2.13

設(shè)選中的個(gè)體向量C=201619122130，若隨機(jī)產(chǎn)生的兩個(gè)變異位置分別時(shí)2和4，則變異后的新的個(gè)體向量是：C’=2012

16192130基于次序的變異該方法是先隨機(jī)地產(chǎn)生兩個(gè)變異位置，然后交換這兩個(gè)變異位置上的基因。例2.14

設(shè)選中的個(gè)體向量D=201216192130，若隨機(jī)產(chǎn)生的兩個(gè)變異位置分別時(shí)2和4，則變異后的新的個(gè)體向量是：D’=2019161221302.2.2遺傳算法5.基本遺傳操作(11/11)37②實(shí)值變異2.2.2遺傳算法37例2.15

用遺傳算法求函數(shù)

f(x)=x2的最大值，其中x為[0，31]間的整數(shù)。解：這個(gè)問(wèn)題本身比較簡(jiǎn)單，其最大值很顯然是在x=31處。但作為一個(gè)例子，它有著較好的示范性和可理解性。按照遺傳算法，其求解過(guò)程如下：(1)編碼

由于x的定義域是區(qū)間[0，31]上的整數(shù)，由5位二進(jìn)制數(shù)即可全部表示。因此，可采用二進(jìn)制編碼方法，其編碼串的長(zhǎng)度為5。例如，用二進(jìn)制串00000來(lái)表示x=0,11111來(lái)表示x=31等。其中的0和1為基因值。

(2)生成初始種群

若假設(shè)給定的種群規(guī)模N=4，則可用4個(gè)隨機(jī)生成的長(zhǎng)度為5的二進(jìn)制串作為初始種群。再假設(shè)隨機(jī)生成的初始種群（即第0代種群）為：

s01=01101s02=11001s03=01000s04=100102.2.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(1/10)38例2.15用遺傳算法求函數(shù)2.2.2遺傳算法38(3)計(jì)算適應(yīng)度

要計(jì)算個(gè)體的適應(yīng)度，首先應(yīng)該定義適應(yīng)度函數(shù)。由于本例是求f(x)的最大值，因此可直接用f(x)來(lái)作為適應(yīng)度函數(shù)。即：

f(s)=f(x)其中的二進(jìn)制串s對(duì)應(yīng)著變量x的值。根據(jù)此函數(shù)，初始種群中各個(gè)個(gè)體的適應(yīng)值及其所占比例如表2-5所示。表2-5初始種群情況表編號(hào)個(gè)體串（染色體）x適應(yīng)值百分比%累計(jì)百分比%選中次數(shù)S01011011316914.3014.301S02110012562552.8867.182S03010008645.4172.590S04100101832427.4110012.2.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(2/10)可以看出，在4個(gè)個(gè)體中S02的適應(yīng)值最大，是當(dāng)前最佳個(gè)體。39(3)計(jì)算適應(yīng)度編號(hào)個(gè)體串（染色體）x適應(yīng)值百分比(4)選擇操作

假設(shè)采用輪盤(pán)賭方式選擇個(gè)體，且依次生成的4個(gè)隨機(jī)數(shù)（相當(dāng)于輪盤(pán)上指針?biāo)傅臄?shù)）為0.85、0.32、0.12和0.46，經(jīng)選擇后得到的新的種群為：

S’01=10010S’02=11001S’03=01101S’04=11001其中，染色體11001在種群中出現(xiàn)了2次，而原染色體01000則因適應(yīng)值太小而被淘汰2.2.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(3/10)40(4)選擇操作2.2.2遺傳算法40(5)交叉

假設(shè)交叉概率Pi為50%，則種群中只有1/2的染色體參與交叉。若規(guī)定種群中的染色體按順序兩兩配對(duì)交叉，且有S’01與S’02交叉，S’03與S’04不交叉，則交叉情況如表2-6所示。表2-6初始種群的交叉情況表編號(hào)個(gè)體串（染色體）交叉對(duì)象交叉位子代適應(yīng)值S’0110010S’02310001289S’0211001S’01311010676S’0301101S’04N01101169S’0411001S’03N110016252.2.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(4/10)可見(jiàn)，經(jīng)交叉后得到的新的種群為：S’’01=10001S’’02=11010S’’03=01101S’’04=1100141(5)交叉編號(hào)個(gè)體串（染色體）交叉對(duì)象交叉位子

(6)變異

變異概率Pm一般都很小，假設(shè)本次循環(huán)中沒(méi)有發(fā)生變異，則變異前的種群即為進(jìn)化后所得到的第1代種群。即：

S11=10001S12=11010S13=01101S14=11001然后，對(duì)第1代種群重復(fù)上述(4)-(6)的操作

2.2.2遺傳算法6.遺傳算法應(yīng)用簡(jiǎn)例(5/10)42(6)變異2.2.2遺傳算法42

其中若假設(shè)按輪盤(pán)賭選擇時(shí)依次生成的4個(gè)隨機(jī)數(shù)為0.14、0.51、0.24和0.82，經(jīng)選擇后得到的新的種群為：

S’11=10001S’12=11010S’13=11010S’14