2024 遗传编程实战（一）基因实战

2024 遗传编程实战（一）基因实战

一、遗传编程实战介绍

1、遗传编程简介

什么是遗传编程算法，和传统机器学习算法有什么区别
传统上，我们接触的机器学习算法，都是被设计为解决某一个某一类问题的确定性算法。对于这些机器学习算法来说，唯一的灵活性体现在参数搜索空间上，向算法输入样本，算法借助不同的优化手段，对参数进行调整，以此来得到一个对训练样本和测试样本的最佳适配参数组。

遗传编程算法完全走了另一外一条路，遗传编程算法的目标是编写一个程度，这个程序会尝试自动构造出解决某一问题的最佳程度。从本质上看，遗传编程算法构造的是一个能够构造算法的算法。

另一方面，我们曾经讨论过遗传算法，遗传算法是一种优化技术，就优化技术而言，无论是何种形式的优化，算法或度量都是预先设定好的，而优化算法所做的工作就是尝试为其找到最佳参数。和优化算法一样，遗传编程也需要一种方法来度量题解的优劣程度。但与优化算法不同的是，遗传编程中的题解并不仅仅是一组用于给定算法的参数，相反，在遗传编程中，连同算法本身及其所有参数，都是需要搜索确定的。

从某种程度上来说，遗传编程和遗传算法的区别在于，进化的基本单位不同，

• 遗传优化：进化的基本单位是模型可变参数
• 遗传编程：进化的基本单位是新算法以及新算法的参数

2、遗传编程和进化论的关系

遗传算法是受达尔文的进化论的启发，借鉴生物进化过程而提出的一种启发式搜索算法，因此遗传算法 ( GA , Genetic Algorithm ) 也称进化算法 。 因此，在讨论遗传编程的时候，会大量借用进化论中的术语和概念，为了更好地讨论遗传算法，我们先介绍一些基本生物进化概念，

• 基因 ( Gene )：一个遗传因子，种群中的最基本单元。
• 染色体 ( Chromosome )：一组的基因。
• 交叉（Crossover）和变异（Mutation）：
  • 交叉：父母染色体将部分基因随机传下一代，并保证子代的基因数与上一代一致。
  • 变异：子代的某一个基因发生随机变异。
• 个体 ( individual )：单个生物。在遗传算法中，个体一般只包含一条染色体。
• 种群 ( Population )：由个体组成的群体。生物的进化以种群的形式进化。
• 适者生存 ( The survival of the fittest )：对环境适应度高的个体参与繁殖的机会比较多，后代就会越来越多。适应度低的个体参与繁殖的机会比较少，后代就会越来越少。

生物所处的环境起到一个提供生存压的作用（反馈），虽然纵观整个地球历史，环境的因素是在不断变化的（有时甚至变化的还很快），但是在某个时间段内（例如5000年内）是基本保持不变的，而物种进化的目的就是通过一代代的繁衍，逐渐适应（拟合）当前的环境，并和其他物种达到最优平衡（纳什均衡）。

3、遗传编程过程解释

遗传编程算法就是模拟了生物进化的过程，简单说来说，

• 生物进化的环境由一个用户定义的任务（user-defined task）所决定，算法由一组初始的题解（程序）开始展开竞争。这里所谓的任务可以是多种形式，

  • 一种竞赛（game）：各个题解（程序）在竞赛中直接展开竞争
  • 个体测试：测出哪个题解（程序）的执行效果更好

• 遗传算法将基因抽象为题解中最小的随机变量因子（例如模型中的可变参数）

• 一个问题的解由很多这样的随机变化因子组成，算法将问题的解编码成个体的染色体（染色体是基因的集合）

• 单个个体包含若干个染色体，个体包含的染色体（题解）越多和越好，则个体的适应度就越好。在实际工程中，为了简化算法，常常假设一个个体只有一条染色体

• 多个个体组成种群，种群中适应度（Fitness）高的个体获得较高概率的繁殖机会，从而导致适应度高的个体会越来越多，经过N代的自然选择后，保存下来的个体都是适应度很高的

