Guided genetic algorithm for the multidimensional knapsack problem

Abstract

Genetic Algorithm (GA) has emerged as a powerful method for solving a wide range of combinatorial optimisation problems in many fields. This paper presents a hybrid heuristic approach named Guided Genetic Algorithm (GGA) for solving the Multidimensional Knapsack Problem (MKP). GGA is a two-step memetic algorithm composed of a data pre-analysis and a modified GA. The pre-analysis of the problem data is performed using an efficiency-based method to extract useful information. This prior knowledge is integrated as a guide in a GA at two stages: to generate the initial population and to evaluate the produced offspring by the fitness function. Extensive experimentation was carried out to examine GGA on the MKP. The main GGA parameters were tuned and a comparative study with other methods was conducted on well-known MKP data. The real impact of GGA was checked by a statistical analysis using ANOVA, t-test and Welch’s t-test. The obtained results showed that the proposed approach largely improved standard GA and was highly competitive with other optimisation methods.

1 Introduction

Genetic Algorithm (GA) was first introduced more than four decades ago and it is still widely used in several research applications. GA is mainly used as a stochastic method for solving combinatorial optimisation problems, especially NP-hard problems. In many real-world problems, exact methods fail to find good solutions in a reasonable time. GA has been applied successfully in many real applications as well as various traditional combinatorial problems [3, 20, 30]. Originally, GA was inspired by the biological evolution of living species. Starting with a randomly generated initial population of a set of individuals, GA aims to improve the quality of the successive generations by applying several genetic operators, e.g. crossover and mutation. It is known that GA is relatively simple to implement compared to several other methods, but, is it really able to provide the best solutions? In reality, GA is a stochastic process, so there is no guarantee of optimality, only a large number of generations and individuals can increase the confidence in the obtained solution [28].

Several variants of GA have been proposed during the past few decades, the main aim of many of these variations is to improve the performance of GA and accelerate its convergence in finding an optimal solution. The vast majority of these ideas are either articulated on changing the GA operators such as: crossover and mutation (e.g. one-point, two-point, cut and splice, three parents, uniform, flip bit, Boundary, non-uniform, uniform, etc.), or based on modifying the GA’s evolutionary behaviour, such as: Hybrid GA [14, 26], Parallel GA [29], Genetic Programming [4, 5, 22], etc. An extensive survey of the different variations of GA is available in [8]. The focus here is only on the methods that are related to the guided GA concept.

This paper presents a memetic algorithm—named Guided GA (GGA)— for the Multidimensional Knapsack Problem (MKP). GGA is a memetic algorithm that exploits prior knowledge about the problem data as an intensification strategy to drive the GA evolutionary process of optimisation toward promising areas of the solutions space.

GGA is inspired by two main concepts: the first is the Proximate Optimality concept which assumes that in most cases, the best solutions have a similar structure, in other words, part of the solution may appear in all the best individuals; the second is the Core Concept for the Multidimensional Knapsack Problem CCMKP [23, 27] that provides a mathematical model for ordering the items in MKP based on a compromise between their weights (costs) and their values. GGA uses the output of the CCMKP model as an additional guide for the GA’s evolutionary process. The CCMKP output is used at two stages of the evolutionary process the initialisation and evaluation (fitness function) stages.

The paper is structured as follows: Sect. 2 provides a definition of MKP and the Core concept for MKP (CCMKP). Section 3 gives an overview of the literature review related to the GGA. The proposed algorithm GGA is introduced in Sect.  4. The experimental setup and the parameters tuning are given in Sect. 5. Section 6 presents the conducted experiments and the obtained results. Conclusions and final remarks are drawn in Sect. 7.

2 The multidimensional knapsack problem

This section presents the MKP mathematical model adopted in this work and provides a quick overview on the Core concept for MKP [23].

2.1 Problem definition

