An efficient optimizer for the 0/1 knapsack problem using group counseling

Main algorithm

The outline of the GCO algorithm is given in algorithm 1:

Selection of individuals for counseling

The counseling process of each individual continues component-wise in each generation. The new value of each component is obtained from the previous values of the same component using one of the following three strategies:

• Other-members counseling

• Self-belief counseling (use self-best values)

• Self-counseling

To influence a person’s decision, the creators of the original GCO algorithm (Eita & Fahmy, 2010) provide other members with counseling and self-counseling techniques. However, in Ali & Khan (2013), the authors add a third technique called self-belief coaching to help an individual stay current.

Strategy, i.e., self-belief counseling, illustrates an individual’s self-experience in decision-making as we know that an individual’s self-experience influences their decisions. This self-experience tries to limit any possible modification against what they believe based on their personal experience. Therefore, the authors introduce the self-belief counseling strategy into the algorithm to make the counseling process more realistic.

For each component, we generate a random number of self-counseling decisive coefficients (sdc) in the range [0, 1]. If “sdc” is less than self-counseling probability (scp), then we do self-counseling; else, we do self-belief or other-members counseling. Now we generate a random number self-belief counseling decisive coefficient “scdc” in the range [0, 1]. If “scdc” is less than the self-belief counseling probability (scdc), use the self-belief counseling strategy; otherwise, use other member counseling strategies. The self-counseling operator covers the whole range of each component at the start of the search and then uses a nonlinear function to limit the range covered over time. So, self–counseling produces a highly explorative behavior at the beginning of the search, and the influence of the self-counseling operator reduces as the number of generations grows.

The process of computing the new value of each component is given in algorithm 2.

Where, (1)${\displaystyle mdf=max\text{\_}mdf\times {\left(1-\frac{iteration}{gen}\right)}^{tr}}$

Updating individual best position

If the present position leads to the best value, replace the best position; otherwise, do not change the best position. If the current and best positions are the same, then we can randomly select any position.

Example of 0/1 knapsack problem

Assume that there is a knapsack with a size of 15 and many objects of varying weights and values. Within the constraints of the knapsack’s capacity, we wish to maximize the worth of goods contained in the knapsack. Four objects were used (A, B, C, and D). The following are their weights and values as shown in Table 1:

We want to maximize the total value: (2)${\displaystyle \sum _{i=1}^4\left(v_1{s}_1+v_2{s}_2+v_3{s}_3+v_4{s}_4\right).}$ (3)${\displaystyle \begin{array}{c}\text{Maximize}\hfill \\ \sum _{i=1}^4{v}_i{s}_i=\left(25s_1+35s_2+40s_3+55s_4\right){\mathrm{s}}_i\in \left(0,1\right)\hfill \\ i=1,2,\dots ,m\hfill \\ subjectto\hfill \\ \sum _{i=1}^4{w}_i{s}_i=\left(8s_1+6s_2+7s_3+9s_4\right)\le W\hfill \end{array}}$

There are 24 potential subsets of objects for this problem, as shown in Table 2:

The best solution satisfies the constraint while also providing the highest total value. The rows in italics face meeting the condition in our situation. As a result, the best value for the given constraint (W = 15) is 90, which is reached with B and D items.

Representation of the items

To represent all items, we need a table with three rows, item #, weights, and values, as seen in Table 3:

Encoding an individual

An array of the same size represents an individual as the number of elements in the array. The item included in the knapsack is denoted by 1; if not included, indicated by 0, but the total weight is always less than or equal to the knapsack size. For example, the second and fourth items are packed in the knapsack, as shown in Table 4.

A table called “population” is used to represent the entire population. The rows represent the number of individuals, and the columns represent the items that might be carried in the knapsack.

Fitness function

Each individual’s fitness is equal to the sum of the values of selected items for the knapsack.

Termination condition

After achieving the provided criteria (maximum number of generations or maximum assigned profit value), the program will terminate. The whole process is given in Fig. 2.

Experimental setup

MATLAB R2018a has been used to develop the GCO algorithm-based solution to solve the 0/1 knapsack problem. A thorough analysis was performed on the performance impact of the parameters used in the GCO algorithm. The three knapsack problems with different weights are given in Tables 5 to 7. These problems were used for various experiments.

Experiment 1: At the same time, we have changed the number of counselors. Analysis was performed by 1 to 5 counselors. The other settings were left alone and followed (Ali & Khan, 2013) exactly.

Experiment 2: The number of function evaluations was changed from 200 to 1,000, as given in Tables 8 to 10. We changed the population sizes to 10, 20, 30, 40, and 50 while keeping the number of generations equal to 100. The other settings were left alone and followed (Ali & Khan, 2013) exactly.

Experiment 3: The number of function evaluations was changed from 200 to 1,000, as given in Tables 11 to 13. We changed the number of generations to 20, 40, 60, 80, and 100 while keeping the population size equal to 100. The other settings were left alone and followed (Ali & Khan, 2013) exactly.

Experiment 4: In this experiment, we changed the self-belief counseling probability. The results are produced by varying the self-belief counseling probability from 10% to 90%, as given in Tables 14 to 16. The other settings were left alone and followed (Ali & Khan, 2013) exactly.

