搜尋技術——遺傳算法

如果有興趣了解更多相關内容，歡迎來我的個人網站看看：瞳孔空間

一：進化與遺傳的概念

拉馬克(Lamarck)進化論：

• 一切物種都是其他物種演變和進化而來的，而生物的演變和進化是一個緩慢和連續的過程
• 環境的變化能夠引起生物的變異，環境的變化迫使生物發生适應性的進化
• 有神經系統的動物發生變異的原因，除了環境變化和雜交外，更重要是通過用進廢退和獲得性狀遺傳
• 生物進化的方向從簡單到複雜，從低到高
• 最原始的生物起源于自然發生。生物并不起源于共同祖先
• 拉馬克曾以長頸鹿的進化為例，說明他的“用進廢退”觀點。長頸鹿的祖先頸部并不長，由于幹旱等原因。在低處已找不到食物，迫使它伸長脖頸去吃高處的樹葉，久而久之，它的頸部就變長了。一代又一代，遺傳下去，它的脖子越來越長，終于進化為現在我們所見的長頸鹿

達爾文(Darwin)進化論：

• 包括兩部分：遺傳(基因)變異；自然選擇
• 生物不是靜止的，而是進化的。物種不斷變異，舊物種消滅，新物種産生
• 生物的進化是連續和逐漸，不會發生突變
• 生物之間存在一定的親緣關系，他們具有共同的祖先
• 自然選擇。生物過渡繁殖，但是它們的生存空間和食物有限，進而面臨生存鬥争，包括：種内、種間以及生物與環境的鬥争。自然選擇是達爾文進化論的核心
• 達爾文摒棄了Lamarck獲得性遺傳法則
• 胚胎學家Weismann用如下實驗：22代連續切割小鼠尾巴而第23代小鼠尾巴仍然不變短，明确否定了獲得性遺傳的觀點

孟德爾學說：1857年，身為神父的孟德爾通過對植物進行一系列仔細的實驗，發現植物的父母單獨地把自身的特征傳遞給下一代。至關重要的是，他還發現特征不是單純地混合在一起，而是保持着獨立性：一株高的植物和一株矮的植物繁殖出來的後代要麼是高的，要麼是矮的，而不是介于兩者之間。表明特征是分開獨立地遺傳給下一代，後來這被稱為遺傳基因。讓人驚奇的是，孟德爾的重要發現被人們忽略了數十年，直到20世紀初才被人們認可。

新達爾文主義：

• 将達爾文進化論和孟德爾-摩根基因相結合，成為現被廣泛接受的新達爾文主義
• 新達爾文注意認為，隻用種群上和物種内的少量統計過程就可以充分地解釋大多數生命曆史，這些過程就是繁殖、變異、競争、選擇。繁殖是所有生命的共同特性；變異保證了任何生命系統能在正熵世界中連續繁殖自己；對于限制在有限區域中的不斷膨脹的種群來說，競争和選擇是不可避免的結論

生物中的遺傳概念：

• 在生物細胞中，控制并決定生物遺傳特性的物質是脫氧核糖核酸，簡稱DNA。染色體是其載體
• DNA是由四種堿基按一定規則排列組成的長鍊。四種堿基不同的排列決定了生物不同的表現性狀。例如，改變DNA長鍊中的特定一段（稱為基因），即可改變人體的身高
• 細胞在分裂時，DNA通過複制而轉移到新産生的細胞中，新的細胞就繼承了上一代細胞的基因
• 在繁殖下一代時，兩個同源染色體之間通過交叉而重組，亦即在兩個染色體的某一相同位置處DNA被切斷，其前後兩串分别交叉形成兩個新的染色體
• 在細胞進行複制時可能以很小的機率産生某些複制差錯，進而使DNA發生某種變異，産生新的染色體
• 這些新的染色體将決定新的個體（後代）的新的性狀
• 在一個群體中，并不是所有的個體都能得到相同的繁殖機會，對生存環境适應度高的個體将獲得更多的繁殖機會；對生存環境适應度較低的個體，其繁殖機會相對較少，即所謂自然選擇。而生存下來的個體組成的群體，其品質不斷得以改良，稱為進化。
• 生物的進化是經過無數次有利的進化積累而成的，不同的環境保留了不同的變異後代

