遺傳算法求解0-1背包問題(JAVA)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)遺傳算法求解0-1背包問題一、問題描述給定n種物品和容量為C的背包。物品i的重量是wi，其價值為vi。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?二、知識表示1、狀態(tài)表示（1）個體或染色體：問題的一個解，表示為n個比特的字符串，比特值為0表示不選該物品，比特值為1表示選擇該物品。（2）基因：染色體的每一個比特。（3）種群：解的集合。（4）適應(yīng)度：衡量個體優(yōu)劣的函數(shù)值。2、控制參數(shù)（1）種群規(guī)模：解的個數(shù)。（2）最大遺傳的代數(shù)（3）交叉率：參加交叉運(yùn)算的染

2、色體個數(shù)占全體染色體的比例，取值范圍一般為0.40.99。（4）變異率：發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，取值范圍一般為0.00010.1。3、算法描述（1）在搜索空間U上定義一個適應(yīng)度函數(shù)f(x)，給定種群規(guī)模N，交叉率Pc和變異率Pm，代數(shù)T；（2）隨機(jī)產(chǎn)生U中的N個個體s1, s2, , sN，組成初始種群S=s1, s2, , sN，置代數(shù)計(jì)數(shù)器t=1；（3）計(jì)算S中每個個體的適應(yīng)度f() ；（4）若終止條件滿足，則取S中適應(yīng)度最大的個體作為所求結(jié)果，算法結(jié)束。（5）按選擇概率P(xi)所決定的選中機(jī)會，每次從S中隨機(jī)選定1個個體并將其染色體復(fù)制，共做N次，然后將復(fù)制

3、所得的N個染色體組成群體S1；（6）按交叉率Pc所決定的參加交叉的染色體數(shù)c，從S1中隨機(jī)確定c個染色體，配對進(jìn)行交叉操作，并用產(chǎn)生的新染色體代替原染色體，得群體S2；（7）按變異率Pm所決定的變異次數(shù)m，從S2中隨機(jī)確定m個染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新染色體代替原染色體，得群體S3；（8）將群體S3作為新一代種群，即用S3代替S，t = t+1，轉(zhuǎn)步3。三、算法實(shí)現(xiàn)1、主要的數(shù)據(jù)結(jié)構(gòu)染色體：用一維數(shù)組表示，數(shù)組中下標(biāo)為i的元素表示第（i+1）個物品的選中狀態(tài)，元素值為1，表示物品被選中，元素值為0表示物品不被選中。種群：用二維數(shù)組表示，每一行表示一個染色體。具有最大價值的染色體：由

4、于每一個染色體經(jīng)過選擇、交叉、變異后都可能發(fā)生變化，所以對于產(chǎn)生的新的總?cè)海枰涗浢總€物品的選中狀態(tài)。同時保存該狀態(tài)下物品的最大價值，如果新的總?cè)耗軌虍a(chǎn)生更優(yōu)的值，則替換具有最大價值的染色體。2、算法流程圖四、實(shí)驗(yàn)結(jié)果和分析1、用戶界面2、輸入3、輸出（1）種群的規(guī)模為4，最大遺傳代數(shù)為8（連續(xù)4次運(yùn)行結(jié)果） （2）種群的規(guī)模為20，最大遺傳代數(shù)為8（連續(xù)4次運(yùn)行結(jié)果） （3）種群的規(guī)模為4，最大遺傳代數(shù)為50（連續(xù)4次運(yùn)行結(jié)果） 由于篇幅的關(guān)系，只給出了不同情況下的連續(xù)4次運(yùn)行結(jié)果，如果運(yùn)行更多次就會發(fā)現(xiàn)：其他控制參數(shù)不變，種群規(guī)模越大，結(jié)果越精確；其他控制參數(shù)不變，最大遺傳代數(shù)越大，結(jié)果

5、越精確。五、程序一共有3個類：PackageByGA（主類），Max_value_single（具有最大價值的個體或染色體），Global（定義了一些全局常量）。1、PackageByGApackage .hdy;import java.beans.PropertyChangeEvent;import java.beans.PropertyChangeListener;import java.io.BufferedReader;import java.io.File;import java.io.FileInputStream;import java.io.FileWrite

6、r;import java.io.InputStreamReader;import java.io.PrintWriter;import javax.swing.JFileChooser;import javax.swing.JOptionPane;/遺傳算法解決0-1背包問題public class PackageByGA private int package_capacity = 0;/背包的容量private int goods_num = 0;/物品的個數(shù)，對應(yīng)遺傳學(xué)中個體的基因個數(shù)private int goods_weight = null;/物品的價值private doubl

7、e goods_value = null;/物品的價值 private int popu = null;/種群public PackageByGA()input();/輸入private void input()JFileChooser fc = new JFileChooser();/文件選擇對話框fc.setCurrentDirectory(new File(.);/從當(dāng)前目錄選擇文件/獲取輸入源，輸入源為選取的文件fc.addPropertyChangeListener(new PropertyChangeListener() /注冊監(jiān)聽器public void propertyChan

8、ge(PropertyChangeEvent arg0) /屬性改變事件if (arg0.getPropertyName() = JFileChooser.SELECTED_FILE_CHANGED_PROPERTY) /選擇單個文件try File file = (File) arg0.getNewValue();/獲取屬性的新值，轉(zhuǎn)換為文件對象/創(chuàng)建輸入流FileInputStream fi = new FileInputStream(file);InputStreamReader ir = new InputStreamReader(fi);BufferedReader br = new

9、 BufferedReader(ir);/獲取第一行數(shù)據(jù)，背包的容量package_capacity = Integer.parseInt(br.readLine().trim();/-String str_line = null;/獲取第二行數(shù)據(jù)，物品的重量str_line = br.readLine();goods_weight = strArr_to_intArr(str_line.split( );/獲取第三行數(shù)據(jù)，物品的價值str_line = br.readLine();goods_value = strArr_to_doubleArr(str_line.split( );/物品的

10、個數(shù)goods_num = goods_value.length;/關(guān)閉輸入流fi.close();ir.close();br.close(); catch (Exception ep) /如果文件的內(nèi)容不是全為數(shù)字，則彈出對話框JOptionPane.showMessageDialog(null,文件讀取異常，檢查文件內(nèi)容是否全為數(shù)字！););fc.showOpenDialog(null);/彈出打開文件對話框/字符串?dāng)?shù)組轉(zhuǎn)換為整數(shù)數(shù)組private int strArr_to_intArr(String strArr)int size = strArr.length;int int_arr

11、 = new intsize;for(int i = 0; i size; i +)int_arri = Integer.valueOf(strArri);return int_arr;/字符串?dāng)?shù)組轉(zhuǎn)換為浮點(diǎn)數(shù)數(shù)組private double strArr_to_doubleArr(String strArr)int size = strArr.length;double double_arr = new doublesize;for(int i = 0; i size; i +)double_arri = Double.valueOf(strArri);return double_arr;/

12、一維數(shù)組復(fù)制private int singleArrayCopy(int source)int size = source.length;int des = new intsize;for(int i = 0; i size; i +)desi = sourcei;return des;/二維數(shù)組復(fù)制private int doubleArrayCopy(int source)int row_num = source.length;int col_num = source0.length;int des = new introw_numcol_num;for(int i = 0; i row

13、_num; i +)for(int j = 0; j col_num; j +)desij = sourceij;return des;/產(chǎn)生初始種群public int generatePopu()popu = new intGlobal.POPU_NUMgoods_num;for(int i = 0; i Global.POPU_NUM; i +)for(int j = 0; j package_capacity)/超出背包容量i -;return popu;/計(jì)算個體的總重量private int get_singleWeight(int single)int total_weight

14、= 0;int size = single.length;for(int i = 0; i size; i +)if(singlei = 1)total_weight += goods_weighti;return total_weight;/計(jì)算個體的總價值private double get_singleValue(int single)int total_value = 0;int size = single.length;for(int i = 0; i size; i +)if(singlei = 1)total_value += goods_valuei;return total_

