Solution Fitness Function
This module provides an interface for how fitness functions should interact
with solvers, as well as the definitions for a few benchmark problems
-
class FitnessFunction.DeceptiveStepTrap(config, _=None)[source]
Implementation of the deceptive step trap benchmark. Inherits evaluate
and subProblemsSolved from DeceptiveTrap.
-
normalize(genes, fitness)[source]
Normalizes a fitness for a set of genes to be in the range [0-1], such
that 1 is considered a successful run. Automatically called by
evaluate.
Parameters:
- genes: The list of genes being evaluated.
- fitness: The fitness value that needs to be normalized.
-
scoreTrap(genes)[source]
Given a set of genes in a trap, returns the fitness of those genes.
Calls DeceptiveTrap.scoreTrap to get the raw trap value, then
modifies the fitness to include fitness plateaus.
Parameters:
- genes: The genes for a single trap to be evaluated.
-
class FitnessFunction.DeceptiveTrap(config, _=None)[source]
Implementation of the deceptive trap benchmark.
-
evaluate(genes)[source]
Given a list of binary genes, return the normalized fitness of those
genes.
Parameters:
- genes: The list of genes to be evaluated.
-
normalize(genes, fitness)[source]
Normalizes a fitness for a set of genes to be in the range [0-1], such
that 1 is considered a successful run. Automatically called by
evaluate.
Parameters:
- genes: The list of genes being evaluated.
- fitness: The fitness value that needs to be normalized.
-
scoreTrap(genes)[source]
Given the set of genes in a trap, return the fitness of those genes.
Automatically called by evaluate.
Parameters:
- genes: The list of genes to be scored.
-
subProblemsSolved(genes)[source]
Returns a list of 0s and 1s indicating with of the traps contain the
optimum value in the passed in genes.
Parameters:
- genes: The list of genes to find solved subproblems in.
-
class FitnessFunction.FitnessFunction(config, runNumber)[source]
An interface for a fitness function provided to ensure all required
functions of a fitness function object are implemented
-
evaluate(genes)[source]
Empty function handle that throws an exception if not overridden.
Given a list of genes, should return the fitness of those genes.
-
subProblemsSolved(genes)[source]
Empty function handle that throws an exception if not overridden.
Given a list of genes, returns a list of zeros and ones indicating
which sub problems have been solved. If this fitness function cannot
be described as having subproblems, should return a list containing a
single 1 or 0 indicating if these genes represent the global optimum.
-
class FitnessFunction.NearestNeighborNK(config, runNumber)[source]
An implementation of the nearest neighbor NK landscape benchmark.
-
buildProblem(config, problemNumber)[source]
Attempts to load the NK problem specified by the configuration and
problem number. If this problem has not been previously generated,
this function will construct the fitness matrix and use solve to
find the global minimum and maximum.
Parameters:
- config: A dictionary containing all configuration information
required to load/generate a NK problem. Should include values
for:
- dimensions: The number of dimensions in use
- k: The amount of gene overlap in the subproblems.
- nkProblemFolder: The relative path to the folder where NK
instances should be saved to and loaded from.
-
evaluate(genes)[source]
Given a list of binary genes, return the normalized fitness of those
genes.
Parameters:
- genes: The list of genes to be evaluated.
-
getFitness(g, neighborhood)[source]
Given a gene index and the list of gene values in its neighborhood,
return the fitness of the subproblem.
Parameters:
- g: The subproblem to get the fitness for.
- neighborhood: The gene values contained in that subproblem
-
solve(extreme)[source]
Returns the optimal value for this NK instance in polynomial time
using dynamic programming. For full explanation for how this
algorithm works see:
A. H. Wright, R. K. Thompson, and J. Zhang. The computational
complexity of N-K fitness functions. IEEE Trans. on Evolutionary
Computation, 4(4):373-379, 2000
Parameters:
- extreme: A function that selects which fitness extreme is being
solved for. For instance, min or max.
-
subProblemsSolved(genes)[source]
Returns a list of 0s and 1s indicating which subproblems currently
have values identical to those for the global best genes.
Parameters:
- genes: The genes to be checked for solved subproblems.