遗传算法-python

• 注：有很多python-GA的库，deap、gaft等，这里选取了一个比较好上手的gaft

简介

• 遗传算法主要包括适应度函数、选择、交叉、变异生成新的个体几个模块，初始化种群大小，然后计算所有个体的适应度，(使用轮盘概率的方法)选择适应度最大的个体，进行交叉、变异生成新个体，并计算适应度，淘汰掉那些具有很低适应度的个体。以此往复，直到达到程序退出条件。
• 参考文献
  
  • https://zhuanlan.zhihu.com/p/28328304
  • http://pytlab.org/2017/07/23/gaft-%E4%B8%80%E4%B8%AA%E5%9F%BA%E4%BA%8EPython%E7%9A%84%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95%E6%A1%86%E6%9E%B6/
• 本文中主要使用了gaft用于GA算法的实现

gaft安装和使用

• 一句命令行就可以完成，官网的链接：https://github.com/PytLab/gaft，上面也有一些其他的博客链接，介绍了基于gaft的GA的应用和优化
• 使用的过程中，主要是按照以下的代码框架编写程序，关于具体的参数解释，在代码中注释给出。有些官网的example可能没有解释。

使用中可能会碰到的问题

• windows下如果使用pip install的时候如果报错，可以先使用easy_install pip安装pip，之后即可使用pip进行安装。
• 在初始化生成种群时，一定要保证eps小于对应变量的范围，否则会报错。
• python中import之后，即使修改了原来的包，也不会更新导入的内容，因此需要reload。在python3之后可以使用importlib进行引入，具体的引用方式见可视化部分的代码。参考链接：https://blog.csdn.net/liang19890820/article/details/75575122
• 为了实现多次引用，防止包名和变量名冲突，我在源码里将保存的文件名改为了dk_best_fit.py

from math import sin, cos, pi

from gaft import GAEngine
from gaft.components import BinaryIndividual
from gaft.components import Population
from gaft.operators import TournamentSelection
from gaft.operators import RouletteWheelSelection
from gaft.operators import UniformCrossover
from gaft.operators import FlipBitBigMutation

# Built-in best fitness analysis.
from gaft.analysis.fitness_store import FitnessStore
from gaft.analysis.console_output import ConsoleOutput

# Define population.
# 变量的范围以及精度，eps可以是1个值或者是1个list，长度是变量的个数
indv_template = BinaryIndividual(ranges=[(-2, 2), (-2, 2)], eps=[0.0001, 0.0001])

# 种群中个体个数为50个
population = Population(indv_template=indv_template, size=50).init()

# Create genetic operators.
#selection = RouletteWheelSelection()
# 选择个体用于后续产生后代，
# 随机产生
# selection = TournamentSelection()
# 使用轮盘法，选择适应度最高的个体
selection = RouletteWheelSelection()

# UniformCrossover表示个体的每个位都有交换的可能性(每个位进行交换的概率为pe)
# pc的含义为进行交叉操作的概率(整体)
crossover = UniformCrossover(pc=0.8, pe=0.5)
# 定义变异操作，pm表示当前step进行变异的概率
# 这里的FlipBitBigMutation是为了防止陷入局部最优的，也可以使用FlipBitMutation
# pbm和alpha是为了之后结合engine修正pm的
# pbm取一个大于5pm的在(0,1)内的值，alpha取一个(0.5,1.0)内的值即可
mutation = FlipBitBigMutation(pm=0.1, pbm=0.55, alpha=0.6)

# Create genetic algorithm engine.
# Here we pass all built-in analysis to engine constructor.
engine = GAEngine(population=population, selection=selection,
                  crossover=crossover, mutation=mutation,
                  #analysis=[ FitnessStore])
                  analysis=[ConsoleOutput, FitnessStore])

# Define fitness function.
# 如果优化目标是最小化目标函数
# 则可以加上装饰器如下
# 如果加上这个装饰器，相当于返回值加了一个负号，之后还得自己取反
# 因此我建议如果是需要最小化，则可以自己手动修改优化函数(取反即可)，更加方便自己的理解
# 注意：在这里添加适应度函数，如果是其他的方法，使用GA调参之类的，则可以将其他的算法卸载fitness中
@engine.fitness_register
# @engine.minimize # 最小化的装饰器
def fitness(indv):
    x, y = indv.solution
    ret = y*sin(2*pi*x) + x*cos(2*pi*y) + 10
    return ret

# 会生成best_fit.py，里面存储了迭代过程中的最优点以及目标函数的信息
# 进行30次种群进化
engine.run(ng=30)

