生物信息學(xué)課程設(shè)計(jì)--生物信息遺傳算法編程實(shí)現(xiàn)

1、<p>　　生物信息學(xué)課程設(shè)計(jì)報(bào)告</p><p><b>　　（算法編程實(shí)現(xiàn)類）</b></p><p>　　副題：生物信息遺傳算法編程實(shí)現(xiàn)</p><p>　　院 系 部 門： </p><p>　　學(xué) 生 學(xué) 號(hào)： </p><p>　　學(xué) 生 姓 名

2、： </p><p>　　指 導(dǎo) 教 師： </p><p><b>　　2013年12月</b></p><p><b>　　目錄</b></p><p>　　第一部分 遺傳算法研究背景、特點(diǎn)與發(fā)展1</p><p>　　1.1 遺傳算法研

3、究背景1</p><p>　　1.2 遺傳算法特點(diǎn)2</p><p>　　1.3 遺傳算法發(fā)展2</p><p>　　1.4 本算法編程實(shí)現(xiàn)內(nèi)容和方案2</p><p>　　第二部分 算法分析與程序流程圖設(shè)計(jì)3</p><p>　　2.1 基于問(wèn)題的描述3</p><p>　

4、　2.2 基于問(wèn)題的知識(shí)表示3</p><p>　　2.2.1 狀態(tài)表示3</p><p>　　2.2.2 控制參數(shù)3</p><p>　　2.2.3算法描述3</p><p>　　2.3 基于問(wèn)題的java算法分析4</p><p>　　2.4 算法流程圖5</p><p>　　第

5、三部分 實(shí)現(xiàn)設(shè)計(jì)語(yǔ)言選擇與算法編程實(shí)現(xiàn)5</p><p>　　3.1 java實(shí)現(xiàn)算法5</p><p>　　第四部分 程序測(cè)試與結(jié)果分析15</p><p>　　4.1 測(cè)試結(jié)果15</p><p>　　4.1.1 用戶界面15</p><p>　　4.1.2 輸入數(shù)據(jù)15</p>&l

6、t;p>　　4.1.3 輸出結(jié)果15</p><p>　　4.2結(jié)果分析16</p><p>　　第五部分 總結(jié)與心得體會(huì)16</p><p>　　第六部分 參考文獻(xiàn)17</p><p>　　第一部分 遺傳算法研究背景、特點(diǎn)與發(fā)展</p><p>　　1.1 遺傳算法研究背景</p>

7、<p>　　眾所周知，在人工智能領(lǐng)域中，有不少問(wèn)題需要在復(fù)雜而龐大的搜索空間中尋找最優(yōu)解或準(zhǔn)優(yōu)解。像貨朗擔(dān)問(wèn)題和規(guī)劃問(wèn)題等組合優(yōu)化問(wèn)題就是典型的例子。在求解此類問(wèn)題時(shí)，若不能利用問(wèn)題的固有知識(shí)來(lái)縮小搜索空間則會(huì)產(chǎn)生搜索的組合爆炸。因此，研究能在搜索過(guò)程中自動(dòng)獲得和積累有關(guān)搜索空間的知識(shí)，并能自適應(yīng)地控制搜索過(guò)程，從而得到最優(yōu)解或準(zhǔn)有解的通用搜索算法一直是令人矚目的課題。遺傳算法就是在這種背景下產(chǎn)生并經(jīng)實(shí)踐證明特別有效的算法。

8、</p><p>　　1.2 遺傳算法特點(diǎn)</p><p>　　遺傳算法具有以下幾方面的特點(diǎn)：</p><p>　　(1)遺傳算法從問(wèn)題解的串集開(kāi)始搜索，而不是從單個(gè)解開(kāi)始。這是遺傳算法與傳統(tǒng)優(yōu)化算法的極大區(qū)別。傳統(tǒng)優(yōu)化算法是從單個(gè)初始值迭代求最優(yōu)解的；容易誤入局部最優(yōu)解。遺傳算法從串集開(kāi)始搜索，覆蓋面大，利于全局擇優(yōu)。</p><p>　

