遗传算法的Python实现(求解函数极值问题)

目录

  • 问题描述
  • 种群初始化
    • 参考代码
  • 计算搜索精度
    • 参考代码
  • 染色体解码
    • 参考代码
  • 选择算子
    • 参考代码
  • 交叉算子
    • 参考代码
  • 变异算子
    • 参考代码
  • 优化
  • 完整代码

问题描述

f(x)=x*sin(x)+1, x属于[0,2π] ,以求解f(x)的最大值和最小值问题为例,设计针对f(x)的遗传算法程序,然后进行运行求解
(1)确定基本功能:本实验是实现f(x)的最大值和最小值的求解。
(2)对f(x)进行编码:用一个二进制矢量表示一个染色体,由染色体来代表变量x的实数值。
(3)设计适应度函数:由于要求f(x)的最值,所以适应度函数就是f(x)。
(4)针对f(x)的设计并且实现遗传算法程序:遗传操作主要包括复制、交叉和变异。复制是直接将父代遗传给子代,即根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。交叉从能进入下一代的个体中选出两个,将两者的部分码值进行交换。变异是根据变异概率选出一个个体,随机对其某位编码进行改变。
(5)设计初始种群:默认设置为50个随机产生的23位字节的染色体,可以通过输入来设置种群规模。
(6)调试交叉和变异概率:在常用的交叉和变异概率范围内,结果随交叉和变异的概率的改变而改变,之间差异相对来说不太明显.

种群初始化

种群初始化的过程就是随机生成种群规模数量的随机二进制编码个体

参考代码

def get_chromosome(size, length):
    """
    生成size个长度为length的染色体列表
    :param size: 种群规模规模
    :param length: 染色体长度
    :return: 二维列表
    """
    population_temp = []
    for i in range(size):
        population_temp.append([random.randint(0, 1) for _ in range(length)])   # 生成长度为length的随机二进制列表,并存放到population_temp列表中
    return population_temp

计算搜索精度

此处根据精度计算公式:
δ = U x − L x 2 l − 1 \delta = \frac{U_{x} - L_{x}}{2 ^{l} - 1} δ=2l1UxLx

参考代码

def get_accuracy(min_, max_, length):
    """
    计算搜索精度
    :param min_: 基因的最小值
    :param max_: 基因的最大值
    :param length: 染色体长度
    :return: 精度
    """
    return (max_ - min_) / (2 ** length - 1)    # 精度计算公式

染色体解码

此处根据解码公式:
x = L x + δ ∑ i = 1 l A i 2 i − 1 x = L_{x} + \delta \sum_{i=1}^l A_{i} 2^{i-1} x=Lx+δi=1lAi2i1

参考代码

def chromosome_decode(chromosome_list, min_, accuracy_):
    """
    染色体解码
    :param chromosome_list: 二进制染色体列表
    :param min_: 基因的最小值
    :param accuracy_: 精度
    :return: 解码的结果
    """
    decimal = int(''.join([str(i) for i in chromosome_list]), 2)    # 二进制列表转为十进制整型
    return min_ + accuracy_ * decimal   # 解码公式

选择算子

遗传算法中选择算子的实现方式有很多种,比较有效的是轮盘赌算法和联赛选择算法,此处使用轮盘赌算法

轮盘赌算法的精髓就是可以根据个体的适应度进行随机选择,适应度越大的个体被选择的概率越大,当种群规模较大时,这种算法可以比较真实的模拟出自然状态中的情况

参考代码

def select(chromosome_list, fitness_list):
    """
    选择(轮盘赌算法)
    :param chromosome_list: 二维列表的种群
    :param fitness_list: 适应度列表
    :return: 选择之后的种群列表
    """
    population_fitness = np.array(fitness_list).sum()  # 种群适应度
    fit_ratio = [i / population_fitness for i in fitness_list]  # 每个个体占种群适应度的比例
    fit_ratio_add = [0]  # 个体累计概率
    for i in fit_ratio:
        fit_ratio_add.append(fit_ratio_add[len(fit_ratio_add) - 1] + i)     # 计算每个个体的累计概率,并存放到fit_ratio_add中
    fit_ratio_add = fit_ratio_add[1:]   # 去掉首位的0

    rand_list = [random.uniform(0, 1) for _ in chromosome_list]     # 生成和种群规模相等的随机值列表,用于轮盘赌选择个体
    rand_list.sort()
    fit_index = 0
    new_index = 0
    new_population = chromosome_list.copy()
    '''个体选择 start'''
    while new_index < len(chromosome_list):
        if rand_list[new_index] < fit_ratio_add[fit_index]:
            new_population[new_index] = chromosome_list[fit_index]
            new_index = new_index + 1
        else:
            fit_index = fit_index + 1
    '''个体选择 end'''
    return new_population

