遺傳算法又叫GA算法

關(guān)于遺傳算法又叫GA算法

自然界充滿了奇跡與生機(jī)，而生命的繁衍更是奇妙無(wú)窮。人類之所以能夠向其自身的演化學(xué)習(xí)以增強(qiáng)決策問(wèn)題的能力，是因?yàn)樽匀谎莼^(guò)程本質(zhì)就是一個(gè)學(xué)習(xí)與優(yōu)化的過(guò)程。這一優(yōu)化過(guò)程的目的是使生命體達(dá)到適應(yīng)環(huán)境的最佳結(jié)構(gòu)與效果。§1.1遺傳算法的起源及生物學(xué)基礎(chǔ)第2頁(yè),共37頁(yè)，2024年2月25日，星期天

曾經(jīng)主宰地球的恐龍由于龐大的身軀跟不上環(huán)境的變遷而滅絕；長(zhǎng)頸鹿為了覓食而長(zhǎng)長(zhǎng)了脖子；老鼠的機(jī)敏是為了生存而掙扎的結(jié)果；青蛙的存活則得益于其兩棲式左右逢源的能力；人類解放出有力的雙手，得益于類人猿求生的努力，而正是這一對(duì)與其它動(dòng)物的不同的、不再用于進(jìn)行行走的雙手，使人類成了這個(gè)世界的主宰。自然演化遵循著一種奇妙的規(guī)律，這就是達(dá)爾文發(fā)現(xiàn)的自然演化規(guī)律：物竟天擇，適者生存。第3頁(yè),共37頁(yè)，2024年2月25日，星期天

自然界特別是生物界神奇的進(jìn)化過(guò)程是一個(gè)不斷優(yōu)化的過(guò)程。近代基因遺傳工程的研究成果正在不斷揭示著這一過(guò)程的本質(zhì)機(jī)理。人們?yōu)槭裁床荒軒煼ù笞匀唬焉飳W(xué)進(jìn)化的一些基本概念和機(jī)理引伸到工程問(wèn)題的研究中來(lái)呢？1975年，Holland提出了建立基因遺傳優(yōu)化的計(jì)算機(jī)仿真——遺傳算法的基本概念和技巧，其本意是在人工適應(yīng)系統(tǒng)中設(shè)計(jì)的一種基于自然演化原理搜索機(jī)制。

第4頁(yè),共37頁(yè)，2024年2月25日，星期天

遺傳算法是基于自然選擇和遺傳機(jī)制，在計(jì)算機(jī)上模擬自然界生物進(jìn)化過(guò)程與機(jī)制的尋優(yōu)搜索仿生智能算法，它模擬的機(jī)制是一切生命與智能的產(chǎn)生與進(jìn)化過(guò)程。它模擬達(dá)爾文的自然演化規(guī)律的原理激勵(lì)好的結(jié)構(gòu)，模擬孟德?tīng)柕倪z傳變異理論在迭代過(guò)程中保持已有的結(jié)構(gòu)，同時(shí)尋找更好的結(jié)構(gòu)。它是一類自組織、自適應(yīng)人工智能技術(shù)。

第5頁(yè),共37頁(yè)，2024年2月25日，星期天

自然界的生物從其父代繼承特征或性狀，這種生命現(xiàn)象稱之為遺傳（Heredity），研究這種生命現(xiàn)象與機(jī)理的科學(xué)即為遺傳學(xué)（Genetics）。由于有遺傳作用，自然界才有穩(wěn)定的物種，人們種瓜得瓜，種豆得豆，之所以魚至今還仍然會(huì)在水中遨游，鳥仍然在天空中飛翔都是這個(gè)緣由。自然界之所以穩(wěn)定有序，持久永恒，而非天翻地覆，恐怕也得益于這一點(diǎn)。第6頁(yè),共37頁(yè)，2024年2月25日，星期天

構(gòu)成生物的基本結(jié)構(gòu)與功能單位是細(xì)胞(Cell).細(xì)胞中的一種微小的絲狀化合物稱為染色體（Chromosome），生物的所有遺傳信息都包含在這個(gè)復(fù)雜而又微小的染色體中。遺傳信息是由基因（Gene）組成的，生物的各種性狀由其相應(yīng)的基因所決定，基因是遺傳的基本單位。細(xì)胞通過(guò)分裂具有自我復(fù)制的能力，在細(xì)胞分裂過(guò)程中，其遺傳基因也同時(shí)被復(fù)制到下一代，從而其性狀也被下一代所繼承。第7頁(yè),共37頁(yè)，2024年2月25日，星期天