9、　(2)遺傳算法同時(shí)處理群體中的多個(gè)個(gè)體，即對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估，減少了陷入局部最優(yōu)解的風(fēng)險(xiǎn)，同時(shí)算法本身易于實(shí)現(xiàn)并行化。</p><p>　　(3)遺傳算法基本上不用搜索空間的知識(shí)或其它輔助信息，而僅用適應(yīng)度函數(shù)值來(lái)評(píng)估個(gè)體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。</p><p>　　(4)遺傳

10、算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來(lái)指導(dǎo)他的搜索方向。</p><p>　　(5)具有自組織、自適應(yīng)和自學(xué)習(xí)性。遺傳算法利用進(jìn)化過(guò)程獲得的信息自行組織搜索時(shí)，適應(yīng)度大的個(gè)體具有較高的生存概率，并獲得更適應(yīng)環(huán)境的基因結(jié)構(gòu)。</p><p>　　1.3 遺傳算法發(fā)展</p><p>　　1967年，Holland的學(xué)生J.D.Bagley在博士論文中首次提

11、出“遺傳（Genet -ic Algorithms）”一詞。此后，Holland指導(dǎo)學(xué)生完成了多篇有關(guān)遺傳算法研究的論文。1971年，R.B.Hollstien在他的博士論文中首次把遺傳算法用于函數(shù)優(yōu)化。1975年是遺傳算法研究歷史上十分重要的一年。這一年Holland出版了他的著名專著《自然系統(tǒng)和人工系統(tǒng)的自適應(yīng)》（Adaptation in Natural and Artificial Systems），這是第一本系統(tǒng)論述遺傳算法

12、的專著，因此有人把1975年作為遺傳算法的誕生年。</p><p>　　進(jìn)入90年代，遺傳算法迎來(lái)了興盛發(fā)展時(shí)期，無(wú)論是理論研究還是應(yīng)用研究都成了十分熱門的課題。尤其是遺傳算法的應(yīng)用研究顯得格外活躍，不但它的應(yīng)用領(lǐng)域擴(kuò)大，而且利用遺傳算法進(jìn)行優(yōu)化和規(guī)則學(xué)習(xí)的能力也顯著提高，同時(shí)產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。此外一些新的理論和方法在應(yīng)用研究中亦得到了迅速的發(fā)展，這些無(wú)疑均給遺傳算法增添了新的活力。遺傳算法的應(yīng)用研

13、究已從初期的組合優(yōu)化求解擴(kuò)展到了許多更新、更工程化的應(yīng)用方面。</p><p>　　1.4 本算法編程實(shí)現(xiàn)內(nèi)容和方案</p><p>　　本算法的實(shí)現(xiàn)內(nèi)容為背包問(wèn)題，具體方案見(jiàn)第二部分。</p><p>　　第二部分 算法分析與程序流程圖設(shè)計(jì)</p><p>　　2.1 基于問(wèn)題的描述</p><p>　　給定n種

14、物品和容量為C的背包。物品i的重量是wi，其價(jià)值為vi。問(wèn)應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?</p><p>　　2.2 基于問(wèn)題的知識(shí)表示</p><p>　　2.2.1 狀態(tài)表示</p><p>　　1、個(gè)體或染色體：?jiǎn)栴}的一個(gè)解，表示為n個(gè)比特的字符串，比特值為0表示不選該物品，比特值為1表示選擇該物品。</p><

15、p>　　2、基因：染色體的每一個(gè)比特。</p><p>　　3、種群：解的集合。</p><p>　　4、適應(yīng)度：衡量個(gè)體優(yōu)劣的函數(shù)值。</p><p>　　2.2.2 控制參數(shù)</p><p>　　1、種群規(guī)模：解的個(gè)數(shù)。</p><p><b>　　2、最大遺傳的代數(shù)</b></p

16、><p>　　3、交叉率：參加交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體的比例，取值范圍一般為0.4～0.99。</p><p>　　4、變異率：發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，取值范圍一般為0.0001～0.1。</p><p><b>　　2.2.3算法描述</b></p><p>　　1、在搜索空間U上定義一