交叉算子

交叉算子用来模拟自然状态中的交配过程,算法中为了简化此过程,直接将两个个体的部分染色体交换

参考代码

def exchange(chromosome_list, pc):
    """
    交叉
    :param chromosome_list: 二维列表的种群
    :param pc: 交叉概率
    """
    for i in range(0, len(chromosome_list) - 1, 2):
        if random.uniform(0, 1) < pc:
            c_point = random.randint(0, len(chromosome_list[0]))    # 随机生成交叉点
            '''对第i位和i+1位进行交叉 start'''
            exchanged_list1 = []
            exchanged_list2 = []
            exchanged_list1.extend(chromosome_list[i][0:c_point])
            exchanged_list1.extend(chromosome_list[i + 1][c_point:len(chromosome_list[i])])
            exchanged_list2.extend(chromosome_list[i + 1][0:c_point])
            exchanged_list2.extend(chromosome_list[i][c_point:len(chromosome_list[i])])
            '''对第i位和i+1位进行交叉 end'''

            '''将新交叉后的染色体替换原染色体 start'''
            chromosome_list[i] = exchanged_list1
            chromosome_list[i + 1] = exchanged_list2
            '''将新交叉后的染色体替换原染色体 end'''

变异算子

变异过程模拟了自然状态中的基因突变

参考代码

def mutation(chromosome_list, pm):
    """
    变异
    :param chromosome_list: 二维列表的种群
    :param pm: 变异概率
    """
    for i in range(len(chromosome_list)):
        if random.uniform(0, 1) < pm:
            m_point = random.randint(0, len(chromosome_list[0]) - 1)    # 随机生成变异点
            chromosome_list[i][m_point] = chromosome_list[i][m_point] ^ 1   # 将该位的值与1异或(即将0置为1,1置为0)

优化

其实只实现上述函数,一个完整的遗传算法过程就可以实现了,但是实际操作中,我们可以对算法过程进行一些优化,让结果更符合我们的预期

  1. 使用精英保留策略,将最优个体直接保留到下一代,而不经过选择过程
  2. 在每一代中直接淘汰一部分不符合预期的个体,例如去掉适应度为负数的个体

完整代码

# coding=utf-8
# @Author: GongDeFeng
import random
import numpy as np
import matplotlib.pyplot as plt

population_size = 50                        # 种群初始规模
generation_count = 50                       # 遗传代数
gene_length = 23                            # 染色体长度
exchange_ratio = 0.8                        # 交叉概率
variation_ratio = 0.01                      # 变异概率
solve_max = True                            # 为True则求解最大值,为False则求解最小值
function = lambda x: x * np.sin(x) + 1      # 需要求解的数学函数
x_min = 0                                   # 基因的最小值,即变量x能取到的最小值
x_max = 2 * np.pi                           # 基因的最大值,即变量x能取到的最大值

plt.rcParams['font.sans-serif'] = ['FangSong']  # 设置中文字体
plt.rcParams['axes.unicode_minus'] = False  # 支持负号显示


def get_chromosome(size, length):
    """
    生成size个长度为length的染色体列表
    :param size: 种群规模规模
    :param length: 染色体长度
    :return: 二维列表
    """
    population_temp = []
    for i in range(size):
        population_temp.append([random.randint(0, 1) for _ in range(length)])   # 生成长度为length的随机二进制列表,并存放到population_temp列表中
    return population_temp


def get_accuracy(min_, max_, length):
    """
    计算搜索精度
    :param min_: 基因的最小值
    :param max_: 基因的最大值
    :param length: 染色体长度
    :return: 精度
    """
    return (max_ - min_) / (2 ** length - 1)    # 精度计算公式


