ارزیابی کیفیت راه حل مسئله کوله پشتی دو هدفه 0-1 با استفاده از الگوریتم های تکاملی و هیوریستیک

Multiobjective 0-1 knapsack problem involving multiple knapsacks is a widely studied problem. In this paper, we consider a formulation of the biobjective 0-1 knapsack problem which involves a single knapsack; this formulation is more realistic and has many industrial applications. Though it is formulated using simple linear functions, it is an NP-hard problem. We consider three different types of knapsack instances, where the weight and profit of an item is (i) uncorrelated, (ii) weakly correlated, and (iii) strongly correlated, to obtain generalized results. First, we solve this problem using three well-known multiobjective evolutionary algorithms (MOEAs) and quantify the obtained solution-fronts to observe that they show good diversity and (local) convergence. Then, we consider two heuristics and observe that the quality of solutions obtained by MOEAs is much inferior in terms of the extent of the solution space. Interestingly, none of the MOEAs could yield the entire coverage of the Pareto-front. Therefore, based on the knowledge of the Pareto-front obtained from the heuristics, we incorporate problem-specific knowledge in the initial population and obtain good quality solutions using MOEAs too. We quantify the obtained solution fronts for comparison. The main point we stress with this work is that, for real world applications of unknown nature, it is indeed difficult to realize how good/bad is the quality of the solutions obtained. Conversely, if we know the solution space, it is trivial to obtain the desired set of solutions using MOEAs, which is a paradox in itself.

The 0-1 knapsack problem is a well-studied combinatorial optimization problem and much research has been performed on many variants of the problem [1] and [28]. There are single and multiobjective versions of the problem involving one and m-dimensional knapsacks [9] and [15]. Even the single objective case has been proven to be NP-hard. Much research for the single objective case has been performed over the decades and the problem continues to be a challenging area of research. There are several effective approximation heuristics for solving knapsack problems. Ibarra and Kim [12] proved the existence of a fully polynomial time approximation scheme (FPTAS) for the 0-1 knapsack problem. For the single objective m-dimensional knapsack problem a polynomial-time approximation scheme (PTAS) was presented by Frieze and Clarke [10]. Their algorithm makes use of the fact that linear programs can be solved in polynomial time. Erlebach et al. [9] described a practical FPTAS for the multiobjective one-dimensional knapsack problem. They described a PTAS based on linear programming for the m-dimensional knapsack problem also. In general, the multiobjective variant of the problem is harder than the single objective case. The multiobjective optimizer is expected to obtain a set of all representative equivalent and diverse solutions [4] and [8]. The set of all optimal solutions is called the Pareto-front. Objectives to be simultaneously optimized may be mutually conflicting. Additionally, achieving proper diversity in the solutions while approaching convergence is another challenge in multiobjective optimization, especially for unknown problems in black-box optimization. Moreover, the size of the obtained Pareto-front may be exponentially large. Evolutionary algorithms (EAs) are emerging as a powerful black-box tool to solve combinatorial optimization problems. EAs use a randomized search technique with a population of individuals. The genetic operators used by EAs, in general, do not apply any problem-specific knowledge. However, special genetic operators may be designed by incorporating domain knowledge to expedite the search in certain applications. In multiobjective scenario, we aim to effectively obtain a set of diverse and mutually competitive solutions. Some results for solving computationally hard problems empirically using multiobjective EAs (MOEAs) are available in the literature, e.g., m-dimensional knapsack [35], minimum spanning tree [24], partitioning of high-dimensional patterns spaces [22], code-book design [26], communication network topology design [20], and network design [18]. Zitzler and Thiele [35] pioneered the work of solving multiobjective 0-1 knapsack problem using EAs. They formulated the problem using m knapsacks and maximized the profits simultaneously for all the m knapsacks within weight constraints. Subsequently, many other researchers (e.g., [29], [14] and [16]) attempted to solve the same problem-formulation using many other variants of EAs. In this work, we consider another formulation of 0-1 knapsack problem which uses a single knapsack. The considered multiobjective formulation, in this paper, is natural and more realistic, and has many industrial applications manifested by bin-packaging of a single set of items. Though it is expressed using linear equations, it is an NP-hard problem. We solve this problem-formulation using well-known MOEAs and obtain interesting insight in to the EA problem solving strategy for real-world applications whose solution space is not known a priori. For comparison of results obtained using MOEAs, we consider two heuristics and observe that the solutions obtained by the heuristics are much superior for larger problem instances than those obtained by MOEAs. Then, with the aim to get equally good solutions from MOEAs, we take a deeper look into the dynamics of population evolutions and infer that the genetic operators are not strong enough to extend the coverage of the solution-front as obtained by the heuristics. Therefore, we apply this knowledge of the problem domain to improve upon and obtain equally good solutions by MOEAs too. Just obtaining quality solutions for a real-world application using MOEAs is not the main point we wish to highlight through this research monogram. The important point which we stress is that it is difficult to assess the quality of solutions obtained using EAs for the problems whose solution spaces are unknown as the available metrics to measure the quality of solutions in terms of convergence, diversity, and extent for such problems are inadequate in absence of any reference. (An initial version of this work appeared in web proceedings of a conference [25].) The rest of the paper is organized as follows. We describe, in Section 2, a brief review of the issues to be addressed for achieving quality solutions in the context of a MOEA. In Section 3, we include a few definitions pertaining to multiobjective optimization, and formulate the 0-1 knapsack problem which we address in this paper. We include, in Section 4, two fast heuristics which we use to compare the solutions obtained by MOEAs. We present results obtained by the heuristics and MOEAs for uncorrelated knapsack instances in Section 5 and for weakly/strongly correlated knapsack instances in Section 6. Finally, we draw conclusions in Section 7.

In this work, we have taken a seemingly simple instance of a problem which is represented by just two linear equations in a single variable. We have shown, first, that each of the three MOEAs obtained good quality of solutions, both visually as well as quantitatively. The solution fronts were good till we were not aware of the solution fronts obtained from other algorithmic paradigms. For such a simple problem, there existed simple heuristics which obtained apparently the complete solution-front. On comparison, the best solutions discovered by EAs (black-box optimization) were too inferior. If we were not having the solution set obtained by other algorithmic paradigms, we were mislead that EAs had obtained quality solutions. (In this work, we considered three different MOEAs so that we can explore the solution space in the best possible ways, and obtain whatever the best can be obtained; we did not aim to compare the solutions obtained by each of these three algorithms.) However, on knowing the solution space, we embedded this simple knowledge of the solutions in to EAs’ solution-evolving process and easily obtained the complete solution front which is comparable with the best Pareto-front. This is a paradox in itself that for solving a problem per se we need to know the solution space before hand. In a recent research, Ishibuchi and Narukawa [13] observed that good solutions are not always obtained by MOEAs, and proposed use of hybrid approaches. The main agenda that we stress with this work is: can we effectively solve unknown problems using black-box optimization technique of EA, especially in a multiobjective setting? All the metrics for convergence look for some reference set which is mostly not available for harder unknown problems. Most diversity measuring metrics aim at achieving uniformly distributed solution set; if the actual solution set itself is not uniformly distributed the measurements would be poorer. This is the case with some real world applications, e.g., bi-objective spanning tree problem [24].Apparently, the obvious question is: how can one trust on the solutions obtained for real-world applications (RWAs) by such black-box optimization techniques? Can we effectively approximate the quality of solutions for such unknown problems?