gaft.ConsoleOutput   INFO     Generation number: 30 Population number: 50
gaft.ConsoleOutput   INFO     Generation: 1, best fitness: 12.866, scaled fitness: 12.866
gaft.ConsoleOutput   INFO     Generation: 2, best fitness: 12.866, scaled fitness: 12.866
gaft.ConsoleOutput   INFO     Generation: 3, best fitness: 12.866, scaled fitness: 12.866
gaft.ConsoleOutput   INFO     Generation: 4, best fitness: 12.866, scaled fitness: 12.866
gaft.ConsoleOutput   INFO     Generation: 5, best fitness: 12.866, scaled fitness: 12.866
gaft.ConsoleOutput   INFO     Generation: 6, best fitness: 13.123, scaled fitness: 13.123
gaft.ConsoleOutput   INFO     Generation: 7, best fitness: 13.123, scaled fitness: 13.123
gaft.ConsoleOutput   INFO     Generation: 8, best fitness: 13.126, scaled fitness: 13.126
gaft.ConsoleOutput   INFO     Generation: 9, best fitness: 13.126, scaled fitness: 13.126
gaft.ConsoleOutput   INFO     Generation: 10, best fitness: 13.126, scaled fitness: 13.126
gaft.ConsoleOutput   INFO     Generation: 11, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 12, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 13, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 14, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 15, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 16, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 17, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 18, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 19, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 20, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 21, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 22, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 23, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 24, best fitness: 13.224, scaled fitness: 13.224
gaft.ConsoleOutput   INFO     Generation: 25, best fitness: 13.472, scaled fitness: 13.472
gaft.ConsoleOutput   INFO     Generation: 26, best fitness: 13.472, scaled fitness: 13.472
gaft.ConsoleOutput   INFO     Generation: 27, best fitness: 13.472, scaled fitness: 13.472
gaft.ConsoleOutput   INFO     Generation: 28, best fitness: 13.472, scaled fitness: 13.472
gaft.ConsoleOutput   INFO     Generation: 29, best fitness: 13.472, scaled fitness: 13.472
gaft.ConsoleOutput   INFO     Generation: 30, best fitness: 13.472, scaled fitness: 13.472
gaft.ConsoleOutput   INFO     Optimal solution: ([1.6990966796875, -1.9512939453125], 13.472490804036644)
gaft.FitnessStore   INFO     Best fitness values are written to best_fit.py

import matplotlib.pyplot as plt
import importlib
import os
# 先重载这个文件
# wozai
import dk_best_fit
importlib.reload( dk_best_fit )
# 再引入这个变量，如果先引入变量再重载文件，则无效
from dk_best_fit import best_fit


steps, variants, fits = list(zip(*best_fit))
best_step, best_v, best_f = steps[-1], variants[-1], fits[-1]

fig = plt.figure()
ax = fig.add_subplot(111)
ax.plot(steps, fits)
ax.set_xlabel('Generation')
ax.set_ylabel('Fitness')

# Plot the maximum.
ax.scatter([best_step], [best_f], facecolor='r')
ax.annotate(s='x: [{:.2f}, {:.2f}]\ny:{:.2f}'.format(*best_v, best_f),
                                                     xy=(best_step, best_f),
                                                     xytext=(best_step, best_f-0.1))


plt.show()

<matplotlib.figure.Figure at 0x7ebf908>

后续的开发

分析结果的保存修改

• 之前只能保存到best_fit.py中，我按照官网作者的提示实现了自定义的结果保存类，里面可以定义保存的文件名，代码如下

  #!/usr/bin/env python
  # -*- coding: utf-8 -*-
  
  from ..plugin_interfaces.analysis import OnTheFlyAnalysis
  
  # 自定义文件存储
  class UserFitnessStore(OnTheFlyAnalysis):
  
      # Analysis interval.
      interval = 1
  
      # Only analyze in master process?
      master_only = True
  
      # 保存的文件名
      _save_fp = "my_best_fit.py"
  
      @property
      def save_fp(self):
          return UserFitnessStore._save_fp
  
      @save_fp.setter
      def save_fp(self, fp):
          UserFitnessStore._save_fp = fp
  
      def setup(self, ng, engine):
          # Generation numbers.
          self.ngs = []
  
          # Best fitness in each generation.
          self.fitness_values = []
  
          # Best solution.
          self.solution = []
  
      def register_step(self, g, population, engine):
          # Collect data.
          best_indv = population.best_indv(engine.fitness)
          best_fit = engine.ori_fmax
  
          self.ngs.append(g)
          self.solution.append(best_indv.solution)
          self.fitness_values.append(best_fit)
  
      def finalize(self, population, engine):
          with open(UserFitnessStore.save_fp, 'w', encoding='utf-8') as f:
              f.write('best_fit = [\n')
              for ng, x, y in zip(self.ngs, self.solution, self.fitness_values):
                  f.write('    ({}, {}, {}),\n'.format(ng, x, y))
              f.write(']\n\n')
  
          self.logger.info('Best fitness values are written to best_fit.py')
  

• 同时还需要在analysis子文件夹下的__init__.py中添加from .user_fitness_store import UserFitnessStore（按照之前有的来就行）

• 其他的分析输出的修改方法思路见：https://github.com/PytLab/gaft/issues/19