Luận Văn Thạc Sĩ Về Giải Thuật Di Truyền Trong Bài Toán Đa Mục Tiêu

Đề tài Giải Thuật Di Truyền cho Bài Toán Đa Mục Tiêu: Luận Văn Thạc Sĩ với cơ sở khoa học chặt chẽ, đóng góp giá trị cho nghiên cứu và thực tiễn

• Tác giả: Trần Hải Thanh
• Người hướng dẫn: TS. Lê Nguyên Khôi
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Giải Thuật Di Truyền Cho Bài Toán Đa Mục Tiêu
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ TỐI ƯU ĐA MỤC TIÊU
• 1.1. Giới thiệu bài toán tối ưu đa mục tiêu
• 1.2. Mô hình bài toán tối ưu đa mục tiêu có ràng buộc
• 1.3. Khái niệm tối ưu Pareto
• 1.4. Khái niệm trội Pareto
• 1.5. Tập các lời giải tối ưu Pareto
• 1.6. Bài toán cái túi
• 1.6.1. Bài cái túi dạng 0-1
• 1.6.2. Bài toán cái túi bị chặn
• 1.6.3. Bài toán cái túi không bị chặn
• 1.6.4. Bài toán cái túi đa mục tiêu
• 1.7. Mô hình bài toán cái túi đa mục tiêu
• 1.7.1. Mô hình mã nhị phân
• 2. CHƯƠNG 2: GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU
• 2.1. Giới thiệu về giải thuật di truyền
• 2.2. Các nguyên tắc căn bản của giải thuật di truyền
• 2.3. Các vấn đề chính trong tìm kiếm đa mục tiêu
• 2.4. Mô hình tổng quát giải thuật tiến hóa
• 2.5. Một số thuật toán thường được áp dụng giải bài toán tối ưu đa mục tiêu
• 2.5.1. Thuật toán MOGA
• 2.5.2. Thuật toán VEGA
• 2.5.3. Thuật toán SEAMO, SEAMO2
• 2.5.4. Thuật toán NSGA, NSGA2
• 2.5.5. Thuật toán SPEA, SPEA2
• 3. CHƯƠNG 3: KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 3.1. Cài đặt thuật toán SEAMO2
• 3.2. Thuật toán SEAMO2. Dữ liệu của bài toán
• 3.3. Phương pháp so sánh
• 3.4. Mô hình và các toán tử cho bài toán cái túi 0-1 đa mục tiêu
• 3.5. Thuật toán SEAMO2_LG
• 3.6. Chiến lược chọn lọc cá thể của thuật toán SEAMO2
• 3.7. Đề xuất cải tiến
• 3.8. Kết quả thực nghiệm
• 3.9. So sánh với thuật toán SPEA2, NSGA2
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về tối ưu đa mục tiêu

Bài toán tối ưu đa mục tiêu (multiobjective optimization) là một lĩnh vực quan trọng trong nghiên cứu tối ưu hóa. Nó liên quan đến việc tìm kiếm một tập hợp các giải pháp mà tại đó các hàm mục tiêu có thể đạt được giá trị tối ưu đồng thời. Các hàm mục tiêu thường đối kháng lẫn nhau, điều này tạo ra thách thức trong việc tìm kiếm giải pháp tối ưu. Để giải quyết bài toán này, khái niệm tối ưu Pareto được sử dụng, cho phép xác định các giải pháp không bị trội, tức là không có giải pháp nào tốt hơn mà không làm giảm giá trị của ít nhất một hàm mục tiêu. Việc áp dụng các mô hình tối ưu đa mục tiêu trong thực tế rất phong phú, từ quản lý tài nguyên đến thiết kế kỹ thuật. Các bài toán như bài toán cái túi đa mục tiêu (Knapsack Problem) là ví dụ điển hình cho việc áp dụng lý thuyết này trong thực tế.

1.1. Giới thiệu bài toán tối ưu đa mục tiêu

Tối ưu đa mục tiêu có thể được định nghĩa là việc tìm kiếm một vectơ các biến quyết định thỏa mãn các ràng buộc và tối ưu hóa một hàm vectơ. Các hàm mục tiêu thường đối kháng lẫn nhau, điều này dẫn đến việc cần phải xác định một tiêu chuẩn để đánh giá các giải pháp khả thi. Các ràng buộc trong bài toán này có thể được biểu diễn dưới dạng bất đẳng thức toán học, và các hàm mục tiêu có thể cực tiểu hóa hoặc cực đại hóa. Việc tìm kiếm giải pháp tối ưu trong bối cảnh này thường yêu cầu sử dụng các phương pháp tính toán thông minh như giải thuật di truyền.

1.2. Khái niệm tối ưu Pareto

