Java-Gaming.org    
Featured games (79)
games approved by the League of Dukes
Games in Showcase (477)
Games in Android Showcase (106)
games submitted by our members
Games in WIP (533)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  How to implement N-Opt in Genetic Algorithm To Solve the Travelesman Problem?  (Read 589 times)
0 Members and 1 Guest are viewing this topic.
Offline Andre Lopes
« Posted 2014-06-21 01:52:14 »

Hi Guys,
How to implement N-Opt in Genetic Algorithm To Solve the Travelesman Problem?

Im trying to implement 2-opt in a GA algorithm, but im confused in how-to..
Should i implement it in the mutate() method or mate() method?

https://bitbucket.org/dermetfan/tsm-ga-solver/src/73f2a35bf2e036bdcca03bef4340eeb683dc620e/core/src/main/net/nexusteam/tsmGaSolver/ann/TSPGeneticAlgorithm.java?at=default

https://bitbucket.org/dermetfan/tsm-ga-solver/src/73f2a35bf2e036bdcca03bef4340eeb683dc620e/core/src/main/net/nexusteam/tsmGaSolver/ann/TSPChromosome.java?at=default


//

https://bitbucket.org/dermetfan/tsm-ga-solver/src/73f2a35bf2e036bdcca03bef4340eeb683dc620e/core/src/main/net/JeffHeatonCode/GeneticAlgorithm.java?at=default

https://bitbucket.org/dermetfan/tsm-ga-solver/src/73f2a35bf2e036bdcca03bef4340eeb683dc620e/core/src/main/net/JeffHeatonCode/Chromosome.java?at=default


I know in theory how 2-opt should WORK :

Example :
For 4 Cities A,B,C,D

A  B
C  D

A--> D -->C -->B

Their connections form  concorrent lines..
The method should be capable to Transform that into either these :

A-->B-->D-->C
or
A-->C-->D-->B

The one with less cost obviously.

Im not getting how to do it.
I know how to identify if a line intersects other by using

f(x) = mx + b
Or is there any other way i should do it?
Offline Andre Lopes
« Reply #1 - Posted 2014-06-21 20:22:25 »

Guys, i got this Now.
But im confused with this part:

1  
2  
3  
4  
5  
6  
  2optSwap(route, i, k) {
       1. take route[0] to route[i-1] and add them in order to new_route
       2. take route[i] to route[k] and add them in reverse order to new_route
       3. take route[k+1] to end and add them in order to new_route
       return new_route;
   }



1.
2.
3.

What exactly should we do?Huh

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
141  
142  
143  
144  
145  
146  
147  
148  
149  
150  
151  
152  
153  
154  
155  
156  
157  
158  
159  
160  
161  
162  
163  
164  
165  
166  
167  
168  
169  
170  
171  
172  
173  
174  
175  
176  
177  
178  
179  
180  
181  
182  
183  
184  
185  
186  
187  
188  
189  
190  
191  
192  
package net.nexusteam.tsmGaSolver.ann;

import net.JeffHeatonCode.Chromosome;
import net.JeffHeatonCode.NeuralNetworkError;

/** @author Mix Of Jeff Heaton Code with Our Team Code */
public class TSPChromosome extends Chromosome<Integer, TSPGeneticAlgorithm> {

   protected Waypoint[] path;

   public TSPChromosome(final TSPGeneticAlgorithm owner, final Waypoint path[]) {
      setGeneticAlgorithm(owner);
      this.path = path;

      final Integer genes[] = new Integer[this.path.length];
      final boolean taken[] = new boolean[path.length];

      for(int i = 0; i < genes.length; i++) {
         taken[i] = false;
      }
      for(int i = 0; i < genes.length - 1; i++) {
         int icandidate;

         do {
            icandidate = (int) (Math.random() * genes.length);
         } while(taken[icandidate]);

         genes[i] = icandidate;
         taken[icandidate] = true;
         if(i == genes.length - 2) {
            icandidate = 0;

            while(taken[icandidate]) {
               icandidate++;
            }

            genes[i + 1] = icandidate;
         }
      }
      setGenes(genes);
      calculateCost();

   }

   @Override
   public void calculateCost() throws NeuralNetworkError {
      double cost = 0.0;
      for(int i = 0; i < path.length - 1; i++) {
         final double dist = path[getGene(i)].dst(path[getGene(i + 1)]);
         cost += dist;
      }
      setCost(cost);

   }

   @Override
   public void mutate() {
      final int length = getGenes().length;
      final int iswap1 = (int) (Math.random() * length);
      final int iswap2 = (int) (Math.random() * length);
      final Integer temp = getGene(iswap1);

      setGene(iswap1, getGene(iswap2));
      setGene(iswap2, temp);
      getGeneticAlgorithm().incrementMutationCounter();

      boolean use2OptSwap = false;
      if(use2OptSwap)
      {
         setGenes(optimize(getGenes()));

      }

      // System.out.println("Mutation Calls : " + getGeneticAlgorithm().gettimesMutated());

   }

