Genetic Algorithms Testbed

-- P. Brooks, Stuyvesant High School, Aug. 2018

-- This testbed is designed to experiment with Genetic Algorithm (GA) programs.  The task is to solve the Traveling Salesman problem, which cannot be solved by the brute-force method of checking all paths, even when the number of cities is relatively small -- for instance, with just 15 cities, the number of possible paths connecting them is 15! = 1,307,674,368,000.

The problem we're trying to solve is the following: given a number of cities (between 6 and 20) randomly placed as points on a circle, and given a number of salesmen (between 4 and 100), find as short a path as possible starting from any city, then traveling to every other city and then returning to the first.  I have placed the cities in a circle so that we, as humans, can see the obvious shortest path (from each city to its neighbor all around the circle).  However, the routines we develop do not know that there is an obvious solution in this particular case -- we are developing a general algorithm that should be suitable for any set of points on a plane (or, for that matter, any dimension greater than or equal to 2).  Unless the number of cities that we choose is small (like 4 or 7), it's unlikely that our algorithms will find the shortest route, but the GA-Viewer will show us the best path we've found (the best of our salesmen), and then the paths that the other salesmen have found (progressively worse paths).

-- The testbed for experimenting with Genetic Algorithms (GA) consists of two cooperating programs:
a) the GA-Viewer.nlogo program (which I have provided) and
b) a Python genetic algorithm program (which you will write)
The two work together, with the Netlogo-based Viewer calling the Python program to implement the GA algorithm, and then receiving the Python program's results, which the viewer displays.

-- Create a directory (folder) on your computer for GA experiments.  We'll call this your GA directory.

-- The GA-Viewer.nlogo can be downloaded by right-clicking here, and choosing "Save As...".  Put it into your GA directory.  It was written using Netlogo version 6.0.1, and you may need to download and install that version to use it.

-- I've also provided a sample Python (non-GA) program that works with the GA-Viewer, so that you can see how they interact.  It's called GA-Random -- it does not implement a genetic algorithm -- it simply assigns a random path (a random permutation of the cities) to each saleman.  It's provided so that you can see how the interaction between a Python program and the GA-Viewer must occur.  Download it from here to your GA directory.  Once downloaded, change the suffix of the file from ".txt" to ".py"


Below you'll find documentation on the GA-Viewer.nlogo program, and then documentation on the data formats for the transfer of information between the Netlogo program and your Python program.  And finally there's the documentation about your Python program.

Contents:
GA-Viewer

GA-Viewer Docs

Explanations of buttons, sliders and other controls:

  • Setup Cities in a Circle: This is the basic setup for a new number of circle-points or a new number of salesmen. GA-Viewer will create the requested number of points on the circle, with no two points closer than 5 degrees apart.  And it will create the requested number of salesmen.  It will also give each salesman a random path (a random permutation of the cities), so that you can see how good/bad the best and worst such paths are.  You can try pressing this button, and then seeing the results by pressing (actually toggling) the "Show Salesmen Paths" button.

  • Load Cities / Save Cities: If there's a particular configuration of cities that you'd like to save (for instance, by chance, the button above placed all the cities in one half of the circle), you can save that configuration to a file and load it back later.

  • WorkingDir: This should be your GA directory where your Python GA program(s) can be found.  The picture shows mine at home.

  • Python-Command-line: GA-Viewer will execute this command-line to launch your Python program. In the image above, there are 7 words (the maximum) on the command line.  The first 4 words are required, and the last three were needed by my Python program as parameters (your Python program can use up to 3 parameters that will be passed to it by this command-line).

    • Python-name: The name of the python program (either "python" or "python3")

    • Program-filename: The filename of your Python program.  (mine was "GA1.py")

    • Input-filename: The filename of the datafile which will be written by GA-Viewer and intended to be read by your Python program (mine was "GA-Net2Py.txt"). 

    • Output-filename: The filename of the datafile that your Python program will write with its calculated results, and that will be read by GA-Viewer and displayed.  (mine was "GA-Py2Net.txt").

    • The next 3 words ("0.8", "0.1" and "1") are used by my program to control some internal probabilities and actions.  Your program may use 0 - 3 parameters for anything you please.

  • Num-Generations: The number of GA generations your program should run. This information will be passed to your program inside the Input-file.

  • Run Python Program:  After writing the Input-file containing information necessary for your Python program, this launches your Python program, waits for it to finish, and then reads the results it produced inside the Output-file.  Once the results are read, GA-Viewer will plot the results (see plot explanations below), and also populate the salesmen's paths that can be seen if the"Show Salesmen Paths" button is depressed.

  • Save Current / Load Previous: If there's a interesting result (some combination of interesting layout of cities, and interesting solution by your program), you can save it and then recall it later.  This is useful for comparing results -- for instance, if your program is controlled by parameters, and you twiddle with the parameters to see how the results change.

  •