Home
This project aims in delivering an optimization system that takes benefits from parallelism.
The project was inspired by: https://github.com/ParaPhraseAGH/erlang-emas. There can be found a general description of the algorithm.
Our implementation is written in Go. To make the system flexible, we divided it into components that can be easily replaced. This wiki briefly describes each component.
This component models an environment that agents can communicate with. Environment component initializes the population, calling method from PopulationFactory. Next, a loop is started. In each iteration we can distinguish three phases:
- Agents tag themselves
- Agents execute their actions
- Stop condition is checked
The environment manages only a general flow and decides, which phase of algorithm should currently be performed. This allows agents to be autonomous and independent. They only communicate with environment to inform about agent's death or birth. They can do this using callbacks (DeleteFromPopulation, AddToPopulation) they receive from the environment. They can also obtain a random agent from environment, calling GetAgentByTag. This callback returns a random agent which is going to perform a specified action.
It publishes a method CreatePopulation which returns agents in number given as argument.
Its method Stop returns boolean that indicates whether the algorithm should already stop. Different implementations of Stopper can model different stop conditions.
-
IterationBasedStopper- this stopper checks if program performed specified number of iterations. If the condition is met, theStopmethod returns true. -
TopFitnessBasedStopper- this stopper checks accuracy of the best acquired solution in every iteration. If the best solution reaches specified level, it ends program execution.
Agent models behaviour of a single, independent actor from the evolutionary algorithm. Each agent has its own ID. Solution models a genotype of an agent and remains constant during whole agent's life. Energy shows vital forces of agent. It is passed to TagCalculator which returns, which action should agent perform, depending on the value of Energy.
Agent can perform 3 types of actions:
DeathReproductionFight
Each action (except Death, which only removes agent from the population) can change the value of agent's energy. When agent reproduces, it looses some energy, which is given to its child. When agents fight, one of them looses a portion of energy, which is transferred to its rival. Operations like Death or obtaining rival are possible thank to callbacks from the Environment described above.
It publishes a method Compare which takes two agents and returns boolean indicating which agent has a better solution. The solution is better, when it corresponds to higher fitness. Computing fitness is a job of FitnessCalculator.
This component represents a solution that agent has. There may be different representations of solution (e.g. one integer, array of integers or bitset), so Solution is a general interface that requires 2 methods that can be implemented in different ways: String and Mutate. A particular solution has an internal solution value and implements methods that make it possible to communicate with this value. String method makes it possible to read the solution value and Mutate method returns a solution that slightly different than the original one.
It calculates fitness corresponding to a particular solution. The type of solution can vary between implementations - see note about Solution component. And even if solution is represented in the same way, it is possible to calculate fitness differently. There are many optimization functions that can be implemented and used inside FitnessCalculator. At the moment, we have 4 different implementations of FitnessCalculator:
-
LinearFitnessCalculator- for Solution that is an integer - simply treats solution value as fitness. -
BitSetFitnessCalculator- for Solution that is a bitset - calculates fitness as the number of ones in the bitset. -
Dejong1FitnessCalculator- for Solution that is a pair of floats. Fitness is calculated as the reversed De Jong 1 function. The goal in De Jong optimization is to find the minimum of the function. In our case the goal is to maximize solution - that is the reason to make the De Jong function reversed. -
RosenbrockFitnessCalculator- for Solution that is a pair of floats. Similar to Dejong1FitnessCalculator, but internally uses Rosenbrock optimization function - De Jong function 2.
TagCalculator is a tool that returns an action tag corresponding to agent's energy. It is fully deterministic, which action should agent perform. Agents with high energy should reproduce, because it means that their solution fits well to the problem. Other agents should fight to decide, which of them is better. Agents without energy should die, because their solution is worse than this of competitors.
This is a general component that publishes methods RandInt() and RandFloat64() that return a random number from the range passed as argument. This component is used in many other components like Envionment (to obtain random agent with a given tag) or Agent (to obtain solution delta between parent and child). Depending on implementations of another components, this component can be used practically everywhere. It is implemented as a singleton.
Go is a new language. Although it borrows ideas from existing languages, it has unusual properties that make effective Go programs different in character from programs written in its relatives. Comparing it to well known existing programming languages Go has very strictly defined conventions of naming, formatting, program construction, and so on. In the results programs are easy for other Go programmers to understand.
Formatting issues are the most contentious but the least consequential. In Go the machine take care of most formatting issues. The gofmt program (also available as go fmt, which operates at the package level rather than source file level) reads a Go program and emits the source in a standard style of indentation and vertical alignment, retaining and if necessary reformatting comments.
Names are as important in Go as in any other language. They even have semantic effect: the visibility of a name outside a package is determined by whether its first character is upper case.
Go programs are organized into packages. A package is a collection of source files in the same directory that are compiled together. Functions, types, variables, and constants defined in one source file are visible to all other source files within the same package. All packages and modules are kept in one place in a system under $GOPATH variable which is by default $home/go. This allow for easy access and management of existing packages and modules in a system and its versioning.
A repository contains one or more modules. A module is a collection of related Go packages that are released together. A Go repository typically contains only one module, located at the root of the repository.
This approach allows for code reusability in very easy way.
For example current project is built as one module named github.com/greg9702/go-emas.
If someone would like to use any package of this module he has to get this module into his system using go get github.com/greg9702/go-emas and at this point module is ready to use.
At this point any package can be used using import github.com/greg9702/go-emas/pkg/<package_name> statement in code. As mentioned above, all functions, variables and structs starting with capital letter can be used.
In our project all components are organized as separate packages. Our goal was to keep as many modules independent from others and make it general purpose packages, to achieve the highest code reusability. Of course it was not possible for all components. Examples for this case are Agent and Environment which depend on many other packages and that is why should be threated as this project related packages.
First attempt was performed using IntSolution and LinearFitnessCalculator components. As stopper component used IterationBasedStopper and set to 100 iterations.
All attempts were performed on 4 agents.
The graph shows the best solution value for each iteration. As expected, in general solution value keeps growing over time. The relation between max solution value and iterations is not linear. That is due to mutation method used, which in this case is solution +/- random value from 0 to solution * MutationRate. As solution value increases, interval also increases. In presented example MutationRate was quite big 0.5.
Next performed series of experiments for components BitSetSolution and BitSetFitnessCalculator. For all attempts vectors of length 30 were used. As stopper component TopFitnessBasedStopper was used with stop value set to 28. (What mean, that program would stop when there will be 29 ones in a vector). Main point of this experiments was to show how different mutation types can affect the results. All plots below show most number of ones in a vectors for each iteration.
For chart readability, the experiments were aborted if the condition was not satisfied after many iterations.
First attempts were performed for mutation, which toggled only one random value from vector.
As we can see, at the beginning value of solution was rising slowly but linearly. Then, when in vectors were more ones than zeros, the speed of solution increase slightly decreased. The final condition was met around 250 iterations.
Next attempts were performed for mutation, which toggled 15 bits at every mutation. (MutationRate * BitSetLength, where MutationRate was set to 0.5)
As we can see, this approach very fast reached 2/3 bits in vector as value one. That is because many elements were toggled at every attempt. But after reaching this level speed of solution increase drastically decreased. That is because in every step half of bits were toggled, which lead to toggling ones to zeros, which was generating worse solutions too often. After 1000+ iterations this method was not able to meet the condition.
Next attempts were performed for mutation method, very similar as previous one, but only 5 bits were toggled each mutation.
As we can see, this approach as the previous one reached ~20 correct bits. But it faced the same problem - the speed of the number of ones in a vector decreased. It still was gaining closer to correct expected value as the previous method, but it was not able to reach it after 1000+ iterations.
Last attempts were performed for hybrid method of the methods from the first method and following ones. There were used Alfa paremeter which was used to adjust number of bits toggled in every iteration. General formula for number of bits toggled every iteration was MutationRate * BitSetLength * Alfa, where MutationRate was set to 0.5 and Alfa was set to 0.9. Each iteration Alfa was decreased by 0.01. (Number of toggles could not be less than 1)
As we can see, this method quite fast was reaching 2/3 of ones bits. Used Alfa parameter allowed to keep reasonable speed of solution grow in later phases.
| Mutation method type | Reached number of ones | Number of iterations |
|---|---|---|
| 1 bit toggle per mutation | 29 | ~250 |
| 15 bit toggle per mutation | 25 | 1000+ |
| 5 bit toggle per mutation | 27 | 1000+ |
| Using Alfa parameter | 29 | ~180 |
Next experiments were performed for Solution consisting of 2 integers. We have implemented 2 FitnessCalculator classes that model 2 well known optimization functions - De Jong's function 1 and Rosenbrock's valley (De Jong's function 2). The visualizations below show how the population's top fitness is growing. The manifold is a visualization of the optimization function and the black path is showing the best solution in the whole population at the moment.
The visualization above shows how the evolution process with De Jong's optimization function 1. We have set MutationRate to 0.5. Similarly to the case of bitset, the population learns quicker at the beggining. Later the progress is not so dynamic. The reason is that the MutationDelta is relative to the solution value on each axis. So the closer the solution is closer to the optimum value in (0, 0), the lower the MutationDelta is. Worth mentioning is, that not every iteration causes top fitness increase - there are some breaks during which nothing happens in the visualization.
Next visualization mechanism is similar, but we have used Rosenbrock's valley as optimization function. The difference is in MutationDelta calculation. In this case we have not used MutationRate and make MutationDelta relative to original solution. Rather we have made MutationDelta a random number from the range +/- MaxMutationDelta. Now there are many small iterations (together 911 iterations to reach required 900'000'000 TopFitnessThreshold with MaxMutationDelta = 50000). We can see that the evolution is not slowing down as in the previous example. On the other hand, the mean progress is rather slow.