Khái niệm tối ưu Pareto, được giới thiệu bởi Vilfredo Pareto, là một trong những khái niệm cốt lõi trong tối ưu đa mục tiêu. Một giải pháp được coi là tối ưu Pareto nếu không có giải pháp nào khác tốt hơn mà không làm giảm giá trị của ít nhất một hàm mục tiêu. Điều này dẫn đến việc hình thành tập các giải pháp tối ưu Pareto, nơi mà mỗi giải pháp trong tập này đều có giá trị riêng. Việc tìm kiếm và phân tích các giải pháp tối ưu Pareto là một phần quan trọng trong nghiên cứu tối ưu hóa, giúp các nhà nghiên cứu và kỹ sư đưa ra quyết định tốt hơn trong các tình huống phức tạp.

II. Giải thuật di truyền cho bài toán tối ưu đa mục tiêu

Giải thuật di truyền (GA) là một trong những phương pháp tính toán phổ biến và hiệu quả trong việc giải quyết bài toán tối ưu đa mục tiêu. GA hoạt động dựa trên nguyên lý chọn lọc tự nhiên, nơi mà các cá thể trong quần thể được chọn lọc và lai ghép để tạo ra thế hệ mới với các đặc điểm tốt hơn. Các nguyên tắc căn bản của GA bao gồm chọn lọc, lai ghép và đột biến. Việc áp dụng GA cho bài toán tối ưu đa mục tiêu đã dẫn đến sự phát triển của nhiều thuật toán như MOGA, NSGA2, SPEA2, và SEAMO2. Mỗi thuật toán có những ưu điểm và nhược điểm riêng, và việc lựa chọn thuật toán phù hợp phụ thuộc vào đặc điểm cụ thể của bài toán cần giải quyết.

2.1. Giới thiệu về giải thuật di truyền

Giải thuật di truyền là một phương pháp tối ưu hóa dựa trên nguyên lý tiến hóa tự nhiên. Nó sử dụng các khái niệm như chọn lọc tự nhiên, lai ghép và đột biến để tìm kiếm giải pháp tối ưu cho bài toán. Trong bối cảnh tối ưu đa mục tiêu, GA cho phép tìm kiếm một tập hợp các giải pháp tối ưu Pareto, giúp các nhà nghiên cứu có thể đưa ra quyết định tốt hơn. Việc áp dụng GA trong các bài toán thực tế đã chứng minh được tính hiệu quả và khả năng thích ứng cao của nó.

2.2. Các vấn đề chính trong tìm kiếm đa mục tiêu

Trong quá trình tìm kiếm giải pháp cho bài toán tối ưu đa mục tiêu, có một số vấn đề chính cần được xem xét. Đầu tiên là vấn đề hội tụ, tức là khả năng của thuật toán trong việc tìm kiếm các giải pháp tối ưu trong một khoảng thời gian ngắn. Thứ hai là vấn đề đa dạng, liên quan đến việc duy trì sự đa dạng trong quần thể để tránh tình trạng hội tụ sớm vào các giải pháp không tối ưu. Cuối cùng, việc đánh giá và so sánh các giải pháp cũng là một thách thức lớn, đặc biệt khi các hàm mục tiêu có thể không thể so sánh trực tiếp với nhau.

III. Kết quả thực nghiệm và đánh giá

Kết quả thực nghiệm từ việc áp dụng giải thuật di truyền cho bài toán tối ưu đa mục tiêu cho thấy sự cải thiện đáng kể trong việc tìm kiếm các giải pháp tối ưu. Các thuật toán như SEAMO2 đã được cài đặt và thử nghiệm với nhiều bộ dữ liệu khác nhau, cho thấy khả năng hội tụ nhanh và độ chính xác cao trong việc tìm kiếm các giải pháp tối ưu Pareto. Việc so sánh với các thuật toán khác như SPEA2 và NSGA2 cũng cho thấy SEAMO2 có những ưu điểm vượt trội trong một số trường hợp nhất định. Những kết quả này không chỉ có giá trị lý thuyết mà còn có ứng dụng thực tiễn trong nhiều lĩnh vực như logistics, quản lý tài nguyên và thiết kế kỹ thuật.

3.1. Cài đặt thuật toán SEAMO2

Thuật toán SEAMO2 được cài đặt với các tham số tối ưu hóa cụ thể để đảm bảo hiệu suất cao nhất trong việc tìm kiếm giải pháp tối ưu đa mục tiêu. Việc lựa chọn các tham số như kích thước quần thể, tỷ lệ lai ghép và tỷ lệ đột biến có ảnh hưởng lớn đến kết quả cuối cùng. Các thử nghiệm cho thấy rằng việc điều chỉnh các tham số này có thể dẫn đến sự cải thiện đáng kể trong khả năng hội tụ và độ chính xác của giải pháp.

