Travelling Salesman Genetic AI Final

Giới thiệu

Đồ án kết thúc môn học môn Trí tuệ nhân tạo, chủ đề là áp dụng thuật toán di truyền giải bài toán người du lịch (Travelling salesman problem)

Cách cài đặt

• Bước 1: Tải git và tạo tài khoản
• Bước 2: Copy link mã nguồn https://github.com/ThienNguyen3001/Travelling-Salesman-Genetic-AI-Final.git
• Bước 3: Mở git bash và clone về máy
• Bước 4: Tải thư viện Numpy, Tkinter và Matplotlib về máy

pip install numpy
pip install matplotlib
pip install tk

• Bước 5:
  • Trong thư mục src chứa code thuật toán.
  • Trong thư mục có các file Experiment có đuôi .ipynb là các file thí nghiệm của thành viên trong nhóm.
  • File Demo.py là file chạy giao diện, mở file lên và chạy chương trình.

Thành viên

Tên	Github
Nguyễn Ngọc Thiện	Thiện Nguyễn
Nguyễn Minh Nhựt	Nhựt Nguyễn
Nguyễn Trọng Hưởng	Arthur Nguyen
Trần Viết Gia Huy	Tommyhuy1705

Lời cảm ơn

Chúng em xin cảm ơn TS. Đặng Ngọc Hoàng Thành đã giúp đỡ chúng em về kiến thức, dìu dắt chúng em để hoàn thành phần dự án này. Và cũng xin cảm ơn các thành viên nhóm đã đóng góp tích cực vào dự án để được hoàn thành trọn vẹn.

Tham khảo

