遗传算法框架GAFT优化小记

前言

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

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

正文

对GAFT进行性能分析(Profiling)

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def do_profile(filename, sortby='tottime'):
    '''
    Constructor for function profiling decorator.
    '''
    def _do_profile(func):
        '''
        Function profiling decorator.
        '''
        @wraps(func)
        def profiled_func(*args, **kwargs):
            '''
            Decorated function.
            '''
            # Flag for doing profiling or not.
            DO_PROF = os.getenv('PROFILING')

            if DO_PROF:
                profile = cProfile.Profile()
                profile.enable()
                result = func(*args, **kwargs)
                profile.disable()
                ps = pstats.Stats(profile).sort_stats(sortby)
                ps.dump_stats(filename)
            else:
                result = func(*args, **kwargs)
            return result
        return profiled_func

    return _do_profile

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

1
2
3
@do_profile(filename='gaft_run.prof')
def run(self, ng=100):
    ...

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

1
export PROFILING=y

分析结果

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

1
pyprof2calltree -i gaft_run.prof -k

将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. 计算适应度值的适应度函数与之前比较没有发生变化(如果计算适应度函数都改变了，那当然需要重新估计适应度值了)。

函数返回值缓存描述符

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Memoized(object):
    '''
    Descriptor for population statistical varibles caching.
    '''
    def __init__(self, func):
        self.func = func
        self.result = None
        self.fitness = None

    def __get__(self, instance, cls):
        self.instance = instance
        return self

    def __call__(self, fitness):
        if ((not self.instance._updated)         # population not changed
                and (self.result is not None)    # result already cached
                and (fitness == self.fitness)):  # fitness not changed
            # Return cached result directly.
            return self.result
        else:
            # Update fitness function.
            self.fitness = fitness
            # Update and memoize result.
            self.result = self.func(self.instance, fitness)
            # Recover flag.
            self.instance._updated = False
            return self.result

动态监视种群的变化

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

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

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

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

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

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class GAIndividuals(object):
        '''
        Descriptor for all individuals in population.
        '''
        def __init__(self, name):
            self.name = '_{}'.format(name)

        def __get__(self, instance, owner):
            return instance.__dict__[self.name]

        def __set__(self, instance, value):
            instance.__dict__[self.name] = value
            # Update flag.
            instance._updated = True

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    def __init__(self, indv_template, size=100):

        # ...

        # Flag for monitoring changes of population.
        self._updated = False

        # Container for all individuals.
        class IndvList(list):
            '''
            A proxy class inherited from built-in list to contain all
            individuals which can update the population._updated flag
            automatically when its content is changed.
            '''
            # NOTE: Use 'this' here to avoid name conflict.
            def __init__(this, *args):
                super(this.__class__, this).__init__(*args)

            def __setitem__(this, key, value):
                '''
                Override __setitem__ in built-in list type.
                '''
                old_value = this[key]
                if old_value == value:
                    return
                super(this.__class__, self).__setitem__(key, value)
                # Update population flag.
                self._updated = True

            def append(this, item):
                '''
                Override append method of built-in list type.
                '''
                super(this.__class__, this).append(item)
                # Update population flag.
                self._updated = True

            def extend(this, iterable_item):
                if not iterable_item:
                    return
                super(this.__class__, this).extend(iterable_item)
                # Update population flag.
                self._updated = True

        self._individuals = IndvList()

优化效果

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

可以看到优化后的跑一代种群的时间缩短为将近原来的1/7! 优化效果还是很明显的。

然后看一看调用关系图:

energy_fitness的调用次数从3807降到了621次！

总结

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

Comments

▲