Example 1: Travelling Saleman Problem

Boltzmann Machine

The Boltzmann Machine is a simple neural network architecture combined with simulated annealing.

Boltzmann network design

Figure 1. A Boltzmann Machine with a simple matrix architecture.

Example code in VB.NET: Traveling Salesman Problem

This is a rendition of the classic Traveling Salesman Problem, where the shortest tour needs to be found among all cites without visiting the same one twice. The algorithm works out the minimum Cartesian distance through eight cities. The cities are arranged in a circle, where the shortest distance is to go around in order, but the algorithm doesn't know this. The correct solution can be in forward or reverse order, and it doesn't matter which city is the start (ie: 01234567, 76543210, or 45670123). There are 10^8 (or, 100,000,000) possible combinations, but this algorithm can find them in less than 10^3. Note that the number of cities can be modified for experimentation.

At the start, the Boltzmann algorithm tries random variations of combinations searching for the final solution. As it gets closer to the solution, it limits the variation of combinations to those that come closest to succeeding. This focuses the search, but we don't want it to focus too narrowly, too fast, otherwise it will wander off track and lose the final sulotion. The rate at which the algorithm should focus is called the temperature (e.g.; like the rate for reducing temperature to get the right consistency).

In this example, the temperature is being reduced by a factor of 0.99, which is pretty close to the slowest possible reduction speed (i.e.; more epochs at each temperature). Setting this factor lower, like 0.95 or 0.90, will entail fewer epochs at each temperature, which might make the algorithm run faster, but increases the likelihood of getting stuck in local minima.

The gamma value performs a similar function to temperature, keeping the algorithm from getting stuck in local minima.

View code example: Boltzmann.vb class

View code example: Form1.vb class

Example Results #1

Eight cities and Gamma value of 9.

Note how this results listing goes from bottom to top. So, the beginning is at the bottom of the list, and the end is here at the top.

Temperature Valid Length Tour

0.9724 yes 6.122934 70123456

0.9822 no 620

0.9921 no 23

1.0021 no 5

1.0122 no 561

1.0225 no 1365

1.0328 no 6

1.0432 no 532106

1.0538 no 645

 

...(results abbreviated)...

 

95.0990 no 7

96.0596 no

97.0299 no

98.0100 no 34

99.0000 no

100.0000 no

Example Results #2

Eight cities and Gamma value of 4.

Note that this results listing goes from bottom to top. So, the beginning is at the bottom of the list, and the end is here at the top.

Temperature Valid Length Tour

0.3419 yes 6.122935 07654321

0.3453 no 42

0.3488 no 0743

0.3524 no

0.3559 no

0.3595 no 7321

0.3631 no 5

0.3668 no 35

 

...(results abbreviated)...

 

95.0990 no 76030

96.0596 no 50

97.0299 no

98.0100 no 144

99.0000 no 156

100.0000 no 3

Example Results #3

Of course, the algorithm will occasionally get stuck in a local minimum, resulting in an incorrect solution.

Ten cities and a Gamma value of 7.

Temperature Valid Length Tour

0.6312 yes 8.180339 2109874563

0.6375 no 085321

0.6440 no 307654

0.6505 no 579123

0.6571 no 09243

0.6637 no 85219

 

...(results abbreviated)...

Example Results #4

More often than not, though, it arrives at the right solution.

Ten cities and a Gamma value of 7.

Temperature Valid Length Tour

0.6186 yes 6.18034 1234567890

0.6248 no 2354601

0.6312 no 98762

0.6375 no 60917

0.6440 no 325

0.6505 no 348910

0.6571 no 07

0.6637 no 43

 

...(results abbreviated)...

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}