Coding Challenge #35.5: TSP with Genetic Algorithm and Crossover

[@Tymon0000]

I think a cool way of visualising it would be to: Have a line from each city to every other city. Brightness of each of the lines will be proportional to the percentage of members of the population linking the two cities. In other words, each road would be brighter the more frequently it was used.

[@Tymon0000]

or for example give more thickness to more frequently used roads

[@oleksandrleskiv]

Tymski sounds like neural network's weights visualising :)

[@TheLargedwarf]

i'm working on it (thickness not brightness in this one, hopefully i'll have the kink worked out)

[@TheLargedwarf]

done, i'll send in the pull request

[@Tymon0000]

cool

[@likeyou3317]

1:31 *Folks slaughtering in the hallway* Dan, regardless of that continues on coding.

[@deefstes]

A man's gotta code what a man's gotta code.

[@DerClaudius]

On mutation rate: one thing you can do is to start with a high mutation rate to cover a lot of the solution space and then cool it down to better optimize local optima. For example start with 100% and cool it down to a minimum value of say 2% within 120 generations and keep it 2% for the rest

[@pdcx]

simulated annealing?

[@kouliniksatya]

Mutation rate could be 1/maxfitness

[@DerClaudius]

Here's another way to do easy crossovers when the gene is about permutations: - don't store the indices in the genes, but a picking/removing order from a list, if that makes sense. Example: gene would be [1,3,2,0,0] .... this means... initialize a list with all indices: [0,1,2,3,4]... then pick the one at index 1, 3, 2, 0, 0 in order, removing the number from the list and inserting it in a new one: [0,1,2,3,4] pick at position 1: [0,2,3,4] => 1 => [1] pick at position 3: [0,2,3] => 4 => [1,4] pick at position 2: [0,2] => 3 => [1,4,3] pick at position 0: [2] => 0 => [1,4,3,0] pick at position 0: [] => 2 => [1,4,3,0,2] You then generated a index list you can use to draw your lines... The advantage of this is, that in the gene, at the first position you can have a random number from 0 to 4, at the second position you can have a random number from 0 to 3, at the third position you always have a random number from 0 to 2 etc... So you can always cross over by just picking an index at which you switch from one gene to the other like you wanted in the first place, without worrying about the numbers, because all genes have that structure that the numbers are limited based on their position

[@TheCodingTrain]

Thanks so much for this!

[@jhfoleiss]

Great video! Just a quick analysis: adding neworder to a Set actually greatly improves the algorithm efficiency. It makes the lookup (equivalent to the "includes" function) run in constant time, in contrast with the linear-time search of array.includes. This improves runtime from O(n * m) where n is the number of elements in the "neworder" array and m is the length of orderB to simply O(m).

[@Charonic]

Easy to make an improvement: if a route is "good", then certainly its some of the "subroutes" must also be good. Mutate on the subroutes instead of the full path.

[@TheCodingTrain]

Great tip, thank you!

[@adeelfitness4993]

I was waiting to see that what technique you use for crossover in this type of problem. Great solution man. 👍

[@gadeichhorn]

Cool stuff! thanks for putting this together! Next one will be the Ant Colony optimization :). The great property of genetic algorithm is the fact it can be scaled to a cluster of machines with map reduce kind of way. you can take that as yet another challenge ;)

[@adiliqbal2118]

I'd like to make a suggestion for the show. It would be nice to see a Coding Train episode that highlights community contributions. I really liked the end result of the Islamic Star Pattern contributions. I think it would also get a lot more people motivated to start coding and contributing to projects as well.

[@TheCodingTrain]

I try to do this in the live streams, but I like the idea of making a video compilation of many things. Would you like to help me with this? (tweet me @shiffman or file an issue at github.com/CodingTrain/Rainbow-Topics/issues)

[@griffonthomas7869]

Great video as always Dan! Really interesting stuff.

[@TheLargedwarf]

here as a crossover strategy you might want to try: 1) pick a random city number (not already chosen) 2) pick a random parent 3) put the city number in the child vector at the same index as in the chosen parent (if the index is free) 4) iterate until there are no free slots left 5)put remaining cities in remaining slots randomly 6) with a low probability randomly swap 2 indexes This method rewards parents for being similar as the similarities will always be copied across. If you only chose your parents from the highest performing in the population then the assumption is that their performance is high due to their similarities. The new child will only contain a mixture of the differences. The mutation helps to prevent local optimums being found and global never being found.

[@frankholiday8671]

