[数据结构与算法]进化算法/遗传算法

原理

简介

占用二进制位数

2进制占用位数：$x_{max}?x_{min}$这个范围下，一定精度小数编码为2进制所占用位数
$$L={\log }_2^{(x_{max}?x_{min})10^k}+1$$

• $L$，length，二进制位数
• $x_{min}$，下界
• $x_{max}$，上界
• $10^k$，精度

编码

编码10进制数为2进制字符串

    def encode_DEC(dec, x_min, decimal, bit_num):
        """
        编码十进制数
        :param: dec: 十进制数
        :param: decimal: 小数位数
        :param: bit_num: 占用bit数
        :return: 二进制字符序列
        """
        # dec - x_min 不考虑负数编码，全部转成正数
        # 因为，编码x_max-x_min范围内的数，所以需要实际dec-x_min
        if x_min < 0:
            binary = bin(int((dec - 2 * x_min) * pow(10, decimal + 1)))
        else:
            binary = bin(int((dec - x_min) * pow(10, decimal + 1)))

        # 除去0b
        binary = str(binary)[2:]
        # 补全
        while len(binary) < bit_num:
            binary = '0' + binary
        return binary

解码

将2进制字符串解码为10进制数

    def decode_BIN(bin, x_min, decimal):
        """
        解码二进制到10进制
        :return: 返回经过精度运算的十进制数
        """
        bin = '0b' + bin
        dec = int(bin, 2)
        # encode_DEC时，将负数+(-x_min)变成了正数，decode_BIN需要变回来
        # 因为解码结果是x_max-x_min范围内的数，所有需要解码数+x_min
        if x_min < 0:
            num = dec / pow(10, decimal + 1) + 2 * x_min
        else:
            num = dec / pow(10, decimal + 1) + x_min

        return num

选择

根据适应度，选择染色体，作为交叉复制步骤的输入
轮盘赌算法：

介绍：

1. 计算个体概率：
   $$p(x_i)=\frac{fitness(x_i)}{\sum _{j=1}^{N}fitness(x_j)}$$
2. 计算累计概率：
   $$q_i=\sum _{j=1}^{i}p(x_j)$$
3. 产生随机概率sr
4. $q_i>sr$，选择这个染色体

特点：

• 可知个体适应度越大被选择的概率越大
• 个体适应度值大于0

交叉复制

以选择的染色体作为输入
单点交叉：下图为示例，代码实际是2进制

2点交叉：下图为示例，代码实际是2进制

变异

根据变异因子决定那条染色体发生基因变异
随机产生变异点
对变异点的基因0变1,1变0

注意

适应度函数选择

• 选择目标函数作为适应度函数时，目标函数值与适应度应该成正比
• 轮盘赌算法，选择个体适应度大的染色体的概率大，高适应度个体会被保留，高函数值个体会被保留

一次迭代后记录适应度最大还是最小解

• 一次迭代后的结果有NP条染色体，由于轮盘赌算法，所有记录适应度大的染色体，记录高函数值的解

代码

步骤：

1. 确定目标函数
2. 确定解空间
3. 初始化种群：符号统一分布且在解空间之内的种群
4. 选择：轮盘赌算法，解的适应度越大被选中的概率越大
5. 交叉复制：单点交叉，交叉因子决定交叉次数
6. 变异：将0变1,1变0，变异因子决定那条染色体发生基因变异

import math
import random
import numpy as np
import matplotlib
import matplotlib.pyplot as plt

matplotlib.rcParams['font.family'] = 'STSong'
matplotlib.rcParams['font.size'] = 10


def fitness_ex(x):
    """
    e的x次方
    单调递增函数，函数值越大，适应度越大
    :param x:
    :return:
    """
    return np.exp(x);


def fitness_sin(x):
    """
    目标函数
    :param x: 十进制数值
    :return: 适应度
    """
    # 计算适应度函数值
    return x * math.sin(10 * math.pi * x) + 2.0


