Advice needed with genetic algorithm and TSP

Programming Questions

gera

Advice needed with genetic algorithm and TSP

in Programming Questions • 3 months ago

Hello all!! First of all, excuse me about my english.

I'm working on a genetic algorithm to solve the TSP. I already have a program that does the work, but I want to improve it. Particulary the crossover function. This is what I have so far:

class Path implements Comparable {
Map myMap;
IntList item;
Path(Map _myMap){
myMap = _myMap;
// init a random path
item = new IntList();
for(int i=0; i < myMap.n_cities; i++){
item.append(i);
}
item.shuffle();
}
....
Path crossover(Path partner){
Path son = new Path(myMap);
int cut = int(random(this.item.size()));
son.clear();
for(int i=0; i < cut; i++)
son.item.append(this.item.get(i));
for(int i=0; i < partner.item.size(); i++){
if(!son.item.hasValue(partner.item.get(i)))
son.item.append(partner.item.get(i));
}
return son;
}
........
}

As you can see, the crossover method copies the first n elements of the parent A (I cut the chromosome in 1 point), and then complete the rest with the elements of the parent B wich havent been copied yet.

Now, I'd like to select a subset inbetween the parent A, copy it to the child, and then complete it with the elements of B. (same concept, but this time cutting the chromosome in 3 points).

Do you have any idea how can I do this??

I figured a way to do it, but I need to use some methods of the IntList class like .getSubset() or .insert(), but I dont know why I cant use them. Here is the reference.

http://processing.org/reference/javadoc/core/processing/data/IntList.html

Well, I hope you can help me. Thanks a lot!!!

Replies(1)

gera

Re: Advice needed with genetic algorithm and TSP

3 months ago

Well, I've just figured out how to do the crossover with a 2-point cut, but its really messy. If you have any idea on how can I do it in a clearer way, please let me know.

Also I've writed a new mutate function that works very well (before I took 2 cities and swapped them, now I take a subtour and reverse the order of its items). This allow the program to resolve the paths intersections.

This is my new Path class:

class Path implements Comparable {
Map myMap;
IntList item;
Path(Map _myMap){
myMap = _myMap;
// init a random path
item = new IntList();
for(int i=0; i < myMap.n_cities; i++){
item.append(i);
}
item.shuffle();
}
void clear(){
item.clear();
}
float fitness(){
float f = 0;
for(int i=0; i < myMap.n_cities; i++)
f += dist(myMap.cities[item.get(i)].x, myMap.cities[item.get(i)].y, myMap.cities[item.get((i+1)%myMap.n_cities)].x, myMap.cities[item.get((i+1)%myMap.n_cities)].y);
return f;
}
Path crossover(Path partner){
int start = int(random(item.size()-1));
int num = int(random(1,item.size()-start));
Path son = new Path(myMap);
IntList subset = new IntList();
subset.append(subset(item.array(),start,num));
son.clear();
for(int i=0; i<partner.item.size() && son.item.size() < start; i++){
int val = partner.item.get(i);
if(!subset.hasValue(val))
son.item.append(val);
}
son.item.append(subset);
for(int i=0; i<partner.item.size(); i++){
int val = partner.item.get(i);
if(!son.item.hasValue(val))
son.item.append(val);
}
return son;
}
void mutate(){
int start = int(random(item.size()-2));
int end = int(random(start+1,item.size()-1));
int aux=0;
while(start < end){
aux = item.get(start);
item.set(start,item.get(end));
item.set(end,aux);
start++;
end--;
}
}
// draw path
void display(color c){
strokeWeight(1);
stroke(c);
for(int i=0; i < myMap.n_cities; i++){
line(myMap.cities[item.get(i)].x, myMap.cities[item.get(i)].y, myMap.cities[item.get((i+1)%myMap.n_cities)].x, myMap.cities[item.get((i+1)%myMap.n_cities)].y);
}
}
int compareTo(Object o){
Path b = (Path)o;
if( this.fitness() < b.fitness() )
return -1;
if( this.fitness() > b.fitness() )
return 1;
return 0;
}
}

Again, thanks for your answers!

Top Reply