3.2. Kết quả thực nghiệm

Kết quả thực nghiệm cho thấy rằng thuật toán SEAMO2 có khả năng tìm kiếm các giải pháp tối ưu Pareto một cách hiệu quả. So sánh với các thuật toán khác như SPEA2 và NSGA2, SEAMO2 cho thấy sự vượt trội trong nhiều trường hợp, đặc biệt là trong các bài toán có độ phức tạp cao. Những kết quả này không chỉ khẳng định tính hiệu quả của SEAMO2 mà còn mở ra hướng nghiên cứu mới cho việc cải tiến các thuật toán di truyền trong tương lai.

Nội dung chính

Tổng quan nghiên cứu

Tối ưu đa mục tiêu là lĩnh vực nghiên cứu quan trọng trong khoa học máy tính và kỹ thuật phần mềm, đặc biệt khi các bài toán thực tế thường yêu cầu tối ưu đồng thời nhiều mục tiêu cạnh tranh nhau. Theo ước tính, các bài toán tối ưu đa mục tiêu xuất hiện phổ biến trong các lĩnh vực như định tuyến giao thông, quản lý tài nguyên, và lập kế hoạch sản xuất. Luận văn tập trung nghiên cứu giải thuật di truyền (Genetic Algorithm - GA) nhằm giải quyết bài toán tối ưu đa mục tiêu, cụ thể là bài toán cái túi 0-1 đa mục tiêu với bộ dữ liệu kn750.2 gồm 750 đồ vật và 2 mục tiêu. Mục tiêu chính là cải tiến chiến lược chọn lọc tự nhiên trong thuật toán SEAMO2 để nâng cao hiệu quả tìm kiếm và chất lượng lời giải. Phạm vi nghiên cứu tập trung vào việc áp dụng và cải tiến các toán tử di truyền trên bộ dữ liệu thực nghiệm, so sánh với các thuật toán tối ưu đa mục tiêu phổ biến như NSGA2 và SPEA2. Nghiên cứu có ý nghĩa quan trọng trong việc phát triển các thuật toán tiến hóa đa mục tiêu, góp phần nâng cao hiệu quả giải quyết các bài toán phức tạp trong thực tế, đồng thời cung cấp cơ sở lý thuyết và thực nghiệm cho các ứng dụng trong công nghệ thông tin và kỹ thuật phần mềm.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Tối ưu đa mục tiêu (Multiobjective Optimization): Tập trung vào việc tìm kiếm các lời giải tối ưu Pareto, trong đó không có lời giải nào vượt trội hoàn toàn các lời giải khác. Khái niệm tối ưu Pareto và trội Pareto được sử dụng làm tiêu chuẩn đánh giá lời giải.
• Bài toán cái túi đa mục tiêu (Multiobjective Knapsack Problem - MKP): Mô hình toán học tổng quát hóa bài toán cái túi 0-1, trong đó cần chọn tập con đồ vật sao cho tối đa hóa giá trị trong các túi mà không vượt quá giới hạn trọng lượng.
• Giải thuật di truyền (Genetic Algorithm - GA): Mô phỏng quá trình tiến hóa tự nhiên với các toán tử lai ghép, đột biến và chọn lọc nhằm tìm kiếm lời giải tối ưu. Các thuật toán GA đa mục tiêu như MOGA, NSGA2, SPEA2, SEAMO2 được nghiên cứu và so sánh.
• Chiến lược chọn lọc tự nhiên trong GA: Tập trung vào các phương pháp thay thế cá thể con vào quần thể cha mẹ nhằm duy trì đa dạng và cải thiện chất lượng quần thể.

Các khái niệm chính bao gồm: biến quyết định, hàm mục tiêu, ràng buộc, tập lời giải khả thi, tập lời giải tối ưu Pareto, khoảng cách quy tụ (crowding distance), và các toán tử di truyền như Single point crossover, Cycle crossover, Insertion mutation.

Phương pháp nghiên cứu

Luận văn sử dụng phương pháp nghiên cứu tổng hợp và thực nghiệm:

