NSGA-Ⅱ算法 代码

### NSGA-II 算法实现 NSGA-II (Non-dominated Sorting Genetic Algorithm II) 是一种用于解决多目标优化问题的有效进化算法。以下是 Python 中的一个简化版 NSGA-II 实现： ```python import random from copy import deepcopy import numpy as np class Individual: def __init__(self, genes): self.genes = genes self.fitness = None self.rank = None self.crowding_distance = 0 def non_dominated_sort(population): fronts = [[]] S = {i: [] for i in range(len(population))} n = [0 for _ in range(len(population))] for p in range(len(population)): for q in range(len(population)): if dominates(population[p], population[q]): S[p].append(q) elif dominates(population[q], population[p]): n[p] += 1 if n[p] == 0: population[p].rank = 0 fronts[0].append(p) front_index = 0 while(fronts[front_index]): next_front = [] for individual in fronts[front_index]: for other in S[individual]: n[other] -= 1 if n[other] == 0: population[other].rank = front_index + 1 next_front.append(other) front_index += 1 fronts.append(next_front) del fronts[-1] return fronts def crowding_distance_assignment(individuals): l = len(individuals) for individual in individuals: individual.crowding_distance = 0 for obj in range(len(individuals[0].fitness)): sorted_individuals = sorted(individuals, key=lambda x: x.fitness[obj]) sorted_individuals[0].crowding_distance = float('inf') sorted_individuals[l-1].crowding_distance = float('inf') for i in range(1,l-1): sorted_individuals[i].crowding_distance += \ (sorted_individuals[i+1].fitness[obj] - sorted_individuals[i-1].fitness[obj]) def create_initial_population(size, num_genes): pop = [] for _ in range(size): genes = [random.random() for _ in range(num_genes)] ind = Individual(genes=genes) pop.append(ind) return pop def crossover(parent1, parent2): child1_genes = [(p1 + p2)/2 for p1,p2 in zip(parent1.genes,parent2.genes)] child2_genes = [(p1 + p2)/2 for p1,p2 in zip(reversed(parent1.genes),reversed(parent2.genes))] return Individual(child1_genes),Individual(child2_genes) def mutate(individual, prob_mutate): new_genes = [] for gene in individual.genes: if random.uniform(0,1) < prob_mutate: new_genes.append(random.random()) else: new_genes.append(gene) individual.genes = new_genes def select_parents(population,k): mating_pool = [] I = list(range(len(population))) random.shuffle(I) for i in range(k//2): tourn_1,tourn_2 = I.pop(),I.pop() winner = binary_tournament_selection(population[tourn_1], population[tourn_2]) mating_pool.append(winner) return mating_pool def binary_tournament_selection(x,y): if x.rank < y.rank or ( x.rank == y.rank and x.crowding_distance > y.crowding_distance): return x else: return y def dominates(solution_a,solution_b): not_equal = False for f_a,f_b in zip(solution_a.fitness, solution_b.fitness): if f_b < f_a: return False elif f_b != f_a: not_equal = True return not_equal def evaluate_fitness(individual): # Define your fitness function here. pass population_size = 100 num_generations = 50 prob_crossover = 0.9 prob_mutation = 0.1 num_objectives = 2 gene_length = 30 initial_pop = create_initial_population(population_size,gene_length) for gen in range(num_generations): offspring = [] parents = select_parents(initial_pop, population_size) for i in range(0,len(parents)-1,2): if random.random() < prob_crossover: children = crossover(parents[i],parents[i+1]) offspring.extend(children) for indiv in offspring: mutate(indiv, prob_mutation) combined_pop = initial_pop + offspring for indiv in combined_pop: evaluate_fitness(indiv) fronts = non_dominated_sort(combined_pop) new_population = [] for front in fronts: crowding_distance_assignment([combined_pop[f] for f in front]) front_sorted_by_cd = sorted( [combined_pop[f] for f in front], key=lambda x:x.crowding_distance, reverse=True ) new_population.extend(front_sorted_by_cd) if len(new_population)>population_size: break initial_pop = new_population[:population_size] print("Final Population:") for ind in initial_pop: print(f'Genes:{ind.genes}, Fitness:{ind.fitness}') ``` 此代码展示了如何创建初始种群、评估适应度函数、执行非支配排序以及拥挤距离计算等功能[^1]。