99 lines
3.2 KiB
Python
99 lines
3.2 KiB
Python
|
import random
|
||
|
|
|
||
|
|
def make_population(population_s, field_s):
|
||
|
|
population = []
|
||
|
|
crops = ['apple', 'cauliflower', 'radish', 'wheat', 'rock_dirt', 'dirt']
|
||
|
|
|
||
|
|
for _ in range(population_s):
|
||
|
|
i = []
|
||
|
|
for _ in range(field_s):
|
||
|
|
row = random.choices(crops, k=field_s)
|
||
|
|
i.append(row)
|
||
|
|
population.append(i)
|
||
|
|
return population
|
||
|
|
|
||
|
|
def calculate_fitness(individual):
|
||
|
|
cost = 0
|
||
|
|
for i in range(len(individual)):
|
||
|
|
for j in range(len(individual[i])):
|
||
|
|
crop = individual[i][j]
|
||
|
|
neighbors = [
|
||
|
|
individual[x][y]
|
||
|
|
for x in range(max(0, i-1), min(len(individual), i+2))
|
||
|
|
for y in range(max(0, j-1), min(len(individual), j+2))
|
||
|
|
if (x,y) != (i,j)
|
||
|
|
]
|
||
|
|
for n in neighbors:
|
||
|
|
if crop == 'wheat' and n == 'apple':
|
||
|
|
cost += 2
|
||
|
|
elif crop == 'cauliflower' and n == 'radish':
|
||
|
|
cost += 4
|
||
|
|
|
||
|
|
fitness = 1/(1+cost)
|
||
|
|
return fitness
|
||
|
|
|
||
|
|
def select_parents(population, fitnesses):
|
||
|
|
fitnesses_sum = sum(fitnesses)
|
||
|
|
selection_parts = [fitness / fitnesses_sum for fitness in fitnesses]
|
||
|
|
parents = random.choices(population, weights=selection_parts, k=2)
|
||
|
|
return parents
|
||
|
|
|
||
|
|
def crossover(parent_1, parent_2):
|
||
|
|
crossover_point = random.randint(1, (len(parent_1)-1))
|
||
|
|
child_1 = parent_1[:crossover_point] + parent_2[crossover_point:]
|
||
|
|
child_2 = parent_2[:crossover_point] + parent_1[crossover_point:]
|
||
|
|
return child_1, child_2
|
||
|
|
|
||
|
|
def mutation(individual, chance):
|
||
|
|
crops = ['apple', 'cauliflower', 'radish', 'wheat', 'rock_dirt', 'dirt']
|
||
|
|
if random.random() < chance:
|
||
|
|
row = random.randint(0, len(individual) - 1)
|
||
|
|
column = random.randint(0, len(individual[0]) - 1)
|
||
|
|
individual[row][column] = random.choice(crops)
|
||
|
|
return individual
|
||
|
|
|
||
|
|
def genetic_algorithm(population_s, field_s, chance, limit):
|
||
|
|
population = make_population(population_s, field_s)
|
||
|
|
|
||
|
|
best_fitness = 0
|
||
|
|
count = 0
|
||
|
|
|
||
|
|
while best_fitness < 1:
|
||
|
|
fitnesses = [calculate_fitness(individual) for individual in population]
|
||
|
|
new_population = []
|
||
|
|
|
||
|
|
for _ in range(population_s // 2):
|
||
|
|
parent_1, parent_2 = select_parents(population, fitnesses)
|
||
|
|
|
||
|
|
p1c = calculate_fitness(parent_1)
|
||
|
|
p2c = calculate_fitness(parent_2)
|
||
|
|
print("p1c: ",p1c,"\np2c: ",p2c)
|
||
|
|
|
||
|
|
child_1, child_2 = crossover(parent_1, parent_2)
|
||
|
|
child_1 = mutation(child_1, chance)
|
||
|
|
child_2 = mutation(child_2, chance)
|
||
|
|
new_population.append(child_1)
|
||
|
|
new_population.append(child_2)
|
||
|
|
|
||
|
|
combined_population = population + new_population
|
||
|
|
combined_population = sorted(combined_population, key=calculate_fitness, reverse=True)
|
||
|
|
|
||
|
|
population = combined_population[:population_s]
|
||
|
|
|
||
|
|
current_best_fitness = calculate_fitness(population[0])
|
||
|
|
if current_best_fitness > best_fitness:
|
||
|
|
best_fitness = current_best_fitness
|
||
|
|
count = 0
|
||
|
|
else:
|
||
|
|
count += 1
|
||
|
|
|
||
|
|
if count >= limit:
|
||
|
|
break
|
||
|
|
|
||
|
|
best_child = max(population, key=calculate_fitness)
|
||
|
|
|
||
|
|
bsf = calculate_fitness(best_child)
|
||
|
|
print("bsf: ", bsf)
|
||
|
|
|
||
|
|
return best_child
|