17、個(gè)適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；</p><p>　　2、隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1, s2, …, sN，組成初始種群S={s1, s2, …, sN}，置代數(shù)計(jì)數(shù)器t=1；</p><p>　　3、計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f(wàn)() ；</p><p>　　4、若終止條件滿足，則取S中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法結(jié)束。&l

18、t;/p><p>　　5、按選擇概率P(xi)所決定的選中機(jī)會(huì)，每次從S中隨機(jī)選定1個(gè)個(gè)體并將其染色體復(fù)制，共做N次，然后將復(fù)制所得的N個(gè)染色體組成群體S1；</p><p>　　6、按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個(gè)染色體，配對(duì)進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；</p><p>　　7、按變異率Pm所決定的變異次數(shù)m

19、，從S2中隨機(jī)確定m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；</p><p>　　8、將群體S3作為新一代種群，即用S3代替S，t = t+1，轉(zhuǎn)步3。</p><p>　　2.3 基于問(wèn)題的java算法分析</p><p>　　產(chǎn)生初始群體在java中用Math.random()方法產(chǎn)生一個(gè)隨機(jī)數(shù)，并以次為標(biāo)準(zhǔn)產(chǎn)生一個(gè)初始群體來(lái)實(shí)現(xiàn)

20、，把數(shù)據(jù)保存到generatePopu[ ][ ]數(shù)組中。隨后分析群體中每個(gè)個(gè)體的適應(yīng)度，在此問(wèn)題中以每個(gè)個(gè)體的總價(jià)值來(lái)評(píng)估個(gè)體的適應(yīng)度，在java中用自定義的方法get_singleValue(int[] single)來(lái)實(shí)現(xiàn)，該方法可以用一個(gè)for循環(huán)來(lái)實(shí)現(xiàn)。若判斷為真取群體中適應(yīng)度最大的個(gè)體作為所求結(jié)果，算法停止。否則繼續(xù)進(jìn)行以下步驟。這時(shí)用最大遺傳代數(shù)來(lái)作為判斷條件。</p><p>　　自定義字符串復(fù)制

21、方法doubleArrayCopy(int[][] source)與singleArrayCopy(int[] source)來(lái)進(jìn)行基因與染色體的復(fù)制，這兩個(gè)方法通過(guò)一個(gè)簡(jiǎn)單的for循環(huán)就可以實(shí)現(xiàn)。</p><p>　　復(fù)制過(guò)后就是選擇與變異，變異又分為交叉和突變，與選擇概率，交叉概率和突變概率分別進(jìn)行選擇與變異操作得到新個(gè)體來(lái)組成新的群體。這只需要對(duì)上一個(gè)群體進(jìn)行遍歷操作，并與選擇概率，交叉概率和突變概率作為條

22、件操作。再對(duì)新群體的個(gè)體進(jìn)行評(píng)估，得到最優(yōu)解，如此循環(huán)直到滿足終止條件。</p><p><b>　　2.4 算法流程圖</b></p><p>　　第三部分 實(shí)現(xiàn)設(shè)計(jì)語(yǔ)言選擇與算法編程實(shí)現(xiàn)</p><p>　　3.1 java實(shí)現(xiàn)算法</p><p>　　import java.beans.PropertyChang

23、eEvent;</p><p>　　import java.beans.PropertyChangeListener;</p><p>　　import java.io.BufferedReader;</p><p>　　import java.io.File;</p><p>　　import java.io.FileInputStream

24、;</p><p>　　import java.io.FileWriter;</p><p>　　import java.io.InputStreamReader;</p><p>　　import java.io.PrintWriter;</p><p>　　import javax.swing.JFileChooser;</p>

25、;<p>　　import javax.swing.JOptionPane;</p><p>　　//遺傳算法解決0-1背包問(wèn)題</p><p>　　public class PackageByGA {</p><p>　　private int package_capacity = 0;//背包的容量</p><p>　　pr

