function SGA_TSP()
%旅行商問題的遺傳算法解法


disp('此次計算的距離矩陣如下')
%此矩陣為一個演示矩陣，上面的代碼產生了一個隨機的距離矩陣，但又被此矩陣暫時覆蓋
distance=[  Inf    76    45    81    34    99    12    70    10    21
    76   Inf    61    72     2     9   100    84    19     5
    45    61   Inf    44    15    96    83    86    80    40
    81    72    44   Inf    98    21    53    46    41    16
    34     2    15    98   Inf    23     8    99    13    57
    99     9    96    21    23   Inf    70    87    89     8
    12   100    83    53     8    70   Inf    73    24    84
    70    84    86    46    99    87    73   Inf    90    82
    10    19    80    41    13    89    24    90   Inf    41
    21     5    40    16    57     8    84    82    41   Inf];  %輸出距離矩陣
 

guimo=10;
%遺傳算法開始
gen_len=guimo; %基因長度
cross_probability=0.01;%交叉概率
mutate_probability=0.005;%變異概率
Maxgen=300;  %最大遺傳代數
NIND=gen_len*10;    %個體數目



%生成初始種群 關鍵是生成可行解
Chrom=rand(NIND,gen_len);
for i=1:NIND
    [a indexa]=sort(Chrom(i,:));%排序值是不會重復的
    Chrom(i,:)=indexa; 
end

%計算目標函數值
Obj(1:NIND)=0;
for j=1:NIND
    for i=1:9
        Obj(j)=Obj(j)+distance(Chrom(j,i),Chrom(j,i+1));
    end
    Obj(j)=Obj(j)+distance(Chrom(j,10),Chrom(j,1));
end

%記錄每一代的最小值,平均值
ma(1,1)=1;
[ma(1,2) index]=min(Obj);
most_min=ma(1,2);%全局最優值
most_min_index=1;
%種群平均值
ma(1,3)=round(mean(Obj));
ma(1,4:3+gen_len)=Chrom(index,:);
for gen=1:Maxgen
    %終止判斷
    %最近30代的最優值都比前面的最優值大則結束
    if gen>29+most_min_index & gen>100
        [m n]=find(ma(gen-30:gen,2)>most_min);
        if length(n)>29
            break;
        end
    end
    %計算適應度
    mmm=max(Obj)+1;
    Obj=mmm-Obj+1;
    sumObj=sum(Obj);%所有個體的目標函數值之和
    fitness=Obj/sumObj;%每個個體的選擇概率
    fitness2=cumsum(fitness);%累計概率
    
    %輪盤選擇
    tempChrom=Chrom;%儲存一個原始的個體值 父代
    index=1;
    for k=1:NIND
        for j=1:NIND
            if rand<fitness2(j)
                Chrom(index,:)=tempChrom(j,:);
                index=index+1;
                break;
            end
        end
    end
    %交叉運算    關鍵是如何產生可行解
    n1=0;
    for i=1:NIND
        if rand(1)<cross_probability 
            if n1==0
                n1=1;
                temindex=i;%紀錄第一個交叉個體
                continue;
            else %選夠兩個個體則交叉
                temp1=Chrom(temindex,:);%記錄父代1
                temp2=Chrom(i,:);%%記錄父代2
                Chrom(i,:)=tsp_cross_func1(temp1,temp1,distance);%TSP的一個啟發式交叉算法函數產生一個子代
                %另一個子代從父代中繼承一個較好的
                if Obj(i)>Obj(temindex)
                    Chrom(temindex,:)=temp2;
                else
                    Chrom(temindex,:)=temp1;
                end
                n1=0;
            end
        end
    end
    %Chrom  %檢查交叉運算是否正確,解是否可行解
    %變異運算 實際上是交換位置
    for i=1:NIND
        for j=1:gen_len
            if rand<mutate_probability
                value=round(rand*(gen_len-1))+1;
                tt=Chrom(i,value);
                Chrom(i,value)=Chrom(i,j);
                Chrom(i,j)=tt;
            end
        end
    end
    %計算目標函數值
    Obj(1:NIND)=0;
    for j=1:NIND
        for i=1:9
        Obj(j)=Obj(j)+distance(Chrom(j,i),Chrom(j,i+1));
        end
        Obj(j)=Obj(j)+distance(Chrom(j,10),Chrom(j,1));
    end
    %記錄每一代的最小值,平均值
    ma(gen+1,1)=gen+1;
    [ma(gen+1,2) index]=min(Obj);
    %各代種群平均值
    ma(gen+1,3)=round(mean(Obj));
    ma(gen+1,4:3+gen_len)=Chrom(index,:);
    [most_min index]=min(ma(:,2));
    most_min_index=index;

