salesman

    Simulated annealing can provide potential solutions to the traveling salesman problem. The traveling salesman problem was introduced in chapter 6, “Understanding Genetic Algorithms.” Aside from the fact that the traveling salesman problem from this chapter uses simulated annealing, it is the same as the program presented in chapter 6.

    The source code accompanying this book provides a generic simulated annealing class. This abstract class is named SimulatedAnnealing and can be used to implement a simulated annealing solution for a variety of problems. We will use this simulated annealing class for both the neural network example and the traveling salesman problem.

    This section will describe how the generic SimulatedAnnealing class works. The application of simulated annealing to neural networks and the traveling salesman problem will be covered later in this chapter.

    The method used to randomize the path of the traveling salesman is somewhat more complex than the method used to randomize the weights of a neural network. This is because there are constraints that exist on the path of the traveling salesman problem that do not exist when optimizing the weight matrix of the neural network. The most significant constraint is that the randomization of the path must be controlled enough to prevent the traveling salesman from visiting the same city more than once, and at the same time ensure that he does visit each city once; no cities may be skipped.

    The previous sections discussed the background of the simulated annealing algorithm and presented various applications for which it is used. In this section, you will be shown how to implement the simulated annealing algorithm. We will first examine the algorithm and then we will develop a simulated annealing algorithm class that can be used to solve the traveling salesman problem, which was introduced in chapter 6.

• What is Simulated Annealing?
• For What is Simulated Annealing Used?
• Implementing Simulated Annealing in C#
• Applying Simulated Annealing to the Traveling Salesman Problem

    In chapter 6, “Understanding Genetic Algorithms,” you were introduced to genetic algorithms and how they can be used to train a neural network. In this chapter you will learn about another popular algorithm you can use, simulated annealing. As you will see, it can also be applied to other situations.

    In this chapter, you were introduced to genetic algorithms. Genetic algorithms provide one approach for finding potential solutions to complex NP-hard problems. An NP-hard problem is a problem for which the number of steps required to solve the problem increases at a very high rate as the number of units in the program increases.

    So far, we have discussed the basic principles of genetic algorithms and how they are used. Now it is time to examine a C# example. In this section, you will be shown a complete application that is capable of finding solutions to the TSP. As this program is examined, you will be shown how the user interface is constructed, and also how the genetic algorithm itself is implemented.

    In this section you will be introduced to the traveling salesman problem (TSP). Genetic algorithms are commonly used to solve the traveling salesman problem, because the TSP is an NP-hard problem that generally cannot be solved by traditional iterative algorithms.

    A genetic algorithm begins by creating an initial population of chromosomes that are given a random collection of genes. It then continues as follows:

    1. Create an initial population of chromosomes.

    2. Evaluate the fitness or “suitability” of each chromosome that makes up the population.

    3. Based on the fitness level of each chromosome, select the chromosomes that will mate, or those that have the “privilege” to mate.

    4. Crossover (or mate) the selected chromosomes and produce offspring.

• Introducing the Genetic Algorithm
• Understanding the Structure of a Genetic Algorithm
• Understanding How a Genetic Algorithm Works
• Implementing the Traveling Salesman Problem
• Neural Network Plays Tic-Tac-Toe