codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <stdio.h> #include <stdlib.h> #include <time.h> typedef unsigned char CHROMOSOME; typedef unsigned char FITNESS; typedef CHROMOSOME *POPULATION; void initialize_pop (POPULATION, int); CHROMOSOME crossover (CHROMOSOME, CHROMOSOME); FITNESS fitness (CHROMOSOME); CHROMOSOME mutate (CHROMOSOME); CHROMOSOME get_parent (POPULATION, FITNESS [], int); void print_pop (POPULATION, int); int main (void) { size_t pop_size; unsigned i, gen, final_gen; unsigned mut_prob = 101; POPULATION pop, prev_pop; CHROMOSOME mom, dad; FITNESS *fit_arr; srand(time(0)); printf("Enter desired population size: "); scanf("%u", &pop_size); while ((mut_prob < 0) || (mut_prob > 100)) { printf("Enter desired mutation probability as an integral percentage: "); scanf("%u", &mut_prob); } printf("Enter desired number of generations: "); scanf("%u", &final_gen); if (!(pop = malloc(sizeof(CHROMOSOME) * pop_size))) { printf("Couldn't allocate enough memory for population."); return 0; } initialize_pop(pop, pop_size); printf("Initial population:\n"); print_pop(pop, pop_size); for (gen = 1; gen <= final_gen; ++gen) { if (!(fit_arr = malloc(sizeof(FITNESS) * pop_size))) { printf("Couldn't allocate enough memory for fitness array."); return 0; } for (i = 0; i < pop_size; ++i) fit_arr[i] = fitness(pop[i]); prev_pop = pop; if (!(pop = malloc(sizeof(CHROMOSOME) * pop_size))) { printf("Couldn't allocate enough memory for population."); return 0; } for (i = 0; i < pop_size; ++i) { mom = get_parent(prev_pop, fit_arr, pop_size); dad = get_parent(prev_pop, fit_arr, pop_size); pop[i] = crossover(mom, dad); if (rand() % 100 < mut_prob) pop[i] = mutate(pop[i]); } free(fit_arr); free(prev_pop); } /* here we have our final population */ printf("Final population:\n"); print_pop(pop, pop_size); free(pop); return 0; } void initialize_pop (POPULATION pop, int size) { int i; for (i = 0; i < size; ++i) pop[i] = rand() % ((int)((CHROMOSOME) (~0)) + 1); } CHROMOSOME crossover (CHROMOSOME mom, CHROMOSOME dad) { /* select random crossover point and generate offspring */ int xovr_point = rand() % (sizeof(CHROMOSOME) * 8 + 1); return (mom & ~(~0 << xovr_point)) | (dad & (~0 << xovr_point)); } FITNESS fitness (CHROMOSOME chr) { /* for this example we will assume that more bits set = higher fitness */ int i; FITNESS fit = 0; for (i = 0; i < sizeof(CHROMOSOME) * 8; ++i) { fit += (chr >> i) & 0x01; } return fit; } CHROMOSOME mutate (CHROMOSOME chr) { /* toggle randomly selected bit in chromosome */ unsigned flip_bit = rand() % (sizeof(CHROMOSOME) * 8); return (~chr & (0x01 << flip_bit)) | (chr & ~(0x01 << flip_bit)); } CHROMOSOME get_parent (POPULATION pop, FITNESS fit_arr[], int size) { /* roulette wheel selection by proportional fitness */ int i, sel_fit, tot_fit = 0; for (i = 0; i < size; tot_fit += fit_arr[i++]); sel_fit = rand() % (tot_fit + 1); for (i = 0, tot_fit = 0; tot_fit < sel_fit; tot_fit += fit_arr[i++]); return pop[i - 1]; } void print_pop (POPULATION pop, int pop_size) { int i, tot_fit = 0; CHROMOSOME best = (CHROMOSOME) 0; for (i = 0; i < pop_size; ++i) { tot_fit += fitness(pop[i]); if (fitness(pop[i]) > fitness(best)) best = pop[i]; printf("%x|", pop[i]); } printf("\n"); printf("Total fitness: %d\n", tot_fit); printf("Best chromosome: %x\tFitness: %d\n", best, fitness(best)); }
Private
[
?
]
Run code
Submit