遗传算法求解01背包问题(JAVA).pdf

《遗传算法求解01背包问题(JAVA).pdf》由会员分享，可在线阅读，更多相关《遗传算法求解01背包问题(JAVA).pdf（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遗传算法求解 0-1 背包问题 一、问题描述 给定 n 种物品和容量为 C 的背包。物品 i 的重量是 wi，其价值为 vi。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?二、知识表示 1、状态表示（1）个体或染色体：问题的一个解，表示为 n 个比特的字符串，比特值为 0 表示不选该物品，比特值为 1 表示选择该物品。（2）基因：染色体的每一个比特。（3）种群：解的集合。（4）适应度：衡量个体优劣的函数值。2、控制参数（1）种群规模：解的个数。（2）最大遗传的代数（3）交叉率：参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为 0.40.99。（4）变异率：发生变异的基因

2、位数所占全体染色体的基因总位数的比例，取值范围一般为0.00010.1。3、算法描述（1）在搜索空间 U 上定义一个适应度函数 f(x)，给定种群规模 N，交叉率 Pc 和变异率 Pm，代数 T；（2）随机产生 U 中的 N 个个体 s1,s2,sN，组成初始种群 S=s1,s2,sN，置代数计数器 t=1；（3）计算 S 中每个个体的适应度 f()；（4）若终止条件满足，则取 S 中适应度最大的个体作为所求结果，算法结束。（5）按选择概率 P(xi)所决定的选中机会，每次从 S 中随机选定 1 个个体并将其染色体复制，共做 N 次，然后将复制所得的 N 个染色体组成群体 S1；（6）按交叉率

3、 Pc 所决定的参加交叉的染色体数 c，从 S1 中随机确定 c 个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体 S2；（7）按变异率 Pm 所决定的变异次数 m，从 S2 中随机确定 m 个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体 S3；（8）将群体 S3 作为新一代种群，即用 S3 代替 S，t=t+1，转步 3。三、算法实现 1、主要的数据结构 染色体：用一维数组表示，数组中下标为 i 的元素表示第（i+1）个物品的选中状态，元素值为 1，表示物品被选中，元素值为 0 表示物品不被选中。种群：用二维数组表示，每一行表示一个染色体。具有最大价值的

4、染色体：由于每一个染色体经过选择、交叉、变异后都可能发生变化，所以对于产生的新的总群，需要记录每个物品的选中状态。同时保存该状态下物品的最大价值，如果新的总群能够产生更优的值，则替换具有最大价值的染色体。2、算法流程图 四、实验结果和分析 1、用户界面 2、输入 3、输出（1）种群的规模为 4，最大遗传代数为 8（连续 4 次运行结果）（2）种群的规模为 20，最大遗传代数为 8（连续 4 次运行结果）（3）种群的规模为 4，最大遗传代数为 50（连续 4 次运行结果）由于篇幅的关系，只给出了不同情况下的连续 4 次运行结果，如果运行更多次就会发现：其他控制参数不变，种群规模越大，结果越精确；

5、其他控制参数不变，最大遗传代数越大，结果越精确。五、程序 一共有 3 个类：PackageByGA（主类），Max_value_single（具有最大价值的个体或染色体），Global（定义了一些全局常量）。1、PackageByGA package hrbeu.edu.hdy;import java.beans.PropertyChangeEvent;import java.beans.PropertyChangeListener;import java.io.BufferedReader;import java.io.File;import java.io.FileInputStream;

6、import java.io.FileWriter;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;/物品的个数，对应遗传学中个体的基因个数 private int goods_weight=n

