「遺傳交配」也能做成演算法?還有matlab代碼?

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

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

「遺傳交配」也能做成演算法?還有matlab代碼? - 天天要聞

1、遺傳演算法簡介

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

2、遺傳演算法核心概念

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

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

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

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

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

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

「遺傳交配」也能做成演算法?還有matlab代碼? - 天天要聞

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

「遺傳交配」也能做成演算法?還有matlab代碼? - 天天要聞

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

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

「遺傳交配」也能做成演算法?還有matlab代碼? - 天天要聞

(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)輸出最優解;

「遺傳交配」也能做成演算法?還有matlab代碼? - 天天要聞

4、實例及其matlab代碼

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

「遺傳交配」也能做成演算法?還有matlab代碼? - 天天要聞

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
 
            

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

「遺傳交配」也能做成演算法?還有matlab代碼? - 天天要聞

「遺傳交配」也能做成演算法?還有matlab代碼? - 天天要聞

若有小夥伴對機器人任務分配演算法較為興趣的,可以在下面評論交流一波,純屬互相學習!

科學分類資訊推薦

時速 600公里、貼地飛行,我國超導電動高速磁浮列車首次亮相! - 天天要聞

時速 600公里、貼地飛行,我國超導電動高速磁浮列車首次亮相!

每經編輯:杜宇據央視新聞,第十二屆世界高速鐵路大會正在北京舉行,時速達600公里超導電動高速磁浮列車也在本次大會首次亮相。圖片來源:央視新聞中車長客股份公司高級工程師介紹:超導電動高速磁浮是通過車載超導磁體與軌道上的線圈相互作用,實現列車與
認識2種丁酸衍生物 - 天天要聞

認識2種丁酸衍生物

丁酸鈉與三丁酸甘油酯作為丁酸的衍生物,在動物消化道中被分解成丁酸和其他物質。他們的主要生物學功能來源於丁酸。腸道上皮細胞優先選用丁酸作為能量源。作為一種短鏈脂肪酸,丁酸在進入小腸後部分以非離子形式被腸道黏膜細胞吸走,直接為腸黏膜細胞生長和增
米東區:這一電化學儲能電站項目推進中 - 天天要聞

米東區:這一電化學儲能電站項目推進中

(米東區融媒體中心記者:黃鵬報道)7月9日,記者在位於米東區北部沙漠東北部的新疆華電烏魯木齊光伏基地100萬千瓦/400萬千瓦時獨立新型儲能示範項目現場看到,工作人員正在對設備進行吊裝調試。該項目總投資約30億元,是全國單體容量最大的電化學
腦圖譜大科學計劃時機已來!中國科學家十項成果給大腦繪高清地圖 - 天天要聞

腦圖譜大科學計劃時機已來!中國科學家十項成果給大腦繪高清地圖

人類大腦是一個非常複雜的組織,要理解大腦的工作原理首先要了解其中的細胞種類和神經聯接規律,近日中國科學家聯合發布系列成果給大腦繪製「高清地圖」。 7月10日深夜,中國科學家聯合發布介觀腦圖譜系列成果,實現從嚙齒類到靈長類大腦的跨越。10項成果以專題論文集的形式集中發表在國際學術期刊《細胞》《神經元》《發育...
國際突破!中大培育光子「雙胞胎」,輻射強度達單光子水平 - 天天要聞

國際突破!中大培育光子「雙胞胎」,輻射強度達單光子水平

7月9日,《自然》雜誌(Nature)在線發表中山大學物理學院王雪華、劉進教授團隊主導的最新研究成果。該團隊提出了一種全新的腔誘導自發雙光子輻射方案,在國際上率先實現與單光子輻射強度相當的自發雙光子輻射,研發出保真度高達99.4%的按需觸發
微型肝臟,是未來希望,還是科技烏托邦 - 天天要聞

微型肝臟,是未來希望,還是科技烏托邦

文︱陸棄隨著全球器官移植需求持續攀升,傳統器官捐獻嚴重不足的問題愈發凸顯。美國初創企業LyGenesis推出了一個令人振奮的創新方案:通過將供體肝細胞注射至患者體內淋巴結中培育「微型肝臟」,嘗試在患者自身體內製造可替代肝臟功能的器官。
「軟黃金」冬蟲夏草,你真的了解嗎? - 天天要聞

「軟黃金」冬蟲夏草,你真的了解嗎?

冬蟲夏草千年傳承的滋補良藥採藥人的尋覓自公元780年起冬蟲夏草便以其獨特的藥用價值被載入史冊從《藏本草》到《中國藥典》均有記載李時珍更將其譽為「人身不老葯」贊其兼具蟲之陽剛與草之陰柔成為中藥中獨一無二的「陰陽同補」聖品享有「東方聖草」「葯中
【鏈博傳奇】中國中車:塑軌道之「鏈」,與世界同行 - 天天要聞

【鏈博傳奇】中國中車:塑軌道之「鏈」,與世界同行

中國中車集團有限公司(以下簡稱「中國中車」)是中國軌道交通裝備領域的「鏈」主企業,是全球規模領先、品種齊全、技術一流的高端裝備製造商和系統解決方案提供商,清潔能源裝備骨幹企業。當前,中國中車搭建了世界領先的軌道交通裝備產品技術研發平台,構建了完整的軌道交通裝備產業體系,開創了軌道交通裝備和清潔能源裝...