Khóa Luận Tốt Nghiệp: Áp Dụng Thuật Toán Di Truyền Để Giải Bài Toán Người Du Lịch

Bài toán người du lịch (TSP), hay còn gọi là bài toán người bán hàng, là một trong những bài toán tối ưu tổ hợp nổi… 61 trang · Đại Học Kinh Tế Huế · 2017.

• Tác giả: Thái Công Danh
• Người hướng dẫn: TS. Nguyễn Đình Hoa Cương
• Trường học: Đại Học Kinh Tế Huế
• Chuyên ngành: Tin Học Kinh Tế
• Đề tài: Áp Dụng Thuật Toán Di Truyền Để Giải Bài Toán Người Du Lịch
• Loại tài liệu: Khóa Luận Tốt Nghiệp
• Năm xuất bản: 2017
• Địa điểm: Huế

Mục lục chi tiết

• LỜI CÁM ƠN
• DANH MỤC CÁC CHỮ VIẾT TẮT VÀ KÍ HIỆU
• DANH MỤC CÁC SƠ ĐỒ, ĐỒ THỊ
• DANH MỤC CÁC BIỂU BẢNG
• I. PHẦN I: ĐẶT VẤN ĐỀ
• I.1. Lý do chọn đề tài
• I.2. Mục tiêu nghiên cứu
• I.3. Đối tượng và phạm vi nghiên cứu
• I.4. Phương pháp nghiên cứu
• I.5. Nội dung khóa luận
• II. PHẦN II: NỘI DUNG VÀ KẾT QUẢ NGHIÊN CỨU
• 1. CHƯƠNG 1: CƠ SỞ LÝ LUẬN
• 1.1. Bài toán người du lịch (Traveling Salesman Problem – TSP)
• 1.1.1. Lịch sử
• 1.1.2. Phát biểu bài toán
• 1.2. Lý thuyết độ phức tạp tính toán
• 1.2.1. Khái niệm
• 1.2.2. Các lớp độ phức tạp
• 1.2.3. Độ phức tạp của bài toán người du lịch
• 1.3. Thuật toán di truyền (Genetic Algorithm)
• 1.3.1. Lịch sử của thuật toán di truyền
• 2. CHƯƠNG 2: CÀI ĐẶT THUẬT TOÁN DI TRUYỀN ĐỂ GIẢI BÀI TOÁN NGƯỜI DU LỊCH
• 3. CHƯƠNG 3: THÍ NGHIỆM CHƯƠNG TRÌNH
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Thuật Toán Di Truyền và Bài Toán TSP

Bài toán người du lịch (TSP), hay còn gọi là bài toán người bán hàng, là một trong những bài toán tối ưu tổ hợp nổi tiếng. Bài toán yêu cầu tìm một lộ trình ngắn nhất để đi qua tất cả các thành phố, mỗi thành phố chỉ một lần và quay trở lại điểm xuất phát. Mặc dù phát biểu đơn giản, việc giải TSP, đặc biệt với số lượng lớn thành phố, là một thách thức lớn. Thuật toán di truyền (Genetic Algorithm) là một phương pháp metaheuristic được sử dụng rộng rãi để tìm kiếm giải pháp gần tối ưu cho bài toán này. GA mô phỏng quá trình tiến hóa tự nhiên, sử dụng các khái niệm như chọn lọc, lai ghép, và đột biến để cải thiện quần thể các giải pháp tiềm năng qua các thế hệ. Ưu điểm của giải thuật di truyền cho TSP là khả năng tìm kiếm trong không gian giải pháp rộng lớn mà không bị mắc kẹt trong các cực trị địa phương.

1.1. Khái niệm TSP Traveling Salesman Problem cơ bản

Bài toán người du lịch đặt ra yêu cầu tìm lộ trình ngắn nhất qua n thành phố, bắt đầu và kết thúc tại cùng một thành phố, mỗi thành phố ghé thăm đúng một lần. Trong đó, khoảng cách giữa các thành phố được xác định trước. Vấn đề này thuộc lớp NP-hard, có nghĩa là không có thuật toán nào tìm ra nghiệm tối ưu trong thời gian đa thức cho mọi trường hợp. Do đó, các phương pháp heuristic algorithm được sử dụng rộng rãi để tìm kiếm giải pháp chấp nhận được. Giải thuật sử dụng ma trận khoảng cách giữa các thành phố để tính toán chi phí hành trình.

1.2. Thuật toán di truyền Genetic Algorithm Giới thiệu và ưu điểm

Thuật toán di truyền là một phương pháp tìm kiếm và tối ưu hóa dựa trên cơ chế tiến hóa tự nhiên. Nó bắt đầu với một quần thể các giải pháp tiềm năng (nhiễm sắc thể), áp dụng các phép toán chọn lọc (selection), lai ghép (crossover), và đột biến (mutation) để tạo ra các thế hệ mới. Các cá thể có fitness function tốt hơn (trong trường hợp TSP là lộ trình ngắn hơn) sẽ có nhiều khả năng được chọn để lai ghép và tạo ra thế hệ sau. Ưu điểm của GA là khả năng khám phá không gian giải pháp rộng lớn và tránh được các cực trị địa phương.

II. Thách Thức và Vấn Đề Của Giải TSP Truyền Thống

Các phương pháp giải bài toán người du lịch truyền thống, như vét cạn hoặc quy hoạch động, trở nên bất khả thi khi số lượng thành phố tăng lên. Độ phức tạp tính toán tăng theo cấp số nhân, khiến thời gian tính toán trở nên quá lớn. Các phương pháp giải pháp tối ưu này không còn phù hợp với các bài toán thực tế có quy mô lớn. Do đó, cần có các phương pháp metaheuristic algorithm hiệu quả hơn để tìm kiếm các giải pháp gần tối ưu trong thời gian tính toán chấp nhận được. Điều kiện ràng buộc và mô hình hóa bài toán cũng là những yếu tố quan trọng cần xem xét.

