Analiza metod probabilistycznych optymalizacji dyskretnej

Widok

Metadane zasobu

Tytuł	Analiza metod probabilistycznych optymalizacji dyskretnej Wariant tytułu: Analysis of probabilistic methods of discrete optimization
Osoby	Autorzy: Krzysztof Marcin Szkatuła Partner: Instytut Badań Systemowych PAN w Warszawie
Opis	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. (Polski) Opis w innym języku: 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. (Angielski)
Słowa kluczowe	"algorytmy dokładne"@pl, "algorytmy przybliżone"@pl, "optymalizacja dyskretna"@pl, "programowanie całkowitoliczbowe"@pl, "optymalizacja"@pl, "analiza najlepszego i najgorszego przypadku"@pl
Klasyfikacja	Typ zasobu: praca dyplomowa Dyscyplina naukowa: dziedzina nauk technicznych / automatyka i robotyka (2011) Grupa docelowa: naukowcy, studenci, przedsiębiorcy Szkodliwe treści: Nie
Charakterystyka	Miejsce powstania: Warszawa Czas powstania: 1985 Liczba stron: 127 Promotor: Stanisław Walukiewicz Język zasobu: Polski Lokalizacja: Warszawa
Licencja	CC BY-SA 4.0
Informacje techniczne	Deponujący: Anna Wasilewska Data udostępnienia: 15-10-2018
Kolekcje	Kolekcja Instytutu Badań Systemowych PAN w Warszawie, Kolekcja e-Biblio IBS PAN

Cytowanie

Skopiowano

Krzysztof Marcin Szkatuła. Analiza metod probabilistycznych optymalizacji dyskretnej. [praca dyplomowa] Dostępny w Atlasie Zasobów Otwartej Nauki, . Licencja: CC BY-SA 4.0, https://creativecommons.org/licenses/by-sa/4.0/legalcode.pl. Data dostępu: DD.MM.RRRR.

Podobne zasoby

Optymalizacja parametryczna z ograniczeniami stanu dla wybranych modeli dynamicznych opisywanych równaniami różniczkowymi cząstkowymi

Krzysztof Piekarski, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, dziedzina nauk technicznych / automatyka i robotyka (2011)

Optymalizacja planowania produkcji wieloasortymentowej (PD-1973-05)

Krzysztof Cichocki, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, 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, artykuł, rozdział, Politechnika Wrocławska, dziedzina nauk technicznych / automatyka i robotyka (2011)

Algorytm optymalizacji procesu dyfuzji stosowanego w produkcji elementów półprzewodnikowych (PD-1975-04)

Wojciech Mały, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, 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, artykuł, rozdział, Instytut Badań Systemowych PAN w Warszawie, Dziedzina nauk społecznych / ekonomia i finanse (2018)

Zastosowanie modeli markowowskich do optymalizacji wielopoziomowej pamięci (PD-1975-05)

Helena Dryzek, praca dyplomowa, Instytut Badań Systemowych PAN w Warszawie, Dziedzina nauk ścisłych i przyrodniczych / informatyka (2018)

Zobacz więcej