OneMax Problem¶

This notebook provides a short solution to a classical test problem in evolutionary computation known as OneMax problem. The goal is to maximize the number of 1 symbols in a bitstring with fixed length.

References¶

Gigùere, Goldberg (1998): Population Sizing for Optimum Sampling with Genetic Algorithms: A Case Study of the Onemax Problem, see pdf
- “The OneMax problem is a bit-counting problem where the fitness value of each binary string (individual) is equal to the number of one bits in it.”

[1]:

import alogos as al

ebnf = """
S = BYTE BYTE BYTE BYTE BYTE BYTE BYTE BYTE BYTE BYTE BYTE BYTE
BYTE = BIT BIT BIT BIT BIT BIT BIT BIT
BIT = "0" | "1"
"""
grammar = al.Grammar(ebnf_text=ebnf)

def obj_func(string):
    return string.count('1')

ea = al.EvolutionaryAlgorithm(grammar, obj_func, 'max', verbose=True, max_or_min_fitness=12*8)
best_individual = ea.run()

Progress         Generations      Evaluations      Runtime (sec)    Best fitness
..... .....      10               803              0.5              67.0
..... .....      20               1573             0.6              77.0
..... .....      30               2266             0.7              89.0
..... .....      40               2877             0.8              93.0
..... .....      50               3404             0.9              96.0


Finished         50               3404             0.9              96.0

[2]:

print(best_individual)

CFG-GP-ST individual:
- Genotype: ((0,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4,1,2,4,2,4,2,4,2,4,2,4,2,4,2,4,2,4),(12,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,8,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0))
- Phenotype: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
- Fitness: 96.0

[3]:

print(best_individual.phenotype)

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111