2.1. Giới hạn về độ phức tạp tính toán của thuật toán vét cạn

Thuật toán vét cạn duyệt qua tất cả các hoán vị có thể của các thành phố, dẫn đến độ phức tạp tính toán là O(n!), với n là số lượng thành phố. Với số lượng thành phố tăng lên, thời gian tính toán tăng lên rất nhanh, làm cho thuật toán này không khả thi cho các bài toán có quy mô lớn. Ví dụ, với 20 thành phố, số lượng hoán vị là khoảng 2.4 x 10^18, cần một lượng lớn tài nguyên tính toán và thời gian để xử lý.

2.2. Khó khăn trong việc mô hình hóa bài toán với ràng buộc thực tế

Trong thực tế, bài toán người du lịch thường đi kèm với các điều kiện ràng buộc phức tạp, chẳng hạn như thời gian mở cửa của các địa điểm, giới hạn trọng tải của phương tiện vận chuyển, hoặc các yêu cầu về ưu tiên ghé thăm. Việc mô hình hóa bài toán để bao gồm các yếu tố này làm tăng độ khó của bài toán và đòi hỏi các phương pháp giải thuật tối ưu linh hoạt hơn.

III. Áp Dụng Thuật Toán Di Truyền Cho Bài Toán Người Du Lịch Chi Tiết

Áp dụng thuật toán di truyền để giải bài toán người du lịch bao gồm một số bước chính: mã hóa hành trình, khởi tạo quần thể ban đầu, tính fitness function, thực hiện các phép toán chọn lọc, lai ghép, và đột biến, và lặp lại quá trình này cho đến khi đạt được điều kiện dừng. Biểu diễn nhiễm sắc thể đóng vai trò quan trọng trong hiệu quả của thuật toán. Chọn lọc (Selection) đảm bảo các cá thể tốt có cơ hội sinh sản cao hơn. Lai ghép (Crossover) kết hợp các phần của hai nhiễm sắc thể cha mẹ để tạo ra các nhiễm sắc thể con. Đột biến (Mutation) giúp duy trì sự đa dạng trong quần thể.

3.1. Mã hóa hành trình và khởi tạo quần thể ban đầu

Một phương pháp phổ biến để mã hóa hành trình là sử dụng một danh sách các số nguyên, mỗi số đại diện cho một thành phố. Quần thể ban đầu có thể được tạo ngẫu nhiên hoặc sử dụng các phương pháp heuristic algorithm khác để tạo ra các giải pháp tốt hơn. Kích thước quần thể là một tham số quan trọng ảnh hưởng đến hiệu quả của thuật toán. Quần thể quá nhỏ có thể dẫn đến hội tụ sớm, trong khi quần thể quá lớn có thể làm tăng thời gian tính toán.

3.2. Hàm fitness function chọn lọc lai ghép và đột biến

Hàm fitness function đánh giá chất lượng của mỗi cá thể trong quần thể. Trong trường hợp TSP, hàm fitness thường là nghịch đảo của tổng độ dài hành trình. Chọn lọc (selection) chọn các cá thể tốt nhất để sinh sản, thường sử dụng các phương pháp như Roulette Wheel Selection hoặc Tournament Selection. Lai ghép (crossover) tạo ra các cá thể con bằng cách kết hợp các phần của hai cá thể cha mẹ. Đột biến (mutation) tạo ra sự thay đổi nhỏ trong nhiễm sắc thể để duy trì sự đa dạng của quần thể. Các tham số như tỷ lệ lai ghép và tỷ lệ đột biến cần được điều chỉnh cẩn thận để đạt được hiệu quả tốt nhất.

IV. Cải Tiến Hiệu Quả Thuật Toán Di Truyền Giải Bài Toán TSP

Để cải tiến thuật toán, cần tối ưu hóa các tham số như kích thước quần thể, tỷ lệ lai ghép, tỷ lệ đột biến. Sử dụng các kỹ thuật heuristic algorithm khác như 2-opt hoặc 3-opt để cải thiện các cá thể sau khi lai ghép hoặc đột biến. Phân tích hiệu năng và so sánh thuật toán với các phương pháp khác như thuật toán Heuristic algorithm giúp đánh giá và cải tiến hiệu quả của thuật toán. Ứng dụng thực tế vào các bài toán routing và logistics cho thấy tính hiệu quả của thuật toán trong các tình huống thực tế.

4.1. Tối ưu hóa tham số và tích hợp heuristic algorithm cục bộ

Việc điều chỉnh các tham số của thuật toán di truyền, chẳng hạn như kích thước quần thể, tỷ lệ lai ghép, và tỷ lệ đột biến, có thể ảnh hưởng đáng kể đến hiệu quả của thuật toán. Tích hợp các thuật toán heuristic algorithm cục bộ, như 2-opt, vào quá trình tìm kiếm có thể giúp cải thiện chất lượng của các giải pháp và giảm thời gian tính toán.

4.2. So sánh hiệu quả thuật toán và đánh giá hiệu năng

So sánh hiệu quả thuật toán di truyền với các thuật toán khác, chẳng hạn như thuật toán nhánh cận hoặc các thuật toán metaheuristic algorithm khác, có thể cung cấp thông tin về điểm mạnh và điểm yếu của thuật toán di truyền. Đánh giá hiệu năng của thuật toán dựa trên các tiêu chí như chất lượng giải pháp, thời gian tính toán, và độ ổn định.

V. Ứng Dụng Thực Tế Của Thuật Toán Di Truyền Trong Vận Tải và Logistics