遺傳學(xué)認(rèn)為，遺傳是作為一種指令遺傳碼封裝在每個(gè)細(xì)胞中，并以基因的形式包含在染色體中，每個(gè)基因有其特殊的位置并控制某個(gè)特殊的性質(zhì)，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境有一定的適應(yīng)性。細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過(guò)復(fù)制（Reproduction）而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新細(xì)胞就繼承了舊細(xì)胞的基因。這正是子代與父代相象的主要原因所在。另外，在進(jìn)行細(xì)胞復(fù)制時(shí)，雖然概率很小，但也可能產(chǎn)生某些復(fù)制差錯(cuò)，從而使DNA中的某些基因發(fā)生變異（Mutation），產(chǎn)生出新的染色體。這正是為什么子代與父代相象，但又不是完全一樣的緣故。否則，就不叫遺傳，恐怕是克隆（Clone）了。這些新的染色體表現(xiàn)出新的性狀。如此這般，遺傳基因或染色體在遺傳過(guò)程中由于各種各樣的原因而發(fā)生變化。第8頁(yè),共37頁(yè)，2024年2月25日，星期天

生物在其延續(xù)生存的過(guò)程中，逐漸適應(yīng)于其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化（Evolution）。生物的進(jìn)化是以集團(tuán)的形式共同進(jìn)行的，這樣的團(tuán)體稱為種群或群體（Population），組成種群的單個(gè)生物稱為個(gè)體（Individual）。每一個(gè)生物個(gè)體對(duì)其生存環(huán)境都有不同的適應(yīng)能力，這種能力稱為個(gè)體的適應(yīng)度（Fitness）。達(dá)爾文的自然選擇學(xué)說(shuō)認(rèn)為，通過(guò)不同生物間的交配以及其他一些原因，生物的基因有可能發(fā)生變異而生成一種新的生物基因，這部分變異了的基因也將遺傳到下一代。盡管這種變化的概率可以預(yù)測(cè)，但具體哪一個(gè)個(gè)體發(fā)生變化卻是偶然的。第9頁(yè),共37頁(yè)，2024年2月25日，星期天這種新的基因根據(jù)其與環(huán)境的適應(yīng)程度決定其增殖能力，有利于生存環(huán)境的基因逐漸增多，而不利于生存環(huán)境的基因逐漸減少。借助于這種自然的選擇機(jī)制，物種將逐漸地向適應(yīng)于生存環(huán)境的方向進(jìn)化，從而產(chǎn)生出越來(lái)越適應(yīng)環(huán)境的物種。不適應(yīng)環(huán)境的物種，也會(huì)逐漸滅絕，銷聲匿跡。這就是“物竟天擇，適者生存”的原理。第10頁(yè),共37頁(yè)，2024年2月25日，星期天人們對(duì)遺傳與進(jìn)化的特征已形成了如下的共識(shí)：1．染色體中包含了生物的所有遺傳信息（基因），染色體決定個(gè)體的生物特征（表現(xiàn)型），而表現(xiàn)型決定個(gè)體對(duì)環(huán)境的適應(yīng)度。2．可以認(rèn)為生物體的基因在染色體上呈線性排列，所有遺傳與進(jìn)化過(guò)程均發(fā)生在染色體上。3．生物的繁殖是由其基因的復(fù)制來(lái)完成的，交叉重組是有性繁殖的基因復(fù)制的基本形式。4．同源染色體之間的交叉或染色體上基因的變異（突變）產(chǎn)生新的物種，使生物體呈現(xiàn)新的性狀，變異是物種進(jìn)化的根本保證。第11頁(yè),共37頁(yè)，2024年2月25日，星期天5．自然依據(jù)個(gè)體生物的適應(yīng)度決定其在種群中是否存活，對(duì)環(huán)境適應(yīng)性強(qiáng)的基因或染色體經(jīng)常比適應(yīng)性差的基因或染色體具有更多的機(jī)會(huì)遺傳到下一代。6．競(jìng)爭(zhēng)存在于生物種群以及種群與種群之間，競(jìng)爭(zhēng)是規(guī)模無(wú)限擴(kuò)大趨勢(shì)的生物分享有限資源的直接結(jié)果，是物種進(jìn)化的促進(jìn)劑。7．有競(jìng)爭(zhēng)必然有選擇，自然選擇是生物進(jìn)化的最基本規(guī)律。第12頁(yè),共37頁(yè)，2024年2月25日，星期天§1.2遺傳算法的基本原理

