Optimizing apparatus, optimizing method, and storage medium

• US 6,651,046 B1
• Filed: 09/12/2000
• Issued: 11/18/2003
• Est. Priority Date: 09/17/1999
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Matsumoto, Shunji, Teramoto, Yohiko, Sato, Makihiko
• Primary Examiner(s): Davis, George B.
• Application Number:
  US09/660,582
• Time in Patent Office: 1,162 Days
• Field of Search: 706/13
• US Class Current: 706/13
• CPC Class Codes: G06Q 99/00 Subject matter not provided for in other groups of this subclass

Abstract

A chromosome is decoded by a decoding unit, and converted into parameters of a problem model calculation unit. In the problem model calculation unit, a controller executes a local search method unit, a GA search unit, or a stochastic search unit while suitably selecting any of them, so that a solution is generated. If a constraint violation is detected by a constraint violation determination unit during a solution generation process, an added part (a part which causes a constraint violation) is removed from a current solution by the constraint violation processing unit, and the solution generation process is continued.

Claims

1. An optimizing apparatus, comprising:

a solution-seeking data presenting unit outputting solution-seeking data represented by a chromosome to a problem model, advancing optimization of the solution-seeking data by receiving, as a fitness of the chromosome, an evaluation value of a solution obtained by applying the solution-seeking data to the problem model, and evolving the chromosome with a genetic algorithm;

a solution seeking unit obtaining a solution-seeking starting point of a solution to the problem model from the solution-seeking data received from said solution-seeking data presenting unit by using a first probability table storing information for stochastically determining the solution-seeking starting point, when decoding a first gene of the chromosome, and seeking a solution to the problem model by using both a local search method and a stochastic search method;

an evaluation value calculating unit calculating an evaluation value of the solution obtained by said solution seeking unit, and outputting the evaluation value to said solution-seeking data presenting unit; and

a solution obtaining unit obtaining a final solution to the problem model by controlling said solution-seeking data presenting unit, said solution seeking unit, and said evaluation value calculating unit.

2. The optimizing apparatus according to claim 1, wherein

said solution seeking unit comprises a second probability table storing information for stochastically determining a next search point, and advances solution seeking with a stochastic search method by decoding a second gene of the chromosome while using the second probability table.

3. The optimizing apparatus according to claim 1, wherein:

the problem model is a constraint satisfying optimization problem model seeking a solution to a second schedule over a plurality of days, which is obtained by connecting a plurality of first schedules, each composed of a sequence of operations in certain units for each day; and

the problem-seeking starting point is an operation that is initially started at the beginning of the second schedule.

4. The optimizing apparatus according to claim 3, wherein:

the operations are aircraft flight operations, the first schedule is a crew pattern on one day, and the second schedule is a crew pattern over a plurality of days;

the local search method is used to search for a connecting flight that can be operated on an operation day except for an irregular flight day;

the stochastic search method is used to search for a flight to be connected next;

said solution seeking unit generates the crew pattern by partitioning a ship line into segments based on the solution-seeking data, and by connecting the partitioned segments;

partitioning of the segments is made by using a segmentation probability table which is arranged for each ship line and stores a segmentation method of each ship line; and

a connection of the partitioned segments is made by a stochastic search using a segment connection probability table which is arranged for each flight and stores connection probability information of a flight to be connected to each flight.

5. The optimizing apparatus according to claim 4, wherein:

said solution-seeking data presenting unit obtains the solution-seeking data in a form of a chromosome by using a genetic algorithm;

said solution seeking unit generates a crew pattern by partitioning each ship line into segments with a first gene of the chromosome, and the segmentation probability table which is arranged for each ship line and stores information for stochastically determining a segmentation method of each ship line, and by connecting the partitioned segments, and at the same time, said solution seeking unit stochastically searches for a segment to be connected next with a second gene of the chromosome, and the segment connection probability table which is arranged for each flight and stores a connection probability value of a flight to be connected to each flight.

6. An optimizing method seeking a final solution to a problem model, comprising:

outputting solution-seeking data represented by a chromosome to a problem model;

advancing optimization of the solution-seeking data by receiving, as a fitness of the chromosome, an evaluation value of a solution obtained by applying the solution-seeking data to the problem model;

evolving the chromosome with a genetic algorithm;

obtaining a solution-seeking starting point of a solution to the problem model from the solution-seeking data by using a first probability table storing information for stochastically determining the solution-seeking starting point, when decoding a first gene of the chromosome, and seeking a solution to the problem model by using at least both of a local search method and a stochastic search method; and

