详解用python实现简单的遗传算法

今天整理之前写的代码,发现在做数模期间写的用python实现的遗传算法,感觉还是挺有意思的,就拿出来分享一下。

首先遗传算法是一种优化算法,通过模拟基因的优胜劣汰,进行计算(具体的算法思路什么的就不赘述了)。大致过程分为初始化编码、个体评价、选择,交叉,变异。

遗传算法介绍

遗传算法是通过模拟大自然中生物进化的历程,来解决问题的。大自然中一个种群经历过若干代的自然选择后,剩下的种群必定是适应环境的。把一个问题所有的解看做一个种群,经历过若干次的自然选择以后,剩下的解中是有问题的最优解的。当然,只能说有最优解的概率很大。这里,我们用遗传算法求一个函数的最大值。

f(x) = 10 * sin( 5x ) + 7 * cos( 4x ),    0 <=  x <= 10

1、将自变量x进行编码

取基因片段的长度为10, 则10位二进制位可以表示的范围是0到1023。基因与自变量转变的公式是x = b2d(individual) * 10 / 1023。构造初始的种群pop。每个个体的基因初始值是[0, 1, 0, 1, 0, 1, 0, 1, 0, 1]

2、计算目标函数值

根据自变量与基因的转化关系式,求出每个个体的基因对应的自变量,然后将自变量代入函数f(x),求出每个个体的目标函数值。

3、适应度函数

适应度函数是用来评估个体适应环境的能力,是进行自然选择的依据。本题的适应度函数直接将目标函数值中的负值变成0. 因为我们求的是最大值,所以要使目标函数值是负数的个体不适应环境,使其繁殖后代的能力为0.适应度函数的作用将在自然选择中体现。

4、自然选择

自然选择的思想不再赘述,操作使用轮盘赌算法。其具体步骤:

假设种群中共5个个体,适应度函数计算出来的个体适应性列表是fitvalue = [1 ,3, 0, 2, 4] ,totalvalue = 10 , 如果将fitvalue画到圆盘上,值的大小表示在圆盘上的面积。在转动轮盘的过程中,单个模块的面积越大则被选中的概率越大。选择的方法是将fitvalue转化为[1 , 4 ,4 , 6 ,10], fitvalue / totalvalue = [0.1 , 0.4 , 0.4 , 0.6 , 1.0] . 然后产生5个0-1之间的随机数,将随机数从小到大排序,假如是[0.05 , 0.2 , 0.7 , 0.8 ,0.9],则将0号个体、1号个体、4号个体、4号个体、4号个体拷贝到新种群中。自然选择的结果使种群更符合条件了。

5、繁殖

假设个体a、b的基因是

a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

这两个个体发生基因交换的概率pc = 0.6.如果要发生基因交换,则产生一个随机数point表示基因交换的位置,假设point = 4,则:

a = [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]
b = [0, 0, 0, 1, 1, 0, 1, 1, 1, 1]

交换后为:

a = [1, 0, 0, 0, 1, 0, 1, 1, 1, 1]
b = [0, 0, 0, 1, 0, 1, 1, 1, 0, 0]

6、突变

遍历每一个个体,基因的每一位发生突变(0变为1,1变为0)的概率为0.001.突变可以增加解空间

以目标式子 y = 10 * sin(5x) + 7 * cos(4x)为例,计算其最大值

首先是初始化,包括具体要计算的式子、种群数量、染色体长度、交配概率、变异概率等。并且要对基因序列进行初始化

pop_size = 500  # 种群数量
max_value = 10  # 基因中允许出现的最大值
chrom_length = 10  # 染色体长度
pc = 0.6   # 交配概率
pm = 0.01   # 变异概率
results = [[]]  # 存储每一代的最优解,N个二元组
fit_value = []  # 个体适应度
fit_mean = []  # 平均适应度
pop = geneEncoding(pop_size, chrom_length) 

其中genEncodeing是自定义的一个简单随机生成序列的函数,具体实现如下

def geneEncoding(pop_size, chrom_length):
 pop = [[]]
 for i in range(pop_size):
  temp = []
  for j in range(chrom_length):
   temp.append(random.randint(0, 1))
  pop.append(temp)
 return pop[1:] 

