決策支持系統(tǒng)與商務(wù)智能：遺傳算法

遺傳算法GeneticAlgorithm（GA）遺傳算法是什么？遺傳算法（GeneticAlgorithm，GA）是進(jìn)化計(jì)算的一個(gè)分支，是一種模擬自然界生物進(jìn)化過程的隨機(jī)搜索算法。遺傳算法的思想來源是怎樣的？它由誰提出的？GA思想源于自然界“自然選擇”和“優(yōu)勝劣汰”的進(jìn)化規(guī)律，通過模擬生物進(jìn)化中的自然選擇和交配變異尋找問題的全局最優(yōu)解。它最早由美國密歇根大學(xué)教授JohnH.Holland提出，現(xiàn)在已經(jīng)廣泛應(yīng)用于各種工程領(lǐng)域的優(yōu)化問題之中。簡介遺傳算法借鑒生物界自然選擇原理和自然遺傳機(jī)制而形成的一種迭代式自適應(yīng)概率性全局優(yōu)化搜索算法。它模擬自然界中生物進(jìn)化的發(fā)展規(guī)律，在人工系統(tǒng)中實(shí)現(xiàn)待定目標(biāo)的優(yōu)化。基本特點(diǎn)簡單易懂、通用、魯棒性強(qiáng)、適合并行處理，可用于解決各種復(fù)雜優(yōu)化問題鼻祖美國密歇根(Michigan)大學(xué)JohnHolland教授一遺傳算法的基本流程二模式定理和隱含并行性四遺傳算法關(guān)鍵參數(shù)和操作設(shè)計(jì)五遺傳算法的改進(jìn)及其并行性六算法的實(shí)現(xiàn)及應(yīng)用三收斂性分析目錄引言在人類歷史上，學(xué)習(xí)和模擬的例子不勝枚舉：模擬飛禽，人類可以翱游太空；模擬游魚，人類可以橫渡海洋；模擬昆蟲，人類可以縱觀千里；模擬大腦，人類創(chuàng)造影響世界發(fā)展的計(jì)算機(jī)；……第一節(jié)GA的基本流程

遺傳算法就是一種更為宏觀意義下的模擬，它模仿的機(jī)制是一切生命和智能的產(chǎn)生與進(jìn)化過程.模擬達(dá)爾文“優(yōu)勝劣汰、適者生存”的原理激勵好的結(jié)構(gòu)模擬孟德爾遺傳變異理論在迭代過程中保持已有結(jié)構(gòu)，同時(shí)尋找更好的結(jié)構(gòu)

70年代初期由美國Michigan大學(xué)的Holland教授發(fā)展起來的。

1975年Holland的專著《AdaptationinnaturalandArtificialsystems》出版為標(biāo)志。遺傳算法

達(dá)爾文進(jìn)化論現(xiàn)代遺傳學(xué)生物模擬技術(shù)一、算法提出依據(jù)達(dá)爾文(Darwin)的進(jìn)化論英國自然學(xué)家，進(jìn)化論的奠基人。青年時(shí)期在愛丁堡大學(xué)和劍橋大學(xué)學(xué)習(xí)，特別喜愛博物學(xué)。大學(xué)畢業(yè)時(shí)22歲，以博物學(xué)者的身份登上英國海軍艦艇貝格爾號(HMSBeagles)，進(jìn)行了5年（1831年—1836年）探險(xiǎn)航行。他觀察了距厄瓜多爾西岸950km的加拉帕戈斯群島上的海龜和地雀。1859年，達(dá)爾文出版了《物種起源》這一劃時(shí)代的著作。這一著作終結(jié)了神創(chuàng)論關(guān)于上帝創(chuàng)造人類的統(tǒng)治地位，使生物學(xué)開始成為科學(xué)，對人類的思想解放有巨大的意義。達(dá)爾文(Darwin)的進(jìn)化論進(jìn)化論是生物學(xué)最基本的理論之一。生物學(xué)上的所謂進(jìn)化或者演化（Evolution），舊稱“天演”，是指生物在變異、遺傳與自然選擇作用下的演變發(fā)展，物種淘汰和物種產(chǎn)生過程。地球上原來無生命，大約在30多億年前，在一定的條件下，形成了原始生命，其后，生物不斷的進(jìn)化，直至今天世界上存在著170多萬個(gè)物種。達(dá)爾文用自然選擇來解釋生物進(jìn)化。自然選擇就是指生物由于環(huán)境中某些因素的影響而使得有利于一些個(gè)體的生存，而不利于另外一些個(gè)體生存的演化過程。簡而言之——物競天擇，適者生存達(dá)爾文的自然選擇說遺傳（heredity）：子代和父代具有相同或相似的性狀，保證物種的穩(wěn)定性；變異（variation）：子代與父代，子代不同個(gè)體之間總有差異，是生命多樣性的根源；生存斗爭和適者生存：具有適應(yīng)性變異的個(gè)體被保留，不具適應(yīng)性變異的個(gè)體被淘汰。自然選擇過程是長期的、緩慢的、連續(xù)的過程。

