用进化算法玩转强化学习 (小朋友都能懂的进化 demo)

pyjiujiu

引言
想象有一群小动物，它们在森林里玩耍，每次玩耍都会获得一些奖励或糖果。现在，我们要教这些小动物如何找到最多的糖果！这就是强化学习（Reinforcement Learning, RL），而我们今天要用一个特别的魔法——进化算法（Genetic Algorithms, GA）来帮助它们。
进化算法是什么？
进化算法就像是自然界里的进化过程！一群小动物（我们叫它们“个体”）在森林里生活，它们都有不同的技能和特质。通过不断地尝试、学习、和进化，它们会变得越来越聪明。
- 初始化：我们先让一群小动物在森林里随机跑来跑去。
- 评估：看看它们谁找到的糖果最多。
- 选择：我们选择那些找到糖果最多的动物，让它们当“父母”。
- 交叉（重组）：这些“父母”会交换一些技能，生出新的小动物。
- 变异：有时小动物会突然学会一个新的技能，这叫变异。
- 换代：新的小动物会代替一些老的小动物，这样它们就变得越来越聪明。
- 重复：我们不断重复这些步骤，直到小动物们变得非常擅长找糖果。
在强化学习中的魔法应用
进化算法在强化学习中就像一个超级助手：
- 教小动物找路：用GA来教小动物在迷宫里找到最短的路线，得到最多的糖果。
- 调节魔法力量：GA还能帮我们调节小动物的魔法力量（比如学习速度），让它们学得更快。

---分割线---
如果上面的不够明白，直接看我画的 流程图


**目标
本次的例子，然而并不是“找糖果”，而是 用随机字符串，去“复现” 原始字符串
原始字符串是  “Hello World!”

具体步骤，在上面流程图已经标识
下面直接上代码


**代码说明
*因为是demo，纯python实现，不需要什么第三方库（要画出图 需要matplotlib，可不装）
*本例来自书籍 deep reinforcement learning in action , (这本书非常不错)
*有必要说明，代码本身不是关键（本身很简单），关键是参数设置，有着自然界本质的规律体现

---分割线---
代码如下  

[Python] 纯文本查看 复制代码

import random
import string
from difflib import SequenceMatcher
import time

#个体的类 （种群中）
class Individual:
    __slots__=("string","fitness")
    def __init__(self,string, fitness=0) -> None:
        self.string = string
        self.fitness = fitness
    def __repr__(self) -> str:
        return f'Individual(string:{self.string},fitness:{self.fitness})'

#计算字符串相似度
def similar(a,b):
    return SequenceMatcher(None,a,b).ratio()

#初始随机产生种群（不包含基因传承）
def spawn_population(length=26,size=100):
    pop = []
    for i in range(size):
        string = ''.join(random.choices(alphabet,k=length))
        individual = Individual(string)
        pop.append(individual)
    return pop

#基因重新组合
def recombine(p1_,p2_):
    p1 = p1_.string
    p2 = p2_.string
    cross_pt = random.randint(0,len(p1))
    child1 = p1[0:cross_pt] + p2[cross_pt:]
    child2 = p2[0:cross_pt] + p1[cross_pt:]
    c1,c2 = Individual(child1),Individual(child2)
    return c1,c2 

#基因随机变异
def mutate(x,mut_rate=0.01):
    new_x = []
    for char in x.string:
        if random.random() < mut_rate:
            new_x.extend(random.choices(alphabet,k=1))
        else:
            new_x.append(char)
    new_x_ = Individual(''.join(new_x))
    return new_x_

#对群体评估（基于相似度，算种群平均分）
def evaluate_population(pop:list[Individual],target):
    avg_fit = 0
    for singal in pop:
        singal.fitness = similar(singal.string,target)
        avg_fit += singal.fitness
    avg_fit /= len(pop)
    return pop, avg_fit

#种群传承 产生新种群（根据基因重组）
def next_generation(pop, size=100, length=26,mut_rate=0.01):
    new_pop = []
    while len(new_pop) < size:
        parents = random.choices(pop,k=2, weights=[x.fitness for x in pop])
        offspring_ = recombine(parents[0],parents[1])
        child1 = mutate(offspring_[0],mut_rate=mut_rate)
        child2 = mutate(offspring_[1],mut_rate=mut_rate)
        new_pop.extend([child1,child2])
    return new_pop

#画图模块（需要装 matplotlib）
def draw(pop_fit):
    try:
        from matplotlib import pyplot as plt
        generations = list(range(1, len(pop_fit) + 1)) 
        plt.figure(figsize=(10, 5))  
        plt.plot(generations, pop_fit, marker='o')  
        plt.title('Fitness Over Generations')
        plt.xlabel('Generation')
        plt.ylabel('Fitness')
        plt.grid(True)
        plt.show()
    except:
        pass


if __name__=="__main__":
    start_time = time.time()
    ####关键参数####
    num_generation = 150
    population_size = 900
    mutation_rate = 0.000_01
    ####关键参数####
    
    alphabet = string.ascii_letters + ",.! "
    target = "Hello World!"
    
    str_len = len(target)
    pop_fit = []
    pop = spawn_population(size=population_size,length=str_len)
    for gen in range(num_generation):
        pop,avg_fit = evaluate_population(pop,target)
        pop_fit.append(avg_fit)
        print(avg_fit)
        pop =  next_generation(pop,size=population_size,length=str_len,mut_rate=mutation_rate)
        
        
    print('')
    print(f'total time consume:{time.time() - start_time:.2f}s')
    print(f'群代 数量：{num_generation}')
    print(f'种群 size：{population_size}')
    print(f'变异率：{mutation_rate}')
    print('')
    pop.sort(key=lambda x:x.fitness,reverse=True)
    print(f'最后字符：{pop[0].string}')
    draw(pop_fit)
    input('')

---分割线---

**这是我运行的截图（常规的参数）


**这是  代数维持150，群体size(个体数量) 缩小到100的结果（思考）




**这是尝试解决 上面群体size100，“成绩”上不去的修复做法（思考）




---分割线---
这个代码执行起来非常快，就几秒钟（过程中 也用pypy3 进行测试，从8秒-> 压缩到2秒多）
可以自己尝试去跑跑看，调整参数再尝试

最后，欢迎交流，关于达尔文的看法也可

zixiangcode

想起来了当年打数模的日子

52blah

可以参考 用遗传算法训练神经网络玩贪吃蛇项目
https://github.com/greerviau/SnakeAI