Nghiên Cứu Thuật Toán Tiến Hóa Đa Nhân Tố Trong Giải Quyết Bài Toán Tối Ưu - Luận Văn Thạc Sĩ

Luận văn thạc sĩ toán học phân tích nghiên cứu về thuật toán tiến hóa đa nhân tố giải quyết bài toán tối ưu, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho

• Tác giả: Nguyễn Dương Kiên
• Người hướng dẫn: TS. Trần Quý Nam
• Trường học: Học viện Công nghệ Bưu chính Viễn thông
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Nghiên Cứu Về Thuật Toán Tiến Hóa Đa Nhân Tố Giải Quyết Bài Toán Tối Ƣu
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Bài toán tối ƣu
• 1.2. Tối ƣu hóa tổ hợp
• 1.3. Giải bải toán tối ƣu
• 1.4. Thuật toán tiến hóa
• 2. CHƯƠNG 2: TIẾN HÓA ĐA NHÂN TỐ
• 2.1. Các khái niệm liên quan
• 2.2. Giải thuật tiến hóa đa nhân tố
• 2.3. Khởi tạo quần thể
• 2.4. Kỹ thuật di truyền
• 2.5. Đánh giá có chọn lọc
• 2.6. Sự lựa chọn
• 3. CHƯƠNG 3: ÁP DỤNG THUẬT TOÁN TIẾN HÓA ĐA NHÂN TỐ ĐỂ GIẢI CÁC BÀI TOÁN TỐI ƢU ĐƠN MỤC TIÊU
• 3.1. Bài toán Knapsack và bài toán Quadratic Assignment Problem
• 3.1.1. Bài toán Knapsack
• 3.1.2. Bài toán Quadratic Assignment
• 3.2. Áp dụng thuật toán tiến hóa đa nhân tố để giải đồng thời hai bài toán Knapsack và bài toán Quadratic Assignment Problem
• 3.3. Kết quả mô phỏng
• 3.4. Tham số thực nghiệm
• 3.5. Kết quả thực nghiệm
• KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về bài toán tối ưu và thuật toán tiến hóa

Luận văn tập trung vào nghiên cứu thuật toán tiến hóa đa nhân tố để giải quyết bài toán tối ưu. Bài toán tối ưu là vấn đề tìm giá trị cực đại hoặc cực tiểu của một hàm mục tiêu, được áp dụng rộng rãi trong các lĩnh vực như vật lý, hóa học, và kinh tế. Thuật toán tiến hóa (Evolutionary Algorithms - EAs) dựa trên học thuyết Darwin, mô phỏng quá trình tiến hóa tự nhiên để tìm ra giải pháp tối ưu. Các thuật toán này khởi tạo một quần thể các cá thể (giải pháp) và qua các thế hệ, chọn lọc những cá thể tốt nhất để tạo ra thế hệ tiếp theo. Các thuật toán tiến hóa phổ biến bao gồm thuật toán di truyền (GA), thuật toán tối ưu hóa bầy đàn (PSO), và thuật toán đàn kiến (ACO).

1.1. Bài toán tối ưu tổ hợp

Bài toán tối ưu tổ hợp là lớp bài toán mà các biến quyết định nhận giá trị trong một tập rời rạc, được giới hạn bởi các ràng buộc. Các bài toán tiêu biểu bao gồm bài toán người du lịch (TSP), bài toán cây khung nhỏ nhất (MST), bài toán phân công, và bài toán cái túi (Knapsack Problem). Ví dụ, bài toán cái túi yêu cầu chọn các đồ vật sao cho tổng giá trị lớn nhất mà không vượt quá sức chứa của túi. Các bài toán này thường phải đối mặt với sự bùng nổ tổ hợp, khi số lượng biến tăng lên, không gian tìm kiếm trở nên quá lớn, gây khó khăn cho việc tìm kiếm giải pháp tối ưu.

1.2. Giải thuật chính xác và gần đúng

Để giải quyết bài toán tối ưu, có hai phương pháp chính: giải thuật chính xác và giải thuật gần đúng. Giải thuật chính xác bao gồm vét cạn và thuật toán nhánh cận. Vét cạn liệt kê tất cả các phương án có thể, đảm bảo tìm ra nghiệm chính xác nhưng tốn nhiều thời gian. Thuật toán nhánh cận cải tiến bằng cách loại bỏ sớm các phương án không tối ưu, giảm không gian tìm kiếm. Giải thuật gần đúng như thuật toán tiến hóa không đảm bảo nghiệm chính xác nhưng có thời gian tính toán nhanh hơn, phù hợp với các bài toán lớn và phức tạp.

