148 lines
5.6 KiB
Python
148 lines
5.6 KiB
Python
from state_space_search import graphsearch, generate_cost_map
|
|
import random
|
|
|
|
# Parametry algorytmu genetycznego
|
|
POPULATION_SIZE = 700
|
|
MUTATION_RATE = 0.01
|
|
NUM_GENERATIONS = 600
|
|
|
|
# Generowanie początkowej populacji
|
|
def generate_individual(animals):
|
|
return random.sample(animals, len(animals))
|
|
|
|
def generate_population(animals, size):
|
|
return [generate_individual(animals) for _ in range(size)]
|
|
|
|
# Obliczanie odległości między zwierzetami
|
|
def calculate_distance(animal1, animal2):
|
|
x1, y1 = animal1
|
|
x2, y2 = animal2
|
|
return abs(x1 - x2) + abs(y1 - y2) # Odległość Manhattana
|
|
|
|
def calculate_total_distance(animals):
|
|
total_distance = 0
|
|
for i in range(len(animals) - 1):
|
|
total_distance += calculate_distance(animals[i], animals[i+1])
|
|
total_distance += calculate_distance(animals[-1], animals[0]) # Zamknięcie cyklu
|
|
return total_distance
|
|
|
|
# Selekcja rodziców za pomocą metody ruletki
|
|
def select_parents(population, num_parents):
|
|
fitness_scores = [1 / calculate_total_distance(individual) for individual in population]
|
|
total_fitness = sum(fitness_scores)
|
|
selection_probs = [fitness / total_fitness for fitness in fitness_scores]
|
|
|
|
parents = random.choices(population, weights=selection_probs, k=num_parents)
|
|
return parents
|
|
|
|
# Krzyżowanie rodziców (OX,Davis)
|
|
def crossover(parent1, parent2):
|
|
child1 = [None] * len(parent1)
|
|
child2 = [None] * len(parent1)
|
|
start_index = random.randint(0, len(parent1) - 1)
|
|
end_index = random.randint(start_index, len(parent1) - 1)
|
|
child1[start_index:end_index+1] = parent1[start_index:end_index+1]
|
|
child2[start_index:end_index+1] = parent2[start_index:end_index+1]
|
|
|
|
# Uzupełnienie brakujących zwierząt z drugiego rodzica
|
|
for i in range(len(parent1)):
|
|
if parent2[i] not in child1:
|
|
for j in range(len(parent2)):
|
|
if child1[j] is None:
|
|
child1[j] = parent2[i]
|
|
break
|
|
|
|
for i in range(len(parent1)):
|
|
if parent1[i] not in child2:
|
|
for j in range(len(parent1)):
|
|
if child2[j] is None:
|
|
child2[j] = parent1[i]
|
|
break
|
|
|
|
return child1, child2
|
|
|
|
# Mutacja: zamiana dwóch losowych zwierząt z prawdopodobieństwem MUTATION_RATE
|
|
def mutate(individual):
|
|
if random.random() < MUTATION_RATE:
|
|
index1, index2 = random.sample(range(len(individual)), 2)
|
|
individual[index1], individual[index2] = individual[index2], individual[index1]
|
|
|
|
# Algorytm genetyczny
|
|
def genetic_algorithm(animals):
|
|
population = generate_population(animals, POPULATION_SIZE)
|
|
|
|
for generation in range(NUM_GENERATIONS):
|
|
# Selekcja rodziców
|
|
parents = select_parents(population, POPULATION_SIZE // 2)
|
|
|
|
# Krzyżowanie i tworzenie nowej populacji
|
|
next_generation = []
|
|
for i in range(0, len(parents), 2):
|
|
parent1 = parents[i]
|
|
if i + 1 < len(parents):
|
|
parent2 = parents[i + 1]
|
|
else:
|
|
parent2 = parents[0]
|
|
child1, child2 = crossover(parent1, parent2)
|
|
next_generation.extend([child1, child2])
|
|
|
|
# Mutacja nowej populacji
|
|
for individual in next_generation:
|
|
mutate(individual)
|
|
|
|
# Zastąpienie starej populacji nową
|
|
population = next_generation
|
|
|
|
# Znalezienie najlepszego osobnika
|
|
best_individual = min(population, key=calculate_total_distance)
|
|
|
|
return best_individual
|
|
|
|
# def calculate_distance(start, goal, max_x, max_y, obstacles, cost_map):
|
|
# istate = (start[0], start[1], 'N') # Zakładamy, że zaczynamy od kierunku północnego
|
|
# actions, cost = graphsearch(istate, goal, max_x, max_y, obstacles, cost_map)
|
|
# return cost
|
|
|
|
# def calculate_total_distance(animals, max_x, max_y, obstacles, cost_map):
|
|
# total_distance = 0
|
|
# for i in range(len(animals) - 1):
|
|
# total_distance += calculate_distance(animals[i], animals[i+1], max_x, max_y, obstacles, cost_map)
|
|
# total_distance += calculate_distance(animals[-1], animals[0], max_x, max_y, obstacles, cost_map) # Zamknięcie cyklu
|
|
# return total_distance
|
|
|
|
# # Selekcja rodziców za pomocą metody ruletki
|
|
# def select_parents(population, num_parents, max_x, max_y, obstacles, cost_map):
|
|
# fitness_scores = [1 / calculate_total_distance(individual, max_x, max_y, obstacles, cost_map) for individual in population]
|
|
# total_fitness = sum(fitness_scores)
|
|
# selection_probs = [fitness / total_fitness for fitness in fitness_scores]
|
|
|
|
# parents = random.choices(population, weights=selection_probs, k=num_parents)
|
|
# return parents
|
|
|
|
|
|
# def genetic_algorithm(animals, max_x, max_y, obstacles, cost_map):
|
|
# population = generate_population(animals, POPULATION_SIZE)
|
|
|
|
# for generation in range(NUM_GENERATIONS):
|
|
# # Selekcja rodziców
|
|
# parents = select_parents(population, POPULATION_SIZE // 2, max_x, max_y, obstacles, cost_map)
|
|
|
|
# # Krzyżowanie i tworzenie nowej populacji
|
|
# next_generation = []
|
|
# for i in range(0, len(parents), 2):
|
|
# parent1 = parents[i]
|
|
# parent2 = parents[i + 1]
|
|
# child1, child2 = crossover(parent1, parent2)
|
|
# next_generation.extend([child1, child2])
|
|
|
|
# # Mutacja nowej populacji
|
|
# for individual in next_generation:
|
|
# mutate(individual)
|
|
|
|
# # Zastąpienie starej populacji nową
|
|
# population = next_generation
|
|
|
|
# # Znalezienie najlepszego osobnika
|
|
# best_individual = min(population, key=lambda individual: calculate_total_distance(individual, max_x, max_y, obstacles, cost_map))
|
|
|
|
# return best_individual |