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...

Full description

Saved in:

Bibliographic Details
Main Author:	Chen, Fei Huang
Format:	Thesis
Language:	English English
Published:	2010
Subjects:	QA440-699 Geometry Trigonometry Topology
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!

id	my-ums-ep.41589
record_format	uketd_dc
spelling	my-ums-ep.415892024-11-26T05:25:52Z Ant colony optimization in dynamic environments 2010 Chen, Fei Huang QA440-699 Geometry. Trigonometry. Topology 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. 2010 Thesis https://eprints.ums.edu.my/id/eprint/41589/ https://eprints.ums.edu.my/id/eprint/41589/1/24%20PAGES.pdf text en public https://eprints.ums.edu.my/id/eprint/41589/2/FULLTEXT.pdf text en validuser masters Universiti Malaysia Sabah Sekolah Kejuruteraan dan Teknologi Maklumat
institution	Universiti Malaysia Sabah
collection	UMS Institutional Repository
language	English English
topic	QA440-699 Geometry Trigonometry Topology
spellingShingle	QA440-699 Geometry Trigonometry Topology Chen, Fei Huang Ant colony optimization in dynamic environments
description	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.
format	Thesis
qualification_level	Master's degree
author	Chen, Fei Huang
author_facet	Chen, Fei Huang
author_sort	Chen, Fei Huang
title	Ant colony optimization in dynamic environments
title_short	Ant colony optimization in dynamic environments
title_full	Ant colony optimization in dynamic environments
title_fullStr	Ant colony optimization in dynamic environments
title_full_unstemmed	Ant colony optimization in dynamic environments
title_sort	ant colony optimization in dynamic environments
granting_institution	Universiti Malaysia Sabah
granting_department	Sekolah Kejuruteraan dan Teknologi Maklumat
publishDate	2010
url	https://eprints.ums.edu.my/id/eprint/41589/1/24%20PAGES.pdf https://eprints.ums.edu.my/id/eprint/41589/2/FULLTEXT.pdf
_version_	1818611417737068544

Ant colony optimization in dynamic environments

Similar Items