II. Mô hình tiến hóa đa nhân tố

Luận văn giới thiệu mô hình tiến hóa đa nhân tố (Multifactorial Optimization - MFO), một phương pháp mới cho phép giải quyết đồng thời nhiều bài toán tối ưu chỉ với một quần thể tiến hóa duy nhất. Mô hình tiến hóa đa nhân tố coi mỗi bài toán tối ưu là một nhân tố ảnh hưởng đến quá trình tiến hóa. Ưu điểm của phương pháp này là khả năng chuyển vật liệu di truyền từ các bài toán đơn giản sang các bài toán phức tạp, giúp tăng tốc quá trình tối ưu hóa và giảm thời gian tính toán.

2.1. Khởi tạo quần thể và kỹ thuật di truyền

Trong mô hình tiến hóa đa nhân tố, quần thể được khởi tạo ngẫu nhiên, và các cá thể trải qua quá trình chọn lọc, lai ghép, và đột biến để tạo ra thế hệ mới. Kỹ thuật di truyền được sử dụng để tối ưu hóa các bài toán, với mục tiêu tạo ra các cá thể có khả năng thích nghi cao hơn. Quá trình này lặp lại cho đến khi đạt được điều kiện dừng, thường là khi tìm được giải pháp đủ tốt hoặc đạt số thế hệ tối đa.

2.2. Đánh giá và lựa chọn

Đánh giá có chọn lọc là bước quan trọng trong mô hình tiến hóa đa nhân tố, giúp xác định các cá thể tốt nhất để tiếp tục quá trình tiến hóa. Các cá thể được đánh giá dựa trên hàm mục tiêu của từng bài toán, và chỉ những cá thể có giá trị hàm mục tiêu tốt nhất được giữ lại. Sự lựa chọn này đảm bảo rằng quần thể tiến hóa theo hướng tối ưu hóa các bài toán đa nhân tố.

III. Áp dụng thuật toán tiến hóa đa nhân tố

Luận văn áp dụng thuật toán tiến hóa đa nhân tố để giải các bài toán tối ưu đơn mục tiêu, bao gồm bài toán Knapsack và bài toán Quadratic Assignment Problem (QAP). Kết quả thực nghiệm cho thấy thuật toán tiến hóa đa nhân tố (MFGA) có hiệu quả cao hơn so với thuật toán di truyền truyền thống (GA) trong việc tìm kiếm giải pháp tối ưu. Các tham số thực nghiệm được điều chỉnh để đảm bảo hiệu suất tối ưu của thuật toán.

3.1. Bài toán Knapsack và QAP

Bài toán Knapsack yêu cầu chọn các đồ vật sao cho tổng giá trị lớn nhất mà không vượt quá sức chứa của túi. Bài toán Quadratic Assignment Problem (QAP) liên quan đến việc phân công các công việc sao cho tổng chi phí là nhỏ nhất. Thuật toán tiến hóa đa nhân tố được áp dụng để giải đồng thời hai bài toán này, với kết quả mô phỏng cho thấy hiệu quả vượt trội so với các phương pháp truyền thống.

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

Kết quả thực nghiệm cho thấy thuật toán tiến hóa đa nhân tố (MFGA) đạt được giải pháp tối ưu nhanh hơn và chính xác hơn so với thuật toán di truyền (GA). Các tham số thực nghiệm như kích thước quần thể, tỷ lệ đột biến, và số thế hệ được điều chỉnh để tối ưu hóa hiệu suất của thuật toán. Kết quả này khẳng định tiềm năng ứng dụng của mô hình tiến hóa đa nhân tố trong các bài toán tối ưu phức tạp.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển nhanh chóng của khoa học máy tính và kỹ thuật, các bài toán tối ưu hóa tổ hợp ngày càng trở nên quan trọng với nhiều ứng dụng thực tiễn như phân công công việc, lập lịch, và thiết kế mạng. Theo ước tính, các bài toán tối ưu hóa tổ hợp thường có không gian tìm kiếm rất lớn, dẫn đến hiện tượng "bùng nổ tổ hợp" gây khó khăn cho việc tìm lời giải tối ưu trong thời gian hợp lý. Trước đây, các thuật toán tiến hóa truyền thống như thuật toán di truyền (GA), tối ưu bầy đàn (PSO) chỉ tập trung giải quyết một bài toán tối ưu tại một thời điểm, chưa khai thác hiệu quả khi phải xử lý đồng thời nhiều bài toán tối ưu khác nhau.