Thanx for the coding train session this has been interesting. I wouldn't know how efficient the GA is however...A comparison of the lexicographic algorithm(LA) and genetic algorithm(GA). The GA found a solution that was lower than the LA in 5 secs(342), the LA has been running for 1370 secs and it has been trying every Permutation. The number of cities is 10, with a 5000 population size and a 0.01 mutation rate. It is stuck on 350.

[@LukeGarbuttGaming]

perfect timing from finishing the last one :')

[@dex5454]

11:00 toucan, nice. Also from the future still interesting

[@sethstuff921]

Thinking about it alphabetically, a cool optimization would be something like if ABCD is not the best one, then dont check DCBA either because thats the exact same line. The lookup table also helps a ton

[@JBFFSK18]

I recognized that in a lot of cases the path was already pretty good except for some local "errors". Thus I think it'd be interesting to change the mutation algorithm in a way that it changes only nearby cities (say only if they're connected within a certain number of connections to each other). And for visualizing: maybe a Graph that shows the earlier and actual lengths of the path.

[@TheCodingTrain]

Great suggestions!

[@JBFFSK18]

Thanks! Oh and I forgot something: I've a feeling like that would slow down the process in the beginning. to solve that one could switch to the other type of mutation after a specific amount of time (proportional to the number of cities). I have my finals in 2 days but after that I am definetly going to try and implement this. and thanks for all your work and videos, I really apreciate them!

[@marcoio8742]

I know this might come a bit late but one thing you might do to implement this algorithm is actually reducing the number of total possibilities. If you think about it a path 1, 2, 3, 4 is the same and has the same length as a path 4, 3, 2, 1. Thus, once the algorithm explores a population [1, 2, 3, 4] you automatically remove population [4, 3, 2, 1] from the newGeneration to look for. Therefore, instead of having 12! or 20! possibilities, you have n!/2.

[@BradHouser]

Actually (n-1)!/2, as the home city doesn't' count, it is always the first and the last.

[@TheOlderSoldier]

Populate a lookup table with all the distances between cities, sort by shortest to longest, select neighboring cities at the top of the list for injection to the list during mutation.

[@zrebbesh]

A good crossover function exists if your genomes express city order as sequences of swaps (starting from a standard order, with one random swap per city) rather than sequences of stops.

[@kevnar]

The ultimate optimization: only swap two cities if they're within a certain distance of each other, otherwise you're pretty much always making the order worse.

[@karoshi2]

Or one might have a local fitness function, so that groups of cities that are already close to each other are more likely to be taken into the next generation. Wouldn't require a hard coded maximum distance to allow swapping, and would probably keep good local solutions intact.

[@yanfoo]

I thought genetic algorithm was also to remove the weakest DNA strand... In this case, this would be the distance of each segments; the longest, the weakest. Therefore, I would personally swap two random segments that are the weakest, normalized proportionally across all segment distances. In this case, I'd always try to reduce the length instead of randomly shuffling the segments around.

[@TheCodingTrain]

Thanks for the feedback!

[@BicycleName]

It seems that every time a path crosses another one, there's a way to connect one of the city making one of the path to another city making the other path so that, in the end, the total distance is smaller than the original one.

[@GABRIELFILMSTUDIOS]

6:04 - "I don't know what an optimal mutation rate would be" why not make a genetic algorithm to find that out? 😂

[@frodeflem9353]

Optimizing an optimizer. It's brilliant!

[@vgarzareyna]

Why not use BackProp?

[@piercegray2324]

What mutation rate should you use for the GA thats finding the mutation rate for the TSP?

[@PerMortensen]

@@piercegray2324 Easy solution. Just make a GA to figure out the optimal mutation rate for that!

[@Absiii]

1:47 One throw, two dots!

[@kevnar]

That crossover function is probably making things worse by losing a lot of progress and resetting it to relatively random values.

[@drpporto]

I think the crossover should check each elemeant of the two orders and maintain the one that appeared more at a given index inside a that population. An example is: a=[4,2,1,3,0] b=[4,3,1,0,2] c=[0,3,4,1,2] the crossover of a and c would be: [4, 3, 1, 0, 2].

[@TheCodingTrain]

Oh, I love this idea!

[@Ma5h1n3]

I do not think this is an efficient method, because it is not about a city appearing at a certain index leading to better solutions, but rather favorable local orders that lead to higher fitness. An example would be as follows: a=[4,2,1,3,0,6] b=[1,2,4,0,3,6] c=[0,3,4,2,1,6] Then a crossover of a and c would be some swap maintaining the route 4-2-1/1-2-4, because orders including this particular routing are more probable to have a higher fitness. Thus, crossovers of a, b and c could be [4,2,1,3,6,0], [3,6,0,4,2,1], [3,0,6,4,2,1], .... . But it would be important to explore not only one but many different favorable local routings.