编码完成之后就是要进行个体评价,个体评价主要是计算各个编码出来的list的值以及对应带入目标式子的值。其实编码出来的就是一堆2进制list。这些2进制list每个都代表了一个数。其值的计算方式为转换为10进制,然后除以2的序列长度次方减一,也就是全一list的十进制减一。根据这个规则就能计算出所有list的值和带入要计算式子中的值,代码如下

# 0.0 coding:utf-8 0.0
# 解码并计算值
import math
def decodechrom(pop, chrom_length):
 temp = []
 for i in range(len(pop)):
  t = 0
  for j in range(chrom_length):
   t += pop[i][j] * (math.pow(2, j))
  temp.append(t)
 return temp 

def calobjValue(pop, chrom_length, max_value):
 temp1 = []
 obj_value = []
 temp1 = decodechrom(pop, chrom_length)
 for i in range(len(temp1)):
  x = temp1[i] * max_value / (math.pow(2, chrom_length) - 1)
  obj_value.append(10 * math.sin(5 * x) + 7 * math.cos(4 * x))
 return obj_value

有了具体的值和对应的基因序列,然后进行一次淘汰,目的是淘汰掉一些不可能的坏值。这里由于是计算最大值,于是就淘汰负值就好了

# 0.0 coding:utf-8 0.0
# 淘汰(去除负值)
def calfitValue(obj_value):
 fit_value = []
 c_min = 0
 for i in range(len(obj_value)):
  if(obj_value[i] + c_min > 0):
   temp = c_min + obj_value[i]
  else:
   temp = 0.0
  fit_value.append(temp)
 return fit_value

然后就是进行选择,这是整个遗传算法最核心的部分。选择实际上模拟生物遗传进化的优胜劣汰,让优秀的个体尽可能存活,让差的个体尽可能的淘汰。个体的好坏是取决于个体适应度。个体适应度越高,越容易被留下,个体适应度越低越容易被淘汰。具体的代码如下

# 0.0 coding:utf-8 0.0
# 选择
import random
def sum(fit_value):
 total = 0
 for i in range(len(fit_value)):
  total += fit_value[i]
 return total
def cumsum(fit_value):
 for i in range(len(fit_value)-2, -1, -1):
  t = 0
  j = 0
  while(j <= i):
   t += fit_value[j]
   j += 1
  fit_value[i] = t
  fit_value[len(fit_value)-1] = 1
def selection(pop, fit_value):
 newfit_value = []
 # 适应度总和
 total_fit = sum(fit_value)
 for i in range(len(fit_value)):
  newfit_value.append(fit_value[i] / total_fit)
 # 计算累计概率
 cumsum(newfit_value)
 ms = []
 pop_len = len(pop)
 for i in range(pop_len):
  ms.append(random.random())
 ms.sort()
 fitin = 0
 newin = 0
 newpop = pop
 # 转轮盘选择法
 while newin < pop_len:
  if(ms[newin] < newfit_value[fitin]):
   newpop[newin] = pop[fitin]
   newin = newin + 1
  else:
   fitin = fitin + 1
 pop = newpop

以上代码主要进行了3个操作,首先是计算个体适应度总和,然后在计算各自的累积适应度。这两步都好理解,主要是第三步,转轮盘选择法。这一步首先是生成基因总数个0-1的小数,然后分别和各个基因的累积个体适应度进行比较。如果累积个体适应度大于随机数则进行保留,否则就淘汰。这一块的核心思想在于:一个基因的个体适应度越高,他所占据的累计适应度空隙就越大,也就是说他越容易被保留下来。

选择完后就是进行交配和变异,这个两个步骤很好理解。就是对基因序列进行改变,只不过改变的方式不一样

交配:

# 0.0 coding:utf-8 0.0
# 交配
import random
def crossover(pop, pc):
 pop_len = len(pop)
 for i in range(pop_len - 1):
  if(random.random() < pc):
   cpoint = random.randint(0,len(pop[0]))
   temp1 = []
   temp2 = []
   temp1.extend(pop[i][0:cpoint])
   temp1.extend(pop[i+1][cpoint:len(pop[i])])
   temp2.extend(pop[i+1][0:cpoint])
   temp2.extend(pop[i][cpoint:len(pop[i])])
   pop[i] = temp1
   pop[i+1] = temp2

变异:

