? Editing: Post:21.body Save Delete Cancel
Content changed Sign & Publish new content

LiberIT Blog

Blogging about how we will colonize the cosmos, while promoting diversity and liberty.

Follow in NewsfeedFollowing

TOC by date
TOC by tag

Latest comments:

Add new post

Title

21 hours ago · 2 min read ·
3 comments

tag:
Body
Read more

(Genetic Programmer in less than 150 lines of C) Evolutionary Programmer Training: Ration One

on Sep 06, 2017
tag: GP evolution programming ration tutorial

I couldn't find a simple genetic programmer tutorial on the Internet, so I loosely followed one on Evolutionary Algorithms to make this post.

Seductive Concept

The seductive concept behind establishing an evolutionary programmer is that it can in principle do a lot of computer programming for you. All you have to do is provide it with inputs, outputs and some functions and then it will fill in the algorithm.

Why C you ask? Because it has the best OpenCL integration, and Evolutionary Programming is embarrassingly parallelizable, so is pliant to highly parallel processors.

Brief Glance

At a brief glance, we can look at the main function:

int main() {
#define TRAINING_SERIES_LONG 3
  const uint16_t training_series_long = TRAINING_SERIES_LONG;
  const uint16_t training_series[TRAINING_SERIES_LONG][2] = {
      {'1', '2'}, {'2', '3'}, {'3', '4'}}; // return input
  uint16_t program_output[TRAINING_SERIES_LONG] = {0};

Here the training series has been established,
each input is paired with an output. Can have very large training sets, though generally 3 is a minimum. Two for evolving and one for testing.

You'll note also there is a program_output variable, it will be used as local memory for one of the function calls, to avoid dynamic allotment each time.

#define CEREMONY_LONG 3
  const uint16_t ceremony_long = CEREMONY_LONG;
  const v16us ceremony[CEREMONY_LONG] = {
      {plus_WORD}, {return_WORD}, {invert_WORD}};

Here the ceremonies or available functions have been established, using constants from pyashWords.h.

#define POPULATION_LONG 16
  const uint16_t population_long = POPULATION_LONG;
  v16us population[POPULATION_LONG] = {0};
  uint16_t population_health[POPULATION_LONG] = {0};

Here the population has been alloted, each person is a program and fits in a vector of sixteen, sixteen bit values (a Pyash Tablet). Later on can have larger populations, but for ration one, it should be sufficient.

  uint16_t champion_iteration = 0;
  uint16_t champion_health = 0;

Allotment for the champion program.

  population_establish(ceremony_long, ceremony, population_long, population);

Here the population is established, by making some random programs and filling in the population allotment.

population_quiz(population_long, population, training_series_long,
                  training_series, program_output, population_health);

This is the most computation intensive part, where the population is quized, by giving it the input, finding the output, and then checking how many that program got correct.

  champion_choose(population_long, population_health, &champion_iteration,
                  &champion_health);

This is a simple ceremony that finds the fittest program.

Typically at this point, if the champion_health is not maximum_health, then we would be going through additional population modification steps, but we'll leave that for ration two.

  printf("0x%X is champion, %d is health\n", population[champion_iteration].s0,
         champion_health);

  return 0;
}

Here we declare the champion and finish successfully.
For the rest of the article will look at the inner ceremonies more deeply.

Health Assessment

The original tutorial started with a fitness function, so did I.

void health_assess(const uint16_t training_series_long,
                   const uint16_t training_series[][2],
                   const uint16_t *program_output, uint16_t *health) {
  assert(training_series_long > 0);
  assert(training_series != NULL);
  assert(program_output != NULL);
  assert(health != NULL);
  uint16_t iteration = 0;
  uint16_t health_collector = 0;
  for (iteration = 0; iteration < training_series_long; ++iteration) {
    if (training_series[iteration][1] == program_output[iteration]) {
      ++health_collector;
    }
  }
  *health = health_collector;
}