二：遺傳算法

2.1：基本介紹

遺傳算法(Genetic Algorithm，GA)最早是由美國的John holland于20世紀70年代提出，該算法是根據大自然中生物體進化規律而設計提出的。是模拟達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模拟自然進化過程搜尋最優解的方法。

遺傳算法通過數學的方式，利用計算機仿真運算，将問題的求解過程轉換成類似生物進化中的染色體基因的交叉、變異等過程。在求解較為複雜的組合優化問題時，相對一些正常的優化算法，通常能夠較快地獲得較好的優化結果。遺傳算法已被人們廣泛地應用于組合優化、機器學習、信号處理、自适應控制和人工生命等領域。

遺傳算法的發展：

• 1967年，美國密歇根大學約翰·霍蘭德(John Holland)教授的學生Bagley在他的博士論文中首次提出了遺傳算法這一術語，此後，Holland指導學生完成了多篇有關遺傳算法研究的論文。1971年，Hollstien在他的博士論文中首次把遺傳算法用于函數優化
• 1975年是遺傳算法研究曆史上十分重要的一年。這一年約翰·霍蘭德(John Holland)出版了他的著名專著《自然系統和人工系統的适應性》，該書系統地闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法極為重要的模式理論，該理論首次确認了結構重組遺傳操作對于獲得隐并行性的重要性
• 同年，迪喬恩(K.A.De Jong)完成了他的重要論文《遺傳自适應系統的行為分析》。他在該論文中所做的研究工作可看作是遺傳算法發展過程中的一個裡程碑。他把Holland的模式理論與他的計算實驗結合起來。盡管迪喬恩主要側重于函數優化的應用研究，但他将選擇、交叉和變異操作進一步完善和系統化，同時又提出了諸如代溝(generation gap)等新的遺傳操作技術。他的研究工作為遺傳算法及其應用打下了堅實的基礎，他所得出的許多結論，迄今仍具有普遍的指導意義
• 20世紀80年代後，遺傳算法進入興盛發展時期，被廣泛應用于自動控制、生産計劃、圖像處理、機器人等研究領域

遺傳算法的基本思想：

• 首先實作從問題到基因映射，即編碼(問題表示)工作，然後從代表問題可能潛在解集得一個種群開始進行進化求解
• 初代種群(編碼集合)産生後，按照優勝劣汰的原則，根據個體适應度大小挑選(選擇)個體，進行複制、交叉、變異，産生出代表新的解集的群體，再對其進行挑選以及一系列遺傳操作，如此往複，逐代演化産生出越來越好的近似解

概念說明：

• 選擇：通過适應度的計算，淘汰不合理的個體。類似于自然界的物競天擇
• 複制：編碼的拷貝，類似于細胞分裂中染色體的複制
• 交叉：編碼的交叉重組，類似于染色體的交叉重組
• 變異：編碼按小機率擾動産生的變化，類似于基因的突變

這個過程将導緻種群像自然進化一樣，後代種群比前代更加适應環境，末代種群中得最優個體經過解碼（從基因到問題的映射），可以作為問題近似最優解。

遺傳算法：

• 遺傳算法直接以目标函數值作為搜尋資訊
• 傳統的優化算法往往不隻需要目标函數值，還需要目标函數的導數等其它資訊。這樣對許多目标函數無法求導或很難求導的函數，遺傳算法就比較友善
• 遺傳算法同時進行解空間的多點搜尋
• 傳統的優化算法往往從解空間的一個初始點開始搜尋，這樣容易陷入局部極值點
• 遺傳算法進行群體搜尋，而且在搜尋的過程中引入遺傳運算，使群體又可以不斷進化。這些是遺傳算法所特有的一種隐含并行性