26、ivate int goods_num = 0;//物品的個(gè)數(shù)，對(duì)應(yīng)遺傳學(xué)中個(gè)體的基因個(gè)數(shù)</p><p>　　private int[] goods_weight = null;//物品的重量</p><p>　　private double[] goods_value = null;//物品的價(jià)值 </p><p>　　private int[][] popu

27、 = null;//種群</p><p>　　public PackageByGA(){</p><p><b>　　input();</b></p><p><b>　　}</b></p><p><b>　　//輸入</b></p><p>　　pr

28、ivate void input(){</p><p>　　/*JFileChooser fc = new JFileChooser();//文件選擇對(duì)話框</p><p>　　fc.setCurrentDirectory(new File("."));//從當(dāng)前目錄選擇文件</p><p>　　//獲取輸入源，輸入源為選取的文件</p&g

29、t;<p>　　fc.addPropertyChangeListener(new PropertyChangeListener() {//注冊(cè)監(jiān)聽(tīng)器</p><p>　　public void propertyChange(PropertyChangeEvent arg0) {//屬性改變事件</p><p>　　if (arg0.getPropertyName() <

30、/p><p>　　== JFileChooser.SELECTED_FILE_CHANGED_PROPERTY) {//選擇單個(gè)文件**/y</p><p><b>　　try {</b></p><p>　　File file = (File) arg0.getNewValue();//獲取屬性的新值，轉(zhuǎn)換為文件對(duì)象</p><

31、;p><b>　　//創(chuàng)建輸入流</b></p><p>　　FileInputStream fi = new FileInputStream(file);</p><p>　　InputStreamReader ir = new InputStreamReader(fi);</p><p>　　BufferedReader br = n

32、ew BufferedReader(ir);</p><p>　　//獲取第一行數(shù)據(jù)，背包的容量</p><p>　　package_capacity = Integer.parseInt(br.readLine().trim());</p><p>　　//------------------------------</p><p>　　S

33、tring str_line = null;</p><p>　　//獲取第二行數(shù)據(jù)，物品的重量</p><p>　　str_line = br.readLine();</p><p>　　goods_weight = strArr_to_intArr(str_line.split(" "));</p><p>　　//獲

34、取第三行數(shù)據(jù)，物品的價(jià)值</p><p>　　str_line = br.readLine();</p><p>　　goods_value = strArr_to_doubleArr(str_line.split(" "));</p><p><b>　　//物品的個(gè)數(shù)</b></p><p>　　

35、goods_num = goods_value.length;</p><p><b>　　//關(guān)閉輸入流</b></p><p>　　fi.close();</p><p>　　ir.close();</p><p>　　br.close();</p><p>　　} catch (Except

36、ion ep) {//如果文件的內(nèi)容不是全為數(shù)字，則彈出對(duì)話框</p><p>　　JOptionPane.showMessageDialog(null,</p><p>　　"文件讀取異常，檢查文件內(nèi)容是否全為數(shù)字！");</p><p><b>　　}</b></p><p><b>　

37、　}</b></p><p><b>　　}</b></p><p><b>　　});</b></p><p>　　fc.showOpenDialog(null);//彈出"打開(kāi)文件"對(duì)話框</p><p><b>　　}</b></p&

38、gt;<p>　　//字符串?dāng)?shù)組轉(zhuǎn)換為整數(shù)數(shù)組</p><p>　　private int[] strArr_to_intArr(String[] strArr){</p><p>　　int size = strArr.length;</p><p>　　int[] int_arr = new int[size];</p><p&

39、gt;　　for(int i = 0; i < size; i ++){</p><p>　　int_arr[i] = Integer.valueOf(strArr[i]);</p><p>　　//Integer.valueOf()這個(gè)函數(shù)把字符串轉(zhuǎn)換為整型變量。</p><p><b>　　}</b></p><p

40、>　　return int_arr;</p><p><b>　　}</b></p><p>　　//字符串?dāng)?shù)組轉(zhuǎn)換為浮點(diǎn)數(shù)數(shù)組</p><p>　　private double[] strArr_to_doubleArr(String[] strArr){</p><p>　　int size = strArr.

