【正文】 了解不多，不便于使搜索過程進(jìn)入最有希望的搜索區(qū)域，從而使得模擬退火算法的運算效率不高。許多學(xué)者從不同的角度對遺傳算法進(jìn)行了改進(jìn)，使遺傳算法的尋優(yōu)能力有了不同程度的提高。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略?；谶z傳算法的進(jìn)化模 型是研究人下生命現(xiàn)象的重要基礎(chǔ)理論。 [12] （ 6）圖像處理 圖像處理是計算 機(jī)視覺中的一個重要研究領(lǐng)域。遺傳算法已經(jīng)成為解決復(fù)雜調(diào)度問題的有效工具，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)車間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。遺傳算法主要應(yīng)用于以下幾個主要領(lǐng)域： [17][13] （ 1）函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法 進(jìn)行性能評價的常用例子。 （ 3）遺傳算法有極強(qiáng)的容錯能力。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第 2 步即選擇操作處繼續(xù)循環(huán)執(zhí)行。 （ 4）變異 根據(jù)生物遺傳中基因變異的原理，以變異概率 Pm 對某些個體的某些“位”執(zhí)行變異。適應(yīng)度較小的個體，繁殖下一代的數(shù)目較少；甚至被淘汰。一般取 n＝ 30群體大小 n 太小時難以求出最優(yōu)解，太大則增長收斂時間。對于模式 H＝1xx0xx，有 0 H ＝ 2，δ H ＝ 4。 經(jīng)過這一系列的過程（選擇、交配和突變），產(chǎn)生的新一代個體不同于初始的一代，并“一代一代”向增加整體適應(yīng)度的方向發(fā)展，因 為最好的個體總是更多的被選擇去產(chǎn)生下一代，而適應(yīng)度低的個體逐漸被淘汰掉。一般的遺傳算法都有一個交配概率，范圍一般是 ，這個交配概率反映兩個被選中的個體進(jìn)行交配的概率。在每一代中，每一個個體都被評價，并通過計算適應(yīng)度函數(shù)得到一個適應(yīng)度數(shù)值。 （ 9）適應(yīng)度 Fitness 表示某一個體對于環(huán)境的適應(yīng)程度。 （ 5）基因位置 Gene Position 一個基因在串中的位置稱為基因位置，有時也簡稱基因位?；蛲蛔兒突螂s交可產(chǎn)生更適應(yīng)于環(huán)境的后代。 遺傳算法的基本思想是基于 Darwin 進(jìn)化論和 Mendel 的遺傳學(xué)說的。遺傳算法的基本思想是基于 Darwin 進(jìn)化論和 Mendel 的遺傳學(xué)說的。 遺傳程序設(shè)計是借鑒生物界的自然選擇和遺傳機(jī)制，在遺傳算法的基礎(chǔ)上發(fā)展起來的搜索算法，它已成為進(jìn)化計算的一個新分支?！?Advanced Computational Intelligence》雜志即將發(fā)刊，由模糊集合 h 教授為名譽主編。此外，以遺傳算法的理論基礎(chǔ)為中心的學(xué)術(shù)會議還有 Foundations of Geic Algorithms，該會也是從 1990 年開始隔年召開一次。盡管 De Jong 和 Hollstien 一樣主要側(cè)重于函數(shù)優(yōu)化的應(yīng)用研究，但他將選擇、交叉和變異操作進(jìn)一步完善和系統(tǒng)化，同時又提出了諸如代溝（ generation gap）等新的遺 傳操作技術(shù)。 1967 年， Holland 的學(xué)生在博士論文中首次提出“遺傳算法”（ Geic Algorithms）一詞。接著對改進(jìn)的遺傳算法做了實驗，得出結(jié)果并分析了數(shù)據(jù)。 TSP 問題是古老的經(jīng)典的問題，有關(guān)的研究有幾百年的時間。 geic operator。該理論首次確認(rèn)了結(jié)構(gòu)重組遺傳操作對于獲得并行性的重 要性。該書總結(jié)了遺傳算法研究的主要成果，對遺傳算法及其應(yīng)用作了全面而系統(tǒng)的論述。有關(guān)遺傳算法的學(xué)術(shù)論文也不斷在《 Artificial Intelligence》、《 Machine Learning》、《 Information science》、《 Parallel Computing》、《 Geic Programming and Evoluable Machines》、《 IEEE Transactions on Neural Networks》、《 IEEE Transactions on Signal Processing》等雜志上發(fā)表。自 1985 年以來 .國際上已召開了多次遺傳算法的學(xué)術(shù)會議和研討會 .國際遺傳算法學(xué)會組織召開的 ICGA International Conference on Geic Algorithms 會議和 FOGA Workshop on Foundation of Geic Algorithms 會議。 近年來，遺傳程序設(shè)計運用遺傳算法的思想自動生成計算機(jī)程序解決了許多問題，如預(yù)測、分類、符號回歸和圖像處理等，作為一種新技術(shù)，它已經(jīng)與遺傳算法并駕齊驅(qū)。 遺傳算法簡稱 GA Geic Algorithm ，在本質(zhì)上是一種不依賴具體問題的直接搜索方法。 Mendel 遺傳學(xué)說最重 要的是基因遺傳原理。 （ 4）基因 Gene 基因是串中的元素，基因用于表示個體的特征?；虿僮魇窃诮Y(jié)構(gòu)空間中進(jìn)行的。 在遺傳算法里，優(yōu)化問題 的解被稱為個體，它表示為一個參數(shù)列表，叫做染色體或者基因串。選擇則是根據(jù)新個體的適應(yīng)度進(jìn)行的，適應(yīng)度越高，被選擇的機(jī)會越高，而適應(yīng)度低的，被選擇的機(jī)會就低。再下一步是突變，通過突變產(chǎn)生新的“子”個體。 例如： H 1 x x 0 x x 是一個模式。串長度及編碼形式對算法收斂影響極大 （ 2）適應(yīng)函數(shù)的確定 適應(yīng)函數(shù) fitness function 也稱對象函數(shù) object function ，這是問題求解品質(zhì)的測量函數(shù)；往往也稱為問題的“環(huán)境”。一般取 Pm＝ 0． 010． 2。適應(yīng)度選擇原則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。這個過程反映了隨機(jī)信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個體。但是，它能保證算法過程不會產(chǎn)生無法進(jìn)化的單一群體。 （ 2）遺傳算法求解時使用特定問題的信息極少，容易形成通用算法程序。這說明遺傳算法是采用隨機(jī)方法進(jìn)行最優(yōu)解搜索，選擇體現(xiàn)了向最優(yōu)解迫近，交叉體現(xiàn)了最優(yōu)解的產(chǎn)生，變異體現(xiàn)了全局最優(yōu)解的覆蓋。這類問題包括旅行商問題、背包問題、裝箱問題和圖形劃分等。 （ 5）機(jī)器人學(xué) 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。 （ 7）人工生命 人工生命是用計算機(jī)、機(jī)械等人下媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。 （ 9）機(jī)器學(xué)習(xí) 學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所具備的能力之一，基于遺傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。遺傳算法以其基本思想簡單、便于實現(xiàn)和并行搜索的優(yōu)點贏得了眾多學(xué)者和各種工程人員的青睞，是目前應(yīng)用最廣的優(yōu)化搜索算法之一?，F(xiàn)將比較常見的混合遺傳算法介紹如下。 [4] （ 3）小生境遺傳算法 生物學(xué)上，小生境指在特定環(huán)境中的一種組織功能，它將每一代個體劃分為若干類，每個類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代表，組成一個新種群，再在 同一種群中以及不同種群之間進(jìn)行雜交、變異，產(chǎn)生新一代個體群，同時采用“預(yù)選擇”機(jī)制或排擠機(jī)制或共享機(jī)制完成選擇操作。在這里，“論域”即指用隸屬函數(shù)來表示遺傳算法的優(yōu)化過程中所采用的約束條件的區(qū)間范圍。 （ 6）量子遺傳算法 量子遺傳算法是量子計算思想與遺傳算法結(jié)合的產(chǎn)物。 模式定理 （ 1） 模式 模式（ schema）是一個描述字符串集的模板，該字符串集中的串的某些位置上存在相似性。在引入模式概念后，我們看到的一個串實際上隱含著多個模式，一個模式可以隱含在多個串中，不同的“串”之間通過模式而相互聯(lián)系。既使具有“同階”的模式，在遺傳操作下，也會有著不同的性質(zhì)。這一操作就是編碼。用遺傳算法完成此任務(wù)，一個染色體就代表一個圖像。這種過程不斷迭代，直到初始群體中個體數(shù)目達(dá)到了預(yù)先確定的規(guī)模。遺傳算法的目標(biāo)函數(shù)不受連續(xù)可微的約束且定義域可以為任意集合。這是因為這些異常個體競爭力太突出，控制了整個選擇過程，從而影響了算法的全局優(yōu)化性能。個體適應(yīng)度越大，被選擇的概率就越高。 ③排序選擇方法（ Rankbased） 排序選擇方法是指在計算每個個體的適應(yīng)度后，根據(jù)適應(yīng)度大小順序?qū)θ后w中個體排序，然后把事先設(shè)計好的概率表按順序分配給個體，作為各自的選擇概率。 基本的交叉算子 ①一點交叉（ One point crossover） 一點交叉又 叫做簡單交叉。但是，遺傳算法的收斂性主要決定于作為其核心操作的交叉算子。這種情況下變異概率應(yīng)取較小值，否則已經(jīng)接近最優(yōu)解的值會因為變異而遭到破壞。另一方面，梯度法、爬山法、模擬退火算法、列表尋優(yōu)法等一些優(yōu)化算法卻具有強(qiáng)的局部搜索能力。下面為用 EXCEL 畫的一個 51 個城市的坐標(biāo)。 適應(yīng)函數(shù)度 因為要求城市的最短距離，所以適應(yīng)度函數(shù)就是各距離的倒數(shù) 選擇算子的設(shè)計 從群體中選擇優(yōu)勝的個體，淘汰劣質(zhì)個體的操作叫做選擇。采用這種選擇方法的優(yōu)點是：進(jìn)化過程中某一代的最優(yōu)解可以不被交叉和變異操作 所破壞。也就是說，交叉算子設(shè)計和編碼設(shè)計需協(xié)調(diào)操作。 遺傳算法引入 變異的目的有兩個：一個是使遺傳算法具有局部的隨機(jī)搜索能力。 （ 2）倒位變異 倒位變異也稱為逆轉(zhuǎn)變異。 比 較一組，二組，三組，四組，五組。 例如上面的 child1 456792813 產(chǎn)生了 par1 135792468 中沒有的線路 4 5 6 和 6 7 9 2 8. OX（順序交叉） 操作保留了部分城市的相對訪問順序，但是它也更多的產(chǎn)生出了父代巡回路線中所沒有的部分新路線。 （ 1）改進(jìn)的算法求同一城市問題（ 51 個城市）： 初始種群為 POPSIZE、最大遺傳代數(shù)為 GENS、交叉概率 PXOVER、變異概率 PMUTATION、最大值 FLT_ +308 如下表：（ .1） 城市 POPSIZE PXOVER PMUTATION CENS 51 100 2021 表（ .1） 次數(shù) 第一次 第二次 第三次 第四次 第五次 第六次 第七次 第八次 第九次 第十次 平均值 最好值 最短距離 438 452 440 450 454 439 448 470 457 448 449 438 最小生成代數(shù) 1680 1919 1306 1830 1992 1919 1653 1671 1989 1903 1791 1306 表（ .2） 最好結(jié)果：代數(shù)： 1680 最短路徑 438 路徑： 48 23 7 43 24 25 14 6 27 46 51 12 5 37 17 4 47 18 13 41 40 19 42 44 15 45 33 39 10 30 34 21 16 50 9 49 38 11 32 1 22 2 29 20 35 36 3 28 31 26 8 下面為 51 個城市一定“比率尺”下的相對坐標(biāo)： 1 37， 52 2 49 ， 49 3 52 ， 64 4 20， 26 5 40 ， 30 6 21 ， 47 7 17， 63 8 31 ， 62 9 52， 33 10 51 ， 21 11 42 ， 41 12 31， 32 13 5， 25 14 12 ，42 15 36， 16 16 52 ， 41 17 27 ， 23 18 17， 33 19 13 ， 13 20 57 ， 58 21 62， 42 22 42 ， 57 23 16 ， 57 24 8， 52 25 7， 38 26 27 ， 68 27 30 ， 48 28 43， 67 29 58， 48 30 58 ， 27 31 37， 69 32 38 ， 46 33 46， 10 34 61 ， 33 35 62 ，63 36 63 ， 69 37 32 ， 22 38 45， 35 39 59， 15 40 5 ， 6 41 10 ， 17 42 21 ，10 43 5， 64 44 30， 15 45 39 ， 10 46 32， 39 47 25 ， 32 48 25， 55 49 48， 28 50 56 ， 37 51 30 ， 40 坐標(biāo)對應(yīng)的圖（ .1） 下面畫出我試驗中最好結(jié)果的路徑圖： 路徑從第 48 個城市開始，它的坐標(biāo)是 48（ 25， 55） 從 48 237 43 依次畫出得下圖（ .2）
。 絕對順序就是 3 在 1 的后面且相臨，相對順序就不一定相臨。 （ 2）比較六組，七組，八組，二組，九組： 橫軸交叉概率，豎軸“最有解”（交叉概率 ，變異概率 ）如圖（ .2） 圖（ .2） 分析交叉概率從 0 到 之間，最優(yōu)值隨交叉概的增大變小，變小是我們愿意看到的，變異概率從 到 1 時，最優(yōu)值浮動于一個值，所以我們的交叉要取大于 的一 個值。 A 1 2 3 | 4 5 6｜ 7 8 9 0 1 2 3｜ 6 5 4 | 7 8 9 0 （ 3）交換變異 交換變異也稱為對換變