【正文】 代的新變化。在環(huán)境變化時(shí)，只有那些能適應(yīng)環(huán)境的個體特征方能保留下來。 Mendel 遺傳學(xué)說最重 要的是基因遺傳原理。它認(rèn)為遺傳以密碼方式存在細(xì)胞中，并以基因形式包含在染色體內(nèi)。每個基因有特殊的位置并控制某種特殊性質(zhì)；所以，每個基因產(chǎn)生的個體對環(huán)境具有某種適應(yīng)性?；蛲蛔兒突螂s交可產(chǎn)生更適應(yīng)于環(huán)境的后代。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。 由于遺傳算法是由進(jìn)化論和遺傳學(xué)機(jī)理而產(chǎn)生的直接搜索優(yōu)化方法；故而在這個算法中要用到各種進(jìn)化和遺傳學(xué)的概念。 [19] 這些概念如下： 1 串 String 它是個體 Individual 的形式，在算法中為二進(jìn)制串，并且對應(yīng)于遺傳學(xué)中的染色體 Chromosome 。 2 群體 Population 個體的集合稱為群體，“串”是群體的元素 （ 3）群體大小 Population Size 在群體中個體的數(shù)量稱為群體的大小。 （ 4）基因 Gene 基因是串中的元素，基因用于表示個體的特征。例如有一個串 S＝ 1011，則其中的 1， 0， 1， 1 這 4 個元素分別稱為基因。它們的值稱為等位基因。 （ 5）基因位置 Gene Position 一個基因在串中的位置稱為基因位置，有時(shí)也簡稱基因位?；蛭恢糜纱畯淖笙蛴矣?jì)算，例如在串 S＝ 1101 中， 0 的基因位置 是 3?；蛭恢脤?yīng)于遺傳學(xué)中的地點(diǎn) Locus 。 （ 6）基因特征值 Gene Feature 在用“二進(jìn)制串”表示整數(shù)時(shí)，基因的特征值與二進(jìn)制數(shù)的權(quán)一致；例如在串 S 1011 中，基因位置 3 中的 1，它的基因特征值為 2；基因位置 1 中的 1，它的基因特征值為 8。 （ 7）串結(jié)構(gòu)空間（ SS） 在串中，基因任意組合所構(gòu)成的串的集合?；虿僮魇窃诮Y(jié)構(gòu)空間中進(jìn)行的。串結(jié)構(gòu)空間對應(yīng)于遺傳學(xué)中的基因型 Genotype 的集合。 （ 8）參數(shù)空間 SP 這是“串空間”在物理系統(tǒng)中的映射，它對應(yīng)于遺傳學(xué)中的表現(xiàn)型 Phenotype 的集合。 （ 9）適應(yīng)度 Fitness 表示某一個體對于環(huán)境的適應(yīng)程度。 遺傳算法的原理 遺傳算法 GA 把“問題的解”表示成“染色體”，在算法中也即是以二進(jìn)制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群“染色體”，也即是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體”進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體”群。這樣，“一代一代”地進(jìn)化，最后就會收斂到最適應(yīng)環(huán)境的一個“染色體”上，它就是問題的最優(yōu)解。 在遺傳算法里，優(yōu)化問題 的解被稱為個體，它表示為一個參數(shù)列表，叫做染色體或者基因串。染色體一般被表達(dá)為簡單的字符串或數(shù)字串，不過也有其他的表示方法適用，這一過程稱為編碼。 一開始，算法隨機(jī)生成一定數(shù)量的個體，有時(shí)候操作者也可以對這個隨機(jī)產(chǎn)生過程進(jìn)行干預(yù)，播下已經(jīng)部分優(yōu)化的種子。在每一代中，每一個個體都被評價(jià)，并通過計(jì)算適應(yīng)度函數(shù)得到一個適應(yīng)度數(shù)值。種群中的“個體”被按照適應(yīng)度排序，適應(yīng)度高的在前面。這里的“高”是相對于初始的種群的“低適應(yīng)度”來說的。 下一步是產(chǎn)生下一代個體并組成種群。這個過程是通過選擇和交叉完成的，其中繁殖包括 crossover 和突變 mutation 。選擇則是根據(jù)新個體的適應(yīng)度進(jìn)行的，適應(yīng)度越高，被選擇的機(jī)會越高，而適應(yīng)度低的，被選擇的機(jī)會就低。初始的數(shù)據(jù)可以通過這樣的選擇過程組成一個相對優(yōu)化的群體。之后，被選擇的個體進(jìn)入交配過程。一般的遺傳算法都有一個交配概率，范圍一般是 ，這個交配概率反映兩個被選中的個體進(jìn)行交配的概率。例如，交配概率為 ，則80%的“夫妻”會生育后代。每兩個個體通過交配產(chǎn)生兩個新個體，代替原來的“老”個體，而沒交配的個體則保持不變。交配父母的染色體相互交換，從而產(chǎn)生兩個新 的染色體，第一個個體前半段是父親的染色體，后半段是母親的，第二個個體則正好相反。不過這里的半段并不是真正的一半，這個位置叫做交配點(diǎn)，也是隨機(jī)產(chǎn)生的，可以是染色體的任意位置。再下一步是突變，通過突變產(chǎn)生新的“子”個體。一般遺傳算法都有一個固定的突變常數(shù)，通常是 或者更小，這代表變異發(fā)生的概率。根據(jù)這個概率，新個體的染色體隨機(jī)的突變，通常就是改變?nèi)旧w的一個字節(jié)（ 0 變到 1，或者 1 變到 0）。 經(jīng)過這一系列的過程（選擇、交配和突變），產(chǎn)生的新一代個體不同于初始的一代，并“一代一代”向增加整體適應(yīng)度的方向發(fā)展，因 為最好的個體總是更多的被選擇去產(chǎn)生下一代，而適應(yīng)度低的個體逐漸被淘汰掉。這樣的過程不斷的重復(fù)：每個“個體”被評價(jià)，計(jì)算出適應(yīng)度，兩個個體交配，然后突變，產(chǎn)生第三代。周而復(fù)始，直到終止條件滿足為止。 遺傳算法的基礎(chǔ)理論是摸式定理。它的有關(guān)內(nèi)容如下： 1 摸式 Schema 概念 [1] 一個基因串用符號集 0， 1， * 表示，則稱為一個因式；其中 *可以是 0 或 1。 例如： H 1 x x 0 x x 是一個模式。 2 摸式的“階”和“長度” 摸式中 0 和 1 的個數(shù)稱為模式的階，并用 0 H 表示。模式中第 1 個數(shù)字串和最后 一個數(shù)字串間的距離稱為模式的長度，并用δ H 表示。對于模式 H＝1xx0xx，有 0 H ＝ 2，δ H ＝ 4。 3 Holland 摸式定理 低階，短長度的模式在群體遺傳過程中將會按指數(shù)規(guī)律增加。當(dāng)群體的大小為 n 時(shí)，每代處理的模式數(shù)目為 0 n3 。 法在應(yīng)用中關(guān)鍵的問題 （ 1）串的編碼方式 這本質(zhì)是問題編碼。一般把問題的各種參數(shù)用二進(jìn)制編碼，構(gòu)成子串；然后把子串拼接構(gòu)成“染色體”串。串長度及編碼形式對算法收斂影響極大 （ 2）適應(yīng)函數(shù)的確定 適應(yīng)函數(shù) fitness function 也稱對象函數(shù) object function ，這是問題求解品質(zhì)的測量函數(shù)；往往也稱為問題的“環(huán)境”。一般可以把問題的模型函數(shù)作為對象函數(shù)；但有時(shí)需要另行構(gòu)造。 （ 3）遺傳算法自身參數(shù)設(shè)定 遺傳算法自身參數(shù)有 3 個，即群體大小 n、交叉概率 Pc和變異概率 Pm。群體大小 n 太小時(shí)難以求出最優(yōu)解，太大則增長收斂時(shí)間。一般 n＝ 30交叉概率 Pc 太小時(shí)難以向前搜索，太大則容易破壞“高適應(yīng)值”的結(jié)構(gòu)。一般取 Pc 。變異概率 Pm 太小時(shí)難以產(chǎn)生新的基因結(jié)構(gòu)，太大使遺傳算法成了單純的隨機(jī)搜索。一般取 Pm＝ 0． 010． 2。 法基 本操作 （ 1）初始化 選擇一個群體，即選擇一個串或個體的集合 bi， i 1， 2， ...n。這個初始的群體也就是問題假設(shè)解的集合。一般取 n＝ 30 通常以隨機(jī)方法產(chǎn)生串或個體的集合 bi,i＝ 1， 2， ...n。問題的最優(yōu)解將通過這些初始假設(shè)解進(jìn)化而求出。 [5] （ 2）選擇 根據(jù)適者生存原則選擇下一代的個體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度選擇原則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。給出目標(biāo)函數(shù) f，則f bi 稱為個體 bi 的適應(yīng)度。 適應(yīng)度較高的個體，繁殖下一代的數(shù)目較多。適應(yīng)度較小的個體，繁殖下一代的數(shù)目較少；甚至被淘汰。 這樣，就產(chǎn)生了對環(huán)境適應(yīng)能力較強(qiáng)的后代。對于問題求解角度來講，就是選擇出和最優(yōu)解較接近的中間解。 （ 3）交叉 對于選中用于繁殖下一代的個體，隨機(jī)地選擇兩個個體的相同位置，按交叉概率 P 交叉。在選中的位置實(shí)行交換。這個過程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個體。交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。 例如有個體 S1 100101 S2 010111 選擇它們的左邊 3 位進(jìn)行交叉操作，則有 S1 010101 S2 100111 一般而言，交叉概率 P 取值為 ― 。 （ 4）變異 根據(jù)生物遺傳中基因變異的原理，以變異概率 Pm 對某些個體的某些“位”執(zhí)行變異。在變異時(shí)，對執(zhí)行變異的串的“對應(yīng)位”求反，即把 1 變?yōu)?0，把 0變?yōu)?1。變異概率 Pm 與生物變異極小的情況一致，所以， Pm 的取值較小，一般取 。 例如有個體 S＝ 101011。 對其的第 1， 4 位置的基因進(jìn)行變異，則有 001111 單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進(jìn)化的單一群體。因?yàn)樵谒械膫€體一樣時(shí)，交叉是無法產(chǎn)生新的個體的，這時(shí)只能靠變異產(chǎn)生新的個體。也就是說，變異 增加了全局優(yōu)化的特質(zhì) . （ 5）全局最優(yōu)收斂 Convergence to the global optimum 當(dāng)最優(yōu)個體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，則算法的迭代過程收斂、算法結(jié)束。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第 2 步即選擇操作處繼續(xù)循環(huán)執(zhí)行。 遺傳算法的特點(diǎn) （ 1）遺傳算法從問題解的中集開始嫂索，而不是從單個解開始。 這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個初始值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。遺 傳算法從“串集”開始搜索，覆蓋面大，利于全局擇優(yōu)。 （ 2）遺傳算法求解時(shí)使用特定問題的信息極少，容易形成通用算法程序。 由于遺傳算法使用“適應(yīng)值”這一信息進(jìn)行搜索，并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息。遺傳算法只需“適應(yīng)值”和串編碼等通用信息，故幾乎可處理任何問題。 （ 3）遺傳算法有極強(qiáng)的容錯能力。 遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串，這是一個強(qiáng)烈的濾波過程，并且是一個并行濾波機(jī)制。故而，遺傳算法有很高的容錯能力。 （ 4）遺傳算法最優(yōu) 迫近。 遺傳算法中的選擇、交叉和變異都是隨機(jī)操作，而不是確定的精確規(guī)則。這說明遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。 （ 5）遺傳算法具有隱含的并行性。 遺傳算法幾個主要應(yīng)用領(lǐng)域 雖然在各種應(yīng)用領(lǐng)域中，算法的具體實(shí)施細(xì)節(jié)有各自的特點(diǎn)，但遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域。遺傳算法主要應(yīng)用于以下幾個主要領(lǐng)域： [17][13] （ 1）函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法 進(jìn)行性能評價(jià)的常用例子。很多人工構(gòu)造的各種各樣復(fù)雜形式的測試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)，有單峰函數(shù)也有多峰函數(shù)等，利用這些函數(shù)來評價(jià)遺傳算法的性能。對于非線性、多目標(biāo)的函數(shù)優(yōu)化問題，用其他算法通常較難求解，但使用遺傳算法卻很方便并可以得到較好的結(jié)果。 （ 2）組合優(yōu)化 隨著問題規(guī)模的擴(kuò)大，組合優(yōu)化問題的搜索空間急劇增大，甚者有時(shí)無法求到精確最優(yōu)解。對于這類復(fù)雜問題，使用遺傳算法求解可行解就顯得更加有實(shí)際價(jià)值。這類問題包括旅行商問題、背包問題、裝箱問題和圖形劃分等。 （ 3）生成調(diào)度 生產(chǎn)調(diào)度問題在很多情況下 所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解，也因簡化太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。因此目前現(xiàn)實(shí)生產(chǎn)中也主要靠一些經(jīng)驗(yàn)進(jìn)行調(diào)度。遺傳算法已經(jīng)成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。 （ 4）自動控制 在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解。遺傳算法已在其中得到了初步的應(yīng)用，并顯示出良好的效果。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計(jì)空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化 設(shè)計(jì)、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和“權(quán)值”學(xué)習(xí)等。都顯出了遺傳算法在這此領(lǐng)域中應(yīng)用的可能性。 （ 5）機(jī)器人學(xué) 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。所以，機(jī)器人學(xué)理所當(dāng)然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域。例如，遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動軌跡規(guī)劃、機(jī)器人逆運(yùn)動學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方而得到研究和應(yīng)用。 [12] （ 6）圖像處理 圖像處理是計(jì)算 機(jī)視覺中的一個重要研究領(lǐng)域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在一次誤差，從而影響圖像的效果。如何使這些誤差最小是使計(jì)算機(jī)視覺達(dá)到實(shí)用化的重要要求。遺傳算法在這些圖像處理中的優(yōu)化計(jì)算方面找到了用武之地。目前已在模式識別 包括漢字識別 、圖像恢復(fù)、圖像邊緣特征提取等方而得到了應(yīng)用。 （ 7）人工生命 人工生命是用計(jì)算機(jī)、機(jī)械等人下媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人下生命的兩大主要特征。人下生命與遺傳算法有著密切的關(guān)系?；谶z傳算法的進(jìn)化模 型是研究人下生命現(xiàn)象的重要基礎(chǔ)理論。雖然人下生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人下生命的研究提供一個有效的下具，人下生命的研究也必將促進(jìn)遺傳算法的進(jìn)一步發(fā)展 .[12] （ 8）遺傳編程 1989 年，美國 Standford 大學(xué)的 Koza 教授發(fā)展了遺傳編