1遺傳算法簡介

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

孟德爾(Mendel)的遺傳學(xué)1822年7月22日孟德爾生于奧地利的海因岑多夫（今捷克的海恩塞斯）。他于1840年畢業(yè)于特羅保的預(yù)科學(xué)校，進(jìn)入奧爾米茨哲學(xué)院學(xué)習(xí)。1843年因家貧而輟學(xué)，同年10月到奧古斯丁修道院做修道士。1847年被任命為神父。1849年受委派到茨納伊姆中學(xué)任希臘文和數(shù)學(xué)代課教師。1851年～1853年在維也納大學(xué)學(xué)習(xí)物理、化學(xué)、數(shù)學(xué)、動物學(xué)和植物學(xué)。1853年，他從維也納大學(xué)畢業(yè)回修道院。1854年被委派到布呂恩技術(shù)學(xué)校任物理學(xué)和植物學(xué)的代理教師。并在那里工作了14年。1884年1月6日卒于布呂恩(今捷克的布爾諾)?？茖W(xué)遺傳學(xué)的奠基人代表作1865《植物雜交試驗(yàn)》孟德爾(Mendel)的遺傳學(xué)遺傳學(xué)是研究基因及它們在生物遺傳中的作用的科學(xué)分支。遺傳學(xué)最早的應(yīng)用在有歷史記載之初就已經(jīng)出現(xiàn)了，即馴養(yǎng)動物及植物的選擇育種。遺傳信息以化學(xué)方法被編碼在DNA（脫氧核糖核酸）中。1865年，孟德爾首先記錄了豌豆某些特性的遺傳模式，表明它們遵守簡單的統(tǒng)計(jì)學(xué)規(guī)律。由他的統(tǒng)計(jì)分析中，孟德爾定義了一個(gè)概念：遺傳的基本單位——等位基因。他描述的等位基因類于現(xiàn)在的基因。直到孟德爾死后，20世紀(jì)初另外的科學(xué)家重新發(fā)現(xiàn)這個(gè)定律之后，孟德爾的工作的重要性才被大家了解。改變一個(gè)生物的DNA從而達(dá)到某種目的被稱為基因工程。遺傳學(xué)時(shí)間表1859年查爾斯·達(dá)爾文發(fā)表了《物種起源》

1865年格雷戈?duì)枴っ系聽柊l(fā)表文章《植物雜交試驗(yàn)》

1903年發(fā)現(xiàn)染色體是遺傳單位

1905年英國科學(xué)家威廉·貝特森在給亞當(dāng)·塞奇威克的一封信中提出了“遺傳學(xué)”這個(gè)名詞。1927年基因的物理變化叫做基因突變1931年交叉互換導(dǎo)致了基因重組

1944年奧斯瓦德·西奧多·艾弗里，科林·麥克勞德和麥克林·麥克卡提分離出遺傳物質(zhì)DNA（那時(shí)叫做遺傳要素）1953年詹姆斯·沃森和弗朗西斯·克里克提出了DNA的雙螺旋結(jié)構(gòu)1958年Meselson-Stahl試驗(yàn)證明DNA是半保留復(fù)制的1961年提出三聯(lián)體遺傳密碼

1977年DNA測序

2001年人類基因組序列草圖由人類基因組計(jì)劃和賽雷拉基因公司同時(shí)完成群體競爭淘汰的群體變異子群種群婚配生物遺傳學(xué)基礎(chǔ)生物進(jìn)化過程遺傳基因重組過程

1遺傳算法簡介

遺傳學(xué)基本概念與術(shù)語染色體（chromosome）：遺傳物質(zhì)的載體；脫氧核糖核酸（DNA）：大分子有機(jī)聚合物，雙螺旋結(jié)構(gòu)；遺傳因子（gene）：DNA或RNA長鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位；

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

