METHOD AND APPARATUS FOR AUTOMATIC CONFIGURATION OF META-HEURISTIC ALGORITHMS IN A PROBLEM SOLVING ENVIRONMENT

• US 20100106714A1
• Filed: 12/22/2006
• Published: 04/29/2010
• 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: Xu, Yi Liang, Ong, Yew Soon, Lim, Meng Hiot
• Granted Patent: US 9,015,145 B2
• Time in Patent Office: Days
• US Class Current: 707/718
• 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 methodology is presented to address the need for rapid generation and optimization of algorithms that are efficient in solving a given class of problems within the framework of a software environment. The environment incorporates an evolutionary learning methodology which automatically optimizes the configurations of procedural components of the algorithm. In this way, both the efficiency and the quality of algorithm development is enhanced significantly.

Claims

1. A method of obtaining 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 method employing 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 method 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;

(c) an evaluation step of evaluating the candidate algorithms; and

(d) obtaining modified probabilistic functions and returning to step (b) until a termination criterion is met.

2. A method according to claim 1 in which 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. A method according to claim 1 in which 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. A method according to claim 1 in which the probabilistic function associated with each traversal split node is defined by a respective set of one or more numerical trace values.

5. A method according to claim 1 in which said evaluation step (c) 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.

6. A method according to claim 5 in which the quality of said one or more solutions is evaluated using a user-defined quality function.

8. A method of configuring a search algorithm, the method comprising performing a 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.

10. A method according to claim 8 in which said evaluation step employs a test set of problems of which the actual optimization problem is statistically typical.

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

7. (canceled)

9. (canceled)

11. A method of configuring a search algorithm for solving a combinatorial-optimization problem, the search algorithm including one or more procedural components, the method employing 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 method 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,

(c) evaluating the candidate search algorithms, and

(d) obtaining modified probabilistic functions and returning to step (b) until a termination criterion is met.

13. A method according to claim 11 further comprising generating source code implementing the configured search algorithm.

12. (canceled)

14. 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 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:

(a) select current probabilistic functions;

(b) produce 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,

(c) evaluate the candidate search algorithms;

(d) obtain modified probabilistic functions; and

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

15. A computer program product 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 the probabilistic functions,

said program instructions causing said processor to perform a set of steps:

(a) select current probabilistic functions;

(b) produce 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,

(c) evaluate the candidate search algorithms, and

(d) obtain modified probabilistic functions and returning to step (b) until a termination criterion is met.

17. 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:

(a) select current probabilistic functions;

(b) produce 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;

(c) evaluate the candidate algorithms; and

(d) obtain modified probabilistic functions, and

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

18. A computer program product 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:

(a) select current probabilistic functions;

(b) produce 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;

(c) evaluate the candidate algorithms; and

(d) obtain modified probabilistic functions, and

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