System and method for solving an optimization problem using a neural-network-based genetic algorithm technique

• US 20040044633A1
• Filed: 08/29/2002
• Published: 03/04/2004
• Est. Priority Date: 08/29/2002
• Status: Abandoned Application

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Chen, Thomas W.
• Application Number:
  US10/231,760
• Publication Number:
  US 20040044633A1
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 3/086 using evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

A system and method for solving a problem using a genetic algorithm technique is disclosed. A population of chromosomes that is representative of a set of candidate solutions of the problem is created and subjected to simulated evolution. A neural network is trained and employed to evaluate the fitness of the population of chromosomes. Based on the neural network evaluation, the population of chromosomes is updated.

Claims

1. A method for solving a problem using a genetic algorithm technique, comprising:

initializing a population of chromosomes representative of a set of candidate solutions to said problem;

training a neural network for fitness prediction with respect to said population of chromosomes; and

applying said trained neural network for finding an optimal solution to said optimization problem, wherein said trained neural network is used for evaluating fitness of each successive generation of chromosomes obtained as a result of a genetic operation.

2. The method as recited in claim 1, wherein a portion of said population of chromosomes representative of said set of candidate solutions comprises a randomly-generated population of chromosomes.

3. The method as recited in claim 1, wherein the step of training a neural network for fitness prediction further comprises training said neural network until the fitness prediction of said neural network asymptotically approaches a predetermined level of accuracy.

4. The method as recited in claim 1, further comprising the step of periodically reinforcing said training of said neural network for fitness prediction with respect to said population of chromosomes.

5. A method for solving an optimization problem using a genetic algorithm technique, comprising:

creating a population of chromosomes representative of a set of candidate solutions of said optimization problem;

performing genetic algorithm operations on said chromosomes to form a new population of chromosomes;

evaluating the fitness of said new population of chromosomes with a neural network; and

updating said new population of chromosomes based on the neural network evaluation.

6. The method as recited in claim 5, wherein said genetic algorithm operations are selected from the group consisting of cross-linking operations, linking operations, and mutation operations.

7. The method as recited in claim 6, further comprising adjusting an evolutionary variable selected from the group consisting of rate of cross-linking operations and rate of mutation operations.

8. The method as recited in claim 5, wherein said neural network comprises a back propagation neural network.

9. The method as recited in claim 5, further comprising the step of training said neural network for fitness evaluation by comparing a neural network prediction and an analytical solution.

10. The method as recited in claim 9, wherein said training comprises neural network learning.

11. The method as recited in claim 9, wherein said training comprises neural network reenforcement learning.

12. A computer-accessible medium having instructions for solving an optimization problem using a genetic algorithm technique operable to be executed on a computer system, said instructions which, when executed on said computer system, perform the steps:

creating a population of chromosomes representative of a set of candidate solutions of said optimization problem;

performing genetic algorithm operations on said chromosomes to form a new population of chromosomes;

evaluating the fitness of said new population of chromosomes with a neural network; and

updating said new population of chromosomes based on the neural network evaluation.

13. The computer-accessible medium as recited in claim 12, wherein said genetic algorithm operations are selected from the group consisting of cross-linking operations, linking operations, and mutation operations.

14. The computer-accessible medium as recited in claim 13, further comprising instructions for adjusting an evolutionary variable selected from the group consisting of rate of cross-linking operations and rate of mutation operations.

15. The computer-accessible medium as recited in claim 12, wherein said neural network comprises a back propagation neural network.

16. The computer-accessible medium as recited in claim 12, further comprising instructions for training said neural network for fitness evaluation by comparing a neural network prediction and an analytical solution.

17. The computer-accessible medium as recited in claim 16, wherein said training comprises neural network learning.

18. The computer-accessible medium as recited in claim 16, wherein said training comprises neural network reenforcement learning.

19. A system for solving a problem using a genetic algorithm technique, comprising:

means for generating successive populations of chromosomes representative of a set of candidate solutions to said problem;

means for training a neural network for fitness with respect to said successive populations of chromosomes; and

means for applying said trained neural network for finding an optimal solution to said problem, wherein said trained neural network is used for evaluating fitness of each said successive generation of chromosomes.

20. The system as recited in claim 19, wherein said means for training a neural network for fitness with respect to said successive populations of chromosomes further comprises means for training said neural network until said neural network'"'"'s predictive accuracy asymptotically approaches a predetermined level of accuracy.

21. The system as recited in claim 19, wherein each of said successive generation of chromosomes is obtained as a result of a genetic operation.

22. The system as recited in claim 19, wherein said neural network comprises a back propagation neural network.

23. The system as recited in claim 19, wherein said neural network comprises a feed-forward neural network.

24. The method as recited in claim 19, wherein said training means comprises neural network learning means.

25. The method as recited in claim 19, wherein said training means comprises neural network reenforcement learning means.