Genetic algorithm running on brainfuck code
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
output
sources
.gitignore
Makefile
README.mkd
__main__.py
bfinterp.c
bfinterp.h
case.py
commons.py
compare_str.c
config.py
creation.py
interpreter.py
main.c
mmh.py
mutator.py
mutator_functions.py
reproduction.py
requirements.txt
scoring.py
selection.py
statistics.py
stepping.py
test_case.py
test_compare_str.py
test_interpreter.py
test_selection.py
unit.py
utils.py

README.mkd

BFIA

Idea: provide unit tests, let the computer find alone the brainfuck source code that correctly answers to the unit tests. Idea#2: use genetic algorithm to generate the code. Idea#3: implement a meta meta heuristic in order to optimize the genetic algorithm parameters in real time.

Brainfuck interpreter

Made in C, very simple. Makefile contains recipes for compilation of both shared lib (used by python code) and standalone module, that can read input file and interpret it.

Later improvements:

Meta heuristic: genetic algorithm

Implements a population of Unit, where a Unit is basically a BF source code. A Unit is conserved for next population and used as parent according to both scoring and selections functions.

The scoring function assign for a Unit its performance. Higher is better. The selection function choose which Units will have the right to remain and produce childs.

All childs are also given to a mutator, a function that will modify slightly the BF source code, bringing variation in the population.

Later improvements:

  • more scoring functions
  • better selection function using scores
  • dissociate right to remain and right to produce childs

Functions and methods naming

For each of the 5 functions implementing the genetic algorithm (scoring, selection, mutation, reproduction and creation), there is a bunch of possible functions, or variations of them. The five modules implementing these functions provides the following three normalized functions:

  • named_functions: returning a dict mapping a method name with the function implementing the method.
  • anonymous_functions: returning an iterable of functions implementing unamed methods.
  • default_functions: returning an iterable of functions to use when no precise instructions are given.

This is necessary in order to allows the naming of some methods, for simpler referencing in configuration. It also introduce the notion of default methods to use when user provides nothing, and anonymous methods that have no code name referring them.

For example, a configuration may be reffered as IOC, PLDD, ALL, SCNP, MOD, meaning that the used functions are io_comparison for score, poolling for selection, all available for mutation, same_with_child without parent conservation for reproduction and memory_oriented_diversity for creation.

Meta meta heuristic: a guide for the meta heuristic

Instead of relying on a human to find the proper configuration to find a problem, a meta meta heuristic (MMH) is implemented.

It is a program that tweaks the parameter of the meta heuristic during time, looking for quicker convergence to the expected solution.

Some parameters this program can touch:

  • population size
  • population number (by splitting and merging populations)
  • scoring, selection, reproduction, mutation, and stepping functions