遗传算法求解0-1背包问题(JAVA)(共14页).doc

精选优质文档-倾情为你奉上遗传算法求解0-1背包问题一、问题描述给定n种物品和容量为C的背包。物品i的重量是wi，其价值为vi。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?二、知识表示1、状态表示（1）个体或染色体：问题的一个解，表示为n个比特的字符串，比特值为0表示不选该物品，比特值为1表示选择该物品。（2）基因：染色体的每一个比特。（3）种群：解的集合。（4）适应度：衡量个体优劣的函数值。2、控制参数（1）种群规模：解的个数。（2）最大遗传的代数（3）交叉率：参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为0.40.99。（4）变异率：发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围一般为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）按交叉率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表示物品不被选中。种群：用二维数组表示，每一行表示一个染色体。具有最大价值的染色体：由于每一个染色体经过选择、交叉、变异后都可能发生变化，所以对于产生的新的总群，需要记录每个物品的选中状态。同时保存该状态下物品的最大价值，如果新的总群能够产生更优的值，则替换具有最大价值的染色体。2、算法流程图四、实验结果和分析1、用户界面2、输入3、输出（1）种群的规模为4，最大遗传代数为8（连续4次运行结果） （2）种群的规模为20，最大遗传代数为8（连续4次运行结果） （3）种群的规模为4，最大遗传代数为50（连续4次运行结果） 由于篇幅的关系，只给出了不同情况下的连续4次运行结果，如果运行更多次就会发现：其他控制参数不变，种群规模越大，结果越精确；其他控制参数不变，最大遗传代数越大，结果越精确。五、程序一共有3个类：PackageByGA（主类），Max_value_single（具有最大价值的个体或染色体），Global（定义了一些全局常量）。1、PackageByGApackage hrbeu.edu.hdy;import java.beans.PropertyChangeEvent;import java.beans.PropertyChangeListener;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 class PackageByGA 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;/获取第二行数据，物品的重量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(String strArr)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(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 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 +)desij = 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 < goods_num; j +)double d = Math.random()*10;/0,10)之间的double型数值popuij = (int)Math.round(d)%2;/1表示选择该物品，0表示不选择该物品if(get_singleWeight(popui) > 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(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(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 < size; j +)if(fitnessj > 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 < 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 +)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 = 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);/参与交换的个体数 /System.out.println(cross_num); int cross_popu = new intGlobal.POPU_NUMgoods_num; cross_popu = doubleArrayCopy(select_popu); for(i = 1; i < cross_num; i += 2) random_pos = (int)Math.round(Math.random()%goods_num; temp = cross_popuirandom_pos; cross_popuirandom_pos= cross_popui-1random_pos; cross_popui-1random_pos = temp; if(get_singleWeight(cross_popui) > 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 = 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 < mutate_num; i +)row_id = (int)Math.round(Math.random()*10)%Global.POPU_NUM;col_id = (int)Math.round(Math.random()*10)%goods_num;mutate_popurow_idcol_id = 1 - mutate_popurow_idcol_id;if(get_singleWeight(mutate_popurow_id) > package_capacity)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("第" + 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 +;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("背包的容量：");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();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_singlepackage hrbeu.edu.hdy;/最大价值的个体public class Max_value_singlepublic static int max_value_single = null;public static double max_value = 0;3、Globalpackage 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.txt102 2 6 5 46 3 5 4 6专心-专注-专业