lab-evolution.c

   1 #include <stdlib.h>
   2 #include <stdio.h>
   3 #include <math.h>
   4 #include <limits.h>
   5
   6 #include <ucw/lib.h>
   7 #include <ucw/conf.h>
   8 #include <ucw/gary.h>
   9 #include <ucw/eltpool.h>
  10
  11 #include "leo.h"
  12 #include "sym.h"
  13 #include "labeller.h"
  14 #include "lab-utils.h"
  15 #include "lab-bitmaps.h"
  16 #include "lab-evolution.h"
  17
  18 enum term_cond
  19 {
  20   TERM_COND_UNDEF,
  21   TERM_COND_PENALTY,
  22   TERM_COND_STAGNATION,
  23   TERM_COND_ITERATIONS,
  24 };
  25
  26 static void evolution_compute_sizes(void);
  27
  28 static void make_population(void);
  29 static void rank_population(void);
  30
  31 static bool shall_terminate(void);
  32 static void breed(void);
  33 static void mutate(void);
  34 static void elite(void);
  35
  36 static void hide_segment_labels(struct individual *individual);
  37
  38 static void init_placement(struct placement *p, struct individual *individual, struct request *r);
  39
  40 static void init_individual(struct individual *i);
  41 static int cmp_individual(const void *a, const void *b);
  42 static void plan_individual(struct individual *individual);
  43 static void clear_individual(struct individual *individual);
  44
  45 static struct individual **perform_crossover(struct individual *parent1, struct individual *parent2);
  46 static void perform_mutation(struct individual *individual);
  47 static void copy_individual(struct individual *src, struct individual *dest);
  48
  49 static double gen_movement(void);
  50 static double gen_movement_uniform(void);
  51 static void move_symbol(struct placement *p);
  52 static void move_symbol_point(struct placement *p);
  53 static void move_symbol_segment(struct placement *p);
  54
  55 static void gen_coords(struct placement *p);
  56 static void gen_coords_point(struct placement *p);
  57 static void gen_coords_segment(struct placement *p);
  58 static void gen_coords_area(struct placement *p);
  59
  60 static void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr);
  61
  62 static int individual_overlap(struct individual *individual);
  63
  64 static double get_distance(struct placement *p);
  65 static double individual_distances(struct individual *individual);
  66
  67 static double get_omittment(struct placement *p);
  68 static double individual_omittment(struct individual *individual);
  69
  70 static void clear_population(struct individual **pop);
  71
  72 static void dump_penalties(struct individual **population);
  73
  74 static struct eltpool *ep_individuals;
  75
  76 static int conf_pop_size = 200, conf_fit_size = 1, conf_term_cond = TERM_COND_ITERATIONS;
  77
  78 static double conf_penalty_bound = 100, conf_stagnation_bound = 10;
  79 static int conf_iteration_limit = 200;
  80
  81 static double conf_rank_distance_w = 1, conf_rank_overlap_w = 1, conf_rank_omittment_w = 1;
  82
  83 static int breed_pop_size;
  84 static int breed_rbest_size;
  85
  86 static int mutate_pop_size;
  87 static int mutate_rbest_size;
  88
  89 static int elite_pop_size;
  90
  91 // In milimeters
  92 static int move_min = 0;
  93 static int move_max = 5;
  94
  95 static double conf_breed_pop_size = 0.45, conf_breed_rbest = 1,
  96        conf_mutate_children, conf_mutate_children_prob = 0.6,
  97        conf_mutate_pop_size = 0.45, conf_mutate_rbest = 1,
  98        conf_mutate_move_bound = 0.1, conf_mutate_regen_bound = 0.05, conf_mutate_chvar_bound = 0.1,
  99        conf_elite_pop_size = 0.1;
 100
 101 static struct cf_section evolution_cf = {
 102   CF_ITEMS {
 103     CF_INT("PopSize", &conf_pop_size),
 104     CF_INT("FitSize", &conf_fit_size),
 105     CF_INT("TermCond", &conf_term_cond),
 106     CF_DOUBLE("PenaltyBound", &conf_penalty_bound),
 107     CF_DOUBLE("StagnationBound", &conf_stagnation_bound),
 108     CF_INT("IterationLimit", &conf_iteration_limit),
 109     CF_DOUBLE("BreedPopSize", &conf_breed_pop_size),
 110     CF_DOUBLE("BreedNumBest", &conf_breed_rbest),
 111     CF_DOUBLE("MutateChild", &conf_mutate_children_prob),
 112     CF_DOUBLE("MutatePopSize", &conf_mutate_pop_size),
 113     CF_DOUBLE("MutateNumBest", &conf_mutate_rbest),
 114     CF_DOUBLE("MutateMoveBound", &conf_mutate_move_bound),
 115     CF_DOUBLE("MutateRegenBound", &conf_mutate_regen_bound),
 116     CF_DOUBLE("MutateChvarBound", &conf_mutate_chvar_bound),
 117     CF_DOUBLE("ElitePopSize", &conf_elite_pop_size),
 118     CF_DOUBLE("DistanceWeight", &conf_rank_distance_w),
 119     CF_DOUBLE("OverlapWeight", &conf_rank_overlap_w),
 120     CF_DOUBLE("OmittmentWeight", &conf_rank_omittment_w),
 121     CF_END
 122   }
 123 };
 124
 125 static struct placement dummy_placement;
 126
 127 static struct individual **population1;
 128 static struct individual **population2;
 129
 130 static int old_best = INT_MAX;
 131 static int iteration = 0;
 132 static int pop2_ind;
 133
 134
 135
 136 void evolution_conf(void)
 137 {
 138   cf_declare_section("Evolution", &evolution_cf, 0);
 139 }
 140
 141 void evolution_init(void)
 142 {
 143   evolution_compute_sizes();
 144 }
 145
 146 void evolve(void)
 147 {
 148   ep_individuals = ep_new(sizeof(struct individual), 1);
 149
 150   GARY_INIT(population1, conf_pop_size);
 151   GARY_INIT(population2, conf_pop_size);
 152
 153   make_population();
 154   rank_population();
 155   qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);
 156
 157   if (dbg_evolution >= VERBOSITY_GENERAL)
 158   {
 159     printf("Penalties after initialization\n");
 160     dump_penalties(population1);
 161   }
 162
 163   while (! shall_terminate())
 164   {
 165     iteration++;
 166     if (dbg_evolution)
 167       printf("\n*** Iteration %d ***\n", iteration);
 168
 169     breed();
 170     mutate();
 171     elite();
 172
 173     struct individual **swp = population1;
 174     population1 = population2;
 175     population2 = swp;
 176     pop2_ind = 0;
 177     clear_population(population2);
 178
 179     rank_population();
 180
 181     if (dbg_evolution >= VERBOSITY_INDIVIDUAL)
 182     {
 183       printf("Penalties before sort\n");
 184       dump_penalties(population1);
 185     }
 186
 187     DEBUG(dbg_evolution, VERBOSITY_GENERAL, "Sorting population\n");
 188     qsort(population1, conf_pop_size, sizeof(struct individual *), cmp_individual);
 189
 190     if (dbg_evolution >= VERBOSITY_GENERAL)
 191     {
 192       printf("Penalties after sort\n");
 193       dump_penalties(population1);
 194     }
 195
 196     old_best = population1[0]->penalty;
 197   }
 198
 199   if (dbg_overlaps >= VERBOSITY_GENERAL)
 200     dump_bitmaps(population1[0]);
 201
 202   plan_individual(population1[0]);
 203 }
 204
 205
 206 static void evolution_compute_sizes(void)
 207 {
 208   breed_pop_size = conf_breed_pop_size * conf_pop_size;
 209   breed_rbest_size = conf_breed_rbest * conf_pop_size;
 210   if (dbg_evolution >= VERBOSITY_GENERAL)
 211   {
 212     printf("Breeding parameters:\n");
 213     printf(" %d individuals are created\n", breed_pop_size);
 214     printf(" %d best individuals in old population are considered\n", breed_rbest_size);
 215   }
 216
 217   mutate_pop_size = conf_mutate_pop_size * conf_pop_size;
 218   mutate_rbest_size = conf_mutate_rbest * conf_pop_size;
 219   if (dbg_evolution >= VERBOSITY_GENERAL)
 220   {
 221     printf("Mutation parameters:\n");
 222     printf(" %d individuals are created\n", mutate_pop_size);
 223     printf(" %d best individuals in old population are considered\n", mutate_rbest_size);
 224   }
 225
 226   elite_pop_size = conf_elite_pop_size * conf_pop_size;
 227   if (dbg_evolution >= VERBOSITY_GENERAL)
 228   {
 229     printf("Elitism parameters:\n");
 230     printf(" %d best individuals are copied\n", elite_pop_size);
 231   }
 232
 233   if (breed_pop_size + mutate_pop_size + elite_pop_size != conf_pop_size)
 234   {
 235     if (conf_fit_size)
 236     {
 237       elite_pop_size += conf_pop_size - (breed_pop_size + mutate_pop_size + elite_pop_size);
 238     }
 239     else
 240     {
 241       fprintf(stderr, "Breeding + mutation + elitism won't create correct number of individuals\n");
 242       fprintf(stderr, "Please fix conf_breed_pop_size, conf_mutate_pop_size and conf_elite_pop_size parameters\n");
 243       exit(2);
 244     }
 245   }
 246 }
 247
 248
 249 void dump_individual(struct individual *individual)
 250 {
 251   printf("*** Individual dump\n");
 252   printf("(There are %d requests)\n", num_requests);
 253
 254   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 255   {
 256     struct placement *p = &(individual->placements[i]);
 257
 258     switch (p->request->type)
 259     {
 260       case REQUEST_POINT:
 261         printf("Point at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_point *) p->request)->zindex);
 262         break;
 263       case REQUEST_LINE: ;
 264         struct request_line *rl = (struct request_line *) p->request;
 265         printf("Line: ");
 266         dump_label(rl->sections[0].segments[0].label);
 267         break;
 268       case REQUEST_SECTION: ;
 269         printf("*");
 270         break;
 271       case REQUEST_SEGMENT: ;
 272         if (p->variant_used >= 0)
 273           printf("Segment placed at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_segment *) p->request)->zindex);
 274         else
 275           printf("Segment not placed\n");
 276         break;
 277       case REQUEST_AREA: ;
 278         struct request_area *ra = (struct request_area *) p->request;
 279         printf("Area label ");
 280         dump_label(ra->label);
 281         printf(" at [%.2f; %.2f] on %u\n", p->x, p->y, ((struct request_area *) p->request)->zindex);
 282         break;
 283       default:
 284         ASSERT(p->request->type != 0);
 285     }
 286   }
 287   printf("\nTotal penalty: %d\n", individual->penalty);
 288 }
 289
 290 static void plan_individual(struct individual *individual)
 291 {
 292   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 293   {
 294     struct symbol *s = NULL;
 295     z_index_t zindex = 0;
 296     /**
 297     if (individual->placements[i].variant_used < 0)
 298     {
 299       printf("Skipping placement of request %d\n", individual->placements[i].request->ind);
 300     }
 301     **/
 302     if (individual->placements[i].variant_used < 0) continue;
 303     switch (individual->placements[i].request->type)
 304     {
 305       case REQUEST_POINT: ;
 306         struct request_point *rp = (struct request_point *) individual->placements[i].request;
 307         s = rp->sym;
 308         zindex = rp->zindex;
 309         break;
 310       case REQUEST_SEGMENT: ;
 311         struct request_segment *rs = (struct request_segment *) individual->placements[i].request;
 312         s = rs->label;
 313         zindex = rs->zindex;
 314         break;
 315       case REQUEST_LINE: ;
 316         break;
 317       case REQUEST_AREA: ;
 318         struct request_area *ra = (struct request_area *) individual->placements[i].request;
 319         s = ra->label;
 320         zindex = ra->zindex;
 321         break;
 322       default:
 323         ASSERT(individual->placements[i].request != REQUEST_INVALID);
 324         continue;
 325     }
 326
 327   DEBUG(dbg_plan, VERBOSITY_PLACEMENT, "Will plan symbol of request %d at [%.2f; %.2f] on %u\n", individual->placements[i].request->ind, individual->placements[i].x, individual->placements[i].y, zindex);
 328
 329     if (s) switch (s->type)
 330     {
 331       case SYMBOLIZER_POINT: ;
 332         struct sym_point *sp = (struct sym_point *) s;
 333         sp->x = individual->placements[i].x;
 334         sp->y = individual->placements[i].y;
 335         sym_plan((struct symbol *) sp, zindex);
 336         break;
 337       case SYMBOLIZER_ICON: ;
 338         struct sym_icon *si = (struct sym_icon *) s;
 339         si->sir.x = individual->placements[i].x;
 340         si->sir.y = individual->placements[i].y;
 341         sym_plan((struct symbol *) si, zindex);
 342         break;
 343       case SYMBOLIZER_TEXT: ;
 344         struct sym_text *st = (struct sym_text *) s;
 345         st->x = individual->placements[i].x;
 346         st->y = individual->placements[i].y;
 347         st->next_duplicate = NULL;
 348         DEBUG(dbg_plan, VERBOSITY_PLACEMENT, "Planning text %s at [%.2f; %.2f] on %u, with rotation %.2f\n", osm_val_decode(st->text), st->x, st->y, zindex, st->rotate);
 349         sym_plan((struct symbol *) st, zindex);
 350         break;
 351       default:
 352         ASSERT(s->type != SYMBOLIZER_INVALID);
 353     }
 354   }
 355 }
 356
 357 static void dump_penalties(struct individual **population)
 358 {
 359   for (int i=0; i<conf_pop_size; i++)
 360   {
 361     printf("Individual %d has penalty %d\n", i, population[i]->penalty);
 362   }
 363 }
 364
 365 static void make_population(void)
 366 {
 367   for (int i=0; i<conf_pop_size; i++)
 368   {
 369     num_placements = 0; // FIXME: This IS a terrible HACK
 370     struct individual *i2 = ep_alloc(ep_individuals);
 371     init_individual(i2);
 372     population2[i] = i2;
 373
 374     DEBUG(dbg_init, VERBOSITY_INDIVIDUAL, "Making individual %d\n", i);
 375     struct individual *individual = ep_alloc(ep_individuals); init_individual(individual);
 376     population1[i] = individual;
 377
 378     int p = 0;
 379     for (uns j=0; j<GARY_SIZE(requests_point); j++)
 380     {
 381       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_point[j]);
 382     }
 383
 384     for (uns j=0; j<GARY_SIZE(requests_line); j++)
 385     {
 386       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j]);
 387
 388       for (uns k=0; k<GARY_SIZE(requests_line[j].sections); k++)
 389       {
 390         init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k]);
 391
 392         for (uns l=0; l<GARY_SIZE(requests_line[j].sections[k].segments); l++)
 393         {
 394           init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_line[j].sections[k].segments[l]);
 395         }
 396       }
 397     }
 398
 399     for (uns j=0; j<GARY_SIZE(requests_area); j++)
 400     {
 401       init_placement(&(individual->placements[p++]), individual, (struct request *) &requests_area[j]);
 402     }
 403
 404     hide_segment_labels(individual);
 405
 406     ASSERT(p == num_requests);
 407   }
 408 }
 409
 410 static bool shall_terminate(void)
 411 {
 412   switch (conf_term_cond)
 413   {
 414     case TERM_COND_PENALTY:
 415       return (population1[0]->penalty < conf_penalty_bound);
 416     case TERM_COND_STAGNATION:
 417       return (abs(old_best - population1[0]->penalty) < conf_stagnation_bound);
 418     case TERM_COND_ITERATIONS:
 419       return (iteration >= conf_iteration_limit);
 420     default:
 421       fprintf(stderr, "Warning: No termination condition is set, terminating\n");
 422       return 1;
 423   }
 424 }
 425
 426 static void breed(void)
 427 {
 428   int i=0;
 429
 430   struct individual **breed_buffer;
 431   while (i < breed_pop_size)
 432   {
 433     int parent1 = randint(0, breed_rbest_size);
 434     int parent2 = randint(0, breed_rbest_size);
 435     DEBUG(dbg_breeding, VERBOSITY_INDIVIDUAL, "Will breed %d and %d\n", parent1, parent2);
 436
 437     breed_buffer = perform_crossover(population1[parent1], population1[parent2]);
 438     population2[pop2_ind++] = breed_buffer[0];
 439     population2[pop2_ind++] = breed_buffer[1];
 440     free(breed_buffer);
 441     i += 2;
 442   }
 443 }
 444
 445 static struct individual **perform_crossover(struct individual *parent1, struct individual *parent2)
 446 {
 447   struct individual **buffer = xmalloc(2*sizeof(struct individual));
 448   struct individual *child1 = ep_alloc(ep_individuals); init_individual(child1);
 449   struct individual *child2 = ep_alloc(ep_individuals); init_individual(child2);
 450
 451   bool *processed;
 452   GARY_INIT_ZERO(processed, GARY_SIZE(parent1->placements));
 453
 454   for (uns i=0; i<GARY_SIZE(parent1->placements); i++)
 455   {
 456     if (! processed[parent1->placements[i].ind])
 457     {
 458       DEBUG(dbg_breeding, VERBOSITY_PLACEMENT, "Creating symbol closure for placement %u\n", i);
 459
 460       struct placement **clos_symbols = get_closure(&(parent1->placements[i]), parent2);
 461       int x = randint(0, 2);
 462
 463       if (x == 0)
 464       {
 465         DEBUG(dbg_breeding, VERBOSITY_PLACEMENT, "Copying parent->child 1->1 and 2->2\n");
 466         copy_symbols(clos_symbols, parent1, child1, &processed);
 467         copy_symbols(clos_symbols, parent2, child2, &processed);
 468       }
 469       else
 470       {
 471         DEBUG(dbg_breeding, VERBOSITY_PLACEMENT, "Copying parent->child 2->1 and 1->2\n");
 472         copy_symbols(clos_symbols, parent2, child1, &processed);
 473         copy_symbols(clos_symbols, parent1, child2, &processed);
 474       }
 475
 476       GARY_FREE(clos_symbols);
 477     }
 478   }
 479
 480   GARY_FREE(processed);
 481
 482   if (conf_mutate_children)
 483   {
 484     if (randdouble() < conf_mutate_children_prob) perform_mutation(child1);
 485     else hide_segment_labels(child1);
 486
 487     if (randdouble() < conf_mutate_children_prob) perform_mutation(child2);
 488     else hide_segment_labels(child2);
 489   }
 490
 491   buffer[0] = child1;
 492   buffer[1] = child2;
 493   return buffer;
 494 }
 495
 496 static void mutate(void)
 497 {
 498   for (int i=0; i < mutate_pop_size; i++)
 499   {
 500     DEBUG(dbg_mutation, VERBOSITY_INDIVIDUAL, "Creating %d-th individual by mutation\n", i);
 501     int ind = randint(0, mutate_rbest_size);
 502     DEBUG(dbg_mutation, VERBOSITY_INDIVIDUAL, "Mutating %d-th individual of original population\n", ind);
 503     population2[pop2_ind] = ep_alloc(ep_individuals);
 504     copy_individual(population1[ind], population2[pop2_ind]);
 505     DEBUG(dbg_mutation, VERBOSITY_INDIVIDUAL, "Individual %d in pop2 inited from individual %d in pop1\n", pop2_ind, ind);
 506     perform_mutation(population2[pop2_ind]);
 507     pop2_ind++;
 508   }
 509 }
 510
 511 static void perform_mutation(struct individual *individual)
 512 {
 513   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 514   {
 515     double x = randdouble();
 516     double acc = 0;
 517
 518     if (x <= acc + conf_mutate_move_bound)
 519     {
 520       DEBUG(dbg_mutation, VERBOSITY_PLACEMENT, "Mutation: Moving symbol in placement %u\n", i);
 521       move_symbol(&(individual->placements[i]));
 522       continue;
 523     }
 524     acc += conf_mutate_move_bound;
 525
 526     if (x <= acc + conf_mutate_regen_bound)
 527     {
 528       gen_coords(&(individual->placements[i]));
 529       continue;
 530     }
 531     acc += conf_mutate_regen_bound;
 532
 533     if (x <= acc + conf_mutate_chvar_bound)
 534     {
 535       struct placement *p = &(individual->placements[i]);
 536       switch (p->request->type)
 537       {
 538         case REQUEST_POINT:
 539         case REQUEST_AREA:
 540           // Does nothing when there are 0 variants... does it mind?
 541           p->variant_used = randint(-1, GARY_SIZE(p->request->variants));
 542           break;
 543         case REQUEST_SEGMENT:
 544           p->variant_used = randint(0, GARY_SIZE(p->request->variants));
 545           break;
 546         case REQUEST_SECTION:
 547           p->variant_used = randint(0, GARY_SIZE(((struct request_section *) p->request)->segments));
 548           break;
 549         default:
 550           ;
 551       }
 552     }
 553   }
 554
 555   hide_segment_labels(individual);
 556 }
 557
 558 static void elite(void)
 559 {
 560   for (int i=0; i<elite_pop_size; i++)
 561   {
 562     DEBUG(dbg_evolution, VERBOSITY_INDIVIDUAL, "Iteration %d: Copying individual #%d from pop 1 to #%d in pop 2\n", iteration, i, pop2_ind);
 563     population2[pop2_ind] = ep_alloc(ep_individuals);
 564     copy_individual(population1[i], population2[pop2_ind++]);
 565   }
 566 }
 567
 568 static int cmp_individual(const void *a, const void *b)
 569 {
 570   struct individual **ia = (struct individual **) a;
 571   struct individual **ib = (struct individual **) b;
 572
 573   return (*ia)->penalty - (*ib)->penalty;
 574 }
 575
 576 static void rank_population(void)
 577 {
 578   int penalty;
 579
 580   for (int i=0; i<conf_pop_size; i++)
 581   {
 582     DEBUG(dbg_rank, VERBOSITY_INDIVIDUAL, "Individual %d\n", i);
 583     population1[i]->penalty = 0;
 584
 585     penalty = conf_rank_omittment_w * individual_omittment(population1[i]);
 586     DEBUG(dbg_rank, VERBOSITY_INDIVIDUAL, "Increasing penalty by %d for omittment\n", penalty);
 587     population1[i]->penalty += penalty;
 588
 589     penalty = conf_rank_overlap_w * individual_overlap(population1[i]);
 590     DEBUG(dbg_rank, VERBOSITY_INDIVIDUAL, "Increasing penalty by %d for overlap\n", penalty);
 591     population1[i]->penalty += penalty;
 592
 593     penalty = conf_rank_distance_w * individual_distances(population1[i]);
 594     DEBUG(dbg_rank, VERBOSITY_INDIVIDUAL, "Increasing penalty by %d for distances\n", penalty);
 595     population1[i]->penalty += penalty;
 596   }
 597 }
 598
 599 static void gen_coords(struct placement *p)
 600 {
 601   switch(p->request->type)
 602   {
 603     case REQUEST_POINT:
 604       gen_coords_point(p);
 605       break;
 606     case REQUEST_AREA:
 607       gen_coords_area(p);
 608       break;
 609     case REQUEST_SEGMENT:
 610       gen_coords_segment(p);
 611       break;
 612     case REQUEST_LINE:
 613       if (dbg_movement)
 614         printf("Not yet implemented\n");
 615       break;
 616     default:
 617       DEBUG(dbg_movement, VERBOSITY_ALL, "Testing request type\n");
 618       ASSERT(p->request->type != REQUEST_INVALID);
 619   }
 620
 621   update_map_parts(p);
 622 }
 623
 624 static double gen_movement(void)
 625 {
 626   double m = (random() % 100000) / 10000;
 627   m = pow(m, 1.0/3) * flip(1, -1);
 628   DEBUG(dbg_movement, VERBOSITY_ALL, "Movement %.2f\n", m);
 629   return m;
 630 }
 631
 632 static double gen_movement_uniform(void)
 633 {
 634   return (move_max - move_min) * randdouble() * flip(1, -1);
 635 }
 636
 637 static void gen_coords_point(struct placement *p)
 638 {
 639   p->x = p->x + gen_movement();
 640 }
 641
 642 static void gen_coords_segment(struct placement *p)
 643 {
 644   struct request_segment *rs = (struct request_segment *) p->request;
 645   p->x = (rs->x1 + rs->x2) / 2;
 646   p->y = (rs->y1 + rs->y2) / 2;
 647 }
 648
 649 static void gen_coords_area(struct placement *p)
 650 {
 651   struct request_area *ra = (struct request_area *) p->request;
 652
 653   p->x = p->x + gen_movement();
 654   p->y = p->y + gen_movement();
 655
 656   DEBUG(dbg_movement, VERBOSITY_PLACEMENT, "Moved label to [%.2f; %.2f] from [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
 657 }
 658
 659 static void copy_symbols(struct placement **closure, struct individual *parent, struct individual *child, bool **processed_ptr)
 660 {
 661   bool *processed = *processed_ptr;
 662   DEBUG(dbg_breeding, VERBOSITY_ALL, "Will copy %zu symbols\n", GARY_SIZE(closure));
 663
 664   for (uns i=0; i<GARY_SIZE(closure); i++)
 665   {
 666     processed[closure[i]->ind] = 1;
 667     int ind = closure[i]->ind;
 668     child->placements[ind] = parent->placements[ind];
 669     child->placements[ind].individual = child;
 670     child->placements[ind].processed = 0;
 671     child->placements[ind].map_links = NULL;
 672     update_map_parts(&child->placements[ind]);
 673   }
 674 }
 675
 676 static void move_symbol(struct placement *p)
 677 {
 678   switch (p->request->type)
 679   {
 680     case REQUEST_POINT:
 681     case REQUEST_AREA:
 682       move_symbol_point(p);
 683       break;
 684     case REQUEST_SEGMENT:
 685       move_symbol_segment(p);
 686       break;
 687     default:
 688       ASSERT(p->request->type != REQUEST_INVALID);
 689   }
 690 }
 691
 692 static void move_symbol_point(struct placement *p)
 693 {
 694   p->x += gen_movement_uniform();
 695   p->y += gen_movement_uniform();
 696 }
 697
 698 static void move_symbol_segment(struct placement *p)
 699 {
 700   struct request_segment *rs = (struct request_segment *) p->request;
 701   double m = gen_movement_uniform();
 702   if (fabs(rs->x2 - rs->x1) > 0.01)
 703   {
 704     p->x += m;
 705     p->y += m * rs->slope;
 706   }
 707   else
 708   {
 709     p->x += m;
 710   }
 711 }
 712
 713 static void hide_segment_labels(struct individual *individual)
 714 {
 715   // BEWARE: This fully depends on current genetic encoding
 716
 717   int used = -1, num = -1;
 718   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 719   {
 720     switch (individual->placements[i].request->type)
 721     {
 722       case REQUEST_SECTION:
 723         used = individual->placements[i].variant_used;
 724         num = 0;
 725         break;
 726       case REQUEST_SEGMENT:
 727         if (num == used)
 728           individual->placements[i].variant_used = 0;
 729         else
 730           individual->placements[i].variant_used = -1;
 731         num++;
 732         break;
 733       default:
 734         ;
 735     }
 736   }
 737 }
 738
 739 static void init_placement(struct placement *p, struct individual *individual, struct request *r)
 740 {
 741   p->ind = num_placements++;
 742   p->request = r;
 743   p->processed = 0;
 744   p->x = p->y = 0; // To prevent valgrind from complaining
 745   p->variant_used = 0;
 746   p->map_links = NULL;
 747   p->individual = individual;
 748   switch (r->type)
 749   {
 750     case REQUEST_POINT: ;
 751       struct request_point *rp = (struct request_point *) r;
 752       p->x = rp->x;
 753       p->y = rp->y;
 754       break;
 755     case REQUEST_LINE: ;
 756       break;
 757     case REQUEST_SECTION: ;
 758       struct request_section *rls = (struct request_section *) r;
 759       p->variant_used = randint(0, GARY_SIZE(rls->segments));
 760       break;
 761     case REQUEST_SEGMENT: ;
 762       struct request_segment *rs = (struct request_segment *) r;
 763       p->x = rs->x2;
 764       p->y = rs->y2;
 765       break;
 766     case REQUEST_AREA: ;
 767       struct request_area *ra = (struct request_area *) r;
 768       p->x = ra->cx;
 769       p->y = ra->cy;
 770       p->variant_used = 0;
 771       break;
 772     default:
 773       ASSERT(p->request->type != REQUEST_INVALID);
 774   }
 775
 776   gen_coords(p);
 777   DEBUG(dbg_init, VERBOSITY_PLACEMENT, "Inited placement to [%.2f; %.2f]\n", p->x, p->y);
 778 }
 779
 780 static void clear_individual(struct individual *individual)
 781 {
 782   for (uns j=0; j<num_map_parts; j++)
 783   {
 784     struct map_placement *mp = individual->map[j]->placement;
 785     while (mp)
 786     {
 787       struct map_placement *tmp = mp;
 788       mp = mp->next_in_map;
 789       free(tmp);
 790     }
 791
 792     free(individual->map[j]);
 793   }
 794
 795   GARY_FREE(individual->map);
 796   GARY_FREE(individual->placements);
 797   ep_free(ep_individuals, individual);
 798 }
 799
 800 static void clear_population(struct individual **pop)
 801 {
 802   for (uns i=0; i<GARY_SIZE(pop); i++)
 803   {
 804     clear_individual(pop[i]);
 805   }
 806 }
 807
 808 static void init_individual(struct individual *individual)
 809 {
 810   GARY_INIT(individual->placements, num_requests);
 811   GARY_INIT(individual->map, 0);
 812   for (uns j=0; j<num_map_parts; j++)
 813   {
 814     GARY_PUSH(individual->map);
 815     struct map_part *part = xmalloc(sizeof(struct map_part));
 816     struct map_placement *mp = xmalloc(sizeof(struct map_placement));
 817     part->placement = mp;
 818     part->ind = j;
 819     mp->placement = &dummy_placement;
 820     mp->next_in_map = mp->prev_in_map = NULL;
 821     mp->next_in_placement = mp->prev_in_placement = NULL;
 822     individual->map[j] = part;
 823   }
 824   individual->penalty = 0;
 825 }
 826
 827 static void copy_individual(struct individual *src, struct individual *dest)
 828 {
 829   init_individual(dest);
 830   dest->penalty = src->penalty;
 831
 832   for (uns i=0; i<GARY_SIZE(src->placements); i++)
 833   {
 834     dest->placements[i] = src->placements[i];
 835     dest->placements[i].map_links = NULL;
 836     dest->placements[i].individual = dest;
 837
 838     update_map_parts_create(&dest->placements[i]);
 839   }
 840 }
 841
 842 static int individual_overlap(struct individual *individual)
 843 {
 844   int overlap = 0;
 845
 846   int *planned;
 847   GARY_INIT_ZERO(planned, GARY_SIZE(individual->placements));
 848
 849   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 850   {
 851     overlap += get_overlap(&individual->placements[i], &planned, i+1);
 852   }
 853
 854   GARY_FREE(planned);
 855
 856 //  printf("Total overlap is %d\n", overlap);
 857
 858   return overlap;
 859 }
 860
 861 static double get_distance(struct placement *p)
 862 {
 863   if (p->variant_used < 0) return 0;
 864   struct variant *v = &p->request->variants[p->variant_used];
 865
 866   double dx, dy, distance;
 867   switch (p->request->type)
 868   {
 869     case REQUEST_POINT: ;
 870       struct request_point *rp = (struct request_point *) p->request;
 871       dx = rp->x + v->offset_x - p->x;
 872       dy = rp->y + v->offset_y - p->y;
 873       distance = hypot(dx, dy);
 874       DEBUG(dbg_rank, VERBOSITY_PLACEMENT, "Point placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, rp->x, rp->y);
 875       break;
 876     case REQUEST_SEGMENT: ;
 877       struct request_segment *rs = (struct request_segment *) p->request;
 878       struct sym_text *st = (struct sym_text *) rs->label;
 879
 880       double width = p->request->variants[p->variant_used].width;
 881       double rotated_x = p->x + width * sin(convert_to_rad(st->rotate));
 882       double rotated_y = p->y + width * cos(convert_to_rad(st->rotate));
 883
 884       if (rs->x1 < rs->x2)
 885       {
 886         if (p->x < rs->x1)
 887         {
 888           dx = rs->x1 - p->x;
 889           dy = rs->y1 - p->y;
 890         }
 891         else if (rotated_x > rs->x2)
 892         {
 893           dx = rotated_x - rs->x2;
 894           dy = rotated_y - rs->y2;
 895         }
 896         else
 897         {
 898           dx = dy = 0;
 899         }
 900       }
 901       else
 902       {
 903         if (p->x < rs->x2)
 904         {
 905           dx = rs->x2 - p->x;
 906           dy = rs->y2 - p->y;
 907         }
 908         else if (rotated_x > rs->x1)
 909         {
 910           dx = rotated_x - rs->x1;
 911           dy = rotated_y - rs->y1;
 912         }
 913         else
 914         {
 915           dx = dy = 0;
 916         }
 917       }
 918
 919       distance = hypot(dx, dy);
 920       break;
 921     case REQUEST_AREA: ;
 922       struct request_area *ra = (struct request_area *) p->request;
 923       dx = ra->cx + v->offset_x - p->x;
 924       dy = ra->cy + v->offset_y - p->y;
 925       distance = hypot(dx, dy);
 926       DEBUG(dbg_rank, VERBOSITY_PLACEMENT, "Area placed at [%.2f; %.2f], expected at [%.2f; %.2f]\n", p->x, p->y, ra->cx, ra->cy);
 927       break;
 928     default:
 929       return 0;
 930   }
 931
 932   DEBUG(dbg_rank, VERBOSITY_PLACEMENT, "Placement %d has distance %.2f\n", p->ind, distance);
 933   return distance;
 934 }
 935
 936 static double individual_distances(struct individual *individual)
 937 {
 938   int distances = 0;
 939
 940   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 941   {
 942     distances += get_distance(&individual->placements[i]);
 943   }
 944
 945   return distances;
 946 }
 947
 948 static double get_omittment(struct placement *p)
 949 {
 950   if (p->variant_used >= 0) return 0;
 951
 952   // FIX ME :)
 953   switch (p->request->type)
 954   {
 955     case REQUEST_POINT:
 956     case REQUEST_AREA:
 957       return 10;
 958       break;
 959     default:
 960       return 0;
 961   }
 962 }
 963
 964 static double individual_omittment(struct individual *individual)
 965 {
 966   int omittment = 0;
 967
 968   for (uns i=0; i<GARY_SIZE(individual->placements); i++)
 969   {
 970     omittment += get_omittment(&individual->placements[i]);
 971   }
 972
 973   return omittment;
 974 }