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
Saturday, May 30, 2015
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)
Tuesday, April 21, 2015
Computing by xeroxing on transparencies
References:
Tom Head, Parallel Computing by Xeroxing on Transparencies, Algorithmic Bioprocesses, Springer 2009, pp. 631-637.
Thursday, April 2, 2015
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; } //-------------------------------------------------------------------------
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
Subscribe to:
Posts (Atom)