Title:

Kind
Code:

A1

Abstract:

Starting from an initial combination state, a destination state to which a certain state is to be moved is determined from its neighboring states or previously defined transferable combination states by using an evaluation function, and an optimal combination state for minimizing or maximizing the function value of an evaluation function comprising the sum of a function to be minimized or maximized and a penalty function representing an amount of constraint violation is intended to be found by iteratively performing a search in which the certain state is successively moved to the thus determined destination state. It is determined whether there is a constraint violation in the current state. If so, the evaluation function is switched to another evaluation function for evaluating a constraint violation alone, whereas if not, the evaluation function is switched to another evaluation function which disregards the constraint violation.

Inventors:

Nakamura, Shizuka (Tokyo, JP)

Itaya, Nobuhiko (Tokyo, JP)

Itaya, Nobuhiko (Tokyo, JP)

Application Number:

10/229004

Publication Date:

07/31/2003

Filing Date:

08/28/2002

Export Citation:

Assignee:

Mitsubishi Denki Kabushiki Kaisha (Tokyo, JP)

Primary Class:

International Classes:

View Patent Images:

Related US Applications:

20070233315 | Library unit and magazine position detecting method in the library unit | October, 2007 | Ishitsuka |

20040167662 | Expansion of an automated data storage system | August, 2004 | Goodman et al. |

20080140248 | Method and System for Determining Characteristics of Lumber Using End Scanning | June, 2008 | Moore |

20050065660 | Method for repairing an oil or gas pipeline | March, 2005 | Aleksandersen et al. |

20080071603 | SYSTEM FOR AND METHOD OF INTERPOLATION FOR SUPPLY CHAIN PLANNING | March, 2008 | Denton et al. |

20090024255 | UTILITY INTERACTIVE INVERTER WITH VAR DISPATCH CAPABILITIES | January, 2009 | Penzenstadler et al. |

20090177316 | AUTOMATED PILL DISPENSING SYSTEMS CONFIGURED FOR DETECTING BOTTLES IN OUTPUT CHUTES AND RELATED METHODS OF OPERATION | July, 2009 | Schedel et al. |

20080226850 | Alternating Spacer Frame Line Control | September, 2008 | Clayton et al. |

20070262081 | Frozen confection machine | November, 2007 | Feola |

20040138772 | Automated machine component design tool | July, 2004 | Barman et al. |

20100076610 | Low cost automatic sprinkler assistant | March, 2010 | Hong |

Primary Examiner:

HIRL, JOSEPH P

Attorney, Agent or Firm:

LEYDIG VOIT & MAYER, LTD (Alexandria, VA, US)

Claims:

1. An apparatus for optimizing a combinatorial optimization problem by using a computer, in which starting from an initial combination state, a destination state to which a certain state is to be moved is determined from one of its neighboring states and previously defined transferable combination states by using an evaluation function, and an optimal combination state for minimizing or maximizing the function value of an evaluation function comprising the sum of a function to be minimized or maximized and a penalty function representing an amount of constraint violation is found by iteratively performing a search in which the certain state is successively moved to the thus determined destination state, said apparatus comprising: first processing means for switching the evaluation function to another evaluation function which evaluates a constraint violation alone thereby to find a sub-search initial evaluation function value, which is an evaluation function value for a current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remains a constraint violation in the current combination state; second processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing; third processing means for switching the evaluation function to another evaluation function which disregards the constraint violation thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there exists no constraint violation in the current combination state; and fourth processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there no longer exists a better solution, thus ending the processing.

2. The combinatorial optimization problem optimizing apparatus according to claim 1, wherein in said first processing means, the evaluation function comprises a total sum of a function to be minimized or maximized and a plurality of penalty functions each representing the value of each type of constraint violation, and the evaluation function is switched to a total sum of penalty functions corresponding to those types of constraints for which constraint violations still remain, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remain constraint violations in the current combination state; and in said second processing means, a search using the new evaluation function is started in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing.

3. An apparatus for optimizing a combinatorial optimization problem by using a computer, in which starting from an initial combination state, a destination state to which a certain state is to be moved is determined from one of its neighboring states and previously defined transferable combination states by using an evaluation function, and an optimal combination state for minimizing or maximizing the function value of an evaluation function comprising the sum of a function to be minimized or maximized and a penalty function representing an amount of constraint violation is found by iteratively performing a search in which the certain state is successively moved to the thus determined destination state, said apparatus comprising: first processing means for switching the evaluation function to a new evaluation function in which the weight of component other than the penalty function is reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for a current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remains a constraint violation in the current combination state; second processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing; third processing means for switching the evaluation function to a new evaluation function in which the weight of the penalty function is reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there exists no constraint violation in the current combination state; and fourth processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there no longer exists a better solution, thus ending the processing.

4. The combinatorial optimization problem optimizing apparatus according to claim 3, wherein in said first processing means, said evaluation function comprises a total sum of a function to be minimized or maximized and a plurality of penalty functions each representing the value of each type of constraint violation, and the evaluation function is switched to a new evaluation function in which the weights of components other than penalty functions corresponding to those types of constraints for which constraint violations still remain are reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remain constraint violations in the current combination state; and in said second processing means, a search using the new evaluation function is started in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing.

Description:

[0001] 1. Field of the Invention

[0002] The present invention relates to an apparatus for optimizing combinatorial optimization problems using a computer.

[0003] 2. Description of the Prior Art

[0004] As a conventional solution finding method for combinatorial optimization problems, for example, there has been known the one according to a simulated annealing method published in an article entitled “New Power System Planning Technique” of the Institute of Electrical Engineers technical report No.647 (page 51).

[0005] This simulated annealing method (Simulated Annealing: SA) proposed by S. Kirkpatrick in the year of 1983 is a method of simulating the annealing process in a physical system. Annealing is a process where a solid material is heated to melt, and then gradually cooled to generate a crystal. When a solid material is heated into a molten state by supplying energy thereto to raise the temperature thereof, particles of the material come to take a random arrangement or configuration. By gradually lowering the temperature from that state, the molten material becomes a ground state of minimum internal energy, and the particles at this time becomes a regular configuration, i.e., a crystal. The SA method makes such a behavior of particles correspond to a decision variable of a combinatorial optimization problem, so that the annealing process can be simulated on a computer.

[0006] In a physical system consisting of a lot of particles, the particles, which are in an equilibrium state at a temperature of T, follows a Boltzmann distribution as shown by the following expression.

_{B}

[0007] Here, E is the energy of the system, and K_{B }

[0008] To simulate the behavior of particles in such a physical system on a computer, N. Metropolis proposed the following procedure. When the current configuration of particles is given, the particles of interest are chosen at random, and a random, minute perturbation is given to the configuration. If a change ΔE in the energy at that time is negative, the energy of the perturbed configuration is smaller than that before the perturbation, and hence this configuration is adopted. If the change ΔE is positive, the configuration after the perturbation is adopted at a probability according to the Boltzmann factor. If the configuration is given by such a perturbation a sufficient number of times, the system becomes equilibrium, and the probability distribution of the energy states of the system gradually approaches the Boltzmann distribution. This rule adopting a new configuration in the above-mentioned manner is called the Metropolis criterion. The procedure of finding the equilibrium of a physical system using the Metropolis criterion is called the Metropolis algorithm.

[0009] In order to apply the Metropolis algorithm as a solution finding technique for a combinatorial optimization problem, a configuration of particles in a physical system is made to correspond to a variable x in the combinatorial optimization problem, and the energy E of the physical system is made to correspond to an objective function f(x) in the combinatorial optimization problem. Also, the temperature factor K_{B}_{B}

[0010] In order to find an optimal solution or a sub-optimal solution through the application of the SA method, it is necessary to lower the temperature slowly while spending a long time. The way to lower the temperature is called the cooling schedule. The accuracy of the solution obtained and the efficiency of computation required depend greatly on what cooling schedule is used. S. Geman et al showed that an optimal solution is obtained at a probability of “1” if the cooling is carried out on the condition that an infinite number of perturbations are given to a configuration at each temperature and that the temperature may meet the requirement of (T>c/log k), where k is the number of times of iterations with respect to the temperature, and c is a constant which does not depend on the temperature. However, such a cooling schedule is not feasible in terms of computing time. Therefore, a fixed rate cooling schedule method is often used in which in actuality, the number of perturbations is limited to a finite value at each temperature, and the temperature is set such that T^{k+1}^{k}