   //2Opt Methods
  private Waypoint[] optSwap(Integer genes[], int i, int k)
   {

      //Step 1

      for(int index = i; index < i - 1; i++)
      {

      }

      //Step 2

      for(int index = i; index < k; i++)
      {

      }

      //Step 3

      for(int index = k + 1; index < genes.length; i++)
      {

      }

      //2optSwap(route, i, k) {
     //     1. take route[0] to route[i-1] and add them in order to new_route
     //   2. take route[i] to route[k] and add them in reverse order to new_route
     //  3. take route[k+1] to end and add them in order to new_route
     //  return new_route;
     // }

      //

      return path;
   }

   /**
    * @param genes
    * @return
    */

   private Integer[] optimize(Integer genes[])
   {
      boolean improved = false;
      double best_distance = Double.MAX_VALUE;

      while(!improved)
      {
         calculateCost();
         best_distance = getCost();

         for(int i = 0; i < getGenes().length; i++)
         {
            for(int k = i + 1; k < getGenes().length; k++)
            {

               TSPChromosome newRoute = new TSPChromosome(this.getGeneticAlgorithm(), optSwap(genes, i, k));

               newRoute.calculateCost();

               double new_distance = newRoute.getCost();

               if(new_distance < best_distance)
               {
                  improved = true;
                  genes = newRoute.getGenes();
               }

            }
         }
      }

      return genes;

      // repeat until no improvement is made {
     //     start_again:
     //   best_distance = calculateTotalDistance(existing_route)
     // for (i = 0; i < number of nodes eligible to be swapped - 1; i++) {
     //   for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
     //     new_route = 2optSwap(existing_route, i, k)
     //   new_distance = calculateTotalDistance(new_route)
     // if (new_distance < best_distance) {
     //   existing_route = new_route
     // goto start_again
     //}
     //}
     //}
     //}

      //
  }

   /** Used to compare two chromosomes. Used to sort by cost.
    *
    * @param other The other chromosome to compare.
    * @return The value 0 if the argument is a chromosome that has an equal cost to this chromosome; a value less than 0 if the
    *         argument is a chromosome with a cost greater than this chromosome; and a value greater than 0 if the argument is a
    *         chromosome what a cost less than this chromosome. */

   @Override
   public int compareTo(Chromosome<Integer, TSPGeneticAlgorithm> other) {
      if(getCost() > other.getCost()) {
         return 1;
      } else if(getCost() == other.getCost())
         return 0;
      else {
         return -1;
      }
   }

   /** @return the {@link #path} */
   public Waypoint[] getPath() {
      return path;
   }

}
Offline Andre Lopes
« Reply #2 - Posted 2014-06-22 20:10:24 »

Ok, i made a small example class...
Not working, having NPE issues..
Can anyone help me?

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
119  
120  
121  
122  
123  
124  
125  
126  
127  
128  
129  
130  
131  
132  
133  
134  
135  
136  
137  
138  
139  
140  
package br.Lopes.Logic;

/**
 *
 * @author Andre Lopes
 */

public class Logic {

    private Waypoint waypoints[];

    public static void main(String args[]) {
        Logic logic = new Logic();
        logic.optimizeRoute(logic.waypoints);

    }

    public Logic() {
        waypoints = new Waypoint[4];

        //Add A--> C and C-->D and D--> B
       waypoints[0] = new Waypoint(0, 0, "A"); //Left Bottom
       waypoints[1] = new Waypoint(5, 5, "C"); // Right Top
       waypoints[2] = new Waypoint(0, 5, "B"); //Left Top
       waypoints[3] = new Waypoint(5, 0, "D"); //Right Bottom

    }

