Links

repo: git

Motivation

I was just finishing up some coursework on Travelling Salesman problems and fired up Spore (truly an absolute gem of a game). In the game, after you conquer a planet, it is in your best interest to re-do the infrastructure of the cities on its surface since the A.I. never really optimises its output that much - this process can be quite tedious and is usually costly.

Fiddling with the layouts until I could find something that was pretty much the best in terms of production output (this usually also meant quite expensive) got pretty boring really quickly - I am not about that kind of life. So I did what any sane man would, and decided to find the most optimal colony layouts using Genetic Algorithms.

Note: There already were plenty of blog posts on this, stating the best city layouts - but I didn't believe them ;)

How does it work?

The script uses a standard genetic algorithm set up.

Solution Representation

We first decide on the representation of a solution, or a Chromosome - it needs to be simple enough and robust enough to still be a viable solution after being spliced, broken up and re-arranged (well it depends on the details of your algorithm, but most often this applies) - the most common are:

  • Binary string. e.g.: say that we are looking to find 2 positive integers smaller than 16 which divided by each other equal to 10, call them A and B. Then A/B = 10, we could represent a possible solution to this by encoding A and B substitutions as 4 bit binary numbers (range or 0 through 15) and flattening the digits to a string. A=2 and B=5 would be represented as: "00100101". Is this a good representation for our toy problem? Well, does it cover all possible inputs ? Check. Does it allow inputs outside of our constraint? Check... oh... So no it's not the best, as you can see, we are looking for integers in the range [1,15] and our representation gives us a range of [0,15]! This is of course only if we mindlessly apply standard operators - if we were to "trim" our space by forbidding certain operations, then our range is exactly what we need.
  • Just a string. Continuing with the previous example, we could try to represent our range of inputs using a simple string containing both the numbers separated by a comma, i.e. "2,5" could be a solution, the big difference between this and binary representation, is that mutating this one, would specifically require your mutation function to know the actual range of numbers, in the binary representation this was an option here it's a requirement.

In the case of Spore, I turned each layout I cared about (there were probably under 15 total in the game) into a graph and gave each node a number - by simply looking at the layout in the game and going clockwise, think sonar beeps.

Now each building does something else, there are 3 main building types which we care about:

  • Houses - these don't do anything until other buildings are linked directly to houses.
  • Factories - these produce spice, the main produce of the game, the amount of spice depends on the way the factory is connected, each link to a house produces spice, specifically SPICE = PLANET_SPICE_CONSTANT * LINKS_TO_HOUSES. There is also a flat out -1 happiness penalty for each factory
  • Entertainment buildings - work the same way as factories but instead of spice produce happiness points, happiness is important if you don't want your colonies to keep rioting - there is a golden value above which colonies won't riot and this we don't need to produce any more than that (We don't need to concern ourselves with our populations views, since there's no politics in Spore ;) ). Each of these gives a flat out bonus of +1 to happiness for each building

Connecting a factory to an entertainment building produces negative happiness, equivalent to -1 * the number of links.

So the way my solution representation ended up as is:

# this is the structure which holds our genes
class Chromosome:
    def __init__(self,genes):
        self.fitness = 0
        self.genes = genes

    def __str__(self):
        return "fitness: "+str(round(self.fitness,2))+" ,genes: "+''.join([self.genes[i].name for i in range(1,len(self.genes))])

# this is a single gene, it represents a building assigned to the corresponding node in the graph at the position where the gene is present.
class Building(Enum):
    _ = 0 # empty field
    H = 1 # house
    F = 2 # factory
    E = 3 # entertainment building
    
    # the building costs are always the in the same proportion to each other in the game,
    # this is multiplied by the PLANET modifier to get the real value 
    def cost(self):
        if self.value == 1:
            return 1600 
        elif self.value == 2:
            return 1200
        elif self.value == 3:
            return 800
        else:
            return 0

    # The constant bonus to happiness due to building type
    def happiness(self):
        if self.value == 1:
            return 0
        elif self.value == 2:
            return -1
        elif self.value == 3:
            return 1
        else:
            return 0

Evaluation Function

This is the most important part of a genetic algorithm, this can single-handedly cause your algorithm to tell you that not building anything is in fact the most cost effective solution and therefore the best Spore city ; This is the equivalent of killing of a civilisation to protect it, and God Damn does it happen often with these kinds of algorithms.

So how do you get it right? I wish I knew. There is a tonne of research in this area, but no one-size-fits-all approach exists. I find choosing an evaluation function to be very much just like throwing mud against the wall and seeing what sticks. Here have a cool article about this: link.

So what did I do in this case? Well here it is:

## NOTE: so whenever you see self.links this refers to the problem at hand, it's just a list of links between nodes, so each link looks like (A,B) where A and B are node 
## indices as discussed earlier. Links is just an array of those without duplicates - So essentially, just the entries from the upper triangular adjacency matrix for our graph 
## enumerated!

class GA:

    # ... #
    
    def evaluationFunction(self,a,weights):
       """
        given a chromosome a and a set of weights corresponding to production, cost and happiness, assign a fitness value to the chromosome. Higher is better
       """
            
        # these are base values, when multiplied by their corresponding planet modifiers, they give us the actual values.
        productionPoints,happinessPoints,costPoints = evaluate(self.links,a.genes)
        
        # we give a big penalty for solutions which dip below our happiness threshold, no riots please!
        negativeHappinessPen = -10 if happinessPoints < self.minHappiness else 0 
            
        # now these are main evaluators we will be using
        
        # average production per connection in the city
        productionFactor = productionPoints / len(self.links)

        # cost just reduces our fitness linearly
        costFactor = (1/(costPoints + 1))

        # happiness adds a tiny bonus, not really that important, since we already penalize bad happiness
        happinessFactor = min(1,happinessPoints/5)

        # combine it all, notice how we can supply weight values to prioritize differently
        return negativeHappinessPen + (weights[0])*productionFactor + (weights[1])*costFactor + (weights[2])*happinessFactor