[0011]

[0012] In

[0013] In the processing block

[0014] According to the above-described method, a transition or move to a worse condition is permitted stochastically, so even if x reaches a local optimal solution, transition or moving is able to be continued without being trapped at a local optimal solution. As a result, it becomes possible to find a better solution.

[0015] Thus, the greatest technical difficulty in solving combinatorial optimization problems by using search methods is how to escape from local optimal solutions and to continue searching. A variety of methods have hitherto been proposed to solve such difficulty, and these are roughly classified as follows.

[0016] 1) A transition or move to a worse condition is permitted at a certain probability (the above-mentioned method).

[0017] 2) A transition or move to the best condition among permitted transitions or moves is iterated (in this case, there being generated a transition or move in which the value of an evaluation function deteriorates or worsens in terms of a local optimal solution), and for those portions in which there has been made a change in the content of a combination, a reverse change is prohibited for a certain period of time, thereby suppressing a return to the once passed local optimal solution.

[0018] 3) A transition or move to the best condition among permitted transitions or moves is iterated (in this case, there being generated a transition or move in which the value of an evaluation function deteriorates or worsens in terms of a local optimal solution), and the value of the evaluation function for each passed local optimal solution is worsened so that subsequent evaluations thereof may be made through the use of the thus worsened evaluation function value, thereby suppressing a return to the once passed local optimal solution.

[0019] The present invention is intended to provide an apparatus for optimizing combinatorial optimization problems by using a computer, in which a novel and efficient method is adopted to cope with how to escape from local optimal solutions to continue searching, which is the greatest technical difficulty in solving the combinatorial optimization problems by using search methods.

[0020] According to one aspect, the present invention resides in an apparatus for optimizing combinatorial optimization problems by using a computer, in which starting from an initial combination state, a destination state to which a certain state is to be moved is determined from its neighboring states or previously defined transferable combination states by using an evaluation function, and an optimal combination state for minimizing or maximizing the function value of an evaluation function comprising the sum of a function to be minimized or maximized and a penalty function representing an amount of constraint violation is found by iteratively performing a search in which the certain state is successively moved to the thus determined destination state. When there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remains a constraint violation in the current combination state, a first processing part switches the evaluation function to another evaluation function which evaluates a constraint violation alone thereby to find a sub-search initial evaluation function value, which is an evaluation function value for a current combination state. A second processing part starts a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing. When there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there exists no constraint violation in the current combination state, a third processing part switches the evaluation function to another evaluation function which disregards the constraint violation thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state. A fourth processing part starts a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there no longer exists a better solution, thus ending the processing.

[0021] When a local optimal solution is reached in the process of searching, the evaluation function is switched to another evaluation function. Thus, the value of a penalty function representing the amount of constraint violation can be improved though the value of a function constituting the evaluation function to be minimized or maximized may be increased or decreased, or the value of a function to be minimized or maximized, which constitutes the evaluation function, can be decreased or increased though a constraint violation may take place. Accordingly, it becomes possible for a state to move to its neighboring state, which would be difficult in a search using an original or intrinsic evaluation function, thereby enabling an efficient escape from the neighborhood of a local optimal solution. As a result, the efficiency of the entire search can be improved, thus making it possible to solve combinatorial optimization problems in an efficient manner.

[0022] Preferably, in the first processing part, the evaluation function comprises a total sum of a function to be minimized or maximized and a plurality of penalty functions each representing the value of each type of constraint violation, and the evaluation function is switched to a total sum of penalty functions corresponding to those types of constraints for which constraint violations still remain, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remain constraint violations in the current combination state.

[0023] According to another aspect, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remains a constraint violation in the current combination state, a first processing part switches the evaluation function to a new evaluation function in which the weights of components other than the penalty function are reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for a current combination state.

[0024] Preferably, in the first processing part, the evaluation function comprises a total sum of a function to be minimized or maximized and a plurality of penalty functions each representing the value of each type of constraint violation, and the evaluation function is switched to a new evaluation function in which the weights of components other than penalty functions corresponding to those types of constraints for which constraint violations still remain are reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remain constraint violations in the current combination state.

[0025] The above and other objects, features and advantages of the present invention will become more readily apparent to those skilled in the art from the following detailed description of preferred embodiments of the present invention taken in conjunction with the accompanying drawings.

