算法

遗传算法的python简单实现

Posted by SkyHigh on September 20, 2016

遗传算法的python简单实现

什么是遗传算法

遗传算法是一种比较常用的启发式算法，一般可以对有解析解的式子求得最优解或较优解。一个比较经典的解释是，在喜马拉雅山上的鹿的生存率仅仅由它所处的高度有关。我们不妨设高度越高，存活率越高。那么山上的各个鹿，可能在山峰，也可能在山谷，但是在山谷的鹿的存活率并不一定比在山峰的低，这是因为很可能这只在山峰的鹿只是站到了它附近比较高的山峰上（局部最优解）。我们的最终目的是让山上的所有鹿不断奔跑，并让处于低处的鹿更容易死亡，这样保留优质的鹿（基因选择）并经过交叉繁殖（基因交叉）和基因突变后，可以得到不断进化的基因（不断趋于最优解）。记录它们到过的最高的地方，即为最优值。

一个例子

我们假设那么，我们可以人为计算出当时函数达到最大值，最大值为98。

步骤分解

初始化编码

给定n组数（代表n只鹿），对每一组数进行基因编码。编码方式有两种，一种是二进制形式，一种是float形式。我们这里采用二进制形式，即比如说我们要编码数字(3,5)，则可以编写成“011101”串（因为这里最大是7，且只有两个数，所以编成6位足够了）。我们不妨设n=2，初始化编码为(g1, g2) = [011101, 100100]。

计算适应度和基因选择

使用目标函数来作为适应度公式。比如按照例子中的公式，上述的初始化编码的适应度为[34, 32]，并保存最优秀的基因011101，此时最佳适应度为34。那么我们就可以计算出g1的生存概率为34/66，而g2的生存概率为32/66，通过这个概率从上述两组中随机选择2次（初始化编码有几组，就选择几次）。比如最后选择的是[g2, g1]=[100100, 011101]作为基因选择的结果。

注：目标函数的值域一定要大于等于0，不然在进行基因选择的时候，概率轮盘无法归一化。并且目标函数有最大值。

基因交叉

设定交换的基因点，比如从左往右数第4个（这个位置也可以随机化），对基因组里的基因两两交换（可以按邻近两组基因交换，也可以随机选择两组基因进行交换），最后交换的就是100和101，结果为[100101, 011100]。

基因变异

对每个基因进行变异，即对基因的某个位点进行取反操作。比如我们对第一个基因的第3个基因点进行变异，变为101101，对第二个基因的第4个基因点进行变异，变为011000。最终结果为[101101, 011000]。

迭代

从第一次初始化后，我们开始对以下过程进行迭代，迭代次数需要人为指定。

  • 计算适应度
  • 基因选择
  • 基因交叉
  • 基因变异
基因解码

最终我们得到最优的基因和适应度，对基因进行解码，得到最优值为111111，即[7, 7]，最优值为98。

代码
\#coding:utf8
import os
import sys
import math
import random
from random import shuffle
import re
import datetime
import logging
import json
import copy
import numpy as np
reload(sys)
sys.setdefaultencoding('utf8')
logging.basicConfig(level=logging.INFO,
                format='%(asctime)s %(filename)s[line:%(lineno)d] %(levelname)s %(message)s',
                datefmt='%a, %d %b %Y %H:%M:%S',
                filename='ga.log',
                filemode='w')


class Generation:
    def __init__(self, aim, groupnum=5, generation=10, var_num=2, crossrate=0.9, variationrate=0.9, var_range=[0, 8], encodebit=5):
        # 适应度函数
        self.aim = aim
        # 种群数量
        self.groupnum = groupnum
        # 变量数
        self.var_num = var_num
        # 繁殖代数
        self.generation = generation
        # 当前代数
        self.curiter = 1
        # 交叉概率
        self.crossrate = crossrate
        # 变异概率
        self.variationrate = variationrate
        # log日志
        self.logger = logging.log
        # 变量取值范围，[a, b]
        self.var_range = var_range
        # 二进制编码位数
        self.encodebit = encodebit
        # 种群结果
        self.population = list()

        for i in range(groupnum):
            p_tmp = list()
            for j in range(self.encodebit*self.var_num):
                p_tmp.append(random.randint(0, 1))
            self.population.append(p_tmp)
        # print self.population
        # 记录最好的结果
        self.best = list()

    # 基因解码
    # pop:list()
    def geneDecode(self, pop):
        cut_p = -1
        decode_pop = list()
        for i in range(self.var_num):
            base = 1
            decimal = 0
            for bit in pop[cut_p:cut_p-self.encodebit:-1]:
                decimal += bit * base
                base *= 2
            cut_p = cut_p - self.encodebit
            decode_pop.append(float(self.var_range[1]-self.var_range[0])*decimal/(2**self.encodebit-1) + self.var_range[0])
        return decode_pop

    # 计算适应度
    def calcSufficiency(self):
        survival_list = list()
        decode_list = list()
        for pop in self.population:
            decode_pop = self.geneDecode(pop)
            decode_list.append(decode_pop)
            survival_rate = self.aim(decode_pop)
            survival_list.append(survival_rate)
        total = float(sum(survival_list))
        rate_survival_list = [rate/total for rate in survival_list]
        index = np.argsort(rate_survival_list)[-1]
        # print self.population, decode_list
        self.best.append((decode_list[index], survival_list[index], copy.copy(self.population[index])))
        # print self.best[-1]
        self.logger(logging.INFO, '{0} The survival rate of each population is: '.format(self.curiter) + '\n' + json.dumps(rate_survival_list))
        self.curiter += 1
        return rate_survival_list

    # 基因选择
    def choosePopulation(self):
        survival_list = self.calcSufficiency()
        for i in xrange(1, len(survival_list)):
            survival_list[i] += survival_list[i-1]
        
        new_population = list()
        for curgroup in range(self.groupnum):
            random_rate = random.random()
            for i, prop in enumerate(survival_list):
                if random_rate <= prop:
                    new_population.append(self.population[i])
                    break
        self.population = new_population
        return new_population

    # 交叉
    def crossCalc(self):
        self.choosePopulation()
        np.random.shuffle(self.population)
        for i in range(0, self.groupnum, 2):
            prop = random.random()
            rand_cross_point = random.randint(1, self.encodebit-1)
            if prop <= self.crossrate:
                self.population[i][rand_cross_point:], self.population[i+1][rand_cross_point:] = \
                    self.population[i+1][rand_cross_point:], self.population[i][rand_cross_point:]
        return self.population

    # 基因突变
    def geneRevolution(self):
        self.crossCalc()
        for i in range(self.groupnum):
            rand_variation_num = random.randint(1, self.encodebit)
            for j in range(rand_variation_num):
                prop = random.random()
                if prop <= self.variationrate:
                    rand_variation_point = random.randint(0, self.encodebit-1)
                    self.population[i][rand_variation_point] = \
                        1 - self.population[i][rand_variation_point]
        return self.population

    # 基因进化
    def geneEvolve(self):
        for i in range(self.generation):
            self.geneRevolution()

        self.best.sort(key=lambda kk:kk[1])
        print self.best[-1]
        return self.best[-1]


if __name__ == '__main__':
    aim = lambda x:x[0]**2+x[1]**2
    g = Generation(aim, groupnum=80, generation=100, var_num=2, var_range=[0, 7], encodebit=5)
    g.geneEvolve()