【路徑規劃】改進差分算法多無人機協同三維航迹規劃【Matlab 045期】

一、簡介

1、差分進化算法的介紹

差分進化算法(Differential Evolution, DE)是一種基于群體差異的啟發式随機搜尋算法，該算法是由R.Storn和K.Price為求解Chebyshev多項式而提出的。DE算法也屬于智能優化算法，與前面的啟發式算法，如ABC，PSO等類似，都屬于啟發式的優化算法。DE算法是我在一篇求解盒子覆寫問題論文中使用的一種優化算法。

2、差分進化算法的流程

初始化種群

變異

交叉

選擇

三、差分進化的具體步驟

對于無限制優化問題

4、選擇

在DE中采用的是貪婪選擇的政策，即選擇較優的個體作為新的個體。

二、源代碼

%清空環境
clear;
 
%定義地形對象
cTerrain = CTerrain3D;
%定義威脅區對象
cTread = CTread;
 
%調整為統一的圖形環境
figure('Renderer','opengl');
 
%繪制地形和威脅區
cTerrain.draw();
cTread.draw();
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%資料形式說明
%xs 初始點位置集合，三維點集
%yt 目标點位置集合，三維點集
%MxsEna 能力矩陣，集合中的二進制組表示最大最小飛行速度
%MxsDIs 最大航程矩陣，集合中的值表示UAV最大可飛的距離
%MytTOrd 任務點間的時序坐标，要求盡量在前面的先執行
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%調用目标配置設定算法
%AssignType表示不同的模型，1, N=M; 2, N>M; 3, N<M
%Key表示算法執行次數, 0，執行一次，1，執行多次
AssignType =1;
Key = 0;
 
%時間測試
Time = cputime;
 
%%    第一種情況的實驗
if AssignType == 1
    %%%%%%%%%%%%%%%%%%%%%%%資料區%%%%%%%%%%%%
    xs = [%11 2 3;2 17 5; 34 26 7;5 2 2;6 33 3;27 34 6;21 45 5;25 12 3;22 17 11;13 31 12;
        %45 21 11; 36 22 11;13 21 16;41 25 10;25 25 11;53 12 14;22 12 12;18 32 11; 67 34 12;26 16 15;
        78 20 15;93 31 12;31 20 13;112 32 15; 134 26 17;45 52 12;36 63 13;67 34 16;21 85 15;32 62 13;];
    yt = [%40 210 12;170 90 13 ; 80 197 21 ;172 120 13;160 56 13;160 143 21;170 200 21;113 200 12;97 134 16;100 145 11;
        %81 101 21; 72 152 12; 133 60 11;84 164 21; 150 90 21;146 121 12; 167 54 12; 108 165 12;99 120 21;110 143 11;
        70 181 12;15 133 13 ; 19 151 12 ;160 192 13;101 120 23;160 113 12;82 101 11;173 140 12;182 65 14; 128 156 12;];
    
    MxsEna=[%0.2 0.3; 0.2 0.4;0.4 0.75;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;0.2 0.3; 0.2 0.4;
        % 0.4 0.75;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;
        0.2 0.3; 0.2 0.4;0.4 0.75;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;0.3 0.5;0.3 0.6;];
    
    MxsDis=[%400 700 650 500 700 900 450 610 400 700
        %650 500 700 900 450 610 700 900 450 610
        500 700 300 350 700 900 450 610 450 610];
    
    
    ytW = [%1 3 4 2 1 1 3 2 1 2
        %3 2 1 3 2 1 2 3 2 1
        1 1 1 1 1 1 1 1 1 1];
    
    MytTOrd=[3 4; 5 2; 6 8; 7 4;];
    
    %引入新的協同矩陣，最大起始時間矩陣
    Twait = [];
    Twindow=[];
    
    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    if Key == 0
        
        
        %%%%%%%%%%%%%%%%%%%%%%算法執行區%%%%%%%%%%%%%%%%%%
        %調用目标配置設定算法，并取得解和相關資料,計算算法耗費時間
        %定義目标配置設定算法對象
        DDE1 = DMDEAssignTarget(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd,Twait,Twindow,1);
        % MC = Cal1.GetMcost();
        %Cal1 = CallocationTargetOld1(cTerrain);
        %标簽顯示文字
        xlabel('X/km')
        ylabel('Y/km')
        zlabel('Z/km')
        %DDEAssign1=DDEAssignTarget1(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd);
        %執行run并傳回結果集
        t1 = cputime;
        [solU solT solC solF ] = DDE1.run();
        Time = cputime -t1;
        
        %         %結果
        solU
        solT
        solC
        solF
        Time
        
        
    else if Key == 1
            for i=1:10
                DDE1 = DMDEAssignTarget(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd,Twait,Twindow,i);
                % MC = Cal1.GetMcost();
                %Cal1 = CallocationTargetOld1(cTerrain);
                %标簽顯示文字
                xlabel('X/km')
                ylabel('Y/km')
                zlabel('Z/km')
                %DDEAssign1=DDEAssignTarget1(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd);
                %執行run并傳回結果集
                t1 = cputime;
                [solU solT solC solF ] = DDE1.run();
                solu(i,:) = solU;
                solt(i,:) = solT;
                solc(i,:) = solC;
                solf(i,:) = solF;
                Time(i,:) = cputime -t1;
            end %i
            %         %結果
            solu
            solt
            solc
            solf
            Time
            
        end % key=1
    end % key=0
    
    
    