# 0.0 coding:utf-8 0.0
# 基因突变
import random
def mutation(pop, pm):
 px = len(pop)
 py = len(pop[0])
 for i in range(px):
  if(random.random() < pm):
   mpoint = random.randint(0, py-1)
   if(pop[i][mpoint] == 1):
    pop[i][mpoint] = 0
   else:
    pop[i][mpoint] = 1

整个遗传算法的实现完成了,总的调用入口代码如下

# 0.0 coding:utf-8 0.0
import matplotlib.pyplot as plt
import math
from calobjValue import calobjValue
from calfitValue import calfitValue
from selection import selection
from crossover import crossover
from mutation import mutation
from best import best
from geneEncoding import geneEncoding
print 'y = 10 * math.sin(5 * x) + 7 * math.cos(4 * x)'
# 计算2进制序列代表的数值
def b2d(b, max_value, chrom_length):
 t = 0
 for j in range(len(b)):
  t += b[j] * (math.pow(2, j))
 t = t * max_value / (math.pow(2, chrom_length) - 1)
 return t
pop_size = 500  # 种群数量
max_value = 10  # 基因中允许出现的最大值
chrom_length = 10  # 染色体长度
pc = 0.6   # 交配概率
pm = 0.01   # 变异概率
results = [[]]  # 存储每一代的最优解,N个二元组
fit_value = []  # 个体适应度
fit_mean = []  # 平均适应度
# pop = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1] for i in range(pop_size)]
pop = geneEncoding(pop_size, chrom_length)
for i in range(pop_size):
 obj_value = calobjValue(pop, chrom_length, max_value)  # 个体评价
 fit_value = calfitValue(obj_value)  # 淘汰
 best_individual, best_fit = best(pop, fit_value)  # 第一个存储最优的解, 第二个存储最优基因
 results.append([best_fit, b2d(best_individual, max_value, chrom_length)])
 selection(pop, fit_value)  # 新种群复制
 crossover(pop, pc)  # 交配
 mutation(pop, pm)  # 变异
results = results[1:]
results.sort()
X = []
Y = []
for i in range(500):
 X.append(i)
 t = results[i][0]
 Y.append(t)
plt.plot(X, Y)
plt.show()

最后调用了一下matplotlib包,把500代最优解的变化趋势表现出来。

