离散优化算法_遗传 离散_遗传算法代码

以下是一个简单的离散遗传算法的 Python 代码示例：

import random

# 遗传算法参数
POPULATION_SIZE = 100  # 种群数量
P_CROSSOVER = 0.9  # 交叉概率
P_MUTATION = 0.1  # 变异概率
MAX_GENERATIONS = 50  # 最大迭代次数

# 问题参数
N_ITEMS = 20  # 物品数量
MAX_WEIGHT = 50  # 背包最大承重
ITEMS_WEIGHT = [random.randint(1, 10) for _ in range(N_ITEMS)]  # 物品重量
ITEMS_VALUE = [random.randint(10, 100) for _ in range(N_ITEMS)]  # 物品价值

# 种群初始化
def init_population(size):
    population = []
    for i in range(size):
        chromosome = [random.randint(0, 1) for _ in range(N_ITEMS)]
        population.append(chromosome)
    return population

# 计算个体适应度
def fitness(individual):
    weight = 0
    value = 0
    for i in range(N_ITEMS):
        if individual[i] == 1:
            weight += ITEMS_WEIGHT[i]
            value += ITEMS_VALUE[i]
    if weight > MAX_WEIGHT:
        return 0
    else:
        return value

# 选择操作
def selection(population):
    fitnesses = [fitness(individual) for individual in population]
    total_fitness = sum(fitnesses)
    probabilities = [f / total_fitness for f in fitnesses]
    chosen = []
    for _ in range(2):
        r = random.random()
        for i in range(len(probabilities)):
            if r < probabilities[i]:
                chosen.append(population[i])
                break
            r -= probabilities[i]
    return chosen

# 交叉操作
def crossover(parents):
    if random.random() < P_CROSSOVER:
        crossover_point = random.randint(1, N_ITEMS - 1)
        child1 = parents[0][:crossover_point] + parents[1][crossover_point:]
        child2 = parents[1][:crossover_point] + parents[0][crossover_point:]
        return [child1, child2]
    else:
        return parents

# 变异操作
def mutation(individual):
    if random.random() < P_MUTATION:
        mutation_point = random.randint(0, N_ITEMS - 1)
        individual[mutation_point] = 1 - individual[mutation_point]
    return individual

# 主循环
population = init_population(POPULATION_SIZE)
for generation in range(MAX_GENERATIONS):
    print("Generation", generation)
    population = sorted(population, key=lambda x: fitness(x), reverse=True)
    print("Best individual:", population[0], "Fitness:", fitness(population[0]))
    new_population = [population[0]]  # 保留最优个体
    while len(new_population) < POPULATION_SIZE:
        parents = selection(population)
        children = crossover(parents)
        children = [mutation(child) for child in children]
        new_population.extend(children)
    population = new_population

print("Best individual:", population[0], "Fitness:", fitness(population[0]))

此代码实现了一个通过离散遗传算法解决背包问题的例子。其中，`init_population` 函数用于初始化种群，`fitness` 函数用于计算个体适应度，`selection` 函数用于选择操作，`crossover` 函数用于交叉操作，`mutation` 函数用于变异操作。主循环中，首先将种群按适应度从高到低排序，并输出最优个体和适应度。然后进行选择、交叉、变异操作，生成新的种群。最后输出最优个体和适应度。