I have started programming binary bat algorithm to solve knapsack problem. i have misunderstanding of position concept in binary space :
Vnew= Vold+(Current-Best) * f;
S= 1/ ( 1+Math.exp(-Vnew));
X(t+1) = { 1 S>Rnd , 0 Rnd>=S)
the velocity updating equation use both position from previous iteration (Current) and global best position (Best). In continuous version of BA, the position is real number but in the binary version, position of bat represented by binary number. In Knapsack Problem it means whether the item is selected or not. In the binary version, transfer function is used to transform velocity from real number to binary number. I'm confused whether the position in BBA is binary or real number ? if binary then the (Current-Best) can only be 1 - 0, 0 - 1, 1 - 1, etc. and if real number then how to get the continous representation if no continous equation to update the position (in original BA, the position updating equation is X(t+1) = X(t) + Vnew
Unless you are doing just an "exercise", I discourage you from trying "new" metaheuristics for knapsack. Besides being a widely studied problem, there are very good knapsack specific algorithms. Check David Pissinger's webpage for codes and test instances generators.
Dera Fate Seeker,
I suggest you to see links and attached files in topic.
- Binary bat algorithm
https://dl.acm.org/citation.cfm?id=2662642
- Bat algorithm in discrete optimization: A review of recent applications
rdo.psu.ac.th/sjstweb/journal/39-5/39-5-10.pdf
- Dynamic Inertia Weight Binary Bat Algorithm with Neighborhood Search
downloads.hindawi.com/journals/cin/2017/3235720.pdf
Best regards
Unless you are doing just an "exercise", I discourage you from trying "new" metaheuristics for knapsack. Besides being a widely studied problem, there are very good knapsack specific algorithms. Check David Pissinger's webpage for codes and test instances generators.
I would not call David Pisinger "Pissinger" - he might be upset! ;-)
By the way, why worry about the knapsack problem? It's one of the easiest combinatorial problems; it's pseudopolynomial, hence among the easiest combinatorial problems, and probably not worth develop metaheuristics for. I would not ask a master student to code something like that, but to give a more challenging one among the combinatorial problems out there.
I agree with David and Michael. There are some excellent exact algorithms out there, some of which are capable of solving instances with thousands or even tens of thousands of items to proven optimality. So why bother with a population-based heuristic --- especially a "non-standard" one like the bat algorithm?
By the way, this paper is relevant:
Article Where are the hard knapsack problems?
- Badges
- Science topic
- Similar topics
- Computer Science