import random
# Fitness function: Counts non-attacking pairs of queens
def fitness(state):
non_attacking = 28 # Total possible pairs in 8-queens
for i in range(len(state)):
for j in range(i + 1, len(state)):
if abs(state[i] - state[j]) == abs(i - j): # Same diagonal
non_attacking -= 1
return non_attacking
# Generate a random population
def generate_population(size):
return [random.sample(range(8), 8) for _ in range(size)]
# Select two parents based on fitness
def select_parents(population):
weights = [fitness(ind) for ind in population]
return random.choices(population, weights=weights, k=2)
# Perform crossover between two parents
def crossover(parent1, parent2):
point = random.randint(0, 7)
child = parent1[:point] + parent2[point:]
return child
# Mutate a child by changing one random position
def mutate(child):
index = random.randint(0, 7)
value = random.randint(0, 7)
child[index] = value
return child
# Genetic Algorithm for 8-Queens
def genetic_algorithm(pop_size=100, generations=1000):
population = generate_population(pop_size)
for generation in range(generations):
new_population = []
for _ in range(pop_size):
parent1, parent2 = select_parents(population)
child = crossover(parent1, parent2)
if random.random() < 0.1: # Mutation chance
child = mutate(child)
new_population.append(child)
population = new_population
best_individual = max(population, key=fitness)
if fitness(best_individual) == 28: # Solution found
return best_individual, generation
return None, generations # No solution found
# Example usage
if __name__ == "__main__":
solution, gen = genetic_algorithm()
if solution:
print(f"Solution found in generation {gen}: {solution}")
else:
print("No solution found.")
Comments
Post a Comment