The MKP is composed of n items and a knapsack with m different capacities $c_i$ ($i \in \lbrace 1,\ldots , m\rbrace$). Each item j ($j \in \lbrace 1,\ldots , n\rbrace$) has a weight $w_{ij}$ on each capacity i of the knapsack and a value $p_j$. The goal is to pack the items in the knapsack so as to maximise the overall value without exceeding the capacities of the knapsack. The MKP model can be represented by the following integer program:

$$\begin{aligned} \mathbf{{Maximise : }}&\sum _{j=1}^{n} p_j x_j \end{aligned}$$

(1)

$$\begin{aligned} \mathbf{{Subject\, to :}}&\sum _{j=1}^{n} w_{ij} x_j \le c_i \quad i\in \{1\dots m\} \end{aligned}$$

(2)

$$\begin{aligned}&x_j \in \{ 0, 1\} \quad \quad j\in \{1\dots n\} \end{aligned}$$

(3)

A feasible solution X for MKP represents the selected items to be packed. A decision variable $x_j$ represent the item j and is binary where $x_j = 1$ means that item j is packed, and $x_j = 0$ means that item j is not packed in the knapsack. $w_{ij}$ represents the weight of item j on dimension i.

2.2 The core concept for MKP

The Core concept for solving combinatorial and linear programming problems was specifically applied for the knapsack problems by Balas and Zemel [6] and later it was extended to the MKP by Puchinger et al. [23]. The CCMKP calculates an efficiency (score) for each variable (item) in the MKP, the efficiency reflects the expected added value of a variable to the final solution; a high efficiency indicates that the variable is likely to appear in the optimal solution, low efficiency indicates that the variable is unlikely to appear in the optimal or near-optimal solutions, while average efficiency indicate that there is uncertainty about the variable’s added value. Therefore, after being sorted decreasingly according to CCMKP efficiency, the variables are divided into three sets. The variables with high efficiency are fixed to 1 whereas those with low efficiency are fixed to 0 and those with close efficiency represent the Core. Consequently, the Core concept allows reducing the original problem into only the Core problem.

The Core concept is based on an efficiency measure function. The aim is to assign an efficiency value to each variable, according to its significance in producing the optimal solution, in such a way to promote those having the high values and low weights. Several efficiency measures have been used as approximations of the efficiency function, for example, simple efficiency $(e_{j}^{simple})$ [12], scaled efficiency $(e_{j}^{scaled})$, Senju & Toyoda $(e_{j}^{st})$ [27] and general efficiency $(e_{j}^{general})$ [18] as shown in Eqs. 4, 5, 6 and 7–8 respectively.

$$\begin{aligned}&e_{j}^{simple} = \frac{p_j}{\sum _{i=1}^{m} w_{ij}} \end{aligned}$$

(4)

$$\begin{aligned}&e_{j}^{scaled} = \frac{p_j}{\sum _{i=1}^{m} \frac{w_{ij}}{c_i}} \end{aligned}$$

(5)

$$\begin{aligned}&e_{j}^{st} = \frac{p_j}{\sum _{j=1}^{m} w_{ij}(\sum _{l=1}^{n} w_{il} - c_i)} \end{aligned}$$

(6)

$$\begin{aligned}&e_{j}^{general} = \frac{p_j}{\sum _{i=1}^{m} r_i w_{ij}} \end{aligned}$$

(7)

$$\begin{aligned}&r_i = \frac{\sum _{j=1}^{n} w_{ij} - c_i}{\sum _{j=1}^{n}w_{ij}} \end{aligned}$$

(8)

Where $e_j$ : efficiency of item j; $p_j$ : value of item j; $w_{ij}$ : weight of item j on dimension i; $c_i$ : capacity of knapsack on dimension i and $r_i$ : coefficient.

3 Related works

There are several methods related to the guided GA concept in literature, that have been applied to a wide range of applications. For solving the Course Timetabling Problem, Yang and Jat [33] used a memory denoted MEM to record useful information to guide the GA process and improve its performance. MEM is a list of limited size, in which a list of room and time slot pairs is recorded. This information is integrated into the crossover operator of the proposed guided GA. Other researchers used an external structure to guide GA such as [1]. Another approach for guiding the GA is through the use of approximate probabilistic models. In [9] GA is augmented with an approximate probabilistic model to guide the crossover and mutation operators. The probabilistic model is used to estimate the quality of candidate solutions generated by the traditional crossover and mutation operators. It also evaluates the quality of candidate solutions. This estimation enables the crossover and mutation operators to generate more promising solutions.

Specific characteristics of the addressed problem are used to guide the GA search process. The Process Discovery through a Genetic algorithm ProDiGen [31] is a GA that adopts three characteristics of the Process Discovery. The method calculates the precision, simplicity and completeness values of the treated model (i.e. log files of the information system process). These values are integrated into the expression of the GA fitness function to guide the optimisation process. A slowdown-guided GA for the Job Scheduling Problem is proposed in [15]. The proposed model is based on the estimation of the execution slowdown of the tasks which is used to guide the GA search process, the slowdown estimation is used to express the fitness function.

In other versions, a subset of genetic operators is guided. The proximate optimality principle assumes that good solutions have a similar structure. Based on this principle, the guided mutation proposed in [34] uses a probability model inspired by Estimation of Distribution Algorithms (EDA) mutation operator. The generated offspring by this operator is constructed using three components, the best solution found so far, a dynamic probabilistic model and a probability $\beta$. This allows conducting the searching process in promising areas. A guided crossover operator has been proposed in [24]. The crossover operator works by using guidance from all members of the GA population to select a direction for exploration. The first parent is selected by the selection operator. To select the second parent, a metric named $Mutual\_fitness$ is calculated for all the other chromosomes. The chromosome which has the maximum value is selected. One offspring is generated by crossing the parents in a point chosen randomly such that the offspring resulting is the best.

The guidance methods in these GA variants are specific to the addressed problems, they do not propose a formal way to extract the guidance information or are integrated to the optimisation process. Some approaches incorporate a partial guidance using genetic operators.

4 The guided genetic algorithm GGA

The algorithm in this paper is motivated by the observation that in many optimisation real-world problems, some prior information about the components/patterns that are likely to appear in the good solutions could be known. For example, in MKP, it is possible using linear relaxation or the optimal fractional solution [11], to predict some of the items that are likely or unlikely to appear in the good solutions. This study proposes a method for using such prior information as an additional guide for the GA evolutionary process for the MKP problem. By guide, we mean any structure external to GA, which maintains its original composition and is used to drive its search process. This can be through a subset of operators, in order to accelerate the search process and improve the speed of convergence. This section aims to describe the GGA components.

4.1 Chromosome design

The population is composed of a finite number of chromosomes. A chromosome represents a feasible solution to the problem (MKP). As mentioned before, the target in the MKP is to define the subset of items that maximises the total profit. The GGA chromosome consists in the set of items to be added to the knapsack. GGA uses the integer representation, where each gene presents an item ID. The items are coded as integer numbers. A chromosome is formed only by the number of items that it contains. This representation allows reducing the size of the processed data (Fig. 1).

Fig. 1

An example of the chromosome design. The objects (items) packed in the knapsack are represented by their identifiers. The objective function value is calculated by summing the benefit of all the objects while the fitness is calculated according to the fitness function

4.2 Guiding information

The guiding information is based on the work by [23]. The items are sorted decreasingly according to their statistical efficiencies $e_j$ based on the value and the weight ($e_{j}^{simple}, e_{j}^{scaled}, e_{j}^{st}$ or $e_{j}^{general}$). In simple words, the items are sorted based on how likely each item is to appear in high performing individuals, the items at the top of this list are likely to be selected while the items at the bottom are unlikely to appear in good solutions. However, it is important to note here that this list is just an estimate and not a predefined part of the solution. It should also be noted that the greedy heuristic [27], as it is only based on the efficiency sorting, is not an effective solution for the strongly correlated problem instances of MKP [17].

The sorting operation allows favouring items that have a good compromise (i.e. efficiency) between the average value and the overall weight. The efficiency of an item is high if its value is high while its required global capacity is low. The sorted items are split into three sets (Fig. 2) where the value of each variable is assigned as follows:

• $X_1: x_j = 1$ The variables have the best efficiency $e_j$. These variables are most likely to build the best solutions even the optimal solution.

• $Core: x_j =?$ The efficiency values $e_j$ of these items are medium, therefore, it is difficult to predict with confidence whether or not some may appear in the optimal solutions.

• $X_0: x_j = 0$ The variables have a very low efficiency $e_j$, in other words, the value is low or the weight is large or both.

Fig. 2

An example of the guide construction. The objects (items) are sorted according to the efficiency $e_j$

The guide is represented by the variables of $X_1 \cup Core \cup X_0$. The sizes of $X_1$, Core and $X_0$ are determined as follows: Construct a feasible solution by adding the items in order. The item that makes the solution infeasible represents the centre of Core. The size of each part of the guide depends on the size of Core. Setting the size of Core defines the size of the other parts.

4.3 Initial population

The GGA algorithm uses a special initialisation process which allows the GA to make use of the prior information available about the items, and in the same time generates a diverse initial population to ensure exploration of the search space. A chromosome is generated from the items of $X_1$ completed by items generated randomly. In each chromosome, $X_1$ is integrated with a probability $\alpha$. If $\alpha$ is set to zero this means that all the items in each individual are selected randomly, while $\alpha = 1$ means that each individual in the initial population contains all the items of $X_1$. This method allows having an initial population of good quality by integrating $X_1$ and ensures the diversification by adding the rest randomly.

4.4 Fitness evaluation

In GGA, the objective function is different than the fitness function f(j). The first is the value of a solution relative to MKP problem. It is evaluated according to Eq. 1, while the fitness function is defined in a way to guide the search process of GGA. Different formulations of the fitness function are examined by introducing the efficiency $e_j$, $X_1$ and $X_0$.

• A) The fitness function is calculated in the same way as the objective function (Eq. 9):

  $$\begin{aligned} f(j) = \sum _{j = 0}^n p_j x_j \end{aligned}$$

  (9)

• B) The efficiency $e_j$ is introduced in its evaluation according to Eq. 10. Every generation, the fitness value of each chromosome is calculated. The fitness formula allows giving more chance to the chromosome that has a high efficiency to be selected more than the others.

  $$\begin{aligned} f(j) = \sum _{j = 0}^n e_j p_j x_j \end{aligned}$$

  (10)

• C) $X_1$ and $X_0$ are introduced in the fitness measuring; the first as a reward and the second as a penalty (Eq. 11). The aim is to reward (respectively penalise) each chromosome according to its similarity with $X_1$ (respectively $X_0$). Thus allows, at the same time, increasing the chance for the good chromosome to be selected and decreasing it for the bad one.

  $$\begin{aligned} f(j) = \sum _{j = 0}^n p_j x_j + reward - penalty \end{aligned}$$

  (11)

  Where $reward = s_1 * p_z$, $penalty = s_0 * p_z$, $s_1$ and $s_0$ represent the similarity rate with $X_1$ and $X_0$ respectively, and $p_z$ is a significant percentage of the average objective function of the generation (in the experiments $p_z = 0.1$ is used).

• D) The fitness uses the similarity of the chromosome with $X_1$ as follows:

  $$\begin{aligned} f(j) = (1 + s_1) \sum _{j = 0}^n p_j x_j \end{aligned}$$

  (12)

4.5 Genetic operators

GGA uses standard genetic crossover and mutation operators. Tournament selection of size 5 is used as the selection method, the random single point method is applied with a probability $p_c$. For mutation, the mutation by random multiple point bit flip is applied with the probability $p_m$. And finally, a reproduction operator copies a subset of individuals with the probability $p_r$ such as $p_c + p_m + p_r = 1$. The pseudo-code of the GGA is illustrated in Fig. 3.

Fig. 3

Flowchart of the GGA optimisation process

5 Experimental setup and parameters tuning