class GeneticAlgorithm(object):
    """
    遗传算法
    """

    def __init__(self, iter_num, fitness_end, x_min, x_max, NP, D, CR, MR, decimal):
        """
        初始化
        :param iter_num: 迭代次数
        :param fitness_end: 截止适应度
        :param x_min: 下限
        :param x_max: 上限
        :param NP(number population): 种群中个体数量
        :param D(dimension): 染色体基因数，染色体维度，一条染色体一个解 解的维度
        :param CR: 交叉因子
        :param MR: 变异因子
        :param decimal: 小数位数
        """
        # 终止条件
        self.iter_num = iter_num
        self.fitness_end = fitness_end
        # 解空间
        self.x_min = x_min
        self.x_max = x_max
        # 求解者
        self.NP = NP
        self.D = D
        # 算法参数
        self.CR = CR
        self.MR = MR
        self.decimal = decimal

    def evolve(self):
        """
        进化
        :return:
        """
        # 初始化种群
        xfloat = np.random.uniform(self.x_min, self.x_max, self.NP)
        x = []
        for m in range(self.NP):
            x.append(Coder.encode_DEC(xfloat[m], self.x_min, self.decimal, self.D))

        # 最优适应度列表
        fitness_list = []
        for gen in range(self.iter_num):
            # 选择
            s = self.select(x)
            # 交叉复制
            cc = self.cross_copy(s)
            # 变异
            v = self.mutate(cc)
            x = v
            # 获取最优染色体和适应度列表
            best_chromosome, best_fitness = self.get_best(v)
            print('第', gen + 1, '迭代的最佳适应度：', best_fitness)
            fitness_list.append(best_fitness)
            # 退出条件
            if np.abs(fitness_list[-1]) < self.fitness_end:
                break

        return best_chromosome, fitness_list

    def select(self, x):
        """
        selection 选择
        :param x: 初始种群
        :return: s选择种群
        """
        # 种群中每条染色体的适应度
        fitness_all = []
        for one in x:
            num = Coder.decode_BIN(one, self.x_min, self.decimal)
            fitness_all.append(fitness_ex(num))

        # 适应度求和
        fitness_sum = sum(fitness_all)

        # 根据适应度构建积累概率
        acc_p = []
        for i in range(0, len(fitness_all)):
            acc_p.append(sum(fitness_all[:i + 1]) / fitness_sum)

        # 开始轮盘赌，选择种群
        s = []
        for i in range(0, len(x)):
            # 选择概率，[0,1)之间的随机数
            sr = np.random.random()
            for j in range(len(acc_p)):
                # 根据轮盘赌规则进行选择
                if acc_p[j] > sr:
                    s.append(x[j])
                    break

        return s

    def cross_copy(self, s):
        """
        交叉复制
        :param self:
        :param s: 选择种群
        :return: cc交叉复制种群
        """
        # 需要交叉次数
        num_cr = self.NP * self.CR
        # 计数器，交换次数达到num次
        count = 0
        i = 0
        # 交叉种群
        cc = []
        # 交叉 选择种群已随机，直接相邻两组做交叉
        while (i < self.NP):
            # 单点交叉点
            index_cross = np.random.randint(0, self.D)
            # 将两个个体从交叉点断开
            tmp11 = s[i][:index_cross]
            tmp12 = s[i][index_cross:]
            tmp21 = s[i + 1][:index_cross]
            tmp22 = s[i + 1][index_cross:]
            # 重新组合成新的个体
            tmp1 = tmp11 + tmp22
            tmp2 = tmp21 + tmp12

            # 超出范围后重新随机产生交叉点
            if not self.range_in(tmp1):
                continue
            if not self.range_in(tmp2):
                continue

            # 均为范围内
            cc.append(tmp1)
            cc.append(tmp2)
            i += 2
            # 交叉次数
            count += 1
            if count >= num_cr:
                break

        # 复制
        for j in range(i, self.NP):
            cc.append(s[i])

        return cc

    def mutate(self, cc):
        """
        mutation 变异
        :param cc: 交叉种群
        :return: v变异种群
        """
        # 变异种群
        v = []
        for i in range(self.NP):
            # 变异概率，[0,1)之间的随机数
            mr = np.random.random()
            if mr >= self.MR:
                v.append(cc[i])
                continue

            # 随机产生变异点
            index_mutate = np.random.randint(0, self.D)
            # 基因变异，改变0为1，1为0
            tmp = self.change01(cc[i], index_mutate)
            # 保证在范围内
            while (not self.range_in(tmp)):
                # 如果超出范围则重新随机产生变异点，直到满足范围
                index_mutate = np.random.randint(0, self.D)
                tmp = self.change01(cc[i], index_mutate)
            v.append(tmp)

        return v

    def show(self, best_chromosome, fitness_list):
        """
        展示迭代过程
        :param best_chromosome: 最优染色体
        :param fitness_list: 每次迭代适应度值
        :return:
        """
        print("最优染色体:", str(best_chromosome))
        print("最优解:", str(fitness_list[-1]))

        plt.title("迭代过程")
        plt.xlabel("迭代次数")
        plt.ylabel("适应度")
        x = range(1, len(fitness_list) + 1)
        y = fitness_list
        plt.plot(x, y, label="GA")
        plt.legend()
        plt.show()

    def range_in(self, bin):
        """
        范围内[x_min,x_max]
        :param bin: 二进制数
        :return: True-范围内 False-范围外
        """
        num = Coder.decode_BIN(bin, self.x_min, self.decimal)
        if num <= self.x_min:
            return False

        if num >= self.x_max:
            return False

        return True

    def change01(self, bin_str, index):
        """
        改变指定位置字符
        0变1， 1变0
        :param bin_str: 二进制字符串
        :param index: 字符位置索引
        :return: 变化后的字符串
        """
        bin_list = list(bin_str)
        if '0' == bin_list[index]:
            bin_list[index] = "1"
        else:
            bin_list[index] = "0"

        return ''.join(bin_list)

    def get_best(self, v):
        """
        获取最优染色体和最优适应度
        :param v: 变异种群
        :return:
        """
        fitness_list = [fitness_ex(Coder.decode_BIN(one, self.x_min, self.decimal)) for one in v]
        # 适应度最大值所在的位置
        best_fitness = max(fitness_list)
        index = fitness_list.index(best_fitness)
        return Coder.decode_BIN(v[index], self.x_min, self.decimal), best_fitness


