Modified genetic algorithm with 2-OPT local search applied in course route generation

By: David, Je Laurence J.; Rivera, Greg Andrew P
Language: English Publisher: . . c2025Description: Undergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2025Content type: text Media type: unmediated Carrier type: volumeGenre/Form: academic writingDDC classification: . LOC classification: QA76.9 A43 D38 2025
Contents:
ABSTRACT: This study presents an enhancement of the Classical Genetic Algorithm designed to address the issue of premature convergence and high selection pressure leading to less diverse and desirable candidate within the population. To address these issues, the enhanced Genetic Algorithm enhanced the generation of the initial population by using made-pairing refined method and nearest neighbor heuristic, and by adjusting the fitness grade of the candidates before Stochastic Universal Sampling (SUS) to select the new candidate at a spaced interval based on their fitness value. Lastly, integrating balanced or-opt for efficient segment relocation the explore better routes, adaptive edge swaps to fix the worst connections, and use the standard 2-opt method as fallback steps on stagnation. This study used a comparative experimental research methodology with statistical validation to assess the performance of each upgrade made to the Standard Genetic Algorithm with 2-Opt Local Search used for courier route development. To ensure accurate results and no data tampering, six known TSP instances and two from two known studies will be used: (a) att48, (b) berlin52, (c) kroA100, (d) pr226, € a280, and (f) rat575. Furthermore, location data from Junera et al. (2019) and Xu et al. (2018) will be used, with the names location19 and location51, respectively. These eight data examples already include a record of their most optimal paths. The results show that the Proposed Genetic Algorithm outperforms the Genertic Algorithm with 2-Opt in terms of solution quality, as indicated by a 2.2222% gain in the Overall Average Best Fitness (OABF) across all instances tested. This suggests that using the proposed approach will result in a more effective overall solution. It is also confirmed that the proposed method is constantly discovering better solutions, with an increase in the average overall percent difference of true best fitness of 1.1623%.
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)

ABSTRACT: This study presents an enhancement of the Classical Genetic Algorithm designed to address the issue of premature convergence and high selection pressure leading to less diverse and desirable candidate within the population. To address these issues, the enhanced Genetic Algorithm enhanced the generation of the initial population by using made-pairing refined method and nearest neighbor heuristic, and by adjusting the fitness grade of the candidates before Stochastic Universal Sampling (SUS) to select the new candidate at a spaced interval based on their fitness value. Lastly, integrating balanced or-opt for efficient segment relocation the explore better routes, adaptive edge swaps to fix the worst connections, and use the standard 2-opt method as fallback steps on stagnation. This study used a comparative experimental research methodology with statistical validation to assess the performance of each upgrade made to the Standard Genetic Algorithm with 2-Opt Local Search used for courier route development. To ensure accurate results and no data tampering, six known TSP instances and two from two known studies will be used: (a) att48, (b) berlin52, (c) kroA100, (d) pr226, € a280, and (f) rat575. Furthermore, location data from Junera et al. (2019) and Xu et al. (2018) will be used, with the names location19 and location51, respectively. These eight data examples already include a record of their most optimal paths. The results show that the Proposed Genetic Algorithm outperforms the Genertic Algorithm with 2-Opt in terms of solution quality, as indicated by a 2.2222% gain in the Overall Average Best Fitness (OABF) across all instances tested. This suggests that using the proposed approach will result in a more effective overall solution. It is also confirmed that the proposed method is constantly discovering better solutions, with an increase in the average overall percent difference of true best fitness of 1.1623%.

Filipiniana

There are no comments for this item.

to post a comment.

© Copyright 2024 Phoenix Library Management System - Pinnacle Technologies, Inc. All Rights Reserved.