Labelling: Option to complete population by elitism

[leo.git] / labeller.c

diff --git a/labeller.c b/labeller.c
index c208c59b3778702171f04cef1a4548eb1e45f927..644fa775edb89fc898e79f9dbb3a3ea43cc4bb8b 100644 (file)
--- a/labeller.c
+++ b/labeller.c
@@ -60,6 +60,7 @@ int num_edges = 0;
 int dbg_num_hits = 0;
 
 int conf_pop_size = 50;
+int conf_fit_size = 1;
 
 int conf_penalty_bound = 0;
 int conf_stagnation_bound = 0;
@@ -135,6 +136,9 @@ void init_individual(struct individual *i);
 void copy_individual(struct individual *src, struct individual *dest);
 int cmp_individual(const void *a, const void *b);
 
+void clear_individual(struct individual *individual);
+void clear_population(struct individual **pop);
+
 void make_bitmap(struct variant *v, struct symbol *sym);
 void make_bitmap_icon(struct variant *v, struct sym_icon *si);
 void make_bitmap_point(struct variant *v, struct sym_point *sp);
@@ -847,6 +851,15 @@ void make_segments(void)
     {
       if (dbg_segments >= VERBOSITY_INDIVIDUAL)
         printf("WARNING: Longline without any segment, skipped\n");
+
+      struct request_section *rls = &request->sections[0];
+      GARY_FREE(rls->segments);
+      GARY_FREE(rls->request.variants);
+
+      struct request_line *rl = &requests_line[GARY_SIZE(requests_line)-1];
+      GARY_FREE(rl->sections);
+      GARY_FREE(rl->request.variants);
+
       GARY_POP(requests_line);
       num_requests -= 2;
     }
@@ -931,6 +944,8 @@ void dump_bitmaps(struct individual *individual)
     fprintf(fd_dump, "\n");
   }
   fclose(fd_dump);
+
+  free(bitmap);
 }
 
 void dump_individual(struct individual *individual)
@@ -1081,9 +1096,16 @@ void compute_sizes(void)
 
   if (breed_pop_size + mutate_pop_size + elite_pop_size != conf_pop_size)
   {
-    fprintf(stderr, "Breeding + mutation + elitism won't create correct number of individuals\n");
-    fprintf(stderr, "Please fix conf_breed_pop_size, conf_mutate_pop_size and conf_elite_pop_size parameters\n");
-    exit(2);
+    if (conf_fit_size)
+    {
+      elite_pop_size += conf_pop_size - (breed_pop_size + mutate_pop_size + elite_pop_size);
+    }
+    else
+    {
+      fprintf(stderr, "Breeding + mutation + elitism won't create correct number of individuals\n");
+      fprintf(stderr, "Please fix conf_breed_pop_size, conf_mutate_pop_size and conf_elite_pop_size parameters\n");
+      exit(2);
+    }
   }
 }
 
@@ -1120,6 +1142,7 @@ void labeller_label(void)
     population1 = population2;
     population2 = swp;
     pop2_ind = 0;
+    clear_population(population2);
 
     rank_population();
 
