Data processing: artificial intelligence – Machine learning – Genetic algorithm and genetic programming system
Reexamination Certificate
2000-09-12
2003-11-18
Davis, George B. (Department: 2121)
Data processing: artificial intelligence
Machine learning
Genetic algorithm and genetic programming system
Reexamination Certificate
active
06651046
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an optimizing apparatus, an optimizing method, and a storage medium.
2. Description of the Related Art
Optimization forms the base of an intellectual process in the use of a highly advanced computer. Its specific application fields are, for example, the scheduling problem, the vehicle allocation problem, the pattern estimation problem, the automatic timetable assignment problem, the crew positioning problem, etc. However, since a limitation is imposed on a calculation amount or a storage apparatus capacity, it is not practical to solve such large-scale optimization problems by a search of all solutions.
As computer performance has been improving, closer attention is being paid to stochastic optimization methods (simulated annealing, a GA (Genetic Algorithm), etc.) as a means for solving a problem that is difficult to be solved with a conventional expert system etc., and studies have been made to put the methods into practical use. Especially, a GA attracts a great deal of attention among various optimization methods because of its simplicity.
Furthermore, personnel scheduling is a fundamental problem in all industries. This can be understood as one of optimization problems. This problem has a critical influence on cost reduction.
For example, in an aviation field, labor costs rank second to fuel costs on a worldwide scale. A reduction in labor costs is a significant challenge.
As a normal method for solving a combinatorial problem, modeling using simultaneous equations and mathematical solution seeking, such as LP (Linear Programming) and IP (Integer Programming) methods, etc., are utilized, and a problem is solved as a set partitioning problem or a set covering problem.
With these methods, however, putting of a complicated problem into definite equations itself is difficult when the problem is solved. For a large-scale problem, a solution cannot be obtained within a practical time due to an increase in the number of definitions or combinations, even if the problem can be put into equations. Besides, a solution cannot sometimes be found even after a search is executed for many hours.
Furthermore, methods such as column generation, etc. are used to increase speed. However, a large-scale problem faces various limitations owing to issues such as a column generation time, a restriction on a memory capacity, etc.
A method which attracts keen interest as a means for solving such problems associated with conventional methods is a GA (Genetic Algorithm) With the GA, a problem is put into a model, and its parameters are represented by using a chromosome. When optimization is made with a GA, a chromosome is decoded and converted into parameters, which are then entered into the problem model. The problem model is evaluated, and its evaluation value is used as a fitness of the chromosome, so that an individual (chromosome) is evolved and optimization is advanced.
Issues in conventional methods are listed below.
1. Issues in a Problem Description
With IP/LP, the problem description must be represented in a matrix form, and it is difficult to reflect the details of each condition with this method.
With some problem-solving methods using column generation, the problem is represented as a set of rules, and the details of the problem are described as generation rules at the time of column generation. However, there are various issues such as how to represent the problem by rules, how to verify coverage or appropriateness of rules, how to maintain consistency of rules, etc.
2. Issues in a Search Method
Even with a GA, which has advantages that are not implemented by conventional methods, its solution-seeking capability has the following limitations if a solution space becomes extremely large.
1) A GA chromosome cannot cover an entire solution space.
2) If coding is performed to cover an entire solution space, the number of areas, as such as the one causing a constraint violation or the one that is unsuitable as a solution, significantly increases. Therefore, optimization cannot efficiently be made.
3) Solution generation with solution generation rules is desirable in some cases. However, if a solution is generated by simply using the rules, a solution-seeking method becomes inflexible, so that a solution of high quality cannot be obtained.
3. Issues in a Scheduling Time Period and Operation Regularity
An actual target to be scheduled can be a rather complicated issue, such as whether a particular operation is to be or not to be performed depending on a day. With conventional methods, it is difficult to directly handle such a target. Therefore, the conventional techniques implicitly assume that the same operation is repeated for consecutive days, and draw up a schedule covering several days. This is referred to as a daily model.
Since operations to be scheduled become increasingly irregular hereafter, a solution to a daily model, etc., becomes increasingly unsuitable to the current status.
Also, as in the case of a flight crew schedule in the United States (US), a schedule such that some operations are not performed on weekends may be considered. This is referred to as a weekly model.
Furthermore, a schedule such that all of irregular schedule targets are included, and its time period is approximately 1 to 2 months is referred to as a fully dated model. An example of directly handling this model is not known.
SUMMARY OF THE INVENTION
An object of the present invention is to implement an optimizing apparatus, an optimizing method, and a storage medium, which can automatically generate a solution to a constraint satisfying an optimization problem that cannot conventionally be solved, and has not only an extensive search space but also many constraints conditions, such as a fully dated model.
An optimizing apparatus according to the present invention comprises the following units.
A solution-seeking data presenting unit outputs solution-seeking data to a problem model, and advances optimization of the solution-seeking data by receiving an evaluation value of a solution resultant from applying the solution-seeking data to the problem model.
A solution seeking unit obtains a solution-seeking starting point of a solution to the problem model from the solution-seeking data received from the solution-seeking data presenting unit, and seeks a solution to the problem model by using at least both a local search method and a stochastic search method.
An evaluation value calculating unit calculates an evaluation value of the solution sought by the solution seeking unit, and outputs the calculated value to the solution-seeking data presenting unit.
A solution obtaining unit obtains a final solution to the problem model by controlling the solution-seeking data presenting unit, the solution seeking unit, and the evaluation value calculating unit.
With the optimizing apparatus having the above described configuration, a search starting point in a solution space (search space) is globally determined according to the solution-seeking data, and the search space is restricted. Next, a solution is searched locally or stochastically from the search starting point (solution-seeking starting point) with local search and stochastic search methods. Therefore, according to the present invention, a search method is modified so that a search space can efficiently be searched in a large-scale problem. As a result, it becomes possible to obtain a solution to a complicated constraint satisfying optimization problem that cannot conventionally be solved, and has an extremely large search space and many constraint conditions, such as a fully dated model. Additionally, a solution can be obtained by a fewer number of search times than that of a conventional apparatus, thereby making a solution seeking time shorter than that of the conventional apparatus.
The solution-seeking data presenting unit represents solution-seeking data, for example, as a chromosome, and receives an evaluation value as a fitness of the chromosome, and advances the optimiz
Matsumoto Shunji
Sato Makihiko
Teramoto Yohiko
Davis George B.
Fujitsu Limited
Staas & Halsey , LLP
LandOfFree
Optimizing apparatus, optimizing method, and storage medium does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimizing apparatus, optimizing method, and storage medium, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing apparatus, optimizing method, and storage medium will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3178031