【正文】 ePTexecuteCrossover(x, y, cityNum)。while (pop 0) {x = (int) (() * popSize)。int y。循環(huán)交叉算子較好的保留了父代的位值特征，較好的避免了不合法個(gè)體的產(chǎn)生，但是由于算法的復(fù)雜性，使得運(yùn)算速度大為降低。}}}雙切點(diǎn)交叉算子的 JAVA實(shí)現(xiàn)類似于單切點(diǎn)交叉算子，在此不做詳細(xì)介紹。 (y).get(k).getSequece() == .get(y).get(i).getSequece())(y).get(k).setSequece((x).get(i).getSequece())。while (k cityNum) {if ((k != i)amp。j++。amp。int j = 0。(x).get(i).setSequece((y).get(i).getSequece())。 i cityNum。// x y 兩個(gè)體執(zhí)行普通遺傳算法的單切點(diǎn)交叉pop。int location = (int) (() * cityNum)。while (pop 0) {x = (int) (() * popSize)。int y。 i++)// 計(jì)算每一個(gè)種群的選擇概率(i).setSelectP((double) (i).getFitness() / sum)。for (int i = 0。 i popSize。計(jì)算選擇算子的 JAVA 實(shí)現(xiàn)：private void CalSelectP(int popSize) {double sum = 0。(i).setFitness(len2)。 j++) {len2 += [(i).get(j).getSequece()][.get(i).get(j + 1).getSequece()]。for (int j = 0。 i popSize。對(duì)優(yōu)化問題，適應(yīng)度函數(shù)就是目標(biāo)函數(shù)。}}4．2．3 適應(yīng)度函數(shù)適應(yīng)度函數(shù)一般根據(jù)目標(biāo)函數(shù)來(lái)進(jìn)行設(shè)計(jì)。(i).setExceptp(0)。}(i).setFitness(0)。num[r] = num[temp 1]。 j++) {int r = (int) (() * temp)。// 隨機(jī)地初始化城市序列for (int j = 0。 j++) {num[j] = j。for (int j = 0。 i++) {(i, new GenoType((list), 0, 0, 0, 0))。for (int i = 0。P 2[n]即為洗牌隨機(jī)生成后的序列。i 增加 1 后，進(jìn)入下一輪循環(huán)。4．2．2 初始化種群 遺傳算法是一種既有群體尋優(yōu)的方法算法運(yùn)行時(shí)是一個(gè)群體在搜索空間進(jìn)行搜索，一般采用隨機(jī)方法產(chǎn)生一個(gè)初始種群。解碼就是求出一條染色體所對(duì)應(yīng)的路徑長(zhǎng)度的過程。本文在 TSP 求解中，采用基于城市序號(hào)的順序?qū)崝?shù)編碼，它是用１～ｎ的自然數(shù)來(lái)編碼，這種編碼不允許重復(fù)，即 xi 1, 2 , 3 ,… , n , 且當(dāng) i j 時(shí)，x i xj 如：??X=（2 3 1 5 4 7 6）表示一個(gè)染色體長(zhǎng)度為 7 的順序?qū)崝?shù)編碼，對(duì)于 7 個(gè)城市的旅行商問題，上述編碼表示 23154762 的一條行走路線。在遺傳算法中最初使用的編碼方法是二進(jìn)制編碼：每個(gè)染色體使用固定長(zhǎng)度的 0，1 字符串表示，如：X=（0110010）表示一個(gè)染色體，該個(gè)體的染色體長(zhǎng)度為 7，二進(jìn)制編碼具有易于位值計(jì)算、包括的實(shí)數(shù)范圍大的優(yōu)點(diǎn)。4．2 遺傳算法求解 TSP 問題4．2．1 編碼與解碼在遺傳算法中每一個(gè)個(gè)體表示成一個(gè)染色體，每一個(gè)染色體又是由一個(gè)個(gè)基因位所構(gòu)成的。這就是窮舉搜索法的思想，理論上它可以解決任何組合優(yōu)化問題，但是對(duì)于 n 個(gè)城市的 TSP 問題來(lái)說(shuō)，可能的合法回路有 條,計(jì)算每一條路徑需求 n 個(gè)距離之和，因此計(jì)算量正比于2)!1(?n。4 遺傳算法在 TSP 問題上的應(yīng)用4．1 TSP 問題概述 TSP 問題就是已知個(gè)城市各城市間的距離，一旅行商從某一城市出發(fā)訪問每個(gè)城市一次且僅一次，最后回到出發(fā)城市，如何安排才能使其所走路程最短？ 問題的數(shù)學(xué)模型可以描述為：對(duì)于 n 個(gè)城市 V={v1,v2,…,vn}的一訪問次序?yàn)門=(t1,t2,…,tn), ti Vi（i=1，2,…，n）,t n+1 = t1,則問題即要求 min ，其中? ???nitid1表示城市 i 與城市 i+1 之間的距離。在變異操作中，變異率不能取得太大，如果變異率大于 ，遺傳算法就退化為隨機(jī)搜索，而遺傳算法的一些重要的數(shù)學(xué)特性和搜索能力也不復(fù)存在了。P1=A1∣A2P2=B1∣B2C1= A1|B2C2 = B1|A2P1=A1∣A2 ∣A3P2=B1∣B2 ∣B3P1=A1∣B2∣A3P2=B1∣A2∣B3C1=2 9 5 3 8 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) 操作變異本身是一種局部隨機(jī)搜索，與選擇/交叉算子結(jié)合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機(jī)搜索能力。 切點(diǎn) 切點(diǎn) 切點(diǎn) 切點(diǎn) 圖 3 雙切點(diǎn)交叉示意圖（3）循環(huán)交叉（cycle crossover ） 循環(huán)交叉 [12]的基本思想是子串位置上的值必須與父母相同位置上的值相等。 切點(diǎn) 切點(diǎn) 圖 2 單切點(diǎn)交叉示意圖單切點(diǎn)交叉操作的信息量比較小，交叉位置的選擇可能帶來(lái)較大的偏差，并且染色體末尾的基因總是被交換。??Njjixf1)(2．2．2 交叉(crossover)操作 交叉就是互換兩個(gè)染色體某些位上的基因以產(chǎn)生新的個(gè)體，普通遺傳算法中常用的交叉算子有單切點(diǎn)交叉、雙切點(diǎn)交叉、循環(huán)交叉，下面我們來(lái)進(jìn)行依次介紹（1）單切點(diǎn)交叉（singlepoint crossover ）初始化群體計(jì)算適應(yīng)度交叉操作變異操作條件終止結(jié)束選擇操作適合度最優(yōu)群體單切點(diǎn)交叉的思想是從種群中選出兩個(gè)個(gè)體 P1 和 P2，隨機(jī)地選擇一個(gè)切點(diǎn)（cutting） ，將切點(diǎn)兩側(cè)分別看成一個(gè)子串，將右側(cè)的子串分別進(jìn)行交換，這樣就得到了兩個(gè)新的個(gè)體 C1 和 C2。賭輪選擇的基本思想：做一個(gè)輪盤，然后按照各個(gè)染色體的個(gè)體適應(yīng)度比例轉(zhuǎn)化為選中概率(選擇概率)，將輪盤分成若干個(gè)扇區(qū)，隨機(jī)地產(chǎn)生「0, 1 ]之間的隨機(jī)數(shù)，這樣就相當(dāng)于轉(zhuǎn)動(dòng)輪盤，獲得轉(zhuǎn)盤停止時(shí)指針位置，指針停止在某一扇區(qū)，該扇區(qū)代表的個(gè)體即被選中。算法簡(jiǎn)單流程圖如右圖所示：圖 1 遺傳算法簡(jiǎn)單流程圖2．2 普通遺傳算法的遺傳操作2．2．1 選擇（selection）操作選擇（selection）操作是模擬生物界優(yōu)勝劣汰的自然選擇法則的一種染色體運(yùn)算，就是從種群中選擇適應(yīng)度較高的染色體進(jìn)行復(fù)制，以生成下一代種群?！?6) 沒有滿足某種停止條件，則轉(zhuǎn)第(2) 步，否則進(jìn)入（7） ?！?4) 按概率 Pc 進(jìn)行交叉操作 。　(2) 計(jì)算群體上每個(gè)個(gè)體的適應(yīng)度值。因此它是一種啟發(fā)式搜索。(4) GA 使的選擇、交叉、變異三個(gè)算子都是隨機(jī)操作，具有不確定性。形象地說(shuō)，GA 是并行地爬多個(gè)峰，這一特點(diǎn)使 GA 具有較好的全局搜索性能，大大減少了陷入局部最優(yōu)解的可能性。使得我們可以借鑒生物學(xué)中的染色體和基因的概念，模仿自然界生物的遺傳和進(jìn)化機(jī)理對(duì)問題參數(shù)集的編碼(染色體群) 進(jìn)行進(jìn)化，而不是象傳統(tǒng)優(yōu)化方法對(duì)參數(shù)本身進(jìn)行優(yōu)化。這樣，一代一代地進(jìn)化，最后就會(huì)收斂到最適應(yīng)環(huán)境的一個(gè)“染色體”上，得到問題的最優(yōu)解。并且，在執(zhí)行遺傳算法之前，給出一群“ 染色體” ，也即是假設(shè)解。變異率：參加發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，取值范圍一般為 ~,這里主要是參考了計(jì)算機(jī)畢業(yè)設(shè)計(jì)網(wǎng) 上的文章。遺傳操作（geic operator）：遺傳算法中有三種關(guān)于染色體的運(yùn)算：選擇、交叉和變異，這三種運(yùn)算被稱為遺傳操作。 適應(yīng)度( fitness)：各個(gè)個(gè)體對(duì)環(huán)境的適應(yīng)程度叫做適應(yīng)度(fitness) 。 個(gè)體(individual) ：指染色體帶有特征的實(shí)體。1．2 遺傳算法的基本原理1．2．1 遺傳算法基本概念 種群( population)：染色體帶有特征的個(gè)體的集合稱為種群。而本文要實(shí)現(xiàn)的基于佳點(diǎn)集的遺傳算法就是通過設(shè)計(jì)合適的交叉算子來(lái)解決收斂速度和收斂性能的問題的。盡管這一結(jié)論說(shuō)明了改進(jìn)的 GA 最終能收斂到全局最優(yōu)解，但收斂到最優(yōu)解的時(shí)間可能很長(zhǎng)。（2（ 遺傳算法的收斂性研究。　　2022 年，江雷等針對(duì)并行遺傳算法求解 TSP 問題, 探討了使用彈性策略來(lái)維持群體的多樣性,使得算法跨過局部收斂的障礙,向全局最優(yōu)解方向進(jìn)化。2022