【優化求解】基於matlab差分進化演算法求解函式極值問題【含Matlab原始碼 1199期】

一、簡介

1 前言

在遺傳、選擇和變異的作用下，自然界生物體優勝劣汰，不斷由低階向高階進化和發展。人們注意到，適者生存的進化規律可以模式化，從而構成一些優化演算法；近年來發展的進化計算類演算法受到了廣泛的關注。 差分進化演算法(Differential Evolution， DE) 是一種新興的進化計算技術[1] 。它是由S torn等人於1995年提出的， 其最初的設想是用於解決切比雪夫多項式問題，後來發現它也是解決複雜優化問題的有 效技術。 差分進化演算法是基於群體智慧理論的優化演算法，是通過群體內個體間的合作與競爭而產生的智慧優化搜尋演算法。但相比於進化計算，它保留了基於種群的全域性搜尋策略，採用實數編碼、基於差分的簡單 變異操作和“一對一”的競爭生存策略，降低了進化計算操作的複雜性。同時，差分進化演算法特有的記憶能力使其可以動態跟蹤當前的搜尋情況，以調整其搜尋策略，它具有較強的全域性收斂能力和穩健性， 且不需要藉助問題的特徵資訊，適用於求解一些利用常規的數學規劃方法很難求解甚至無法求解的複雜優化問題[2-5]。因此，差分進化演算法作為一種高效的並行搜尋演算法，對其進行理論和應用研究具有重要的學術意義和工程價值。 目前，差分進化演算法已經在許多領域得到了應用，如人工神經元網路、電力、機械設計、機器人、訊號處理、生物資訊、經濟學、現代農業和運籌學等。然而，儘管差分進化演算法獲得了廣泛研究，但相 對於其他進化演算法而言，其研究成果相當分散，缺乏系統性，尤其在理論方面還沒有重大突破。

2 差分進化演算法理論 2.1差分進化演算法原理 差分進化演算法是一種隨機的啟發式搜尋演算法，簡單易用，有較強的魯棒性和全域性尋優能力。它從數學角度看是一種隨機搜尋演算法，從工程角度看是一種自適應的迭代尋優過程。除了具有較好的收斂性外，差分進化演算法非常易於理解與執行，它只包含不多的幾個控制引數，並且在整個迭代過程中，這些引數的值可以保持不變。差分進化演算法是一種自組織最小化方法，使用者只需很少的輸入。它的關鍵思想與傳統進化方法不同：傳統方法是用預先確定的概率分佈函式決定向量擾動；而差分進化演算法的自組織程式利用種群中兩個隨機選擇的不同向量來干擾一個現有向量，種群中的每一個向量都要進行干擾。差分進化演算法利用一個向量種群，其中種群向量的隨機擾動可獨立進行，因此是並行的。如果新向量對應函式值的代價比它們的前輩代價小，它們將取代前輩向量。 同其他進化演算法一樣，差分進化演算法也是對候選解的種群進行操作，但其種群繁殖方案與其他進化演算法不同：它通過把種群中兩個成員之間的加權差向量加到第三個成員上來產生新的引數向量，該操作 稱為“變異”； 然後將變異向量的引數與另外預先確定的目標向量引數按一定規則混合來產生試驗量，該操作稱為“交叉”；最後，若試驗向量的代價函式比目標向量的代價函式低，試驗向量就在下一代中代替目標向量，該操作稱為“選擇”。種群中所有成員必須當作目標向量進行一次這樣的操作，以便在下一代中出現相同個數競爭者。 在進化過程中對每一代的最佳引數向量都進行評價，以記錄最小化過程。這樣利用隨機偏差擾動產生新個體的方式，可以獲得一個收斂性非常好的結果，引導搜尋過程向全域性最優解逼近[6-7]。

2.2差分進化演算法的特點 差分進化演算法從提出到現在，在短短二十幾年內人們對其進行了廣泛的研究並取得了成功的應用。該演算法主要有如下特點： (1)結構簡單，容易使用。差分進化演算法主要通過差分變異運算元來進行遺傳操作，由於該運算元只涉及向量的加減運算，因此很容易實現；該演算法採用概率轉移規則，不需要確定性的規則。此外，差分進化演算法的控制引數少，這些引數對演算法效能的影響已經得到一定的研究，並得出了一些指導性的建議，因而可以方便使用人員根據問題選擇較優的引數設定。 (2)效能優越。差分進化演算法具有較好的可靠性、高效性和魯棒性，對於大空間、非線性和不可求導的連續問題，其求解效率比其他進化方法好，而且很多學者還在對差分進化演算法繼續改良，以不斷提高其效能。 (3)自適應性。差分進化演算法的差分變異運算元可以是固定常數，也可以具有變非同步長和搜尋方向自適應的能力，根據不同目標函式進行自動調整，從而提高搜尋質量。 (4)差分進化演算法具有內在的並行性，可協同搜尋，具有利用個體區域性資訊和群體全域性資訊指導演算法進一步搜尋的能力。在同樣精度要求下，差分進化演算法具有更快的收斂速度。 (5)演算法通用，可直接對結構物件進行操作，不依賴於問題資訊，不存在對目標函式的限定。差分進化演算法操作十分簡單，易於程式設計實現，尤其利於求解高維的函式優化問題。

