DENOPTIM's evolutionary algorithm. More...

Collaboration diagram for denoptim.ga.EvolutionaryAlgorithm:

Public Member Functions
	EvolutionaryAlgorithm (GAParameters settings, ExternalCmdsListener cmdListener)

void	run () throws DENOPTIMException

void	stopRun ()

void	removeCandidates (Set< String > candID)
	Adds candidate IDs to the list of "to-be-removed" candidates. More...

void	addCandidates (Set< String > pathNames)
	Adds candidate IDs to the list of "to-be-included" candidates. More...

Package Attributes
final ExternalCmdsListener	cmdListener
	Service watching for external commands. More...

Private Member Functions
void	initializePopulation (Population population) throws DENOPTIMException
	Fills up the population with candidates build from scratch. More...

int	processInitialPopCandidate (Candidate candidate, Population population, Monitor mnt, List< Task > batchOfSyncParallelTasks, int attemptsToFillBatch, boolean replaceWorstPopMember, boolean candidatesOverflow) throws DENOPTIMException

void	submitSyncParallelBatch (List< Task > batchOfSyncParallelTasks) throws DENOPTIMException

boolean	evolvePopulation (Population population, int genId) throws DENOPTIMException
	Generates a given number of new candidate items and adds them to the current population. More...

List< Candidate >	makeOffspringA (List< Candidate > eligibleParents, Population population, Monitor mnt) throws DENOPTIMException
	Generates one offspring according to the method where crossover and mutation are decoupled, i.e., we can do mutation without doing crossover. More...

List< Candidate >	makeOffspringB (List< Candidate > eligibleParents, Population population, Monitor mnt) throws DENOPTIMException
	Generates one offspring according to the method where crossover and mutation are coupled, i.e., we do mutation only on offsprings that come from a successful crossover. More...

void	cleanupAsync ()
	Removes all tasks whether they are completed or not. More...

void	cleanupCompleted ()
	Removes only tasks that are marked as completed. More...

boolean	checkForException ()

Private Attributes
SizeControlledSet	scs
	Storage of unique identifiers encountered by this instance. More...

boolean	stopped = false
	Flag signaling this EA was stopped. More...

Set< String >	candidatesToRemove = new HashSet<String>()
	List of IDs of candidates to be removed from the population. More...

List< String >	candidatesToAdd = new ArrayList<String>()
	List of IDs of candidates to be evaluated upon request from the user. More...

boolean	isAsync = true
	Flag determining the use of asynchronous parallelization scheme. More...

Map< FitnessTask, Future< Object > >	futures
	Temporary storage of future results produced by fitness evaluation tasks submitted to asynchronous parallelization scheme. More...

List< FitnessTask >	submitted
	Temporary storage of fitness evaluation tasks just submitted to asynchronous Parallelization scheme. More...

ThreadPoolExecutor	tpe
	Execution service used in asynchronous parallelization scheme. More...

TasksBatchManager	tbm
	Task manager for tasks to be executed as batches. More...

Throwable	ex
	Issue emerging from a thread submitted by asynchronous parallelization scheme. More...

GAParameters	settings
	Parameters controlling the execution of this evolutionary algorithm. More...

Logger	logger = null
	Program-specific logger. More...

final String	NL = System.getProperty("line.separator")

Detailed Description

DENOPTIM's evolutionary algorithm.

This implementation offers two parallelization schemes for managing the amount and timing of threads dedicated to the evaluation of candidates. The schemes are named synchronous and asynchronous.

The synchronous algorithm generates as many new candidates as needed to fill-up or evolve the population, and then submits the candidate evaluation threads with a batch-based executor. All submitted threads must terminate before submitting more threads. With this parallelization scheme all candidates initiated at a given generation can only become part of that very generation. This, however, is only possible when accepting a somewhat inefficient use of the resources every time a generation is about to be completed. To illustrate: consider the moment when there are N free seats in the population (i.e., candidates still to build and evaluate) and M potentially available seats for candidate evaluation threads, where N<M. The algorithm will generate N candidates, and M-N thread seats will remain idle. The situation is repeated a few times until fewer and fewer threads are submitted and the last population member (or new candidate population member) has been evaluated.

