Evolutionary Algorithm with Tabu for Global Optimization

Konrad Goszczyński

Abstract

The subject of this thesis is the design of new optimization algorithm which would combine advantages of global, multimodal and local search optimization algorithms. As the basis for such an algorithm the Evolutionary Algorithm was chosen. Into this algorithm some concepts were introduced which were drawn from Tabu Search Algorithm. The tabu region is determined with use of the density based chiśtering algorithm known under the abbreviation DBSCAN. Additionally, the innovative directional mutation operator with a-stable distribution was applied in the designed algorithm. The main purpose of the designed algorithm is to deal with optimization problems containing highly time consuming objective function evaluation. In order to design the algorithm which would meet those expectations, distribution of objective function evaluation trough network is introduced. Presentation of designed algorithm operation, its possibilities and potential is performed by implementation of an application. In order to extend functionality of this application, it is created in such a way that it could be used as teaching aid during the lectures on the optimization methods. Implementation is perfonned with use of Python programming language and PyQt graphical user interfäce libraries.
Diploma typeMaster of Science
Author Konrad Goszczyński II
Konrad Goszczyński,,
- The Institute of Computer Science
Title in PolishAlgorytm Ewolucyjny z Tabu dla optymalizacji globalnej
Supervisor Przemysław Miazga RE
Przemysław Miazga,,
- The Institute of Radioelectronics
Certifying unitFaculty of Electronics and Information Technology (FEIT)
Affiliation unitThe Institute of Computer Science (IN)
Languageen angielski
StatusFinished
Issue date (year)2013
Internal identifierENII-PM.001738
Keywords in PolishAlgorytm Ewolucyjny, Algorytm Przeszukiwanie Tabu, DBSCAN, rozkład a stabilny, QuickWave, obliczenia rozproszone, obliczenia w chmurze, Python
Keywords in EnglishEvolutionary Algorithm, Tabu Search Algorithm, DBSCAN, a-stable distribution, QuickWave, distributed computation, cloud computing, Python
Abstract in PolishTematem tej pracy jest zaprojektowanie nowego algorytmu optymalizacyjnego, który łączyłby zalety algorytmów optymalizacji globalnej multimodalnej oraz lokalnego przeszukiwania. Jako podstawa takiego algorytmu został wybrany Algorytm Ewolucyjny. Do tego algorytmu wprowadzono rozwiązania zaczerpnięte z Algorytmu Przeszukiwania z Tabu. Do określenia obszaru tabu został użyty algorytm klasteryzacji oparty na wyszukiwaniu gęstości znany jako DBSCAN. Dodatkowo w projektowanym algorytmie zastosowany został imiowacyjny kierunkowy operator mutacji z rozkładem a-stabilnym. Głównym przeznaczeniem zaprojektowanego algorytmu jest zastosowanie go przy optymalizacji problemów zawierających czasochłonne ocenę funkcji celu. Aby zaprojektować algorytm, który spełniłby pokładane w nim nadzieje, zostało wprowadzone rozproszenie obliczeń funkcji celu w sieci. Prezentacja zaprojektowanego algorytmu, jego możliwości i potencjalu jest przeprowadzona poprzez stworzenie aplikacji. Aby rozszerzyć funkcjonalność tej aplikacji jest ona stworzona w taki sposób, aby mogłaby zostać użyta jako pomoc dydaktyczna na zajęciach z metod optymalizacji. Implementacja jest przeprowadzona przy użyciu języka programowania Python oraz bibliotek graficznego interfejsu użytkownika PyQt.


Back