ltga Package

Experiments Module

This module contains the code used to actually run experiments and to parse the results of those experiments.

ltga.Experiments.bisection(config)

Determines the minimum population size for a configuration that acceptably solves the specified problem using bisection. Starts with a minimum population size of 2, this will double the population size until the success criteria are met. It will then perform a binary search of the space between the lowest found successful population size and the highest found unsuccessful population size. Modifies the input configuration dictionary to contain the minimum successful population size found.

Parameters:

• config: A dictionary containing all configuration information required to perform bisection. Should include values for:
  • bisectionRuns: The number of runs to use a given population size in order to determine if it is successful.
  • problem: The problem being solved, for instance DeceptiveTrap, DeceptiveStepTrap or NearestNeighborNK.
  • bisectionFailureLimit: The maximum number of times a population size can fail to find the global optimum of a problem before it is marked as unsuccessful. IE: A failure limit of 1 means it can fail one of the bisectionRuns without being marked as unsuccessful.
  • All configuration information required to initialize the FitnessFunction.
  • All configuration information required by oneRun.

ltga.Experiments.combineResults(results)

Given a list of result dictionaries, determine the mean and standard deviation for all key values. Only combines results where the success key is true and the number of required evaluations is greater than zero (ensures the LTGA variant was actually used and successful). Returns a dictionary containing all keys found in the original result objects, with the success key now set to the success rate

Parameters:

• results: A list of dictionaries that recorded result information.

ltga.Experiments.createInitialPopulation(runNumber, evaluator, config)

Used to create the initial population for a given run on a specified problem. Uses a HillClimber.steepestAscentHillClimber to optimize all individuals. Will store results to the ‘initialPopFolder’ specified by config for future use, and will automatically load past saved information. Returns the population and a dictionary describing features of that population as well as how it was created.

Parameters:

• runNumber: What number run this population is for. Ensures that populations created for this run in past experiments is reused and that all runs of a single experiment use different initial populations.
• evaluator: A FitnessFunction object used when optimizing the initial population
• config: A dictionary containing all configuration information required to generate initial individuals. Should include values for:
  • initialPopFolder: The relative path for where to save initial population information.
  • problem: The name of the problem currently being solved.
  • dimensions: The number of dimensions in the problem.
  • k: The k value used by the problem.
  • popSize: The population size to be created.

ltga.Experiments.fullRun(config)

Performs a full run of the specified configuration using oneRun. Will return a list of result dictionaries describing what happened in each run. If a keyboard interrupt occurs, will return partial information.

Parameters

• config: A dictionary containing all configuration information required to perform all runs. Should include values for:
  • runs: The number of runs to perform
  • problem: The problem being solved, for instance DeceptiveTrap, DeceptiveStepTrap or NearestNeighborNK.
  • All configuration information required to initialize the FitnessFunction.
  • All configuration information required by oneRun.

ltga.Experiments.oneRun(runNumber, optimizerClass, evaluator, config)

Performs a single run of LTGA in solving a specific problem. Returns a dictionary of result information

Parameters:

• runNumber: What number run this is
• optimizerClass: What class of optimizer to use, for instance LTGA
• evaluator: The problem being solved, for instance FitnessFunction.DeceptiveTrap, FitnessFunction.DeceptiveStepTrap or FitnessFunction.NearestNeighborNK.
• config: A dictionary containing all configuration information required to perform a single run. Should include values for:
  • maximumEvaluations: The hard limit on how many evaluations to perform.
  • maximumFitness: The fitness required for a run to be considered a success.
  • unique: A True / False value to determine if only unique evaluations should be counted
  • All configuration information required by createInitialPopulation and any required by the optimizerClass.

FitnessFunction Module

This module provides an interface for how fitness functions should interact with solvers, as well as the definitions for a few benchmark problems

class ltga.FitnessFunction.DeceptiveStepTrap(config, _=None)

Bases: ltga.FitnessFunction.DeceptiveTrap

Implementation of the deceptive step trap benchmark. Inherits evaluate and subProblemsSolved from DeceptiveTrap.

normalize(genes, fitness)

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)

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 ltga.FitnessFunction.DeceptiveTrap(config, _=None)

Bases: ltga.FitnessFunction.FitnessFunction

Implementation of the deceptive trap benchmark.

evaluate(genes)

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)

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)

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)

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 ltga.FitnessFunction.FitnessFunction(config, runNumber)

Bases: object

An interface for a fitness function provided to ensure all required functions of a fitness function object are implemented

evaluate(genes)

Empty function handle that throws an exception if not overridden. Given a list of genes, should return the fitness of those genes.

