English
Polski
REPORT A PROBLEM
LINKS
Resource link (short)
http://zasobynauki.pl/zasoby/20933Resource link (repository)
https://id.e-science.pl/records/20933Resource metadata
| Title |
Analiza metod probabilistycznych optymalizacji dyskretnej Title variant: Analysis of probabilistic methods of discrete optimization |
|---|---|
| Persons |
Authors:
Krzysztof Marcin Szkatuła
Partner: Systems Research Institute Polish Academy of Sciences, Warsaw |
| Description |
W pracy sformułowano podstawowe definicje dotyczące oceny złożoności obliczeniowej zadań optymalizacji dyskretnej zarówno w najgorszym jak i w tzw. średnim przypadku. Omówiono różne oceny jakości algorytmów w tych dwóch przypadkach. Wyniki tych teoretycznych rozważań zastosowano dla binarnego zadania załadunku i dla zadania pakowania. Analizie poddano dwa algorytmy dla binarnego zadania załadunku: algorytm zachłanny (greedy algorithm) oraz algorytm najprostszy (blind greedy algorithm). Są to dwa proste i tanie w sensie obliczeniowym algorytmy należące do grupy szeroko stosowanych w optymalizacji dyskretnej algorytmów zachłannych. Algorytmy te różnią się tylko tym, że algorytm zachłanny zawiera wstępną fazę sortowania zmiennych w zadaniu, pominiętą w przypadku algorytmu najprostszego. Przedstawiono przykłady binarnych zadań załadunku, dla których algorytmy te mogą dawać rozwiązania dowolnie odległe od rozwiązania optymalnego. Oznacza to, że z punktu widzenia metodologii najgorszego przypadku oba te algorytmy uzyskują rozwiązania o niskiej jakości. W pracy uzyskano wyniki pokazujące, że przy słabych założeniach dotyczących rozkładów probabilistycznych współczynników zadania algorytm zachłanny, i, co więcej, również jego uproszczona (obcięta) wersja, uzyskuje prawie wszędzie rozwiązanie optymalne zadania. Dla algorytmów: zachłannego oraz najprostszego uzyskano twierdzenia pozwalające obliczyć wartości średnie uzyskiwanych przez te algorytmy rozwiązań jako funkcje rozmiaru zadania, wartości prawej strony ograniczenia oraz rozkładów probabilistycznych współczynników zadania. (Polish) Description in another language: The work formulates basic definitions regarding the evaluation of the computational complexity of discrete optimization problems in both the worst and the so-called average case. Various assessments of the quality of algorithms in these two cases are considered. The results of these theoretical considerations were applied in the case of the binary knapsack and two-dimensional bin-packing problems. Two algorithms for the binary task of loading were analyzed: greedy algorithm and the so-called simplest algorithm (blind greedy algorithm). These are two simple and computationally inexpensive algorithms belonging to the group of greedy algorithms that are widely used in discrete optimization. These algorithms differ only in that the greedy algorithm contains the initial phase of sorting variables in the problem, omitted in the case of the simplest algorithm. Examples of binary knapsack problems are presented, for which both algorithms may provide solutions arbitrarily far from the optimal solution. So, from the point of view of the worst-case methodology, both of these algorithms get low-quality solutions. The dissertation presents results showing that, with weak assumptions about probabilistic distributions of the problem coefficients, the greedy algorithm, and its simplified (truncated) version, obtains almost everywhere the optimal solutions for the problem. For both greedy and simplest algorithms theorems were obtained presenting the average values of the solutions obtained by these algorithms as functions of problem size, values of the right side of the constraint and probabilistic distributions of the problem coefficients. (English) |
| Keywords | "algorytmy dokładne"@pl, "algorytmy przybliżone"@pl, "optymalizacja dyskretna"@pl, "programowanie całkowitoliczbowe"@pl, "optymalizacja"@pl, "analiza najlepszego i najgorszego przypadku"@pl |
| Classification |
Resource type:
thesis Scientific discipline: dziedzina nauk technicznych / automatyka i robotyka (2011) Destination group: scientists, students, entrepreneurs Harmful content: No |
| Characteristics |
Place of creation: Warszawa
Creation time: 1985 Number of pages: 127 Supervisor: Stanisław Walukiewicz Resource language: Polish Location: Warszawa |
| License | CC BY-SA 4.0 |
| Technical information |
Submitter: Anna Wasilewska Availability date: 15-10-2018 |
| Collections | Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN |
Similar resources
Optymalizacja parametryczna z ograniczeniami stanu dla wybranych modeli dynamicznych opisywanych równaniami różniczkowymi cząstkowymi
Krzysztof Piekarski, thesis, Systems Research Institute Polish Academy of Sciences, Warsaw, dziedzina nauk technicznych / automatyka i robotyka (2011)
Optymalizacja planowania produkcji wieloasortymentowej (PD-1973-05)
Krzysztof Cichocki, thesis, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk społecznych / nauki o zarządzaniu i jakości (2018)
Ku metryce dla układów nieholonomicznych. Część 2 - Planowanie toru
Ignacy Dulęba, article, chapter, Wrocław University of Science and Technology, dziedzina nauk technicznych / automatyka i robotyka (2011)
Algorytm optymalizacji procesu dyfuzji stosowanego w produkcji elementów półprzewodnikowych (PD-1975-04)
Wojciech Mały, thesis, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk inżynieryjno-technicznych / automatyka, elektronika i elektrotechnika (2018)
Optimal portfolio choice under a liability constraint (RB-1996-57)
Włodzimierz Smoleński, Leszek Zaremba, article, chapter, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk społecznych / ekonomia i finanse (2018)
Zastosowanie modeli markowowskich do optymalizacji wielopoziomowej pamięci (PD-1975-05)
Helena Dryzek, thesis, Systems Research Institute Polish Academy of Sciences, Warsaw, Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018)