Thuật toán di truyền được ứng dụng thực tế rộng rãi trong nhiều lĩnh vực, đặc biệt là trong routing, logistics, vận tải, và phân phối hàng hóa. Việc tối ưu hóa hành trình giúp giảm chi phí hành trình, cải thiện hiệu quả hoạt động, và tăng tính cạnh tranh. Ứng dụng trong các hệ thống vận tải thông minh giúp quản lý và điều phối phương tiện hiệu quả hơn. Các công ty logistics sử dụng GA để tối ưu hóa hành trình và giảm chi phí hành trình. Việc cài đặt thuật toán trong các ngôn ngữ như Python, Java, C++ giúp dễ dàng triển khai và tích hợp vào các hệ thống hiện có.

5.1. Tối ưu hóa hành trình và phân phối hàng hóa trong logistics

Trong lĩnh vực logistics, thuật toán di truyền có thể được sử dụng để tối ưu hóa hành trình cho các xe tải giao hàng, giảm chi phí hành trình và cải thiện hiệu quả giao hàng. Thuật toán có thể xem xét các yếu tố như thời gian giao hàng, giới hạn trọng tải, và khoảng cách giữa các điểm đến.

5.2. Ứng dụng trong routing và hệ thống vận tải thông minh

Trong lĩnh vực routing, thuật toán di truyền có thể được sử dụng để tìm đường đi ngắn nhất giữa hai điểm, xem xét các yếu tố như tình trạng giao thông, giới hạn tốc độ, và các tuyến đường cấm. Các hệ thống vận tải thông minh có thể sử dụng thuật toán di truyền để điều phối phương tiện và quản lý lưu lượng giao thông hiệu quả hơn.

VI. Kết Luận Tiềm Năng và Hướng Phát Triển Của Thuật Toán Di Truyền

Thuật toán di truyền là một công cụ mạnh mẽ để giải quyết bài toán người du lịch và các bài toán tối ưu hóa hành trình khác. Mặc dù không đảm bảo tìm ra giải pháp tối ưu, GA có thể tìm kiếm các giải pháp gần tối ưu trong thời gian tính toán chấp nhận được, đặc biệt với các bài toán có quy mô lớn. Các nghiên cứu tiếp theo có thể tập trung vào việc cải tiến thuật toán, tích hợp các kỹ thuật heuristic algorithm mới, và mở rộng ứng dụng thực tế vào các lĩnh vực khác. Các ngôn ngữ lập trình hướng đối tượng hỗ trợ tốt cho việc triển khai thuật toán.

6.1. Tổng kết hiệu quả và hạn chế của thuật toán di truyền

Thuật toán di truyền cung cấp một phương pháp hiệu quả để tìm kiếm các giải pháp gần tối ưu cho bài toán người du lịch, đặc biệt khi số lượng thành phố lớn. Tuy nhiên, thuật toán không đảm bảo tìm ra giải pháp tối ưu và có thể đòi hỏi thời gian tính toán đáng kể. Việc lựa chọn các tham số phù hợp và tích hợp các kỹ thuật heuristic algorithm là rất quan trọng để cải thiện hiệu quả của thuật toán.

6.2. Hướng nghiên cứu và phát triển giải pháp tối ưu trong tương lai

Các hướng nghiên cứu trong tương lai có thể tập trung vào việc cải tiến thuật toán di truyền, tích hợp các kỹ thuật heuristic algorithm mới, và khám phá các phương pháp mã hóa hành trình hiệu quả hơn. Việc phát triển các thư viện thuật toán di truyền dễ sử dụng cũng có thể giúp mở rộng ứng dụng thực tế của thuật toán trong nhiều lĩnh vực khác nhau.

Nội dung chính

Bối cảnh và vấn đề nghiên cứu

Khóa luận tốt nghiệp "Áp dụng thuật toán di truyền để giải bài toán người du lịch" được thực hiện bởi sinh viên Thái Công Danh (lớp K47 Tin học Kinh tế, Khoa Hệ thống Thông tin Kinh tế, Trường Đại học Kinh tế – Đại học Huế) dưới sự hướng dẫn khoa học của TS. Nguyễn Đình Hoa Cương vào tháng 5 năm 2017. Bối cảnh thực tiễn của đề tài gắn liền với đợt thực tập tốt nghiệp của tác giả tại Công ty FPT Software Đà Nẵng nhằm tiếp cận dữ liệu và ứng dụng kiến thức thuật toán vào môi trường phát triển thực tế.

Bài toán người du lịch (Traveling Salesman Problem – TSP) là một trong những bài toán kinh điển thuộc lớp tối ưu tổ hợp. Vấn đề cốt lõi mà đề tài giải quyết xuất phát từ việc tìm kiếm một hành trình tối ưu đi qua $n$ thành phố, mỗi thành phố đúng một lần rồi quay trở lại điểm xuất phát sao cho tổng quãng đường là ngắn nhất. Dù phát biểu đơn giản, TSP thuộc lớp bài toán NP-đầy đủ (NP-Complete) và NP-khó (NP-Hard). Khi số lượng thành phố tăng lên, số lượng chu trình khả dĩ bùng nổ theo hàm giai thừa $(n-1)!$, khiến các thuật toán duyệt toàn bộ (vét cạn) hoàn toàn bất khả thi về mặt thời gian tính toán. Việc giải quyết các bài toán NP-đầy đủ như TSP còn là tiền đề lý thuyết quan trọng để nghiên cứu vấn đề thiên niên kỷ liệu $P = NP$ trong lý thuyết độ phức tạp tính toán. Nhằm vượt qua rào cản thời gian, thuật toán di truyền (Genetic Algorithm – GA) được lựa chọn như một phương pháp tìm kiếm heuristic phỏng sinh học hiệu quả, có khả năng tìm kiếm nghiệm xấp xỉ tối ưu trong thời gian chấp nhận được.

