NSGA-II算法求解01背包问题python代码

以下是使用 NSGA-II 算法求解 01 背包问题的 Python 代码：

import random

# 定义背包容量和物品的重量和价值
capacity = 50
weights = [10, 20, 30, 40, 50]
values = [1, 2, 3, 4, 5]

# 定义种群大小和迭代次数
pop_size = 100
max_iter = 50

# 定义交叉概率、变异概率和选择压力
crossover_prob = 0.9
mutation_prob = 0.1
tournament_size = 2

# 定义个体类
class Individual:
    def __init__(self):
        self.chromosome = []
        self.fitness = []

    def initialize(self):
        for i in range(len(weights)):
            self.chromosome.append(random.randint(0, 1))

    def evaluate(self):
        weight_sum = 0
        value_sum = 0
        for i in range(len(weights)):
            weight_sum += self.chromosome[i] * weights[i]
            value_sum += self.chromosome[i] * values[i]
        if weight_sum <= capacity:
            self.fitness.append(value_sum)
        else:
            self.fitness.append(0)

# 定义种群类
class Population:
    def __init__(self):
        self.population = []

    def initialize(self):
        for i in range(pop_size):
            individual = Individual()
            individual.initialize()
            individual.evaluate()
            self.population.append(individual)

    def non_dominated_sort(self):
        fronts = [[]]
        for individual in self.population:
            individual.domination_count = 0
            individual.dominated_individuals = []
            for other_individual in self.population:
                if individual.fitness[0] < other_individual.fitness[0] and individual.fitness[1] < other_individual.fitness[1]:
                    individual.dominated_individuals.append(other_individual)
                elif individual.fitness[0] > other_individual.fitness[0] and individual.fitness[1] > other_individual.fitness[1]:
                    individual.domination_count += 1
            if individual.domination_count == 0:
                fronts[0].append(individual)

        i = 0
        while len(fronts[i]) > 0:
            next_front = []
            for individual in fronts[i]:
                for dominated_individual in individual.dominated_individuals:
                    dominated_individual.domination_count -= 1
                    if dominated_individual.domination_count == 0:
                        next_front.append(dominated_individual)
            i += 1
            fronts.append(next_front)
        return fronts[:-1]

    def crowding_distance_assignment(self, front):
        for individual in front:
            individual.distance = 0
        for m in range(len(front[0].fitness)):
            sorted_front = sorted(front, key=lambda individual: individual.fitness[m])
            front_min = sorted_front[0].fitness[m]
            front_max = sorted_front[-1].fitness[m]
            for i in range(1, len(front)-1):
                individual = sorted_front[i]
                next_individual = sorted_front[i+1]
                individual.distance += (next_individual.fitness[m] - individual.fitness[m]) / (front_max - front_min)

    def selection(self, front):
        self.crowding_distance_assignment(front)
        front.sort(key=lambda individual: individual.distance, reverse=True)
        selected_individuals = front[:pop_size-len(self.population)]
        self.population.extend(selected_individuals)

    def crossover(self, parent1, parent2):
        child1 = Individual()
        child2 = Individual()
        if random.random() < crossover_prob:
            crossover_point = random.randint(1, len(weights)-1)
            child1.chromosome = parent1.chromosome[:crossover_point] + parent2.chromosome[crossover_point:]
            child2.chromosome = parent2.chromosome[:crossover_point] + parent1.chromosome[crossover_point:]
        else:
            child1.chromosome = parent1.chromosome
            child2.chromosome = parent2.chromosome
        return child1, child2

    def mutation(self, individual):
        if random.random() < mutation_prob:
            mutation_point = random.randint(0, len(weights)-1)
            individual.chromosome[mutation_point] = 1 - individual.chromosome[mutation_point]

    def evolve(self):
        self.initialize()
        for i in range(max_iter):
            fronts = self.non_dominated_sort()
            for front in fronts:
                self.selection(front)
                while len(self.population) > pop_size:
                    self.population.pop()
                for j in range(0, len(front)-1, 2):
                    parent1 = front[j]
                    parent2 = front[j+1]
                    child1, child2 = self.crossover(parent1, parent2)
                    child1.evaluate()
                    child2.evaluate()
                    self.mutation(child1)
                    self.mutation(child2)
                    self.population.append(child1)
                    self.population.append(child2)
        return self.population

# 运行算法
population = Population()
final_population = population.evolve()

# 输出最后的 Pareto 前沿
pareto_front = population.non_dominated_sort()[0]
print("Pareto Front:")
for individual in pareto_front:
    print(individual.fitness)

在这个代码中，我们首先定义了背包容量和物品的重量和价值。然后，我们定义了种群大小和迭代次数，以及交叉概率、变异概率和选择压力等参数。接着，我们定义了个体类和种群类，其中个体类包含了染色体和适应度评估方法，而种群类则包含了初始化、非支配排序、拥挤距离分配、选择、交叉和变异等方法。最后，我们运行算法并输出最后的 Pareto 前沿。

需要注意的是，这个算法只能找到 Pareto 前沿，而不能找到最优解。如果你想找到最优解，可以在找到 Pareto 前沿之后，使用其他方法进行进一步优化。