遗传算法的简单实现(1):求解函数最大值

刚刚了解了一点遗传算法的原理,参照了网上的一篇入门教程自己实现了一下。

参数和操作： 染色体(表示方法)，染色体长度,变异率,交叉率,最大的总群个体数,评估函数,目标函数(在这里与评估函数一致)。

对函数

搜索最大值。

实现思路:将染色体表示为x,y的值(以bit的形式来表示),进行选择，交叉,变异。同时为了保证解具有较好的全局性,我们每次都选择最好的一个解来替代下一代的最差的一个解,同时提高变异率增加多样性。

变异手段就是对某一个bit进行取反,随着变异率的提高,每一代最差个体的情况曲线变得比较稳定。

交叉手段就是对某两个互异的染色体交换部分。

class Person: def __init__(self,attr,chrom_size,interval): self.attr = attr self.interval = interval self.chrom_size = chrom_size self.fitness = self.evaluate(self.map_into(attr[0]),self.map_into(attr[1])) def map_into(self,x): d = self.interval[1] - self.interval[0] n = float (2 ** self.chrom_size -1) return (self.interval[0] + x * d / n) def evaluate(self,x,y):# to compute the fitness n = lambda x, y: math.sin (math.sqrt (x*x + y*y)) ** 2 - 0.5 d = lambda x, y: (1 + 0.001 * (x*x + y*y)) ** 2 func = lambda x, y: 0.5 - n (x, y)/d (x, y) return func (x, y) import random import math class Population: def __init__(self,max_num,capacity,mutation_rate,cross_rate,chrom_size): self.current_generation = [] self.next_generation = [] self.max_generations = max_num self.size = capacity self.mutation_rate = mutation_rate self.cross_rate = cross_rate self.chrom_size = chrom_size self.interval = (-10,10) self.select_prob = [] self.best = None size = 2**self.chrom_size - 1 for i in range(capacity): x,y = random.randint(0,size),random.randint(0,size) one = Person((x,y),self.chrom_size,self.interval) self.current_generation.append(one) def generate_selectprob(self): prob = 0 self.select_prob = [] total = sum(p.fitness for p in self.current_generation) for each in self.current_generation: prob += each.fitness/total self.select_prob.append(prob) def select(self): t = random.random() i = next(i for i,p in enumerate(self.select_prob) if t < p) return self.current_generation[i] def cross(self,chrom1,chrom2): #now:swap only one part # to do:swap several part of chroms p = random.random() if chrom1!=chrom2 and p < self.cross_rate: pos = random.randint(0,self.chrom_size-1) mask1,mask2 = (2**self.chrom_size-1)<<pos,2**pos-1 t1,t2 = chrom1&mask1,chrom2&mask1 r1,r2 = chrom1&mask2,chrom2&mask2 chrom1,chrom2 = t1+r2,t2+r1 return chrom1,chrom2 def mutate(self,chrom): p = random.random() if p<self.mutation_rate: pos = random.randint(1,self.chrom_size) mask1 = 1<<(pos-1) chrom = chrom^mask1 return chrom def evolve(self): self.generate_selectprob() num = 0 while num < self.size: #cross indv1,indv2 = self.select(),self.select() indv1_x,indv2_x = self.cross(indv1.attr[0],indv2.attr[0]) indv1_y,indv2_y = self.cross(indv1.attr[1],indv2.attr[1]) #mutation tmp = [indv1_x,indv1_y,indv2_x,indv2_y] [indv1_x,indv1_y,indv2_x,indv2_y] = [self.mutate(u) for u in tmp] one = Person((indv1_x,indv1_y),self.chrom_size,self.interval) two = Person((indv2_x,indv2_y),self.chrom_size,self.interval) self.next_generation.append(one) self.next_generation.append(two) num+=2 self.current_generation = self.next_generation self.next_generation = [] def run (self): for i in range (self.max_generations): self.evolve() _,_,self.best = max((p.fitness,i,p) for i,p in enumerate(self.current_generation)) worest,i = min((p.fitness,i) for i,p in enumerate(self.current_generation)) self.current_generation[i] = self.best print(self.best.fitness,mean(p.fitness for p in self.current_generation),worest) population = Population(150,50,0.3,0.8,50) ans = population.run()

当我们将搜索空间变大的时候,可以发现找到最优解的情况在变得不稳定,很容易就收敛到局部的最优解,这时候除了增加变异率,最有效的办法就是扩大种群的数量。

结果展示:三元组分别是最优解,平均,最差: