#coding:utf-8
"""NSGA-II related functions"""
import functools
from population import Population
from car import Car
import random
import math
import copy
from functools import cmp_to_key
import operator
from individual import Individual
class MIMOAUtils(object):
def __init__(self, problem, num_of_individuals, mutation_strength=0.2, num_of_genes_to_mutate=5, num_of_tour_particips=2):
self.problem = problem
self.num_of_individuals = num_of_individuals
self.mutation_strength = mutation_strength
self.number_of_genes_to_mutate = num_of_genes_to_mutate
self.num_of_tour_particips = num_of_tour_particips
def fast_nondominated_sort(self, population):
population.fronts = []
population.fronts.append([])
for individual in population:
individual.domination_count = 0
individual.dominated_solutions = set()
for other_individual in population:
if individual.dominates(other_individual):
individual.dominated_solutions.add(other_individual)
elif other_individual.dominates(individual):
individual.domination_count += 1
if individual.domination_count == 0:
population.fronts[0].append(individual)
individual.rank = 0
i = 0
while len(population.fronts[i]) > 0:
temp = []
for individual in population.fronts[i]:
for other_individual in individual.dominated_solutions:
other_individual.domination_count -= 1
if other_individual.domination_count == 0:
other_individual.rank = i+1
temp.append(other_individual)
i = i+1
population.fronts.append(temp)
def __sort_objective(self, val1, val2, m):
return operator.gt(val1.objectives[m], val2.objectives[m])
def calculate_crowding_distance(self, front):
if len(front) > 0:
solutions_num = len(front)
for individual in front:
individual.crowding_distance = 0
for m in range(len(front[0].objectives)):
front = sorted(front, key=cmp_to_key(functools.partial(self.__sort_objective, m=m)))
front[0].crowding_distance = self.problem.max_objectives[m]
front[solutions_num-1].crowding_distance = self.problem.max_objectives[m]
for index, value in enumerate(front[1:solutions_num-1]):
front[index].crowding_distance = (front[index+1].crowding_distance - front[index-1].crowding_distance) / (self.problem.max_objectives[m] - self.problem.min_objectives[m])
def crowding_operator(self, individual, other_individual):
if(individual.rank < other_individual.rank) or (individual.rank == other_individual.rank and (individual.crowding_distance > other_individual.crowding_distance)):
return 1
else:
return -1
def create_initial_population(self, cusset):
population = Population()
for _ in range(self.num_of_individuals):
individual = self.problem.generateIndividual(cusset)
self.problem.calculate_objectives(individual)
population.population.append(individual)
return population
def create_children(self, population, cusset):
children = []
count_child = 0
while len(children) < len(population):
parent1 = self.tournament_selection(population)
parent2 = self.tournament_selection(population)
# while self.similarity_detection(parent1, parent2) > 0.68:
# parent2 = self.tournament_selection(population)
child1, child2 = self.crossover_new(parent1, parent2, cusset)
child1 = copy.deepcopy(self.rm_empty(child1))
child2 = copy.deepcopy(self.rm_empty(child2))
child1 = copy.deepcopy(self.mutate_self(child1))
child2 = copy.deepcopy(self.mutate_self(child2))
child1 = copy.deepcopy(self.rm_empty(child1))
child2 = copy.deepcopy(self.rm_empty(child2))
# self.output_ind(child1)
# self.output_ind(child2)
child1 = self.problem.local_search(child1, cusset)
child2 = self.problem.local_search(child2, cusset)
ind1 = self.problem.RSM(child1, cusset)
ind2 = self.problem.RSM(child2, cusset)
child1.cost = copy.deepcopy(ind1.cost)
child1.sat = copy.deepcopy(ind1.sat)
child2.cost = copy.deepcopy(ind2.cost)
child2.sat = copy.deepcopy(ind2.sat)
# self.output_ind(child1)
# self.output_ind(child2)
# print 'child1', child1.cost
# print 'child1', child1.sat
# print 'child2', child2.cost
# print 'child2', child2.sat
self.problem.calculate_objectives(child1)
self.problem.calculate_objectives(child2)
children.append(child1)
children.append(child2)
# print '@@@@@@@@@@@@@@@@@@@@@@@@@@', len(children)
# print 'count_child', len(children)
return children
def __crossover(self, individual1, individual2):
child1 = self.problem.generateIndividual()
child2 = self.problem.generateIndividual()
genes_indexes = range(len(child1.features))
half_genes_indexes = random.sample(genes_indexes, 1)
for i in genes_indexes:
if i in half_genes_indexes:
child1.features[i] = individual2.features[i]
child2.features[i] = individual1.features[i]
else:
child1.features[i] = individual1.features[i]
child2.features[i] = individual2.features[i]
return child1, child2
def cal_dis(self, cus1, cus2):
return math.sqrt((cus1[0] - cus2[0]) ** 2 + (cus1[1] - cus2[1]) ** 2)
def output_ind(self, individual):
print('-----------------------------')
for ai in range(len(individual.car_route)):
print(individual.car_route[ai].route)
print('-----------------------------')
def remove_repeat(self, individual, carroute):
for ai in range(len(individual.car_route)):
for cus in carroute.route:
if cus in individual.car_route[ai].route:
individual.car_route[ai].route.remove(cus)
for car in individual.car_route:
if len(car.route) == 0:
individual.car_route.remove(car)
#self.output_ind(individual)
return individual
def rm_empty(self, individual):
for car in individual.car_route:
if len(car.route) == 0:
individual.car_route.remove(car)
return individual
def crossover_new(self, parent1, parent2, cusset):
child1 = self.problem.generateIndividual(cusset)
child2 = self.problem.generateIndividual(cusset)
child1.car_route = copy.deepcopy(parent1.car_route)
child2.car_route = copy.deepcopy(parent2.car_route)
# area_list1 = range(len(parent1.car_route))
# random.shuffle(area_list1)
# area_select_id1 = random.choice(area_list1)
# area1_cent = parent1.car_route[area_select_id1].cus_area_center
# area_list2 = range(len(parent2.car_route))
# area_select_id2 = random.choice(area_list2)
# area2_cent = parent2.car_route[area_select_id2].cus_area_center
# li = []
# lii = []
# for i in range(len(child1.car_route)):
# li.append(self.cal_dis(area2_cent, child1.car_route[i].cus_area_center))
# c1_select_aid = li.index(min(li))
# for j in range(len(child2.car_route)):
# lii.append(self.cal_dis(area1_cent, child2.car_route[j].cus_area_center))
# c2_select_aid = lii.index(min(lii))
car_list1 = list(range(len(parent1.car_route)))
random.shuffle(car_list1)
car_select_id1 = random.choice(car_list1)
car_list2 = list(range(len(parent2.car_route)))
random.shuffle(car_list2)
car_select_id2 = random.choice(car_list2)
# print 'child1 len_parent2.car_route', len(parent2.car_route), area_select_id2, 'len_carset', len(parent2.car_route[area_select_id2].carset), car_select_id2
# print 'child2 len_parent1.car_route', len(parent1.car_route), area_select_id1, 'len_carset', len(parent1.car_route[area_select_id1].carset), car_select_id1
# print 'p2', parent2.car_route[area_select_id2].carset[car_select_id2].route
# print 'p1', parent1.car_route[area_select_id1].carset[car_select_id1].route
# print 'parent+++++++++++++++++++++++++++++++++++'
# self.output_ind(parent1)
# self.output_ind(parent2)
# print 'child+++++++++++++++++++++++++++++++++++'
# self.output_ind(child1)
# self.output_ind(child2)
child1 = self.remove_repeat(child1, parent2.car_route[car_select_id2])
child2 = self.remove_repeat(child2, parent1.car_route[car_select_id1])
# print 'child===================================='
# self.output_ind(child1)
# self.output_ind(child2)
# print parent2.car_route[area_select_id2].carset[car_select_id2].route
# print parent1.car_route[area_select_id1].carset[car_select_id1].route
child1.car_route.append(parent2.car_route[car_select_id2])
child2.car_route.append(parent1.car_route[car_select_id1])
# print 'child***************************************'
# self.output_ind(child1)
# self.output_ind(child2)
return child1, child2
def __mutate(self, child):
genes_to_mutate = random.sample(range(0, len(child.features)), self.number_of_genes_to_mutate)
for gene in genes_to_mutate:
child.features[gene] = child.features[gene] - self.mutation_strength/2 + random.random() * self.mutation_strength
if child.features[gene] < 0:
child.features[gene] = 0
elif child.features[gene] > 1:
child.features[gene] = 1
def mutate_self(self, child):
# area_list = range(len(child.car_route))
# if len(area_list) == 0:
# print 'area_len = 0'
# random.shuffle(area_list)
# area_select_id = random.choice(area_list)
# while len(child.car_route[area_select_id]) == 0:
# area_select_id = random.choice(area_list)
mut_type_list = [0, 1, 2]
random.shuffle(mut_type_list)
mut_select_id = random.choice(mut_type_list)
# for mut_select_id in mut_type_list:
if mut_select_id == 0:
li = list(range(len(child.car_route)))
random.shuffle(li)
car_id1 = random.choice(li)
random.shuffle(li)
car_id2 = random.choice(li)
aa = 0
while car_id1 == car_id2 and aa < 10:
car_id2 = random.choice(li)
aa = aa + 1
car1 = child.car_route[car_id1]
car2 = child.car_route[car_id2]
car1_route_li = range(len(car1.route))
# print 'car1_route_li', car1_route_li
car1_mut_id = random.choice(car1_route_li)
car2_route_li = range(len(car2.route))
# print 'car2_route_li', car2_route_li