随機搜尋 + 定向搜尋：

• 遺傳算法使用機率搜尋技術。遺傳算法屬于一種自适應機率搜尋技術，其選擇、交叉、變異等運算都是以一種機率的方式來進行的，進而增加了其搜尋過程的靈活性
• 實踐和理論都已證明了在一定條件下遺傳算法總是以機率1收斂于問題的最優解

用遺傳算法求解問題需要解決以下六個問題：

• 編碼：GA在進行搜尋之前先将解空間的解資料表示成遺傳空間的基因型串結構資料，這些串結構資料的不同組合便構成了不同的點
• 初始群體的生成：随機産生N個初始串結構資料，每個串結構資料稱為一個個體，N個個體構成了一個群體。GA以這N個串結構資料作為初始點開始進化
• 适應度評估：适應度表明個體或解的優劣性。不同的問題，适應性函數的定義方式也不同
• 選擇：選擇的目的是為了從目前群體中選出優良的個體，使它們有機會作為父代為下一代繁殖子孫。遺傳算法通過選擇過程展現這一思想，進行選擇的原則是适應性強的個體為下一代貢獻一個或多個後代的機率大。選擇展現了達爾文的适者生存原則
• 交叉：交叉操作是遺傳算法中最主要的遺傳操作。通過交叉操作可以得到新一代個體，新個體組合了其父輩個體的特性。交叉展現了資訊交換的思想
• 變異：變異首先在群體中随機選擇一個個體，對于選中的個體以一定的機率随機地改變串結構資料中某個串的值。同生物界一樣，GA中變異發生的機率很低，通常取值很小

2.2：概念說明

編碼問題：把解決的問題映射成一個數學問題，也就是所謂的“數學模組化”或問題表示，那麼這個問題的一個可行解即被稱為一條“染色體”。編碼的方法直接影響到了遺傳算法的交叉算子、變異算子等遺傳算子的運算，是以很大程度上決定了遺傳進化的效率。

基因型（Genotype）：在自然界中，通過基因型表征繁殖，繁殖和突變，基因型是組成染色體的一組基因的集合。在遺傳算法中，每個個體都由代表基因集合的染色體構成。例如，一條染色體可以表示為二進制串，其中每個位代表一個基因。

種群（Population）：遺傳算法保持大量的個體（individuals）——針對目前問題的候選解集合。由于每個個體都由染色體表示，是以這些種族的個體（individuals）可以看作是染色體集合：

适應度函數（Fitness function）：在算法的每次疊代中，使用适應度函數（也稱為目标函數）對個體進行評估。目标函數是用于優化的函數或試圖解決的問題。适應度得分更高的個體代表了更好的解，其更有可能被選擇繁殖并且其性狀會在下一代中得到表現。随着遺傳算法的進行，解的品質會提高，适應度會增加，一旦找到具有令人滿意的适應度值的解，終止遺傳算法。

選擇（Selection）：在計算出種群中每個個體的适應度後，使用選擇過程來确定種群中的哪個個體将用于繁殖并産生下一代，具有較高值的個體更有可能被選中，并将其遺傳物質傳遞給下一代。也有機會選擇低适應度值的個體，但機率較低。這樣，就不會完全摒棄其遺傳物質。

交叉（Crossover）：為了建立一對新個體，通常将從目前代中選擇的雙親樣本的部分染色體互換（交叉），以建立代表後代的兩個新染色體。此操作稱為交叉或重組：

交叉政策分為單點交叉運算與兩點交叉運算

單點交叉運算：

兩點交叉運算：

突變（Mutation）：突變操作的目的是定期随機更新種群，将新模式引入染色體，并鼓勵在解空間的未知區域中進行搜尋。突變可能表現為基因的随機變化。變異是通過随機改變一個或多個染色體值來實作的。例如，翻轉二進制串中的一位：

以下是一個遺傳場景：

編解碼過程圖示：

編碼政策評估：

