Cognitive discrete gravitational search algorithm for solving 0-1 knapsack problem

Abstract

The Gravitational Search Algorithm (GSA) has been proposed for solving continues problems based on the law of gravity. In this paper, we propose a Cognitive Discrete GSA (called CDGSA) for solving 0-1 knapsack problem. The GSA has used a function of time to determine the number of the best particles for attracting others in each time, while our main idea is based on attracting each particle with two cognitive and social components. The cognitive component contains the best position of the particles up to now, while the social component contains the particle with the best position in the whole of the system at the current time and the particles with the best position in the neighborhood. In the other words, the cognitive component is such an appropriate actuator for embedding in the intelligent agents like robots. Such intelligent agent or robot is guided in the right direction with the help of its best previous position. Finally, by introducing discrete version of this idea, the efficiency of the proposed algorithm is measured for 0-1 knapsack problem. Experimental results on some benchmark and high dimensional problems illustrate that the proposed algorithm has gained the better accuracy in comparison of the other similar methods.

Keywords

Cognitive component discrete gravitational search algorithm (DGSA)knapsack problem social component

1 Introduction

The 0-1 knapsack problem is one of the combinatorial optimization problems. It contains a set of N items, each with a weight and a value which want to select a subset of items; so that the total weight is less than or equal to the boundary of the knapsack and the total value is as large as possible [19, 37].

Suppose, W is the boundary of the knapsack (W > 0), vectors w = (w ₁, w ₂, …, w _N) and v = (v ₁, v ₂, …, v _N) stand for the weight and the value of items, where w _i > 0, v _i > 0, 1 ≤ i ≤ N.

The aim is to find a vector x = (x _i, x ₂, …, x _N), where x _i = 0 or 1 (1 ≤ i ≤ N) which satisfies the constraints of Equations (1) and (2): $\sum_{i = 1}^{N} x_{i} \times w_{i} \leq w$ (1) where $Maximize \sum_{i = 1}^{N} x_{i} \times v_{i}$ (2)

If x _i = 1 then the ith item put into the knapsack; if x _i = 0 then the ith item does not put into the knapsack [19, 37].

Knapsack problem has a numerous applications in theory and real world [9] such as: capital budgeting problems [12], loading problems [18], resource allocation [33] and project selection problems [17], also it can be found as a sub problem of the other more general models [7].

Many exact and approximate methods have been developed to solve knapsack problem: exact methods such as dynamic programming [4, 35], branch-and-bound approach [24]; approximate methods such as ant colony optimization [22, 31], genetic algorithm [30, 34], particle swarm optimization [15, 16], simulated annealing [3], harmony search algorithm [11], amoeboid organism algorithm [39], a schema-guiding evolutionary algorithm [40], a soccer league algorithm [32] and a shuffled frog leaping algorithm [26].

Since some new, more difficult 0-1 knapsack problems with high dimensions are hidden in the real world; in addition the available algorithms may lose their efficiency in solving them due to their constraints, therefore the research on this topic is still important.

The Gravitational Search Algorithm (GSA) is one of the meta-heuristic algorithms which has been investigated for solving continues optimization problems based on the law of gravity and mass interactions [14]. Also, it was employed in many other fields such as clustering [2], classification [1] and etc. In the GSA, all particles attract each other with the gravitational force law and all particles move toward the particles with heavier masses. While the heavy particles which correspond to good solutions move more slowly than lighter ones.

In this paper, we propose a new approach for solving 0-1 knapsack problem with introducing a Cognitive Discrete GSA (CDGSA). Our main focus is how to interactions between the particles; in other words, just two components apply the force to each particle instead of that the particle is attracted by all the other particles. Two components are obtained according to the following criteria: the cognitive component (the best position of the each particle up to now), the social component (the best particle in the system at the current time, two of the best neighbors in term of similarity and distance). Furthermore, we introduce an approach for updating the position of the particles, discretely. Experimental results show that the CDGSA is successful in solving 0-1 knapsack problem.

