Evolutionary Genetic Algorithm for Path Optimization in Python

This is an optimizer which tries to optimize a path on a virtual terrain in regards to energy consumption. It works by creating simple creatures which contain a brain which is modeled as a very simple neural network. The training process works by generating a population of creatures which we get by randomly modifying and combining the parameters inside the neural networks of the previous generation.

Problem statement

We have:

terrain
starting point
target point

Goal: find optimal path in regards to energy consumption

Approach

Basic Idea:

make creatures
let them walk
evaluate their performance
"kill" the worst ones
generate new population (randomly, mating or mutation)
iterate until convergence

Which classes do we need?

World
Creature
Brain

The world contains a certain amount of creatures which all have their own individual brain.

World

The world contains:

terrain (simple perlin noise as a height map)
creatures

For each iteration the world…

creates new creatures by breeding, mutating and killing the previous population
calculates the trajectory each creature makes over 1000+ steps

There are a couple of rules:

a creature dies when it reaches the border of the terrain
each step has to be a certain size
for each step a creature loses / gains some energy (uphill loses, downhill gains)
the final score is a weighted sum of the energy and 1/distance_to_goal

Creature

A creature contains:

id
starting location
target location
current location
trajectory
energy score
brain

-> while walking the brain decides which step to take according to given inputs

Brain Inputs:

current energy current height height difference to last step x,y distances to target the heights of 4 points around the creature how many steps it already took

Brain

Implementation:

input tensor
n x m matrix for the connections between two layers
where n,m are the amount of neurons which are connected
non linear functions after each layer (relu)
output tensor [x,y]

to calculate the next step:

matrix multiplication with input
use non linear function to truncate the result
do these steps for each hidden layer
get output

thomacdebabo / evolgenalg Goto Github PK

evolgenalg's Introduction