Mục tiêu nghiên cứu của luận văn là phát triển và ứng dụng thuật toán tiến hóa đa nhân tố (Multifactorial Evolutionary Algorithm - MFEA) nhằm giải quyết đồng thời nhiều bài toán tối ưu hóa đơn mục tiêu sử dụng một quần thể tiến hóa duy nhất. Phạm vi nghiên cứu tập trung vào các bài toán tối ưu tổ hợp, đặc biệt là bài toán Knapsack và bài toán Quadratic Assignment Problem (QAP), với dữ liệu mô phỏng kích thước từ 4 đến 9 phần tử. Nghiên cứu được thực hiện tại Học viện Công nghệ Bưu chính Viễn thông, Hà Nội, trong năm 2020.

Ý nghĩa của nghiên cứu thể hiện qua việc giảm thiểu thời gian tính toán và tăng hiệu quả tìm kiếm lời giải tối ưu cho các bài toán phức tạp, đồng thời mở rộng khả năng ứng dụng thuật toán tiến hóa trong môi trường đa nhiệm vụ. Kết quả nghiên cứu góp phần nâng cao hiệu suất giải quyết các bài toán tối ưu hóa trong lĩnh vực hệ thống thông tin và kỹ thuật tính toán.

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 nền tảng các lý thuyết và mô hình sau:

• Thuật toán tiến hóa (Evolutionary Algorithms - EA): Mô phỏng quá trình tiến hóa sinh học dựa trên các bước khởi tạo quần thể, chọn lọc, lai ghép, đột biến và sinh sản. EA được sử dụng để giải các bài toán tối ưu hóa phức tạp, đặc biệt là các bài toán tổ hợp.

• Thuật toán tiến hóa đa nhân tố (Multifactorial Evolutionary Algorithm - MFEA): Mô hình tiến hóa đa nhiệm cho phép giải đồng thời nhiều bài toán tối ưu hóa khác nhau trên một quần thể duy nhất. MFEA sử dụng các khái niệm như factorial cost, factorial rank, scalar fitness và skill factor để đánh giá và lựa chọn cá thể phù hợp trong môi trường đa tác vụ.

• Khái niệm tối ưu hóa tổ hợp: Bao gồm các bài toán như bài toán Knapsack, bài toán phân công, bài toán cây khung nhỏ nhất, và bài toán người du lịch. Các bài toán này có không gian tìm kiếm rời rạc và bị giới hạn bởi các ràng buộc cụ thể.

• Các thuật toán giải bài toán tối ưu: Thuật toán chính xác như vét cạn, nhánh cận, quy hoạch động; và thuật toán gần đúng như heuristic, meta-heuristic (GA, PSO, SA).

Ba khái niệm chính được sử dụng trong nghiên cứu là factorial cost (giá trị mục tiêu cộng với phạt vi phạm ràng buộc), scalar fitness (đo độ thích nghi dựa trên xếp hạng factorial), và skill factor (tác vụ mà cá thể phù hợp nhất).

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

• Nguồn dữ liệu: Dữ liệu mô phỏng cho bài toán Knapsack và QAP với kích thước từ 4 đến 9 phần tử, được khởi tạo ngẫu nhiên.

• Phương pháp phân tích: Thuật toán MFEA được cài đặt trên Matlab, sử dụng các kỹ thuật mã hóa thực cho cá thể trong không gian tìm kiếm hợp nhất. Các cá thể được giải mã thành lời giải cụ thể cho từng bài toán thông qua kỹ thuật phân cụm nhị phân (cho Knapsack) và sắp xếp khóa ngẫu nhiên (cho QAP).

• Timeline nghiên cứu: Nghiên cứu được thực hiện trong năm 2020, bao gồm các bước tổng quan lý thuyết, thiết kế thuật toán, cài đặt mô phỏng, và phân tích kết quả.

• Cỡ mẫu và chọn mẫu: Quần thể tiến hóa gồm n cá thể được khởi tạo ngẫu nhiên, đảm bảo đại diện cho các tác vụ tối ưu hóa khác nhau. Phương pháp chọn mẫu dựa trên skill factor để cân bằng số lượng cá thể cho từng tác vụ.

