Abstract

W rozprawie zajmujemy się efektywnymi metodami przybliżonego rozwiązywania problemów optymalizacji dyskretnej, a w szczególności algorytmami opartymi na metodzie selekcji klonalnej (SK), należącymi do kategorii sztucznych systemów immunologicznych. Techniki optymalizacji to znaczące pole badań w informatyce, a niektóre ze starszych technik, takie jak algorytmy genetyczne, symulowane wyżarzanie czy przeszukiwanie tabu, stały się metodami klasycznymi. Praca stanowi efekt badań nad algorytmami przybliżonymi dla dwóch NP-trudnych problemów optymalizacji dyskretnej: kolorowania wierzchołków grafu: Graph Coloring Problem oraz marszrutyzacji: Capacitated Vehicle Routing Problem. Zasadniczą część pracy stanowią algorytmy oparte na metodzie SK dla tych problemów oraz eksperymenty komputerowe przeprowadzone na zestawach instancji benchmarkowych, mające na celu porównanie wyników osiąganych przez algorytmy SK z wynikami osiąganymi przy użyciu innych metod przybliżonych. Teza pracy:Algorytmy optymalizacji dyskretnej oparte na metodzie selekcji klonalnej wykazują przewagę nad klasycznymi metodami przeszukiwania lokalnego, oraz są konkurencyjne w stosunku do innych technik ewolucyjnych. Dalsza poprawa parametrów tych algorytmów jest możliwa dzięki zrównolegleniu i hybrydyzacji. Implementacja algorytmu selekcji klonalnej jest łatwiejsza niż dla innych ewolucyjnych technik obliczeniowych ze względu na konieczność zdefiniowania tylko jednego operatora dla konkretnego problemu.

Author (1)