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

• US 7,505,947 B2
• Filed: 10/20/2005
• Issued: 03/17/2009
• Est. Priority Date: 10/20/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McArdle, James Michael
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US11/255,200
• Publication Number:
  US 20070112698A1
• Time in Patent Office: 1,244 Days
• Field of Search: 706/13
• 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 solutions involving physical constraints comprising:

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

regenerating a next generation from said initial population by reproducing P solutions where P represents a percentage of N solutions obtained 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 regenerating steps, selecting the solution having the highest fitness function value;

the improvement comprising;

applying said genetic algorithm method for providing solutions to determine the optimum arrangement of tangible objects each having defined linear dimensions within a container of defined linear dimensions;

counting the number of a plurality of said regenerations for each solution; and

changing said set of genetic operators for each solution after a predetermined plural number of said regenerations.

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

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

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

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

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

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

8. A computer program comprising a computer useable medium having a computer readable program including a genetic algorithm for providing solutions involving physical constraints, wherein the computer readable program when executed on a computer causes the computer to:

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

regenerate a next generation from said initial population by reproducing P solutions where P represents a percentage of N solutions obtained through the application of a set of genetic operators to said N solutions (chromosomes);

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

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

after a plurality of said regenerate steps, select the solution having the highest fitness function value;

the improvement comprising causing the computer to;

apply said genetic algorithm method for providing solutions to determine the optimum arrangement of tangible objects each having defined linear dimensions within a container of defined linear dimensions;

count the number of a plurality of said regenerations for each solution; and

change said set of genetic operators for each solution after a predetermined plural number of said regenerations.

9. The computer program of claim 8 wherein said set of genetic operators is changed a plurality of times for each solution after respective predetermined numbers of said plurality of said counts.

10. The computer program of claim 9 wherein said set of genetic operators includes a percentage of N mutations, and a percentage of N crossovers.

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

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

13. The computer program of claim 11 wherein said step of selecting the solution having the highest fitness function value is carried out after a predetermined count of said regenerations.

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