• Phương pháp đánh giá: Đánh giá hiệu quả thuật toán dựa trên giá trị hàm mục tiêu, thời gian chạy, và so sánh với các thuật toán tiến hóa truyền thống như GA.

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

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

1. Hiệu quả giải quyết đồng thời nhiều bài toán: Thuật toán MFEA cho phép giải đồng thời bài toán Knapsack và QAP trên cùng một quần thể với kích thước tối đa 9 phần tử. Kết quả mô phỏng cho thấy MFEA đạt hiệu quả tối ưu hoặc gần tối ưu với thời gian tính toán giảm đáng kể so với giải thuật GA truyền thống.

2. Giảm số lượng đánh giá hàm mục tiêu: Nhờ cơ chế selective imitation, MFEA chỉ đánh giá cá thể con cho tác vụ có skill factor tương ứng, giảm gần hệ số K (số lượng tác vụ) so với việc đánh giá toàn bộ tác vụ. Điều này giúp tiết kiệm chi phí tính toán đáng kể.

3. Cân bằng giữa khám phá và khai thác: Tham số rmp điều chỉnh xác suất lai ghép giữa các cá thể có skill factor khác nhau, giúp cân bằng giữa việc khám phá không gian tìm kiếm rộng và khai thác các vùng tiềm năng. Giá trị rmp phù hợp giúp tránh bị kẹt trong tối ưu cục bộ và duy trì đa dạng di truyền.

4. Khả năng chuyển giao vật liệu di truyền: MFEA tận dụng sự tương đồng giữa các tác vụ để chuyển giao các khối xây dựng di truyền hiệu quả, đẩy nhanh quá trình hội tụ. Ví dụ, các gen có giá trị cao trong bài toán Knapsack có thể hỗ trợ cải thiện lời giải cho bài toán QAP.

Thảo luận kết quả

Kết quả mô phỏng được trình bày qua các biểu đồ so sánh giá trị hàm mục tiêu và thời gian chạy giữa MFEA và GA trên các bộ dữ liệu kích thước khác nhau. MFEA thể hiện ưu thế rõ rệt khi kích thước bài toán tăng, nhờ khả năng xử lý đa nhiệm và giảm số lượng đánh giá hàm mục tiêu.

So với các nghiên cứu trước đây chỉ tập trung giải quyết từng bài toán riêng biệt, nghiên cứu này mở rộng phạm vi ứng dụng thuật toán tiến hóa sang môi trường đa tác vụ, phù hợp với các hệ thống tính toán đám mây và các bài toán phức tạp trong thực tế.

Nguyên nhân chính của hiệu quả này là do MFEA tận dụng được sự tương đồng giữa các tác vụ để chuyển giao vật liệu di truyền, đồng thời giảm thiểu chi phí tính toán nhờ cơ chế đánh giá chọn lọc. Tuy nhiên, việc lựa chọn tham số rmp và kích thước quần thể cần được cân nhắc kỹ để tránh mất đa dạng hoặc hội tụ chậm.

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

1. Tối ưu tham số thuật toán: Đề xuất điều chỉnh tham số rmp trong khoảng 0.2 đến 0.5 để cân bằng giữa lai ghép nội văn hóa và giao văn hóa, giúp tăng hiệu quả khám phá không gian tìm kiếm trong vòng 50-100 thế hệ. Chủ thể thực hiện: nhà nghiên cứu và kỹ sư phát triển thuật toán.

2. Mở rộng ứng dụng đa tác vụ: Khuyến nghị áp dụng MFEA cho các bài toán tối ưu đa nhiệm trong tính toán đám mây, lập lịch sản xuất, và phân tích dữ liệu lớn trong vòng 1-2 năm tới nhằm tận dụng khả năng xử lý đồng thời nhiều bài toán phức tạp.

3. Phát triển kỹ thuật mã hóa giải mã: Đề xuất nghiên cứu thêm các kỹ thuật mã hóa giải mã phù hợp với các bài toán tổ hợp phức tạp hơn, nhằm nâng cao khả năng biểu diễn và giảm thiểu sai số trong quá trình tiến hóa. Thời gian thực hiện: 6-12 tháng.

