2023年8月1日发(作者：)

[01背包]遗传算法{最近向 学习了遗传算法他是专门研究这智能搜索这⼀⽅⾯的 ⽔平很⾼在我⽤解决"⼗滴⽔"⼩游戏时他⽤也写了 很强⼤我⽤从他那所学的遗传算法 写了⼀个01背包问题的程序}

01背包问题 ⼤家应该很熟悉是背包问题的⼀种不过值得注意的是背包问题是NPH问题(如果容量和体积是整数且有范围的话 ⾃然⽤DP可以很好的解决)对于此类没有多项式复杂度算法的问题我们⼀般⽤搜索解决对于01背包问题最为朴素的做法是 枚举每个物品取还是不取 再选取最优解不过这样的复杂度是2^n 加了可⾏性和最优性剪枝也不能优化太多这是我们就会考虑智能搜索算法此类算法很强⼤ ⽬前我只了解过遗传算法- -|||于是我就⽤遗传算法写了⼀个在理解 的教导的基础之上 我还参考了这篇论⽂

遗传算法本质是模拟达尔⽂的⽣物进化论思想将⼀个解视为⼀个⽣物 通过对这样的⽣物的种群进⾏繁衍不断地使⽣物得到进化 也就是让解得到不断的优化根据⽣物学理论 ⽣物的性状由基因控制我们仅保存DNA即遗传信息进⾏模拟并且还设计⼀个函数来根据遗传信息估计⽣物的适应度适应度帮助我们得到⽣物⽣存和繁衍的概率⽽且 由于性状之间不互相⼲扰所以遗传算法多⽤于解决组合类的最优化问题01背包 每个物品取与不取与其他物品的情况⽆关所以可以⽤遗传算法解决我们把繁衍的过程 简化为以下⼏个步骤选择 交叉 变异基于贪⼼思想 ⼜附加了修复 修正的操作具体内容上述论⽂讲的很清楚我讲⼀下⼏个注意点 ⽅便程序实现　　*实数运算有精度问题 需要多加注意　　*建议将各操作分为各个函数写　　⾼度⾯向过程的程序对与遗传算法这种多块的代码由为重要　　　　主要表现在 变量不会搞混 查错⽅便　　*⼏个基本变量千万不要搞错 最⼤繁衍代数 种群规模 遗传信息规模排序可以⽤nlogn级别的 数据⼤了优化⽐较明显另外 ⼏个参数是需要根据测试来定的⽐如 变异概率 最⼤繁衍代数 种群规模可以同过测试来不断微调 直⾄达到满意的效果

最后给出我的代码⾃以为写的⽐较优美 不过也变的很长