else if AssignType == 2
        %% 第二種實驗的情況
        %%%%%%%%%%%%%%%%%%%%%%%資料區%%%%%%%%%%%%
        xs = [%11 2 3;2 17 5; 34 26 7;5 2 2;6 33 3;27 34 6;21 45 5;25 12 3;22 17 11;13 31 12;
            %45 21 11; 36 22 11;13 21 16;41 25 10;25 25 11;53 12 14;22 12 12;18 32 11; 67 34 12;26 16 15;
            78 20 15;93 31 12;31 20 13;112 32 15; 134 26 17;45 52 12;36 63 13;67 34 16;21 85 15;32 62 13;];
        yt = [%40 210 12;170 90 13 ; 80 197 21 ;172 120 13;160 56 13;160 143 21;170 200 21;113 200 12;97 134 16;100 145 11;
            %81 101 21; 72 152 12; 133 60 11;84 164 21; 150 90 21;146 121 12; 167 54 12; 108 165 12;99 120 21;110 143 11;
            70 181 12;15 133 13 ; 19 151 12 ;160 192 13 ];
        
        MxsEna=[%0.2 0.3; 0.2 0.4;0.4 0.75;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;0.2 0.3; 0.2 0.4;
            % 0.4 0.75;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;
            0.2 0.3; 0.2 0.4;0.4 0.75;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;0.3 0.5;0.3 0.6;];
        
        MxsDis=[%400 700 650 500 700 900 450 610 400 700
            %650 500 700 900 450 610 700 900 450 610
            500 700 300 350 700 900 450 610 450 610];
        
        
        
        ytW = [%1 3 4 2 1 1 3 2 1 2
            %3 2 1 3 2 1 2 3 2 1
            1 1 1 1];
        
        %這個資料裡都代表的是目标點，是目标點與目标點的關系
        MytTOrd=[3 2];
        
        %引入新的協同矩陣，最大起始時間矩陣
        Twait = [30 40 20 15 50 70 30 80 90 65];
        Twindow=[];
        %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        if Key == 0
            
       
        else if Key == 1
                for i=1:20
                    DDE1 = DMDEAssignTarget(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd,Twait,Twindow,i);
                    % MC = Cal1.GetMcost();
                    %Cal1 = CallocationTargetOld1(cTerrain);
                    %标簽顯示文字
                    xlabel('X/km')
                    ylabel('Y/km')
                    zlabel('Z/km')
                    %DDEAssign1=DDEAssignTarget1(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd);
                    %執行run并傳回結果集
                    t1 = cputime;
                    [solU solT solC solF ] = DDE1.run();
                    solu(i,:) = solU;
                    solt(i,:) = solT;
                    solc(i,:) = solC;
                    solf(i,:) = solF;
                    Time(i,:) = cputime -t1;
                end %i
                %         %結果
                solu
                solt
                solc
                solf
                Time
                
            end % key=1
        end % key=0
        
        
    else if AssignType == 3
            %% 第三種實驗的情況
            %%%%%%%%%%%%%%%%%%%%%%%資料區%%%%%%%%%%%%
            xs = [%11 2 3;2 17 5; 34 26 7;5 2 2;6 33 3;27 34 6;21 45 5;25 12 3;22 17 11;13 31 12;
                %45 21 11; 36 22 11;13 21 16;41 25 10;25 25 11;53 12 14;22 12 12;18 32 11; 67 34 12;26 16 15;
                78 20 15;93 31 12;31 20 13;112 32 15];
            yt = [%40 210 12;170 90 13 ; 80 197 21 ;172 120 13;160 56 13;160 143 21;170 200 21;113 200 12;97 134 16;100 145 11;
                %81 101 21; 72 152 12; 133 60 11;84 164 21; 150 90 21;146 121 12; 167 54 12; 108 165 12;99 120 21;110 143 11;
                70 131 12;15 133 13 ; 19 151 12 ;160 192 13;101 120 23;160 113 12;82 101 11;173 140 12;182 65 14; 45 176 12;];
            
            MxsEna=[%0.2 0.3; 0.2 0.4;0.4 0.75;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;0.2 0.3; 0.2 0.4;
                % 0.4 0.75;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;0.2 0.3;0.35 0.45;0.3 0.5;0.3 0.6;
                0.2 0.5; 0.3 0.4;0.4 0.75;0.3 0.45];
            
            MxsDis=[%400 700 650 500 700 900 450 610 400 700
                %650 500 700 900 450 610 700 900 450 610
                700 700 900 650];
            
            ytW = [%1 3 4 2 1 1 3 2 1 2
                %3 2 1 3 2 1 2 3 2 1
                1 1 1 1 1 1 1 1 1 1];
            
            MytTOrd=[3 4; 5 2];
            
            %引入新的協同矩陣，最大起始時間矩陣
            Twait = [30 40 20 15];
            Twindow=[1300,6000];
            %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
            if Key == 0
                
                
                %%%%%%%%%%%%%%%%%%%%%%算法執行區%%%%%%%%%%%%%%%%%%
                %調用目标配置設定算法，并取得解和相關資料,計算算法耗費時間
                %定義目标配置設定算法對象
                DDE1 = DMDEAssignTarget(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd,Twait,Twindow,1);
                % MC = Cal1.GetMcost();
                %Cal1 = CallocationTargetOld1(cTerrain);
                %标簽顯示文字
                xlabel('X/km')
                ylabel('Y/km')
                zlabel('Z/km')
                %DDEAssign1=DDEAssignTarget1(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd);
                %執行run并傳回結果集
                t1 = cputime;
                [solU solT solC solF]  = DDE1.run();
                Time = cputime -t1;
                
                %         %結果
                solU
                solT
                solC
                solF
                Time
                
                
            else if Key == 1
                    
                    for i=1:20
                        DDE1 = DMDEAssignTarget(cTerrain,xs,yt,MxsEna,MxsDis,ytW,MytTOrd,Twait,Twindow,i);
                        % MC = Cal1.GetMcost();
                        %Cal1 = CallocationTargetOld1(cTerrain);
                        %标簽顯示文字
                        xlabel('X/km')
                        ylabel('Y/km')
                        zlabel('Z/km')
                        
                        t1 = cputime;
                        [solU solT solC solF ] = DDE1.run();
                        solu(i,:) = solU;
                        solt(i,:) = solT;
                        solc(i,:) = solC;
                        solf(i,:) = solF;
                        Time(i,:) = cputime -t1;
                    end %i
                    %         %結果
                    solu
                    solt
                    solc
                    solf
                    Time
                end % key=1
            end % key=0
            
        end % type =3
        
    end % type =2
    
end % type=1
           

三、運作結果

四、備注

版本：2014a