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   /* Optional serialization */
  92   pi_serialize_f serialize;
  93   pi_unserialize_f unserialize;
  94
  95   individual_t fittest;
  96
  97   individual_t *individuals;
  98   size_t individuals_num;
  99 };
 100
 101 /*
 102  * Constructor and destructor
 103  */
 104 population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
 105     pi_free_f f)
 106 {
 107   population_t *p;
 108   size_t i;
 109
 110   p = (population_t *) malloc (sizeof (population_t));
 111   if (p == NULL)
 112     return (NULL);
 113
 114   memset (p, 0, sizeof (*p));
 115   pthread_mutex_init (&p->lock, /* attr = */ NULL);
 116
 117   p->rate = rate;
 118   p->copy = copy;
 119   p->free = f;
 120
 121   p->fittest.ptr = NULL;
 122   p->fittest.rating = -1;
 123
 124   p->individuals = malloc (32 * sizeof (p->individuals[0]));
 125   if (p->individuals == NULL)
 126   {
 127     free (p);
 128     return (NULL);
 129   }
 130   memset (p->individuals, 0, 32 * sizeof (p->individuals[0]));
 131   p->individuals_num = 32;
 132
 133   for (i = 0; i < p->individuals_num; i++)
 134   {
 135     p->individuals[i].ptr = NULL;
 136     p->individuals[i].rating = -1;
 137   }
 138
 139   return (p);
 140 } /* }}} population_t *population_create */
 141
 142 void population_destroy (population_t *p) /* {{{ */
 143 {
 144   if (p == NULL)
 145     return;
 146
 147   if (p->fittest.ptr != NULL)
 148     p->free (p->fittest.ptr);
 149   p->fittest.ptr = NULL;
 150   p->fittest.rating = -1;
 151
 152   if (p->individuals_num > 0)
 153   {
 154     size_t i;
 155
 156     for (i = 0; i < p->individuals_num; i++)
 157     {
 158       if (p->individuals[i].ptr != NULL)
 159         p->free (p->individuals[i].ptr);
 160       p->individuals[i].ptr = NULL;
 161       p->individuals[i].rating = -1;
 162     }
 163
 164     free (p->individuals);
 165     p->individuals = NULL;
 166     p->individuals_num = 0;
 167   }
 168
 169   memset (p, 0, sizeof (*p));
 170   free (p);
 171 } /* }}} void population_destroy */
 172
 173 int population_set_size (population_t *p, /* {{{ */
 174     size_t population_size)
 175 {
 176   size_t i;
 177   individual_t *temp;
 178
 179   if (p == NULL)
 180     return (-1);
 181
 182   pthread_mutex_lock (&p->lock);
 183
 184   if (p->individuals_num == population_size)
 185   {
 186     pthread_mutex_unlock (&p->lock);
 187     return (0);
 188   }
 189
 190   for (i = population_size; i < p->individuals_num; i++)
 191   {
 192     p->free (p->individuals[i].ptr);
 193     p->individuals[i].ptr = NULL;
 194     p->individuals[i].rating = -1;
 195   }
 196
 197   temp = (individual_t *) realloc (p->individuals,
 198       population_size * sizeof (p->individuals[0]));
 199   if (temp == NULL)
 200   {
 201     pthread_mutex_unlock (&p->lock);
 202     return (-1);
 203   }
 204   p->individuals = temp;
 205
 206   for (i = p->individuals_num; i < population_size; i++)
 207   {
 208     p->individuals[i].ptr = NULL;
 209     p->individuals[i].rating = -1;
 210   }
 211
 212   p->individuals_num = population_size;
 213
 214   pthread_mutex_unlock (&p->lock);
 215
 216   return (0);
 217 } /* }}} */
 218
 219 int population_set_serialization (population_t *p,
 220     pi_serialize_f serialize, pi_unserialize_f unserialize) /* {{{ */
 221 {
 222   if (p == NULL)
 223     return (-1);
 224
 225   pthread_mutex_lock (&p->lock);
 226
 227   p->serialize = serialize;
 228   p->unserialize = unserialize;
 229
 230   pthread_mutex_unlock (&p->lock);
 231   return (0);
 232 } /* }}} int population_set_serialization */
 233
 234 void *population_get_random (population_t *p) /* {{{ */
 235 {
 236   void *ret = NULL;
 237   size_t i;
 238
 239   pthread_mutex_lock (&p->lock);
 240
 241   if (p->individuals_num < 1)
 242   {
 243     pthread_mutex_unlock (&p->lock);
 244     return (NULL);
 245   }
 246
 247   while (ret == NULL)
 248   {
 249     i = (size_t) (((double) p->individuals_num)
 250         * (rand() / (RAND_MAX + 1.0)));
 251     if (p->individuals[i].ptr == NULL)
 252       continue;
 253
 254     ret = p->copy (p->individuals[i].ptr);
 255   }
 256
 257   pthread_mutex_unlock (&p->lock);
 258
 259   return (ret);
 260 } /* }}} void *population_pick_random */
 261
 262 void *population_get_fittest (population_t *p) /* {{{ */
 263 {
 264   void *ret = NULL;
 265
 266   if (p == NULL)
 267     return (NULL);
 268
 269   pthread_mutex_lock (&p->lock);
 270
 271   if (p->fittest.ptr == NULL)
 272   {
 273     pthread_mutex_unlock (&p->lock);
 274     return (NULL);
 275   }
 276
 277   ret = p->copy (p->fittest.ptr);
 278
 279   pthread_mutex_unlock (&p->lock);
 280
 281   return (ret);
 282 } /* }}} void *population_get_fittest */
 283
 284 int population_insert (population_t *p, void *pi_orig) /* {{{ */
 285 {
 286   void *pi;
 287   int pi_rating;
 288   int num_tries;
 289   int i;
 290
 291   if (p == NULL)
 292     return (-1);
 293
 294   if (pi_orig == NULL)
 295     return (-1);
 296
 297   pi = p->copy (pi_orig);
 298   if (pi == NULL)
 299   {
 300     fprintf (stderr, "population_insert: p->copy failed.\n");
 301     return (-1);
 302   }
 303
 304   pi_rating = p->rate (pi);
 305
 306   pthread_mutex_lock (&p->lock);
 307
 308   /* Keep track of the all time best. */
 309   if ((p->fittest.ptr == NULL) || (p->fittest.rating > pi_rating))
 310   {
 311     void *temp;
 312
 313     temp = p->copy (pi);
 314     if (temp != NULL)
 315     {
 316       if (p->fittest.ptr != NULL)
 317         p->free (p->fittest.ptr);
 318       p->fittest.ptr = temp;
 319       p->fittest.rating = pi_rating;
 320     }
 321   }
 322
 323   if (p->individuals_num <= 0)
 324   {
 325     pthread_mutex_unlock (&p->lock);
 326     p->free (pi);
 327     return (-1);
 328   }
 329
 330   num_tries = (int) ceil (log (p->individuals_num) / log (2.0));
 331   for (i = 0; i < num_tries; i++)
 332   {
 333     size_t j;
 334
 335     j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
 336
 337     if (p->individuals[j].ptr == NULL)
 338     {
 339       p->individuals[j].ptr = pi;
 340       p->individuals[j].rating = pi_rating;
 341       pi = NULL;
 342       break;
 343     }
 344
 345     if (pi_rating < p->individuals[j].rating)
 346     {
 347       void *temp0;
 348       int temp1;
 349
 350       temp0 = p->individuals[j].ptr;
 351       p->individuals[j].ptr = pi;
 352       pi = temp0;
 353
 354       temp1 = p->individuals[j].rating;
 355       p->individuals[j].rating = pi_rating;
 356       pi_rating = temp1;
 357     }
 358   }
 359
 360   pthread_mutex_unlock (&p->lock);
 361
 362   if (pi != NULL)
 363   {
 364     p->free (pi);
 365     pi = NULL;
 366   }
 367
 368   return (0);
 369 } /* }}} int population_insert */
 370
 371 /* vim: set sw=2 sts=2 et fdm=marker : */
 372