User ParametersPopulation Size
This parameter specifies the number of chromosomes that will be created at each
generational step. Usual values are in the range between 50 and 500.
Generations
This value represents the number of generations that will be created before the
system stops and displays the result. In other words, this is the time limit of the evolution. Usual values are in the range between 25 and 300.
It's recommended to start with a low value and increase it until the resulting graph shows that the population fitness has time enough to converge.
Crossover is applied when a new offspring chromosome, based on two parent chromosomes, is created. The algorithm selects one part from the first parent chromosome and another part from the other parent and the combines them, resulting in the new offspring chromosome.
The chromosome part selection and recombination differs between crossover algorithms. In this system, two kinds of crossover algorithms are provided.
Fixed Position Sequential
This algorithm is a close cousin to the traditional two-point crossover operator. It "cuts" out a section from one of the parents and combines that section with the missing parts of the other parent.
The Traveling Salesman problem does however put restrictions to this procedure in such a way that the traditional two-pointer can't be used (the gene material is constant).
The kind of mutation used in this program is called "scramble sublist mutation". It randomly selects a section of the chromosome and mixes up the genes within the selected section.
The "Mutation Probabilaty" factor determines how often mutation will occur.
Population Deletion
This GA part defines how new chromosomes will be put into the existing population.
In this system, two different kinds are implemented.
The "Elitism Value" parameter is used to assure that the best [x] chromosomes will survive the generational replacement.
Steady Delete
In this algorithm, every new offspring is replacing the worst chromosome in the population. Thus, chromosomes that are members of the same generation can be eachother's parents! This is, of course, not biological viable but can have good effect in speeding up the population fitness convergence during evolution.
When solving the Traveling Salesman problem, it is wise to let the initial evaluation of a chromosome be the sum of the distances between the genes in the chromosome. Since the goal is to find the shortest path, low evaluation value is equal to good fitness. For technical reasons (the system uses "Roulette Wheel Selection"), the initial chromosome evaluation is "inverted" in such a way that the best chromosome gets the worst chromosome's evaluation and v.v. This process is discussed in more detail in the information document.
After the initial evaluation, the actual chromosome fitness of each chromosome (based on the evaluation mentioned above) is calculated using one out of three algorithms.
Windowing
This algorithm translates the entire population fitness so that the weakest chromosome gets fitness 1, and the other gets a fitness equal to the amount by which they exceed the weakest chromosome evaluation.
The guarding value can be thought of as a social security algorithm for the weak chromosomes. Every chromosome with a fitness value less than the guarding value is assigned the guarding value.
Linear Normalization
The best chromosome is assigned fitness = 100. All other chromosomes' fitness gets decreasing values of the best fitness value. The decrement factor is set to be [x] percent (assigned in the "Parameter" form) of the best fitness which usually results in a slow but stable population fitness convergence.
In this implementation it is possible to "freeze" the random generator (by assigning "Seed" other integer values than zero) which makes it possible to repeat one specific GA run. If "Seed" is assigned the value 0, the program sets the internal seed to a random value, which in turn results in a different outcome at every execution.
Initially, the nodes are cities in Europe (including my home village Nykvarn and the place where I at the time do my CS studies - Umeå), but you are free to edit. Any real life problem (or virtual, for that matter) involving a graph is suitable. -It doesn't have to involve cities or geographical locations.
The name you give each node (city name initially) will show up in the "Best solution" section in the GATSS results document, allowing you to trace the best solution through your node names.
The number of nodes are crucial to the success of the Genetic Algorithm. This matter is discussed in the information document.
For the time beeing, the form syntax check is poor (this actually complies the entire collection of parameters), and thus, leaves no room for mistyping. Please use exactly the same syntax shown in the form initially:
[Node name]:[x coordinate],[y coordinate]No empty spaces or lines before or after the node definitions are allowed etc. Otherwise the program will act unpredictable.