def chromosome_decode(chromosome_list, min_, accuracy_):
    """
    染色体解码
    :param chromosome_list: 二进制染色体列表
    :param min_: 基因的最小值
    :param accuracy_: 精度
    :return: 解码的结果
    """
    decimal = int(''.join([str(i) for i in chromosome_list]), 2)    # 二进制列表转为十进制整型
    return min_ + accuracy_ * decimal   # 解码公式


def get_fitness(x, solve_flag):
    """
    计算适应度
    :param x: 染色体解码的结果
    :param solve_flag: 求最大值则为True,最小值则为False
    :return: 适应度结果
    """
    if solve_flag:
        return function(x)
    return -(function(x))


def select(chromosome_list, fitness_list):
    """
    选择(轮盘赌算法)
    :param chromosome_list: 二维列表的种群
    :param fitness_list: 适应度列表
    :return: 选择之后的种群列表
    """
    population_fitness = np.array(fitness_list).sum()  # 种群适应度
    fit_ratio = [i / population_fitness for i in fitness_list]  # 每个个体占种群适应度的比例
    fit_ratio_add = [0]  # 个体累计概率
    for i in fit_ratio:
        fit_ratio_add.append(fit_ratio_add[len(fit_ratio_add) - 1] + i)     # 计算每个个体的累计概率,并存放到fit_ratio_add中
    fit_ratio_add = fit_ratio_add[1:]   # 去掉首位的0

    rand_list = [random.uniform(0, 1) for _ in chromosome_list]     # 生成和种群规模相等的随机值列表,用于轮盘赌选择个体
    rand_list.sort()
    fit_index = 0
    new_index = 0
    new_population = chromosome_list.copy()
    '''个体选择 start'''
    while new_index < len(chromosome_list):
        if rand_list[new_index] < fit_ratio_add[fit_index]:
            new_population[new_index] = chromosome_list[fit_index]
            new_index = new_index + 1
        else:
            fit_index = fit_index + 1
    '''个体选择 end'''
    return new_population


def exchange(chromosome_list, pc):
    """
    交叉
    :param chromosome_list: 二维列表的种群
    :param pc: 交叉概率
    """
    for i in range(0, len(chromosome_list) - 1, 2):
        if random.uniform(0, 1) < pc:
            c_point = random.randint(0, len(chromosome_list[0]))    # 随机生成交叉点
            '''对第i位和i+1位进行交叉 start'''
            exchanged_list1 = []
            exchanged_list2 = []
            exchanged_list1.extend(chromosome_list[i][0:c_point])
            exchanged_list1.extend(chromosome_list[i + 1][c_point:len(chromosome_list[i])])
            exchanged_list2.extend(chromosome_list[i + 1][0:c_point])
            exchanged_list2.extend(chromosome_list[i][c_point:len(chromosome_list[i])])
            '''对第i位和i+1位进行交叉 end'''

            '''将新交叉后的染色体替换原染色体 start'''
            chromosome_list[i] = exchanged_list1
            chromosome_list[i + 1] = exchanged_list2
            '''将新交叉后的染色体替换原染色体 end'''


def mutation(chromosome_list, pm):
    """
    变异
    :param chromosome_list: 二维列表的种群
    :param pm: 变异概率
    """
    for i in range(len(chromosome_list)):
        if random.uniform(0, 1) < pm:
            m_point = random.randint(0, len(chromosome_list[0]) - 1)    # 随机生成变异点
            chromosome_list[i][m_point] = chromosome_list[i][m_point] ^ 1   # 将该位的值与1异或(即将0置为1,1置为0)


def get_best(fitness_list):
    """
    计算这一代中的最优个体
    :param fitness_list: 适应度列表
    :return: 最优个体的下标
    """
    return fitness_list.index(max(fitness_list))


def eliminate(fitness_list):
    """
    淘汰(去掉负值)
    :param fitness_list: 适应度列表
    :return: 淘汰后的列表
    """
    fit_value = []
    for i in range(len(fitness_list)):
        fit_value.append(fitness_list[i] if fitness_list[i] >= 0 else 0.0)   # 将小于0的适应度置为0
    return fit_value