This asynchronous parallelization scheme removes the waiting for completion of a batch of threads by keeping always as many active fitness evaluation threads as the max number of such threads, which is controllable in the GAParameters. Even towards the end of a generation, all threads will be used to evaluate candidates. The latter may thus exceed the number of candidates needed to complete the current generation. It is thus possible that a candidate designed in generation I becomes a member of generation J, where J ≥ I.

Author: Vishwesh Venkatraman; Marco Foscato

Definition at line 93 of file EvolutionaryAlgorithm.java.

Constructor & Destructor Documentation

◆ EvolutionaryAlgorithm()

denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm	(	GAParameters	settings,
		ExternalCmdsListener	cmdListener
	)

Definition at line 170 of file EvolutionaryAlgorithm.java.

Here is the call graph for this function:

Member Function Documentation

◆ addCandidates()

void denoptim.ga.EvolutionaryAlgorithm.addCandidates ( Set< String > pathNames )

Adds candidate IDs to the list of "to-be-included" candidates.

Definition at line 1194 of file EvolutionaryAlgorithm.java.

References denoptim.ga.EvolutionaryAlgorithm.candidatesToAdd.

Referenced by denoptim.ga.ExternalCmdsListener.processExternalCmdFile().

Here is the caller graph for this function:

◆ checkForException()

boolean denoptim.ga.EvolutionaryAlgorithm.checkForException ( )

private

Definition at line 1144 of file EvolutionaryAlgorithm.java.

References denoptim.ga.EvolutionaryAlgorithm.ex, denoptim.ga.EvolutionaryAlgorithm.isAsync, denoptim.ga.EvolutionaryAlgorithm.logger, and denoptim.ga.EvolutionaryAlgorithm.submitted.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), and denoptim.ga.EvolutionaryAlgorithm.initializePopulation().

Here is the caller graph for this function:

◆ cleanupAsync()

void denoptim.ga.EvolutionaryAlgorithm.cleanupAsync ( )

private

Removes all tasks whether they are completed or not.

Definition at line 1104 of file EvolutionaryAlgorithm.java.

References denoptim.ga.EvolutionaryAlgorithm.futures, denoptim.ga.EvolutionaryAlgorithm.submitted, and denoptim.ga.EvolutionaryAlgorithm.tpe.

Referenced by denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), and denoptim.ga.EvolutionaryAlgorithm.stopRun().

Here is the caller graph for this function:

◆ cleanupCompleted()

void denoptim.ga.EvolutionaryAlgorithm.cleanupCompleted ( )

private

Removes only tasks that are marked as completed.

Definition at line 1124 of file EvolutionaryAlgorithm.java.

References denoptim.ga.EvolutionaryAlgorithm.futures, and denoptim.ga.EvolutionaryAlgorithm.submitted.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), and denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate().

Here is the caller graph for this function:

◆ evolvePopulation()

boolean denoptim.ga.EvolutionaryAlgorithm.evolvePopulation	(	Population	population,
		int	genId
	)		throws DENOPTIMException

private

Generates a given number of new candidate items and adds them to the current population.

One run of this method corresponds to a generation.

Parameters

population	the list of items to be evolved.
genId	the number identifying this generation in the history of the population.

Exceptions

DENOPTIMException

Definition at line 715 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.run().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ initializePopulation()

void denoptim.ga.EvolutionaryAlgorithm.initializePopulation ( Population population ) throws DENOPTIMException

private

Fills up the population with candidates build from scratch.

Parameters

population the collection of population members. This is where pre-existing and newly generated population members will be collected.

Exceptions

DENOPTIMException

