生物的進化是一個奇妙的優(yōu)化過程，它通過選擇淘汰，突然變異，基因遺傳等規(guī)律產(chǎn)生適應環(huán)境變化的優(yōu)良物種。遺傳算法是根據(jù)生物進化思想而啟發(fā)得出的一種全局優(yōu)化算法。
遺傳算法的概念最早是由Bagley
J.D在1967年提出的；而開始遺傳算法的理論和方法的系統(tǒng)性研究的是1975年，這一開創(chuàng)性工作是由Michigan大學的J.H.Holland所實行。當時，其主要目的是說明自然和人工系統(tǒng)的自適應過程。
遺傳算法簡稱GA(Genetic Algorithm)，在本質上是一種不依賴具體問題的直接搜索方法。遺傳算法在模式識別、神經(jīng)網(wǎng)絡、圖像處理、機器學習、工業(yè)優(yōu)化控制、自適應控制、生物科學、社會科學等方面都得到應用。在人工智能研究中，現(xiàn)在人們認為“遺傳算法、自適應系統(tǒng)、細胞自動機、混沌理論與人工智能一樣，都是對今后十年的計算技術有重大影響的關鍵技術”。
1.1 遺傳算法的基本概念
遺傳算法的基本思想是基于Darwin進化論和Mendel的遺傳學說的。
Darwin進化論最重要的是適者生存原理。它認為每一物種在發(fā)展中越來越適應環(huán)境。物種每個個體的基本特征由后代所繼承，但后代又會產(chǎn)生一些異于父代的新變化。在環(huán)境變化時，只有那些能適應環(huán)境的個體特征方能保留下來。
Mendel遺傳學說最重要的是基因遺傳原理。它認為遺傳以密碼方式存在細胞中，并以基因形式包含在染色體內(nèi)。每個基因有特殊的位置并控制某種特殊性質；所以，每個基因產(chǎn)生的個體對環(huán)境具有某種適應性。基因突變和基因雜交可產(chǎn)生更適應于環(huán)境的后代。經(jīng)過存優(yōu)去劣的自然淘汰，適應性高的基因結構得以保存下來。
由于遺傳算法是由進化論和遺傳學機理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個算法中要用到各種進化和遺傳學的概念。
這些概念如下：
一、串(String)
它是個體(Individual)的形式，在算法中為二進制串，并且對應于遺傳學中的染色體(Chromosome)。
二、群體(Population)
個體的集合稱為群體，串是群體的元素
三、群體大小(Population Size)
在群體中個體的數(shù)量稱為群體的大小。
四、基因(Gene)
基因是串中的元素，基因用于表示個體的特征。例如有一個串S＝1011，則其中的1，0，1，1這4個元素分別稱為基因。它們的值稱為等位基因(Alletes)。
五 、基因位置(Gene Position)
一個基因在串中的位置稱為基因位置，有時也簡稱基因位�；蛭恢糜纱淖笙蛴矣嬎�，例如在串S＝1101中，0的基因位置是3。基因位置對應于遺傳學中的地點(Locus)。
六、基因特征值(Gene Feature)
在用串表示整數(shù)時，基因的特征值與二進制數(shù)的權一致；例如在串S=1011中，基因位置3中的1，它的基因特征值為2；基因位置1中的1，它的基因特征值為8。
七、串結構空間SS
在串中，基因任意組合所構成的串的集合�；虿僮魇窃诮Y構空間中進行的。串結構空間對應于遺傳學中的基因型(Genotype)的集合。
八、參數(shù)空間SP
這是串空間在物理系統(tǒng)中的映射，它對應于遺傳學中的表現(xiàn)型(Phenotype)的集合。
九、非線性
它對應遺傳學中的異位顯性(Epistasis)
十、適應度(Fitness)
表示某一個體對于環(huán)境的適應程度。
遺傳算法還有一些其它的概念，這些概念在介紹遺傳算法的原理和執(zhí)行過程時，再進行說明。
1.2 遺傳算法的原理
遺傳算法GA把問題的解表示成“染色體”，在算法中也即是以二進制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設解。然后，把這些假設解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應環(huán)境的“染色體”進行復制，再通過交叉，變異過程產(chǎn)生更適應環(huán)境的新一代“染色體”群。這樣，一代一代地進化，最后就會收斂到最適應環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。
一、遺傳算法的目的
典型的遺傳算法CGA(Canonical Genetic Algorithm)通常用于解決下面這一類的靜態(tài)最優(yōu)化問題：
考慮對于一群長度為L的二進制編碼bi，i＝1，2，…，n；有
bi∈{0,1}L
(3-84)
給定目標函數(shù)f，有f(bi)，并且
0<f(bi)<∞
同時
f(bi)≠f(bi+1)
求滿足下式
max{f(bi)|bi∈{0,1}L}
(3-85)
的bi。
很明顯，遺傳算法是一種最優(yōu)化方法，它通過進化和遺傳機理，從給出的原始解群中，不斷進化產(chǎn)生新的解，最后收斂到一個特定的串bi處，即求出最優(yōu)解。
二、遺傳算法的基本原理
長度為L的n個二進制串bi(i＝1，2，…，n)組成了遺傳算法的初解群，也稱為初始群體。在每個串中，每個二進制位就是個體染色體的基因。根據(jù)進化術語，對群體執(zhí)行的操作有三種：
1．選擇(Selection)
這是從群體中選擇出較適應環(huán)境的個體。這些選中的個體用于繁殖下一代。故有時也稱這一操作為再生(Reproduction)。由于在選擇用于繁殖下一代的個體時，是根據(jù)個體對環(huán)境的適應度而決定其繁殖量的，故而有時也稱為非均勻再生(differential
reproduction)。
2．交叉(Crossover)
這是在選中用于繁殖下一代的個體中，對兩個不同的個體的相同位置的基因進行交換，從而產(chǎn)生新的個體。
3．變異(Mutation)
這是在選中的個體中，對個體中的某些基因執(zhí)行異向轉化。在串bi中，如果某位基因為1，產(chǎn)生變異時就是把它變成0；反亦反之。
遺傳算法的原理可以簡要給出如下：
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
這里所指的某種結束準則一般是指個體的適應度達到給定的閥值；或者個體的適應度的變化率為零。
三、遺傳算法的步驟和意義
1．初始化
選擇一個群體，即選擇一個串或個體的集合bi，i=1，2，...n。這個初始的群體也就是問題假設解的集合。一般取n＝30-160。
通常以隨機方法產(chǎn)生串或個體的集合bi,i＝1，2，...n。問題的最優(yōu)解將通過這些初始假設解進化而求出。
2．選擇
根據(jù)適者生存原則選擇下一代的個體。在選擇時，以適應度為選擇原則。適應度準則體現(xiàn)了適者生存，不適應者淘汰的自然法則。
給出目標函數(shù)f，則f(bi)稱為個體bi的適應度。以
(3-86)
