基于非線性規劃和遺傳算法的函數尋優

王榮亮

基于非線性規劃和遺傳算法的函數尋優

王榮亮

（宿遷職業技術學院，江蘇 宿遷 223800）

針對遺傳算法求解復雜非線性函數尋優出現早熟，陷入最優解這一問題，將非線性規劃和遺傳算法相結合，通過對典型復雜函數的仿真，并與遺傳算法比較，表明基于遺傳算法和非線性規劃的函數尋優算法具有明顯的優勢，收斂速度快，尋找到的極值非常接近最優解。

非線性規劃；遺傳算法；函數尋優；函數模型

1 引言

非線性規劃大多數采用梯度下降法，局部搜索能力較強，但是全局搜索能力較弱。遺傳算法具備很好的全局搜索能力，但是容易出現早熟現象，陷入局部最優解。例如上述的Ackley函數，函數具有很多極小值，很容易陷入局部最優解，如圖1所示。

圖1 函數圖像

為了解決在上述一類函數優化時，遺傳算法早熟，進入局部最優解這一問題，本文采用遺傳算法進行全局搜索，非線性規劃進行局部搜索，以得到函數全局最優解。

2 理論基礎

2.1 非線性規劃函數

非線性規劃是一種求解目標函數（）或約束條件中有一個或幾個非線性函數的最優化問題的方法。MATLAB工具箱提供非線性規劃函數，可以直接調用。函數fmincon是MATLAB最優化工具箱中求解非線性規劃問題的函數，它是從一個預估值出發，搜索約束條件下非線性多元函數的最小值。函數fmincon的約束條件為：

式（1）中：，，，，為矢量；，為矩陣；（），（）為返回矢量的函數；（），（），（）為非線性函數。

2.2 遺傳算法及其基本步驟

2.2.1 遺傳算法

遺傳算法是一種進化算法，基本原理是仿效生物界中的“物競天擇，適者生存”的演化規則。遺傳算法將問題參數編碼為染色體，再利用迭代方式進行選擇、交叉和變異等運算來變換種群中染色體的信息，最終生成符合優化目標的染色體。在遺傳算法中，染色體對應的是數據或數組，通常由一維的串結構數據來表示，串上各個位置對應基因的取值。基因組成的串就是染色體，也稱為基因型個體，一定數量的個體構成了群體。群體中個體數目稱為種群大小，也稱為群體規模。各個個體對環境的適應程度稱為適應度。

2.2.2 基本步驟

遺傳算法主要涉及的基本步驟如下。

2.2.2.1 編碼

遺傳算法在進行搜索之前，需要將解空間的數據表示成遺傳空間的基因型串結構數據，這些串結構數據的不同組合便構成了不同的點。常用的編碼方式主要有位串編碼、Grey編碼、實數（浮點法）編碼、多級參數編碼等。其中，實數編碼不需要進行數值轉換，可以直接在解的表現形式上進行遺傳算法操作，因此本文采用該方法編碼，每一個染色體為一個實數向量。

2.2.2.2 初始種群生成

隨機產生個初始串結構數據，每個串結構數據稱為一個個體，個個體構成了一個群體。遺傳算法以這個串結構數據作為初始點開始進化。

2.2.2.3 適應度函數

2.2.2.4 選擇

2.2.2.5 交叉

2.2.2.6 變異

變異主要是為了維持種群多樣性。變異首先在群體中隨機選擇一個個體，對于選中的個體以一定的概率隨機地改變串結構數據中的某個串的值。同生物界一樣，遺傳算法中變異概率很低，通常取很小的值，本文選取變異概率為0.01。

3 算法設計

本文結合非線性規劃和遺傳算法的各自有點，一方面采用遺傳算法進行全局搜索，一方面采用非線性規劃進行局部搜索，以得到問題的全局最優解，算法流程如圖2所示。其中，種群初始化模塊根據求解問題初始化種群，適應度值計算模塊根據適應度函數計算個體適應度值，選擇、交叉以及變異為遺傳算法的搜索算子，為固定值，當進化次數為的倍數時，則采用非線性規劃尋優加快進化，非線性規劃利用當前染色體值采用函數fmincon尋找問題的局部最優解。

圖2 算法流程圖

4 實驗分析

如圖1所示，Ackley函數是一個非常復雜的非線性函數，存在很多局部極小值點，但是全局的極小值點只有一個0，位置為（0，0）。

分別采用基本遺傳算法和本文的基于遺傳算法、非線性規劃的函數尋優算法進行求解Ackley函數的極小值。設定種群規模100，進化30代，交叉概率為0.6，變異概率為0.01。算法的優化過程中各代平均函數值和最優個體函數值變化如圖3所示。在種群進化到20代時，函數值收斂到0.158 8，位置為（0.041 2，﹣0.032 1）。

圖3 基本遺傳算法優化過程

用基于遺傳算法和非線性規劃的函數尋優算法求解，算法參數設置為：種群規模20，進化30代，交叉概率為0.6，變異概率為0.01。算法的優化過程中各代平均函數值和最優個體函數值變化如圖4所示。在種群進化到10代時，函數值收斂到﹣0.005 4，位置為（0，0）。比較圖3和圖4可見，基本遺傳算法出現早熟現象，陷入局部最優解，而基于遺傳算法和非線性規劃的函數尋優算法以較小的種群規模，進化到更好的解。基于遺傳算法和非線性規劃的函數尋優算法跳出了局部最優，在收斂結果和求解結果上都明顯優于基本遺傳算法。

5 結論

函數極值尋優現象是日常生活中比較常見的一類問題。本文結合非線性規劃和遺傳算法的各自優點，一方面采用遺傳算法進行全局搜索，一方面采用非線性規劃進行局部搜索，得到全局最優解，避免了遺傳算法早熟，陷入局部最優解。實驗分析結果充分表明，在處理復雜非線性函數極值尋優問題上，基于遺傳算法和非線性規劃的函數尋優算法具有明顯的優勢，需要種群規模小，收斂速度快，尋找到的極值非常接近最優解，為解決現實生活中的一些極值尋優問題提供了一種可借鑒的思路。

圖4 非線性規劃遺傳算法優化過程

［1］李巖，袁弘宇，于佳喬，等.遺傳算法在優化問題中的應用綜述［J］.山東工業技術，2019（12）：180，242-243.

［2］吳龍，任紅民，畢惟紅.遺傳算法求解非線性方程組研究綜述［J］.電子科技，2014，27（4）：173-178.

［3］張國民.遺傳算法的綜述［J］.科技視界，2013（9）： 37，36.

［4］申合帥，李澤民.混合線性約束非線性最優化問題的一個新算法［J］.湖南師范大學自然科學學報，2018，41（5）：75-81.

［5］薛美芬，陳奕榕，陳省江.基于蒙特卡羅法與梯度法解非線性優化問題的研究［J］.寧德師范學院學報（自然科學版），2017，29（2）：127-130.

［6］楊娜，荊園園.基于改進PSO算法的函數極值尋優研究［J］.計算機仿真，2015，32（9）：263-266.

TP18

A

10.15913/j.cnki.kjycx.2019.15.016

2095－6835（2019）15－0047－02

〔編輯：王霞〕