多目标优化算法非支配排序遗传 算法Ⅱ

多目标优化算法非支配排序遗传算法Ⅱ（NSGA-II）是一种常用的多目标优化算法，它是对非支配排序遗传算法（NSGA）的改进。NSGA-II在保留NSGA的非支配排序和拥挤度距离计算的基础上，引入了快速非支配排序和精英策略，以提高算法的收敛速度和搜索能力。

以下是NSGA-II算法的主要步骤：
1. 初始化种群，包括个体的编码方式和初始值。
2. 计算每个个体的适应度值，即目标函数值。
3. 进行非支配排序，将种群中的个体按照非支配等级进行排序。
4. 计算每个个体的拥挤度距离，以保证种群的多样性。
5. 选择新的种群，包括精英策略和锦标赛选择策略。
6. 对新的种群进行交叉和变异操作，生成下一代种群。
7. 重复步骤2-6，直到满足停止条件。

以下是NSGA-II算法的Python实现示例：

# 引入相关库
import random
import numpy as np

# 定义目标函数
def obj_func(x):
    f1 = x[0]**2 + x[1]**2
    f2 = (x[0]-1)**2 + x[1]**2
    return [f1, f2]

# 定义种群类
class Individual:
    def __init__(self, x):
        self.x = x
        self.obj = obj_func(x)
        self.rank = None
        self.crowding_distance = None

# 定义NSGA-II算法类
class NSGA2:
    def __init__(self, pop_size, n_generations, p_crossover, p_mutation, n_obj):
        self.pop_size = pop_size
        self.n_generations = n_generations
        self.p_crossover = p_crossover
        self.p_mutation = p_mutation
        self.n_obj = n_obj
        self.population = None

    # 初始化种群
    def initialize_population(self):
        self.population = []
        for i in range(self.pop_size):
            x = np.random.uniform(-5, 5, size=self.n_obj)
            self.population.append(Individual(x))

    # 计算非支配排序
    def non_dominated_sort(self, population):
        fronts = [[]]
        for individual in population:
            individual.domination_count = 0
            individual.dominated_solutions = []
            for other_individual in population:
                if individual.obj[0] < other_individual.obj[0] and individual.obj[1] < other_individual.obj[1]:
                    individual.dominated_solutions.append(other_individual)
                elif individual.obj[0] > other_individual.obj[0] and individual.obj[1] > other_individual.obj[1]:
                    individual.domination_count += 1
            if individual.domination_count == 0:
                individual.rank = 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_solutions:
                    dominated_individual.domination_count -= 1
                    if dominated_individual.domination_count == 0:
                        dominated_individual.rank = i + 1
                        next_front.append(dominated_individual)
            i += 1
            fronts.append(next_front)
        return fronts[:-1]

    # 计算拥挤度距离
    def crowding_distance(self, front):
        n = len(front)
        for individual in front:
            individual.crowding_distance = 0
        for m in range(self.n_obj):
            front = sorted(front, key=lambda individual: individual.obj[m])
            front[0].crowding_distance = np.inf
            front[-1].crowding_distance = np.inf
            for i in range(1, n-1):
                front[i].crowding_distance += (front[i+1].obj[m] - front[i-1].obj[m]) / (front[-1].obj[m] - front[0].obj[m])

    # 选择新的种群
    def selection(self, fronts):
        new_population = []
        n = 0
        while len(new_population) < self.pop_size:
            if len(fronts[n]) < self.pop_size - len(new_population):
                new_population += fronts[n]
                n += 1
            else:
                self.crowding_distance(fronts[n])
                fronts[n] = sorted(fronts[n], key=lambda individual: individual.crowding_distance, reverse=True)
                new_population += fronts[n][:self.pop_size - len(new_population)]
        self.population = new_population

    # 变异操作
    def mutation(self, individual):
        for i in range(self.n_obj):
            if random.random() < self.p_mutation:
                individual.x[i] += np.random.normal(0, 1)
                individual.x[i] = max(min(individual.x[i], 5), -5)
        individual.obj = obj_func(individual.x)

    # 交叉操作
    def crossover(self, parent1, parent2):
        if random.random() < self.p_crossover:
            child1 = Individual(np.zeros(self.n_obj))
            child2 = Individual(np.zeros(self.n_obj))
            alpha = np.random.uniform(0, 1, size=self.n_obj)
            for i in range(self.n_obj):
                child1.x[i] = alpha[i] * parent1.x[i] + (1 - alpha[i]) * parent2.x[i]
                child2.x[i] = alpha[i] * parent2.x[i] + (1 - alpha[i]) * parent1.x[i]
            child1.obj = obj_func(child1.x)
            child2.obj = obj_func(child2.x)
            return child1, child2
        else:
            return parent1, parent2

    # 进化
    def evolve(self):
        self.initialize_population()
        for i in range(self.n_generations):
            fronts = self.non_dominated_sort(self.population)
            self.selection(fronts)
            offspring_population = []
            while len(offspring_population) < self.pop_size:
                parent1 = random.choice(self.population)
                parent2 = random.choice(self.population)
                child1, child2 = self.crossover(parent1, parent2)
                self.mutation(child1)
                self.mutation(child2)
                offspring_population.append(child1)
                if len(offspring_population) < self.pop_size:
                    offspring_population.append(child2)
            self.population += offspring_population

# 运行NSGA-II算法
nsga2 = NSGA2(pop_size=100, n_generations=100, p_crossover=0.9, p_mutation=0.1, n_obj=2)
nsga2.evolve()

# 输出最终种群
for individual in nsga2.population:
    print(individual.obj)