遗传算法解决背包问题

遗传算法可以认为是一种启发式算法，根据达尔文的进化学说中“优胜劣汰”、“适者生存”的观点来解决一些实际生活中难以解决的问题。其实简单来说，遗传算法所做的事情就是“随机”生成一些可行解（不是最优解），然后随机一段时间之后找到局部最优解。但是这个“随机”的过程模拟了自然界中的进化规律，也是“更优解”更容易生存，“更优解”与“更优解”的结合能够生成“更更优解”。不断重复这个结合的过程，最终可以得到局部最优解，甚至可能是全局最优解。

算法具体描述可见： 一文读懂遗传算法工作原理 如何理解遗传算法

在此我给出有遗传算法求解背包问题的思路。

问题描述

背包问题

为了简单起见，我此处只介绍01背包问题。当然其实01背包问题用动态规划很容易就能实现。但遗传算法的意义却绝不是动态规划可以代替的。动态规划只能解决一些一定有明确解的问题，但事实上现在主流问题很少是有明确解的，大多数都是优化问题，也就是只能寻找局部最优解，并认为局部最优解已经足够好了。

import random import copy import codecs class Genetic_alg: def __init__(self, weights, support_points, threshold): self.weights = weights self.support_points = support_points self.threshold = threshold self.size = len(weights) self.populations = [] def construct_populations(self, times): local_populations = [] local_populations.append([0 for i in range(self.size)]) for k in range(times): chromosome = [] for i in range(self.size): chromosome.append(random.randint(0, 1)) local_populations.append(chromosome) self.selection(local_populations) def Mating(self, times=10): local_chromosomes = [] self.populations.sort(key=lambda each: self.compute_points(each), reverse=True) total_points = 0 for each in self.populations: total_points += self.compute_points(each) for i in range(times): father = random.randint(0, total_points) mother = random.randint(0, total_points) father_chromosome, mother_chromosome = self.Crossover(father, mother) local_chromosomes.append(father_chromosome) local_chromosomes.append(mother_chromosome) self.selection(local_chromosomes) def Crossover(self, father, mother): father_chromosome = copy.deepcopy(self.populations[-1]) mother_chromosome = copy.deepcopy(self.populations[-1]) # bug for each in self.populations: if self.compute_points(each) > father: father_chromosome = each else: father -= self.compute_points(each) for each in self.populations: if self.compute_points(each) > mother: mother_chromosome = each else: mother -= self.compute_points(each) mating_points = random.randint(0, self.size - 1) while mating_points < self.size: father_chromosome[mating_points], mother_chromosome[mating_points] \ = mother_chromosome[mating_points], father_chromosome[mating_points] mating_points += 1 return self.Mutation(father_chromosome, 20), self.Mutation(mother_chromosome, 20) def Mutation(self, chromosome, times=1): tmp = copy.deepcopy(chromosome) for i in range(times): mutation_point = random.randint(0, self.size - 1) tmp[mutation_point] = 1 - tmp[mutation_point] return tmp def selection(self, chromosomes): local_chromosomes = set() for each in chromosomes: tmp = self.compute_weights(each) if tmp <= self.threshold: local_chromosomes.add(' '.join([str(value) for value in each])) for each in local_chromosomes: self.populations.append([int(value) for value in each.split(' ')]) def compute_weights(self, chromosome): tmp = 0 for i in range(len(chromosome)): if chromosome[i] == 1: tmp += self.weights[i] return tmp def compute_points(self, chromosome): tmp = 0 for i in range(len(chromosome)): if chromosome[i] == 1: tmp += self.support_points[i] return tmp def final_result(self): self.populations.sort(key=lambda each: self.compute_points(each), reverse=True) return self.populations[0] def evaluation(weights, points, threshold): result = [0 for i in range(threshold + 1)] size = len(weights) for i in range(size): if i == 0: continue j = threshold while j > 0: if j >= weights[i]: result[j] = max(result[j], result[j - weights[i]] + points[i]) j -= 1 return max(result) if __name__ == '__main__': with codecs.open('./test.txt', 'r') as f: first = 1 weights = [] points = [] weights.append(0) points.append(0) threshold = 0 for each in f.readlines(): each = each.strip('\n') array = each.split(' ') if first: threshold = int(array[0]) first = 0 else: weights.append(int(array[0])) points.append(int(array[1])) alg = Genetic_alg(weights, points, threshold) alg.construct_populations(1000) alg.Mating(10000) print(alg.final_result()) print('Points:' + str(alg.compute_points(alg.final_result()))) print('Weights:' + str(alg.compute_weights(alg.final_result()))) print(points) print(evaluation(weights, points, threshold))

测试案例：

600 30 95 89 75 59 23 19 73 43 50 100 22 72 6 44 57 16 89 7 98 64 95 89 75 59 23 19 73 43 50 100 22 72 6 44 57 16 89 7 98 64 95 89 75 59 23 19 73 43 50 100 22 72 6 44 57 16 89 7 98 64

总结

在测试过程中，我发现事实上遗传算法并没有那么容易实现。就算是对于有唯一解的基础背包问题，也很难保证有正确解。仔细回顾算法的设计其实很容易发现问题的。

在最开始构造基础population的时候已经不简单了，特别是对于有很多数据的情况，你甚至很难可以随机构造一种情况使得可以满足给定背包重量大小的条件。于是就变成了在一堆不怎么好的sample中，期望通过crossover构造一个较好的sample。这其实是非常不容易的。

但我其实觉得，这个算法是可行的，但可能需要比较长的时间。我通过增加mutation的概率来使得一些特别的sample能够保留下来，并且能够繁衍。而且我觉得只要进过一段时间后，就可以得到相当不错的结果。

但是正如前文所说的，遗传算法不是用于求解全局最优解的（虽然如果有全局最优解的话，一般都能够达到），而且用于求解局部最优解的，所以我们可以认为遗传算法得出的结果是“足够好的”，事实上，也确实是如此。