人工智慧之遺傳算法(GA),搜索最優解的方法

2020-11-22 電子發燒友

人工智慧之遺傳算法(GA),搜索最優解的方法

工程師8 發表於 2018-05-11 10:35:00

導讀:人們一提到遺傳算法(GA),就會聯想到達爾文的生物進化論。遺傳算法(GA)是一類借鑑生物界的進化規律演化而來的隨機化搜索方法。

今天我們重點探討一下遺傳算法(GA)。^_^

人們一提到遺傳算法(GA),就會聯想到達爾文的生物進化論。遺傳算法(GA)是一類借鑑生物界的進化規律演化而來的隨機化搜索方法。它是由美國的J.Holland教授1975年首先提出。目前,遺傳算法(GA)已成為進化計算研究的一個重要分支。

概念和定義:

遺傳算法(GeneticAlgorithm)是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型,是一種通過模擬自然進化過程搜索最優解的方法。

遺傳算法(GA)是從代表問題可能潛在的解集的一個種群(population)開始,而一個種群則由經過基因(gene)編碼的一定數目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特徵的實體。染色體作為遺傳物質的主要載體,即多個基因的集合,其內部表現(即基因型)是某種基因組合,它決定了個體的形狀的外部表現。因此,在一開始需要實現從表現型到基因型的映射即編碼工作。

由於仿照基因編碼的工作很複雜,往往進行簡化,初代種群產生之後,按照適者生存和優勝劣汰的原理,逐代(generation)演化產生出越來越好的近似解,在每一代,根據問題域中個體的適應度(fitness)大小選擇(selection)個體,並藉助於自然遺傳學的遺傳算子(geneticoperators)進行組合交叉(crossover)和變異(mutation),產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境,末代種群中的最優個體經過解碼(decoding),可以作為問題近似最優解。

遺傳操作是模擬生物基因遺傳的做法。在遺傳算法中,通過編碼組成初始群體後,遺傳操作的任務就是對群體的個體按照它們對環境適應度(適應度評估)施加一定的操作,從而實現優勝劣汰的進化過程。從優化搜索的角度而言,遺傳操作可使問題的解,一代又一代地優化,並逼近最優解。

框架與術語:

1)編碼—把問題空間的參數轉換成遺傳空間的由基因按一定結構組成的染色體或個體的操作過程。目前的幾種常用的編碼技術有二進位編碼,浮點數編碼,字符編碼,變成編碼等,最常用的是二進位編碼。評估編碼策略有3個規範:a)完備性(completeness);b)健全性(soundness);c)非冗餘性(nonredundancy)。

2)適應度函數—表示某一個體對環境的適應能力,也表示該個體繁殖後代的能力。遺傳算法的適應度函數也叫評價函數,是用來判斷群體中的個體的優劣程度的指標,它是根據所求問題的目標函數來進行評估的。遺傳算法在搜索進化過程中一般不需要其他外部信息,僅用評估函數來評估個體或解的優劣,並作為以後遺傳操作的依據。適應度函數設計直接影響到遺傳算法的性能,因此適應度函數的設計需要滿足以下條件:a)單值、連續、非負、最大化;b) 合理、一致性;c)計算量小;d)通用性強。

3)初始群體選取—初始群體中的個體是隨機產生的。初始群體的設定可採取如下策略:a)根據問題固有知識,設法把握最優解所佔空間在整個問題空間中的分布範圍,然後,在此分布範圍內設定初始群體。b)先隨機生成一定數目的個體,然後從中挑出最好的個體加到初始群體中。這種過程不斷迭代,直到初始群體中個體數達到了預先確定的規模。

4)染色體—又叫做基因型個體(individuals),一定數量的個體組成了群體(population),群體中個體的數量叫做群體大小。

5)基因—串中的元素,基因用於表示個體的特徵。

6)基因位置—簡稱基因位,在算法中表示一個基因在串中的位置稱為基因位置(Gene Position)。

7)特徵值—在用串表示整數時,基因的特徵值與二進位數的權一致。

8)選擇—從群體中選擇優勝的個體,淘汰劣質個體的操作。選擇算子有時又稱為再生算子(reproduction operator)。選擇的目的是把優化的個體(或解)直接遺傳到下一代或通過配對交叉產生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。目前常用的選擇算子有:適應度比例方法、隨機遍歷抽樣法、局部選擇法、錦標賽選擇和輪盤賭選擇法(最簡單、最常用)等。

9)交叉—把兩個父代個體的部分結構加以替換重組而生成新個體的操作。遺傳算法中起核心作用的是遺傳操作的交叉算子。交叉算子根據交叉率將種群中的兩個個體隨機地交換某些基因,能夠產生新的基因組合,期望將有益基因組合在一起。通過交叉,遺傳算法的搜索能力得以飛躍提高。最常用的交叉算子為單點交叉(one-point crossover)。

