Microbial Genetic Algorithm(微遗传算法)
这种算法是用来解决遗传算法中的一些问题，当我们在遗传的过程中，我们在利用原始的种群繁衍变异产生新的种群以后，原来的种群就消失了，但是有可能我们在这个过程也将好的个体丢失了，所以有可能变异之后的种群还没有原来的种群好。
那么所以我就应该在繁衍变异的过程中保留一部分好的基因，这就是问题。一句话来概括，就是：在袋子里抽两个球，对比两个球的大小，把球大的放回袋子里，把球小的变一下再放回袋子里。
首先有一个种群，随机选取两个DNA，对比他们的，然后分成好的和坏的：winer、loser，然后winer不做任何改动，loser摄取一些winer的，然后再将两者放回，这个过程并没有改变winer的DNA， loser的DNA。
import numpy as np
import matplotlib.pyplot as pltDNA_SIZE = 10 # DNA length
POP_SIZE = 20 # population size
CROSS_RATE = 0.6 # mating probability (DNA crossover)
MUTATION_RATE = 0.01 # mutation probability
N_GENERATIONS = 200
X_BOUND = [0, 5] # x upper and lower boundsdef F(x): return np.sin(10*x)*x + np.cos(2*x)*x # to find the maximum of this functionclass MGA(object):def __init__(self, DNA_size, DNA_bound, cross_rate, mutation_rate, pop_size):self.DNA_size = DNA_sizeDNA_bound[1] += 1self.DNA_bound = DNA_boundself.cross_rate = cross_rateself.mutate_rate = mutation_rateself.pop_size = pop_size# initial DNAs for winner and loserself.pop = np.random.randint(*DNA_bound, size=(1, self.DNA_size)).repeat(pop_size, axis=0)def translateDNA(self, pop):# convert binary DNA to decimal and normalize it to a range(0, 5)return pop.dot(2 ** np.arange(self.DNA_size)[::-1]) / float(2 ** self.DNA_size - 1) * X_BOUND[1]def get_fitness(self, product):return product # it is OK to use product value as fitness in heredef crossover(self, loser_winner): # crossover for losercross_idx = np.empty((self.DNA_size,)).astype(np.bool)for i in range(self.DNA_size):cross_idx[i] = True if np.random.rand() < self.cross_rate else False # crossover indexloser_winner[0, cross_idx] = loser_winner[1, cross_idx] # assign winners genes to loserreturn loser_winnerdef mutate(self, loser_winner): # mutation for losermutation_idx = np.empty((self.DNA_size,)).astype(np.bool)for i in range(self.DNA_size):mutation_idx[i] = True if np.random.rand() < self.mutate_rate else False # mutation index# flip values in mutation pointsloser_winner[0, mutation_idx] = ~loser_winner[0, mutation_idx].astype(np.bool)return loser_winnerdef evolve(self, n): # nature selection wrt pop's fitnessfor _ in range(n): # random pick and compare n timessub_pop_idx = np.random.choice(np.arange(0, self.pop_size), size=2, replace=False)sub_pop = self.pop[sub_pop_idx] # pick 2 from popproduct = F(self.translateDNA(sub_pop))fitness = self.get_fitness(product)loser_winner_idx = np.argsort(fitness)loser_winner = sub_pop[loser_winner_idx] # the first is loser and second is winnerloser_winner = self.crossover(loser_winner)loser_winner = self.mutate(loser_winner)self.pop[sub_pop_idx] = loser_winnerDNA_prod = self.translateDNA(self.pop)pred = F(DNA_prod)return DNA_prod, predplt.ion() # something about plotting
x = np.linspace(*X_BOUND, 200)
plt.plot(x, F(x))ga = MGA(DNA_size=DNA_SIZE, DNA_bound=[0, 1], cross_rate=CROSS_RATE, mutation_rate=MUTATION_RATE, pop_size=POP_SIZE)for _ in range(N_GENERATIONS): # 100 generationsDNA_prod, pred = ga.evolve(5) # natural selection, crossover and mutation# something about plottingif 'sca' in globals(): sca.remove()sca = plt.scatter(DNA_prod, pred, s=200, lw=0, c='red', alpha=0.5); plt.pause(0.05)plt.ioff();plt.show()