15、value;/獲取總價值最大的個體public void get_maxValue_single(int popu)int size = popu.length;double fitness = new doublesize;for(int i = 0; i size; i +)fitnessi = get_singleValue(popui);int id = 0;double max_value = fitness0;for(int j = 1; j max_value)max_value = fitnessj;id = j;if(max_value Max_value_single.ma

16、x_value)Max_value_single.max_value = max_value;int max_value_single = new intgoods_num;for(int i = 0; i goods_num; i +)max_value_singlei = popuidi;Max_value_single.max_value_single = max_value_single;/計(jì)算每個個體的適應(yīng)度public double getFitness(int popu)int size = popu.length;double fitness = new doublesize;

17、for(int i = 0; i size; i +)fitnessi = get_singleValue(popui);return fitness;/計(jì)算每個個體的選擇概率private double get_selectRate(double fitness)double sum = 0;int size = fitness.length;double select_rate = new doublesize;for(int i = 0; i size; i +)sum += fitnessi;for(int j = 0; j size; j +)select_ratej = fitne

18、ssj/sum;return select_rate;/計(jì)算每個個體的累積概率private double get_accuRate(double select_rate)int i = 0;int size = select_rate.length;double accu_rate = new doublesize;for(i = 0; i size; i +)accu_ratei = select_ratei; for(i = 1; i size; i +)accu_ratei += accu_ratei-1; return accu_rate;/選擇public int select(d

19、ouble accu_rate, int popu)double random_rate;int size = accu_rate.length;int select_popu = new intGlobal.POPU_NUMgoods_num;select_popu = doubleArrayCopy(popu);for(int i = 0; i size; i +)random_rate = Math.random();for(int j = 0; j size; j +)if(random_rate = accu_ratej)select_popui = singleArrayCopy(

20、select_popuj);return select_popu;/交叉public int crossover(int select_popu) int i = 0; int random_pos = 0, temp = 0;/交換基因的位置 int cross_num = (int)(Global.CROSS_RATE * Global.POPU_NUM);/參與交換的個體數(shù) /System.out.println(cross_num); int cross_popu = new intGlobal.POPU_NUMgoods_num; cross_popu = doubleArrayCo

21、py(select_popu); for(i = 1; i package_capacity | get_singleWeight(cross_popui-1) package_capacity) temp = cross_popuirandom_pos; cross_popuirandom_pos= cross_popui-1random_pos; cross_popui-1random_pos = temp; return cross_popu;/變異public int mutate(int cross_popu)int i = 0;int row_id = 0;int col_id =

22、 0;int mutate_num = (int)(Global.MUTA_RATE * Global.POPU_NUM * goods_num);/參與變異的基因個數(shù)/System.out.println(mutate_num); int mutate_popu = new intGlobal.POPU_NUMgoods_num;mutate_popu = doubleArrayCopy(cross_popu); for(i = 0; i package_capacity)mutate_popurow_idcol_id = 1 - mutate_popurow_idcol_id; retur

23、n mutate_popu;/遺傳算法public int packetByGA()int popu_id = 1;/總?cè)旱拇鷶?shù)double fitness = null;double select_rate = null;double accu_rate = null;int select_popu = null;int cross_popu = null;int popu = generatePopu();get_maxValue_single(popu);/*System.out.println(第 + popu_id + 代種群的最大值： + Max_value_single.max_

24、value);*/while(popu_id Global.MAX_GEN_NUM)/沒有終止fitness = getFitness(popu);select_rate = get_selectRate(fitness);accu_rate = get_accuRate(select_rate);select_popu = select(accu_rate, popu);cross_popu = crossover(select_popu);popu = mutate(cross_popu);/下一代總?cè)簆opu_id +;get_maxValue_single(popu);/*System

25、.out.println(第 + popu_id + 代種群的最大值： + Max_value_single.max_value);*/return popu;/輸出public void output(int popu)/-File f = null;FileWriter fw = null;PrintWriter pw = null;/-try f = new File(./packageByGA.txt);fw = new FileWriter(f);pw = new PrintWriter(fw);/背包的容量pw.write(背包的容量：);pw.write( + package_capacity);pw.println();pw.println();/物品的重量pw.write(物品的重量：);for(int j = 0; j goods_num; j +)if(Max_value_single.max_value_singlej = 1)pw.write(go