Saturday, May 30, 2015

MEPX - a cross platform tool for data analysis

MEPX can be used to determine relationships between data. You have to provide it some training data in the form of pairs (input, output) and MEPX will discover a computer program which connects the input with the output.

MEPX is based on a Genetic Programming (GP) variant named Multi Expression Programming (MEP). MEP has a unique feature: it encodes multiple solutions in the same chromosome. This means that one can explore the search space more efficiently than other GP techniques encoding only one solution in a chromosome.

MEPX is available for download from here: www.mep.cs.ubbcluj.ro.

A video showing how MEPX works is below:

s

Friday, May 1, 2015

A very short wxWidgets application

#include <wx/wx.h>

class MyApp : public wxApp
{
public:
 bool OnInit()
 {
  wxFrame *w = new wxFrame(NULL, wxID_ANY, "salut");
  w->Show();
  return true;
 }
};

IMPLEMENT_APP(MyApp)

Sunday, March 29, 2015

A genetic algorithm for solving the function optimization problem

// genetic algorithm with steady state
// for function optimization problem
// (finding the minum or maximum of a given function)

// implemented by Mihai Oltean
// web: http://www.cs.ubbcluj.ro/~moltean
// email: mihai.oltean@gmail.com

// compiled with Visual Studio 2013 Express Edition
// last modified on: 2015.08.09

// more implementations at: http://www.cs.ubbcluj.ro/~moltean/links.html