遺傳算法中常用術(shù)語基因（遺傳因子）：染色體的一個(gè)片段，通常為單個(gè)參數(shù)的編碼值。染色體（基因串）：攜帶基因信息的數(shù)據(jù)結(jié)構(gòu)，簡稱個(gè)體，二進(jìn)制位串或整數(shù)數(shù)組。

1遺傳算法簡介

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

1遺傳算法簡介

遺傳學(xué)基本概念與術(shù)語基因型（genotype）：遺傳因子組合的模型，染色體的內(nèi)部表現(xiàn)；表現(xiàn)型（phenotype）：由染色體決定性狀的外部表現(xiàn)，基因型形成的個(gè)體；

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

1111111

1110111遺傳學(xué)基本概念與術(shù)語基因座（locus）：遺傳基因在染色體中所占據(jù)的位置，同一基因座可能有的全部基因稱為等位基因（allele）；個(gè)體（individual）：指染色體帶有特征的實(shí)體；種群（population）：個(gè)體的集合，該集合內(nèi)個(gè)體數(shù)稱為種群的大小；種群大小：種群中個(gè)體的數(shù)量，也叫群體規(guī)模。

1遺傳算法簡介

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

遺傳學(xué)基本概念與術(shù)語進(jìn)化（evolution）：生物在其延續(xù)生存的過程中，逐漸適應(yīng)其生存環(huán)境，使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化；適應(yīng)度（fitness）：個(gè)體性能的數(shù)量值，度量某個(gè)物種對于生存環(huán)境的適應(yīng)程度。對生存環(huán)境適應(yīng)程度較高的物種將獲得更多的繁殖機(jī)會，而對生存環(huán)境適應(yīng)程度較低的物種，其繁殖機(jī)會就會相對較少，甚至逐漸滅絕;

1遺傳算法簡介

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

遺傳學(xué)基本概念與術(shù)語選擇（selection）：指決定以一定的概率從種群中選擇若干個(gè)體的操作；復(fù)制（reproduction）：細(xì)胞在分裂時(shí)，遺傳物質(zhì)DNA通過復(fù)制而轉(zhuǎn)移到新產(chǎn)生的細(xì)胞中，新的細(xì)胞就繼承了舊細(xì)胞的基因;交叉（crossover）：在兩個(gè)染色體的某一相同位置處DNA被切斷，其前后兩串分別交叉組合形成兩個(gè)新的染色體。又稱基因重組，俗稱“雜交”;

1遺傳算法簡介

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

遺傳學(xué)基本概念與術(shù)語變異（mutation）：在細(xì)胞進(jìn)行復(fù)制時(shí)可能以很小的概率產(chǎn)生某些復(fù)制差錯，從而使DNA發(fā)生某種變異，產(chǎn)生出新的染色體，這些新的染色體表現(xiàn)出新的性狀;編碼（coding）：表現(xiàn)型到基因型的映射；解碼（decoding）：從基因型到表現(xiàn)型的映射。

1遺傳算法簡介

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

進(jìn)化論與遺傳學(xué)的融合

1930～1947年，達(dá)爾文進(jìn)化論與遺傳學(xué)走向融合，Th.Dobzhansky1937年發(fā)表的《遺傳學(xué)與物種起源》是融合進(jìn)化論與遺傳學(xué)的代表作。生物進(jìn)化與智能學(xué)的關(guān)系

生物物種作為復(fù)雜系統(tǒng)，具有奇妙的自適應(yīng)、自組織和自優(yōu)化能力，這是一種生物在進(jìn)化過程中體現(xiàn)的智能，也是人工系統(tǒng)夢寐以求的功能。

1遺傳算法簡介

1.1

生物進(jìn)化理論和遺傳學(xué)的基本知識