The paper is organized as follows. Section 2 briefly introduces the mathematical model of the GSA and a discrete version of it. Section 3 introduces a cognitive discrete version of the GSA for solving 0-1 knapsack problem. Evaluating the efficiency of the proposed algorithm on some knapsack problems is presented in Section 4. Finally, the paper is concluded by a summary in Section 5.

2 Related works

In this section the GSA and a discrete version of it are introduced.

2.1 Gravitational search algorithm (GSA)

The GSA has been proposed to solve the optimization problems based on the Newtonian gravity law. The GSA has been considered as an artificial system of the particles (in the literature of the GSA [14] is named the masses) which they obey from the Newtonian gravity law. In the GSA, each particle has four attributes: position, inertial mass, active gravitational mass (a measure of the strength of the gravitational field) and passive gravitational mass (measure of the strength of a particle’s interaction with the gravitational field). The position of the particle determines a solution of the problems as well as its gravitational and the inertial masses are indicated by using a fitness function (Note: the GSA assumes that the value of the gravitational and the inertial masses are equal). In each time, the heaviest particle presents an optimum solution and the other particles will be attracted byit [14].

The GSA is formulated in a system with N particles as follows:

In the GSA, the position of the ith particle is shown with Equation (3): $X_{i} = (X_{i}^{1}, \dots, X_{i}^{d}, \dots, X_{i}^{N}) i = 1, 2, . . ., N$ (3) where $X_{i}^{d}$ presents the position of the ith particle in the dth dimension.

Based on the law of gravity , the applied force on the ith particle from the jth particle at time t, is measured by Equation (4): $F_{ij}^{d} (t) = G (t) \times \frac{M_{pi} (t) \times M_{aj} (t)}{R_{ij} + ɛ} \times (X_{j}^{d} (t) - X_{i}^{d} (t))$ (4)

The details of the components of Equation (4) is as follows:

1. G (t) is the gravitational constant at time t. It is a descending function of time and an initial value (G ₀).

2. M _pi and M _aj are the passive gravitational mass of the ith particle and the active gravitational mass of the jth particle, iteratively. The equality of the gravitational and the inertial masses has been assumed by the GSA and they are updated by the following equations: $M_{ai} = M_{pi} = M_{ii} = M_{i} i = 1, 2, \dots, N$ (5) where M _i is calculated according to Equation (6): $M_{i} (t) = \frac{m_{i} (t)}{\sum_{j = 1}^{N} m_{j} (t)}$ (6) where m _i (t) is measured by Equation (7): $m_{i} (t) = \frac{{fit}_{i} (t) - worst (t)}{best (t) - worst (t)}$ (7) In above equation, fit _i (t) represents the fitness value of the ith particle at time t and worst (t) and best (t) are as follow: $best (t) = \max_{j \in {1, 2, \dots N}} {fit}_{j} (t)$ (8) and $worst (t) = \min_{j \in {1, 2, \dots N}} {fit}_{j} (t)$ (9) 3. ɛ is a small constant.

4. R _ij (t) is the Euclidean distance between two particles at time t and it is computed by Equation (10): $R_{ij} (t) = | | X_{i} (t), X_{j} (t) | |_{2}$ (10) Of course, a recent research on the GSA [29] claims that the Equation (4) is independent from the R _ij and the gravitational force directly related to the product of the particle’s masses and the gravitational constant.

In order to achieve a random characteristic to the GSA, the total applied force on the ith particle in the dth dimension is randomly weighted sum of the dth dimension of the forces that are applied from the other particles: $F_{i}^{d} (t) = \sum_{j = 1, j \neq i}^{N} {rand}_{j} \times F_{ij}^{d} (t)$ (11) where rand _j is a random number in the interval [0, 1].

To receive a good compromise between exploration and exploitation, the GSA has just selected a K _best number of particles with bigger mass for applying their force to the others. In order to avoid of trapping in a local optimum, the algorithm must use the exploration at the beginning with a large value for K _best. K _best is a function of time with an initial value (K ₀) that decreases with time; in other words, at the beginning all the particles attract the others, then at over time, K _best decreases linearly and at the end there will be just one particle for applying force to the others. Therefore, Equation (11) can be rewritten as follows: $F_{i}^{d} (t) = \sum_{j \in K_{best}, i \neq j} {rand}_{j} \times F_{ij}^{d} (t)$ (12)

