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