Mục tiêu nghiên cứu của khóa luận được phân định thành:

1. Mục tiêu tổng quát: Dựa trên các nghiên cứu cụ thể về bài toán người du lịch và thuật toán di truyền để xây dựng chương trình phần mềm giải quyết bài toán, đồng thời kiểm thử tính hiệu quả của thuật toán.
2. Các mục tiêu cụ thể:
   • Nghiên cứu cơ sở lý luận về bài toán người du lịch cũng như thuật toán di truyền: lịch sử hình thành, tư tưởng toán học và các bước thực hiện.
   • Nghiên cứu phương pháp cài đặt thuật toán bằng ngôn ngữ lập trình Java theo mô hình hướng đối tượng.
   • Tiến hành kiểm thử chương trình, đánh giá tính hiệu quả và thời gian thực thi của thuật toán di truyền so với thuật toán duyệt sâu.

Đối tượng và phạm vi nghiên cứu:

• Đối tượng nghiên cứu: Thuật toán di truyền và cơ chế ứng dụng để giải quyết bài toán người du lịch.
• Phạm vi nghiên cứu: Đề tài tập trung vào không gian bài toán TSP đối xứng hai chiều, trong đó mỗi thành phố được biểu diễn bằng tọa độ Descartes phẳng $(x, y)$, khoảng cách giữa hai thành phố là khoảng cách Euclid; phạm vi công nghệ giới hạn trong việc xây dựng ứng dụng độc lập trên nền tảng Java; phạm vi thời gian nghiên cứu và thực nghiệm hoàn thành vào tháng 5 năm 2017.

Cơ sở lý thuyết và phương pháp

Cơ sở lý thuyết của khóa luận được xây dựng dựa trên hai trụ cột chính: lý thuyết độ phức tạp tính toán của bài toán TSP và nguyên lý tiến hóa của thuật toán di truyền:

• Lý thuyết bài toán người du lịch: Khóa luận hệ thống hóa lịch sử từ trò chơi Icosian năm 1857 của William Rowan Hamilton (với đồ thị 20 đỉnh), nghiên cứu toán học của Karl Menger (1930), Hassler Whitney, Merrill Flood tại Đại học Princeton và RAND Corporation. Năm 1972, Richard Karp đã chứng minh bài toán chu trình Hamilton thuộc lớp NP-đầy đủ, khẳng định không tồn tại thuật toán thời gian đa thức để giải chính xác bài toán trừ khi chứng minh được $P = NP$.
• Lý thuyết độ phức tạp tính toán: Văn bản phân định bốn lớp độ phức tạp cơ bản gồm lớp $P$ (Polynomial time), lớp $NP$ (Nondeterministic Polynomial time), lớp $NP$-Complete và lớp $NP$-Hard.
• Nguyên lý thuật toán di truyền: Bắt nguồn từ công trình nghiên cứu hệ thống thích nghi tự nhiên của John Holland tại Đại học Michigan trong thập niên 1960 và cuốn sách nền tảng "Adaptation in Natural and Artificial Systems" (1975). GA mô phỏng chọn lọc tự nhiên và di truyền học, vận hành qua các khái niệm quần thể (population), cá thể/nhiễm sắc thể (chromosome), gen (gene), hàm thích nghi (fitness function) và các toán tử: chọn lọc (selection), lai ghép (crossover), đột biến (mutation).
• Các công trình liên quan: Tác giả đã tổng quan 10 tài liệu tiêu biểu trong và ngoài nước, bao gồm: nghiên cứu lập lịch bệnh viện của Bùi Thu Lâm và Phan Việt Anh (2010); xếp thời khóa biểu tín chỉ của Nguyễn Thanh Bình và Trương Công Tuấn; phân lớp dữ liệu Random Forest kết hợp KPCA và GA của Nguyễn Hà Nam; bộ giải nhanh TSP trên Java của Hiroaki Sengoku và Ikuo Yoshihara; nghiên cứu toán tử lai và biểu diễn của P. Larranaga và cộng sự; giải thuật tìm kiếm di truyền địa phương của Bernd Freisleben và Peter Merz; toán tử lai ghép cấu trúc tuần tự SCX của Ahmed; kỹ thuật tránh toán tử đặc biệt của Gokturk Ucoluk; mô hình GA cho TSP của Potvin; điều kiện dừng bằng chuỗi Markov của Safe và cộng sự; cùng tài liệu hướng dẫn GA của Darrell Whitley.

Phương pháp nghiên cứu thực hiện trong đề tài bao gồm:

• Phương pháp nghiên cứu tài liệu: Thu thập, tổng hợp các công trình khoa học, sách chuyên khảo, tài liệu lý thuyết đồ thị và giải thuật tiến hóa.
• Phương pháp hỏi ý kiến chuyên gia: Tham vấn giảng viên hướng dẫn và các nhà nghiên cứu trong ngành để hoàn thiện giải pháp kỹ thuật.
• Phương pháp phân tích thiết kế hướng đối tượng (OOAD): Mô hình hóa các thực thể của bài toán thành các lớp đối tượng tường minh trong ngôn ngữ Java.
• Phương pháp thực nghiệm và kiểm thử: Đo lường thời gian chạy và chất lượng nghiệm trên các bộ dữ liệu mô phỏng, đồng thời đối chiếu hiệu năng với thuật toán duyệt sâu (DFS – Depth First Search).

Nguồn dữ liệu sử dụng trong nghiên cứu:

• Dữ liệu tọa độ điểm hai chiều do người dùng nhập trực tiếp từ giao diện dòng lệnh.
• Dữ liệu sinh ngẫu nhiên tự động bởi chương trình dựa trên số lượng thành phố $N$ yêu cầu.
• Dữ liệu đọc từ tập tin văn bản cấu trúc lưu tại đường dẫn E:\input.txt với định dạng mỗi dòng gồm ba trường: <số thứ tự thành phố> <tung độ> <hoành độ>.