Based on the law of motion , the acceleration of the ith particle in the dth dimension at time t, $a_{i}^{d} (t)$ , is formulated according to Equation (13): $a_{i}^{d} (t) = \frac{F_{i}^{d} (t)}{M_{ii} (t)}$ (13) where M _ii is the inertial mass of the ith particle(Equation (5)).

Also, the next velocity of a particle is considered as a fraction of its current velocity added to its acceleration. So, the velocity of the particle could be updated by Equation (14): $V_{i}^{d} (t + 1) = {rand}_{i} \times V_{i}^{d} (t) + a_{i}^{d} (t)$ (14) where rand _i is a random number in the interval [0, 1].

Finally, updating the particle’s position is formulated by Equation (15) as follow: $X_{i}^{d} (t + 1) = X_{i}^{d} (t) + V_{i}^{d} (t + 1)$ (15)

2.2 Binary gravitational search algorithm (BGSA)

To do combinatorial optimization, a discrete or binary optimization algorithm is required. In recent years, many researchers have tried to present a discrete GSA [13 , 36]. Other optimization methods in continues spaces are converted to discrete one. For example a binary Cuckoo search algorithm is introduced in [10] for feature selection which is a binary optimization problem. Some of the methods use Sigmoid function for binarization or discretization of the algorithms [27].

A quantum-inspired gravitational search algorithm is proposed in [21] for binary encoded optimization problems. Another binary version of the GSA is introduced in [13]. Since the main difference between the continues and the discrete (or binary) GSA is in the relation of the position updating, so the Discrete GSA (DGSA) has 0 or 1 values in each position’s dimension and it updates the position with switching between 0 and 1 values (or vice versa) based on the particle’s velocity. The main idea for updating particle’s position is as follows:

A large absolute value of the velocity in each dimension shows that particle’s position in that dimension is not proper; while a small absolute value of the velocity in each dimension shows that the particle’s position in that dimension is proper. It should be noted that a zero value of the velocity shows that the particle’s position must not be changed and is good.

Based on the above mentioned concepts, the DGSA (or BGSA) uses the Equation (16) (presented in the Table 1) for updating the position; where in Equation (16), rand is a random number in the interval [0,1] and C denotes the complement function.

3 Proposed method

The GSA and a discrete version of it were introduced in the previous section. Reducing the number of interactions between the particles with using a function of time and an initial value (using Equation (12) instead of Equation (11)) was a good way to create a compromise between exploration and exploitation. Indeed, in Equation (12) the K _best number of the particles attract others instead of that all particles attract others.

In our proposed algorithm, the situation of each particle is changed by two type of components: cognitive component (the best position of the same particle that has been achieved so far) and social components (the position of the best particle in the system, the position of the best particles in term of similarity and distance). In other words, the social components have taken from the behavior of the other particles in the system while the cognitive component is like the effect of an actuator of robot or an intelligent agent that selects an appropriate path by using its previous knowledge and the current situation.

On the other hands, in the GSA the position of a particle represents a solution of the problems. The continues problems have a continues relation for updating the position of the particles based on their velocity (Equation (15)). Therefore, to introduce a discrete version of the above idea, we apply a discrete relation for updating the position.

Also in the GSA, the gravitational constant is a function of time. In this paper, we employ two proper functions for updating G value during the algorithm.

Details of the proposed method have been presented at the next subsections:

3.1 Cognitive gravitational search algorithm (CGSA)

In the GSA, the total gravitational force on the ith particle in the dth dimension is calculated according to Equation (12). As regards to perform a good compromise between exploitation and exploration, all particles do not apply the force to others and just the K _best numbers of the best particles just apply the force on the other particles in each time. K _best is a function of time with an initial value (K ₀), so it is considered as the parameter that directly affects on the solutions. Therefore, to increase the speed of the algorithm convergence, we consider four forces apply on the each particle in each time. Although in the GSA only the masses and the gravitational forces between particles are considered for optimization, in our proposed algorithm we consider the particles so that they can memorize their best situation of their self and their neighbors. These particles can be robots with memory and actuators or particles with embedded intelligent software agents. These forces are applied from the cognitive and the social components:

Cognitive component : It contains the best position of each particle until current time (C _best).

Social components:

The particle with the best position in the whole of the system (G _best)

The particle with the best position in the neighborhood of the each particle, in term of:

similarity (S _best)

distance (D _best)

In the following, the more detailed description of the above concepts will be mentioned.

Cognitive component of the ith particle determines the best position of it until the current time, according to Equation (17) (presented in Table 1); where in Equation (17), X _ij represents the position of the ith particle at specific time j and fit _i (t) represents the fitness value of the ith particle at time t.

Also, detecting a particle with the best position at the current time in the system can be calculated by Equation (18) (presented in Table 1).

In order to determine the best particle in the neighborhood of each particle, the size of the neighborhood (s _N) is considered as an essential parameter. In our experiments we investigate random sizes for the neighborhood.

Therefore, the necessary equation for finding a particle with the best position in the neighborhood of the ith particle (in term of the similarity) is considered as Equation (19) (presented in Table 1); where in the Equation (19), s _N is the size of neighborhood around the ith particle and D denotes the dimension size.

In the literature of this paper, the meaning of the similarity neighborhood is as follows: the j ^th particle is a similar neighbor of the i ^th particle when their position is similar in the most of the dimensions.

As well as, a particle with the best position based on the distance in the neighborhood of the ith particle is expressed by Equation (20) (presented in Table 1); where in the Equation (20), ∥X _i (t) , X _j (t) ∥ ₂ determines the Euclidean distance between two particles.

Finally, based on the above comments, Equation (12) can be rewritten as Equation (21) (presented in Table 1).

As a final point, if the applied forces lead to decline the position of the particle in term of fitness then these forces will be ineffective and the particle maintains its situations (such as position, velocity, acceleration and mass). Otherwise, the particle moves toward the better position.

3.2 Cognitive Discrete GSA (CDGSA) for solving 0-1 knapsack problem

In the GSA, the positions of the particles represent the solutions of the problem. Based on its representation (Equation (3)), the value of the particle’s position in each dimension ( $X_{i}^{d}$ ) is dependent to the nature of the problem (continues or discrete).

So, to generalize to the discrete case, the following points should be noted:

The position of the particles in each dimension should be included 0 or 1 values.

The relation for updating the position should be discrete (switching 0 to 1 or vice versa).

Also, based on the concepts of the GSA, the following notes are essential to update the position:

A large absolute value of the velocity determines a high probability of changing the position of the particle from 0 to 1 or vice versa.

A small absolute value of the velocity determines a low probability of changing the position. It should be noted that a zero value of the velocity indicates that the position must not be changed.

Therefore, based on the above points, we employ a function (arc tan(x)) to update the position (Equation (22) instead of Equation (15)) which it illustrates in the Fig. 1 and satisfies all of the above mentioned requirements. Equation (22) is presented in Table 1; where in Equation (22), α is a random number in the interval [0, π /2] and C denotes the complement function.

3.3 Updating gravitational constant

The gravitational constant (G) is a function of the time and an initial value (G ₀). At the beginning, G has large value then it will be reduced to control the search accuracy. Therefore, we employ two following functions (exponential, linear) for updating the gravitational constant in our method as:

$G = (\frac{G_{0}}{iteration}) + 1$ (23)

and $G = (\frac{1 - G_{0}}{max_iteration}) \times iteration + G_{0}$ (24)

The schema of Equation (23) and (24) are illustrated in Fig. 2.

3.4 Evaluating the population

At this point, we propose a fitness function in order to evaluate the population. We know that the 0-1 knapsack problem has a constraint that the weight of the selected items must be less than or equal to the boundary of the knapsack, while the total value of them must be as large as possible. Therefore, we employ Equation (25) (presented in Table 1) for evaluating the population. It calculates the fitness value of the ith particle at time t; where in Equation (25), D denotes the dimension size and α is named a penalty coefficient with a large value to guarantee that the fitness value of the best infeasible solution is lower than of that the worst feasible solution. We noted that in the GSA, the position of the particles represents the solutions.

