Bingo Tutorial 2: Zero Min Problem

Goal: Find a list of numbers with zero magnitude through genetic optimization

Chromosome

The basic unit of bingo evolutionary analyses are Chromosomes. The chromosome used in this example is a MultipleFloatChromosome. The MultipleFloatChromosome contains a list of floating point values. It also has optional use of local optimization for some of those values.

from bingo.chromosomes.multiple_floats import MultipleFloatChromosome
chromosome = MultipleFloatChromosome([0., 1., 2., 3.])
print(type(chromosome))
print(chromosome)

Chromosome Generator

Chromosomes are created with a Generator. Generation of MultipleValueChromosome requires a function that returns floats to populate the list of values. In this example, that function is get_random_float.

The Generator is initialized with the random value function, along with the desired size of the float list, and an optional list of indices on which to perform local optimization. The Generator is used to generate populations of Chromosomes on Islands.

import numpy as np
from bingo.chromosomes.multiple_floats import MultipleFloatChromosomeGenerator

VALUE_LIST_SIZE = 8
np.random.seed(0)

def get_random_float():
    return np.random.random_sample()

generator = MultipleFloatChromosomeGenerator(get_random_float, VALUE_LIST_SIZE, [1, 3, 4])

# Example of Generator
chromosome = generator()
print(chromosome)
print(chromosome.get_number_local_optimization_params())

Chromosome Variation

Variation of MultipleValueChromosome individuals is performed with single-point crossover and/or single-point mutation.

from bingo.chromosomes.multiple_values import SinglePointCrossover
from bingo.chromosomes.multiple_values import SinglePointMutation

crossover = SinglePointCrossover()
mutation = SinglePointMutation(get_random_float)

# Example of Mutation
before_mutation = MultipleFloatChromosome([0., 0., 0., 0., 0., 0.])
after_mutation = mutation(before_mutation)
print("Mutation")
print("before: ", before_mutation)
print("after:  ", after_mutation)

# Example of Crossover
parent_1 = MultipleFloatChromosome([0., 0., 0., 0., 0., 0.])
parent_2 = MultipleFloatChromosome([1., 1., 1., 1., 1., 1.])
child_1, child_2 = crossover(parent_1, parent_2)
print("Crossover")
print("parent 1: ", parent_1)
print("parent 1: ", parent_2)
print("child 1: ", child_1)
print("child 1: ", child_2)

Fitness and Evaluation

In order to Evaluate Chromosomes and assign them a fitness value, first we must define a FitnessFunction. For the Zero Min Problem, this Fitness Function calculates fitness by finding the norm of all the values in a Chromosome’s list of values. Once a FitnessFunction has been defined, it can be passed to an Evaluation to be applied to a population. In this example, we also wrap the FitnessFunction with LocalOptFitnessFunction to perform local optimization on indicies specified in the Generator class.

from bingo.evaluation.fitness_function import FitnessFunction
from bingo.local_optimizers.scipy_optimizer import ScipyOptimizer
from bingo.local_optimizers.local_opt_fitness import LocalOptFitnessFunction
from bingo.evaluation.evaluation import Evaluation

class ZeroMinFitnessFunction(FitnessFunction):
    def __call__(self, individual):
        return np.linalg.norm(individual.values)


fitness = ZeroMinFitnessFunction()
optimizer = ScipyOptimizer(fitness)
local_opt_fitness = LocalOptFitnessFunction(fitness, optimizer)
evaluator = Evaluation(local_opt_fitness) # evaluates a population (list of chromosomes)

# Example of fitness
chromosome = MultipleFloatChromosome([1., 1., 1., 1., 1., 1.],
                                     needs_opt_list=[0, 3]) # perform local optimization on these indices
print(fitness(chromosome))
print(chromosome)
print(local_opt_fitness(chromosome))
print(chromosome)

Notice that the values in the chromosome at indices 0 and 3 become very near zero. This occurs as part of the local optimization.

Selection

For this example, we use Tournament Selection to select GOAL_POPULATION_SIZE individuals to advance to the next generation.

from bingo.selection.tournament import Tournament

GOAL_POPULATION_SIZE = 25

selection = Tournament(GOAL_POPULATION_SIZE)

Evolutionary Algorithm: Mu + Lambda

The Evolutionary Algorithm used in this example is called MuPlusLambda. Mu represents the parent population and Lambda represents their offspring. MuPlusLambda means the parents and offspring are evaluated together and then the most fit individuals for the next generation are selected from both populations combined. We pass our previously defined Evaluation and Selection modules to MuPlusLambda, along with Crossover and Mutation which will be used to define the behaviors of Variation.

