2022年遗传算法求解背包问题 .pdf

遗传算法求解 0-1 背包问题一、问题描述给定 n 种物品和容量为C 的背包。物品i 的重量是wi，其价值为vi 。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?二、知识表示1、状态表示（1）个体或染色体：问题的一个解，表示为n 个比特的字符串，比特值为0 表示不选该物品，比特值为1 表示选择该物品。（2）基因：染色体的每一个比特。（3）种群：解的集合。（4）适应度：衡量个体优劣的函数值。2、控制参数（1）种群规模：解的个数。（2）最大遗传的代数（3）交叉率： 参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为0.40.99。（4）变异率：发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围一般为0.0001 0.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）按交叉率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 表示物品不被选中。种群：用二维数组表示，每一行表示一个染色体。具有最大价值的染色体：由于每一个染色体经过选择、交叉、变异后都可能发生变化，所以对于产生的新的总群，需要记录每个物品的选中状态。同时保存该状态下物品的最大价值，如果新的总群能够产生更优的值，则替换具有最大价值的染色体。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 2、算法流程图四、实验结果和分析1、用户界面名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - 2、输入3、输出（1）种群的规模为4，最大遗传代数为8（连续 4 次运行结果）（2）种群的规模为20，最大遗传代数为8（连续 4 次运行结果）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - （3）种群的规模为4，最大遗传代数为50（连续 4 次运行结果）由于篇幅的关系， 只给出了不同情况下的连续4 次运行结果， 如果运行更多次就会发现：其他控制参数不变，种群规模越大，结果越精确；其他控制参数不变，最大遗传代数越大，结果越精确。五、程序一共有 3 个类： PackageByGA（主类），Max_value_single （具有最大价值的个体或染色体） ，Global（定义了一些全局常量） 。1、PackageByGApackagehrbeu.edu.hdy;import java.beans.PropertyChangeEvent;import java.beans.PropertyChangeListener;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - import java.io.BufferedReader;import java.io.File;import java.io.FileInputStream;import java.io.FileWriter;import java.io.InputStreamReader;import java.io.PrintWriter;import javax.swing.JFileChooser;import javax.swing.JOptionPane;/遗传算法解决0-1 背包问题public classPackageByGA private int package_capacity = 0;/背包的容量private int goods_num = 0;/物品的个数，对应遗传学中个体的基因个数private int goods_weight = null;/ 物品的价值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() / 注册监听器public 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);BufferedReader br = new BufferedReader(ir);/获取第一行数据，背包的容量package_capacity= Integer.parseInt(br.readLine().trim();/-String str_line = null;/获取第二行数据，物品的重量名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - str_line = br.readLine();goods_weight = strArr_to_intArr(str_line.split();/获取第三行数据，物品的价值str_line = br.readLine();goods_value = strArr_to_doubleArr(str_line.split();/物品的个数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(StringstrArr)int size = strArr.length;int int_arr = new intsize;for(int i = 0; i size; i +)int_arri = Integer.valueOf(strArri);return int_arr;/字符串数组转换为浮点数数组private double strArr_to_doubleArr(StringstrArr)int size = strArr.length;double double_arr = new doublesize;for(int i = 0; i size; i +)double_arri = Double.valueOf(strArri);return double_arr;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - /一维数组复制private int singleArrayCopy(intsource)int size = source.length;int des= new intsize;for(int i = 0; i size; i +)desi = sourcei;return des;/二维数组复制private int doubleArrayCopy(intsource)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 +)desij = sourceij;return des;/产生初始种群public intgeneratePopu()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;/计算个体的总重量名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - private int get_singleWeight(int single)int total_weight = 0;int size = single.length;for(int i = 0; i size; i +)if(singlei= 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(intpopu)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.max_value)Max_value_single.max_value = max_value;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - 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;/计算每个个体的适应度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(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 = fitnessj/sum;return select_rate;/计算每个个体的累积概率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 +)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - accu_ratei += accu_ratei-1;return accu_rate;/选择public intselect(double accu_rate,intpopu)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(select_popuj);return select_popu;/交叉public intcrossover(intselect_popu)int i = 0;int random_pos = 0, temp = 0;/交换基因的位置int cross_num = (int)(Global.CROSS_RATE* Global.POPU_NUM);/ 参与交换的个体数/System.out.println(cross_num);intcross_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;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - return cross_popu;/变异public intmutate(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_capacity)mutate_popurow_idcol_id= 1 - mutate_popurow_idcol_id;return mutate_popu;/遗传算法public intpacketByGA()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(第+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);名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - select_popu = select(accu_rate,popu);cross_popu = crossover(select_popu);popu = mutate(cross_popu);/下一代总群popu_id +;get_maxValue_single(popu);/*System.out.println(第 +popu_id+ 代 种 群 的 最 大 值 ： +Max_value_single.max_value);*/return popu;/输出public void output(intpopu)/-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(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(goods_valuej+ );pw.println();名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - 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_singlepackagehrbeu.edu.hdy;/最大价值的个体public classMax_value_singlepublic static int max_value_single = null;public static double max_value = 0;3、Globalpackagehrbeu.edu.hdy;public classGlobal 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.txt102 2 6 5 46 3 5 4 6名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -