【文章內(nèi)容簡(jiǎn)介】 ystems),開創(chuàng)了基于遺傳算法的機(jī)器學(xué)習(xí)的新概念。 2 1967 年在其博士論文中首次提出了：“遺傳算法”一詞，發(fā)展了復(fù)制、交叉、變異、顯性、倒位等遺傳算子，創(chuàng)立了自適應(yīng)遺傳算法的概念。 3 Jong 1975 年在其博士論文中結(jié)合模式定理進(jìn)行了大量的純數(shù)值函數(shù)優(yōu)化計(jì)算實(shí)驗(yàn)，樹立了遺傳算法的工作框架，定義了評(píng)價(jià)遺傳算法性能的在線指標(biāo)和離線指標(biāo)。 4 1989 年出版了專著《搜索、優(yōu)化和機(jī)器學(xué)習(xí)中的遺傳算法 (Geic Algorithms in Search，Optimization and Machine Learning)》，系統(tǒng)總結(jié)了遺傳算法的主要研究成果，全面而完整的論述了遺傳算法的基本原理及其應(yīng)用。 5 1991 年編輯出版了《遺 傳算法手冊(cè) (Handbook of Geic Algorithms)》書中包括遺傳算法在科學(xué)計(jì)算、工程技術(shù)和社會(huì)經(jīng)濟(jì)中的大量應(yīng)用實(shí)例。 1992 年將遺傳算法應(yīng)用于計(jì)算機(jī)程序的優(yōu)化設(shè)計(jì)及自動(dòng)生成，提出了遺傳編程 (Geic Programming) 的概念，并成功的將其提出的遺傳編程應(yīng)用于人工智能、機(jī)器學(xué)習(xí)符號(hào)處理等方面。 5 遺傳 算法基本原理 遺傳算法是受大自然的啟發(fā)，模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)、具有全局優(yōu)化能力的隨機(jī)搜索算法。 遺傳算法的 思路是通過從給定一個(gè)初始群體出發(fā)，利用選擇算子、交叉算子以及變異算子來模擬自然進(jìn)化的三種原則，逐步改進(jìn)種群，越來越逼近最優(yōu)解，以達(dá)到求解最優(yōu)化問題的目的。在 遺傳算法中，種群中的 每一個(gè) 個(gè)體是問題的一個(gè) 解 ， 稱為“染色體”， 染色體是 一串 符號(hào)，比如二進(jìn)制的 01 串 。這些 染色體 在后續(xù)的迭代中不斷的進(jìn)化，稱為遺傳。在 每一代 中應(yīng)用適應(yīng)度（ fitness） 來 測(cè)量染色體的優(yōu)越性 ， 適應(yīng)度 高的 更容易在自然的選擇中 存活 下來。生存 下來的 染色體被稱為后代 （ offspring） 。 后代通常是前一代染色體通過交叉（ crossover） 或者 變異 （ mutation ） 形成 。新的下一代再重復(fù) 根據(jù) 適應(yīng)度選擇部分后代，淘汰一部分后代，這樣 即 可以 保證 種群染色體的優(yōu)越性，也 保持了 種群大小的穩(wěn)點(diǎn)性。 遺傳算法中每一條染色體，對(duì)應(yīng)著遺傳算法的一個(gè)解決方案，一般我們用適應(yīng)性函數(shù)（ fitness function）來衡量這個(gè)解決方案的優(yōu)劣。所以也可以把遺傳算法的過程看作是一個(gè)在多元函數(shù)里面求最優(yōu)解的過程。在這個(gè)多維曲面里面也有數(shù)不清的 “山峰 ”，而這些最優(yōu)解所對(duì)應(yīng)的就 是 這些山峰 ， 這些山峰就是局部最優(yōu)解 。而其中也會(huì)有一個(gè) “山峰 ”的海拔最高的，那么這個(gè)就是全局最優(yōu)解。而遺傳 算法的任務(wù)就是盡量爬到最高峰，而不是陷落在一些小山峰。（另外，值得注意的是遺傳算法不一定要找 “最高的山峰 ”，如果問題的適應(yīng)度評(píng)價(jià)越小越好的話，那么全局最優(yōu)解就是函數(shù)的最小值，對(duì)應(yīng)的，遺傳算法所要找的就是 “最深的谷底 ”） 。 下面給出生物學(xué)的幾個(gè)基本概念知識(shí)，這對(duì)于理解遺傳算法很重要： 1）遺傳因子（ gene） :DNA 長(zhǎng)鏈結(jié)構(gòu)中占有一定位置的基本遺傳單位，也稱基因。生物的基因根據(jù)物種的不同而多少不一。 2）個(gè)體（ individual） :指染色體帶有特征的實(shí)體。 3）種群（ population） :染色體帶有特征的 個(gè)體的集合。 4）進(jìn)化（ evolution） 。生物在其延續(xù)生命的過程中，逐漸適應(yīng)其生存環(huán)境使得其品質(zhì)不斷得到改良，這種生命現(xiàn)象稱為進(jìn)化。生物的進(jìn)化是以種群的形式進(jìn)行的。 5）適應(yīng)度（ fitness） :度量某個(gè)物種對(duì)于生存環(huán)境的適應(yīng)程度。 6）選擇（ selection） :指以一定的概率從種群中選擇若干個(gè)體的操作。 7）變異（ musation）：復(fù)制時(shí)很小的概率產(chǎn)生的某些復(fù)制差錯(cuò)。 8）編碼（ coding） :DNA 中遺傳信息在一個(gè)長(zhǎng)鏈上按一定的模式排列，也即進(jìn)行了遺傳編碼。遺傳編碼可以看成是從表現(xiàn)型到遺傳子型的 映射。 9）串（ String） :它是 個(gè)體的 形式 ，在算法 中 為二進(jìn)制串，并且對(duì)應(yīng)于遺傳學(xué) 中 的染色體。 10）串 結(jié)構(gòu) 空間 （ ss） ： 在串中，基因任意組合所構(gòu)成的串集合。 基因 操作是在 結(jié)構(gòu) 空間中進(jìn)行的。 串 結(jié)構(gòu)空間 對(duì) 應(yīng)用 于遺傳學(xué) 中的基因 型 的 集合 。 11）染色體：是生物細(xì)胞中含有的一種微小的絲狀化合物，是遺傳物質(zhì)的主要載體，由多個(gè)遺傳因子 — 基因組成。 6 遺傳 算法基本步驟 步驟一 ： 編碼 ： 把 所需要選擇的群體進(jìn)行編號(hào)，每一個(gè)個(gè)體就是 一條 染色體 ，一個(gè) 解就是一串基因的組合 。 步驟二 ： 初始化 ：隨機(jī)生成有 N 個(gè) 個(gè)體的初始群體 ， 這些個(gè) 體一起組成了一個(gè)種群 。遺傳算法 就是 以這個(gè)初始群體為起點(diǎn)開始迭代。參數(shù) N 可以根據(jù) 具體的情況 而定 。 步驟三： 交叉算子：這是遺傳算法最重要的操作。 所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。遺傳算法中起核心作用的就是交叉算子。 步驟四 ： 適應(yīng)度： 確定個(gè)體適應(yīng)度的量化評(píng)價(jià)方法， 適應(yīng)度 用于 衡 量種群中個(gè)體的優(yōu)劣性， 是確定 種群中個(gè)體留存的關(guān)鍵 。 步驟五 ： 選擇 算子： 選擇 的目的是為了從交換后的群體中 選出 優(yōu)良 的 染色體攜帶者，使 它們 有機(jī)會(huì)作為父 代 繁殖 出 下一代群體。選擇 操作 是建立在適應(yīng)度之上的，適應(yīng)度高的被選 中的幾率就大，選擇操作體現(xiàn)出了 生物 適者生存的原 則 。 步驟六 ： 變異 算子：變異 是根據(jù) 生物 遺傳 中基因突變的原理， 以 變異概率 對(duì) 群體中的某一些個(gè)體 的 某些 “位 ”執(zhí)行 變異。 變異 操作可以保證 算法 過程中不會(huì)產(chǎn)生無法進(jìn)化的單一群體， 避免 算法 早熟 出現(xiàn) 局部最優(yōu)。 步驟七 ： 終止 。給定最大的遺傳代數(shù)，算法在計(jì)算到最大的遺傳代數(shù)時(shí)，終止計(jì)算。 遺傳 算法 算法 流程圖 開始編碼初始化染色體種群計(jì)算每個(gè)染色體的適應(yīng)度滿足終止條件根據(jù)適應(yīng)度選擇交叉變異輸出最優(yōu)解是否 7 圖 24 遺傳 算法算法流程圖 遺傳 算法的特點(diǎn) 遺傳算法 屬于進(jìn)化算法 （ Evolutionary Algorithms） 的 一種 ，它通過模仿自然界的選擇與 遺傳的原理來求出最優(yōu)解，遺傳算法 有 三個(gè) 最 基本的算子：選擇、交叉、變異。 數(shù)值 方法求解這一問題的主要手段是迭代運(yùn)算。一般的 迭代 方法容易陷入局部極小的陷阱而出現(xiàn)“ 死循環(huán) ” 現(xiàn)象 ， 使迭代無法進(jìn)行。遺傳算法 很好 地克服了這個(gè)缺點(diǎn)，是一種全局優(yōu)化算法。 遺傳 算法 與 傳統(tǒng)的 優(yōu)化 方法（ 枚舉 ，啟發(fā) 式 等） 相 比較，以生物進(jìn)化為原型 ， 具有很多的 優(yōu)點(diǎn) 。 主要有 以 下幾點(diǎn)： （ 1） 遺傳 算法的本質(zhì)并行性。 首先 ，遺傳算法并行的方式 是 從問題 解 的串 集 開始搜索，而不是從單個(gè)解開始。這是 遺傳算法與 傳統(tǒng)優(yōu)化算法的 最 大區(qū)別。傳統(tǒng) 優(yōu)化 算 法從單個(gè)初始值迭代求最優(yōu)解，容易 早熟 陷入局部最優(yōu)解。遺傳算法 從 串集開始搜索，覆蓋面大，有利于全局最優(yōu)。 其次 ，算法內(nèi) 含 并行性，遺傳算法采用種群方式組織搜索，因而可同時(shí)搜索解空間的多個(gè)區(qū)域，并 相互 交流信息，能以較小的計(jì)算獲得較大收益。 （ 2） 遺傳算法求解時(shí)使用特定問題的信息極少，容易形成通用算法程序 .僅 用 適應(yīng)度函數(shù)值來評(píng)估個(gè)體 ，在 此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度 函數(shù) 不僅不受連續(xù)可微的約束，而且其定義域可以任意的設(shè)定 ， 故幾乎可處理任何問題 。 （ 3） 遺傳算法 不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指導(dǎo) 它 的搜索方向 ，具有 自組織 、自適應(yīng)和自學(xué)習(xí)性。遺傳算法 利用 進(jìn)化過程獲得信息自行組織搜索時(shí)，適應(yīng)度高的個(gè)體具有較高的生存率，并獲得更加適應(yīng)環(huán)境的 染色體 。 這種 通過自然選擇與進(jìn)化的機(jī)制消除了算法設(shè)計(jì)過程中的一個(gè)最大障礙，即需要事先描述問題的 全部 特點(diǎn)， 并 要 說明 針對(duì) 所求 問題的不同 特點(diǎn)， 我們?cè)O(shè)計(jì)的算法應(yīng)該采用的具體 措施 。 所以 ， 遺傳算法有很高的容錯(cuò)能力 ，我 們 可以 利用 遺傳算法 解決復(fù)雜的 非 結(jié)構(gòu)化問題。 （ 4） 遺傳 算法可以直接用于實(shí)際應(yīng)用當(dāng)中，對(duì)于給定的問題，可以產(chǎn)生許多解，最終選擇是根據(jù)用戶自己的需求來選取，通用性 高 ， 實(shí)際 應(yīng)用性強(qiáng) ， 應(yīng)用范圍 廣 。 遺傳 算法的應(yīng)用 遺傳 算法為求解復(fù)雜 系統(tǒng)問題 提供了一種通用的算法框架，它不取決于問題的 具體 領(lǐng)域，有很強(qiáng)的魯棒性 ， 因而被廣泛的 使用 于 組合 優(yōu)化 、 機(jī)械設(shè)計(jì)、人工智能、數(shù)學(xué)建模、軟件工程等領(lǐng)域 。 （ 1） 函數(shù) 優(yōu)化 函數(shù) 優(yōu)化是遺傳算法經(jīng)典的應(yīng)用領(lǐng)域 ，也是 使用最頻繁的 領(lǐng)域 。 尤其是 在數(shù)學(xué)領(lǐng)域，科學(xué)家 構(gòu)造出了 許許多多復(fù)雜 的測(cè)試函數(shù)： 連續(xù) 函數(shù)、離散函數(shù)、凸函數(shù)、凹函數(shù) 、 單峰函數(shù)、多峰函數(shù)等等。對(duì)于 這些 非線性、 求 極 值、 多模型或 多目標(biāo)的 函數(shù) 優(yōu)化 問題，用傳統(tǒng)的優(yōu)化方法很難解決，而用遺傳算法可以 方便地 得到 較好的結(jié)果。 （ 2） 組合優(yōu)化 隨著 變量 n 的 不斷增大，問題的規(guī)模增大，組合優(yōu)化問題的求解空間也急劇增大， 應(yīng) 8 用 傳統(tǒng)的枚舉法等就很難求出最優(yōu)解。對(duì)于 這一類 復(fù)雜的 問題 ， 遺傳 算法 已經(jīng) 被證實(shí)是十分有效的求解方式 。 遺傳 算法 已經(jīng)在求解 TSP 問題、 01 背包 問題、 圖形 劃分問題等方面得到了成功的應(yīng)用。 (3)生產(chǎn)調(diào)度問題 生產(chǎn)調(diào)度問題在很多情況下建立起來的傳統(tǒng)數(shù)學(xué)模難以精確求解，雖然經(jīng)過一些簡(jiǎn)化之后可以進(jìn)行求解 .也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差太大。目前在現(xiàn)實(shí)生產(chǎn)中主要是靠一些經(jīng)驗(yàn)來進(jìn)行調(diào)度。現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效措施。 在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。 （ 4）機(jī)器人 學(xué) 機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。所以，機(jī)器人學(xué)理所當(dāng)然地成為遺傳算法的一個(gè)重要應(yīng)用領(lǐng)域。例如，遺傳算法已經(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）數(shù)據(jù) 挖掘 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù)，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價(jià)值的知識(shí)和規(guī)則。 許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫中進(jìn)行搜索，對(duì)隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化 .直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。 Sunil 已成功地開發(fā)了一個(gè)基于遺傳算法的數(shù)據(jù)挖掘下具。利用該工具對(duì)兩個(gè)飛機(jī)失事的真實(shí)數(shù)據(jù)庫進(jìn)行了數(shù)據(jù)挖掘?qū)嶒?yàn)，結(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一。 （ 6）人工 生命 人工生命是用計(jì)算機(jī)、機(jī)械等人工媒體模擬或構(gòu)造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學(xué)習(xí)能力是人工生命的兩大主要特 征。人工生命與遺傳算法有著密切的關(guān)系。基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論。雖然人工生命的研究尚處于啟蒙階段，但遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力，并且必將得到更為深入的應(yīng)用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人工生命的研究提供一個(gè)有效的工具，人工生命的研究也必將促進(jìn)遺傳算法的進(jìn)一步發(fā)展。 9 3 基于 遺傳 算法求解 TSP問題 旅行商問題， 即 TSP 問題 又譯為旅行推銷員問題， 屬于 NP 完全問題，是 數(shù)學(xué)領(lǐng)域中著 名的 問題之一。 它可以 大致 描述 為 這樣 ： 有一個(gè)旅行商人要拜訪 n 個(gè)城市，他必須要 經(jīng)過所有的城市 ，而且每個(gè)城市只能拜訪一次，最后要回到原來出發(fā)的城市。要求得的路徑路程為所有可能路徑之中的最小值， 即 最優(yōu)值問題 。 可以用如下公式表達(dá) : n1 f(T)= ∑d(ti,ti+1)+d(nt,t1) i=1 本系統(tǒng)是 用遺傳算法求解 45 個(gè) 城市的旅行商問題， 并對(duì)其 進(jìn)行計(jì)算機(jī)仿真，做出一個(gè)能在計(jì)算機(jī) 上 運(yùn)行的軟件 。 方式 編碼是應(yīng)用遺傳算法時(shí)要解決的首要問題，也是設(shè)計(jì)遺傳算法時(shí)的一個(gè)關(guān)鍵步驟。因?yàn)榫幋a方法將會(huì)影響到交叉算 子、變異算子等遺傳算子的運(yùn)算方法，很大 的程度上決定了遺傳進(jìn)化的效率。迄今為止人們已經(jīng)提出了許多種不同的編碼方法?？偟膩碚f，這些編碼方法可以分為三大類：二進(jìn)制編碼法、浮點(diǎn)編碼法、符號(hào)編碼法。下面我們從具體實(shí)現(xiàn)角度出發(fā)介紹其中的幾種主要編碼方法。 ： 它由二進(jìn)制符號(hào) 0 和 1 所組成的二值符號(hào)集。它有以下一些優(yōu)點(diǎn)： (1）編碼、解碼操作簡(jiǎn)單易行 (2)交叉、變異等遺傳操作便于實(shí)現(xiàn) (3)符合最小字符集編碼原則 (4)利用模式定理對(duì)算法進(jìn)行理論分析。 二進(jìn)制編碼的缺點(diǎn)是：對(duì)于一些連續(xù)函數(shù)的優(yōu)化問題，由 于其隨機(jī)性使得其局部搜索能力較差，如對(duì)于一些高精度的問題（如上題），當(dāng)解迫近于最優(yōu)解后，由于其變異后表現(xiàn)型變化很大，不連續(xù)，所以會(huì)遠(yuǎn)離最優(yōu)解，達(dá)不到穩(wěn)定。而格雷碼能有效地防止這類現(xiàn)象。 ： 對(duì)于