搜索
遗传算法求解0-1背包问题一、问题描述给定n种物品和容量为C的背包。物品i的重量是wi，其价值为vi。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?二、知识表示1、状态表示（1）个体或染色体：问题的一个解，表示为n个比特的字符串，比特值为0表示不选该物品，比特值为1表示选择该物品。（2）基因：染色体的每一个比特。（3）种群：解的集合。（4）适应度：衡量个体优劣的函数值。2、控制参数（1）种群规模：解的个数。（2）最大遗传的代数（3）交叉率：参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为0.4～0.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表示物品不被选中。种群：用二维数组表示，每一行表示一个染色体。具有最大价值的染色体：由于每一个染色体经过选择、交叉、变异后都可能发生变化，所以对于产生的新的总群，需要记录每个物品的选中状态。同时保存该状态下物品的最大价值，如果新的总群能够产生更优的值，则替换具有最大价值的染色体。2、算法流程图四、实验结果和分析1、用户界面2、输入3、输出（1）种群的规模为4，最大遗传代数为8（连续4次运行结果）（2）种群的规模为20，最大遗传代数为8（连续4次运行结果）（3）种群的规模为4，最大遗传代数为50（连续4次运行结果）由于篇幅的关系，只给出了不同情况下的连续4次运行结果，如果运行更多次就会发现：其他控制参数不变，种群规模越大，结果越精确；其他控制参数不变，最大遗传代数越大，结果越精确。五、程序一共有3个类：PackageByGA（主类），Max_value_single（具有最大价值的个体或染色体），Global（定义了一些全局常量）。1、PackageByGApackagehrbeu.edu.hdy;importjava.beans.PropertyChangeEvent;importjava.beans.PropertyChangeListener;importjava.io.BufferedReader;importjava.io.File;importjava.io.FileInputStream;importjava.io.FileWriter;importjava.io.InputStreamReader;importjava.io.PrintWriter;importjavax.swing.JFileChooser;importjavax.swing.JOptionPane;//遗传算法解决0-1背包问题publicclassPackageByGA{privateintpackage_capacity=0;//背包的容量privateintgoods_num=0;//物品的个数，对应遗传学中个体的基因个数privateint[]goods_weight=null;//物品的价值privatedouble[]goods_value=null;//物品的价值privateint[][]popu=null;//种群publicPackageByGA(){input();}//输入privatevoidinput(){JFileChooserfc=newJFileChooser();//文件选择对话框fc.setCurrentDirectory(newFile(.));//从当前目录选择文件//获取输入源，输入源为选取的文件fc.addPropertyChangeListener(newPropertyChangeListener(){//注册监听器publicvoidpropertyChange(PropertyChangeEventarg0){//属性改变事件if(arg0.getPropertyName()==JFileChooser.SELECTED_FILE_CHANGED_PROPERTY){//选择单个文件try{Filefile=(File)arg0.getNewValue();//获取属性的新值，转换为文件对象//创建输入流FileInputStreamfi=newFileInputStream(file);InputStreamReaderir=newInputStreamReader(fi);BufferedReaderbr=newBufferedReader(ir);//获取第一行数据，背包的容量package_capacity=Integer.parseInt(br.readLine().trim());//------------------------------Stringstr_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(Exceptionep){//如果文件的内容不是全为数字，则弹出对话框JOptionPane.showMessageDialog(null,文件读取异常，检查文件内容是否全为数字！);}}}});fc.showOpenDialog(null);//弹出打开文件对话框}//字符串数组转换为整数数组privateint[]strArr_to_intArr(String[]strArr){intsize=strArr.length;int[]int_arr=newint[size];for(inti=0;isize;i++){int_arr[i]=Integer.valueOf(strArr[i]);}returnint_arr;}//字符串数组转换为浮点数数组privatedouble[]strArr_to_doubleArr(String[]strArr){intsize=strArr.length;double[]double_arr=newdouble[size];for(inti=0;isize;i++){double_arr[i]=Double.valueOf(strArr[i]);}returndouble_arr;}//一维数组复制privateint[]singleArrayCopy(int[]source){intsize=source.length;int[]des=newint[size];for(inti=0;isize;i++){des[i]=source[i];}returndes;}//二维数组复制privateint[][]doubleArrayCopy(int[][]source){introw_num=source.length;intcol_num=source[0].length;int[][]des=newint[row_num][col_num];for(inti=0;irow_num;i++){for(intj=0;jcol_num;j++){des[i][j]=source[i][j];}}returndes;}//产生初始种群publicint[][]generatePopu(){popu=newint[Global.POPU_NUM][goods_num];for(inti=0;iGlobal.POPU_NUM;i++){for(intj=0;jgoods_num;j++){doubled=Math.random()*10;//[0,10)之间的double型数值popu[i][j]=((int)Math.round(d))%2;//1表示选择该物品，0表示不选择该物品}if(get_singleWeight(popu[i])package_capacity){//超出背包容量i--;}}returnpopu;}//计算个体的总重量privateintget_singleWeight(int[]single){inttotal_weight=0;intsize=single.length;for(inti=0;isize;i++){if(single[i]==1){total_weight+=goods_weight[i];}}returntotal_weight;}//计算个体的总价值privatedoubleget_singleValue(int[]single){inttotal_value=0;intsize=single.length;for(inti=0;isize;i++){if(single[i]==1){total_value+=goods_value[i];}}returntotal_value;}//获取总价值最大的个体publicvoidget_maxValue_single(int[][]popu){intsize=popu.length;double[]fitness=newdouble[size];for(inti=0;isize;i++){fitness[i]=get_singleValue(popu[i]);}intid=0;doublemax_value=fitness[0];for(intj=1;jsize;j++){if(fitness[j]max_value){max_value=fitness[j];id=j;}}if(max_valueMax_value_single.max_value){Max_value_single.max_value=max_value;int[]max_value_single=newint[goods_num];for(inti=0;igoods_num;i++){max_value_single[i]=popu[id][i];}Max_value_single.max_value_single=max_value_single;}}//计算每个个体的适应度publicdouble[]getFitness(int[][]popu){intsize=popu.length;double[]fitness=newdouble[size];for(inti=0;isize;i++){fitness[i]=get_singleValue(popu[i]);}returnfitness;}//计算每个个体的选择概率privatedouble[]get_selectRate(doubl