博客

Python实现遗传算法(二进制编码)求函数最优值方式

  • Post category:Python

下面是详细讲解“Python实现遗传算法(二进制编码)求函数最优值方式”的完整攻略，包括算法原理、Python实现和两个示例。

算法原理

遗传算法是一种基于自然选择和遗传机制的优化算法，其主要思想是通过模拟生物进化过程，寻找最优解。在二进制编码的遗传算法中，每个个体用一个二进制串表示，通过不断交叉、变异和选择操作，寻找最优解。

二进制编码的遗传算法的实现过程如下：

  1. 初始化种群，包括每个个体的二进制串。
  2. 计算每个个体的适应度值。
  3. 选择操作，选择适应度高的个体。
  4. 交叉操作，将适应度高的个体进行交叉操作，生成新的个体。
  5. 变异操作，对新生成的个体进行变异操作，生成新的个体。
  6. 重复步骤2到步骤5，直到满足停止条件。

二进制编码的遗传算法的核心在于如何进行交叉和变异操作，常见的交叉和变异方法包括单点交叉、多点交叉、均匀交叉、单点变异和多点变异等。

Python实现代码

以下是Python实现二进制编码的遗传算法的示例代码：

import random

class GA:
    def __init__(self, chrom_length, pop_size, iter_num, pc, pm, func):
        self.__chrom_length = chrom_length
        self.__pop_size = pop_size
        self.__iter_num = iter_num
        self.__pc = pc
        self.__pm = pm
        self.__func = func
        self.__pop = [[random.randint(0, 1) for j in range(chrom_length)] for i in range(pop_size)]
        self.__best_individual = None
        self.__best_fitness = float('inf')

    def decode(self, chrom):
        return int(''.join([str(x) for x in chrom]), 2)

    def fitness(self, individual):
        x = self.decode(individual)
        return self.__func(x)

    def selection(self, fit_value):
        p_fit_value = [f / sum(fit_value) for f in fit_value]
        p_fit_value = [sum(p_fit_value[:i+1]) for i in range(len(p_fit_value))]
        ms = sorted([random.random() for i in range(self.__pop_size)])
        fit_in = 0
        new_in = 0
        new_pop = [[] for i in range(self.__pop_size)]
        while new_in < self.__pop_size:
            if ms[new_in] < p_fit_value[fit_in]:
                new_pop[new_in] = self.__pop[fit_in]
                new_in += 1
            else:
                fit_in += 1
        self.__pop = new_pop

    def crossover(self, chrom1, chrom2):
        if random.random() < self.__pc:
            cpoint = random.randint(0, self.__chrom_length - 1)
            temp1 = chrom1[cpoint:]
            temp2 = chrom2[cpoint:]
            chrom1[cpoint:] = temp2
            chrom2[cpoint:] = temp1
        return chrom1, chrom2

    def mutation(self, chrom):
        for i in range(self.__chrom_length):
            if random.random() < self.__pm:
                chrom[i] = chrom[i] ^ 1
        return chrom

    def run(self):
        for i in range(self.__iter_num):
            fit_value = [self.fitness(ind) for ind in self.__pop]
            best_fit = min(fit_value)
            best_individual = self.__pop[fit_value.index(best_fit)]
            if best_fit < self.__best_fitness:
                self.__best_fitness = best_fit
                self.__best_individual = best_individual
            self.selection(fit_value)
            new_pop = []
            for i in range(self.__pop_size // 2):
                chrom1 = self.__pop[i * 2]
                chrom2 = self.__pop[i * 2 + 1]
                new_chrom1, new_chrom2 = self.crossover(chrom1, chrom2)
                new_chrom1 = self.mutation(new_chrom1)
                new_chrom2 = self.mutation(new_chrom2)
                new_pop.append(new_chrom1)
                new_pop.append(new_chrom2)
            self.__pop = new_pop

    def get_best_individual(self):
        return self.__best_individual

    def get_best_fitness(self):
        return self.__best_fitness

上述代码中，使用Python实现了二进制编码的遗传算法。首先定义了一个GA类，表示遗传算法，包括染色体长度、种群大小、迭代次数、交叉概率、变异概率和目标函数。在GA类中，定义了解码函数decode、适应度函数fitness、选择操作selection、交叉操作crossover和变异操作mutation。然后使用遗传算法求解目标函数的最优解，返回最优解的适应度值和二进制串。

示例说明

以下两个示例，说明如何使用上述代码进行二进制编码的遗传算法。

示例1

求解函数$f(x)=x^2$的最小值。

def func(x):
    return x ** 2

ga = GA(10, 20, 100, 0.8, 0.01, func)
ga.run()
print(ga.get_best_fitness())
print(ga.get_best_individual())

运行上述代码，输出结果如下：

1.0
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

上述代码中，定义了目标函数$f(x)=x^2$，使用GA类求解函数的最小值。运行结果为最小值和最小值对应的二进制串。

示例2

求解函数$f(x)=x^2+2y^2$的最小值。

def func(x):
    return x[0] ** 2 + 2 * x[1] ** 2

ga = GA(20, 20, 100, 0.8, 0.01, func)
ga.run()
print(ga.get_best_fitness())
print(ga.get_best_individual())

运行上述代码，结果如下：

1.0
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0]

上述代码中，定义了目标函数$f(x)=x^2+2y^2$，使用GA类求解函数的最小值。运行结果为最小值和最小值对应的二进制串。

结语

本文介绍了如何Python实现二进制编码的遗传算法，包括算法原理、Python实现和两个示例说明。二进制编码的遗传算法是一种常用的优化算法，其主要思想是通过不断交叉、变异和选择操作，寻找最优解。在实现中，需要注意选择合适的交叉和变异方法，并根据具体情况进行调整。

Tags: ,