【文章內(nèi)容簡介】 概率：使用公式21計算個體的選擇概率 個體的期望概率：個體的期望概率=(個體選擇概率*種群大小) 個體的變異概率：因為算法中的采用的增加較優(yōu)個體的變異概率的策略，因此不同的個體有不同的變異概率（較優(yōu)個體有更大的變異概率） 是否被選擇：boolean類型，為true表示該個體被選擇，進入下一代，表示false被淘汰，是否被淘汰由期望概率決定。圖31個體的數(shù)據(jù)類型 運行參數(shù)設置 在程序運行前需要設置下面運行參數(shù)：種群大?。悍N群個體的數(shù)目，一般取30100。最大迭代次數(shù)：本算法的最大迭迭代次數(shù)，與最大相同解次數(shù)一起決定算法是否停止。范圍一般取600060000。最大相同解次數(shù)：如果算法迭代了最大相同解次數(shù)都沒有找到更好的解，說明種群的進化趨勢已經(jīng)減弱到一定閥值，種群已經(jīng)趨于成熟，此時算法應該停止。一般取6006000。交叉率：發(fā)生交叉運算的個體個數(shù)占全體個體總數(shù)的比例，~。初始變異率：發(fā)生變異的基因位數(shù)所占全體個體的基因總位數(shù)的比例，~。算法采用增大較優(yōu)個體的變異概率，因此這里設置的只是個體的初始變異率。最優(yōu)種群大?。阂驗楸舅惴ú捎昧俗顑?yōu)保存策略，將當前最優(yōu)個體和前面數(shù)次迭代中的種群最優(yōu)個體保存在最優(yōu)種群中。最優(yōu)種群大小一般設置為種群大小的二分之一。采用的種群初始化策略為隨機初始化。例如求解n個城市的TSP，隨機初始化的方法如下： 對n個城市使用0(n1)的順序?qū)崝?shù)編碼 生成一個訪問順序隨機的訪問序列的關鍵代碼如下： // 使所有的個體都是從第一個城市出發(fā), //0表示第一個城市，1表示第二個城市,依次類推） population[i].citys[0] = 0。 int[] num = new int[cityNum]。 for (int j = 1。 j cityNum。 j++) {//生成1n1之間的種子 num[j] = j。 } int temp = cityNum。 for (int j = 1。 j cityNum。 j++) { // 產(chǎn)生0到temp間的隨機整數(shù),不包括temp int r = (int) (() * (temp 1) + 1)。 population[i].citys[j] = num[r]。 num[r] = num[temp 1]。 temp。 }若種群大小為M，則循環(huán)執(zhí)行操作2 M次就可以生成M個個體，再由這M個個體組成種群就完成了種群的隨機初始。 適應度函數(shù)算法的適應度就是個體的位串表示的環(huán)路的總距離，計算適應度的函數(shù)如下：public void calFitness() { = 0。 // 計算節(jié)點0n1之間的距離之和 for (int j = 0。 j cityNum 1。 j++) { += distance[[j]][[j + 1]]。 } // 再加上節(jié)點n1和節(jié)點0之間的距離 +=distance[[0]][[cityNum 1]]。 } 選擇操作本遺傳算法的選擇操作采用了最優(yōu)保存策略，有利于加快收斂，策略的實現(xiàn)如下： 定義一個最優(yōu)種群，最優(yōu)種群初始時和初始種群一樣。// 由前面各次迭代取得的最優(yōu)解組成的種群，最前面一個是當前最優(yōu)解private Genotype[] bestPopualtion = new Genotype[popSize]。把當前最優(yōu)解復制到最優(yōu)種群的第一個個體，再分別把前面popSize1次迭代產(chǎn)生的最優(yōu)解復制到最優(yōu)種群的其它個體，生成最優(yōu)種群。在做選擇操作前需要先計算種群中每個個體的選擇概率、期望概率，關鍵代碼如下： public void calProbality() { = 0。 if (fitnessSum != 0) { = (double) / fitnessSum。 // 計算選擇概率 } = 0。 = (double) ( * popSize)。 // 計算期望概率 = false。 } 其中fitnessSum是種群中所有個體的適應度之和。 計算種群適應度之和的代碼： private void calfitnessSum() { fitnessSum = 0。 for (int i = 0。 i popSize。 i++) { fitnessSum += population[i].fitness。 } }根據(jù)期望概率淘汰掉當前種群中部分適應度較差的個體： private void calIsSelected() { for (int i = 0。 i popSize。 i++) { double random = ()+。 if (population[i].expectP random) { // 根據(jù)期望概率選擇優(yōu)良個體 population[i].isSelected = true。 } } }其中沒有被選擇(isSelected=false)的個體就是被淘汰掉的個體。從最優(yōu)種群中選擇隨機選擇一部分個體（但是保證當前最優(yōu)的個體一定被選擇）來覆蓋當前種群中被淘汰掉的個體，并且增大這些局部最優(yōu)個體的變異概率。這樣既可以增加種群的多樣性，提高解的質(zhì)量又可以有效加快解收斂，因為全局最優(yōu)解和局部最優(yōu)解相似程度高，很可能由局部最優(yōu)解變異產(chǎn)生。實現(xiàn)代碼如下： public void copy() { int count = 0。 for (int i = 0。 i popSize。 i++) { if (!population[i].isSelected) { if (count == 0) { // 先用當前最優(yōu)解填充 for (int j = 1。 j cityNum。 j++) { population[i].citys[j]=bestPopualtion[0].citys[j]。 } population[i].pmultation = 1。 // 增加變異概率 } else { int index = (int) (() * (popSize))。 for (int j = 1。 j cityNum。 j++) { population[i].citys[j]=bestPopualtion[index].citys[j]。 } population[i].pmultation = 。 // 增加變異概率 } count++。 } } }本算法采用雙切點交叉算子。首先從種群中隨機選擇兩個個體進行配對，然后在生成兩個0cityNum（城市個數(shù)）之間（不包括cityNum）的隨機數(shù)，將這兩個隨機數(shù)做為位串上的兩個切點位置，再交換兩個切點之間的基因。這里要注意的是交換基因可能會產(chǎn)生非法個體，因此還要進行合法性修復。例如：C1=0 4 2 1 0 6 7 6C2=4 3 2 3 1 5 7 5P1= 0 4 2 | 3 1 5 | 7 6P2= 4 3 2 | 1 0 6 | 7 5 隨機生成切點 非法個體 映射關系： 31 10 56 修復后的個體P1= 3 4 2 1 0 6 7 5P2= 4 0 2 3 1 5 7 6 圖32雙切點交叉Java實現(xiàn)雙切點交叉的代碼如下： 交叉主體函數(shù) public void crossover() { int x = 1。 int y = 1。 // 計算有多少個個體會發(fā)生交叉 int pop = (int) (popSize * pxover / 2)。 while (pop 0) { // 進行交叉配對 // 生成0popSize的隨機數(shù),包括0，不包括popSize x = (int) (() * popSize)。 while (true) { y = (int) (() * popSize)。 // 防止自己與自己交叉 if (y != x)break。 } // x,y兩個體執(zhí)行雙切點交叉 doublePointCrossover(x, y)。 pop。 } } 雙切點交叉函數(shù)private void doublePointCrossover(int x, int y) { // 第一個切點在0到cityNum1之間隨機選擇 int location1 = (int) (() * (cityNum 1)) + 1。 // 第二個切點在location1+1到cityNum之間隨機選擇 int location2 = (int) (() * (cityNum location1 1))+ location1 + 1。 // 交換兩個個體切點之間的城市序列 for (int i = location1。 i location2。 i++) { int tempX = population[x].citys[i]。 int tempY = population[y].citys[i]。 population[x].citys[i] = tempY。 population[y].citys[i] = tempX。 // 修復個體X for (int j = 1。 j cityNum。 j++) { if (j != i amp。amp。 population[x].citys[j] == population[x].citys[i]) { population[x].citys[j] = tempX。 break。 } } // 修復個體Y for (int k = 1。 k cityNum。 k++) { if (k != i amp。amp。 population[y].citys[k] == population[y].citys[i]) { population[y].citys[k] = tempY。 break。 } } } }變異簡單的說就是個體位串內(nèi)基因的位置發(fā)生改變，種群的個體有一定的可能性（變異概率）發(fā)生變異。本算法的變異操作由交換變異、倒序變異和插入變異三種變異算子混合?；旌系姆椒ㄊ?，每次執(zhí)行變異操作之前，先生成02的隨機數(shù)，然后根據(jù)生成的隨機數(shù)來選擇此次使用哪種變異方式。交換變異，在位串中隨機取兩個位置，交換這兩個位置上的基因，例如：Px= [ 0 1 2 3 4 5 6 7]，隨機取兩個位置1和4（基因位從0開始），交換位置1和4上的基因后得：Px=[ 0 4 2 3 1 5 6 7]倒序變異，在位串中隨機取兩個位置，反轉(zhuǎn)這兩個位置之間的基因，例如：Px= [ 0 1 2 3 4 5 6 7]，隨機取兩個位置1和4（基因位從0開始），倒序位置1到位置4之間的基因后得：Px=[ 0 4 3 2 1 5 6 7]插入變異，在位串中隨機取兩個位置，將后面那個位置上的基因插入到前面那個位置。例如：Px= [ 0 1 2 3 4 5 6 7]，隨機取兩個位置1和4（基因位從0開始），將位置4上的基因插入到位置1后得：Px= [ 0 4 1 2 3 5 6 7]Java實現(xiàn)代碼如下： 變異主體函數(shù)public void mutate() { double random。 int loc1,loc2。 for (int i = 0。 i popSize。 i++) { random = ()。 if (random population[i].pmultation) { loc1 = (int) (() * (cityNum 1)) + 1。 loc2 = (int) (() * (cityNum 1)) + 1。 if (loc1 loc2) { int loc = loc2。 loc2 = loc1。 loc1 = loc。 } // 采用多種變異方式混合 int select = (int) (() * 3)。 switch (select) {case 0: // 采用交換的方式變異 exchangeMutate(i, loc1, loc2)。 break。 case 1: // 采用倒序的方式變異 backMutate(i, loc1, loc2)。 break。 case 2: // 采用插入的方式變異 insertMutate(i, loc1, loc2)。 break。 } } } } 交換變異算子：private void exchangeMutate(int index, int loc1, int loc2) { int temp =