An Improved Genetic Algorithm Based on Adaptive Repair Operator for Solving the Knapsack Problem

Problem statement: Knapsack problem is a typical NP complete problem. During last few decades, Knapsack problem has been studied through different approaches, according to the theoretical development of combinatorial optimization. Approach: In this study, modified evolutionary algorithm was presented for 0/1 knapsack problem. Results: A new objective_func_evaluation operator was proposed which employed adaptive repair function named as repair and elitism operator to achieve optimal results in place of problem specific knowledge or domain specific operator like penalty operator (which are still being used). Additional features had also been incorporated which allowed the algorithm to perform more consistently on a larger set of problem instances. Conclusion/Recommendations: This study also focused on the change in behavior of outputs generated on varying the crossover and mutation rates. New algorithm exhibited a significant reduction in number of function evaluations required for problems investigated.


I. INTRODUCTION
Knapsack problem is a well known and well studied problem in combinatorial optimization being widely used in areas like network planning, network routing, parallel scheduling and budgeting [1] . Mathematically the 0-1 Knapsack problem may be formulated as: where, x j the number of each kind of item is restricted to one or zero indicating its presence or absence in the knapsack. c is the capacity of the knapsack into which n types of objects may be placed. The object of type i has a profit p i and weight w i , associated with it.
Since the Knapsack problem is NP problem, various approaches presently available such as dynamic programming, backtracking, branch and bound etc. are not very useful for solving it. These exact algorithms have a running time that is bounded by an exponential function of length of input data, thus it is very difficult to obtain the exact solutions in case of many large scale knapsack instances which come from practical applications [2] . Hence, for those large scale instances, it has to rely on heuristic algorithms to obtain the near optimal solutions to them.
Amongst the Heuristic algorithms for knapsack problem, genetic algorithm is an effective method to solve the knapsack instances approximately. Genetic algorithm is a search technique to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics [3,4] . They work on the Darwin's principle of natural selection and survival of the fittest. Evolutionary algorithm produces initial population with individuals selected at random. The fitness value of each individual of the population is worked out. If it does not satisfy the goal criterion then it is improved through crossover and mutation operators. Because of the incompatibility between the speed of convergence and the action for searching for the best solution, the simple evolutionary algorithm always behave slowly in convergence, easily in prematurity and plunges into local optimizations. The Evolutionary algorithm with adaptive repair operator is proposed in this study. It leads the search direction of the population by collecting some better individuals from every generation by using the elitism operator and hence results in improving the searching efficiency. Furthermore, the computational cost implications of using adaptive repair function in the algorithm have also been evaluated.
Evolutionary algorithm with adaptive repair operator: A modified algorithm called KNAP-GA is described in this section for solving KP using elitist GAs. The structure of the proposed KNAP-GA is presented in Fig. 1.
Here P represents the population {P 0 , P 1 , P 2 …..P max } where each population comprises of m entries {S 1 , S 2 ,…..S m } and each entry S i = {J k such that 1≤k≤n and J k = {0 ,1}} . Let J = {J 1 , J 2 , J 3 ,……J n } represents the set of unique items that are available . The selected items are represented by value 1 and the not selected ones are represented by value 0. The fitness values of the chromosomes in a population are evaluated based on the profits associated with the items. The best fit chromosome generated from a given population is stored in S * . The crossover and mutation rate are varied to study the impact of varying these operators on the outputs obtained. The working, the characteristics and the need of objective_func_evaluation operator is explained in the preceding section. Each generation of the population yields a set of unique items that would result in maximum profit, thus modifying the solution vector in each step by proceeding towards the best fit solution.
The objective_func_evaluation is a function which evaluates the fitness of chromosomes in the new population. For the Knapsack problem, we calculate the fitness of each chromosome by summing up the benefits of the items that are included in the knapsack, restricting the total weight of the selected items to the capacity of knapsack. If the total weight of the items in the chromosome generated by the crossover and mutation procedure is greater than the capacity of the knapsack then that solution is infeasible and the Repair Operator and the elitism come into play. The Objective_func_evaluation operator is basically a combination of Elitism and Repair operator which is simple to implement and provides us with similar results as obtained with other operators which need complex computations. The outline of the algorithm is given in Fig. 2.