It is a skeleton simply returns the number of results that it got correct. Later on we'll include partials.

Population Establish

We need to have an initial population of programs.

void population_establish(const uint16_t ceremony_long, const v16us *ceremony,
                          const uint16_t population_long, v16us *population) {
  uint16_t iteration = 0;
  srand(5);
  for (iteration = 0; iteration < population_long; ++iteration) {
    population[iteration] = ceremony[rand() % 3];
  }
}

Here the population is comprised of persons performing a single ceremony. Later on we could have them doing multiple and more complicated ceremonies.

Program Interpret

void program_interpret(const v16us program, const uint16_t input,
                       uint16_t *output) {
  uint16_t activity = program.s0;
  assert(activity != 0);
  switch (activity) {
  case plus_WORD:
    *output = input + 1;
    break;
  case return_WORD:
    *output = input;
    break;
  case invert_WORD:
    *output = ~input;
    break;
  default:
    assert(1 == 0);
  }
}

The program interpreter is where there is the most room for growth. Ideally it would be Turing complete, support multiple input arguments and have named functions.

It will be the largest part of the OpenCL kernel.

Program Quiz and Population Quiz

void program_quiz(const uint16_t training_series_long,
                  const uint16_t training_series[][2], const v16us program,
                  uint16_t *output) {
  assert(output != NULL);
  uint16_t iteration = 0;
  uint16_t program_output = 0;
  for (iteration = 0; iteration < training_series_long; ++iteration) {
    program_interpret(program, training_series[iteration][0], &program_output);
    output[iteration] = program_output;
  }
}

This quizzes a single program, by running it through all the inputs, and getting the outputs. It would be possible to use this as an OpenCL kernel, however it would be inefficient unless you have many thousands of inputs and outputs.

void population_quiz(const uint16_t population_long, const v16us *population,
                     const uint16_t training_series_long,
                     const uint16_t training_series[][2],
                     /*local*/ uint16_t *program_output,
                     uint16_t *population_health) {
  assert(population != NULL);
  assert(training_series != NULL);
  assert(population_health != NULL);
  uint16_t iteration = 0;
  v16us program = {0};
  uint16_t health = 0;
  for (iteration = 0; iteration < population_long; ++iteration) {
    program = population[iteration];
    program_quiz(training_series_long, training_series, program,
                 program_output);
    health_assess(training_series_long, training_series, program_output,
                  &health);
    population_health[iteration] = health;
  }
}

This ceremony quizzes each program and returns their health.

For an OpenCL implementation it would be feeding a parallel_program_quiz ceremony that accepts as input the training_series, a list of programs and a program_output array large enough to fit all the outputs.

Within parallel_program_quiz each worker would then select a point in the training_series and a program to interpret. After it finishes interpreting the program it would write the output to it's program_output point. It would then go onto the next training_series and program that hadn't been done yet, until they are all finished.

champion_choose

void champion_choose(const uint16_t population_long,
                     const uint16_t *population_health,
                     uint16_t *champion_iteration, uint16_t *champion_health) {
  assert(champion_health != NULL);
  assert(champion_iteration != NULL);
  assert(population_health != NULL);
  uint16_t iteration = 0;
  uint16_t fittest_health = 0;
  uint16_t fittest_iteration = 0; // expand to array for multiple fittest
  uint16_t health = 0;
  for (iteration = 0; iteration < population_long; ++iteration) {
    health = population_health[iteration];
    if (health > fittest_health) {
      fittest_iteration = iteration;
      fittest_health = health;
    }
  }
  *champion_iteration = fittest_iteration;
  *champion_health = fittest_health;
}

This is a simple ceremony that chooses the fittest individual based on the most health.

And that's it!

All Program Code

For the working program code you can Git copy it from gitlab and zeronet

0 Comment:

user_name1 day ago
Reply
Body
<< >>
This page is a snapshot of ZeroNet. Start your own ZeroNet for complete experience. Learn More