• 繁殖过程中，算法会评估并挑选出本轮表现最好的一部分题解题解（程序），并对程序的某些部分以**随机（一定概率）**的方式进行修改，包括：

  • 基因交叉（Acrossover）：在最优题解之间，挑选部分随机变量因子进行彼此互换。遗传算法交叉比人体内染色体交叉要简单许多。遗传算法的染色体是单倍体，而人体内的真正的染色体是双倍体。下图是遗传算法中两条染色体在中间进行交叉的示意图，

  • 基因突变（Mutation）：在最优题解上，直接对某些随机变量因子（基因位）进行随机修改。下图是遗传算法中一条染色体在第二位发生基因变异的示意图，

• 经过繁殖过程，新的种群（即新的一组解）产生，称为“下一代”，理论上，这些新的题解基于原来的最优程序，但又不同于它们。这些新产生的题解和旧的最优题解会一起进入下一轮自然选择阶段

  • 上述繁殖过程重复多次，直到达到收敛条件，包括，
  • 找到了全局最优解
  • 找到了表现足够好的解
    题解在历经数代之后都没有得到任何改善
  • 繁衍的代数达到了规定的限制

• 最终，历史上适应度最高个体所包含的解，作为遗传算法的输出。

二、基于遗传编程的例子

1、实战题目介绍

在一个长度为n的数组nums中选择10个元素，使得10个元素的和与原数组的所有元素之和的1/10无限接近。

2、遗传算法的伪代码

BEGIN:
        i = 0;          //进化种群的代数
        Initialize P(i) //初始化种群
        While(not Terminate - Condition)//不满足终止条件时继续循环
        {
            Fitness(i)       // 计算适宜度
            GA-Operation P(i)//交叉、变异操作
            Fitness(i)       // 计算适宜度
            Selection(P)     //物竞天择、适者生存。适应度低的死亡
        }
EMD //结束
1
2
3
4
5
6
7
8
9
10
11

3、遗传实战具体代码与详细注释

未来的大佬请上座，下面是依据这个伪代码撰写的遗传实战轮子代码

import random
import math
# 定义问题参数
total_numbers = 100   # 种群的基因上下限  （人类基因组）
Generange=1000        # 种群基因的取值范围 （理论上全部物种的基因范围）
selected_numbers = 10 # 一个个体占据的基因 （一个人的全部基因 ：20000~25000）
pop_size=100          # 这个种群的个体个数 （一个人群的人数）
terminder=10          # 进化的终点       （进化到什么程度结束）

# 生成初始种群与种群基因组
def generate_population():

    population = []
    HumanGene = random.sample(range(Generange),100) # 从全部基因取值范围里面选取100个做为这个种群的基因取值范围
    for _ in range(pop_size):
        # 从种群的基因取值范围里面选取10个基因做为一个个体的全部基因组成
        individual = random.sample(HumanGene, selected_numbers)
        population.append(individual)
    return population,HumanGene

# 计算个体的适应度
def fitness(individual,HumanGene):
    #
    sum_selected = sum(individual)
    sum_total = sum(HumanGene)
    diff = abs(sum_selected - sum_total / 10)
    return 10 / (diff + 1) # diff越小，权重越大


# 选择优秀个体,将后面的一半淘汰掉
def selection(population, fitness_values):
    selected = random.choices(population, weights=fitness_values, k=total_numbers)
    return selected


# 两个人交配并生两娃的操作
def crossover(parent1, parent2):
    # pivot是染色体杂交的位点
    pivot = random.randint(1, selected_numbers - 1)
    child1 = parent1[:pivot] + parent2[pivot:]
    child2 = parent2[:pivot] + parent1[pivot:]
    return child1, child2

# 个体变异操作
def mutate(individual,HumanGene):
    # 确定那个位置变异
    mutated_index = random.randint(0, selected_numbers - 1)
    individual[mutated_index] =random.sample(HumanGene,1)[0]
    return individual