4. Tích hợp với các thuật toán khác: Khuyến nghị kết hợp MFEA với các thuật toán tìm kiếm cục bộ hoặc học máy để cải thiện khả năng hội tụ và độ chính xác lời giải trong các bài toán thực tế. Chủ thể thực hiện: nhóm nghiên cứu đa ngành trong 1 năm.

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

1. Nhà nghiên cứu và sinh viên ngành hệ thống thông tin, khoa học máy tính: Nắm bắt kiến thức về thuật toán tiến hóa đa nhân tố, áp dụng trong nghiên cứu và phát triển các thuật toán tối ưu hóa đa nhiệm.

2. Kỹ sư phát triển phần mềm tối ưu hóa: Áp dụng thuật toán MFEA để giải quyết các bài toán tối ưu phức tạp trong sản xuất, logistics, và quản lý tài nguyên.

3. Chuyên gia trong lĩnh vực tính toán đám mây và điện toán phân tán: Tận dụng khả năng xử lý đồng thời nhiều tác vụ tối ưu hóa để nâng cao hiệu suất hệ thống.

4. Nhà quản lý dự án và doanh nghiệp: Hiểu rõ tiềm năng ứng dụng thuật toán tiến hóa đa nhân tố trong việc tối ưu hóa quy trình kinh doanh và giảm chi phí vận hành.

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

1. Thuật toán tiến hóa đa nhân tố (MFEA) là gì?
   MFEA là một thuật toán tiến hóa cho phép giải đồng thời nhiều bài toán tối ưu hóa khác nhau trên một quần thể duy nhất, tận dụng sự tương đồng giữa các tác vụ để chuyển giao vật liệu di truyền và giảm chi phí tính toán.

2. MFEA khác gì so với thuật toán di truyền truyền thống?
   Khác biệt chính là MFEA xử lý đa tác vụ cùng lúc, trong khi thuật toán di truyền truyền thống chỉ giải quyết một bài toán tại một thời điểm với một quần thể riêng biệt.

3. Làm thế nào để mã hóa giải pháp trong MFEA?
   MFEA sử dụng không gian tìm kiếm hợp nhất với các khóa ngẫu nhiên biểu diễn các gen. Giải mã được thực hiện bằng cách ánh xạ khóa ngẫu nhiên sang lời giải cụ thể cho từng bài toán, ví dụ như phân cụm nhị phân cho Knapsack và sắp xếp khóa cho QAP.

4. MFEA có thể áp dụng cho những bài toán nào?
   MFEA phù hợp với các bài toán tối ưu hóa tổ hợp, đặc biệt là khi cần giải đồng thời nhiều bài toán đơn mục tiêu khác nhau như Knapsack, QAP, bài toán phân công, và các bài toán tối ưu đa nhiệm trong thực tế.

5. Làm sao để chọn tham số rmp trong MFEA?
   Tham số rmp điều chỉnh xác suất lai ghép giữa các cá thể có skill factor khác nhau. Giá trị rmp nên được điều chỉnh trong khoảng 0.2 đến 0.5 để cân bằng giữa khám phá và khai thác, tránh hội tụ sớm hoặc mất đa dạng.

Kết luận

• Thuật toán tiến hóa đa nhân tố (MFEA) là giải pháp hiệu quả cho việc giải đồng thời nhiều bài toán tối ưu hóa đơn mục tiêu trên một quần thể duy nhất.
• MFEA giảm đáng kể chi phí tính toán nhờ cơ chế đánh giá chọn lọc và tận dụng sự chuyển giao vật liệu di truyền giữa các tác vụ.
• Ứng dụng thành công trên bài toán Knapsack và Quadratic Assignment Problem với dữ liệu mô phỏng kích thước từ 4 đến 9 phần tử.
• Cần tiếp tục nghiên cứu tối ưu tham số thuật toán và mở rộng ứng dụng cho các bài toán phức tạp hơn trong thực tế.
• Khuyến khích các nhà nghiên cứu và kỹ sư áp dụng MFEA trong các lĩnh vực tính toán đám mây, logistics, và quản lý tài nguyên để nâng cao hiệu quả tối ưu hóa.

Đề nghị triển khai thử nghiệm MFEA trên các bộ dữ liệu thực tế lớn hơn và phối hợp với các kỹ thuật học máy để nâng cao hiệu quả giải pháp.

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

HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG —————————— Nguyễn Dƣơng Kiên NGHIÊN CỨU VỀ THUẬT TOÁN TIẾN HÓA ĐA NHÂN TỐ GIẢI QUYẾT BÀI TOÁN TỐI ƢU LUẬN VĂN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) Hà Nội - 2020 e HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG —————————— Nguyễn Dƣơng Kiên NGHIÊN CỨU VỀ THUẬT TOÁN TIẾN HÓA ĐA NHÂN TỐ GIẢI QUYẾT BÀI TOÁN TỐI ƢU Chuyên ngành: Hệ thống thông tin Mã số: 8.04 LUẬN VĂN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) NGƢỜI HƢỚNG DẪN KHOA HỌC: TS. Trần Quý Nam Hà Nội - 2020 e i LỜI CẢM ƠN Luận văn đƣợc hoàn thành dƣới sự hƣớng dẫn và chỉ bảo nhiệt tình của TS. Trần Quý Nam giảng viên học viện bƣu chính viễn thông. Trong quá trình làm việc, em không chỉ tích lũy đƣợc nhiều kiến thức và kinh nghiệm quý báu mà còn đƣợc học hỏi ở Thầy một tinh thần làm việc khoa học, đầy tinh thần trách nhiệm.

Qua đây, em xin bày tỏ lòng biết ơn chân thành và sâu sắc tới Thầy. Nhân dịp này, em cũng xin bày tỏ lòng biết ơn tới toàn thể các thầy cô giáo trong học viện Công nghệ Bƣu chính Viễn thông những ngƣời đã dạy bảo em tận tình trong suốt quá trình học tập và tạo điều kiện về cơ sở vật chất để em có thể hoàn thành tốt luận văn này. Cuối cùng, em xin đƣợc gửi lời cảm ơn chân thành tới gia đình, bạn bè đã cổ vũ, động viên và tạo điều kiện cho em trong quá trình học tập và thực hiện luận văn. Dù đã cố gắng hết sức cùng với sự tận tâm của thầy giáo hƣớng dẫn tuy nhiên do trình độ còn hạn chế nên khó tránh khỏi những thiếu sót, em rất mong nhận đƣợc sự đóng góp ý kiến của thầy cô và các bạn.

Hà Nội, ngày tháng năm 2020 Học viên cao học Nguyễn Dƣơng Kiên e ii MỤC LỤC LỜI CẢM ƠN. i DANH SÁCH BẢNG. iv DANH SÁCH HÌNH VẼ .1 Chƣơng 1 TỔNG QUAN .1 Bài toán tối ƣu .1 Tối ƣu hóa tổ hợp .2 Giải bải toán tối ƣu .2 Thuật toán tiến hóa .26 Chƣơng 2 TIẾN HÓA ĐA NHÂN TỐ.1 Các khái niệm liên quan .2 Giải thuật tiến hóa đa nhân tố .3 Khởi tạo quần thể .4 Kỹ thuật di truyền .5 Đánh giá có chọn lọc .6 Sự lựa chọn .37 Chƣơng 3 ÁP DỤNG THUẬT TOÁN TIẾN HÓA ĐA NHÂN TỐ ĐỂ GIẢI CÁC BÀI TOÁN TỐI ƢU ĐƠN MỤC TIÊU .1 Bài toán Knapsack và bài toán Quadratic Assignment Problem .1 Bài toán Knapsack .2 Bài toán Quadratic Assignment .2 Áp dụng thuật toán tiến hóa đa nhân tố để giải đồng thời hai bài toán Knapsack và bài toán Quadratic Assignment Problem .3 Kết quả mô phỏng .2 Tham số thực nghiệm .3 Kết quả thực nghiệm .44 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .46 TÀI LIỆU THAM KHẢO .47 e iv DANH SÁCH BẢNG Bảng 3-1: Kích thƣớc các bài toán sẽ kết hợp giải .43 Bảng 3-2: Tham số thực nghiệm .44 e v DANH SÁCH HÌNH VẼ Hình 1-1: Ví dụ cây khung của đồ thị .5 Hình 1-2: Sơ đồ khối cấu trúc thuật toán di truyền .17 Hình 1-3: Sơ đồ khối thuật toán PSO.23 Hình 1-4: Lời giải nhận đƣợc nhờ thay 2 cạnh (2,3), (1,6) bằng (1,3), (2,6) .25 Hình 1-5: Mô tả các bƣớc tổng thể của các EA .26 Hình 2-1:Nổi bật sự khác biệt giữa tối ƣu hóa đa mục tiêu và đa yếu tố.31 Hình 2-2: Mô tả các bƣớc tổng thể của các EA(thuật toán 1) .32 Hình 2-3: Mô tả các bƣớc tổng thể của các EA (thuật toán 2) .34 Hình 2-4: Mô tả các bƣớc tổng thể của EA (thuật toán 3) .36 Hình 3-1: Sự biểu diễn của các tác vụ trên các không gian tìm kiếm khác nhau đƣợc chuyển về không gian tìm kiếm hợp nhất .39 Hình 3-2: So sánh kết quả cảu MFGA với GA và lời giải tối ƣu trên bài toán QAP .44 Hình 3-3: So sánh kết quả của MFGA với GA và lời giải tối ƣu trên bài toán KP .45 e 1 LỜI NÓI ĐẦU Trong những năm vừa qua, các thuật toán tiến hóa đƣợc áp dụng để giải quyết nhiều bài toán tối ƣu trong khoa học máy tính và trong thực tế. Tuy nhiên, việc thiết kế các thuật toán tiến hóa mới chỉ tập trung vào việc giải quyết có hiệu quả một bài toán tối ƣu tại một thời điểm, chƣa có thuật toán tiến hóa giải quyết đồng thời các bài toán tối ƣu hóa chỉ sử dụng duy nhất một quần thể.

