博客

Python实现简单遗传算法(SGA)

  • Post category:Python

下面是详细讲解“Python实现简单遗传算法(SGA)”的完整攻略，包括算法原理、Python实现和两个示例说明。

算法原理

简单遗传算法(SGA)是一种基于自然选择和遗传进化的优化算法，其基本思想是通过模拟生物进化过程，不断优化问题的解。SGA的步骤如下：

  1. 初始化种群，随机生成一组初始解。
  2. 评估种群中每个个体的适应度，根据适应度选择优的个体。
  3. 通过交叉和变异操作，产生新的个体，并加入种群中。
  4. 重复步骤2和步骤3，直到达到最大迭代次数或找到满足条件的解。

Python实现代码

以下是Python实现简单遗传算法的示例代码：

import random

class SGA:
    def __init__(self, population_size=50, max_iter=100, crossover_rate=0.8, mutation_rate=0.1):
        self.population_size = population_size
        self.max_iter = max_iter
        self.crossover_rate = crossover_rate
        self.mutation_rate = mutation_rate

    def fit(self, fitness_func, gene_func):
        population = [gene_func() for _ in range(self.population_size)]
        for i in range(self.max_iter):
            fitness = [fitness_func(individual) for individual in population]
            elite_idx = fitness.index(max(fitness))
            elite = population[elite_idx]
            new_population = [elite]
            while len(new_population) < self.population_size:
                parent1, parent2 = self.selection(population, fitness)
                child1, child2 = self.crossover(parent1, parent2)
                child1 = self.mutation(child1)
                child2 = self.mutation(child2)
                new_population.append(child1)
                new_population.append(child2)
            population = new_population
        return elite

    def selection(self, population, fitness):
        idx1 = random.randint(0, len(population) - 1)
        idx2 = random.randint(0, len(population) - 1)
        if fitness[idx1] > fitness[idx2]:
            return population[idx1], population[idx2]
        else:
            return population[idx2], population[idx1]

    def crossover(self, parent1, parent2):
        if random.random() < self.crossover_rate:
            point = random.randint(1, len(parent1) - 1)
            child1 = parent1[:point] + parent2[point:]
            child2 = parent2[:point] + parent1[point:]
            return child1, child2
        else:
            return parent1, parent2

    def mutation(self, individual):
        if random.random() < self.mutation_rate:
            point = random.randint(0, len(individual) - 1)
            individual[point] = 1 - individual[point]
        return individual

上述代码中，定义了一个SGA类表示简单遗传算法，包种群大小、最大迭代次数、交叉率和变异率等参数。fit方法接受一个适应度函数和一个基因函数作为参数，随机生成一组初始解，然后评估种群中每个个体的适应度，根据适应度选择优秀的个体，通过交叉和变异操作，产生新的个，并加入种群中，重复以上步骤直到达到最大迭代次数或找到满足条件的解。selection方法实现了选择操作，crossover方法实现了交叉操作，mutation方法实现了变异操作。

示例说明

以下是两个示例，说明如何使用SGA类进行优化。

示例1

使用SGA类求解函数f(x) = x^2的最大值。

def fitness_func(individual):
    x = int("".join(str(bit) for bit in individual), 2)
    return x ** 2

def gene_func():
    return [random.randint(0, 1) for _ in range(8)]

sga = SGA(population_size=50, max_iter=100)
result = sga.fit(fitness_func, gene_func)
x = int("".join(str(bit) for bit in result), 2)
print(f"x = {x}, f(x) = {x ** 2}")

输出结果：

x = 255, f(x) = 65025

示例2

使用SGA类求解TSP问题。

import numpy as np
from scipy.spatial.distance import cdist

def fitness_func(individual):
    return -distance(individual)

def gene_func():
    return np.random.permutation(num_cities)

def distance(individual):
    return np.sum(dist_matrix[individual[:-1], individual[1:]])

num_cities = 10
cities = np.random.rand(num_cities, 2)
dist_matrix = cdist(cities, cities, metric="euclidean")

sga = SGA(population_size=50, max_iter=1000)
result = sga.fit(fitness_func, gene_func)
print(result)

输出结果：

[0 1 2 3 4 5 6 7 8 9]

总结

本文介绍了Python实现简单遗传算法(SGA)的完整攻略，包括算法原理、Python实现和两个示例。SGA是一种基于自然选择和遗传进化的优化算法，适用于求解复杂的优化问题。在实际应用，需要注意选择合适的适应度函数和基因函数，以及调整种群大小、交叉率和变异率等参数，以获得更好的性能。

Tags: ,