智能控制作业遗传算法求解背包问题

1、智能控制遗传算法求解背包问题16组遗传算法求解背包问题摘 要：遗传算法是在分析遗传个体进化机制基础上提出的一种新型优化算法。本论文根据0-1 背包问题的特点，提出用于求该问题的遗传算法及相关的解决方案，阐明算法的具体实现过程。通过对其他文献中仿真实例的计算和结果比较，表明应用该算法求解背包问题取得了良好的效果。该算法同样可以应用于其他组合优化题。 关键词：背包问题；遗传算法概述背包问题(knapsack problem) 是运筹学中一个典型的优化难题，有着广泛的实际应用背景，如管理中的资源分配、投资决策、预算控制等问题，并且经常作为其他问题的子问题被研究。研究背包问题的求解算法在理论上和实践中

2、都具有一定的意义。从计算复杂性理论来看，背包问题是个NP完全问题，该问题的求解方法主要有启发式算法，如贪心算法、遗传算法、粒子群算法。 以遗传算法为代表的生物进化算法建立在达尔文自然选择学说的基础上，是对生物进化过程的模拟，是人们对从自然演化过程中抽象出的概念、原则和机制的类比应用，被广泛用于解决复杂的计算问题。 其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人

3、工生命等领域。它是现代有关智能计算中的关键技术。 本文在分析遗传算法的基础上，提出了将贪婪修复方法与遗传算法相结合，构成混和遗传算法，并应用于求解经典背包问题。它是可以解决复杂问题的新方法。本论文系统的介绍背包问题的遗传算法解决方案。背包问题的数学模型背包问题的定义：我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：方法1：每个背包只能使用一次或有限次(可转化为一次)： A.求最多可放入的重量。 有一个箱子容量为v(正整数，ov20000)，同时有n

