Discrete Flower Pollination Algorithm for solving the symmetric Traveling Salesman Problem

Simple item page
dc.contributor.authorStrange, Ryan
dc.date.accessioned2018-01-05T09:29:52Z
dc.date.available2018-01-05T09:29:52Z
dc.date.issued2017
dc.descriptionA dissertation submitted in fulfilment of the requirements for the degree of Masters of Science in Engineering (Electrical) to the Faculty of Engineering and the Built Environment, University of the Witwatersrand, Johannesburg, 2017en_ZA
dc.description.abstractThe Travelling Salesman Problem (TSP) is an important NP-hard combinatorial optimisation problem that forms the foundation of many modern-day, practical problems such as logistics or network route planning. It is often used to benchmark discrete optimisation algorithms since it is a fundamental problem that has been widely researched. The Flower Pollination Algorithm (FPA) is a continuous optimisation algorithm that demonstrates promising results in comparison to other well-known algorithms. This research proposes the design, implementation and testing of two new algorithms based on the FPA for solving discrete optimisation problems, more specifically the TSP, namely the Discrete Flower Pollination Algorithm (DFPA) and the iterative Discrete Flower Pollination Algorithm (iDFPA). The iDFPA uses two proposed update methods, namely the Best Tour Update (BTU) and the Rejection Update (RU), to perform the iterative update process. The two algorithms are compared to the Ant Colony Optimisation’s (ACO) MAX−MIN Ant System (MMAS) as well as the Genetic Algorithm (GA) since they are well studied and developed. The DFPA and iDFPA results are significantly better than the GA and the iDFPA is able to outperform the ACO in all tested instances. The iDFPA with 300 iterations was able to achieve the optimal solution in the Berlin52 benchmark TSP problem as well as have improvements of up to 4.56% and 41.87% compared to the ACO and GA respectively. An analysis of how the RU and the annealing schedule used in the RU impacts on the overall results of the iDFPA is given. The RU analysis demonstrates how the annealing schedule can be manipulated to achieve certain results from the iDFPA such as faster convergence or better overall results. A parameter analysis is performed on both the DFPA and iDFPA for different TSP problem sizes and the suggested initial parameters for these algorithms are outlined.en_ZA
dc.description.librarianXL2018en_ZA
dc.format.extentOnline resource (xvi, 56, 2 leaves)
dc.identifier.citationStrange, Ryan (2017) Discrete Flower Pollination Algorithm for solving the symmetric Traveling Salesman Problem, University of the Witwatersrand, Johannesburg, <http://hdl.handle.net/10539/23622>
dc.identifier.urihttp://hdl.handle.net/10539/23622
dc.language.isoenen_ZA
dc.subject.lcshAlgorithms--Data processing
dc.subject.lcshDiscrete-time systems
dc.subject.lcshManufacturing processes
dc.titleDiscrete Flower Pollination Algorithm for solving the symmetric Traveling Salesman Problemen_ZA
dc.typeThesisen_ZA
Files
Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
RyanStrange_537434_MScAbstract.pdf
Size:
76.72 KB
Format:
Adobe Portable Document Format
Description:
Download
No Thumbnail Available
Name:
RyanStrange_537434_MScDissertation.pdf
Size:
1.89 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
ETD Collection