3 差分進化演算法種類 3.1基本差分進化演算法 基本差分進化演算法的操作程式如下[8]： (1)初始化； (2)變異； (3)交叉； (4)選擇； (5)邊界條件處理。 初始化 差分進化演算法利用NP個維數為D的實數值引數向量，將它們作為每 一代的種群，每個個體表示為： 另外一個方法是進行邊界吸收處理，即將超過邊界約束的個體值設定為臨近的邊界值。

3.2差分進化演算法的其他形式 上面闡述的是最基本的差分進化演算法操作程式，實際應用中還發展了差分進化演算法的幾個變形形式，用符號DE/x/y/z加以區分，其中：x限定當前被變異的向量是“隨機的”或“最佳的”；y是所利用的差向量的個數；z指示交叉程式的操作方法。前面敘述的交叉操作表示為“bin”。利用這個表示方法， 基本差分進化演算法策略可描述為DE/rand/1/bin。 還有其他形式[5，如： 3.3改進的差分進化演算法 自適應差分進化演算法 作為一種高效的並行優化演算法，差分進化演算法發展很快，出現了很多改進的差分進化演算法。下面介紹一種具有自適應運算元的差分進化演算法[9].

4差分進化演算法流程 差分進化演算法採用實數編碼、基於差分的簡單變異操作和“一對一”的競爭生存策略，其具體步驟如下： (1)確定差分進化演算法的控制引數和所要採用的具體策略。差分進化演算法的控制引數包括：種群數量、變異運算元、交叉運算元、最大進化代數、終止條件等。 (2)隨機產生初始種群，進化代數k=1。 (3)對初始種群進行評價，即計算初始種群中每個個體的目標函式值。 (4)判斷是否達到終止條件或達到最大進化代數：若是，則進化終止，將此時的最佳個體作為解輸出；否則，繼續下一步操作。 (5)進行變異操作和交叉操作，對邊界條件進行處理，得到臨時種群。 (6)對臨時種群進行評價，計算臨時種群中每個個體的目標函式值。 (7)對臨時種群中的個體和原種群中對應的個體，進行“一對-”的選擇操作，得到新種群。 (8)進化代數k=k+1，轉步驟(4)。 差分進化演算法運算流程如圖3.1所示。

5關鍵引數的說明 控制引數對一個全域性優化演算法的影響是很大的，差分進化演算法的控制變數選擇也有一些經驗規則。

種群數量NP 一般情況下，種群的規模AP越大，其中的個體就越多，種群的多樣性也就越好，尋優的能力也就越強，但也因此增加了計算的難度。所以，NP不能無限取大。根據經驗，種群數量NP的合理選擇在5D~ 10D之間，必須滿足NP≥4，以確保差分進化演算法具有足夠的不同的變異向量。

變異運算元F 變異運算元FE[0，2]是一個實常數因數，它決定偏差向量的放大比例。變異運算元熨小，則可能造成演算法“早熟”。隨著/值的增大，防止演算法陷入區域性最優的能力增強，但當F>1時，想要演算法快速收斂到最優值會變得十分不易；這是由於當差分向量的擾動大於兩個個體之間的距離時，種群的收斂性會變得很差。目前的研究表明，F小於0.4和大於1的值僅偶爾有效，/=0.5通常是一個較好的初始選擇。若種 群過早收斂，那麼F或NP應該增大。

交叉運算元CR 交叉運算元CR是一個範圍在[0，1]內的實數，它控制著一個試驗向量引數來自於隨機選擇的變異向量而不是原來向量的概率。交叉運算元CK越大，發生交叉的可能性就越大。CR的一個較好的選擇是0.1，但 較大的CK通常會加速收斂，為了看看是否可能獲得一個快速解，可以先嚐試CR=0.9或CF=1.0.

最大進化代數G 最大進化代數6是表示差分進化演算法執行結束條件的一個引數，表示差分進化演算法執行到指定的進化代數之後就停止執行，並將當前群體中的最佳個體作為所求問題的最優解輸出。一般，6取100~500。

終止條件 除最大進化代數可作為差分進化演算法的終止條件外，還可以增加其他判定準則。一般當目標函式值小於閾值時程式終止，閾值常選為10-6。上述引數中，F、CR與NP一樣，在搜尋過程中是常數，一般F和CR影響搜尋過程的收斂速度和穩健性，它們的優化值不僅依賴於目標函式的特性，還與NP有關。通常可通過對不同值做一些試驗之後，利用試驗和結果誤差找到F、CR和NP的合適值。

二、案例及完整原始碼

1 案例

2 完整程式碼 ```c %%%%%%%%%%%%%%%%%差分進化演算法求函式極值%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%% clear all; %清除所有變數 close all; %清圖 clc; %清屏 NP=50; %個體數目 D=10; %變數的維數 G=200; %最大進化代數 F0=0.4; %初始變異運算元 CR=0.1; %交叉運算元 Xs=20; %上限 Xx=-20; %下限 yz=10^-6; %閾值 %%%%%%%%%%%%%%%%%%%%%%%%%賦初值%%%%%%%%%%%%%%%%%%%%%%%% x=zeros(D,NP); %初始種群 v=zeros(D,NP); %變異種群 u=zeros(D,NP); %選擇種群 x=rand(D,NP)(Xs-Xx)+Xx; %賦初值 %%%%%%%%%%%%%%%%%%%%計算目標函式%%%%%%%%%%%%%%%%%%%% for m=1:NP Ob(m)=func1(x(:,m)); end trace(1)=min(Ob); %%%%%%%%%%%%%%%%%%%%%%%差分進化迴圈%%%%%%%%%%%%%%%%%%%%% for gen=1:G %%%%%%%%%%%%%%%%%%%%%%變異操作%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%自適應變異運算元%%%%%%%%%%%%%%%%%%% lamda=exp(1-G/(G+1-gen)); F=F02^(lamda); %%%%%%%%%%%%%%%%%r1,r2,r3和m互不相同%%%%%%%%%%%%%%%% for m=1:NP r1=randi([1,NP],1,1); while (r1==m) r1=randi([1,NP],1,1); end r2=randi([1,NP],1,1); while (r2==m)|(r2==r1) r2=randi([1,NP],1,1); end r3=randi([1,NP],1,1); while (r3==m)|(r3==r1)|(r3==r2) r3=randi([1,NP],1,1); end v(:,m)=x(:,r1)+F(x(:,r2)-x(:,r3)); end %%%%%%%%%%%%%%%%%%%%%%交叉操作%%%%%%%%%%%%%%%%%%%%%%% r=randi([1,D],1,1); for n=1:D cr=rand(1); if (cr<=CR)|(n==r) u(n,:)=v(n,:); else u(n,:)=x(n,:); end end %%%%%%%%%%%%%%%%%%%邊界條件的處理%%%%%%%%%%%%%%%%%%%%% for n=1:D for m=1:NP if (u(n,m)Xs) u(n,m)=rand(Xs-Xx)+Xx; end end end %%%%%%%%%%%%%%%%%%%%%%選擇操作%%%%%%%%%%%%%%%%%%%%%%% for m=1:NP Ob1(m)=func1(u(:,m)); end for m=1:NP if Ob1(m)<Ob(m) x(:,m)=u(:,m); end end
for m=1:NP Ob(m)=func1(x(:,m)); end trace(gen+1)=min(Ob); if min(Ob(m))<yz break end end [SortOb,Index]=sort(Ob); x=x(:,Index); X=x(:,1); %最優變數
Y=min(Ob); %最優值
%%%%%%%%%%%%%%%%%%%%%%%%%畫圖%%%%%%%%%%%%%%%%%%%%%%%%%% figure plot(trace); xlabel('迭代次數') ylabel('目標函式值') title('適應度進化曲線')

```

c %%%%%%%%%%%%%%%%%%%%%%%適應度函式%%%%%%%%%%%%%%%%%%%%%%%% function result=func1(x) summ=sum(x.^2); result=summ;

三、解題過程及執行結果

1 解題過程

2 執行結果

四、matlab版本及參考文獻

1 matlab版本 2014a

2 參考文獻 《智慧優化演算法及其MATLAB例項（第2版）》包子陽 餘繼周 楊杉著 電子工業出版社