如何借鑒？對于一個(gè)優(yōu)化問題，一定數(shù)量的候選解（生命個(gè)體）被表示為抽象的數(shù)字串（染色體），通過進(jìn)化向更好的解發(fā)展。選解一般為二進(jìn)制數(shù)字串（即0和1），但也可能有其他表示。一開始，生命個(gè)體完全隨機(jī)產(chǎn)生，之后一代一代的進(jìn)化，在進(jìn)化過程中的每一代，每一個(gè)個(gè)體的適應(yīng)程度被評價(jià)，通過自然選擇和變異產(chǎn)生新的生命群體，該群體就是下一代的個(gè)體。遺傳算法與自然進(jìn)化的比較自然界染色體基因等位基因(allele)染色體位置(locus)基因型(genotype)表現(xiàn)型(phenotype)遺傳算法字符串字符，特征特征值字符串位置結(jié)構(gòu)參數(shù)集，譯碼結(jié)構(gòu)進(jìn)化過程的三種運(yùn)算選擇：根據(jù)適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體p(t)中選擇優(yōu)良的個(gè)體遺傳到下一代群體p(t+1)中。交叉：將群體p(t)內(nèi)各個(gè)個(gè)體隨機(jī)搭配成對，對每個(gè)個(gè)體中交換一部分染色體。變異：對群體p(t)中的每個(gè)個(gè)體改變某個(gè)或一些值是其他個(gè)體的值。選擇運(yùn)算群體p(t)交叉運(yùn)算變異運(yùn)算解碼群體p(t+1)解集合個(gè)體評價(jià)遺傳空間解空間生物遺傳概念遺傳算法中的作用適者生存?zhèn)€體(individual)染色體(chromosome)基因(gene)適應(yīng)性(fitness)群體(population)交叉(crossover)變異(mutation)種群(reproduction)根據(jù)適應(yīng)函數(shù)值選定的一組解解解的編碼(字符串，向量等)解中每一分量特征(編碼單元)適應(yīng)函數(shù)值搜索空間中選定的一組有效解算法停止，最優(yōu)值被留住交換部分基因產(chǎn)生一組新解的過程編碼的某一分量發(fā)生變化例1

用遺傳算法求解優(yōu)化問題其中為整數(shù)。產(chǎn)生群體:適應(yīng)函數(shù)交叉變異的第一個(gè)基因發(fā)生變異二、算法發(fā)展回顧遺傳算法最開始是產(chǎn)生于Holland教授和他的同事對cellularautomata的研究過程中。在二十世紀(jì)八十年代中期之前，對于遺傳算法的研究還僅限于理論方面，直到在伊里諾斯大學(xué)召開了第一屆世界遺傳算法大會。隨著計(jì)算機(jī)計(jì)算能力的發(fā)展和實(shí)際應(yīng)用需求的增多，遺傳算法逐漸進(jìn)入實(shí)際應(yīng)用階段。1989年，紐約時(shí)報(bào)作者約翰馬克夫?qū)懥艘黄恼旅枋龅谝粋€(gè)商業(yè)用途的遺傳算法--進(jìn)化者(Evolver）。之后，越來越多種類的遺傳算法出現(xiàn)并被用于許多領(lǐng)域中，財(cái)富雜志500強(qiáng)企業(yè)中大多數(shù)都用它進(jìn)行時(shí)間表安排、數(shù)據(jù)分析、未來趨勢預(yù)測、預(yù)算等很多其他優(yōu)化問題。

1遺傳算法簡介

產(chǎn)生早在50年代，一些生物學(xué)家開始研究運(yùn)用數(shù)字計(jì)算機(jī)模擬生物的自然遺傳與自然進(jìn)化過程；1963年，德國柏林技術(shù)大學(xué)的I.Rechenberg和H.P.Schwefel，做風(fēng)洞實(shí)驗(yàn)時(shí)，產(chǎn)生了進(jìn)化策略的初步思想；60年代，L.J.Fogel在設(shè)計(jì)有限態(tài)自動機(jī)時(shí)提出進(jìn)化規(guī)劃思想。1966年Fogel等出版《基于模擬進(jìn)化的人工智能》，系統(tǒng)闡述了進(jìn)化規(guī)劃的思想。

1.2

遺傳算法的產(chǎn)生與發(fā)展

人工進(jìn)化系統(tǒng)早在20世紀(jì)50年代和60年代，就有計(jì)算機(jī)科學(xué)家進(jìn)行了“人工進(jìn)化系統(tǒng)”的研究。這些研究大多都是以用計(jì)算機(jī)來模擬生物系統(tǒng)為主，從生物的角度進(jìn)行進(jìn)化模擬、遺傳模擬等方面的研究工作。

——形成了遺傳算法的雛形

1遺傳算法簡介

產(chǎn)生60年代中期，美國Michigan大學(xué)的J.H.Holland教授提出借鑒生物自然遺傳的基本原理用于自然和人工系統(tǒng)的自適應(yīng)行為研究和串編碼技術(shù)；1967年，他的學(xué)生J.D.Bagley在博士論文中首次提出“遺傳算法(GeneticAlgorithms)”一詞；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，標(biāo)志遺傳算法的誕生。

1.2

遺傳算法的產(chǎn)生與發(fā)展

1遺傳算法簡介

發(fā)展70年代初，Holland提出了“模式定理”（SchemaTheorem），一般認(rèn)為是“遺傳算法的基本定理”，從而奠定了遺傳算法研究的理論基礎(chǔ)；1985年，在美國召開了第一屆遺傳算法國際會議，并且成立了國際遺傳算法學(xué)會(ISGA，InternationalSocietyofGeneticAlgorithms)；

1.2

遺傳算法的產(chǎn)生與發(fā)展

J.H.Holland20世紀(jì)60年代認(rèn)識到了生物的遺傳和自然進(jìn)化現(xiàn)象與人工自適應(yīng)系統(tǒng)的相似關(guān)系，運(yùn)用生物遺傳和進(jìn)化的思想來研究自然和人工自適應(yīng)系統(tǒng)的生成以及它們與環(huán)境的關(guān)系，提出在研究和設(shè)計(jì)人工自適應(yīng)系統(tǒng)時(shí)，可以借鑒生物遺傳機(jī)制，以群體的方法進(jìn)行自適應(yīng)搜索，充分認(rèn)識到了交叉、變異等運(yùn)算策略在自適應(yīng)系統(tǒng)中的重要性。

20世紀(jì)70年代，Holland提出了遺傳算法的基本定理---模式定理(SchemaTheorem)，奠定了遺傳算法的理論基礎(chǔ)。

20世紀(jì)80年代，Holland實(shí)現(xiàn)了第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)----分類器系統(tǒng)，開創(chuàng)了基于遺傳算法學(xué)習(xí)的新概念，為分類器系統(tǒng)構(gòu)造出了一個(gè)完整的框架。