//--------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//--------------------------------------------------------------------
struct chromosome{ 
 // also called individual, or potential solution
 double *x;      // an array of genes; one for each dimension
 double fitness; // the quality of an individual
};
//--------------------------------------------------------------------
void generate_random(chromosome c, int num_dims, double min_x, double max_x)
{
 // num_dims is the number of dimensions of the function to be optimized
 // min_x, max_x is the range for variables
 for (int i = 0; i < num_dims; i++)
  c.x[i] = rand() / (double)RAND_MAX * (max_x - min_x) + min_x;
}
//--------------------------------------------------------------------
void copy_individual(chromosome *dest, chromosome source, int num_dims)
{
 for (int i = 0; i < num_dims; i++)
  dest->x[i] = source.x[i];
 dest->fitness = source.fitness;
}
//--------------------------------------------------------------------
void compute_fitness(chromosome *c, int num_dims)
{
 // a very simple function to optimize
 c->fitness = 0;

 for (int i = 0; i < num_dims; i++)
  c->fitness += c->x[i] * c->x[i];

 // another function
 // rastrigin
 //c->fitness = 10 * num_dims;
 //for (int i = 0; i < num_dims; i++)
 //c->fitness += c->x[i] * c->x[i] - 10 * cos(2 * 3.1415 * c->x[i]);
}
//--------------------------------------------------------------------
void mutation(chromosome c, int num_dims, double pm, double delta, double min_x, double max_x) 
// mutate the individual
{
 // mutate each symbol with the same pm probability

 for (int i = 0; i < num_dims; i++){

  double p = rand() / (double)RAND_MAX; 
  if (p < pm){
   int r = rand() % 2;
   // I choose randomly if I add or if I subtract delta
   if (r){
    if (c.x[i] + delta <= max_x)
     c.x[i] += delta;
   }
   else{
    if (c.x[i] - delta >= min_x)
     c.x[i] -= delta;
   }
  }
 }
}
//--------------------------------------------------------------------
void one_cut_point_crossover(chromosome parent1, chromosome parent2, chromosome offspring1, chromosome offspring2, int num_dims)
{
 int pct;
 pct = 1 + rand() % (num_dims - 1);
 // the cutting point should be after first gene 
 //and before the last one
 for (int i = 0; i < pct; i++){
  offspring1.x[i] = parent1.x[i];
  offspring2.x[i] = parent2.x[i];
 }
 for (int i = pct; i < num_dims; i++){
  offspring1.x[i] = parent2.x[i];
  offspring2.x[i] = parent1.x[i];
 }
}
//--------------------------------------------------------------------
void uniform_crossover(chromosome parent1, chromosome parent2, chromosome offspring1, chromosome offspring2, int num_dims)
{
 // uniform crossover can also be used
 // for each gene we decide randomly where it goes
 // (to the first or second offspring)
 for (int i = 0; i < num_dims; i++) {
  if (rand() % 2) {// flip
   offspring1.x[i] = parent2.x[i];
   offspring2.x[i] = parent1.x[i];
  }
  else {
   offspring1.x[i] = parent1.x[i];
   offspring2.x[i] = parent2.x[i];
  }
 }
}
//--------------------------------------------------------------------
int sort_function(const void *a, const void *b)
{
 if (((chromosome *)a)->fitness >((chromosome *)b)->fitness)
  return 1;
 else
  if (((chromosome *)a)->fitness < ((chromosome *)b)->fitness)
   return -1;
  else
   return 0;
}
//--------------------------------------------------------------------
void print_chromosome(chromosome c, int num_dims)
{
 printf("x = (");
 
 for (int i = 0; i < num_dims; i++)
  printf("%lf ", c.x[i]);
  printf(") ");
 printf("fitness = %lf\n", c.fitness);
}
//--------------------------------------------------------------------
int tournament_selection(int tournament_size, chromosome *pop, int pop_size)     
{
 // randomly pick several individuals
 // and return the best of them
 int selected_index;
 selected_index = rand() % pop_size;
 for (int i = 1; i < tournament_size; i++){
  int r = rand() % pop_size;
  selected_index = pop[r].fitness < pop[selected_index].fitness ? r : selected_index;
 }
 return selected_index;
}
//--------------------------------------------------------------------
void start_steady_state_ga(int pop_size, int num_gens, int num_dims, double pcross, double pm, double delta, double min_x, double max_x)       
// Steady-State genetic algorithm
// each step:
// pick 2 parents, mate them, 
// mutate the offspring
// and replace the worst in the population
// (only if offspring are better)
{
 // allocate memory
 chromosome *population;
 population = (chromosome*)malloc(pop_size * sizeof(chromosome));
 for (int i = 0; i < pop_size; i++)
  population[i].x = (double*)malloc(num_dims * sizeof(double));

 chromosome offspring1, offspring2;
 offspring1.x = (double*)malloc(num_dims * sizeof(double));
 offspring2.x = (double*)malloc(num_dims * sizeof(double));

  // initialize
 for (int i = 0; i < pop_size; i++){
  generate_random(population[i], num_dims, min_x, max_x);
  compute_fitness(&population[i], num_dims);
 }

 qsort((void *)population, pop_size, sizeof(population[0]), sort_function);

 printf("generation 0\n");
 // print the best from generation 0
 print_chromosome(population[0], num_dims); 

 for (int g = 1; g < num_gens; g++){
  for (int k = 0; k < pop_size; k += 2){
   // choose the parents using binary tournament
   int r1 = tournament_selection(2, population, pop_size);
   int r2 = tournament_selection(2, population, pop_size);
   // crossover
   double p = rand() / double(RAND_MAX);
   if (p < pcross)
    one_cut_point_crossover(population[r1], population[r2], offspring1, offspring2, num_dims);
   else{
    copy_individual(&offspring1, population[r1], num_dims);
    copy_individual(&offspring2, population[r2], num_dims);
   }
   // mutate the result
   mutation(offspring1, num_dims, pm, delta, min_x, max_x);
   compute_fitness(&offspring1, num_dims);
   mutation(offspring2, num_dims, pm, delta, min_x, max_x);
   compute_fitness(&offspring2, num_dims);

   // are offspring better than the worst
   if (offspring1.fitness < population[pop_size - 1].fitness){

    copy_individual(&population[pop_size - 1], offspring1, num_dims);
    qsort((void *)population, pop_size, sizeof(population[0]), sort_function);
   }
   if (offspring2.fitness < population[pop_size - 1].fitness){
    copy_individual(&population[pop_size - 1], offspring2, num_dims);
    qsort((void *)population, pop_size, sizeof(population[0]), sort_function);
   }
  }
  printf("generation %d\n", g);
  print_chromosome(population[0], num_dims);
 }
 // free memory
 free( offspring1.x);
 free( offspring2.x);

 for (int i = 0; i < pop_size; i++)
  free(population[i].x);
 free(population);
}
//--------------------------------------------------------------------
int main(void)
{

 int pop_size = 10;    // the number of individuals in population 
        // must be an even number
 int num_gens = 100;   // the number of generations
 double pm = 0.1;      // mutation probability
 double pcross = 0.9;  // crossover probability
 double delta = 1;  // jumps for mutation

 int num_dims = 2;  // number of dimensions of the function to be optimized
 double min_x = -10;  // definition domain for functions
 double max_x = 10;

 srand(0);

 start_steady_state_ga(pop_size, num_gens, num_dims, pcross, pm, delta, min_x, max_x);

 printf("Press enter ...");
 getchar();

 return 0;
}
//--------------------------------------------------------------------

MiniMax with alpha-beta pruning

// minimax.cpp : Defines the entry point for the console application.
//

// MIT licence ... you may do whatever you want with this source code
// last updated on 2015.03.29
// version 0.1

#include <stdio.h>
#include <stdlib.h>

#define infinity 10000

//-------------------------------------------------------------------------
struct node{
 int score;         // score for leaves
 int num_children;  // number of children
 int *children;     // index of children 
};

//-------------------------------------------------------------------------
bool read_tree(node*& tree, int &num_nodes)
{
 // each node has an index.
 // root has index 0
 // the indexes of other nodes are obtained by traversing the tree level by level.

 // file structure: on each line we have information about one node:
 // node_index num_children
 // if num_children is 0 then the next value is the score of that leaf
 // if num_children > 0 then we have a list of indexes for each children

 FILE *f = fopen("tree1.txt", "r"); // full path to the input file
 if (!f)
  return false;

 fscanf(f, "%d", &num_nodes);
 tree = (node*)malloc(num_nodes * sizeof(node));

 for (int i = 0; i < num_nodes; i++){
  int node_index;
  fscanf(f, "%d", &node_index);
  fscanf(f, "%d", &tree[node_index].num_children);

  if (!tree[node_index].num_children){
   fscanf(f, "%d", &tree[node_index].score);
   tree[node_index].children = NULL;
  }
  else{
   tree[node_index].children = (int*)malloc (tree[node_index].num_children * sizeof(int));
   tree[node_index].score = 0; // it is not used anyway
   for (int j = 0; j < tree[node_index].num_children; j++)
    fscanf(f, "%d", &tree[node_index].children[j]);
  }
 }
 return true;
}
//-------------------------------------------------------------------------
int minimax_ab(node* tree, int node_index, int level, int a, int b, int *visited, int &num_visited)
{
 if (!tree[node_index].num_children){
  visited[num_visited++] = node_index;
  return tree[node_index].score;
 }
 else
  if (level % 2){// min level
   int min_score = infinity;
   visited[num_visited++] = node_index;

   for (int i = 0; i < tree[node_index].num_children; i++){
    int child_score = minimax_ab(tree, tree[node_index].children[i], level + 1, a, b, visited, num_visited);
    if (min_score > child_score)
     min_score = child_score;
    if (b > min_score)
     b = min_score;
    if (b <= a)
     break;
   }
   return min_score;
  }
  else{// max level;
   int max_score = -infinity;
   visited[num_visited++] = node_index;
   for (int i = 0; i < tree[node_index].num_children; i++){
    int child_score = minimax_ab(tree, tree[node_index].children[i], level + 1, a, b, visited, num_visited);
    if (max_score < child_score)
     max_score = child_score;
    if (a < max_score)
     a = max_score;
    if (b <= a)
     break;
   }
   return max_score;
  }
}
//-------------------------------------------------------------------------
int main(void)
{
 int num_nodes;
 node *tree;

 if (read_tree(tree, num_nodes)){

  int a = -infinity;
  int b = infinity;

  int *visited = (int*)malloc (num_nodes * sizeof(int));
  int num_visited = 0;

  int alpha = minimax_ab(tree, 0, 0, a, b, visited, num_visited);

  printf("Alpha = %d\n", alpha);

  printf("Number of visited nodes = %d\n", num_visited);
  printf("Visited nodes: ");
  for (int i = 0; i < num_visited; i++)
   printf("%d ", visited[i]);

  free(visited);
// free memory allocated by tree
  for (int i = 0; i < num_nodes; i++)
   if (tree[i].children)
     free(tree[i].children);
  free(tree);
 }
 else
  printf("Cannot read/find file!");

 printf("\n\nPress enter.");
 getchar();

 return 0;
}
//-------------------------------------------------------------------------
Example of input (from: https://en.wikipedia.org/wiki/Alpha-beta_pruning (accessed on 2015.03.22)). Just copy the lines below in a file and specify the correct location in the read_tree function:
33
0 3 1 2 3
1 2 4 5
2 2 6 7
3 2 8 9
4 2 10 11
5 1 12
6 2 13 14
7 1 15
8 1 16
9 2 17 18
10 2 19 20
11 3 21 22 23
12 1 24
13 1 25
14 2 26 27
15 1 28
16 1 29
17 2 30 31
18 1 32
19 0 5
20 0 6
21 0 7
22 0 4
23 0 5
24 0 3
25 0 6
26 0 6
27 0 9
28 0 7
29 0 5
30 0 9
31 0 8
32 0 6