智能信息處理實(shí)驗(yàn)報(bào)告

1、智能信息處理實(shí)驗(yàn)報(bào)告一、實(shí)驗(yàn)?zāi)康?) 掌握遺傳算法的基本原理和程序流程。2) 理解TSP問題的基本概念。3) 能利用遺傳算法求解TSP問題。二、實(shí)驗(yàn)環(huán)境與設(shè)備實(shí)驗(yàn)由1個(gè)學(xué)生獨(dú)立完成，實(shí)驗(yàn)環(huán)境：筆記本電腦（Eclipse /Android Studio IDE）。三、預(yù)備知識(shí)1、TSP問題基本概念TSP問題即旅行商問題（Traveling Salesperson Problem）。該問題給定n個(gè)城市和兩兩城市之間的距離，要求確定一條經(jīng)過各城市當(dāng)且僅當(dāng)一次的最短路線。其圖論描述為：給定圖G=(V, A)，其中V為頂點(diǎn)集，A為各頂點(diǎn)相互連接組成的邊集，已知各頂點(diǎn)間的連接距離，要求確定一條長度最短的H

2、amilton回路，即遍歷所有頂點(diǎn)當(dāng)且僅當(dāng)一次的最短回路。2、遺傳算法的基本原理遺傳算法是一類隨機(jī)優(yōu)化算法，但它不是簡單的隨機(jī)比較搜索，而是通過對(duì)染色體的評(píng)價(jià)和對(duì)染色體中基因的作用，有效地利用已有信息來指導(dǎo)搜索有希望改善優(yōu)化質(zhì)量的狀態(tài)。標(biāo)準(zhǔn)遺傳算法主要步驟可描述如下： 隨機(jī)產(chǎn)生一組初始個(gè)體構(gòu)成初始種群。 計(jì)算每一個(gè)體的適配值（fitness value，也稱為適應(yīng)度）。適應(yīng)度值是對(duì)染色體(個(gè)體)進(jìn)行評(píng)價(jià)的一種指標(biāo)，是GA進(jìn)行優(yōu)化所用的主要信息，它與個(gè)體的目標(biāo)值存在一種對(duì)應(yīng)關(guān)系。 判斷算法收斂準(zhǔn)則是否滿足，若滿足，則輸出搜索結(jié)果；否則執(zhí)行以下步驟。 根據(jù)適應(yīng)度值大小以一定方式執(zhí)行復(fù)制操作（也稱為

3、選擇操作）。 按交叉概率pc執(zhí)行交叉操作。 按變異概率pm執(zhí)行變異操作。 返回步驟。標(biāo)準(zhǔn)遺傳算法流程圖下圖所示。NN計(jì)算各個(gè)體的適配值（適應(yīng)度）算法收斂準(zhǔn)則滿足？Yrandom0,1<Pc?復(fù)制（選擇）輸出搜索結(jié)果交叉Yrandom0,1<Pm?變異N隨機(jī)產(chǎn)生初始種群Y圖2.1 標(biāo)準(zhǔn)遺傳算法流程圖四、實(shí)驗(yàn)內(nèi)容1、設(shè)計(jì)算法的編碼方式路徑編碼是描述TSP解的最常用的一種策略。所謂路徑編碼，即直接采用城市在路徑中的位置來構(gòu)造用于優(yōu)化的狀態(tài)。例如：設(shè)九城市TSP問題的路徑為5-4-1-7-9-8-6-2-3，對(duì)應(yīng)的路徑編碼為：(5 4 1 7 9 8 6 2 3)。這種編碼形式自然直觀，易

4、于加入啟發(fā)式信息，也有利于優(yōu)化操作的設(shè)計(jì)。2、設(shè)計(jì)遺傳算法的適應(yīng)度函數(shù)對(duì)個(gè)體i，計(jì)算與路徑編碼相對(duì)應(yīng)的距離，設(shè)為di。顯然距離值di越大，適應(yīng)度值應(yīng)越小。因此，適應(yīng)度函數(shù)可定義為：。這里我們?cè)谒惴ǔ绦蛑袀€(gè)體適應(yīng)度函數(shù)定義為：tempfk = 10.0 / fitnessk。3、設(shè)計(jì)遺傳算法的選擇操作選擇是用來確定交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。它是基于適應(yīng)度值計(jì)算基礎(chǔ)上進(jìn)行的。在實(shí)現(xiàn)算法的程序中，挑選種群中適應(yīng)度最高的個(gè)體。挑選函數(shù)為selectBestGh()。挑選策略為賭輪選擇策略。函數(shù)實(shí)現(xiàn)： public void select() int k, i, selectId; f

