Our project aims to benchmark the performance of two algorithms: PSO and Genetic Algorithm. For this purpose we've chosen the following functions in a 30-N dimension space:
- Ackley https://www.sfu.ca/~ssurjano/ackley.html
- Levy https://www.sfu.ca/~ssurjano/levy.html
- Rastrigin https://www.sfu.ca/~ssurjano/rastr.html
- Rosenbrock https://www.sfu.ca/~ssurjano/rosen.html
- Schwefel https://www.sfu.ca/~ssurjano/schwef.html
PSO is a computational method that optimizes a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. The computation occurs in a manner that mimics the behavior of swarms when trying to reach for food. The flow of PSO can be described as:
- Initialize a swarm with randomly set particle location
- For each particle, while a stop criteria is not reached:
- Compute the fitness value
- Check whether the current fitness is the best solution yet on particle memory (pbest). If so, update the personal best
- Check whether the current fitness is better than the previous best fitness known to the swarm (gbest). If so, update gbest
- Update speed based on the the new pbest and gbest.
- Update particle location on the function domain.
- Initialize a population of size 300 randomly.
- Select parents by choosing the two best individuals from a random sample of 30 individuals.
- Compute if crossover should occour (90% chance).
- The Crossover consists in randomly selecting 50% of the genes from each parent.
- Two children are generated from the crossover process.
- Compute if a mutation should occour (70% chance).
- 30% of the genes are selected for mutation.
- An offset is generated by using a normal distribution.
- The value of the offset is added to all selected genes.
- The generated children are added to the population and the two worst individuals are removed.
- This process is repeated.
All experiments we performed are a mean of 30 executations of the algorithm.
We have defined a grid with the following parameters for experiments on the functions to be optimized:
- Swarm size [10,20,30]
- Cognitive Coefficient (c1) [0.3,0.5,0.7]
- Social Coefficient (c2) [0.3,0.5,0.7]
The number of epochs was set after experimenting with large values and watching we're convergence would happen. We also set a stopping criteria to activate when a experiment has no improve during a thousand epochs.
The first four functions we experimented on [Ackely,Levy, Rastrigin, Rosenbrock], the algorithm converged to the same point, without variation for every combination of swarm size, cognitive and social coefficient we've explored. The following graphic shows the results on a size 10 swarm with cognitive and social coefficient set to 0.5:
However, for the Schwefel we faced a greater problem complexity. We've tried experimenting with various values for c1 and c2 and also set the experiments running for a greater number of epochs. The constants c1 and c2 seem to have had little to no effect on the convergence value, whereas the swarm size semeed to have a greater influence on the final convergence value.
- Swarm size 10, c1 0.5, c2 0.5
- Swarm size 20, c1 0.5, c2 0.5
- Swarm size 30, c1 0.5, c2 0.5
On the following link you can find a folder containing all the experiments that were performed: https://drive.google.com/drive/folders/1rT8Mxik2OEQFYZBKnQhuK6B7rNwnbeh2?usp=sharing
For all experiments, a limit of 2000 epochs was set.
