No video :(

Coding Challenge #35.5: TSP with Genetic Algorithm and Crossover

Подписаться 1,7 млн

Просмотров 80 тыс.

50% 1

In Part 1 of this multi-part coding challenge, I introduce the classic computer science problem of the Traveling Salesperson (TSP) and discuss the pitfalls with a brute force solution. In Part 2, I discuss Lexicographic Ordering and demonstrate one algorithm to iterate over all the permutations of an array. In Part 3, I apply this algorithm to a brute-force solution of the TSP problem. Every single route permutation is checked one by one. In Part 4, I attempt to create a solution to the TSP problem with a genetic algorithm, and then I add a “crossover” algorithm in Part 5. Code: thecodingtrain.com/challenges...
p5.js Web Editor Sketches:
🕹️ Part 1: Traveling Salesperson (TSP): editor.p5js.org/codingtrain/s...
🕹️ Part 2: Lexicographic Order: editor.p5js.org/codingtrain/s...
🕹️ Part 3: TSP with Lexicographic Order: editor.p5js.org/codingtrain/s...
🕹️ Part 4: TSP with Genetic Algorithm: editor.p5js.org/codingtrain/s...
🕹️ Part 5: TSP with Genetic Algorithm and Crossover: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Part 1: Traveling Salesperson (TSP): • Coding Challenge #35.1...
📺 Part 2: Lexicographic Order: • Coding Challenge #35.2...
📺 Part 3: TSP with Lexicographic Order: • Coding Challenge #35.3...
📺 Part 4: TSP with Genetic Algorithm: • Coding Challenge #35.4...
🎥 Previous video: • Coding Challenge #34: ...
🎥 Next video: • Coding Challenge #36: ...
🎥 All videos: • Coding Challenges
References:
🌐 Traveling Salesman on Wikipedia: en.wikipedia.org/wiki/Travell...
🗨️ Permutation Algorithm Using Lexicographic Ordering: www.quora.com/How-would-you-e...
📝 Array on MDN: developer.mozilla.org/en/docs...
📝 Array.includes() on MDN: developer.mozilla.org/en/docs...
📝 Array.reverse() on MDN: developer.mozilla.org/en/docs...
📝 ES6 Sets on MDN: developer.mozilla.org/en/docs...
💾 The Nature of Code Part 2: github.com/shiffman/NOC-S17-2...
📕 The Nature of Code: natureofcode.com/
Videos:
🎥 Improved Pool Selection: • 9.8: Genetic Algorithm...
🎥 Genetic Algorithm Playlist: • 9: Genetic Algorithms ...
🔴 Live Stream Archive #57: • Live Stream #57 - Trav...
Related Coding Challenges:
🚂 #29 Smart Rockets in p5.js: • Coding Challenge #29: ...
🚂 #51 A* Pathfinding Algorithm: • A* Pathfinding Algorit...
🚂 #69 Evolutionary Steering Behaviors: • Coding Challenge #69: ...
🚂 #70 Nearest Neighbors Recommendation Engine: • Coding Challenge #70: ...
Timestamps:
00:00 Recap from Part 4
00:35 What is crossover?
02:33 Improvement: showing the algorithm running
04:24 Improvement: adding a mutation rate
06:08 Where to apply crossover in the code?
07:10 How to apply crossover?
11:08 Code! Implementing the crossOver() function
15:30 Testing the crossOver() function
16:13 Playing with the variables
17:45 About the ES6 includes() function and Set
18:03 Inefficiency of the dist() function
18:44 Suggestion to improve mutation
21:10 Please share your own variations and improvements!
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: ru-vid.comjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#travelingsalesperson #permutation #lexicographicordering #natureofcode #geneticalgorithm #evolution #bruteforce #factorial #arrays #p5js

Опубликовано:

12 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 129

@likeyou3317 6 лет назад

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

@deefstes 4 года назад

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

@Tymon0000 7 лет назад

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 7 лет назад

or for example give more thickness to more frequently used roads

@oleksandrleskiv 7 лет назад

Tymski sounds like neural network's weights visualising :)

@TheLargedwarf 7 лет назад

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

@TheLargedwarf 7 лет назад

done, i'll send in the pull request

@Tymon0000 7 лет назад

cool

@DerClaudius 7 лет назад

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 6 лет назад

simulated annealing?

@kouliniksatya 3 года назад

Mutation rate could be 1/maxfitness

@DerClaudius 7 лет назад

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 7 лет назад

Thanks so much for this!

@Charonic 7 лет назад

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 7 лет назад

Great tip, thank you!

@griffonthomas7869 7 лет назад

Great video as always Dan! Really interesting stuff.

@adeelfitness4993 5 лет назад

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

@gadeichhorn 5 лет назад

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 ;)

@LukeGarbuttGaming 7 лет назад

perfect timing from finishing the last one :')

@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).

@zrebbesh 5 лет назад

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.

@TheLargedwarf 7 лет назад

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.

@unhott1893 5 лет назад

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 3 года назад

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

@yanfoo 7 лет назад

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 7 лет назад

Thanks for the feedback!

@marcoio8742 3 года назад

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 3 года назад

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

@kevnar 3 года назад

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.

@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

@dex5454 3 года назад

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

@adiliqbal2118 7 лет назад

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 7 лет назад

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)

@frankholiday8671 2 года назад

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.

@BicycleName 2 года назад

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.

@TheOlderSoldier 6 лет назад

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.

@nunustone7133 7 лет назад

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

@aperiodicwalk3009 7 лет назад

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

@jolo2274 7 лет назад

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?

@JBFFSK18 7 лет назад

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 7 лет назад

Great suggestions!

@JBFFSK18 7 лет назад

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!

@drpporto 7 лет назад

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 7 лет назад