5、loat ran1; for (k = 1; k < scale; k+) ran1 = (float) (random.nextInt(65535) % 1000 / 1000.0); / 產(chǎn)生方式 for (i = 0; i < scale; i+) if (ran1 <= Pii) break; selectId = i; / System.out.println("選中" + selectId); copyGh(k, selectId); 在被選集中，每個(gè)個(gè)體都有一個(gè)選擇概率，這個(gè)概率由種群中個(gè)體的適應(yīng)度及其分布決定。若某個(gè)個(gè)體i，其適應(yīng)度為fi，

6、則其被選取的概率表示為：。函數(shù)實(shí)現(xiàn)： 計(jì)算種群中各個(gè)個(gè)體的累積概率，前提是已經(jīng)計(jì)算出各個(gè)個(gè)體的適應(yīng)度fitnessmax，作為賭輪選擇策略一部分，Pimax void countRate() int k; double sumFitness = 0;/ 適應(yīng)度總和 double tempf = new doublescale; for (k = 0; k < scale; k+) tempfk = 10.0 / fitnessk; sumFitness += tempfk; Pi0 = (float) (tempf0 / sumFitness); for (k = 1; k < s

7、cale; k+) Pik = (float) (tempfk / sumFitness + Pik - 1); 為了選擇交叉?zhèn)€體，需要進(jìn)行多輪選擇，每一輪產(chǎn)生一個(gè)0, 1均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來確定被選個(gè)體。4、設(shè)計(jì)遺傳算法的交叉操作在選擇操作的基礎(chǔ)上，根據(jù)一定的概率（稱為交叉概率）進(jìn)行交叉操作。交叉的目的是為了能夠在下一代產(chǎn)生新的個(gè)體，它是遺傳算法獲取新的優(yōu)良個(gè)體的最重要的手段。交叉操作中，把兩個(gè)父個(gè)體的部分結(jié)構(gòu)進(jìn)行替換重組，生成新個(gè)體。根據(jù)個(gè)體編碼方法的不同可以有不同的算法。TSP問題中，交叉操作可設(shè)計(jì)如下：遺傳算法交叉操作的函數(shù)實(shí)現(xiàn)： void OXCross(int k1

8、, int k2) int i, j, k, flag; int ran1, ran2, temp; int Gh1 = new intcityNum; int Gh2 = new intcityNum; ran1 = random.nextInt(65535) % cityNum; ran2 = random.nextInt(65535) % cityNum; while (ran1 = ran2) ran2 = random.nextInt(65535) % cityNum; if (ran1 > ran2) / 確保ran1<ran2 temp = ran1; ran1 =

9、ran2; ran2 = temp; flag = ran2 - ran1 + 1;/ 刪除重復(fù)基因前染色體長度 for (i = 0, j = ran1; i < flag; i+, j+) Gh1i = newPopulationk2j; Gh2i = newPopulationk1j; / 已近賦值i=ran2-ran1個(gè)基因 for (k = 0, j = flag; j < cityNum;) / 染色體長度 Gh1j = newPopulationk1k+; for (i = 0; i < flag; i+) if (Gh1i = Gh1j) break; if

10、(i = flag) j+; for (k = 0, j = flag; j < cityNum;)/ 染色體長度 Gh2j = newPopulationk2k+; for (i = 0; i < flag; i+) if (Gh2i = Gh2j) break; if (i = flag) j+; for (i = 0; i < cityNum; i+) newPopulationk1i = Gh1i; / 交叉完畢放回種群 newPopulationk2i = Gh2i; 遺傳算法中并不是所有被選擇的個(gè)體，都要進(jìn)行交叉操作。交叉概率用于控制交叉操作的頻率。概率太大時(shí)，種

