一種改進操作算子的加速收斂遺傳算法

2020-11-22 電子產品世界

摘 要：針對基本遺傳算法效率低和易早熟的缺陷，提出了一種改進操作算子的遺傳算法。該算法在種群初始化、選擇、交叉、變異等基本算子的基礎上加以改進，使算法具有更好的適應性。對3組不同函數的測試表明，改進算法較傳統的遺傳算法具有在種群很小的情況下收斂速度快穩定性高的優點，同時能有效地避免早熟現象。
關鍵詞：遺傳算法；變異；收斂速度；種群數

本文引用地址：http://www.eepw.com.cn/article/192077.htm


0 引 言
遺傳算法(Genetic Algorithm，GA)是一種宏觀意義下的仿生算法，它模仿的機制是一切生命與智能的產生與進化過程，從一個初始種群出發，不斷重複執行選擇，雜交和變異的過程，使種群進化越來越接近某一目標。它通過模擬達爾文「優勝劣汰，適者生存」的原理激勵好的結構；通過模擬孟德爾遺傳變異理論在迭代過程中保持已有的結構，同時尋找更好的結構。經典遺傳算法的求解步驟為：初始化種群；選擇；交叉；變異；判斷終止條件。由於它簡單有效，具有很強的魯棒性和通用性，所以被廣泛應用於模式識別、神經網絡、圖像處理、機器學習、工業優化控制、自適應控制、生物科學、社會科學等多種領域。
早熟和收斂時間過長是影響遺傳算法效率的兩個主要因素，而選擇壓力過大是導致早熟收斂的一個重要原因，為此不少學者對遺傳算法做了改進，但仍存在一定局限性。在此對遺傳算法個操作算子加以改進，通過對經典多極值測試函數的仿真研究表明，改進後的算法能夠有效避免早熟且在種群規模較小的情況下具有較快的收斂速度。


l 改進操作算子的遺傳算法
經典遺傳算法的把變異作為一種輔助手段，認為變異只是一個背景機制，這一觀點與生物學中的實際觀察是相符的，但作為設計人工求解問題方法的思想，他正受到理論與實踐兩方面的挑戰。另外，從微觀角度來講，變異隨時都有可能發生，如果突變向不好的方向進行．其「修復系統」立刻就能對其進行修復。基於以上兩點，這裡在選擇與交叉算子中滲入不同的變異行為，且動態改進變異算子，使算法能快速達到全局最優。
1．1 初始化
為了改善初始群體的效能，提高模式的優良度，採取如下方法：先隨機產生一個父染色體，對其進行一定次數(20次左右)的逐位精英選擇高頻變異，方法如下：例如染色體為01001，先把第一位變異為1，成為11001。若適應度提高，則此位以很大的概率p(如O．98)轉換為1，否則以很小的概率(如0．01)轉換為1，以此類推。接著產生具有一定規模的染色體種群，隨機使其中每個染色體的某段基因與之前父染色體相應基因段保持一致。如：假設父染色體為00110，隨機產生個體10101，若以第一和第二位基因與父染色體一致，則該個體變為：00101。該方法把較優秀的模式分散到各個染色體中，使它一開始就具有一定概率的優秀短模式，從而有效提高算法的尋優效率。
1．2 選擇操作
經典遺傳算法根據適者生存原則選擇下一代個體。在選擇時，以適應度為選擇原則。適應度準則體現了適者生存，不適應者淘汰的自然法則。
然而基於適應度的概率選擇機制如輪盤賭選擇法在種群中出現個別或極少數適應度相當高的個體時，就可能導致這些個體在群體中迅速繁殖，經過少數迭代後佔滿了種群的位置。這樣，遺傳算法的求解過程就結束了，也即收斂了。但這樣很有可能使收斂到局部最優解，即出現早熟現象。為了從根本上避免早熟現象且加快收斂速度，採用基於高頻精英變異的錦標賽選擇法。其操作如下：假設競賽規模為2，首先選取種群中第1和第2個個體X和Y
如：X=100101，Y=011110
從第1位開始比較適應值的大小，即當個體X與Y的第1位分別是1和O時，假設fitness(X)>fitness(Y)，於是把Y的第1位由0高頻變異為1，此時：
X=110101，Y=101110
此時，若fithess(X)fithess(Y)，則把Y的第1位由1高頻變異為O。如此下去，最終得到的為選擇出的個體，其中較高位(如第1至L／3位，其中L為染色體長度)變異率為0．8，其他位變異率為0．95，理由是較高位的個體即使適應度低也有可能在附近變異成適應度更高的個體。
然後選取種群中第2和第3個個體應用上法選擇出第2個個體，這個過程重複進行，完成剩餘個體的選擇。這種算子在選擇個體上就可以有方向性且極大地加快算法的收斂速度。
1．3 交叉操作
交叉是把兩個父個體的部分結構加以替換重組而生成新個體的操作，從而在下一代產生新的個體。它的目的是開發問題解空間中新的區域，尋找父個體已有的但未能合理組合的基因，儘量保證具有優良模式的個體不被交叉操作所完全破壞，同時增大種群的離散程度，產生新的搜索空間。所有交叉操作的一個共同特徵是，不破壞兩個父個體之間的公共串模式，允許繼續搜索空間時保留好的模式。
對於選中用於繁殖下一代的個體，隨機地選擇2個個體的相同位置，按交叉概率P在選中的位置實行交換。在選中的位置實行交換。這個過程反映了隨機信息交換，目的在於產生新的基因組合，也即產生新的個體。在交叉時，可實行單點交叉或多點交叉。

