王榮亮

基于非線性規(guī)劃和遺傳算法的函數(shù)尋優(yōu)

王榮亮

（宿遷職業(yè)技術(shù)學(xué)院，江蘇 宿遷 223800）

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

非線性規(guī)劃；遺傳算法；函數(shù)尋優(yōu)；函數(shù)模型

1 引言

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

圖1 函數(shù)圖像

為了解決在上述一類函數(shù)優(yōu)化時，遺傳算法早熟，進(jìn)入局部最優(yōu)解這一問題，本文采用遺傳算法進(jìn)行全局搜索，非線性規(guī)劃進(jìn)行局部搜索，以得到函數(shù)全局最優(yōu)解。

2 理論基礎(chǔ)

2.1 非線性規(guī)劃函數(shù)

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

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

2.2 遺傳算法及其基本步驟

2.2.1 遺傳算法

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

2.2.2 基本步驟

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

2.2.2.1 編碼

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

2.2.2.2 初始種群生成

隨機(jī)產(chǎn)生個初始串結(jié)構(gòu)數(shù)據(jù)，每個串結(jié)構(gòu)數(shù)據(jù)稱為一個個體，個個體構(gòu)成了一個群體。遺傳算法以這個串結(jié)構(gòu)數(shù)據(jù)作為初始點(diǎn)開始進(jìn)化。

2.2.2.3 適應(yīng)度函數(shù)

2.2.2.4 選擇

2.2.2.5 交叉

2.2.2.6 變異

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

3 算法設(shè)計(jì)

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

圖2 算法流程圖

4 實(shí)驗(yàn)分析

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

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

圖3 基本遺傳算法優(yōu)化過程

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

5 結(jié)論

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

圖4 非線性規(guī)劃遺傳算法優(yōu)化過程

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

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

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

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

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

［6］楊娜，荊園園.基于改進(jìn)PSO算法的函數(shù)極值尋優(yōu)研究［J］.計(jì)算機(jī)仿真，2015，32（9）：263-266.

TP18

A

10.15913/j.cnki.kjycx.2019.15.016

2095－6835（2019）15－0047－02

〔編輯：王霞〕