Oh, I love this idea!

@Ma5h1n3 6 лет назад

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.

@TheHpsh 6 лет назад

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

@ndiniuyauya6648 7 лет назад

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

@skulduggerypleasant3178 7 лет назад

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.

@Absiii 5 лет назад

1:47 One throw, two dots!

@sadhlife 7 лет назад

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 7 лет назад

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

@TheHpsh 6 лет назад

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

@bretthaupt1019 7 лет назад

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 7 лет назад

Great suggestion!

@ZachDaChampion 7 лет назад

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

@kevnar 4 года назад

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

@raphschru9865 7 лет назад

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 7 лет назад

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().

@satishkpradhan 2 года назад

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

@ThatBastardOverThere 7 лет назад

Possible alternative method of crossover: Say you have two ordered list of cities, [A,B,D,C] and [B,A,C,D]. For each letter, you then say what the order is. So in the first list, it would be A = 0, B = 1 etc etc. In the second list, it would be A = 1, B = 0 etc etc. You could then represent the two orders as arrays like this: [0,1,3,2] and [1,0,2,3] (imagine [A=1,B=0,C=3,D=2]) So then when you're doing crossover, you could pick at random from one of those two lists. So you might get [0,0,3,3] You then go through that list for duplicates, and for each of the duplicates, you pick the closest unpicked number and assign it at random (or a weighted random selection) to one of the two. So the closest unpicked to 0 is 1, and the closest unpicked to 3 is 2. So you might end up with [0,1,3,2] or somesuch. On a separate note, one of the issues I think with the algorithm as it is is that it picks a random subsection and then puts it at the start. So if the optimal thing is [A,B,C,D,E], and you have [A,B,C,E,D], which is pretty close to being good, and you pick [B,C], you then might get [B,C,A,D,E], which is really bad, even though B and C were good picks (they really should end up next to each other). It'd be better if instead it put them back where they were, because their position in the order might be part of what makes them good. so you'd get [X,B,C,X,X], which might end up as like [D,B,C,E,A], but it's more likely to have maintained the 'good part' of thee [B,C] connection.

@TheCodingTrain 7 лет назад

Thanks so much for this feedback!

@GABRIELFILMSTUDIOS 7 лет назад

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

@frodeflem9353 7 лет назад

Optimizing an optimizer. It's brilliant!

@vgarzareyna 6 лет назад

Why not use BackProp?

@piercegray2324 5 лет назад

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

@PerMortensen 5 лет назад

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

@crellagecommunity7168 7 лет назад

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

@gitchai8838 3 года назад

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.

@brittgriscom7905 7 лет назад

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 7 лет назад

Not yet, but I should!

@christopheranagbogu7659 5 лет назад

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.

@theWorldOfIss Год назад

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

@erggish 6 лет назад

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.

@adrijeguha9806 2 года назад

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 2 года назад

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

@earthbjornnahkaimurrao9542 6 лет назад

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 6 лет назад

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

@earthbjornnahkaimurrao9542 6 лет назад

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

@BeholdTheDevil 7 лет назад

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 7 лет назад

Oh, I like this idea!

@BeholdTheDevil 3 года назад

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.

@ivanxdxd 7 лет назад

I thought it was the traveling salesman problem.

@spookyturbo1618 6 лет назад

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 6 лет назад

Thanks for this feedback!

@balabuyew 6 лет назад

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.

@twiho 9 месяцев назад

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.

@adityavijayvergia8495 5 лет назад

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 5 лет назад

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

@jojosukida 7 лет назад

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 7 лет назад

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

@baqarhussain5758 7 лет назад

can i get its code please

@ivanpetrovic-poljak6411 7 лет назад

Hey what programming languages do you know?

@topie5344 2 года назад

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 2 года назад

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

@ericguzman4367 3 года назад

Is this a multiobjective TSP?

@SirCutRy 7 лет назад

@Fasyx Atom

@Fasyx 7 лет назад

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

@letoan285 7 лет назад

It's Atom, as i saw

@TheCodingTrain 7 лет назад

Yes, it's Atom. Here are some of these workflow videos: sublime text: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-UCHzlUiDD10.html atom editor: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-d3OcFexe9Ik.html brackets: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-nmZbhManVcY.html codepen: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-5gfUgNpS6kY.html

@charbelsarkis3567 7 лет назад

did someone just scream in the hallway?

@Jkauppa 3 года назад

it will work if you do partial optimization minimization

@Jkauppa 3 года назад

two, four, eight, summed up

@Jkauppa 3 года назад

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

@Jkauppa 3 года назад

order pizza

@Jkauppa 3 года назад

slices

@Jkauppa 3 года назад

hacking locks?

@nicholascurry5536 7 лет назад

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 5 лет назад

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

@BradHouser 3 года назад

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 2 года назад

I agree

@AlefeLucas 5 лет назад

After applying crossover, my algorithm became far to optimal.

@akshpatel7935 6 лет назад

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

@luckydubeandbobm1 6 лет назад

I think he is doing th Order Crossover :)

@JosephOntime 7 лет назад

Next Coding Challenge: GTA 5

@ColeNOXyd2nd 7 лет назад

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

@TheCodingTrain 7 лет назад

Aha, thanks!

@masterflamaster6377 7 лет назад

I don't really like ES6...

@Tymon0000 7 лет назад

ES6 is awesome! So elegant, natural and amazing!

@crazyfox55 7 лет назад

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

@Nulono 7 лет назад

6:04 *fewer

@TheCodingTrain 7 лет назад

doh

@neeleshranjansrivastava6985 4 года назад

7:56 This is Cancer 🤣

@assaqwwq 7 лет назад

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 5 лет назад

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 5 лет назад

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.