-
Notifications
You must be signed in to change notification settings - Fork 0
/
gptgeneticsalgo.py
79 lines (72 loc) · 2.89 KB
/
gptgeneticsalgo.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import random
import numpy as np
# Define the size of the chessboard (8x8 for the 8-queens problem)
size = 8
def fitness_fn(board):
# Calculate the fitness of an individual board (lower fitness is better)
# Fitness is the number of attacking_pairs (queens attacking each other)
attacking_pairs = 0
for i in range(size):
for j in range(i + 1, size):
if board[i] == board[j] or abs(board[i] - board[j]) == j - i:
attacking_pairs += 1
return attacking_pairs
def random_selection(population, fitness_fn):
#Select a random individual from the population based on fitness
weighted_population = [(ind, 1.0 / (fitness_fn(ind) + 1)) for ind in population]
total_weight = sum(weight for ind, weight in weighted_population)
rand_num = random.uniform(0, total_weight)
cumulative_weight = 0
for ind, weight in weighted_population:
cumulative_weight += weight
if cumulative_weight > rand_num:
return ind
def reproduce(x, y):
# Create a child by combining the genes of two parents (queens positions)
n = len(x)
crossover_point = random.randint(1, n - 1)
child = x[:crossover_point] + y[crossover_point:]
return child
def mutate(child):
# Mutate a child by randomly changing the position of one queen
index_to_mutate = random.randint(0, size - 1)
new_position = random.randint(0, size - 1)
child[index_to_mutate] = new_position
return child
def genetic_algorithm(population, fitness_fn):
n=0
while True:
new_population = []
for i in range(len(population)):
x = random_selection(population, fitness_fn)
y = random_selection(population, fitness_fn)
child = reproduce(x, y)
if random.random() < 0.1: # Small random probability for mutation
child = mutate(child)
new_population.append(child)
population = new_population
best_individual = min(population, key=fitness_fn)
n=n+1
if fitness_fn(best_individual) == 0: # Solution found
print(fitness_fn(best_individual))
return best_individual
elif n==200:
print("Time-out!")
print("Following is the best solution found --->")
print(fitness_fn(best_individual))
return best_individual
# Initialize the population with 100 random queen positions
initial_population = [[random.randint(0, size - 1) for i in range(size)] for j in range(100)]
# Solve the 8-queens problem using the genetic algorithm
solution = genetic_algorithm(initial_population, fitness_fn)
print("Solution:", solution)
state=[]
for i in range(8):
row=[]
row.extend([0,0,0,0,0,0,0,0])
state.append(row)
for k in range(8):
if solution[k]==i:
state[i][k]=1
for ele in state:
print(ele)