1 {$I+,Q+,R+,S+} 2 const maxn=200; maxp=20; maxt=500; 3 xrr=2; dsn=2; 4 pm=0.1; 5 var p,tempp:axn]of longint; 6 ans:axn]of longint; 7 c,w,v:axn]of real; 8 h:axp]of real; 9 n,m,i,j:longint; 10 max:real; 11 procedure revise(x:longint; y:real); 12 var i,j,t,z:longint; 13 temp:axn]of longint; 14 begin 15 t:=0; 16 for i:=1 to n do 17 if p[x][i]=0 18 then begin 19 inc(t); 20 temp[t]:=i; 21 end; 22 for i:=1 to t-1 do 23 for j:=i+1 to t do 24 if c[temp[i]]m then p[x][temp[i]]:=0; 38 end; 39 procedure repair(x:longint; y:real); 40 var i,j,t,z:longint; 41 temp:axn]of longint; 42 begin 43 t:=0; 44 for i:=1 to n do 45 if p[x][i]=1 46 then begin 47 inc(t); 48 temp[t]:=i; 49 end; 50 for i:=1 to t-1 do 51 for j:=i+1 to t do 52 if c[temp[i]]>c[temp[j]] 53 then begin 54 z:=temp[i]; 55 temp[i]:=temp[j]; 56 temp[j]:=z; 57 end; 58 i:=0; 59 while (im) do 60 begin 61 inc(i); 62 p[x][temp[i]]:=0; 63 y:=y-w[temp[i]]; 64 end; 65 end; 66 procedure create; 67 var i,j:longint; 68 t:real; 69 begin 70 for i:=1 to maxp do 71 begin 72 t:=0; 73 for j:=1 to n do 74 begin 75 p[i][j]:=random(2); 76 t:=t+w[j]*p[i][j]; 77 end; 78 if tm then repair(i,t); 80 end; 81 end; 82 procedure propagate; 83 var i,j,x,y,t:longint; 84 k,s,tr,tr0,r:real; 85 f,temp:axn]of longint; 86 begin 87 for i:=1 to maxp do h[i]:=0; 88 for i:=1 to maxp do 89 for j:=1 to n do 90 h[i]:=h[i]+v[j]*p[i][j]; 91 for i:=1 to maxp-1 do 92 for j:=i+1 to maxp do 93 if h[i]m then repair(i,s);132 end;133 t:=dsn;134 while tm then repair(t,s);164 s:=0;165 for i:=1 to n do s:=s+v[i]*p[t][i];166 if s>max167 then begin168 max:=s;169 move(p[t],ans,sizeof(p[t]));170 end;171 end;172 end;173 begin174 randomize;175 assign(input,''); reset(input);176 assign(output,''); rewrite(output);177 readln(n,m);178 for i:=1 to n do179 begin180 read(w[i]); read(v[i]);181 c[i]:=v[i]/w[i];182 end;183 create;184 max:=0;185 for i:=1 to maxt do186 propagate;187 writeln(max:0:4);188 for i:=1 to n do189 write(ans[i]);190 writeln;191 close(input); close(output);192 end.193

遗传算法 是⽣物学与算法的强⼤结合！

Bob Han 原创 转载请注明出处

2023年8月1日发(作者：)

[01背包]遗传算法{最近向 学习了遗传算法他是专门研究这智能搜索这⼀⽅⾯的 ⽔平很⾼在我⽤解决"⼗滴⽔"⼩游戏时他⽤也写了 很强⼤我⽤从他那所学的遗传算法 写了⼀个01背包问题的程序}

01背包问题 ⼤家应该很熟悉是背包问题的⼀种不过值得注意的是背包问题是NPH问题(如果容量和体积是整数且有范围的话 ⾃然⽤DP可以很好的解决)对于此类没有多项式复杂度算法的问题我们⼀般⽤搜索解决对于01背包问题最为朴素的做法是 枚举每个物品取还是不取 再选取最优解不过这样的复杂度是2^n 加了可⾏性和最优性剪枝也不能优化太多这是我们就会考虑智能搜索算法此类算法很强⼤ ⽬前我只了解过遗传算法- -|||于是我就⽤遗传算法写了⼀个在理解 的教导的基础之上 我还参考了这篇论⽂

遗传算法本质是模拟达尔⽂的⽣物进化论思想将⼀个解视为⼀个⽣物 通过对这样的⽣物的种群进⾏繁衍不断地使⽣物得到进化 也就是让解得到不断的优化根据⽣物学理论 ⽣物的性状由基因控制我们仅保存DNA即遗传信息进⾏模拟并且还设计⼀个函数来根据遗传信息估计⽣物的适应度适应度帮助我们得到⽣物⽣存和繁衍的概率⽽且 由于性状之间不互相⼲扰所以遗传算法多⽤于解决组合类的最优化问题01背包 每个物品取与不取与其他物品的情况⽆关所以可以⽤遗传算法解决我们把繁衍的过程 简化为以下⼏个步骤选择 交叉 变异基于贪⼼思想 ⼜附加了修复 修正的操作具体内容上述论⽂讲的很清楚我讲⼀下⼏个注意点 ⽅便程序实现　　*实数运算有精度问题 需要多加注意　　*建议将各操作分为各个函数写　　⾼度⾯向过程的程序对与遗传算法这种多块的代码由为重要　　　　主要表现在 变量不会搞混 查错⽅便　　*⼏个基本变量千万不要搞错 最⼤繁衍代数 种群规模 遗传信息规模排序可以⽤nlogn级别的 数据⼤了优化⽐较明显另外 ⼏个参数是需要根据测试来定的⽐如 变异概率 最⼤繁衍代数 种群规模可以同过测试来不断微调 直⾄达到满意的效果

