遗传算法求解背包问题信管专业李鹏 201101002044一、遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。
在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。
二、背包问题描述背包问题是一个典型的组合优化问题，在计算理论中属于NP完全问题，主要应用于管理中的资源分配，资金预算，投资决策、装载问题的建模。
传统“0/1”背包问题可以描述为：把具有一定体积和价值的n件不同种类物品放到一个有限容量的背包里，使得背包中物品的价值总量最大。
三、数学模型背包问题可以描述如下：假设有n个物体，其重量用表示，价值用表示，背包的最大容量为b。
这里和b都大于0。
问题是要求背包所装的物体的总价值最大。
背包问题的数学模型描述如下：(1)(2)(3)约束条件(3)中表示物体i被选入背包，反之，表示物体i没有被选入背包。
约束条件(2)表示背包的容量约束。
四、使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。
这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。
五、程序整体流程（1）读取存取包的限种、商品的重要和价值的TXT文件；（2）初始化种群；（3）计算群体上每个个体的适应度值(Fitness) ；（4）评估适应度,对当前群体P(t)中每个个体Pi计算其适应度F(Pi)，适应度表示了该个体的性能好坏；（5）依照Pc选择个体进行交叉操作；（6）仿照Pm对繁殖个体进行变异操作（7）没有满足某种停止条件，则转第3步，否则进入8 ；（8）输出种群中适应度值最优的个体。
六、代码function Main()%定义全局变量global VariableNum POPSIZE MaxGens PXOVER PMutationVariableNum=3 %变量个数POPSIZE=50 %种群大小MaxGens=1000 %种群代数PXOVER=0.8 %交叉概率PMutation=0.2 %变异概率%读取数据文件load E:\现代优化算法\遗传算法\bound.txtVarBound=bound(:,1:2);global Pop newPopPop=zeros(POPSIZE+1,VariableNum);newPop=zeros(POPSIZE+1,VariableNum);%初始化种群for i=1:POPSIZEfor j=1:VariableNumPop(i,j)=VarBound(j,1)+rand()*(VarBound(j,2)-VarBound(j,1)); endend%计算适应值fitnessList=zeros(POPSIZE,1);for i=1:POPSIZEfitnessList(i,1)=fitness(Pop(i,1:VariableNum));end%保存最好值和最坏值Best=zeros(1,VariableNum+1);Worst=zeros(1,VariableNum+1);maxvalue=max(fitnessList);indexMax=find(fitnessList==maxvalue,1,'first');Best(1,1:VariableNum)=Pop(indexMax,1:VariableNum);Best(1,VariableNum+1)=maxvalue;minvalue=min(fitnessList);indexMin=find(fitnessList==minvalue,1,'first');Worst(1,1:VariableNum)=Pop(indexMin,1:VariableNum);Worst(1,VariableNum+1)=minvalue;genetation=1;while genetation<MaxGens%计算适应度区间sumfit=sum(abs(fitnessList));relativeFitness=zeros(POPSIZE,1);relativeFitness=abs(fitnessList)/sumfit;for i=2:POPSIZErelativeFitness(i)=relativeFitness(i-1)+relativeFitness(i); end%选择操作newPop=Select(Pop,relativeFitness);%交叉操作newPop=Xcross(newPop,VariableNum,PXOVER);%变异操作newPop=Mutation(newPop,VariableNum,PMutation,VarBound);%计算新种群适应值for i=1:POPSIZEfitnessList(i,1)=fitness(newPop(i,1:VariableNum));end%保存最好值和替换最坏值maxvalue=max(fitnessList);indexMax=find(fitnessList==maxvalue,1,'first');minvalue=min(fitnessList);indexMin=find(fitnessList==minvalue,1,'first');if Best<maxvalueBest(1,1:VariableNum)=newPop(indexMax,1:VariableNum); Best(1,VariableNum+1)=maxvalue;elsenewPop(indexMin,1:VariableNum)=Best(1,1:VariableNum); fitnessList(indexMin,1)=Best(1,VariableNum+1);end%用子代替换父代Pop=newPop;genetation=genetation+1;endBest=========================================================%选择操作function newPop=Select(Pop,Rfitness)for i=1:length(Rfitness)r=rand();index=1;for j=1:length(Rfitness)if r<=Rfitness(j,1)index=j;break;endendnewPop(i,:)=Pop(index,:);end======================================%交叉操作function newPop=Xcross(Pop,VariableNUM,CrossRate)point=1;sizePop=length(Pop);for i=0:sizePop/2Xrate=rand();if Xrate<CrossRate %如果交叉first_index=round(rand()*(sizePop-2)+1);second_index=round(rand()*(sizePop-2)+1);while first_index==second_index %排除两个个体一样的情况 second_index=round(rand()*(sizePop-2)+1);endif VariableNUM>1if VariableNUM==2point=1;elsepoint=round(rand()*(VariableNUM-2)+1);endtempOne=zeros(1,point);tempOne(1,1:point)=Pop(first_index,1:point);Pop(first_index,1:point)=Pop(second_index,1:point); Pop(second_index,1:point)=tempOne(1,1:point);endendendnewPop=zeros(size(Pop),1);newPop=Pop;====================================================%变异操作function newPop=Mutation(Pop,VariableNUM,MutationRate,bound) point=1;sizePop=length(Pop);for i=1:sizePopfor j=1:VariableNUMMrate=rand();if Mrate<MutationRate %如果发生变异Pop(i,j)= rand()*(bound(j,2)-bound(j,1))+ bound(j,1);endendendnewPop=zeros(size(Pop),1);newPop=Pop;=================================================%适应值函数或目标函数%函数 x1^2-x1*x2+x3function value=fitness(varargin)n=varargin{1,1};value=n(1,1)^2-n(1,1)*n(1,2)+n(1,3);七、结论遗传算法在处理背包问题时借助了大自然的演化过程，采用的是种群和随机搜索机制，它是一种多线索而非单线索的全局优化方法，能克服传统优化方法的缺点。