遗传算法之函数最值

Author Avatar
Tr0y 5月 28, 2017 20:57:21 本文共 1.2k 字
  • 文为知己者书
  • 在其它设备中阅读本文章

利用 Python 实现遗传算法解决函数最值问题, 并画出取点图

代码

# -*- coding: cp936 -*-
import math
import random
import time,os
from matplotlib.pyplot import *
import numpy as np

class Evolution():
    def __init__(self, lower_bound, upper_bound, chromosome_size, population, mutation_rate, retain_rate, formula): 

        self.lower_bound = lower_bound
        self.upper_bound = upper_bound
        self.chromosome_size = chromosome_size
        self.num = population
        self.mutation_rate = mutation_rate
        self.retain_rate = retain_rate
        self.formula = formula
        self.best = 0

        # 随机生成初始种群
        self.population = self.Gene_population()

    def Gene_population(self):
        """
        获取初始种群(一个含有 self.num 个长度为 self.chromosome_size 的染色体的列表)
        """
        return [self.Gene_chromosome() for i in xrange(self.num)]

    def Evolve(self, random_select_rate=0.5):
        """
        进化
        对当前一代种群依次进行选择、交叉并生成新一代种群,然后对新一代种群进行变异
        """
        parents = self.Selection(random_select_rate)
        self.Crossover(parents)
        self.Mutation()

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


    def Fitness(self, chromosome):
        """
        计算适应度,将染色体解码为定义域之间的数字,代入函数计算
        因为是求最大值,所以数值越大,适应度越高
        """
        x = self.Decode(chromosome)
        return eval(self.formula)

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

        graded = [x for y,x in sorted([(y, x) for y, x in [(self.Fitness(chromosome), chromosome) for chromosome in self.population]],reverse = True)]

        # 选出适应性强的染色体
        retain_chromosome_size = int(len(graded) * self.retain_rate)
        parents = graded[:retain_chromosome_size]
        # 选出适应性不强,但是幸存的染色体
        for chromosome in graded[retain_chromosome_size:]:
            if random.random() < random_select_rate:
                parents.append(chromosome)
        return parents

    def Crossover(self, parents):
        """
        染色体的交叉、繁殖,生成新一代的种群
        新出生的孩子,最终会被加入存活下来的父母之中,形成新一代的种群。
        """

        children = []
        # 需要繁殖的孩子的量
        target_num = len(self.population) - len(parents)
        # 开始根据需要的量进行繁殖
        while len(children) < target_num:
            male = random.randint(0, len(parents)-1)
            female = random.randint(0, len(parents)-1)
            if male != female:
                # 随机选取交叉点
                cross_pos = random.randint(0, self.chromosome_size)
                # 生成掩码,方便位操作
                mask = 0
                for i in xrange(cross_pos):
                    mask |= (1 << i) 
                male = parents[male]
                female = parents[female]
                # 孩子将获得父亲在交叉点前的基因和母亲在交叉点后(包括交叉点)的基因
                child = ((male & mask) | (female & ~mask)) & ((1 << self.chromosome_size) - 1)
                children.append(child)
        # 经过繁殖后,孩子和父母的数量与原始种群数量相等,在这里可以更新种群。
        self.population = parents + children

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


    def Decode(self, chromosome):
        """
        解码染色体,将二进制转化为属于定义域的实数
        """
        return self.lower_bound + chromosome * (self.upper_bound - self.lower_bound) / (2 ** self.chromosome_size - 1.0)

    def Result(self):
        """
        获得当前代的最优值,这里取的是函数取最大值时 x 的值。
        """
        global x
        graded = sorted([(yi, xi) for yi, xi in [(self.Fitness(chromosome), chromosome) for chromosome in self.population]],reverse = True)

        chromosome = [xi for yi,xi in graded]
        fitness = [yi for yi,xi in graded]

        if self.best < fitness[0]:
            self.best = fitness[0]
            os.system('cls')
            print '历史最优出现在第',x,'代, 个体为 '+ bin(chromosome[0])[2:] + ' 最优适应度 ' + str(self.Decode(chromosome[0])) + ' ,其值为 ' + str(fitness[0])
            xi = [self.Decode(i) for i in chromosome]
            self.PlotAndSave(xi, fitness)

        return '最优个体为 '+ bin(chromosome[0])[2:] + ' 最优适应度 ' + str(self.Decode(chromosome[0])) + ' ,其值为 ' + str(fitness[0])

    def PlotAndSave(self, chromosome, fitness):
        x = np.arange(self.lower_bound, self.upper_bound, 0.0001)
        y = eval(self.formula.replace('math','np'))
        plot(x,y)

        plot(chromosome, fitness, 'o')
        savefig('Best.jpg')
        close('all')


time.clock()

#------------------------------------------------------------------参数设置------------------------------------------------------------------

lower_bound     = 0     #函数定义域的下限
upper_bound     = 9     #函数定义域的上限
chromosome_size = 17    #染色体长度
population      = 200   #种群数量
mutation_rate   = 0.1  #变异概率
generations     = 2000   #进化代数
retain_rat      = 0.2   #种群筛选时保留 20% 的精英
formula         = 'x + 10 * math.sin(5 * x) + 7 * math.cos(4 * x)' #表达式

#------------------------------------------------------------------参数设置------------------------------------------------------------------


gene = Evolution(lower_bound, upper_bound, chromosome_size, population, mutation_rate, retain_rat, formula)
for x in xrange(generations):
    gene.Evolve()
    print '\r进化到第',x,'代',gene.Result(),

print '花费时间',int(time.clock()),'S'
os.system('pause')
  • 直接双击运行, 图片均保存在运行目录.

    运行结果

    结果

End

What do you think?

本文标题: 遗传算法之函数最值
原始链接: http://www.tr0y.wang/2017/05/28/GA_Function/
发布时间: 2017.05.28-20:57
最后更新: 2018.11.03-20:43
版权声明: 本站文章均采用CC BY-NC-SA 4.0协议进行许可。转载请注明出处!