Definition at line 403 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.run().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ makeOffspringA()

List< Candidate > denoptim.ga.EvolutionaryAlgorithm.makeOffspringA	(	List< Candidate >	eligibleParents,
		Population	population,
		Monitor	mnt
	)		throws DENOPTIMException

private

Generates one offspring according to the method where crossover and mutation are decoupled, i.e., we can do mutation without doing crossover.

Besides crossover and mutation, this offspring generation method includes also construction from scratch, which corresponds to mutation of everything. Effectively, these are the alternative possibilities:

Crossover between selected population members.
Mutation of a selected population member.
Construction from scratch.

The operation chosen to try to generate the offspring is given by the weights of the respective strategies in the genetic algorithm settings. Since it is possible that there is no pair of population members that allows to do crossover, it is possible that this method has no way to produce an offspring, in which case it returns null.

Returns: the new offspring if it could be made or null.

Exceptions

DENOPTIMException

Definition at line 976 of file EvolutionaryAlgorithm.java.

References denoptim.ga.EAUtils.buildCandidateByMutation(), denoptim.ga.EAUtils.buildCandidateFromScratch(), denoptim.ga.EAUtils.buildCandidatesByXOver(), denoptim.ga.EAUtils.chooseGenerationMethod(), and denoptim.ga.EvolutionaryAlgorithm.settings.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ makeOffspringB()

List< Candidate > denoptim.ga.EvolutionaryAlgorithm.makeOffspringB	(	List< Candidate >	eligibleParents,
		Population	population,
		Monitor	mnt
	)		throws DENOPTIMException

private

Generates one offspring according to the method where crossover and mutation are coupled, i.e., we do mutation only on offsprings that come from a successful crossover.

Besides crossover, this offspring generation method includes also construction from scratch, which corresponds to mutation of everything. Effectively, these are the alternative possibilities:

Crossover between selected population members.
Crossover between selected population members followed by mutation.
Construction from scratch.

The weights of the respective operation defined in the genetic algorithm settings define which way we try to generate the offspring. Since it is possible that there is no pair of population members that allows to do crossover, it is possible that this method has no way to produce an offspring, in which case it returns null.

Returns: the new offspring if it could be made or null.

Exceptions

DENOPTIMException

Definition at line 1037 of file EvolutionaryAlgorithm.java.

References denoptim.ga.EAUtils.buildCandidateByMutation(), denoptim.ga.EAUtils.buildCandidateFromScratch(), denoptim.ga.EAUtils.buildCandidatesByXOver(), denoptim.programs.denovo.GAParameters.getConstructionWeight(), denoptim.programs.denovo.GAParameters.getCrossoverWeight(), denoptim.graph.Candidate.getGraph(), denoptim.programs.denovo.GAParameters.getMutationWeight(), denoptim.programs.RunTimeParameters.getRandomizer(), denoptim.ga.EAUtils.pickNewCandidateGenerationMode(), denoptim.graph.DGraph.setLocalMsg(), and denoptim.ga.EvolutionaryAlgorithm.settings.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ processInitialPopCandidate()

int denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate	(	Candidate	candidate,
		Population	population,
		Monitor	mnt,
		List< Task >	batchOfSyncParallelTasks,
		int	attemptsToFillBatch,
		boolean	replaceWorstPopMember,
		boolean	candidatesOverflow
	)		throws DENOPTIMException

private

Parameters

candidate	the candidate to process.
population	the population where the candidate may enter.
mnt	the monitor of events.
batchOfSyncParallelTasks	used only in synchronous parallelization.
attemptsToFillBatch	counter of attempts to fill a sync parallel batch of tasks.
replaceWorstPopMember	`true` to add evaluated candidates to the population only if they are better than the worst member in the population.
candidatesOverflow	`true` to allow submission of more candidates than the size of the population.

Returns: the update number of attemptsToFillBatch, if it needs to be updated.

Exceptions