calculating an evaluation value of the obtained solution, and using the evaluation value to advance optimization of the solution-seeking data.

7. The optimizing method according to claim 6, further comprising

advancing solution seeking with a stochastic search method by decoding a second gene of the chromosome while using a second probability table storing information for stochastically determining a next search point.

8. The optimizing method according to claim 6, wherein

the problem model is a constraint satisfying optimization problem model seeking a solution to a second schedule over a plurality of days, which is obtained by connecting a plurality of first schedules, each composed of a sequence of operations in certain units for each day;

and

the problem-seeking starting point is an operation that is initially started at the beginning of the second schedule.

9. The optimizing method according to claim 8, wherein:

the operations are aircraft flight operations, the first schedule is a crew pattern on one day, and the second schedule is a crew pattern over a plurality of days;

the local search method is used to search for a connecting flight that can be operated on an operation day except for an irregular flight day;

the stochastic search method is used to search for a flight to be connected next;

the crew pattern is generated by partitioning a ship line into segments based on the solution-seeking data, and by connecting the partitioned segments;

partitioning of the segments is made by using a segmentation probability table which is arranged for each ship line and stores a segmentation method of each ship line; and

a connection of the partitioned segments is made by a stochastic search using a segment connection probability table which is arranged for each flight and stores connection probability information of a flight to be connected to each flight.

10. The optimizing method according to claim 9, further comprising:

obtaining the solution-seeking data in a form of a chromosome by using a genetic algorithm;

generating a crew pattern by partitioning each ship line into segments with a first gene of the chromosome, and the segmentation probability table which is arranged for each ship line and stores information for stochastically determining a segmentation method of each ship line, and by connecting the partitioned segments, and at the same time, stochastically searching for a segment to be connected next with a second gene of the chromosome, and the segment connection probability table which is arranged for each flight and stores a connection probability value of a flight to be connected to each flight.

11. A computer-readable storage medium on which is recorded a program for causing a computer to execute a process, said process comprising:

outputting solution-seeking data represented by a chromosome to a problem model;

advancing optimization of the solution-seeking data by receiving, as a fitness of the chromosome, an evaluation value of a solution obtained by applying the solution-seeking data to the problem model;

evolving the chromosome with a genetic algorithm;

obtaining a solution-seeking starting point of a solution to the problem model from the solution-seeking data by using a first probability table storing information for stochastically determining the solution-seeking starting point, when decoding a first gene of the chromosome, and seeking a solution to the problem model by using at least both of a local search method and a stochastic search method; and

calculating an evaluation value of the obtained solution, and using the evaluation value to advance optimization of the solution-seeking data.

12. The storage medium according to claim 11, wherein said process further comprising:

advancing solution seeking with a stochastic search method by decoding a second gene of the chromosome while using a second probability table storing information for stochastically determining a next search point.

13. The storage medium according to claim 11, wherein:

the problem model is a constraint satisfying optimization problem model seeking a solution to a second schedule over a plurality of days, which is obtained by connecting a plurality of first schedules, each composed of a sequence of operations in certain units for each day; and

the problem-seeking starting point is an operation that is initially started at the beginning of the second schedule.

14. The storage medium according to claim 13, wherein:

the operations are aircraft flight operations, the first schedule is a crew pattern on one day, and the second schedule is a crew pattern over a plurality of days;

the local search method is used to search for a connecting flight that can be operated on an operation day except for an irregular flight day;

the stochastic search method is used to search for a flight to be connected next;

the crew pattern is generated by partitioning a ship line into segments based on the solution-seeking data, and by connecting the partitioned segments;

partitioning of the segments is made by using a segmentation probability table which is arranged for each ship line and stores a segmentation method of each ship line; and

a connection of the partitioned segments is made by a stochastic search using a segment connection probability table which is arranged for each flight and stores connection probability information of a flight to be connected to each flight.

15. The storage medium according to claim 14, wherein said process further comprising:

obtaining the solution-seeking data in a form of a chromosome by using a genetic algorithm;

generating a crew pattern by partitioning each ship line into segments with a first gene of the chromosome, and the segmentation probability table which is arranged for each ship line and stores information for stochastically determining a segmentation method of each ship line, and by connecting the partitioned segments, and at the same time, stochastically searching for a segment to be connected next with a second gene of the chromosome, and the segment connection probability table which is arranged for each flight and stores a connection probability value of a flight to be connected to each flight.