    public Waypoint[] optSwap(Waypoint waypoints[], int i, int k) {

        Waypoint auxWaypoints[] = new Waypoint[waypoints.length];

        for (int index = 0; index < i - 1; index++) {
            System.out.println("Step 1 : Index :" + index);
            auxWaypoints[index] = waypoints[index];
        }
        System.out.println("Step 1 : ");
        //printVector(auxWaypoints);

        int reverse = k;
        for (int index = i; index < k; index++) {
            auxWaypoints[index] = waypoints[reverse];
            reverse--;
        }
        System.out.println("Step 2 : ");
        printVector(auxWaypoints);

        for (int index = k + 1; index < waypoints.length; index++) {
            auxWaypoints[index] = waypoints[index];
        }
        System.out.println("Step 3 : ");
        printVector(auxWaypoints);

        return auxWaypoints;

    }

//     2optSwap(route, i, k) {
//       1. take route[0] to route[i-1] and add them in order to new_route
//       2. take route[i] to route[k] and add them in reverse order to new_route
//       3. take route[k+1] to end and add them in order to new_route
//       return new_route;
//   }
//    
//      example route: A ==> B ==> C ==> D ==> E ==> F ==> G ==> H ==> A
//   example i = 4, example k = 7
//   new_route:
//       1. (A ==> B ==> C)
//       2. A ==> B ==> C ==> (G ==> F ==> E ==> D)
//       3. A ==> B ==> C ==> G ==> F ==> E ==> D (==> H ==> A)
//    
//          repeat until no improvement is made {
//       start_again:
//       best_distance = calculateTotalDistance(existing_route)
//       for (i = 0; i < number of nodes eligible to be swapped - 1; i++) {
//           for (k = i + 1; k < number of nodes eligible to be swapped; k++) {
//               new_route = 2optSwap(existing_route, i, k)
//               new_distance = calculateTotalDistance(new_route)
//               if (new_distance < best_distance) {
//                   existing_route = new_route
//                   goto start_again
//               }
//           }
//       }
//   }
   public void optimizeRoute(Waypoint waypoints[]) {
        int numberOfRowsToBeSwapped = waypoints.length;
        int numberOfColumnsToBeSwapped = waypoints.length;

        double bestDistance = calculateTotalDistance(waypoints);

        //Aux Variables
       Waypoint[] new_route;
        double new_distance;
        for (int i = 0; i < numberOfRowsToBeSwapped - 1; i++) {
            for (int k = i + 1; k < numberOfColumnsToBeSwapped; k++) {
                System.out.println("OptSwap : (i;k)" + i + ";" + k);
                new_route = optSwap(waypoints, i, k);
                System.out.println("New Route Calculated!");
                new_distance = calculateTotalDistance(new_route);

                if (new_distance < bestDistance) {
                    this.waypoints = new_route;
                    System.out.println("New Route Set!");
                }
            }
        }
    }

    public double calculateTotalDistance(Waypoint waypoints[]) {
        double distance = 0;
        for (int i = 0; i < waypoints.length; i++) {
            Waypoint auxpoint = waypoints[i];
            double dx = 0, dy = 0;
            if (i > 0) {
                dx = waypoints[i - 1].getX() - auxpoint.getX();
                dy = waypoints[i - 1].getY() - auxpoint.getY();
            }

            System.out.println("Name : " + auxpoint.getName());
            distance += Math.sqrt(dx * dx + dy * dy);
        }

        System.out.println("Calculated Distance :" + distance);
        return distance;

    }

    private void printVector(Waypoint waypointsAux[]) {
        for (int index = 0; index < waypointsAux.length; index++) {
            Waypoint auxpoint = waypointsAux[index];
            if (auxpoint == null) {
                System.out.println("WayPoint[" + index + "] = NULL!");
                break;
            }
            System.out.println("\nWayPoint");
            System.out.println("Name : " + auxpoint.getName());
            System.out.println("X;Y :" + auxpoint.getX() + ";" + auxpoint.getY());
        }
    }
}

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #3 - Posted 2014-06-22 21:24:17 »

You're just attempting to find a path through waypoints?  If so, forget genetic.  Heck even forget shortest path.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #4 - Posted 2014-06-22 21:27:20 »

You're just attempting to find a path through waypoints?  If so, forget genetic.  Heck even forget shortest path.

His problem is to find the shortest path through all waypoints and back. I believe that is the minimum criteria.

Offline Andre Lopes
« Reply #5 - Posted 2014-06-22 21:32:54 »

It works fine without 2-opt method.

Now im trying to implement 2-opt into the mutate() method...
Offline Roquen
« Reply #6 - Posted 2014-06-23 07:21:09 »

His problem is to find the shortest path through all waypoints and back. I believe that is the minimum criteria.
I understand the definition of the problem. Smiley  And I also understand that the solution to the problem contains no fun-factor.  Moreover, generally, traveling salesman paths tend to look unnatural because they are.  Likewise for shortest path (with obstacles).  It's not what animals or humans do.  Keep it simple.

EDIT:  Likewise for A* like path finding.  Forget admissible heuristics.
Pages: [1]
  ignore  |  Print  
 
 

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

pw (25 views)
2014-07-24 01:59:36

Riven (25 views)
2014-07-23 21:16:32

Riven (19 views)
2014-07-23 21:07:15

Riven (22 views)
2014-07-23 20:56:16

ctomni231 (51 views)
2014-07-18 06:55:21

Zero Volt (46 views)
2014-07-17 23:47:54

danieldean (37 views)
2014-07-17 23:41:23

MustardPeter (40 views)
2014-07-16 23:30:00

Cero (56 views)
2014-07-16 00:42:17

Riven (55 views)
2014-07-14 18:02:53
HotSpot Options
by dleskov
2014-07-08 03:59:08

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:58:24

Java and Game Development Tutorials
by SwordsMiner
2014-06-14 00:47:22

How do I start Java Game Development?
by ra4king
2014-05-17 11:13:37

HotSpot Options
by Roquen
2014-05-15 09:59:54

HotSpot Options
by Roquen
2014-05-06 15:03:10

Escape Analysis
by Roquen
2014-04-29 22:16:43

Experimental Toys
by Roquen
2014-04-28 13:24:22
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!