The IRMA Community
Newsletters
Research IRM
Click a keyword to search titles using our InfoSci-OnDemand powered search:
|
Biogeography-Based Optimization for Large Scale Combinatorial Problems
Abstract
Biogeography-based optimization (BBO) is a recently-developed heuristic algorithm that has shown impressive performance and efficiency over many standard benchmarks. The application of BBO is still limited because it was only developed four years ago. The objective of this chapter is to expand the application of BBO to large scale combinatorial problems. This chapter addresses the solution of combinatorial problems based on BBO combined with five techniques: (1) nearest neighbor algorithm (NNA), (2) crossover methods designed for traveling salesman problems (TSPs), (3) local optimization methods, (4) greedy methods, and (5) density-based spatial clustering of applications with noise (DBSCAN). This chapter also provides a discussion about the advantages and disadvantages for each of these five techniques when used with BBO, and describes the construction of a combinatorial solver based on BBO. In the end, a framework is proposed for large scale combinatorial problems based on hybrid BBO. Based on four benchmark problems, the experimental results demonstrate the quality and efficiency of our framework. On average, the algorithm reduces costs by over 69% for a 2152-city TSP compared to other methods: genetic algorithm (GA), ant colony optimization (ACO), nearest neighbor algorithm (NNA), and simulated annealing (SA). Convergence time for the algorithm is only 28.56 sec on a 1.73-GHz quad core PC with 6 GB of RAM . The algorithm also demonstrated good results for small and medium sized problems such as ulysses16 (16-city TSP, where we obtained the best performance), st70 (70-city TSP, where the second best performance was obtained), and rat575 (575-city TSP, where the second best performance was obtained).
Related Content
|
Bhargav Naidu Matcha, Sivakumar Sivanesan, K. C. Ng, Se Yong Eh Noum, Aman Sharma.
© 2023.
60 pages.
|
|
Lavanya Sendhilvel, Kush Diwakar Desai, Simran Adake, Rachit Bisaria, Hemang Ghanshyambhai Vekariya.
© 2023.
15 pages.
|
|
Jayanthi Ganapathy, Purushothaman R., Ramya M., Joselyn Diana C..
© 2023.
14 pages.
|
|
Prince Rajak, Anjali Sagar Jangde, Govind P. Gupta.
© 2023.
14 pages.
|
|
Mustafa Eren Akpınar.
© 2023.
9 pages.
|
|
Sreekantha Desai Karanam, Krithin M., R. V. Kulkarni.
© 2023.
34 pages.
|
|
Omprakash Nayak, Tejaswini Pallapothala, Govind P. Gupta.
© 2023.
19 pages.
|
|
|