Asee peer logo

Optimization Using The Simulated Annealing Algorithm

Download Paper |

Conference

1998 Annual Conference

Location

Seattle, Washington

Publication Date

June 28, 1998

Start Date

June 28, 1998

End Date

July 1, 1998

ISSN

2153-5965

Page Count

9

Page Numbers

3.434.1 - 3.434.9

Permanent URL

https://peer.asee.org/7327

Download Count

40

Request a correction

Paper Authors

author page

Edgar N. Reyes

author page

Dennis I. Merino

author page

Carl W. Steidley

Download Paper |

Abstract
NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Session 2520 Optimization Using the Simulated Annealing Algorithm

Edgar N. Reyes, Dennis I. Merino, Carl Steidley Southeastern Louisiana University/Texas A&M University - Corpus Christi Hammond, LA 70402/Corpus Christi, TX 78412

Abstract In this paper we will briefly review the simulated annealing algorithm, an algorithm with applications in optimization and pattern recognition used extensively in artificial intelligence. In earlier papers the authors analyzed a simulation of the annealing of a solid, a dodecahedron in particular. Our use of this algorithm, which is based in the field of combinatorial optimization, reflects properties of Boltzman machines - a neural network characterized by massive parallelism.

We will demonstrate two implementations of this algorithm in simulated annealing. Each of the implementations depends upon a neighborhood structure and a transition mechanism. In the first implementation our neighborhood structure is a linear transformation of the vector space of all configurations and the transition probability is deterministic. In this case, we will use techniques from character theory of finite groups to analyze simulated annealing. In the second implementation, a special case of which includes the first implementation, our neighborhood structure is a set-valued function and the transition mechanism is stochastic in nature. In this case, we use techniques from matrix analysis, in particular properties of doubly stochastic matrices, to analyze simulated annealing modeled and based on a class of Boltzman machines.

For pattern recognition, we use the simulated annealing algorithm to solve the classic seven-segment display problem. This is a classification problem which we will solve by choosing an appropriate Boltzmann machine.

1. Introduction. Annealing is the physical process of heating up a solid and following it by a specified slow cooling process. We shall use the simulated annealing algorithm, a method based in the field of combinatorial optimization, to describe simulated controlled cooling processes. In the annealing process, one can interpret the states (and free energy) of the solid in the cooling process as solutions (and cost function, respectively) of a combinatorial optimization problem [1]. Our use of the simulated annealing algorithm reflects properties of Boltzman machines, a neural network model belonging to a class of connectionists models and which has massive parallelism as a feature, amongst others.

Also, we will use an appropriate Boltzmann machine to solve a pattern recognition problem, namely, the seven-segment display problem. The display of the decimal digits in a hand-watch for instance uses a seven-segment display. In identifying the digit displayed, we will maximize an overall measurement of desirability of the Boltzmann machine.

We shall briefly review some aspects of Boltzman machines and the simulated annealing algorithm. Let (U, C) be a network consisting of units, U = {u i : i = 1, ..., n } , and a set of

{ } { } connections, C, consisting of unordered pairs u i , u j . A connection u i , u j in C is said to join u i to u j . Intrinsic to Boltzman machines are the notions of a connection strength s and a

Reyes, E. N., & Merino, D. I., & Steidley, C. W. (1998, June), Optimization Using The Simulated Annealing Algorithm Paper presented at 1998 Annual Conference, Seattle, Washington. https://peer.asee.org/7327

ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 1998 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015