@@ -1255,9 +1278,9 @@ struct individual **perform_crossover(struct individual *parent1, struct individ
         printf("Creating symbol closure for placement %u\n", i);
 
       struct placement **clos_symbols = get_closure(&(parent1->placements[i]));
-      int x = randint(1, 2);
+      int x = randint(0, 2);
 
-      if (x == 1)
+      if (x == 0)
       {
         if (dbg_breeding >= VERBOSITY_PLACEMENT)
           printf("Copying parent->child 1->1 and 2->2\n");
@@ -1295,9 +1318,10 @@ void mutate(void)
   {
     if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
       printf("Creating %d-th individual by mutation\n", i);
-    int ind = randint(1, mutate_rbest_size);
+    int ind = randint(0, mutate_rbest_size);
     if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
       printf("Mutating %d-th individual of original population\n", ind);
+    population2[pop2_ind] = ep_alloc(ep_individuals);
     copy_individual(population1[ind], population2[pop2_ind]);
     if (dbg_mutation >= VERBOSITY_INDIVIDUAL)
       printf("Individual %d in pop2 inited from individual %d in pop1\n", pop2_ind, ind);
@@ -1356,6 +1380,7 @@ void elite(void)
 {
   for (int i=0; i<elite_pop_size; i++)
   {
+    population2[pop2_ind] = ep_alloc(ep_individuals);
     copy_individual(population1[i], population2[pop2_ind++]);
   }
 }
@@ -1415,7 +1440,7 @@ int get_overlap(struct placement *p)
 
   for (uns i=0; i<GARY_SIZE(parts); i++)
   {
-    struct map_placement *mp = parts[i]->placement->next;
+    struct map_placement *mp = parts[i]->placement->next_in_map;
     while (mp)
     {
       if (! planned[mp->placement->request->ind])
@@ -1424,7 +1449,7 @@ int get_overlap(struct placement *p)
         *p = mp->placement;
         planned[mp->placement->request->ind] = true;
       }
-      mp = mp->next;
+      mp = mp->next_in_map;
     }
   }
 
@@ -1583,24 +1608,24 @@ struct map_part **get_map_parts(struct placement *p)
   return buffer;
 }
 
-void update_map_parts(struct placement *p)
+void update_map_parts_delete(struct placement *p)
 {
-  struct placement_link *ml = p->map_links;
-  while (ml)
+  struct map_placement *mp = p->map_links;
+  while (mp)
   {
-    struct map_placement *mp = ml->mp;
-
-    mp->prev->next = mp->next;
-    if (mp->next)
-      mp->next->prev = mp->prev;
-    free(mp);
+    mp->prev_in_map->next_in_map = mp->next_in_map;
+    if (mp->next_in_map)
+      mp->next_in_map->prev_in_map = mp->prev_in_map;
 
-    struct placement_link *tmp = ml;
-    ml = ml->next;
+    struct map_placement *tmp = mp;
+    mp = mp->next_in_placement;
     free(tmp);
   }
   p->map_links = NULL;
+}
 
+void update_map_parts_create(struct placement *p)
+{
   struct map_part **parts = get_map_parts(p);
   if (parts == NULL) return;
 
@@ -1608,21 +1633,27 @@ void update_map_parts(struct placement *p)
   {
     struct map_placement *mp = malloc(sizeof(struct map_placement));
     mp->placement = p;
+    mp->part = parts[i];
 
-    mp->next = parts[i]->placement->next;
-    mp->prev = parts[i]->placement;
-    parts[i]->placement->next = mp;
-    if (mp->next) mp->next->prev = mp;
+    mp->next_in_map = parts[i]->placement->next_in_map;
+    mp->prev_in_map = parts[i]->placement;
+    parts[i]->placement->next_in_map = mp;
+    if (mp->next_in_map) mp->next_in_map->prev_in_map = mp;
 
-    struct placement_link *ml = malloc(sizeof(struct placement_link));
-    ml->mp = mp;
-    ml->next = p->map_links;
-    p->map_links = ml;
+    mp->next_in_placement = p->map_links;
+    mp->prev_in_placement = NULL;
+    p->map_links = mp;
   }
 
   GARY_FREE(parts);
 }
 
+void update_map_parts(struct placement *p)
+{
+  update_map_parts_delete(p);
+  update_map_parts_create(p);
+}
+
 void gen_coords(struct placement *p)
 {
   switch(p->request->type)
@@ -1734,6 +1765,8 @@ struct placement **get_closure(struct placement *placement)
     first++;
   }
 
+  free(chosen);
+
   return closure;
 }
 
