2 * libpopulation - src/evolve.c
3 * Copyright (C) 2008,2009 Florian octo Forster
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.
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.
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
19 * Florian octo Forster <octo at verplant.org>
23 * First tell the compiler to stick to the C99 and POSIX standards as close as
26 #ifndef __STRICT_ANSI__ /* {{{ */
27 # define __STRICT_ANSI__
30 #ifndef _ISOC99_SOURCE
31 # define _ISOC99_SOURCE
34 #ifdef _POSIX_C_SOURCE
35 # undef _POSIX_C_SOURCE
37 #define _POSIX_C_SOURCE 200112L
39 /* Single UNIX needed for strdup. */
44 #define _XOPEN_SOURCE 500
61 #include "population.h"
75 #include <sys/types.h>
76 #include <sys/socket.h>
80 #define NETWORK_BUFFER_SIZE 1450
90 typedef struct individual_s individual_t;
96 /* Callback functions */
101 /* Optional serialization */
102 pi_serialize_f serialize;
103 pi_unserialize_f unserialize;
108 #define POPULATION_FLAG_LISTEN 0x01
109 #define POPULATION_FLAG_SHUTDOWN 0x02
110 #define POPULATION_FLAG_EXPLORE 0x10
112 pthread_t listen_thread_id;
114 individual_t fittest;
116 individual_t *individuals;
117 size_t individuals_num;
120 struct listen_thread_args_s
122 population_t *population;
126 typedef struct listen_thread_args_s listen_thread_args_t;
131 static char *population_strdup (const char *src)
139 s = strlen (src) + 1;
140 ret = (char *) malloc (s);
144 memcpy (ret, src, s);
146 } /* char *population_strdup */
148 static int population_send_to_peer (population_t *p, void *pi) /* {{{ */
150 char buffer[NETWORK_BUFFER_SIZE];
165 buffer_size = sizeof (buffer);
166 memset (buffer, 0, buffer_size);
168 pthread_mutex_lock (&p->lock);
170 if (p->serialize == NULL)
172 pthread_mutex_unlock (&p->lock);
173 fprintf (stderr, "population_send_to_peer: Cannot send to peer without "
174 "serialization function!\n");
178 i = (int) (((double) p->peers_num) * (rand() / (RAND_MAX + 1.0)));
182 buffer_free = sizeof (buffer);
183 status = p->serialize (pi, &buffer_ptr, &buffer_free);
186 pthread_mutex_unlock (&p->lock);
187 fprintf (stderr, "population_send_to_peer: p->serialize failed "
188 "with status %i.\n", status);
192 buffer_size = sizeof (buffer) - buffer_free;
195 pthread_mutex_unlock (&p->lock);
196 fprintf (stderr, "population_send_to_peer: p->serialize didn't put "
197 "anything into the buffer..\n");
201 /* write should not block - hopefully */
202 status = send (fd, buffer, buffer_size, MSG_DONTWAIT | MSG_NOSIGNAL);
205 pthread_mutex_unlock (&p->lock);
207 if (status != ECONNREFUSED)
209 fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
210 "send(2) returned with error %i.\n", status);
214 else if (((size_t) status) != buffer_size)
216 pthread_mutex_unlock (&p->lock);
217 fprintf (stderr, "population_send_to_peer: Writing to socket failed: "
218 "send(2) returned %i (expected %zu).\n",
219 status, buffer_size);
223 pthread_mutex_unlock (&p->lock);
226 printf ("population_send_to_peer: Sent individual with rating %i to peer #%i.\n",
231 } /* }}} int population_send_to_peer */
233 static void *listen_thread (void *data)
235 listen_thread_args_t *args;
242 struct addrinfo ai_hints;
243 struct addrinfo *ai_list;
244 struct addrinfo *ai_ptr;
246 args = (listen_thread_args_t *) data;
247 p = args->population;
249 service = args->service;
253 memset (&ai_hints, 0, sizeof (ai_hints));
254 ai_hints.ai_flags = AI_PASSIVE;
256 ai_hints.ai_flags |= AI_ADDRCONFIG;
258 ai_hints.ai_family = AF_UNSPEC;
259 ai_hints.ai_socktype = SOCK_DGRAM;
260 ai_hints.ai_protocol = 0;
262 status = getaddrinfo (node,
263 (service != NULL) ? service : POPULATION_DEFAULT_PORT,
264 &ai_hints, &ai_list);
267 fprintf (stderr, "listen_thread: getaddrinfo (%s) failed: %s\n",
268 (node != NULL) ? node : "NULL", gai_strerror (status));
269 return ((void *) -1);
273 for (ai_ptr = ai_list; ai_ptr != NULL; ai_ptr = ai_ptr->ai_next)
275 fd = socket (ai_ptr->ai_family, ai_ptr->ai_socktype, ai_ptr->ai_protocol);
279 status = bind (fd, ai_ptr->ai_addr, ai_ptr->ai_addrlen);
290 freeaddrinfo (ai_list);
294 fprintf (stderr, "listen_thread: No socket could be opened.\n");
295 return ((void *) -1);
298 pthread_mutex_lock (&p->lock);
299 p->flags |= POPULATION_FLAG_LISTEN;
300 while ((p->flags & POPULATION_FLAG_SHUTDOWN) == 0)
302 /* Allocate one extra byte to null-terminate the data. */
303 char buffer[NETWORK_BUFFER_SIZE + 1];
306 pthread_mutex_unlock (&p->lock);
308 status = recvfrom (fd, buffer, sizeof (buffer) - 1, /* flags = */ 0,
309 /* from = */ NULL, /* fromlen = */ NULL);
312 fprintf (stderr, "listen_thread: recvfrom(2) failed: status = %i; "
313 "errno = %i;\n", status, errno);
314 pthread_mutex_lock (&p->lock);
317 assert (status < sizeof (buffer));
318 buffer[sizeof (buffer) - 1] = 0;
320 pi = p->unserialize (buffer, (size_t) status);
323 fprintf (stderr, "listen_thread: p->unserialize returned NULL.\n");
324 pthread_mutex_lock (&p->lock);
329 printf ("listen_thread: Received individual with rating %i.\n",
333 population_insert (p, pi);
337 pthread_mutex_lock (&p->lock);
343 /* clear the listen flag */
344 p->flags &= ~(POPULATION_FLAG_LISTEN);
346 pthread_mutex_unlock (&p->lock);
348 } /* void *listen_thread */
351 * Constructor and destructor
353 population_t *population_create (pi_rate_f rate, pi_copy_f copy, /* {{{ */
359 p = (population_t *) malloc (sizeof (population_t));
363 memset (p, 0, sizeof (*p));
364 pthread_mutex_init (&p->lock, /* attr = */ NULL);
370 p->fittest.ptr = NULL;
371 p->fittest.rating = -1;
373 p->individuals = malloc (32 * sizeof (p->individuals[0]));
374 if (p->individuals == NULL)
379 memset (p->individuals, 0, 32 * sizeof (p->individuals[0]));
380 p->individuals_num = 32;
382 for (i = 0; i < p->individuals_num; i++)
384 p->individuals[i].ptr = NULL;
385 p->individuals[i].rating = -1;
389 } /* }}} population_t *population_create */
391 void population_destroy (population_t *p) /* {{{ */
396 pthread_mutex_lock (&p->lock);
397 p->flags |= POPULATION_FLAG_SHUTDOWN;
398 if ((p->flags & POPULATION_FLAG_LISTEN) != 0)
400 pthread_kill (p->listen_thread_id, SIGTERM);
401 pthread_mutex_unlock (&p->lock);
402 pthread_join (p->listen_thread_id, /* return = */ NULL);
403 pthread_mutex_lock (&p->lock);
406 if (p->fittest.ptr != NULL)
407 p->free (p->fittest.ptr);
408 p->fittest.ptr = NULL;
409 p->fittest.rating = -1;
411 if (p->individuals_num > 0)
415 for (i = 0; i < p->individuals_num; i++)
417 if (p->individuals[i].ptr != NULL)
418 p->free (p->individuals[i].ptr);
419 p->individuals[i].ptr = NULL;
420 p->individuals[i].rating = -1;
423 free (p->individuals);
424 p->individuals = NULL;
425 p->individuals_num = 0;
428 memset (p, 0, sizeof (*p));
430 } /* }}} void population_destroy */
432 int population_set_size (population_t *p, /* {{{ */
433 size_t population_size)
441 pthread_mutex_lock (&p->lock);
443 if (p->individuals_num == population_size)
445 pthread_mutex_unlock (&p->lock);
449 for (i = population_size; i < p->individuals_num; i++)
451 p->free (p->individuals[i].ptr);
452 p->individuals[i].ptr = NULL;
453 p->individuals[i].rating = -1;
456 temp = (individual_t *) realloc (p->individuals,
457 population_size * sizeof (p->individuals[0]));
460 pthread_mutex_unlock (&p->lock);
463 p->individuals = temp;
465 for (i = p->individuals_num; i < population_size; i++)
467 p->individuals[i].ptr = NULL;
468 p->individuals[i].rating = -1;
471 p->individuals_num = population_size;
473 pthread_mutex_unlock (&p->lock);
478 int population_set_serialization (population_t *p, /* {{{ */
479 pi_serialize_f serialize, pi_unserialize_f unserialize)
484 pthread_mutex_lock (&p->lock);
486 p->serialize = serialize;
487 p->unserialize = unserialize;
489 pthread_mutex_unlock (&p->lock);
491 } /* }}} int population_set_serialization */
493 int population_set_replacement_method (population_t *p, int method) /* {{{ */
500 pthread_mutex_lock (&p->lock);
502 if (method == POPULATION_REPLACEMENT_EXPLOIT)
503 p->flags &= ~POPULATION_FLAG_EXPLORE;
504 else if (method == POPULATION_REPLACEMENT_EXPLORE)
505 p->flags |= POPULATION_FLAG_EXPLORE;
509 pthread_mutex_unlock (&p->lock);
512 } /* }}} int population_set_replacement_method */
514 int population_add_peer (population_t *p, const char *node, /* {{{ */
517 struct addrinfo ai_hints;
518 struct addrinfo *ai_list;
519 struct addrinfo *ai_ptr;
529 port = POPULATION_DEFAULT_PORT;
533 memset (&ai_hints, 0, sizeof (ai_hints));
534 ai_hints.ai_flags = 0;
536 ai_hints.ai_flags |= AI_ADDRCONFIG;
538 ai_hints.ai_family = AF_UNSPEC;
539 ai_hints.ai_socktype = SOCK_DGRAM;
540 ai_hints.ai_protocol = 0;
542 status = getaddrinfo (node, port, &ai_hints, &ai_list);
545 fprintf (stderr, "population_add_peer: getaddrinfo (%s) failed: %s\n",
546 node, gai_strerror (status));
550 pthread_mutex_lock (&p->lock);
552 for (ai_ptr = ai_list; ai_ptr != NULL; ai_ptr = ai_ptr->ai_next)
556 temp = (int *) realloc (p->peers, sizeof (int) * (p->peers_num + 1));
559 fprintf (stderr, "population_add_peer: realloc failed.\n");
564 p->peers[p->peers_num] = socket (ai_ptr->ai_family, ai_ptr->ai_socktype,
565 ai_ptr->ai_protocol);
566 if (p->peers[p->peers_num] < 0)
569 status = connect (p->peers[p->peers_num],
570 ai_ptr->ai_addr, ai_ptr->ai_addrlen);
573 fprintf (stderr, "population_add_peer: connect(2) failed.\n");
574 close (p->peers[p->peers_num]);
578 status = fcntl (p->peers[p->peers_num], F_SETFL, O_NONBLOCK);
581 fprintf (stderr, "population_add_peer: fcntl (F_SETFL, O_NONBLOCK) "
582 "failed. Will use the socket with blocking.\n");
587 printf ("population_add_peer: Successfully added peer #%i.\n",
590 pthread_mutex_unlock (&p->lock);
592 freeaddrinfo (ai_list);
595 } /* }}} int population_add_peer */
597 int population_start_listen_thread (population_t *p, /* {{{ */
598 const char *node, const char *service)
600 listen_thread_args_t *args;
602 pthread_mutex_lock (&p->lock);
603 if ((p->flags & POPULATION_FLAG_LISTEN) != 0)
605 pthread_mutex_unlock (&p->lock);
606 fprintf (stderr, "population_start_listen_thread: "
607 "Listen thread already started.\n");
611 args = (listen_thread_args_t *) malloc (sizeof (listen_thread_args_t));
614 fprintf (stderr, "population_start_listen_thread: malloc failed.\n");
618 memset (args, 0, sizeof (listen_thread_args_t));
619 args->population = p;
620 args->node = population_strdup (node);
621 args->service = population_strdup (service);
623 pthread_create (&p->listen_thread_id, /* attr = */ NULL,
624 listen_thread, (void *) args);
626 pthread_mutex_unlock (&p->lock);
628 } /* }}} int population_start_listen_thread */
630 void *population_get_random (population_t *p) /* {{{ */
635 pthread_mutex_lock (&p->lock);
637 if (p->individuals_num < 1)
639 pthread_mutex_unlock (&p->lock);
645 i = (size_t) (((double) p->individuals_num)
646 * (rand() / (RAND_MAX + 1.0)));
647 if (p->individuals[i].ptr == NULL)
650 ret = p->copy (p->individuals[i].ptr);
653 pthread_mutex_unlock (&p->lock);
656 } /* }}} void *population_pick_random */
658 void *population_get_fittest (population_t *p) /* {{{ */
665 pthread_mutex_lock (&p->lock);
667 if (p->fittest.ptr == NULL)
669 pthread_mutex_unlock (&p->lock);
673 ret = p->copy (p->fittest.ptr);
675 pthread_mutex_unlock (&p->lock);
678 } /* }}} void *population_get_fittest */
680 int population_insert (population_t *p, void *pi_orig) /* {{{ */
693 pi = p->copy (pi_orig);
696 fprintf (stderr, "population_insert: p->copy failed.\n");
701 * With a small chance, send this individual to somewhere else.
702 * `sent_to_peer = -1' is used to signal the following code that this
703 * individual has been sent to somewhere else and doesn't go into the local
707 if (p->peers_num > 0)
711 prob = ((double) rand ()) / (((double) RAND_MAX) + 1.0);
714 population_send_to_peer (p, pi);
719 pi_rating = p->rate (pi);
721 pthread_mutex_lock (&p->lock);
723 /* Keep track of the all time best. */
724 if ((p->fittest.ptr == NULL) || (p->fittest.rating >= pi_rating))
731 if (p->fittest.ptr != NULL)
732 p->free (p->fittest.ptr);
733 p->fittest.ptr = temp;
734 p->fittest.rating = pi_rating;
738 if ((sent_to_peer != 0) || (p->individuals_num <= 0))
740 pthread_mutex_unlock (&p->lock);
753 j = (size_t) (((double) p->individuals_num) * (rand() / (RAND_MAX + 1.0)));
755 if (p->individuals[j].ptr == NULL)
757 p->individuals[j].ptr = pi;
758 p->individuals[j].rating = pi_rating;
763 /* large distance from fittest => high probability of losing. */
764 chance_j = 1 + p->individuals[j].rating - p->fittest.rating;
765 chance_pi = 1 + pi_rating - p->fittest.rating;
767 chance_j = chance_j * chance_j;
768 chance_pi = chance_pi * chance_pi;
770 chance = (int) (((double) (chance_j + chance_pi))
771 * (rand() / (RAND_MAX + 1.0)));
773 if (p->flags & POPULATION_FLAG_EXPLORE)
776 if (chance < chance_j) /* j looses ;) */
781 temp0 = p->individuals[j].ptr;
782 p->individuals[j].ptr = pi;
785 temp1 = p->individuals[j].rating;
786 p->individuals[j].rating = pi_rating;
791 pthread_mutex_unlock (&p->lock);
797 } /* }}} int population_insert */
799 /* vim: set sw=2 sts=2 et fdm=marker : */