home *** CD-ROM | disk | FTP | other *** search
/ Media Share 13 / mediashare_13.zip / mediashare_13 / ZIPPED / PROGRAM / APR94_1.ZIP / GA.ZIP / SOURCE.ZIP / GRPHPHEN.CPP < prev    next >
C/C++ Source or Header  |  1994-01-10  |  8KB  |  250 lines
  1. //Copyright (C) Man Machine Interfaces 1994. All rights reserved.
  2.  
  3. //grphphen.cpp
  4.  
  5. #include "stdafx.h"
  6. //eos headers
  7. #include "eos.h"
  8. #include "eosutil.h"
  9. #include "geno.h"
  10.  
  11. //graph GA headers
  12. #include "grphphen.h"
  13. #include "wmatrix.h"
  14. #include "gdriver.h"
  15. #include "grphutil.h"
  16.  
  17. const HIGHEST_REWARD = 10 ;
  18. const MEDIUM_REWARD = 5 ;
  19. const SMALLEST_REWARD = 1 ;
  20. const HIGHEST_PENALTY = 10 ;
  21. const MEDIUM_PENALTY = 5;
  22. const SMALLEST_PENALTY = 1;
  23.  
  24. CGraphDrawingPheno::CGraphDrawingPheno(CGAGraphDriver &driver, int width, int height) 
  25.     : m_Driver(driver) 
  26. {
  27.     m_Width = width ;
  28.     m_Height = height ;
  29.     m_pGrid = new CWordMatrix(height,width,EMPTY_CELL) ;  //matricies are in row-col form
  30.     m_GridIndex[0] = new int [m_Driver.GetNumNodes()];
  31.     m_GridIndex[1] = new int [m_Driver.GetNumNodes()];
  32. }
  33.  
  34. CGraphDrawingPheno::~CGraphDrawingPheno() 
  35. {
  36.     delete m_pGrid ;
  37.     delete [] m_GridIndex[0] ;      
  38.     delete [] m_GridIndex[1] ;
  39. }
  40.  
  41. double CGraphDrawingPheno::CalcFitness() 
  42. {
  43.     WORD numNodes = (WORD) m_Driver.GetNumNodes() ;                                 
  44.     long maxDist = (m_Width + m_Height) ;
  45.     maxDist*=maxDist;                               
  46.     //set base fitness so even the worst case phenotype will not bring fitness below 0
  47.     int connectivity = m_Driver.GetConnectivity() ; 
  48.  
  49.     double base_fitness = numNodes*(numNodes-1) * maxDist ; //* connectivity; 
  50.     double fitness = base_fitness ;
  51.     for (WORD node1=0;node1<numNodes;node1++) {
  52.         int node1Connections = Max(m_Driver.GetNumConnections(node1),1);
  53.         for (WORD node2=0;node2<numNodes;node2++) {    
  54.             if (node1 == node2)
  55.                 continue ;
  56.             BOOL bConnected = m_Driver.Connected(node1,node2) ;
  57.             int node2Connections = Max(m_Driver.GetNumConnections(node2),1);
  58.             double distance = Distance(node1,node2) ;
  59.             distance*=distance; 
  60.             if (bConnected && distance > 4)  {
  61.                 fitness -= distance ; //(node1Connections+node2Connections) ;
  62.                 continue ;
  63.                 }
  64.             if (!bConnected && distance <= 4)  {
  65.                 fitness -= 4/distance ; //(node1Connections+node2Connections) ; 
  66.                 continue ;
  67.                 }
  68.             }                                   
  69.         }
  70.     ASSERT(fitness >= 0);    
  71.     return fitness ;
  72. }
  73.  
  74.  
  75.  
  76. void CGraphDrawingPheno::Decode(PTGenotype pGeno) 
  77. {  
  78.     WORD numNodes = (WORD) m_Driver.GetNumNodes() ;                                 
  79.     int rowAlleleLen =  m_Driver.CalcRowAlleleLength() ;
  80.     int colAlleleLen =  m_Driver.CalcColAlleleLength() ;
  81.     int offset = 0 ;
  82.     for (WORD node=0;node<numNodes;node++) {
  83.         char rowAllele[16], colAllele[16] ;     //we know that these are no bigger than sizeof(WORD)
  84.         for(int bit=0;bit<rowAlleleLen;bit++)
  85.             rowAllele[bit] = pGeno->GetExpressedGeneValue(offset++,0) ;
  86.         for(bit=0;bit<colAlleleLen;bit++)
  87.             colAllele[bit] = pGeno->GetExpressedGeneValue(offset++,0) ;
  88.         int codedRow = AllelesToInt(rowAllele,0,    rowAlleleLen-1) ;
  89.         int codedCol = AllelesToInt(colAllele,0,    colAlleleLen-1) ;
  90.         int actualRow, actualCol ;
  91.         GetNearestEmptyCell(codedRow,codedCol,actualRow,actualCol) ;
  92.         m_pGrid->SetAt(actualRow, actualCol, node) ;
  93.         m_GridIndex[0][node] = actualRow ;
  94.         m_GridIndex[1][node] = actualCol ;
  95.         }
  96. }
  97.  
  98. PTPhenotype CGraphDrawingPheno::Copy()  
  99. {
  100.     CGraphDrawingPheno * pPheno= new CGraphDrawingPheno(m_Driver,m_Height,m_Width) ;
  101.     return pPheno ; //don't copy values because these are derived by the genotype via Decode
  102. }
  103.  
  104. void CGraphDrawingPheno::GetPhenoInfo(void *pInfoStruct)  
  105. {
  106.     *((CWordMatrix **)pInfoStruct) = m_pGrid ;
  107. }
  108.        
  109. void CGraphDrawingPheno::GetNearestEmptyCell(const int row, const int col, int &actualRow,int &actualCol)
  110. {
  111.     actualRow = row % m_Height ;
  112.     actualCol = col % m_Width ;    
  113.     if (m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL)
  114.         return ;
  115.     else { //search for "nearest" empty cell
  116.         int maxDist=Max(m_Height,m_Width) ;
  117.         int actualRow2 = actualRow ; //save actuals
  118.         int actualCol2 = actualCol ;
  119.         for (int dist=1;dist<maxDist;dist++) {  //start at a distance of 1 and search outward
  120.             //first check "sides"
  121.             for(int i=-dist; i<=dist;i++) {
  122.                 for(int j=-dist;j<=dist;j++) {
  123.                     if (i!=j && (j==dist || j==-dist || i==dist || i==-dist)) {
  124.                         actualCol = actualCol2+j ;
  125.                         actualRow = actualRow2+i ;
  126.                         if(actualCol >= 0 && actualCol < m_Width && 
  127.                                actualRow >= 0 && actualRow < m_Height && 
  128.                                m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL) 
  129.                             return ;
  130.                         } //if
  131.                     } // for j             
  132.                 } //for i
  133.                 //now check 4 corners
  134.                 actualCol = actualCol2+dist ;
  135.                 actualRow = actualRow2+dist ;
  136.                 if(actualCol < m_Width && 
  137.                        actualRow < m_Height && 
  138.                        m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL) 
  139.                     return ;
  140.                 actualCol = actualCol2-dist ;
  141.                 actualRow = actualRow2+dist ;
  142.                 if(actualCol >= 0 && 
  143.                        actualRow < m_Height && 
  144.                        m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL) 
  145.                     return ;
  146.                 actualCol = actualCol2+dist ;
  147.                 actualRow = actualRow2-dist ;
  148.                 if(actualCol < m_Width && 
  149.                        actualRow >= 0 && 
  150.                        m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL) 
  151.                     return ;
  152.                 actualCol = actualCol2-dist ;
  153.                 actualRow = actualRow2-dist ;
  154.                 if(actualCol >= 0 && 
  155.                        actualRow >= 0 && 
  156.                        m_pGrid->GetAt(actualRow,actualCol) == EMPTY_CELL) 
  157.                     return ;
  158.             } //for dist
  159.         } //else    
  160.     return ;
  161. }
  162.  
  163. BOOL CGraphDrawingPheno::Adjacent(WORD node1, WORD node2) 
  164. {            
  165.     int row1, col1 ;
  166.     if (!FindNode(node1,row1,col1))
  167.         return FALSE ;
  168.     int row2, col2 ;
  169.     //look up
  170.     row2=row1-1 ; 
  171.     if (row2 >= 0 && m_pGrid->GetAt(row2,col1) == node2)
  172.         return TRUE ; 
  173.     //look down
  174.     row2=row1+1 ; 
  175.     if (row2 < m_Height && m_pGrid->GetAt(row2,col1) == node2)
  176.         return TRUE ; 
  177.     //look left    
  178.     col2=col1-1 ; 
  179.     if (col2 >= 0 && m_pGrid->GetAt(row1,col2) == node2)
  180.         return TRUE ; 
  181.     //look right
  182.     col2=col1+1 ; 
  183.     if (col2 < m_Width && m_pGrid->GetAt(row1,col2) == node2)
  184.         return TRUE ; 
  185.     return FALSE ;
  186. }
  187.  
  188.  
  189. BOOL CGraphDrawingPheno::Diagonal(WORD node1, WORD node2) 
  190. {
  191.     int row1, col1 ;
  192.     if (!FindNode(node1,row1,col1))
  193.         return FALSE ;
  194.     int row2, col2 ;
  195.     //look upper left
  196.     row2=row1-1 ; 
  197.     col2=col1-1 ;
  198.     if (row2 >= 0 && col2 >= 0 && m_pGrid->GetAt(row2,col2) == node2)
  199.         return TRUE ; 
  200.     //look lower left
  201.     row2=row1+1 ; 
  202.     col2=col1-1 ;
  203.     if (row2 < m_Height && col2 >= 0 && m_pGrid->GetAt(row2,col1) == node2)
  204.         return TRUE ; 
  205.     //look lower right    
  206.     row2=row1+1 ; 
  207.     col2=col1+1 ; 
  208.     if (row2 < m_Height && col2 < m_Width && m_pGrid->GetAt(row1,col2) == node2)
  209.         return TRUE ; 
  210.     //look upper left
  211.     row2=row1-1 ; 
  212.     col2=col1+1 ; 
  213.     if (row2 >= 0 && col2 < m_Width && m_pGrid->GetAt(row1,col2) == node2)
  214.         return TRUE ; 
  215.     return FALSE ;
  216. }
  217.  
  218. double CGraphDrawingPheno::Distance(WORD node1, WORD node2) 
  219. {
  220.     int row1, col1, row2, col2 ;
  221.     if (FindNode(node1,row1,col1) && FindNode(node2,row2,col2)) {
  222.         double diffRow = row1 - row2 ;
  223.         double diffCol = col1 - col2 ;
  224.         return sqrt(diffRow*diffRow + diffCol*diffCol) ;
  225.         }
  226.     else
  227.         return sqrt(m_Height*m_Height + m_Width*m_Width) ; //really an error ?!?
  228. }
  229.  
  230. double CGraphDrawingPheno::RectDistance(WORD node1, WORD node2) 
  231. {
  232.     int row1, col1, row2, col2 ;
  233.     if (FindNode(node1,row1,col1) && FindNode(node2,row2,col2)) {
  234.         double diffRow = row1 - row2 ;
  235.         double diffCol = col1 - col2 ;
  236.         return Abs(diffRow) + Abs(diffCol) ;
  237.         }
  238.     else
  239.         return m_Height + m_Width ; //really an error ?!?
  240. }
  241.  
  242. BOOL CGraphDrawingPheno::FindNode(const WORD node, int &row, int &col) 
  243. {   
  244.     if (node >= m_Driver.GetNumNodes())
  245.         return FALSE ;
  246.     row = m_GridIndex[0][node] ;
  247.     col = m_GridIndex[1][node] ;
  248.     return TRUE ;
  249. }
  250.