@@ -1748,6 +1781,7 @@ void copy_symbols(struct placement **closure, struct individual *parent, struct
     processed[closure[i]->ind] = 1;
     int ind = closure[i]->ind;
     child->placements[ind] = parent->placements[ind];
+    child->placements[ind].individual = child;
     child->placements[ind].processed = 0;
     child->placements[ind].map_links = NULL;
     update_map_parts(&child->placements[ind]);
@@ -1852,24 +1886,65 @@ void init_placement(struct placement *p, struct individual *individual, struct r
     printf("Inited placement to [%.2f; %.2f]\n", p->x, p->y);
 }
 
-void init_individual(struct individual *i)
+void reset_individual_map(struct individual *i)
 {
-  if (dbg_init >= VERBOSITY_INDIVIDUAL)
-    printf("Initing individual\n");
-  GARY_INIT(i->placements, num_requests);
-  GARY_INIT(i->map, 0);
   for (uns j=0; j<num_map_parts; j++)
   {
-    struct map_part *part = GARY_PUSH(i->map);
-    GARY_INIT(part->placement, 0);
-    struct map_placement *mp = GARY_PUSH(part->placement);
+    struct map_placement *mp = i->map[j]->placement;
+    while (mp)
+    {
+      struct map_placement *tmp = mp;
+      mp = mp->next_in_map;
+      free(tmp);
+    }
+
+    free(i->map[j]);
+    struct map_part *part = malloc(sizeof(struct map_part));
+    part->ind = j;
+
+    mp = malloc(sizeof(struct map_placement));
+    part->placement = mp;
     mp->placement = &dummy_placement;
-    mp->next = mp->prev = NULL;
+    mp->next_in_map = mp->prev_in_map = NULL;
+    mp->next_in_placement = mp->prev_in_placement = NULL;
+    i->map[j] = part;
   }
-  i->penalty = 0; // FIXME
+}
 
-  if (dbg_init >= VERBOSITY_INDIVIDUAL)
-    printf("Individual inited, has %u map parts\n", GARY_SIZE(i->map));
+void update_individual(struct individual *individual)
+{
+  for (uns i=0; i<GARY_SIZE(individual->placements); i++)
+  {
+    update_map_parts_delete(&individual->placements[i]);
+  }
+}
+
+void clear_individual(struct individual *individual)
+{
+  for (uns j=0; j<num_map_parts; j++)
+  {
+    struct map_placement *mp = individual->map[j]->placement;
+    while (mp)
+    {
+      struct map_placement *tmp = mp;
+      mp = mp->next_in_map;
+      free(tmp);
+    }
+
+    free(individual->map[j]);
+  }
+
+  GARY_FREE(individual->map);
+  GARY_FREE(individual->placements);
+  ep_free(ep_individuals, individual);
+}
+
+void clear_population(struct individual **pop)
+{
+  for (uns i=0; i<GARY_SIZE(pop); i++)
+  {
+    clear_individual(pop[i]);
+  }
 }
 
 struct placement **get_overlapping(struct placement *p)
@@ -1882,7 +1957,7 @@ struct placement **get_overlapping(struct placement *p)
 
   for (uns i=0; i<GARY_SIZE(parts); i++)
   {
-    struct map_placement *mp = parts[i]->placement->next;
+    struct map_placement *mp = parts[i]->placement->next_in_map;
     while (mp)
     {
       if (p->variant_used >= 0)
@@ -1890,7 +1965,7 @@ struct placement **get_overlapping(struct placement *p)
        struct placement **p = GARY_PUSH(buffer);
        *p = mp->placement;
       }
-      mp = mp->next;
+      mp = mp->next_in_map;
     }
   }
   GARY_FREE(parts);
@@ -1929,21 +2004,36 @@ double randdouble(void)
   return ((double) rand() / (double) RAND_MAX);
 }
 
+void init_individual(struct individual *individual)
+{
+  GARY_INIT(individual->placements, num_requests);
+  GARY_INIT(individual->map, 0);
+  for (uns j=0; j<num_map_parts; j++)
+  {
+    GARY_PUSH(individual->map);
+    struct map_part *part = malloc(sizeof(struct map_part));
+    struct map_placement *mp = malloc(sizeof(struct map_placement));
+    part->placement = mp;
+    part->ind = j;
+    mp->placement = &dummy_placement;
+    mp->next_in_map = mp->prev_in_map = NULL;
+    mp->next_in_placement = mp->prev_in_placement = NULL;
+    individual->map[j] = part;
+  }
+  individual->penalty = 0;
+}
+
 void copy_individual(struct individual *src, struct individual *dest)
 {
+  init_individual(dest);
   dest->penalty = src->penalty;
-  GARY_INIT(dest->placements, GARY_SIZE(src->placements));
+
   for (uns i=0; i<GARY_SIZE(src->placements); i++)
   {
     dest->placements[i] = src->placements[i];
     dest->placements[i].map_links = NULL;
-  }
-  for (uns j=0; j<num_map_parts; j++)
-  {
-    struct map_part *part = GARY_PUSH(dest->map);
-    GARY_INIT(part->placement, 0);
-    struct map_placement *mp = GARY_PUSH(part->placement);
-    mp->placement = &dummy_placement;
-    mp->next = mp->prev = NULL;
+    dest->placements[i].individual = dest;
+
+    update_map_parts_create(&dest->placements[i]);
   }
 }