Data processing: artificial intelligence – Machine learning
Reexamination Certificate
2000-02-28
2003-02-04
Davis, George B. (Department: 2121)
Data processing: artificial intelligence
Machine learning
C706S021000
Reexamination Certificate
active
06516307
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a processing apparatus for solving an optimizing problem using simulated annealing (hereinafter, referred to as SA) and a method thereof.
2. Description of the Related Art
In recent years, in order to solve problems in various fields, it has become necessary to solve relatively large optimizing problems. The SA is a general-purpose solving method for solving such optimizing problems. The SA has been successfully used for optimizing problems such as cell placing problems in VLSI (very large scale integration) design and scheduling in production process.
In the annealing method, a substance is heated to a high temperature and then gradually cooled so that the energy thereof physically becomes the minimum state (ground state). In a system to be evaluated, evaluating energy is defined. An annealing process of the system is simulated corresponding to metropolis procedure so as to optimize the state of the system. This technique is referred to as SA.
Next, the algorithm of conventional SA will be described. First, assume a system that is composed of many objects that have various states. The sum of states of all the objects is the state of the system. As a real function of the state of the system, energy is defined. When SA is applied for a problem of a combination, energy is defined corresponding to an evaluation value of the combination. As the energy is low, the evaluation is high.
Next, objects are selected in a proper order. For each object, the metropolis procedure is applied. States of alternatives with probabilities are designated to each object. A system energy E
f
in the state of an alternative designated to each object and a system energy E
n
in the present state are calculated. On the other hand, random numbers in the range from 0 to 1 are uniformly generated. The generated random numbers are denoted by r. A temperature parameter is denoted by T. When exp[−(E
f
−E
n
)/T]≧r, each object is designated to the state of the alternative. On the other hand, when exp[−(E
f
=E
n
)/T]<r, each object is kept in the present state.
When this operation is continued with T (constant), the system converges to a Gibbs distribution due to the temperature T and the system energy. When T is gradually decreased and approaches O, the system converges to a state of which the minimum value or semi-minimum value of energy is given. The latter is referred to as SA due to an analogy of a physical phenomenon. In particular, a temperature change schedule is referred to as an annealing schedule. Logically, it has been proved that when the temperature T is very gradually decreased, the system converges to a state of which the minimum value of the energy is given. However, practically, so as to reduce the process time, the temperature is relatively quickly decreased.
The SA has the following advantages. As a first advantage, it is logically assured that the system converges to an optimum solution. In reality, the system converges to an optimum solution or a semi-optimum solution. As a second advantage, since the SA can be generally used, it can be easily applied for various problems. As a third advantage, functions that represent system energy or restricting condition have almost no restrictions and they may be discontinuous.
However, as described above, since the algorithm of the SA is basically a sequence of simple operations that determine whether or not to accept the state of the next alternative, it may take a very long time. In addition, the acceptance of the state of the alternative depends on the difference of energy in the present state and the state of the alternative. Thus, the state is not always accepted. When the state of the alternative is not accepted, since the system remains in the present state, the convergence of the system is further delayed.
In other words, when the SA is used, a good solution can be finally obtained. However, it takes a very long time to obtain a solution. Thus, it is necessary to perform the system at a high speed.
SUMMARY OF THE INVENTION
An object of the present invention is to modify the algorithm of the SA so as to provide a processing apparatus for solving an optimizing problem at high speed and a method thereof.
As an aspect of the present invention, when determining whether or not to transit the present state to the next state, an alternative of the next state is selected so that the probability for accepting the alternative of the next state becomes high. In other words, the probability for selecting the alternative of the next state is designated so that the alternative is accepted as the next state with a high probability. Thus, the simulated annealing process can be performed at high speed, thereby contributing to solving various optimizing problems.
These and other objects, features and advantages of the present invention will become more apparent in light of the following detailed description of best mode embodiments thereof, as illustrated in the accompanying drawings.
REFERENCES:
patent: 5134685 (1992-07-01), Rosenbluth
patent: 5241465 (1993-08-01), Oba
patent: 5274742 (1993-12-01), Morita
patent: 5303328 (1994-04-01), Masui
patent: 5475608 (1995-12-01), Masuoka
patent: 5754444 (1998-05-01), Koford
patent: 5813798 (1998-09-01), Whiffen
Qian, “Computer networking representations for parallel distributed computing algorithms”, IEEE Proceedings of Intl Conf on Neural Networks v 2 p 1577-81.
Chen, “Electronic structure and morphology of alkali-metal clusters”, J. Phys. B: At. Mol. Opt. Phys. 23, pp 885-903.
Poteau, “Distance dependent Huckel type model for the study of sodium clusters”, Physical review B v 45 n4.
Lu, “first principles simulated annealing study of phase transitions and short range order in transition metal and semiconductor alloys”, Physical review B v 50 n10.
Goldstein, “Optimal protein folding codes from spin glass theory”, Proc Natl Acad Sci USA v89.
Puma, “Computer analysis of electron paramagnetic resonance data using the monte carlo method”, J. Phys C: solid state phys. 21.
Duane, “Hybrid Monte Carlo”, Physics Letters B v 195 n2.
Tomanek, “Growth regimes of carbon clusters”, Physical review letters v67.
De Groot, “Optimizing complex problems by nature's algorithms: simulated annealing and evolution strategy-a comparative study”, IEEE conf of parallel problem solving from nature.
Pensini, “Flowshop and TSP”.
Beckerman, “Segmentation and cooperative fusion of laser radar image data”, SPIE conf on sensor fusion and aerospace applications II v 2233.
Hynderickx, “Simulated anneal method for the determination of spin hamiltonian parameters from esr data”, Journal of magnetic resonance v70.
H. Igarashi, “An estimation of parameters in an energy function used in a simulated annealing method”, 1992 International Joint Conference on Neural Networks, vol. 4, pp. 480-485.
Chong Su Yu et al., “Parallel mean field annealing neural network for solving traveling salesman problem”, 1992 International Joint Conference on Neural Networks, vol. 4, pp. 532-536.
A. Rangarajan et al., “A continuation method for emission tomography”, Conference Record of the 1992 Nuclear Science Symposium and Medical Imaging Conference, vol. 2, pp. 1204-1206.
German et al., “Stochastic relaxation, Gibbs distributions, and the Bayesian Restoration of images”,IEEE Transactions of Pattern Analysis and Machine Intelligence PAM-6, No. 6, pp. 721-741, 1984.
Johnson et al., “Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning”,Operations Research, vol. 39, No. 3, pp. 378-406, 1991.
Johnson et al., “Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning”,Operations Research, vol. 37, No. 6, pp; 865-892, 1989.
Yugami et al., “Solving a Large-Scale Production Scheduling by Extended Simulated Annealing”,Artificial Intelligence, vol. 90-8, pp. 61-69, 1993.
Hongo et al., “Contour Extraction By Local Parallel and Stochastic Algorithm which ha
Kitajima Hironobu
Masuoka Ryusuke
Armstrong Westerman & Hattori, LLP
Davis George B.
Fujitsu Limited
LandOfFree
Next alternative generating apparatus using simulated... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Next alternative generating apparatus using simulated..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Next alternative generating apparatus using simulated... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3182564