遗传算法框架GAFT已支持自定义编码方式

前言

遗传算法中个体的编码方式有很多比如二进制编码，实数编码，格雷编码，符号编码等等。之前我写的遗传算法框架提供了两种固定的编码方式: 二进制编码和实数编码。但是这些编码方式都是写死在GAIndividual类的encode和decode方法里的。为了使得gaft能够灵活的支持更多的编码方式，我对个体的定义进行了更新，目前可以通过实现接口自定义编码方式了。目前仍然内置二进制编码和实数编码方式，不过实现的方式已经与以前不同。

可以参考v0.5.0的CHANGELOG

正文

在这里我就介绍一下接口的更新和使用方法。

个体基类

个体基类IndividualBase是一个抽象基类用于自定义编码个体时候继承。主要需要实现的就两个方法encode和decode。其中encode方法把solution候选解进行编码成chromsome染色体列表比如编码成二进制列表，相反，decode方法则把chromsome解码成候选解solution。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class IndividualBase(object):

    # ...

    def encode(self):
        ''' *NEED IMPLIMENTATION*
        Convert solution to chromsome sequence.

        :return chromsome: The chromsome sequence, float list.
        '''
        raise NotImplementedError

    def decode(self):
        ''' *NEED IMPLIMENTATION*
        Convert chromsome sequence to solution.

        :return solution: The solution vector, float list.
        '''
        raise NotImplementedError

同时IndividualBase还实现了初始化和随机初始化个体的方法，具体实现参见:https://github.com/PytLab/gaft/blob/master/gaft/components/individual.py

二进制编码个体

这里为了区别个体编码方式的不同，个体的定义的名字都进行了更改，例如二进制编码个体命名为BinaryIndividual，指代这此个体的编码方式为二进制编码。

定义BinaryIndividual类的时候，需要继承IndividualBase并实现encode和decode方法:

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
class BinaryIndividual(IndividualBase):

    # ...

    def encode(self):
        '''
        Encode solution to gene sequence in individual using different encoding.
        '''
        chromsome = []
        for var, (a, _), length, eps in zip(self.solution, self.ranges,
                                            self.lengths, self.precisions):
            chromsome.extend(self.binarize(var-a, eps, length))

        return chromsome

    def decode(self):
        ''' 
        Decode gene sequence to solution of target function.
        '''
        solution =  [self.decimalize(self.chromsome[start: end], eps, lower_bound)
                     for (start, end), (lower_bound, _), eps in
                     zip(self.gene_indices, self.ranges, self.precisions)]
        return solution

    # ...

具体实现参见: https://github.com/PytLab/gaft/blob/master/gaft/components/binary_individual.py

实数编码(浮点编码)

对于一些多维、高精度要求的连续函数优化问题，使用二进制编码来表示个体时将会有一些不利之处。二进制编码存在着连续函数离散化时的映射误差。个体长度较知时，可能达不到精度要求，而个体编码长度较长时，虽然能提高精度，但却使遗传算法的搜索空间急剧扩大。

所谓浮点法，是指个体的每个基因值用某一范围内的一个浮点数来表示。在浮点数编码方法中，必须保证基因值在给定的区间限制范围内，遗传算法中所使用的交叉、变异等遗传算子也必须保证其运算结果所产生的新个体的基因值也在这个区间限制范围内。

其实实现浮点编码的个体很简单，因为我们的solution本身就是使用浮点数表示的，唯一需要注意的是解向量中元素的取值范围的限定。此编码个体的实现方式也可以作为其他自定义编码方式个体的参考。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from .individual import IndividualBase


class DecimalIndividual(IndividualBase):
    ''' Individual with decimal encoding.
    '''
    def __init__(self, ranges, eps=0.001):
        super(self.__class__, self).__init__(ranges, eps)
        # Initialize it randomly.
        self.init()

    def encode(self):
        return self.solution

    def decode(self):
        return self.solution

具体的范围限制则需要在变异算子中进行个体的编码方式判断并针对性的处理, 具体的实现参考: https://github.com/PytLab/gaft/blob/master/gaft/operators/mutation/flip_bit_mutation.py

关于自定义编码方式

对于在使用GAFT中自定义编码方式，需要以下两点即可:

  1. 实现一个新的Individual类继承自IndividualBase，然后实现相应编码方式的encode和decode接口。
  2. 在mutation算子中的mutate方法中加入相应编码方式个体的变异操作

总结

目前GAFT已支持自定义编码方式，并内置了二进制编码和实数编码，使用的童鞋若实现了较好的编码个体欢迎Pull Request

Comments

▲