Method and apparatus for automatic configuration of meta-heuristic algorithms in a problem solving environment

• US 9,015,145 B2
• Filed: 12/22/2006
• Issued: 04/21/2015
• Est. Priority Date: 12/22/2006
• Status: Active Grant

• Current Assignee: Nanyang Technological University, Singapore Technologies Dynamics PTD Limited
• Original Assignee: Nanyang Technological University, Singapore Technologies Dynamics PTD Limited
• Inventors: Lim, Meng Hiot, Xu, Yi Liang, Ong, Yew Soon
• Primary Examiner(s): Btit, Jacob F
• Assistant Examiner(s): WILLIS, AMANDA LYNN
• Application Number:
  US12/519,953
• Publication Number:
  US 20100106714A1
• Time in Patent Office: 3,042 Days
• Field of Search: 707/718, 707/797, 707/829, 707/E17.017, 707/856, 707/999.002, 707/999.102, 707/748, 707/712, 707/736, 706 12- 13, 706/21, 706/47, 706/11, 706/15, 706/20, 706/25, 706/46, 706/48, 706/52
• US Class Current: 707/712
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06N 3/12 using genetic models
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A method and system are presented for configuring a search algorithm for solving a combinatorial optimization problem. The search algorithm has a number of procedural components. Each procedural component is configured using a respective data structure. The data structure has a tree structure, including traversal split nodes, each of which represents a choice to be made when configuring the procedural component of the search algorithm. Configuring the procedural component corresponds to traversing the tree structure, and the traversal is performed automatically. At each of the traversal split nodes, the choice of which direction to take through the tree structure is made randomly, using a respective probabilistic function. Thus, a population of candidate algorithms is generated. These are evaluated, and the probabilistic functions modified.

Claims

1. A method of obtaining a set of probabilistic functions for configuring a search algorithm including one or more procedural components, said method comprising:

(a) providing for each procedural component a corresponding data structure representing options for configuring the procedural component, each data structure comprising a plurality of nodes associated together in a tree structure, a plurality of said nodes being traversal split nodes representing respective choices which are to be made to configure the corresponding procedural component, the traversal split nodes being associated with one of the probabilistic functions;

(b) selecting current probabilistic functions;

(c) producing one or more candidate algorithms, each candidate algorithm being produced by traversing the tree structures by performing a traversal algorithm in which a plurality of said nodes are labeled successively as a current node, and, upon the current node being a traversal split node, performing the associated current probabilistic function to make the choice represented by the current node, wherein the probabilistic function associated with each traversal split node is defined by a respective set of one or more numerical trace values, said set of one or more numerical trace values being associated with a plurality of branches representing routing options through said tree structure, wherein the set of numerical trace values guides the decision of choosing one branch of the plurality of branches at the traversal split node;

(d) evaluating the candidate algorithms by forming for each candidate algorithm a respective quality index; and

(e) obtaining modified probabilistic functions based on the quality indices and returning to step (c) until a termination criterion is met, wherein the modified probabilistic functions are obtained by adjusting a relative weight of the numerical trace values associated with the plurality of branches at the traversal split node, based on numeric trace values of at least one of the traversal split nodes chosen by one of the candidate algorithms and its quality index in the current iteration, to modify the probability of the branch being chosen in the next iteration by returning to step (c) to produce candidate algorithms using the adjusted numerical trace values;

wherein said search algorithm is a search algorithm for solving a combinatorial-optimization problem and said quality index is representative of the quality of performance of the combinatorial-optimization problem by the corresponding candidate algorithm.

2. The method according to claim 1 wherein at least some of said traversal split nodes are variation nodes at which the associated probabilistic function selects one of a plurality of routing options for traversing the corresponding tree structure.

3. The method according to claim 1 wherein at least some of said traversal split nodes are nodes at which the associated probabilistic function selects one of a plurality of options for setting a numerical parameter.

4. The method according to claim 1 wherein said step (d) includes running the candidate algorithms to solve a set of one or more test problems, and evaluating the quality of one or more solutions the candidate algorithms produce.

5. The method according to claim 4 wherein the quality of said one or more solutions is evaluated using a user-defined quality function.

6. A method of configuring a search algorithm, the method comprising performing the method according to claim 1 to generate a set of probabilistic functions, and then selecting at least one of the evaluated candidate algorithms to be used as a search algorithm to solve an actual optimization problem.

7. The method according to claim 6 wherein said evaluating step (d) employs a test set of problems of which the actual optimization problem is statistically typical.

8. The method according to claim 6 further comprising generating source code implementing the configured search algorithm.

9. A method of configuring a search algorithm for solving a combinatorial-optimization problem, the search algorithm including one or more procedural components, said method comprising:

