2023年7月31日发(作者：)
遗传算法解决01背包问题遗传算法求解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｝。，xi∈｛0,1｝，xi=1表⽰物品i装⼊了背包，xi =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％。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; j
2023年7月31日发(作者：)
遗传算法解决01背包问题遗传算法求解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｝。，xi∈｛0,1｝，xi=1表⽰物品i装⼊了背包，xi =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％。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; j
![[力扣]动态规划(DP)问题分类汇总](/uploads/image/0950.jpg)
发布评论