Genetic Algorithms: Evolution - Part 3

Max Clark
Mar 16, 2017
5 min read

The third and final part in the genetic algorithm series will explain the coding of the evolution behind the genetic algorithm shown in parts 1 and 2. You will need the code and explanations from part 1 and part 2.

In order get the angles of the bird's wings given the bird's DNA and the time, we need to create a function. The Bird's DNA will be 'flap'. The first line reduces time ('frameCount') so that it is always within the constraints of the DNA's time period, 'flap[1]'. The next line finds the time between two consecutive angle points in the DNA and calls it 'gap'. The variable 'sec' is the current section number where sections are periods between angle points, for example, for DNA with angle points of [10,20,30,40], section 0 would be between 10 and 20 with 3 sections in total. The final angle is given by the variable 'y' and is calculated as if the transition between two angle points is linear.

def get_ang(flap, time): time -= int(time/flap[1])*flap[1] gap = flap[1]/flap[0] sec = int(time/gap) y = (flap[sec+3]-flap[sec+2])*(time-sec*gap)/gap + flap[sec+2] return y

This next function generates DNA. There are two methods of doing so: creating one completely randomly and asexually reproducing from previous DNA. The variable 'breed' will determine this where being set to false means random DNA will be produced. The variable 'flap' is the parent DNA and is only used if 'breed' is true. Remember how DNA is an array made of two arrays? Well 'r1' and 'r2' are the first and second parts respectively. Starting with when 'breed' is false, we give the DNA parts the number of angle points and the time period. Then it creates random values for the angle points and repeats the first angle point. When 'breed' is true, everything is the same except that the values are random variations from the parent DNA.

def create_flap(flap, breed): if breed: flap1,flap2 = flap[0],flap[1]

timed = ri(-10,10) r1 = [abs(int(ri(-6,6)/5)+flap1[0]-1)+1, abs(timed+int(ri(-6,6)/5)+flap1[1]-20)+20] r2 = [abs(int(ri(-6,6)/5)+flap2[0]-1)+1, abs(timed+int(ri(-6,6)/5)+flap2[1]-20)+20] for i in range(r1[0]): r1.append(abs(ri(-10,10)+flap1[i+2])) r1.append(r1[2]) for i in range(r2[0]): r2.append(abs(ri(-10,10)+flap2[i+2])) r2.append(r2[2]) else: r1 = [ri(2,10), ri(30,180)] #[number, time period] r2 = [ri(2,10), ri(30,180)]

for i in range(r1[0]): r1.append(ri(0,180)) r1.append(r1[2]) for i in range(r2[0]): r2.append(ri(0,180)) r2.append(r2[2]) return r1,r2

We will need some new variables. The maximum height a bird has achieved is stored as 'max_y' and the corresponding DNA for that height is stored as 'max_flap'. Next, 'b_flap' is the DNA which is asexually reproducing and 'r1, r2' make up the DNA which is currently trying to fly. If you want to try out some specific DNA, set 'r1' and 'r2' to the DNA and the first bird will have that DNA. The variables 't1' and 't2' are the angles shown in part 2 of the series. Then points 3 and 2 are the elbow and hand coordinates respectively; 'ppx,ppy' is the coordinates of the body of the bird in the previous frame. Finally, 'gen' and 'org' are the generation and organism numbers with 10 organisms per generation.

#Variables

max_y = ySize max_flap = [[],[]] b_flap = create_flap(max_flap, False)

r1,r2 = create_flap(b_flap, True)

t1 = get_ang(r1, 0) t2 = get_ang(r2, 0)

px3,py3 = get_end(length,t1,px1,py1) px2,py2 = get_end(length,180-t2+t1,px3,py3) ppx,ppy = px2,py2 #Previous values

gen = 1 org = 0

Now we move to within the main while loop. We use our function to get the current angles from the DNA. This belongs right after the line 'screen.fill([255,255,255])'.

t1 = -get_ang(r1, frameCount) t2 = get_ang(r2, frameCount)

From the code from part 2, this next bit belongs inside the first if statement in the main loop (if frameCount > 1:). It should be put as the last indented code in the if statement. This checks if the bird's height has reached a new maximum and sets the current winning variables accordingly. if py1 < max_y: max_y = py1 max_flap[0], max_flap[1] = r1, r2

