GAFT - 一个使用 Python 实现的遗传算法框架

前言

最近需要用到遗传算法来优化一些东西,最初是打算直接基于某些算法实现一个简单的函数来优化,但是感觉单纯写个非通用的函数运行后期改进算子或者别人使用起来都会带来困难,同时遗传算法基本概念和运行流程相对固定,改进也一般通过编码机制,选择策略,交叉变异算子以及参数设计等方面,对于算法的整体结构并没有大的影响。这样对于遗传算法来说,就非常适合写个相对固定的框架然后给算子、参数等留出空间以便对新算法进行测试和改进。于是就动手写了个遗传算法的小框架gaft,本文对此框架进行一些介绍并分别以一个一维搜索和二维搜索为例子对使用方法进行了介绍。

GitHub: https://github.com/PytLab/gaft
PyPI: https://pypi.python.org/pypi/gaft

目前框架只是完成了最初的版本,比较简陋,内置了几个基本的常用算子,使用者可以根据接口规则实现自定义的算子并放入框架中运行。我自己也会根据自己的需求后续添加更多的改进算子,同时改进框架使其更加通用.

正文

遗传算法介绍

这里我对遗传算法的基本概念进行简要的介绍,并阐述gaft的设计原则。

简单而言,遗传算法使用群体搜索技术,将种群代表一组问题的可行解,通过对当前种群施加选择,交叉,变异等一些列遗传操作来产生新一代的种群,并逐步是种群进化到包含近似全局最优解的状态。下面我将遗传学和遗传算法相关术语的对应关系总结一下:

术语

WX20170723-192645@2x

算法特点

  1. 以决策变量的编码作为运算对象,使得优化过程借鉴生物学中的概念成为可能
  2. 直接以目标函数作为搜索信息,确定搜索方向很范围,属于无导数优化
  3. 同时使用多个搜索点的搜索信息,算是一种隐含的并行性
  4. 是一种基于概率的搜索技术
  5. 具有自组织,自适应和自学习等特性

算法流程

算法特点

  1. 以决策变量的编码作为运算对象,使得优化过程借鉴生物学中的概念成为可能
  2. 直接以目标函数作为搜索信息,确定搜索方向很范围,属于无导数优化
  3. 同时使用多个搜索点的搜索信息,算是一种隐含的并行性
  4. 是一种基于概率的搜索技术
  5. 具有自组织,自适应和自学习等特性

算法流程

gaft 设计原则

由于遗传算法的流程相对固定,我们优化算法基本上也是在流程整体框架下对编码机制,算子,参数等进行修改,因此在写框架的时候,我便想把那些固定的遗传算子,适应度函数写成接口,并使用元类、装饰器等方式实现对接口的限制和优化,这样便可以方便后续自定义算符和适应度函数定制。最后将各个部分组合到一起组成一个engine然后根据算法流程运行遗传算法对目标进行优化.

这样我们便脱离每次都要写遗传算法流程的繁琐,每次只需要像写插件一样实现自己的算子和适应度函数便可以将其放入gaft开始对算法进行测试或者对目标函数进行优化了。

GAFT文件结构

此部分我对自己实现的框架的整体结构进行下介绍.