用遗传算法求解函数

Stanley Sun

发布于 2020-08-11 01:36:37

1.4K0

发布于 2020-08-11 01:36:37

文章被收录于专栏：思考是一种快乐

问题：

用遗传算法求解函数f(x) = x + 10sin(5x) + 7cos(4x) 在区间[0,9]的最大值。

这个函数的图形为：

从图上可以看出，在[0,9]区间内，最大值为(7.857,24.855)。现在，用遗传算法找到这个点。选择使用Python语言。

基本概念:基因、染色体和种群

一系列个体组成的集合叫种群。每一个个体就是问题的一个解。

个体的特征，是由一系列参数(Gene)决定的。基因组合起来形成染色体(Chromosome)，一个染色体就是一个问题的解。（通常一个个体只用一个染色体）

步骤

创建算法类

创建一个ga.py的文件，创建一个GA类。指定两个参数,分别表示染色体的长度(length)和种群中个体的数量(count)。

#encoding=utf-8

import math
import random
import operator

class GA():
    def __init__(self, length, count):
        # 染色体长度
        self.length = length
        # 种群中的染色体数量
        self.count = count

生成染色体

随机生成长度为length的染色体，每个基因的取值是0或1。这里用一个bit表示一个基因

def gen_chromosome(self, length):
    chromosome = 0
    for i in xrange(length):
        chromosome |= (1 << i) * random.randint(0, 1)
    return chromosome

注释: << 是左移动运算符，如二进制‘0011 1100’左移两位就是'1111 0000'

>>> int('00111100',2)
60
>>> int('11110000',2)
240
>>> 60<<2
240

符号“|” 是按位或运算符：只要对应的二个二进位有一个为1时，结果位就为1。

二进制‘0011 1100’ ｜ '1111 0000'结果为‘1111 1100’

“|=”即运算后再赋值给自己。

>>> 60|240
252
>>> int('11111100',2)
252

random.randint(a, b)为返回一个整数N，使得a<=N<=b, random.randint(0,1)就是随机返回0或1。

gen_chromosome(self, length)方法返回一个随机生成的长度为length的二进制数，即染色体。

初始化种群

我们的模型里面，一个个体只有一个染色体。一个种群里由count个个体，所以初始化种群就是：生成count个染色体，每个染色体的长度为length。

def gen_population(self, length, count):
    return [self.gen_chromosome(length) for i in xrange(count)]

解码染色体

因为，问题是求区间[0, 9]的解，所以要把染色体(chromosome)转换成[0,9]的实数. 染色体是一个长度为length的二进制，所以chromosome是一个区间为[0,2**length-1]的值，chromosome*9/(2**length-1)就是一个[0,9]的值。

def decode(self, chromosome):
    return chromosome * 9.0 / (2**self.length-1)

适应度函数（Fitness Function）

自然界生物竞争过程包含两个方面：生物间搏斗及生物与环境的搏斗。我们的问题不包含生物间搏斗，只考虑生物与环境的搏斗即可，表示为适应度。适应度函数就是将染色体代入函数计算。因为是求最大值，所以数值越大，适应度越高

def fitness(self, chromosome):
    x = self.decode(chromosome)
    return x + 10*math.sin(5*x) + 7*math.cos(4*x)

自然选择

"""
选择
先对适应度从大到小排序，选出存活的染色体
再进行随机选择，选出适应度虽然小，但是幸存下来的个体
"""
def selection(self, retain_rate, random_select_rate):

    # 对适应度从大到小进行排序
    graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
    graded = [x[1] for x in sorted(graded, reverse=True)]
    # 选出适应性强的染色体
    retain_length = int(len(graded) * retain_rate)
    parents = graded[:retain_length]
    # 选出适应性不强，但是幸存的染色体
    for chromosome in graded[retain_length:]:
        if random.random() < random_select_rate:
            parents.append(chromosome)
    return parents

retain_rate是留存率，即选择百分之多少的(优质)个体进行下一代繁殖。

random_select_rate是随机选择率。为了保持多样性，对于非优质的个体，也要随机选择一小部分留下来。

基因交叉与繁殖

基因交叉是遗传算法里重要的一环。方法是：在染色体上随机选一个交叉点。子代个体的染色体，左边片段来自父亲对应的基因片段，右边片段来自母亲对应的基因片段。下图A1、A2是双亲，A5、A6是他们的子女。

代码如下：

def crossover(self, parents):
        """
        染色体的交叉、繁殖，生成新一代的种群
        """
        # 新出生的孩子，最终会被加入存活下来的父母之中，形成新一代的种群。
        children = []
        # 需要繁殖的孩子的量
        target_count = len(self.population) - len(parents)
        # 开始根据需要的量进行繁殖
        while len(children) < target_count:
            male = random.randint(0, len(parents)-1)
            female = random.randint(0, len(parents)-1)
            if male != female:
                # 随机选取交叉点
                cross_pos = random.randint(0, self.length)
                # 生成掩码，方便位操作
                mask = 0
                for i in xrange(cross_pos):
                    mask |= (1 << i) 
                male = parents[male]
                female = parents[female]
                # 孩子将获得父亲在交叉点前的基因和母亲在交叉点后（包括交叉点）的基因
                child = ((male & mask) | (female & ~mask)) 
                children.append(child)
        # 经过繁殖后，孩子和父母的数量与原始种群数量相等，在这里可以更新种群。
        self.population = parents + children