• Nguồn dữ liệu: Thu thập từ tài liệu chuyên ngành, bài báo khoa học, sách và các nguồn trực tuyến liên quan đến giải thuật di truyền và bài toán tối ưu đa mục tiêu.
• Phân tích lý thuyết: Tổng hợp các mô hình giải thuật di truyền hiện có, đặc biệt là SEAMO2, NSGA2, SPEA2, và các chiến lược chọn lọc cá thể.
• Thực nghiệm: Cài đặt thuật toán SEAMO2 và đề xuất cải tiến SEAMO2_LG trên bộ dữ liệu kn750.2 với 750 đồ vật và 2 mục tiêu. Sử dụng kích thước quần thể 250, xác suất đột biến 1%, chạy 30 lần độc lập với số thế hệ 500 và 1920.
• Phân tích kết quả: So sánh hiệu suất thuật toán dựa trên các tham số độ bao phủ (Coverage) và kích thước không gian bao phủ, đánh giá sự hội tụ và đa dạng của quần thể.
• Timeline nghiên cứu: Nghiên cứu và phát triển thuật toán trong năm 2014, với các giai đoạn thu thập tài liệu, cài đặt thuật toán, thực nghiệm và phân tích kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của các toán tử lai ghép và đột biến:

   • Trong mô hình mã hóa nhị phân, toán tử lai ghép Uniform crossover cho kết quả tốt hơn so với Single point và Two point crossover.
   • Trong mô hình mã hóa hoán vị, phép đột biến Insertion mutation vượt trội hơn so với Inversion và Displaced Inversion mutation.
   • Kết quả thực nghiệm trên bộ dữ liệu kn750.2 cho thấy mô hình mã hóa hoán vị với Cycle crossover và Insertion mutation đạt hiệu quả cao hơn mô hình mã hóa nhị phân.

2. Chiến lược chọn lọc cá thể trong SEAMO2:

   • Tỷ lệ thay thế cá thể con tốt hơn cha mẹ trong SEAMO2 giảm dần theo số thế hệ, từ khoảng 22,38% ở 100 thế hệ xuống còn 1,40% ở 1920 thế hệ.
   • Chiến lược thay thế ngẫu nhiên cá thể trong quần thể chiếm tỷ lệ lớn nhất (khoảng 41,63% ở 100 thế hệ).
   • Tỷ lệ cá thể bị loại do trùng lặp duy trì ở mức khoảng 5%.

3. Cải tiến thuật toán SEAMO2_LG:

   • Áp dụng chiến lược thay thế cá thể con bằng cá thể tồi nhất trong lân cận giúp quần thể hội tụ nhanh hơn về tập nghiệm tối ưu.
   • Tỷ lệ cá thể con tốt hơn cha mẹ tăng lên đáng kể, ví dụ từ 22,38% lên 30,36% ở 100 thế hệ.
   • Tỷ lệ thay thế cá thể tồi nhất giảm nhẹ so với SEAMO2, đồng thời tỷ lệ cá thể bị loại tăng lên, giúp loại bỏ các cá thể kém hiệu quả nhanh hơn.
   • Độ bao phủ trung bình của SEAMO2_LG cao hơn SEAMO2 ở 500 thế hệ (22% so với 17,97%) và vẫn giữ ưu thế ở 1920 thế hệ.

4. So sánh với các thuật toán NSGA2 và SPEA2:

   • SEAMO2_LG có độ bao phủ tốt hơn NSGA2 (79,33% so với 59,67% ở 500 thế hệ).
   • Tuy nhiên, SPEA2 vẫn cho kết quả tốt hơn SEAMO2_LG về độ bao phủ.
   • SEAMO2_LG thể hiện khả năng cạnh tranh cao trong việc giải quyết bài toán cái túi đa mục tiêu.

Thảo luận kết quả

Kết quả thực nghiệm cho thấy việc cải tiến chiến lược chọn lọc trong SEAMO2 bằng cách giới hạn không gian tìm kiếm và thay thế cá thể tồi nhất trong lân cận giúp tăng tốc độ hội tụ và cải thiện chất lượng lời giải. Việc sử dụng mô hình mã hóa hoán vị cùng các toán tử lai ghép và đột biến phù hợp cũng góp phần nâng cao hiệu quả thuật toán. So với các thuật toán tiến hóa đa mục tiêu phổ biến như NSGA2 và SPEA2, SEAMO2_LG thể hiện sự cạnh tranh tốt, đặc biệt trong các lần chạy ngắn và trung bình. Tuy nhiên, SPEA2 vẫn giữ ưu thế về độ bao phủ tổng thể, cho thấy cần tiếp tục nghiên cứu để cải tiến thêm. Các biểu đồ so sánh độ bao phủ và tỷ lệ thay thế cá thể minh họa rõ sự khác biệt về hiệu suất giữa các thuật toán, đồng thời phản ánh sự cân bằng giữa đa dạng quần thể và hội tụ về tập nghiệm tối ưu.

Đề xuất và khuyến nghị

