Visualisation of Genetic Algorithms for The Traveling Salesman Problem in Java - By Johannes Sarg

xiaoxiao2021-03-06  134

The Traveling Salesman Problem (TSP) Find the shortest trip through n towns where each town must be visited exactly once. In the following we define that from each town all other towns can be visited. The costs to visit a town from another are represented by Their Euklidic Distance. Therefore The costs are reflexive.

The Genetic Algorithm (GA) A GA tries to use basic principles of natural evolution. It is especially appropriate for problems with large and complex search-spaces, where the global optimum can not be found within a reasonable amount of time using traditional techniques as Eg Total Enumeration or Branch and Bound. It cannot Be Guaranteed That The Optimum Solution is found by The Ga. Here Area Some References for GAS. Structure of A GA:

Procedure Ga

Begin

T = 0;

Initialize (p (t));

Evaluate (p (t));

While (Not Termination Condition)

Begin

T = T 1;

Qs (t) = Selection (p (t-1));

QR (T) = Recombination (QS (T));

P (t) = mutation (qr (t));

Evaluate (p (t));

END;

END;

Description: A set of potential solutions are randomly initialized and their quality evaluated Out of this set better solutions are preferred, corresponding to a probability distribution Each time, two of the selected solutions creats new solutions by recombination which finally are mutated These generated... .......................

Objectives of the program TSPGA

Exact Simulation and Visualisation of a Ga Run Visualisation of The Mutation and Recombination Methods Possibility To Compare Different Ga Runs Concerning The Same TSP

The Ga for Tsps in The "Options" Menu, You Can CONFIGURE THE FOLLOWING Properties for the Ga: Ga Parameters: Recombination Methode:

Partially Matched Crossover (PMX) Order Crossover (OX) Cycle Crossover (CX) Uniform Order Based Crossover (UOBX) Edge Recombination Crossover (ERX) ERX with heuristic (Grefenstette) None recombination probability (0% - 100%) mutation methode:

Inversion Insertion Displacement Reciprocal Exchange (Swap) None mutation probability (0% - 100%) population size (5 - 100) k value for the Tournament selection (1 - 10) elitism (true / false) Set Problem: A grid can be defined Where the user can set the positions of the direction (4 - 100 towns).

转载请注明原文地址:https://www.9cbs.com/read-127316.html

New Post(0)