遗传算法框架GAFT优化小记

專 欄

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

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

blog:http://pytlab.org

github:https://github.com/PytLab

前言

前段时间一直在用自己写的遗传算法框架测试算法在优化力场参数的效果,但是跑起来效率很慢,因为适应度函数需要调用多次力场程序计算能量,但是还是比我预想中的慢我也没有及时对程序进行profiling和优化。直到放假前在github有个使用gaft做SVM参数优化的童鞋开了个issue中说道在gaft优化的过程中会大量调用适应度函数,这才使我在国庆放假期间对gaft进行了profiling找到程序瓶颈并针对性的优化。

本文就记录下自己gaft做profiling并优化的过程以及优化的效果。

正文 对GAFT进行性能分析(Profiling)

关于如何对Python程序进行性能分析生成分析报告并可视化分析报告,我在之前的一篇博客里《Python优化第一步: 性能分析实践》进行了详细的介绍,这里我就直接分析了。

为了能针对gaft中不同的函数进行分析,借助Python内置的cProfile和pstats模块我写了个装饰器方便分析并生成不同的分析统计文件。

对上面的带参数的装饰器我在这里稍微解释下,装饰器构造器do_profile的两个参数filename和sortby分别指定分析结果报告的文件名以及统计结果的排序方式。它会对需要进行性能分析的函数进行装饰,然后在函数运行完后在当前目录生成结果报告。例如我需要对gaft中遗传算法迭代主循环进行分析,则需要:

同时为了方便,我还需要一个环境变量PROFILING来启动分析:

分析结果

这里为了方便查看函数的相互调用关系,我是用了pyprof2calltree 然后使用Mac上的QCacheGrind来可视化分析结果:

将Python的profiling文件转换并直接调用QCacheGrind便可以方便的查看分析相关信息。

通过调用关系图可以看到,gaft的初始版本的min,max,mean等函数多次调用best_indv和worst_indv会多次调用适应度函数来相互比较,而通常情况下用户自定义的适应度函数都是需要额外去调用外部程序的,一般都比较费时。所以必须要通过优化best_indv和worst_indv对fitness的调用次数才能提升gaft的效率。

优化GAFT 函数返回值缓存

从之前我写的best_indv中可以看到,我将fitness作为key用于获取最大值,Python内置的max函数会内部调用fitness进行相互比较来获取最大值,这个时候便对fitness进行了多余的调用,因为在遗传算法中,每一代的population中的个体是不会发生变化的我们只需要在每一次迭代的一开始调用fitnessn次就好了(n为种群大小),每一代中再次需要用到适应度值的地方直接获取。这样需要我们对种群中的个体进行惰性求值,也就是对所有的fitness的值进行缓存。这种操作我在优化自己的催化动力学程序的时候也使用过,叫做函数返回值缓存.

但是在gaft中这种缓存有稍微麻烦一点,因为缓存并不是缓存一次就可以一直用了,它会随着条件的变化需要重新计算种群中所有个体的适应度然后重新缓存。

重新计算适应度值需要同时满足的条件

1、种群中的所有个体没有发生任何变化 (如果变化了那肯定要重新计算适应度值了)。 2、已有缓存的适应度值 (如果是第一次那肯定需要计算一次所有个体的适应度值)。 3、计算适应度值的适应度函数与之前比较没有发生变化(如果计算适应度函数都改变了,那当然需要重新估计适应度值了)。

函数返回值缓存描述符

为此我写了个装饰器来缓存函数的返回值:

动态监视种群的变化

好了上面我们可以通过描述符来缓存函数返回值,但是一旦种群不满足上述的三个条件就需要重新计算适应度值,那我们如何监控种群的变化呢?

我在GAPopulation中添加了一个标记_updated用于标记种群是否已经发生了变化, 然后我们的任务就是在其他能够影响到种群的地方试图去更新这个flag。

如何能更Pythonic的更新这个标记呢?

所谓的种群发生变化,也是就种群中的个体列表发生了变化,种群中的个体我都放在了一个列表中,我需要监控这个列表是否发生变化以便更新flag,具体又是那些变化呢?

1、列表整体是否发生了变化(赋值操作) 2、列表中的元素是否发生变化(对列表中的元素赋值操作,列表的append, extend操作等)

好了我们要具体怎么实现呢?

  1. 对于第一种,由于Python中无法进行赋值运算符重载,但是我们可以通过描述符的set来处理:

2、对于第二种情况,我们需要对Python的List类型的相应方法进行override

但是嘞,即使重写了list的接口,又如何更新population中的变量呢?这个时候就需要用闭包了。在GAPopulation的构造函数init中定义list的派生类,并立即实例化,这时候派生类的便可以获取population对象了,于是GAPopulation的构造函数可以这些写:

优化效果

通过上面对代码的优化,我们看看我们优化的效果如何,使用分析描述符来分析GAEngine.run跑一代种群的情况,其中种群大小为10。如下图为cProfile生成的分析报告对比:

可以看到优化后的跑一代种群的时间缩短为将近原来的1/7!优化效果还是很明显的。然后看一看调用关系图:energy_fitness的调用次数从3807降到了621次!

总结

本文记录了遗传算法框架GAFT的一次profiling和优化过程,通过缓存值的方式极大的减少了适值函数的调用次数,在时间上,跑一代种群的效率提升了7倍左右。

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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏tkokof 的技术,小趣及杂念

iTween那些事儿(二)

  上次我们简单浏览了一番iTween的使用和原理,这次我们换个角度,转而看看iTween目前存在的一些缺陷以及一点点可能的改进之处,当然,这些所谓的缺陷或者改...

7110
来自专栏后端技术探索

php进阶

基本数据类型和数组都为真复制,即为真副本,当属性为对象时,为假复制,改变副本仍会影响原对象.解决方案:

17310
来自专栏吉浦迅科技

DAY37:阅读不同存储器的修饰符

13640
来自专栏牛客网

51信用卡前端凉面

18300
来自专栏一名叫大蕉的程序员

简约的JAVA版本MapReduce和日常No.25

昨天做了一个小调查,说看看想看些啥。大概的分布是这样的,一个1代表一个投票。看来还是2、3比较多。 11111 希望看到"算法"回复1。 111...

20250
来自专栏数据结构与算法

洛谷P2704 [NOI2001]炮兵阵地(状压dp)

司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成,地图的每一格可能是山地(用“H” 表示),也可能是平原(用“P”表示)...

8020
来自专栏racaljk

关于llvm kaleidoscope: 记一次Debug血泪之路

简而言之,慎(bu)用(yong)全局变量!                                

14010
来自专栏机器之心

这些Python代码技巧,你肯定还不知道

人们还经常把 Python 笑称为「可执行伪码(executable pseudocode)」。但是,当你可以编写这样的代码时,很难去反驳这种言论:

12630
来自专栏码匠的流水账

java降低竞争锁的一些方法

本文介绍一下提升并发可伸缩性的一些方式:减少锁的持有时间,降低锁的粒度,锁分段、避免热点域以及采用非独占的锁或非阻塞锁来代替独占锁。

12510
来自专栏进击的程序猿

The Clean Architecture in PHP 读书笔记(二)

设计模式是对软件中通用问题的总结,有了设计模式,方便我们进行交流,譬如一说MVC,我们就知道是怎么回事了,不然我们必须巴拉巴拉一大堆话去描述,不易于传播、交流,...

8440

扫码关注云+社区

领取腾讯云代金券