from bingo.evolutionary_algorithms.mu_plus_lambda import MuPlusLambda

MUTATION_PROBABILITY = 0.4
CROSSOVER_PROBABILITY = 0.4
NUM_OFFSPRING = GOAL_POPULATION_SIZE

evo_alg = MuPlusLambda(evaluator,
                       selection,
                       crossover,
                       mutation,
                       CROSSOVER_PROBABILITY,
                       MUTATION_PROBABILITY,
                       NUM_OFFSPRING)

Hall of Fame

A HallOfFame object can be used to keep track of the best individuals that occur during the evolution of a population. It is initialized with the maximum number of members to track, i.e., the 5 best individuals will be saved in the hall of fame in the example below. Optionally, a similarity function can be given as an argument, in order to identify similar individuals (and track only unique ones). It is passed to an island on initialization (see next subsection).

from bingo.stats.hall_of_fame import HallOfFame

def similar_mfcs(mfc_1, mfc_2):
    """identifies if two MultpleFloatChromosomes have similar values"""
    difference_in_values = 0
    for i, j in zip(mfc_1.values, mfc_2.values):
        difference_in_values += abs(i - j)
    return difference_in_values < 1e-4

hof = HallOfFame(max_size=5, similarity_function=similar_mfcs)

Island

An Island is where evolution takes place in bingo analyses. The Island class takes as arguments an Evolutionary Algorithm, a Generator with which to generate an initial population, and thesize of the population on the island. The Island will create a population and then execute generational steps of the Evolutionary Algorithm to evolve the population.

from bingo.evolutionary_optimizers.island import Island

POPULATION_SIZE = 10

island = Island(evo_alg, generator, POPULATION_SIZE, hall_of_fame=hof)

print("Island age:", island.generational_age,
      " with best fitness:", island.get_best_fitness(), "\n")
for i, indv in enumerate(island.population):
    print("indv", i, indv)

Evolution

There are two mechanisms for performing evolution in bingo.

1. Manually step through a set number of generations

print("Island age:", island.generational_age,
      " with best fitness:", island.get_best_fitness())

island.evolve(num_generations=10)

print("Island age:", island.generational_age,
      " with best fitness:", island.get_best_fitness())

2. Evolve automatically until convergence

island.evolve_until_convergence(max_generations=1000,
                                fitness_threshold=0.05)

print("Island age:", island.generational_age,
      " with best fitness:", island.get_best_fitness(), "\n")
print("Best indv: ", island.get_best_individual())

The hall of fame is automatically updated during evolution.

Note that, for the most part, it can be treated like a list of individuals, in ascending order of fitness.

print("RANK      FITNESS")
for i, member in enumerate(hof):
    print(" ", i, " ", member.fitness)

Animation of Evolution

# Reinitialize and rerun island while documenting best individual
island = Island(evo_alg, generator, POPULATION_SIZE)
best_indv_values = []
best_indv_values.append(island.get_best_individual().values)
for i in range(50):
    island.evolve(1)
    best_indv_values.append(island.get_best_individual().values)

import matplotlib.pyplot as plt
import matplotlib.animation as animation

def animate_data(list_of_best_indv_values):

    fig, ax = plt.subplots()

    num_generations = len(list_of_best_indv_values)
    x = np.arange(0, len(list_of_best_indv_values[0]))
    y = list_of_best_indv_values
    zero = [0]*len(x)
    polygon = ax.fill_between(x, zero, y[0], color='b', alpha=0.3)
    points, = ax.plot(x, y[0], 'bs')
    points.set_label('Generation :' + str(0))
    legend = ax.legend(loc='upper right', shadow=True)


    def animate(i):
        for artist in ax.collections:
            artist.remove()
        polygon = ax.fill_between(x, zero, y[i], color='b', alpha=0.3)
        points.set_ydata(y[i])  # update the data
        points.set_label('Generation :' + str(i))
        legend = ax.legend(loc='upper right')
        return points, polygon, legend


    # Init only required for blitting to give a clean slate.
    def init():
        points.set_ydata(np.ma.array(x, mask=True))
        return points, polygon, points

    plt.xlabel('Chromosome Value Index', fontsize=15)
    plt.ylabel('Value Magnitude', fontsize=15)
    plt.title("Values of Best Individual in Island", fontsize=15)
    plt.ylim(-0.01,0.5)
    ax.tick_params(axis='y', labelsize=15)
    ax.tick_params(axis='x', labelsize=15)

    plt.close()

    return animation.FuncAnimation(fig, animate, num_generations, init_func=init,
                                   interval=250, blit=True)

from IPython.display import HTML
HTML(animate_data(best_indv_values).to_jshtml())