Do vậy, luận văn sẽ tìm hiểu một mô hình tiến hóa mới trong tính toán tiến hóa: mô hình tiến hóa đa nhân tố (Multifactorial Optimization) cho phép giải đồng thời nhiều bài toán tối ƣu mà chỉ dựa trên một quần thể tiến hóa duy nhất. Thuật toán tiến hóa (Evolutionary Algorithms - EAs) dựa theo học thuyết Darwin nói chung đƣợc hình thành trên quan niệm cho rằng, quá trình tiến hóa là quá trình hoàn hảo nhất vì tự nó đã mang tính tối ƣu [1]. Tính tối ƣu đƣợc thể hiện ở chỗ, cá thể sau đƣợc sinh ra bao giờ cũng tốt hơn, hoàn hảo hơn cá thể cha-mẹ, chúng có khả năng thích nghi với sự thay đổi của môi trƣờng cao hơn cá thể cha- mẹ. Thuật toán tiến hóa đƣợc áp dụng trong các bài toán tối ƣu.

Bài toán tối ƣu là bài toán tìm giá trị cực đại hoặc cực tiểu của một hàm hoặc một quá trình nào đó. Cơ chế này đƣợc sử dụng trong nhiều lĩnh vực nhƣ vật lý, hóa học, kinh tế,. Trong thuật toán tiến hóa, một nhóm các cá thể (giải pháp của bài toán) sẽ đƣợc khởi tạo ngẫu nhiên. Trong mỗi thế hệ, những cá thể tốt, thích nghi với môi trƣờng (bài toán) sẽ đƣợc giữ lại.

Quá trình tiếp tục cho đến khi gặp điều kiện dừng của bài toán. Có nhiều thuật toán tiến hóa khác nhau nhƣ: thuật toán di truyền (Genetic Algorithm – GA), thuật toán tối ƣu hóa bầy đàn (Particle Swarm Optimization – PSO), thuật toán đàn kiến (Ant Colony Optimization - ACO),.Trong đó, thuật toán di truyền đƣợc xây dựng dựa trên quy luật tiến hóa sinh học hay phát triển tự nhiên của một quần thể sống. Các cá thể trải qua một quá trình phát triển và sinh sản để tạo ra những cá thể mới cho thế hệ kế tiếp. Trong quá trình tăng trƣởng và phát triển những cá thể xấu tức là những cá thể không thích nghi đƣợc với môi trƣờng sẽ bị đào thải, ngƣợc lại, những cá thể tốt sẽ đƣợc giữ lại (đây chính là quá trình chọn lọc) và đƣợc lai ghép (quá trình lai ghép) để tạo ra những cá thể mới cho thế hệ sau.

Những cá thể e 2 mới đƣợc sinh ra mang những tính trạng của cá thể cha-mẹ (còn gọi là hiện tƣợng di truyền). Thuật toán tối ƣu bầy đàn đƣợc xây dựng dựa vào quá trình mô phỏng sinh học của đàn chim. Để hiểu rõ về thuật toán, hãy xem một ví dụ về quá trình tìm kiếm thức ăn của một đàn chim. Tại thời điểm tìm kiếm cả đàn bay theo một hƣớng nào đó, có thể là ngẫu nhiên.