1. Áp dụng chiến lược chọn lọc cá thể tồi nhất trong lân cận:

   • Động từ hành động: Triển khai
   • Target metric: Tăng tốc độ hội tụ và cải thiện chất lượng lời giải
   • Timeline: 6-12 tháng
   • Chủ thể thực hiện: Các nhà nghiên cứu và phát triển thuật toán tiến hóa

2. Tối ưu hóa các toán tử lai ghép và đột biến:

   • Động từ hành động: Tinh chỉnh
   • Target metric: Nâng cao hiệu quả tìm kiếm và đa dạng quần thể
   • Timeline: 3-6 tháng
   • Chủ thể thực hiện: Nhóm nghiên cứu thuật toán và kỹ sư phần mềm

3. Mở rộng thử nghiệm trên các bộ dữ liệu đa mục tiêu khác:

   • Động từ hành động: Mở rộng
   • Target metric: Đánh giá tính tổng quát và khả năng áp dụng thuật toán
   • Timeline: 6 tháng
   • Chủ thể thực hiện: Các phòng thí nghiệm nghiên cứu và doanh nghiệp ứng dụng

4. Phát triển giao diện phần mềm hỗ trợ thuật toán SEAMO2_LG:

   • Động từ hành động: Phát triển
   • Target metric: Tăng khả năng ứng dụng thực tế và tiếp cận người dùng
   • Timeline: 9-12 tháng
   • Chủ thể thực hiện: Đội ngũ phát triển phần mềm và chuyên gia công nghệ thông tin

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và giảng viên trong lĩnh vực công nghệ thông tin và kỹ thuật phần mềm:

   • Lợi ích: Cung cấp cơ sở lý thuyết và thực nghiệm về giải thuật di truyền đa mục tiêu.
   • Use case: Phát triển các đề tài nghiên cứu mới hoặc giảng dạy chuyên sâu về tối ưu hóa.

2. Kỹ sư phát triển phần mềm và chuyên gia tối ưu hóa:

   • Lợi ích: Áp dụng các thuật toán tiến hóa cải tiến vào giải quyết bài toán thực tế.
   • Use case: Tối ưu hóa quy trình sản xuất, lập kế hoạch logistics, hoặc thiết kế hệ thống.

3. Sinh viên cao học và nghiên cứu sinh ngành công nghệ thông tin:

   • Lợi ích: Tham khảo phương pháp nghiên cứu, cài đặt thuật toán và phân tích kết quả.
   • Use case: Tham khảo để hoàn thiện luận văn thạc sĩ hoặc tiến sĩ liên quan đến tối ưu hóa.

4. Doanh nghiệp và tổ chức ứng dụng công nghệ tối ưu hóa:

   • Lợi ích: Nâng cao hiệu quả vận hành và ra quyết định dựa trên các thuật toán tối ưu đa mục tiêu.
   • Use case: Ứng dụng trong quản lý chuỗi cung ứng, phân phối, và các hệ thống phức tạp khác.

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

1. Giải thuật di truyền là gì và tại sao lại phù hợp với bài toán đa mục tiêu?
   Giải thuật di truyền mô phỏng quá trình tiến hóa tự nhiên, sử dụng các toán tử lai ghép và đột biến để tìm kiếm lời giải tối ưu. Nó phù hợp với bài toán đa mục tiêu vì khả năng xử lý song song nhiều lời giải, duy trì đa dạng quần thể và tìm kiếm hiệu quả trong không gian lời giải phức tạp.

2. Mô hình mã hóa nhị phân và mã hóa hoán vị khác nhau như thế nào?
   Mã hóa nhị phân biểu diễn lời giải dưới dạng chuỗi bit 0-1, phù hợp với bài toán chọn hoặc không chọn. Mã hóa hoán vị biểu diễn lời giải dưới dạng dãy sắp xếp các đối tượng, thích hợp cho bài toán cần sắp xếp hoặc phân phối. Mã hóa hoán vị thường cho kết quả tốt hơn trong bài toán cái túi đa mục tiêu.

3. Chiến lược chọn lọc cá thể tồi nhất trong lân cận có ưu điểm gì?
   Chiến lược này giúp duy trì đa dạng quần thể bằng cách thay thế cá thể con bằng cá thể kém nhất trong vùng lân cận, từ đó tăng tốc độ hội tụ và tránh tối ưu cục bộ. Đồng thời, nó giảm thiểu thời gian tìm kiếm cá thể thay thế so với việc tìm kiếm toàn bộ quần thể.

4. Thuật toán SEAMO2_LG có thể áp dụng cho các bài toán đa mục tiêu khác không?
   Có, SEAMO2_LG với chiến lược chọn lọc cải tiến có thể áp dụng cho nhiều bài toán tối ưu đa mục tiêu khác nhau, đặc biệt là các bài toán tổ hợp phức tạp có không gian lời giải lớn và yêu cầu duy trì đa dạng lời giải.