1975年，Holland出版了第一本系統(tǒng)論述遺傳算法和人工自適應(yīng)系統(tǒng)的專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性（AdaptationinNaturalandArtificialSystems）》。J.D.Bagley1967年，Holland的學(xué)生Bagley在其博士論文中首次提出了“遺傳算法”一詞，并發(fā)表了遺傳算法應(yīng)用方面（在博弈中）的第一篇論文。發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，在個(gè)體編碼上使用了雙倍體編碼方法。這些都與目前遺傳算法中所使用的算子和方法類似。意識到了在遺傳算法執(zhí)行的不同階段可以使用不同的選擇率，這將有利于防止遺傳算法的早熟現(xiàn)象，從而創(chuàng)立了自適應(yīng)遺傳算法概念。Holland

《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)性》

第一次系統(tǒng)地論述了遺傳算法的基本理論與方法，提出了遺傳算法的基本定理——模式定理（schematheorem），從而奠定了遺傳算法的理論基礎(chǔ)。模式定理揭示了群體中優(yōu)良個(gè)體（較好模式）的樣本數(shù)將以指數(shù)規(guī)律增長，確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得隱并行性的重要性，從理論上保證了遺傳算法是一個(gè)可以尋求最優(yōu)可行解的優(yōu)化過程。

——該書的出版標(biāo)志著遺傳算法得到正式承認(rèn)，Holland也被視為遺傳算法的創(chuàng)始人。K.A.DeJong

1975年，DeJong在其博士論文中結(jié)合模式定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化的計(jì)算實(shí)驗(yàn)，將選擇、交叉、變異等遺傳操作進(jìn)一步完善和系統(tǒng)化，建立了遺傳算法的工作框架，得到了一些重要且具有指導(dǎo)意義的結(jié)論。他推薦了在大多數(shù)優(yōu)化問題中都比較適用的遺傳算法參數(shù)，還建立了著名的DeJong五函數(shù)測試平臺，定義了評價(jià)遺傳算法性能的在線指標(biāo)和離線指標(biāo)。

發(fā)展1989年，Holland的學(xué)生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning（遺傳算法——搜索、優(yōu)化及機(jī)器學(xué)習(xí)）”，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述?！摃到y(tǒng)總結(jié)了遺傳算法的主要研究成果，全面完整地論述了遺傳算法的基本原理及應(yīng)用。

1遺傳算法簡介

1.2

遺傳算法的產(chǎn)生與發(fā)展

發(fā)展1991年，L.Davis編輯出版了《HandbookofGeneticAlgorithms（遺傳算法手冊）》，書中介紹了遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會經(jīng)濟(jì)等領(lǐng)域中大量的應(yīng)用實(shí)例，該書為推廣和普及遺傳算法的應(yīng)用起到了重要的指導(dǎo)作用。