[@aperiodicwalk3009]

I found that taking a section of the city order and simply reversing it was very effective in creating helpful mutations. However, I also used simulated annealing (kind of like genetic algorithm but with a population of only one) which is almost certainly a factor in faster convergence. en.wikipedia.org/wiki/Simulated_annealing

[@TheHpsh]

one thing i have begin to think about, one of the big problem with using genetic algorithm on the traveling salesperson problem, is local optimum, has any one tried to put in speciation in a genetic algorithm? if it was possible for speciation we can the "agents" to split up in different solution

[@adrijeguha9806]

I was wondering how do we determine if the path found is the best. Like when do I stop the iteration for this program, how many generations do we need to go before finding the true optimized path. What will be the stopping criteria. Answer from any one would be appreciated.

[@snaxman]

You cant determine the best, you can just run it multiple times for example 500 times, then do it again! You should get a small enough distance

[@jolo2274]

Question: isn't it true that the best place to start of from, is the point that is the most isolated one? and could't you find it by comparing the sum of the distances pointA has to all other points?

[@satishkpradhan]

Better to use route optimisation techniques that are more efficient. Using 2opt, 3opt and relocate.

[@nunustone7133]

Hey, very nice video-series, thanks a lot. I have a question to the relation of the mutationrate an the number of population. Of course it can be build a statistics-function with the same data (position of the cities on canvas) and change the values to compare the results after a certain amount of time. How can be calculate the best ratio between mutationrate an the number of population or an other question is, Would it be make sense to change the mutationrate an the number of population on runtime? Have a nice weekend Nunu

[@gitchai8838]

How do I know that this is the shortest path, in the other word is how to know that this is the end of program run? Otherwise program keeps running forever.

[@bretthaupt1019]

as part of your mutation you should un-cross paths as paths that cross or have an intersection between cities is not optimal. This would decrease the search space

[@TheCodingTrain]

Great suggestion!

[@twiho]

Is it not required that the population is sorted before picking by that function? I would have thought you wanted to prefer the most successful in a controllable way.

[@ZachDaChampion]

idea: start the program by letting the user "eyeball it" and draw their own path, then use that as a base for mutating a better path

[@theWorldOfIss]

Sir how to implement MTSP using NSGA-2 in python.

[@sadhlife]

Maybe crossover between the BestEver and WorstEver once in a while? Could give great results maybe, the only way to find out is by implementing.

[@sadhlife]

It's pretty much like choosing the best sort algorithm. The only way of finding out is practically trying it out.

[@earthbjornnahkaimurrao9542]

could you have an algorithm that starts with a subset of cities, finds the solution then adds a new city and leaves the first set in same relative order but is just testing where to insert the new city? Seems like this would take N^2 time

[@earthbjornnahkaimurrao9542]

might be good to first sort them by proximity and start on one side and work toward the other.

[@earthbjornnahkaimurrao9542]

another idea is to start with a circles that surrounds all cities and slowly shrink it until it collides with a city and then fix that point and keep shrinking

[@brittgriscom7905]

I want to have the bots compete with the user. How do I create sequential game screens? Have you covered that in any of your videos?

[@TheCodingTrain]

Not yet, but I should!

[@raphschru9865]

Is there a simple way to perform the optimisation in a separate thread from the one that displays the best solution ? Because even if you optimise e.g. the distance computation, you will still be limited to the frame rate !

[@TheCodingTrain]

Yes! JavaScript doesn't really have threads, but you could certainly run the algorithm in calls outside of the animation loop or even multiple times per cycle through draw().

[@nicholascurry5536]

Pre-solve for all distances between each city and use the shortest distances more often. Example Data: City 1 is 2miles apart from City 2 City 2 is 3miles apart from City 3 City 3 is 1miles apart from City 4 City 4 is 3miles apart from City 2 City 3 is 4miles apart from City 1 City 2 is 2miles apart from City 4 City 4 is 5miles apart from City 1 Using collected data. You can start by connecting 3 to 4. Check options leading off 3 and 4. Since you have all cities distances from "4 to n" and "3 to n". Choose the next shortest path to a city from city 4 and also city 3. Example System loop: Path #1: -------------- (Shortest Distance apart) 1a) 3 4 (Next, shortest off 3 and 4 in two directions.) 2a) 2 3 4 1 = 9miles (Since, both 3 and 4 are the same distance from the same city swap on the very next check.) ---------------- 1b) 3 4 2b) 1 3 4 2 = 8miles You can than mutate starting location to the second shortest next. Many variations can be made from that point on. Hope someone reads this and has feedback. Good or bad! :)