This section explains the experimental setup and presents the parameter tuning analysis for the GGA algorithm. It is important to note that the concept of guide can be applied to any problem if an effective method for sorting the problem variables exists. For an experimental purpose, and because the chosen sorting method concerns MKP, it is natural to use data from this problem. The test platform is a Toshiba laptop with 4GB RAM capacity and an Intel Core (TM) i5-4200 M 2.5 Ghz CPU. The Java language is used to implement the approach. As for the test data, the well-known Chu&Beasley benchmarks from the OR-Library¹ are used.

Due to the lack of standard methods, trial-and-error is the most common used method for parameter tuning in most heuristic-based optimisation algorithms. We conducted several experiments in order to analyse the performance of the GGA algorithm under different parameter values. For this task the subset of instances OR5 $\times$ 100-0.25 is used. All parameter values are set as shown in Table 1; only the parameter to be measured is changed.

Table 1 Parameters of the GGA used to perform the experiments

Fig. 4

GGA tuning of four parameters by calculating the average distance from the optimum A.D.F.O of 30 runs on the OR5 $\times$ 100-0.25 instances. $\alpha$, number of generation ng, population size ps and the couple crossover/mutation probability (pc, pm) are illustrated in a, b, c and d respectively. (pc, pm) value is in {(0.1, 0.8), (0.2, 0.7), (0.3, 0.6), (0.4, 0.5), (0.5, 0.4), (0.6,0.3), (0.7, 0.2), (0.8, 0.1)}

Fig. 5

The average objective function values range obtained by GGA with different values of efficiency measurement functions and using the dataset: OR5 $\times$ 100-0.25, OR5 $\times$ 250-0.25 and OR5 $\times$ 500-0.25

The optimum values are known for almost all the instances composing the Chu&Beasley dataset. In this work, the Distance From the Optimum D.F.O and the Average Distance From the Optimum A.D.F.O are measured according to the best-known solutions.

Figure 4a, displays how $\alpha$ may affect the GGA D.F.O by changing its value. Based on the value of $\alpha$, the D.F.O ranged from 0.0 to 0.9.

Better results were achieved when the value of $\alpha$ was equal to 0.9. This indicates that using more items of $X_1$ in the initial population individuals improves significantly the quality of the obtained solutions. However, the integration of the whole group (i.e. $\alpha = 1$) reduces the diversity of individuals.

The Average Distance From the Optimum A.D.F.O of the GGA application on the OR5 $\times$ 100-0.25 instances with different values of ng is given in Fig. 4b. The results indicated that when ng was high A.D.F.O decreased and in some cases GGA found the optimal solution. In the next experiments it is considered that $ng = 500$.

The impact of the population size parameter ps on the GGA performance is given in Fig. 4c. The results show that large number of individuals (ps between 100 and 1000) discovered better solutions with A.D.F.O close to the optimum. $ps > 1000$ gave a low value because a large population requires more time to reach high-quality solutions.

The performance of GGA was tested using eight couple values of crossover and mutation probabilities $(p_c, p_m)$. The OR5 $\times$ 100_0.25 instances were executed 30 times and the A.D.F.O results are shown in Fig. 4d. The A.D.F.O significantly improved with increase of the crossover rate and decrease of the mutation rate (Fig. 4d). The first couple gave the best A.D.F.O.

Different functions to measure the efficiency of items are presented in Sect. 2.2. They have been compared as methods for performing the pre-analysis in GGA. For that, the OR5 $\times$ 100-0.25; OR5 $\times$ 250-0.25 and OR5 $\times$ 500-0.25 have been used. The results are illustrated by Fig. 5. From the charts, no significant difference between the functions was observed.

Four formulations of the fitness function are presented in Sect.  4.4. To decide which one gives better results, a comparison has been carried out by applying GGA on the OR5 $\times$ 100-0.25 instances, Table 2 summaries the results. It is shown that GGA with Eq. 10 as fitness function gives the best D.F.O for all the instances.

