US 9,311,597 B2Granted

Early generation of individuals to accelerate genetic algorithms

AssigneeInternational Business Machines Corporation

InventorJason F. Cantin

Life of this patent

Estimating the term…

Loading patent…

Abstract

While at least one candidate solution of a first generation of candidate solutions remains to be evaluated in accordance with a fitness function for an optimization problem, a plurality of candidate solutions is selected from the first generation of candidate solutions to participate in a tournament. It is determined whether each of the plurality of candidate solutions selected to participate in the tournament have been evaluated in accordance with the fitness function. If all have been evaluated, then one or more winners of the tournament are selected from the plurality of candidate solutions of the first generation of candidate solutions. A candidate solution of a second generation of candidate solutions is created with the selected one or more winners of the tournament in accordance with a genetic operator.

Claims18

Dependent claims

A method comprising:

while at least one candidate solution of a first generation of candidate solutions remains to be evaluated in accordance with a fitness function for an optimization problem, selecting a plurality of candidate solutions from the first generation of candidate solutions to participate in a tournament, wherein in response to a first candidate solution of the plurality of candidate solutions being of an earlier generation in comparison to a second candidate solution of the plurality of candidate solutions, the first candidate solution is given a higher priority than the second candidate solution that is used to prioritize selection;
determining that each of the plurality of candidate solutions selected to participate in the tournament have been evaluated in accordance with the fitness function;
selecting one or more winners of the tournament from the plurality of candidate solutions of the first generation of candidate solutions;
and
while at least one candidate solution of the first generation remains to be evaluated in accordance with the fitness function, creating a candidate solution of a second generation of candidate solutions with the selected one or more winners of the tournament in accordance with a genetic operator.

2 more elements

A computer program product for early construction of candidate solutions, the computer program product comprising:

a computer readable storage device having computer usable program code embodied therewith, the computer usable program code comprising a computer usable program code configured to:
select a plurality of candidate solutions from a first generation of candidate solutions to participate in a tournament, wherein in response to a first candidate solution of the plurality of candidate solutions being of an earlier generation in comparison to a second candidate solution of the plurality of candidate solutions, the first candidate solution is given a higher priority than the second candidate solution that is used to prioritize selection;
determine whether each of the plurality of candidate solutions selected to participate in the tournament have been evaluated in accordance with the fitness function;
select one or more winners of the tournament from the plurality of candidate solutions of the first generation of candidate solutions;
and
while at least one candidate solution of the first generation remains to be evaluated in accordance with the fitness function, create a candidate solution of a second generation of candidate solutions with the selected one or more winners of the tournament in accordance with a genetic operator.

3 more elements

An apparatus comprising:

a processor;
and
a computer readable storage medium coupled with the processor, the computer readable storage medium having computer usable program code embodied therewith, the computer usable program code comprising a computer usable program code configured to:
select a plurality of candidate solutions from a first generation of candidate solutions to participate in a tournament, wherein in response to a first candidate solution of the plurality of candidate solutions being of an earlier generation in comparison to a second candidate solution of the plurality of candidate solutions, the first candidate solution is given a higher priority than the second candidate solution that is used to prioritize selection;
determine whether each of the plurality of candidate solutions selected to participate in the tournament have been evaluated in accordance with the fitness function;
select one or more winners of the tournament from the plurality of candidate solutions of the first generation of candidate solutions;
and
while at least one candidate solution of the first generation remains to be evaluated in accordance with the fitness function, create a candidate solution of a second generation of candidate solutions with the selected one or more winners of the tournament in accordance with a genetic operator.

5 more elements

Dependencies are inferred from the claim text.