遺傳算法

文章部分圖片和思路來自司守奎，孫兆亮《數學建模算法與應用》第二版

定義：遺傳算法是一種基于自然選擇原理和自然遺傳機制的搜索（尋優）算法，模擬自然界中的聲明進化機制，在人工系統中實現特定目標的優化。

本質其實就是群體搜索技術，根據適者生存的原則逐代進化，最終得到最優解或近似最優解。

(資料圖)

操作步驟

1. 產生初始群體（一般就是隨機產生，但是也可以做一些操作，使得初始群體稍微優質一些，比如改良圈算法）
2. 求個體的適應度，即和最優解的距離
3. 根據適者生存的原則選擇優良個體并兩兩配對
4. 通過隨機交叉或隨機變異得到下一代群體
5. 按照第四步的方法逐代進化
6. 滿足進化終止條件

實現中需要注意

根據具體問題確定一種編碼方式，能用數值或字符串表示可行解域的每一個解需要確定適應度函數，即所需求解的目標函數各種參數需要定義，如群體規模，交叉概率，變異概率，終止條件

模型操作方法

編碼

采用十進制編碼，用隨機數列作為染色體

初始種群（改良圈）

對于隨機產生的編碼序列，交換u和v之間的順序，得到的新路徑和原路徑代入目標函數計算，如果新路徑得到的值更小則用新的路徑替換，直到不能修改為止。

更小是因為本題求解的是最短路徑越短越好

交叉

變異

選擇

選擇與目標函數最接近的個體進化到下一代

代碼

這里解決的問題是從經緯度[70,40]出發，走完100個地址的最短路徑

這里的100個地址的經緯度直接隨機生成了random_matrix = rand(25, 8);

是以這樣的方式儲存在txt里

clc,clearsj0=load("the2023_7_9\sj.txt"); % 加載一百個目標的數據x=sj0(:,1:2:8); x=x(:);y=sj0(:,2:2:8); y=y(:);sj=[x,y];d1=[0,0]; % 初始位置sj=[d1;sj;d1];sj=sj*pi/180; % 轉化為弧度制d=zeros(102); % 距離矩陣d初始化 102*102 for i=1:101     for j=(i+1):102         d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));     end end d=d+d"; % 上三角的d和它的轉置相加就得到了對稱陣 w=50;g=100; % 種群數50，進化代數100 rand("state",sum(clock)); % 初始化隨機數發生器 %% 改良圈優化 for k=1:w     c=randperm(100); % 產生1-100的隨機排列     c1=[1,c+1,102]; % 初始解     for t=1:102 % 此循環是修改圈         flag=0; % 退出修改圈的標志         for m=1:100             for n=(m+2):101                 if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))

遺傳算法的改進

遺傳算法作為現代優化算法之一主要特點是對于非線性極值問題能以概率1跳出局部最優解找到全局最優解。這樣的特性全都基于算法中的交叉和變異。在傳統的算法結構中，變異是在交叉的基礎上進行，認為變異只是一個生物學背景機制。交叉方法方面，上述算法使用的是單點交叉（隨機選取某一點，該點右端的遺傳信息全都交換）。

具體改進思路

1. 將變異操作從交叉操作中獨立出來，作為一個單獨的，并列與交叉操作的尋優操作
2. 混沌與遺傳操作聯系在一起
3. 以“門當戶對”的原則進行個體間的交配，并采用單點交叉，確保算法收斂速度
4. 利用混沌序列對染色體中多個基因進行變異，防止算法早熟

模型及算法

交叉操作

對父代以適應度函數值進行排序，目標函數值小的之間相互配對，目標函數值大的之間配對，然后利用混沌序列確定交叉點的位置。比如：O1=a1-a2-a3-a4-a5---a102O2=b1-b2-b3-b4-b5---b102進行交叉操作采用logistic混沌序列x(n+1)=4x(n)[1-x(n)]產生一個2-101之間的正整數

這里是怎么產生的呢：

1. 取一個(0,1)區間上的隨機數作為初始值【比如0.6】
2. 利用x(n+1)=4x(n)[1-x(n)]運算一次產生一個(0,1]區間上的值，稱為混沌值（簡單的求導運算就可以證明一定是在這個區間內）【計算得0.96】
3. 將0.96保存一下，下一次迭代的初值就不是隨機取值了，而是0.96了，【第三代根據0.96來計算混沌值，即0.1536】
4. 這些(0.1)區間的值乘以100+2，最后取整，得到的數字就從那個位置開始進行單點交叉【比如0.6*100+2=62，那就從62開始交叉】
5. 最后得到O1=a1-a2-a3---b62---b102, O2=b1-b2-b3---a62---a102

變異操作

變異算子的設置：給定一個變異率比如0.02之類，隨機地選取兩個2-101之間的整數，這兩個位置進行變異，同樣是使用混沌序列。

改進的遺傳代碼

tic % 計時開始clc,clearsj0=load("the2023_7_9\sj.txt"); % 加載一百個目標的數據x=sj0(:,1:2:8); x=x(:);y=sj0(:,2:2:8); y=y(:);sj=[x,y];d1=[40,70]; % 初始位置sj=[d1;sj;d1];sj=sj*pi/180; % 轉化為弧度制d=zeros(102); % 距離矩陣d初始化 102*102 for i=1:101     for j=(i+1):102         d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2)));     end end d=d+d"; % 上三角的d和它的轉置相加就得到了對稱陣 w=50;g=100; % 種群數50，進化代數100 rand("state",sum(clock)); % 初始化隨機數發生器 %% 改良圈優化 for k=1:w     c=randperm(100); % 產生1-100的隨機排列     c1=[1,c+1,102]; % 初始解     for t=1:102 % 此循環是修改圈         flag=0; % 退出修改圈的標志         for m=1:100             for n=(m+2):101                 if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))