遺傳算法是基于自然選擇和遺傳機(jī)制，在計(jì)算機(jī)上模擬生物進(jìn)化機(jī)制的尋優(yōu)搜索仿生智能算法，它模擬的機(jī)制是一切生命與智能的產(chǎn)生與進(jìn)化過(guò)程。

在自然界的演化過(guò)程中，生物體通過(guò)遺傳（傳宗接代、后代和雙親非常相像）、變異（后代與雙親又不完全相像）來(lái)適應(yīng)外界環(huán)境，一代又一代地優(yōu)勝劣汰、繁衍進(jìn)化。第13頁(yè),共37頁(yè)，2024年2月25日，星期天GA則模擬了上述進(jìn)化現(xiàn)象，它把搜索空間（所求問(wèn)題的解的隸屬空間）映射為遺傳空間，即把每一個(gè)可能的解編碼為一個(gè)向量（二進(jìn)制或十進(jìn)制數(shù)字或字符串），稱為一個(gè)染色體或個(gè)體，向量的每個(gè)元素稱為基因，所有染色體組成群體或種群，并按預(yù)定的目標(biāo)函數(shù)（或某種評(píng)價(jià)指標(biāo)）對(duì)每個(gè)染色體進(jìn)行評(píng)價(jià)，據(jù)其評(píng)價(jià)結(jié)果給出一個(gè)適應(yīng)度值。第14頁(yè),共37頁(yè)，2024年2月25日，星期天

算法開始時(shí)先隨機(jī)地產(chǎn)生一些染色體（即所求問(wèn)題的侯選解），計(jì)算其適應(yīng)度，據(jù)適應(yīng)度大小對(duì)諸染色體進(jìn)行選擇、交叉（雜交）、變異等遺傳操作，剔除適應(yīng)度低（性能不佳、不適宜環(huán)境生存）的染色體，留下適應(yīng)度高（性能優(yōu)良、適宜環(huán)境生存）的染色體，從而得到新的群體。由于新群體的成員是上一代群體的優(yōu)秀者，繼承了上一代的優(yōu)良性能，因而明顯優(yōu)于上一代。GA就是這樣反復(fù)地操作，向著更優(yōu)解的方向進(jìn)化，直到滿足某種預(yù)定的優(yōu)化收斂指標(biāo)。第15頁(yè),共37頁(yè)，2024年2月25日，星期天§1.3遺傳算法的幾個(gè)基本概念

個(gè)體種群和種群規(guī)模適應(yīng)度函數(shù)

生物群體中的染色體，設(shè)計(jì)向量映射到遺傳空間中的一個(gè)編碼串。具體地說(shuō)，就是一個(gè)侯選解。

一個(gè)生物群體就是一個(gè)種群，其中的生物個(gè)體的總數(shù)目就是種群規(guī)模。編碼串總數(shù)目。

適應(yīng)度是生物個(gè)體適應(yīng)環(huán)境生存的能力大小，或評(píng)價(jià)個(gè)體性能優(yōu)劣的指標(biāo)，與染色體之間存在一定的關(guān)系。第16頁(yè),共37頁(yè)，2024年2月25日，星期天§1.4遺傳算法的基本算子選擇（Selection）算子

選擇算子又稱為繁殖、再生或復(fù)制（Reproduction）算子，它是用以模擬生物界去劣存優(yōu)的自然選擇現(xiàn)象。它從舊種群中選擇出適應(yīng)性強(qiáng)（適應(yīng)度高）的某些個(gè)體（染色體），放入匹配（交配或配對(duì)）集（MatingPool），為通過(guò)染色體交叉和變異產(chǎn)生新的種群作準(zhǔn)備。適應(yīng)度越高的染色體被選擇的可能性越大，其遺傳基因在下一代種群中的分布就越廣，其子孫（后代）在下一代出現(xiàn)的數(shù)量就越多。第17頁(yè),共37頁(yè)，2024年2月25日，星期天

