Scatter Search

The scatter search algorithm combines different types of solutions. It is a vector algorithm, which generates new solutions based on the auxiliary heuristic techniques. Scatter search works with set of solutions and reference set of best solutions. Linear combination of vectors from a reference set created a new set. From this set is selected a subset of the best solutions on which are re-applied the auxiliary heuristic techniques.

Description of the scatter search algorithm:

1.	It creates a starting set of solutions.
2.	It applies a heuristic process (in this solution hill climb algorithm) and the result is set of solutions.
3.	Subset of the best solutions from set from step 2 is selected as a reference set.
4.	It applies a randomly two vector linear combination to the reference set. It creates new set from which is selected subset of the best solutions. This subset is the new starting set.
5.	It continues with step 2 if predefined count of iterations is not reached.

Parameters description:

Parameter	Description	Recommended Value
Specimen	Model of solution	Depends on the cost function
First population		[10;1000]
Number of iterations	Depends on the cost function	[10;100]
Size of reference set 1	Stores the best solution	[2;5]
Size of reference set 2	Stores the outermost solutions.	[2;5]
Local optimization parameters
Kind of neighbourhood	This indicates the way of generating neighbors	Cross or Randomly in square
Number of iterations	Determines the number of algorithm steps	[1;10]
Size of neighbourhood	Depends on the cost function constraints	[0.1;2]
Step size	Depends on the cost function constraints	[0.01;2]