41、length;</p><p>　　double[] double_arr = new double[size];</p><p>　　for(int i = 0; i < size; i ++){</p><p>　　double_arr[i] = Double.valueOf(strArr[i]);</p><p><b>

42、;　　}</b></p><p>　　return double_arr;</p><p><b>　　}</b></p><p>　　//為什么要把字符串?dāng)?shù)組——》整數(shù)數(shù)組——》浮點(diǎn)型數(shù)組？？？</p><p><b>　　//一維數(shù)組復(fù)制</b></p><p&g

43、t;　　private int[] singleArrayCopy(int[] source){</p><p>　　int size = source.length;</p><p>　　int[] des = new int[size];</p><p>　　for(int i = 0; i < size; i ++){</p><p&

44、gt;　　des[i] = source[i];</p><p><b>　　}</b></p><p>　　return des;</p><p><b>　　}</b></p><p><b>　　//二維數(shù)組復(fù)制</b></p><p>　　pri

45、vate int[][] doubleArrayCopy(int[][] source){</p><p>　　int row_num = source.length;</p><p>　　int col_num = source[0].length;</p><p>　　int[][] des = new int[row_num][col_num];</p&

46、gt;<p>　　for(int i = 0; i < row_num; i ++){</p><p>　　for(int j = 0; j < col_num; j ++){</p><p>　　des[i][j] = source[i][j];</p><p><b>　　}</b></p><

47、p><b>　　}</b></p><p>　　return des;</p><p><b>　　}</b></p><p>　　//以上兩個(gè)復(fù)制為染色體的復(fù)制</p><p><b>　　//產(chǎn)生初始種群</b></p><p>　　publi