1遺傳算法簡介

1.2

遺傳算法的產(chǎn)生與發(fā)展

發(fā)展1992年，J.R.Koza《GeneticProgramming》將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動生成，提出了遺傳編程的概念。Koza成功地將提出的遺傳編程方法應(yīng)用于人工智能、機(jī)器學(xué)習(xí)、符號處理等方面。

1遺傳算法簡介

1.2

遺傳算法的產(chǎn)生與發(fā)展

幾個(gè)名詞概念

遺傳算法——進(jìn)化計(jì)算——計(jì)算智能——人工智能

1遺傳算法簡介

1.2

遺傳算法的產(chǎn)生與發(fā)展

幾個(gè)名詞概念

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

由于遺傳算法、進(jìn)化規(guī)劃和進(jìn)化策略是不同領(lǐng)域的研究人員分別獨(dú)立提出的，在相當(dāng)長的時(shí)期里相互之間沒有正式溝通。直到90年代，才有所交流。

他們發(fā)現(xiàn)彼此的基本思想具有驚人的相似之處，于是提出將這類方法統(tǒng)稱為“進(jìn)化計(jì)算”(EvolutionaryComputation)。

1遺傳算法簡介

1.2

遺傳算法的產(chǎn)生與發(fā)展

幾個(gè)名詞概念

計(jì)算智能：

計(jì)算智能主要包括神經(jīng)計(jì)算、進(jìn)化計(jì)算和模糊計(jì)算等。它們分別從不同的角度模擬人類的智能活動，以使計(jì)算機(jī)具有智能。通常將基于符號處理的傳統(tǒng)人工智能稱為符號智能，以區(qū)別于正在興起的計(jì)算智能。符號智能的特點(diǎn)是以知識為基礎(chǔ)，偏重于邏輯推理，而計(jì)算智能則是以數(shù)據(jù)為基礎(chǔ)，偏重于數(shù)值計(jì)算。

1遺傳算法簡介

1.2

遺傳算法的產(chǎn)生與發(fā)展

三、算法機(jī)理優(yōu)化問題的解被視為個(gè)體，它表示為一個(gè)參數(shù)列表，叫做染色體或者基因串。染色體一般被表達(dá)為簡單的字符串或數(shù)字串。一開始，算法隨機(jī)生成一定數(shù)量的個(gè)體，有時(shí)操作者也可以對這個(gè)隨機(jī)產(chǎn)生過程進(jìn)行干預(yù)，播下已經(jīng)部分優(yōu)化的種子。在每一代中，每一個(gè)個(gè)體都被評價(jià)，并通過適應(yīng)度函數(shù)計(jì)算并返回一個(gè)適應(yīng)度數(shù)值。下一步是產(chǎn)生下一代個(gè)體并組成群落。這個(gè)過程是通過選擇和繁殖完成的，其中繁殖包括雜交和突變。選擇是根據(jù)新個(gè)體的適應(yīng)度數(shù)值進(jìn)行的，適應(yīng)度越高，選擇的機(jī)會越多，而適應(yīng)度低的，被選擇的機(jī)會就低。通過這樣的過程，初始的數(shù)據(jù)可以達(dá)到一個(gè)優(yōu)化的群體。之后，被選擇的個(gè)體進(jìn)入雜交過程。一般的遺傳算法都有一個(gè)雜交率的參數(shù)，范圍一般是0.6~1，這個(gè)雜交率反映兩個(gè)被選中的個(gè)體進(jìn)行雜交的概率。例如，雜交率為0.8，則80%的“夫妻”會生育后代。每兩個(gè)個(gè)體通過雜交產(chǎn)生兩個(gè)新個(gè)體，代替原來的“老”個(gè)體，而不雜交的個(gè)體則保持不變。雜交父母的染色體相互交錯，從而產(chǎn)生兩個(gè)新的染色體，第一個(gè)個(gè)體前半段是父親的染色體，后半段是母親的，第二個(gè)個(gè)體則正好相反。不過這里的半段不是真正的一半，這個(gè)位置叫做雜交點(diǎn)，也是隨機(jī)產(chǎn)生的，可以是染色體的任意位置。再下一步是變異，通過變異產(chǎn)生新的“子”個(gè)體。一般遺傳算法都有一個(gè)固定的變異常數(shù)，通常是0.01或者更小，這代表變異發(fā)生的概率。根據(jù)這個(gè)概率，新個(gè)體的染色體隨機(jī)的變異，通常就是改變?nèi)旧w的一個(gè)字節(jié)（0變到1，或者1變到0）。經(jīng)過這一系列的過程（選擇、雜交和變異），產(chǎn)生的新一代個(gè)體不同于初始的一代，并一代一代向增加整體適應(yīng)度的方向發(fā)展，因?yàn)樽詈玫膫€(gè)體總是更多的被選擇去產(chǎn)生下一代，而適應(yīng)度低的個(gè)體逐漸被淘汰掉。這樣的過程不斷的重復(fù)：每個(gè)個(gè)體被評價(jià)，計(jì)算出適應(yīng)度，兩個(gè)個(gè)體雜交，然后變異，產(chǎn)生第三代。周而復(fù)始，直到終止條件滿足為止。終止條件有以下幾種：進(jìn)化次數(shù)限制；計(jì)算耗費(fèi)的資源限制（例如計(jì)算時(shí)間、計(jì)算占用的內(nèi)存等）；一個(gè)個(gè)體已經(jīng)滿足最小值的條件，即最小值已經(jīng)找到；適應(yīng)度已經(jīng)達(dá)到飽和，繼續(xù)進(jìn)化不會造成適應(yīng)度更好的個(gè)體；人為干預(yù)；以及以上兩種或更多種的組合。Step1

隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成初始種群,并評價(jià)每一個(gè)個(gè)體的適配值(fitnessvalue);Step2

判斷算法收斂準(zhǔn)則是否滿足。若滿足則輸出搜索結(jié)果；否則執(zhí)行以下步驟;Step3

根據(jù)適配值大小以一定方式進(jìn)行復(fù)制操作;Step6

返回Step2.四、標(biāo)準(zhǔn)遺傳算法的主要步驟Step4

按交叉概率執(zhí)行交叉操作;Step5

按變異概率執(zhí)行變異操作;算法基本流程開始隨機(jī)產(chǎn)生初始種群并計(jì)算各個(gè)體的適配值算法收斂準(zhǔn)則滿足否？輸出搜索結(jié)果Y執(zhí)行復(fù)制操作交叉概率滿足否?執(zhí)行交叉操作變異概率滿足否？執(zhí)行變異操作YYNNN遺傳算法流程圖和偽代碼遺傳算法基本要素編碼：固定長度的二進(jìn)制符號串初始種群的產(chǎn)生：若干初始解組成的初始群體適值度函數(shù)的設(shè)定：區(qū)分群中個(gè)體好壞的標(biāo)準(zhǔn)遺傳算子：選擇運(yùn)算；交叉運(yùn)算；變異運(yùn)算終止條件：進(jìn)化結(jié)束的條件。如最大進(jìn)化代數(shù)或最優(yōu)解所需滿足的精度。運(yùn)行參數(shù)：群體規(guī)模、交叉概率、變異概率五、SGA結(jié)構(gòu)標(biāo)準(zhǔn)遺傳算法(SimpleGeneticAlgorithms,簡稱SGA)是一種統(tǒng)一的最基本的遺傳算法，它只使用選擇、交叉、變異這三種基本遺傳算子，其遺傳進(jìn)化操作過程簡單，容易理解，是其他一些遺傳算法的雛形和基礎(chǔ)，它不僅給各種遺傳算法提供了一個(gè)基本框架，同時(shí)也具有一定的應(yīng)用價(jià)值。又叫基本遺傳算法或簡單遺傳算法。構(gòu)成要素①染色體編碼方法。標(biāo)準(zhǔn)遺傳算法使用固定長度的二進(jìn)制符號串來表示群體中的個(gè)體，其等位基因是由二值符號集{0，1}所組成的。初始群體中各個(gè)個(gè)體的基因值可用均勻分布的隨機(jī)數(shù)來生成。②個(gè)體適應(yīng)度評價(jià)。標(biāo)準(zhǔn)遺傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會多少。為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。③遺傳算子。標(biāo)準(zhǔn)遺傳算法使用下述三種遺傳算子：選擇運(yùn)算使用比例選擇算子，交叉運(yùn)算使用單點(diǎn)交叉算子，變異運(yùn)算使用基本位變異算子或均勻變異算子。④運(yùn)行參數(shù)。標(biāo)準(zhǔn)遺傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：群體大小M，即群體中所含個(gè)體數(shù)目，一般取為20~100；遺傳運(yùn)算的終止進(jìn)化代數(shù)T，一般取為100~500；交叉概率Pc，一般取為0.4~0.99；變異概率Pm，一般取為0.0001~0.1。⑤形式化定義算法可定義為一個(gè)8元組：C---個(gè)體的編碼方法；E---個(gè)體適應(yīng)度評價(jià)函數(shù)；P0---初始群體；M---群體大??；Φ---選擇算子；Γ---交叉算子；---變異算子T---遺傳運(yùn)算終止條件。2023/12/463例利用遺傳算法求解區(qū)間［0,31］上的二次函數(shù)y=x2的最大值。y=x2