Experiment 5: In this experiment, we changed the self-counseling probability. The results are produced by varying the self-counseling probability from 10% to 90%, as given in Tables 17 to 19. The other settings were left alone and followed (Ali & Khan, 2013) exactly.

The following subsections explain the findings.

Experiment 1

This experiment sought to determine how the GCO algorithm’s use of counselors affected its ability to solve the 0/1 knapsack problem. We compare the GCO results by varying the number of counselors using three different knapsack problems.

Tables 8 to 10 show that the average and standard deviation of results produced by varying the number of counselors are best when the number of counsellors is equal to 1 for all three knapsack problems. So we should use only one counselor for knapsack problems.

Experiment 2

This experiment was designed to find the impact of the number of function evaluations and population size in the GCO algorithm when solving the 0/1 knapsack problem. We compare the GCO results by varying the number of function evaluations using three different knapsack problems.

Tables 11 to 13 show that the error decreases as the number of function evaluations increases. Because the average and standard deviation of results produced by varying the number of function evaluations are minima when the number of functions is equal to 1,000 for all three knapsack problems, we can say that GCO does not trap knapsack problems at a local optimum.

Experiment 3

This experiment aimed to determine how the GCO algorithm’s function evaluations and generation count affected its ability to solve the 0/1 knapsack problem. We compare the GCO results by varying the number of function evaluations using three different knapsack problems.

Tables 14 to 16 show that the error decreases as the number of function evaluations increases. Because the average and standard deviation of results produced by varying the number of function evaluations are minima when functions are equal to 1,000 for all three knapsack problems, we can say that GCO is not a trap for knapsack problems at the local optimum.

Comparing the results produced in experiments 2 and 3 shows that increasing the number of generations is more effective than a population. So, we use more generations except for the population.

Experiment 4

This experiment aimed to determine how the self-belief counseling probability affected the GCO algorithm’s capacity to solve the 0/1 knapsack problem. Compare the GCO results using three different knapsack problems and varying the probability of trust advice from 10% to 90%.

Tables 17 to 19 show that the average and standard deviation results produced by varying the self-belief-counseling probability are best at 70% for two out of three knapsack problems. So we should use a 70% self-belief-counseling probability for knapsack problems.

Experiment 5

This experiment aimed to determine how the self-counseling probability affected the GCO algorithm’s capacity to solve the 0/1 knapsack problem. We compare the GCO results by varying the self-counseling probability from 10% to 90% using three knapsack problems.

Tables 20 to 22 show that the average and standard deviation of results produced by varying the self-counseling probability is best at 50% for two out of three knapsack problems. So we should use a 50% self-belief-counselling probability for knapsack problems.

A proposed solution for the 0/1 knapsack problem based on GCO is implemented in MATLAB R2018a. GCO advanced parameter settings are initialized as follows:

• The population size is equal to 50;

• The maximum number of generations increases from 20 to 100;

• The number of counselors is equal to 1;

• self-belief-counseling probability is equal to 70%;

• self-counseling probability is equal to 50%;

• Max_mdf is equal to 0.5;

In all experiments, we report results obtained from 100 independent runs. The best results are presented in all cases.

Results

Our experiments use the 0/1 knapsack problem with three different knapsack capacities. Details of the 0/1 knapsack problem are shown in Table 2 to Table 4.

Set the population size to 20 and vary the number of generations from 20 to 100 to generate results. Tables 5 to 7 show the maximum fit found after 100 runs of the algorithm in each generation. The results demonstrate the usefulness of GCO for the 0/1 knapsack problem. They show that for all numbers of function evaluations, it yields results close to those of the dynamic programming approach for all three problems.

Diff = ((Optimal value –GCO Optimal value)/ Optimal value) *100

Various problem sizes are present in the test scenarios to examine the effectiveness of the proposed algorithm. The numbers of items that sizes are 20, 40, 60, and 80 having the size of knapsack 125, 400, 800, and 1,150 respectively. We apply the dynamic programming and GOC algorithm to know the optimal values of the given problem.

In Table 23, the number of items is 20, having a knapsack size of 125. The optimal value is 261 according to the dynamic programming technique, and the result produced by the GCO is also 261. So the difference between dynamic programming and the proposed algorithm is zero.

In Table 24, the number of items is 40, having a knapsack size of 400. The optimal value is 741 according to the dynamic programming technique, and the result produced by the GCO is also 735. So the difference between the dynamic programming and the proposed algorithm is 0.80%.

In Table 25, the number of items is 60, having a knapsack size of 800. The optimal value is 951 according to the dynamic programming technique, and the result produced by the GCO is also 945. So the difference between the dynamic programming and the proposed algorithm is 0.63%.

In Table 26, the number of items is 80, having a knapsack size of 1,150. The optimal value is 1,426 according to dynamic programming techniques, and the result produced by the GCO is also 1,335. So the difference between the dynamic programming and the proposed algorithm is 0.14%.

Table 27 shows that the results produced by the GCO algorithms differ by less than 1% by using the dynamic programming method.