Simple genetic Algorithm for a list of floating point numbers

Question

I am currently trying to make a genetic algorithm to match a list of floating point numbers to another list of floating point numbers (I know this is sort of "pointless" because I already have the data, but I just want to have the ability to do this before trying to tackle more complex genetic algorithm problems). I have the following code written in Python.

from random import random
ofInterest = [
                5.76260089714,
                7.87666520017,
                9.53163269149,
                9.72801578613,
                5.20002737716,
                0.50133290228,
                8.58820041647,
                9.65056792475,
                3.07043110493,
                1.13232332178
              ]

print(ofInterest)

fits = []

for i in range(100):
    fits.append([])
    for j in range(10):
        fits[i].append(random()*10)

fitness = []
for i in range(100):
    fitness.append(100000000)


def makeFitnessList():
    for i in range(100):
        fitValue = 0
        for j in range(10):
            fitValue += (fits[i][j] - ofInterest[j])**2
        fitness[i] = fitValue

topTenFitness = []

for i in range(10):
    topTenFitness.append(10000000000000)
print(topTenFitness)

def sortByFitness():
    makeFitnessList()
    temp = []
    count = 0
    while len(temp) < 10:
        k = 100000000000000000000000000
        index = -1
        for i in range(len(fitness)):
            if k > fitness[i]:
                k = fitness[i]
                index = i  
        temp += [index]
        topTenFitness[count] = fitness[index]
        print(fitness[index])
        fitness[index] = 1000000000000
        count += 1
    temp2 = fits
    for i in range(10):
        fits[i] = temp2[temp[i]]

#sortByFitness()
#print(fitness[0])
#print(fits[0])

def cross(rate):
    for i in range(10,100):
        parent1Place = int(random()*10.01)
        if (i*random()) > rate:
            parent2Place = int(random()*10.01)
            crossPoint = int(random()*10.01)
            for i in range(crossPoint):
                tempOne = fits[parent1Place][i]
                tempTwo = fits[parent2Place][i]
                fits[parent1Place][i] = tempOne
                fits[parent2Place][i] = tempTwo
        else:
            fits[i] = fits[parent1Place]



def mutate(rate):
    for i in range(10,100):
        for gene in range(10):
            if random() < rate:
                fits[i][gene] = random()*10

for i in range(10):
    makeFitnessList()
    sortByFitness()
    print("")
    cross(.6)
    mutate(.4)

sortByFitness()
print(fits[0])

This program runs, but there is no gain in fitness:

158.551483202
89.0049309654
150.062479048
223.447907282
162.41893599
105.727706028
169.756843723
77.0767420744
122.905567656
144.328292984
113.405444904
132.748651766
144.739705127
155.959141194
151.507885923
86.3246751862
etc...

Answer 1

Here are some things that might contribute to the bad result:

1. Your mutation rate is way too high. 40% per gene means that with 10 genes each individual will have on average 4 changes. Actually you should choose the mutation rate such that for each generation only few mutations are introduced in the whole population.

2. Your cross function exchanges genes between the chosen parents, instead of leaving the parents unchanged and copying fractions of the genes of both parents to a newly created child.

3. If you mutate a gene you substitute it by a new independent random variable. That is ineffective as it makes the landscape on which the algorithm operates very rough. You get a smoother landscape and a better fit if you only add small random variables to the original value, for example in the range [-0.1, 0.1].

4. Instead of choosing a crosspoint for the genome it would be more effective to choose the genes completely randomly between the parents, because the order of genes has no meaning in your model.

5. You are not waiting long enough, 10 generations will not bring you far.

6. As far as I can see you are not measuring the fitness gain correctly. You should print out the average fitness of the population (maybe the best fitness or average of the top10).

Answer 2

If you use numpy all your computations are more easy, and you should try to be more pythonic:

import numpy as np

ofInterest = np.array([
                5.76260089714,
                7.87666520017,
                9.53163269149,
                9.72801578613,
                5.20002737716,
                0.50133290228,
                8.58820041647,
                9.65056792475,
                3.07043110493,
                1.13232332178
              ])
print(ofInterest)

fits = np.random.random((100,10)) * 10

def sortByFitness():
    global fits
    fitness = np.sum((fits - ofInterest)**2,axis=1)
    fits = fits[fitness.argsort()]

def cross(rate):
    for i in range(10,100):
        parents = fits[np.random.random_integers(0,9,2)]
        if (i*np.random.random()) > rate:
            crossPoint = np.random.random_integers(0,10)
            fits[i] = np.hstack((parents[0,:crossPoint],parents[1,crossPoint:]))
        else:
            fits[i] = parents[0]

def mutate(rate):
    for i in range(10,100):
        for gene in range(10):
            if np.random.random() < rate:
                fits[i][gene] = np.random.random()*10

for i in range(100):
    sortByFitness()
    cross(.6)
    mutate(.4)

print(fits[0])

Answer 3

just cause genetic algorithms are fun ... :)

import random
target_list = [1,2,3,4,5,6,7,8,9,10]
size_of_individual = len(target_list)
size_of_population = 100
n_generations = 10000

def score_fitness(individual):
    return sum((val-target)**2 for val,target in zip(individual,target_list))

def create_individual():
    return [random.random()*10 for _ in range(size_of_individual)]

def crossover(individual1,individual2):
    return [val1 if random.random() < 0.5 else val2 for val1,val2 in zip(individual1,individual2)]

def mutate(individual,mutation_chance=0.1,mutation_size = 0.1):
    def get_mutation(val):
         return val if random.random()>mutation_chance else val + [-mutation_size,mutation_size][random.random()<0.5]
    return [get_mutation(val) for val in individual]

def selection_step(sorted_old_population):
    def select_one():
        while True:
            candidate_idx = random.randint(0,len(sorted_old_population)-1)
            if random.randint(0,len(sorted_old_population))>= candidate_idx:
                return sorted_old_population[candidate_idx]
    selections = [select_one(),select_one()]
    while selections[1] == selections[0]:
        selections[1] = select_one()
    return selections

def create_new_population(old_population,elitism=0):
    sorted_population = sorted(old_population,key= score_fitness)
    print "BEST OLD:",sorted_population[0],score_fitness(sorted_population[0])
    print "AVG OLD:", sum(score_fitness(i) for i in sorted_population)
    new_population = sorted_population[:elitism]
    while len(new_population) < size_of_population:
          new_population.append(mutate(crossover(*selection_step(sorted_population))))
    return new_population[:size_of_population]


population = [create_individual() for _ in range(size_of_population)]
for i in range(n_generations):
    population = create_new_population(population,5)

keep in mind this is a poor problem for genetic algorithms, and also that there are lots and lots of room for improvements (IE get rid of elitism all together)