• 完備性(completeness)：問題空間中的所有點(候選解)都能作為GA空間中的點(染色體)表現
• 健全性(soundness): GA空間中的染色體能對應所有問題空間中的候選解。
• 非備援性(non-redundancy)：染色體和候選解一一對應。

2.3：算法流程

遺傳算法概念流程如下：

• 初始化。随機選擇一些個體組成最初的種群(population)
• 評估函數。通過某種方法來評估個體的适應度，即衡量染色體（解）的優劣。
• 選擇selection 。自然選擇，優良的基因、生存能力強的被選擇下來的機率要大。
• 交叉crossover。産生後代，基因交叉，可以了解為有性繁殖，子代會分别從父母那得到部分基因
• 變異mutation。後代的基因可能會變異。變異在生物進化起了很大作用

遺傳算法步驟如下：

• 首先将變量二進制化，産生随機初始種群，并計算種群中每個個體的适應度值
• 按照适應度将種群個體進行排序，再依次執行基因重組與基因變異，得到子代新種群
• 将子代群體插入到父代群體中，篩選出适應度值優良的個體
• 進入到下一次的進化，直到進化到制定代數時停止并輸出最優解

2.4：遺傳算法總結

遺傳算法應用：

• 函數優化：函數優化是遺傳算法的經典應用領域，也是遺傳算法進行性能評價的常用算例，如：連續函數和離散函數、凸函數和凹函數、低維函數和高維函數、單峰函數和多峰函數等。對于一些非線性、多模型、多目标的函數優化問題，用其它優化方法較難求解，而遺傳算法可以友善的得到較好的結果。
• 組合優化：随着問題規模的增大，組合優化問題的搜尋空間也急劇增大，有時在計算上用枚舉法很難求出最優解。對這類複雜的問題，人們已經意識到應把主要精力放在尋求滿意解上，而遺傳算法是尋求這種滿意解的最佳工具之一。實踐證明，遺傳算法對于組合優化中的NP問題非常有效。例如遺傳算法已經在求解旅行商問題、背包問題、裝箱問題、圖形劃分問題等方面得到成功的應用。
• 工廠中的房間排程：工廠中的房間排程問題是一個典型的NP-Hard問題，遺傳算法作為一種經典的智能算法廣泛用于工廠中的房間排程中，很多學者都緻力于用遺傳算法解決工廠中的房間排程問題，現今也取得了十分豐碩的成果。從最初的傳統工廠中的房間排程（JSP）問題到柔性作業工廠中的房間排程問題（FJSP），遺傳算法都有優異的表現，在很多算例中都得到了最優或近優解。
• 遺傳算法也在生産排程問題、自動控制、機器人學、圖象處理、人工生命、遺傳編碼和機器學習等方面獲得了廣泛的運用。

正常優化算法：

• 解析法：隻能得到局部最優解，且要求目标函數連續光滑及可微資訊
• 枚舉法：雖然克服了這些缺點，但計算效率太低，且對于實際問題往往由于搜尋空間大而不能将所有的情況都搜尋到
• 動态規劃法：存在“指數爆炸”問題，它對于中等規模和适度複雜性的問題，也常常無能為力

同正常算法相比，遺傳算法有以下特點：

• 算法從問題解的集合（種群）開始搜尋，而不是從單個解開始。這是遺傳算法與傳統優化算法的極大差別。傳統優化算法是從單個初始值疊代求最優解的；容易誤入局部最優解。
• 遺傳算法同時處理群體中的多個個體，即對搜尋空間中的多個解進行評估，覆寫面大，利于全局擇優，減少了陷入局部最優解的風險，同時算法本身易于實作并行化。
• 遺傳算法是對決策變量的編碼進行操作，這樣提供的參數資訊量大，優化效果好。
• 遺傳算法是從許多點開始并行操作，因而可以有效地防止搜尋過程收斂于局部最優解。
• 遺傳算法通過目标函數來計算适配值，而不需要其他推導和附加資訊，進而對問題的依賴性小。
• 遺傳算法的尋優規則是由機率決定的，而非确定性的。

