libfgen  0.1.15
Library for optimization using a genetic algorithm or particle swarm optimization
ga.c
00001 /*
00002     ga.c -- main module of the genetic algorithm implementation.
00003 
00004     fgen -- Library for optimization using a genetic algorithm or particle swarm optimization.
00005     Copyright 2012-13, Harm Hanemaaijer <fgenfb at yahoo.com>
00006 
00007     This file is part of fgen.
00008 
00009     fgen is free software: you can redistribute it and/or modify it
00010     under the terms of the GNU Lesser General Public License as published
00011     by the Free Software Foundation, either version 3 of the License, or
00012     (at your option) any later version.
00013 
00014     fgen is distributed in the hope that it will be useful, but WITHOUT
00015     ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00016     FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
00017     License for more details.
00018 
00019     You should have received a copy of the GNU Lesser General Public
00020     License along with fgen.  If not, see <http://www.gnu.org/licenses/>.
00021 
00022 */
00023 
00024 /*
00025  * This file contains the main module of the program; it controls the
00026  * high-level flow of the genetic algorithm.
00027  */
00028 
00095 #include <stdlib.h>
00096 #include <stdio.h>
00097 #ifdef __GNUC__
00098 #include <unistd.h>
00099 #endif
00100 #include <math.h>
00101 #include <limits.h>
00102 #include <float.h>
00103 #include <pthread.h>
00104 #include "fgen.h"
00105 #include "parameters.h"
00106 #include "population.h"
00107 #include "selection.h"
00108 #include "crossover.h"
00109 #include "mutation.h"
00110 #include "random.h"
00111 #include "cache.h"
00112 #include "migration.h"
00113 #include "win32_compat.h"
00114 
00144 FgenPopulation *fgen_create(int population_size, int individual_size_in_bits, int data_element_size,
00145 FgenGenerationCallbackFunc fgen_generation_callback_func, FgenCalculateFitnessFunc fgen_calculate_fitness_func,
00146 FgenSeedFunc fgen_seed_func, FgenMutationFunc fgen_mutation_func, FgenCrossoverFunc fgen_crossover_func) {
00147         FgenPopulation *pop = (FgenPopulation *)malloc(sizeof(FgenPopulation));
00148         fgen_initialize(pop, population_size, individual_size_in_bits, data_element_size,
00149                 fgen_generation_callback_func, fgen_calculate_fitness_func, fgen_seed_func,
00150                 fgen_mutation_func, fgen_crossover_func);
00151         return pop;
00152 }
00153 
00171 void fgen_initialize(FgenPopulation *pop, int population_size, int individual_size_in_bits,
00172 int data_element_size, FgenGenerationCallbackFunc fgen_generation_callback_func, FgenCalculateFitnessFunc
00173 fgen_calculate_fitness_func, FgenSeedFunc fgen_seed_func, FgenMutationFunc fgen_mutation_func, FgenCrossoverFunc
00174 fgen_crossover_func) {
00175         pop->size = population_size;
00176         pop->individual_size_in_bits = individual_size_in_bits;
00177         pop->data_element_size = data_element_size;
00178         pop->fgen_generation_callback_func = fgen_generation_callback_func;
00179         pop->fgen_calculate_fitness_func = fgen_calculate_fitness_func;
00180         pop->fgen_seed_func = fgen_seed_func;
00181         pop->fgen_mutation_func = fgen_mutation_func;
00182         pop->fgen_crossover_func = fgen_crossover_func;
00183         pop->cache = NULL;
00184         pop->rng = fgen_random_create_rng();
00185         pop->migration_probability = 0;
00186         pop->migration_probability_float = 0;
00187         pop->migration_interval = 1;
00188         fgen_set_tournament_size(pop, DEFAULT_TOURNAMENT_SIZE);
00189         if (pop->size < 64)
00190                 fgen_set_number_of_elites(pop, 1);
00191         else
00192                 fgen_set_number_of_elites(pop, pop->size / 64);
00193         pop->generation_callback_interval = 1;
00194         pop->fast_mutation_cumulative_chance = NULL;
00195         pop->ind = NULL;
00196         pop->initialization_type = FGEN_INITIALIZATION_SEED;
00197 }
00198 
00212 void fgen_set_parameters(FgenPopulation *pop, int selection_type, int selection_fitness_type,
00213 float crossover_probability_float, float mutation_probability_float, float macro_mutation_probability_float) {
00214         pop->selection_type = selection_type;
00215         pop->selection_fitness_type = selection_fitness_type;
00216         fgen_set_crossover_probability(pop, crossover_probability_float);
00217         fgen_set_mutation_probability(pop, mutation_probability_float);
00218         fgen_set_macro_mutation_probability(pop, macro_mutation_probability_float);
00219 }
00220 
00233 void fgen_run(FgenPopulation *pop, int max_generation) {
00234         CreateInitialPopulation(pop);
00235 
00236         pop->generation = 0;
00237         pop->stop_signalled = 0;
00238         pop->fgen_generation_callback_func(pop, pop->generation);
00239         if (pop->stop_signalled)
00240                 goto end;
00241 
00242         for (;;) {
00243 
00244                 DoSelection(pop);
00245 
00246                 DoCrossover(pop);
00247 
00248                 DoMutation(pop);
00249 
00250                 pop->generation++;
00251                 if (pop->generation % pop->generation_callback_interval == 0)
00252                         pop->fgen_generation_callback_func(pop, pop->generation);
00253                 if ((max_generation != - 1 && pop->generation >= max_generation) || pop->stop_signalled)
00254                         break;
00255         }
00256 end :
00257         CalculatePopulationFitness(pop, NULL, NULL);
00258 }
00259 
00267 void fgen_destroy(FgenPopulation *pop) {
00268         if (pop->fast_mutation_cumulative_chance != NULL)
00269                 free(pop->fast_mutation_cumulative_chance);
00270         if (pop->cache != NULL)
00271                 DestroyCache(pop);
00272         fgen_random_destroy_rng(pop->rng);
00273         if (pop->ind != NULL) {
00274                 FreePopulation(pop, pop->ind);
00275                 free(pop->ind);
00276         }
00277         free(pop);
00278 }
00279 
00287 void fgen_signal_stop(FgenPopulation *pop) {
00288         pop->stop_signalled = 1;
00289 }
00290 
00304 void fgen_run_threaded(FgenPopulation *pop, int max_generation) {
00305 //      RandomInformCommonRange(pop->individual_size_in_bits);
00306 //      RandomInformCommonRange(pop->individual_size_in_bits / pop->data_element_size);
00307 //      RandomInformCommonRange(pop->size);
00308 #if defined(__GNUC__) && !defined(_WIN32)
00309         pop->max_threads = sysconf(_SC_NPROCESSORS_ONLN);
00310 #else
00311         pop->max_threads = 4;
00312 #endif
00313 //      printf("fgen: number of CPU cores detected = %d.\n", pop->max_threads);
00314 
00315         CreateInitialPopulation(pop);
00316         CalculatePopulationFitnessThreaded(pop);
00317 
00318         pop->generation = 0;
00319         pop->stop_signalled = 0;
00320         pop->fgen_generation_callback_func(pop, pop->generation);
00321         if (pop->stop_signalled)
00322                 goto end;
00323 
00324         for (;;) {
00325 
00326                 DoSelection(pop);
00327 
00328                 DoCrossover(pop);
00329 
00330                 DoMutation(pop);
00331 
00332                 /* The best we can do is to force the fitness of the population to be precalculated */
00333                 /* with concurrency. */
00334                 CalculatePopulationFitnessThreaded(pop);
00335 
00336                 pop->generation++;
00337                 if (pop->generation % pop->generation_callback_interval == 0)
00338                         pop->fgen_generation_callback_func(pop, pop->generation);
00339                 if ((max_generation != - 1 && pop->generation >= max_generation) || pop->stop_signalled)
00340                         break;
00341         }
00342 end : ;
00343 }
00344 
00345 
00359 void fgen_run_archipelago(int nu_pops, FgenPopulation **pops, int max_generation) {
00360         int i;
00361         /* Randomize the seeds of the random number generators of the populations after */
00362         /* the first one based on random number from the first random number generator. */
00363         for (i = 1; i < nu_pops; i++)
00364                 fgen_random_seed_rng(pops[i]->rng, fgen_random_32(pops[0]->rng));
00365 
00366         for (i = 0; i < nu_pops; i++) {
00367                 CreateInitialPopulation(pops[i]);
00368                 pops[i]->generation = 0;
00369                 pops[i]->stop_signalled = 0;
00370                 pops[i]->island = i;
00371                 pops[i]->fgen_generation_callback_func(pops[i], pops[i]->generation);
00372         }
00373         for (i = 0; i < nu_pops; i++)
00374                 if (pops[i]->stop_signalled)
00375                         goto end;
00376 
00377         for (;;) {
00378                 for (i = 0; i < nu_pops; i++) {
00379                         DoSelection(pops[i]);
00380 
00381                         DoCrossover(pops[i]);
00382 
00383                         DoMutation(pops[i]);
00384 
00385                         pops[i]->generation++;
00386                 }
00387 
00388                 if (pops[0]->migration_interval != 0)
00389                         if (pops[0]->generation % pops[0]->migration_interval == 0)
00390                                 DoMigration(nu_pops, pops);
00391 
00392                 for (i = 0; i < nu_pops; i++)
00393                         if (pops[i]->generation % pops[i]->generation_callback_interval == 0)
00394                                 pops[i]->fgen_generation_callback_func(pops[i], pops[i]->generation);
00395                 for (i = 0; i < nu_pops; i++)
00396                         if ((max_generation != - 1 && pops[i]->generation >= max_generation) || pops[i]->stop_signalled)
00397                                 goto end;
00398         }
00399 end :
00400         for (i = 0 ; i < nu_pops; i++)
00401                 CalculatePopulationFitness(pops[i], NULL, NULL);
00402 }
00403 
00404 /* Threaded archipelago. */
00405 
00406 static void *fgen_create_initial_population_thread(void *threadarg) {
00407         FgenPopulation *pop = (FgenPopulation *)threadarg;
00408         CreateInitialPopulation(pop);
00409         CalculatePopulationFitness(pop, NULL, NULL);
00410         pthread_exit(NULL);
00411         return NULL;
00412 }
00413 
00414 typedef struct {
00415         FgenPopulation *pop;
00416         int nu_generations;
00417         pthread_cond_t *condition_ready;
00418         pthread_cond_t *condition_start;
00419         pthread_cond_t *condition_end;
00420         pthread_cond_t *condition_continue;
00421         pthread_mutex_t *mutex_ready;
00422         pthread_mutex_t *mutex_start;
00423         pthread_mutex_t *mutex_end;
00424         pthread_mutex_t *mutex_continue;
00425         int *ready_signalled_count;
00426         int *start_signalled;
00427         int *end_signalled_count;
00428         int *continue_signalled;
00429 } ThreadData;
00430 
00431 static void *fgen_do_multiple_generations_cond_thread(void *threadarg) {
00432         ThreadData *thread_data = (ThreadData *)threadarg;
00433         FgenPopulation *pop = thread_data->pop;
00434         for (;;) {
00435                 int nu_generations;
00436                 int i;
00437                 /* Give the ready signal. */
00438                 pthread_mutex_lock(thread_data->mutex_ready);
00439                 (*thread_data->ready_signalled_count)++;
00440                 pthread_cond_signal(thread_data->condition_ready);
00441                 pthread_mutex_unlock(thread_data->mutex_ready);
00442                 /* Wait for the start signal. */
00443                 pthread_mutex_lock(thread_data->mutex_start);
00444                 while (!(*thread_data->start_signalled))
00445                         pthread_cond_wait(thread_data->condition_start, thread_data->mutex_start);
00446                 pthread_mutex_unlock(thread_data->mutex_start);
00447                 /* Do the work. */
00448                 nu_generations = thread_data->nu_generations;
00449                 if (nu_generations == 0)
00450                         pthread_exit(NULL);
00451                 i = 0;
00452                 for (i = 0; i < nu_generations; i++) {
00453                         DoSelection(pop);
00454                         /* If there is an individual with infinite fitness, DoSelection will leave it as the */
00455                         /* first individual. Make use of this to skip multiple generations if this is the case. */
00456                         if (pop->ind[0]->fitness == POSITIVE_INFINITY_DOUBLE) {
00457                                 pop->generation += nu_generations - i;
00458                                 break;
00459                         }
00460                         DoCrossover(pop);
00461                         DoMutation(pop);
00462                         pop->generation++;
00463                 }
00464                 /* Take advantage of the multiple threads to update the fitness now, instead of */
00465                 /* later in single-threaded mode. */
00466                 CalculatePopulationFitness(pop, NULL, NULL);
00467                 /* Signal the end of the work. */
00468                 pthread_mutex_lock(thread_data->mutex_end);
00469                 (*thread_data->end_signalled_count)++;
00470                 pthread_cond_signal(thread_data->condition_end);
00471                 pthread_mutex_unlock(thread_data->mutex_end);
00472                 /* Wait for the continue signal. */
00473                 pthread_mutex_lock(thread_data->mutex_continue);
00474                 while (!(*thread_data->continue_signalled))
00475                         pthread_cond_wait(thread_data->condition_continue, thread_data->mutex_continue);
00476                 pthread_mutex_unlock(thread_data->mutex_continue);
00477         }
00478 }
00479 
00492 void fgen_run_archipelago_threaded(int nu_pops, FgenPopulation **pops, int max_generation) {
00493         int i;
00494         pthread_t *thread;
00495         int max_threads;
00496         ThreadData *thread_data;
00497         pthread_cond_t *condition_ready;
00498         pthread_cond_t *condition_start;
00499         pthread_cond_t *condition_end;
00500         pthread_cond_t *condition_continue;
00501         pthread_mutex_t *mutex_ready;
00502         pthread_mutex_t *mutex_start;
00503         pthread_mutex_t *mutex_end;
00504         pthread_mutex_t *mutex_continue;
00505         int ready_signalled_count;
00506         int *start_signalled;
00507         int end_signalled_count;
00508         int continue_signalled;
00509 
00510         /* Randomize the seeds of the random number generators of the populations after */
00511         /* the first one based on random number from the first random number generator. */
00512         for (i = 1; i < nu_pops; i++)
00513                 fgen_random_seed_rng(pops[i]->rng, fgen_random_32(pops[0]->rng));
00514 
00515         /* In practice, just running a lot of threads seems to be at least as efficient as imposing a maximum */
00516         /* on the amount of concurrently active threads. */
00517 //      max_threads = sysconf(_SC_NPROCESSORS_ONLN);
00518 //      for (i = 0; i < nu_pops; i++)
00519 //              pops[i]->max_threads = max_threads;
00520 //      printf("fgen: number of CPU cores detected = %d.\n", max_threads);
00521         max_threads = nu_pops;
00522 
00523         thread = (pthread_t *)malloc(sizeof(pthread_t) * nu_pops);
00524         thread_data = (ThreadData *)malloc(sizeof(ThreadData) * nu_pops);
00525         condition_ready = (pthread_cond_t *)malloc(sizeof(pthread_cond_t));
00526         condition_start = (pthread_cond_t *)malloc(sizeof(pthread_cond_t) * nu_pops);
00527         condition_end = (pthread_cond_t *)malloc(sizeof(pthread_cond_t));
00528         condition_continue = (pthread_cond_t *)malloc(sizeof(pthread_cond_t));
00529         mutex_ready = (pthread_mutex_t *)malloc(sizeof(pthread_mutex_t));
00530         mutex_start = (pthread_mutex_t *)malloc(sizeof(pthread_mutex_t));
00531         mutex_end = (pthread_mutex_t *)malloc(sizeof(pthread_mutex_t));
00532         mutex_continue = (pthread_mutex_t *)malloc(sizeof(pthread_mutex_t));
00533         start_signalled = (int *)malloc(sizeof(int) * nu_pops);
00534 
00535         /* Create the initial populations and calculate fitness, threaded. */
00536         for (i = 0; i < nu_pops; i++) {
00537                 pops[i]->generation = 0;
00538                 pops[i]->stop_signalled = 0;
00539                 pops[i]->island = i;
00540                 pthread_create(&thread[i], NULL, fgen_create_initial_population_thread, pops[i]);
00541         }
00542         for (i = 0; i < nu_pops; i++)
00543                 pthread_join(thread[i], NULL);
00544         for (i = 0; i < nu_pops; i++)
00545                 pops[i]->fgen_generation_callback_func(pops[i], pops[i]->generation);
00546         for (i = 0; i < nu_pops; i++)
00547                 if (pops[i]->stop_signalled)
00548                         goto end2;
00549 
00550         /* Initialize the condition variables and mutex. */
00551         pthread_cond_init(condition_ready, NULL);
00552         for (i = 0; i < nu_pops; i++)
00553                 pthread_cond_init(&condition_start[i], NULL);
00554         pthread_cond_init(condition_end, NULL);
00555         pthread_cond_init(condition_continue, NULL);
00556         pthread_mutex_init(mutex_ready, NULL);
00557         pthread_mutex_init(mutex_start, NULL);
00558         pthread_mutex_init(mutex_end, NULL);
00559         pthread_mutex_init(mutex_continue, NULL);
00560 
00561         /* Create a worker thread for each island. */
00562         ready_signalled_count = 0;
00563         for (i = 0; i < nu_pops; i++) {
00564                 start_signalled[i] = 0;
00565                 thread_data[i].pop = pops[i];
00566                 thread_data[i].condition_ready = condition_ready;
00567                 thread_data[i].condition_start = &condition_start[i];
00568                 thread_data[i].condition_end = condition_end;
00569                 thread_data[i].condition_continue = condition_continue;
00570                 thread_data[i].mutex_ready = mutex_ready;
00571                 thread_data[i].mutex_start = mutex_start;
00572                 thread_data[i].mutex_end = mutex_end;
00573                 thread_data[i].mutex_continue = mutex_continue;
00574                 thread_data[i].ready_signalled_count = &ready_signalled_count;
00575                 thread_data[i].start_signalled = &start_signalled[i];
00576                 thread_data[i].end_signalled_count = &end_signalled_count;
00577                 thread_data[i].continue_signalled = &continue_signalled;
00578                 pthread_create(&thread[i], NULL, fgen_do_multiple_generations_cond_thread,
00579                         &thread_data[i]);
00580         }
00581 
00582         for (;;) {
00583                 int nu_generations_to_run;
00584                 int starting_thread;
00585 
00586                 /* Figure out how many generations can be run without having to call the generation */
00587                 /* callback function or do migration, and then run them concurrently. */
00588                 if (max_generation == - 1)
00589                         nu_generations_to_run = INT_MAX - pops[0]->generation;
00590                 else
00591                         nu_generations_to_run = max_generation - pops[0]->generation;
00592                 for (i = pops[0]->generation + 1; i < pops[0]->generation + nu_generations_to_run; i++)
00593                         if ((pops[0]->migration_interval != 0 && i % pops[0]->migration_interval == 0) ||
00594                         i % pops[0]->generation_callback_interval == 0) {
00595                                 nu_generations_to_run = i - pops[0]->generation;
00596                                 break;
00597                         }
00598 
00599                 /* Check whether all the workers are ready. */
00600                 pthread_mutex_lock(mutex_ready);
00601                 while (ready_signalled_count < nu_pops) {
00602                         pthread_cond_wait(condition_ready, mutex_ready);
00603                 }
00604                 pthread_mutex_unlock(mutex_ready);
00605                 ready_signalled_count = 0;
00606                 continue_signalled = 0;
00607 
00608                 /* Run max_threads concurrent threads. Of the nu_pops threads, only allow max_threads to be */
00609                 /* active at the same time. */
00610                 for (starting_thread = 0; starting_thread < nu_pops; starting_thread += max_threads) {
00611                         /* Calculate the number of active threads. */
00612                         int nu_threads = max_threads;
00613                         if (starting_thread + max_threads > nu_pops)
00614                                 nu_threads = nu_pops - starting_thread;
00615                         /* Activate the worker threads for each selected island. */
00616                         for (i = starting_thread; i < starting_thread + max_threads && i < nu_pops; i++)
00617                                 thread_data[i].nu_generations = nu_generations_to_run;
00618                         end_signalled_count = 0;
00619                         for (i = starting_thread; i < starting_thread + max_threads && i < nu_pops; i++) {
00620                                 pthread_mutex_lock(mutex_start);
00621                                 start_signalled[i] = 1;
00622                                 pthread_cond_signal(&condition_start[i]);
00623                                 pthread_mutex_unlock(mutex_start);
00624                         }
00625 
00626                         /* Wait for all of them to finish. */
00627                         pthread_mutex_lock(mutex_end);
00628                         while (end_signalled_count < nu_threads) {
00629                                 pthread_cond_wait(condition_end, mutex_end);
00630                         }
00631                         pthread_mutex_unlock(mutex_end);
00632         
00633                         for (i = starting_thread; i < starting_thread + max_threads && i < nu_pops; i++)
00634                                 start_signalled[i] = 0;
00635                 }
00636                 /* Give the signal to continue. */
00637                 pthread_mutex_lock(mutex_continue);
00638                 continue_signalled = 1;
00639                 pthread_cond_broadcast(condition_continue);
00640                 pthread_mutex_unlock(mutex_continue);
00641 
00642                 if (pops[0]->migration_interval != 0)
00643                         if (pops[0]->generation % pops[0]->migration_interval == 0)
00644                                 DoMigration(nu_pops, pops);
00645 
00646                 for (i = 0; i < nu_pops; i++) {
00647                         if (pops[i]->generation % pops[i]->generation_callback_interval == 0)
00648                                 pops[i]->fgen_generation_callback_func(pops[i], pops[i]->generation);
00649                 }
00650                 for (i = 0; i < nu_pops; i++)
00651                         if ((max_generation != - 1 && pops[i]->generation >= max_generation) || pops[i]->stop_signalled)
00652                                 goto end;
00653         }
00654 end :
00655         /* Instruct the threads to exit. */
00656         for (i = 0; i < nu_pops; i++)
00657                 thread_data[i].nu_generations = 0;
00658         for (i = 0; i < nu_pops; i++) {
00659                 pthread_mutex_lock(mutex_start);
00660                 start_signalled[i] = 1;
00661                 pthread_cond_signal(&condition_start[i]);
00662                 pthread_mutex_unlock(mutex_start);
00663         }
00664         for (i = 0; i < nu_pops; i++)
00665                 pthread_join(thread[i], NULL);
00666         /* Free all data structures. */
00667         pthread_cond_destroy(condition_ready);
00668         for (i = 0; i < nu_pops; i++)
00669                 pthread_cond_destroy(&condition_start[i]);
00670         pthread_cond_destroy(condition_end);
00671         pthread_cond_destroy(condition_continue);
00672         pthread_mutex_destroy(mutex_ready);
00673         pthread_mutex_destroy(mutex_start);
00674         pthread_mutex_destroy(mutex_end);
00675         pthread_mutex_destroy(mutex_continue);
00676 end2 :
00677         free(thread);
00678         free(thread_data);
00679         free(condition_ready);
00680         free(condition_start);
00681         free(condition_end);
00682         free(condition_continue);
00683         free(mutex_ready);
00684         free(mutex_start);
00685         free(mutex_end);
00686         free(mutex_continue);
00687         free(start_signalled);
00688 }
00689 
00690 
00697 int fgen_get_island(const FgenPopulation *pop) {
00698         return pop->island;
00699 }
00700 
00707 int fgen_is_cached(const FgenPopulation *pop) {
00708         return pop->cache != NULL;
00709 }
00710 
00715 FgenRNG *fgen_get_rng(const FgenPopulation *pop) {
00716         return pop->rng;
00717 }
00718 
00723 int fgen_get_generation(const FgenPopulation *pop) {
00724         return pop->generation;
00725 }
00726 
00727 
 All Data Structures Functions Variables