After the if statement (if frameCount > 1:), there is a line setting 'ppy' to the current y value. Straight after this line comes the next code. This code is run when the bird's time (300 frames) is up. It creates the next organism. If the organism number is 8 or 9 or if it's the first generation, random DNA is used. The body coordinates are set to the original point. Now we print the information about the generation and organism numbers and the most successful bird so far. If all organisms in the generation have passed, then a new generation is created and the breeding DNA is replaced by the new maximum.

if frameCount >= 300: org += 1 if gen == 1 or org >= 8: r1,r2 = create_flap(b_flap, False) else: r1,r2 = create_flap(b_flap, True)

px1, py1 = ox, oy

print(gen,org,"max:",ySize-max_y, max_flap) frameCount = 0

if org >= 9: gen += 1 org = 0 b_flap = max_flap

Parts 2 and 3 in the series have now covered all of the code used in the script and the program is now complete. If you want to speed through many generations, increase the frame rate cap in the penultimate line. Here is all the code:

import pygame import time import math from math import radians, sin, cos import random from random import randint as ri

pygame.init()

xSize, ySize = 600, 900 screen = pygame.display.set_mode((xSize, ySize)) pygame.display.set_caption("Learn to Fly")

def get_end(length,angle,px0,py0): py = length*cos(radians(angle)) + py0 px = length*sin(radians(angle)) + px0 return int(px),int(py)

def get_ang(flap, time): time -= int(time/flap[1])*flap[1] gap = flap[1]/flap[0] sec = int(time/gap) y = (flap[sec+3]-flap[sec+2])*(time-sec*gap)/gap + flap[sec+2] return y

def create_flap(flap, breed): if breed: flap1,flap2 = flap[0],flap[1]

for i in range(r1[0]): r1.append(ri(0,180)) r1.append(r1[2]) for i in range(r2[0]): r2.append(ri(0,180)) r2.append(r2[2]) return r1,r2 #Variables

length = 100 ox, oy = 300,ySize-200 px1, py1 = ox, oy px2, py2 = 500,200 px3, py3 = 0,0

max_y = ySize max_flap = [[],[]] b_flap = create_flap(max_flap, False) r1,r2 = create_flap(b_flap, True)

t1 = get_ang(r1, 0) t2 = get_ang(r2, 0) px3,py3 = get_end(length,t1,px1,py1) px2,py2 = get_end(length,180-t2+t1,px3,py3) ppx,ppy = px2,py2 #Previous values

gen = 1 org = 0

#----------------------Main Loop----------------------# clock = pygame.time.Clock() frameCount = 0 mouseHold = False done = False while not done: frameCount += 1 screen.fill([255,255,255])

t1 = -get_ang(r1, frameCount) t2 = get_ang(r2, frameCount) px3,py3 = get_end(length,t1,px1,py1) px2,py2 = get_end(length,180-t2+t1,px3,py3)

if frameCount > 2: diff = (py2 - ppy)*(px2 - px1)/200 if py1 < ySize and py2 < ySize and py3 < ySize: py1 += diff + 1 else: py1 += diff - max(py1,py2,py3) + ySize if py1 < max_y: max_y = py1 max_flap[0], max_flap[1] = r1, r2 ppy = py2

if frameCount >= 300: org += 1

if gen == 1 or org >= 8: r1,r2 = create_flap(b_flap, False) else: r1,r2 = create_flap(b_flap, True)

px1, py1 = ox, oy print(gen,org,"max:",ySize-max_y, max_flap) frameCount = 0

if org >= 9: gen += 1 org = 0 b_flap = max_flap #Draw pygame.draw.line(screen, [0,0,0], (px1,int(py1)), (px3,py3),1) pygame.draw.line(screen, [0,0,0], (px3,py3), (px2,py2),1) pygame.draw.circle(screen, [0,0,255], (px3,py3), 4) pygame.draw.circle(screen, [255,0,0], (px2,py2), 4)

pygame.draw.line(screen, [0,0,0], (2*ox-px1,int(py1)), (2*ox-px3,py3),1) pygame.draw.line(screen, [0,0,0], (2*ox-px3,py3), (2*ox-px2,py2),1) pygame.draw.circle(screen, [0,0,255], (2*ox-px3,py3), 4) pygame.draw.circle(screen, [255,0,0], (2*ox-px1,int(py1)), 4) pygame.draw.circle(screen, [255,0,0], (2*ox-px2,py2), 4)