机器学习：优化算法（四）—— 遗传算法

算法背景

术语界定

算法核心

问题定义

$$argmax f(x_{1})$$

• 编码DNA
• 定义适应度函数

问题求解

算法描述

经过N代进化，从末代种群中选出最优个体，每轮迭代：

1. 自然选择
2. 交叉重组
3. 基因突变

算法流程图

算法实现

#!/usr/bin/env python
# coding:utf-8
"""
遗传算法：“在程序里生宝宝, 杀死不乖的宝宝, 让乖宝宝继续生宝宝”

问题描述：
1. DNA：将每个可行解编码为DNA
2. 适应度函数：get_fitness(NDA)->value，计算每个DNA的适应度

进化过程：
1. 自然选择（selection）：适应性高的个体更容易存活
2. 交叉重组（crossover）：父代基因片段交换产生新的子代
3. 基因突变（mutation）：子代有一定概率发生基因突变

参数选择：
1. 种群大小
2. 交叉概率
3. 变异概率
4. 迭代次数
"""
import numpy as np
from erate import get_expected_rate


class Ga(object):
    def __init__(self, prob_matrix, for_accept, pop_size=50, cross_rate=0.6, mutate_rate=0.02, max_gen=100):
        """
        初始化遗传算法的进化参数，并生成初代DNA种群
        :param prob_matrix: 概率矩阵，type = ndarray，shape = (members_num * captains_num)
        :param for_accept: 每个队长待接收的队员数，ndarray shape = captains_num
        :param pop_size: 种群大小
        :param cross_rate: 交叉概率
        :param mutate_rate: 变异概率
        :param max_gen: 最大迭代次数
        """
        self.L = prob_matrix
        self.FOR_ACCEPT_NUM = for_accept
        self.MEMBERS_NUM = self.L.shape[0]
        self.CAPTAINS_NUM = self.L.shape[1]
        self.POP_SIZE = pop_size
        self.DNA_SIZE = L.size
        self.CROSS_RATE = cross_rate
        self.MUTATE_RATE = mutate_rate
        self.MAX_GEN = max_gen
        self.population = np.random.randint(2, size=(self.POP_SIZE, self.DNA_SIZE))
        self.fitness = np.apply_along_axis(self.get_fitness, axis=1, arr=self.population)

    def get_fitness(self, dna):
        """
        适应度：计算单个DNA的适应度
        :param dna: ndarray
        :return: 推荐矩阵ndarray
        """
        fitness = get_expected_rate(self.L, self.dna_decode(dna), self.FOR_ACCEPT_NUM)
        return fitness

    def dna_encode(self, individual):
        """
        DNA编码：将原始形式的参数编码为二进制形式的NDA列表
        :param individual: 存储二进制DNA的矩阵，(pop_size,DNA_size)
        :return: dna
        """
        dna = individual.ravel('C')
        return dna

    def dna_decode(self, dna):
        """
        DNA解码：将二进制形式的DNA解码为原始形式的参数形式
        :param dna: 个体dna
        :return: 原始推荐矩阵
        """
        individual = dna.reshape(self.MEMBERS_NUM, -1)
        return individual

    def select(self, population, fitness):
        """
        自然选择：依适应度高低/概率从原始种群中有放回地抽样出等容量的新种群，原地修改
        :param population: 种群矩阵ndarray
        :param fitness: 种群中每个个体的适应度,ndarray
        :return: 新的种群ndarray
        """
        idx = np.random.choice(np.arange(self.POP_SIZE), size=self.POP_SIZE, replace=True, p=fitness / fitness.sum())
        population[:] = population[idx]
        return

    def crossover(self, population, cross_rate):
        """
        交叉重组：给定父代群体，通过奇偶个体以一定概率进行交叉重组产生子代群体
        :param population: 给定父代群体，通过交叉重组产生子代群体
        :param cross_rate: 交叉重组的概率
        :return: 子代群体
        """
        for parent1, parent2 in zip(population[::2],population[1::2]):
            if np.random.rand() < cross_rate:
                cross_points = np.random.randint(0, 2, self.DNA_SIZE).astype(np.bool)
                parent1[cross_points], parent2[cross_points] = parent2[cross_points], parent1[cross_points]
        return

    def mutate(self, population, mutation_rate):
        """
        基因突变：子代DNA中的基因码位有一定概率发生变异
        :param population: 待变异的DNA
        :param mutation_rate: 突变的概率
        :return: 变异后的DNA
        """
        mutate_points = np.random.choice(2, size=population.shape, p=[1-mutation_rate, mutation_rate]).astype(np.bool)
        population[mutate_points] = 1 ^ population[mutate_points]
        self.fitness = np.apply_along_axis(self.get_fitness, axis=1, arr=self.population)
        return

    def evolution(self):
        """
        种群进化过程，迭代"自然选择-交叉重组-基因突变"，退出条件为满足一定的迭代次数
        :return: 最优的个体
        """
        for gen in range(self.MAX_GEN):
            print('generation: {}，fitness: {}'.format(gen, self.fitness.max()))
            self.select(self.population, self.fitness)
            self.crossover(self.population, self.CROSS_RATE)
            self.mutate(self.population, self.MUTATE_RATE)

        print('generation: {}，fitness: {}'.format(gen + 1, self.fitness.max()))
        res_id = self.fitness.argmax()
        print('近似最优期望组队成功率：{}'.format(self.fitness[res_id]))
        print('最优的分配方式: \n{}'.format(self.dna_decode(self.population[res_id])))
        return self.fitness[res_id]


if __name__ == "__main__":
    # 测试
    L = np.random.rand(6, 3)
    for_accept = np.ones(shape=L.shape[1], dtype=int) * (L.shape[0]//2)
    ga = Ga(L, for_accept)
    ga.evolution()

算法应用

优化方法

其他话题