At the end, the block diagram of the proposed algorithm for solving 0-1 knapsack problem is shown in Fig. 3.

4 Experimental results

In this section, the performance of the CDGSA is studied by different experiments. All the computational experiments are conducted with Matlab R2010b in Intel^® Core^TM2 Duo CPU T6500 @ 2.10 GHz with 4 GB RAM system. At first, we consider the ten small 0-1 knapsack problems which their details (contain item’s weight w, item’s value v, knapsack’s boundary W and optimum solution) have been presented in Table 2.

It should be noted that many authors are employed these problems for evaluating their method. Problems P ₁ and P ₂ are solved by an improved ant colony algorithm [22] while it does not received the optimum solution of them. Problem P ₃ is used with a sequential combination tree algorithm [6] and problem P ₄ is examined by a greedy-policy-based algorithm [38]. Problem P ₅ is analyzed with the information of search-space landscape to search the optimum solution [23] and problem P ₆ is solved in a manner similar to the shrinking boundary method [8]. Problems P ₇ and P ₈ are considered with a nonlinear dimensionality reduction method [25]. Problem P ₉ is used by a DNA algorithm [41] and in the end problem P ₁₀ is adopted from the literature [5]. It should be noted that problems P _i where i = 3, 4, …, 10, have reached to optimum solution in the mentioned paper.

As a first test, the performance of the three algorithms, BGSA [13], CDGSA and DGSA (the proposed approach, but lacks the cognitive component) on the ten test samples (in Table 2) are reported in Table 3. The optimum solution and the best, worst, average and median solution, the standard deviation (std.dev) and average total time (avg.time) during 20 independent runs are presented in Table 3. In the literature of these experiments, the solution is the total value of the selected items in the knapsack; for example, when we say the best solution, it means the total value of the selected items for the particle with the best position. In all the experiments in Table 3, the initial parameters are as follows: maximum iteration number (Max_iteration) is 200, size of the population (pop) is 50 and initial gravitational constant (G ₀) is set to 1000.

From Table 3, it is clear that the CDGSA has a

faster convergence for the large problems, P _i where

i = 1, 2, 5, 6, 8, 10, in the comparison of the BGSA and DGSA. It is due to reduce the number of interactions between particles based on the two components. While the BGSA has sufficient to local optimum solution for many problems (such as P _i, i = 2, 5, 8, 10). Also the DGSA has achieved a similar behavior in many problems (such as P _i, i = 2, 8, 10).

Also, we execute the CDGSA on the other eight knapsack problems to evaluate its performance on the high dimension problems. In these problems, the number of items (N) is as 100, 200, 300, 500, 800, 1000, 1200 and 1500, respectively; while corresponding knapsack’s boundary is according to 1100, 1500, 1700, 2000, 5000, 10000, 14000 and 16000, respectively. Other parameters (the weight of items (w), the value of items (v)) are randomly generated as:

v _i (i = 1, …, N) ∼ rand (50, 100)

w _i (i = 1, …, N) ∼ rand (5, 20)

All results of this experiment have been gained during 10 independent runs. The best, worst, average and median solution and the standard deviation (std.dev) are presented in Table 4.

From Table 4, it is clear that the proposed method (CDGSA) in comparison of the DGSA (CDGSA without the cognitive component) has gained better results to solve the high dimensional 0-1 knapsack problems. This argument is obtained based on the best, worst, average and median solutions and standard deviation.

Also, we offered two different functions for updating the gravitational constant (G). Therefore, we have selected two medium and large problems (P ₂ from Table 3 and P ₁₁ from Table 4) for evaluating the performance of the CDGSA with Equations (23) and (24). We have reported the convergence diagram of this experiment in Fig. 4.

