【正文】 和 Rosenberg 就提出了生物遺傳算法(GA) 的初步思想，1975年由美國 Michigan 大學(xué)的 John Holland 的出色工作奠定了遺傳學(xué)算法的理論基礎(chǔ)，遺傳變異和優(yōu)勝劣汰現(xiàn)象的優(yōu)化搜索算法付諸了實際應(yīng)用，這也標(biāo)志著遺傳算法的誕生。與此同時 Holland 還給出了一個自適應(yīng)的規(guī)則學(xué)習(xí)系統(tǒng)，并于 1980 年成功地實現(xiàn)了這一學(xué)習(xí)系統(tǒng)，Holland 及其學(xué)生的研究成果使得人們開始看到了 GA 的應(yīng)用價值。也正是他們的研究使得更多的人把目光投向了遺傳算法，1985 年召開了第一屆 GA 國際會議，至此以后每兩年召開一次。1989 年. Goldberg 總結(jié)了遺傳算法的主要成果，全面論述了遺傳學(xué)的基本原理極其應(yīng)用，奠定了現(xiàn)代 GA 的科學(xué)基礎(chǔ)。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不僅它的應(yīng)用領(lǐng)域擴大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。遺傳算法的應(yīng)用研究已從初期的組合優(yōu)化求解擴展到了許多更新、更工程化的應(yīng)用方面。D. H. Ackley 等提出了隨機迭代遺傳爬山法（Stochastic Iterated Geic Hillclimbing，SIGH ）采用了一種復(fù)雜的概率選舉機制，此機制中由 m 個“ 投票者” 來共同決定新個體的值（m 表示群體的大?。?。H. Bersini 和 G. Seront 將遺傳算法與單一方法（simplex method）結(jié)合起來，形成了一種叫單一操作的多親交叉算子（simplex crossover） ，該算子在根據(jù)兩個母體以及一個額外的個體產(chǎn)生新個體，事實上他的交叉結(jié)果與對三個個體用選舉交叉產(chǎn)生的結(jié)果一致。 近年來，國內(nèi)也有不少的專家和學(xué)者對遺傳算法的交叉算子進(jìn)行改進(jìn)。該方法以粗粒度并行遺傳算法為基本框架，在染色體群體中識別出可能的基因塊，然后用基因塊作為新的基因單位對染色體重新編碼，產(chǎn)生長度較短的染色體，在用重新編碼的染色體群體作為下一輪以相同方式演化的初始群體。總之人們對遺傳算法的研究主要可以概括為以下三個方面：（1（ 遺傳算法搜索在進(jìn)化到一定的程度就往往會使得種群的適應(yīng)度趨向于相同，這樣似的種群間的概率變的非常接近，這時的選擇和復(fù)制策略接近于純隨機的抽樣過程，使得搜索的收斂速度比較慢，針對這一問題，人們提出了不同的選擇和復(fù)制策略。主要結(jié)果是典型的 GA 不會收斂到全局最優(yōu)，對于保留精英( elitism selection )的選擇策略，GA 能收斂到全局最優(yōu)。（3（ 遺傳算法收斂性能的研究，普通的遺傳算法搜索的局部性而往往不能全局最優(yōu)，針對這一問題人們采用設(shè)計合適的交叉算子和變異算子來解決。關(guān)于遺傳算法收斂性能的研究，到目前為止還沒有肯定的結(jié)論哪一種方法的遺傳算法性能絕對最優(yōu)，對于遺傳算法的性能往往是問題不同，得到的結(jié)論也不同。該集合內(nèi)個體數(shù)稱為群體的大小。 種群大小( population size): 種群中個體數(shù)目稱為群體大小。適應(yīng)度函數(shù)（fitness function）：為了體現(xiàn)染色體的適應(yīng)能力，引入了對問題中的每一個染色體都能進(jìn)行度量的函數(shù)，叫適應(yīng)度函數(shù)，適應(yīng)度函數(shù)是計算個體在群體中被使用的概率。交叉率：交叉運算的染色體個數(shù)占全體染色體總數(shù)的比例，取值范圍一般為~。1．2．2 遺傳算法基本原理遺傳算法 [10]GA 把問題的解表示成“ 染色體”，在算法中也即是以二進(jìn)制編碼或?qū)崝?shù)編碼的串。然后，把這些假設(shè)解置于問題的“環(huán)境” 中，設(shè)定相應(yīng)的適應(yīng)度函數(shù)，并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的“染色體” 進(jìn)行復(fù)制，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代“染色體 ” 群。1．2．3 遺傳算法的特點 遺傳算法 GA 利用了生物進(jìn)化和遺傳的思想，所以它有許多與傳統(tǒng)的優(yōu)化方法不同的特點(1) GA 遺傳算法是對問題參數(shù)集的編碼(染色體群)作為運算對象。(2) GA 是從問題的集合開始進(jìn)行群體搜索，而不是從某個解開始進(jìn)行單點搜索。(3) GA 的適應(yīng)性強，僅用適應(yīng)度函數(shù)值來引導(dǎo)搜索，而不需要問題領(lǐng)域的先驗知識或其它輔助信息，從而對問題的依賴性較小。采用概率的變遷規(guī)則來指導(dǎo)搜索方向，引導(dǎo)搜索過程朝著搜索空間的更優(yōu)化的解區(qū)域移動。2 普通遺傳算 法2．1 普通遺傳遺傳算法思想　(1) 初始化群體 。(3) 按由個體適應(yīng)度值所決定的某個規(guī)則選擇將進(jìn)入下一代的個體。　(5) 按概率 Pm 進(jìn)行變異操作。(7) 輸出種群中適應(yīng)度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。最常用的選擇策略是賭輪選擇策略。這里選擇概率的計算公式：P(xi)= 其中 f 為適應(yīng)度函數(shù)，f(x i)為的適應(yīng)度。P1 和 P2 其中稱為父代染色體， C1 和 C2 稱為子代染色體。（2）雙切點交叉（doublepoint crossover ）雙切點交叉的思想是從種群中選出兩個個體 P1 和 P2，隨機地選擇兩個切點（cutting） ，交換兩個切點之間的子串，從而得到了新一代的染色體。循環(huán)交叉操作的具體步驟如下：(a) 選 P1 的第一個元素作為 C1 的第一個元素；選 P2 的第一個元素作為 C2 的第一個元素；(b) 在 P1 中找 P2 的第一個元素賦給 C1 的相對位置……重復(fù)此過程，直到 P2 上得到 P1 的第一個元素為止，稱為一個循環(huán)；(c) 對最前的基因按 P P2 基因輪替原則重復(fù)以上過程；(d) 重復(fù)以上過程，直至所有位已完成。同時使得遺傳算法保持種群的多樣性，以防止出現(xiàn)非成熟收斂。最常用的變異操作是按位交換變異，它的基本思想：對于同一個個體的基因如果發(fā)生變異，則隨機與同一個個體的另一個基因交換位置。1?itd 對于 TSP 這樣的一個典型的組合優(yōu)化問題，最為普通的一種解決辦法就是窮舉出所有可能的合法序列，然后比較距離函數(shù)，得出最優(yōu)的城市序列。即使使用運算速度為 105億次每秒的巨型計算機按窮舉搜索法計算 100 個城市的2!nTSP 問題也需要 10136年的時間，在這里還沒有考慮算法所需的巨大的存儲空間，?由此可見 TSP 問題的時空復(fù)雜度之高，這就為遺傳算法的應(yīng)用提供了機會，下面我們就來看一求解 TSP 問題的遺傳算法。這樣每一個個體對象相當(dāng)于生物體的表現(xiàn)型，而染色體就相當(dāng)于生物體的基因型，從表現(xiàn)型到基因型的映射稱為編碼。適合于背包問題、實優(yōu)化問題和指派問題，但是在另外的一些實際問題如 TSP 問題，二進(jìn)制編碼編碼長，不易計算同時不易進(jìn)行變異交叉操作，易產(chǎn)生大量非可行解，所以針對特殊的問題，可以采用不同的編碼方法。這種編碼雖然方便，但是要注意編碼的合法性檢查，并對不合法的個體進(jìn)行合法性修復(fù)。如：一染色體 X 的順序?qū)崝?shù)編碼為（2 3 1 5 4 7 6） ，解碼就是要把相鄰兩點的距離進(jìn)行求和，具體地說就是要把 2 與 3，3 與 1，1 與 5，5 與 4，4 與 7，7 與 6，6 與 2 之間的距離相加，相加的結(jié)果就是由解碼得到的路徑長度 d。本文就是采用是一種經(jīng)典的洗牌隨機生成的方法生成初始種群，設(shè)表示編碼的一維數(shù)組為 P1[n]和 P2[n],先把 P1[n]和 P2[n]按城市序號初始化為{0 ， 1，…，n1}，令 i=0，產(chǎn)生一個（n1 ）i 范圍內(nèi)的整數(shù) r，然后將 P1[n1i]賦值于 P2[i],P1[n1i]賦值給 P1[r]。如此循環(huán)直至達(dá)到所需的群體規(guī)模為止。其算法 JAVA 實現(xiàn)如下：public void init(ListCity list, int popSize, int cityNum, String fileName) {initDistance(list, fileName, cityNum)。 i popSize。// 初始化種群數(shù)組int[] num = new int[cityNum]。 j cityNum。}int temp = cityNum。 j cityNum。(i).get(j).setSequece(num[r])。temp。(i).setSelectP(0)。(i).setIsSelected(0)。目標(biāo)函數(shù)一般表示為 f(x),適應(yīng)度函數(shù)一般表示為 F（x） 。TSP 的目標(biāo)是路徑總長度為最短，路徑總長度可作為 TSP 問題的適應(yīng)度函數(shù)F（x）= f(x)= （其中 x n+1 = x1 ）???njjxD11),(計算種群適應(yīng)度的函數(shù) JAVA 實現(xiàn)：private void CalFitness(int popSize, int cityNum) {for (int i = 0。 i++) {double len2 = (i).getFitness()。 j cityNum 1。}len2 += [(i).get(0).getSequece()][.get(i).get(cityNum 1).getSequece()]。}}4．2．4 選擇算子 在每一代的運算過程中，個體被選中的概率與其在群體中的相對適應(yīng)度成正比，即采用賭輪選擇機制。for (int i = 0。 i++)// 計算所有種群的適應(yīng)度之和sum += (i).getFitness()。 i popSize。}4．2．5 交叉算子普通單切點、雙切點交叉算子由單切點交叉算子的思想，隨機選取個體 AA2，然后隨機地選取一基因位交換兩個體中該基因位之后的基因，而雙切點交叉算子是在隨機選取的兩個個體中隨機的選取兩個基因位，然后把兩基因位之間的基因位相互交換位置，由于我們 TSP 問題采用的是順序?qū)崝?shù)編碼，產(chǎn)生