48、c int[][] generatePopu(){</p><p>　　popu = new int[Global.POPU_NUM][goods_num];</p><p>　　for(int i = 0; i < Global.POPU_NUM; i ++){</p><p>　　for(int j = 0; j < goods_num; j ++)

49、{</p><p>　　double d = Math.random()*10;//[0,10)之間的double型數(shù)值</p><p>　　popu[i][j] = ((int)Math.round(d))%2;//1表示選擇該物品，0表示不選擇該物品</p><p><b>　　}</b></p><p>　　if(

50、get_singleWeight(popu[i]) > package_capacity){//超出背包容量</p><p><b>　　i --;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return

51、popu;</p><p><b>　　}</b></p><p>　　//計(jì)算個(gè)體的總重量</p><p>　　private int get_singleWeight(int[] single){</p><p>　　int total_weight = 0;</p><p>　　int si

52、ze = single.length;</p><p>　　for(int i = 0; i < size; i ++){</p><p>　　if(single[i] == 1){</p><p>　　total_weight += goods_weight[i];</p><p><b>　　}</b><

53、/p><p><b>　　}</b></p><p>　　return total_weight;</p><p><b>　　}</b></p><p>　　//計(jì)算個(gè)體的總價(jià)值</p><p>　　private double get_singleValue(int[] si

54、ngle){</p><p>　　int total_value = 0;</p><p>　　int size = single.length;</p><p>　　for(int i = 0; i < size; i ++){</p><p>　　if(single[i] == 1){</p><p>　　t

55、otal_value += goods_value[i];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return total_value;</p><p><b>　　}</b></p><p>

56、;　　//獲取總價(jià)值最大的個(gè)體</p><p>　　public void get_maxValue_single(int[][] popu){</p><p>　　int size = popu.length;</p><p>　　double[] fitness = new double[size];</p><p>　　for(int

57、i = 0; i < size; i ++){</p><p>　　fitness[i] = get_singleValue(popu[i]);</p><p><b>　　}</b></p><p>　　int id = 0;</p><p>　　double max_value = fitness[0];<

58、;/p><p>　　for(int j = 1; j < size; j ++){</p><p>　　if(fitness[j] > max_value){</p><p>　　max_value = fitness[j];</p><p><b>　　id = j;</b></p><p&

59、gt;<b>　　}</b></p><p><b>　　}</b></p><p>　　if(max_value > Max_value_single.max_value){</p><p>　　Max_value_single.max_value = max_value;</p><p>

60、　　int[] max_value_single = new int[goods_num];</p><p>　　for(int i = 0; i < goods_num; i ++){</p><p>　　max_value_single[i] = popu[id][i];</p><p><b>　　}</b></p>

61、<p>　　Max_value_single.max_value_single = max_value_single;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//計(jì)算每個(gè)個(gè)體的適應(yīng)度</p><p>　　public doubl

62、e[] getFitness(int[][] popu){</p><p>　　int size = popu.length;</p><p>　　double[] fitness = new double[size];</p><p>　　for(int i = 0; i < size; i ++){</p><p>　　fitnes

63、s[i] = get_singleValue(popu[i]);</p><p><b>　　}</b></p><p>　　return fitness;</p><p><b>　　}</b></p><p>　　//計(jì)算每個(gè)個(gè)體的選擇概率</p><p>　　priva

64、te double[] get_selectRate(double[] fitness){</p><p>　　double sum = 0;</p><p>　　int size = fitness.length;</p><p>　　double[] select_rate = new double[size];</p><p>　　fo

65、r(int i = 0; i < size; i ++){</p><p>　　sum += fitness[i];</p><p><b>　　}</b></p><p>　　for(int j = 0; j < size; j ++){</p><p>　　select_rate[j] = fitness

66、[j]/sum;</p><p><b>　　}</b></p><p>　　return select_rate;</p><p><b>　　}</b></p><p>　　//計(jì)算每個(gè)個(gè)體的累積概率</p><p>　　private double[] get_accu

67、Rate(double[] select_rate){</p><p>　　int i = 0;</p><p>　　int size = select_rate.length;</p><p>　　double[] accu_rate = new double[size];</p><p>　　for(i = 0; i < size;

68、 i ++){</p><p>　　accu_rate[i] = select_rate[i]; </p><p><b>　　}</b></p><p>　　for(i = 1; i < size; i ++){</p><p>　　accu_rate[i] += accu_rate[i-1]; </p&g

69、t;<p><b>　　}</b></p><p>　　return accu_rate;</p><p><b>　　}</b></p><p><b>　　//選擇</b></p><p>　　public int[][] select(double[] ac

70、cu_rate, int[][] popu){</p><p>　　double random_rate;</p><p>　　int size = accu_rate.length;</p><p>　　int[][] select_popu = new int[Global.POPU_NUM][goods_num];</p><p>　　

71、select_popu = doubleArrayCopy(popu);</p><p>　　for(int i = 0; i < size; i ++){</p><p>　　random_rate = Math.random();//產(chǎn)生隨機(jī)數(shù)</p><p>　　for(int j = 0; j < size; j ++){</p>

72、<p>　　if(random_rate <= accu_rate[j]){</p><p>　　select_popu[i] = singleArrayCopy(select_popu[j]);</p><p><b>　　}</b></p><p><b>　　}</b></p><

73、p><b>　　}</b></p><p>　　return select_popu;</p><p><b>　　}</b></p><p><b>　　//交叉</b></p><p>　　public int[][] crossover(int[][] select

74、_popu){</p><p>　　int i = 0;</p><p>　　int random_pos = 0, temp = 0;//交換基因的位置</p><p>　　int cross_num = (int)(Global.CROSS_RATE * Global.POPU_NUM);//參與交換的個(gè)體數(shù)</p><p>　　//Sy

75、stem.out.println(cross_num);</p><p>　　int[][] cross_popu = new int[Global.POPU_NUM][goods_num];</p><p>　　cross_popu = doubleArrayCopy(select_popu);</p><p>　　for(i = 1; i < cross_

76、num; i += 2){</p><p>　　random_pos = (int)Math.round(Math.random())%goods_num;</p><p>　　temp = cross_popu[i][random_pos];</p><p>　　cross_popu[i][random_pos]= cross_popu[i-1][random_p

77、os];</p><p>　　cross_popu[i-1][random_pos] = temp;</p><p>　　if(get_singleWeight(cross_popu[i]) > package_capacity || get_singleWeight(cross_popu[i-1]) > package_capacity){</p><p&

78、gt;　　temp = cross_popu[i][random_pos];</p><p>　　cross_popu[i][random_pos]= cross_popu[i-1][random_pos];</p><p>　　cross_popu[i-1][random_pos] = temp;</p><p><b>　　}</b><

79、;/p><p><b>　　}</b></p><p>　　return cross_popu;</p><p><b>　　}</b></p><p><b>　　//變異</b></p><p>　　public int[][] mutate(int[]

