遺傳算法在優化問題中的應用綜述

李巖 袁弘宇 于佳喬 張更偉 劉克平

摘 要：根據遺傳算法的特點和優化過程中存在的問題，指出遺傳算法存在缺陷。針對遺傳算法在優化問題中的研究現狀，從編碼技術的改進、自適應算子的引入、操作算子的改進、混沌理論的加入、多種群方式的改進、免疫學原理的引入和小生鏡技術的結合等方面做出了總結，最后研究并探討遺傳算法仍需要克服的困難與待解決的問題。

關鍵詞：遺傳算法；優化；研究現狀；遺傳算法的組成；遺傳算法結構

DOI：10.16640/j.cnki.37-1222/t.2019.12.210

1 引言

遺傳算法（GA）是一種基于生物界規律和自然遺傳機制的并行搜索算法。1975年，J. Holland教授首次在書中提出“自然組合人工智能系統的適應性”。它是一種多參數，多組合同時優化方法，模擬自然進化過程中“自然選擇，適者生存”的原則。其主要特征是群體間的搜索方法以及群體中個體信息的交換。GA非常適合解決傳統搜索方法難以解決的非線性問題。遺傳算法也經常用于生產線優化問題。文獻[3]在生產線運行優化問題中運用GA，并通過與模擬退火算法得到的結果進行對比，得到遺傳算法具有更好的效果。文獻[4]使用免疫遺傳算法研究線平衡問題。文獻[5]主要采用遺傳算法研究第一類生產線的平衡問題，解決了第一類生產線的負荷平衡問題。文獻[6]對作業元素分配給工作站的順序進行編碼，并根據最大分配原則對其進行解碼。實踐證明，遺傳算法可以有效地解決U形生產線的平衡問題。文獻[7]的主要特點是受“鰻魚效應”啟發設計了周期性自適應雜交算子和變異算子。實驗結果表明，改進算法可以有效地改善局部收斂和早熟現象。文獻[8]提出了一種改進的遺傳算法，并結合實例給出了第二類生產平衡問題的解決方案。縮放適應度方法，即保持最佳適應度的值與平均適應度的值的比率是恒定的通用采樣策略，以及線性可變交叉和變異算子。文獻[9]通過利用遺傳算法對生產線排列來達到平衡生產線的目的。文獻[10]提出一種針對“序列組合”編碼方式的遺傳算法，這種編碼方式，設計了相應的遺傳操作算子，提高搜索的效率和解的質量。

2 應用背景

與其他啟發式算法相比，遺傳算法具有以下特征：

（1）遺傳算法從多個初始點而不是單個初始點開始搜索，因此可以有效地跳出局部極值；

（2）利用目標函數的評價信息而不是傳統導數的目標函數，形式對目標函數沒有要求，因而有良好的適應性和可規模化；

（3）具有良好的尋找全局最優解的能力，能夠在非連續，多峰和嘈雜的環境中以較大的概率收斂到全局最優或滿意的解；

（4）將每個過程劃分作為決策變量，優化生產過程，解決最優作業調度問題；

（5）具有天生的并行性，即在對群體進行運算的同時，對多個結果進行信息搜索；它具有一定的概率，這增加了其搜索最優解決過程的靈活性。

生產線平衡問題也是一個典型的尋優過程，為此，人們在尋找新算法的同時，GA憑借著自身的優勢而不失為一種好的算法。

3 遺傳算法

3.1 遺傳算法的基本原理

與舊的搜索算法不同，GA從種群的初始解決方案開始其搜索過程。群體中的每個個體被稱為染色體。在迭代過程中染色體的不斷更新稱為遺傳。GA主要通過交叉、變異、選擇算子來實現。染色體的優點和缺點通常通過適應性來評估。根據適合度值的大小，從父母和后代中選擇一定比例的個體作為后代的群體，然后繼續迭代計算直到它收斂到全局最佳染色體。適應度是遺傳算法用來評價種群在進化的過程中所能達到的最優值的一個概念。為了證明染色體的適應性，引入了測量每條染色體的功能函數，稱為適應度函數。

3.2 遺傳算法的組成

遺傳算法的流程如圖1所示。其主要組成部分包括：

（1）編碼方式。遺傳算法通常根據問題本身進行編碼，并將問題的有效解決方案轉化為遺傳算法的搜索空間。工業中常用的編碼方法包括實數編碼，二進制編碼，整數編碼和數據結構編碼。

（2）適應度函數。適應度函數，也稱為目標函數，是對整個個體與其適應度之間的對應關系的描述。具有高適應性的個體中包含的高質量基因具有較高的傳遞給后代的概率，而具有低適應性的個體的遺傳概率較低。

（3）遺傳操作。基本的遺傳操作包括：選擇、交叉、變異。

