reset password
Author Message
rabbott
Posts: 1649
Posted 22:24 Apr 23, 2020 |

I apologize that I fell a bit behind this week, but a framework for your code is now available.

Download ga_tsp.py from the ga_examples directory on GitHub. (Actually, you should download all of PyLogo.)

Your job is to write three methods. Two of them generate initial TSP paths. They are TSP_Chromosome.greedy_path and TSP_Chromosome.spanning_tree_path.

They are both in the TSP_Chromosome class as static methods. There is a third path generator, TSP_Chromosome.random_path.

The generators are called from TSP_World.gen_individual. As currently written, each has a 1/3 chance of being called.

The third method is the mutation method two_opt, which is also in the TSP_Chromosome class. Its job is to do a 2-opt transformation on the chromosome that calls it. It is called from mutate in the TSP_Individual class. The other mutate operator is move_gene_in_chromosome. (It picks a gene, i.e., a point, at random and looks for a better place in the path to put it.) Each has a 50% chance of being called.

As usual, if you have questions, please post them to the forum.

I may make changes to this file, but it shouldn't affect your code.

Last edited by rabbott at 23:10 Apr 23, 2020.
rabbott
Posts: 1649
Posted 23:01 Apr 23, 2020 |

One of the things I enjoy watching is how the system adjusts as the points move around. To get that effect, check move points on the UI.

rabbott
Posts: 1649
Posted 12:31 Apr 24, 2020 |

The Create and Delete nodes buttons now work. There is also a Reverse button that reverses the direction of motion of the points. Download both core.ga.py and Exampes.ga_examples.ga_tsp.py.

rabbott
Posts: 1649
Posted 12:42 Apr 24, 2020 |

With Eliminate duplicates on, the default, the system ensures that the population contains no duplicate individuals. This is a fairly straight-forward and relatively simple way to ensure diversity.

Testing for duplicates is more difficult than it may seem for the TSP problem. In general, all one need do is to compare the chromosomes of two individuals to see if they are the same. For TSP and related problems, it's not so simple. Two chromosomes may be rotated or reversed versions of each other and yet should still count as the same.

To eliminate this problem, whenever an Individual is created, its chromosome is normalized: the point on the screen with the smallest id is put first with the rest following in the original order. Even that is not quite right. We must decide which element comes after the first point. Is it the one to the right or the one to the left. The code selects the smaller one. If that one had originally been to the left, the chromosome is reversed.

The static (factory) method (appropriately called factory) in TSP_Chromosome does all that work and generates the normalized chromosome. Chromosomes should be instantiated through the use of the factory method rather than by calling TSP_Chromosome directly.

Last edited by rabbott at 12:46 Apr 24, 2020.