80、[] cross_popu){</p><p>　　int i = 0;</p><p>　　int row_id = 0;</p><p>　　int col_id = 0;</p><p>　　int mutate_num = (int)(Global.MUTA_RATE * Global.POPU_NUM * goods_num);//

81、參與變異的基因個(gè)數(shù)</p><p>　　//System.out.println(mutate_num);</p><p>　　int[][] mutate_popu = new int[Global.POPU_NUM][goods_num];</p><p>　　mutate_popu = doubleArrayCopy(cross_popu);</p>

82、;<p>　　for(i = 0; i < mutate_num; i ++){</p><p>　　row_id = (int)Math.round(Math.random()*10)%Global.POPU_NUM;</p><p>　　col_id = (int)Math.round(Math.random()*10)%goods_num;</p>

83、<p>　　mutate_popu[row_id][col_id] = 1 - mutate_popu[row_id][col_id];</p><p>　　if(get_singleWeight(mutate_popu[row_id]) > package_capacity){</p><p>　　mutate_popu[row_id][col_id] = 1 - mut

84、ate_popu[row_id][col_id];</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　return mutate_popu;</p><p><b>　　}</b></p><p>&l

85、t;b>　　//遺傳算法</b></p><p>　　public int[][] packetByGA(){</p><p>　　int popu_id = 1;//總?cè)旱拇鷶?shù)</p><p>　　double[] fitness = null;</p><p>　　double[] select_rate = null

86、;</p><p>　　double[] accu_rate = null;</p><p>　　int[][] select_popu = null;</p><p>　　int[][] cross_popu = null;</p><p>　　int[][] popu = generatePopu();</p><p&

87、gt;　　get_maxValue_single(popu);</p><p>　　/*System.out.println("第" + popu_id + "代種群的最大值：" + Max_value_single.max_value);*/</p><p>　　while(popu_id < Global.MAX_GEN_NUM){//沒(méi)有

88、終止</p><p>　　fitness = getFitness(popu);</p><p>　　select_rate = get_selectRate(fitness);</p><p>　　accu_rate = get_accuRate(select_rate);</p><p>　　select_popu = select(ac

89、cu_rate, popu);</p><p>　　cross_popu = crossover(select_popu);</p><p>　　popu = mutate(cross_popu);//下一代總?cè)?lt;/p><p>　　popu_id ++;</p><p>　　get_maxValue_single(popu);</p&

90、gt;<p>　　/*System.out.println("第" + popu_id + "代種群的最大值：" + Max_value_single.max_value);*/</p><p><b>　　}</b></p><p>　　return popu;</p><p><b

91、>　　}</b></p><p><b>　　//輸出</b></p><p>　　public void output(int[][] popu){</p><p>　　//-----------------------</p><p>　　File f = null;</p><

92、p>　　FileWriter fw = null;</p><p>　　PrintWriter pw = null;</p><p>　　//------------------------</p><p><b>　　try {</b></p><p>　　f = new File("./package

93、ByGA.txt");</p><p>　　fw = new FileWriter(f);</p><p>　　pw = new PrintWriter(fw);</p><p><b>　　//背包的容量</b></p><p>　　pw.write("背包的容量：");</p>

94、;<p>　　pw.write("" + package_capacity);</p><p>　　pw.println();</p><p>　　pw.println();</p><p><b>　　//物品的重量</b></p><p>　　pw.write("物品的重量

95、：");</p><p>　　for(int j = 0; j < goods_num; j ++){</p><p>　　if(Max_value_single.max_value_single[j] == 1){</p><p>　　pw.write(goods_weight[j] + " ");</p><

96、;p><b>　　}</b></p><p><b>　　}</b></p><p>　　pw.println();</p><p>　　pw.println();</p><p><b>　　//物品的價(jià)值</b></p><p>　　pw.wr