# 遗传编程主函数
def genetic_algorithm( generations):
    # 生成种群100
    population ,HumanGene= generate_population()

    for _ in range(generations):
        # 适宜度计算
        fitness_values = [fitness(individual,HumanGene) for individual in population]

        # 选择、交配、变异
        new_population = population.copy()
        for _ in range(pop_size//2):
            # 从人群中依据适宜度，做为权重，权重越高选择中的概率就越高
            # 选两个出来交配，生下两娃
            parent1, parent2 = random.choices(population, k=2, weights=fitness_values)
            child1, child2 = crossover(parent1, parent2)

            # 让下一代概率性变异
            if random.random() < 0.1:
                child1 = mutate(child1,HumanGene)
            if random.random() < 0.1:
                child2 = mutate(child2,HumanGene)

            # 将孩子插入到新的种群中
            new_population.extend([child1, child2])

        # 重新计算群体的适宜度，然后再依据适宜度进行淘汰
        fitness_values=[fitness(ind,HumanGene) for ind in new_population] #
        population = selection(new_population, fitness_values)
    # 依据适宜度返回最佳的个体
    best_individual = max(population, key=lambda x:fitness(x,HumanGene))
    return population,HumanGene,best_individual


# 运行遗传编程
population,HumanGene,best_solution = genetic_algorithm(generations=1000)
print('最终的种群：'+str(population))
print('种群的基因组：'+str(HumanGene))

print('基因组的和：'+str(sum(HumanGene)))
print("最佳解决方案:{},解决方案的和：{}".format(str(best_solution),sum(best_solution)))
print("从基因组中抽出的10个值的和，近乎是整个基因组的和的十分之一，差："+str(abs(sum(HumanGene)//10-sum(best_solution))))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

运行结果：

4、将以上纯python运算实现代码套入DEAP强化学习框架实现

DEAP是目前强化学习主流使用的框架，可以看到在这个框架的支持下，结构和代码量都减少了许多，并且也有了更多的可视化过程。
解决问题：在一个长度为n的数组nums中选择10个元素，使得10个元素的和与原数组的所有元素之和的1/10无限接近。
具体代码如下

import random
from deap import base, creator, tools, algorithms

# 定义问题参数
total_numbers = 100   # 种群的基因上下限  （人类基因组）
Generange=1000        # 种群基因的取值范围 （理论上全部物种的基因范围）
selected_numbers = 10 # 一个个体占据的基因 （一个人的全部基因 ：20000~25000）
pop_size=100          # 这个种群的个体个数 （一个人群的人数）
terminder=10          # 进化的终点       （进化到什么程度结束）


nums = [random.randint(1, Generange) for _ in range(100)]  # 生成一个长度为100的随机数组
target_sum = sum(nums) / 10  # 目标和为原数组所有元素之和的1/10


# 创建遗传算法所需的工具：个体类、种群类、目标函数、交叉函数、变异函数等
# 一、定义问题,是最小化问题还是最大化
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))  # 目标是最小化目标函数
creator.create("Individual", list, fitness=creator.FitnessMin)

# 二、生成个体
IND_SIZE = 10  # 个体大小，即选择的元素数量
toolbox = base.Toolbox()
toolbox.register("indices", random.sample, range(len(nums)), IND_SIZE)
toolbox.register("individual", tools.initIterate, creator.Individual, toolbox.indices)
# 三、生成初始种群
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
pop = toolbox.population(n=300)  # 种群大小

# 四、定义遗传算子：评估函数、交叉函数、变异函数、选择函数
def evalSolution(individual):
    """评价函数，计算个体与目标和的差的绝对值"""
    return (abs(sum(nums[i] for i in individual) - target_sum),)

toolbox.register("evaluate", evalSolution)                       # 评价个体的适应度的函数，由于权重是最小化，所以越小适应度越高。
toolbox.register("mate", tools.cxTwoPoint)                       # 使用两点交叉
toolbox.register("mutate", tools.mutShuffleIndexes, indpb=0.05)  # 使用基因位置交换的方式变异
toolbox.register("select", tools.selTournament, tournsize=3)     # 使用锦标赛选择

def main():
    random.seed(64)

    hof = tools.HallOfFame(1)  # 保留最佳个体
    stats = tools.Statistics(lambda ind: ind.fitness.values) # 运行中间输出
    stats.register("avg", lambda x: sum(val[0] for val in x) / len(x))

    stats.register("min", min)
    stats.register("max", max)

    algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=50,
                        stats=stats, halloffame=hof, verbose=True)

    return hof[0]

if __name__ == "__main__":
    best = main()
    print("Best individual is:", best)
    print("Sum of selected elements:", sum(nums[i] for i in best))
    print('Sum of Gene：',sum(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

运行过程：