Genetic Programming applied to AI Heuristic Optimization

Photo by James Harrison on Unsplash

Introduction

My interest in genetic programming began in 2015 when I studied the iterated ultimatum game. More recently, I have been using genetic algorithms to optimize parameters in a risk management system at work. In this short article, I will discuss the high level idea and the necessary ingredients to build your own genetic algorithm. I will also give a simple implementation of a genetic algorithm used to optimize the heuristic function for a general game playing AI agent using alpha beta pruning and minimax with iterative deepening. Finally, I will discuss several drawbacks to genetic programming in AI.

What is it?

Genetic programming (GP) is a type of evolutionary algorithm that can compute solutions to general problems which humans do not know how to solve directly. The machine is tasked with generating a working computer program from a high-level implementation of the problem. The idea is to randomly generate thousands of computer programs and use Darwinian natural selection to evolve the programs until the population converges to a global maxima/minima. It is often used in the field of Machine Learning to determine relationships between features in data. GP has also been applied in various financial areas: building automated trading strategies, risk management systems and credit card detection. Other areas of interest include quantum computing, design of electric circuits and antennae. I’ve also recently heard of genetic algorithms being used to debug code in large scale programs.

Ingredients for a Genetic Program

All evolutionary algorithms must have a mechanism for breeding, mutating and evolving. Additionally, if you wish to use true genetic programming, you must define a genetic representation of the parameters. For example, a simple representation of a float data type would be a binary string representation. One could then apply evolution to each bit of the string. With regards to breeding, crossover is the most popular method by which genomes of the binary data are combined in a random way. Defining a robust breeding and mutation mechanism are crucial to ensure that the solution converges to a global maxima/minima.

Example in Game Playing

Suppose we are tasked with building an AI system to play a general game (chess for example). If we applied the standard methods of minimax and alpha beta pruning we would be tasked with generating a heuristic function to determine the relative “strength” of a move. Suppose we choose something of the form:

V(w) = w * white_pieces — (1-w)*black_pieces where w in [0,1].

Genetic programming will be tasked with choosing the parameter, w, for our AI agent. Note that in the code below I will be using my AlphaBetaPlayer class as a representation of the individuals in the population. The genetic score function is defined to be the simple heuristic above.

Out first task is to define an individual agent as follows:

def individual(weight):
    # creates an individual 
    return AlphaBetaPlayer(score_fn=genetic, weight=weight)

The initial population is just a group of individuals who have random weights. We can implement it as follows:

def population(count):
    # creates a list of individuals 
    return [ individual(random.uniform(0,1)) for x in range(count) ]

We may now define the breeding process as computing a random number between the mother’s weight and the father’s weight, and increase the range slightly to keep more genetic diversity. We don’t allow the mother and father to be the same individual.

def breed(mother, father):
    if mother != father:   
        if father.w > mother.w:
            childWeight = random.uniform(mother.w*.95, father.w*1.05)
        else:
            childWeight = random.uniform(father.w*.95, mother.w*1.05)
        if childWeight < 0:
            childWeight = 0
        if childWeight > 1:
            childWeight = 1
        child = individual(childWeight)
        return child
    else:
        print('Cannot breed with itself: Error: Mother == Father')

Keep in mind that the breeding process chosen here is completely arbitrary and may be defined differently. For example, we may consider taking the arithmetic average of the mother and father or even the geometric average. You should be trying to mimic Darwinian evolution to the best of your knowledge. Again, to reiterate my comments above, the most robust method would be to use some type of binary string representation and apply true crossover on the genotypes. This will not be discussed in this short example. We adjust for trivial border cases in the obvious way.

Our next task is to define the mutation process. A simple implementation would be shift the weights up or down by a random amount. We do something slightly more clever to ensure genetic diversity.

def mutate_agent(agent):
    if agent.w < 0.5:
        newWeight = (1-agent.w) + random.uniform(-0.5, 0.1)
    else:
        newWeight = (1-agent.w) + random.uniform(-0.1, 0.5) 
    if newWeight < 0:
        newWeight = 0
    if newWeight > 1:
        newWeight = 1
    mutated_agent = individual(newWeight)
    return mutated_agent