Thiết kế và triển khai

Hệ thống được xây dựng bằng ngôn ngữ lập trình Java, sử dụng phương pháp lập trình hướng đối tượng nhằm phản ánh trực quan các thành phần của bài toán người du lịch và các cơ chế tiến hóa sinh học.

Kiến trúc phần mềm bao gồm 5 lớp đối tượng chính:

• Lớp ThanhPho: Biểu diễn một đỉnh trên đồ thị với hai tọa độ thực $x$ (hoành độ) và $y$ (tung độ). Lớp cung cấp phương thức khoangCachToi(ThanhPho) tính khoảng cách Euclid theo công thức: $$d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$$
• Lớp DanhSachThanhPho: Sử dụng cấu trúc danh sách động tĩnh ArrayList<ThanhPho> để lưu trữ toàn bộ các điểm đến cần ghé thăm, quản lý thuộc tính thanhPhoBatDau và cung cấp các phương thức truy xuất, định danh thành phố.
• Lớp ChuTrinh: Biểu diễn một cá thể (nhiễm sắc thể) trong quần thể, chứa một hành trình khép kín thông qua ArrayList<ThanhPho>. Lớp cài đặt phương thức taoChuTrinh() khởi tạo ngẫu nhiên bằng cách hoán vị danh sách thông qua Collections.shuffle(), phương thức tính tổng độ dài getKhoangCach() và hàm thích nghi getDoThichNghi(): $$f(x) = \frac{1}{d(x)}$$ trong đó $d(x)$ là tổng độ dài chu trình $x$. Phương thức toString() chịu trách nhiệm định dạng chuỗi kết quả hành trình theo thứ tự bắt đầu từ thành phố khởi hành được chỉ định.
• Lớp QuanThe: Quản lý tập hợp các cá thể chu trình dưới dạng mảng ChuTrinh[] quanThe, hỗ trợ khởi tạo quần thể ban đầu với kích thước xác định và phương thức layChuTrinhTotNhat() để tìm cá thể có độ thích nghi cao nhất.
• Lớp ThuatToanDiTruyen: Chịu trách nhiệm thực thi các toán tử tiến hóa cốt lõi:
  • Cơ chế biểu diễn nhiễm sắc thể: Sử dụng biểu diễn theo lộ trình (path representation) dưới dạng dãy hoán vị các thành phố.
  • Toán tử chọn lọc: Sử dụng phương pháp giao đấu (tournament selection) với quy mô nhóm giao đấu là 5 cá thể (nhomChuTrinh = new QuanThe(5, false)). Lớp lấy ngẫu nhiên 5 chu trình trong quần thể và chọn ra cá thể có độ thích nghi cao nhất.
  • Toán tử lai ghép: Hiện thực cơ chế lai bảo toàn thứ tự để tránh trùng lặp thành phố. Thuật toán chọn ngẫu nhiên hai vị trí diemDau và diemCuoi từ chu trình cha để sao chép nguyên vẹn sang chu trình con, sau đó duyệt chu trình mẹ để bổ sung các thành phố chưa có theo đúng thứ tự xuất hiện.
  • Toán tử đột biến: Duyệt qua các vị trí trong chu trình, tiến hành hoán đổi ngẫu nhiên hai thành phố với nhau theo xác suất đột biến (tham số khai báo trong mã nguồn là private static double tiLeDotBien = 0.015, tương ứng 1,5%, trong khi phần thuyết minh mô tả ghi tỷ lệ 15%).
  • Chiến lược tiến hóa: Áp dụng cơ chế ưu tú (elitism) bằng cách giữ lại cá thể tốt nhất của thế hệ trước đưa thẳng vào vị trí đầu tiên của thế hệ mới (quanTheMoi.luuChuTrinh(0, quanThe.layChuTrinhTotNhat())), các cá thể còn lại được sinh ra thông qua chọn lọc, lai ghép và đột biến.
• Lớp XuLyBaiToan: Chứa hàm main, quản lý luồng tương tác với người dùng qua Scanner, khởi tạo quần thể gồm 50 cá thể (new QuanThe(50, true)), thực thi vòng lặp tiến hóa qua 10.000 thế hệ và in kết quả chu trình tối ưu tìm được cùng tổng độ dài.

Chương trình cung cấp ba phương thức nạp dữ liệu: khai báo thủ công các đối tượng ThanhPho(x, y), sinh ngẫu nhiên số lượng thành phố qua hàm Math.random(), và đọc tệp E:\input.txt sử dụng bộ tách ký tự khoảng trắng docFile.useDelimiter(" ").

Nội dung chính theo từng chương

Chương 1: Cơ sở lý luận

Chương 1 tập trung làm rõ bản chất toán học của bài toán người du lịch, cơ sở của lý thuyết độ phức tạp tính toán và các nguyên lý của giải thuật di truyền.

Tác giả phân tích bảng tiến trình lịch sử giải quyết kích thước bài toán TSP qua các giai đoạn nghiên cứu thực nghiệm:

Năm	Nhà nghiên cứu	Quy mô thành phố giải được
1954	G. Dantzig, R. Fulkerson, S. Johnson	49 thành phố
1971	S. Lin, B. Kernighan	64 thành phố
1975	P. M. Camerini, L. Fratta, F. Maffioli	67 thành phố
1977	M. Grötschel	120 thành phố
1980	H. Crowder, M. Padberg	318 thành phố
1987	M. Padberg, G. Rinaldi	532 thành phố
1987	M. Grötschel, O. Holland	666 thành phố
1987	M. Padberg, G. Rinaldi	2.392 thành phố
1998	D. Applegate, R. Bixby, V. Chvátal, W. Cook	13.509 thành phố
2001	D. Applegate, R. Bixby, V. Chvátal, W. Cook	15.112 thành phố
2006	D. Applegate, R. Bixby, V. Chvátal, W. Cook, K. Helsgaun	85.900 thành phố