最后给出我的代码⾃以为写的⽐较优美 不过也变的很长

1 {$I+,Q+,R+,S+} 2 const maxn=200; maxp=20; maxt=500; 3 xrr=2; dsn=2; 4 pm=0.1; 5 var p,tempp:axn]of longint; 6 ans:axn]of longint; 7 c,w,v:axn]of real; 8 h:axp]of real; 9 n,m,i,j:longint; 10 max:real; 11 procedure revise(x:longint; y:real); 12 var i,j,t,z:longint; 13 temp:axn]of longint; 14 begin 15 t:=0; 16 for i:=1 to n do 17 if p[x][i]=0 18 then begin 19 inc(t); 20 temp[t]:=i; 21 end; 22 for i:=1 to t-1 do 23 for j:=i+1 to t do 24 if c[temp[i]]m then p[x][temp[i]]:=0; 38 end; 39 procedure repair(x:longint; y:real); 40 var i,j,t,z:longint; 41 temp:axn]of longint; 42 begin 43 t:=0; 44 for i:=1 to n do 45 if p[x][i]=1 46 then begin 47 inc(t); 48 temp[t]:=i; 49 end; 50 for i:=1 to t-1 do 51 for j:=i+1 to t do 52 if c[temp[i]]>c[temp[j]] 53 then begin 54 z:=temp[i]; 55 temp[i]:=temp[j]; 56 temp[j]:=z; 57 end; 58 i:=0; 59 while (im) do 60 begin 61 inc(i); 62 p[x][temp[i]]:=0; 63 y:=y-w[temp[i]]; 64 end; 65 end; 66 procedure create; 67 var i,j:longint; 68 t:real; 69 begin 70 for i:=1 to maxp do 71 begin 72 t:=0; 73 for j:=1 to n do 74 begin 75 p[i][j]:=random(2); 76 t:=t+w[j]*p[i][j]; 77 end; 78 if tm then repair(i,t); 80 end; 81 end; 82 procedure propagate; 83 var i,j,x,y,t:longint; 84 k,s,tr,tr0,r:real; 85 f,temp:axn]of longint; 86 begin 87 for i:=1 to maxp do h[i]:=0; 88 for i:=1 to maxp do 89 for j:=1 to n do 90 h[i]:=h[i]+v[j]*p[i][j]; 91 for i:=1 to maxp-1 do 92 for j:=i+1 to maxp do 93 if h[i]m then repair(i,s);132 end;133 t:=dsn;134 while tm then repair(t,s);164 s:=0;165 for i:=1 to n do s:=s+v[i]*p[t][i];166 if s>max167 then begin168 max:=s;169 move(p[t],ans,sizeof(p[t]));170 end;171 end;172 end;173 begin174 randomize;175 assign(input,''); reset(input);176 assign(output,''); rewrite(output);177 readln(n,m);178 for i:=1 to n do179 begin180 read(w[i]); read(v[i]);181 c[i]:=v[i]/w[i];182 end;183 create;184 max:=0;185 for i:=1 to maxt do186 propagate;187 writeln(max:0:4);188 for i:=1 to n do189 write(ans[i]);190 writeln;191 close(input); close(output);192 end.193

遗传算法 是⽣物学与算法的强⼤结合！

Bob Han 原创 转载请注明出处