NSGA-II的算法代码实现

以下是NSGA-II算法的Python实现代码：

import random
import copy

class NSGAII:

    def __init__(self, num_variables, objectives, constraints, generations, population_size, crossover_prob, mutation_prob):
        self.num_variables = num_variables
        self.objectives = objectives
        self.constraints = constraints
        self.generations = generations
        self.population_size = population_size
        self.crossover_prob = crossover_prob
        self.mutation_prob = mutation_prob
        self.population = []
        self.offspring_population = []
        self.fronts = [[]]
        self.crowding_distance = []
        self.rank = []
        self.max_rank = 0
        self.min_distance = []
        self.min_value = []
        self.max_value = []
        self.initialize_population()

    def initialize_population(self):
        for i in range(self.population_size):
            individual = []
            for j in range(self.num_variables):
                individual.append(random.uniform(self.constraints[j][0], self.constraints[j][1]))
            self.population.append(individual)

    def evaluate_objectives(self, individual):
        return [obj(individual) for obj in self.objectives]

    def dominates(self, individual1, individual2):
        obj1 = self.evaluate_objectives(individual1)
        obj2 = self.evaluate_objectives(individual2)
        dominates = False
        for i in range(len(obj1)):
            if obj1[i] < obj2[i]:
                dominates = True
            elif obj1[i] > obj2[i]:
                return False
        return dominates

    def fast_non_dominated_sort(self, population):
        self.fronts = [[]]
        self.rank = [-1 for i in range(len(population))]
        self.min_distance = [0 for i in range(len(population))]
        self.max_rank = 0
        for i in range(len(population)):
            self.rank[i] = 0
            for j in range(len(population)):
                if i != j:
                    if self.dominates(population[i], population[j]):
                        self.fronts[i].append(j)
                    elif self.dominates(population[j], population[i]):
                        self.rank[i] += 1
            if self.rank[i] == 0:
                self.fronts[0].append(i)
        i = 0
        while len(self.fronts[i]) > 0:
            next_front = []
            for j in range(len(self.fronts[i])):
                for k in range(len(self.fronts[i][j])):
                    self.rank[self.fronts[i][j][k]] -= 1
                    if self.rank[self.fronts[i][j][k]] == 0:
                        next_front.append(self.fronts[i][j][k])
            i += 1
            self.fronts.append(next_front)
        self.fronts.pop()

    def crowding_distance_assignment(self, front):
        self.crowding_distance = [0 for i in range(len(front))]
        for m in range(len(self.objectives)):
            sorted_front = sorted(front, key=lambda individual: self.evaluate_objectives(individual)[m])
            self.min_value[m] = self.evaluate_objectives(sorted_front[0])[m]
            self.max_value[m] = self.evaluate_objectives(sorted_front[-1])[m]
            for i in range(1, len(sorted_front)-1):
                self.crowding_distance[i] += (self.evaluate_objectives(sorted_front[i+1])[m] - self.evaluate_objectives(sorted_front[i-1])[m])/(self.max_value[m] - self.min_value[m])

    def crowding_distance_sort(self, front):
        sorted_front = sorted(front, key=lambda individual: self.crowding_distance[front.index(individual)], reverse=True)
        return sorted_front

    def selection(self):
        selected_population = []
        for i in range(self.population_size):
            front = self.fronts[random.randint(0, len(self.fronts)-1)]
            if len(front) == 1:
                selected_population.append(front[0])
            else:
                sorted_front = self.crowding_distance_sort(front)
                selected_population.append(sorted_front[0])
        self.population = [self.population[individual] for individual in selected_population]

    def crossover(self, parent1, parent2):
        child1 = copy.deepcopy(parent1)
        child2 = copy.deepcopy(parent2)
        if random.random() < self.crossover_prob:
            for i in range(self.num_variables):
                if random.random() < 0.5:
                    child1[i] = parent2[i]
                    child2[i] = parent1[i]
        return child1, child2

    def mutation(self, individual):
        mutated_individual = copy.deepcopy(individual)
        for i in range(self.num_variables):
            if random.random() < self.mutation_prob:
                mutated_individual[i] = random.uniform(self.constraints[i][0], self.constraints[i][1])
        return mutated_individual

    def create_offspring_population(self):
        self.offspring_population = []
        for i in range(self.population_size//2):
            parent1 = self.population[random.randint(0, self.population_size-1)]
            parent2 = self.population[random.randint(0, self.population_size-1)]
            child1, child2 = self.crossover(parent1, parent2)
            mutated_child1 = self.mutation(child1)
            mutated_child2 = self.mutation(child2)
            self.offspring_population.append(mutated_child1)
            self.offspring_population.append(mutated_child2)

    def replace_population(self):
        combined_population = self.population + self.offspring_population
        self.fast_non_dominated_sort(combined_population)
        new_population = []
        i = 0
        while len(new_population) + len(self.fronts[i]) <= self.population_size:
            for individual in self.fronts[i]:
                new_population.append(individual)
            i += 1
        self.crowding_distance_assignment(self.fronts[i])
        sorted_front = self.crowding_distance_sort(self.fronts[i])
        for j in range(self.population_size - len(new_population)):
            new_population.append(sorted_front[j])
        self.population = [combined_population[individual] for individual in new_population]

    def optimize(self):
        for i in range(self.generations):
            self.create_offspring_population()
            self.replace_population()
            print("Generation:", i+1, "Best individual:", self.population[0], "Objectives:", self.evaluate_objectives(self.population[0]))