Chương này cũng minh họa sự bùng nổ tổ hợp của không gian tìm kiếm TSP thông qua số lượng chu trình Hamilton trên đồ thị đầy đủ gồm $n$ đỉnh theo công thức $(n-1)!$:

Số đỉnh	Số cạnh	Số lượng chu trình
6	15	120
7	21	720
8	28	5.040
9	36	40.320
10	45	362.880
11	55	3.628.800
12	66	$3{,}216451 \times 10^{17}$

Văn bản ghi nhận khi số đỉnh đạt tới 20, số lượng chu trình cần duyệt qua vượt quá 121 triệu tỷ chu trình, chứng minh phương pháp vét cạn hoàn toàn bất khả thi đối với máy tính hiện đại. Bên cạnh đó, chương 1 trình bày chi tiết các dạng biểu diễn cá thể (lộ trình, thứ tự, liền kề), các kỹ thuật chọn lọc (vòng quay Roulette, giao đấu), kỹ thuật đột biến đảo bit, đổi chỗ, và khảo sát tổng quan 10 nghiên cứu khoa học liên quan trực tiếp đến ứng dụng GA.

Chương 2: Cài đặt thuật toán di truyền để giải bài toán người du lịch

Chương 2 trình bày chi tiết quá trình hiện thực hóa giải thuật trên ngôn ngữ lập trình Java. Tác giả phân tích thiết kế hướng đối tượng qua biểu đồ lớp (Class Diagram), phân chia cấu trúc thành 4 lớp dữ liệu (ThanhPho, DanhSachThanhPho, ChuTrinh, QuanThe) và 1 lớp thuật toán (ThuatToanDiTruyen).

Nội dung chương mô tả đầy đủ các đoạn mã nguồn hiện thực:

• Thiết lập cách tính khoảng cách Euclid giữa các tọa độ điểm thực.
• Mã hóa hành trình dưới dạng lộ trình không lặp đỉnh.
• Hiện thực toán tử chọn lọc giao đấu với quy mô nhóm ngẫu nhiên bằng 5.
• Cài đặt toán tử lai ghép cắt - dán bảo toàn tính hợp lệ của chu trình.
• Cài đặt toán tử đột biến hoán vị vị trí hai thành phố ngẫu nhiên.
• Xây dựng 3 cơ chế nạp dữ liệu đầu vào: nhập cố định qua hàm khởi tạo, sinh ngẫu nhiên qua vòng lặp, và đọc dữ liệu từ tệp tin E:\input.txt.

Chương 3: Thí nghiệm chương trình

Theo danh mục mục lục và danh mục biểu bảng của khóa luận, Chương 3 tập trung vào việc đánh giá thực nghiệm chương trình đã cài đặt thông qua ba nội dung:

• Thí nghiệm chương trình với số thành phố tăng dần: Khảo sát thời gian thực thi của thuật toán khi quy mô bài toán mở rộng (được tổng hợp tại Bảng 3.1 và Biểu đồ 3.1).
• Thí nghiệm kết quả chương trình với số thế hệ tăng dần: Khảo sát mức độ cải thiện của hàm thích nghi và độ dài chu trình ngắn nhất tìm được khi tăng số lượng thế hệ lặp (được tổng hợp tại Bảng 3.2).
• So sánh thời gian chạy của thuật toán di truyền với thuật toán duyệt sâu (DFS): Đo lường sự chênh lệch về thời gian xử lý giữa thuật toán heuristic di truyền và thuật toán tìm kiếm vét cạn duyệt sâu khi số đỉnh tăng lên (được tổng hợp tại Bảng 3.3 và Biểu đồ 3.2).

Kết quả và đóng góp

Khóa luận đã đạt được các kết quả kỹ thuật và đóng góp cụ thể sau:

• Xây dựng thành công ứng dụng Java hoàn chỉnh giải quyết bài toán TSP bằng thuật toán di truyền theo phương pháp lập trình hướng đối tượng, cung cấp cấu trúc mã nguồn tường minh và dễ mở rộng.
• Hệ thống hóa bộ tham số cấu hình thực nghiệm của thuật toán:

Thành phần / Tham số	Giá trị cài đặt trong khóa luận
Ngôn ngữ phát triển	Java
Phương pháp mã hóa	Biểu diễn theo lộ trình (Path representation)
Kích thước quần thể	50 cá thể
Phương pháp chọn lọc	Giao đấu (Tournament selection) với quy mô nhóm 5 cá thể
Cơ chế lai ghép	Cắt đoạn cha ngẫu nhiên, điền bù từ mẹ bảo toàn thứ tự
Cơ chế đột biến	Hoán đổi vị trí ngẫu nhiên hai thành phố
Tỷ lệ đột biến	Khai báo mã nguồn: 0,015 (thuyết minh văn bản ghi 15%)
Chiến lược thế hệ	Giữ lại 1 cá thể tốt nhất (Elitism)
Điều kiện dừng	Cố định số thế hệ tiến hóa (10.000 vòng lặp trong hàm main)
Hàm mục tiêu thích nghi	$f(x) = 1 / d(x)$ ($d(x)$ là tổng độ dài Euclid của chu trình)

