• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Jeanne Boyarsky
  • Junilu Lacar
  • Henry Wong
Sheriffs:
  • Ron McLeod
  • Devaka Cooray
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Frits Walraven
  • Tim Holloway
  • Carey Brown
Bartenders:
  • Piet Souris
  • salvin francis
  • fred rosenberger

How Genetic Algorithm processes a matrix of distances?

 
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi everyone!

I would like to know if anyone had experience with the genetic algorithm and distance matrix? I got a matrix of distances:



And I got the code from here genetic algorithm implementation from github. You can have a look at it is a safe resource.

The algorithm is an example from a book and it works, but the thing is it is finding the Euclidean distance between the random number of cities.

In my case, I got an existing matrix of distances. The distances are 10x10, therefore, I got 100 distances. An example is shown below.

What would be the implementation for that? The idea is to find the shortest route between them all. How would that be possible when I already have the distances? How the method would look like? I am so confused that I can't find the answer for days.

Thank you!
download.png
[Thumbnail for download.png]
 
Marshal
Posts: 25594
69
Eclipse IDE Firefox Browser MySQL Database
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
One route would be (g1, g2, g3, g4, g5, g6, g7, g8, g9, g10). The length of that route would be (g1:g2) + (g2:g3) + (g3:g4) + ... + (g10:g1), which if you copy the numbers out of that table you get 8.1 + 12.0 + 11.2 + ... + 7.0, which adds up to whatever it would add up to if you looked up all ten distances from the table and added them up. To put it briefly, the implementation is to arrange the ten cities into some order and then get the distances from the table and add them up.

Does that help? To do that doesn't require any knowledge of genetic algorithms.
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you for your thoughts on that!

Could you explain in more details? Could you show a pseudo code of how would you do that?
I am not so good at data structures and algorithms, not yet, and I need some directions.
 
Paul Clapham
Marshal
Posts: 25594
69
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Data structures and algorithms? All you need to know is how to pick a number out of a two-dimensional array. Actually, to pick ten numbers and find their sum.
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
and how would you do that? Any pseudo code please?
 
Saloon Keeper
Posts: 7175
65
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The most straight forward implementation for visiting a set of nodes in all possible combinations is to use recursions. You'll need to create a class ("Route") to hold the current state of the recursion as you descend and return from the various node combinations. A Route would need a list of nodes (aka points, or cities) that it has visited as it descends through the nodes. As a node is visited it is added to the current Route's list. When it gets to the bottom, meaning no more nodes to visit, then calculate and return the sum of the distances. As the caller receives these returned distances it remembers the shortest Route and eventually passes that up to its caller until the entire recursion unwinds leaving you with the shortest possible Route.


An enhancement of this would be to track partial distances as you descend down through the nodes and compare that to your shortest (so far) Route. If it is longer, stop descending and return, thus trimming some of the search paths and making it more efficient.
 
Paul Clapham
Marshal
Posts: 25594
69
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
 
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Marin,

just had a quick look at the github project you linked to. Can't follow everything, but if I am not mistaking, have a look at this codesnippet in the class Route:
You see the totalDistance being increased by the distance from route[cityIndex] to route[cityIndex + 1].
This distance is, as you wrote, the Euclidean distance between the two cities. In your case you have your 2D matrix that determines the distance between two cities. So you would get:

Or alternatively, you could change the 'distanceFrom' method in the City class in a similar way.
I haven't tested it, though.

By the way: a nice way to represent a DNA (or route in this case) is:
for the first city we can choose a number from 0-9 (when route size = 10). Then, from the 9 remaining cities, we can choose a number from 0-8, et cetera.
So Pauls route g1-g2-...-g10 would be represented as: 0-0-0-0-0-0-0-0-0-0.
The advantage is that you can do the crossover at any index, or mutate any gene and still have a valid route.
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I like your reply, you are the only one who actually got close enough. I am trying no the implementation but could have a look again at the code and tell me how would you do that? You can show me a pseudo-code perhaps. My matrix looks like this, where the distances are parsed from a google distance matrix API.