11、群中串的更新很快，使高適應(yīng)度值的個(gè)體很快被破壞掉。概率太小時(shí)，交叉操作很少進(jìn)行，使搜索停滯不前。5、設(shè)計(jì)遺傳算法的變異操作同交叉操作一樣，并不是所有被選擇的個(gè)體，都要進(jìn)行變異操作。變異概率是加大種群多樣性的重要因素，但是概率太小就很難產(chǎn)生新個(gè)體，概率太大會(huì)使GA成為隨機(jī)搜索?；诙M(jìn)制編碼的GA中，通常一個(gè)較低的變異率足以防止整個(gè)群體中任一位置的基因一直保持不變。TSP問題中，變異操作可設(shè)計(jì)如下：利用上面實(shí)現(xiàn)的交叉操作，根據(jù)變異運(yùn)算示意圖，定義進(jìn)化函數(shù)： public void Evolution() int k; selectBestGh(); / 根據(jù)遺傳算法的特點(diǎn)，挑選某代種群中適應(yīng)度最

12、高的個(gè)體 select(); /挑選下一代的個(gè)體（賭輪選擇策略） float r; / 交叉方法 for (k = 0; k < scale; k = k + 2) r = random.nextFloat();/ /產(chǎn)生概率 if (r < Pc) OXCross1(k, k + 1); else r = random.nextFloat();/ /產(chǎn)生概率 / 變異 if (r < Pm) OnCVariation(k); r = random.nextFloat();/ /產(chǎn)生概率 / 變異 if (r < Pm) OnCVariation(k + 1); 6、編

13、寫基于遺傳算法的TSP問題求解程序1) 采用遺傳算法解決27城市TSP問題。27個(gè)城市的坐標(biāo)為：41 94；37 84；53 67；25 62；7 64；2 99；68 58；71 44；54 62；83 69；64 60；18 54；22 60；83 46；91 38；25 38；24 42；58 69；71 71；74 78；87 76；18 40；13 40；82 7；62 32；58 35；45 21。這27個(gè)城市的坐標(biāo)數(shù)據(jù)位于文件cityLocations.txt文件中，在程序中對(duì)其讀取并進(jìn)行處理.算法的關(guān)鍵函數(shù)及參數(shù)說明（Java）：算法的全部邏輯位于GATest.java文件中。

14、 public GATest(int s, int n, int g, float c, float m) /構(gòu)造函數(shù) scale = s; /種群規(guī)模 cityNum = n; /城市數(shù)量 MAX_GEN = g; /繁衍代數(shù) Pc = c; /交叉概率 Pm = m; /變異概率程序的入口函數(shù)及初始參數(shù)： public static void main(String args) throws IOException GATest gaTest = new GATest(50, 27, 3000, 0.8f, 0.9f); gaTest.init("C:/Users/HaohaoC

15、hang/Desktop/data/cityLocations.txt"); /初始化數(shù)據(jù) gaTest.solve(); /執(zhí)行算法 算法運(yùn)行結(jié)果：=最佳長度出現(xiàn)所繁衍的代數(shù)：2788最佳長度：143最佳路徑：11-22-21-16-15-26-25-24-23-14-13-7-6-10-8-2-17-18-9-20-19-0-1-5-4-12-3.Eclipse運(yùn)行結(jié)果圖（1）Eclipse運(yùn)行結(jié)果圖（2）2）利用實(shí)驗(yàn)數(shù)據(jù)，分析討論以下問題。a) 在其他條件不變的情況下，只改變變異概率的取值，對(duì)求解結(jié)果有何影響？實(shí)驗(yàn)次數(shù)：10種群規(guī)模：27交叉概率：0.8試驗(yàn)結(jié)果：變異概率最佳長度最佳路徑0.0010.010.10.30.40.50.60.70.90.95b) 在其他條件不變的情況下，只改變交叉概率的取值，對(duì)求解結(jié)果有何影響？c) 在其他條件不變的情況下，只改變種群規(guī)模的取值，對(duì)求解結(jié)果有何影響？d) 在其他條件不變的情況下，采用不同的算法終止