Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: knapsack problems

Sortuj według:

Ogranicz wyniki do:

A Specialized evolutionary approach to the bi-objective travelling thief problem

Laszczyk Maciej, Myszkowski Paweł B.

Annals of Computer Science and Information Systems

2019

Vol. 18

47--56

In the recent years, it has been shown that real world-problems are often comprised of two, interdependent subproblems. Often, solving them independently does not lead to the solution to the entire problem. In this article, a Travelling Thief Problem is considered, which combines a Travelling Salesman Problem with a Knapsack Problem. A Non-Dominated Sorting Genetic Algorithm II (NSGA-II) is investigated, along with its recent modification - a Non-Dominated Tournament Genetic Algorithm (NTGA). Each method is investigated in two configurations. One, with generic representation, and genetic operators. The other, specialized to the given problem, to show how the specialization of genetic operators leads to better results. The impact of the modifications introduced by NTGA is verified. A set of Quality Measures is used to verify the convergence, and diversity of the resulting PF approximations, and efficiency of the method. A set of experiments is carried out. It is shown that both methods work almost the same when generic representation is used. However, NTGA outperforms classical NSGA-II in the specialized results.

Wybrane modele i metody optymalizacji alokacji zasobów

Pieńkosz K.

Prace Naukowe Politechniki Warszawskiej. Elektronika

2010

z. 174

3-132

Monografia dotyczy zagadnień związanych z efektywnym rozdziałem szeroko rozumianych zasobów. Prezentowane są metody optymalizacji dla problemów alokacji pojedynczego zasobu, zasobu dostępnego w porcjach o określonej wielkości oraz zestawu różnych rodzajów zasobów. Szczegółowo analizowane są właściwości modeli i algorytmów rozwiązywania dla problemów alokacji formułowanych jako zadania plecakowe, zadania pakowania i rozkroju oraz zagadnienia transportowe i dystrybucyjne. Klasyczne modele alokacji mają głównie charakter dyskretny, wykluczający możliwość częściowej realizacji zapotrzebowań, bądź ciągły z pełną swobodą przydziału zasobu. W pracy szczególną uwagę poświęcono analizie semi-ciągłych problemów rozdziału zasobów i algorytmom ich rozwiązywania. W modelach semi-ciągłych zakłada się, że wielkość przydzielanego zasobu nie może być mniejsza od wartości zadanego parametru β. Tego typu modele były dotychczas badane w literaturze w ograniczonym stopniu, pomimo ich istotnego znaczenia praktycznego i teoretycznego. Stanowią one uogólnienie klasycznych modeli alokacji. Poprzez możliwość wyboru wartości parametru β dostosowanej do rzeczywistych uwarunkowań, pozwalają wyznaczać bardziej elastyczne sposoby gospodarowania zasobami.

The book investigates resource allocation problems. We present models and methods fbr effective allocation of resources among competing activities. Classical discrete optimization models assume that if a resource is allocated to an activity then its demand must be fully satisfied. In continuous models, it is allowed to allocate a very small amount of resource. The main subject of the monograph are semi-continuous models which can be seen as a generalization of the classical discrete and continuous approaches. In semi-continuous models, the amount of resource allocated to an activity cannot be smaller than a given parameter β. In the case when only a single resource is available, the Semi-Continuous Knapsack Problem is formulated and its structural properties are analyzed. As a result, a procedure is developed which enables to fix the optimal values of some variables and transforms the resulting problem of reduced size into the Cardinality Constrained Knapsack Problem. Next, two classes of approximation algorithms are proposed and their performance in the worst case is analyzed. For multi resource allocation problems with uniform resources, the One-Dimensional Semi-Continuous Bin Packing model is formulated. We describe several approximation algorithms for solving such problem and analyze their properties. The results of computational experiments and conclusions relating to the effectiveness of the algorithms are also presented. The Two-Dimensional Bin Packing Problem is discussed only for the discrete case concerning cutting stock process. The application of an approximation algorithm exploiting bottom-up approach and the best-first strategy is described. General multi resource allocation problems are considered in the context of the General Assignment Problem, Transportation Problem and Capacitated Facility Location Problem. The semi-continuous model is discussed mainly for the Transportation Problem. The conditions for existing feasible solutions of semi-continuous model arę formulated. Moreover, an exact algorithm is developed for a special case concerning two resources and sufficiently small β. For the Capacitated Facility Location Problem a Lagrangian heuristic is described and the possibility of its application to the semi-continuous model is discussed.