硕士毕业论文的时候使用了遗传算法，所以研究了一段时间，曾经用 Python 写一个简单的遗传算法，好自己拿来实验。整个代码还是仿照《游戏编程中的人工智能技术》中的代码来写的。如果想简单的学习一下遗传算法以及简单应用《游戏编程中的人工智能技术》是不错的选择。 代码如下面所附。
我写了一个简单的测试函数 main
运行后多数情况下会产生如下输出
-----------------
Function: y = 0 - 2 * x * x + 12 * x + 5
The best genome is: [0, 0, 1, 1]
The variable is: 3
The max value is 23
-----------------
Function: y = 0 - 2 * x * x + 8 * x + 4
The best genome is: [0, 0, 1, 0]
The variable is: 2
The max value is 12
-----------------
以 y = 0 - 2 * x * x + 8 * x + 4 为例，在 Matlab 中画出该函数的曲线的时候，可以看到 该函数的极值点确实在 x = 2 处，证明算法还是相当成功的。
因为写的测试算法主要针对求函数的极大值，如果是求函数极小值可以乘上 -1 就 OK 了。
其实上边的函数，乘上 -1 ，然后求导也可以知道极值为 x=8/4=2 ，这是极小值，乘上 -1 就得极大值了。
算是初步改写成功了，当然还有很多问题，比如选择时用的轮盘赌，但是 AI 的书上的算法似乎有点问题，另外似乎变异操作也有点问题，变异我现在只是变异一处，而原书上则是每一处都根据变异率来进行变异。
种群要设置的稍微大点，太小了没效果。变异率也要大一点。
另外，测试函数里的解空间比较小，还有就是终止条件目前仅判断代数是否超过了设置的最大代数，我想还应该在判断适应性分数最高的地方设置终止条件。这样就避免了多余的运算 [code lang="python"] # -*- coding:utf-8 -*- # file: GA.py # date: 2011-10-22 # note: import random class genome: def __init__(self, length = 0): self.fitness = 0 self.bits = [] for i in range(length): self.bits.append(random.randint(0, 1)) class ga: def __init__(self, pop_size, genome_len, expr = 'y = 0 - 2 * x * x + 8 * x + 4', crossover_rate = 0.7, mutation_rate = 0.01, max_generation = 1000 ): self.crossover_rate = crossover_rate self.mutation_rate = mutation_rate self.pop_size = pop_size self.genome_len = genome_len self.generation = 0 self.genomes = [] self.busy = False self.fittest_genome = genome() self.best_fitness_score = 0 self.total_fitness_score = 0 self.expr = expr self.max_generation = max_generation def create_start_populations(self): del self.genomes[0:] for i in range(self.pop_size): self.genomes.append(genome(self.genome_len)) self.generation = 0 self.best_fitness_score = 0 self.total_fitness_score = 0 def selection(self): f_slice = random.uniform(0, 1) * self.total_fitness_score c_f_slice = 0.0 selected_genome = 0 for i in range(self.pop_size): c_f_slice = c_f_slice + self.genomes[i].fitness if c_f_slice f_slice: selected_genome = i break return self.genomes[i] def crossover(self, mum, dad): baby1 = [] baby2 = [] if (random.uniform(0, 1) self.crossover_rate): baby1 = mum.bits; baby2 = dad.bits; return baby1, baby2 cp = random.randint(0, self.genome_len - 1) for i in range(cp): baby1.append(mum.bits[i]) baby2.append(dad.bits[i]) for i in range(cp, self.genome_len): baby1.append(dad.bits[i]) baby2.append(mum.bits[i]) return baby1, baby2 def mutate(self, bits): if (random.uniform(0, 1) self.mutation_rate): mp = random.randint(0, self.genome_len - 1) bits[mp] = int(not bits[mp]) def decode(self, gen): x = self.bin2int(gen) exec(self.expr) return y def bin2int(self, lists): m = 1 r = 0 lists.reverse() for i in range(len(lists)): r = r + m * lists[i] m = m * 2 lists.reverse() return r def update_fitness_scores(self): self.total_fitness_score = 0 for i in range(self.pop_size): self.genomes[i].fitness = self.decode(self.genomes[i].bits) self.total_fitness_score ...
阅读全文 »