a）選擇。選擇操作基于個體適應度評估，選擇群體中具有較高適應度的個體，并且消除具有較低適應度的個體。當然不同的選擇操作也會帶來不同的結果，有效的選擇操作可以顯著的提高搜索的效率和速度，減少無用的計算量。

常見的選擇方法有：基于比例的適應度分配方法，期望值選擇方法，基于排名的適應度分配方法，輪盤賭選擇方法等。

b）交叉。在自然界生物進化過程中，兩條染色體通過基因重組形成新的染色體，因此交叉操作是遺傳算法的核心環節。交叉算子的設計需要根據具體的問題具體分析，編碼操作和交叉操作互相輔助，交叉產生的新的個體必須滿足染色體的編碼規律。父代染色體的優良性狀最大程度上的遺傳給下一代染色體，在此期間也能能夠產生一些較好的性狀。

常見的交叉算子包括實質重組，中間重組，離散重組，線性重組，二進制交叉，單點交叉，均勻交叉，多點交叉和減少代理交叉。

c）變異。通過隨機選擇的方法改變染色體上的遺傳基因。變異本身可以被視為隨機算法，嚴格來說，是用于生成新個體的輔助算法。

幾個與浮點數編碼和二進制編碼個體匹配的交叉運算：單點交叉，均勻交叉，算術交叉，兩點交叉和多點交叉。

（4）算法終止條件。算法終止一般指適應度函數值的變化趨于穩定或者滿足迭代終止的公式要求，也可以是迭代到指定代數后停止進化。

4 遺傳算法的研究現狀

（1）編碼技術的改進。石飛等人[11]針對分區編碼方法的不足，設計了一種改進的編碼方式。該算法的編碼方法基于組件的處理順序和組件的組裝關系。而且還設計了一種基于鄰接矩陣的方法來修復不可行染色體，通過與分區編碼的對比，最后證明了該算法的優越性。

杜軒等人[12]分析實際生產線組件分布問題的基礎上，設計出矩陣編碼的改進方式，并運用了兩點交叉和改進的局部變異和自適應突變率方法用于變異操作。最后，通過工程實例解決了該問題，取得了良好的效果，提高了PCB裝配線的效率，證明了算法的有效性。

林培光等人[13]將Grefenstette編碼和2-opt優化算法結合到遺傳算法中，并使用一定數量的城市坐標來解決路徑搜索問題。提出的搜索空間路徑方案實現了遺傳算法能夠快速收斂到最優解，保持強大的搜索能力，實現全局優化，防止陷入局部優化。

（2）操作算子的改進。朱佳棟等人[14]針對傳統的遺傳算法不能很好地解決現殘存的問題，對其進行了優化。本文對變異個體和操作算子的設計進行了改進，并應用于多功能液壓千斤頂的配置設計。改進的交互式算法可以在進化階段將個體劃分為不同的遺傳單元，并為多用戶協同配置設計具有相似偏好的用戶。它可以更好地減少用戶疲勞，并快速、輕松地獲得用戶需求。

李敬花等人[15]提出基于改進遺傳算法的舾裝件托盤揀選的智能化方法。通過建立以總延遲時間為優化目標的數學模型，設計了一種改進的遺傳算法求解模型。使用基于托盤的單層整數編碼方法，建議用每條染色體來表示不同的托盤排序。當種群陷入局部最優解，種群的多樣性可以通過進化逆轉操作和插入操作來實現，使種群能跳出局部最優解，并繼續尋找全局最優解。

（3）自適應算子的引入。吳聰等人[16]提出了一種在進化的過程中，交叉概率自適應調整的交叉方法，變異概率自適應于調整的變異方法。進化代數和進化整個過程中沒有改變個體的數量，從而提高了算法的局部搜索能力。引入自適應算子能有效抑制遺傳算法的“早熟”，優化精度更高，使得到的優化結果更靠近全局最優。

劉帥等人[17]將自適應遺傳算法應用到民航空中交通監視雷達部署方面的優化。該算法首先根據首要指標建立雷達部署的數學模型，如管制區域的覆蓋范圍和進近控制區域的雙重覆蓋。為了避免遺傳算法的隨機發散和局部收斂，采用可變交叉概率和變異概率。最后，實驗結果表明，所需要的空域范圍可以被自適應遺傳算法快速收斂得到，并獲得全局最優部署方案，提高雷達利用率并且增大空域覆蓋率。

劉書明等人[18]針對解決水管網絡的優化設計問題，選用了一種自適應遺傳算法的應對方案。根據管段的流速和直徑，可以自適應地調整遺傳算法中下一代個體的直徑選擇，以提高演化效率。優化結果表明，與傳統遺傳算法相比，自適應遺傳算法具有更高的收斂速度和優化效率。

