longchute

about

Toy Genetic Algorithm

27 Dec 2013

This implements a toy genetic algorithm which optimizes a set of parameters for a fitness function (simulate) which produces outputs to be score'd. The simulation is mocked up with a set of random values for sensor outputs. The number of parameters is optimized to be a minimum. If this were being used in tandem with a simulation, the simulate function would use parameters as input (potentially components in a circuit representing an Amplifier) to determine output characteristics. Each generation is 100 members. The first generation is randomly generated. All subsequent generations consist of the top 10 members of the previous generation, 10 mutate'd copies of the top 10 (1/10 mutation chance per parameter), and 80 randomly generated new members. No recombination is performed. This implementation stops upon reaching a score greater than 5 (6 is optimum).

Usage: ./amp.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#!/usr/bin/env python

import random

#   Heat, input power, output power, # of components
the_weights = [-0.4, -0.3, 0.6, -0.1]

class Amplifier(object):
    parameters  = None
    result      = None

    def __init__(self, parameters=None):
        self.parameters = parameters if parameters else [random.randint(0, 100) for i in range(0, random.randint(0, 20))] 

    #   Random correlation between parameters and simulation scores
    def simulate(self):
        self.result = self.result if self.result else [random.randint(0, 10), random.randint(0, 10), random.randint(0, 10), len(self.parameters)]
        return self.result

    def score(self):
        return sum([a_weight * a_score for (a_weight, a_score) in zip(the_weights, self.simulate())])

    def mutate(self):
        return Amplifier(parameters=[a_parameter if (random.randint(0, 10) > 1) else random.randint(0, 100) for a_parameter in self.parameters])

the_population  = [Amplifier() for i in range(0, 100)]
the_generation  = 0

while True:
    the_scores = []

    for a_member in the_population:
        the_scores.append((a_member.score(), a_member.simulate(), a_member))

    the_scores.sort(key=lambda x: -x[0])
    top_score = the_scores[0]

    print "Top Score (generation %d): score: %s, simulated: %s, obj: %s" % (the_generation, top_score[0], top_score[1], top_score[2].parameters)
    the_generation += 1

    if top_score[0] > 5:
        break

    mutated_scores = [a_score[2].mutate() for a_score in the_scores[:10]]

    #   Keep the first 10, mutate the first 10, and generate 80 new ones
    the_population = [a_score[2] for a_score in the_scores[:10]]           + \
                     [a_score[2].mutate() for a_score in the_scores[:10]]  + \
                     [Amplifier() for i in range(0, 80)]