通用的改進遺傳算法求解帶限制的優化問題（MATLAB代碼）

目錄

​​1 概述​​

​​2 遺傳算法​​

​​2.1 遺傳算法的基本概念​​

​​2.2 遺傳算法的特點 ​​

​​2.3 程式框圖 ​​

​​3 運作結果​​

​​ 4 通用的改進遺傳算法求解帶限制的優化問題（MATLAB代碼）​​

1 概述

       遺傳算法(Genetic Algorithm,GA)是模拟生物在自然環境中的遺傳和進化過程而形成的自适應全局優化搜尋算法。它最早由美國的J.H.Holland教授提出,起源于20世紀60年代對自然和人工自适應系統的研究;70年代，K.A.De Jong基于遺傳算法的思想，在計算機上進行了大量的純數值函數優化計算試驗80年代，遺傳算法由D.J.Goldberg在一系列研究工作的基礎上歸納總結而成。遺傳算法是通過模仿自然界生物進化機制而發展起來的随機全局搜尋和優化方法。它借鑒了達爾文的進化論和孟德爾的遺傳學說，本質上是一種并行、高效、全局搜尋的方法，它能在搜尋過程中自動擷取和積累有關搜尋空間的知識，并自适應地控制搜尋過程以求得最優解。遺傳算法操作:使用“适者生存”的原則，在潛在的解決方案種群中逐次産生一個近似最優的方案。在每一代中，根據個體在問題域中的适應度值和從自然遺傳學中借鑒來的再造方法進行個體選擇,産生一個新的近似解。這個過程導緻種群中個體的進化，得到的新個體比原個體更能适應環境。

       自然選擇學說認為适者生存，生物要存活下去，就必須進行生存鬥争。生存鬥争包括種内鬥争、種間鬥争以及生物跟環境之間的鬥争三個方面。在生存鬥争中，具有有利變異的個體容易存活下來,并且有更多的機會将有利變異傳給後代;具有不利變異的個體就容易被淘汰，産生後代的機會也将少得多。是以，凡是在生存鬥争中獲勝的個體都是對環境适應性比較強的個體。達爾文把這種在生存鬥争中适者生存、不适者淘汰的過程叫作自然選擇。達爾文的自然選擇學說表明，遺傳和變異是決定生物進化的内在因素。遺傳是指父代與子代之間，在性狀上存在的相似現象;變異是指父代與子代之間，以及子代的個體之間，在性狀上存在的差異現象。在生物體内，遺傳和變異的關系十分密切。一個生物體的遺傳性狀往往會發生變異，而變異的性狀有的可以遺傳。遺傳能使生物的性狀不斷地傳送給後代，是以保持了物種的特性;變異能夠使生物的性狀發生改變，進而适應新的環境而不斷地向前發展。生物的各項生命活動都有它的物質基礎，生物的遺傳與變異也是這樣。根據現代細胞學和遺傳學的研究得知，遺傳物質的主要載體是染色體，基因是有遺傳效應的片段，它儲存着遺傳資訊，可以準确地複制，也能夠發生突變。生物體自身通過對基因的複制和交叉，使其性狀的遺傳得到選擇和控制。同時，通過基因重組、基因變異和染色體在結構和數目上的變異産生豐富多彩的變異現象。生物的遺傳特性，使生物界的物種能夠保持相對的穩定;生物的變異特性，使生物個體産生新的性狀，以至形成了新的物種，推動了生物的進化和發展。由于生物在繁殖中可能發生基因交叉和變異，引起了生物性狀的連續微弱改變，為外界環境的定向選擇提供了物質條件和基礎，使生h2物的進化成為可能。

2 遺傳算法

2.1 遺傳算法的基本概念

      簡單而言，遺傳算法使用群體搜尋技術，将種群代表一組問題解，通過對目前種群施加選擇、交叉和變異等一系列遺傳操作來産生新一代的種群，并逐漸使種群進化到包含近似最優解的狀态。由于遺傳算法是自然遺傳學與計算機科學互相滲透而形成的計算方法，是以遺傳算法中經常會使用一些有關自然進化的基礎術語，其中的術語對應關系如表2.1所示。

遺傳學術語

遺傳算法術語

群體

可行解集

個體

可行解

染色體

可行解的編碼

基因

可行解編碼的分量

基因形式

遺傳編碼

适應度

目标函數值

選擇

選擇操作

交叉

交叉操作

變異

變異操作

2.2 遺傳算法的特點 

遺傳算法是模拟生物在自然環境中的遺傳和進化的過程而形成的一種并行、高效、全局搜尋的方法，它主要有以下特點:

