python 如何实现遗传算法

1、基本概念

遗传算法(GA)是最早由美国Holland教授提出的一种基于自然界的“适者生存,优胜劣汰”基本法则的智能搜索算法。该法则很好地诠释了生物进化的自然选择过程。遗传算法也是借鉴该基本法则,通过基于种群的思想,将问题的解通过编码的方式转化为种群中的个体,并让这些个体不断地通过选择、交叉和变异算子模拟生物的进化过程,然后利用“优胜劣汰”法则选择种群中适应性较强的个体构成子种群,然后让子种群重复类似的进化过程,直到找到问题的最优解或者到达一定的进化(运算)时间。

基因:在GA算法中,基因代表了具体问题解的一个决策变量,问题解和染色体中基因的对应关系如下所示:

种群:多个个体即组成一个种群。GA算法中,一个问题的多组解即构成了问题的解的种群。

2、主要步骤

GA算法的基本步骤如下:

Step 1. 种群初始化。选择一种编码方案然后在解空间内通过随机生成的方式初始化一定数量的个体构成GA的种群。

Step 2. 评估种群。利用启发式算法对种群中的个体(矩形件的排入顺序)生成排样图并依此计算个体的适应函数值(利用率),然后保存当前种群中的最优个体作为搜索到的最优解。

Step 3. 选择操作。根据种群中个体的适应度的大小,通过轮盘赌或者期望值方法,将适应度高的个体从当前种群中选择出来。

Step 4. 交叉操作。将上一步骤选择的个体,用一定的概率阀值Pc控制是否利用单点交叉、多点交叉或者其他交叉方式生成新的交叉个体。

Step 5. 变异操作。用一定的概率阀值Pm控制是否对个体的部分基因执行单点变异或多点变异。

Step 6. 终止判断。若满足终止条件,则终止算法,否则返回Step 2。

流程图如下所示:

3、主要操作介绍

3.1 种群初始化

种群的初始化和具体的问题有关。比如一个问题有n个决策变量{x1,x2,…,xn}。每个决策变量有取值范围:下界{L1,L2,…,Ln}和上界{U1,U2,…,Un},则种群中个体的初始化即随机地在决策变量的取值范围内生成各个决策变量的值:Xj={x1,x2,...,xn},其中xi属于范围(Li,Ui)内。所有的个体即构成种群。当每个个体都初始化后,即种群完成初始化。

3.2 评价种群

种群的评价即计算种群中个体的适应度值。假设种群population有popsize个个体。依次计算每个个体的适应度值及评价种群。

3.3 选择操作

GA算法中常见的选择操作有轮盘赌方式:种群中适应度值更优的个体被选择的概率越大。假设popsize=4,按照如下表达式计算各个个体的被选择概率的大小,然后用圆饼图表示如下。

P(Xj) = fit(Xj)/(fit(X1)+fit(X2)+fit(X3)+fit(X4)),j=1,2,3,4

当依据轮盘赌方式进行选择时,则概率越大的越容易被选择到。

3.4 交叉操作

交叉操作也有许多种:单点交叉,两点交叉等。此处仅讲解一下两点交叉。首先利用选择操作从种群中选择两个父辈个体parent1和parent2,然后随机产生两个位置pos1和pos2,将这两个位置中间的基因位信息进行交换,便得到下图所示的off1和off2两个个体,但是这两个个体中一般会存在基因位信息冲突的现象(整数编码时),此时需要对off1和off2个体进行调整:off1中的冲突基因根据parent1中的基因调整为parent2中的相同位置处的基因。如off1中的“1”出现了两次,则第二处的“1”需要调整为parent1中“1”对应的parent2中的“4”,依次类推处理off1中的相冲突的基因。需要注意的是,调整off2,则需要参考parent2。

3.5 变异操作

变异操作的话,根据不同的编码方式有不同的变异操作。

如果是浮点数编码,则变异可以就染色体中间的某一个基因位的信息进行变异(重新生成或者其他调整方案)。

如果是采用整数编码方案,则一般有多种变异方法:位置变异和符号变异。

位置变异:

符号变异:

4、Python代码

#-*- coding:utf-8 -*-

import random
import math
from operator import itemgetter

class Gene:
  '''
  This is a class to represent individual(Gene) in GA algorithom
  each object of this class have two attribute: data, size
  '''
  def __init__(self,**data):
    self.__dict__.update(data)
    self.size = len(data['data'])#length of gene