理论上，生物可以单性繁殖、双性繁殖甚至多性繁殖。上面的代码用了双性繁殖，原因是自然界以双性繁殖为主。

代码解释：

假如选择交叉点是5，父亲的染色体是100110010110，母亲的染色体是010010111000。

male = 1001100 10110

female = 0100101 11000

mask ＝ 11111

male & mask => 0000000 10110

~mask => ... 100000 //左侧的...全部是1，负数用补码表示

female & ~mask => 0100101 00000

(male&mask) | (female& ~mask) => 0100101 10110 //左侧是母亲的染色体，右侧父亲的染色体。

基因突变

基因突变是染色体的某一个位点上基因的改变，它使一个基因变成它的等位基因。基因突变是为了保持种群的多样性，避免种群早熟和收敛。

def mutation(self, rate):
        """
        变异
        对种群中的所有个体，随机改变某个个体中的某个基因
        """
        for i in xrange(len(self.population)):
            if random.random() < rate:
                j = random.randint(0, self.length-1)
                self.population[i] ^= 1 << j

终止

当种族收敛的时候，就需要终止程序。所谓收敛，就是新生的子代与父代之间的差异很小了。也可以直接指定多少代之后自动停止。

def result(self):
        """
        获得当前代的最优值，这里取的是函数取最大值时x的值。
        """
        graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
        graded = [x[1] for x in sorted(graded, reverse=True)]
        return ga.decode(graded[0])

完整代码

#encoding=utf-8

import math
import random
import operator

class GA():
    def __init__(self, length, count):
        # 染色体长度
        self.length = length
        # 种群中的染色体数量
        self.count = count
        # 随机生成初始种群
        self.population = self.gen_population(length, count)

    def evolve(self, retain_rate=0.2, random_select_rate=0.5, mutation_rate=0.01):
        """
        进化
        对当前一代种群依次进行选择、交叉并生成新一代种群，然后对新一代种群进行变异
        """
        parents = self.selection(retain_rate, random_select_rate)
        self.crossover(parents)
        self.mutation(mutation_rate)

    def gen_chromosome(self, length):
        """
        随机生成长度为length的染色体，每个基因的取值是0或1
        这里用一个bit表示一个基因
        """
        chromosome = 0
        for i in xrange(length):
            chromosome |= (1 << i) * random.randint(0, 1)
        return chromosome

    def gen_population(self, length, count):
        """
        获取初始种群（一个含有count个长度为length的染色体的列表）
        """
        return [self.gen_chromosome(length) for i in xrange(count)]

    def fitness(self, chromosome):
        """
        计算适应度，将染色体解码为0~9之间数字，代入函数计算
        因为是求最大值，所以数值越大，适应度越高
        """
        x = self.decode(chromosome)
        return x + 10*math.sin(5*x) + 7*math.cos(4*x)

    def selection(self, retain_rate, random_select_rate):
        """
        选择
        先对适应度从大到小排序，选出存活的染色体
        再进行随机选择，选出适应度虽然小，但是幸存下来的个体
        """
        # 对适应度从大到小进行排序
        graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
        graded = [x[1] for x in sorted(graded, reverse=True)]
        # 选出适应性强的染色体
        retain_length = int(len(graded) * retain_rate)
        parents = graded[:retain_length]
        # 选出适应性不强，但是幸存的染色体
        for chromosome in graded[retain_length:]:
            if random.random() < random_select_rate:
                parents.append(chromosome)
        return parents

    def crossover(self, parents):
        """
        染色体的交叉、繁殖，生成新一代的种群
        """
        # 新出生的孩子，最终会被加入存活下来的父母之中，形成新一代的种群。
        children = []
        # 需要繁殖的孩子的量
        target_count = len(self.population) - len(parents)
        # 开始根据需要的量进行繁殖
        while len(children) < target_count:
            male = random.randint(0, len(parents)-1)
            female = random.randint(0, len(parents)-1)
            if male != female:
                # 随机选取交叉点
                cross_pos = random.randint(0, self.length)
                # 生成掩码，方便位操作
                mask = 0
                for i in xrange(cross_pos):
                    mask |= (1 << i) 
                male = parents[male]
                female = parents[female]
                # 孩子将获得父亲在交叉点前的基因和母亲在交叉点后（包括交叉点）的基因
                child = ((male & mask) | (female & ~mask)) & ((1 << self.length) - 1)
                children.append(child)
        # 经过繁殖后，孩子和父母的数量与原始种群数量相等，在这里可以更新种群。
        self.population = parents + children

    def mutation(self, rate):
        """
        变异
        对种群中的所有个体，随机改变某个个体中的某个基因
        """
        for i in xrange(len(self.population)):
            if random.random() < rate:
                j = random.randint(0, self.length-1)
                self.population[i] ^= 1 << j


    def decode(self, chromosome):
        """
        解码染色体，将二进制转化为属于[0, 9]的实数
        """
        return chromosome * 9.0 / (2**self.length-1)

    def result(self):
        """
        获得当前代的最优值，这里取的是函数取最大值时x的值。
        """
        graded = [(self.fitness(chromosome), chromosome) for chromosome in self.population]
        graded = [x[1] for x in sorted(graded, reverse=True)]
        return ga.decode(graded[0])     


if __name__ == '__main__':
    # 染色体长度为17， 种群数量为300
    ga = GA(17, 300)

    # 200次进化迭代
    for x in xrange(200):
         ga.evolve()

    print ga.result()