From: Florian Forster <octo@leeloo.home.verplant.org>
Date: Fri, 11 Jul 2008 15:27:27 +0000 (+0200)
Subject: src/libpopulation.c: Keep track of the fittest individual.
X-Git-Url: https://git.octo.it/?p=libpopulation.git;a=commitdiff_plain;h=fb5eeea19c692eff4feb261a63f23e115a196d2b

src/libpopulation.c: Keep track of the fittest individual.

So that the fittest doesn't _need_ to stay in the population all the
time..
---

diff --git a/src/libpopulation.c b/src/libpopulation.c
index f92e125..f5379a0 100644
--- a/src/libpopulation.c
+++ b/src/libpopulation.c
@@ -72,6 +72,13 @@
 /*
  * Data types
  */
+struct individual_s
+{
+  void *ptr;
+  int rating;
+};
+typedef struct individual_s individual_t;
+
 struct population_s
 {
   pthread_mutex_t lock;
@@ -81,7 +88,9 @@ struct population_s
   pi_free_f free;
   pi_copy_f copy;
 
-  void **individuals;
+  individual_t fittest;
+
+  individual_t *individuals;
   size_t individuals_num;
 };
 
@@ -92,6 +101,7 @@ population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
     pi_free_f f)
 {
   population_t *p;
+  size_t i;
 
   p = (population_t *) malloc (sizeof (population_t));
   if (p == NULL)
@@ -104,15 +114,24 @@ population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
   p->copy = copy;
   p->free = f;
 
-  p->individuals = (void **) malloc (32 * sizeof (void *));
+  p->fittest.ptr = NULL;
+  p->fittest.rating = -1;
+
+  p->individuals = malloc (32 * sizeof (p->individuals[0]));
   if (p->individuals == NULL)
   {
     free (p);
     return (NULL);
   }
-  memset (p->individuals, 0, 32 * sizeof (void *));
+  memset (p->individuals, 0, 32 * sizeof (p->individuals[0]));
   p->individuals_num = 32;
 
+  for (i = 0; i < p->individuals_num; i++)
+  {
+    p->individuals[i].ptr = NULL;
+    p->individuals[i].rating = -1;
+  }
+
   return (p);
 } /* }}} population_t *population_create */
 
@@ -121,14 +140,21 @@ void population_destroy (population_t *p) /* {{{ */
   if (p == NULL)
     return;
 