if __name__ == '__main__':
    results = []  # 存储每一代的最优解,二维列表
    all_fitness = []    # 存放每一代中的最高适应度和种群适应度
    population = get_chromosome(population_size, gene_length)   # 种群初始化
    for _ in range(generation_count):
        accuracy = get_accuracy(x_min, x_max, gene_length)  # 计算搜索精度
        decode_list = [chromosome_decode(individual, x_min, accuracy) for individual in population]  # 解码之后的列表
        fit_list = [get_fitness(decode_i, solve_max) for decode_i in decode_list]  # 计算每个个体的适应度
        fit_list = eliminate(fit_list)  # 淘汰一部分,去掉负值
        results.append([decode_list[get_best(fit_list)],
                        fit_list[get_best(fit_list)] if solve_max else -fit_list[get_best(fit_list)]])  # 保存每一代最优解,即适应度最高的个体
        all_fitness.append(np.array(fit_list).sum() if solve_max else -np.array(fit_list).sum())    # 保存每一代中的最高适应度和种群适应度
        population = select(population.copy(), fit_list)
        exchange(population, exchange_ratio)
        mutation(population, variation_ratio)

    if solve_max:
        results.sort(key=lambda x: x[1])
    else:
        results.sort(key=lambda x: x[1], reverse=True)
    print('最{}值点 x={},y={}'.format('大' if solve_max else '小', results[-1][0], results[-1][1]))

    '''绘制极值趋势图和种群适应度趋势图 start'''
    X = [generation_i for generation_i in range(generation_count)]
    Y1 = [results[generation_i][1] for generation_i in range(generation_count)]
    Y2 = [all_fitness[generation_i] for generation_i in range(generation_count)]

    fig1 = plt.figure('figure', figsize=(13, 5)).add_subplot(121)
    fig1.plot(X, Y1)
    fig2 = plt.figure('figure', figsize=(13, 5)).add_subplot(122)
    fig2.plot(X, Y2)

    fig1.set_title('极值点趋势图')
    fig1.set_xlabel("遗传代数")
    fig1.set_ylabel("极值")
    fig2.set_title('种群整体适应度趋势图')
    fig2.set_xlabel("遗传代数")
    fig2.set_ylabel("种群适应度")

    plt.show()
    '''绘制极值趋势图和种群适应度趋势图 end'''

热门文章

暂无图片
编程学习 ·

exe4j详细使用教程(附下载安装链接)

一、exe4j介绍 ​ exe4j是一个帮助你集成Java应用程序到Windows操作环境的java可执行文件生成工具&#xff0c;无论这些应用是用于服务器&#xff0c;还是图形用户界面&#xff08;GUI&#xff09;或命令行的应用程序。如果你想在任务管理器中及Windows XP分组的用户友好任务栏…
暂无图片
编程学习 ·

AUTOSAR从入门到精通100讲(126)-浅谈车载充电系统通信方案

01 引言 本文深入研究车载充电系统策略,设计出一套基于电动汽车电池管理系统与车载充电机的CAN通信协议,可供电动汽车设计人员参考借鉴。 02 电动汽车充电系统通讯网络 电动汽车整车控制系统中采用的是CAN总线通信方式,由一个整车内部高速CAN网络、内部低速CAN网络和一个充电…
暂无图片
编程学习 ·

CMake(九):生成器表达式

当运行CMake时&#xff0c;开发人员倾向于认为它是一个简单的步骤&#xff0c;需要读取项目的CMakeLists.txt文件&#xff0c;并生成相关的特定于生成器的项目文件集(例如Visual Studio解决方案和项目文件&#xff0c;Xcode项目&#xff0c;Unix Makefiles或Ninja输入文件)。然…
暂无图片
编程学习 ·

47.第十章 网络协议和管理配置 -- 网络配置(八)

4.3.3 route 命令 路由表管理命令 路由表主要构成: Destination: 目标网络ID,表示可以到达的目标网络ID,0.0.0.0/0 表示所有未知网络,又称为默认路由,优先级最低Genmask:目标网络对应的netmaskIface: 到达对应网络,应该从当前主机哪个网卡发送出来Gateway: 到达非直连的网络,…
暂无图片
编程学习 ·

元宇宙技术基础

请看图&#xff1a; 1、通过AR、VR等交互技术提升游戏的沉浸感 回顾游戏的发展历程&#xff0c;沉浸感的提升一直是技术突破的主要方向。从《愤怒的小鸟》到CSGO,游戏建模方式从2D到3D的提升使游戏中的物体呈现立体感。玩家在游戏中可以只有切换视角&#xff0c;进而提升沉浸…
暂无图片
编程学习 ·

