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