 |
|
||||||||||
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne graphische Elemente dargestellt. Die Funktionalität der Website ist aber trotzdem gewährleistet. Wenn Sie diese Website regelmässig benutzen, empfehlen wir Ihnen, auf Ihrem Computer einen aktuellen Browser zu installieren. Weitere Informationen finden Sie auf
folgender Seite.
Important Note:
The content in this site is accessible to any browser or Internet device, however, some graphics will display correctly only in the newer versions of Netscape. To get the most out of our site we suggest you upgrade to the latest Netscape.
More information
The well-known single-objective 0/1 knapsack problem is defined as follows: Given a set of items, weight and profit associated with each item, and an upper bound for the capacity of the knapsack. The task is to find a subset of items which maximizes the total of the profits in the subset, yet all selected items fit into the knapsack, i.e., the total weight does not exceed the given capacity [GJ1979] [MT1990].
By transforming the capacity constraint into a second optimization criterion, this problem can be easily formulated as a multiobjective optimization problem [Ste1986]: maximize the profit and minimize the weight simultaneously (there are also other formulations [ZT1998b] [ZT1999a]). Obviously, these two objectives are conflicting and cannot be optimized at the same time: Maximizing the overall profit means putting as many items as possible in the knapsack, minimum weight is achieved when no item is in the knapsack. There is a trade-off between profit and weight. Thus, in contrast to the single-objective 0/1 knapsack problem, there is not a single optimal solutions but rather a set of optimal trade-offs which consists of all solutions that cannot be improved in one criterion without degradation in another. The corresponding set is denoted as Pareto-optimal set (cf. [Ste1986] [Gol1989] [ZT1999a]).
Mathematically, the concept of Pareto optimality can be defined in terms of a dominance relation (with regard to the 0/1 knapsack problem):
Therefore, the optimization goal of the multiobjective 0/1 knapsack problem is to find the set of Pareto-optimal solutions.
Evolutionary algorithm (EA) is used as an umbrella term for a class of computational models that mimic natural evolution in order to solve arbitrary optimization problems. Since the 1970s, several evolutionary methodologies have been proposed, mainly genetic algorithms, evolutionary programming, and evolution strategies [BHS1997]. All these approaches have in common that they process a set of candidate solutions, called population, simultaneously. Using strong simplifications, this set is subsequently modified by the two basic principles of evolution: selection and variation. Selection represents the competition for resources among living beings. Some are better than others and more likely to survive and to reproduce their genetic information. In evolutionary algorithms, natural selection is simulated by a stochastic selection process. Each solution (individual) is given a chance to reproduce a certain number of times, proportionate to their quality. Thereby, quality is assessed by evaluating the individuals and assigning them scalar fitness values. The other principle, variation, imitates natural capability of creating "new" living beings by means of crossing over and mutation.
Although simplistic from a biologist's viewpoint, these algorithms have proven themselves as a general, robust and powerful search mechanism. Moreover, EAs seem to be especially suited to multiobjective optimization because they are able to capture multiple Pareto-optimal solutions in a single simulation run and may exploit similarities of solutions by recombination. Some researchers suggest that multiobjective search and optimization might be a problem area where EAs do better than other blind search strategies [FF1995] [VRUC1997]. Although this statement must be qualified with regard to the "no free lunch" theorems [WM1997], up to now there are few if any alternatives to EA-based multiobjective optimization [Hor1997].
The above Java applet implements a simple evolutionary algorithm to solve the multiobjective 0/1 knapsack problem. Each solution is encoded by a binary string, the length of which corresponds to the number of items available. Each item is assigned a position within the binary string, where 0 means the item is not in the solution, 1 stands for 'the solution contains the corresponding item'. Fitness assignment is performed according to the scheme suggested in [Gol1989]: An individual's fitness is equal to the number of individuals in the population that dominate it. Note that no niching technique such as fitness sharing [Gol1989] is used here, because the focus is on demonstrating the mechanism how a multiobjective EA works. A number of evolutionary approaches have been proposed that are based on Goldberg's ideas (cf. [FF1995] [Hor1997] [ZT1999a]). Finally, genetic operators implemented in the applet are binary tournament selection with replacement, one-point crossover, and bit-flip mutation.
In [ZT1998b] [ZT1999a] several evolutionary techniques, which differ in the fitness assignment scheme and the niching mechanism, are compared on the basis of a slighlty differently defined multiobjective 0/1 knapsack problem.
