用python写NSGA2

NSGA-II（Non-dominated Sorting Genetic Algorithm II）是一种经典的多目标优化算法，可以求解具有多个决策变量和多个目标函数的优化问题。下面是一个用Python实现NSGA-II算法的简单示例：

import random
import math

# 定义一个个体类
class Individual:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.fitness = [0, 0]
        self.rank = 0
        self.distance = 0

# 生成初始种群
def generate_population(population_size):
    population = []
    for i in range(population_size):
        x = random.uniform(0, 1)
        y = random.uniform(0, 1)
        individual = Individual(x, y)
        population.append(individual)
    return population

# 计算适应度函数
def calculate_fitness(individual):
    x = individual.x
    y = individual.y
    fitness1 = x
    fitness2 = (1 + y) / x
    individual.fitness = [fitness1, fitness2]

# 非支配排序
def non_dominated_sorting(population):
    fronts = []
    population_size = len(population)
    domination_count = [0] * population_size
    dominated_individuals = [[] for i in range(population_size)]
    S = [[] for i in range(population_size)]
    front = []
    for i in range(population_size):
        individual = population[i]
        for j in range(population_size):
            if i == j:
                continue
            other_individual = population[j]
            if individual.fitness[0] > other_individual.fitness[0] and individual.fitness[1] > other_individual.fitness[1]:
                dominated_individuals[i].append(j)
            elif individual.fitness[0] < other_individual.fitness[0] and individual.fitness[1] < other_individual.fitness[1]:
                domination_count[i] += 1
        if domination_count[i] == 0:
            individual.rank = 1
            front.append(i)
            S[0].append(i)
    fronts.append(front)
    i = 0
    while len(fronts[i]) > 0:
        next_front = []
        for j in fronts[i]:
            for k in dominated_individuals[j]:
                domination_count[k] -= 1
                if domination_count[k] == 0:
                    population[k].rank = i + 2
                    next_front.append(k)
        i += 1
        fronts.append(next_front)
    return fronts[:-1]

# 计算拥挤度距离
def calculate_crowding_distance(front):
    distance = [0] * len(front)
    front_size = len(front)
    for i in range(2):
        fitness_list = [front[j].fitness[i] for j in range(front_size)]
        sorted_fitness_index = sorted(range(front_size), key=lambda k: fitness_list[k])
        distance[sorted_fitness_index[0]] = math.inf
        distance[sorted_fitness_index[-1]] = math.inf
        for j in range(1, front_size - 1):
            distance[sorted_fitness_index[j]] += (fitness_list[sorted_fitness_index[j + 1]] - fitness_list[sorted_fitness_index[j - 1]]) / (fitness_list[sorted_fitness_index[-1]] - fitness_list[sorted_fitness_index[0]])
    for i in range(front_size):
        front[i].distance = distance[i]

# 选择操作
def selection(population):
    population_size = len(population)
    mating_pool = []
    for i in range(population_size):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        mating_pool.append((parent1, parent2))
    return mating_pool

# 锦标赛选择
def tournament_selection(population):
    tournament_size = 2
    population_size = len(population)
    tournament_population = random.sample(population, tournament_size)
    best_individual = None
    for individual in tournament_population:
        if best_individual is None or individual.rank < best_individual.rank or (individual.rank == best_individual.rank and individual.distance > best_individual.distance):
            best_individual = individual
    return best_individual

# 交叉操作
def crossover(mating_pool, crossover_rate):
    offspring_population = []
    for parents in mating_pool:
        if random.random() < crossover_rate:
            offspring1, offspring2 = simulated_binary_crossover(parents)
        else:
            offspring1, offspring2 = parents
        offspring_population.append(offspring1)
        offspring_population.append(offspring2)
    return offspring_population

# 模拟二进制交叉
def simulated_binary_crossover(parents):
    parent1, parent2 = parents
    eta = 10
    u = random.random()
    if u <= 0.5:
        beta = (2 * u) ** (1 / (eta + 1))
    else:
        beta = (1 / (2 * (1 - u))) ** (1 / (eta + 1))
    offspring1 = Individual(0, 0)
    offspring2 = Individual(0, 0)
    offspring1.x = 0.5 * ((1 + beta) * parent1.x + (1 - beta) * parent2.x)
    offspring1.y = 0.5 * ((1 + beta) * parent1.y + (1 - beta) * parent2.y)
    offspring2.x = 0.5 * ((1 - beta) * parent1.x + (1 + beta) * parent2.x)
    offspring2.y = 0.5 * ((1 - beta) * parent1.y + (1 + beta) * parent2.y)
    return offspring1, offspring2

# 变异操作
def mutation(offspring_population, mutation_rate):
    for individual in offspring_population:
        if random.random() < mutation_rate:
            polynomial_mutation(individual)

# 多项式变异
def polynomial_mutation(individual):
    eta_m = 20
    u = random.random()
    if u <= 0.5:
        delta = (2 * u) ** (1 / (eta_m + 1)) - 1
    else:
        delta = 1 - (2 * (1 - u)) ** (1 / (eta_m + 1))
    x_min = 0
    x_max = 1
    y_min = 0
    y_max = 1
    individual.x = max(x_min, min(x_max, individual.x + delta))
    individual.y = max(y_min, min(y_max, individual.y + delta))

# NSGA-II算法主函数
def nsga2(population_size, max_generation, crossover_rate, mutation_rate):
    # 生成初始种群
    population = generate_population(population_size)
    # 计算适应度函数
    for individual in population:
        calculate_fitness(individual)
    # 迭代进化
    for generation in range(max_generation):
        # 非支配排序
        fronts = non_dominated_sorting(population)
        # 计算拥挤度距离
        for i in range(len(fronts)):
            calculate_crowding_distance([population[j] for j in fronts[i]])
        # 选择操作
        mating_pool = selection(population)
        # 交叉操作
        offspring_population = crossover(mating_pool, crossover_rate)
        # 变异操作
        mutation(offspring_population, mutation_rate)
        # 计算适应度函数
        for individual in offspring_population:
            calculate_fitness(individual)
        # 合并种群
        population += offspring_population
        # 非支配排序
        fronts = non_dominated_sorting(population)
        # 选择下一代种群
        new_population = []
        i = 0
        while len(new_population) + len(fronts[i]) <= population_size:
            new_population += [population[j] for j in fronts[i]]
            i += 1
        if len(new_population) < population_size:
            remaining_individuals = sorted([population[j] for j in fronts[i]], key=lambda individual: (individual.rank, -individual.distance), reverse=True)
            new_population += remaining_individuals[:(population_size - len(new_population))]
        population = new_population
    # 返回Pareto前沿集合
    pareto_front = [population[i] for i in range(len(population)) if population[i].rank == 1]
    return pareto_front

在这个示例中，我们定义了一个`Individual`类表示一个个体，包括两个决策变量、两个目标函数、非支配排序的等级和拥挤度距离。我们使用`generate_population`函数生成初始种群，使用`calculate_fitness`函数计算适应度函数，使用`non_dominated_sorting`函数进行非支配排序，并使用`calculate_crowding_distance`函数计算拥挤度距离。然后使用`selection`函数进行选择操作，使用`crossover`函数进行交叉操作，使用`mutation`函数进行变异操作。在每次迭代结束后，我们使用非支配排序选择下一代种群，并返回Pareto前沿集合。