Method and apparatus for an algorithm development environment for solving a class of real-life combinatorial optimization problems

• US 8,170,962 B2
• Filed: 12/08/2006
• Issued: 05/01/2012
• Est. Priority Date: 12/13/2005
• Status: Expired due to Fees

• 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
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): CHANG, LI WU
• Application Number:
  US12/097,254
• Publication Number:
  US 20080313113A1
• Time in Patent Office: 1,971 Days
• Field of Search: None
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The invention pertains to an algorithm development environment for solving a class of combinatorial optimization problems. Many practical real-life applications can be formulated as combinatorial optimization problems. Over the years, there have been algorithms proposed to solve these problems. The effort in customizing algorithms to fulfill a particular domain-specific application is still significant. Furthermore, conventional approaches towards codes generation and modification are tedious and thus inefficient. To address the need for rapid generation of algorithms that are efficient in solving a given class of real-life problems, embodiments provide a hierarchical tree structure for managing a procedure modules library. Based on the preferred management and object-oriented design concept, users configure and generate a genetic algorithm (GA) via an intuitive graphical user interface. The goal-seeking customization of the generated GA can be easily carried out for solving various optimization problems. This way, the efficiency of algorithm development is enhanced significantly.

Claims

1. A method of configuring one or more procedural components of a search algorithm for solving at least one combinatorial-optimization problem, the method employing for each procedural component a corresponding data structure representing ways of configuring the procedural component, the data structure comprising a plurality of nodes associated together in a tree structure, the plurality of nodes representing respective choices which are to be made to configure the procedural component, the method comprising:

configuring the procedural component by traversing the tree structure by a traversal algorithm, wherein the plurality of nodes are labeled successively as a current node;

upon the current node representing a choice which is to be made to configure the procedural component, receiving input making the choice represented by the current node;

wherein the tree structure includes one or more property subtrees, each property subtree being associated with one or more choices which are required by an aspect of the procedural component;

wherein each property subtree includes (i) a property node indicative of the existence of one or more choices which are adapted to configure an aspect of the component and (ii) one or more nodes stemming from the property nodes and representing the respective choices;

the traversal algorithm, upon the current node being a property node, causing all of the nodes stemming from the property node to be labeled successively as the current node, and upon one of those nodes becoming the current node receiving input making the corresponding choice; and

wherein upon the current node being a node from which both a variation node and a procedural node stem, firstly the variation node is selected as the current node, and subsequently the property node is selected as the current node.

2. A method according to claim 1, wherein the algorithm comprises one of:

a genetic algorithm; and

a hybrid genetic algorithm;

the algorithm operating by generating an initial population of chromosomes, and in successive iterations modifying the population of chromosomes.

3. A method according to claim 1, wherein the tree structure includes one or more variation subtrees, each variation subtree being associated with a plurality of options for configuring an aspect of the procedural component.

4. A method according to claim 3, wherein each variation subtree includes (i) a variation node indicative of the existence of a plurality of options for configuring an aspect of the procedural component and (ii) a plurality of nodes stemming from the variation node and representing the respective options;

the traversal algorithm, upon the current node being a variation node, receiving input selecting a single one of the nodes stemming from the current node to be labeled as the current node.

5. A method of configuring one or more procedural components of a search algorithm for solving at least one combinatorial-optimization problem, the method employing for each procedural component a corresponding data structure representing ways of configuring the procedural component, the data structure comprising a plurality of nodes associated together in a tree structure, the plurality of nodes representing respective choices which are to be made to configure the procedural component, the method comprising:

configuring the procedural component by traversing the tree structure by a traversal algorithm, wherein the plurality of nodes are labeled successively as a current node;

upon the current node representing a choice which is to be made to configure the procedural component, receiving input making the choice represented by the current node;

wherein the algorithm comprises one of;

a genetic algorithm; and

a hybrid genetic algorithm;

the algorithm operating by generating an initial population of chromosomes, and in successive iterations modifying the population of chromosomes; and

wherein at least one of the procedural components comprises a Population Initialization procedure which produces the initial population of chromosomes.

6. A method according to claim 5, wherein at least one of the procedural components comprises a Population Evaluation procedure for evaluating the quality of the population.

7. A method according to claim 5, wherein at least one of the procedural components comprises an Offspring Producer procedure for generating new chromosomes using the existing chromosomes.

8. A method according to claim 5, wherein at least one of the procedural components comprises an operation performed on the chromosomes individually.

9. A method according to claim 5, wherein at least one of the procedural components comprises a termination procedure for determining when to terminate the algorithm.

10. A method according to claim 5, wherein the tree structure includes one or more variation subtrees, each variation subtree being associated with a plurality of options for configuring an aspect of the procedural component.

11. A method according to claim 10, wherein each variation subtree includes (i) a variation node indicative of the existence of a plurality of options for configuring an aspect of the procedural component and (ii) a plurality of nodes stemming from the variation node and representing the respective options;

the traversal algorithm, upon the current node being a variation node, receiving input selecting a single one of the nodes stemming from the current node to be labeled as the current node.

12. A method according to claim 5, wherein the tree structure includes one or more property subtrees, each property subtree being associated with one or more choices which are required by an aspect of the procedural component.

13. A method according to claim 12, wherein each property subtree includes (i) a property node indicative of the existence of one or more choices which are adapted to configure an aspect of the component and (ii) one or more nodes stemming from the property nodes and representing the respective choices;

the traversal algorithm, upon the current node being a property node, causing all of the nodes stemming from the property node to be labeled successively as the current node, and upon one of those nodes becoming the current node receiving input making the corresponding choice.

14. A method according to claim 13, wherein upon the current node being a node from which both a variation node and a procedural node stem, firstly the variation node is selected as the current node, and subsequently the property node is selected as the current node.

15. A method of configuring one or more procedural components of a search algorithm for solving at least one combinatorial-optimization problem, the method employing for each procedural component a corresponding data structure representing ways of configuring the procedural component, the data structure comprising a plurality of nodes associated together in a tree structure, the plurality of nodes representing respective choices which are to be made to configure the procedural component, the method comprising:

configuring the procedural component by traversing the tree structure by a traversal algorithm, wherein the plurality of nodes are labeled successively as a current node;

upon the current node representing a choice which is to be made to configure the procedural component, receiving input making the choice represented by the current node; and

wherein upon the current node being a node from which a first type of node and a second type of node stem, firstly the first node is selected as the current node, and subsequently the second type of node is selected as the current node.

16. An apparatus for configuring one or more procedural components of a search algorithm for solving at least one combinatorial-optimization problem, the apparatus employing for each procedural component a corresponding data structure representing ways of configuring the procedural component, the data structure comprising a plurality of nodes associated together in a tree structure, the plurality of nodes representing respective choices which are to be made to configure the procedural component, the apparatus comprising:

means for configuring the procedural component by traversing the tree structure by a traversal algorithm, wherein the plurality of nodes are labeled successively as a current node;

means for, upon the current node representing a choice which is to be made to configure the procedural component, receiving input making the choice represented by the current node; and

wherein upon the current node being a node from which a first type of node and a second type of node stem, firstly the first node is selected as the current node, and subsequently the second type of node is selected as the current node.