(a) providing for each procedural component a corresponding data structure representing options for configuring the procedural component, each data structure comprising a plurality of nodes associated together in a tree structure, a plurality of said nodes being traversal split nodes representing respective choices which are to be made to configure the corresponding procedural component, the traversal split nodes being associated with one of a set of probabilistic functions;

(b) selecting current probabilistic functions;

(c) producing one or more candidate algorithms, each candidate algorithm being produced by traversing the tree structure by performing a traversal algorithm in which a plurality of said nodes are labeled successively as a current node, and, upon the current node being a traversal split node, performing the associated current probabilistic function to make the choice represented by the current node, wherein the probabilistic function associated with each traversal split node is defined by a respective set of one or more numerical trace values, said set of one or more numerical trace values being associated with a plurality of branches representing routing options through said tree structure, wherein the set of numerical trace values guides the decision of choosing one branch of the plurality of branches at the traversal split node;

(d) evaluating the candidate algorithms by forming for each candidate algorithm a respective quality index representative of the quality of performance of the combinatorial-optimization problem by the corresponding candidate algorithm;

(e) obtaining modified probabilistic functions based on the quality indices and returning to step (c) until a termination criterion is met, wherein the modified probabilistic functions are obtained by adjusting a relative weight of the numerical trace values associated with the plurality of branches at the traversal split node, based on numeric trace values of at least one of the traversal split nodes chosen by one of the candidate algorithms and its quality index in the current iteration, to modify the probability of the branch being chosen in the next iteration by returning to step (c) to produce candidate algorithms using the adjusted numerical trace values; and

(f) upon the termination criterion being met, configuring a search algorithm for solving the combinatorial-optimization problem based on one of the said candidate algorithms.

10. The method according to claim 9 further comprising generating source code implementing the configured search algorithm.

11. A computer system arranged to configure a search algorithm for solving a combinatorial-optimization problem, the search algorithm including one or more procedural components, the computer system comprising:

a processor arranged to employ for each procedural component a corresponding data structure representing options for configuring the procedural component, each data structure comprising a plurality of nodes associated together in a tree structure, a plurality of said nodes being traversal split nodes representing respective choices which are to be made to configure the corresponding procedural component, the traversal split nodes being associated with respective ones of a set of probabilistic functions, said processor being arranged to perform a set of steps comprising;

(a) selecting current probabilistic functions;

(b) producing one or more candidate search algorithms, each candidate search algorithm being produced by traversing the tree structure by performing a traversal algorithm in which a plurality of said nodes are labeled successively as a current node, and, upon the current node being a traversal split node, performing the associated current probabilistic function to make the choice represented by the current node, wherein the probabilistic function associated with each traversal split node is defined by a respective set of one or more numerical trace values, said set of one or more numerical trace values being associated with a plurality of branches representing routing options through said tree structure, wherein the set of numerical trace values guides the decision of choosing one branch of the plurality of branches at the traversal split node,

(c) evaluating the candidate search algorithms by forming for each candidate algorithm a respective quality index representative of the quality of performance of the combinatorial-optimization problem by the corresponding candidate algorithm;

(d) obtaining modified probabilistic functions based on the quality indices, wherein the modified probabilistic functions are obtained by adjusting a relative weight of the numerical trace values associated with the plurality of branches at the traversal split node, based on numeric trace values of at least one of the traversal split nodes chosen by one of the candidate algorithms and its quality index in the current iteration, to modify the probability of the branch being chosen in the next iteration by returning to step (b) to produce candidate algorithms using the adjusted numerical trace values; and

(e) returning to step (b) until a termination criterion is met.

12. A non-transitory computer-readable medium containing computer program instructions operative, upon being read by a computer system, to cause the computer system to configure a search algorithm for solving a combinatorial-optimization problem, the search algorithm including one or more procedural components, said program instructions causing a processor of the computer system to employ for each procedural component a corresponding data structure representing options for configuring the procedural component, each data structure comprising a plurality of nodes associated together in a tree structure, a plurality of said nodes being traversal split nodes representing respective choices which are to be made to configure the corresponding procedural component, the traversal split nodes being associated with respective ones of a set of probabilistic functions, said program instructions causing said processor to perform a set of steps comprising:

(a) selecting current probabilistic functions;

(b) producing one or more candidate search algorithms, each candidate search algorithm being produced by traversing the tree structure by performing a traversal algorithm in which a plurality of said nodes are labeled successively as a current node, and, upon the current node being a traversal split node, performing the associated current probabilistic function to make the choice represented by the current node, wherein the probabilistic function associated with each traversal split node is defined by a respective set of one or more numerical trace values, said set of one or more numerical trace values being associated with a plurality of branches representing routing options through said tree structure, wherein the set of numerical trace values guides the decision of choosing one branch of the plurality of branches at the traversal split node,