How would this matrix be implemented, I mean how would you change the distanceFrom in order to process them all in the route class?

For now, I return for a reason only the last value from every 10 distances. Altogether 10 values, but I got 100.
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Marin,

first of all: you are doing a lot of unnecessary work! The 10 distanceMatrix determinations can be replaced by just one:

And why not immediately calculate the distance:

That saves you from calculating x, y and xAndY2, of which the meanings are not clear to me, just like the reason for this Distance class.

In the code that you linked to, there was a City class, that had variables x and y. Since these are irrelevant now (you get your distances from the distanceMatrix), you can drop this class. The cities are represented by the numbers 0-9. Later, when you have figured out the minimum distance, you can always translate the numbers back to real city-names. Note that using numbrs for the cities will also involve some code-changes elsewhere, but that should not be difficult.

Can you show placeDistances.sublist(0, 30), to get an idea how that List looks like, and explain how that list is to be interpreted?
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Piet,

Thank you for the simplification of my code, I have to learn a lot I can tell.

Regarding the placeDistances.sublist(0,30) that's the output if I got it right what you requested:

[1 m, 2.9 km, 1.3 km, 2.7 km, 1.3 km, 5.6 km, 5.5 km, 10.3 km, 5.7 km, 6.6 km, 2.0 km, 1 m, 1.9 km, 3.2 km, 1.7 km, 3.6 km, 3.3 km, 6.8 km, 3.6 km, 4.5 km, 2.0 km, 2.0 km, 1 m, 1.8 km, 1.7 km, 4.8 km, 4.6 km, 9.4 km, 4.8 km, 5.8 km]

All these data are changing dynamically depending on the user request. It shows the nearby places around user location and calculates the distances and shows directions. I use the Places API, Directions API, and Distance Matrix API.

You got it correct. I want to pass the distances to the Route class I believe in order to find the shortest route. I am not sure if it will work because the Route class is requiring a simple array and not a matrix?

Also, regarding indexing for later translation to the real cities. I got the lists ready, I just need somehow attach the distances to each pair of origin place and destination, but the problem is I don't know how to integrate it with the genetic algorithm because it requires only numerical values, hence distances.

The City class is not required perhaps anymore, yet I tried with it for some reason. Maybe all due to my lack of knowledge and limited time.

How could I pass the matrix of distance to the genetic algorithm? If I drop the City, in my case Distance class, should I pass it straight to the Route.class?

And how would you do with the indexing from 0-9 the cities so later I can display the order?

This is my GetDistanceMatrix class with all the data processed and passed onto the Distance.class and following Genetic algorithm. I know is messy, sorry about that:



Hope it will answer few questions that may arise. Let me know what you think about it.
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Marin,

your distances String does not lead to a symmetric matrix. That is not necessary of course, but it does make me wonder if the interpretation is correct.

Anyway, I got the impression that the changes that I wanted to make were too many to put in a reply. So I changed the original code and put it in my GitHub account: github.
The project is called 'GeneticTSP', with startup class GeneticTSP.Java. In this file I have the input defined as you listed, with a List<String> cities (containing names) and the distances String as you showed me.
I changed the main method in TSP.java to accept these two arguments.
I repaired a bug in the Route-getdistances method and a bug in geneticAlgorithm that caused me an IndexOutOfBoundsException.

The code is a bit messy, it is full of outcommented original code, and it contains a lot of print-statements, for debugging reasons.

Well, give it a look and let me know if you agree to this set up.
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And oh ja, most important: I dropped the idea of working with a 2D matrix, but instead gave each city an array with the distances to the other cities. It seemed more easy to do it that way, but, with hindsight, I doubt whether I made the right decision...
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's an amazing job. The Genetic algorithm works just fine. However, after testing multiple times I noticed that the best result returned by the algorithm has a pattern like this:

2,3,1,0,4,7,6,8,9
instead of:

0,2,3,1,4,6,7,8,9,0

What I am trying to say it seems that the algorithm is finding the shortest route in general and is not actually finding the route starting and ending with place number 0.

What would be the problem and suggestions?

Also, I am trying now to add the latitudes and longitudes of the cities along with their indeces, so at the return I can get a list of LatLng variables in a specific order that I can use them to display on the map.
 
Piet Souris
Bartender
Posts: 3959
155
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Marin,

indeed it is finding the shortest path, no matter what starting and ending point. If you want to start and end the route at the same city, then my first thoughts are: as a starting population, we must only have routes that start and end in city 0, so that crossovers will keep that property, and that mutations will not be applied to start and end cities. It seems possible, but then I have to spit through the code to see where I can put these constraints in.

As a simple alternative that does not guarantee the "best" result (but then, no GA does that), is to find the shortest path between the nine cities 1-2-...-9, and then add the distances (0 - start) and (end - 0). That seems for now the easiest thing to do.

And you can add the fields 'longitude' and 'latitide' to the city data, no problem. For instance, the city list may have this form:

It requires a new Constructor, but that should not be difficult.
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Piet,

But even if it does not start and end at the City[0] is it still a TSP or it has to start with City[0] and end there? What is doing now is a minimum spanning tree isn't it?
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
As it is now, it is indeed a MST.  A Traveling salesman that has to travel that route every day is advised to buy a premise at the first city. If he must start and end in the city he lives in, then you get the variant you mentioned.
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah for sure I need TSP, then. I have to add the city[0] at the beginning and the end of the list, but somehow remove it from the middle just like you suggested. Is that dealing with the population class only or is somewhere else as well?
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Marin,