10)變異—變異算子是對群體中的個體串的某些基因座上的基因值作變動。利用變異算子的局部隨機搜索能力可以加速向最優解收斂;利用變異算子可維持群體多樣性,防止出現未成熟收斂現象。依據個體編碼表示方法的不同,可以有:a)實值變異;b)二進位變異。變異率的選取一般受種群大小、染色體長度等因素的影響,通常選取很小的值。

11)終止條件—當最優個體的適應度達到給定的閾值,或者最優個體的適應度和群體適應度不再上升時,或者迭代次數達到預設的代數時,算法終止。

遺傳操作進行的是高效有向的搜索。遺傳操作包括3個基本遺傳算子(genetic operator):選擇(selection);交叉(crossover);變異(mutation)。遺傳操作的效果和3個遺傳算子所取的操作概率、編碼方法、群體大小、初始群體以及適應度函數的設定密切相關。3個基本遺傳算子的作用:a)選擇的作用:優勝劣汰,適者生存;b)交叉的作用:保證種群的穩定性,朝著最優解的方向進化;c)變異的作用:保證種群的多樣性,避免交叉可能產生的局部收斂。

打開APP閱讀更多精彩內容

聲明:本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人,不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用,如有內容圖片侵權或者其他問題,請聯繫本站作侵刪。 侵權投訴

