(2021-MC-43)
(Ahad fayyaz)
A genetic algorithm is used to solve complicated problems with greater number of variables and possible outcomes. The combinations of different solutions are passed through the Darwinian based algorithm to find the best solutions. The poorer solutions are then replaced with the offspring of good solution
This code creates a 10x10 maze with 500 randomly generated pops. The code then loops through the maze, generating a new pop at each intersection. The generated pops are inserted into the maze at the appropriate location, based on their position and size.
The generateranpop() function creates a random sequence of bits that can be used to generate any number from 0–9. This function is used in the next section to create an agent that can navigate the maze and find food. The code will generate a random list of integers between 0 and 9, where each number in the list corresponds to a different location on the maze. The generated list is then inserted into the maze at those locations. Finally, the last two numbers in the generated list are used to determine where on the maze the agent should start. The code creates an array of points. The first column is the character and the second column is the row number. .
The code creates an array of points, where each point corresponds to the position of a character in a text file. The first column of the points array corresponds to the character’s ordinal position (starting at 0), while the second column corresponds to the character’s index within that row. . Finally, it appends these coordinates together into a single string and returns it.
The code first imports the necessary modules. It then defines two functions, getFitness and getFitnessArr_z. The first function takes a character and a maze map as input, and returns the fitness of that character in the maze map.
The second function getFitnessArr_z. takes a list of pop objects (each representing an individual player), and returns the fitness of those players in the maze map.
The next section of code is where the real work happens. It defines three variables: infeasible_steps, map_path, and maze_map. infeasible_steps is initially set to 0. This variable will track how many steps are required to reach the exit from the maze map with 100% success. Next, the code iterates over each coordinate in map_path using for looping syntax. Once all coordinates have been checked, the code uses if statement syntax to determine whether or not any obstacles exist The code first imports the necessary modules.
The getMap() function is used to obtain a path representation of the maze map.
The getFitness() function is then called with two arguments, the character and maze map. The fitness value is calculated by subtracting the number of obstacles in the path from 99. The getFitnessArr_z() function is then used to return an array of fitness values for each pop in the maze. The code begins by creating a list of 25 parents. These are the individuals that will be used to create new offspring from the original population of pop. Next, the code creates a maze map. This is simply a data structure that stores information about where each individual in the population can move. The maze map is used to help determine which parents should be chosen for crossover.
The code uses selection_parents() to select 25 parents from the original population based on their fitness values. The fitness values are calculated using the algorithm described earlier in this chapter and are based on how well each parent fares when it tries to navigate the maze map.
Finally, crossover() is used to combine DNA from these selected parents and produce new offspring. The code first creates a list of 25 parents, which are the individuals that the crossover algorithm will use to create new offspring. The fitness_arr list contains the fitness scores of each parent. Next, the crossover algorithm is used to create new offspring by mating two parents from the list of parents.
After cross over Mutation is performed to get good fitness value.
After all solution is displayed with the help of using maze map variable .
GIF
from pyamaze import maze, agent
import numpy as npCOLS = 10
ROWS = 10
pop_size = 500
def generateranpop():
dir_bits = np.random.randint(2, size=(pop_size, 1))
pop = np.random.randint(1, ROWS, size=(pop_size, COLS - 2))
pop = np.insert(pop, 0, 1, axis=1)
pop = np.insert(pop, COLS - 1, ROWS, axis=1)
pop = np.append(dir_bits, pop, axis=1)
return pop
def coordinates(chr):
points = []
for col in range(COLS, 1, -1):
row_direction = -1 if chr[col] >= chr[col - 1] else 1
if chr[0] == 1:
points.append((chr[col], col))
for row in range(chr[col], chr[col - 1], row_direction):
points.append((row, col - 1))
else:
for row in range(chr[col], chr[col - 1], row_direction):
points.append((row, col))
points.append((chr[col - 1], col))
points.append((1, 1))
return points
def Direction(points):
map = {}
for i in range(len(points) - 1):
if points[i][0] > points[i + 1][0]:
dir = 'N'
elif points[i][0] < points[i + 1][0]:
dir = 'S'
elif points[i][1] > points[i + 1][1]:
dir = 'W'
elif points[i][1] < points[i + 1][1]:
dir = 'E'
map[points[i]] = dir
return map
def getMap(chr):
return Direction(coordinates(chr))
def obstacles(map_path, maze_map):
infeasible_steps = 0
for coord, dir in map_path.items():
if maze_map[coord][dir] == 0:
infeasible_steps += 1
return infeasible_steps
def getFitness(chr, maze_map):
map_path = getMap(chr)
return 99 - obstacles(map_path, maze_map)def getFitnessArr_z(pop, maze_map):
return [getFitness(pop[i], maze_map) for i in range(pop_size)]
def selection_parents(pop, fitness_arr, num_parents=25):
sum_fitness = np.sum(fitness_arr)
fit = [sum(fitness_arr[:i+1]) for i in range(len(fitness_arr))]
pointer_distance = sum_fitness / num_parents
start = np.random.uniform(0, pointer_distance)
parents = np.empty((num_parents, COLS + 1), dtype=int)
for i in range(num_parents):
position = start + i * pointer_distance
j = 0
while fit[j] < position:
j += 1
parents[i] = pop[j]
return parents
def crossover(pop, fitness_arr, maze_map):
parents = selection_parents(pop, fitness_arr) def offSpring():
cut_point = np.random.randint(2, COLS - 1)
parent_one = parents[np.random.randint(len(parents))]
parent_two = parents[np.random.randint(len(parents))]
for i in range(0, cut_point):
parent_one[i], parent_two[i] = parent_two[i], parent_one[i]
return parent_one, parent_two
new_pop = np.empty((pop_size, COLS + 1), dtype=int)
for i in range(0, len(pop), 2):
off_springs = offSpring()
new_pop[i] = off_springs[0]
new_pop[i + 1] = off_springs[1]
return new_pop
def Mutation(pop, Mutation_rate=0.5):
for i in range(len(pop)):
if np.random.random() < Mutation_rate:
pop[i][np.random.randint(2, COLS)] = np.random.randint(1, ROWS)
if np.random.random() < 0.1:
pop[i][0] = 1 - pop[i][0]
return pop
def solution(maze_map):
pop = generateranpop()
for gen in range(1000):
fitness_arr = getFitnessArr_z(pop, maze_map)
if (gen==999):
print('Solution not found') if max(fitness_arr) == 99:
print(f"solution found in {gen} th generation")
sol = list(fitness_arr)
idx = sol.index(max(sol))
print(pop[idx])
return coordinates(pop[idx])
pop = crossover(pop, fitness_arr, maze_map)
pop = Mutation(pop)m = maze(ROWS, COLS)
m.CreateMaze(loopPercent=100, pattern='v')
a = agent(m, footprints=True)
path = solution(m.maze_map)
m.tracePath({a: path})
m.run()