遺傳算法導(dǎo)論

《遺傳算法導(dǎo)論》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、IntroductiontoGeneticAlgorithms遺傳算法導(dǎo)論http://cs.felk.cvut.cz/~xobitko/ga/（其中有全部操作的小程序可視化演示）byMarekObitko,studentofCzechTechnicalUniversity.王鄭耀翻譯原文為英語版本,你可以在這里找到.你也可以在這里下載到PDF格式的英語版本的文件.--------------------------------------------------------------------------------這里我想介紹一下遺傳算法的一些基礎(chǔ)知識。

2、我盡量寫的比較通俗易懂,使得以前沒有任何相關(guān)知識的讀者也能讀懂。我們只假設(shè)讀者對于計(jì)算機(jī)程序設(shè)計(jì)有一定的了解。這里我們有一些JavaApplet程序用來演示遺傳算法的工作情況。遺傳算法所涉及的范圍是很寬的，所以我們不可能涉及到它的方方面面。但是你可以從這里得到遺傳算法的一些思想：什么是遺傳算法？遺傳算法可以用來做什么？這里面沒有什么很難的數(shù)學(xué)理論?，F(xiàn)在，你可以選擇下一步去瀏覽下面的內(nèi)容，你也可以從左邊的菜單中任意選擇你想要瀏覽的內(nèi)容。如果你不想閱讀全部的內(nèi)容而只關(guān)心其中的一部分，你也可以跳過去直接去首頁面。這里還有一個日語譯本。I簡介前言遺傳算法是進(jìn)化計(jì)算技術(shù)的

3、一部分，而進(jìn)化計(jì)算技術(shù)在人工智能領(lǐng)域得到飛速的發(fā)展。你或許已經(jīng)在想：遺傳算法是不是受到了達(dá)爾文進(jìn)化論的啟發(fā)？簡單地說，用遺傳算法求解問題時，問題的解是在不斷進(jìn)化中得到的。歷史二十世紀(jì)六十年代，I.Rechenberg在他的《演化戰(zhàn)略》中第一次引入了進(jìn)化算法的思想（起初稱之為Evolutionsstrategies）。他的這一思想逐漸被其他一些研究者發(fā)展。遺傳算法（GeneticAlgorithms）是JohnHolland發(fā)明的，后來他和他的學(xué)生及他的同事又不斷發(fā)展了它。終于，在1975年JohnHolland出版了專著《自然系統(tǒng)和人工系統(tǒng)中的自適應(yīng)》（Adap

4、tionInNaturalandArtificialSystems）。1992年，JohnKoza曾經(jīng)使用遺傳算法編出新的程序去做一些具體的工作。他稱他的這種方法為“進(jìn)化規(guī)劃”（GeneticProgramming，簡稱GP）。其中使用了LISP規(guī)劃方法，這是因?yàn)檫@種語言中的程序被表示為“分析樹”（ParseTree），而這種遺傳算法就是以這些分析樹為對象的。II生物學(xué)背景基因所有的生物都是由細(xì)胞組成的。在每一個細(xì)胞中都有想同序列的染色體。染色體是一串DNA的片斷，它為整個有機(jī)體提供了一種復(fù)制模式。染色體是由基因組成的，或者說染色體就是一塊塊的基因。每一個基因?yàn)?/p>

5、一個特定的蛋白質(zhì)編碼?；蛘吒唵蔚恼f，每一個基因?yàn)樯矬w的某一特定特征編碼，比如說眼睛的顏色。所有可能的某一特定特征的屬性（比如，藍(lán)色，桔黃色等）被稱之為等位基因。每一個基因在染色體上都有其特定的位置，這個位置一般被稱作位點(diǎn)（Locus）。全部序列的基因物質(zhì)（或者全部的染色體）稱之為基因組（或染色體組）（Genome）?；蚪M上特定序列的基因被稱作基因型（Genotype）?；蛐秃秃筇斓谋憩F(xiàn)型兩者是有機(jī)體的顯性、生理和心理特征比如說眼睛的顏色、智力的基礎(chǔ)。復(fù)制（Repeoduction）在復(fù)制中，首先發(fā)生的是交叉（Crossover）。來自于父代的基因按照一定

6、的方式組成了新的基因。新的子代還可能發(fā)生變異（Mutation）。變異的意思是DNA上的某一些成分發(fā)生了一點(diǎn)點(diǎn)的變化。這些改變可能是由于在由父代到子代的基因復(fù)制中出現(xiàn)的誤差。生物體的適應(yīng)度由生物體自身是否能生存來度量的。III搜索空間搜索空間（SearchSpace）在很多情況下,我們解決一個問題就是從一大堆的數(shù)據(jù)中尋找一個解，而通常這個解都是混雜在數(shù)據(jù)中的。所有可行解（FeasibleSolution可行解就是滿足了一定約束條件的解）組成的空間稱之為搜索空間（也可以稱之為狀態(tài)空間）。搜索空間中的每一個點(diǎn)都是一個可行解。每一個可行解都可以被它的函數(shù)值或者它的適應(yīng)

7、度所標(biāo)記。記住：問題的解就是搜索空間中的一個點(diǎn)，于是我們就是要從搜索空間中找到這個點(diǎn)。Exampleofasearchspace這樣，求解問題就可以轉(zhuǎn)化為在搜索空間中尋找極值點(diǎn)（最大值或者最小值點(diǎn)）。搜索空間在求解問題時可能是完全已知的，但一般來說我們只知道一些孤立的點(diǎn)，然后我們逐漸地生成其它點(diǎn)。問題是，這個搜索過程可能很復(fù)雜，我們甚至不知道該去哪里搜索或者該從是么地方開始搜索。事實(shí)上，有很多尋找合適解（注意：不一定是最優(yōu)解）的方法，比如說爬山法（HillClimbing）禁止接近法(TabuSearch),模擬退火算法(SimulatedAnnealing)以

8、及遺傳算法等等.用遺傳算