7
$\begingroup$

I am working on an implementation of Cuckoo Search for a set covering problem. After reading some papers I cannot understand how choosing a random solution (new cuckoo) works. What I see is that solutions are represented in 2 dimensions and by Lévy flight it picks a random solution.

I am not sure how to implement this. Do I need to generate a lot of solutions and then pick one by Lévy flight? Or generate the solution after the Lévy flight algorithm is executed?

$\endgroup$
  • 3
    $\begingroup$ I edited the English in your question. I hope I got your meaning right. If not, feel free to edit further or to roll back my edit. $\endgroup$ – LarrySnyder610 Jul 13 '19 at 21:11
3
$\begingroup$

The paper in which Yang and Deb introduce Cuckoo Search presents their method as a way to maximise the value of an objective function $f: C\rightarrow \mathbb{R}$, where $C$ is some continuous space (e.g. some area in the plane) and each individual solution $x\in C$ can be represented as a vector. In such a space, a Levy flight is well defined and I think section 2 and 3 of the paper explain fairly clearly how this is done. However, you cannot directly approach to the set cover problem.

The problem here is that set cover is not a continuous optimisation problem, but a discrete one. It is possible to represent a solution set cover as a binary vector $x\in \{0,1\}^{|S|}$ where the $i$-th coordinate of $x$ is $1$ if the set $S_i$ is included in the cover and $0$ otherwise. We cannot perform a Levy flight directly here, because a single jump from a valid solution vector such as $[0,1,0,0]$ often changes into something like $[-3.54,2.3,0.84,1.05]$, for which it isn't clear how to map this to a valid solution.

Gherboudj et al.1 resolve this issue by performing the Levy flights in a continuous space $C$ and then mapping the points in this space to a (valid) binary solution vector to evaluate the solution. For each coordinate of a vector $c\in C$, they use a sigmoid function to get a number $p_i\in [0,1]$ and then create the vector $x$ where the $i$-th coordinate is set to $1$ with probability $p_i$ and $0$ otherwise.

Another way to look at this approach is that here Cuckoo Search is used to search in a continuous space of 'strategies' for the discrete problem, where each strategy is evaluated by the best result it has lead to in the original problem.

Note that this is just one approach to apply Levy flights in a discrete context. There may be better methods in general, or better methods for your specific problem. As with most heuristics, you will have to try and see how well it works.

1: Gherboudj, Amira, Abdesslem Layeb, and Salim Chikhi. "Solving 0-1 knapsack problems by a discrete binary version of cuckoo search algorithm." International Journal of Bio-Inspired Computation 4.4 (2012): 229-236.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Levy flight + sigmoid function not consider restrictions, so Cuckoo Search walk over non solutions? $\endgroup$ – Cristofer Fuentes Jul 22 '19 at 9:49
  • 1
    $\begingroup$ @CristoferFuentes That's what the approach by Gherboudj et al., does, yes. In their approach, the Levy flight/walk and most parts of the Cuckoo Search are over points in $\mathbb{R}^{|S|}$, which does not contain solutions to the actual problem. Only when they want to evaluate a point in $\mathbb{R}^{|S|}$, they map it to the actual solution space $\{0,1\}^{|S|}$. $\endgroup$ – Discrete lizard Jul 22 '19 at 10:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.