【正文】 的局部性而往往不能全局最優(yōu)，針對(duì)這一問(wèn)題人們采用設(shè)計(jì)合適的交叉算子和變異算子來(lái)解決。該集合內(nèi)個(gè)體數(shù)稱(chēng)為群體的大小。適應(yīng)度函數(shù)（fitness function）：為了體現(xiàn)染色體的適應(yīng)能力，引入了對(duì)問(wèn)題中的每一個(gè)染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)，適應(yīng)度函數(shù)是計(jì)算個(gè)體在群體中被使用的概率。1．2．2 遺傳算法基本原理遺傳算法 [10]GA 把問(wèn)題的解表示成“ 染色體”，在算法中也即是以二進(jìn)制編碼或?qū)崝?shù)編碼的串。1．2．3 遺傳算法的特點(diǎn) 遺傳算法 GA 利用了生物進(jìn)化和遺傳的思想，所以它有許多與傳統(tǒng)的優(yōu)化方法不同的特點(diǎn)(1) GA 遺傳算法是對(duì)問(wèn)題參數(shù)集的編碼(染色體群)作為運(yùn)算對(duì)象。(3) GA 的適應(yīng)性強(qiáng)，僅用適應(yīng)度函數(shù)值來(lái)引導(dǎo)搜索，而不需要問(wèn)題領(lǐng)域的先驗(yàn)知識(shí)或其它輔助信息，從而對(duì)問(wèn)題的依賴(lài)性較小。2 普通遺傳算 法2．1 普通遺傳遺傳算法思想　(1) 初始化群體 ?！?5) 按概率 Pm 進(jìn)行變異操作。最常用的選擇策略是賭輪選擇策略。P1 和 P2 其中稱(chēng)為父代染色體， C1 和 C2 稱(chēng)為子代染色體。循環(huán)交叉操作的具體步驟如下：(a) 選 P1 的第一個(gè)元素作為 C1 的第一個(gè)元素；選 P2 的第一個(gè)元素作為 C2 的第一個(gè)元素；(b) 在 P1 中找 P2 的第一個(gè)元素賦給 C1 的相對(duì)位置……重復(fù)此過(guò)程，直到 P2 上得到 P1 的第一個(gè)元素為止，稱(chēng)為一個(gè)循環(huán)；(c) 對(duì)最前的基因按 P P2 基因輪替原則重復(fù)以上過(guò)程；(d) 重復(fù)以上過(guò)程，直至所有位已完成。最常用的變異操作是按位交換變異，它的基本思想：對(duì)于同一個(gè)個(gè)體的基因如果發(fā)生變異，則隨機(jī)與同一個(gè)個(gè)體的另一個(gè)基因交換位置。即使使用運(yùn)算速度為 105億次每秒的巨型計(jì)算機(jī)按窮舉搜索法計(jì)算 100 個(gè)城市的2!nTSP 問(wèn)題也需要 10136年的時(shí)間，在這里還沒(méi)有考慮算法所需的巨大的存儲(chǔ)空間，?由此可見(jiàn) TSP 問(wèn)題的時(shí)空復(fù)雜度之高，這就為遺傳算法的應(yīng)用提供了機(jī)會(huì)，下面我們就來(lái)看一求解 TSP 問(wèn)題的遺傳算法。適合于背包問(wèn)題、實(shí)優(yōu)化問(wèn)題和指派問(wèn)題，但是在另外的一些實(shí)際問(wèn)題如 TSP 問(wèn)題，二進(jìn)制編碼編碼長(zhǎng)，不易計(jì)算同時(shí)不易進(jìn)行變異交叉操作，易產(chǎn)生大量非可行解，所以針對(duì)特殊的問(wèn)題，可以采用不同的編碼方法。如：一染色體 X 的順序?qū)崝?shù)編碼為（2 3 1 5 4 7 6） ，解碼就是要把相鄰兩點(diǎn)的距離進(jìn)行求和，具體地說(shuō)就是要把 2 與 3，3 與 1，1 與 5，5 與 4，4 與 7，7 與 6，6 與 2 之間的距離相加，相加的結(jié)果就是由解碼得到的路徑長(zhǎng)度 d。如此循環(huán)直至達(dá)到所需的群體規(guī)模為止。 i popSize。 j cityNum。 j cityNum。temp。(i).setIsSelected(0)。TSP 的目標(biāo)是路徑總長(zhǎng)度為最短，路徑總長(zhǎng)度可作為 TSP 問(wèn)題的適應(yīng)度函數(shù)F（x）= f(x)= （其中 x n+1 = x1 ）???njjxD11),(計(jì)算種群適應(yīng)度的函數(shù) JAVA 實(shí)現(xiàn)：private void CalFitness(int popSize, int cityNum) {for (int i = 0。 j cityNum 1。}}4．2．4 選擇算子 在每一代的運(yùn)算過(guò)程中，個(gè)體被選中的概率與其在群體中的相對(duì)適應(yīng)度成正比，即采用賭輪選擇機(jī)制。 i++)// 計(jì)算所有種群的適應(yīng)度之和sum += (i).getFitness()。}4．2．5 交叉算子普通單切點(diǎn)、雙切點(diǎn)交叉算子由單切點(diǎn)交叉算子的思想，隨機(jī)選取個(gè)體 AA2，然后隨機(jī)地選取一基因位交換兩個(gè)體中該基因位之后的基因，而雙切點(diǎn)交叉算子是在隨機(jī)選取的兩個(gè)個(gè)體中隨機(jī)的選取兩個(gè)基因位，然后把兩基因位之間的基因位相互交換位置，由于我們 TSP 問(wèn)題采用的是順序?qū)崝?shù)編碼，產(chǎn)生的后代也必須是合法的編碼，然而單切點(diǎn)和雙切點(diǎn)交叉都不能保證交叉后個(gè)體的合法性，因此我們要對(duì)非法個(gè)體進(jìn)行合法性修復(fù)，如： 切點(diǎn) 非法個(gè)體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 單切點(diǎn)交叉算子合法性修復(fù)示意圖單切點(diǎn)交叉算子的 JAVA實(shí)現(xiàn)：public void SiglePointPTcrossover(int popSize, int cityNum, double pxover) {int x。y = (int) (() * popSize)。}}public void SiglePointPTexecuteCrossover(int x, int y, int location,int cityNum) {for (int i = location。(y).get(i).setSequece(temp)。 (x).get(j).getSequece() == .get(x).get(i).getSequece())(x).get(j).setSequece((y).get(i).getSequece())。amp。普通循環(huán)交叉算子 為克服單切點(diǎn)、雙切點(diǎn)交叉帶來(lái)的子代個(gè)體解的不合法性，我們采用循環(huán)交叉的方法，該交叉算子的思想在上文中已做詳細(xì)介紹，這里不做贅述。int pop = (int) (popSize * pxover / 2)。// x y 兩個(gè)體執(zhí)行交叉pop。 i cityNum。 //實(shí)現(xiàn)循環(huán)交叉的主體類(lèi)對(duì)象int[] result1 = ()。 i++) {(x).get(i).setSequece(result1[i])。例如：A1=（7，2，0，1，8，5 ，9，4，3，6）A2=（1，2，4，0，5，6 ，9，3，7，6） 相同部分：（*，2，*, * ，* , * , 9 , *, * ，6） 不同部分：S （0， 1，3，4，5，7，8） 取佳點(diǎn) P（， ，）從小到大排序得到 T (， ，) T 相對(duì)于 S，得到一個(gè)新的 S 排列 S（ 1，0，7，5， 4，3，8）與 A1 和 A2 相同部分合并得交叉后的新個(gè)體：（1，2，0，7，5，4，9，3，8，6） 佳點(diǎn)集交叉操作有效的避免了普通交叉算子因交叉產(chǎn)生的非法個(gè)體，又避免了因問(wèn)題規(guī)模的擴(kuò)大，使算法性能的下降。 i++)if ((x).get(i).getSequece() != (y).get(i).getSequece()) // 個(gè)體x和個(gè)體y 中對(duì)應(yīng)位基因不同dimension++。 i cityNum。diffItem++。 // 用于交叉函數(shù)的交叉點(diǎn)，運(yùn)用佳點(diǎn)集交叉for (int k = 0。 j++)if (temp[j] == k) {double item = temp[k]。diff[k] = diff[j]。while (tempDimension 0) {if ((x).get(tempi).getSequece() == 1) // 當(dāng)為不同的基因片段時(shí) {(x).get(tempi).setSequece((int) diff[dimension tempDimension])。temp = gp(y, dimension)。 j dimension。item = diff[k]。tempi = 0。}}private double[] gp(int individual, int dimension) {double[] temp = new double[dimension]。for (int i = 0。if (temp[i] 0)temp[i] = 1 + temp[i]。(temp1)。 j dimension。而對(duì)于順序?qū)崝?shù)編碼，就是在同一個(gè)個(gè)體的基因中，隨機(jī)選取另一個(gè)基因交換位置，如：變異算子的 JAVA 實(shí)現(xiàn)：public void mutate(int popSize, int cityNum, double pmultation) {double random。for (int i = 0。temp2 = (int) (() * cityNum)。}}}4．2．7 停止準(zhǔn)則 遺傳算法中的停止準(zhǔn)則一般是設(shè)定最大代數(shù)的方式，最大代數(shù)常設(shè)為 popsize，本文采用，最大代數(shù)與收斂情況相結(jié)合的方式來(lái)設(shè)計(jì)停止準(zhǔn)則，判斷停止準(zhǔn)則的 JAVA代碼：if ((result)) // 判斷2022代內(nèi)的最優(yōu)解是否相同，相同則結(jié)束，不同則看下一代break。佳點(diǎn)集的遺傳算法較普通遺傳算法不僅更穩(wěn)定，而且所得到的解更接近于最優(yōu)解?？?結(jié)本文對(duì)佳點(diǎn)集遺傳算法和普通遺傳算法最經(jīng)常使用的三種交叉算子進(jìn)行了詳盡的分析并予以實(shí)現(xiàn),說(shuō)明了佳點(diǎn)集遺傳算法較普通遺傳算法不僅提高了求解的速度，而且有效的避免了“早熟”現(xiàn)象。致 謝本課題的研究和論文撰寫(xiě)得到了我的導(dǎo)師趙靖的精心指導(dǎo)和幫助，在此謹(jǐn)對(duì)趙老師表示由衷的感謝和深深的敬意，趙老師開(kāi)闊的眼界，敏捷的思維、好學(xué)的精神，以及嚴(yán)謹(jǐn)?shù)闹螌W(xué)態(tài)度和一絲不茍的工作作風(fēng)，而更為重要的是，在做畢業(yè)設(shè)計(jì)的學(xué)習(xí)生活中，我向老師學(xué)到了認(rèn)真、誠(chéng)實(shí)、謙虛的做