# given a list of links of the form (i,j) 0 <= i,j < N, 0 being the city hall, a building type list of length N of buildings
# return the production points and happiness points along with the cost, which can be evaluated with a production multiplier to get the total spice per hour
# assumes there are no duplicate links
def  evaluate(links,buildings):
    productionPoints = happinessPoints = costPoints = 0
    # evaluate each link
    for l in links:
        A = buildings[l[0]]
        B = buildings[l[1]]
        # workout the spice/happiness values from the link using the enum values
        # possible connections:
        # H to F = 1 * 2 = 2
        # H to E = 1 * 3 = 3
        # E to F = 3 * 2 = 6

        value = A.value * B.value

        # +1P
        if value == 2:
            productionPoints+=1
        # +1H
        elif value == 3:
            happinessPoints+=1
        # -1H
        elif value == 6:
            happinessPoints-=1
        # no effect
        else:
            continue

    # evaluate total building cost
    cost = sum([x.cost() for x in buildings]) - buildings[0].cost()
    happiness = sum([x.happiness() for x in buildings])

    # evaluate happiness from buildings themselves

    return (productionPoints,happinessPoints+happiness,cost)

It's not that bad eh? Now I experimented with throwing powers into the equation but in the end I went with the customizable weights option. As I said before, You just gotta experiment my dude.

Now let's go over some basic operators and the general structure of our algorithm.

Structure

The general idea is to start with a randomized population of chromosomes, evaluate them, pick the best ones and somehow mutate/combine them to create better chromosomes the next iteration, then rinse and repeat. So:

  1. Initial Population - just whip out a couple of chromosomes at random.
  2. Evaluation - assign fitness scores to each individual in the population using the evaluation function and store them.
  3. New Population - this is normally described as a sequence of selection, crossover and mutation, but I don't particularly like that, since these operators don't necessarily happen in this order! Here we produce a new population from the old one, using our mutation, selection and crossover operators, I will explain this in detail don't worry.
  4. Convergence check - are we there yet? this is our stopping condition for the entire algorithm.
  • (If not converged) repeat from step 2.
  • (if converged) Evaluate the population and proudly return the best individual as the solution. Yay!

Operators

Selection

This operator is applied whenever we need to scoop up a new chromosome for our next population. Some selection operators produce an entire population at once, while others let you pick chromosomes on the fly continuously from the old pool. This is why the order of operators is not always the same.

A popular selection operator is tournament selection:

Tournament Selection

there are many variants, but the one I used is simply taking N random chromosomes, and choosing the best one out of those. The classic way of doing this is as follows:

choose k (the tournament size) individuals from the population at random 
choose the best individual from the tournament with probability p
choose the second best individual with probability p*(1-p)
choose the third best individual with probability p*((1-p)^2)
and so on

How do you that exactly in practice ? I am not entirely sure myself, most likely by calculating intervals between 0 and 1 according to the probability distribution above, generating a random number and seeing which "bucket" it belongs to.

Roulette Wheel Selection

This one is probably the most intuitive, here we simply "distribute" the probability of being chosen according to the fitness of each individual. So for example if we have 3 chromosomes:

A, with fitness 5

B, with fitness 10

C, with fitness 15

Then we could calculate their "survival probabilities" as follows:

A - 5/30 = 0.1666..

B - 10/30 = 0.333..

C - 15/30 = 0.5

This defines a probability distribution from which we can pick our chromosomes because all probabilities add up to 1.

Pretty neat isn't it ?

Mutation

Mutation is usually done after we generate all our new individuals and just before we evaluate them. There are a tonne of ways in which we can mutate on our solutions, and the particular one you choose should be evaluated against the particular problem space you're facing. Usually you'd only mutate an individual with a certain probability, i.e. the mutation probability.

Flip Bit

This one is really simple, take a chromosome, pick a random bit and flip it. In other representations you could understand this as flipping, or altering an atomic part of the chromosome.

Uniform

The operator I decided to go with. Pick a random bit and select a new random value between the minimum and maximum values specified.

Bit String Mutation

this is literally just the flip bit applied on each of the bits of the chromosome where each bit is flipped with the mutation probability.

There are way more mutation operators than this, but I just wanted to give you a taste, and besides, I think you should always chose a mutation operator designed for your specific problem, since it plays a big role.

Crossover

This operator is applied whenever we decide that we want to generate a new offspring via "reproduction" from 2 individuals in our old pool. So when you're making your new population you have a choice of either:

  • Selecting an individual directly without crossover as the new offspring
  • Selecting two individuals and performing crossover to generate the new offspring

the latter would happen with the crossover probability.

There are many ways in which you can actually perform the crossover:

Single-Point Crossover

Simply select a point in the chromosome, the new offspring will contain the genes from parent 1 for the first segment before that point and from parent 2 for the rest.

N-Point Crossover

Select more than one point this time, and alternate the gene source for each segment.

and so on.

Results

As it turns out, the results aligned perfectly with previous calculations done by the Spore community. This post succinctly displays all the best combinations for all possible colony layouts: link. Who could have thought... Anyhow this was a very fun experiment and I have absolutely no regrets :)