python实现简单遗传算法

1. 简介

遗传算法是一种基于生物进化原理而产生的计算方法，是一种搜索算法，目标是从一组解中找到能够最大化或最小化某个特定目标函数的解。其思想是模拟达尔文进化论中的自然选择和遗传机制，根据每个个体的适应度来选择优秀的个体，然后通过交叉互换和变异等操作筛选出更好的个体，并不断地迭代以求得最优解。

本文将介绍如何使用Python实现简单遗传算法，主要包括以下几个部分：目标函数的定义、参数设置、种群初始化、适应度函数的编写、选择操作、交叉互换和变异等。

2. 目标函数的定义

在本例中，我们选用经典的函数y=sin(10x)+x，其中取值范围为0到1，目标是通过遗传算法来寻找使得函数值最大的x.

import math
def fitness(x):
    y = math.sin(10 * x) + x
    return y

其中fitness函数即为我们所定义的目标函数，输入的x即为待求解的变量值。

3. 参数设置

以下是一些关键参数的设置：

population_size：种群的大小，即个体的数量

chromosome_length：染色体的长度，即每个个体的基因数量

crossover_rate：交叉概率，即两个个体进行交叉的概率

mutation_rate：变异概率，即某个个体发生变异的概率

max_generation：最大迭代次数

temperature：初始化选举温度

population_size = 100  # 种群大小，即个体数量
chromosome_length = 20  # 染色体长度，即每个个体基因数量
crossover_rate = 0.8  # 交叉概率，两个个体进行交叉的概率
mutation_rate = 0.01  # 变异概率，某个个体发生变异的概率
max_generation = 200  # 最大迭代次数
temperature = 0.6  # 初始化选举温度

4. 种群初始化

种群的初始化是遗传算法的第一步，其目的是产生一组符合要求的个体集合。在本例中，我们采用二进制编码的方式来表示每个个体的基因，即将范围在（0, 1）之间的x值转换为20位二进制数的形式，这样每个个体就可以用一个长度为20的字符串表示。种群初始化的代码如下：

import random
def init_population():
    population = []
    for i in range(population_size):
        chromosome = ''
        for j in range(chromosome_length):
            chromosome += str(random.randint(0, 1))
        population.append(chromosome)
    return population

其中，init_population函数即为我们所定义的种群初始化函数，该函数返回一个由多个个体组成的列表population，其中每个个体均为长度为20的二进制字符串。

5. 适应度函数的编写

适应度函数的作用是计算个体的适应度值，以此作为选择、交叉和变异的依据。在本例中，我们使用fitness函数来计算每个个体的适应度值，即y值。但是，由于我们的目标是求函数最大值，而在遗传算法中通常使用最小化函数，因此有必要将fitness函数进行一定的转换。

def adapt(population):
    fitnesses = []
    for i in range(len(population)):
        individual = population[i]
        x = int(individual, 2) / (2 ** chromosome_length - 1)  # 将二进制转换为实数
        fitnesses.append(1 / float(fitness(x)))  # 将最大化函数转换为最小化函数
    total_fitness = sum(fitnesses)
    adapt_values = [fitnesses[i] / total_fitness for i in range(len(population))]  # 计算适应度值
    return adapt_values

其中adapt函数即为我们所定义的适应度函数，该函数接受种群population作为输入，返回一个适应度值的列表adapt_values。该函数首先将二进制字符串转换为实数，然后计算其对应的适应度值，将最大化函数转化为最小化函数。最后，该函数计算每个个体的适应度值，并将其标准化。

6. 选择操作

选择操作的目的是从种群中选择出适应度最高的个体，用于交叉和变异。在本文中，我们采用轮盘赌选择算法来进行个体的挑选。具体来说，轮盘赌选择算法的过程如下：

计算每个个体的适应度值

计算每个个体被选中的概率

根据轮盘赌法规则进行选择（即按照适应度值的大小确定各自所占的权重，并使用随机数在所有个体中选择一个个体）

def select(population, adapt_values):
    new_population = []
    for i in range(len(population)):
        cumsum_adapt_values = [sum(adapt_values[:i + 1]) for i in range(len(population))]  # 计算累计适应度值
        pointer = random.uniform(0, 1)  # 生成一个随机数
        for i in range(len(population)):
            if pointer < cumsum_adapt_values[i]:
                new_population.append(population[i])
                break
    return new_population

其中select函数即为我们所定义的选择函数，该函数接受种群population和相应的适应度值列表adapt_values为输入，返回一个选择过后的新种群new_population。该函数首先计算每个个体的累计适应度值，然后生成一个随机数，并按照轮盘赌法规则进行选择，最后将选择过后的新个体加入到新种群new_population中。

7. 交叉互换

交叉互换的目的是通过交叉互换来产生新的个体，从而保证种群的多样性。在本例中，我们采用单点交叉的方式进行个体的交换。具体来说，单点交叉的过程如下：

从种群中选中两个个体

根据交叉概率，决定是否对这两个个体进行交叉

从两个个体中随机选取一个交叉点

将两个个体在交叉点处的染色体进行交换

def crossover(population):
    for i in range(len(population) - 1):
        if random.uniform(0, 1) < crossover_rate:
            cross_point = random.randint(1, chromosome_length - 1)  # 随机选择交叉点
            chrom_a = population[i][:cross_point] + population[i + 1][cross_point:]
            chrom_b = population[i + 1][:cross_point] + population[i][cross_point:]
            population[i], population[i + 1] = chrom_a, chrom_b
    return population

其中crossover函数即为我们所定义的交叉互换函数，该函数接受种群population为输入，返回一个交叉互换过后的种群。该函数首先从种群中随机选择两个个体，并按照交叉概率决定是否进行交叉操作，然后随机选择交叉点，将两个个体在交叉点处的染色体进行交换。

8. 变异操作

变异操作的目的是通过变异来产生新的个体，并保证种群的多样性。在本例中，我们采用单点变异的方式进行个体的变异。具体来说，单点变异的过程如下：

从种群中选中一个个体

根据变异概率，决定是否对这个个体进行变异

从这个个体中随机选取一个基因

将这个基因进行取反操作

def mutation(population):
    for i in range(len(population)):
        if random.uniform(0, 1) < mutation_rate:
            mutation_point = random.randint(0, chromosome_length - 1)  # 随机选择变异点
            mutation_bit = population[i][mutation_point]
            new_bit = '0' if mutation_bit == '1' else '1'
            population[i] = population[i][:mutation_point] + new_bit + population[i][mutation_point + 1:]
    return population

其中mutation函数即为我们所定义的变异函数，该函数接受种群population为输入，返回一个进行变异操作过后的种群。该函数首先从种群中随机选择一个个体，并按照变异概率决定是否进行变异操作，然后随机选择变异点，将这个基因进行取反操作。

9. 完整代码

下面是完整代码的实现：

import math
import random
population_size = 100  # 种群大小，即个体数量
chromosome_length = 20  # 染色体长度，即每个个体基因数量
crossover_rate = 0.8  # 交叉概率，两个个体进行交叉的概率
mutation_rate = 0.01  # 变异概率，某个个体发生变异的概率
max_generation = 200  # 最大迭代次数
temperature = 0.6  # 初始化选举温度
def fitness(x):
    y = math.sin(10 * x) + x
    return y
def init_population():
    population = []
    for i in range(population_size):
        chromosome = ''
        for j in range(chromosome_length):
            chromosome += str(random.randint(0, 1))
        population.append(chromosome)
    return population
def adapt(population):
    fitnesses = []
    for i in range(len(population)):
        individual = population[i]
        x = int(individual, 2) / (2 ** chromosome_length - 1)  # 将二进制转换为实数
        fitnesses.append(1 / float(fitness(x)))  # 将最大化函数转换为最小化函数
    total_fitness = sum(fitnesses)
    adapt_values = [fitnesses[i] / total_fitness for i in range(len(population))]  # 计算适应度值
    return adapt_values
def select(population, adapt_values):
    new_population = []
    for i in range(len(population)):
        cumsum_adapt_values = [sum(adapt_values[:i + 1]) for i in range(len(population))]  # 计算累计适应度值
        pointer = random.uniform(0, 1)  # 生成一个随机数
        for i in range(len(population)):
            if pointer < cumsum_adapt_values[i]:
                new_population.append(population[i])
                break
    return new_population
def crossover(population):
    for i in range(len(population) - 1):
        if random.uniform(0, 1) < crossover_rate:
            cross_point = random.randint(1, chromosome_length - 1)  # 随机选择交叉点
            chrom_a = population[i][:cross_point] + population[i + 1][cross_point:]
            chrom_b = population[i + 1][:cross_point] + population[i][cross_point:]
            population[i], population[i + 1] = chrom_a, chrom_b
    return population
def mutation(population):
    for i in range(len(population)):
        if random.uniform(0, 1) < mutation_rate:
            mutation_point = random.randint(0, chromosome_length - 1)  # 随机选择变异点
            mutation_bit = population[i][mutation_point]
            new_bit = '0' if mutation_bit == '1' else '1'
            population[i] = population[i][:mutation_point] + new_bit + population[i][mutation_point + 1:]
    return population
if __name__ == '__main__':
    population = init_population()
    best_individual = population[0]
    g = 0
    while True:
        adapt_values = adapt(population)
        new_population = select(population, adapt_values)
        new_population = crossover(new_population)
        new_population = mutation(new_population)
        population = new_population
        g += 1
        # 更新最优个体
        for i in range(len(population)):
            if fitness(int(population[i], 2)) > fitness(int(best_individual, 2)):
                best_individual = population[i]
        if g > max_generation:
            break
print('The best individual is:', best_individual)
print('The best fitness is:', fitness(int(best_individual, 2)))

10. 总结

本文介绍了如何使用Python实现简单遗传算法，并以求函数最大值为例进行了演示。遗传算法作为一种优化算法，可以在复杂问题中快速找到最优解。在实现遗传算法时，我们需要考虑到一些关键参数的设置，包括种群大小、染色体长度、交叉互换和变异等操作的概率等等。在实际应用过程中，我们还需要结合具体问题进行调参和分析，以获得更好的优化结果。