31

XY例1

用遺傳算法求解優(yōu)化問題

分析

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問題。那么，［0,31］中的點(diǎn)x就是個(gè)體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(qū)間［0,31］就是一個(gè)(解)空間。這樣,只要能給出個(gè)體x的適當(dāng)染色體編碼,該問題就可以用遺傳算法來解決。2023/12/4642023/12/465解

(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定義適應(yīng)度函數(shù),

取適應(yīng)度函數(shù)：f(x)=x2

2023/12/466

(3)計(jì)算各代種群中的各個(gè)體的適應(yīng)度,并對其染色體進(jìn)行遺傳操作,直到適應(yīng)度最高的個(gè)體(即31（11111）)出現(xiàn)為止。

首先計(jì)算種群S1中各個(gè)體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應(yīng)度f(si)。容易求得

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=3612023/12/467再計(jì)算種群S1中各個(gè)體的選擇概率。2023/12/468選擇概率的計(jì)算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.312023/12/469

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法2023/12/470在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計(jì)算公式為2023/12/471選擇-復(fù)制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(jī)數(shù)如下:

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.0012023/12/472交叉設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對，s3’與s4’配對。分別交換后兩位基因，得新染色體：

s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）

2023/12/473變異設(shè)變異率pm=0.001。這樣，群體S1中共有

5×4×0.001=0.02位基因可以變異。

0.02位顯然不足1位，所以本輪遺傳操作不做變異。

于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）2023/12/4742023/12/475

第二代種群S2中各染色體的情況

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=110016250.360.361s2=011001440.080.441s3=110117290.410.851s4=100002560.151.0012023/12/476假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）

做交叉運(yùn)算，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）

這一輪仍然不會發(fā)生變異。2023/12/477于是，得第三代種群S3：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）

2023/12/478

第三代種群S3中各染色體的情況

染色體

適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.0012023/12/479

設(shè)這一輪的選擇-復(fù)制結(jié)果為：

s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）

做交叉運(yùn)算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）

這一輪仍然不會發(fā)生變異。2023/12/480

于是，得第四代種群S4：

s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）2023/12/481顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問題的解，即函數(shù)y=x2的最大值為961。2023/12/482YYy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度y=x2

16242831

X第四代種群及其適應(yīng)度1是否有其他形式的候選解？2如何選取交叉概率、變異概率？3是否有適配值的其他替代形式？4交叉及變異點(diǎn)的如何選擇？5如何利用更多的信息？6終止準(zhǔn)則？Problem例2、旅行商問題（TSP）實(shí)例

已知n個(gè)城市的地理位置（x,y），求經(jīng)過所有城市，并回到出發(fā)城市且每個(gè)城市僅經(jīng)過一次的最短距離。這是一個(gè)NP完全問題，其計(jì)算量為城市個(gè)數(shù)的指數(shù)量級?，F(xiàn)用遺傳算法來解決這個(gè)問題。

2023/12/4841、編碼

每條路徑對應(yīng)一個(gè)個(gè)體，個(gè)體形式地表示為R={City_No|City_No互不重復(fù)}n，n為城市數(shù)。例如對于n=10的TSP問題，對其中一個(gè)個(gè)體

它表示一條城市路徑：

3→1→5→7 →8 →9→10→4 →2 →62023/12/485315789104262、適應(yīng)值函數(shù)

每個(gè)個(gè)體代表一條可能的路徑。個(gè)體n的適應(yīng)值為：其中N為種群數(shù)，Dn為

沿個(gè)體標(biāo)示的城市序列的所經(jīng)過的距離：其中ni表示個(gè)體中第i位的城市編號，n11=n1。適應(yīng)值為非負(fù)，且取值越大越好。表示所有個(gè)體的路徑長度的總和