MATERIALS AND METHODS
The test data represents various instances of the 0/1 Knapsack problem as available in the literature [1] . The data sets consist of varying correlation types between profits and weights.

Correlation types:
Data set Uncorrelated (UC) w i = (uniformly) random (1…v) and p i = (uniformly) random (1…v) Data set Weakly Correlated (WC) w i = (uniformly) random (1…v) and p i = w i + (uniformly) random ( -r..r) Data set Strongly Correlated (SC) w i = (uniformly) random (1…v) and p i = w i + r The experiments have been conducted without sorting the items on p i /w i values. Knapsack problem instances were studied on data sets with 100, 250 and 500 items for each of the three correlation types and the three types of Knapsack capacities. However, due to space limitation we are presenting only the case with 250 items.
KNAP-GA was implemented on Pentium-4 (1.7 Ghz) and the results were compared with those obtained by the dynamic programming algorithm. We ran 100 instances of the random sets. Each table entry is the average of 30 runs.

RESULTS
The effects of varying crossover and mutation rates have been studied and is presented in Table 1. When the crossover and mutation rates are both set to 0, the population has obviously contained copies of the strategies randomly generated at the beginning. In other words, with no with no crossover or mutation, all the children looked exactly like one of their parents.
However, on setting crossover rate equal to zero and varying the mutation rate it was observed that the mutation rate of n/100 (where n can be anything between 0-9) yields the best results. Due to space constraint we have shown only 3 instances of the mutation rate i.e., 03, 0.003, 0.70. Experimental results do not show the case when mutation is turned off, because it does not matter much what the crossover rate is when mutation is turned off as mutation is a function which is an integral part of crossover operator and if mutation is off, it yields the same results as when crossover and mutation are set equal to zero.
The second observation worth noticing from Table 1 is that crossover rate between 60 and 70 yields best solution with mutation rate having negligible impact on the output. On examining the three cases, without Elitism and Repair operator, with Repair operator and with elitism and Repair operator, we observed that the mere presence of Repair operator improved the final solution than the one that we were getting in the absence of Elitism and Repair operators and by clubbing the Elitism and Repair operators i.eby using objective_func_evaluation operator ∆, considerable improvement in the final solution has been found.

DISCUSSION
The objective_func_evaluation operator incorporating the new adaptive repair operator has been found to be more cost effective than the existing techniques that have been used in the past to handle chromosomes yielding infeasible solutions. As per the philosophy Richardson et al. [5] , (employing penalty method) infeasible bred strings (or chromosomes) were allowed to join the population however by reducing the string strength by adding penalty terms to the fitness. The farther the string is from feasibility, the higher is the penalty term. In the other approach flags were used to signal the feasibility of final solution. If after several runs on the same problem instance, the flag consistently indicated an infeasible string then one had to either bias the random number generator so as to produce strings in which the number of zeros is greater than the number of one's [6] or use some other heuristic such as greedy one, to generate a solution [7] . Both the methods, the penalty method or using flags increase the computation overhead because in addition to estimating the fitness of chromosomes in a population the track of unfit chromosomes had to be kept by assigning varying penalties and again estimating the strength in each iteration. Whereas if flags were used then one had to keep track of the status of the flag amongst several problem instances and if the same value persists then greedy approach is used thus increasing computational cost multi folds.
The algorithm employing objective_func_evaluation operator ∆ provides a much efficient approach of reaching an optimal solution by using a simple to implement adaptive repair operator which incorporates a strategy of making all bits of the chromosome equal to zero from the point where the fitness exceeds the capacity and by employing elitism to get a small percentage of the best chromosomes from the old population to the new population. Thus the evolutionary algorithm with adaptive repair operator proposed in this study, leads the search direction of the population by collecting the few best individuals from every generation by using the elitism operator. It has resulted in improving the search efficiency.

CONCLUSION
The results obtained with the newly designed genetic operators in algorithm are encouraging, on the practical data sets. Rather than augmenting the genetic algorithm with domain specific knowledge, we have introduced a fitness function employing adaptive repair operator and elitism which is simple to use. In order to further the results, application of the developed KNAP-GA to real life problems, hybridization of local search techniques with other heuristic or meta heuristic techniques for solving the Knapsack problem may be studied. Future work may address whether the proposed algorithm can be applied to other constraint optimization problems such as the maximum clique or the degree constrained minimum spanning tree problems.