DENOPTIMException

Definition at line 617 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.initializePopulation().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ removeCandidates()

void denoptim.ga.EvolutionaryAlgorithm.removeCandidates ( Set< String > candID )

Adds candidate IDs to the list of "to-be-removed" candidates.

Definition at line 1181 of file EvolutionaryAlgorithm.java.

References denoptim.ga.EvolutionaryAlgorithm.candidatesToRemove.

Referenced by denoptim.ga.ExternalCmdsListener.processExternalCmdFile().

Here is the caller graph for this function:

◆ run()

void denoptim.ga.EvolutionaryAlgorithm.run ( ) throws DENOPTIMException

Definition at line 249 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), and denoptim.programs.denovo.GARunner.runProgram().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ stopRun()

void denoptim.ga.EvolutionaryAlgorithm.stopRun ( )

Definition at line 1089 of file EvolutionaryAlgorithm.java.

References denoptim.ga.EvolutionaryAlgorithm.cleanupAsync(), denoptim.ga.EvolutionaryAlgorithm.isAsync, denoptim.ga.EvolutionaryAlgorithm.stopped, and denoptim.ga.EvolutionaryAlgorithm.tpe.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.programs.denovo.GARunner.handleThrowable(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), and denoptim.ga.ExternalCmdsListener.processExternalCmdFile().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ submitSyncParallelBatch()

void denoptim.ga.EvolutionaryAlgorithm.submitSyncParallelBatch ( List< Task > batchOfSyncParallelTasks ) throws DENOPTIMException

private

Definition at line 697 of file EvolutionaryAlgorithm.java.

References denoptim.task.TasksBatchManager.executeTasks(), denoptim.programs.denovo.GAParameters.getNumberOfCPU(), denoptim.ga.EvolutionaryAlgorithm.settings, and denoptim.ga.EvolutionaryAlgorithm.tbm.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), and denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ candidatesToAdd

List<String> denoptim.ga.EvolutionaryAlgorithm.candidatesToAdd = new ArrayList<String>()

private

List of IDs of candidates to be evaluated upon request from the user.

These candidates might or might not end up in the populations depending on their performance. This list is cleared once its content has been

Definition at line 121 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.addCandidates(), and denoptim.ga.EvolutionaryAlgorithm.evolvePopulation().

◆ candidatesToRemove

Set<String> denoptim.ga.EvolutionaryAlgorithm.candidatesToRemove = new HashSet<String>()

private

List of IDs of candidates to be removed from the population.

This list is cleared once its content has been processed.

Definition at line 114 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), and denoptim.ga.EvolutionaryAlgorithm.removeCandidates().

◆ cmdListener

final ExternalCmdsListener denoptim.ga.EvolutionaryAlgorithm.cmdListener

package

Service watching for external commands.

This enables interactive EA runs.

Definition at line 98 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), and denoptim.ga.EvolutionaryAlgorithm.run().

◆ ex

Throwable denoptim.ga.EvolutionaryAlgorithm.ex

private

Issue emerging from a thread submitted by asynchronous parallelization scheme.

Definition at line 154 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.checkForException(), denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), and denoptim.ga.EvolutionaryAlgorithm.run().

◆ futures

Map<FitnessTask,Future<Object> > denoptim.ga.EvolutionaryAlgorithm.futures

private

Temporary storage of future results produced by fitness evaluation tasks submitted to asynchronous parallelization scheme.

Definition at line 132 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.cleanupAsync(), denoptim.ga.EvolutionaryAlgorithm.cleanupCompleted(), denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), and denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate().

◆ isAsync

boolean denoptim.ga.EvolutionaryAlgorithm.isAsync = true

private

Flag determining the use of asynchronous parallelization scheme.

Definition at line 126 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.checkForException(), denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate(), denoptim.ga.EvolutionaryAlgorithm.run(), and denoptim.ga.EvolutionaryAlgorithm.stopRun().