class GA:
  '''
  This is a class of GA algorithm.
  '''
  def __init__(self,parameter):
    '''
    Initialize the pop of GA algorithom and evaluate the pop by computing its' fitness value .
    The data structure of pop is composed of several individuals which has the form like that:

    {'Gene':a object of class Gene, 'fitness': 1.02(for example)}

    Representation of Gene is a list: [b s0 u0 sita0 s1 u1 sita1 s2 u2 sita2]

    '''
    #parameter = [CXPB, MUTPB, NGEN, popsize, low, up]
    self.parameter = parameter

    low = self.parameter[4]
    up = self.parameter[5]

    self.bound = []
    self.bound.append(low)
    self.bound.append(up)

    pop = []
    for i in range(self.parameter[3]):
      geneinfo = []
      for pos in range(len(low)):
        geneinfo.append(random.uniform(self.bound[0][pos], self.bound[1][pos]))#initialise popluation

      fitness = evaluate(geneinfo)#evaluate each chromosome
      pop.append({'Gene':Gene(data = geneinfo), 'fitness':fitness})#store the chromosome and its fitness

    self.pop = pop
    self.bestindividual = self.selectBest(self.pop)#store the best chromosome in the population

  def selectBest(self, pop):
    '''
    select the best individual from pop
    '''
    s_inds = sorted(pop, key = itemgetter("fitness"), reverse = False)
    return s_inds[0]

  def selection(self, individuals, k):
    '''
    select two individuals from pop
    '''
    s_inds = sorted(individuals, key = itemgetter("fitness"), reverse=True)#sort the pop by the reference of 1/fitness
    sum_fits = sum(1/ind['fitness'] for ind in individuals) #sum up the 1/fitness of the whole pop

    chosen = []
    for i in xrange(k):
      u = random.random() * sum_fits#randomly produce a num in the range of [0, sum_fits]
      sum_ = 0
      for ind in s_inds:
        sum_ += 1/ind['fitness']#sum up the 1/fitness
        if sum_ > u:
          #when the sum of 1/fitness is bigger than u, choose the one, which means u is in the range of [sum(1,2,...,n-1),sum(1,2,...,n)] and is time to choose the one ,namely n-th individual in the pop
          chosen.append(ind)
          break

    return chosen  

  def crossoperate(self, offspring):
    '''
    cross operation
    '''
    dim = len(offspring[0]['Gene'].data)

    geninfo1 = offspring[0]['Gene'].data#Gene's data of first offspring chosen from the selected pop
    geninfo2 = offspring[1]['Gene'].data#Gene's data of second offspring chosen from the selected pop

    pos1 = random.randrange(1,dim)#select a position in the range from 0 to dim-1,
    pos2 = random.randrange(1,dim)

    newoff = Gene(data = [])#offspring produced by cross operation
    temp = []
    for i in range(dim):
      if (i >= min(pos1,pos2) and i <= max(pos1,pos2)):
        temp.append(geninfo2[i])
        #the gene data of offspring produced by cross operation is from the second offspring in the range [min(pos1,pos2),max(pos1,pos2)]
      else:
        temp.append(geninfo1[i])
        #the gene data of offspring produced by cross operation is from the frist offspring in the range [min(pos1,pos2),max(pos1,pos2)]
    newoff.data = temp

    return newoff

  def mutation(self, crossoff, bound):
    '''
    mutation operation
    '''

    dim = len(crossoff.data)

    pos = random.randrange(1,dim)#chose a position in crossoff to perform mutation.

    crossoff.data[pos] = random.uniform(bound[0][pos],bound[1][pos])
    return crossoff

  def GA_main(self):
    '''
    main frame work of GA
    '''

    popsize = self.parameter[3]

    print("Start of evolution")

    # Begin the evolution
    for g in range(NGEN):

      print("-- Generation %i --" % g)   

      #Apply selection based on their converted fitness
      selectpop = self.selection(self.pop, popsize)  

      nextoff = []
      while len(nextoff) != popsize:
        # Apply crossover and mutation on the offspring      

        # Select two individuals
        offspring = [random.choice(selectpop) for i in xrange(2)]

        if random.random() < CXPB: # cross two individuals with probability CXPB
          crossoff = self.crossoperate(offspring)
          fit_crossoff = evaluate(self.xydata, crossoff.data)# Evaluate the individuals      

          if random.random() < MUTPB: # mutate an individual with probability MUTPB
            muteoff = self.mutation(crossoff,self.bound)
            fit_muteoff = evaluate(self.xydata, muteoff.data)# Evaluate the individuals
            nextoff.append({'Gene':muteoff,'fitness':fit_muteoff})

      # The population is entirely replaced by the offspring
      self.pop = nextoff

      # Gather all the fitnesses in one list and print the stats
      fits = [ind['fitness'] for ind in self.pop]

      length = len(self.pop)
      mean = sum(fits) / length
      sum2 = sum(x*x for x in fits)
      std = abs(sum2 / length - mean**2)**0.5
      best_ind = self.selectBest(self.pop)

      if best_ind['fitness'] < self.bestindividual['fitness']:
        self.bestindividual = best_ind

      print("Best individual found is %s, %s" % (self.bestindividual['Gene'].data,self.bestindividual['fitness']))
      print(" Min fitness of current pop: %s" % min(fits))
      print(" Max fitness of current pop: %s" % max(fits))
      print(" Avg fitness of current pop: %s" % mean)
      print(" Std of currrent pop: %s" % std)

    print("-- End of (successful) evolution --")  