4、个物品(on30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。 l.搜索方法 procedure search(k,v:integer); 搜索第k个物品，剩余空间为v var i,j:integer; begin if v=best then exit; sn为前n个物品的重量和 if kwk then search(k+1,v-wk); search(k+1,v); end; end;2.DP ：FI,j为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。 实现:将最优化问题转化为判定性问题 f I, j = f i-1,

5、j-wi (wI=j0 then if j+now=n then inc(cj+now,aj); a:=c; end; 方法2：可重复背包 A求最多可放入的重量。 FI,j为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。 状态转移方程为 fI,j = f I-1, j wI*k (k=1. j div wI) B.求可以放入的最大价值。 进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。 *易想到：

6、 fi,j = max f i- k*wj, j-1 + k*pj (0=k=0 Then Begin t:=problemj.point+fi-problemj.time; If tfi Then fi:=t; End; Writeln(fM); End. C.求恰好装满的情况数。 求自然数n本质不同的质数和的表达式的数目。 思路一：生成每个质数的系数的排列，在一一测试，这是通法。 procedure try(dep:integer); var i,j:integer; begin cal; 此过程计算当前系数的计算结果，now为结果 if nown then exit; 剪枝 if dep

7、=l+1 then begin 生成所有系数 cal; if now=n then inc(tot); exit; end; for i:=0 to n div prdep do begin xsdep:=i; try(dep+1); xsdep:=0; end; end; 思路二：递归搜索效率较高 procedure try(dep,rest:integer); var i,j,x:integer; begin if (rest0 then for k:=1 to n div now do if j+now*k=n then inc(cj+now*k,aj); a:=c; end; main

8、 begin read(now); 读入第一个物品的重量 i:=0; ai为背包容量为i时的放法总数 while i0).*(v*c-m1);cf表示惩罚力度其他过程与加入贪婪算法的基本一致。五背包问题的遗传算法应用程序（matlab）1.将贪婪算法、遗传算法结合解决背包问题：源代码：%遗传算法解决背包问题 GA.mclc;clear;close all;%初始化物品价值value和质量cc=98 92 95 70 72 70 83 80 65 25 50 55 40 48 50 32 22 60 30 32 40 38 35 32 25 28 30 22 50 30 45 30 60 50

9、20 65 20 25 30 10 56 50 30 20 15 10 8 5 3 1 ;value=300 318 298 192 180 180 265 242 160 138 155 130 125 122 120 118 115 110 105 101 100 100 98 96 95 90 88 82 80 77 75 73 72 70 69 66 65 63 60 58 20 25 15 10 20 10 7 5 2 2;g=value./c; %价值重量比，用于贪婪算法m1=1000; %总重量约束值v = 2*rand(50,50)-1;v=hardlim(v); %v为50*

10、50随机产生的矩阵 值为0或1%贪婪算法修复解%v=greedy(v,c,g,m1);N,L = size(v); ger = 500; pc = 0.5; pm = 0.01;disp(sprintf(代数: %d,ger);disp(sprintf(种群大小: %d,N);disp(sprintf(交叉概率: %.3f,pc);disp(sprintf(变异概率: %.3f,pm);% 初始化与参数设定sol1=1; it = 1; updatef=-10; %soll为当前算出的总价值，it为代数fit =v*value;t0 = clock; %记录初始时间figure(1);hold

11、 on;while it sp(sindex) sindex=sindex+1; %寻找要选择个体的位置 end newv(i,:)=v(sindex,:); end for i=1:N v(i,:)=newv(i,:);%用选择出的个体构成的种群替代旧的种群 end % 交叉 for i=1:N cindex(i)=i; end for i=1:N %产生要配对的父代的序号；经过N次顺序调换，将原有顺序打乱，使相邻两个个体作为交叉的父代 point=unidrnd(N-i+1); temp=cindex(i); cindex(i)=cindex(i+point-1); cindex(i+po

12、int-1)=temp; end for i=1:2:N p=rand(1); if(ppc) point=unidrnd(L-1)+1;%1pointL 产生交叉点 for j=point:(L-1) %交叉 ch=v(cindex(i),j); v(cindex(i),j)=v(cindex(i+1),j); %cindex中相邻的两个为两个父代的序号 v(cindex(i+1),j)=ch; end end end % 变异 M=rand(N,L)=sol1 sol1=updatef; v(indb1,:)=updatec; end updatef=sol1; updatec=v(ind

13、b1,:); sol2,indb2 = min(fit); %indb2为适应度最小的染色体 v(indb2,:) = v(indb1,:); fit = v*value; media = mean(fit); it = it + 1; plot(it,sol1,r);end;T = etime(clock,t0);fx = sol1; P = v;disp(sprintf(程序运行时间 %2.4f,T);disp(sprintf(最优解: %.2f,fx);%* 修正函数：function v=greedy(v,c,g,m1)m n=size(v);for i=1:m label=g; la

14、bel=label.*v(i,:); if sum(v(i,:).*c)m1 %修复 while sum(v(i,:).*c)m1 min=10000; for j=1:n if label(j)=0&label(j)0).*(v*c-m1); t0 = clock; %记录初始时间figure(1);hold on;while it sp(sindex) sindex=sindex+1; %寻找要选择个体的位置 end newv(i,:)=v(sindex,:); end for i=1:N v(i,:)=newv(i,:);%用选择出的个体构成的种群替代旧的种群 end % 交叉 for

15、i=1:N cindex(i)=i; end for i=1:N %产生要配对的父代的序号；经过N次顺序调换，将原有顺序打乱，使相邻两个个体作为交叉的父代 point=unidrnd(N-i+1); temp=cindex(i); cindex(i)=cindex(i+point-1); cindex(i+point-1)=temp; end for i=1:2:N p=rand(1); if(ppc) point=unidrnd(L-1)+1;%1pointL 产生交叉点 for j=point:(L-1) %交叉 ch=v(cindex(i),j); v(cindex(i),j)=v(ci

16、ndex(i+1),j); %cindex中相邻的两个为两个父代的序号 v(cindex(i+1),j)=ch; end end end % 变异 M=rand(N,L)0).*(v*c-m1); sol1,indb1 = max(fit); %indb1为适应度最大的染色体 if updatef=sol1 sol1=updatef; v(indb1,:)=updatec; end updatef=sol1; updatec=v(indb1,:); sol2,indb2 = min(fit); %indb2为适应度最小的染色体 v(indb2,:) = v(indb1,:); fit =v*value-cf*v*value./(v*c).*(v*c-m1)0).*(v*c-m1); media = mean(fit); it = it + 1; fit2 =v*value-v*value.*(v*c-m1)0); sol3,indb3 = max(fit2); plot(it,sol3,r);end;T = etime(clock,t0);fit2 =v*value-v*value.*(v*c-m1)0);sol3,indb3 = max(fit2);fx = sol3; P = v;disp(sprintf(程序运行时间 %2.4f,T);disp(sprintf(最优解: