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