Traveling Salesman Problem

In this section, the Flask will be used to solve the Traveling Salesman Problem (TSP).  TSP is a well-studied NP Complete problem.  In TSP, there is a set of cities with roads between all cities.  The problem is to find the shortest tour starting and ending at some node and passing through all cities once.  In the Symmetric Traveling Salesman Problem (STSP), the route from city a to city b is the same as the route from city b to city a.  Figure 1 shows a graph where the nodes represent cities and the arcs between nodes gives the distance between the cities.

Figure 1 - Traveling Salesman Problem

There are (n-1)!/2 possible tours in STSP where n is the number of cities.  For the simple graph in the figure, there are only 12 tours.  But, for a graph of 10 cities, there are over 181,000 tours.  Algorithms that generate all tours and test for the shortest one cannot deal with very large values of n.  Solving TSP using the Flask is essentially a generate and test approach.  However, a Flask solution for TSP will give insight into how this problem could be solved with the massive parallelism of using real molecules to solve TSP.

I sketch two solutions to TSP using the Flask.  Both represent the cities as atoms and use the BondLength attribute of binding sites to assign lengths of the roads between the cities.  The general idea is to form a molecule where all cities are represented, each atom has two road bonds, and following these bonds gives a tour of the cities.  Then, an atomic machine is used to find the solution molecule with the shortest path length.

The difficulty in setting up the problem is to control binding in such a way that only complete tours are formed where each city is represented once and the bonds connect all these cities in a proper tours.  We must design the problem such there are no free bonds in a full solution or that partial solution molecules do not bond to other solution molecules.

The two solutions have the following things in common:

  • 2of binding sites are used for the binding sites used to represent the roads between cities.  Each of the city atoms have four 2of binding sites, two of which will bind representing a tour with two roads attached to the city.
  • The ImprovedBLC (Improved Bond Length Comparator) atomic machine is used to compare two molecules representing tours and to select the one with the shortest path.  At the end of the simulation, the solution molecule attached to the ImrpovedBLC atomic machine is the best solution found.
The first method is based on a molecule that binds to five city atoms first, and then allows the city atoms to bind using the road binding sites.  The road binding sites are conditional binding sites and do no get a chance to form bonds until a molecule is formed with each of the city atoms.  This solution depends on the internalBondingOrderSites Flask parameter to present invalid solution molecules from forming.  The second method captures city molecules one at a time and builds a city tour as it adds atoms.  The key to making the second solution work is the IntraMolecular binding site attribute, which prevents partial solutions from binding to other molecules representing partial solutions.

TSP Solution 1

Figure 2 shows the atoms used in the first TSP solution.  All the atoms have number 15 except the Comparator atom, which has number 1.

Figure 2 - Atoms for Solution 1

When the atoms are simulated in the Flask, molecules representing TSP tours are formed.  These molecules are compared to each other by the Comparator, and when the simulation finishes after having been run for enough iterations, the Comparator atom will be attached to a single solution molecule.

Here are the steps in forming a solution molecule.  First, an S atom binds to a city atom by one of the SA, SB,...,SE binding sites.  It continues to collect city atoms of different names until all it has one of each city atom attached.  Next, with all the SA,...,SE binding sites bound, all the conditional bonds of S are fired.  The SAA,...,SEE binding sites form bonds with the a, b, c, d, and e atoms.  This causes these atoms to fire their conditional bonds, A,...,H that represent the road lengths.  Each atom has 2Of  road binding sites, so each city forms two roads with two other city atoms.

For proper tours to be formed, the internalBondingOrderSites Flask parameter must be enabled.  Without this feature, the city atoms would make bonds with other city atoms in nondeterministic order, which can result in tours that don't include all the cities, e.g., the tour <a, b, c, a> could be formed.  In this case, free binding sites for atoms d and e can then bind to atoms in other partially formed solution molecules.

With internalBondingOrderSites enabled, the atoms with the largest number of free binding sites are selected to form bonds first.  So, once a binds to b and c, either of the remaining two atoms are selected to form bonds next.  This prevents atom b from immediately forming a bond to c, causing a short tour.

Figure 3 shows a solution to the TSP problem as represented by the MoleView component of the FlaskRunner.

Figure 3 - FlaskRunner View of a TSP Solution

The Comparator atom has several attributes that are used in both TSP approaches.  First, the Dissolve feature is selected that removes the SOL binding site from any solution molecule that the Comparator releases.  This action prevents non-optimal solutions from rebinding to the Comparator atom.  The second option is Print.  If this option is enabled, the Comparator will output to System.out each time a comparison is made.  When using the MoleView feature of FlaskRunner, clicking on the Comparator will produce a dialog window with the result of the last comparison.  So, Print is usually disabled when running the GUI.  The third option is doMax.  If it is disabled, as in path length runs, the Comparator retrains the shortest path.  Otherwise, the longest path is retained.

Finally, there are options to guide how the Comparator finds either a path length or a tour length.  In TSP, the Comparator is told to look for cycles starting at city a and proceeding along road bonds.

TSP Solution 2

The second TSP solution is, perhaps, a bit more principled than the first since it does not rely on a special bond ordering feature of the virtual flask.  Instead, IntraMolecular binding sites are used.  These sites will only bind to other atoms in the same molecule.  They prevent partial solutions from binding to free atoms or other partial solutions.

Figure 4 shows the atoms in the solution.  All atoms have number 25 except for the Comparator, which has number 1.  Unlike the first solution, this version works by binding to one city atom at a time and forming routes as city atoms become part of the molecule.

Figure 4 - Atoms for second TSP approach

The function city a is split between two atoms:  SS and a.  The route out of city a is represented by one of the road binding sites from the SS, while the road into city a is represented by one of the road binding sites into atom a.  The remaining city atoms attach to the SB,...,SE binding sites of the SS atom.  When a city atom attaches to SS, its road binding sites are activated.  The first city atom to attach will form a road bond with SS.  At that point, the only active road binding sites in the molecule are from the first city atom to bind to the molecule.  And, because the road binding sites of the city atoms are 2of binding sites, only one road binding site is available.

When the next city atom attaches to the molecule, it forms one road bond with the previous city and has one more road binding site open.  The process continues until four city atoms are attached.  The order that the city atoms attach and the resulting road bonds created are stochastic in nature, so, if there are enough free atoms to start with, all tours will be formed.

Once the city atoms are attached to SS, the conditional SA binding site on it fires, and eventually an a atom attaches to the atom.  At that point, it forms a road bond with the last city atom that attached and fires its SOL binding site.  As before, the Comparator atomic machine finds solution molecules and retains a bond to one of the ones with the shortest tour.  Figure 5 shows a solution.

Figure 5 - MoleView of TSP solution using the second method

Both TSP methods rely on a single comparator atomic machine to find the best solution.  Since the comparator retains an attachment to the best solution it has found, using more comparators could lead to the case where each comparator would have an attachment to one solution and no comparisons could be made.  One solution is to allow comparators to attach to each other and compare the solutions they have attached to.  A better approach, perhaps, would be to add a Flask feature that would trace the most and least massive molecules and the ones with the longest and shortest bond length paths or cycles.