5. Làm thế nào để đánh giá hiệu quả của các thuật toán tối ưu đa mục tiêu?
   Hiệu quả thường được đánh giá qua các tham số như độ bao phủ (Coverage), kích thước không gian bao phủ, khoảng cách quy tụ, và phân bố lời giải trên biên Pareto. Các tham số này giúp so sánh chất lượng và đa dạng của tập lời giải thu được từ các thuật toán khác nhau.

Kết luận

• Luận văn đã nghiên cứu và cải tiến chiến lược chọn lọc trong giải thuật di truyền SEAMO2 nhằm nâng cao hiệu quả giải bài toán tối ưu đa mục tiêu, đặc biệt là bài toán cái túi 0-1 đa mục tiêu.
• Mô hình mã hóa hoán vị kết hợp với các toán tử lai ghép Cycle crossover và đột biến Insertion mutation cho kết quả tốt hơn mô hình mã hóa nhị phân.
• Thuật toán SEAMO2_LG với chiến lược thay thế cá thể tồi nhất trong lân cận giúp quần thể hội tụ nhanh hơn và cải thiện chất lượng lời giải so với SEAMO2 gốc.
• So sánh với các thuật toán NSGA2 và SPEA2 cho thấy SEAMO2_LG có khả năng cạnh tranh cao, đặc biệt vượt trội hơn NSGA2 về độ bao phủ.
• Các bước tiếp theo bao gồm mở rộng thử nghiệm trên các bộ dữ liệu khác, tối ưu hóa các toán tử di truyền và phát triển phần mềm hỗ trợ ứng dụng thuật toán trong thực tế.

Khuyến khích các nhà nghiên cứu và kỹ sư công nghệ thông tin áp dụng và phát triển thêm các chiến lược chọn lọc trong giải thuật di truyền để giải quyết các bài toán đa mục tiêu phức tạp trong thực tế.

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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ TRẦN HẢI THANH GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN ĐA MỤC TIÊU LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Hà Nội – 2014 z ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ Trần Hải Thanh GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN ĐA MỤC TIÊU Ngành: Công nghệ thông tin Chuyên ngành: Kỹ thuật phần mềm Mã số: 60480103 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. LÊ NGUYÊN KHÔI Hà Nội – 2014 z LỜI CẢM ƠN Đầu tiên, tôi xin chân thành cảm ơn TS. Lê Nguyên Khôi đã tận tâm hướng dẫn chỉ bảo và giúp đỡ tôi hoàn thành đề tài luận văn này. Tôi xin gửi lời cảm ơn đến quý thầy cô ở khoa Công nghệ Thông tin, phòng Đào tạo trường Đại học Công nghệ – Đại học Quốc gia Hà Nội đã tạo điều kiện thuận lợi cho các học viên cao học như tôi trong suốt thời gian học tập tại trường.

Tôi cũng gửi lời cám ơn đến gia đình, bạn bè và đồng nghiệp, những người đã luôn bên tôi, động viên và khuyến khích tôi trong quá trình thực hiện đề tài nghiên cứu của mình. Tuy đã có những cố gắng nhất định, tiếp cận với thực tế để tìm hiểu và áp dụng khoa học vào cuộc sống, nhưng do thời gian và trình độ còn nhiều hạn chế nên luận văn này khó tránh khỏi các thiếu sót. Kính mong nhận được sự đóng góp ý kiến của thầy cô và các bạn. Sau cùng, tôi xin kính chúc quý thầy cô trong khoa Công nghệ Thông tin cũng như Ban Giám Hiệu trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội dồi dào sức khỏe, niềm tin để tiếp tục thực hiện sứ mệnh cao đẹp của mình là truyền đạt kiến thức cho thế hệ mai sau.

Hà Nội, ngày tháng năm 2014 Học viên Trần Hải Thanh z 4 LỜI CAM ĐOAN Tôi xin cam đoan rằng số liệu và kết quả nghiên cứu trong luận văn này là trung thực và không trùng lặp với các đề tài khác của cá nhân tôi, được thực hiện dưới sự hướng dẫn khoa học của Tiến sĩ Lê Nguyên Khôi. Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã được cảm ơn và các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc. Học viên Trần Hải Thanh z 5 Mục Lục LỜI CẢM ƠN. 3 LỜI CAM ĐOAN.

4 Danh mục các ký hiệu và chữ viết tắt. 7 Danh mục các hình vẽ đồ thị. 8 Danh mục các bảng. 10 CHƢƠNG 1 TỔNG QUAN VỀ TỐI ƢU ĐA MỤC TIÊU.