Table 2 Comparison of the D.F.O obtained by GGA with different expression of the fitnessfunction, using the OR5 $\times$ 100-0.25 dataset

Fig. 6

Comparing the convergence of GGA with GA using the OR5 $\times$ 100-0.25_1 instance

6 Experimental results

In order to provide a comprehensive analysis of the proposed GGA algorithm, this section provides two sets of experiments. The first set evaluates the gain in terms of performance from adding the guiding component to the standard GA. The results are supported with a statistical analysis. This is achieved by comparing the GGA with GA using the same evolutionary parameters (Sect. 6.1). The second set aims to compare the proposed GGA with the state-of-art results reported in the literature (Sect. 6.2).

Table 3 The GGA compared to GA in term of A.D.F.O, Best D.F.O, Worst D.F.O and Average execution Time. The first and the last instance of each group is used

Fig. 7

The objective function rang obtained by GGA and GA within 30 times of run

Table 4 Comparison of GGA to GA, SAHS-SLS, SGHS, HS and greedy algorithms in terms of A.D.F.O and average time

Table 5 Statistics of ANOVA test used to check the GGA performance on GA using OR5 $\times$ 100-0.25_1

Table 6 The ANOVA test results of the GGA performance on GA using OR5 $\times$ 100-0.25_1

Table 7 Statistics of the ANOVA test used to check the GGA performance on GA using Chu&Beasley instances

6.1 Analysis of the GGA performance

A comparison between GA and GGA was conducted to measure the contribution of the data pre-analysis information on the convergence of GA. GGA and GA both were executed 30 times, each run given 200 generations on the OR5 $\times$ 100-0.25_1. The obtained objective function value of each generation was recorded. The average objective function of both approaches is compared in Fig. 6. The curves indicated two search steps: diversification (0-35) and intensification (36-200) in both experiments, GGA outperformed standard GA throughout the evolutionary process. GGA kept a large gap on GA and maintained it throughout the process.

An extended investigation is done using the first and the last instances of each class of the Chu&Beasley benchmarks (i.e. $m\times n-\alpha \_01$, $m\times n-\alpha \_10$, for example: 5 $\times$ 100-0.25_01, 5 $\times$ 100-0.25_10). Table 3 shows a comparison between the performance of GGA against GA. The table shows the Average D.F.O, Best D.F.O, Worst D.F.O and the average processing Time for each algorithm. The results show that GGA outperformed GA on many instances. Also, GGA with high $\alpha$ value performed better than GGA with small $\alpha$ value, the lower and upper whiskers show the worst and best results achieved from 30 independent run times. Figure 7 compares GGA to GA in terms A.D.F.O range. Both methods were applied 30 times on the first instance of each class. Many values were recorded. Figure 7 shows lower, upper and median values obtained by GGA and GA.

6.1.1 Performance on large benchmarks

GGA is evaluated on the Chu&Beasley dataset and compared to: Harmony Search (HS), Self-adaptive Global best Harmony Search (SGHS), Self-Adaptive Hybrid Harmony Search-Stochastic Local Search (SAHS-SLS) [25], GA and greedy sorting (i.e. the feasible solution of adding the items in the sorting order as long as the constraints are verified). Table 4 shows the A.D.F.O and the execution time for all the above algorithms on 270 instances.

Closer inspection of the results shows that for 60% of the data, GGA was able to give better solutions than almost all the other approaches. In addition, the gap improvement from the greedy method after the application of GGA varied from 2% up to 40%. Furthermore, on many instances, GGA results were very close to the optimum. In terms of time, the approach was faster than the other approaches except the GA.

6.1.2 Statistical analysis

Simple statistical analysis was used to investigate whether or not the guidance has a real effect on the GA, hence, ANalysis Of the Variance (ANOVA) pairwise comparison was conducted. It has been supposed that the null hypothesis $H_0$ is: “GGA has not a significant improvement on GA”. The first comparison includes only one instance (Tables 5 and 6) while the second includes all the instances (Tables 7 and 8). The first comparison indicated a $F =152.72$ largely greater than F $crit = 3.99$, and a P-$value = 2.23\times 10^{-18}$ largely lower than $\alpha = 0.05$. The second comparison including all the instances showed a $F = 9.58$ greater than F $crit = 4.03$, and a P-$value = 0.003$ lower than $\alpha = 0.05$. Both results confirm that GA is significantly improved by adding the guidance to its search process. Consequently, the null hypothesis can be rejected.

