Ant colony optimization in dynamic environments
Optimization is the process of finding the maximum or minimum of some objective function. During recent years, a new direction of research has emerged in optimization, with the research focus moving from the conventional static optimization problems to the dynamic optimization problems. Dynamic opti...
Saved in:
| Main Author: | |
|---|---|
| Format: | Thesis |
| Language: | English English |
| Published: |
2010
|
| Subjects: | |
| Online Access: | https://eprints.ums.edu.my/id/eprint/41589/1/24%20PAGES.pdf https://eprints.ums.edu.my/id/eprint/41589/2/FULLTEXT.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Optimization is the process of finding the maximum or minimum of some objective function. During recent years, a new direction of research has emerged in optimization, with the research focus moving from the conventional static optimization problems to the dynamic optimization problems. Dynamic optimization problems differ from the static ones where the optimal solution is dynamic and changes over time. A similar trend can be seen in the application of Ant Colony Optimization (ACO). ACO is an optimization technique inspired by the ants' foraging behavior which optimizes their routes taken to food sources. This thesis is an investigation into the application ' of ACO for solving dynamic optimization problems. The first objective of this study is to identify which ant algorithm performs the best under a dynamic environment. In order to achieve this objective, six ant algorithms namely Ant System (AS), Ant Colony System (ACS), Best-Worst Ant System (BWAS), Elitist Ant System (EAS), Max-Min Ant System (MMAS) and Rank-Based Ant System (RBAS) were implemented to solve a dynamic optimization problem in the form of the dynamic Traveling Salesman Problem (TSP). Three different sizes of the dynamic TSP test sets were used: eil51 (small), lin318 (medium) and d1291 (large). Apart from the size of the optimization problem, how the swapping interval affects the dynamic optimization by the ant algorithms is also investigated. Swapping of cities in the dynamic TSP was done in the early, middle and late stages of the optimization process. A series of 30 test runs were conducted on each dynamic TSP instance and also for each swap condition. The second objective of the research is to investigate the suitability of applying local search algorithms to the best performing ant algorithm from the first objective. For this purpose, three local search algorithms namely 2-opt, 2.S-opt and 3-opt were chosen to be coupled with the ant algorithm in order to solve the dynamic TSP. The last objective of this thesis is to optimize the parameter settings of the best performing ant algorithm with local search. From the experimental analysis, it was found that ACS works best for solving the dynamic TSP compared to the other five ant algorithms. When coupled with a local search technique, a significant improvement can be seen for ACS using the 3-opt local search algorithm. Lastly, it was also found that different optimal parameter settings were required for solving the different sizes of the dynamic TSP problems. |
|---|