Giới thiệu bài toán tối ưu đa mục tiêu. Mô hình bài toán tối ưu đa mục tiêu có ràng buộc. Khái niệm tối ưu Pareto. Khái niệm trội Pareto.

Tập các lời giải tối ưu Pareto. Bài toán cái túi bị chặn. Bài toán cái túi không bị chặn. Bài toán cái túi đa mục tiêu.

Mô hình bài toán cái túi đa mục tiêu. Mô hình mã nhị phân. Mô hình mã hóa hoán vị. Một số ví dụ mã hóa đối với bài toán cái túi đa mục tiêu .1 Mô hình mã hóa nhị phân.

Mô hình mã hóa hoán vị. 19 CHƢƠNG 2 GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN TỐI ƢU ĐA MỤC TIÊU .Giới thiệu về giải thuật di truyền. Các nguyên tắc căn bản của giải thuật di truyền. Các vấn đề chính trong tìm kiếm đa mục tiêu.

Mô hình tổng quát giải thuật tiến hóa. Một số thuật toán thường được áp dụng giải bài toán tối ưu đa mục tiêu. Thuật toán MOGA. Thuật toán VEGA.

Thuật toán SEAMO, SEAMO2. Thuật toán NSGA, NSGA2. Thuật toán SPEA, SPEA2. 35 CHƢƠNG 3 KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ.

Cài đặt thuật toán SEAMO2. Thuật toán SEAMO2. Dữ liệu của bài toán. Phương pháp so sánh.

Mô hình và các toán tử cho bài toán cái túi 0-1 đa mục tiêu. Thuật toán SEAMO2_LG. Chiến lược chọn lọc cá thể của thuật toán SEAMO2. Đề xuất cải tiến.

Kết quả thực nghiệm. So sánh với thuật toán SPEA2, NSGA2. 51 TÀI LIỆU THAM KHẢO. 52 z 7 Danh mục các ký hiệu và chữ viết tắt GA : Genetic Algorithms MOGA : Multi-Objective Evolutionary Algorithms : Nondominated Sorting in Genetic NSGA Algorithms : A Simple Evolutionary Algorithm for SEAMO Multi-objective Optimization SPEA : Strength Pareto Evolutionary Algorithm ⃗=(x1,…,xn) : Vector biến quyết định ( ⃗) ( ( ⃗) ( ⃗) ( ⃗)) : Vector hàm mục tiêu nu : Số nghiệm trội hơn nghiệm u Su : Tập nghiệm trội bởi nghiệm u P : Quần thể ban đầu Fj : Biên chứa các nghiệm không trội thứ j, j =1,…,R Q : Tập lưu trữ nghiệm không trội qua mỗi thế hệ Pt : Quần thể cha Qt : Quần thể con tạo thành t các cá thể trong Pt Fj : Biên chứa các nghiện không trội thứ j, {j=1,…,R} N : Số lượng cá thể trong quần thể Pt NE : Số lượng lớn nhất mà tập E có thể chứa được các nghiệm không trội NP : Số lượng cá thể trong quần thể/kích thước tập P k Tham số của mật độ tính toán: k = √ : khoảng cách giữa nghiệm x đếm nghiệm lân cận gần nhất thứ k trong tập Et+1 z 8 Danh mục các hình vẽ đồ thị Hình 2.1 Mối liên hệ giữa không gian cá thể, vectơ quyết định và mục tiêu .2: Mô hình tổng quát giải thuật di truyền .3: Minh họa thuật toán MOGA .4:Minh họa biên chứa các nghiệm không trội và thứ hạng tương ứng .6: Minh họa khoảng cách quy tụ quanh nghiệm i .7: Minh họa các biên và thứ hạng .8: Minh họa sự quy tụ của các nghiệm quanh một nghiệm .9: Minh họa tính toán độ thích nghi của các cá thể .10: Minh họa cách xóa bỏ các nghiệm nào có δk nhỏ nhất .1: Mô hình mã hóa nhị phân .2: Mô hình mã hóa hoán vị .3: So sánh mã hóa nhị phân - mã hóa hoán vị .4: Minh họa không gian tìm kiếm .5: Thuật toán SEAMO2_LG .6: So sánh SEAMO2 và SEAMO2_LG – 500 thế hệ .7: So sánh SEAMO2 và SEAMO2_LG – 1920 thế hệ .8: So sánh thuật toán SEAMO2_LG với NSGA2, SPEA2.