1. Gent, I. P., & Walsh, T. (1996). The TSP phase transition. Artificial Intelligence, 88(1-2), 349–358. https://doi.org/10.1016/s0004-3702(96)00030-6
2. Jünger, M., Reinelt, G., & Rinaldi, G. (1995, January 1). Chapter 4 The traveling salesman problem. ScienceDirect; Elsevier. https://www.sciencedirect.com/science/article/abs/pii/S0927050705801215
3. Goyal, S. (2010). A Survey on Travelling Salesman Problem. https://micsymposium.org/mics_2010_proceedings/mics2010_submission_51.pdf
4. Larrañaga, P., Kuijpers, C. M. H., Murga, R. H., Inza, I., & Dizdarevic, S. (1999). Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review, 13(2), 129–170. https://doi.org/10.1023/a:1006529012972
5. Dorigo, M., & Gambardella, L. M. (1997). Ant colonies for the travelling salesman problem. Biosystems, 43(2), 73–81. https://doi.org/10.1016/s0303-2647(97)01708-5
6. Chatterjee, S., Carrera, C., & Lynch, L. A. (1996). Genetic algorithms and traveling salesman problems. European Journal of Operational Research, 93(3), 490–510. https://doi.org/10.1016/0377-2217(95)00077-1
7. TSP-Data for the Traveling Salesperson Problem. (2019). Fsu.edu. https://people.sc.fsu.edu/~jburkardt/datasets/tsp/tsp.html
8. Gotshall, S., & Rylander, B. (2002). Optimal Population Size and the Genetic Algorithm. Www.semanticscholar.org. https://www.semanticscholar.org/paper/Optimal-Population-Size-and-the-Genetic-Algorithm-Gotshall-Rylander/6eb8128b679348b5bef2729c56dd31f0f173a60b
9. Padberg, M., & Rinaldi, G. (1987). Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Operations Research Letters, 6(1), 1–7. https://doi.org/10.1016/0167-6377(87)90002-2
10. Lin, S., & Kernighan, B. W. (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Research, 21(2), 498–516. https://doi.org/10.1287/opre.21.2.498
11. Martin, O., Otto, S., & Felten, E. (1991). Large-Step Markov Chains for the Traveling Salesman Problem (pp. 299–326). https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=2ebfc1496d19d10bc8f9cfcf7a540ce93f7796f2
12. Kirkpatrick, S. (1984). Optimization by simulated annealing: Quantitative studies. Journal of Statistical Physics, 34(5-6), 975–986. https://doi.org/10.1007/bf01009452
13. Holland, J. (1975). Adaptation in Natural and Artificial Systems. In ADAPTATION iN NATURAL AND ARTIFICIAL SYSTEMS. https://books.google.com.vn/books?hl=vi&lr=&id=5EgGaBkwvWcC&oi=fnd&pg=PR7&dq=+Adaptation+in+Natural+and+Artificial+Systems+Holland+1975+University+of+Michigan+Press&ots=mKik04Gotm&sig=jqDlXMrrPG_X38yFO6vPgGl04nA&redir_esc=y#v=onepage&q=Adaptation%20in%20Natural%20and%20Artificial%20Systems%20Holland%201975%20University%20of%20Michigan%20Press&f=false
14. Golberg, D. E. (1989). Genetic algorithms in search, optimization, and machine learning. Addion wesley, 1989(102), 36.
15. Ahn, C. W., & Ramakrishna, R. S. (2003). Elitism-based compact genetic algorithms. IEEE Transactions on Evolutionary Computation, 7(4), 367–385. https://doi.org/10.1109/tevc.2003.814633
16. L. Miller, B., & E. Goldberg, D. (1995). Genetic Algorithms , Tournament Selection, and the Effects of Noise. Com Plex Sy, 9, 193–212. https://wpmedia.wolfram.com/sites/13/2018/02/09-3-2.pdf
17. Jebari, K., & Madiafi, M. (2013). Selection Methods for Genetic Algorithms Selection Methods for Genetic Algorithms. Int. J. Emerg. Sci, 3(4), 333–344.
18. Lipowski, A., & Lipowska, D. (2012). Roulette-wheel selection via stochastic acceptance. Physica A: Statistical Mechanics and Its Applications, 391(6), 2193–2196. https://doi.org/10.1016/j.physa.2011.12.004
19. Harifi, S., & Mohamaddoust, R. (2023). Zigzag mutation: a new mutation operator to improve the genetic algorithm. Multimedia Tools and Applications, 82(29), 45411–45432. https://doi.org/10.1007/s11042-023-15518-3
20. Fahmi Abd Samad, M., & Ayiesya Zainuddin, F. (2020). A Review of Crossover Methods and Problem Representation of Genetic Algorithm in Recent Engineering Applications A Review of Crossover Methods and Problem Representation of Genetic Algorithm in Recent Engineering Applications. International Journal of Advanced Science and Technology, 29(6s), 759–769.
21. Chen, T., Tang, K., Chen, G., & Yao, X. (2012). A large population size can be unhelpful in evolutionary algorithms. Theoretical Computer Science, 436, 54–70. https://doi.org/10.1016/j.tcs.2011.02.016
22. Deep, K., & Thakur, M. (2007). A new crossover operator for real coded genetic algorithms. Applied Mathematics and Computation, 188(1), 895–911. https://doi.org/10.1016/j.amc.2006.10.047
23. Lobo, F. G., & Lima, C. F. (2007). Adaptive Population Sizing Schemes in Genetic Algorithms. Springer EBooks, 185–204. https://doi.org/10.1007/978-3-540-69432-8_9
24. Hassan, R., Cohanim, B., de Weck, O., & Venter, G. (2005). A Comparison of Particle Swarm Optimization and the Genetic Algorithm. 46th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics and Materials Conference. https://doi.org/10.2514/6.2005-1897
25. Deb, K., & Agrawal, R. (2017). Simulated Binary Crossover for Continuous Search Space. Complex Systems. https://www.semanticscholar.org/paper/Simulated-Binary-Crossover-for-Continuous-Search-Deb-Agrawal/b8ee6b68520ae0291075cb1408046a7dff9dd9ad