From Fig. 4, it seems that the using Equation (24) (linear relation) for updating the gravitational constant is quickly converged to the optimum solution. While using Equation (23) for updating the gravitational constant provide later convergence.

As a final point, we can conclude that the CDGSA with Equation (24) for updating the gravitational constant has gained good results for solving 0-1 knapsack problems with medium and large size. One of the most manifest features of the CDGSA is that it reaches to optimum solution of the problems in an appropriate time. The remarkable thing is that the performance of the CDGSA improve with the increasing in the dimensions of the problem due to its cognitive and social components. These components reduce the interaction between the particles, also they cause to decrease the total time of solving problems.

5 Conclusion

0-1 knapsack problem is an algorithm of NP-hard problems. To this end a number of algorithms have been developed for solving it. A Gravitational Search algorithm (GSA) is an optimization algorithm based on the law of gravity and mass interactions. In this paper, we introduced a Cognitive Gravitational Search Algorithm (CGSA). We employed a cognitive and social components for each particle in the system. Our original idea was to allocate a memory to each particle to maintain his former best situation. Also, we defined a social component that contains the particles with the best position in the whole of the system and in the neighborhood. Finally, by proposing a discrete version of the our idea (called CDGSA), we tried to solve 0-1 knapsack problem. Experimental results show the efficiency and the accuracy of the proposed method to solve 0-1 knapsack problem.

Footnotes

Acknowledgments

This work has been supported by a Grant from the University of Tehran (No. 29999/01/01).

References

Bahrololoum

Nezamabadi-pour

Bahrololoum

Saeed

2014

A prototype classifier based on gravitational search algorithm

Applied Soft Computing 12 819 825

Hatamlo

Abdullah

Nezamabadi-pour

2011

Application of gravitational search algorithm on data clustering

6th International Conference Rough Sets and Knowledge Technology (RSKT2011) 6954 337 346

Liu

Wang

Han

Wang

Wen

2006

Improved Simulated Annealing Algorithm Solving for 0-1 Knapsack Problem

Proceedings of IEEE the Sixth International Conference on Intelligent Systems Design and Applications (ISDA’06)

Rong

Figueira

Klamroth

2012

Dynamic programming based algorithms for the discounted {0-1} knapsack problem

Appl Math Comput 218 2 6921 6933

2008

Research on the algorithm for 0/1 knapsack problem

Computer and Digital Engineering 5 23 26

2008

On the sequential combination tree algorithm for 0-1 knapsack problem

Journal of Wenzhou University (Natural Science) 29 10 14

Gao

Liu

2013

Modeling and restraining mobile virus propagation

IEEE Trans Mob Comput 12 3 529 541

Fayard

Plateau

1975

Resolution of the 0-1 knapsack problem comparison of methods

Mathematical Programming 8 272 307

Pisinger

1995

Algorithms for Knapsack Problems

Phd Thesis

University of Copenhangen

Denmark

10.

Rodrigues

Pereira

Almeida

TNS

Papa

Souza

Ramos

Yang

2013

BCS: A Binary Cuckoo Search algorithm for feature selection

IEEE International Symposium on Circuits and Systems (ISCAS) 465 468

11.

Zou

Gao

Wua

2011

Solving 0-1 Knapsack problem by a novel global harmony search algorithm

Applied Soft Computing 1 1556 1564

12.

Bas

2011

A capital budgeting problem for preventing workplace mobbing by using analytic hierarchy process and fuzzy 0-1 bidimensional knapsack model

Expert Sys 38 10 12415 12422

13.

Rashedi

Nezamabadi-pour

Saryazdi

2010

BGSA, binary gravitational search algorithm

Natural Computing 9 727 745

14.

Rashedi

Nezamabadi-pour

Saryazdi

2009

GSA, A gravitational search algorithm

Information Sciences 179 2232 2248

15.

2009

An improved particle swarm optimization for knapsack problem

International Conference on Computational Intelligence and Software Engineering

16.

Hembecker

Lopes

Godoy

2007

Particle swarm optimization for the multidimensional knapsack problem

Adapt Natur Comput Algorithms 358 365

17.

Mavrotas