flink的伪分布式搭建

一 flink的伪分布式搭建 1.1 执行架构图 1.Flink程序需要提交给 Job Client2.Job Client将作业提交给 Job Manager3.Job Manager负责协调资源分配和作业执行。 资源分配完成后&#xff0c;任务将提交给相应的 Task Manage。4.Task Manager启动一个线程以开始执行。Task Manage…
暂无图片
编程学习 ·

十进制正整数与二进制字符串的转换(C++)

Function one&#xff1a; //十进制数字转成二进制字符串 string Binary(int x) {string s "";while(x){if(x % 2 0) s 0 s;else s 1 s;x / 2;}return s; } Function two&#xff1a; //二进制字符串变为十进制数字 int Decimal(string s) {int num 0, …
暂无图片
编程学习 ·

[含lw+源码等]微信小程序校园辩论管理平台+后台管理系统[包运行成功]Java毕业设计计算机毕设

项目功能简介: 《微信小程序校园辩论管理平台后台管理系统》该项目含有源码、论文等资料、配套开发软件、软件安装教程、项目发布教程等 本系统包含微信小程序做的辩论管理前台和Java做的后台管理系统&#xff1a; 微信小程序——辩论管理前台涉及技术&#xff1a;WXML 和 WXS…
暂无图片
编程学习 ·

树莓派驱动DHT11温湿度传感器

1&#xff0c;直接使用python库 代码如下 import RPi.GPIO as GPIO import dht11 import time import datetimeGPIO.setwarnings(True) GPIO.setmode(GPIO.BCM)instance dht11.DHT11(pin14)try:while True:result instance.read()if result.is_valid():print(ok)print(&quo…
暂无图片
编程学习 ·

ELK简介

ELK简介 ELK是三个开源软件的缩写&#xff0c;Elasticsearch、Logstash、Kibana。它们都是开源软件。不过现在还新增了一个 Beats&#xff0c;它是一个轻量级的日志收集处理工具(Agent)&#xff0c;Beats 占用资源少&#xff0c;适合于在各个服务器上搜集日志后传输给 Logstas…
暂无图片
编程学习 ·

Linux 基础

通常大数据框架都部署在 Linux 服务器上&#xff0c;所以需要具备一定的 Linux 知识。Linux 书籍当中比较著名的是 《鸟哥私房菜》系列&#xff0c;这个系列很全面也很经典。但如果你希望能够快速地入门&#xff0c;这里推荐《Linux 就该这么学》&#xff0c;其网站上有免费的电…
暂无图片
编程学习 ·

Windows2022 无线网卡装不上驱动

想来 Windows2022 和 windows10/11 的驱动应该差不多通用的&#xff0c;但是死活装不上呢&#xff1f; 搜一下&#xff0c;有人提到 “默认安装时‘无线LAN服务’是关闭的&#xff0c;如果需要开启&#xff0c;只需要在“添加角色和功能”中&#xff0c;选择开启“无线LAN服务…
暂无图片
编程学习 ·

【嵌入式面试宝典】版本控制工具Git常用命令总结

目录 创建仓库 查看信息 版本回退 版本检出 远程库 Git 创建仓库 git initgit add <file> 可反复多次使用&#xff0c;添加多个文件git commit -m <message> 查看信息 git status 仓库当前的状态git diff 差异对比git log 历史记录&#xff0c;提交日志--pret…
暂无图片
编程学习 ·

用Postman生成测试报告

newman newman是一款基于nodejs开发的可以运行postman脚本的工具&#xff0c;使用Newman&#xff0c;可以直接从命令运行和测试postman集合。 安装nodejs 下载地址&#xff1a;https://nodejs.org/en/download/ 选择自己系统相对应的版本内容进行下载&#xff0c;然后傻瓜式安…
暂无图片
编程学习 ·

Java面向对象之多态、向上转型和向下转型

文章目录前言一、多态二、引用类型之间的转换Ⅰ.向上转型Ⅱ.向下转型总结前言 今天继续Java面向对象的学习&#xff0c;学习面向对象的第三大特征&#xff1a;多态&#xff0c;了解多态的意义&#xff0c;以及两种引用类型之间的转换&#xff1a;向上转型、向下转型。  希望能…