home *** CD-ROM | disk | FTP | other *** search
/ Media Share 13 / mediashare_13.zip / mediashare_13 / ZIPPED / PROGRAM / APR94_1.ZIP / GA.ASC < prev    next >
Text File  |  1994-02-27  |  23KB  |  669 lines
  1. _ALGORITHMS FOR DIRECTED GRAPHS_
  2. by Salvatore R. Mangano
  3.  
  4. Listing One
  5.  
  6. //File: GRPHPHEN.H
  7.  
  8. #ifndef __GRPHPHEN_H
  9. #define __GRPHPHEN_H
  10.  
  11. //Header for EOS class representing a phenotype. 
  12. //You need EOS v1.1 to compile this code
  13. #ifndef __PHENO_H
  14. #include "pheno.h"
  15. #endif //__PHENO_H
  16.                                                         
  17. class CGraphDrawingPheno : public TPhenotype
  18. {
  19.    public:         
  20.     CGraphDrawingPheno(CGAGraphDriver &driver,int width, int height) ;
  21.     ~CGraphDrawingPheno() ;
  22.     double CalcFitness() ;
  23.     void Decode(PTGenotype geno) ;
  24.     PTPhenotype Copy()  ;
  25.     void GetPhenoInfo(void *pInfoStruct)  ;
  26.     void GetNearestEmptyCell(const int row, const int col, int &actualRow,
  27.                                                              int &actualCol) ;
  28.     BOOL Adjacent(WORD node1, WORD node2) ;
  29.     BOOL Diagonal(WORD node1, WORD node2) ;
  30.     BOOL FindNode(const WORD node, int &row, int &col) ;
  31.     double Distance(WORD node1, WORD node2) ;
  32.     double RectDistance(WORD node1, WORD node2) ;
  33. private:
  34.     int m_Width  ;
  35.     int m_Height ;
  36.     CWordMatrix *m_pGrid ;      //grid where each entry is a node 
  37.                                     //                 number or EMPTY_CELL
  38.     CGAGraphDriver &m_Driver ;  //interface to the graph driver class
  39.     int * m_GridIndex[2] ;      //index into grid to quickly locate nodes
  40. };
  41.  
  42. Listing Two
  43.  
  44. //File: GRPHPHEN.CPP
  45.  
  46. #include "stdafx.h"
  47. //eos headers
  48. #include "eos.h"
  49. #include "eosutil.h"
  50. #include "geno.h"
  51.  
  52. //graph GA headers
  53. #include "grphphen.h"
  54. #include "wmatrix.h"
  55. #include "gdriver.h"
  56. #include "grphutil.h"
  57.  
  58. const HIGHEST_REWARD = 10 ;
  59. const MEDIUM_REWARD = 5 ;
  60. const SMALLEST_REWARD = 1 ;
  61. const HIGHEST_PENALTY = 10 ;
  62. const MEDIUM_PENALTY = 5;
  63. const SMALLEST_PENALTY = 1;
  64.  
  65. CGraphDrawingPheno::CGraphDrawingPheno(CGAGraphDriver &driver, int width, int height) 
  66.     : m_Driver(driver) 
  67. {
  68.     m_Width = width ;
  69.     m_Height = height ;
  70.     m_pGrid = new CWordMatrix(height,width,EMPTY_CELL) ;  
  71.     m_GridIndex[0] = new int [m_Driver.GetNumNodes()];
  72.     m_GridIndex[1] = new int [m_Driver.GetNumNodes()];
  73. }
  74. CGraphDrawingPheno::~CGraphDrawingPheno() 
  75. {
  76.     delete m_pGrid ;
  77.     delete [] m_GridIndex[0] ;      
  78.     delete [] m_GridIndex[1] ;
  79. }
  80. double CGraphDrawingPheno::CalcFitness() 
  81. {
  82.     WORD numNodes = (WORD) m_Driver.GetNumNodes() ;
  83.     long maxDist = (m_Width + m_Height) ;
  84.     maxDist*=maxDist;                               
  85.     //set base fitness so even the worst case phenotype 
  86.         //           will not bring fitness below 0
  87.     int connectivity = m_Driver.GetConnectivity() ; 
  88.     double base_fitness = numNodes*(numNodes-1) * maxDist ; 
  89.                                                             //* connectivity; 
  90.     double fitness = base_fitness ;
  91.     for (WORD node1=0;node1<numNodes;node1++) {
  92.         int node1Connections=Max(m_Driver.GetNumConnections(node1),1);
  93.         for (WORD node2=0;node2<numNodes;node2++) {    
  94.             if (node1 == node2)
  95.                 continue ;
  96.             BOOL bConnected = m_Driver.Connected(node1,node2) ;
  97.             int node2Connections = 
  98.                                       Max(m_Driver.GetNumConnections(node2),1);
  99.             double distance = Distance(node1,node2) ;
  100.             distance*=distance; 
  101.             if (bConnected && distance > 4)  {
  102.                 fitness -= distance ; 
  103.                                        //(node1Connections+node2Connections) ;
  104.                 continue ;
  105.                 }
  106.             if (!bConnected && distance <= 4)  {
  107.                 fitness -= 4/distance ; 
  108.                                         //(node1Connections+node2Connections) ; 
  109.                 continue ;
  110.                 }
  111.             }                                   
  112.         }
  113.     ASSERT(fitness >= 0);   
  114.     return fitness ;
  115. }
  116. void CGraphDrawingPheno::Decode(PTGenotype pGeno) 
  117. {  
  118.     WORD numNodes = (WORD) m_Driver.GetNumNodes() ;
  119.     int rowAlleleLen =  m_Driver.CalcRowAlleleLength() ;
  120.     int colAlleleLen =  m_Driver.CalcColAlleleLength() ;
  121.     int offset = 0 ;
  122.     for (WORD node=0;node<numNodes;node++) {
  123.         char rowAllele[16], colAllele[16] ;     
  124.                            //we know that these are no bigger than sizeof(WORD)
  125.         for(int bit=0;bit<rowAlleleLen;bit++)
  126.             rowAllele[bit] = 
  127.                                      pGeno->GetExpressedGeneValue(offset++,0) ;
  128.         for(bit=0;bit<colAlleleLen;bit++)
  129.             colAllele[bit] = 
  130.                                      pGeno->GetExpressedGeneValue(offset++,0) ;
  131.         int codedRow = AllelesToInt(rowAllele,0, rowAlleleLen-1) ;
  132.         int codedCol = AllelesToInt(colAllele,0, colAlleleLen-1) ;
  133.         int actualRow, actualCol ;
  134.         GetNearestEmptyCell(codedRow,codedCol,actualRow,actualCol) ;
  135.         m_pGrid->SetAt(actualRow, actualCol, node) ;
  136.         m_GridIndex[0][node] = actualRow ;
  137.         m_GridIndex[1][node] = actualCol ;
  138.         }
  139. }
  140. PTPhenotype CGraphDrawingPheno::Copy()  
  141. {
  142.     CGraphDrawingPheno * pPheno = 
  143.                             new CGraphDrawingPheno(m_Driver,m_Height,m_Width) ;
  144.     return pPheno ; 
  145.        //don't copy values because these are derived by the genotype via Decode
  146. }
  147. void CGraphDrawingPheno::GetPhenoInfo(void *pInfoStruct)  
  148. {
  149.     *((CWordMatrix **)pInfoStruct) = m_pGrid ;
  150. }
  151. //Algorithm resolves collisions by searching around the neighborhood of 
  152. // (row,col) in the grid for an empty cell. The row and col of the empty cell 
  153. // is returned in actualRow and actualCol.       
  154. void CGraphDrawingPheno::GetNearestEmptyCell(const int row, const int col, 
  155.                                                  int &actualRow,int &actualCol)
  156. {
  157.     //insure we are in range!
  158.     actualRow = row % m_Height ; 
  159.     actualCol = col % m_Width ; 
  160.     //if we find and empty cell then no search necessary
  161.     if (m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL)
  162.         return ;
  163.     else { //search for "nearest" empty cell
  164.         int maxDist=Max(m_Height,m_Width) ;
  165.         int actualRow2 = actualRow ; //save actuals
  166.         int actualCol2 = actualCol ;
  167.          //start at a distance of 1 and search outward
  168.         for (int dist=1;dist<maxDist;dist++) { 
  169.             //First check "sides"
  170.             for(int i=-dist; i<=dist;i++) {
  171.                 for(int j=-dist;j<=dist;j++) {
  172.                          if (i!=j && (j==dist || j==-dist || 
  173.                                                         i==dist || i==-dist)) {
  174.                         actualCol = actualCol2+j ;
  175.                         actualRow = actualRow2+i ;
  176.                         if(actualCol >= 0 && actualCol 
  177.                                                                  < m_Width && 
  178.                            actualRow >= 0 && actualRow
  179.                                                                  < m_Height && 
  180.                     m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL) 
  181.                             return ;
  182.                         } //if
  183.                     } // for j             
  184.                 } //for i
  185.                 //Now check 4 corner cells
  186.                 actualCol = actualCol2+dist ;
  187.                 actualRow = actualRow2+dist ;
  188.                 if(actualCol < m_Width && 
  189.                     actualRow < m_Height && 
  190.                         m_pGrid->GetAt(actualRow,actualCol) ==
  191.                                                                    EMPTY_CELL) 
  192.                     return ;
  193.                 actualCol = actualCol2-dist ;
  194.                 actualRow = actualRow2+dist ;
  195.                 if(actualCol >= 0 && 
  196.                     actualRow < m_Height && 
  197.                     m_pGrid->GetAt(actualRow,actualCol) ==
  198.                                                                     EMPTY_CELL)
  199.                     return ;
  200.                 actualCol = actualCol2+dist ;
  201.                 actualRow = actualRow2-dist ;
  202.                 if(actualCol < m_Width && 
  203.                     actualRow >= 0 && 
  204.                     m_pGrid->GetAt(actualRow,actualCol) == 
  205.                                                                     EMPTY_CELL)
  206.                     return ;
  207.                 actualCol = actualCol2-dist ;
  208.                 actualRow = actualRow2-dist ;
  209.                 if(actualCol >= 0 && 
  210.                     actualRow >= 0 && 
  211.                     m_pGrid->GetAt(actualRow,actualCol) == 
  212.                                                                     EMPTY_CELL)
  213.                     return ;
  214.             } //for dist
  215.         } //else    
  216.     return ;
  217. }
  218. //Return TRUE if node1 is adjacent to node2 on the grid
  219. BOOL CGraphDrawingPheno::Adjacent(WORD node1, WORD node2) 
  220. {            
  221.     int row1, col1 ;
  222.     if (!FindNode(node1,row1,col1))
  223.         return FALSE ;
  224.     int row2, col2 ;
  225.     //look up
  226.     row2=row1-1 ; 
  227.     if (row2 >= 0 && m_pGrid->GetAt(row2,col1) == node2)
  228.         return TRUE ; 
  229.     //look down
  230.     row2=row1+1 ; 
  231.     if (row2 < m_Height && m_pGrid->GetAt(row2,col1) == node2)
  232.         return TRUE ; 
  233.     //look left 
  234.     col2=col1-1 ; 
  235.     if (col2 >= 0 && m_pGrid->GetAt(row1,col2) == node2)
  236.         return TRUE ; 
  237.     //look right
  238.     col2=col1+1 ; 
  239.     if (col2 < m_Width && m_pGrid->GetAt(row1,col2) == node2)
  240.         return TRUE ; 
  241.     return FALSE ;
  242. }
  243. //Return TRUE if node1 is diagonal to node2 on the grid
  244. BOOL CGraphDrawingPheno::Diagonal(WORD node1, WORD node2) 
  245. {
  246.     int row1, col1 ;
  247.     if (!FindNode(node1,row1,col1))
  248.         return FALSE ;
  249.     int row2, col2 ;
  250.     //look upper left
  251.     row2=row1-1 ; 
  252.     col2=col1-1 ;
  253.     if (row2 >= 0 && col2 >= 0 && m_pGrid->GetAt(row2,col2) == node2)
  254.         return TRUE ; 
  255.     //look lower left
  256.     row2=row1+1 ; 
  257.     col2=col1-1 ;
  258.     if (row2 < m_Height && col2 >= 0 && m_pGrid->GetAt(row2,col1) == node2)
  259.         return TRUE ; 
  260.     //look lower right  
  261.     row2=row1+1 ; 
  262.     col2=col1+1 ; 
  263.     if (row2 < m_Height && col2 < m_Width && m_pGrid->GetAt(row1,col2) == 
  264.                                                                          node2)
  265.         return TRUE ; 
  266.     //look upper left
  267.     row2=row1-1 ; 
  268.     col2=col1+1 ; 
  269.     if (row2 >= 0 && col2 < m_Width && m_pGrid->GetAt(row1,col2) == node2)
  270.         return TRUE ; 
  271.     return FALSE ;
  272. }
  273. //Return the Euclidean distance between nodes on the grid
  274. double CGraphDrawingPheno::Distance(WORD node1, WORD node2) 
  275. {
  276.     int row1, col1, row2, col2 ;
  277.     if (FindNode(node1,row1,col1) && FindNode(node2,row2,col2)) {
  278.         double diffRow = row1 - row2 ;
  279.         double diffCol = col1 - col2 ;
  280.         return sqrt(diffRow*diffRow + diffCol*diffCol) ;
  281.         }
  282.     else
  283.         return sqrt(m_Height*m_Height + m_Width*m_Width) ; 
  284. }
  285. //Return the recti-linear distance between nodes on the grid
  286. double CGraphDrawingPheno::RectDistance(WORD node1, WORD node2) 
  287. {
  288.     int row1, col1, row2, col2 ;
  289.     if (FindNode(node1,row1,col1) && FindNode(node2,row2,col2)) {
  290.         double diffRow = row1 - row2 ;
  291.         double diffCol = col1 - col2 ;
  292.         return Abs(diffRow) + Abs(diffCol) ;
  293.         }
  294.     else
  295.         return m_Height + m_Width ; //really an error ?!?
  296. }
  297. //Use an index to quickly locate a node on the grid
  298. BOOL CGraphDrawingPheno::FindNode(const WORD node, int &row, int &col) 
  299. {   
  300.     if (node >= m_Driver.GetNumNodes())
  301.         return FALSE ;
  302.     row = m_GridIndex[0][node] ;
  303.     col = m_GridIndex[1][node] ;
  304.     return TRUE ;
  305. }
  306.  
  307.  
  308. Listing Three
  309.  
  310. //File: GDRIVER.H
  311.  
  312. #ifndef __GDRIVER_H__
  313. #define __GDRIVER_H__
  314. //flag an empty cell in the grid    
  315. const EMPTY_CELL = 0xFFFF ;
  316.  
  317. class CGAGraphDriver
  318. {           
  319.     //Interface
  320. public:
  321.     CGAGraphDriver(int numNodes, int width, int height) ;
  322.     ~CGAGraphDriver() ;
  323.     void SetGraph(CWordMatrix &graph) ;
  324.     void Optimize(int numGenrations) ;
  325.     void DrawOptimized(CDC &dc) ;
  326.     void DrawUnOptimized(CDC &dc) ;
  327.     //Query members (const)
  328.     //Calc the length of a chromosome
  329.     //needed based on the graph and grid
  330.     UINT CalcChromosomeLength() const ;                         
  331.     UINT CalcRowAlleleLength() const ; ;
  332.     UINT CalcColAlleleLength() const ; ;
  333.     int GetWidth() const ;
  334.     int GetHeight() const ;
  335.     int GetNumNodes() const ;
  336.     BOOL Connected(WORD node1, WORD node2)  const;  
  337.     int GetNumConnections(WORD node) const ;
  338.     int GetConnectivity() ; 
  339.     void Stop() ;
  340.     PTIndividual m_pBest ;
  341.     PTIndividual m_pWorst ;
  342.     BOOL m_Stop ;
  343.     //Implementation
  344. private:
  345.     //Draw the graph in this grid
  346.     void Draw(CDC &dc, CWordMatrix &Grid) ;
  347.     //num nodes in the graph
  348.     int m_NumGraphNodes ;                   
  349.     //width of grid to draw on (in cells)
  350.     int m_GridWidth ;           
  351.     //height of grid to draw on (in cells)          
  352.     int m_GridHeight ;           
  353.     //connection table representation of a graph
  354.     CWordMatrix *m_pGraph ;      
  355.     //GA that will find the "optimal" drawing   
  356.     //of the graph on the grid
  357.     TBasicGA  *m_pTheGA ;         
  358. } ;
  359.  
  360. Listing Four
  361.  
  362. //File: GDRIVER.CPP
  363.  
  364. //Used as an interface class to the GA.
  365. //Stores the representation of the graph as
  366. //a connection grid.
  367.                             
  368. //required headers                            
  369. #include "stdafx.h"
  370.  
  371. //Headers needed for EOS programs
  372. //You need EOS v1.1 to compile this code
  373. #include "eos.h"   
  374. #include "eosutil.h"   
  375. #include "geno.h"
  376. #include "individ.h"
  377. #include "gaenviro.h"
  378.  
  379. //headers specific to graph GA
  380. #include "wmatrix.h"
  381. #include "gdriver.h"
  382. #include "grphutil.h"
  383. #include "graphga.h"
  384.  
  385. //GA parameters used, these need not be
  386. //hard coded in advanced implementations
  387. const int POP_SIZE = 20 ;
  388. const double PX = 0.7 ;
  389. const double PM = 0.03 ;
  390. const double RAND_SEED=0.76451 ;
  391.  
  392. //DRAWING parameters used, these need not be
  393. //hard coded in advanced implementations
  394. const int CELL_WIDTH = 30 ;
  395. const int CELL_HEIGHT = 30  ;
  396. const int CELL_SPACE = 30 ;
  397.  
  398. //Driver constructor initializes a graph with  numNodes and a 
  399. //grid that the graph will be optimized to draw on (width x height)
  400. CGAGraphDriver::CGAGraphDriver(int numNodes, int width, int height) 
  401. {           
  402.     m_NumGraphNodes = numNodes;        
  403.     m_GridWidth = width ;                       
  404.     m_GridHeight = height ;
  405.     //graph represented as boolean connection matrix
  406.     m_pGraph = new CWordMatrix(m_NumGraphNodes,m_NumGraphNodes) ; 
  407.     //The Graph GA object
  408.     m_pTheGA = new CGraphDrawerGA(*this) ;
  409.     m_pBest = NULL ;
  410.     m_pWorst = NULL ;
  411.     m_Stop = FALSE ;
  412. }   
  413. //Clean up in the destructor     
  414. CGAGraphDriver::~CGAGraphDriver() 
  415. {
  416.     delete m_pGraph ;
  417.     delete m_pTheGA ;
  418. }
  419. //set the conections from graph into the member m_pGraph
  420. void CGAGraphDriver::SetGraph(CWordMatrix &graph) 
  421. {
  422.     for (int row = 0 ; row < m_NumGraphNodes; row++)
  423.         for (int col = 0 ; col < m_NumGraphNodes; col++)
  424.             m_pGraph->SetAt(row,col,graph[row][col]) ;  
  425. }
  426. // Optimize the drawing of the graph by first initializing the GA's population 
  427. // and environment. Then execute the GA for numGenerations generations
  428. void CGAGraphDriver::Optimize(int numGenerations) 
  429. {
  430.     m_pTheGA->CreatePopulation(POP_SIZE) ;
  431.     m_pTheGA->CreateEnvironment(PX,PM,RAND_SEED) ;
  432.     m_pTheGA->Evolve(numGenerations) ;
  433. }
  434. //Draw the optimized graph on the Windows DC
  435. void CGAGraphDriver::DrawOptimized(CDC &dc) 
  436. {
  437.     CWordMatrix *pGrid ;
  438.     m_pBest->GetPhenoInfo(&pGrid) ;
  439.     Draw(dc,*pGrid) ;
  440. }
  441. //Draw the un-optimized graph on the Windows DC
  442. void CGAGraphDriver::DrawUnOptimized(CDC &dc)
  443. {
  444.     CWordMatrix *pGrid ;
  445.     m_pWorst->GetPhenoInfo(&pGrid) ;
  446.     Draw(dc,*pGrid) ;
  447. }
  448. void CGAGraphDriver::Draw(CDC &dc, CWordMatrix &Grid)
  449. {   
  450.     CPen *pPen = (CPen *) dc.SelectStockObject(BLACK_PEN) ;
  451.     for (int row = 0 ; row < m_GridHeight; row++)
  452.         for (int col = 0 ; col < m_GridWidth; col++) {
  453.            if (Grid[row][col] != EMPTY_CELL)  {
  454.               int x1 = col * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
  455.               int x2 = x1 + CELL_WIDTH    ;
  456.               int y1 = row * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
  457.               int y2 = y1 + CELL_HEIGHT   ;
  458.               dc.Ellipse(x1,y1,x2,y2) ;                   
  459.               char buffer[4] ;
  460.               sprintf(buffer,"%d",Grid[row][col]) ;
  461.               dc.TextOut(x1+CELL_WIDTH/4,y1+CELL_HEIGHT/4,buffer,
  462.                                                               strlen(buffer)) ;
  463.               }
  464.            }       
  465.     //draw arcs     
  466.     for (int node1 = 0 ; node1 < m_NumGraphNodes; node1++)
  467.         for (int node2 = 0 ; node2 < m_NumGraphNodes; node2++)
  468.             if (m_pGraph->GetAt(node1,node2)) {
  469.                int row1, col1 ;
  470.                Grid.Find(node1, row1, col1) ;
  471.                int row2, col2 ;
  472.                Grid.Find(node2, row2, col2) ;
  473.                int x1 = col1 * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
  474.                int x2 = col2 * (CELL_WIDTH + CELL_SPACE) + CELL_SPACE ;
  475.              int y1 = row1 * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
  476.              int y2 = row2 * (CELL_HEIGHT + CELL_SPACE)  + CELL_SPACE ;
  477.              if (x1 < x2)
  478.              x1 += CELL_WIDTH ;
  479.              else   
  480.                 if (x2 < x1)
  481.                     x2 += CELL_WIDTH ;
  482.                 else    
  483.                 if (x1 == x2) {
  484.                     if (Abs(row1 - row2) > 1) { //route around!
  485.                         y1 += CELL_WIDTH/2 ;
  486.                         y2 += CELL_WIDTH/2 ;
  487.                         int x3 = x1 - CELL_WIDTH/2 ;
  488.                         dc.MoveTo(x1,y1) ;
  489.                         dc.LineTo(x3,y1) ;
  490.                         dc.LineTo(x3,y2) ;  
  491.                         dc.LineTo(x2,y2) ;
  492.                         continue ;
  493.                         }
  494.                     x1 += CELL_WIDTH/2 ;
  495.                     x2 += CELL_WIDTH/2 ;
  496.                     }
  497.                 if (y1 < y2)
  498.                     y1 += CELL_HEIGHT ;
  499.                 else    
  500.                 if (y2 < y1)
  501.                     y2 += CELL_HEIGHT ;
  502.                 else
  503.                 if (y1 == y2) {          
  504.                     if (Abs(col1 - col2) > 1) { //route around!
  505.                         if (x1 < x2) {
  506.                             x1 -= CELL_WIDTH/2 ;
  507.                             x2 += CELL_WIDTH/2 ;
  508.                             }
  509.                         else {
  510.                             x1 += CELL_WIDTH/2 ;
  511.                             x2 -= CELL_WIDTH/2 ;
  512.                             }
  513.                         int y3 = y1 - CELL_HEIGHT/2 ;
  514.                         dc.MoveTo(x1,y1) ;
  515.                         dc.LineTo(x1,y3) ;
  516.                         dc.LineTo(x2,y3) ;  
  517.                         dc.LineTo(x2,y2) ;
  518.                         continue ;
  519.                         }
  520.                     y1 += CELL_HEIGHT/2 ;
  521.                     y2 += CELL_HEIGHT/2 ;
  522.                     }
  523.                             
  524.                 dc.MoveTo(x1,y1) ;
  525.                 dc.LineTo(x2,y2) ;
  526.                 }   
  527.                 
  528.     dc.SelectObject(pPen ) ;
  529. }
  530. //Calculate the length of the chromosome needed to encode
  531. //a drawing of the graph in a grid  
  532. UINT CGAGraphDriver::CalcChromosomeLength() const                          
  533. {
  534.        return m_NumGraphNodes*(GetNumBitsToEncode(m_GridHeight) + 
  535.                                               GetNumBitsToEncode(m_GridWidth));
  536. }
  537. UINT CGAGraphDriver::CalcRowAlleleLength() const  
  538. {   
  539.     return (UINT) GetNumBitsToEncode(m_GridWidth) ;
  540. }
  541.  
  542. UINT CGAGraphDriver::CalcColAlleleLength() const  
  543. {
  544.     return (UINT) GetNumBitsToEncode(m_GridHeight) ;
  545. }
  546. //Return TRUE if node1 is connected to node2
  547. BOOL CGAGraphDriver::Connected(WORD node1, WORD node2) const 
  548. {
  549.     return  m_pGraph->GetAt(node1,node2) ;
  550. }
  551. //Returns the  number of connection leaving node
  552. int CGAGraphDriver::GetNumConnections(WORD node) const 
  553. {                                    
  554.     int count = 0 ;
  555.     for (WORD i=0;i<m_NumGraphNodes;i++)
  556.         if (i != node && m_pGraph->GetAt(node,i))
  557.             count++ ;
  558.     return count ;
  559. }
  560. //Returns the total number of connections in the graph
  561. int CGAGraphDriver::GetConnectivity() 
  562. {
  563.     int count = 0 ;
  564.     for (WORD node1=0;node1<m_NumGraphNodes;node1++)
  565.         for (WORD node2=0;node2<m_NumGraphNodes;node2++)
  566.             if (node1 != node2 && m_pGraph->GetAt(node1,node2))
  567.                 count ++ ;
  568.     return count ;
  569. }
  570. void CGAGraphDriver::Stop() 
  571. {
  572.     m_Stop = TRUE ;
  573. }
  574.  
  575. Listing Five
  576.  
  577. //File: GRAPHGA.H
  578.  
  579. #ifndef __GRAPHGA_H__
  580. #define __GRAPHGA_H__
  581.  
  582. //Headers needed for EOS programs
  583. //You need EOS v1.1 to compile this code
  584. #ifndef __BASICGA_H
  585. #include "basicga.h"
  586. #endif
  587.  
  588. class CGraphDrawerGA : public TBasicGA
  589. {
  590. public:
  591.     CGraphDrawerGA(CGAGraphDriver &driver) ;
  592.     void CreatePopulation(long size, PTIndividual prototype = NULL) ;
  593.     void ExitReport() ;
  594.  
  595. private:
  596.     BOOL Stop() ;
  597.     void InterGeneration(ulong, PTIndividual, PTIndividual, PTIndividual, PTIndividual) ;
  598.     CGAGraphDriver & m_Driver ;
  599. };
  600. #endif
  601.  
  602.  
  603. Listing Six
  604.  
  605. //File: GRAPHGA.CPP
  606.  
  607. #include "stdafx.h"
  608.  
  609. //Headers needed for EOS programs
  610. //You need EOS v1.1 to compile this code
  611. #include "eos.h"
  612. #include "geno.h"
  613. #include "basicga.h"
  614. #include "nptxgeno.h"
  615. #include "genrepop.h"
  616. #include "gaenviro.h"
  617.  
  618. //headers specific to graph GA
  619. #include "gdriver.h"
  620. #include "graphga.h"
  621. #include "graphind.h"
  622. #include "grphphen.h"
  623. #include "wmatrix.h"
  624.  
  625. CGraphDrawerGA::CGraphDrawerGA(CGAGraphDriver &driver) 
  626.     : m_Driver(driver)
  627. {
  628. }
  629. //Create the population of individuals
  630. //We use 2 Point Crossover and Elitism
  631. void CGraphDrawerGA::CreatePopulation(long size, PTIndividual prototype) 
  632. {
  633.     //Create a genotype with 1 chromosome and 2 point crossover 
  634.     //The graph driver is queried to determine the chromosome length
  635.     PTNPtCrossGenotype pGeno = 
  636.                    new TNPtCrossGenotype(m_Driver.CalcChromosomeLength(),1,2) ;
  637.     CGraphDrawingPheno * pPheno = 
  638.         new CGraphDrawingPheno(m_Driver,m_Driver.GetWidth(),
  639.                                 m_Driver.GetHeight()) ;
  640.     CGraphDrawingInd indiv(pGeno,pPheno);
  641.     m_pPopulation = new TGenReplacePopulation(size,&indiv) ;
  642.     m_pPopulation->SetElitism(2) ;
  643. }
  644. //When the GA is done set the best and worst individuals in the driver
  645. void CGraphDrawerGA::ExitReport() 
  646. {   
  647.     m_Driver.m_pBest = m_pEnvironment->GlobalFittestIndivid ;
  648.     m_Driver.m_pWorst = m_pEnvironment->GlobalWorstIndivid ;
  649. }
  650. //allow for windows processing!
  651. void CGraphDrawerGA::InterGeneration(ulong, PTIndividual, PTIndividual, 
  652.                                                    PTIndividual, PTIndividual) 
  653. {
  654.     MSG msg ;            
  655.     //while there are msgs for status window
  656.     while (PeekMessage(&msg,AfxGetApp()->m_pMainWnd->
  657.                                                     m_hWnd,0,0,PM_REMOVE)) {
  658.         TranslateMessage(&msg) ;
  659.         DispatchMessage(&msg) ;
  660.         }
  661.     SetCursor(LoadCursor(NULL, IDC_WAIT));
  662. }
  663. //GA calls this function to determine if it should stop    
  664. BOOL CGraphDrawerGA::Stop() 
  665. {
  666.     return m_Driver.m_Stop ;
  667. }
  668.  
  669.