[@terryhealy7826]

I think this would be a great optimization to make the initial ordering. I has to be much better than random.

[@BeholdTheDevil]

Hm can't the mutation rate be proportional to the distance (something like 1/(bestDist-dist)) this way the worse solutions would also be mutated more often?

[@TheCodingTrain]

Oh, I like this idea!

[@BeholdTheDevil]

Yes but you could make sure the algorithm has a baseline lowest mutation rate. Looking at this again I see that it probably should be something like n - (1/ (1+ dist-bestDist )) where n > 1 and dist-bestDist > 0. If you for example set n to 1.25 the lowest possible mutation rate would be 1.25 -1/(1+0) = 0.25 The algorithm would still of course have an increased chance of getting stuck in a solution that isn't the perfect one. However it will be pretty good at finding a "decent" solution.

[@TheHpsh]

wonder how many times I have looked at this video, and not seen this problem, a gene would be a complete solution of the problem, so a gene would be the something like [0,1,2,3,4] and not 0 or 1 or 2 and so on, so if you should do some kind of crossover, you would need to have more complete solutions for each "being", you might since it only 1 solution you are looking for, get each being select randomly between its genes. else I wonder how it would be to do single cell duplications, like bacterias do, since we then don't use crossover

[@christopheranagbogu7659]

Hey guys, I'm currently working on a project that involves me using Genetic Algorithm to solve the job assignment problem. Please can I get any form of assistance here? Would appreciate! Thanks.

[@jojosukida]

Amazing what you are doing. Really want to see if you would record some Python courses or videos in the future. I think Python plus javascript would be the future of full stack data skills

[@TheCodingTrain]

Someday! (I have some examples of python + p5 for machine learning which I will present soon.)

[@erggish]

I am not sure how the crossover works... let's say: orderA = [0,1,2,3,4] orderB = [0,1,2,4,3] now if the random start is equal to the length of orderA you are getting back: order = [] + [0,1,2,4,3] = [0,1,2,4,3] which Is unnecessary loss of a mutation (this has already happened with orderB) wouldn't it be better to number the lines than the cities? that way paths like [34] and [43] are the same thing... and each city will have "Ncities-1" indices (or maps) - thinking in terms of OOP.

[@spookyturbo1618]

Is this not sorta random in the given situation? Per say you have the GA with no cross over, just taking the fittest few and applying mutations. Eventually these will get better IF the right cities are swapped. Now once you introduce cross over, especially in the way described, you are now typically ruining some of those subsections of the current path. So if you take 3 or so in a row from path one, you now have a subsection, and thats good because the subsections being the best they can be together makes the best path, but then this causes you to break up a sub section of the path you are combining with it typically, because the two it had linked together (so if anywhere near accurate to a short path) should be close to each other, and then you spread them out. You really have no way of determining the fitness because in here it is done by total distance, but when swapping or doing cross over, it isn't combining two with a short total distance that is going to help, but finding two with different short local distances that when combined create a shorter distance. To clarify I am not saying the GA doesn't help, I just feel like the crossover part in the specific application is not helpful or actually less then helpful. To farther give an example, lets take two optimal paths 1, 2, 3, 4, 5 and 1, 2, 3, 4, 5 These are the exact same, so you would think crossover would give the same result. In this method, 2, 3, 4 is selected from the first path 2, 3, 4, _, _ The next two unseen in the next path is 1, 5 2, 3, 4, 1, 5 is the final result.

[@TheCodingTrain]

Thanks for this feedback!

[@skulduggerypleasant3178]

Even though I'm a bit late to comment on this I may have an improvement. You could work with the minimum spanning tree heuristics to get a nerly optimal path and let the programm try improving this.

[@crellagecommunity7168]

hey bro can You make a full course of java from zero to hero with a lots useful tips or something like that!!??

[@ndiniuyauya6648]

can l implement this algorithm on a bus routing system for a school project

[@topie5344]

Does somebody know link to a similar javascript program for TSP with full bruteforce, like it has to try all possibility and show the percentage of how much is it done ! Thnx for reading and i hope you can help me!

[@qxyhu]

