home *** CD-ROM | disk | FTP | other *** search
/ Media Share 13 / mediashare_13.zip / mediashare_13 / ZIPPED / PROGRAM / APR94_1.ZIP / GA.ZIP / SOURCE.ZIP / GDRIVER.CPP next >
C/C++ Source or Header  |  1994-01-10  |  7KB  |  226 lines
  1. //Copyright (C) Man Machine Interfaces 1994. All rights reserved.
  2.  
  3. //gdriver.cpp
  4. //Used as an interface class to the GA.
  5. //Stores the representation of the graph as
  6. //a connection grid.
  7.                             
  8. //required headers                            
  9. #include "stdafx.h"
  10.  
  11. //Headers needed for EOS programs
  12. //You need EOS v1.1 to compile this code
  13. #include "eos.h"   
  14. #include "eosutil.h"   
  15. #include "geno.h"
  16. #include "individ.h"
  17. #include "gaenviro.h"
  18.  
  19. //headers specific to graph GA
  20. #include "wmatrix.h"
  21. #include "gdriver.h"
  22. #include "grphutil.h"
  23. #include "graphga.h"
  24.  
  25. //GA parameters used, these need not be
  26. //hard coded in advanced implementations
  27. const int POP_SIZE = 20 ;
  28. const double PX = 0.7 ;
  29. const double PM = 0.03 ;
  30. const double RAND_SEED=0.76451 ;
  31.  
  32. //DRAWING parameters used, these need not be
  33. //hard coded in advanced implementations
  34. const int CELL_WIDTH = 30 ;
  35. const int CELL_HEIGHT = 30  ;
  36. const int CELL_SPACE = 30 ;
  37.  
  38.  
  39. //Driver constructor initializes a graph with  numNodes and a 
  40. //grid that the graph will be optimized to draw on (width x height)
  41. CGAGraphDriver::CGAGraphDriver(int numNodes, int width, int height) 
  42. {           
  43.     m_NumGraphNodes = numNodes;           
  44.     m_GridWidth = width ;                         
  45.     m_GridHeight = height ;                                                                                   
  46.     //graph represented as boolean connection matrix
  47.     m_pGraph = new CWordMatrix(m_NumGraphNodes,m_NumGraphNodes) ; 
  48.     //The Graph GA object
  49.     m_pTheGA = new CGraphDrawerGA(*this) ;
  50.     m_pBest = NULL ;
  51.     m_pWorst = NULL ;
  52.     m_Stop = FALSE ;
  53. }   
  54.      
  55. //Clean up in the destructor     
  56. CGAGraphDriver::~CGAGraphDriver() 
  57. {
  58.     delete m_pGraph ;
  59.     delete m_pTheGA ;
  60. }
  61.  
  62. //set the conections from graph into the member m_pGraph
  63. void CGAGraphDriver::SetGraph(CWordMatrix &graph) 
  64. {
  65.     for (int row = 0 ; row < m_NumGraphNodes; row++)
  66.         for (int col = 0 ; col < m_NumGraphNodes; col++)
  67.             m_pGraph->SetAt(row,col,graph[row][col]) ;    
  68. }
  69.  
  70. //Optimize the drawing of the graph by first initializing the
  71. //GA's population and environment. Then execute the 
  72. //GA for  numGenerations generations
  73. void CGAGraphDriver::Optimize(int numGenerations) 
  74. {
  75.     m_pTheGA->CreatePopulation(POP_SIZE) ;
  76.     m_pTheGA->CreateEnvironment(PX,PM,RAND_SEED) ;
  77.     m_pTheGA->Evolve(numGenerations) ;
  78. }
  79.  
  80. //Draw the optimized graph on the Windows DC
  81. void CGAGraphDriver::DrawOptimized(CDC &dc) 
  82. {                                                                                     
  83.     CWordMatrix *pGrid ;
  84.     m_pBest->GetPhenoInfo(&pGrid) ;
  85.     Draw(dc,*pGrid) ;
  86. }
  87.  
  88. //Draw the un-optimized graph on the Windows DC
  89. void CGAGraphDriver::DrawUnOptimized(CDC &dc)
  90. {
  91.     CWordMatrix *pGrid ;
  92.     m_pWorst->GetPhenoInfo(&pGrid) ;
  93.     Draw(dc,*pGrid) ;
  94. }
  95.  
  96. void CGAGraphDriver::Draw(CDC &dc, CWordMatrix &Grid)
  97. {    
  98.     CPen *pPen = (CPen *) dc.SelectStockObject(BLACK_PEN) ;
  99.     for (int row = 0 ; row < m_GridHeight; row++)
  100.         for (int col = 0 ; col < m_GridWidth; col++) {
  101.             if (Grid[row][col] != EMPTY_CELL)  {
  102.                 int x1 = col * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
  103.                 int x2 = x1 + CELL_WIDTH    ;
  104.                 int y1 = row * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
  105.                 int y2 = y1 + CELL_HEIGHT   ;
  106.                 dc.Ellipse(x1,y1,x2,y2) ;                   
  107.                 char buffer[4] ;
  108.                 sprintf(buffer,"%d",Grid[row][col]) ;
  109.                 dc.TextOut(x1+CELL_WIDTH/4,y1+CELL_HEIGHT/4,buffer,strlen(buffer)) ;
  110.                 }
  111.             }       
  112.     //draw arcs        
  113.     for (int node1 = 0 ; node1 < m_NumGraphNodes; node1++)
  114.         for (int node2 = 0 ; node2 < m_NumGraphNodes; node2++)
  115.             if (m_pGraph->GetAt(node1,node2)) {
  116.                 int row1, col1 ;
  117.                 Grid.Find(node1, row1, col1) ;
  118.                 int row2, col2 ;
  119.                 Grid.Find(node2, row2, col2) ;
  120.                 int x1 = col1 * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
  121.                 int x2 = col2 * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
  122.                 int y1 = row1 * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
  123.                 int y2 = row2 * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
  124.                 if (x1 < x2)
  125.                     x1 += CELL_WIDTH ;
  126.                 else    
  127.                 if (x2 < x1)
  128.                     x2 += CELL_WIDTH ;
  129.                 else    
  130.                 if (x1 == x2) {
  131.                     if (Abs(row1 - row2) > 1) { //route around!
  132.                         y1 += CELL_WIDTH/2 ;
  133.                         y2 += CELL_WIDTH/2 ;
  134.                         int x3 = x1 - CELL_WIDTH/2 ;
  135.                         dc.MoveTo(x1,y1) ;
  136.                         dc.LineTo(x3,y1) ;                
  137.                         dc.LineTo(x3,y2) ;    
  138.                         dc.LineTo(x2,y2) ;
  139.                         continue ;
  140.                         }
  141.                     x1 += CELL_WIDTH/2 ;
  142.                     x2 += CELL_WIDTH/2 ;
  143.                     }
  144.                 if (y1 < y2)
  145.                     y1 += CELL_HEIGHT ;
  146.                 else    
  147.                 if (y2 < y1)
  148.                     y2 += CELL_HEIGHT ;
  149.                 else
  150.                 if (y1 == y2) {          
  151.                     if (Abs(col1 - col2) > 1) { //route around!
  152.                         if (x1 < x2) {
  153.                             x1 -= CELL_WIDTH/2 ;
  154.                             x2 += CELL_WIDTH/2 ;
  155.                             }
  156.                         else {
  157.                             x1 += CELL_WIDTH/2 ;
  158.                             x2 -= CELL_WIDTH/2 ;
  159.                             }
  160.                         int y3 = y1 - CELL_HEIGHT/2 ;
  161.                         dc.MoveTo(x1,y1) ;
  162.                         dc.LineTo(x1,y3) ;                
  163.                         dc.LineTo(x2,y3) ;    
  164.                         dc.LineTo(x2,y2) ;
  165.                         continue ;
  166.                         }
  167.                     y1 += CELL_HEIGHT/2 ;
  168.                     y2 += CELL_HEIGHT/2 ;
  169.                     }
  170.                             
  171.                 dc.MoveTo(x1,y1) ;
  172.                 dc.LineTo(x2,y2) ;                
  173.                 }    
  174.                 
  175.     dc.SelectObject(pPen ) ;
  176. }
  177.  
  178. //Calculate the length of the chromosome needed to encode
  179. //a drawing of the graph in a grid    
  180. UINT CGAGraphDriver::CalcChromosomeLength() const                          
  181. {
  182.     return m_NumGraphNodes*(GetNumBitsToEncode(m_GridHeight)+GetNumBitsToEncode(m_GridWidth));
  183. }
  184.  
  185. UINT CGAGraphDriver::CalcRowAlleleLength() const  
  186. {   
  187.     return (UINT) GetNumBitsToEncode(m_GridWidth) ;
  188. }
  189.  
  190. UINT CGAGraphDriver::CalcColAlleleLength() const  
  191. {
  192.     return (UINT) GetNumBitsToEncode(m_GridHeight) ;
  193. }
  194.  
  195. //Return TRUE if node1 is connected to node2
  196. BOOL CGAGraphDriver::Connected(WORD node1, WORD node2) const 
  197. {
  198.     return  m_pGraph->GetAt(node1,node2) ;
  199. }
  200.  
  201. //Returns the  number of connection leaving node
  202. int CGAGraphDriver::GetNumConnections(WORD node) const 
  203. {                                    
  204.     int count = 0 ;
  205.     for (WORD i=0;i<m_NumGraphNodes;i++)
  206.         if (i != node && m_pGraph->GetAt(node,i))
  207.             count++ ;
  208.     return count ;
  209. }
  210.  
  211. //Returns the total number of connections in the graph
  212. int CGAGraphDriver::GetConnectivity() 
  213. {
  214.     int count = 0 ;
  215.     for (WORD node1=0;node1<m_NumGraphNodes;node1++)
  216.         for (WORD node2=0;node2<m_NumGraphNodes;node2++)
  217.             if (node1 != node2 && m_pGraph->GetAt(node1,node2))
  218.                 count ++ ;
  219.     return count ;
  220. }
  221.  
  222. void CGAGraphDriver::Stop() 
  223. {
  224.     m_Stop = TRUE ;
  225. }
  226.