Back to results
US 7,444,309 B2Granted
Method and system for implementing evolutionary algorithms
AssigneeIcosystem Corporation
InventorsJuergen Branke, Michael Campos
Life of this patent
Estimating the term…
Abstract
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.
Claims50
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).
5 more elements
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).
5 more elements
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).
12 more elements
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).
9 more elements
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.
5 more elements
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.
5 more elements
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.
12 more elements
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.
9 more elements
Dependencies are inferred from the claim text.