【正文】 設(shè) G V , E 是一個(gè)圖，其中是 V 頂點(diǎn)集， E 是邊集，旅行商問(wèn)題就是要決定一條通過(guò)所有頂點(diǎn)且每個(gè)頂點(diǎn)只通過(guò)一次的最短 距離回路，這樣的回路就是哈密爾頓回路。 2 增加了編碼變換操作過(guò)程。 簡(jiǎn)言之，混合遺傳算法是在標(biāo)準(zhǔn)遺傳算法中融合了局部搜索方法的思想， 其特點(diǎn)主要體現(xiàn)在下面兩個(gè)方面： 1 引入了局部搜索過(guò)程。另一方面，梯度法、爬山法、模擬退火算法、列表尋優(yōu)法等一些優(yōu)化算法卻具有強(qiáng)的局部搜索能力。并且一般來(lái)說(shuō)，對(duì)不少問(wèn)題，基本遺傳算法的求解效果往往不是最為有效的，它比專(zhuān)門(mén)針對(duì)某一問(wèn)題的知識(shí)性啟發(fā)算法的求解效率要差。 混合遺傳算法 混合遺傳算法簡(jiǎn)述 遺傳算法由于其運(yùn)算簡(jiǎn)單和解決問(wèn)題的有效能力而被廣泛應(yīng)用于眾多領(lǐng)域。遺傳算法中，交叉算子因?yàn)槠淙炙阉髂芰ψ鳛橹饕阕?，變異算子因其局部搜索能力作為輔助算子。這種情況下變異概率應(yīng)取較小值，否則已經(jīng)接近最優(yōu)解的值會(huì)因?yàn)樽儺惗獾狡茐?。遺傳算法引入變異的目的有兩個(gè)：一個(gè)是使遺傳算法具有局部的隨機(jī)搜索能力。例如，基于字符集 0,1 的“二值碼串”，變異操作就 是把 1 變成 0 或者把 0 變成 1。需要指出的是，交叉算子并未提供收斂性保證。但是，遺傳算法的收斂性主要決定于作為其核心操作的交叉算子。 交叉算子與遺傳算法的收斂性關(guān)系。 ④算術(shù)交叉（ Arithmetic Crossover） 算術(shù)交叉是指由兩個(gè)個(gè)體的線(xiàn)性組合而產(chǎn)生出兩個(gè)新的個(gè)體。 ②二點(diǎn)交叉（ Two point crossover） 二點(diǎn)交叉與“一點(diǎn)交叉”類(lèi)似，只是設(shè)值 2 個(gè)交叉點(diǎn)（隨機(jī)設(shè)定）。 基本的交叉算子 ①一點(diǎn)交叉（ One point crossover） 一點(diǎn)交叉又 叫做簡(jiǎn)單交叉。也就是說(shuō)，交叉算子設(shè)計(jì)和編碼設(shè)計(jì)需協(xié)調(diào)操作。 2 交叉算子 交叉算子的設(shè)計(jì) 實(shí)現(xiàn)個(gè)體結(jié)構(gòu)重組的交叉算子設(shè)計(jì)一般與所求解的具體問(wèn)題有關(guān)，一般包括以下一些要點(diǎn)： ① 任何交叉算子需要滿(mǎn)足交叉算子的評(píng)估準(zhǔn)則，就是說(shuō)交叉算子需要保證前一代中優(yōu)秀個(gè)體的性狀能在后一代的新個(gè)體中盡可能得到遺傳和繼承。此外，它和適應(yīng)度比例方法一樣都是一種基于概率的選擇，所以仍然有統(tǒng)計(jì)誤差。 ③排序選擇方法（ Rankbased） 排序選擇方法是指在計(jì)算每個(gè)個(gè)體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個(gè)體排序，然后把事先設(shè)計(jì)好的概率表按順序分配給個(gè)體，作為各自的選擇概率。另外，最佳個(gè)體保存方法還可加以推廣，即在每一代的進(jìn)化過(guò)程中保留多個(gè)最優(yōu)個(gè)體不參加交叉、變異等遺傳操 作，而直接將它們復(fù)制到下一代群體中。也就是說(shuō)，該方法的全局搜索能力不強(qiáng)，它更加適合于單峰性質(zhì)的搜索空間搜索。采用這種選擇方法的優(yōu)點(diǎn)是：進(jìn)化過(guò)程中某一代的最優(yōu)解可以不被交叉和變異操作所破壞。個(gè)體適應(yīng)度越大，被選擇的概率就越高。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的，目前常用的選擇算子有： ①適應(yīng)度比例方法（ Fitness proportional model） 適應(yīng)度比例方法是目前遺傳算法中最基本最常用的選擇方法，它也叫“賭輪”或蒙特卡羅（ Monte Carlo）選擇。選擇算子又叫再生算子（ Reproduction Operator）。這種對(duì)適應(yīng)度的縮放調(diào)整稱(chēng)作適應(yīng)度定標(biāo)。這是因?yàn)檫@些異常個(gè)體競(jìng)爭(zhēng)力太突出，控制了整個(gè)選擇過(guò)程，從而影響了算法的全局優(yōu)化性能。在通常情況下，為了把一個(gè)最小化問(wèn)題轉(zhuǎn)化為最大化問(wèn)題，只需要簡(jiǎn)單的把原函數(shù)乘以 1 即可 . 2 適應(yīng)度尺度變換（適應(yīng)度函數(shù)定標(biāo)） 應(yīng)用遺傳算法時(shí)，常常會(huì)出現(xiàn)一些不利于優(yōu)化的現(xiàn)象或結(jié)果。但是遺傳算法中，適應(yīng)度函數(shù)要進(jìn)行比較排序并且在此基礎(chǔ)上計(jì)算選擇概率，所以適應(yīng)度函數(shù)的值要取正值。 1 目標(biāo)函數(shù)到適應(yīng)度函數(shù)的映射 在許多問(wèn) 題中，目標(biāo)是求費(fèi)用函數(shù) g x 的最小值。遺傳算法的目標(biāo)函數(shù)不受連續(xù)可微的約束且定義域可以為任意集合。另一方面，如果群體規(guī)模太小，會(huì)使遺傳算法的搜索空間分布范圍有限，因此搜索有可能停止在未成熟階段，導(dǎo)致未成熟收斂。群體規(guī)模越大，群體中個(gè)體的多樣性越高，算法陷入局部解的危險(xiǎn)就小。所以在實(shí)際應(yīng)用中，群體個(gè)數(shù)的取值范圍一般在幾十到幾百。這種過(guò)程不斷迭代，直到初始群體中個(gè)體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。 群體設(shè)定 群體的設(shè)定可以采取下面的策略：根據(jù)問(wèn)題固有知識(shí)，設(shè)法把握最優(yōu)解所占空間在整個(gè)問(wèn)題空間的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。雖然此時(shí)也可以把“圖結(jié)構(gòu)”編碼為一維染色體來(lái)處理，但是“圖結(jié)構(gòu)”特性不能在適應(yīng)度評(píng)估中充分體現(xiàn)出來(lái)。 多參數(shù)映射編碼 多參數(shù)映射編碼的基本思想是把每個(gè)參數(shù)先進(jìn)行二值編碼得到子串，再把這些子串連成一個(gè)完整的染色體。用遺傳算法完成此任務(wù)，一個(gè)染色體就代表一個(gè)圖像。此時(shí)若采用一維染色體編碼就顯得不方便了。一維染色體編碼中最常用的符號(hào)集是二值符號(hào)集 0,1 ，基于此符號(hào)集的個(gè)體呈“二值碼串”。反之，由遺傳算法空間向問(wèn)題空間的映射稱(chēng)作譯碼（ Decoding）。這一操作就是編碼。 遺傳算法主要通過(guò)遺傳操作對(duì)群體中具有某種結(jié)構(gòu)形式的個(gè)體施加結(jié)構(gòu)重組處理，從而不斷的搜索出群體中個(gè)體間的結(jié)構(gòu)相似性。 【定義】（模式定理） 在遺傳算子選擇，交叉和變異的作用下，具有低階、短的定義長(zhǎng)度，并且平均適應(yīng)度高于群體平均適應(yīng)度的模式將按“指數(shù)級(jí)”增長(zhǎng)。 定義 模式 H 中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱(chēng)作該模式的定義距離或定義長(zhǎng)度，記作 δ H 。既使具有“同階”的模式，在遺傳操作下，也會(huì)有著不同的性質(zhì)。顯然，一個(gè)模式的“階數(shù)”越高，其樣本數(shù)就越少，因而確定性越高。 定義 模式 H 中確定位置的個(gè)數(shù)稱(chēng)作該模式的模式階，記作 O H 。因此通過(guò)分析模式在遺傳操作下的變化，就可以了解什么性質(zhì)被延續(xù)，什么性質(zhì)被丟棄，從而把握遺傳算法的實(shí)質(zhì)，這正是模式定理所要揭示的內(nèi)容。在引入模式概念后，我們看到的一個(gè)串實(shí)際上隱含著多個(gè)模式，一個(gè)模式可以隱含在多個(gè)串中，不同的“串”之間通過(guò)模式而相互聯(lián)系。在引入模式概念前，我們看到的遺傳算法是：在某一代中， N 個(gè)互不相同的串在選擇、交叉、變異等遺傳算子的作用下產(chǎn)生下一代的 N 個(gè)新的互不相同的串。 [4] 定義 基于三值字符集 0， 1， * 所產(chǎn)生的能描述具有某些結(jié)構(gòu)相似的 0、 1 字符串稱(chēng)作模式?，F(xiàn)在增加一個(gè)通配符“ *” ，“ *”既可以被當(dāng)作“ 0”，又可以被當(dāng)作“ 1”。 模式定理 （ 1） 模式 模式（ schema）是一個(gè)描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。 隨著人們對(duì)遺傳算法研究的不斷深入，可以預(yù)見(jiàn)，會(huì)有更多的理論和方法被引入到遺傳算法中來(lái)。還有其他的算法已被引入到遺傳算法中來(lái)（如禁忌―并行 ，分層），在此， 就不再過(guò)多介紹。在表達(dá)方式上，量子遺傳算法將量子的態(tài)矢量表述引入染色體編碼；在演化機(jī)制上，它利用量子門(mén)實(shí)現(xiàn)染色體演化。 （ 6）量子遺傳算法 量子遺傳算法是量子計(jì)算思想與遺傳算法結(jié)合的產(chǎn)物?；煦邕\(yùn)動(dòng)的上述性質(zhì)作為避免陷入局部極小的優(yōu)化搜索機(jī)制，恰好可以彌補(bǔ)遺傳算法易陷入局部最優(yōu)、收斂速度慢的缺陷。 （ 5）混沌遺傳算法 混沌是自然界廣泛存在的一種非線(xiàn)性現(xiàn)象，它充分體現(xiàn)了系統(tǒng)的復(fù)雜性。其次，在模糊遺傳算法中，采用權(quán)變理論中的以變應(yīng)變的思想。在這里，“論域”即指用隸屬函數(shù)來(lái)表示遺傳算法的優(yōu)化過(guò)程中所采用的約束條件的區(qū)間范圍。其目的是利用模糊優(yōu)化設(shè)計(jì)的優(yōu)點(diǎn)，克服一般遺傳算法優(yōu)化設(shè)計(jì)存在的不足，從而使得系統(tǒng)的優(yōu)化設(shè)計(jì)更靈活、方便，取得好的設(shè)計(jì)效果。用小生境思想來(lái)實(shí)現(xiàn)遺傳算法的選擇操作，使遺傳算法的全局尋優(yōu)能力得到了明顯提高。常用的小生境遺傳算法大多在對(duì)群體進(jìn)行選擇操作前，計(jì)算個(gè)體之間的海明距離，如小于事先設(shè)定值，則對(duì)“適應(yīng)值”低的個(gè)體處以罰函數(shù)，降低其適應(yīng)值。 [4] （ 3）小生境遺傳算法 生物學(xué)上，小生境指在特定環(huán)境中的一種組織功能，它將每一代個(gè)體劃分為若干類(lèi)，每個(gè)類(lèi)中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類(lèi)的優(yōu)秀代表，組成一個(gè)新種群，再在 同一種群中以及不同種群之間進(jìn)行雜交、變異，產(chǎn)生新一代個(gè)體群，同時(shí)采用“預(yù)選擇”機(jī)制或排擠機(jī)制或共享機(jī)制完成選擇操作。 （ 2）免疫遺傳算法 人工免疫算法受生物免疫系統(tǒng)原理的啟發(fā)，針對(duì)求解問(wèn)題特征進(jìn)行人工疫苗接種，可充分利用問(wèn)題本身的信息，和遺傳算法結(jié)合時(shí)，遺傳算法的全局搜索能力及免疫算法的局部?jī)?yōu)化相配合，可大大提高搜索效率。但如果將遺傳算法和模擬退火算法相結(jié)合，互相取長(zhǎng)補(bǔ)短，則有可能開(kāi)發(fā)出性能優(yōu)良的新的全局搜索算法。從統(tǒng)計(jì)物理學(xué)的觀點(diǎn)看 ，隨著溫度的降低，物質(zhì)的能量將逐漸趨近于一個(gè)較低的狀態(tài)，并最終達(dá)到某種平衡?，F(xiàn)將比較常見(jiàn)的混合遺傳算法介紹如下。其中，尤以遺傳算法與其他算法相結(jié)合方面的研究最為引人關(guān)注。和其它方法結(jié) 合的遺傳算法才有生命力。遺傳算法如何提高遺傳算法跳出局部最優(yōu)的能力和如何提高遺傳算法的收斂速度成為近年來(lái)遺傳算法的研究熱點(diǎn)。遺傳算法以其基本思想簡(jiǎn)單、便于實(shí)現(xiàn)和并行搜索的優(yōu)點(diǎn)贏得了眾多學(xué)者和各種工程人員的青睞，是目前應(yīng)用最廣的優(yōu)化搜索算法之一。利用該工具對(duì)兩個(gè)飛機(jī)失事的真實(shí)數(shù)據(jù)庫(kù)進(jìn)行了數(shù)據(jù)挖掘?qū)嶒?yàn)，結(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫(kù)中進(jìn)行搜索，對(duì)隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化 .直到數(shù)據(jù)庫(kù)能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫(kù)中的規(guī)則。 [9] （ 10）數(shù)據(jù)挖掘 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫(kù)技術(shù)，它能夠從大型數(shù)據(jù)庫(kù)中提取隱含的、先前未知的、有潛在應(yīng)用價(jià)值的知識(shí)和規(guī)則。 （ 9）機(jī)器學(xué)習(xí) 學(xué)習(xí)能力是高級(jí)自適應(yīng)系統(tǒng)所具備的能力之一，基于遺傳算法的機(jī)器學(xué)習(xí)，特別是分類(lèi)器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。雖然遺 傳編程的理論尚未成熱，應(yīng)用也有一些限制，但它已成功地應(yīng)用于人工智能、機(jī)器學(xué)習(xí)等領(lǐng)域。雖然人下生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。人下生命與遺傳算法有著密切的關(guān)系。 （ 7）人工生命 人工生命是用計(jì)算機(jī)、機(jī)械等人下媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。遺傳算法在這些圖像處理中的優(yōu)化計(jì)算方面找到了用武之地。在圖像處理過(guò)程中，如掃描、特征提取、圖像分割等不可避免地會(huì)存在一次誤差，從而影響圖像的效果。例如，遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人逆運(yùn)動(dòng)學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方而得到研究和應(yīng)用。 （ 5）機(jī)器人學(xué) 機(jī)器人是一類(lèi)復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來(lái)自于人工自適應(yīng)系統(tǒng)的研究。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計(jì)空間交會(huì)控制器、基于遺傳算法的模糊控制器的優(yōu)化 設(shè)計(jì)、基于遺傳算法的參數(shù)辨識(shí)、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計(jì)和“權(quán)值”學(xué)習(xí)等。 （ 4）自動(dòng)控制 在自動(dòng)控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問(wèn)題需要求解。因此目前現(xiàn)實(shí)生產(chǎn)中也主要靠一些經(jīng)驗(yàn)進(jìn)行調(diào)度。這類(lèi)問(wèn)題包括旅行商問(wèn)題、背包問(wèn)題、裝箱問(wèn)題和圖形劃分等。 （ 2）組合優(yōu)化 隨著問(wèn)題規(guī)模的擴(kuò)大，組合優(yōu)化問(wèn)題的搜索空間急劇增大，甚者有時(shí)無(wú)法求到精確最優(yōu)解。很多人工構(gòu)造的各種各樣復(fù)雜形式的測(cè)試函數(shù)，有連續(xù)函數(shù)也有離散函數(shù)，有單峰函數(shù)也有多峰函數(shù)等，利用這些函數(shù)來(lái)評(píng)價(jià)遺傳算法的性能。 遺傳算法幾個(gè)主要應(yīng)用領(lǐng)域 雖然在各種應(yīng)用領(lǐng)域中，算法的具體實(shí)施細(xì)節(jié)有各自的特點(diǎn)，但遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問(wèn)題的通用框架，它不依賴(lài)于問(wèn)題的具體領(lǐng)域。這說(shuō)明遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。 （ 4）遺傳算法最優(yōu) 迫近。 遺傳算法的初始串集本身就帶有大量與最優(yōu)解甚遠(yuǎn)的信息，通過(guò)選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的串，這是一個(gè)強(qiáng)烈的濾波過(guò)程，并且是一個(gè)并行濾波機(jī)制。遺傳算法只需“適應(yīng)值”和串編碼等通用信息，故幾乎可處理任何問(wèn)題。 （ 2）遺傳算法求解時(shí)使用特定問(wèn)題的信息極少，容易形成通用算法程序。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的，容易誤入局部最優(yōu)解。 遺傳算法的特點(diǎn) （ 1）遺傳算法從問(wèn)題解的中集開(kāi)始嫂索，而不是從單個(gè)解開(kāi)始。也就是說(shuō)，變異 增加了全局優(yōu)化的特質(zhì) . （ 5）全局最優(yōu)收斂 Convergence to the global optimum 當(dāng)最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值，或者最優(yōu)個(gè)體的適應(yīng)度和群體適應(yīng)度不再上升時(shí)，則算法的迭代過(guò)程收斂、算法結(jié)束。但是，它能保證算法過(guò)程不會(huì)產(chǎn)生無(wú)法進(jìn)化的單一群體。 例如有個(gè)體 S＝ 101011。在變異時(shí)，對(duì)執(zhí)行變異的串的“對(duì)應(yīng)位”求反，即把 1 變?yōu)?0，把 0變?yōu)?1。 例如有個(gè)體 S1 100101 S2 010111 選擇它們的左邊 3 位進(jìn)行交叉操作，則有 S1 010101 S2 100111 一般而言，交叉概率 P 取值為 ― 。這個(gè)過(guò)程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。 （ 3）交叉 對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇兩個(gè)個(gè)體的相同位置，按交叉概率 P 交叉。 這樣，就產(chǎn)生了對(duì)環(huán)境適應(yīng)能力較強(qiáng)的后代。 適應(yīng)度較高的個(gè)體，繁殖下一代的數(shù)目較多。適應(yīng)度選擇原則體現(xiàn)了適者生存，