遗传算法求解01背包问题.doc

遗传算法求解01背包问题一、问题描述01背包问题属于组合优化问题的一个例子，求解01背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下：给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。01背包问题是NP问题，传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决01背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。二、遗传算法1、遗传算法的基本思想遗传算法的搜索从一个被称作种群的候选解集开始，新的种群由旧的种群中产生以期得到更好的种群。从旧种群中按照解的适应度来选择解以产生新的解；适应度越大，解被选择生成后代的机率也越大。这个从已有种群中选择双亲并产生后代的迭代过程持续到遗传算法的停止条件满足为止。2、遗传算法的基本元素。遗传算法由以下几个原素组成：由染色体组成的种群，根据适应度进行选择以及交叉产生后代。三、用遗传算法求解01背包问题1、01背包问题中染色体的表示。用向量X来表示染色体，X = x1，x2，xn。，xi0,1，xi=1表示物品i装入了背包，xi =0表示物品i未装入背包。每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的适应度。程序中定义了这样的一个结构来表示染色体：typedef structint Weight;/染色体代表的物品的总重量int Fitness;/染色体代表的物品的价值（适应度）int GeneNUMG; /用元素取值于定义域0,1的数组表示染色体。GENE;2、遗传算法求解01背包问题时用到的参数。POPSIZE：种群大小，即已知的可行解的个数。NUMG：染色体中基因的个数，即物品的总数。CAPACITY：背包的容量。MAXB：二进制表示的染色体换算之后的最大十进制整数。用于随机产生一个整数，进而转换作染色体。SIM：染色体之间的相似度阈值。当染色体之间的相似度达到阈值时，算法即停止运行。PC=1.0 ：交叉概率为100。PM=0.2 ：变异概率为20，变异可以保证种群的多样性，从而防止算法收敛于某个局部解。3、选择操作。选择操作采用了赌轮选择（Roulette-wheel selection）的方法。函数selectIndex()中包含了选择染色体的具体过程。其流程图如图1所示。图1 赌轮选择流程图程序中用一个Begin来代表当前赌轮上的指针的位置，End则用来使赌轮循环转动。用summaryBE表示当前赌轮上的指针转过的染色体的总价值。用summaryF表示当前全部染色体的价值总和。用randProb作为染色体选择的阈值。randProb为介于0,1之间的随机数。选择使summaryBE/summaryF 大于阈值randProb的染色体作为要选择的染色体。4、交叉操作程序中采用了单点交叉的策略。如下程序代码所示：for(int j=0; jpartPos ;j+)nextGenomei.Genej = parentGenomeFather.Genej;nextGenomei+POPSIZE/2.Genej = parentGenomeMother.Genej;for(;j=0.9 & pDiff=0.1)sameFlag = false;如果当前maxFitness最大的头结点满足if语句中的判断条件，则sameFlag置为真，即算法停止迭代的条件得到了满足。TraverseHashTable函数则用于遍历HASH表。算法终止的另一个条件是迭代的次数。程序中设定了算法的最大迭代次数为1000。四、实验结果。试验中用到的物品的重量和价值分别存储于以下两个数组之中。int WeightNUMG=6,9,8,8,6, 1, 10,5,7, 1;int ValueNUMG=2,20,5,4,19,14,18,8,11,6;父代种群存储于parentGenomeNUMG中，子代种群存储于nextGenomeNUMG中。程序的初始状态和结束状态如下面的表格所示：初始的种群WeightValue染色体中的基因21520010110101222300110001012240000110001122530100010110264510100110012453110001001122530100010110232510110100002648101011010025290111000000初始的HASH表头结点索引maxFitnessCountDiff单链表中的结点内容0521152:1534253:40:3291129:6451145:9481148:10231123:12251125:程序在运行了16次后停止运行。停止时的种群WeightValue染色体中的基因29780100110111297801001101112978010011011129780100110111297801001101112978010011011129780100110111286401001001112978010011011129780100110111停止