遺傳算法的基本思想是基于Darwin進(jìn)化論和Mendel的遺傳學(xué)說的。

Darwin進(jìn)化論最重要的是適者生存原理。它認(rèn)為每一物種在發(fā)展中越來越適應(yīng)環(huán)境。物種每個(gè)個(gè)體的基本特征由后代所繼承，但后代又會(huì)產(chǎn)生一些異于父代的新變化。在環(huán)境變化時(shí)，只有那些熊適應(yīng)環(huán)境的個(gè)體特征方能保留下來。

Mendel遺傳學(xué)說最重要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個(gè)基因有特殊的位置并控制某種特殊性質(zhì)； 所以，每個(gè)基因產(chǎn)生的個(gè)體對(duì)環(huán)境具有某種適應(yīng)性。基因突變和基因雜交可產(chǎn)生更適應(yīng)于環(huán)境的后代。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下 來。

由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個(gè)算法中要用到各種進(jìn)化和遺傳學(xué)的概念。這些概念如下：

一、串(String)

它是個(gè)體(Individual)的形式，在算法中為二進(jìn)制串，并且對(duì)應(yīng)于遺傳學(xué)中的染色體(Chromosome)。

二、群體(Population)

個(gè)體的集合稱為群體，串是群體的元素

三、群體大小(Population Size)

在群體中個(gè)體的數(shù)量稱為群體的大小。

四、基因(Gene)

基因是串中的元素，基因用于表示個(gè)體的特征。例如有一個(gè)串S＝1011，則其中的1，0，1，1這4個(gè)元素分別稱為基因。它們的值稱為等位基因(Alletes)。

五 、基因位置(Gene Position)

一個(gè)基因在串中的位置稱為基因位置，有時(shí)也簡(jiǎn)稱基因位。基因位置由串的左向右計(jì)算，例如在串S＝1101中，0的基因位置是3。基因位置對(duì)應(yīng)于遺傳學(xué)中的地點(diǎn)(Locus)。

//以下五到九可以不看

六、基因特征值(Gene Feature)

在用串表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。

七、串結(jié)構(gòu)空間S^S

在串中，基因任意組合所構(gòu)成的串的集合。基因操作是在結(jié)構(gòu)空間中進(jìn)行的。串結(jié)構(gòu)空間對(duì)應(yīng)于遺傳學(xué)中的基因型(Genotype)的集合。

八、參數(shù)空間S^P

這是串空間在物理系統(tǒng)中的映射，它對(duì)應(yīng)于遺傳學(xué)中的表現(xiàn)型(Phenotype)的集合。

九、非線性

它對(duì)應(yīng)遺傳學(xué)中的異位顯性(Epistasis)

//

十、適應(yīng)度(Fitness)

表示某一個(gè)體對(duì)于環(huán)境的適應(yīng)程度。

遺傳算法還有一些其它的概念，這些概念在介紹遺傳算法的原理和執(zhí)行過程時(shí)，再進(jìn)行說明。

遺傳算法的原理

遺傳算法GA把問題的解表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些 假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體” 群。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，它就是問題的最優(yōu)解。

一、遺傳算法的目的

典型的遺傳算法CGA(Canonical Genetic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問題：

考慮對(duì)于一群長(zhǎng)度為L(zhǎng)的二進(jìn)制編碼b_i，i＝1，2，…，n；有

b_i∈{0,1}^L        (3-84)

給定目標(biāo)函數(shù)f，有f(b_i)，并且

0<f(b_i)<∞

同時(shí)
f(b_i)≠f(b_i+1)

求滿足下式

max{f(b_i)|b_i∈{0,1}^L}            (3-85)

的b_i。

很明顯，遺傳算法是一種最優(yōu)化方法，它通過進(jìn)化和遺傳機(jī)理，從給出的原始解群中，不斷進(jìn)化產(chǎn)生新的解，最后收斂到一個(gè)特定的串b_i處，即求出最優(yōu)解。

遺傳算法的基本原理

長(zhǎng)度為L(zhǎng)的n個(gè)二進(jìn)制串bi(i＝1，2，…，n)組成了遺傳算法的初解群，也稱為初始群體。在每個(gè)串中，每個(gè)二進(jìn)制位就是個(gè)體染色體的基因。根據(jù)進(jìn)化術(shù)語，對(duì)群體執(zhí)行的操作有三種：

1．選擇(Selection)

這是從群體中選擇出較適應(yīng)環(huán)境的個(gè)體。這些選中的個(gè)體用于繁殖下一代。故有時(shí)也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代 的個(gè)體時(shí)，是根據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度而決定其繁殖量的，故而有時(shí)也稱為非均勻再生(differential reproduction)。

2．交叉(Crossover)

這是在選中用于繁殖下一代的個(gè)體中，對(duì)兩個(gè)不同的個(gè)體的相同位置的基因進(jìn)行交換，從而產(chǎn)生新的個(gè)體。

3．變異(Mutation)

這是在選中的個(gè)體中，對(duì)個(gè)體中的某些基因執(zhí)行異向轉(zhuǎn)化。在串bi中，如果某位基因?yàn)?，產(chǎn)生變異時(shí)就是把它變成0；反亦反之。

遺傳算法的原理可以簡(jiǎn)要給出如下：

choose an intial population

determine the fitness of each individual

perform selection

repeat

    perform crossover

    perform mutation

    determine the fitness of each individual

    perform selection

until some stopping criterion applies

這里所指的某種結(jié)束準(zhǔn)則一般是指?jìng)€(gè)體的適應(yīng)度達(dá)到給定的閥值；或者個(gè)體的適應(yīng)度的變化率為零。