1 /********************************************************************** 2 ga_core.h 3 ********************************************************************** 4 5 ga_core - Genetic algorithm routines. 6 Copyright ©2000-2005, Stewart Adcock <stewart@linux-domain.com> 7 All rights reserved. 8 9 The latest version of this program should be available at: 10 http://gaul.sourceforge.net/ 11 12 This program is free software; you can redistribute it and/or modify 13 it under the terms of the GNU General Public License as published by 14 the Free Software Foundation; either version 2 of the License, or 15 (at your option) any later version. Alternatively, if your project 16 is incompatible with the GPL, I will probably agree to requests 17 for permission to use the terms of any other license. 18 19 This program is distributed in the hope that it will be useful, but 20 WITHOUT ANY WARRANTY WHATSOEVER. 21 22 A full copy of the GNU General Public License should be in the file 23 "COPYING" provided with this distribution; if not, see: 24 http://www.gnu.org/ 25 26 ********************************************************************** 27 28 Synopsis: Routines for handling populations and performing GA 29 operations. 30 31 **********************************************************************/ 32 33 #ifndef GA_CORE_H_INCLUDED 34 #define GA_CORE_H_INCLUDED 35 36 /* 37 * Includes. 38 */ 39 #include "gaul.h" 40 41 #ifdef HAVE_LIMITS_H 42 #include <limits.h> 43 #endif 44 #include <math.h> 45 #include <sys/types.h> 46 #ifdef HAVE_SYS_WAIT_H 47 #include <sys/wait.h> 48 #endif 49 50 /* 51 * Debugging 52 */ 53 #ifndef GA_DEBUG 54 # ifdef DEBUG 55 # define GA_DEBUG DEBUG 56 # else 57 # define GA_DEBUG 0 58 # endif 59 #endif 60 61 /* 62 * Specification of number of processes used in 63 * multiprocess functions. 64 */ 65 #ifndef GA_NUM_PROCESSES_ENVVAR_STRING 66 #define GA_NUM_PROCESSES_ENVVAR_STRING "GAUL_NUM_PROCESSES" 67 #endif 68 69 #ifndef GA_DEFAULT_NUM_PROCESSES 70 #define GA_DEFAULT_NUM_PROCESSES 8 71 #endif 72 73 /* 74 * Specification of number of threads used in 75 * multithreaded functions. 76 */ 77 #ifndef GA_NUM_THREADS_ENVVAR_STRING 78 #define GA_NUM_THREADS_ENVVAR_STRING "GAUL_NUM_THREADS" 79 #endif 80 81 #ifndef GA_DEFAULT_NUM_THREADS 82 #define GA_DEFAULT_NUM_THREADS 4 83 #endif 84 85 /* 86 * Whether simple statistics should be dumped to disk. 87 */ 88 #ifndef GA_WRITE_STATS 89 # if GA_DEBUG > 1 90 # define GA_WRITE_STATS TRUE 91 # else 92 # define GA_WRITE_STATS FALSE 93 # endif 94 #endif 95 96 /* 97 * Include remainder of this library's headers. 98 */ 99 #include "gaul/ga_bitstring.h" 100 #include "gaul/ga_chromo.h" 101 #include "gaul/ga_climbing.h" 102 #include "gaul/ga_de.h" 103 #include "gaul/ga_deterministiccrowding.h" 104 #include "gaul/ga_gradient.h" 105 #include "gaul/ga_optim.h" 106 #include "gaul/ga_qsort.h" 107 #include "gaul/ga_randomsearch.h" 108 #include "gaul/ga_sa.h" 109 #include "gaul/ga_similarity.h" 110 #include "gaul/ga_systematicsearch.h" 111 #include "gaul/ga_simplex.h" 112 #include "gaul/ga_tabu.h" 113 114 /* 115 * Compilation constants. 116 */ 117 #define GA_BOLTZMANN_FACTOR (1.38066e-23) 118 #define GA_TINY_DOUBLE (1.0e-9) 119 120 /* 121 * MPI message tags. 122 */ 123 #define GA_TAG_NULL 0 124 125 #define GA_TAG_NUMENTITIES 101 126 #define GA_TAG_ENTITYLEN 102 127 #define GA_TAG_ENTITYFITNESS 103 128 #define GA_TAG_ENTITYCHROMOSOME 104 129 130 #define GA_TAG_POPSTABLESIZE 201 131 #define GA_TAG_POPCROSSOVER 202 132 #define GA_TAG_POPMUTATION 203 133 #define GA_TAG_POPMIGRATION 204 134 #define GA_TAG_POPALLELEMUTPROB 205 135 #define GA_TAG_POPALLELEMININT 206 136 #define GA_TAG_POPALLELEMAXINT 207 137 #define GA_TAG_POPALLELEMINDOUBLE 208 138 #define GA_TAG_POPALLELEMAXDOUBLE 209 139 140 /* 141 * Entity Structure. 142 * 143 * FIXME: Make opaque i.e. move definition into ga_core.c 144 * Should encourage the use of accessor functions rather than directly tweaking 145 * the values in this structure manually. 146 */ 147 struct entity_t 148 { 149 double fitness; /* Fitness score. */ 150 vpointer *chromosome; /* The chromosomes (the genotype). */ 151 vpointer data; /* User data containing physical properties. (the phenotype) */ 152 }; 153 154 /* 155 * Tabu-search parameter structure. 156 */ 157 typedef struct 158 { 159 int list_length; /* Length of the tabu-list. */ 160 int search_count; /* Number of local searches initiated at each iteration. */ 161 GAtabu_accept tabu_accept; /* Acceptance function. */ 162 } ga_tabu_t; 163 164 /* 165 * Simulated Annealling search parameter structure. 166 */ 167 typedef struct 168 { 169 double initial_temp; /* Initial temperature. */ 170 double final_temp; /* Final temperature. */ 171 double temp_step; /* Increment of temperature updates. */ 172 int temp_freq; /* Frequency for temperature updates. 173 * (Or, -1 for smooth transition between Ti and Tf) */ 174 double temperature; /* Current temperature. */ 175 GAsa_accept sa_accept; /* Acceptance criterion function. */ 176 } ga_sa_t; 177 178 /* 179 * Hill climbing parameter structure. 180 */ 181 typedef struct 182 { 183 GAmutate_allele mutate_allele; /* Allele mutation function. */ 184 } ga_climbing_t; 185 186 /* 187 * Simplex parameter structure. 188 */ 189 typedef struct 190 { 191 int dimensions; /* Size of double array. */ 192 double alpha; /* (range: 0=no extrap, 1=unit step extrap, higher OK.) */ 193 double beta; /* (range: 0=no contraction, 1=full contraction.) */ 194 double gamma; /* (range: 0=no contraction, 1=full contraction.) */ 195 double step; /* Initial randomisation step (range: >0, 1=unit step randomisation, higher OK.) */ 196 GAto_double to_double; /* Convert chromosome to double array. */ 197 GAfrom_double from_double; /* Convert chromosome from double array. */ 198 } ga_simplex_t; 199 200 /* 201 * Deterministic crowding parameter structure. 202 */ 203 typedef struct 204 { 205 GAcompare compare; /* Compare two entities (either genomic or phenomic space). */ 206 } ga_dc_t; 207 208 /* 209 * Differential evolution parameter structure. 210 */ 211 typedef struct 212 { 213 ga_de_strategy_type strategy; /* Selection strategy. */ 214 ga_de_crossover_type crossover_method; /* Crossover strategy. */ 215 int num_perturbed; /* Number to perturb. */ 216 double crossover_factor; /* Crossover ratio. */ 217 double weighting_min; /* Minimum crossover weighting factor. */ 218 double weighting_max; /* Maximum crossover weighting factor. */ 219 } ga_de_t; 220 221 /* 222 * Gradient methods parameter structure. 223 */ 224 typedef struct 225 { 226 int dimensions; /* Size of double array. */ 227 double step_size; /* Step size, (or initial step size). */ 228 double alpha; /* Step size scale-down factor. */ 229 double beta; /* Step size scale-up factor. */ 230 GAto_double to_double; /* Convert chromosome to double array. */ 231 GAfrom_double from_double; /* Convert chromosome from double array. */ 232 GAgradient gradient; /* Return gradients array. */ 233 } ga_gradient_t; 234 235 /* 236 * Systematic search parameter structure. 237 */ 238 typedef struct 239 { 240 GAscan_chromosome scan_chromosome; /* Allele searching function. */ 241 int chromosome_state; /* Permutation counter. */ 242 int allele_state; /* Permutation counter. */ 243 } ga_search_t; 244 245 /* 246 * Probabilistic sampling parameter structure. 247 */ 248 typedef struct 249 { 250 int **num_states; /* Number of states for each allele. */ 251 } ga_sampling_t; 252 253 /* 254 * Internal state values for built-in selection operators. 255 * Currently used for roulette wheel and SUS selection routines. 256 */ 257 typedef struct 258 { 259 double mean, stddev, sum; /* Fitness statistics. */ 260 double current_expval; /* Total of expectancy values. */ 261 double minval; /* Worst fitness value. */ 262 double step; /* Distance between each pointer. */ 263 double offset1, offset2; /* Current pointer offsets. */ 264 int marker; /* The roulette wheel marker. */ 265 int num_to_select; /* Number of individuals to select. */ 266 int current1, current2; /* Currently selected individuals. */ 267 int *permutation; /* Randomly ordered indices. */ 268 } ga_selectdata_t; 269 270 271 /* 272 * Population Structure. 273 * 274 * FIXME: Make opaque. (I have already written the accessor functions.) 275 * IMPORTANT NOTE: If you really must iterate over all entities in 276 * a population in external code, loop over entity_iarray... NOT entity_array. 277 */ 278 struct population_t 279 { 280 int max_size; /* Current maximum population size. */ 281 int stable_size; /* Requested population size. */ 282 int size; /* Actual population size. */ 283 int orig_size; /* Number of parents (entities at start of generation). */ 284 int island; /* Population's island. */ 285 int free_index; /* Next potentially free entity index. */ 286 int generation; /* For ga_population_get_generation(). */ 287 288 MemChunk *entity_chunk; /* Buffer for entity structures. */ 289 entity **entity_array; /* The population in id order. */ 290 entity **entity_iarray; /* The population sorted by fitness. */ 291 292 int num_chromosomes; /* Number of chromosomes in genotype. FIXME: should be an array of lengths. */ 293 int len_chromosomes; /* Maximum length of each chromosome. */ 294 295 vpointer data; /* User data. */ 296 297 int select_state; /* Available to selection algorithms. */ 298 ga_selectdata_t selectdata; /* State values for built-in selection operators. */ 299 300 /* 301 * Special parameters for particular built-in GA operators. 302 * FIXME: I don't like how this is currently implemented; need a more 303 * elegant approach. 304 */ 305 int allele_min_integer, allele_max_integer; /* Range for "integer" alleles. */ 306 double allele_min_double, allele_max_double; /* Range for "double" alleles. */ 307 308 /* 309 * Evolutionary parameters. 310 */ 311 double crossover_ratio; /* Chance for crossover. */ 312 double mutation_ratio; /* Chance for mutation. */ 313 double migration_ratio; /* Chance for migration. */ 314 ga_scheme_type scheme; /* Evolutionary scheme. */ 315 ga_elitism_type elitism; /* Elitism mode. */ 316 317 /* 318 * Special (aka miscellaneous) parameters. 319 */ 320 double allele_mutation_prob; /* Chance for individual alleles to mutate in certain mutation operators. */ 321 322 /* 323 * Non-evolutionary parameters. 324 */ 325 ga_tabu_t *tabu_params; /* Parameters for tabu-search. */ 326 ga_sa_t *sa_params; /* Parameters for simulated annealling. */ 327 ga_climbing_t *climbing_params; /* Parameters for hill climbing. */ 328 ga_simplex_t *simplex_params; /* Parameters for simplex search. */ 329 ga_dc_t *dc_params; /* Parameters for deterministic crowding. */ 330 ga_de_t *de_params; /* Parameters for differential evolution. */ 331 ga_gradient_t *gradient_params; /* Parameters for gradient methods. */ 332 ga_search_t *search_params; /* Parameters for systematic search. */ 333 ga_sampling_t *sampling_params; /* Parameters for probabilistic sampling. */ 334 335 /* 336 * The scoring function and the other callbacks are defined here. 337 */ 338 GAgeneration_hook generation_hook; 339 GAiteration_hook iteration_hook; 340 341 GAdata_destructor data_destructor; 342 GAdata_ref_incrementor data_ref_incrementor; 343 344 GAchromosome_constructor chromosome_constructor; 345 GAchromosome_destructor chromosome_destructor; 346 GAchromosome_replicate chromosome_replicate; 347 GAchromosome_to_bytes chromosome_to_bytes; 348 GAchromosome_from_bytes chromosome_from_bytes; 349 GAchromosome_to_string chromosome_to_string; 350 351 GAevaluate evaluate; 352 GAseed seed; 353 GAadapt adapt; 354 GAselect_one select_one; 355 GAselect_two select_two; 356 GAmutate mutate; 357 GAcrossover crossover; 358 GAreplace replace; 359 GArank rank; 360 361 /* 362 * Memory handling. 363 */ 364 #if USE_CHROMO_CHUNKS == 1 365 MemChunk *chromoarray_chunk; 366 MemChunk *chromo_chunk; 367 #endif 368 369 /* 370 * Execution locks. 371 */ 372 THREAD_LOCK_DECLARE(lock); 373 #if USE_CHROMO_CHUNKS == 1 374 THREAD_LOCK_DECLARE(chromo_chunk_lock); 375 #endif 376 }; 377 378 /* 379 * Constant definitions. 380 */ 381 382 /* Define lower bound on fitness. */ 383 #define GA_MIN_FITNESS -DBL_MAX 384 385 /* 386 * Define some default values. 387 */ 388 #define GA_DEFAULT_CROSSOVER_RATIO 0.9 389 #define GA_DEFAULT_MUTATION_RATIO 0.1 390 #define GA_DEFAULT_MIGRATION_RATIO 0.1 391 392 /* 393 * Define chance of any given allele being mutated in one mutation 394 * operation (only for certain mutation functions). 395 */ 396 #define GA_DEFAULT_ALLELE_MUTATION_PROB 0.02 397 398 /* 399 * A private prototype. 400 */ 401 boolean gaul_population_fill(population *pop, int num); 402 403 #endif /* GA_CORE_H_INCLUDED */ 404 405