Cuckoo Search algorithm

We solve the problem by the means of optimization algorithm known as cuckoo search, elaborated by Xin-She Yang and Suash Deb in 2009. It is inspired by brood parisitism of certain cuckoo species. Candidate solutions are represented by eggs, located in nests. In the version of the algorithm which is used in Posh Wolf, each nest keeps at most one egg. What provides new candidates are the cuckoos, each of them holding one such candidate solution instance.

As soon as initial nests and cuckoos population are generated, optimization process starts. In every single iteration, one cuckoo is randomly chosen and its solution is modified in a random way. Various strategies are employed to this modification. Yang and Deb prove in their article that the optimal strategy are so-called Lévy flights, but we did not follow this path due to implementational difficulties. Posh Wolf uses simple random walk instead - a modified egg (solution) is placed in a randomly chosen nest (if only it surpasses the egg that was placed there before). At the end of each iteration, a number of the worst solution candidates is removed and substituted with randomly generated ones.

Solution quality is estimated using a target function - for flow shop problem it is defined as the total execution timespan. The algorithm aims, of course, at minimizing this value, i.e. at minimizing the time that passes between the first job starts and the very last jobs completes.

The general outline of algorithm, as proposed by Yang & Deb, is as follows:

begin Objective function f(x), x = (x1, ..., xd) T
Generate initial population of n (nest number) host nests xi, i = 1, 2, ..., n
while (t < number of iterations) or (stop criterion) Get a cuckoo randomly (possibly by Lévy flights)
Evaluate its quality/fitness Fi
Choose a nest among n (say, j) randomly
if Fi > Fj
Replace j by the new solution end
With a fixed probability (referred to as abandon probability), a fixed number (referred to as nests to abandon number) of the worst nests are abandoned and new ones are built
Keep the best solutions (or nests with quality solutions)
Rank the solutions and find the current best
end while