(c) evaluating the candidate search algorithms by forming for each candidate algorithm a respective quality index representative of the quality of performance of the combinatorial-optimization problem by the corresponding candidate algorithm, and

(d) obtaining modified probabilistic functions based on the quality indices and returning to step (b) until a termination criterion is met, wherein the modified probabilistic functions are obtained by adjusting a relative weight of the numerical trace values associated with the plurality of branches at the traversal split node, based on numeric trace values of at least one of the traversal split nodes chosen by one of the candidate algorithms and its quality index in the current iteration, to modify the probability of the branch being chosen in the next iteration by returning to step (b) to produce candidate algorithms using the adjusted numerical trace values.

13. A computer system arranged to obtain a set of probabilistic functions for configuring a search algorithm for solving a combinatorial-optimization problem, the search algorithm including one or more procedural components, the computer system having a processor arranged to employ for each procedural component a corresponding data structure representing options for configuring the procedural component, each data structure comprising a plurality of nodes associated together in a tree structure, a plurality of said nodes being traversal split nodes representing respective choices which are to be made to configure the corresponding procedural component, the traversal split nodes being associated with respective ones of the probabilistic functions, said processor being arranged to perform a set of steps comprising:

(a) selecting current probabilistic functions;

(b) producing one or more candidate algorithms, each candidate algorithm being produced by traversing the tree structures by performing a traversal algorithm in which a plurality of said nodes are labeled successively as a current node, and, upon the current node being a traversal split node, performing the associated current probabilistic function to make the choice represented by the current node, wherein the probabilistic function associated with each traversal split node is defined by a respective set of one or more numerical trace values, said set of one or more numerical trace values being associated with a plurality of branches representing routing options through said tree structure, wherein the set of numerical trace values guides the decision of choosing one branch of the plurality of branches at the traversal split node;

(c) evaluating the candidate algorithms by forming for each candidate algorithm a respective quality index representative of the quality of performance of the combinatorial-optimization problem by the corresponding candidate algorithm; and

(d) obtaining modified probabilistic functions based on the quality indices, wherein the modified probabilistic functions are obtained by adjusting a relative weight of the numerical trace values associated with the plurality of branches at the traversal split node, based on numeric trace values of at least one of the traversal split nodes chosen by one of the candidate algorithms and its quality index in the current iteration, to modify the probability of the branch being chosen in the next iteration by returning to step (b) to produce candidate algorithms using the adjusted numerical trace values, and

(e) returning to step (b) until a termination criterion is met.

14. A non-transitory computer-readable medium containing computer program instructions operative, upon being read by a computer system, to cause the computer system to obtain a set of probabilistic functions for configuring a search algorithm for solving a combinatorial-optimization problem, the search algorithm including one or more procedural components, said program instructions causing a processor of the computer system to employ for each procedural component a corresponding data structure representing options for configuring the procedural component, each data structure comprising a plurality of nodes associated together in a tree structure, a plurality of said nodes being traversal split nodes representing respective choices which are to be made to configure the corresponding procedural component, the traversal split nodes being associated with respective ones of the probabilistic functions, said program instructions causing said processor to perform a set of steps comprising:

(a) selecting current probabilistic functions;

(b) producing one or more candidate algorithms, each candidate algorithm being produced by traversing the tree structures by performing a traversal algorithm in which a plurality of said nodes are labeled successively as a current node, and, upon the current node being a traversal split node, performing the associated current probabilistic function to make the choice represented by the current node, wherein the probabilistic function associated with each traversal split node is defined by a respective set of one or more numerical trace values, said set of one or more numerical trace values being associated with a plurality of branches representing routing options through said tree structure, wherein the set of numerical trace values guides the decision of choosing one branch of the plurality of branches at the traversal split node;

(c) evaluating the candidate algorithms by forming for each candidate algorithm a respective quality index representative of the quality of performance of the combinatorial-optimization problem by the corresponding candidate algorithm;

(d) obtaining modified probabilistic functions based on the quality indices, wherein the modified probabilistic functions are obtained by adjusting a relative weight of the numerical trace values associated with the plurality of branches at the traversal split node, based on numeric trace values of at least one of the traversal split nodes chosen by one of the candidate algorithms and its quality index in the current iteration, to modify the probability of the branch being chosen in the next iteration by returning to step (b) to produce candidate algorithms using the adjusted numerical trace values, and

(e) returning to step (b) until a termination criterion is met.