◆ logger

Logger denoptim.ga.EvolutionaryAlgorithm.logger = null

private

Program-specific logger.

Definition at line 164 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.checkForException(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), and denoptim.ga.EvolutionaryAlgorithm.run().

◆ NL

final String denoptim.ga.EvolutionaryAlgorithm.NL = System.getProperty("line.separator")

private

Definition at line 166 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), and denoptim.ga.EvolutionaryAlgorithm.run().

◆ scs

SizeControlledSet denoptim.ga.EvolutionaryAlgorithm.scs

private

Storage of unique identifiers encountered by this instance.

Definition at line 103 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate(), and denoptim.ga.EvolutionaryAlgorithm.run().

◆ settings

GAParameters denoptim.ga.EvolutionaryAlgorithm.settings

private

Parameters controlling the execution of this evolutionary algorithm.

Definition at line 159 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), denoptim.ga.EvolutionaryAlgorithm.makeOffspringA(), denoptim.ga.EvolutionaryAlgorithm.makeOffspringB(), denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate(), denoptim.ga.EvolutionaryAlgorithm.run(), and denoptim.ga.EvolutionaryAlgorithm.submitSyncParallelBatch().

◆ stopped

boolean denoptim.ga.EvolutionaryAlgorithm.stopped = false

private

Flag signaling this EA was stopped.

Definition at line 108 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), denoptim.ga.EvolutionaryAlgorithm.run(), and denoptim.ga.EvolutionaryAlgorithm.stopRun().

◆ submitted

List<FitnessTask> denoptim.ga.EvolutionaryAlgorithm.submitted

private

Temporary storage of fitness evaluation tasks just submitted to asynchronous Parallelization scheme.

Definition at line 138 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.checkForException(), denoptim.ga.EvolutionaryAlgorithm.cleanupAsync(), denoptim.ga.EvolutionaryAlgorithm.cleanupCompleted(), denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), and denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate().

◆ tbm

TasksBatchManager denoptim.ga.EvolutionaryAlgorithm.tbm

private

Task manager for tasks to be executed as batches.

Definition at line 148 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), and denoptim.ga.EvolutionaryAlgorithm.submitSyncParallelBatch().

◆ tpe

ThreadPoolExecutor denoptim.ga.EvolutionaryAlgorithm.tpe

private

Execution service used in asynchronous parallelization scheme.

Definition at line 143 of file EvolutionaryAlgorithm.java.

Referenced by denoptim.ga.EvolutionaryAlgorithm.cleanupAsync(), denoptim.ga.EvolutionaryAlgorithm.EvolutionaryAlgorithm(), denoptim.ga.EvolutionaryAlgorithm.evolvePopulation(), denoptim.ga.EvolutionaryAlgorithm.initializePopulation(), denoptim.ga.EvolutionaryAlgorithm.processInitialPopCandidate(), denoptim.ga.EvolutionaryAlgorithm.run(), and denoptim.ga.EvolutionaryAlgorithm.stopRun().

The documentation for this class was generated from the following file:

/github/workspace/src/main/java/denoptim/ga/EvolutionaryAlgorithm.java

Public Member Functions

Package Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ EvolutionaryAlgorithm()

Member Function Documentation

◆ addCandidates()

◆ checkForException()

◆ cleanupAsync()

◆ cleanupCompleted()

◆ evolvePopulation()

◆ initializePopulation()

◆ makeOffspringA()

◆ makeOffspringB()

◆ processInitialPopCandidate()

◆ removeCandidates()

◆ run()

◆ stopRun()

◆ submitSyncParallelBatch()

Member Data Documentation

◆ candidatesToAdd

◆ candidatesToRemove

◆ cmdListener

◆ ex

◆ futures

◆ isAsync

◆ logger

◆ NL

◆ scs

◆ settings

◆ stopped

◆ submitted

◆ tbm

◆ tpe