Tuy nhiên, sau một thời gian tìm kiếm một số cá thể trong đàn bắt đầu tìm ra đƣợc nơi có chứa thức ăn. Tùy vào số lƣợng thức ăn vừa tìm đƣợc mà các cá thể gửi tín hiệu đến các cá thể đang tìm kiếm ở vùng lân cận. Tín hiệu này đƣợc lan truyền trên toàn quần thể. Dựa vào thông tin nhận đƣợc, mỗi cá thể sẽ điều chỉnh hƣớng bay và vận tốc bay theo hƣớng về nơi có nhiều thức ăn nhất.

Cơ chế truyền tin nhƣ vậy thƣờng đƣợc xem là một kiểu hình của trí tuệ bầy đàn. Cơ chế này giúp đàn chim tìm ra nơi có nhiều thức ăn nhất trên không gian tìm kiếm [2]. Các thuật toán tiến hóa trên chỉ dừng lại ở việc giải quyết một bài toán tối ƣu tại một thời điểm. Tuy nhiên, hầu hết các ứng dụng trong thực tế đều yêu cầu phải giải quyết nhiều bài toán tối ƣu cùng lúc, ví dụ nhƣ ứng dụng trong tính toán đám mây.

Do đó, luận văn sẽ tìm hiểu một mô hình tiến hóa mới: mô hình tiến hóa đa nhân tố (Multifactorial Optimization - MFO). Mô hình tiến hóa đa nhân tố là mô hình tiến hóa tổng hợp để giải quyết đồng thời nhiều bài toán tối ƣu. Mỗi bài toán tối ƣu đƣợc coi nhƣ một nhân tố ảnh hƣởng đến quá trình tiến hóa. Ƣu điểm của phƣơng pháp này là chúng ta có thể chuyển vật liệu di truyền từ các bài toán tối ƣu đơn giản đến các bài toán tối ƣu phức tạp.

Điều này có thể đẩy nhanh quá trình tối ƣu hóa, giảm thời gian thực hiện. Cấu trúc luận văn đƣợc tổ chức nhƣ sau Chƣơng 1: Luận văn sẽ trình bày tổng quan về bài toán tối ƣu hóa và các phƣơng pháp để giải quyết một bài toán tối ƣu hóa. Chƣơng 2: Luận văn sẽ trình bày về mô hình tiến hóa đa nhân tố và giải thuật tiến hóa đa nhân tố để giải quyết bài toán tối ƣu hóa. Chƣơng 3: Áp dụng thuật toán tiến hóa đa nhân tố để giải các bài toán tối ƣu đơn mục tiêu e 3 Chƣơng 1 TỔNG QUAN 1.1 Bài toán tối ƣu Giải thuật di truyền (Di truyền - Genetic Algorithm (GA)) Tối ƣu hóa là cơ chế tìm giá trị cực tiểu hoặc cực đại của một hàm hoặc một quá trình nào đó.

Cơ chế này đƣợc sử dụng trong nhiều lĩnh vực nhƣ vật lý, hóa học, kinh tế.để đạt đƣợc mục đích là tối đa hóa hiệu quả, sản xuất hoặc các thƣớc đo khác. Tối ƣu hóa liên quan đến hai khái niệm cực tiểu và cực đại của một hàm f nào đó. Đây là hai bài toán đối lập nhau, trong đó, tìm cực tiểu của hàm f tƣơng đƣơng với tìm cực đại của hàm −f. Về mặt toán học, bài toán tìm cực đại đƣợc định nghĩa nhƣ sau: f : Rn → R, (1.

Miền Rn đƣợc gọi là không gian tìm kiếm. Mỗi phần tử thuộc Rn đƣợc gọi là một giải pháp trong không gian tìm kiếm, X∗ đƣợc gọi là giải pháp tối ưu. Hàm f đƣợc gọi là hàm mục tiêu, hàm này xác định trong không gian n chiều và nhận giá trị thực. Bài toán tối ƣu hóa đƣợc chia làm hai loại chính đó là Tối ƣu rời rạc hay còn gọi là tối ƣu tổ hơp (TƢTH) và Tối ƣu liên tục.