• Giải pháp và kiến nghị của tác giả: Đề xuất sử dụng thuật toán di truyền như một giải pháp thay thế hiệu quả cho các phương pháp duyệt toàn bộ khi giải quyết bài toán TSP quy mô lớn; định hướng ứng dụng thuật toán vào các bài toán thực tiễn như định tuyến vận tải, bài toán tìm đường đi ngắn nhất giữa các đô thị trong các hệ thống bản đồ số.
• Đóng góp so với các nghiên cứu trước: Tác giả tự nêu việc xây dựng chương trình minh họa trực quan trên Java giúp người học dễ tiếp cận cơ chế sinh học của GA; đồng thời thực hiện kiểm chứng so sánh thực nghiệm giữa thuật toán di truyền và thuật toán duyệt sâu (DFS) nhằm cung cấp minh chứng định lượng về giới hạn của thuật toán vét cạn trên không gian bài toán NP-đầy đủ.

Hạn chế và hướng nghiên cứu tiếp

Khóa luận ghi nhận các hạn chế và hướng mở nghiên cứu dựa trên văn bản:

• Hạn chế:
  • Điều kiện dừng của thuật toán mới chỉ áp dụng phương án đơn giản là đặt số lần lặp thế hệ cố định, chưa cài đặt các điều kiện dừng nâng cao như giới hạn hội tụ của hàm thích nghi hoặc mô hình xác suất chuỗi Markov (như nghiên cứu của Safe và cộng sự đã chỉ ra).
  • Tỷ lệ đột biến và kích thước quần thể được thiết lập dưới dạng hằng số cố định, chưa có cơ chế điều chỉnh thích nghi linh hoạt theo từng giai đoạn tiến hóa.
  • Không gian bài toán mới dừng lại ở mô hình tọa độ phẳng hai chiều đối xứng với khoảng cách hình học thuần túy, chưa xét đến các ràng buộc thực tế như mạng lưới giao thông một chiều, lưu lượng tắc nghẽn hay bài toán TSP có hướng.
• Hướng nghiên cứu tiếp:
  • Nghiên cứu và thử nghiệm các điều kiện dừng tối ưu dựa trên biến thiên độ thích nghi giữa các thế hệ liên tiếp.
  • Tích hợp các toán tử lai ghép chuyên biệt có hiệu năng cao hơn như phép lai cấu trúc tuần tự (SCX), phép lai tái kết nối cạnh (ERX) hoặc kết hợp thuật toán tìm kiếm địa phương (Genetic Local Search).
  • Mở rộng ứng dụng trên dữ liệu địa lý thực tế từ hệ thống bản đồ số với đồ thị có trọng số phức tạp.

Giá trị tham khảo

Tài liệu khóa luận có giá trị tham khảo thiết thực đối với:

• Sinh viên các ngành Hệ thống Thông tin Kinh tế, Tin học Kinh tế, Công nghệ Thông tin và Khoa học Máy tính đang học tập các học phần về Lý thuyết đồ thị, Cấu trúc dữ liệu và giải thuật, hoặc Trí tuệ nhân tạo.
• Người nghiên cứu đang tìm kiếm mã nguồn mẫu viết bằng Java cài đặt thuật toán di truyền theo chuẩn thiết kế hướng đối tượng (OOP) rõ ràng, phục vụ cho các bài toán tối ưu tổ hợp.
• Nội dung tổng quan ở Chương 1 là tài liệu tham khảo súc tích về lịch sử giải bài toán TSP, các lớp độ phức tạp thuật toán và tổng kết các hướng tiếp cận toán tử lai ghép trong GA.

Câu hỏi thường gặp

1. Khóa luận sử dụng phương pháp biểu diễn cá thể nào cho bài toán người du lịch? Khóa luận sử dụng phương pháp biểu diễn theo lộ trình (path representation). Trong phương pháp này, mỗi cá thể (chu trình) là một dãy hoán vị chứa đầy đủ các thành phố theo đúng thứ tự cần ghé thăm. Để thuận tiện cho việc thực hiện các toán tử di truyền, thành phố bắt đầu chỉ được liệt kê một lần trong mảng và chỉ được bổ sung điểm khép kín khi hiển thị kết quả.

2. Hàm tính độ thích nghi (fitness) trong chương trình được xác định như thế nào? Hàm thích nghi được xác định tỷ lệ nghịch với tổng độ dài của chu trình theo công thức $f(x) = 1 / d(x)$, trong đó $d(x)$ là tổng khoảng cách Euclid giữa các thành phố liên tiếp trong chu trình $x$ (bao gồm cả chặng quay về điểm xuất phát). Chu trình có tổng quãng đường càng ngắn thì giá trị $f(x)$ càng lớn, thể hiện cá thể có độ thích nghi càng cao.

3. Toán tử chọn lọc trong chương trình Java được cài đặt theo kỹ thuật nào? Chương trình sử dụng phương pháp chọn lọc giao đấu (tournament selection). Cụ thể, thuật toán tạo một nhóm gồm 5 cá thể ngẫu nhiên rút ra từ quần thể hiện tại (new QuanThe(5, false)), sau đó so sánh độ thích nghi giữa các cá thể trong nhóm và chọn ra cá thể có độ thích nghi cao nhất để làm cha mẹ tham gia vào quá trình lai ghép.

4. Chương trình hỗ trợ những hình thức nhập dữ liệu đầu vào nào? Chương trình hỗ trợ 3 hình thức nhập dữ liệu:

• Nhập thủ công các điểm tọa độ cố định trong mã nguồn bằng cách khởi tạo các đối tượng ThanhPho(x, y).
• Nhập số lượng $N$ thành phố từ bàn phím để chương trình tự động sinh tọa độ thực ngẫu nhiên thông qua hàm Math.random().
• Đọc dữ liệu danh sách thành phố từ tệp văn bản lưu tại đường dẫn E:\input.txt, trong đó mỗi dòng lưu trữ ba thông tin gồm số thứ tự, tung độ và hoành độ, phân cách nhau bằng dấu khoảng trắng.

