烟花算法解决0-1背包问题的代码

import random
import math

# 适应度函数
def fitness(population, weight, value, max_weight):
    fit_value = []
    for i in range(len(population)):
        w = 0
        v = 0
        for j in range(len(population[i])):
            if population[i][j] == 1:
                w += weight[j]
                v += value[j]
        if w > max_weight:
            fit_value.append(0)
        else:
            fit_value.append(v)
    return fit_value

# 初始化种群
def init_population(population_size, gene_length):
    population = []
    for i in range(population_size):
        gene = [random.randint(0, 1) for j in range(gene_length)]
        population.append(gene)
    return population

# 选择操作
def selection(population, fit_value):
    new_population = []
    total_fit = sum(fit_value)
    for i in range(len(population)):
        p = random.uniform(0, total_fit)
        s = 0
        for j in range(len(population)):
            s += fit_value[j]
            if s > p:
                new_population.append(population[j])
                break
    return new_population

# 交叉操作
def crossover(population, pc):
    new_population = []
    for i in range(0, len(population), 2):
        if i + 1 < len(population):
            if random.random() < pc:
                cpoint = random.randint(1, len(population[i]) - 1)
                new_population.append(population[i][0:cpoint] + population[i + 1][cpoint:])
                new_population.append(population[i + 1][0:cpoint] + population[i][cpoint:])
            else:
                new_population.append(population[i])
                new_population.append(population[i + 1])
        else:
            new_population.append(population[i])
    return new_population

# 变异操作
def mutation(population, pm):
    new_population = []
    for i in range(len(population)):
        if random.random() < pm:
            mpoint = random.randint(0, len(population[i]) - 1)
            if population[i][mpoint] == 1:
                population[i][mpoint] = 0
            else:
                population[i][mpoint] = 1
        new_population.append(population[i])
    return new_population

# 烟花算法初始化
def init_fireworks(n, d, w, c, a, b):
    fireworks = []
    for i in range(n):
        firework = []
        for j in range(d):
            x = random.uniform(a, b)
            firework.append(x)
        fireworks.append(firework)
    return fireworks

# 烟花算法适应度函数
def fitness_fireworks(fireworks, weight, value, max_weight):
    fit_value = []
    for i in range(len(fireworks)):
        w = 0
        v = 0
        for j in range(len(fireworks[i])):
            if fireworks[i][j] > 0.5:
                w += weight[j]
                v += value[j]
        if w > max_weight:
            fit_value.append(0)
        else:
            fit_value.append(v)
    return fit_value

# 烟花算法爆炸操作
def explosion(firework, a, b, c):
    new_fireworks = []
    for i in range(c):
        new_firework = []
        for j in range(len(firework)):
            x = firework[j] + random.uniform(a, b) * (firework[j] - a)
            new_firework.append(x)
        new_fireworks.append(new_firework)
    return new_fireworks

# 烟花算法合并操作
def merge(fireworks, new_fireworks, w):
    all_fireworks = fireworks + new_fireworks
    all_fit_value = fitness_fireworks(all_fireworks, weight, value, max_weight)
    sorted_index = sorted(range(len(all_fit_value)), key=lambda k: all_fit_value[k], reverse=True)
    new_fireworks = []
    for i in range(w):
        new_fireworks.append(all_fireworks[sorted_index[i]])
    return new_fireworks

# 烟花算法
def fireworks_algorithm(weight, value, max_weight, n, d, w, c, a, b, T):
    fireworks = init_fireworks(n, d, w, c, a, b)
    fit_value = fitness_fireworks(fireworks, weight, value, max_weight)
    best_firework = fireworks[fit_value.index(max(fit_value))]
    best_fit_value = max(fit_value)
    for t in range(T):
        for i in range(n):
            new_fireworks = explosion(fireworks[i], a, b, c)
            new_fireworks_fit_value = fitness_fireworks(new_fireworks, weight, value, max_weight)
            fireworks[i] = merge(fireworks, new_fireworks, w)[0]
            fit_value[i] = fitness_fireworks([fireworks[i]], weight, value, max_weight)[0]
            if fit_value[i] > best_fit_value:
                best_firework = fireworks[i]
                best_fit_value = fit_value[i]
    return best_firework

# 0-1背包问题
def knapsack_01(weight, value, max_weight, population_size, pc, pm, T):
    gene_length = len(weight)
    population = init_population(population_size, gene_length)
    for t in range(T):
        fit_value = fitness(population, weight, value, max_weight)
        new_population = selection(population, fit_value)
        new_population = crossover(new_population, pc)
        new_population = mutation(new_population, pm)
        population = new_population
    best_individual = population[fit_value.index(max(fit_value))]
    best_weight = 0
    best_value = 0
    for i in range(len(best_individual)):
        if best_individual[i] == 1:
            best_weight += weight[i]
            best_value += value[i]
    return best_weight, best_value

# 测试
weight = [2, 2, 6, 5, 4]
value = [6, 3, 5, 4, 6]
max_weight = 10
population_size = 100
pc = 0.8
pm = 0.01
T = 100
best_weight, best_value = knapsack_01(weight, value, max_weight, population_size, pc, pm, T)
print("0-1背包问题的最优解为：")
print("最优重量为：", best_weight)
print("最优价值为：", best_value)
print("烟花算法解决0-1背包问题的最优解为：")
best_firework = fireworks_algorithm(weight, value, max_weight, 100, 5, 10, 5, 0, 1, 100)
best_weight = 0
best_value = 0
for i in range(len(best_firework)):
    if best_firework[i] > 0.5:
        best_weight += weight[i]
        best_value += value[i]
print("最优重量为：", best_weight)
print("最优价值为：", best_value)