Diakoulaki

Kourentzis

2008

Selection among ranked projects under segmentation, policy and logical constraints

Eur J Oper Res 187 1 177 192

18.

Wascher

Schumann

2007

An improved typology of cutting and packing problems

Eur J Oper Res 183 3 1109 1130

19.

Kellerer

Pferschy

Pisinger

2004

Knapsack Problems

Springer

Berlin

20.

Shamsudin

Irawan

Ibrahim

Abidin

AFZ

Wahyudi

Rahim

MAA

Khalil

2012

A fast discrete gravitational search algorithm, Fourth International Conference on Computational Intelligence, Modelling and Simulation (CIMSIM)

24 28

21.

Nezamabadipour

2015

A quantum-inspired gravitational search algorithm for binary encoded optimization problems

Engineering Applications of Artificial Intelligence 40 62 75

22.

Shi

2006

Solution to 0-1 knapsack problem based on improved ant colony algorithm

IEEE International Conference on Information Acquisition 1062 1066

23.

Yoshizawa

Hashimoto

2000

Landscape analyses and global search of knapsack problems

IEEE Systems, Man and Cybernetics 3 231 2315

24.

Gallardo

Cotta

Fernandez

2005

A hybrid model of evolutionary algorithms and branch-and-bound for combinatorial optimization problems

The 2005 IEEE Congress on Evolutionary Computation 3 2248 2254

25.

Zhao

2007

Nonlinear reductive dimension approximate algorithm for 0-1 knapsack problem

Journal of Inner Mongolia Normal University (Natural Science) 36 25 29

26.

Bhattacharjee

Sarmah

2014

Shuffled frog leaping algorithm and its application to 0/1 knapsack problem

Applied Soft Computing 19 252 263

27.

Shibata

2005

Discretization of series of communication signals in noisy environment by reinforcement learning

Springer

28.

Dowlatshahi

Nezamabadi_pour

Mashinchi

2014

A discrete gravitational search algorithm for solving combinatorial optimization problems

Information Science 258 94 107

29.

Guaci

Dodd

Grob

2012

Why ‘GSA, a gravitational search algorithm’ is not genuinely based on the law of grty

Natural Computing 11 719 720

30.

Gupta

2013

A fast and efficient Genetic Algorithm to solve 0-1 Knapsack problem

International Journal of Digital Application and Contemporary Research 1 6 1 5

31.

Liang

Delong

2001

Ant Colony algorithm for knapsack problem

Computer Application 21 8 56 59

32.

Moosavian

2015

Soccer league competition algorithm for solving knapsack problems

Swarm and Evolutionary Computation 20 14 22

33.

Granmo

Oommen

Myrer

Olsen

2007

Learning automata-based solutions to the nonlinear fractional knapsack problem with applications to optimal resource allocation

IEEE Trans Syst Man Cybern Part B Cybern 37 1 166 175

34.

Chu

Beasley

1998

A genetic algorithm for the multidimensional knapsack problem

J Heuristics 4 1 63 86

35.

Balev

Yanev

Freville

Andonov

2008

A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem

Eur J Oper Res 186 1 63 76

36.

Sudin

2014

A Modified Gravitational Search Algorithm for Discrete Optimization Problem, A Modified Grtational Search Algorithm for Discrete Optimization Problem, IJSSST

15 51 55

37.

Cormen

Leiserson

Rivest

Steinclrs

2002

Introduction to Algorithms

MIT press

38.

You

2007

Study of greedy-policy-based algorithm for 0/1 knapsack problem

Computer and Modernization 4 10 16

39.

Zhang

Huang

Zhang

Mahadevan

Deng

2013

Solving 0-1 knapsack problems based on amoeboid organism algorithm

Applied Mathematics and Computation 219 9959 9970

40.

Liu

2009

A schema-guiding evolutionary algorithm for 0-1 knapsack problem

International Association of Computer Science and Information Technology-Spring Conference 160 164

41.

Zhu

Ren

Ding

2008

DNA ligation design and biological realization of knap-sack problem

Chinese Journal of Computers 31 2207 2214