5. Tại sao thuật toán duyệt sâu (DFS) không thể áp dụng cho bài toán TSP khi số lượng thành phố lớn? Khi giải bài toán TSP bằng phương pháp vét cạn qua duyệt sâu, số lượng chu trình Hamilton cần phải kiểm tra trên đồ thị đầy đủ gồm $n$ đỉnh là $(n-1)!$. Với $n = 12$, số chu trình đã lên tới hơn $3{,}216 \times 10^{17}$, và với $n = 20$, số chu trình vượt quá 121 triệu tỷ. Không gian tìm kiếm tăng theo hàm giai thừa vượt xa năng lực xử lý của máy tính hiện nay, đòi hỏi phải sử dụng các thuật toán tìm kiếm xấp xỉ gần đúng như thuật toán di truyền.

Kết luận

Khóa luận tốt nghiệp của sinh viên Thái Công Danh đã hoàn thành việc nghiên cứu cơ sở lý luận và hiện thực hóa thuật toán di truyền để giải quyết bài toán tối ưu tổ hợp người du lịch trên nền tảng Java. Đề tài đã phân tích bản chất NP-đầy đủ của bài toán, xây dựng kiến trúc hướng đối tượng hoàn chỉnh cho các toán tử chọn lọc giao đấu, lai ghép bảo toàn hoán vị và đột biến hoán đổi vị trí. Các thực nghiệm kiểm thử và so sánh với thuật toán duyệt sâu đã khẳng định tính khả thi của giải thuật di truyền trong việc tìm kiếm lời giải gần tối ưu với chi phí thời gian chấp nhận được.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: CƠ SỞ LÝ LUẬN 1. Bài toán người du lịch (Traveling Salesman Problem – TSP) 1. Lịch sử: Vấn đề toán học liên quan đến bài toán người du lịch đã được nghiên cứu từ những năm 1800 bởi nhà toán học Ai-Len William Rowan Hamilton và nhà toán học người Anh Thomas Penyngton Kirkman. Hamilton đã tạo ra một trò chơi gọi là Icosian vào năm 1857, trò chơi này yêu cầu người chơi phải hoàn thành một chu trình mà chỉ sử dụng những đường kết nối cho trước qua 20 đỉnh [12].

Bài toán người du lịch được nghiên cứu đầu tiên vào năm 1930 bởi nhà toán học và kinh tế học Karl Menger tại đại học Vienna và Harvard. Sau đó nó được nghiên cứu bởi Hassler Whitney và Merrill Flood tại đại học Princeton. Vào những năm 1940 bài toán người du lịch được nghiên cứu bởi những nhà thống kê học là Mahalanobis, Jessen, Gosh, và Marks liên quan đến các ứng dụng nông nghiệp, và nhà toán học Merill Flood phổ biến nó với các đồng nghiệp tại công ty RAND. Phương pháp giải của bài toán bắt đầu xuất hiện trong các tài liệu vào giữa những năm 1950, các tài liệu sử dụng một số thay đổi nhỏ về thuật ngữ "Bài toán người du lịch".

Trong những thế kỷ sau đó, bài toán được nghiên cứu bởi rất nhiều nhà toán học, khoa học máy tính, hóa học, vật lý và những ngành khoa học khác. Mặc dù bài toán người du lịch khá dễ hiểu, tuy nhiên nó rất khó giải quyết. Karp đã chứng minh vào năm 1972 rằng bài toán tìm chu trình Hamilton là bài toán NP-đầy đủ (NP-Complete). NP-khó (NP-hard), là một lớp các bài toán khó nhất trong NP, nói cách khác nó không có thuật toán nào có thể giải bài toán người du lịch trong thời gian đa thức.

Điều này cung cấp một sự giải thích khoa học cho sự khó khăn trong việc tìm ra chu trình tối ưu. Những phương pháp giải quyết bài toán người du lịch đã trở nên phức tạp và các phương pháp khả thi xuất hiện ngày càng nhiều. Dưới đây là một bảng tổng hợp mốc lịch sử của bài toán người du lịch : SV: Thái Công Danh-K47 Tin Học Kinh Tế Trang 4 Khóa luận tốt nghiệp GVHD: TS. Nguyễn Đình Hoa Cương Bảng 1.1: Các cột mốc lịch sử của bài toán người du lịch Năm Người nghiên cứu Số thành phố giải được G.

Fulkerson, và 1954 49 thành phố S. Karp 64 thành phố P. Fratta, và 1975 67 thành phố F. Grötschel 120 thành phố H.

1980 318 thành phố Padberg 1987 M. Rinaldi 532 thành phố 1987 M. Grötschel và O. Holland 666 thành phố 1987 M.397 thành phố Chvátal, và W.509 thành phố Chvátal, và W.112 thành phố Chvátal, và W.978 thành phố Helsgaun 1.

Phát biểu bài toán: Có rất nhiều cách để phát biểu bài toán người du lịch, tuy nhiên tư tưởng của bài toán là giống nhau:  Bài toán người du lịch liên quan đến một người du lịch muốn thực hiện một chuyến đi qua một số thành phố sử dụng đường đi ngắn nhất có thể và thăm mỗi thành phố chỉ một lần sau đó trở về thành phố bắt đầu [18].  Nếu một người du lịch muốn thăm đúng một lần mỗi thành phố của một danh sách m thành phố (chi phí đi từ thành phố i tới thành phố j là cij) và sau đó trở về thành phố bắt đầu. Lộ trình ít tốn kém nhất mà người du lịch có thể đi là bao nhiêu [10] ?  Cho một danh sách các thành phố và đường đi giữa chúng, hãy tìm chu trình ngắn nhất có thể (chu trình Hamilton) đi qua mỗi thành phố đúng một lần [12]. Ta có thể phát biểu lại bài toán như sau: Có n thành phố mà một người du lịch muốn đi tham quan.