adding city[0] at the beginning and end of the shortest path leaves the possibility that the start and end of the route of nine cities are far away from city[0]. But if you have a list of 10 cities, then in the TSP method, you remove city 0 from the list (and also from the distance matrix) and, when the calculation is finished, add city[0] into the calculation. This requires that every start and end of the 9-city route must have a connection to city[0]. But sofar we are only discussing fully connected graphs. (please don't say 'no')

But neater is to take care that every route (chromosome) starts and ends with city[0]. That means that the startpopulation must have only routes of that form. Crossover will retain this property for each route, but we must make sure that mutations do not affect the start and end. To achieve that, we must check the code to see where populations are and how the author managed the mutations. It is now bedtime in Holland, so that will be tomorrow. But maybe you can have a look and tell your findings?

By the way: in the City class you can adjusrt the 'toString' method, so that also the long- and latitudes are displayed.

To be continued...    
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Piet!

Holland, nice, I just came back from there. At the moment I am in Brazil stuck, because of the quarantine. I have a flight back to Europe with a stop in Amsterdam at the end of May.

Regarding the code, I am trying to implement at the moment the latitudes and longitudes so I can display them on the map in the same order they are returned by the TSP class.

On genetic algorithm part, I had a look and I believe I have to change the crossover part. In my vision, it should look like this.

The normal approach of the crossover -
[City0][City1][City2][City3][City4][City5] = route 1
[City4][City2][City0][City5][City3][City1] = route 2

Now the crossover,

[City0][City1][City2][null][null][null] = crossover route
[City0][City1][City2][City4][City5][City3] = final crossover route

I believe to achieve the TSP is should be like this:

[City0] - stays unchanged and [City5] too.

so it should be like this,

[City0][City1][City2][City3][City4][City5] = route 1
[City0][City2][City1][City4][City3][City5] = route 2

[City0][City1][City2][null][null][City5] = crossover route  (crossover only the middle part)
[City0][City1][City2][City4][City3][City5] = final crossover route

This is what I think, however with the implementation I will try to achieve it somehow now. If any thoughts and I am sure you have please share.
 
Piet Souris
Bartender
Posts: 3959
155
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Marin,

toy toy for your way home. There are some 20.000 Dutch people stuck all over the world, so it will not be an easy thing.

I was just finished with my new version and had written my reply, when I noticed your new reply. Have not read it yet, but my version is based on setting the start city (that will also be the end city). Now, the input stays the same, but I was a bit reluctant to mess with the code that does the crossover and mutations. So I opted for a slightly simpler version.

Say, you have the List<City>(A, B, C, D) and you indicate that A should be the start- and endcity. Then I calculate the shortest route for the remining cities (B, C, D), where the fitness of such a route iis increased with the distance from A to the first city of that route, plus the distance of the last city of that route to A. That seemed to me much easier. Biggest problem was adjusting the long List<String> distances, that had to take care that A should not be involved.

I only tested it for four cities with some made-up distances, so chance is high you will find some errors when using a much bigger inputset. And the code is still messy, could use a firm clean-up.

The version is called "GenericTSP_1", still in my GitHub-account.

Gonna read your reply now.
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Marin,

yes that would be ideal, this way. Problem is that I could not detect how the code worked. I did not understand why he author had an Individual class AND a Route class as well. And the code that guaranteed that a crossover would always lead to a valid new route, was a bit cryptic. That is why I used the method I described. Changing the input accordingly, was challenging, however (see the TSP class for sme horrors).
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hey Piet,

Thank you for your quick reply. I had a look into the program and noticed the java8+ stuff. The thing is I have an Android project and its support not bigger than java 7, plus I don't know much of a java 8 and above. Could be there an alternative for streams and vars? I tried to add some streams in my project but they simply don't work because I have a minimum SDK 21 and is meant to be 24. =(
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I will give it a shot, but that' ll be tonight at the earliest, probably tomorrow. Is java 7 oke?
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah, I had run it on a different project and it is just fine. It returns a value from A ... A. It would be great to have it in java 7. I will try to implement it anyway, maybe I can substitute all the new words with some old ones. Let's see =)
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I just put "GeneticTSP_2" on my GitHub account. I checked it for the lava8+ terms "Stream", "var" and "List.of", and they were missing, as it should. I don't have java 7, so I couldn't test it.

Question: I have not run the original version, but I get the impression that, although starting and ending with the same city, that city was not determined beforehand; it was just the starting city of the shortest route. Am I correct? The version I have lets you choose the starting city.
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I found a very simple TSP genetic program at GeeksForGeeks: TSP GeeksforGeeks.

That code also works for a Graph that is not fully connected, by setting the distance between two unconnected vertices to Integer.MAX_VALUE, so that the fitness of such a route (total distance) is also MAX_VALUE, and thus such a route will not make it into the next generation. Clever!
 
Marin Capranov
Ranch Hand
Posts: 66
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Piet,

Sorry for the long delay in my answer. I been busy implementing the code to my needs and I am pretty sure I made it. If you think the GA algorithm always is returning the shortest route. The one thing I don't fully understand is what is the population fitness and how does it actually influence the result. I noticed that the better result the higher is the population fitness. How come?

Many thank to you for your support, you helped a lot!
Cheers!
 
Piet Souris
Bartender
Posts: 3959
155
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Marin,

as you have realized, I'm no expert at all when it comes to genetic algo's, just read a few articles about it, long ago. So I'm not sure if my answer is correct.
First of all, it is a good sign if the population fitness increases, that gives faith to go on generating new and better populations. And it follows that if you have a series of consecutive generations for which the fitness does not increase (or even decrease) then you might as well stop and take the best chromosome sofar, instead of going all the way to the last generation. I could not determine whether the code you linked to followed this strategy, the GFG code certainly does not.

That the population fitness increases (normally) is due to the fact that the better chromosomes either survive, or that the crossover and mutations really deliver better chromosomes.
 
Good night. Drive safely. Here's a tiny ad for the road:
Devious Experiments for a Truly Passive Greenhouse!
https://www.kickstarter.com/projects/paulwheaton/greenhouse-1
    Bookmark Topic Watch Topic
  • New Topic