前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >用遗传算法求解函数

用遗传算法求解函数

作者头像
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)。

代码语言:javascript
复制
#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表示一个基因

代码语言:javascript
复制
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'

代码语言:javascript
复制
>>> int('00111100',2)
60
>>> int('11110000',2)
240
>>> 60<<2
240

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

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

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

代码语言:javascript
复制
>>> 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。

代码语言:javascript
复制
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]的值。

代码语言:javascript
复制
def decode(self, chromosome):
    return chromosome * 9.0 / (2**self.length-1)

适应度函数(Fitness Function

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

代码语言:javascript
复制
def fitness(self, chromosome):
    x = self.decode(chromosome)
    return x + 10*math.sin(5*x) + 7*math.cos(4*x)

自然选择

代码语言:javascript
复制
"""
选择
先对适应度从大到小排序,选出存活的染色体
再进行随机选择,选出适应度虽然小,但是幸存下来的个体
"""
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是他们的子女。

代码如下:

代码语言:javascript
复制
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 //左侧是母亲的染色体,右侧父亲的染色体。

基因突变

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

代码语言:javascript
复制
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

终止

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

代码语言:javascript
复制
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])     

完整代码

代码语言:javascript
复制
#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()

参考文章

https://applenob.github.io/ga.html

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

https://blog.csdn.net/u010451580/article/details/51178225

http://www.runoob.com/python/python-operators.html

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 问题:
    • 基本概念:基因、染色体和种群
    • 步骤
      • 创建算法类
        • 生成染色体
          • 初始化种群
            • 解码染色体
              • 适应度函数(Fitness Function)
                • 自然选择
                  • 基因交叉与繁殖
                    • 基因突变
                      • 终止
                        • 完整代码
                        • 参考文章
                        领券
                        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档