Simple implementation of genetic algorithm. Shared project to practice group collaboration.
Authors: Paweł Dąbrowski, Janusz Brodacki, Kamil Surowiec.
Algorithm Working Principle
Goals
Development Progress
Workflow
Branch naming convention
Project history
Code structure
- First Step
- All Genes are initialized
- Fitness is counted for each gene and assigned to it
- Perform evolution Step
- CrossoverHandler merge genes into pairs based on their fitness, and then crossover perform cross method on these genes
- Mutator check if a mutation occurs, if yes then perform proper mutation
- Evaluator count new fitness for each gene and assign them new value of fitness
- SolutionFinder checks final condition, if final conditions are not met then perform evolution step is repeated
- working in small group
- practicing git branching, issues and documentation
- using TDD
We are working to develop functioning Stage 16 on 14.04.2021 - builder for GenePoolService.
- We use separate branches to develop each stage of project.
- Each stage consist of at least three steps: documentation, tests and implementation. They are developed in this order and depend on each other.
- Documentation describes the task.
- Tests are our specification of product and we want them to describe acceptance conditions for implementation.
- Implementation is developed at the end of the stage and it should pass all of the tests before release.
- On each stage we put tests before implementation. If during implementation step it appears, that tests are not sufficient, we extend tests before continuing.
- Each task in project is developed based on an Issue. If there is no Issue for your work - create one. Use Issues to report bugs or possible enhancements also.
- When stage is finished, we release it, by pulling current branch to main.
- Each task is developed on separate branch - naming conventions is explained below.
- Production code is release on main
- Stage branches are formed as dev-sX, where X is number of development stage.
- Task branches follow this pattern: X-Label, where X is number of an Issue and Label is short description.
| Stage | Description |
|---|---|
| 1 | Creation of Gene class, which is a fundament of our model. Adding RandomProvider to test creation of random genes. |
| 2 | Creation of Evaluator interface and its implementation. |
| 3 | Documentation refactor, added section Code Structure. Gene value is now single char instead of an array. |
| 4 | Creation of CrossoverService to provide gene values recombination. Another Gene docs refactor. |
| 5 | Creation of MutatorService to provide mutation of gene values after cross recombination. |
| 6 | Creation GenePool as container for Gene objects. It uses dependencies to perform evolution during each generation. |
| 7 | Working on GenePool, improving tests for Mutator and Evaluator dependencies and first implementation of GenePool. |
| 8 | Work on GenePool, improve tests for Mutator and Evaluator to use ArgumentCaptor. BitwiseUtils exception refactor. |
| 9 | Added CrossoverHandler and SolutionFinder to GenePool. Create table of content for documentation. |
| 10 | Working on GenePoolService and refactor of GenePool and its test. |
| 11 | Working on first working app. Start with integration tests for whole app. |
| 12 | Working on first working app. Create solve method in GenePool to make integration test work correctly |
| 13 | Working on improve integration tests. Add new getSolve method with new functionalities. |
| 14 | Create factory classes for Mutator, CrossoverService. |
| 15 | Working on builders for GenePool and GenePoolService. |
class Gene
private final RandomProvider
private char value
private float fitness
private void generateValue()
// getters and setters for value and fitness
Gene has two fields char value and float fitness, generateValue() method use RandomProvider interface to randomly generate char value. It has also getters and setters for its fields: value and fitness.
interface Evaluator
void setFitness(Gene)
Evaluator has method setFitness(Gene) to calculate and assign calculated value of fitness to gene field fitness. Evaluator count fitness only by comparing two char. One current value in gene with target char Target char should be passed to Evaluator as argument in constructor. There are two implementations of Evaluator: LogarithmicEvaluatorImpl and MaxDeltaEvaluatorImpl.
Formulas for setFitness() method:
LogarithmicEvaluatorImpl: 1 / (1+log10(1+delta))
MaxDeltaEvaluatorImpl: (65535 - delta) / 65535
where:
delta - Absolute value of difference between target and current char
65535 - value equal to Character.MAX_VALUE
CrossoverHandler is responsible for sorting genes according to their fitness descending, and picking pair of genes starting from the highest fitness and pass this pair as an argument to cross method from a crossover. Each pair of a gene must be put to the cross method only once for each generation. CrossoverHandler uses CrossoverService and its cross method
class CrossoverHandler
private CrossoverService crossoverService
List<Gene> fitnessSort(List<Gene> genes)
List<Gene> performCross()
CrossoverService, an interface responsible for changing gene values (mix their values) to increase their chances to match with optimal solution during next generation.
interface CrossoverService
void cross(Gene g1, Gene g2)
Multiple implementations (strategies) describe how provided Gene objects should be changed:
| Strategy | gene 1 | gene 2 |
|---|---|---|
| MixingHalvesCrossoverServiceImpl | 2nd byte copied from g2 | 2nd byte copied from g1 |
| OddBitsCrossoverServiceImpl | odd bits copied from g2 | odd bits copied from g1 |
| EvenBitsCrossoverServiceImpl | even bits copied from g2 | even bits copied from g1 |
| BitPairCrossoverServiceImpl | even bit pairs copied from g2 | even bit pairs copied from g1 |
MutatorService an interface with single method mutate, responsible for mutating gene values. Based on given strategies selected bits changing its value in order to faster find target.
Classes that implementing MutatorService have additional mutationChance float field that is set in setter (takes random value from 0 - 1) and represents probability of mutation in percent (0 - 100%). Set in seter because in each generation of Gene mutationChance can be different.
Classes imlementing MutatorService use RandomProvider and BItwiseUtils to mutate gene in a proper way.
interface MutatorService
void mutate(Gene gene)
Two implementations (strategies) describe how provided gene object is mutated.
| Strategy | Description |
|---|---|
| SingleMutator | take one bit from random position (0 - 15) and then assign opposite value for this bit (0 or 1) |
| MultipleMutator | first take random number that represents number of bits to mutate (0 - 15), then in a loop take one bit from random position (0 - 15) and assign opposite value to this bit (0 or 1). We allow that the same bit can change many times. |
class SolutionFinder
private char target
boolean findSolution(List<Gene>)
SolutionFinder is a class responsible for checking if any gene has value equal to target. This checking is done by evoking findSolution method
class GenePoolService
private final RandomProvider randomProvider
private final MutatorService mutator
private final Evaluator evaluator
private final CrossoverHandler crossoverHandler
private final List<Gene> poolOfGenes
void makeMutation()
void evaluateFitness()
void makeCross()
void getPoolOfGenes()
GenePoolService class carry all logic responsible for gene evolution by evoking methods in proper order.GenePoolService is also a container for genes.
Mutator and Evaluator dependencies are used by methods makeMutation() and evaluateFitness() and perform operations for each gene in poolOfGenes.
CrossoverHandler is used to perform cross method of pair of gene in proper way. Takes pair of gene in descending order according to fitness.
For now it is responsible for:- performing mutation by evoking makeMutation()
- performing cross by evoking makeCross()
- updating genes by evoking evaluateFitness()
Builder for GenePoolService returns object with default configuration. Optional parameters are taken to specify configuration.
| builder method | option | instance |
|---|---|---|
| mutator | MutatorEnum.SINGLE | SingleMutator |
| mutator | MutatorEnum.MULTIPLE | MultipleMutator |
| mutator | MutatorEnum.DEFAULT | SingleMutator |
| mutator | MutatorEnum.ZERO | SingleMutator |
| mutationChance | float given | mutationChance == given |
| mutationChance | MutatorEnum.ZERO | mutationChance == 0f |
| mutationChance | MutatorEnum.* | mutationChance == DEFAULT |
| evaluator | EvaluatorEnum.MAX_DELTA | MaxDeltaEvaluatorImpl |
| evaluator | EvaluatorEnum.LOG | LogarithmicEvaluatorImpl |
| evaluator | EvaluatorEnum.DEFAULT | MaxDeltaEvaluatorImpl |
| target | not set | evaluatorTarget == '0' |
| target | not set | solutionFinderTarget == '0' |
| target | char given | evaluatorTarget == given |
| target | char given | solutionFinderTarget == given |
| crossover | CrossoverEnum.DEFAULT | BirPairCrossoverServiceImpl |
| crossover | CrossoverEnum.BIT_PAIR | BitPairCrossoverServiceImpl |
| crossover | CrossoverEnum.EVEN_BITS | EvenBitsCrossoverServiceImpl |
| crossover | CrossoverEnum.MIXING_HALVES | MixingHalvesCrossoverServiceImpl |
| crossover | CrossoverEnum.ODD_BITS | OddBitsCrossoverServiceImpl |
class GenePool
private GenePoolService
private final List<Gene> poolOfGenes
private int generation
List<Gene> getPoolOfGenes()
int getGeneration()
setGeneration(int)
void performEvolution()
int solve()
List<Gene> getSolve()
GenePool class is a container for pool of genes and is responsible for performing evolution by evoking GenePoolService methods.
GenePool has performEvolution method that evokes all cycle of evolution and this cycle is repeated until a solution is found.
solve method is responsible for searching the target, as a result method returns number of generation in which solution (target) was found.
getSolve method is returning list of genes which are solution of given genepool
For now it is responsible for:- incrementing generation count
- performing evolution until a solution is found
Builer to fabricate preconfigured GenePool objects.
| builder method | option | instance |
|---|---|---|
| poolSize | int given | genePoolSize == given |
| generation | int given | generaton == given |
| genePoolService | GenePoolService instance | GenePoolService instance |
Default values:
poolSize == 100
generation == 0
genePoolService == genePoolServiceBuilder default
interface RandomProvider
int getInt(int bound)
float getFloat()
RandomProvider is a helper class for mocking, to enable tests for classes taking random input.
class BitwiseUtils
int getBit(int number, int index)
int setBit(int number, int index, int value) throws IllegalArgumentException
int getByte(int number, int index)
int setByte(int number, int index, int value) throws IllegalArgumentException
BitwiseUtils provides methods to read and write bits and bytes from given number.
index is a position of bit or byte (starting with 0 for least significant bit)
value is target value of bit (0 or 1) or byte (0 to 255)
throws IllegalArgumentException when index is negative number or value is out of expected range.
class MutatorFactory
MutatorService getMutator()
MutatorService getMutator(OPTION)
MutatorService getMutator(float mutationChance, OPTION...)
MutatorFactory is a factory returning MutatorService object. Evoked without arguments it returns default configuration, but can take also optional PARAMS and float mutationChance.
Default values are:
mutationChance == 0.05f
MutatorService implementation => SingleMutator
| OPTION | |
|---|---|
MutatorEnum.ZERO |
mutationChance = 0, SingleMutator |
MutatorEnum.SINGLE |
mutationChance = 0.05, SingleMutator |
MutatorEnum.MULTIPLE |
mutationChance = 0.05, MultipleMutator |
MutatorEnum.DEFAULT |
mutationChance = 0.05, SingleMutator |
When evoked getMutator(float mutationChance, OPTION) mutationChance is taken from first argument and overrides information from OPTION.
When getMutator(float X, MutatorEnum.ZERO) and X is other than zero throws IllegalArgumentException.
class CrossoverServiceFactory
CrossoverService getCrossoverService()
CrossoverService getCrossoverService(OPTION)
CrossoverServiceFactory is a factory returning CrossoverService instance. Evoked without arguments it returns default configuration.
| OPTION | description |
|---|---|
| CrossoverServiceEnum.DEFAULT | BirPairCrossoverServiceImpl |
| CrossoverServiceEnum.BIT_PAIR | BitPairCrossoverServiceImpl |
| CrossoverServiceEnum.EVEN_BITS | EvenBitsCrossoverServiceImpl |
| CrossoverServiceEnum.MIXING_HALVES | MixingHalvesCrossoverServiceImpl |
| CrossoverServiceEnum.ODD_BITS | OddBitsCrossoverServiceImpl |
class EvaluatorFactory
Evaluator getEvaluator(char target)
Evalaator getEvaluator(char target, OPTION)
EvaluatorFactory is a factory returning Evaluator object. Evoked without OPTION argument returns default configuration.
| OPTION | description |
|---|---|
| EvaluatorEnum.DEFAULT | MaxDeltaEvaluatorImpl |
| EvaluatorEnum.MAX_DELTA | MaxDeltaEvaluatorImpl |
| EvaluatorEnum.LOG | LogarithmicEvaluatorImpl |