[0026]

[0027]

[0028]

[0029]

[0030]

[0031]

[0032]

[0033] Hereinafter, preferred embodiments of the present invention will be described in detail while referring to the accompanying drawings.

[0034] Embodiment 1.

[0035]

[0036]

[0037] A variety of evaluation functions (see A in

[0038] Subsequently, in a processing block or step

[0039] In the processing block

[0040] In a processing block or step

[0041] In the processing block

[0042] In the processing block

[0043] Next, the operational effect of the above-described solution finding technique for combinatorial optimization problems according to the present invention will be explained below while referring to

[0044] Now, it is assumed that the initial state of the system to be optimized is in a state shown by a thick circle. The value of the evaluation function in this state (i.e., the sum of the numerical value on the lower row to be minimized and the numerical value on the upper row representing a penalty) is five, and hence this is in a situation including no constraint violation (i.e., the penalty value being 0). In addition, this state is a local optimal solution which has no better state among its neighboring states (i.e., there being no neighboring state having its evaluation function value less than

[0045] In this state, a conventional search (i.e., the method described in

[0046] In contrast to this, however, according to the present invention, the initial or central state is a local optimal solution without any constraint violation. Therefore, a sub-search is made while disregarding constraints (penalty values), and advances to its right-side state. This state having a sub-search evaluation function value of 3 is better than the initial state having a sub-search initial evaluation function value of 5. Accordingly, the search is restored to the conventional search, and the state moves up to its upper state having an evaluation function value of 7. (In this case, the state is unable to move to the left because its left-side evaluation function value, which would have an evaluation function value of 5 according to the conventional search, was increased to 105 for instance.) Subsequently, the state moves to its right-side state having an evaluation function value of 0. Thus, according to the present invention, even if there is a conflict between a penalty and an evaluation function value to be minimized, the search is able to move in a desirable direction.

[0047] In the above description, there has been explained the operational effect of the present invention in the case where a search is trapped at a local optimal solution having no constraint violation. In the following, however, reference will be made to the effect of the present invention in the case where a search is trapped at a local optimal solution including a constraint violation.

[0048] The moving of the conventional search is decided solely by the sum of an evaluation function value to be minimized and a penalty value, and hence it is not altered by the above change in reading.

[0049] Since the initial or central state is a local optimal solution having a constraint violation according to the present invention, a sub-search is started while disregarding an evaluation function value to be minimized (i.e., numerical value on the upper row), and it advances to its right state. This state having a sub-search evaluation function value of 3 is better than the initial or central state having a sub-search initial evaluation function value of 5. Accordingly, the search is restored to the conventional search, and the state moves to its upper state having an evaluation function value of 7. (In this case, the state is unable to be returned to its left-side state because the evaluation function value of the local optimal solution was sufficiently increased.) Subsequently, the state moves to its right-side state having an evaluation function value of 0. In this manner, according to the present invention, even if there is a conflict between a penalty and a evaluation function value to be minimized, the search is able to move in a desirable direction.

[0050] Embodiment 2.

[0051]

[0052] In this second embodiment, the penalty is classified or subdivided into a plurality of kinds of penalties. In case where one kind of penalty takes place, the operations or moves of the search become the same as those described in the first embodiment. On the other hand, in case where there take place a plurality of kinds of penalties, assuming that the sum of the penalties are taken as one total penalty, the same explanation as made in the first embodiment will hold true for this case.

[0053] In the present invention, even when there is intrinsically a relation of conflict between an evaluation function to be minimized or maximized and a penalty, it is possible to find a good solution more efficiently by disregarding one of them under a certain condition. In addition, according to this embodiment, in case where there is a relation of conflict between subdivided penalties, it is possible to find a good solution more efficiently by disregarding one or some of the penalties under a certain condition.

[0054] Embodiment 3.

[0055]

[0056] This third embodiment is intended to achieve the same effect as that obtained by “disregarding” in the first embodiment, by “reducing weight”, so that a good solution can be found more efficiently by performing weighting through the use of the nature or characteristics of a problem to be solved.

[0057] Embodiment 4.

[0058]

[0059] In this fourth embodiment, too, it is intended to achieve the same effect as that obtained by “disregarding” in the second embodiment, by “reducing weights”, so that a good solution can be found more efficiently by performing weighting through the use of the nature or characteristics of a problem to be solved.

[0060] As described in the foregoing, according to a first aspect of the present invention, there is provided an apparatus for optimizing a combinatorial optimization problem by using a computer, in which starting from an initial combination state, a destination state to which a certain state is to be moved is determined from its neighboring states or previously defined transferable combination states by using an evaluation function, and an optimal combination state for minimizing or maximizing the function value of an evaluation function comprising the sum of a function to be minimized or maximized and a penalty function representing an amount of constraint violation is found by iteratively performing a search in which the certain state is successively moved to the thus determined destination state. The apparatus includes: first processing means for switching the evaluation function to another evaluation function which evaluates a constraint violation alone thereby to find a sub-search initial evaluation function value, which is an evaluation function value for a current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remains a constraint violation in the current combination state; second processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing; third processing means for switching the evaluation function to another evaluation function which disregards the constraint violation thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there exists no constraint violation in the current combination state; and fourth processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there no longer exists a better solution, thus ending the processing.

[0061] In one preferred form of the first aspect of the present invention, in the first processing means, the evaluation function comprises a total sum of a function to be minimized or maximized and a plurality of penalty functions each representing the value of each type of constraint violation, and the evaluation function is switched to a total sum of penalty functions corresponding to those types of constraints for which constraint violations still remain, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remain constraint violations in the current combination state. In the second processing means, a search using the new evaluation function is started in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing.

[0062] According to a second aspect of the present invention, there is provided an apparatus for optimizing a combinatorial optimization problem by using a computer, in which starting from an initial combination state, a destination state to which a certain state is to be moved is determined from its neighboring states or previously defined transferable combination states by using an evaluation function, and an optimal combination state for minimizing or maximizing the function value of an evaluation function comprising the sum of a function to be minimized or maximized and a penalty function representing an amount of constraint violation is found by iteratively performing a search in which the certain state is successively moved to the thus determined destination state. The apparatus includes: first processing means for switching the evaluation function to a new evaluation function in which the weights of components other than the penalty function are reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for a current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remains a constraint violation in the current combination state; second processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing; third processing means for switching the evaluation function to a new evaluation function in which the weight of the penalty function is reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there exists no constraint violation in the current combination state; and fourth processing means for starting a search using the new evaluation function in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there no longer exists a better solution, thus ending the processing.

[0063] In one preferred form of the second aspect of the present invention, in the first processing means, the evaluation function comprises a total sum of a function to be minimized or maximized and a plurality of penalty functions each representing the value of each type of constraint violation, and the evaluation function is switched to a new evaluation function in which the weights of components other than penalty functions corresponding to those types of constraints for which constraint violations still remain are reduced, thereby to find a sub-search initial evaluation function value, which is an evaluation function value for the current combination state, when there exists no neighboring state having an evaluation function value better than that of the current combination state, and when there still remain constraint violations in the current combination state. In the second processing means, a search using the new evaluation function is started in such a manner that if a combination state having an evaluation function value better than the sub-search initial evaluation function value is reached within a predetermined number of searches, the search is continued while restoring the evaluation function to the original evaluation function, whereas if a combination state having an evaluation function value better than the sub-search initial evaluation function value is unable to be reached within the predetermined number of searches, it is determined that there exists no feasible solution, thereby ending the processing.

[0064] According to the various aspects of the present invention as referred to above, there are achieved the following advantages. When a local optimal solution is reached in the process of searching, the evaluation function is switched to another evaluation function, so that the value of a penalty function representing the amount of constraint violation can be improved though the value of a function constituting the evaluation function to be minimized or maximized may be increased or decreased, or the value of a function to be minimized or maximized, which constitutes the evaluation function, can be decreased or increased though a constraint violation may take place. Accordingly, it becomes possible for a state to move to its neighboring state, which would be difficult in a search using an original or intrinsic evaluation function, thereby enabling an efficient escape from the neighborhood of a local optimal solution. As a result, the efficiency of the entire search can be improved, thus making it possible to solve combinatorial optimization problems in an efficient manner.

[0065] While the invention has been described in terms of preferred embodiments, those skilled in the art will recognize that the invention can be practiced with modifications within the spirit and scope of the appended claims.