（4）免疫學原理的引入。黃碩果等人[19]提出了一種解決模糊柔性作業車間調度的免疫遺傳算法。算法中染色體采用實數編碼，并采用自適應提取疫苗操作來進行濃度抑制，提出了新型的采用模擬退火的疫苗接種操作。這種算法可以有效地降低早熟及過早收斂的情況，并添加記憶庫來彌補傳統交叉變異的不靈活性。

趙韓等人[20]通過該算法自適應調整遺傳過程中的遺傳參數來提高算法的穩定性和效率。作者將改進的免疫遺傳算法應用于作業車間調度問題，并驗證了其有效性。

楊峰等人[21]將免疫學原理引入遺傳算法，并提出一種新的編碼方式來編碼巡回路線，來實現抗體濃度群體的更新和多樣性策略的保持，在物流路徑規劃的問題上實現了顯著的改善。

（5）混沌理論的引進。張浩為等人[22]提出了將混沌理論與遺傳算法相結合的優化算法。初始種群通過混沌理論進行優化，使用精英預留和混合排序選擇策略，設計自適應交叉算子、自適應變異算子來提高改進算法的搜索性能。最后，驗證了該算法的優化效果更好。

王華等人[23]把混沌理論的優點和遺傳算法的優勢相結合。運用該算法對已知模型進行仿真。相比之下，新算法比傳統遺傳算法具有更少的延遲，并且可以提高搜索結果的效率。

（6）多種群方式的改進算法。李鋒等人[24]提出了一種有效解決裝配線平衡問題的多種群遺傳算法。采用多種群遺傳算法對固定工位下裝配線的優化目標進行求解，在子種群進化的階段該算法保證了種群的多樣性，優秀種群之間通過優秀個體的相互交流也保證了解的收斂速度，防止種群出現退化現象。提升了種群的多樣性和遺傳算法的全局搜索能力。

王軍等人[25]提出了一種改進的雙種群遺傳算法。作者將頂點圖像法、適應度函數、適應度函數增量法引入遺傳算法，同時基于多種群的進化過程，將初始種群分為倆個種群，一個種群是全局種群，其主要目的是找到可能存在最優值的區域。另一個種群是局部種群，主要任務是仔細搜索全局種群劃分的區域，找到最優解。

（7）小生境遺傳算法。雷磊等人[26]找到了一種以實數編碼為基礎的小生境遺傳算法。并將其用于雷達干擾資源的調度。小生境遺傳算法將小生境技術引入遺傳算法的原始結構，不影響遺傳算法的原始特征。此外，保持了種群的多樣性，并且改善了遺傳算法處理多峰優化問題的能力。

李振等人[27]提出了一種采用適應函數共享的小生境技術結合遺傳算法計算種群個體適應度。該算法在遺傳算法的基礎上借鑒了小生境技術，引入適應度共享函數作為評價標準，提高了整體的搜索效率避免陷入局部最優解，可以看出，小生境遺傳算法優于傳統的遺傳算法。

5 遺傳算法在尋優過程中存在的問題

通過不斷的實驗總結發現，遺傳算法在迭代尋優的過程中容易出現以下需要解決的問題：

（1）遺傳算法是以一個不斷迭代來尋找最優值的過程，但該算法對新空間的搜索能力是有限的，處理規模也很小，特別是在優化的后期階段，搜索效率很低，很容易收斂到局部最優解；

（2）選擇算子，交叉算子和變異算子的實現也需要很多參數，如交叉率和變異率。而且，這些參數的選擇嚴重影響了解的質量；

（3）遺傳算法對初始種群有很強的依賴性，直接影響解的收斂性和優化結果的質量；

（4）根據一般情況，遺傳算法迭代次數越多，算法的收斂性越好。然而，在增加遺傳迭代次數的同時，算法的計算工作量增加，這消耗了大量的計算時間。

6 總結

遺傳算法是近幾年比較熱的話題，相對于優化問題遺傳算法憑借自身優勢廣泛應用于數據挖掘、自動控制，生產調度，自動控制，圖像處理，組合優化等領域。但根據現在的研究和發展來看，遺傳算法在優化的問題上還存在很多的不足，主要問題是遺傳算法的編碼不能完全表達優化問題的約束。還有很多方面需要改善，如適應度函數是影響種群的一個重要因素，對于子代種群以及初始種群間的關系以及如何合理的選擇適應度函數都是需要進一步探討的問題。

近年來，由于人工智能的快速發展，遺傳算法有了更廣闊的發展平臺。與其他的智能優化算法相比，遺傳算法雖然經歷的發展較長，但仍然存在著以下幾方面的問題需要進一步的研究：

（1）遺傳算法在編碼規則性和編碼表示方面存在不準確性；

（2）單個遺傳算法編碼不能完全表達優化問題的約束。考慮約束的優化方法是找到不可行解決方案的閾值，以便更好地控制計算時間；

（3）遺傳算法的一般效率低于其他傳統優化方法，容易過早收斂；

（4）遺傳算法對算法的準確性，可行性和計算復雜度沒有有效的定量分析方法；

（5）將算法與神經網絡，小生境技術和混沌理論等優化方法相結合，開發出一種新的混合優化算法，揭示了一種新的智能平臺。

參考文獻：

[1]HOLLAND J H. Adaptation in natural and artificial system. An Arbor， MI，USA ：The University of Michigan Press，1975.

[2]劉環宇，夏吉慶等.基于遺傳算法對A公司生產線平衡的分析[J]. 物流技術，2014（17）：367-370.

（下轉第180頁）

（上接第243頁）

[3]梁承姬，陳維斗，崔佳誠.自動化集裝箱碼頭雙軌道吊協調調度分析[J].計算機應用與軟件，2018，35（09）：17-21.

[4]安鑫.免疫遺傳算法在中藥制藥車間調度的研究[D].昆明理工大學，2011.

[5]范維博，周俊，許正良.應用遺傳算法解決第一類裝配平衡問題[J].計算機技術與發展，2010（02）：P194-196.

[6]宋華明，韓玉啟.基于遺傳算法的U型生產線平衡[J].系統工程學報，2002（10）：424-429.

[7]陳曉峰，肖田園.應用遺傳算法解決裝配線平衡問題[J]. 計算機工程與應用，2001（23）：81-83.

[8]張瑞軍，陳定方，楊琴.用改進的遺傳算法解決ALB問題[J]. 計算機工程與設計，2006，27（20）：3731-3736.

[9]王紅軍，趙建輝.基于遺傳的裝配線平衡系統研究[J].計算機工程與應用，2008，44（10）：195-197.

[10]吳爾飛.雙邊裝配線平衡技術研究[D].上海：上海交通大學博士學位論文，2009.

[11]石飛，趙詩奎.基于工序約束鏈編碼的遺傳算法求解產品綜合調度問題[J].中國機械工程，2017，28（20）：2483-2492.

[12]杜軒，李登橋，朱康.基于矩陣編碼遺傳算法的PCB生產線元件分配優化[J].三峽大學學報（自然科學版），2015，37（01）：89-93.

[13]公冶小燕，林培光，任威隆.基于Grefenstette 編碼和2-opt 優化的遺傳算法 [J/OL].山東大學學報（工學版）.

[14]朱佳棟，蘇少輝，陳昌，劉桂英.面向產品配置設計的改進交互式遺傳算法[J].中國機械工程，2018，29（20）：2474-2478.

[15]李敬花，曹旺，趙定剛，蔣巖，周青驊.基于改進遺傳算法的托盤揀選延誤時間優化[J].計算機集成制造系統.

[16]吳聰，陳侃松，姚靜.基于改進自適應遺傳算法的物流配送路徑優化研究[J].計算機測量與控制，2018（02）.

[17]劉帥，秦姍姍.基于自適應遺傳算法的空管雷達部署優化[J]. 通信技術，2018（04）.

[18]劉書明，李婷婷，王曉婷，吳雪.自適應遺傳算法在給水管網優化中的應用[J]. 給水排水，2017（04）：107-110.

[19]黃碩果.基于免疫遺傳算法的模糊柔性作業車間調度問題研究[D].重慶交通大學，2017.

[20]趙韓，高先圣，姜康.基于免疫遺傳算法的多目標柔性作業車間調度研究[J].系統仿真學報，2008（22）：6163-6168.

[21]楊峰，柳林，唐賢瑛等.基于免疫遺傳算法的物流配送車輛路徑優化問題研究[J]. 計算機應用與軟件，2007，24（05）：50-51.

[22]張浩為，謝軍偉，張昭建.基于混合自適應遺傳算法的相控陣雷達任務調度[J].兵工學報，2017，38（09）：1761-1770.

[23]王華，蔡延光.基于混沌遺傳算法的干線交叉口信號控制優化研究[J].電子世界，2014（18）：362-363.

[24]李鋒，邢靜忠，劉偉.基于多種群遺傳算法的裝配線平衡問題研究[J].四川理工學院學報（自然科學版），2015，28（02）：30-36.

[25]王軍.基于改進雙種群遺傳算法的AUV路徑規劃方法研究[J]. 自動化技術與應用，2010，29（06）：13-16.

[26]雷磊，周青松，張劍云.基于小生境遺傳算法的干擾資源調度研究[J].現代防御技術，2014，42（01）.

[27]李振，胡慶東，張國英.基于小生境遺傳算法的人工揀貨路徑優化研究[J].物流科技，2011（06）：85-88.

基金項目：吉林省科技發展計劃項目（20180201105G X）

通訊作者：李巖（1978-），男，吉林人，博士在讀，副教授，主要研究方向：智能機械與機器人控制。