Thạc Sĩ Giải thuật di truyền cho bài toán đa mục tiêu

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 . 9
MỞ ĐẦU . 10
CHƯƠNG 1 TỔNG QUAN VỀ TỐI ƯU ĐA MỤC TIÊU 12
1.1. Giới thiệu bài toán tối ưu đa mục tiêu 12
1.1.1. Mô hình bài toán tối ưu đa mục tiêu có ràng buộc . 12
1.1.2. Khái niệm tối ưu Pareto 13
1.1.3. Khái niệm trội Pareto 13
1.1.4. Tập các lời giải tối ưu Pareto 13
1.2. Bài toán cái túi (Knapsack) 14
1.2.1. Bài cái túi dạng 0-1 . 14
1.2.2. Bài toán cái túi bị chặn 15
1.2.3. Bài toán cái túi không bị chặn . 15
1.3. Bài toán cái túi đa mục tiêu 15
1.4. Mô hình bài toán cái túi đa mục tiêu 17
1.4.1. Mô hình mã nhị phân 17
1.4.2. Mô hình mã hóa hoán vị 18
1.4.3. Một số ví dụ mã hóa đối với bài toán cái túi đa mục tiêu . 18
1.4.3.1 Mô hình mã hóa nhị phân 18
1.4.3.2. 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 . 21
2.1.Giới thiệu về giải thuật di truyền 21
2.1.1. Các nguyên tắc căn bản của giải thuật di truyền . 21
2.1.2. Các vấn đề chính trong tìm kiếm đa mục tiêu 23
2.1.3. Mô hình tổng quát giải thuật tiến hóa . 24
2.2. 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 . 25
2.2.1. Thuật toán MOGA 25
2.2.2. Thuật toán VEGA . 26
2.2.3. Thuật toán SEAMO, SEAMO2 . 27
2.2.4. Thuật toán NSGA, NSGA2 . 30
2.2.5. Thuật toán SPEA, SPEA2 . 35
CHƯƠNG 3 KẾT QUẢ THỰC NGHIỆM VÀ ĐÁNH GIÁ 39
3.1. Cài đặt thuật toán SEAMO2 39
3.1.1. Thuật toán SEAMO2 . 39
3.1.2. Dữ liệu của bài toán 39
3.1.3. Phương pháp so sánh . 39
3.1.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 39
3.2. Thuật toán SEAMO2_LG 42
3.2.1. Chiến lược chọn lọc cá thể của thuật toán SEAMO2 . 42 6
3.2.2. Đề xuất cải tiến 43
3.2.3. Kết quả thực nghiệm . 46
3.3. So sánh với thuật toán SPEA2, NSGA2 49
KẾT LUẬN . 51
TÀI LIỆU THAM KHẢO . 52
Tiếng Việt 52
Tiếng Anh 52

7
Danh mục các ký hiệu và chữ viết tắt

GA : Genetic Algorithms
MOGA : Multi-Objective Evolutionary Algorithms
NSGA
: Nondominated Sorting in Genetic
Algorithms
SEAMO
: A Simple Evolutionary Algorithm for
Multi-objective Optimization
SPEA : Strength Pareto Evolutionary Algorithm ⃗ =(x 1 , ,x n ) : Vector biến quyết định ( ⃗) ( ( ⃗) ( ⃗) ( ⃗)) : Vector hàm mục tiêu
n u : Số nghiệm trội hơn nghiệm u
S u : Tập nghiệm trội bởi nghiệm u
P : Quần thể ban đầu
F j : 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ệ
P t : Quần thể cha
Q t : Quần thể con tạo thành t các cá thể trong
P t
F j : 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ể P t
N
E
: Số lượng lớn nhất mà tập E có thể chứa
được các nghiệm không trội
N
P
: 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
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 . 23
Hình 2.2: Mô hình tổng quát giải thuật di truyền . 25
Hình 2.3: Minh họa thuật toán MOGA . 26
Hình 2.4:Minh họa biên chứa các nghiệm không trội và thứ hạng tương ứng . 31
Hình 2.6: Minh họa khoảng cách quy tụ quanh nghiệm i . 34
Hình 2.7: Minh họa các biên và thứ hạng . 34
Hình 2.8: Minh họa sự quy tụ của các nghiệm quanh một nghiệm 35
Hình 2.9: Minh họa tính toán độ thích nghi của các cá thể 37
Hình 2.10: Minh họa cách xóa bỏ các nghiệm nào có δ k
nhỏ nhất 37
Hình 3.1: Mô hình mã hóa nhị phân . 40
Hình 3.2: Mô hình mã hóa hoán vị . 41
Hình 3.3: So sánh mã hóa nhị phân - mã hóa hoán vị 42
Hình 3.4: Minh họa không gian tìm kiếm . 44
Hình 3.5: Thuật toán SEAMO2_LG . 46
Hình 3.6: So sánh SEAMO2 và SEAMO2_LG – 500 thế hệ . 48
Hình 3.7: So sánh SEAMO2 và SEAMO2_LG – 1920 thế hệ . 49
Hình 3.8: So sánh thuật toán SEAMO2_LG với NSGA2, SPEA2 . 50
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 19
Bảng 3.1: Tỷ lệ % thực hiện của các trường hợp thay thế - SEAMO2 43
Bảng 3.2: Tỷ lệ % thực hiện của các trường hợp thay thế - SEAMO2_LG . 47
Bảng 3.3: Độ bao phủ trung bình – 500 thế hệ . 48
Bảng 3.4: Độ bao phủ trung bình – 1920 thế hệ . 49
Bảng 3.5: Độ bao phủ trung bình 50
10

MỞ ĐẦU
1. 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”.
2. 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 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.
3. 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.
4. Đố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.
5. Phương pháp nghiên cứu
Dựa trên tài liệu thu thập t nhiều nguồn (tài liệu, bài báo do giảng viên
hướng dẫn cung cấp, sách, báo, tạp chí, internet ) tổng hợp, phân tích và trình
bày lại theo sự hiểu biết của bản thân
Mở rộng các cách tiếp cận trước đây trên cơ sở phân tích đặc thù giải thuật,
bài toán cần giải quyết để đưa ra những ý kiến, đề xuất cải tiến hợp lý.
Ứng dụng những kết quả dựa trên nghiên cứu để xây dựng chương trình thực
nghiệm, t đó 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.