2021年08月27日22:40:03 科學 1640

沒錯，「遺傳交配」也能做成演算法。想一下，我們人類的進化史，大海就是我們的家呀！從海洋生物進化到陸地生物，由簡單生物進化到複雜生物……，不禁想起了生物的高考考點。基因、染色體、交配、變異……這些都造成了生物的進化。也許就是從達爾文的進化論衍生出了一種尋優的演算法——遺傳演算法(Genetic Algorithm，簡稱GA)，這演算法是我目前感覺最容易理解的演算法了哦。

1、遺傳演算法簡介

遺傳演算法是由美國教授John holland於1975年左右提出的，它是借鑒了生物界自然選擇和自然遺傳機制的一種隨機搜索演算法，有一種「適者生存」、「優勝劣汰」的蓬勃之氣。遺傳演算法常用來解決傳統搜索演算法難以解決的複雜和非線性的尋優問題。

2、遺傳演算法核心概念

先來補一下生物書簡單的知識：

個體：這個概念很簡單，就是我自己一個人，一個人稱為個體，在遺傳演算法中的個體，也就是指擁有完整一套染色體的解。

群體：我們人類作為一個群體，群體之間可以相互交配，那麼在理想情況下，不同群體之間是不可能發生交配的，即不同群體之間的進化過程是不不干擾的。

基因：染色體中的一個單位，也可以稱為一個特徵分量。

染色體：在生物中是可以簡單理解為只有在發生交配的時候，染色體才會發生變化，也就是只有在交配的時候，群體的染色體類型才會更加地多樣化，群體才能進化。在遺傳演算法中，則解釋為根據問題的類型而編碼形成的一個向量或字元串。

編碼方式：有二進位編碼、浮點數編碼、十進位編碼、有序串編碼、結構式編碼等。像TSP問題的話，是與參訪的城市順序有關的，則稱為有序串編碼。

適應度：適應度是由適應度函數計算出來的，它的值的大小表示對應個體適應環境的程度。其值越大則表示它越優秀。

選擇：從當前群體中按照一定概率(選擇概率)選出優良的個體，使它們有機會作為父代繁殖下一代子孫。個體適應度越大，其被選擇作為父代的概率也就越大，優秀的基因肯定會被遺傳下去的噻！接下來，介紹三種選擇方法吧！

（1）輪盤賭方法:按個體的選擇概率產生一個輪盤，輪盤每個區的角度與個體的選擇概率成比例，然後隨機產生一個0~1的數，選擇輪盤內第一個比隨機數大的個體，如下圖所示，第一個隨機數為0.81，選擇了6號個體，第二個隨機數為0.32，選擇了2號個體。

（2）錦標賽方法：從群體中隨機選擇若干個體，將其中適應度最高的個體保存到下一代。這一過程反覆執行，直到保存到下一代的個體數達到預先設定的數量為止

（3）最佳個體保存方法群體中適應度最高的個體不進行交叉而直接複製到下一代中，保證遺傳演算法終止時得到的最後結果一定是歷代出現過的最高適應度的個體。

變異：類似於生物學中的基因突變，執行變異操作的概率稱為變異運算元，以下介紹6種遺傳演算法中的變異方法。

(1) 位點變異：群體中的個體碼串，隨機挑選一個或多個基因，並對這些基因的基因值以變異概率作變動。

(2)逆轉變異：在個體碼串中隨機選擇兩點（逆轉點），然後將兩點之間的基因值以逆向排序插入到原位置中。

(3)插入變異：在個體碼串中隨機選擇一個碼，然後將此碼插入隨機選擇的插入點中間。

(4)互換變異：隨機選取染色體的兩個基因進行簡單互換。

(5)移動變異：隨機選取一個基因，向左或者向右移動一個隨機位數。

(6)自適應變異：類似於位點變異，但變異概率隨群體中個體的多樣性程度而自適應調整。

交叉：指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉操作是遺傳演算法產生新個體的關鍵步驟，執行交叉操作的概率稱為交叉運算元。主要交叉方法如下：

(1)單點交叉：在個體串中隨機設定一個交叉點，實行交叉時，該點前或後的兩個個體的部分結構進行互換，並生成兩個新的個體。

(2)兩點交叉：隨機設置兩個交叉點，將兩個交叉點之間的碼串相互交換。

(3)均勻交叉：按照均勻概率抽取一些位，每一位是否被選取都是隨機的，並且獨立於其他位。然後將兩個個體被抽取位互換組成兩個新個體。

