1 import numpy 2 import matplotlib.pyplot as plt 3 4 5 data = numpy.array([[77, 92], 6 [22, 22], 7 [29, 87], 8 [50, 46], 9 [99, 90]]) 10 11 12 class GA(object): 13 """ 14 遗传算法解决0-1背包问题 15 """ 16 17 def __init__(self, length, number, iter_number): 18 """ 19 参数初始化 20 :param length: 5 21 :param number: 300 22 :param iter_number: 300 23 """ 24 self.length = length # 确定染色体编码长度 25 self.number = number # 确定初始化种群数量 26 self.iteration = iter_number # 设置迭代次数 27 self.bag_capacity = 100 # 背包容量 28 29 self.retain_rate = 0.2 # 每一代精英选择出前20% 30 self.random_selection_rate = 0.5 # 对于不是前20%的，有0.5的概率可以进行繁殖 31 self.mutation_rate = 0.01 # 变异概率0.01 32 33 def initial_population(self): 34 """ 35 种群初始化， 36 37 :return: 返回种群集合 38 """ 39 init_population = numpy.random.randint(low=0, high=2, size=[self.length, self.number], dtype=numpy.int16) 40 return init_population 41 42 def weight_price(self, chromosome): 43 """ 44 计算累计重量和累计价格 45 :param chromosome: 46 :return:返回每一个个体的累计重量和价格 47 """ 48 w_accumulation = 0 49 p_accumulation = 0 50 for i in range(len(chromosome)): 51 52 w = chromosome[i]*data[i][0] 53 p = chromosome[i]*data[i][1] 54 w_accumulation = w + w_accumulation 55 p_accumulation = p + p_accumulation 56 57 return w_accumulation, p_accumulation 58 59 def fitness_function(self, chromosome): 60 """ 61 计算适应度函数，一般来说，背包的价值越高越好，但是 62 当重量超过100时，适应度函数=0 63 :param chromosome: 64 :return: 65 """ 66 67 weight, price = self.weight_price(chromosome) 68 if weight > self.bag_capacity: 69 fitness = 0 70 else: 71 fitness = price 72 73 return fitness 74 75 def fitness_average(self, init_population): 76 """ 77 求出这个种群的平均适应度，才能知道种群已经进化好了 78 :return:返回的是一个种群的平均适应度 79 """ 80 f_accumulation = 0 81 for z in range(init_population.shape[1]): 82 f_tem = self.fitness_function(init_population[:, z]) 83 f_accumulation = f_accumulation + f_tem 84 f_accumulation = f_accumulation/init_population.shape[1] 85 return f_accumulation 86 87 def selection(self, init_population): 88 """ 89 选择 90 :param init_population: 91 :return: 返回选择后的父代，数量是不定的 92 """ 93 sort_population = numpy.array([[], [], [], [], [], []]) # 生成一个排序后的种群列表，暂时为空 94 for i in range(init_population.shape[1]): 95 96 x1 = init_population[:, i] 97 # print('打印x1', x1) 98 x2 = self.fitness_function(x1) 99 x = numpy.r_[x1, x2] 100 # print('打印x', x) 101 sort_population = numpy.c_[sort_population, x] 102 103 sort_population = sort_population.T[numpy.lexsort(sort_population)].T # 联合排序，从小到大排列 104 105 # print('排序后长度', sort_population.shape[1]) 106 print(sort_population) 107 108 # 选出适应性强的个体，精英选择 109 retain_length = sort_population.shape[1]*self.retain_rate 110 111 parents = numpy.array([[], [], [], [], [], []]) # 生成一个父代列表，暂时为空 112 for j in range(int(retain_length)): 113 y1 = sort_population[:, -(j+1)] 114 parents = numpy.c_[parents, y1] 115 116 # print(parents.shape[1]) 117 118 rest = sort_population.shape[1] - retain_length # 精英选择后剩下的个体数 119 for q in range(int(rest)): 120 121 if numpy.random.random() < self.random_selection_rate: 122 y2 = sort_population[:, q] 123 parents = numpy.c_[parents, y2] 124 125 parents = numpy.delete(parents, -1, axis=0) # 删除最后一行，删除了f值 126 # print('打印选择后的个体数') 127 # print(parents.shape[0]) 128 129 parents = numpy.array(parents, dtype=numpy.int16) 130 131 return parents 132 133 def crossover(self, parents): 134 """ 135 交叉生成子代，和初始化的种群数量一致 136 :param parents: 137 :return:返回子代 138 """ 139 children = numpy.array([[], [], [], [], []]) # 子列表初始化 140 141 while children.shape[1] < self.number: 142 father = numpy.random.randint(0, parents.shape[1] - 1) 143 mother = numpy.random.randint(0, parents.shape[1] - 1) 144 if father != mother: 145 # 随机选取交叉点 146 cross_point = numpy.random.randint(0, self.length) 147 # 生成掩码，方便位操作 148 mark = 0 149 for i in range(cross_point): 150 mark |= (1 << i) 151 152 father = parents[:, father] 153 # print(father) 154 mother = parents[:, mother] 155 156 # 子代将获得父亲在交叉点前的基因和母亲在交叉点后（包括交叉点）的基因 157 child = ((father & mark) | (mother & ~mark)) & ((1 << self.length) - 1) 158 159 children = numpy.c_[children, child] 160 161 # 经过繁殖后，子代的数量与原始种群数量相等，在这里可以更新种群。 162 # print('子代数量', children.shape[1]) 163 # print(children.dtype) 164 children = numpy.array(children, dtype=numpy.int16) 165 return children 166 167 def mutation(self, children): 168 """ 169 变异 170 171 :return: 172 """ 173 for i in range(children.shape[1]): 174 175 if numpy.random.random() < self.mutation_rate: 176 j = numpy.random.randint(0, self.length - 1) # s随机产生变异位置 177 children[:, i] ^= 1 << j # 产生变异 178 children = numpy.array(children, dtype=numpy.int16) 179 return children 180 181 def plot_figure(self, iter_plot, f_plot, f_set_plot): 182 """ 183 画出迭代次数和平均适应度曲线图 184 画出迭代次数和每一步迭代最大值图 185 :return: 186 """ 187 plt.figure() 188 189 ax1 = plt.subplot(121) 190 ax2 = plt.subplot(122) 191 192 plt.sca(ax1) 193 plt.plot(iter_plot, f_plot) 194 plt.ylim(0, 140) # 设置y轴范围 195 196 plt.sca(ax2) 197 plt.plot(iter_plot, f_set_plot) 198 plt.ylim(0, 140) # 设置y轴范围 199 plt.show() 200 201 def main(self): 202 """ 203 main函数,用来进化 204 对当前种群依次进行选择、交叉并生成新一代种群，然后对新一代种群进行变异 205 :return: 206 """ 207 init_population = self.initial_population() 208 # print(init_population) 209 210 iter_plot = [] 211 f_plot = [] 212 iteration = 0 213 214 f_set_plot = [] 215 216 while iteration < self.iteration: # 设置迭代次数300 217 218 parents = self.selection(init_population) # 选择后的父代 219 children = self.crossover(parents) 220 mutation_children = self.mutation(children) 221 222 init_population = mutation_children 223 224 f_set = [] # 求出每一步迭代的最大值 225 for init in range(init_population.shape[1]): 226 f_set_tem = self.fitness_function(init_population[:, init]) 227 f_set.append(f_set_tem) 228 229 f_set = max(f_set) 230 231 f_set_plot.append(f_set) 232 233 iter_plot.append(iteration) 234 iteration = iteration+1 235 print("第%s进化得如何******************************************" % iteration) 236 f_average = self.fitness_average(init_population) 237 f_plot.append(f_average) 238 print(f_set) 239 # f_accumulation = f_accumulation + f 240 # f_print = f_accumulation/(iteration + 1) 241 # print(f_print) 242 self.plot_figure(iter_plot, f_plot, f_set_plot) 243 244 245 if __name__ == '__main__': 246 g1 = GA(5, 300, 100) 247 g1.main()