相關焦點

  • 遺傳算法:組合優化算法,按照進化論的方式啟發搜索尋優解
    遺傳算法是由美國密西根大學的 Holland教授創立於20世紀六七十年代,受達爾文「進化論」思想的啟發而設計實現。遺傳算法不是通過暴力搜索解的方法,而是通過模擬種群的基因交叉和突變,經過種群一代一代的適者生存的方式尋找問題優解的方法,這在解決組合優化時解空間組合爆炸中應用廣泛。
  • 什麼是遺傳算法?怎樣繪製遺傳算法流程圖
    遺傳算法是一種通過模擬自然進化過程搜索最優解的操作方法,遺傳算法有三個基本算子選擇、交叉和變異。對於遺傳算法我們也可以使用流程圖對其整個過程進行總結歸納,那要怎樣繪製遺傳算法流程圖呢?下面是分享的簡單操作方法,希望可以幫助大家。
  • 變壓器之遺傳算法(Genetic Algorithm)的具體實現過程
    遺傳算法(Genetic Algorithm)是一類借鑑生物界的進化規律(適者生存,優勝劣汰遺傳機制)演化而來的隨機化搜索方法。
  • 遺傳算法010.解線性方程
    而我們要介紹的遺傳算法解方程,也屬於迭代法中的一種。在本節中,我們將看到,遺傳算法如何來解線性方程組。這樣我們就可以慢慢改變當前最佳基因周圍的搜索範圍。這使得算法能夠比較容易的找到下一個最優的改進可能。
  • 詳解遺傳算法
    遺傳算法是受達爾文的進化論的啟發,借鑑生物進化過程而提出的一種啟發式搜索算法。因此在介紹遺傳算法前有必要簡單的介紹生物進化知識。 遺傳算法思想   借鑑生物進化論,遺傳算法將要解決的問題模擬成一個生物進化的過程,通過複製、交叉、突變等操作產生下一代的解,並逐步淘汰掉適應度函數值低的解,增加適應度函數值高的解。這樣進化N代後就很有可能會進化出適應度函數值很高的個體。
  • 遺傳算法全接觸(一)
    因為遺傳算法中每一條染色體,對應著遺傳算法的一個 解決方案,一般我們用適應性函數(fitness function)來衡量這個解決方案的優劣。所以從一個基因組到其解的適應度形成一個映射。所以也可以把遺傳算法的過程看作是一個在多元函數裡面求最優解的過程。在這個多維曲面裡面也有數不清的「山峰」,而這些最優解所對應的就是局部最優解。
  • 利用遺傳算法優化GANs
    遺傳算法是根據大自然中生物體進化規律而設計提出的,是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型,是一種通過模擬自然進化過程搜索最優解的方法。在本片文章中,我們嘗試使用遺傳算法來對訓練GANs進行優化,我們的訓練模型是生成手寫數字。什麼是遺傳算法?
  • 改進遺傳算法的支持向量機特徵選擇解決方案
    遺傳算法作為一種魯棒性極強的智能識別方法,直接對尋優對象進行操作,不存在特定數學條件的限定,具有極好的全局尋優能力和並行性;而由於遺傳算法採用概率化的尋優方法,所以在自動搜索的過程中可以自主獲取與尋優有關的線索,並在加以學習之後可以自適應地調整搜索方向,不需要確定搜索的規則。因此遺傳算法被廣泛應用在知識發現、組合優化、機器學習、信號處理、自適應控制和人工生命等領域。
  • 自我代碼提升之啟發式算法(番外篇)
    本期給大家帶來一些啟發式算法的介紹和代碼實現。嚴格來說,啟發式算法並不屬於機器學習領域的方法,其解決的問題也並不是分類和回歸預測,因此本篇屬於該系列番外篇。啟發式算法簡介在數學建模的經典問題當中,有一種問題是最優化問題,即在給定條件下,給出能夠是的目標實現最優的答案的方法。
  • 改進遺傳算法的支持向量機特徵選擇解決方案介紹
    遺傳算法作為一種魯棒性極強的智能識別方法,直接對尋優對象進行操作,不存在特定數學條件的限定,具有極好的全局尋優能力和並行性;而由於遺傳算法採用概率化的尋優方法,所以在自動搜索的過程中可以自主獲取與尋優有關的線索,並在加以學習之後可以自適應地調整搜索方向,不需要確定搜索的規則。
  • 蒙特卡洛樹搜索在黑盒優化和神經網絡結構搜索中的應用
    原創 Synced 機器之心機器之心專欄作者:王林楠、田淵棟布朗大學在讀博士王林楠在本文中介紹了他與 Facebook 田淵棟團隊合作,在 2020 年 NeurIPS 取得亮眼表現的新算法,以及其在神經網絡結構搜索中的應用
  • 一種改進操作算子的加速收斂遺傳算法
    l 改進操作算子的遺傳算法 經典遺傳算法的把變異作為一種輔助手段,認為變異只是一個背景機制,這一觀點與生物學中的實際觀察是相符的,但作為設計人工求解問題方法的思想,他正受到理論與實踐兩方面的挑戰。另外,從微觀角度來講,變異隨時都有可能發生,如果突變向不好的方向進行.其「修復系統」立刻就能對其進行修復。
  • [算法系列]最優化問題綜述
    3 求解算法3.1 無約束優化算法3.1.1 梯度下降法梯度下降法是最早最簡單,也是最為常用的最優化方法。梯度下降法實現簡單,當目標函數是凸函數時,梯度下降法的解是全局解。一般情況下,其解不保證是全局最優解,梯度下降法的速度也未必是最快的。
  • 啟發式算法分類 - CSDN
    1.2算法描述   所以,我們需要一個pbest來記錄個體搜索到的最優解,用gbest來記錄整個群體在一次迭代中搜索到的最優解。模擬退火其實也是一種貪心算法,但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解,因此有可能會跳出這個局部的最優解,達到全局的最優解。
  • ​公務員考試之行測試題、MATLAB與遺傳算法
    仔細閱讀題目,發現題目與自己以前使用「遺傳算法」求解的「哥隆尺」問題比較相似。遺傳算法比較適合計算那種離散的、可解空間非常大的問題。因為學生的分數個個不相同。參考上次的遺傳算法求解「哥隆尺」問題,使用pdist函數撰寫約束條件用ga命令可以寫出如下代碼:
  • 人工智慧之ICA算法
    人工智慧機器學習有關算法內容,請參見公眾號「科技優化生活」之前相關文章。人工智慧之機器學習主要有三大類:1)分類;2)回歸;3)聚類。今天我們重點探討一下ICA算法。  ICA獨立成分分析是一種用來從多變量(多維)統計數據裡找到隱含的因素或成分的方法,被認為是PCA主成分分析(請參見人工智慧(46))和FA因子分析的一種擴展。對於盲源分離問題,ICA是指在只知道混合信號,而不知道源信號、噪聲以及混合機制的情況下,分離或近似地分離出源信號的一種分析過程。
  • 基於遺傳算法的工廠AGV路徑優化研究
    遺傳算法是模仿自然界生物進化機制發展起來的隨機全局搜索優化方法,具有算法效率高、魯棒性強、可實現並行搜索等特點 [3] ,被廣泛用於解決路徑規劃等領域的問題。  2 遺傳算法的流程  本文採用遺傳算法進行路徑的優化。
  • 遺傳算法原理以及在量化投資的應用
    原標題:遺傳算法原理以及在量化投資的應用 點擊標題下「藍色微信名」可快速關注 本篇內容涉及遺傳算法的概念,原理描述,實現方法以及在量化投資的應用。 遺傳算法優化 1.容易局部收斂的問題 遺傳算法的局部搜索很強,所以一般容易收斂用以下解決方案,具體情況具體對待。 擴大搜索空間 提高種群的數量、增加數據種類和數量、增加算子。
  • 人工智慧之蒙特卡羅方法(MCM)
    是指使用隨機數(或偽隨機數)來解決很多計算問題的方法。與它對應的是確定性算法。蒙特卡羅方法在金融工程學,宏觀經濟學,計算物理學(如粒子輸運計算、量子熱力學計算、空氣動力學計算)以及人工智慧之機器學習等領域應用廣泛。
  • 淺析基於優化算法的能量管理控制策略(二)
    算法博弈論(Game Theory,GT)凸規劃(Convex Programming,CP)模擬退火是一種受金屬退火過程啟發的方法,該方法通過隨機搜索,顯示目標函數優化的可能最優解的同時保留了符合標準定義的次優解,這樣可以防止算法陷入局部極小值,並增強其向全局最優的演化。