inteligentny-traktor/genetic_algorithm.py
2023-06-25 20:06:32 +02:00

91 lines
2.9 KiB
Python

import random
import math
def create_initial_population(population_size, new_list, player):
population = []
for _ in range(population_size):
chromosome = new_list.copy()
chromosome.remove((player.x+1, player.y+1))
random.shuffle(chromosome)
chromosome.insert(0, (player.x+1, player.y+1))
population.append(chromosome)
return population
def calculate_distance(node1, node2):
x1, y1 = node1
x2, y2 = node2
distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
return distance
def calculate_fitness(individual):
total_distance = 0
num_nodes = len(individual)
for i in range(num_nodes - 1):
node1 = individual[i]
node2 = individual[i + 1]
distance = calculate_distance(node1, node2)
total_distance += distance
if total_distance == 0:
fitness = float('inf')
return fitness
fitness = 1 / total_distance
return fitness
def crossover(parent1, parent2, player):
child = [(player.x+1, player.y+1)] + [None] * (len(parent1) - 1)
start_index = random.randint(1, len(parent1) - 1)
end_index = random.randint(start_index + 1, len(parent1))
child[start_index:end_index] = parent1[start_index:end_index]
remaining_nodes = [node for node in parent2 if node not in child]
child[1:start_index] = remaining_nodes[:start_index - 1]
child[end_index:] = remaining_nodes[start_index - 1:]
return child
def mutate(individual, mutation_rate):
for i in range(1, len(individual)):
if random.random() < mutation_rate:
j = random.randint(1, len(individual) - 1)
individual[i], individual[j] = individual[j], individual[i]
return individual
def genetic_algorithm(new_list, player):
max_generations = 200
population_size = 200
mutation_rate = 0.1
population = create_initial_population(population_size, new_list, player)
best_individual = None
best_fitness = float('-inf')
for generation in range(max_generations):
fitness_values = [calculate_fitness(individual) for individual in population]
population = [x for _, x in sorted(zip(fitness_values, population), reverse=True)]
fitness_values.sort(reverse=True)
best_individuals = population[:10]
new_population = best_individuals.copy()
while len(new_population) < population_size:
parent1, parent2 = random.choices(best_individuals, k=2)
child = crossover(parent1, parent2, player)
child = mutate(child, mutation_rate)
new_population.append(child)
for individual in best_individuals:
fitness = calculate_fitness(individual)
if fitness > best_fitness:
best_fitness = fitness
best_individual = individual
population = new_population[:population_size]
return best_individual