Scatter Search Algorithm - YuryENG/Slab-Yard-Optimization GitHub Wiki

Scatter search (SS) is a metaheuristic evolutionary method that may provide good enough solutions for very complex problems with either too many restrictions or the data is too big for the classic genetic algorithm.

SS usually are designed to solve a specific problem and not universal, or generic problems.

The SS algorithm consists of the following steps

  1. Generate an initial set of solutions (heuristic or random)

    • During generation, you need to design this method to guarantee a critical level of diversity. Since there is no mutation that could add missing piece of the solution, it is necessary to include all required data in the initial set.
    • The generation method could be deterministic or random. It might be beneficial to create a heuristic method to generate an initial set of solutions so you start to work with the very good solutions.
    • Tip: You could create about 50 to 100 solutions to provide good diversity.

  2. Design fitness or objective function.

    • Prior to move to the next step, you should already have evaluation method in place.

  3. Design heuristic method to improve solutions.

    • This is the most important part of the SS algorithm. Poorly designed improvement function will lead to larger number of iterations, and larger reference set, and at the end SS algorithm may become very slow losing the advantage over genetic algorithm (GA) ;

  4. After applying improvement method and evaluate fitness again.

  • Sort the improved initial set and pick best solutions.

  1. Create the first reference set.

    • The reference set should be small, somewhere around 20 solutions. The 20 is fairly small number, which is an advantage of SS algorithm. The size, of course, could vary but I would recommend to keep it under 100.

  2. Create new solutions by combining reference solutions (Crossover)

    • It is recommended to generate new solutions within the convex and outside of the convex.
    • Can be totally random or heuristic. Heuristic is the best, if possible. This will reduce the number of iterations to solve the problem, or will improve solutions.
    • When creating new solutions, you should cross every solution with all others. For example if you have solutions 1, 2, 3,4; then cross 1+2, 1+3, 1+4, 2+3, 2+4, 3+4; If the reference size is 20 you will have 190 new solutions. Also you can add combinations such as 1+2+3, 1+3+4, 2+3+;4; and even 1+2+3+4;

  3. Apply method to improve solutions designed in step 3.

  4. Evaluate fitness using objective function to new solutions

  5. Update reference set

  • Order new solutions by fitness, and update reference set only if fitness is better than reference.

Repeat 6 to 9 until reference set does not change anymore; I also prefer to limit the number of possible iterations so the algorithm does not run in an endless loop.

In addition, when the reference set is not being updated, and the solution is not improving, you can add a condition to generate new "initial" set (using method designed in step 1) and add diversity to the reference set.

Methods:

  1. Diversification generation method (initial solutions)

  2. Improvement method

  3. Reference set update method

  4. Subset generation method (crossover)

  5. Objective function

In addition, you can add functions converting from genotype to phenotype

Useful links:

https://view.officeapps.live.com/op/view.aspx?src=http://islab.soe.uoguelph.ca/sareibi/TEACHING_dr/ENG6140_html_dr/outline_W2003/docs/PAPER_REVIEW_dr/Eng614-03-ScatterSearch.ppt

https://www.uv.es/~rmarti/paper/docs/ss8.pdf

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.130.3357&rep=rep1&type=pdf