選擇是遺傳算法中的最主要的算子（機(jī)制），也是影響遺傳算法性能的最主要的因素。但選擇只能從舊的種群中選擇出優(yōu)秀者，而不能創(chuàng)造出新的染色體。選擇壓（SelectionPressure）描述了選擇算子挑選種群中不同個(gè)體做母體的概率大小的差異。選擇壓過(guò)大，會(huì)造成幾個(gè)較好可行解（不一定是近似全局最優(yōu)解）迅速占領(lǐng)了整個(gè)種群；選擇壓過(guò)小，則會(huì)使算法呈現(xiàn)出純粹的隨機(jī)徘徊行為。第18頁(yè),共37頁(yè)，2024年2月25日，星期天

選擇有多種方法，如適應(yīng)度比例法、順序法、適應(yīng)度函數(shù)的尺度變換、杰出者選擇（ElitistSelection）。其中，適應(yīng)度比例法是比較普遍采用的策略，其缺陷是易造成選擇壓過(guò)大或過(guò)小。

適應(yīng)度比例選擇法又稱輪轉(zhuǎn)法，它把種群中的所有染色體適應(yīng)度的總和看作一個(gè)輪子的圓周，而每個(gè)染色體按其適應(yīng)度在總和中所占的比例占據(jù)輪子的一個(gè)扇區(qū)片。每次染色體的選擇可看作輪子的一次隨機(jī)轉(zhuǎn)動(dòng)，它轉(zhuǎn)到哪個(gè)扇區(qū)停下來(lái)，哪個(gè)扇區(qū)對(duì)應(yīng)的染色體就被選中。盡管這種選擇方法是隨機(jī)的，第19頁(yè),共37頁(yè)，2024年2月25日，星期天但它與各染色體適應(yīng)度成比例。這是因?yàn)檫m應(yīng)度大的染色體占據(jù)輪子扇區(qū)面積大，被選中的概率就高（機(jī)會(huì)多），而適應(yīng)度小的染色體占據(jù)的扇區(qū)面積小，被選中的概率就低（機(jī)會(huì)少）。12345687910…M第20頁(yè),共37頁(yè)，2024年2月25日，星期天舉例：第21頁(yè),共37頁(yè)，2024年2月25日，星期天交叉（Crossover，又稱雜交）算子

選擇算子雖然能夠從舊種群中選擇出優(yōu)秀者，但不能創(chuàng)造新的染色體，因此，遺傳算法的開創(chuàng)者提出了交叉算子。交叉算子是用于模擬生物進(jìn)化過(guò)程中的繁殖雜交現(xiàn)象，它通過(guò)兩個(gè)染色體的交叉組合來(lái)產(chǎn)生新的染色體，即在匹配集中任選兩個(gè)染色體（又稱雙親），隨機(jī)地選擇一個(gè)交叉點(diǎn)（稱為單點(diǎn)交叉、單點(diǎn)雜交），通過(guò)交換雙親染色體交叉點(diǎn)右邊的部分，從而得到兩個(gè)新的染色體（后代）。交叉的結(jié)果，有可能使各個(gè)個(gè)體的優(yōu)點(diǎn)互相補(bǔ)充而產(chǎn)生更優(yōu)的后代。由于交叉算子能夠創(chuàng)造新的染色體，從而允許測(cè)試產(chǎn)生于搜索空間中的新點(diǎn)，它體現(xiàn)了自然界信息交換的思想。第22頁(yè),共37頁(yè)，2024年2月25日，星期天第23頁(yè),共37頁(yè)，2024年2月25日，星期天變異（Mutation）算子

選擇和交叉算子實(shí)現(xiàn)了遺傳算法的大范圍搜索過(guò)程，而變異的目的在于增強(qiáng)遺傳算法搜索最優(yōu)解的能力。變異算子用以模擬生物在自然的遺傳環(huán)境中由于各種偶然因素引起的基因突變，它以很小的概率隨機(jī)地改變遺傳基因（表示染色體的數(shù)字串的某一位）的值。在染色體以二進(jìn)制編碼的系統(tǒng)中，它隨機(jī)地將染色體的某一個(gè)基因由1變成0或由0變?yōu)?。第24頁(yè),共37頁(yè)，2024年2月25日，星期天