class Population(object):
    """
    种群
    """

    def __init__(self, x, s, cc, v, ):
        """
        初始化
        :param x: 初始种群
        :param s: 选择种群
        :param cc: 交叉种群
        :param v: 变异种群
        """
        self.x = x
        self.s = s
        self.cc = cc
        self.v = v


class Coder(object):
    """
    编码解码器
    """

    @staticmethod
    def get_dim(x_min, x_max, decimal):
        """
        获取十进制范围所需占用二进制位数
        :param: x_min: 十进制下边界
        :param: x_max: 十进制上边界
        :param: decimal: 小数位数
        :return: 占用bit数
        """
        # x_max-x_min，范围值，真实值需要+x_min
        # 不论如何+1，可以确保能存下
        dim = int(
            math.log(
                (x_max - x_min) * pow(10, decimal + 1)
                , 2)
        ) + 1

        return dim

    @staticmethod
    def encode_DEC(dec, x_min, decimal, bit_num):
        """
        编码十进制数
        :param: dec: 十进制数
        :param: decimal: 小数位数
        :param: bit_num: 占用bit数
        :return: 二进制字符序列
        """
        # dec - x_min 不考虑负数编码，全部转成正数
        # 因为，编码x_max-x_min范围内的数，所以需要实际dec-x_min
        if x_min < 0:
            binary = bin(int((dec - 2 * x_min) * pow(10, decimal + 1)))
        else:
            binary = bin(int((dec - x_min) * pow(10, decimal + 1)))

        # 除去0b
        binary = str(binary)[2:]
        # 补全
        while len(binary) < bit_num:
            binary = '0' + binary
        return binary

    @staticmethod
    def decode_BIN(bin, x_min, decimal):
        """
        解码二进制到10进制
        :return: 返回经过精度运算的十进制数
        """
        bin = '0b' + bin
        dec = int(bin, 2)
        # encode_DEC时，将负数+(-x_min)变成了正数，decode_BIN需要变回来
        # 因为解码结果是x_max-x_min范围内的数，所有需要解码数+x_min
        if x_min < 0:
            num = dec / pow(10, decimal + 1) + 2 * x_min
        else:
            num = dec / pow(10, decimal + 1) + x_min

        return num


if __name__ == '__main__':
    dim = Coder.get_dim(-1, 2, 5)
    ga = GeneticAlgorithm(100, 10e-6, -1, 2, 50, dim, 0.6, 0.005, 5)
    best_chromosome, fitness_list = ga.evolve()
    ga.show(best_chromosome, fitness_list)