遗传算法求解 01 背包问题
一、问题描述
01 背包问题属于组合优化问题的一个例子，求解 01 背包问题的过程可以被视作在很多可行解当
中求解一个最优解。01 背包问题的一般描述如下：
给定 n 个物品和一个背包，物品 i 的重量为 W
i
，其价值为 V
i
，背包的容量为 C。选择合适的物品
装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于
背包的容量 C。在选择装入背包的物品时，对每种物品 i 只有两种选择：装入背包或者不装入背包，即
只能将物品 i 装入背包一次。称此类问题为 0/1 背包问题。
01 背包问题是 NP 问题，传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法
不能有效地解决 01 背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索
最优（或次优）解的有效算法。
二、遗传算法
1、遗传算法的基本思想
遗传算法的搜索从一个被称作种群的候选解集开始，新的种群由旧的种群中产生以期得到更好的
种群。从旧种群中按照解的适应度来选择解以产生新的解；适应度越大，解被选择生成后代的机率也
越大。这个从已有种群中选择双亲并产生后代的迭代过程持续到遗传算法的停止条件满足为止。
2、遗传算法的基本元素。
遗传算法由以下几个原素组成：由染色体组成的种群，根据适应度进行选择以及交叉产生后代。
三、用遗传算法求解 01 背包问题
1、01 背包问题中染色体的表示。
用向量 X 来表示染色体，
X = ｛x
1
，
x
2
，……，x
n
｝。，x
i
∈｛0,1｝，
x
i
=1 表示物品 i 装入了背包，x
i
=0 表示物品 i 未装入背包。
每个染色体对应其当前装入背包的物品的总价值和总重量。背包中物品的中价值代表了该物品的
适应度。
程序中定义了这样的一个结构来表示染色体：
typedef struct{
int Weight; //染色体代表的物品的总重量
int Fitness; //染色体代表的物品的价值（适应度）
int Gene[NUMG]; //用元素取值于定义域｛0,1｝的数组表示染色体。
}GENE;
2、遗传算法求解 01 背包问题时用到的参数。
POPSIZE：种群大小，即已知的可行解的个数。
NUMG：染色体中基因的个数，即物品的总数。
CAPACITY：背包的容量。
MAXB：二进制表示的染色体换算之后的最大十进制整数。用于随机产生一个整数，进而转换作
染色体。
SIM：染色体之间的相似度阈值。当染色体之间的相似度达到阈值时，算法即停止运行。
PC=1.0 ：交叉概率为 100％。
评论0