+  if (p->fittest.ptr != NULL)
+    p->free (p->fittest.ptr);
+  p->fittest.ptr = NULL;
+  p->fittest.rating = -1;
+
   if (p->individuals_num > 0)
   {
     size_t i;
 
     for (i = 0; i < p->individuals_num; i++)
     {
-      p->free (p->individuals[i]);
-      p->individuals[i] = NULL;
+      if (p->individuals[i].ptr != NULL)
+        p->free (p->individuals[i].ptr);
+      p->individuals[i].ptr = NULL;
+      p->individuals[i].rating = -1;
     }
 
     free (p->individuals);
@@ -144,7 +170,7 @@ int population_set_size (population_t *p, /* {{{ */
     size_t population_size)
 {
   size_t i;
-  void **temp;
+  individual_t *temp;
 
   if (p == NULL)
     return (-1);
@@ -159,11 +185,13 @@ int population_set_size (population_t *p, /* {{{ */
 
   for (i = population_size; i < p->individuals_num; i++)
   {
-    p->free (p->individuals[i]);
-    p->individuals[i] = NULL;
+    p->free (p->individuals[i].ptr);
+    p->individuals[i].ptr = NULL;
+    p->individuals[i].rating = -1;
   }
 
-  temp = (void **) realloc (p->individuals, population_size * sizeof (void *));
+  temp = (individual_t *) realloc (p->individuals,
+      population_size * sizeof (p->individuals[0]));
   if (temp == NULL)
   {
     pthread_mutex_unlock (&p->lock);
@@ -172,7 +200,10 @@ int population_set_size (population_t *p, /* {{{ */
   p->individuals = temp;
 
   for (i = p->individuals_num; i < population_size; i++)
-    p->individuals[i] = NULL;
+  {
+    p->individuals[i].ptr = NULL;
+    p->individuals[i].rating = -1;
+  }
 
   p->individuals_num = population_size;
 
@@ -198,10 +229,10 @@ void *population_get_random (population_t *p) /* {{{ */
   {
     i = (size_t) (((double) p->individuals_num)
         * (rand() / (RAND_MAX + 1.0)));
-    if (p->individuals[i] == NULL)
+    if (p->individuals[i].ptr == NULL)
       continue;
 
-    ret = p->copy (p->individuals[i]);
+    ret = p->copy (p->individuals[i].ptr);
   }
 
   pthread_mutex_unlock (&p->lock);
@@ -212,38 +243,20 @@ void *population_get_random (population_t *p) /* {{{ */
 void *population_get_fittest (population_t *p) /* {{{ */
 {
   void *ret = NULL;
-  int best_rating;
-  size_t i;
 
   if (p == NULL)
     return (NULL);
 
   pthread_mutex_lock (&p->lock);
 
-  best_rating = INT_MAX;
-  for (i = 0; i < p->individuals_num; i++)
+  if (p->fittest.ptr == NULL)
   {
-    int rating;
-
-    if (p->individuals[i] == NULL)
-      continue;
-
-    rating = p->rate (p->individuals[i]);
-    if (rating < best_rating)
-    {
-      void *temp;
-
-      temp = p->copy (p->individuals[i]);
-      if (temp != NULL)
-      {
-        if (ret != NULL)
-          p->free (ret);
-        ret = temp;
-        best_rating = rating;
-      }
-    }
+    pthread_mutex_unlock (&p->lock);
+    return (NULL);
   }
 
+  ret = p->copy (p->fittest.ptr);
+
   pthread_mutex_unlock (&p->lock);
 
   return (ret);
@@ -273,6 +286,21 @@ int population_insert (population_t *p, void *pi_orig) /* {{{ */
 
   pthread_mutex_lock (&p->lock);
 
+  /* Keep track of the all time best. */
+  if ((p->fittest.ptr == NULL) || (p->fittest.rating > pi_rating))
+  {
+    void *temp;
+
+    temp = p->copy (pi);
+    if (temp != NULL)
+    {
+      if (p->fittest.ptr != NULL)
+        p->free (p->fittest.ptr);
+      p->fittest.ptr = temp;
+      p->fittest.rating = pi_rating;
+    }
+  }
+
   if (p->individuals_num <= 0)
   {
     pthread_mutex_unlock (&p->lock);
@@ -284,28 +312,29 @@ int population_insert (population_t *p, void *pi_orig) /* {{{ */
   for (i = 0; i < num_tries; i++)
   {
     size_t j;
-    int j_rating;
 
     j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
 
-    if (p->individuals[j] == NULL)
+    if (p->individuals[j].ptr == NULL)
     {
-      p->individuals[j] = pi;
+      p->individuals[j].ptr = pi;
+      p->individuals[j].rating = pi_rating;
       pi = NULL;
       break;
     }
 
-    j_rating = p->rate (p->individuals[j]);
-
-    if (pi_rating < j_rating)
+    if (pi_rating < p->individuals[j].rating)
     {
-      void *temp;
+      void *temp0;
+      int temp1;
 
-      temp = p->individuals[j];
-      p->individuals[j] = pi;
-      pi = temp;
+      temp0 = p->individuals[j].ptr;
+      p->individuals[j].ptr = pi;
+      pi = temp0;
 
-      pi_rating = j_rating;
+      temp1 = p->individuals[j].rating;
+      p->individuals[j].rating = pi_rating;
+      pi_rating = temp1;
     }
   }
 
diff --git a/src/population.h b/src/population.h
index d2cf2be..53cd5c8 100644
--- a/src/population.h
+++ b/src/population.h
@@ -12,6 +12,9 @@ typedef int   (*pi_rate_f) (const void *);
 typedef void *(*pi_copy_f) (const void *);
 typedef void  (*pi_free_f) (void *);
 
+typedef int   (*pi_serialize) (void *, char **, size_t *);
+typedef void *(*pi_unserialize) (char * size_t);
+
 /*
  * (Opaque) data types
  */