7、ull;/物品的价值 private double goods_value=null;/物品的价值 private int popu=null;/种群 public PackageByGA()input();/输入 private void input()JFileChooser fc=new JFileChooser();/文件选择对话框 fc.setCurrentDirectory(new File(.);/从当前目录选择文件 /获取输入源，输入源为选取的文件 fc.addPropertyChangeListener(new PropertyChangeListener()/注册监听器 p

8、ublic void propertyChange(PropertyChangeEvent arg0)/属性改变事件 if(arg0.getPropertyName()=JFileChooser.SELECTED_FILE_CHANGED_PROPERTY)/选择单个文件 try File file=(File)arg0.getNewValue();/获取属性的新值，转换为文件对象 /创建输入流 FileInputStream fi=new FileInputStream(file);InputStreamReader ir=new InputStreamReader(fi);Buffered

9、Reader br=new BufferedReader(ir);/获取第一行数据，背包的容量 package_capacity=Integer.parseInt(br.readLine().trim();/-String str_line=null;/获取第二行数据，物品的重量 str_line=br.readLine();goods_weight=strArr_to_intArr(str_line.split();/获取第三行数据，物品的价值 str_line=br.readLine();goods_value=strArr_to_doubleArr(str_line.split();/物

10、品的个数 goods_num=goods_value.length;/关闭输入流 fi.close();ir.close();br.close();catch(Exception ep)/如果文件的内容不是全为数字，则弹出对话框 JOptionPane.showMessageDialog(null,文件读取异常，检查文件内容是否全为数字！););fc.showOpenDialog(null);/弹出打开文件对话框 /字符串数组转换为整数数组 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;/字符串数组转换为浮点数数组 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;/一维数组复制 private int

12、singleArrayCopy(int source)int size=source.length;int des=new intsize;for(int i=0;i size;i+)desi=sourcei;return des;/二维数组复制 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_num;i+)for(int j=0;j col_num;j+)desi

13、j=sourceij;return des;/产生初始种群 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;/计算个体的总重量 private int get_singleWeight(int single)int total_weight=0;int size=single.length;for(int i=0;i size;i+)if(sing

14、lei=1)total_weight+=goods_weighti;return total_weight;/计算个体的总价值 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_value;/获取总价值最大的个体 public void get_maxValue_single(int popu)int size=popu.length

15、;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.max_value)Max_value_single.max_value=max_value;int max_value_single=new intgoods_num;for(int i=0;i goo

16、ds_num;i+)max_value_singlei=popuidi;Max_value_single.max_value_single=max_value_single;/计算每个个体的适应度 public double getFitness(int popu)int size=popu.length;double fitness=new doublesize;for(int i=0;i size;i+)fitnessi=get_singleValue(popui);return fitness;/计算每个个体的选择概率 private double get_selectRate(doub

17、le 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=fitnessj/sum;return select_rate;/计算每个个体的累积概率 private double get_accuRate(double select_rate)int i=0;int size=select_rate.length;double accu_rate=ne

18、w 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(double 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=

19、0;i size;i+)random_rate=Math.random();for(int j=0;j size;j+)if(random_rate=accu_ratej)select_popui=singleArrayCopy(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);/参与交换的个体数 /Syst

20、em.out.println(cross_num);int cross_popu=new intGlobal.POPU_NUMgoods_num;cross_popu=doubleArrayCopy(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 cro

21、ss_popu;/变异 public int mutate(int cross_popu)int i=0;int row_id=0;int col_id=0;int mutate_num=(int)(Global.MUTA_RATE*Global.POPU_NUM*goods_num);/参与变异的基因个数 /System.out.println(mutate_num);int mutate_popu=new intGlobal.POPU_NUMgoods_num;mutate_popu=doubleArrayCopy(cross_popu);for(i=0;i package_capacit

22、y)mutate_popurow_idcol_id=1-mutate_popurow_idcol_id;return mutate_popu;/遗传算法 public int packetByGA()int popu_id=1;/总群的代数 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(第

23、 +popu_id+代 种 群 的 最 大 值：+Max_value_single.max_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);/下一代总群 popu_id+;

24、get_maxValue_single(popu);/*System.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(背包的容

25、量：);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(goods_weightj+);pw.println();pw.println();/物品的价值 pw.write(物品的价值：);for(int j=0;j goods_num;j+)if(Max_value_single.max_value_singlej=1)pw.write(

26、goods_valuej+);pw.println();pw.println();/总价值 pw.print(物品的总价值：);pw.print(Max_value_single.max_value);/-pw.close();fw.close();catch(Exception e)e.printStackTrace();public static void main(String args)PackageByGA ga=new PackageByGA();int popu=ga.packetByGA();ga.output(popu);2、Max_value_single package

27、hrbeu.edu.hdy;/最大价值的个体 public class Max_value_single public static int max_value_single=null;public static double max_value=0;3、Global package hrbeu.edu.hdy;public class Global public final static int POPU_NUM=4;/种群的规模 public final static int MAX_GEN_NUM=8;/遗传的最大代数 public final static double CROSS_RATE=1;/交叉率 public final static double MUTA_RATE=0.1;/变异率 输入：input.txt 10 2 2 6 5 4 6 3 5 4 6