遺傳演算法 -- matlab簡單實現

6 人贊了文章

參考源代碼 : https://github.com/Mschenl/matlab.git

1、演算法介紹

遺傳演算法（Genetic Algorithm）是模擬達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模型，是一種通過模擬自然進化過程搜索最優解的方法。遺傳演算法是從代表問題可能潛在的解集的一個種群（population）開始的，而一個種群則由經過基因（gene）編碼的一定數目的個體(individual)組成。每個個體實際上是染色體(chromosome)帶有特徵的實體。染色體作為遺傳物質的主要載體，即多個基因的集合，其內部表現（即基因型）是某種基因組合，它決定了個體的形狀的外部表現，如黑頭髮的特徵是由染色體中控制這一特徵的某種基因組合決定的。因此，在一開始需要實現從表現型到基因型的映射即編碼工作。由於仿照基因編碼的工作很複雜，我們往往進行簡化，如二進位編碼，初代種群產生之後，按照適者生存和優勝劣汰的原理，逐代（generation）演化產生出越來越好的近似解，在每一代，根據問題域中個體的適應度（fitness）大小選擇（selection）個體，並藉助於自然遺傳學的遺傳運算元（genetic operators）進行組合交叉（crossover）和變異（mutation），產生出代表新的解集的種群。這個過程將導致種群像自然進化一樣的後生代種群比前代更加適應於環境，末代種群中的最優個體經過解碼（decoding），可以作為問題近似最優解

2、運算過程

遺傳演算法的基本運算過程如下：

a)初始化：設置進化代數計數器t=0，設置最大進化代數T，隨機生成M個個體作為初始群體P(0)。

b)個體評價：計算群體P(t)中各個個體的適應度。

c)選擇運算:將選擇運算元作用於群體。選擇的目的是把優化的個體直接遺傳到下一代或通過配對交叉產生新 的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應度評估基礎上的。

d)交叉運算：將交叉運算元作用於群體。遺傳演算法中起核心作用的就是交叉運算元。

e)變異運算：將變異運算元作用於群體。即是對群體中的個體串的某些基因座上的基因值作變動。

群體P(t)經過選擇、交叉、變異運算之後得到下一代群體P(t+1)。

f)終止條件判斷:若t=T,則以進化過程中所得到的具有最大適應度個體作為最優解輸出，終止計算。

3、matlab實現

核心函數：

(1) function[pop]=initializega(num,bounds,eevalFN,eevalOps,options)--初始種群的生成函數

【輸出參數】

pop--生成的初始種群

【輸入參數】

num--種群中的個體數目

bounds--代表變數的上下界的矩陣

eevalFN--適應度函數

eevalOps--傳遞給適應度函數的參數

options--選擇編碼形式(浮點編碼或是二進位編碼)[precisionF_or_B],如

precision--變數進行二進位編碼時指定的精度

F_or_B--為1時選擇浮點編碼，否則為二進位編碼,由precision指定精度)

(2) function[x,endPop,bPop,traceInfo]=ga(bounds,evalFN,evalOps,startPop,opts,...

termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)

--遺傳演算法函數

【輸出參數】

x--求得的最優解

endPop--最終得到的種群

bPop--最優種群的一個搜索軌跡

【輸入參數】

bounds--代表變數上下界的矩陣

evalFN--適應度函數

evalOps--傳遞給適應度函數的參數

startPop-初始種群

opts[epsilonprob_opsdisplay]--opts(1:2)等同於initializega的options參數，第三個參數控制是否輸出，一般為0。如[1e-610]

termFN--終止函數的名稱,如[maxGenTerm]

termOps--傳遞個終止函數的參數,如[100]

selectFN--選擇函數的名稱,如[normGeomSelect]

selectOps--傳遞個選擇函數的參數,如[0.08]

xOverFNs--交叉函數名稱表，以空格分開，如[arithXoverheuristicXoversimpleXover]

xOverOps--傳遞給交叉函數的參數表，如[20;23;20]

mutFNs--變異函數表，如[boundaryMutation，multiNonUnifMutation，nonUnifMutation，unifMutation]

mutOps--傳遞給交叉函數的參數表,如[400;61003;41003;400]

matlab 主函數 實現

%% I. 清空環境變數clear allclc%% II. 繪製函數曲線x = 0:0.01:9;y = x + 10*sin(5*x)+7*cos(4*x);figureplot(x, y)xlabel(自變數)ylabel(因變數)title(y = x + 10*sin(5*x) + 7*cos(4*x))%% III. 初始化種群initPop = initializega(50,[0 9],fitness);%% IV. 遺傳演算法優化[x endPop bpop trace] = ga([0 9],fitness,[],initPop,[1e-6 1 1],maxGenTerm,25,... normGeomSelect,0.08,arithXover,2,nonUnifMutation,[2 25 3]);%% V. 輸出最優解並繪製最優點xhold onplot (endPop(:,1),endPop(:,2),ro)%% VI. 繪製迭代進化曲線figure(2)plot(trace(:,1),trace(:,3),b:)hold onplot(trace(:,1),trace(:,2),r-)xlabel(Generation); ylabel(Fittness);legend(Mean Fitness, Best Fitness)