The links are literally in the video description, you might want to watch part 1 and part 2 too! ;)

[@balabuyew]

I think, cross-over does not do anything usefull in GA. Its better to continue exploring search space adding several random species to new generation. Imho (but I'm not sure), in nature, cross-over is an utility function, such as a replacement of random generator.

[@BradHouser]

The Traveling Salesman Problem has a core requirement that the salesman stops traveling and returns home. I see you finding the shortest path to every city, from the starting city, but I don't see you completing the circuit back to the home city. Therefore the total route lengths are incorrect, and therefore your solutions, while feasible, are not necessarily optimal.

[@snaxman]

I agree

[@rodrigoqteixeira]

1:32 BRO WHAT THE HECK IS THE BASEMENT KID TRYING TO ESCAPE OR SMTH???

[@adityavijayvergia8495]

I tried to decrease randomness in the mutation function. I selected the first city c1 randomly from any parent. For next city c2, I selected a city from the cities that the 2 parents had after c1 based on which had lesser distance. Say parent 1 had c3 and parent 2 had c4. I selected c3 if dist(c1, c3) < dist(c1, c4). And then applied some random swaps. This resulted in a lot of speed up and more accurate solutions even for less population size. You can find my python implementation at github.com/AdityaVijayvergia/travelling-salesman-problem

[@twinpotatoes5513]

This is what I first thought of, thanks for doing it

[@Jkauppa]

it will work if you do partial optimization minimization

[@Jkauppa]

two, four, eight, summed up

[@Jkauppa]

or three, five, nine, having the connection edges, 2*n+1, not just 2*n

[@Jkauppa]

order pizza

[@Jkauppa]

slices

[@Jkauppa]

hacking locks?

[@unhott1893]

One interesting thing here is that the distance between the first point and the last point is not included in the total distance. This is equivalent to the salesperson not having to return to their start position. For example 1 2 3 2,1,3 is much shorter than 1,2,3. But if you had to return to the starting point they'd be equivalent.

[@pjaborges]

Exactly!!! This is not a TSP and should not even have TSP on the video description.

[@baqarhussain5758]

can i get its code please

[@Fasyx]

What´s the name of the texteditor he´s using?

[@letoan285]

It's Atom, as i saw

[@TheCodingTrain]

Yes, it's Atom. Here are some of these workflow videos: sublime text: kzbin.info/www/bejne/i3Srq5-Lnql3Z5I atom editor: kzbin.info/www/bejne/mmSylHmbrcpsf80 brackets: kzbin.info/www/bejne/pJ69k5uDltOJmbs codepen: kzbin.info/www/bejne/a5jJhpqEpbhpobs

[@ericguzman4367]

Is this a multiobjective TSP?

[@iiiiii-w8h]

I thought it was the traveling salesman problem.

[@akshpatel7935]

What is the name for the algorithm Dan uses for crossover?

[@luckydubeandbobm1]

I think he is doing th Order Crossover :)

[@ivanpetrovic-poljak6411]

Hey what programming languages do you know?

[@charbelsarkis3567]

did someone just scream in the hallway?

[@AlefeLucas]

After applying crossover, my algorithm became far to optimal.

[@ColeNOXyd2nd]

18:40 yep its pretty unpronounceable but i tend to say Cole N(

[@TheCodingTrain]

Aha, thanks!

[@Nulono]

6:04 *fewer

[@TheCodingTrain]

doh

[@SirCutRy]

@Fasyx Atom

[@JosephOntime]

Next Coding Challenge: GTA 5

[@masterflamaster6377]

I don't really like ES6...

[@Tymon0000]

ES6 is awesome! So elegant, natural and amazing!

[@neeleshranjansrivastava6985]

7:56 This is Cancer 🤣

[@crazyfox55]

Your DNA is missing Genotype & Phenotype. Its hard to explain in just a comment but basically you need your DNA to store backup information.

[@assaqwwq]

can you not film yourself cleaning the whiteboard? "do you guys hear that?" no but thank you for stopping to describe noises. why are you throwing a marker? you're a good programmer that clearly enjoys what he is doing but for the love of god, keep it about the topic.

[@christopheranagbogu7659]

Hey guys, I'm currently working on a project that involves me using Genetic Algorithm to solve the job assignment problem. Please can I get any form of assistance here? Would appreciate! Thanks.

[@christopheranagbogu7659]

Hey guys, I'm currently working on a project that involves me using Genetic Algorithm to solve the job assignment problem. Please can I get any form of assistance here? Would appreciate! Thanks.