完整代码可以在github查看

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • 遗传算法之Python实现代码

    写在前面 之前的文章中已经讲过了遗传算法的基本流程,并且用MATLAB实现过一遍了.这一篇文章主要面对的人群是看过了我之前的文章,因此我就不再赘述遗传算法是什么以及基本的内容了,假设大家已经知道我是怎么写遗传算法的了. Python的遗传算法主函数 我的思想是,创建一个染色体的类,其中包括了两个变量:染色体chrom与适应度fitness.因此我们就可以通过直接建立对象来作为种群中的个体. #染色体的类 class Chrom: chrom = [] fitness = 0 def showCh

  • 详解用python实现简单的遗传算法

    今天整理之前写的代码,发现在做数模期间写的用python实现的遗传算法,感觉还是挺有意思的,就拿出来分享一下. 首先遗传算法是一种优化算法,通过模拟基因的优胜劣汰,进行计算(具体的算法思路什么的就不赘述了).大致过程分为初始化编码.个体评价.选择,交叉,变异. 遗传算法介绍 遗传算法是通过模拟大自然中生物进化的历程,来解决问题的.大自然中一个种群经历过若干代的自然选择后,剩下的种群必定是适应环境的.把一个问题所有的解看做一个种群,经历过若干次的自然选择以后,剩下的解中是有问题的最优解的.当然,只

  • 详解用Python进行时间序列预测的7种方法

    数据准备 数据集(JetRail高铁的乘客数量)下载. 假设要解决一个时序问题:根据过往两年的数据(2012 年 8 月至 2014 年 8月),需要用这些数据预测接下来 7 个月的乘客数量. import pandas as pd import numpy as np import matplotlib.pyplot as plt df = pd.read_csv('train.csv') df.head() df.shape 依照上面的代码,我们获得了 2012-2014 年两年每个小时的乘

  • 详解在Python中使用Torchmoji将文本转换为表情符号

    很难找到关于如何使用Python使用DeepMoji的教程.我已经尝试了几次,后来又出现了几次错误,于是决定使用替代版本:torchMoji. TorchMoji是DeepMoji的pyTorch实现,可以在这里找到:https://github.com/huggingface/torchMoji 事实上,我还没有找到一个关于如何将文本转换为表情符号的教程.如果你也没找到,那么本文就是一个了. 安装 这些代码并不完全是我的写的,源代码可以在这个链接上找到. pip3 install torch=

  • 详解用Python调用百度地图正/逆地理编码API

    一.背景 (正)地理编码指的是:将地理位置名称转换成经纬度: 逆地理编码指的是:将经纬度转换成地理位置信息,如地名.所在的省份或城市等 百度地图提供了相应的API,可以方便调用.相应的说明文档如下: 正地理编码 逆地理编码 具体API的参数可以查看相应的"服务文档": 不过首次使用时需要申请,具体在控制台.申请AK的方式可参见其他文章. 二.源码 废话不多说,直接放源码.这里提供了Python调用这两个API的方法. #!/usr/bin/env python # -*- coding

  • 详解用python -m http.server搭一个简易的本地局域网

    工作时同事间几mb小文件的传输,一般使用QQ或者微信就足够了,但当传输文件几百MB或者几十G时,这种方法的效率就显得不足了.本篇就是简单说明一个python小功能,让大家能利用python方便的搭建一个本地局域网.跟同事测试时,速度轻松达到800mb/s. 搭建只需三步就可以: 1.设置python路径为环境变量 2.命令行输入python -m http.server 8888来搭建局域网 3.使用本机的ip地址进行访问 接下来我们一步一步看: 设置python路径为环境变量 1.先找到自己p

  • 详解基于python的图像Gabor变换及特征提取

    1.前言 在深度学习出来之前,图像识别领域北有"Gabor帮主",南有"SIFT慕容小哥".目前,深度学习技术可以利用CNN网络和大数据样本搞事情,从而取替"Gabor帮主"和"SIFT慕容小哥"的江湖地位.但,在没有大数据和算力支撑的"乡村小镇"地带,或是对付"刁民小辈","Gabor帮主"可以大显身手,具有不可撼动的地位.IT武林中,有基于C++和OpenCV,或

  • 详解使用python爬取抖音app视频(appium可以操控手机)

    记录一下如何用python爬取app数据,本文以爬取抖音视频app为例. 编程工具:pycharm app抓包工具:mitmproxy app自动化工具:appium 运行环境:windows10 思路: 假设已经配置好我们所需要的工具 1.使用mitmproxy对手机app抓包获取我们想要的内容 2.利用appium自动化测试工具,驱动app模拟人的动作(滑动.点击等) 3.将1和2相结合达到自动化爬虫的效果 一.mitmproxy/mitmdump抓包 确保已经安装好了mitmproxy,并

  • 详解用Python处理Args的3种方法

    1. sys 模块 Python 中的 sys 模块具有 argv 功能.当通过终端触发 main.py 的执行时,此功能将返回提供给 main.py 的所有命令行参数的列表.除了其他参数之外,返回列表中的第一个元素是 main.py 的路径. 考虑下面的 main.py 示例 import sys list_of_arguments = sys.argv print(list_of_args[0]) print(list_of_args[1]) print(list_of_args[2]) p

  • 详解用Python把PDF转为Word方法总结

    先讲一下为啥要写这个文章,网上其实很多这种PDF转化的代码和软件.我一直想用Python做,但是网上搜到的代码很多都不能用,很多是2.7版本的代码,再就是PDF需要用到的库在导入的时候,很多的报错,解决起来特别费劲,而且自从2021年初以来,似乎网上很少有关PDF转化的代码出现了.我在研究了很多代码和pdfminer的用法后,总结了几个方法,目前这几种方法可以解决大多数格式的转化,后面我也专门放了提取PDF表格的代码,文末有高效的免费在线工具推荐. 下面这个是我最最推荐的方法 ,简单高效 ,只要

  • 详解运行Python的神器Jupyter Notebook

    Jupyter Notebook Jupyter项目是从Ipython项目中分出去的,在Ipython3.x之前,他们两个是在一起发布的.在Ipython4.x之后,Jupyter作为一个单独的项目进行开发和管理.因为Jupyter不仅仅可以运行Python程序,它还可以执行其他流程编程语言的运行. Jupyter Notebook包括三个部分,第一个部分是一个web应用程序,提供交互式界面,可以在交互式界面中运行相应的代码. 上图是NoteBook的交互界面,我们可以对文档进行编辑,运行等操作

随机推荐