2.5　MATLAB仿真實例

例2.1　用標準遺傳算法求函數f（x）=x+10sin（5x）+7cos（4x）的最大值，其中x的取值范圍為［0，10］。這是一個有多個局部極值的函數，其函數值圖形如圖2.2所示，其MATLAB實現程序如下：

解：仿真過程如下：

（1）初始化種群數目為NP=50，染色體二進制編碼長度為L=20，最大進化代數為G=100，交叉概率為Pc=0.8，變異概率為Pm=0.1。

（2）產生初始種群，將二進制編碼轉換成十進制，計算個體適應度值，并進行歸一化；采用基于輪盤賭的選擇操作、基于概率的交叉和變異操作，產生新的種群，并把歷代的最優個體保留在新種群中，進行下一步遺傳操作。

（3）判斷是否滿足終止條件：若滿足，則結束搜索過程，輸出優化值；若不滿足，則繼續進行迭代優化。

優化結束后，其適應度進化曲線如圖2.3所示，優化結果為x=7.8567，函數f（x）的最大值為24.86。

MATLAB源程序如下：

例2.2　計算函數的最小值，其中個體x的維數n=10。這是一個簡單的平方和函數，只有一個極小點x=（0，0，…，0），理論最小值f（0，0，…，0）=0。

解：仿真過程如下：

（1）初始化種群數目為NP=100，染色體基因維數為D=10，最大進化代數為G=1000，交叉概率為Pc=0.8，變異概率為Pm=0.1。

（2）產生初始種群，計算個體適應度值；進行實數編碼的選擇以及交叉和變異操作。選擇和交叉操作采用“君主方案”，即在對群體根據適應度值高低進行排序的基礎上，用最優個體與其他偶數位的所有個體進行交叉，每次交叉產生兩個新的個體。在交叉過后，對新產生的群體進行多點變異產生子群體，再計算其適應度值，然后和父群體合并，并且根據適應度值進行排序，取前NP個個體為新群體，進行下一次遺傳操作。

（3）判斷是否滿足終止條件：若滿足，則結束搜索過程，輸出優化值；若不滿足，則繼續進行迭代優化。

優化結束后，其適應度進化曲線如圖2.4所示，優化后的結果為x=［0.0003 -0.0037 0.0069 -0.0000 -0.0020 0.0001 -0.0009 0.0056 0.0052 0.0003］，函數f（x）的最小值為1.24×10-4。

MATLAB源程序如下：

例2.3　旅行商問題（TSP）。假設有一個旅行商人要拜訪全國31個省會城市，他需要選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發的城市。對路徑選擇的要求是：所選路徑的路程為所有路徑之中的最小值。

全國31個省會城市的坐標為［1304 2312；3639 1315；4177 2244；3712 1399；3488 1535；3326 1556；3238 1229；4196 1004；4312 790；4386 570；3007 1970；2562 1756；2788 1491；2381 1676；1332 695；3715 1678；3918 2179；4061 2370；3780 2212；3676 2578；4029 2838；4263 2931；3429 1908；3507 2367；3394 2643；3439 3201；2935 3240；3140 3550；2545 2357；2778 2826；2370 2975］。

解：仿真過程如下：

（1）初始化種群數目為NP=200，染色體基因維數為N=31，最大進化代數為G=1000。

（2）產生初始種群，計算個體適應度值，即路徑長度；采用基于概率的方式選擇進行操作的個體；對選中的成對個體，隨機交叉所選中的成對城市坐標，以確保交叉后路徑每個城市只到訪一次；對選中的單個個體，隨機交換其一對城市坐標作為變異操作，產生新的種群，進行下一次遺傳操作。

（3）判斷是否滿足終止條件：若滿足，則結束搜索過程，輸出優化值；若不滿足，則繼續進行迭代優化。

優化后的路徑如圖2.5所示，其適應度進化曲線如圖2.6所示。

MATLAB源程序如下：

例2.4　0-1背包問題。有N件物品和一個容量為V的背包。第i件物品的體積是c（i），價值是w（i）。求解將哪些物品放入背包可使物品的體積總和不超過背包的容量，且價值總和最大。假設物品數量為10，背包的容量為300。每件物品的體積為［95，75，23，73，50，22，6，57，89，98］，價值為［89，59，19，43，100，72，44，16，7，64］。

解：仿真過程如下：

（1）初始化種群數目為NP=50，染色體基因維數為L=10，最大進化代數為G=100。

（2）產生二進制初始種群，其中1表示選擇該物品，0表示不選擇該物品。取適應度值為選擇物品的價值總和，計算個體適應度值，當物品體積總和大于背包容量時，對適應度值進行懲罰計算。

（3）對適應度進行歸一化，采用基于輪盤賭的選擇操作、基于概率的交叉和變異操作，產生新的種群，并把歷代的最優個體保留在新種群中，進行下一步遺傳操作。

（4）判斷是否滿足終止條件：若滿足，則結束搜索過程，輸出優化值；若不滿足，則繼續進行迭代優化。

優化結果為［1 0 1 0 1 1 1 0 0 1］，1表示選擇相應物品，0表示不選擇相應物品，價值總和為388。其適應度進化曲線如圖2.7所示。

MATLAB源程序如下：