(4)順序交叉：在兩個父代染色體中隨機選擇起始和結束位置，將父代染色體1該區域內的基因複製到子代1相同位置上，再在父代染色體2上將子代1中缺少的基因按照順序填入。

3、遺傳演算法流程

(1)初始化GA參數，隨機生成初始種群；

(2)計算種群中每一個個體的適應度值；

(3)進行選擇、交叉、變異操作，產生新種群；

(4)是否滿足終止條件，若是，則終止，否則跳轉到(2)；

(5)輸出最優解；

4、實例及其matlab代碼

為了更加具體地解釋遺傳演算法，又來同樣一招，就是利用它來解決TSP問題。一個人從一個城市出發，遍歷完給定的所有城市，並儘可能使整體的旅行距離最短。城市的坐標分布圖如下所示。

function TSP_gaout = TSPGA(xy,dmat,popSize,IterNum,showProg,showResult)
%利用遺傳演算法解決TSP問題
tStart = tic; % 演算法計時器
nargs = 6;
for i = nargin:nargs-1 %nargin代表函數已輸入參數個數
    switch i
        case 0 %產生城市坐標
%              xy = round(500*rand(40,2));%隨機生成40個城市坐標
             xy =[307,415;5,429;287,395;395,159;118,226;224,376;285,55;31,55;
                  248,135;321,262;111,486;419,355;486,156;423,146;253,425;139,456;
                  373,320;118,128;479,44;310,419;300,292;86,474;45,31;128,292;429,143;
                  456,414;350,95;363,221;115,197;288,413;405,338;202,104;494,159;45,67;
                  160,336;256,285;30,85;363,74;278,238;265,454];
        case 1 %計算距離矩陣
             N = size(xy,1);
             a =meshgrid(1:N);%生成N*N升序矩陣
             dmat = reshape(sqrt(sum((xy(a,:)-xy(a',:)).^2,2)),N,N);% '為矩陣的轉置，reshape把數據生成N*N的矩陣
        case 2 %設置種群規模
            popSize = 100;
        case 3 %設置演算法迭代次數
            IterNum = 1e3;
        case 4 %是否展示迭代過程
            showProg = 1;
        case 5 %是否展示最終結果
            showResult =1;
        otherwise
    end
end
%對輸入參數進行檢查
[N,~] = size(xy);%城市個數、維數
[nr,nc] = size(dmat);%距離矩陣的行數和列數
if N~=nr || N~=nc
    error('城市坐標或距離矩陣輸入有誤')
end
showProg = logical(showProg(1));%將數值轉變為邏輯值
showResult = logical(showResult(1));
%畫出城市位置分布圖
figure(1);
plot (xy(:,1),xy(:,2),'k.','MarkerSize',14);
title('城市坐標位置');

%% GA運算元、參數設置
SelectRate = 0.5; %選擇概率
crossRate = 0.9; %交叉概率
mutationRate = 0.1; %變異概率
global_min = Inf; %Inf表示無窮大
popRoute = zeros(popSize,N); %存儲種群個體路徑
offspring = zeros(popSize,N); %存儲後代種群
totaldist = zeros(1,popSize); %記錄每一個個體的路徑長度
minLhistory = zeros(IterNum,1); %存儲每一代種群中的最優路徑長度
subPath = zeros(1,N); %子代「兒子」
BestPath = zeros(1,N);%記錄最優個體
for i =1:popSize
    popRoute(i,:) = randperm(N); %初始化種群，隨機生成路線
end

%% 種群進化
for iter = 1:IterNum
    %計算種群中每一個個體的路徑長度和最短長度路徑
  
    for i = 1:popSize
          d = 0;
        for j = 1:(N-1)
            d = d + dmat(popRoute(i,j),popRoute(i,j+1));%計算路徑起點到終點距離
        end
        totaldist(1,i) = d + dmat(popRoute(i,N),popRoute(i,1));%加上由終點到起點的直線距離
    end
    [minPath,index] = min(totaldist);%找出最短路徑長度minPath,索引index
    minLhistory(iter,1) = minPath;
   %% 畫出迭代過程
    if minPath <global_min %如果距離小於前一個最優距離的話
        global_min = minPath;%更新最優路徑長度
        BestPath = popRoute(index,:);%記錄最優個體
        if showProg %如果需要展示迭代過程的話
            figure(2);
            for i = 1:N-1%畫出中間路段
                plot([xy(BestPath(i),1),xy(BestPath(i+1),1)],[xy(BestPath(i),2),xy(BestPath(i+1),2)],'bo-','LineWidth',2);
                hold on;
            end
            %畫出終點到起點的路線
            plot([xy(BestPath(N),1),xy(BestPath(1),1)],[xy(BestPath(N),2),xy(BestPath(1),2)],'ro-','LineWidth',2);
            title(sprintf('最優路線距離 = %1.2f，迭代次數 = %d次',global_min,iter));
            hold off
        end
    end

  %% 運用錦標賽的方法進行選擇
    t = 4;%錦標賽選手個數
    for k = 1:popSize
        teamDist = zeros(t,1);%記錄每一個參賽選手的路徑長度
        for i = 1:t
            randrow = randi(popSize);%從種群中隨機選擇一個個體
            teamDist(i,1) = totaldist(1,randrow); %距離賦值
        end
        %在4個個體中選擇最好的作為父體1
        parent1 = min(teamDist);
        [~,parent1Y] = find(totaldist ==parent1,1,'first');%返回數組totaldist中第一個滿足要求的元素的行和列下標
        parent1Path = popRoute(parent1Y(1,1),:); %parent1Path是四個路徑中距離最短的路徑（是一個解）
        
        %找第二個父體
        for i = 1:t
            randrow = randi(popSize);%從種群中隨機選擇一個個體
            teamDist(i,1) = totaldist(1,randrow); %距離賦值
        end
        %在4個個體中選擇最好的作為父體2
        parent2 = min(teamDist);
        [~,parent2Y] = find(totaldist ==parent2,1,'first');%返回數組totaldist中第一個滿足要求的元素的行和列下標
        parent2Path = popRoute(parent2Y(1,1),:); %parent2Path是四個路徑中距離最短的路徑（是一個解）
        
        %交叉
        subPath = crossover(parent1Path,parent2Path,crossRate);
        %變異
        subPath = mutate(subPath,mutationRate);
        offspring(k,:) = subPath(1,:);
    end
    popRoute = offspring;
end
%% 展示結果
if showResult
   figure(3);
   plot(minLhistory,'b','LineWidth',2);
   xlabel('迭代次數');
   ylabel('當前最優路徑長度');
   title('最優路徑長度變化曲線圖');
   set(gca,'XLim',[0 IterNum+1],'YLim',[0 1.1*max(minLhistory)]);
end
tEnd = toc(tStart);
fprintf('時間:%d 分  %f 秒.\n', floor(tEnd/60), rem(tEnd,60));%列印時間
end
%% 交叉操作函數（順序交叉）
function subPath = crossover(parent1Path,parent2Path,crossRate)
random = rand();%產生0~1的隨機數
if crossRate >= random %如果交叉概率大於該隨機數，則盡行交叉操作
    [~,length] = size(parent1Path);
    subPath = zeros(1,length);
    setsize = floor(length/2) -1;
    offset = randi(setsize);%%隨機產生兩個插入點
    for i = offset:setsize+offset-1
        subPath(1,i) = parent1Path(1,i);%把父體1的中間段基因賦給子代
    end
    iterator = i+1;
    j = iterator;
    while any(subPath == 0) %一直循壞到子代基因全不為0
        if j>length
            j =1;
        end
        if iterator > length
            iterator =1;
        end
        if ~any(subPath == parent2Path(1,j)) %把父代2中的基因轉移到子代，且不能重複
            subPath(1,iterator) = parent2Path(1,j);
            iterator = iterator+1;
        end
        j = j+1;
    end
else %如果隨機數大於交叉概率,則不發生交叉操作
    subPath = parent1Path;
end
end
%% 變異操作函數
function subPath = mutate(subPath,mutationRate)
random = rand;%產生0~1的隨機數
if mutationRate>=random %變異概率大於隨機數則發生變異
    [~,n] = size(subPath);
    C = ceil(n*rand(1,2));%隨機產生兩個隨機數
    C = sort(C);%升序排列
    subPath(1,[C(2),C(1)]) = subPath(1,[C(1),C(2)]);%將兩個城市位置調轉
else
    subPath =subPath ;
end
end

代碼中的注釋都比較的詳盡，所以過多的話就不解釋了，有啥不懂的，歡迎在評論上討論，或者私信我，直接上結果圖。