50 z 9 Danh mục các bảng Bảng 1.1: Ví dụ bài toán cái túi đa mục tiêu .1: Tỷ lệ % thực hiện của các trường hợp thay thế - SEAMO2 .2: Tỷ lệ % thực hiện của các trường hợp thay thế - SEAMO2_LG .3: Độ bao phủ trung bình – 500 thế hệ .4: Độ bao phủ trung bình – 1920 thế hệ .5: Độ bao phủ trung bình. Lý do chọn đề tài Trên thực tế, tồn tại rất nhiều bài toán yêu cầu tối ưu hóa đồng thời nhiều mục tiêu (thường là cạnh tranh lẫn nhau) ví dụ như: định tuyến các phương tiện giao thông để xác định các tuyến đường tối ưu nhằm cung cấp dịch vụ cho một tập hợp các khách hàng có thể liên quan đến một số mục tiêu khác nhau: tổng quãng đường đi (hoặc thời gian thực hiện), lượng xe sử dụng, độ hài lòng của khách hàng (giao hàng trong khoảng thời gian đã thỏa thuận trước), … hay việc đi chợ mua thức ăn cần đảm bảo sao cho đủ lượng calo cần thiết, chất lượng bữa ăn đảm bảo, số tiền chi tiêu không vượt quá giới hạn, … Giải thuật di truyền (GA) là một trong những mô hình tính toán phổ biến và thành công nhất trong lĩnh vực tính toán thông minh. Cùng với các kỹ thuật tính toán thông minh khác như tính toán mờ (fuzzy computing), mạng Nơ-ron (neural networks), hệ đa tác tử (multi- agent systems), trí tuệ bầy đàn (swarm intelligence), giải thuật di truyền ngày càng phát triển, được áp dụng rộng rãi trong các lĩnh vực của cuộc sống. Đối với bài toán đa mục tiêu, đã có nhiều phương pháp nghiên cứu đề xuất ra các thuật toán để giải quyết bài toán như: MOGA, NSGA2, SPEA2, SEAMO2, … trong đó giải thuật SEAMO2 là hiệu quả hơn cả [4].

Với giải thuật SEAMO2, việc thay thế cá thể vào quần thể (thực hiện chiến lược chọn lọc tự nhiên) thì độ hội tụ về tập nghiệm tối ưu (với lần chạy ngắn) là chưa cao và khi quần thể nghiệm đã đạt ngưỡng tối ưu (với lần chạy dài) thì sẽ mất nhiều thời gian để loại cá thể không phù hợp. Chính vì vậy, tác giả mạnh dạn nghiên cứu phương pháp cải tiến chiến lược chọn lọc tự nhiên trong giải thuật SEAMO2 để giải các bài toán tối ưu đa mục tiêu trong luận văn: “Giải thuật di truyền cho bài toán đa mục tiêu”. Mục đích nghiên cứu Mục tiêu của luận văn là nghiên cứu các toán tử trong giải thuật di truyền (hay giải thuật tiến hóa nói chung) đặc biệt là toán tử chọn lọc tự nhiên để chọn lọc và thay thế các lời giải nhằm tối ưu tập lời giải thu được giúp cho giải thuật di truyền giải quyết hiệu quả các bài toán tối ưu đa mục tiêu. Mục đích cụ thể của luận văn là sử dụng các toán tử di truyền khác nhau đối với thuật toán SEAMO2, ứng dụng cho bài toán cái túi đa mục tiêu, thay đổi chiến lược chọn lọc tự nhiên của thuật toán nhằm cải tiến thuật toán.

Phương z 11 pháp này sẽ được so sánh với kết quả của các thuật toán tối ưu đa mục tiêu khác như: SPEA2, NSGA2, …[3,13,16,17]. Do đó mục tiêu của luận văn là: Nghiên cứu giải thuật di truyền cho bài toán đa mục tiêu. Nhiệm vụ nghiên cứu Nghiên cứu các mô hình của giải thuật di truyền có áp dụng các nguyên lý tiến hóa và trên cơ sở đó tiếp cận các ý tưởng t thuật toán di truyền để giải bài toán cái túi đa mục tiêu như: NSGA2, SPEA2, SEAMO2, cách thức tìm nghiệm của các thuật toán này để cải tiến thuật toán di truyền có áp dụng nguyên lý tiến hóa SEAMO2. Đối tượng và phạm vi nghiên cứu Tìm hiểu về bài toán tối ưu đa mục tiêu, bài toán cái túi 0-1 đa mục tiêu.

Tìm hiểu về giải thuật tiến hóa, các mô hình giải thuật tiến hóa có thể áp dụng cho bài toán cái túi 0 - 1 đa mục tiêu. Xây dựng ứng dụng giải bài toán cái túi 0 - 1 đa mục tiêu với giải thuật SEAMO2 và đề xuất phương pháp cải tiến giải thuật. So sánh kết quả thực nghiệm của phương pháp đề xuất với các kết quả của các thuật toán khác.