if __name__ == "__main__":

  CXPB, MUTPB, NGEN, popsize = 0.8, 0.3, 50, 100#control parameters

  up = [64, 64, 64, 64, 64, 64, 64, 64, 64, 64]#upper range for variables
  low = [-64, -64, -64, -64, -64, -64, -64, -64, -64, -64]#lower range for variables
  parameter = [CXPB, MUTPB, NGEN, popsize, low, up]

  run = GA(parameter)
  run.GA_main()

以上就是python 如何实现遗传算法的详细内容,更多关于python 遗传算法的资料请关注我们其它相关文章!

(0)

相关推荐

  • python 遗传算法求函数极值的实现代码

    废话不多说,大家直接看代码吧! """遗传算法实现求函数极大值-Zjh""" import numpy as np import random import matplotlib.pyplot as plt class Ga(): """求出二进制编码的长度""" def __init__(self): self.boundsbegin = -2 self.boundsend = 3 p

  • 遗传算法之Python实现代码

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

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

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

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

    目标函数 编码方式 本程序采用的是二进制编码精确到小数点后五位,经过计算可知对于 其编码长度为18,对于 其编码长度为15,因此每个基于的长度为33. 参数设置 算法步骤 设计的程序主要分为以下步骤:1.参数设置:2.种群初始化:3.用轮盘赌方法选择其中一半较好的个体作为父代:4.交叉和变异:5.更新最优解:6.对最有个体进行自学习操作:7结果输出.其算法流程图为: 算法结果 由程序输出可知其最终优化结果为38.85029, 输出基因编码为[1 1 0 0 1 0 1 1 1 1 1 1 1 0

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

    本文用Python3完整实现了简单遗传算法(SGA) Simple Genetic Alogrithm是模拟生物进化过程而提出的一种优化算法.SGA采用随机导向搜索全局最优解或者说近似全局最优解.传统的爬山算法(例如梯度下降,牛顿法)一次只优化一个解,并且对于多峰的目标函数很容易陷入局部最优解,而SGA算法一次优化一个种群(即一次优化多个解),SGA比传统的爬山算法更容易收敛到全局最优解或者近似全局最优解. SGA基本流程如下: 1.对问题的解进行二进制编码.编码涉及精度的问题,在本例中精度de

  • 遗传算法python版

    本文实例为大家分享了python遗传算法的具体代码,供大家参考,具体内容如下 1.基本概念 遗传算法(GA)是最早由美国Holland教授提出的一种基于自然界的"适者生存,优胜劣汰"基本法则的智能搜索算法.该法则很好地诠释了生物进化的自然选择过程.遗传算法也是借鉴该基本法则,通过基于种群的思想,将问题的解通过编码的方式转化为种群中的个体,并让这些个体不断地通过选择.交叉和变异算子模拟生物的进化过程,然后利用"优胜劣汰"法则选择种群中适应性较强的个体构成子种群,然后让

  • Python使用遗传算法解决最大流问题

    本文为大家分享了Python遗传算法解决最大流问题,供大家参考,具体内容如下 Generate_matrix def Generate_matrix(x,y): import numpy as np import random return np.ceil(np.array([random.random()*10 for i in range(x*y)]).reshape(x,y)) Max_road def Max_road(A,degree,start): import random imp

  • python实现简单遗传算法

    今天整理之前写的代码,发现在做数模期间写的用python实现的遗传算法,感觉还是挺有意思的,就拿出来分享一下. 首先遗传算法是一种优化算法,通过模拟基因的优胜劣汰,进行计算(具体的算法思路什么的就不赘述了).大致过程分为初始化编码.个体评价.选择,交叉,变异. 以目标式子 y = 10 * sin(5x) + 7 * cos(4x)为例,计算其最大值 首先是初始化,包括具体要计算的式子.种群数量.染色体长度.交配概率.变异概率等.并且要对基因序列进行初始化 pop_size = 500 # 种群

  • python 如何实现遗传算法

    1.基本概念 遗传算法(GA)是最早由美国Holland教授提出的一种基于自然界的"适者生存,优胜劣汰"基本法则的智能搜索算法.该法则很好地诠释了生物进化的自然选择过程.遗传算法也是借鉴该基本法则,通过基于种群的思想,将问题的解通过编码的方式转化为种群中的个体,并让这些个体不断地通过选择.交叉和变异算子模拟生物的进化过程,然后利用"优胜劣汰"法则选择种群中适应性较强的个体构成子种群,然后让子种群重复类似的进化过程,直到找到问题的最优解或者到达一定的进化(运算)时间.

  • python实现使用遗传算法进行图片拟合

    目录 引言 预备知识及准备工作 打开图片 随机生成生物族群 按照生物性状画图 对比生物个体和目标图片的相似度 保存图片 算法主体 交叉互换 基因突变 基因片段易位 增加基因片段 减少基因片段 变异 繁殖 淘汰 拟合 示例展示 降低图片分辨率 原图 拟合过程展示 完整代码下载(已封装成类) 引言 算法思路 假设我们有这样一个生物族群,他们的每个基因片段都是一个个三角形(即只含三个点和颜色信息),他们每个个体表现出的性状就是若干个三角形叠加在一起.假设我们有一张图片可以作为这种生物族群最适应环境的性

  • python遗传算法之geatpy的深入理解

    目录 1. geatpy的安装 2. geatpy的基础数据结构 2.1 种群染色体 2.2 种群表现型 2.3 目标函数值 2.4 个体适应度 2.5 违反约束程度矩阵 2.6 译码矩阵 2.7 进化追踪器 3. geatpy的种群结构 3.1 Population类 3.2 PsyPopulation类 4. 求解标准测试函数——McCormick函数 5.参考文章 今天我们来学习python中的遗传算法的使用,我们这里使用的是geatpy的包进行学习,本博客主要从geatpy中的各种数据结

  • AI与Python人工智能遗传算法

    目录 什么是遗传算法? 如何使用GA进行优化问题? GA机制优化过程的阶段 安装必要的软件包 使用遗传算法实现解决方案 生成位模式 符号回归问题 本章详细讨论了人工智能的遗传算法. 什么是遗传算法? 遗传算法(GA)是基于自然选择和遗传概念的基于搜索的算法.GA是更大的计算分支的子集,称为进化计算. GA由John Holland及其密歇根大学的学生和同事开发,最着名的是David E. Goldberg.从那以后,已经尝试了各种优化问题并取得了很大的成功. 在GA中,我们有一组可能的解决方案来

  • Python决策树和随机森林算法实例详解

    本文实例讲述了Python决策树和随机森林算法.分享给大家供大家参考,具体如下: 决策树和随机森林都是常用的分类算法,它们的判断逻辑和人的思维方式非常类似,人们常常在遇到多个条件组合问题的时候,也通常可以画出一颗决策树来帮助决策判断.本文简要介绍了决策树和随机森林的算法以及实现,并使用随机森林算法和决策树算法来检测FTP暴力破解和POP3暴力破解,详细代码可以参考: https://github.com/traviszeng/MLWithWebSecurity 决策树算法 决策树表现了对象属性和

  • python实现K最近邻算法

    KNN核心算法函数,具体内容如下 #! /usr/bin/env python3 # -*- coding: utf-8 -*- # fileName : KNNdistance.py # author : zoujiameng@aliyun.com.cn import math def getMaxLocate(target): # 查找target中最大值的locate maxValue = float("-inFinIty") for i in range(len(target)

随机推荐