In particular, we shift the probability distribution to move weights, which are either close to 0 or 1 to something closer to 1 or 0, respectively. Again, we adjust for trivial border cases in the obvious way.

Our final task is to combine the functions above to evolve the current population. Our approach involved letting the agents play against each other for a set number of games and then choosing the top 20% of the performers to use in the next evolution cycles. We also randomly select some of the lesser performing agents to ensure genetic diversity. We effectively kill off the rest of the agents. Finally, we create the children using our breeding process and mutate 5% of the population using our mutation function discussed above. The parameters in the function define the number of games to be played, the percentage of the parents to retain, the random selection size of the bottom performers and the mutation rate.

def evolve(pop, gamesFactor=2, retain=0.2, random_select=0.05, mutate=0.01):
    # Determine the parents to breed from the population
    agent_score = {}
    numGames = len(pop) * gamesFactor
    bar = progressbar.ProgressBar()
for game in bar(range(numGames)):
        competitors = random.sample(pop, 2)
        game = Board(competitors[0], competitors[1])
        winner, history, outcome = game.play()
        competitors.remove(winner)
        loser = competitors[0]
        if winner not in agent_score.keys():
            agent_score[winner] = 1
        else:
            agent_score[winner] += 1
        if loser not in agent_score.keys():
            agent_score[loser] = -1
        else:
            agent_score[loser] -= 1        
        
    top_performers_size = int(retain * len(pop))
    bottom_performers_size = len(pop) - top_performers_size
    rand_select_size = int(len(pop) * random_select)
    top_perfomers = heapq.nlargest(top_performers_size, agent_score, key=agent_score.get)
    bottom_performers = heapq.nsmallest(bottom_performers_size, agent_score, key=agent_score.get)
    parents = top_perfomers + random.sample(bottom_performers, rand_select_size)
    random.shuffle(parents)
# Create children
    numChildren = len(pop) - len(parents)
    
    children = []
    for i in range(numChildren):
        par = random.sample(parents, 2)
        father = par[0]
        mother = par[1] 
        child = breed(mother, father)
        children.append(child)
        
    new_pop = parents + children
mutated_pop = []
    # Randomly mutate some of the new population
    for agent in new_pop:
        if mutate > random.uniform(0,1):
            print('Mutate')
            mutated_agent = mutate_agent(agent)
            mutated_pop.append(mutated_agent)
        else:
            mutated_pop.append(agent)
    return mutated_pop

Combining everything into our main program, we can continuously evolve the population until we have converged to a global maxima/minima. The simulation took 17 hours to run on my machine.

if __name__ == "__main__":
    pop_count = 100
    evolution_cyles = 12
    pop = population(pop_count)
    history = []
    for i in range(evolution_cyles):
        print(i)
        pop = evolve(pop, gamesFactor=10, retain=0.2, random_select=0.05, mutate=0.05)
        best_weights = [i.w for i in pop]
        print(stats.describe(best_weights))
        history.append(best_weights)
      
    print('Evolution Results:')
    [stats.describe(x) for x in history]

At the end of the day you will be interested in observing the final population after a suitable number of evolution cycles. The descriptive statistics should have a small standard deviation and a tight inter-quartile range. You should see that all the agents have similar weights. For the chess-playing agent, the genetic algorithm gives an optimal weight of approximately 0.3452.

Drawbacks to Genetic Programming

One simple drawback to genetic programming is the computational cost. One needs to evolve many populations before convergence is reached. Another drawback is that the solution is not guaranteed to converge to the global maxima/minima. It’s also often difficult to determine breeding and mutation procedures. Finally, a large number of parameters usually require a large number of evolution cycles. Game playing heuristic functions are often designed to balance complexity and insight into the game. It’s often important to design the heuristic to be as simple as possible. For that reason, genetic programming works quite well for AI game playing agents.

References

[1] https://zhanggw.wordpress.com/2009/11/08/a-simple-genetic-programming-in-python-4/

[2] https://lethain.com/genetic-algorithms-cool-name-damn-simple/

[3] https://en.wikipedia.org/wiki/Genetic_programming

[4] http://www.genetic-programming.org/

[5] Ben Lande during summer of 2015