Computer controlled method using genetic algorithms to provide non-deterministic solutions to problems involving physical restraints

• US 20070112698A1
• Filed: 10/20/2005
• Published: 05/17/2007
• Est. Priority Date: 10/20/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McArdle, James
• Granted Patent: US 7,505,947 B2
• Time in Patent Office: Days
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

In a computer controlled genetic algorithm method for providing non-deterministic solutions involving physical constraints the effectiveness of the genetic algorithm may be enhanced by periodically changing the combination or set of genetic operators during the genetic algorithm operation and before selecting the final solution.

Claims

1. In a computer controlled genetic algorithm method for providing non-deterministic solutions involving physical constraints comprising:

generating an existing population of N solutions (chromosomes) to a problem, each solution (chromosome) including a set of values for a predetermined number, M of said physical constraints (genes);

regenerating a next generation from said initial population by reproducing (P=% N) solutions through the application of a set of genetic operators to said N solutions (chromosomes);

applying a weighted fitness function to said P solutions to fail and thereby discard a number of said P solutions;

adding the undiscarded solutions to a number of existing solutions to provide the next generation of solutions; and

after a plurality of said regenerations, selecting the solution having the highest fitness function value;

the improvement comprising;

counting the number of said regenerations for each solution; and

changing said set of genetic operators for each solution after at least one predetermined number of said regenerations.

2. The method of claim 1 wherein said undiscarded solutions are added to a sufficient number of existing solutions to provide a next generation population of N solutions.

3. The method of claim 2 wherein said set of genetic operators is changed a plurality of times for each solution after respective predetermined numbers of a said plurality of said counts for each of said solutions.

4. The method of claim 3 wherein said set of genetic operators includes a % of N mutations, and a % of N crossovers.

5. The method of claim 2 wherein said set of genetic operators includes the value level of the fitness function determining the number of said P solutions.

6. The method of claim 5 said second set of genetic operators includes a changed value of said fitness function determining the number of said P solutions.

7. The method of claim 5 wherein said step of selecting the solution having the highest fitness function value is carried out after a predetermined count of said regenerations.

8. The method of claim 1 wherein said deterministic solution involves linear constraints.

9. The method of claim 8 wherein said linear constraints define spatial relationships.

10. The method of claim 1 wherein said undiscarded solutions are added to a plurality of other undiscarded solutions to provide a next generation population of solutions.

11. In a computer program having code recorded on a computer readable medium providing an improvement in a genetic for providing non-deterministic solutions involving physical constraints comprising:

means for generating an existing population of N solutions (chromosomes) to a problem, each solution (chromosome) including a set of values for a predetermined number, M of said physical constraints (genes);

means for regenerating a next generation from said initial population by reproducing (P=% N) solutions through the application of a set of genetic operators to said N solutions (chromosomes);

means for applying a weighted fitness function to said P solutions to fail and thereby discard a predetermined number of said P solutions;

means for adding the undiscarded solutions to a number of existing solutions to provide the next generation of solutions; and

means, after a plurality of said regenerations, for selecting the solution having the highest fitness function value;

the improvement comprising;

means for counting the number of said regenerations for each of the solutions; and

means for changing said set of genetic operators for each of the solutions after at least one predetermined number of said regenerations.

12. The computer program of claim 11 wherein said undiscarded solutions are added to a sufficient number of existing solutions to provide a next generation population of N solutions.

13. The computer program of claim 12 wherein said set of genetic operators is changed a plurality of times for each solution after a respective predetermined number in said plurality of said counts for each solution.

14. The computer program of claim 13 wherein said set of genetic operators includes a % of N mutations, and a % of N crossovers.

15. The computer program of claim 12 wherein said set of genetic operators includes the value level of the fitness function determining the number of said P solutions.

16. The computer program of claim 15 wherein said second set of genetic operators includes a changed value of said fitness function determining the number of said P solutions.

17. The computer program of claim 15 wherein said means for selecting the solution having the highest fitness function value is carried out after a predetermined count of said regenerations.

18. The computer program of claim 11 wherein said deterministic solution involves linear constraints.

19. The computer program of claim 18 wherein said linear constraints define spatial relationships.

20. The computer program of claim 11 wherein said undiscarded solutions are added to a plurality of other undiscarded solutions to provide a next generation population of solutions.