遗传算法——以背包问题为例

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

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

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

# 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)