遺傳算法的優點

• 全局最優：在許多情況下，優化問題具有局部最大值和最小值。這些值代表的解比周圍的解要好，但并不是最佳的解。大多數傳統的搜尋和優化算法，尤其是基于梯度的搜尋和優化算法，很容易陷入局部最大值，而不是找到全局最大值。遺傳算法更有可能找到全局最大值。這是由于使用了一組候選解，而不是一個候選解，而且在許多情況下，交叉和變異操作将導緻候選解與之前的解有所不同。隻要設法維持種群的多樣性并避免過早趨同（premature convergence），就可能産生全局最優解。
• 處理複雜問題：由于遺傳算法僅需要每個個體的适應度函數得分，而與适應度函數的其他方面（例如導數）無關，是以它們可用于解決具有複雜數學表示、難以或無法求導的函數問題。
• 處理缺乏數學表達的問題：遺傳算法可用于完全缺乏數學表示的問題。這是由于适應度是人為設計的。例如，想要找到最有吸引力顔色組合，可以嘗試不同的顔色組合，并要求使用者評估這些組合的吸引力。使用基于意見的得分作為适應度函數應用遺傳算法搜尋最佳得分組合。即使适應度函數缺乏數學表示，并且無法直接從給定的顔色組合計算分數，但仍可以運作遺傳算法。隻要能夠比較兩個個體并确定其中哪個更好，遺傳算法甚至可以處理無法獲得每個個體适應度的情況。例如，利用機器學習算法在模拟比賽中駕駛汽車，然後利用基于遺傳算法的搜尋可以通過讓機器學習算法的不同版本互相競争來确定哪個版本更好，進而優化和調整機器學習算法。
• 耐噪音：一些問題中可能存在噪聲現象。這意味着，即使對于相似的輸入值，每次得到的輸出值也可能有所不同。例如，當從傳感器産生異常資料時，或者在得分基于人的觀點的情況下，就會發生這種情況。盡管這種行為可以幹擾許多傳統的搜尋算法，但是遺傳算法通常對此具有魯棒性，這要歸功于反複交叉和重新評估個體的操作。
• 并行性：遺傳算法非常适合并行化和分布式處理。适應度是針對每個個體獨立計算的，這意味着可以同時評估種群中的所有個體。另外，選擇、交叉和突變的操作可以分别在種群中的個體和個體對上同時進行。
• 持續學習：進化永無止境，随着環境條件的變化，種群逐漸适應它們。遺傳算法可以在不斷變化的環境中連續運作，并且可以在任何時間點擷取和使用目前最佳的解。但是需要環境的變化速度相對于遺傳算法的搜尋速度慢。

遺傳算法的局限性：

• 需要特殊定義：将遺傳算法應用于給定問題時，需要為它們建立合适的表示形式——定義适應度函數和染色體結構，以及适用于該問題的選擇、交叉和變異算子。
• 超參數調整：遺傳算法的行為由一組超參數控制，例如種群大小和突變率等。将遺傳算法應用于特定問題時，沒有标準的超參數設定規則。
• 計算密集：種群規模較大時可能需要大量計算，在達到良好結果之前會非常耗時。可以通過選擇超參數、并行處理以及在某些情況下緩存中間結果來緩解這些問題。
• 過早趨同：如果一個個體的适應能力比種群的其他個體的适應能力高得多，那麼它的重複性可能足以覆寫整個種群。這可能導緻遺傳算法過早地陷入局部最大值，而不是找到全局最大值。為了防止這種情況的發生，需要保證物種的多樣性。
• 無法保證的解的品質：遺傳算法的使用并不能保證找到目前問題的全局最大值（但幾乎所有的搜尋和優化算法都存在此類問題，除非它是針對特定類型問題的解析解）。通常，遺傳算法在适當使用時可以在合理的時間内提供良好的解決方案。