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.
[2]:
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.
[4]:
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.
[7]:
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.
[9]:
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.
[10]:
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).
[11]:
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.
[12]:
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.
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())
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())
[ ]:
print("RANK FITNESS")
for i, member in enumerate(hof):
print(" ", i, " ", member.fitness)
Animation of Evolution#
[17]:
# 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)
[28]:
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())
[ ]: