Data processing: artificial intelligence – Fuzzy logic hardware – Having function calculator
Reexamination Certificate
2000-01-31
2004-02-24
Starks, Jr., Wilbert L. (Department: 2121)
Data processing: artificial intelligence
Fuzzy logic hardware
Having function calculator
C382S250000
Reexamination Certificate
active
06697788
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a processing device for searching for an optimum value of a cost function in an optimization problem such as an optimum structure problem, an optimum location problem, an optimum route problem, etc.
2. Description of the Related Art
In recent years, the demand for solving an optimization problem has been increasing in various industrial fields. The optimization problem is a problem of searching for a state where a given cost function becomes a maximum, a minimum, a local maximum, or a local minimum. By changing the sign of the cost function, the problem of obtaining a maximum or a local maximum is changed to a problem of obtaining a minimum or a local minimum. Hereinafter, the optimization problem will be described mainly as a problem of obtaining a minimum or a local minimum.
For example, in a CAD (Computer-Aided Design), an evaluation value of intensity or stability is used as a cost function in order to improve the intensity of a building, a construction, etc., and the stability to an external force, and the structure corresponding to its optimum value is then obtained. Additionally, in a material design, the energy of an atomic/molecular level of a material is used as a cost function, and the structure corresponding to the lowest energy state is obtained. Also in a more general parameter fitting problem, a parameter combination which makes a cost optimum is obtained.
As the conventional methods for solving such optimization problems, there are two methods such as a descent method and a probabilistic method. A steepest descent method being a representative of the descent method is a method which calculates from a given state a direction where the value of a cost function drops, changes the state in the calculated direction, and obtains one candidate of the minimum value of the cost function. In this way, the local minimum value of the cost function can be obtained.
Additionally, algorithms representative of the probabilistic method include a random method, an SA (Simulated Annealing) method, and a GA (Genetic Algorithm) method.
The random method is a method which selects a state at random, and picks up a state where the value of a cost function is small. The SA method adopts a metropolis algorithm so as to determine a next state. According to this algorithm, if the cost of the next state drops, that state is adopted. If the cost rises, the state is adopted with a certain probability. This probability depends on a temperature parameter. The metropolis algorithm is used by setting a temperature somewhat high at first. Thereafter, the temperature is gradually lowered.
The GA method is an optimization method which simulates the mechanism of the evolution of living things. This method represents a state as a character string which is referred to as a chromosome, and optimizes respective genes by performing genetic operations such as selection, crossing-over, mutation, etc. for a chromosome aggregation.
However, the above described conventional methods have the following problems.
With the steepest descent method, if the state where a cost function becomes a local minimum is found during a search, the search falls into a trap and cannot get out of that state. Accordingly, the state where the cost function is the minimum cannot be necessarily found. The random method has a possibility that a strict solution can be found if the number of states is finite and small. However, if the number of states becomes large, this method does not work well.
With the SA method, a temperature must be lowered in order to improve a realization probability of a low cost value state according to the metropolis algorithm, which leads to a slow state change for a search. Accordingly, once the search is trapped into a local minimum state, it is impossible to get out of this state without waiting for a long time. Accordingly, the method for setting a temperature high at first, and for lowering the temperature gradually is considered to be effective. However, there is no deterministic and general implementation of this temperature scheduling method, and how to arrange a temperature schedule becomes a problem.
Furthermore, since the GA method is lack of a neighborhood search capability, it cannot find a more optimum state if it exists in a neighborhood, which frequently causes a near miss. Still further, a theoretical proof that an optimum state can be found is insufficient.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a processing device for efficiently searching for an optimum value of a cost function regardless of its local form.
In a first aspect of the present invention, a processing device comprises an inputting device, a candidate searching device, and an outputting device.
The inputting device inputs a state where a problem is described, and information of a cost function giving the cost of the state. The candidate searching device obtains one or more candidates of an optimum state by using deterministic dynamics which generates a realization probability that takes a higher value at a state that attains a more optimum value of the cost function. The outputting device outputs the obtained candidates.
In a second aspect of the present invention, a processing device comprises an inputting device, a defining device, a setting device, a calculating device, and an outputting device.
The inputting device inputs a parameter. The defining device defines a cost function which gives a state cost. The setting device sets an adjustment a function. The calculating device numerically solves a differential equation, which is described by the parameter, the cost function, and the adjustment function, in terms of a value, and obtains one or more candidates of an optimum state. The outputting device makes an obtained calculation result visible, and presents it to a user.
REFERENCES:
patent: 5734755 (1998-03-01), Ramchandran et al.
patent: 6032123 (2000-02-01), Jameson
Gear, C.William, Applications and Algorithms in Science and Engineering, Science Research Associates, Inc., 1978, pp. A8-A12.
Fukuda Ikuo
Kameda Shigeru
Masuda Shoichi
Suzuki Ichiro
Fujitsu Limited
Staas & Halsey , LLP
Starks, Jr. Wilbert L.
LandOfFree
Processing device searching for an optimum value of a cost... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Processing device searching for an optimum value of a cost..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Processing device searching for an optimum value of a cost... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3284512