遺傳演算法框架GAFT優化小記

前言

前段時間一直在用自己寫的遺傳演算法框架測試演算法在優化力場參數的效果，但是跑起來效率很慢，因為適應度函數需要調用多次力場程序計算能量，但是還是比我預想中的慢我也沒有及時對程序進行profiling和優化。直到放假前在github有個使用gaft做SVM參數優化的童鞋開了個issue中說道在gaft優化的過程中會大量調用適應度函數，這才使我在國慶放假期間對gaft進行了profiling找到程序瓶頸並針對性的優化。

本文就記錄下自己gaft做profiling並優化的過程以及優化的效果。gaft項目鏈接:

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

正文

對GAFT進行性能分析(Profiling)

關於如何對Python程序進行性能分析生成分析報告並可視化分析報告，我在之前的一篇博客里《Python優化第一步: 性能分析實踐》進行了詳細的介紹，這裡我就直接分析了。

為了能針對gaft中不同的函數進行分析，藉助Python內置的cProfile和pstats模塊我寫了個裝飾器方便分析並生成不同的分析統計文件。

def do_profile(filename, sortby=tottime):n n Constructor for function profiling decorator.n n def _do_profile(func):n n Function profiling decorator.n n @wraps(func)n def profiled_func(*args, **kwargs):n n Decorated function.n n # Flag for doing profiling or not.n DO_PROF = os.getenv(PROFILING)n if DO_PROF:n profile = cProfile.Profile()n profile.enable()n result = func(*args, **kwargs)n profile.disable()n ps = pstats.Stats(profile).sort_stats(sortby)n ps.dump_stats(filename)n else:n result = func(*args, **kwargs)n return resultn return profiled_funcn return _do_profilen

對上面的帶參數的裝飾器我在這裡稍微解釋下，裝飾器構造器do_profile的兩個參數filename和sortby分別指定分析結果報告的文件名以及統計結果的排序方式。它會對需要進行性能分析的函數進行裝飾，然後在函數運行完後在當前目錄生成結果報告。例如我需要對gaft中遺傳演算法迭代主循環進行分析，則需要:

@do_profile(filename=gaft_run.prof)ndef run(self, ng=100):n ...n

同時為了方便，我還需要一個環境變數PROFILING來啟動分析:

export PROFILING=yn

分析結果

這裡為了方便查看函數的相互調用關係，我是用了pyprof2calltree 然後使用Mac上的QCacheGrind來可視化分析結果:

pyprof2calltree -i gaft_run.prof -kn

將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. 計算適應度值的適應度函數與之前比較沒有發生變化(如果計算適應度函數都改變了，那當然需要重新估計適應度值了)。

函數返回值緩存描述符

為此我寫了個裝飾器來緩存函數的返回值:

class Memoized(object):n n Descriptor for population statistical varibles caching.n n def __init__(self, func):n self.func = funcn self.result = Nonen self.fitness = Nonen def __get__(self, instance, cls):n self.instance = instancen return selfn def __call__(self, fitness):n if ((not self.instance._updated) # population not changedn and (self.result is not None) # result already cachedn and (fitness == self.fitness)): # fitness not changedn # Return cached result directly.n return self.resultn else:n # Update fitness function.n self.fitness = fitnessn # Update and memoize result.n self.result = self.func(self.instance, fitness)n # Recover flag.n self.instance._updated = Falsen return self.resultn

動態監視種群的變化

好了上面我們可以通過描述符來緩存函數返回值，但是一旦種群不滿足上述的三個條件就需要重新計算適應度值，那我們如何監控種群的變化呢？

我在GAPopulation中添加了一個標記_updated用於標記種群是否已經發生了變化, 然後我們的任務就是在其他能夠影響到種群的地方試圖去更新這個flag。

如何能更Pythonic的更新這個標記呢？

所謂的種群發生變化，也是就種群中的個體列表發生了變化，種群中的個體我都放在了一個列表中，我需要監控這個列表是否發生變化以便更新flag，具體又是那些變化呢？

1. 列表整體是否發生了變化(賦值操作)
2. 列表中的元素是否發生變化(對列表中的元素賦值操作，列表的append, extend操作等)

好了我們要具體怎麼實現呢？

1. 對於第一種，由於Python中無法進行賦值運算符重載，但是我們可以通過描述符的__set__來處理:

class GAIndividuals(object):n n Descriptor for all individuals in population.n n def __init__(self, name):n self.name = _{}.format(name)n def __get__(self, instance, owner):n return instance.__dict__[self.name]n def __set__(self, instance, value):n instance.__dict__[self.name] = valuen # Update flag.n instance._updated = Truen

2. 對於第二種情況，我們需要對Python的List類型的相應方法進行override

但是嘞，即使重寫了list的介面，又如何更新population中的變數呢？這個時候就需要用閉包了。在GAPopulation的構造函數__init__中定義list的派生類，並立即實例化，這時候派生類的便可以獲取population對象了，於是GAPopulation的構造函數可以這些寫:

def __init__(self, indv_template, size=100):n # ...n # Flag for monitoring changes of population.n self._updated = Falsen # Container for all individuals.n class IndvList(list):n n A proxy class inherited from built-in list to contain alln individuals which can update the population._updated flagn automatically when its content is changed.n n # NOTE: Use this here to avoid name conflict.n def __init__(this, *args):n super(this.__class__, this).__init__(*args)n def __setitem__(this, key, value):n n Override __setitem__ in built-in list type.n n old_value = this[key]n if old_value == value:n returnn super(this.__class__, self).__setitem__(key, value)n # Update population flag.n self._updated = Truen def append(this, item):n n Override append method of built-in list type.n n super(this.__class__, this).append(item)n # Update population flag.n self._updated = Truen def extend(this, iterable_item):n if not iterable_item:n returnn super(this.__class__, this).extend(iterable_item)n # Update population flag.n self._updated = Truen self._individuals = IndvList()n

優化效果

通過上面對代碼的優化，我們看看我們優化的效果如何，使用分析描述符來分析GAEngine.run跑一代種群的情況，其中種群大小為10。如下圖為cProfile生成的分析報告對比:

可以看到優化後的跑一代種群的時間縮短為將近原來的1/7! 優化效果還是很明顯的。

然後看一看調用關係圖:

energy_fitness的調用次數從3807降到了621次！

總結

本文記錄了遺傳演算法框架GAFT的一次profiling和優化過程，通過緩存值的方式極大的減少了適值函數的調用次數，在時間上，跑一代種群的效率提升了7倍左右。