【文章內容簡介】 4 6 7 1C2=3 4 8 6 5 9 2 1 7C1=２＿＿３＿＿６＿＿C2= 3＿＿６＿＿２＿＿循環(huán)２：９－４C1=２9 5３8 4６＿＿C2= 3 4 8６5 9２＿＿循環(huán) 4：7－1C1=２9＿３＿4６＿＿C2= 3 4＿６＿9２＿＿循環(huán) 3：5－8P1=２４５３８９６１７P1=３９８６５４２７１循環(huán)１：２－３－６ 圖 4 循環(huán)交叉示意圖2．2．3 變異(mutation) 操作變異本身是一種局部隨機搜索，與選擇/交叉算子結合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機搜索能力。同時使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。在變異操作中，變異率不能取得太大，如果變異率大于 ，遺傳算法就退化為隨機搜索，而遺傳算法的一些重要的數(shù)學特性和搜索能力也不復存在了。最常用的變異操作是按位交換變異，它的基本思想：對于同一個個體的基因如果發(fā)生變異，則隨機與同一個個體的另一個基因交換位置。4 遺傳算法在 TSP 問題上的應用4．1 TSP 問題概述 TSP 問題就是已知個城市各城市間的距離，一旅行商從某一城市出發(fā)訪問每個城市一次且僅一次，最后回到出發(fā)城市，如何安排才能使其所走路程最短？ 問題的數(shù)學模型可以描述為：對于 n 個城市 V={v1,v2,…,vn}的一訪問次序為T=(t1,t2,…,tn), ti Vi（i=1，2,…，n）,t n+1 = t1,則問題即要求 min ，其中? ???nitid1表示城市 i 與城市 i+1 之間的距離。1?itd 對于 TSP 這樣的一個典型的組合優(yōu)化問題，最為普通的一種解決辦法就是窮舉出所有可能的合法序列，然后比較距離函數(shù)，得出最優(yōu)的城市序列。這就是窮舉搜索法的思想，理論上它可以解決任何組合優(yōu)化問題，但是對于 n 個城市的 TSP 問題來說，可能的合法回路有 條,計算每一條路徑需求 n 個距離之和，因此計算量正比于2)!1(?n。即使使用運算速度為 105億次每秒的巨型計算機按窮舉搜索法計算 100 個城市的2!nTSP 問題也需要 10136年的時間，在這里還沒有考慮算法所需的巨大的存儲空間，?由此可見 TSP 問題的時空復雜度之高，這就為遺傳算法的應用提供了機會，下面我們就來看一求解 TSP 問題的遺傳算法。4．2 遺傳算法求解 TSP 問題4．2．1 編碼與解碼在遺傳算法中每一個個體表示成一個染色體，每一個染色體又是由一個個基因位所構成的。這樣每一個個體對象相當于生物體的表現(xiàn)型，而染色體就相當于生物體的基因型，從表現(xiàn)型到基因型的映射稱為編碼。在遺傳算法中最初使用的編碼方法是二進制編碼：每個染色體使用固定長度的 0，1 字符串表示，如：X=（0110010）表示一個染色體，該個體的染色體長度為 7，二進制編碼具有易于位值計算、包括的實數(shù)范圍大的優(yōu)點。適合于背包問題、實優(yōu)化問題和指派問題，但是在另外的一些實際問題如 TSP 問題，二進制編碼編碼長，不易計算同時不易進行變異交叉操作，易產(chǎn)生大量非可行解，所以針對特殊的問題，可以采用不同的編碼方法。本文在 TSP 求解中，采用基于城市序號的順序實數(shù)編碼，它是用１～ｎ的自然數(shù)來編碼，這種編碼不允許重復，即 xi 1, 2 , 3 ,… , n , 且當 i j 時，x i xj 如：??X=（2 3 1 5 4 7 6）表示一個染色體長度為 7 的順序實數(shù)編碼，對于 7 個城市的旅行商問題，上述編碼表示 23154762 的一條行走路線。這種編碼雖然方便，但是要注意編碼的合法性檢查，并對不合法的個體進行合法性修復。解碼就是求出一條染色體所對應的路徑長度的過程。如：一染色體 X 的順序實數(shù)編碼為（2 3 1 5 4 7 6） ，解碼就是要把相鄰兩點的距離進行求和，具體地說就是要把 2 與 3，3 與 1，1 與 5，5 與 4，4 與 7，7 與 6，6 與 2 之間的距離相加，相加的結果就是由解碼得到的路徑長度 d。4．2．2 初始化種群 遺傳算法是一種既有群體尋優(yōu)的方法算法運行時是一個群體在搜索空間進行搜索，一般采用隨機方法產(chǎn)生一個初始種群。本文就是采用是一種經(jīng)典的洗牌隨機生成的方法生成初始種群，設表示編碼的一維數(shù)組為 P1[n]和 P2[n],先把 P1[n]和 P2[n]按城市序號初始化為{0 ， 1，…，n1}，令 i=0，產(chǎn)生一個（n1 ）i 范圍內的整數(shù) r，然后將 P1[n1i]賦值于 P2[i],P1[n1i]賦值給 P1[r]。i 增加 1 后，進入下一輪循環(huán)。如此循環(huán)直至達到所需的群體規(guī)模為止。P 2[n]即為洗牌隨機生成后的序列。其算法 JAVA 實現(xiàn)如下：public void init(ListCity list, int popSize, int cityNum, String fileName) {initDistance(list, fileName, cityNum)。for (int i = 0。 i popSize。 i++) {(i, new GenoType((list), 0, 0, 0, 0))。// 初始化種群數(shù)組int[] num = new int[cityNum]。for (int j = 0。 j cityNum。 j++) {num[j] = j。}int temp = cityNum。// 隨機地初始化城市序列for (int j = 0。 j cityNum。 j++) {int r = (int) (() * temp)。(i).get(j).setSequece(num[r])。num[r] = num[temp 1]。temp。}(i).setFitness(0)。(i).setSelectP(0)。(i).setExceptp(0)。(i).setIsSelected(0)。}}4．2．3 適應度函數(shù)適應度函數(shù)一般根據(jù)目標函數(shù)來進行設計。目標函數(shù)一般表示為 f(x),適應度函數(shù)一般表示為 F（x） 。對優(yōu)化問題，適應度函數(shù)就是目標函數(shù)。TSP 的目標是路徑總長度為最短，路徑總長度可作為 TSP 問題的適應度函數(shù)F（x）= f(x)= （其中 x n+1 = x1 ）???njjxD11),(計算種群適應度的函數(shù) JAVA 實現(xiàn)：private void CalFitness(int popSize, int cityNum) {for (int i = 0。 i popSize。 i++) {double len2 = (i).getFitness()。for (int j = 0。 j cityNum 1。 j++) {len2 += [(i).get(j).getSequece()][.get(i).get(j + 1).getSequece()]。}len2 += [(i).get(0).getSequece()][.get(i).get(cityNum 1).getSequece()]。(i).setFitness(len2)。}}4．2．4 選擇算子 在每一代的運算過程中，個體被選中的概率與其在群體中的相對適應度成正比，即采用賭輪選擇機制。計算選擇算子的 JAVA 實現(xiàn)：private void CalSelectP(int popSize) {double sum = 0。for (int i = 0。 i popSize。 i++)// 計算所有種群的適應度之和sum += (i).getFitness()。for (int i = 0。 i popSize。 i++)// 計算每一個種群的選擇概率(i).setSelectP((double) (i).getFitness() / sum)。}4．2．5 交叉算子普通單切點、雙切點交叉算子由單切點交叉算子的思想，隨機選取個體 AA2，然后隨機地選取一基因位交換兩個體中該基因位之后的基因，而雙切點交叉算子是在隨機選取的兩個個體中隨機的選取兩個基因位，然后把兩基因位之間的基因位相互交換位置，由于我們 TSP 問題采用的是順序實數(shù)編碼，產(chǎn)生的后代也必須是合法的編碼，然而單切點和雙切點交叉都不能保證交叉后個體的合法性，因此我們要對非法個體進行合法性修復，如： 切點 非法個體P1= 2 1 6 7︱4 5 6 3P2= 4 3 1 6︱5 7 6 2P1= 2 1 6 7 5 7 6 2P2= 4 3 1 6 4 5 6 3 圖 5 單切點交叉算子合法性修復示意圖單切點交叉算子的 JAVA實現(xiàn)：public void SiglePointPTcrossover(int popSize, int cityNum, double pxover) {int x。int y。int pop = (int) (popSize * pxover / 2)。while (pop 0) {x = (int) (() * popSize)。y = (int) (() * popSize)。int location = (int) (() * cityNum)。SiglePointPTexecuteCrossover(x, y,