「遗传算法」以背包问题为例

What's Genetic Algorithm?

A Genetic Algorithm (GA) is a type of optimization algorithm that is inspired by the process of natural selection and genetics. GAs are used to find approximate solutions to optimization and search problems, especially in cases where the search space is vast and complex. They are particularly useful when you have a large solution space and don't know the mathematical form of the objective function you're trying to optimize.

什么是背包问题？

假设我们有一个背包，最多只能装6件物品且物品总重量不超过80，如何才能找到一个组合，可以尽量让装进去的物品总价值最高？

这，就是背包问题。

GA算法解决背包问题

随机初始化种群函数

def init_population(population_size: int = 50) -> list:
    """
    Create a population of random solutions
    :param population_size: Number of organisms in a population
    :return: Randomly generated population
    """
    population = []
    for i in range(population_size):
        chromosome = []
        for j in range(num_items):
            chromosome.append(random.randint(0, 1))
        population.append(chromosome)

    return population

该函数用于初始化一个种群，该种群中具有population_size个成员。

以随机化得到的第二个成员[1, 1, 0, 1, 1, 1]为例：

表示选择1、2、4、5、6号物品装入背包的组合。

基因评价函数

def evaluate_fitness(chrom: list) -> int:
    """
    Evaluate the fitness of a solution using your objective function
    :param chrom: 基因序列
    :return: 返回该基因序列的“质量高低“
    """
    weight_sum, value_sum = 0, 0
    for i in range(len(chrom)):
        if chrom[i] == 1:
            weight_sum, value_sum = weight_sum + weights[i], value_sum + values[i]

    return 0 if weight_sum > capacity else value_sum

该函数的作用是，传入一个成员的基因（物品）组合，然后返回其基因质量评分。对应到背包问题，就是返回该种组合物品的总价值。

需要特殊说明的是，当物品总重量超过限制值时（weight_sum > capacity），则返回0，因为此时价格没有意义。

种群优质成员选择

def select_parents(population: list, selection_rate: float = 0.5) -> list:
    """
    Select parents based on their fitness
    :param population: All members of the population
    :param selection_rate: Selection ratio of high-quality members
    :return: high-quality members(Selected by function evaluate_fitness())
    """
    population_fitness_values = []
    for chrom in population:  # 遍历种群中每一个成员的基因，得到其基因”评分“
        population_fitness_values.append(evaluate_fitness(chrom))

    sorted_population = [x for _, x in
                         sorted(zip(population_fitness_values, population), reverse=True)]  # 将种群中的成员按照其基因”质量评分“升序排列
    cut_num = int(selection_rate * len(sorted_population))  # 只选择前cut_num个”优质“种群成员用于后续交配繁衍
    return sorted_population[:cut_num]  # 返回”优质“种群成员

该函数的作用是对种群中的优质成员进行筛选。反应到背包问题中，就是对当前所有物品组合的价值进行排序，过滤价值较高的组合。

父类繁衍函数

def crossover(parent_0: list, parent_1: list) -> list:
    """
    Perform crossover to create offspring
    :param parent_0: First parent class member
    :param parent_1: Second parent class member
    :return: Two offspring by exchanging information between two parents
    """
    cut_point = random.randint(0, len(parent_0) - 1)
    child = parent_0[:cut_point] + parent_1[cut_point:]
    # child_1 = parent_1[:cut_point] + parent_0[cut_point:]
    return child

该函数的作用是对两个传入父类的基因进行交叉重组，得到一个新的子类。

基因突变函数

def mutate(chrom: list, mutation_rate: float = 0.01) -> list:
    """
    Apply mutation to a solution
    :param mutation_rate: Probability of gene mutations
    :param chrom: Normal chromosomes
    :return: Mutated chromosomes
    """
    for i in range(len(chrom)):
        if random.random() < mutation_rate:
            j = random.randint(0, num_items - 1)
            chrom[i], chrom[j] = chrom[j], chrom[i]

    return chrom

该函数的作用是对某个成员的基因进行突变。

GA算法思路

# Main GA loop
num_iterations = 100  # 循环迭代数——即进行多少代的繁衍
population = init_population(100)  # 初始化100个种群成员

for generation in range(num_iterations):  # 开始优胜略汰循环繁衍
    # 对初始种群成员进行过滤筛选，保留“高质量”种群成员基因
    parents = select_parents(population)

    # 使用“高质量”种群成员基因交配繁衍新成员
    offspring = []
    for _ in range(len(population) - len(parents)):  # 优胜略汰淘汰了几个种群成员，那么就再在“优秀”成员中繁衍出几个新成员
        parent_0, parent_1 = random.choice(parents), random.choice(parents)  # 随机选择两个高质量成员
        child = crossover(parent_0, parent_1)  # 交换基因得到新成员
        child = mutate(child)  # 新成员进行基因变异
        offspring.append(child)

    # 将新成员补充到种群中
    population = parents + offspring

# 对经过多次迭代循环后的种群基因进行排序，选择出最好的
best_chrom = max(population, key=evaluate_fitness)
best_fitness = evaluate_fitness(best_chrom)
print('Best Solution: ', best_chrom)
print('Best Fitness: ', best_fitness)

对于该问题，最终的解为选择物品1、3、4装入背包，总重量为75（满足小于80的需求），总价值为45。