subProblemsSolved(genes)

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 ltga.FitnessFunction.NearestNeighborNK(config, runNumber)

Bases: ltga.FitnessFunction.FitnessFunction

An implementation of the nearest neighbor NK landscape benchmark.

buildProblem(config, problemNumber)

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)

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)

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)

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)

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.

HillClimber Module

This module contains coroutines designed to perform different types of hill climbing as well as a function to perform a complete climb of a single set of genes.

ltga.HillClimber.climb(genes, evaluator, method)

Improves the fitness of a list of binary genes using the given method on the specified evaluation function. Modifies the genes in place and returns how many hill climbing evaluations were required to optimize the genes.

Parameters:

• genes: The initial list of binary genes to improve using hill climbing.
• evaluator: A function that takes in a list of genes and returns its fitness.
• method: The hill climbing coroutine to be used. For instance steepestAscentHillClimbing.

ltga.HillClimber.steepestAscentHillClimber(genes)

Given a initial list of binary genes, create a generator designed to yield each step in a steepest ascent hill climb. Modifies the genes in place, such that when iteration ends the genes list contains the best found individual.

Parameters:

• genes: The initial list of binary genes to improve using hill climbing.

Individual Module

Simple module containing individual object implementations.

class ltga.Individual.Individual(genes=[], fitness=-2147483646)

Bases: object

A basic individual object used to combine gene fitness with genomes, as well as some basic utility functions.

LTGA Module

This module contains the implementation of LTGA itself. It includes functionality for each of the variants

class ltga.LTGA.LTGA

Bases: object

Class containing all of the LTGA functionality. Uses the coroutine design structure to interact with problems being optimized. To use, create an LTGA object and then call the generate function. This will send out individuals and expects their fitness to be sent back in.

applyMask(p1, p2, mask)

Used by two parent crossover to create an individual by coping the genetic information from p2 into a clone of p1 for all genes in the given mask. Returns the newly created individual.

Parameters:

• p1: The first parent.
• p2: The second parent.
• mask: The list of indices used in this crossover.

buildTree(distance)

Given a method of calculating distance, build the linkage tree for the current population. The tree is built by finding the two clusters with the minimum distance and merging them into a single cluster. The process is initialized with all possible clusters of size 1 and ends when only a single cluster remains. Returns the subtrees in the order they were created.

Parameters:

• distance: The method of calculating distance. Current options are self.clusterDistance and self.pairwiseDistance

clusterDistance(c1, c2, lookup)

Calculates the true entropic distance between two clusters of genes.

Parameters:

• c1: The first cluster.
• c2: The second cluster.
• lookup: A dictionary mapping cluster pairs to their previously found distances. Should be reset if the population changes.

entropy(mask, lookup)

Calculates the current populations entropy for a given mask.

Parameters:

• mask: The list of indices to examine
• lookup: A dictionary containing entropy values already found for this population. Should be reset if the population changes.

generate(initialPopulation, config)

The individual generator for the LTGA population. Sends out individuals that need to be evaluated and receives fitness information. Will continue sending out individuals until the population contains only one unique individual or a generation passes without the set of unique individuals changing.

Parameters:

• initialPopulation: The list of individuals to be used as the basis for LTGA’s evolution. These individuals should already have fitness values set. If local search is to be performed on the initial population, it should be done before sending to this function.
• config: A dictionary containing all configuration information required by LTGA to generate individuals. Should include values for:
  • distance: The method used to determine the distance between clusters, for instance clusterDistance and pairwiseDistance.
  • ordering: The method used to determine what order subtrees should be used as crossover masks, for instance leastLinkedFirst and smallestFirst.
  • crossover: The method used to generate new individuals, for instance twoParentCrossover and globalCrossover.

getMaskValue(individual, mask)

Gets the individual’s gene values for the given mask

Parameters:

• individual: The individual to get gene information from
• mask: The list of indices to get information from

globalCrossover(masks)

Creates individual generator using the global crossover variant. Uses coroutines to send out individuals and receive their fitness values. Terminates when a complete evolutionary generation has finished.

Parameters:

• masks: The list of crossover masks to be used when generating individuals, ordered based on how they should be applied.

leastLinkedFirst(subtrees)

Reorders the subtrees such that the cluster pairs with the least linkage appear first in the list. Assumes incoming subtrees are ordered by when they were created by the self.buildTree function.

Parameters:

• subtrees: The list of subtrees ordered by how they were originally created.

pairwiseDistance(c1, c2, lookup)

Calculates the pairwise approximation of the entropic distance between two clusters of genes.

Parameters:

• c1: The first cluster.
• c2: The second cluster.
• lookup: A dictionary mapping cluster pairs to their previously found distances. Should be reset if the population changes.

setMaskValues(individual, mask, value)

Sets the individual’s gene values for the given mask

Parameters:

• individual: The individual who’s genes are changing.
• mask: The list of indices to change.
• value: The list of values to change to.

smallestFirst(subtrees)

Reorders the subtrees such that the cluster pairs with the smallest number of genes appear first in the list. Assumes incoming subtrees are ordered by when they were created by the self.buildTree function.

Parameters:

• subtrees: The list of subtrees ordered by how they were originally created.

twoParentCrossover(masks)

Creates individual generator using the two parent crossover variant. Uses coroutines to send out individuals and receive their fitness values. Terminates when a complete evolutionary generation has finished.

Parameters:

• masks: The list of crossover masks to be used when generating individuals, ordered based on how they should be applied.

Util Module

Module containing a host of useful functions that do not fall into more explicit categories.

ltga.Util.binaryCounter(bits)

Creates a generator that will count through all possible values for a set number of bits. Returned in counting order. For instance, binaryCounter(3) will yield, 000, 001, 010, 011 ... 110, 111.

Parameters:

• bits The number of bits in the binary counter.

ltga.Util.classMethods(classType)

Given a class type, return a dictionary mapping string names of that class’s methods to the actual method. For instance classMethod(LTGA)['twoParentCrossover'] will return the twoParentCrossover function.

Parameters:

• classType: Specifies what class to retrieve methods for.

ltga.Util.loadConfiguration(filename, fileMethod=<built-in function open>)

Loads a json from the given file name. Optional file method allows for compressed files.

Parameters:

• filename: The relative path to the file to be loaded.
• fileMethod: Handler to use to open the file. Defaults to regular open.

ltga.Util.loadConfigurations(filenames, fileMethod=<built-in function open>)

Given a list of file names, create a single dictionary containing all of their contents. Repeated keywords will override previously encountered values. Optional file method allows for compressed files.

Parameters:

• filenames: A list of relative paths to the files to be loaded.
• fileMethod: Handler to use to open the file. Defaults to regular open.

ltga.Util.meanstd(data)

Returns the mean and standard deviation of the given data.

Parameters:

• data: The data to find the mean and standard deviation of.

ltga.Util.median(data, default=0)

Given a data set, return the median value.

Parameters:

• data: The data to find the median of.
• default: If data contains no information, what value should be returned. Defaults to 0.

ltga.Util.moduleClasses(module)

Given a module, return a dictionary mapping string names of that module’s classes to the actual classes. For instance moduleClasses(FitnessFunction)['DeceptiveTrap'] will return the DeceptiveTrap class.

Parameters:

• module: Specifies what module to retrieve classes for.

ltga.Util.randomBitString(length)

Generate and return a random list of 0s and 1s.

Parameters:

• length: The length of the list to be generated.

ltga.Util.saveConfiguration(filename, data, fileMethod=<built-in function open>)

Writes a block of json-able data to the specifed file path.

Parameters:

• filename: The relative path to the file to be written to.
• data: Data that can be converted to a json. IE dictionaries and lists.
• fileMethod: Handler to use to open the file. Defaults to regular open.

ltga.Util.saveList(filename, data, fileMethod=<built-in function open>)

Write out a list of jsons in a more human readable way than saveConfiguration.

Parameters:

• filename: The relative path to the file to be written to.
• data: A list of json-able data to be written
• fileMethod: Handler to use to open the file. Defaults to regular open.

main Module

This module is intended to duplicate the ‘main()’ function found in other languages such as C++ and Java. In order to run an experiment, this module should be passes to your interpreter. In the interest of speed and consistency we suggest that PyPy 1.8.0 with GCC 4.6.2 be used to run this code, although Python 2.7 should be able to handle it correctly.

To see a full description of this modules command line arguments, run ``pypy main.py -h``.

Provided with this code should be the folders experiments, problems, and variants, which contain configuration information require to recreate the experiments performed in the Linkage Tree Genetic Algorithms: Variants and Analysis publication. For example, the following command uses the general experiment setup on the Deceptive Trap problem with 50 dimensions and a trap size of 5. The LTGA variant original+ is used, and the verbose flag is set to increase the output given. Since no population size is specified, it will automatically call bisection to find the minimum population size.

pypy main.py experiments/general.cfg problems/DeceptiveTrap_50_5.cfg variants/originalplus.cfg -v

For any support questions email brianwgoldman@acm.org or dtauritz@acm.org.