如果只有選擇和交叉算子，而沒(méi)有變異算子，則無(wú)法在初始基因組合以外的空間進(jìn)行搜索，從而使進(jìn)化過(guò)程的早期就陷入局部解而終止進(jìn)化過(guò)程，使解的質(zhì)量受到很大限制。通過(guò)變異算子可以確保群體中遺傳基因類型的多樣性，以使搜索能在盡可能大的空間中進(jìn)行，避免丟失在搜索中有用的遺傳信息而陷入局部解，從而獲得質(zhì)量較高的優(yōu)化解。變異算子是個(gè)體空間到個(gè)體空間的隨機(jī)映射，其作用方式為獨(dú)立地以概率Pm改變個(gè)體分量取值。稱Pm為變異概率。

第25頁(yè),共37頁(yè)，2024年2月25日，星期天

遺傳算法的上述三個(gè)基本算子：選擇、交叉和變異算子，各有其功能。單純利用選擇可找到局部最優(yōu)值，變異可以使搜索空間遍及整個(gè)空間，而交叉結(jié)果依賴于初始分布。因此，一個(gè)完整的遺傳算法應(yīng)當(dāng)是選擇、交叉和變異運(yùn)算共同構(gòu)成的。第26頁(yè),共37頁(yè)，2024年2月25日，星期天§1.5遺傳算法實(shí)現(xiàn)舉例

假設(shè)一個(gè)快餐店追求的目標(biāo)是最高的利潤(rùn)，要達(dá)到這一目標(biāo)，必須選擇適當(dāng)?shù)慕?jīng)營(yíng)策略。一種可能的策略是對(duì)以下三個(gè)問(wèn)題作出決策。

1)

每盤炒米粉的價(jià)格是5元還是10元

2)與炒米粉配套的飲料是非?？蓸?lè)還是椰子汁

3)提供快速還是排隊(duì)慢速服務(wù)以下介紹用遺傳算法來(lái)解決這個(gè)決策問(wèn)題的方法和過(guò)程。第27頁(yè),共37頁(yè)，2024年2月25日，星期天

（1）把問(wèn)題的可能解表示為染色體數(shù)字串（問(wèn)題編碼）由于這個(gè)問(wèn)題有三個(gè)決策變量，其取值為是或否，可以用1或0來(lái)表示，于是可以用三位的二進(jìn)制數(shù)字表征一種可能的經(jīng)營(yíng)策略，解的搜索空間為23=8，即有8種經(jīng)營(yíng)策略可供選擇。表3給出了其中快餐店經(jīng)理已知的4種經(jīng)營(yíng)策略（初始解）。表中數(shù)字串的第一位取0表示價(jià)格高，1表示價(jià)格低；第二位取0表示椰子汁，取1表示非常可樂(lè)；第三位取0表示排隊(duì)慢速服務(wù)，取1表示快速服務(wù)。第28頁(yè),共37頁(yè)，2024年2月25日，星期天第29頁(yè),共37頁(yè)，2024年2月25日，星期天

a)

求各染色體的適應(yīng)度。這個(gè)問(wèn)題中，一個(gè)染色體的適應(yīng)度假設(shè)恰好是其二進(jìn)制數(shù)字串等價(jià)的十進(jìn)制數(shù)，也是對(duì)應(yīng)的經(jīng)營(yíng)策略的利潤(rùn)。

第30頁(yè),共37頁(yè)，2024年2月25日，星期天

b)

選擇進(jìn)入交叉集的染色體由表4可見(jiàn)，所有染色體串的適應(yīng)度的總和是12，數(shù)字串110的適應(yīng)度是6，占適應(yīng)度總和的1/2，也就是說(shuō)該串被選中的機(jī)會(huì)有兩次，其概率為1/2；串011，001，010被選中的概率分別為3/12=1/4，1/12，2/12=1/6。按前述的適應(yīng)度比例法，選擇進(jìn)入交叉集的染色體串及其適應(yīng)度值見(jiàn)表5所示。

第31頁(yè),共37頁(yè)，2024年2月25日，星期天第32頁(yè),共37頁(yè)，2024年2月25日，星期天

從表5可知，選擇算子的作用確實(shí)是改進(jìn)了種群的平均適應(yīng)度，使其由原來(lái)的3提高到了4.25，最壞的適應(yīng)度由原來(lái)的1改進(jìn)為2，性能最差的染色體已從種群中刪除。但是，選擇不能創(chuàng)造新的染色體，為了改進(jìn)這一缺點(diǎn)，尋找搜索空