Table 8 The ANOVA test results of the GGA performance on GA using Chu&Beasley instances

Table 9 Summary of t-test, ANOVA and Welch’s t-test of GGA performance compared to greedy, GA, SAHS-SLS, SGHS and HS on the Chu&Beasley instances

Table 10 Comparison of the results obtained by GGA to some constructive and improvement heuristics

The statistical pairwise comparison of GGA with greedy, GA, SAHS-SLS, SGHS and HS approaches is reported in Table 9. The comparison is performed with t-test, ANOVA and $Welch's$ t-test (also known as t-test with two-sample assuming unequal variances) and using the same data. The obtained t-test values were less than P-$value = 0.05$ except with SAHS-SLS. Also, ANOVA comparison results indicated a P-value less than $\alpha = 0.05$ and F largely greater than F crit except when compared with SAHS-SLS. $Welch's$ t-test obtained a negative t-Stat and a P-value less than $\alpha = 0.05$ except for SAHS-SLS. From all this statistical analysis it may be concluded that the null hypothesis $H_0$ is rejected. Therefore, GGA performs significantly better than the other approaches and is comparative to the SAHS-SLS.

Fig. 8

Comparing the average distance from the optimum A.D.F.O obtained by GGA using the Chu&Beasley instances with nine other algorithms from the literature

6.2 Comparison with the literature

Heuristics could be classified into two groups: constructive heuristics that aim to construct a solution for the treated problem and improvement heuristics which improve a given initial solution. GGA is compared with a set of constructive and improvement heuristics. A brief description of each heuristic is given bellow.

• Constructive heuristics:

• PECH (Primal Effective Capacity Heuristic) [2] is a simple greedy heuristic which incorporates a strategy based on the effective capacity for selecting and adding the items to the knapsack.

• MAG [19] and VZ [32] are algorithms based on the Lagrange multipliers approach.

• PIR [21] is a heuristic based on a dual surrogate relaxation of the MKP supported with a branch and bound method.

• SCE (Shuffled Complex Evolution) [7] is an evolutionary heuristic that iteratively redistributes the population individuals into smaller structures (or complexes) according to their fitness.

• Improvement heuristics:

• CB [10] is a GA augmented with a feasibility and constraint operator which utilises problem-specific knowledge and repair operators which locally improves the offspring.

• NR (P) (New Reduction (Pirkul)) [16], operates a lagrangian dual relaxation on MKP, and proposes a dynamic estimation of the Core size relative to the problem difficulty. The Core is then solved with a greedy heuristic combined with a local improvement phase.

• MCF (Modified Choice Function - Late Acceptance Strategy) [13] is a hyper-heuristic based on heuristics selection function named Modified Choice Function.

The comparison illustrated in Table 10 and Fig. 8 revealed that GGA was competitive with both constructive and improvement methods and has managed to outperform both group of methods on a few instances.

7 Conclusion

The purpose of the current study was to introduce a memetic algorithm named Guided Genetic Algorithm (GGA) for solving the Multidimensional Knapsack Problem (MKP). GGA analyses the problem data based on a greedy algorithm. Useful information about the items of the MKP are extracted and integrated in the initialisation and evaluation operators of a GA. To validate the approach, several experiments were conducted on well-known MKP test data. The research has shown that adding the guidance has significantly improved the performance of the GA and accelerated its speed of convergence. These experiments confirmed that GGA has a real impact on GA performance. One of the more significant findings of this study is that prior-knowledge about the data of a combinatorial optimisation problem could be significantly helpful to accelerate its solving. The future work intends to extend and evaluate GGA on other combinatorial optimisation problems.