背包问题的算法研究与实现本科毕业论文 精品

bool LChild; //左儿子结点标志 };

template class HeapNode {

friend Knap; public:

operator Typep () const {return uprofit;} private:

Typep uprofit, //结点的价值上界 profit; //结点所相应的价值 Typew weight; //结点所相应的重量

int level; //活结点在子集树中所处的层序号 bbnode *ptr; //指向活结点在子集树中相应结点的指针 }；

template class Knap {

friend Typep Knapsack(Typep *,Typew *,Typew,int,int *); public:

Typep MaxKnapsack(); private:

MaxHeap>*H; Typep Bound(int i);

void addLiveNode(Typep up,Typep cp,Typep cw,bool ch,int level); bbnode *E; //指向扩展结点的指针 Typew c; //背包容量 int n; //物品总数 Typew *w; //物品重量数组 Typep *p; //物品价值数组 Typew cw; //当前装包重量

14

Typep cp; //当前装包价值 int * bestx; //最优解 };

template Typep Knap::MaxKnapsack()

{//优先队列式分支限界法，返回最大价值，bestx返回最优解 //定义最大堆的容量为1000

H=new MaxHeap>(1000); //为bestx分配存储空间 bestx=new int[n+1]; //初始化 int i=1;

E=0;

cw =cp =0;

Typep bestp =0; //当前最优值 Typep up =Bound(1); //价值上界 //搜索子集空间树

while(i!=n+1){// 非叶结点 //检查当前扩展结点的左儿子结点 Typew wt =cw +w[i];

if(wt<=c){//左儿子结点为可行结点 if(cp+p[i]>bestp)bestp=cp+p[i];

AddliveNode(up,cp+p[i],cw+w[i],ture,i+1);} up =Bound(i+1);

//检查当前扩展结点的右儿子结点 if(up>=bestp)//右子树可能含最优解 AddLiveNode(up,cp,cw,false,i+1); //取下一扩展结点 HeapNodeN; H->deleteMax(N);

15

E=N.ptr; cw=N.weight; cp=N.profit; up=N.uprofit; i=N.level; }

//构造当前最优解 for(int j=n;j>0;j--){ bestx[j]=E->LChild; E=E->parent; }

return cp; }[1]

2.4 0-1背包问题在遗传算法中的实现

2.4.1遗传算法的基本原理与分析

遗传算法作为一种解决复杂问题的有效方法是在1975年首次由美国密西根大学的Hol-land教授和他的同事们借鉴生物界自然选择和进化机制基础之上提出的，它是基于生物进化中自然选择、适者生存和物种遗传思想的一种搜索算法。它将问题的每一个可能解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应值。算法将根据适应值进行寻优过程。遗传算法的寻优过程是通过选择、杂交和变异等遗传算子来具体实现的，它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的每一个点，从而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Holland提出的模式定理和隐式并行性得以解释。在遗传算法中，定义长度较短、低阶且适应值超过平均适应值的模式在群体中数目的期望值按指数递增，这个结论成为遗传算法的基本定理。

遗传算法可看成是在一个定义域为L维的向量空问B。中有一适应度函数，依其适应度大小，随机进行选择、交叉和变异操作来求此函数的最大值，即将遗

16

传算法看成是在某个空间进行求最大值的搜索技术。在操作中，新点主要是由交叉操作产生。传统的交叉算子是随机操作，后代简单地继承了“父母”的一部分基因，并不能保证子代的性能优于父辈，而且以这种方式点对点的搜索范围有限，可能会忽略邻域内更好的点而使结果收敛于局部最优。 2.4.2 0-1背包问题的实现

(1) 编码方案: 用遗传算法来求解0-1背包问题，一种很自然的编码方案是将待求解的各量X表示成长为n的二进制字符串X[i],j=1,2,?n,x[i]=1表示物体j 放人背包，x[j]表示物体j放入背包。

(2) 适应度函数的设计: 基于上述编码，按照所提出的罚函数 处理约束条件的方法构造背包问题的适应度函数 (X):

(X)=

-

这里，对于所有满足条?C的可行解X，惩罚函数Va(X)=0

惩罚函数可以使用对数函数，线性函数，二次函数等，分别随侵犯的程度增加而顺序采用。

(3) 选择操作：根据选择概率选择染色体，将上述的个体作为第0代。对于每个染色体，计算累积概率Qi，从区间(0, Qi) 种产生一个随机数r，若Qi -1

(4) 交叉操作：判断染色体是否为活的染色体，若为活的染色体，则将染色体进行交叉，一般采用单点交叉方式。

(5) 变异操作：染色体变异采用位点变异的方式。使变异后的适应度至少大于等于原适应度，否则重新选择变异位进行变异，如此重复若干次，若适应度值没有提高，则变异失败。

(6) 当某代得到的结果满足要求或当前代数等于结束代数时算法结束得到结果，否则重复上述步骤(3)、(4) [7]。 则主要算法描述为：

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

if v

17