home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / genetk / cigenfun.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-28  |  4.1 KB  |  191 lines
  1.  
  2.  
  3. /********************************************************************
  4. (c) Copyright 1993 Toms Computer Solutions,Inc. All rights reserved.
  5. ********************************************************************/
  6.  
  7.  
  8.  
  9. #include"grafopen.h"
  10. #include<string.h>
  11. #include<fstream.h>
  12. #include<iostream.h>
  13. #include<iomanip.h>
  14. #include<stdlib.h>
  15. #include<stdio.h>
  16. #include<conio.h>
  17.  
  18.  
  19.  
  20. #define number_of_cities  25
  21.  
  22.  
  23.  
  24.  
  25.  
  26. struct city
  27. {
  28.    unsigned char id;
  29.    unsigned long order;
  30. }
  31. ;
  32.  
  33.  
  34. struct city_loc
  35. {
  36.    int x,y;
  37. }
  38. ;
  39.  
  40.  
  41.  
  42. city      cities[number_of_cities];
  43. city_loc  cities_loc[number_of_cities];
  44.  
  45.  
  46.  
  47. // This function randomly sets up the locations of the cities in a 10000 by
  48. // 10000 square.
  49. void set_up_cities_locs()
  50. {
  51.    for(int i=0;i<number_of_cities;i++)
  52.    {
  53.       cities_loc[i].x=random(10000);
  54.       cities_loc[i].y=random(10000);
  55.    }
  56. }
  57.  
  58.  
  59. // This function is used by the qsort function called in the score_func.
  60. city_sort_func(const void *c1, const void *c2)
  61. {
  62.    unsigned long c1_order,c2_order;
  63.    city *city1,*city2;
  64.    city1=(city *)c1;
  65.    city2=(city *)c2;
  66.    c1_order=(*city1).order;
  67.    c2_order=(*city2).order;
  68.    if(c1_order>c2_order)
  69.    {
  70.       return 1;
  71.    }
  72.    else if(c1_order<c2_order)
  73.    {
  74.       return -1;
  75.    }
  76.    else
  77.    {
  78.       return 0;
  79.    }
  80. }
  81.  
  82.  
  83. void pre_init()
  84. {
  85.    
  86.    clrscr();
  87.    printf("/********************************************************************\n");
  88.    printf("(c) Copyright 1993 Toms Computer Solutions,Inc. All rights reserved.\n");
  89.    printf("********************************************************************/\n");
  90.    
  91.    
  92.    printf("\n\nDemo of a genetic algorithm solving the traveling salesman problem.\n");
  93.    printf("\nPress Q to quit.\n");
  94.    
  95.    
  96.    
  97.    printf("\n\n\nPress any key to continue\n");
  98.    
  99.    getch();
  100.    
  101.    randomize();
  102.    set_up_cities_locs();
  103.    tomopen();
  104. }
  105.  
  106.  
  107.  
  108. void init_round()
  109. {
  110. }
  111.  
  112.  
  113. // This is the scoreing function passed to the population class.
  114. // It returns the distance traveled by the salesman times -1.
  115. // It is multiplied by -1 so that the higher numbers represent better
  116. // solutions.
  117.  
  118. double score_func(unsigned char *gene_ptr)
  119. {
  120.    double dist;
  121.    unsigned long *lptr;
  122.    lptr=(unsigned long *)gene_ptr;
  123.    for(int i=0;i<number_of_cities;i++)
  124.    {
  125.       (cities[i]).id=i;
  126.       (cities[i]).order=*lptr;
  127.       lptr++;
  128.    }
  129.    qsort(&(cities[0]),number_of_cities,sizeof(cities[0]),city_sort_func);
  130.    dist=0.0;
  131.    int x1,x2,y1,y2;
  132.    double dx,dy;
  133.    x1=cities_loc[cities[number_of_cities-1].id].x;
  134.    y1=cities_loc[cities[number_of_cities-1].id].y;
  135.    for(i=0;i<number_of_cities;i++)
  136.    {
  137.       x2=cities_loc[cities[i].id].x;
  138.       y2=cities_loc[cities[i].id].y;
  139.       dx=fabs(x1-x2);
  140.       dy=fabs(y1-y2);
  141.       dist+=sqrt(dx*dx+dy*dy);
  142.       x1=x2;
  143.       y1=y2;
  144.    }
  145.    return -dist;
  146. }
  147.  
  148.  
  149. // This is a function passed to the population class to display a given
  150. // solution. In this case the solution is displayed graphically as a map
  151. // of the cities and the route taken by the salesman.
  152.  
  153. void print_solution(unsigned char *gene_ptr,double score,ofstream *ofs)
  154. {
  155.    clearviewport();
  156.    char gstring[256];
  157.    sprintf(gstring,"Total Distance = %f             ",-score);
  158.    setcolor(LIGHTMAGENTA);
  159.    outtextxy(25,25,gstring);
  160.    unsigned long *lptr;
  161.    lptr=(unsigned long *)gene_ptr;
  162.    for(int i=0;i<number_of_cities;i++)
  163.    {
  164.       (cities[i]).id=i;
  165.       (cities[i]).order=*lptr;
  166.       lptr++;
  167.    }
  168.    qsort(&(cities[0]),number_of_cities,sizeof(cities[0]),city_sort_func);
  169.    long x1,x2,y1,y2;
  170.    x1=cities_loc[cities[number_of_cities-1].id].x;
  171.    y1=cities_loc[cities[number_of_cities-1].id].y;
  172.    x1=((x1*max_x*0.8)/10000)+(max_x*0.1);
  173.    y1=((y1*max_y*0.9)/10000)+(max_y*0.1);
  174.    for(i=0;i<number_of_cities;i++)
  175.    {
  176.       x2=cities_loc[cities[i].id].x;
  177.       y2=cities_loc[cities[i].id].y;
  178.       x2=((x2*max_x*0.8)/10000)+(max_x*0.1);
  179.       y2=((y2*max_y*0.9)/10000)+(max_y*0.1);
  180.       setcolor(BLUE);
  181.       line(x1,y1,x2,y2);
  182.       setcolor(RED);
  183.       circle(x1,y1,4);
  184.       setcolor(YELLOW);
  185.       circle(x1,y1,2);
  186.       x1=x2;
  187.       y1=y2;
  188.    }
  189. }
  190.  
  191.