#### Genetic Algorithm – car trajectory

I’m trying to implement Genetic Algorithm to get from point A to point B by car in python. So it’s more like a proof of concept.

``````import sys
import math
import random

POPULATION_SIZE=10
GENE_LENGTH=10
MUTATION_RATE=.1
ELITISM=.1
ELITISM_IDX=int (ELITISM*POPULATION_SIZE)
GENERATIONS=20
MAX_ANGLE_CHANGE=18
FRICTION=.85
WIDTH=16000
HEIGHT=9000
MIN_FITNESS=0
MAX_FITNESS=100000

def distance(ax, ay, bx, by):
return math.sqrt(pow(ax-bx,2)+pow(ay-by,2))

def validate_angle(cur_angle,desired_angle):
angle_diff=(desired_angle-cur_angle+360)%360
if angle_diff>180:
angle_diff-=360
angle_change=max(-MAX_ANGLE_CHANGE,min(angle_diff,MAX_ANGLE_CHANGE))
new_angle=(cur_angle+angle_change)%360
return int(new_angle)

def validate_position(x,y,vx,vy,angle,thrust):
x+=vx; y+=vy
vx=int(vx*FRICTION); vy=int(vy*FRICTION)
return x,y,vx,vy

def generate_individual():
chromosome=[]
x,y,vx,vy,angle=init_x,init_y,init_vx,init_vy,init_angle
for _ in range(GENE_LENGTH):
desired_angle=angle+random.uniform(-MAX_ANGLE_CHANGE,MAX_ANGLE_CHANGE)
angle=validate_angle(angle,desired_angle)
thrust=random.randint(0,200)
x,y,vx,vy=validate_position(x,y,vx,vy,angle,thrust)
chromosome.append((int(angle),int(thrust)))
return chromosome

def generate_population():
return [generate_individual() for _ in range(POPULATION_SIZE)]

def simulate(chromosome):
x,y,vx,vy,angle=init_x,init_y,init_vx,init_vy,init_angle
for gene in chromosome:
desired_angle,thrust=gene

angle=validate_angle(angle,desired_angle)
x,y,vx,vy=validate_position(x,y,vx,vy,angle,thrust)

if distance(x,y,*checkpoint)<=600:
solved=True

return x,y,vx,vy,angle

def fitness(chromosome):
global solved
x,y,vx,vy,angle=simulate(chromosome)
if y>HEIGHT or y<0 or x>WIDTH or x<0:
return MIN_FITNESS
if solved:
print("Solution found !",file=sys.stderr)
return MAX_FITNESS
else:
fitness=-distance(x,y,*checkpoint)
return fitness

def selection(population):
population.sort(key=lambda chromosome: fitness(chromosome), reverse=True)
return population[:ELITISM_IDX],population[ELITISM_IDX:]

def crossover(parent1, parent2, counter):
child=[]
for i in range(GENE_LENGTH):
crossover_point=random.random()
angleP1=parent1[i][0]; angleP2=parent2[i][0]
thrustP1=parent1[i][1]; thrustP2=parent2[i][1]

angle=crossover_point*angleP1+(1-crossover_point)*angleP2
thrust=crossover_point*thrustP1+(1-crossover_point)*thrustP2
if not counter%2:
angle=(1-crossover_point)*angleP1+crossover_point*angleP2
thrust=(1-crossover_point)*thrustP1+crossover_point*thrustP2
if i==0:
angle=validate_angle(init_angle,angle)
else:
angle=validate_angle(child[-1][0],angle)
child.append((int(angle),int(thrust)))
return child

def mutate(chromosome):
for i in range(GENE_LENGTH):
mutate_point=random.random()
if mutate_point < MUTATION_RATE:
angle=validate_angle(chromosome[i][0],chromosome[i][0]+random.uniform(-MAX_ANGLE_CHANGE,MAX_ANGLE_CHANGE))
thrust=random.randint(0,200)
chromosome[i]=(int(angle),int(thrust))
return chromosome

def roulette_wheel_selection(probabilities):
cumulative_probabilities=[sum(probabilities[:i+1]) for i in range(len(probabilities))]
r=random.random()
for i,cumulative_probability in enumerate(cumulative_probabilities):
if r<cumulative_probability:
return i

def is_valid_chromosome(chromosome):
for gene in chromosome:
if gene[1]>HEIGHT or gene[1]<0 or gene[0]>WIDTH or gene[0]<0:
return False
return True

def calc_fitness_probabilities(population):
fitnesses=[fitness(chromosome) for chromosome in population];
min_fitness=min(fitnesses)
normalized_fitnesses=[fitness-min_fitness+1 for fitness in fitnesses];
total_fitness=sum(normalized_fitnesses)
fitness_probabilities=[fitness/total_fitness for fitness in normalized_fitnesses]
return fitness_probabilities

def print_population(population):
for chromosome in population:
print(chromosome,file=sys.stderr)
print(f"Fitness {fitness(chromosome)}",file=sys.stderr)
print("",file=sys.stderr)
print("",file=sys.stderr)

solved=False
init_y=init_x=init_vy=init_vx=init_angle=0
checkpoint=(2757, 4659)
prev=0
init_x, init_y, init_vx, init_vy, init_angle = 10353, 1986, 0, 0, 161
population=generate_population(); #print_population(population)
generation=1

while not solved:
print(f"Generation {generation}",file=sys.stderr)
elites_population,commons_population=selection(population)

fitness_probabilities=calc_fitness_probabilities(commons_population);
counter=1
while len(elites_population)<POPULATION_SIZE:
parent1=roulette_wheel_selection(fitness_probabilities);
while not is_valid_chromosome(commons_population[parent1]): parent1=roulette_wheel_selection(fitness_probabilities)
parent2=parent1
while parent1!=parent2 and not is_valid_chromosome(commons_population[parent2]): parent2=roulette_wheel_selection(fitness_probabilities)
child=crossover(commons_population[parent1],commons_population[parent2],counter)
child=mutate(child)
if child not in elites_population:
elites_population.append(child)
counter+=1
population=elites_population
population.sort(key=lambda chromosome: fitness(chromosome), reverse=True)
print_population(population)
best_chromosome=max(population,key=fitness)
best_fitness=fitness(best_chromosome)
print(f"nBest fitness: {best_fitness}n",file=sys.stderr)
generation+=1

``````

I’m trying to find the correct set of genes for that. Gene consists of 2 values: thrust and angle.

Unfortunately I either get stuck with the same genes, even though I filter out same pairs. Or my car get’s out of the map.

I’m sure I’m missing something basic here, it’s just I can’t pinpoint what exactly.

New contributor

5tack is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

Theme wordpress giá rẻ Theme wordpress giá rẻ Thiết kế website