src/libpopulation.c

   1 /**
   2  * libevolve - src/evolve.c
   3  * Copyright (C) 2008 Florian octo Forster
   4  *
   5  * This program is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License as published by the
   7  * Free Software Foundation; only version 2 of the License is applicable.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License along
  15  * with this program; if not, write to the Free Software Foundation, Inc.,
  16  * 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
  17  *
  18  * Authors:
  19  *   Florian octo Forster <octo at verplant.org>
  20  **/
  21
  22 /*
  23  * First tell the compiler to stick to the C99 and POSIX standards as close as
  24  * possible.
  25  */
  26 #ifndef __STRICT_ANSI__ /* {{{ */
  27 # define __STRICT_ANSI__
  28 #endif
  29
  30 #ifndef _ISOC99_SOURCE
  31 # define _ISOC99_SOURCE
  32 #endif
  33
  34 #ifdef _POSIX_C_SOURCE
  35 # undef _POSIX_C_SOURCE
  36 #endif
  37 #define _POSIX_C_SOURCE 200112L
  38
  39 /* Single UNIX needed for strdup. */
  40 #if 0
  41 #ifdef _XOPEN_SOURCE
  42 # undef _XOPEN_SOURCE
  43 #endif
  44 #define _XOPEN_SOURCE 500
  45 #endif
  46
  47 #ifndef _REENTRANT
  48 # define _REENTRANT
  49 #endif
  50
  51 #ifndef _THREAD_SAFE
  52 # define _THREAD_SAFE
  53 #endif
  54
  55 #ifdef _GNU_SOURCE
  56 # undef _GNU_SOURCE
  57 #endif
  58 /* }}} */
  59
  60 #include "config.h"
  61 #include "population.h"
  62
  63 #include <stdlib.h>
  64 #include <stdint.h>
  65 #include <inttypes.h>
  66 #include <string.h>
  67 #include <stdio.h>
  68 #include <limits.h>
  69 #include <pthread.h>
  70 #include <math.h>
  71
  72 /*
  73  * Data types
  74  */
  75 struct individual_s
  76 {
  77   void *ptr;
  78   int rating;
  79 };
  80 typedef struct individual_s individual_t;
  81
  82 struct population_s
  83 {
  84   pthread_mutex_t lock;
  85
  86   /* Callback functions */
  87   pi_rate_f rate;
  88   pi_free_f free;
  89   pi_copy_f copy;
  90
  91   individual_t fittest;
  92
  93   individual_t *individuals;
  94   size_t individuals_num;
  95 };
  96
  97 /*
  98  * Constructor and destructor
  99  */
 100 population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
 101     pi_free_f f)
 102 {
 103   population_t *p;
 104   size_t i;
 105
 106   p = (population_t *) malloc (sizeof (population_t));
 107   if (p == NULL)
 108     return (NULL);
 109
 110   memset (p, 0, sizeof (*p));
 111   pthread_mutex_init (&p->lock, /* attr = */ NULL);
 112
 113   p->rate = rate;
 114   p->copy = copy;
 115   p->free = f;
 116
 117   p->fittest.ptr = NULL;
 118   p->fittest.rating = -1;
 119
 120   p->individuals = malloc (32 * sizeof (p->individuals[0]));
 121   if (p->individuals == NULL)
 122   {
 123     free (p);
 124     return (NULL);
 125   }
 126   memset (p->individuals, 0, 32 * sizeof (p->individuals[0]));
 127   p->individuals_num = 32;
 128
 129   for (i = 0; i < p->individuals_num; i++)
 130   {
 131     p->individuals[i].ptr = NULL;
 132     p->individuals[i].rating = -1;
 133   }
 134
 135   return (p);
 136 } /* }}} population_t *population_create */
 137
 138 void population_destroy (population_t *p) /* {{{ */
 139 {
 140   if (p == NULL)
 141     return;
 142
 143   if (p->fittest.ptr != NULL)
 144     p->free (p->fittest.ptr);
 145   p->fittest.ptr = NULL;
 146   p->fittest.rating = -1;
 147
 148   if (p->individuals_num > 0)
 149   {
 150     size_t i;
 151
 152     for (i = 0; i < p->individuals_num; i++)
 153     {
 154       if (p->individuals[i].ptr != NULL)
 155         p->free (p->individuals[i].ptr);
 156       p->individuals[i].ptr = NULL;
 157       p->individuals[i].rating = -1;
 158     }
 159
 160     free (p->individuals);
 161     p->individuals = NULL;
 162     p->individuals_num = 0;
 163   }
 164
 165   memset (p, 0, sizeof (*p));
 166   free (p);
 167 } /* }}} void population_destroy */
 168
 169 int population_set_size (population_t *p, /* {{{ */
 170     size_t population_size)
 171 {
 172   size_t i;
 173   individual_t *temp;
 174
 175   if (p == NULL)
 176     return (-1);
 177
 178   pthread_mutex_lock (&p->lock);
 179
 180   if (p->individuals_num == population_size)
 181   {
 182     pthread_mutex_unlock (&p->lock);
 183     return (0);
 184   }
 185
 186   for (i = population_size; i < p->individuals_num; i++)
 187   {
 188     p->free (p->individuals[i].ptr);
 189     p->individuals[i].ptr = NULL;
 190     p->individuals[i].rating = -1;
 191   }
 192
 193   temp = (individual_t *) realloc (p->individuals,
 194       population_size * sizeof (p->individuals[0]));
 195   if (temp == NULL)
 196   {
 197     pthread_mutex_unlock (&p->lock);
 198     return (-1);
 199   }
 200   p->individuals = temp;
 201
 202   for (i = p->individuals_num; i < population_size; i++)
 203   {
 204     p->individuals[i].ptr = NULL;
 205     p->individuals[i].rating = -1;
 206   }
 207
 208   p->individuals_num = population_size;
 209
 210   pthread_mutex_unlock (&p->lock);
 211
 212   return (0);
 213 } /* }}} */
 214
 215 void *population_get_random (population_t *p) /* {{{ */
 216 {
 217   void *ret = NULL;
 218   size_t i;
 219
 220   pthread_mutex_lock (&p->lock);
 221
 222   if (p->individuals_num < 1)
 223   {
 224     pthread_mutex_unlock (&p->lock);
 225     return (NULL);
 226   }
 227
 228   while (ret == NULL)
 229   {
 230     i = (size_t) (((double) p->individuals_num)
 231         * (rand() / (RAND_MAX + 1.0)));
 232     if (p->individuals[i].ptr == NULL)
 233       continue;
 234
 235     ret = p->copy (p->individuals[i].ptr);
 236   }
 237
 238   pthread_mutex_unlock (&p->lock);
 239
 240   return (ret);
 241 } /* }}} void *population_pick_random */
 242
 243 void *population_get_fittest (population_t *p) /* {{{ */
 244 {
 245   void *ret = NULL;
 246
 247   if (p == NULL)
 248     return (NULL);
 249
 250   pthread_mutex_lock (&p->lock);
 251
 252   if (p->fittest.ptr == NULL)
 253   {
 254     pthread_mutex_unlock (&p->lock);
 255     return (NULL);
 256   }
 257
 258   ret = p->copy (p->fittest.ptr);
 259
 260   pthread_mutex_unlock (&p->lock);
 261
 262   return (ret);
 263 } /* }}} void *population_get_fittest */
 264
 265 int population_insert (population_t *p, void *pi_orig) /* {{{ */
 266 {
 267   void *pi;
 268   int pi_rating;
 269   int num_tries;
 270   int i;
 271
 272   if (p == NULL)
 273     return (-1);
 274
 275   if (pi_orig == NULL)
 276     return (-1);
 277
 278   pi = p->copy (pi_orig);
 279   if (pi == NULL)
 280   {
 281     fprintf (stderr, "population_insert: p->copy failed.\n");
 282     return (-1);
 283   }
 284
 285   pi_rating = p->rate (pi);
 286
 287   pthread_mutex_lock (&p->lock);
 288
 289   /* Keep track of the all time best. */
 290   if ((p->fittest.ptr == NULL) || (p->fittest.rating > pi_rating))
 291   {
 292     void *temp;
 293
 294     temp = p->copy (pi);
 295     if (temp != NULL)
 296     {
 297       if (p->fittest.ptr != NULL)
 298         p->free (p->fittest.ptr);
 299       p->fittest.ptr = temp;
 300       p->fittest.rating = pi_rating;
 301     }
 302   }
 303
 304   if (p->individuals_num <= 0)
 305   {
 306     pthread_mutex_unlock (&p->lock);
 307     p->free (pi);
 308     return (-1);
 309   }
 310
 311   num_tries = (int) ceil (log (p->individuals_num) / log (2.0));
 312   for (i = 0; i < num_tries; i++)
 313   {
 314     size_t j;
 315
 316     j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
 317
 318     if (p->individuals[j].ptr == NULL)
 319     {
 320       p->individuals[j].ptr = pi;
 321       p->individuals[j].rating = pi_rating;
 322       pi = NULL;
 323       break;
 324     }
 325
 326     if (pi_rating < p->individuals[j].rating)
 327     {
 328       void *temp0;
 329       int temp1;
 330
 331       temp0 = p->individuals[j].ptr;
 332       p->individuals[j].ptr = pi;
 333       pi = temp0;
 334
 335       temp1 = p->individuals[j].rating;
 336       p->individuals[j].rating = pi_rating;
 337       pi_rating = temp1;
 338     }
 339   }
 340
 341   pthread_mutex_unlock (&p->lock);
 342
 343   if (pi != NULL)
 344   {
 345     p->free (pi);
 346     pi = NULL;
 347   }
 348
 349   return (0);
 350 } /* }}} int population_insert */
 351
 352 /* vim: set sw=2 sts=2 et fdm=marker : */
 353