: 15h00, ngày 07/07/2023 (Thứ Sáu)
: P104 D3
: Seminar Toán rời rạc
: Tạ Anh Sơn
: Viện Toán ứng dụng và Tin học, ĐH Bách Khoa Hà Nội
Tóm tắt báo cáo
The genetic algorithm (GA) is the most widely used meta-heuristic and nature-inspired algorithm, it is well-known for its efficiency in combinatorial optimization problems. This work focuses on a critical part of GA: population seeding techniques. We aim to answer the question of how to create effective population seeding techniques for GA and what criteria evolving operators (crossover, mutation, and selection) must meet to work in combination with high-quality seeding techniques. First, we investigate the impact of population initialization and each evolving operator on GA. Then we define the characteristics of an initial competitive population. Population seeding techniques can be improved by focusing on these characteristics. We demonstrate our approach by creating new algorithms to solve the TSP (traveling salesman problem) and the MTSP (multi-traveling salesman problem). Experiments on TSPLIB benchmarks show that our algorithms significantly outperform other methods.