(1)遺傳算法以決策變量的編碼作為運算對象。這種對決策變量的編碼處理方式，使得在優化計算過程中可以借鑒生物學中染色體和基因等概念，模仿自然界中生物的遺傳和進化等的機理，友善地應用遺傳操作算子。特别是對一些隻有代碼概念而無數值概念或很難有數值概念的優化問題，編碼處理方式更顯示出了其獨特的優越性。

(2)遺傳算法直接以目标函數值作為搜尋資訊。它僅使用由目标函數值變換來的适應度函數值，就可确定進一步的搜尋方向和搜尋範圍，而不需要目标函數的導數值等其他一些輔助資訊。實際應用中很多函數無法或很難求導，甚至根本不存在導數，對于這類目标函數的優化群組合優化問題，遺傳算法就顯示了其高度的優越性，因為它避開了函數求導這個障礙。

(3)遺傳算法同時使用多個搜尋點的搜尋資訊。遺傳算法對最優解的搜尋過程,是從一個由很多個體所組成的初始群體開始的，而不是從單一的個體開始的。

對這個群體所進行的選擇、交叉、變異等運算，産生出新一代的群體，其中包括了很多群體資訊。這些資訊可以避免搜尋一些不必搜尋的點，相當于搜尋了更多的點，這是遺傳算法所特有的一種隐含并行性。

(4)遺傳算法是一種基于機率的搜尋技術。遺傳算法屬于自适應機率搜尋技術，其選擇、交叉、變異等運算都是以一種機率的方式來進行的，進而增加了其搜尋過程的靈活性。雖然這種機率特性也會使群體中産生一些适應度不高的個體，但随着進化過程的進行，新的群體中總會更多地産生出優良的個體。與其他一些算法相比，遺傳算法的魯棒性使得參數對其搜尋效果的影響盡可能小。(5)遺傳算法具有自組織、自适應和自學習等特性。當遺傳算法利用進化過程獲得資訊自行組織搜尋時，适應度大的個體具有較高的生存機率，并獲得更适應環境的基因結構。同時，遺傳算法具有可擴充性，易于同别的算法相結合，生成綜合雙方優勢的混合算法。

2.3 程式框圖 

遺傳算法的運算流程如圖2.1所示。具體步驟如下:

(1)初始化。設定進化代數計數器g=0，設定最大進化代數G，随機生成NP個個體作為初始群體P(0)。

(2)個體評價。計算群體P()中各個個體的适應度。

(3)選擇運算。将選擇算子作用于群體，根據個體的适應度，按照一定的規則或方法，選擇一些優良個體遺傳到下一代群體

(4)交叉運算。将交叉算子作用于群體，對選中的成對個體，以某一機率交換它們之間的部分染色體，産生新的個體。

(5)變異運算。将變異算子作用于群體，對選中的個體，以某一機率改變某一個或某一些基因值為其他的等位基因。群體P(i)經過選擇、交叉和變異運算之後得到下一代群體P(t+1)。計算其适應度值，并根據适應度值進行排序，準備進行下一次遺傳操作。

(6)終止條件判斷:若g<G，則g=g+1，轉到步驟(2);若g>G，則此進化過程中所得到的具有最大适應度的個體作為最優解輸出，終止計算。

部分代碼：

function New_Population = EnviornmentalSelection(Population,Offspring,state)
% 本函數用來挑選新的種群

N = length(Population);
New_Population = Population;

%% 基本思路如下：為了確定種群的多樣性，采用一對一替換機制。隻有後代表現強于父代才會發生替換。
for i=1:N
    pcv = Population(i).con;
    ccv = Offspring(i).con;
    pf = Population(i).obj;
    cf = Offspring(i).obj;
    if (pcv == 0 && ccv == 0) % 采用 feasible rules 挑選新解
        if pf < cf
            New_Population(i) = Population(i);
        else
            New_Population(i) = Offspring(i);
        end
    else
        if pcv < ccv
            New_Population(i) = Population(i);
        else
            New_Population(i) = Offspring(i);
        end
    end
end

% %% 此處采用精英保留政策，每一次疊代之後，挑選指定數量的最佳解替換最劣解，其中數量于機率根據疊代進度計算
% objs = [New_Population.obj];
% cons = [New_Population.cons];
% [~,index] = sortrows([cons' objs']);
% n = ceil((1-state)*(N/100));
% if rand>state*state/2
%     New_Population(index(end-n+1:end)) = New_Population(index(1:n));
% end
      

3 運作結果

 4 通用的改進遺傳算法求解帶限制的優化問題（MATLAB代碼）