nsga2算法代码python
时间: 2023-09-16 21:09:18 浏览: 44
以下是使用Python实现的NSGA-II算法代码:
```python
import random
import copy
import math
class Individual:
def __init__(self, variables, objectives):
self.variables = variables
self.objectives = objectives
self.dominated_count = 0
self.dominating_set = set()
def fast_non_dominated_sort(individuals):
fronts = []
dominating_sets = {individual: set() for individual in individuals}
dominated_counts = {individual: 0 for individual in individuals}
for i, p in enumerate(individuals):
for q in individuals[i+1:]:
if p.objectives < q.objectives:
dominating_sets[p].add(q)
dominated_counts[q] += 1
elif q.objectives < p.objectives:
dominating_sets[q].add(p)
dominated_counts[p] += 1
current_front = []
for individual in individuals:
if dominated_counts[individual] == 0:
current_front.append(individual)
individual.rank = 1
while current_front:
next_front = []
for p in current_front:
for q in dominating_sets[p]:
dominated_counts[q] -= 1
if dominated_counts[q] == 0:
q.rank = p.rank + 1
next_front.append(q)
fronts.append(current_front)
current_front = next_front
return fronts
def crowding_distance(front):
distances = {individual: 0 for individual in front}
objectives_count = len(front[0].objectives)
for i in range(objectives_count):
front.sort(key=lambda individual: individual.objectives[i])
distances[front[0]] = distances[front[-1]] = math.inf
objective_range = front[-1].objectives[i] - front[0].objectives[i]
for j in range(1, len(front)-1):
distances[front[j]] += (front[j+1].objectives[i] - front[j-1].objectives[i])/objective_range
return distances
def tournament_selection(population):
tournament_size = 2
tournament = random.sample(population, tournament_size)
return max(tournament, key=lambda individual: individual.rank)
def simulated_binary_crossover(p, q, crossover_probability, distribution_index):
if random.random() > crossover_probability:
return copy.deepcopy(p), copy.deepcopy(q)
else:
c1, c2 = copy.deepcopy(p), copy.deepcopy(q)
for i, (p_var, q_var) in enumerate(zip(p.variables, q.variables)):
if random.random() > 0.5:
if abs(p_var - q_var) > 1e-14:
y1, y2 = min(p_var, q_var), max(p_var, q_var)
u = random.random()
beta = 1 + (2.0*(y1 - 0.0)/(y2 - y1))
alpha = 2.0 - beta**(-(distribution_index+1))
if u <= 1.0/alpha:
beta_q = (u*alpha)**(1.0/(distribution_index+1))
else:
beta_q = (1.0/(2.0 - u*alpha))**(1.0/(distribution_index+1))
beta_p = 1.0 - beta_q
c1.variables[i] = beta_p*p_var + beta_q*q_var
c2.variables[i] = beta_q*p_var + beta_p*q_var
return c1, c2
def polynomial_mutation(individual, mutation_probability, distribution_index):
for i, variable in enumerate(individual.variables):
if random.random() < mutation_probability:
y1, y2 = 0.0, 1.0
y = variable
delta_1 = (y - y1)/(y2 - y1)
delta_2 = (y2 - y)/(y2 - y1)
u = random.random()
if u <= 0.5:
delta_q = (2*u + (1 - 2*u)*(1 - delta_1)**(distribution_index+1))**(1/(distribution_index+1)) - 1
else:
delta_q = 1 - (2*(1 - u) + 2*(u - 0.5)*(1 - delta_2)**(distribution_index+1))**(1/(distribution_index+1))
individual.variables[i] += delta_q*(y2 - y1)
def nsga2(objective_function, variable_count, lower_bound, upper_bound, population_size, max_generations):
crossover_probability = 0.9
mutation_probability = 1.0/variable_count
distribution_index = 20
population = []
for i in range(population_size):
variables = [random.uniform(lower_bound, upper_bound) for j in range(variable_count)]
objectives = objective_function(variables)
population.append(Individual(variables, objectives))
for i in range(max_generations):
fronts = fast_non_dominated_sort(population)
for front in fronts:
distances = crowding_distance(front)
for individual in front:
individual.distance = distances[individual]
offspring_population = []
while len(offspring_population) < population_size:
p = tournament_selection(population)
q = tournament_selection(population)
c1, c2 = simulated_binary_crossover(p, q, crossover_probability, distribution_index)
polynomial_mutation(c1, mutation_probability, distribution_index)
polynomial_mutation(c2, mutation_probability, distribution_index)
c1.objectives = objective_function(c1.variables)
c2.objectives = objective_function(c2.variables)
offspring_population.extend([c1, c2])
population.extend(offspring_population)
fronts = fast_non_dominated_sort(population)
population = []
for front in fronts:
if len(front) + len(population) > population_size:
front.sort(key=lambda individual: individual.distance, reverse=True)
population.extend(front[:population_size-len(population)])
break
else:
population.extend(front)
return population
```
这是一个NSGA-II实现的基本框架,可以根据具体问题进行修改和优化。在使用时,需要定义目标函数和变量个数,以及定义变量的取值范围、种群大小和迭代次数等参数。