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

專 欄

❈PytLab,Python 中文社区专栏作者。主要从事科学计算与高性能计算领域的应用,主要语言为Python,C,C++。熟悉数值算法(最优化方法,蒙特卡洛算法等)与并行化 算法(MPI,OpenMP等多线程以及多进程并行化)以及python优化方法,经常使用C++给python写扩展。

知乎专栏:化学狗码砖的日常

blog:http://pytlab.org

github:https://github.com/PytLab

前言

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

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

正文

遗传算法介绍

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

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

术语

算法特点

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

算法流程

gaft 设计原则

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

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

GAFT文件结构

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

目前的文件结果如上所示,

  • /gaft/components中定义了内置的个体和种群类型,提供了两种不同的遗传编码方式:二进制编码和实数编码。
  • /gaft/plugin_interfaces中是插件接口定义,所有的算子定义以及on-the-fly分析的接口规则都在里面,使用者可以根据此来编写自己的插件并放入到engine中。
  • /gaft/operators里面是内置遗传算子,他们也是遵循/gaft/plugin_interfaces中的规则进行编写,可以作为编写算子的例子。其中算子我目前内置了roulette wheel选择算子,uniform 交叉算子和flipbit变异算子,使用者可以直接使用内置算子来使用gaft对自己的问题进行优化。
  • /gaft/analysis里面是内置的on-the-fly分析插件,他可以在遗传算法迭代的过程中对迭代过程中的变量进行分析,例如我在里面内置了控制台日志信息输出,以及迭代适应度值的保存等插件方便对进化曲线作图。
  • /gaft/engine便是遗传算法的流程控制模块了,他将所有的之前定义的各个部分组合到一起使用遗传算法流程进行优化迭代。

使用GAFT

下面我就以两个函数作为例子来使用GAFT对目标函数进行优化.

一维搜索

首先我们先对一个简单的具有多个局部极值的函数进行优化,我们来使用内置的算子求函数

的极大值,x的取值范围为[0,10]

1. 先导入需要的模块

2. 创建引擎

3. 自定义适应度函数

可以通过修饰符的方式将,适应度函数注册到引擎中。

4. 自定义on-the-fly分析插件

也可以通过修饰符在定义的时候直接将插件注册到引擎中

5. Ok, 开始跑(优化)吧!

我们这里跑100代种群.

内置的分析插件会在每步迭代中记录得到的每一代的最优个体,并生成数据保存。

绘制一下函数本身的曲线和我们使用遗传算法得到的进化曲线:

优化过程动画:

二维搜索

下面我们使用GAFT内置算子来搜索同样具有多个极值点的二元函数

的最大值,x, y 的范围为 [−2,2].

这里我们就不自定义分析插件了,直接使用内置的分析类,并在构造引擎时直接传入.

进化曲线:

二维函数面:

搜索过程动画:

可见目前内置的基本算子都能很好的找到例子中函数的最优点。

总结

本文主要介绍了本人开发的一个用于遗传算法做优化计算的Python框架,框架内置了遗传算法中常用的组件,包括不同编码方式的个体,种群,以及遗传算子等。同时框架还提供了自定义遗传算子和分析插件的接口,能够方便快速搭建遗传算法流程并用于算法测试。

目前框架仅仅处于初步阶段,后续会在自己使用的过程中逐步完善更多的内置算子,是框架更加通用。本文中的两个优化例子均能在GitHub上找到源码(https://github.com/PytLab/gaft/tree/master/examples)

目前的计划:1. 添加更多的内置算子; 2. 给内置算子和组件添加C++ backend; 3. 并行化

参考

《智能优化算法及其MATLAB实例》
《MATLAB最优化计算》

原文发布于微信公众号 - Python中文社区(python-china)

原文发表时间:2017-09-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(七)——关联规则方法之Apriori算法

一、关联规则简介         关联规则挖掘的目标是发现数据项集之间的关联关系,是数据挖据中一个重要的课题。关联规则最初是针对购物篮分析(Market Bas...

24660
来自专栏窗户

scratch写的图灵机

15630
来自专栏机器之心

资源 | Facebook开源DrQA的PyTorch实现:基于维基百科的问答系统

选自GitHub 机器之心编译 参与:Panda 今年 4 月,斯坦福大学和 Facebook 人工智能研究所在 arXiv 发布了一个基于维基百科的开放域问题...

46350
来自专栏linjinhe的专栏

WiscKey:LSM-Tree 写放大优化WiscKey 简介WiscKey 带来的好处WiscKey 面临的问题和挑战参考文档

WiscKey 的提出,主要是为了优化 LSM-Tree 的写放大问题。此前已经有不少论文讨论过这个问题,如 LSM-trie 和 PebblesDB,但是大部...

24020
来自专栏奇点大数据

Github寻宝 | 贪吃蛇游戏AI版,代码就得这么写!

本期案例是一个C++ 项目,同时也是经典小游戏——贪吃蛇的升级版。(该项目由Github用户stevennl贡献,英文原版可访问Github网站:https:/...

39340
来自专栏华章科技

以卖香蕉为例,从4个方面了解SQL的数据汇总

导读:面对一个新数据集时,人们往往会关心数据中的异常值、数据的分布形式、行列之间的关系等。SQL是一种专为数据计算设计的语言,其中已经内置了许多数据汇总函数,也...

9530
来自专栏数说工作室

换个姿势学量化!|【量化小讲堂】使用python计算各类移动平均线

作者:邢不行 原文链接: http://bbs.pinggu.org/thread-3631776-1-1.html (本文已获作者授权转载,如需转载请与原作者...

477110
来自专栏大数据文摘

干货 | 男朋友老是说自己R语言很6,快来用这40道题目检测他

21540
来自专栏CDA数据分析师

实战案例 | 使用机器学习和大数据预测心脏病

大数据和机器学习的组合是一项革命性的技术,如果以恰当的方式使用它,它可以在任何工业上产生影响。在医疗保健领域,它在很多情况下都有重要的使用,例如疾病检测、找到流...

61060
来自专栏WOLFRAM

Wolfram Alpha:用IPad完成微积分运算

26520

扫码关注云+社区

领取腾讯云代金券