end

disp('計算過程中的最優值記錄')
disp('代數       最優值       平均值          ||||最優解---------------')
disp(num2str(ma))

[best_Y ]=min(ma(:,2));
str=['最短路徑為: ' num2str(best_Y)  ];
disp(str)

X=ma(index,4:3+gen_len);
str=['最優解為:   ' num2str(X)  '代數： ' num2str(index)];
disp(str)


function child=tsp_cross_func1(father1,father2,distance)
%TSP的一個啟發式交叉算法函數
%該算法以一定概率計算出一個比父代好的子代
%算法思路：F1：10 4 3 2 9 7 8 1 5 6  F2：9 1 3 5 2 6 7 8 4 10 。
%隨機確定交叉點，如4,F1中第四位為2。
%將F1向左旋轉3位，使第四位在成為第一位 F1：2 9 7 8 1 5 6 10 4 3。
%在F2中找到2所在位置，進行旋轉2成為第一個 F2：2 6 7 8 4 10 9 1 3 5。
%然后比較disance(2-9)  disance(2-6),取比較小的如2-6所在父代F2,F2不變,
%將F1的后9位旋轉,使6在第2位  成為F2: 2 6 10 4 3 9 7 8 1 5
%這樣就形成了2 6 *********的模式,如此往復,

%演示的例子
%distance=[  Inf    76    45    81    34    99    12    70    10    21
%    76   Inf    61    72     2     9   100    84    19     5
%    45    61   Inf    44    15    96    83    86    80    40
 %   81    72    44   Inf    98    21    53    46    41    16
%    34     2    15    98   Inf    23     8    99    13    57
%    99     9    96    21    23   Inf    70    87    89     8
%    12   100    83    53     8    70   Inf    73    24    84
%    70    84    86    46    99    87    73   Inf    90    82
%    10    19    80    41    13    89    24    90   Inf    41
%    21     5    40    16    57     8    84    82    41   Inf];
%father1=[10 4 3 2 9 7 8 1 5 6];
%father2=[9 1 3 5 2 6 7 8 4 10];



len=length(father1);

pos=round(rand*(len-1))+1;%交叉點
%pos=3;

pos2=find(father2==father1(pos));

%以下完成第一次旋轉移動
tem1=father1(pos:len);
tem2=father1(1:pos-1);
father1=[tem1 tem2];

tem1=father2(pos2:len);
tem2=father2(1:pos2-1);
father2=[tem1 tem2];

%一下完成剩下的旋轉移動生成一個后代
for i=2:len
    if distance(father1(i-1),father1(i))<=distance(father2(i-1),father2(i))  
        pos2=find(father2==father1(i));
        tem0=father2(1:i-1);
        tem1=father2(pos2:len);
        tem2=father2(i:pos2-1);
        father2=[tem0 tem1 tem2];
    else
        pos2=find(father1==father2(i));
        tem0=father1(1:i-1);
        tem1=father1(pos2:len);
        tem2=father1(i:pos2-1);
        father1=[tem0 tem1 tem2];
    end
end
child=father1;