TSPgeneticProblem.java

//Problem trgovskega potnika pripravljen za resevanje z genetskim algoritmom
 
public class TSPgeneticProblem extends TSPproblem implements GeneticProblem {
 
  public TSPgeneticProblem(int sz) {
    super(sz);
  }
  public SolutionSearchState newState() {
    return new TSPsolutionState(this) ;
  }
   public SolutionSearchState randomState() {
     TSPsolutionState s = new TSPsolutionState(this)  ;
     s.setRandom();
     return s ;
   }
   public void crossover(SolutionSearchState state1, SolutionSearchState state2,
                      SolutionSearchState crs1, SolutionSearchState crs2) {
      // krizani del je med tockama cross1 in cross2, ostalo se nakljucno doloci
      TSPsolutionState s1 = (TSPsolutionState) state1 ;
      TSPsolutionState s2 = (TSPsolutionState) state2 ;
      TSPsolutionState c1 = (TSPsolutionState) crs1 ;
      TSPsolutionState c2 = (TSPsolutionState) crs2 ;
      c1.walk = new int[size] ;
      c2.walk = new int[size] ;
      c1.walkLen = c2.walkLen = size ;
      int i, j, cross1, cross2 ;
      cross1 = (int)((size-1) * Math.random()) ;
      cross2 = (int)((size-1) * Math.random()) ;
      if (cross1 > cross2) {
        i = cross1 ;
        cross1 = cross2 ;
        cross2 = i ;
      }
      for (i=cross1 ; i <= cross2 ; i++) {
        c1.walk[i] = s1.walk[i] ;
        c2.walk[i] = s2.walk[i] ;
      }
      int u1[] = new int[size] ;
      int u2[] = new int[size] ;
      for (i=0 ; i < size ; i++)
        u1[i] = u2[i] = i ;
      int used = size  ;
      for (i=cross1 ; i <= cross2 ; i++) {
        for (j = 0; j < used; j++)
          if (u1[j] == c1.walk[i]) {
            u1[j] = u1[used - 1];
            break ;
          }
        for (j = 0; j < used; j++)
          if (u2[j] == c2.walk[i]) {
            u2[j] = u2[used - 1];
            break ;
          }
        used -- ;
      }
      int rnd ;
      for (i=cross2+1 ; i < size ; i++) {
        rnd = (int)(Math.random()*used) ;
        c1.walk[i] = u1[rnd] ;
        c2.walk[i] = u2[rnd] ;
        u1[rnd] = u1[used-1] ;
        u2[rnd] = u2[used-1] ;
        used -- ;
      }
      for (i=0 ; i < cross1 ; i++) {
        rnd = (int)(Math.random()*used) ;
        c1.walk[i] = u1[rnd] ;
        c2.walk[i] = u2[rnd] ;
        u1[rnd] = u1[used-1] ;
        u2[rnd] = u2[used-1] ;
        used -- ;
      }
      //if (!c1.isConsistent())
      //  System.out.println("c1 Error");
      //if (!c2.isConsistent())
      //  System.out.println("c2 Error");
    }
 
 
   public void mutation(SolutionSearchState state, double p) {
     TSPsolutionState s = (TSPsolutionState) state ;
     int replaced, i, j ;
     for (i=0 ; i < size ; i++)
       if (Math.random() < p) {
         replaced = s.walk[i] ;
         do {
           s.walk[i] = (int) (Math.random() * size);
         } while (s.walk[i] == replaced) ;
         // substitute mutated city
         for (j=0 ; j < size ; j++) {
            if (i == j)
              continue;
            if  (s.walk[j] == s.walk[i]) {
              s.walk[j] = replaced ;
              break ;
            }
         }
      }
   }
}