초록 ▼

A method, computer program storage medium and system that implement evolutionary algorithms on heterogeneous computers; in which a central process resident in a central computer delegates subpopulations of individuals of similar fitness from a central pool to separate processes resident on periphera

A method, computer program storage medium and system that implement evolutionary algorithms on heterogeneous computers; in which a central process resident in a central computer delegates subpopulations of individuals of similar fitness from a central pool to separate processes resident on peripheral computers where they evolve for a certain number of generations after which they return to the central pool before the delegation is repeated.

대표청구항 ▼

What is claimed is: 1. In a computer system comprising a central processor and a plurality of peripheral processors, and at least one user interface including at least one input device and at least one output device, a method comprising: a) receiving by means of at least one of the at least one inp

What is claimed is: 1. In a computer system comprising a central processor and a plurality of peripheral processors, and at least one user interface including at least one input device and at least one output device, a method comprising: a) receiving by means of at least one of the at least one input devices information concerning an optimization problem, b) in response to a communication from one of the plurality of peripheral processors to the central processor, selecting a subpopulation of candidate solutions to the optimization problem from a pool of available candidate solutions, said subpopulation being selected from among a plurality of candidate solutions having fitness values found in a contiguous subrange among fitness values of available candidate solutions in the pool, c) processing the subpopulation according to an evolutionary algorithm until a termination condition is reached, d) merging the subpopulation whose processing has terminated back into the pool, e) repeating said selecting, processing, and merging until an ending condition is reached, and f) generating an output signal based upon the candidate solutions in the pool, and providing that output signal including information about at least one candidate solution to the optimization problem to a user by means of at least one of the at least one output devices, wherein the central processor maintains the pool, and two or more peripheral processors of heterogeneous capabilities communicatively linked to the central processor process the subpopulations, and wherein the contiguous subrange of fitness values from which the selection is made in at least one iteration of step b) does not overlap the contiguous subrange of fitness values from which the selection was made in at least one prior iteration of step b). 2. The method of claim 1, wherein each subpopulation has the same number of candidate solutions. 3. The method of claim 1, wherein a size of a subpopulation is selected in dependence on a capability of a processor responsible for processing the said subpopulation. 4. The method of claim 1 wherein processing a subpopulation according to the evolutionary algorithm comprises one or more generations, each generation comprising: selecting a plurality of candidate solutions from the subpopulation based on a fitness of each candidate solution, creating a plurality of new candidate solutions by applying evolutionary operators to the selected plurality of solutions, and evaluating the fitness of a plurality of the created solutions. 5. The method of claim 4 wherein the termination condition comprises processing for a fixed number of generations. 6. The method of claim 4 wherein the termination condition comprises processing until the fitness of a plurality of created solutions increases by less than a predetermined amount. 7. The method of claim 1, wherein at least part of the processing of at least two subpopulations is concurrent in time. 8. The method of claim 1, wherein the contiguous fitness subranges in successive iterations of step b) are chosen such that a probability of a solution in the central pool being included in a contiguous fitness subrange does not depend upon the fitness of the solution. 9. The method of claim 1, wherein the contiguous fitness subranges in successive iterations of step b) are chosen in a round-robin order by fitness rank. 10. The method of claim 1, wherein all solutions in the contiguous subrange of fitness have an equal chance for selection. 11. The method of claim 1, wherein the solutions selected from the contiguous subrange of fitness are chosen randomly. 12. A computer program storage medium comprising encoded software instructions for causing a computer system comprising a central processor and a plurality of peripheral processors, and at least one user interface including at least one input device and at least one output device, to perform the steps of: a) receiving by means of at least one of the at least one input devices information concerning an optimization problem, b) in response to a communication from one of the plurality of peripheral processors to the central processor, selecting a subpopulation of candidate solutions to the optimization problem from a pool of available candidate solutions, said subpopulation being selected from among a plurality of candidate solutions having fitness values found in a contiguous subrange among fitness values of available candidate solutions in the pool, c) processing the subpopulation according to an evolutionary algorithm until a termination condition is reached, d) merging the subpopulation whose processing has terminated back into the pool, e) repeating said selecting, processing, and merging until an ending condition is reached, and f) generating an output signal based upon the candidate solutions in the pool, and providing that output signal including information about at least one candidate solution to the optimization problem to a user by means of at least one of the at least one output devices, wherein the central processor maintains the pool, and two or more peripheral processors of heterogeneous capabilities communicatively linked to the central processor process the subpopulations, and wherein the contiguous subrange of fitness values from which the selection is made in at least one iteration of step b) does not overlap the contiguous subrange of fitness values from which the selection was made in at least one prior iteration of step b). 13. The medium of claim 12, wherein each subpopulation has the same number of candidate solutions. 14. The medium of claim 12, wherein a size of a subpopulation is selected in dependence on a capability of a processor responsible for processing the said subpopulation. 15. The medium of claim 12 wherein processing a subpopulation according to the evolutionary algorithm comprises one or more generations, each generation comprising: selecting a plurality of candidate solutions from the subpopulation based on a fitness of each candidate solution, creating a plurality of new candidate solutions by applying evolutionary operators to the selected plurality of solutions, and evaluating the fitness of a plurality of the created solutions. 16. The medium of claim 15 wherein the termination condition comprises processing for a fixed number of generations. 17. The medium of claim 15 wherein the termination condition comprises processing until the fitness of a plurality of created solutions increases by less than a predetermined amount. 18. The medium of claim 12, wherein at least part of the processing of at least two subpopulations is concurrent in time. 19. The media of claim 12, wherein the contiguous fitness subranges in successive iterations of step b) are chosen such that a probability of a solution in the central pool being included in a contiguous fitness subrange does not depend upon the fitness of the solution. 20. The media of claim 12, wherein the contiguous fitness subranges in successive iterations of step b) are chosen in a round-robin order by fitness rank. 21. The media of claim 12, wherein all solutions in the contiguous subrange of fitness have an equal chance for selection. 22. The media of claim 12, wherein the solutions selected from the contiguous subrange of fitness are chosen randomly. 23. A computer system comprising: at least one user interface including at least one input device and at least one output device, a central computer comprising a memory, and two or more peripheral computers of heterogeneous capabilities, each comprising a memory, the central computer and all peripheral computers being communicatively linked, wherein the central computer memory comprises simultaneously or sequentially one or more programs which cause this computer to perform the steps of: a) receiving by means of at least one of the at least one input devices information concerning an optimization problem, b) in response to a communication from one of the peripheral computers to the central computer, selecting a subpopulation of candidate solutions to the optimization problem from a pool of available candidate solutions, said subpopulation being selected from among a plurality of candidate solutions having fitness values found in a contiguous subrange among fitness values of available candidate solutions in the pool, and c) transmitting this subpopulation to the said peripheral computer, d) merging a subpopulation of evolved candidate solutions received from the said peripheral computer back into the pool, e) repeating the steps of selecting, transmitting, and merging until an ending condition is reached, and f) generating an output signal based upon the candidate solutions in the pool, and providing that output signal including information about at least one candidate solution to the optimization problem to a user by means of at least one of the at least one output devices, wherein each peripheral computer memory comprises simultaneously or sequentially one or more programs which cause the said computer to perform the steps of: requesting and receiving a subpopulation of candidate solutions from the central computer, processing the received subpopulation according to the evolutionary algorithm until a termination condition is reached, and returning the processed subpopulation back to the central processor, and wherein the contiguous subrange of fitness values from which the selection is made in at least one iteration of step b) does not overlap the contiguous subrange of fitness values from which the selection was made in at least one prior iteration of step b). 24. The system of claim 23, wherein each subpopulation has the same number of candidate solutions. 25. The system of claim 23, wherein a size of a subpopulation is selected in dependence on a capability of a peripheral computer responsible for processing the said subpopulation. 26. The system of claim 23 wherein processing a subpopulation according to the evolutionary algorithm comprises one or more generations, each generation comprising: selecting a plurality of candidate solutions from the subpopulation based on a fitness of each candidate solution, creating a plurality of new candidate solutions by applying genetic operators to the selected plurality of solutions, and evaluating the fitness of a plurality of the created solutions. 27. The system of claim 26 wherein the termination condition comprises processing for a fixed number of generations. 28. The system of claim 26 wherein the termination condition comprises processing until the fitness of a plurality of created solutions increases by less than a predetermined amount. 29. The system of claim 23, wherein at least part of the processing of at least two subpopulations is concurrent in time. 30. The system of claim 23, wherein the contiguous fitness subranges in successive iterations of step b) are chosen such that a probability of a solution in the central pool being included in a contiguous fitness subrange does not depend upon the fitness of the solution. 31. The system of claim 23, wherein the contiguous fitness subranges in successive iterations of step b) are chosen in a round-robin order by fitness rank. 32. The system of claim 23, wherein all solutions in the contiguous subrange of fitness have an equal chance for selection. 33. The system of claim 23, wherein the solutions selected from the contiguous subrange of fitness are chosen randomly. 34. In a computer system comprising a central process and a plurality of peripheral processes, and at least one user interface including at least one input device and at least one output device, a method for generating one or more solutions to an optimization problem, comprising: a) receiving by means of at least one of the at least one input devices information concerning the optimization problem, b) generating a central pool comprising a population of candidate optimization problem solutions; c) associating a fitness with each of the said solutions; d) in response to a communication from one of the plurality of peripheral processes to the central process, selecting in the central process a subpopulation of solutions from a collection of solutions forming a contiguous subrange of fitness within the central pool when the selection is made; e) performing an evolutionary algorithm in the said peripheral process to generate an evolved subpopulation of solutions from the selected subpopulation of solutions; f) merging the evolved subpopulation of solutions into the central pool; g) repeating the steps d), e) and f) until a stopping condition is satisfied; and h) generating an output signal based upon one or more of the solutions in the central pool, and providing that output signal including information about the one or more solutions to the optimization problem to a user by means of at least one of the at least one output devices; wherein the central process is resident in a central computer, and a plurality of peripheral processes are resident in a plurality of peripheral computers communicatively connected to the central computer; and wherein the contiguous subrange of fitness from which the selection is made in at least one iteration of step d) does not overlap the contiguous subrange of fitness from which the selection was made in at least one prior iteration of step d). 35. The method of claim 34, wherein at least two peripheral processes are resident in the same peripheral computer. 36. The method of claim 34, wherein at least one peripheral process performs step d) by using idle background resources in the peripheral computer in which it resides. 37. The method of claim 34, wherein at least two of the peripheral processes perform step d) on selected subpopulations of solutions simultaneously. 38. The method of claim 34, wherein a size of the subpopulation selected for the peripheral process is determined by a processing capability of the peripheral process. 39. The method of claim 34, wherein a size of the central pool is determined based upon processing capabilities of the peripheral processes, to reduce a likelihood that a subpopulation of candidate solutions will not he available for a peripheral process. 40. The method of claim 34, wherein the stopping condition is a predetermined number of generations of evolution having occurred. 41. The method of claim 34, wherein the stopping condition is a determination that the fitness of solutions in the evolved subpopulations has increased by less than a predetermined amount. 42. The method of claim 34, wherein performing the evolutionary algorithm in the said peripheral process to generate the evolved subpopulation of solutions from the subpopulation of solutions comprises: a) selecting a plurality of solutions from the solutions in the subpopulation, based upon the fitness of each of the said solutions; b) generating a plurality of new candidate solutions by evolutionary operations upon the selected plurality of solutions in the subpopulation; c) determining a fitness for each generated new candidate solution in the subpopulation; and d) repeating steps a), b) and c) for a plurality of generations. 43. The method of claim 34, wherein the contiguous fitness subranges in successive iterations of step d) are chosen such that a probability of a solution in the central pool being included in a contiguous fitness subrange does not depend upon the fitness of the solution. 44. The method of claim 34, wherein the contiguous fitness subranges in successive iterations of step d) are chosen in a round-robin order by fitness rank. 45. The method of claim 34, wherein all solutions in the contiguous subrange of fitness bay an equal chance for selection. 46. The method of claim 34, wherein the solutions selected from the contiguous subrange of fitness are chosen randomly. 47. In a computer system comprising a central processor and a plurality of peripheral processors, and at least one user interface including at least one input device and at least one output device, a method comprising: a) receiving by means of at least one of the at least one input devices information concerning an optimization problem, b) in response to a communication from one of the plurality of peripheral processors to the central processor, selecting a subpopulation of candidate solutions to the optimization problem from a pool of available candidate solutions, said subpopulation being selected from among a plurality of candidate solutions having fitness values found in a contiguous subrange among fitness values of available candidate solutions in the pool, c) processing the subpopulation according to an evolutionary algorithm until a termination condition is reached, d) merging the subpopulation whose processing has terminated back into the pool, e) repeating said selecting, processing, and merging until an ending condition is reached, and f) generating an output signal based upon the candidate solutions in the pool, and providing that output signal including information about at least one candidate solution to the optimization problem to a user by means of at least one of the at least one output devices, and wherein the central processor maintains the pool, and two or more peripheral processors of heterogeneous capabilities communicatively linked to the central processor process the subpopulations, and, wherein in at least one iteration of step b), the contiguous subrange of fitness values does not include the highest fitness values. 48. A computer program storage medium comprising encoded software instructions for causing a computer system comprising a central processor and a plurality of peripheral processors, and at least one user interface including at least one input device and at least one output device, to perform the steps of: a) receiving by means of at least one of the at least one input devices information concerning an optimization problem, b) in response to a communication from one of the plurality of peripheral processors to the central processor, selecting a subpopulation of candidate solutions to the optimization problem from a pool of available candidate solutions, said subpopulation being selected from among a plurality of candidate solutions having fitness values found in a contiguous subrange among fitness values of available candidate solutions in the pool, c) processing the subpopulation according to an evolutionary algorithm until a termination condition is reached, d) merging the subpopulation whose processing has terminated back into the pool, e) repeating said selecting, processing, and merging until an ending condition is reached, and f) generating an output signal based upon the candidate solutions in the pool and providing that output signal including information about at least one candidate solution to the optimization problem to a user by means of at least one of the at least one output devices, and wherein the central processor maintains the pool, and two or more peripheral processors of heterogeneous capabilities communicatively linked to the central processor process the subpopulations, and, wherein in at least one iteration of step b), the contiguous subrange of fitness values does not include the highest fitness values. 49. A computer system comprising: at least one user interface including at least one input device and at least one output device, a central computer comprising a memory, and two or more peripheral computers of heterogeneous capabilities, each comprising a memory, the central computer and all peripheral computers being communicatively linked, wherein the central computer memory comprises simultaneously or sequentially one or more programs which cause this computer to perform the steps of: a) receiving by means of at least one of the at least one input devices information concerning an optimization problem, b) in response to a communication from one of the peripheral computers to the central computer, selecting a subpopulation of candidate solutions to the optimization problem from a pool of available candidate solutions, said subpopulation being selected from among a plurality of candidate solutions having fitness values found in a contiguous subrange among fitness values of available candidate solutions in the pool, and c) transmitting this subpopulation to the said peripheral computer, d) merging a subpopulation of evolved candidate solutions received from the said peripheral computer back into the pool, e) repeating the steps of selecting, transmitting, and merging until an ending condition is reached, and f) generating an output signal based upon the candidate solutions in the pool, and providing that output signal including information about at least one candidate solution to the optimization problem to a user by means of at least one of the at least one output devices, and wherein each peripheral computer memory comprises simultaneously or sequentially one or more programs which cause the said computer to perform the steps of: requesting and receiving a subpopulation of candidate solutions from the central computer, processing the received subpopulation according to the evolutionary algorithm until a termination condition is reached, and returning the processed subpopulation back to the central processor, and, wherein in at least one iteration of step b), the contiguous subrange of fitness values does not include the highest fitness values. 50. In a computer system comprising a central process and a plurality of peripheral processes, and at least one user interface including at least one input device and at least one output device, a method for generating one or more solutions to an optimization problem, comprising: a) receiving by means of at least one of the at least one input devices information concerning the optimization problem, b) generating a central pool comprising a population of candidate optimization problem solutions; c) associating a fitness with each of the said solutions; d) in response to a communication from one of the plurality of peripheral processes to the central process, selecting in the central process a subpopulation of solutions from a collection of solutions forming a contiguous subrange of fitness within the central pool when the selection is made; e) performing an evolutionary algorithm in the said peripheral process to generate an evolved subpopulation of solutions from the selected subpopulation of solutions; f) merging the evolved subpopulation of solutions into the central pool; g) repeating the steps d), e) and f) until a stopping condition is satisfied; and h) generating an output signal based upon one or more of the solutions in the central pool, and providing that output signal including information about the one or more solutions to the optimization problem to a user by means of at least one of the at least one output devices; and wherein the central process is resident in a central computer, and a plurality of peripheral processes are resident in a plurality of peripheral computers communicatively connected to the central computer, and, wherein in at least one iteration of step d), the contiguous subrange of fitness does not include the highest fitness values.