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

智能控制

遗传算法求解背包问题

——16组遗传算法求解背包问题

摘 要：遗传算法是在分析遗传个体进化机制基础上提出的一种新型优化算法。本论文根据0-1 背包问题的特点，提出用于求该问题的遗传算法及相关的解决方案，阐明算法的具体实现过程。通过对其他文献中仿真实例的计算和结果比较，表明应用该算法求解背包问题取得了良好的效果。该算法同样可以应用于其他组合优化题。

关键词：背包问题；遗传算法

一． 概述

背包问题(knapsack problem) 是运筹学中一个典型的优化难题，有着广泛的实际应用背景，如管理中的资源分配、投资决策、预算控制等问题，并且经常作为其他问题的子问题被研究。研究背包问题的求解算法在理论上和实践中都具有一定的意义。从计算复杂性理论来看，背包问题是个NP 完全问题，该问题的求解方法主要有启发式算法，如贪心算法、遗传算法、粒子群算法。

以遗传算法为代表的生物进化算法建立在达尔文自然选择学说的基础上，是对生物进化过程的模拟，是人们对从自然演化过程中抽象出的概念、原则和机制的类比应用，被广泛用于解决复杂的计算问题。 其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。

本文在分析遗传算法的基础上，提出了将贪婪修复方法与遗传算法相结合，构成混和遗传算法，并应用于求解经典背包问题。它是可以解决复杂问题的新方法。本论文系统的介绍背包问题的遗传算法解决方案。

二． 背包问题的数学模型

背包问题的定义：

我们有n 种物品，物品j 的重量为wj ，价格为pj 。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W 。

如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。可以用公式表示为：

1

max n

j j j imize p x = (1)∑

{}1

,0,1n j j j j subject to x w x ω= ≤ ∈ (2)∑

方法1：每个背包只能使用一次或有限次(可转化为一次)：

A.求最多可放入的重量。

有一个箱子容量为v(正整数，o ≤v ≤20000)，同时有n 个物品(o ≤n ≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。

l.搜索方法

procedure search(k,v:integer); {搜索第k 个物品，剩余空间为v}

var i,j:integer;

begin

if v

if v-(s[n]-s[k-1])>=best then exit; {s[n]为前n个物品的重量和}

if k<=n then begin

if v>w[k] then search(k+1,v-w[k]);

search(k+1,v);

end;

end;

2.DP ：

F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。实现:将最优化问题转化为判定性问题

f [I, j] = f [ i-1, j-w[i] ] (w[I]<=j<=v) 边界：f[0,0]:=true.

For I:=1 to n do

For j:=w[I] to v do F[I,j]:=f[I-1,j-w[I]];

优化：当前状态只与前一阶段状态有关，可降至一维。

F[0]:=true;

For I:=1 to n do begin

F1:=f;

For j:=w[I] to v do

If f[j-w[I]] then f1[j]:=true;

F:=f1;

End;

B.求可以放入的最大价值。

F[I,j] 为容量为I时取前j个背包所能获得的最大价值。

F [i,j] = max { f [ i – w [ j ], j-1] + p [ j ], f[ i,j-1] }

C.求恰好装满的情况数。

DP:

Procedure update;

var j,k:integer;

begin

c:=a;

for j:=0 to n do

if a[j]>0 then

if j+now<=n then inc(c[j+now],a[j]);

a:=c;

end;

方法2：可重复背包

A求最多可放入的重量。

F[I,j]为前i个物品中选择若干个放入使其体积正好为j的标志，为布尔型。

状态转移方程为

f[I,j] = f [ I-1, j – w[I]*k ] (k=1.. j div w[I])

B.求可以放入的最大价值。

进行一次竞赛，总时间T固定，有若干种可选择的题目，每种题目可选入的数量不限，每种题目有一个ti（解答此题所需的时间）和一个si（解答此题所得的分数），现要选择若干题目，使解这些题的总时间在T以内的前提下，所得的总分最大，求最大的得分。

*易想到：

f[i,j] = max { f [i- k*w[j], j-1] + k*p[j] } (0<=k<= i div w[j])

其中f[i,j]表示容量为i时取前j种背包所能达到的最大值。

*实现：

Begin

FillChar(f,SizeOf(f),0);

For i:=1 To M Do

For j:=1 To N Do

If i-problem[j].time>=0 Then

Begin

t:=problem[j].point+f[i-problem[j].time];

If t>f[i] Then f[i]:=t;

End;

Writeln(f[M]);

End.

C.求恰好装满的情况数。

求自然数n本质不同的质数和的表达式的数目。

思路一：生成每个质数的系数的排列，在一一测试，这是通法。

procedure try(dep:integer);

var i,j:integer;

begin

cal; {此过程计算当前系数的计算结果，now为结果}

if now>n then exit; {剪枝}

if dep=l+1 then begin {生成所有系数}

cal;

if now=n then inc(tot);

exit;

end;

for i:=0 to n div pr[dep] do begin

xs[dep]:=i;

try(dep+1);

xs[dep]:=0;

end;

end;

本文来源：https://www.bwwdw.com/article/186q.html