相關焦點

  • 配電網絡重構的改進混合遺傳算法
    本文提出一種基於改進的混合遺傳算法的配電網重構算法，在算法中使用可操作開關支路的整數編號的排列順序來表示染色體一個大型的配網包含眾多的節點和支路，因此圖中支撐樹的組合數目極大，若窮舉所有的樹，算法將非常的低效。　　遺傳算法具有全局收斂性、無可微性要求、具有很好的魯棒性等優點，特別適合於求解組合優化問題。另外，與一般的隨機搜索方法進行的盲目無向搜索不同，遺傳算法進行的是高效有向的全局搜索，能夠逐步地逼近並收斂於全局最優解。因此，遺傳算法在配網重構中得到越來越廣泛的應用。
  • 改進遺傳算法的支持向量機特徵選擇解決方案介紹
    遺傳算法作為一種魯棒性極強的智能識別方法，直接對尋優對象進行操作，不存在特定數學條件的限定，具有極好的全局尋優能力和並行性;而由於遺傳算法採用概率化的尋優方法，所以在自動搜索的過程中可以自主獲取與尋優有關的線索，並在加以學習之後可以自適應地調整搜索方向，不需要確定搜索的規則。
  • 改進遺傳算法的支持向量機特徵選擇解決方案
    遺傳算法作為一種魯棒性極強的智能識別方法，直接對尋優對象進行操作，不存在特定數學條件的限定，具有極好的全局尋優能力和並行性;而由於遺傳算法採用概率化的尋優方法，所以在自動搜索的過程中可以自主獲取與尋優有關的線索，並在加以學習之後可以自適應地調整搜索方向，不需要確定搜索的規則。因此遺傳算法被廣泛應用在知識發現、組合優化、機器學習、信號處理、自適應控制和人工生命等領域。
  • 遺傳算法原理以及在量化投資的應用
    什麼是遺傳算法 1.介紹遺傳算法的概念 遺傳算法是一種進化策略的算法，模擬生物基因遺傳。遵循物競天擇，適者生存，劣者淘汰的自然規律進化。，太小將容易導致種群多樣性差，容易收斂。 遺傳算法優化 1.容易局部收斂的問題 遺傳算法的局部搜索很強，所以一般容易收斂用以下解決方案，具體情況具體對待。 擴大搜索空間 提高種群的數量、增加數據種類和數量、增加算子。
  • 引入Powerball 與動量技術,新SGD優化算法收斂速度與泛化效果雙...
    在這篇論文中，我們提出了一種新的基於SGD的優化方法（pbSGD）用於訓練神經網絡。與目前的主流思路（自適應學習率或者動量法）不同，該論文作者在之前的工作[1]中，通過利用ODE的有限時間穩定性的直觀表達，提出了一種新的加速算法收斂的方法。
  • 基於單純形的改進精英人工蜂群算法
    金葉2，孫越泓*1，2，王加翠2,王丹21.江蘇省大規模複雜系統數值模擬重點實驗室2.南京師範大學  數學科學學院摘 要本文針對人工蜂群算法收斂速度慢文章中，在僱傭蜂階段藉助精英個體引導蜜源搜索，並利用蜂群中蜜源的質量排序重新構造蜜源的選擇概率公式；在跟隨蜂階段，選擇種群最優蜜源引領蜂群，加強算法對全局最好解的局部開採能力，同時將隨機選擇鄰居蜜源變為最優定向選擇。最後利用單純形算法對精英解集進行再次更新，進一步平衡蜂群的全局搜索和局部尋優能力。數值實驗表明改進的新算法的尋優精度和收斂速度均有明顯提高。
  • 基於改進的LM算法的可見光定位研究
    文獻[7]提出了一種基於自適應混合蛙跳算法的可見光定位方法，雖然啟發式算法具有優越的全局搜索能力，但是獲得全局收斂解卻需要大量計算時間，因此並不適用於嵌入式設備。文獻[8]提出了一種基於融合神經網絡與指紋的可見光定位算法，雖然算法在仿真條件下能得到極高的精度，但是由於BPNN神經的輸入數量是固定的，在複雜的定位條件下算法可能無法靈活的運用冗餘光源信息而導致魯棒性不強。
  • 矩形平面陣列天線旁瓣電平優化的遺傳算法
    本文運用遺傳算法對不等幅不等距矩型平面陣列的最大相對旁瓣電平進行了優化，通過提出新的自適應變異算子改進了算法的收斂性能，良好的計算結果表明遺傳算法是目前求解此類問題的有效方法.
  • 利用遺傳算法優化GANs
    對於我的普通電腦來說，把gan訓練到收斂是非常困難的。遺傳算法是根據大自然中生物體進化規律而設計提出的，是根據大自然中生物體進化規律而設計提出的。是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。在本片文章中，我們嘗試使用遺傳算法來對訓練GANs進行優化，我們的訓練模型是生成手寫數字。
  • 基於遺傳算法的工廠AGV路徑優化研究
    2 遺傳算法的流程　　本文採用遺傳算法進行路徑的優化。傳統的算法解決路徑規劃問題時，初始群體都是固定值，算法只產生適用一種情況的最優路徑，本文在算法的前端加入了物料類型選擇的循環套。通過變異操作，可增加種群的多樣性，有效地防止了遺傳算法過早的收斂，出現「早熟」現象。　　3.5 控制參數的設定以及循環終止條件　　遺傳算法中關鍵的參數為：交叉概率、變異概率和迭代次數C。交叉概率控制著交叉算子的應用頻率，變異操作是保持群體多樣性的最有效手段，迭代次數決定了遺傳操作的執行次數。
  • 應用改進的算法,優化波浪能轉換裝置陣列,提升系統發電效率
    差分進化算法全局搜索能力強並且計算時間少；同時，差分進化算法在精度和收斂速度上沒法兩全且可能會陷入局部解，為了使優化結果更準確，引入了自適應變異算子的概念對差分進化算法進行改進，改進後的算法收斂速度相對較快而且結果準確度高。結合改進算法，分別針對不同浮子數目的陣列進行優化與對比分析。
  • 人工智慧之遺傳算法(GA),搜索最優解的方法
    遺傳算法（GA）是一類借鑑生物界的進化規律演化而來的隨機化搜索方法。 今天我們重點探討一下遺傳算法（GA）。＾＿＾ 人們一提到遺傳算法（GA），就會聯想到達爾文的生物進化論。遺傳算法（GA）是一類借鑑生物界的進化規律演化而來的隨機化搜索方法。它是由美國的J．Holland教授1975年首先提出。目前，遺傳算法（GA）已成為進化計算研究的一個重要分支。
  • 遺傳算法全接觸(一)
    這是我看過的最好的一份遺傳算法教程，如果你能耐心看完他，相信你一定能基本掌握遺傳算法。 遺傳算法的有趣應用很多，諸如尋路問題，8數碼問題，囚犯困境，動作控制，找圓心問題（這是一個國外網友的建議：在一個不規則的多邊形 中，尋找一個包含在該多邊形內的最大圓圈的圓心。）
  • 一種新的變步長波束形成算法
    這兩種算法有很多優點，其代價就是增加了計算複雜度。文獻在的基礎上提出了DR-LMS算法，本文首先介紹了LS-DRMTCM算法，然後詳細介紹了DR―LMS算法，最後根據文獻中算法改進的思想提出一種新的變步長算法，最後對新算法進行了Matlab仿真。　　l 信號模型　　一個具有K個用戶的DS-CDMA系統，接收端為具有M個陣元的均勻直線陣。
  • 【優化】遺傳算法介紹
    [2]葛繼科,邱玉輝,吳春明,蒲國林.遺傳算法研究綜述[J].計算機應用研究,2008(10):2911-2916.[3]雷德明.多維實數編碼遺傳算法[J].控制與決策,2000(02):239-241.[4]臧文科. DNA遺傳算法的集成研究與應用[D].山東師範大學,2018.
  • 遺傳算法:組合優化算法,按照進化論的方式啟發搜索尋優解
    遺傳算法是由美國密西根大學的 Holland教授創立於20世紀六七十年代，受達爾文「進化論」思想的啟發而設計實現。遺傳算法不是通過暴力搜索解的方法，而是通過模擬種群的基因交叉和突變，經過種群一代一代的適者生存的方式尋找問題優解的方法，這在解決組合優化時解空間組合爆炸中應用廣泛。
  • 遺傳算法:讓發明自動「進化」
    這項技術的核心是一種基於遺傳學的運算法則，簡稱遺傳算法。它模仿了自然選擇的原理，任何一個設計方案都可以看做是一個由無數片段構成的遺傳基因。 在這項發明中，每一個片段都是一個構成參數，可以隨著形狀不同而發生變化。
  • 遺傳算法Python實戰 004.八皇后問題
    遺傳算法Python實戰 004.八皇后問題寫在前面的話本節我們主要講解如何使用遺傳算法解決八皇后問題
  • 什麼是遺傳算法?怎樣繪製遺傳算法流程圖
    遺傳算法是一種通過模擬自然進化過程搜索最優解的操作方法，遺傳算法有三個基本算子選擇、交叉和變異。對於遺傳算法我們也可以使用流程圖對其整個過程進行總結歸納，那要怎樣繪製遺傳算法流程圖呢？下面是分享的簡單操作方法，希望可以幫助大家。
  • 遺傳算法的發展
    • 1965年，德國的L.Rechenberg等人正式提出進化策略的方法，當時的進化策略只 有一個個體，而且進化操作也只有變異一種。 • 1965年，美國的L.j.Fogel正式提出進化規劃，在計算中採用多個個體組成的群 體，而且只運用變異操作。