Optimization technique using evolutionary algorithms

• US 8,700,548 B2
• Filed: 10/15/2010
• Issued: 04/15/2014
• Est. Priority Date: 04/28/2010
• Status: Active Grant

• Current Assignee: Indian Statistical Institute
• Original Assignee: Indian Statistical Institute
• Inventors: Bhandari, Dinabandhu, Murthy, C. A., Pal, Sankar Kumar
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US13/265,480
• Publication Number:
  US 20120123980A1
• Time in Patent Office: 1,278 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

Provided embodiments include a method, a system, a device, and an article of manufacture. A system for terminating a genetic algorithm (GA), where the GA uses an iterator and generates one best solution per iteration, includes a memory, an iterative processor, and a terminating processor. The memory is provided for storing a plurality of best solutions generated in a plurality of iterations of the GA. One of the best solutions generated in one of the iterations is stored in the memory if the one of the best solutions is better than a previous one of the best solutions generated in a previous one of the iterations. The iterative processor computes a variance of the plurality of the best solutions stored in the memory. The terminating processor terminates the iterator when the variance is less than or equal to a predetermined threshold.

Claims

1. A system for terminating a genetic algorithm (GA) comprising:

an iterator that executes a GA that generates at least one best solution per iteration;

a memory that stores a plurality of best solutions generated in a plurality of iterations of the GA, wherein a best solution is stored in the memory if a fitness function of the best solution is greater than a fitness function of a previous best solution generated in a previous iteration;

an iterative processor that computes a variance of the plurality of the best solutions stored in the memory; and

a terminating processor that terminates the iterator when the variance is less than or equal to a predetermined threshold,

wherein the terminating processor determines whether the variance is less than or equal to the predetermined threshold after a predetermined number of iterations are completed following a starting iteration, and

wherein the predetermined number of iterations is statistically determined based on a rate of change of the variance when the rate of change of the variance relative to a number of the iterations is negative.

2. The system of claim 1, wherein the iterative processor computes the variance when a starting iteration is reached.

3. The system of claim 1, wherein the predetermined threshold is statistically determined based on a rate of change of the variance when the rate of change of the variance relative to a number of the iterations is negative.

4. The system of claim 2, wherein the starting iteration is statistically determined based on a rate of change of the variance when the rate of change of the variance relative to a number of the iterations is positive.

5. The system of claim 1, wherein the iterative processor generates the at least one best solution per iteration from a population of solutions using the fitness function, wherein each solution in the population is coded as a string of a finite length, and wherein a starting iteration is statistically determined based on the finite length and a size of the population.

6. The system of claim 5, wherein when the variance is greater than the predetermined threshold, the iterative processor generates a subsequent population of solutions from the population of solutions using operators including selection, crossover, and mutation.

7. The system of claim 1, wherein the predetermined threshold is selected based on a desired accuracy of the GA.

8. The system of claim 1, wherein the predetermined threshold takes into account properties of an objective function and genetic parameters used in the GA.

9. A method for terminating a genetic algorithm (GA), comprising:

executing a GA by an iterator to generate at least one best solution per iteration;

storing a plurality of best solutions generated in a plurality of iterations of the GA, wherein the best solution is stored in a memory if a fitness function of the best solution is greater than a fitness function of a previous best solution generated in a previous iteration;

computing a variance of the plurality of best solutions stored in the memory using an iterative processor;

terminating the iterator using a terminating processor when the variance is less than or equal to a predetermined threshold;

determining whether the variance is less than or equal to the predetermined threshold after a redetermined number of iterations are completed when a starting iteration is reached; and

determining statistically the predetermined number of iterations based on a rate of change of the variance when the rate of change of the variance relative to a number of iterations is negative.

10. The method of claim 9, further comprising computing the variance when a starting iteration is reached.

11. The method of claim 9, further comprising determining statistically the predetermined threshold based on a rate of change of the variance when the rate of change of the variance relative to a number of the iterations is negative, wherein the predetermined threshold takes into account properties of an objective function and genetic parameters used in the GA.

12. The method of claim 10, further comprising determining statistically the starting iteration based on a rate of change of the variance when the rate of change of the variance relative to a number of iterations is positive.

13. The method of claim 9, further comprising generating the at least one best solution per iteration from a population of solutions using the fitness function, wherein each solution in the population is coded as a string of a finite length, and wherein the starting iteration is determined statistically based on the finite length and a size of the population.

14. The method of claim 13, further comprising generating a subsequent population of solutions from the population of solutions using operators including selection, crossover, and mutation when the variance is greater than the predetermined threshold.

15. The method of claim 9, further comprising selecting the predetermined threshold based on a desired accuracy of the GA.

16. A tangible computer-readable storage device for storing program instructions that cause a processor to perform steps of the method of claim 9 when the processor executes the program instructions.