97、ite("物品的價(jià)值：");</p><p>　　for(int j = 0; j < goods_num; j ++){</p><p>　　if(Max_value_single.max_value_single[j] == 1){</p><p>　　pw.write(goods_value[j] + " ");&

98、lt;/p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　pw.println();</p><p>　　pw.println();</p><p><b>　　//總價(jià)值</b></p><

99、p>　　pw.print("物品的總價(jià)值：");</p><p>　　pw.print(Max_value_single.max_value);</p><p>　　//-------------------------</p><p>　　pw.close();</p><p>　　fw.close();</

100、p><p>　　} catch (Exception e) {</p><p>　　e.printStackTrace();</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　public static void main(Str

101、ing[] args){</p><p>　　PackageByGA ga = new PackageByGA();</p><p>　　int[][] popu = ga.packetByGA();</p><p>　　ga.output(popu);</p><p><b>　　}</b></p>&l

102、t;p><b>　　}</b></p><p><b>　　//最大價(jià)值的個(gè)體</b></p><p>　　public class Max_value_single{</p><p>　　public static int[] max_value_single = null;</p><p>

103、;　　public static double max_value = 0;</p><p><b>　　}</b></p><p>　　public class Global {</p><p>　　public final static int POPU_NUM = 4;//種群的規(guī)模</p><p>　　publ

104、ic final static int MAX_GEN_NUM = 8;//遺傳的最大代數(shù)</p><p>　　public final static double CROSS_RATE = 1;//交叉率</p><p>　　public final static double MUTA_RATE = 0.1;//變異率</p><p><b>　

105、　}</b></p><p>　　第四部分 程序測(cè)試與結(jié)果分析</p><p><b>　　4.1 測(cè)試結(jié)果</b></p><p>　　4.1.1 用戶界面</p><p>　　4.1.2 輸入數(shù)據(jù)</p><p>　　第一行：背包容量，第二行：物品重量，第三行：物品價(jià)值：與第二行

106、對(duì)應(yīng)</p><p>　　4.1.3 輸出結(jié)果</p><p>　　1、種群規(guī)模為4，最大遺傳代數(shù)為8時(shí)連續(xù)運(yùn)行四次的結(jié)果：</p><p>　　種群規(guī)模為8，最大遺傳代數(shù)為20時(shí)連續(xù)運(yùn)行四次的結(jié)果：</p><p><b>　　4.2結(jié)果分析</b></p><p>　　可以看出在保持其他條件不

107、變的條件下增大種群規(guī)模和最大遺傳代數(shù)結(jié)果越精確。</p><p>　　第五部分 總結(jié)與心得體會(huì)</p><p>　　該算法具有遺傳算法的所有不足之處：</p><p>　　(1)編碼不規(guī)范及編碼存在表示的不準(zhǔn)確性。</p><p>　　(2)單一的遺傳算法編碼不能全面地將優(yōu)化問(wèn)題的約束表示出來(lái)?？紤]約束的一個(gè)方法就是對(duì)不可行解采用閾值，這樣

108、，計(jì)算的時(shí)間必然增加。</p><p>　　(3)遺傳算法通常的效率比其他傳統(tǒng)的優(yōu)化方法低。</p><p>　　(4)遺傳算法容易過(guò)早收斂。</p><p>　　(5)遺傳算法對(duì)算法的精度、可行度、計(jì)算復(fù)雜性等方面，還沒(méi)有有效的定量分析方法</p><p>　　而且這個(gè)算法實(shí)現(xiàn)得比較簡(jiǎn)單，還有很多未知錯(cuò)誤沒(méi)有進(jìn)行優(yōu)化，容易出現(xiàn)異常。<