Thạc Sĩ Một lớp thuật toán phỏng tiến hóa sinh học dựa trên thông tin định hướng giải bài toán đa cực trị

LỜI CẢM ƠN
Luận án được thực hiện tại Bộ môn Công nghệ phần mềm, Khoa Công
nghệ thông tin, Học viện Kỹ thuật Quân sự dưới sự hướng dẫn khoa học
của PGS.TS. Bùi Thu Lâm.
Lời đầu tiên, tác giả xin được bày tỏ sự kính trọng và cảm ơn chân
thành nhất đến thầy giáo hướng dẫn: PGS.TS. Bùi Thu Lâm, người đã
định hướng để tác giả có thể tiếp cận lĩnh vực nghiên cứu mới mẻ, khó
khăn nhưng đầy tiềm năng này. Thầy đã cung cấp đầy đủ các kiến thức
cũng như kinh nghiệm nghiên cứu khoa học vô cùng quý báu, thầy cũng
là người động viên, khích lệ tác giả trong suốt quá trình nghiên cứu để tác
giả có thể hoàn thành cuốn luận án này.
Tác giả cũng xin chân thành cảm ơn tập thể cán bộ, giảng viên Bộ môn
Công nghệ phần mềm, Khoa Công nghệ thông tin và Phòng Đào tạo Sau
đại học, Học viện Kỹ thuật Quân sự đã tạo mọi điều kiện thuận lợi, giúp
đỡ tác giả trong quá trình học tập và nghiên cứu tại Học viện.
Tác giả cũng xin cảm ơn tập thể cán bộ, giảng viên Khoa Công nghệ
thông tin và Trung tâm Công nghệ thông tin, Trường Đại học Vinh đã tạo
điều kiện về thời gian để tác giả có thể thực hiện kế hoạch nghiên cứu và
hoàn thành luận án đúng tiến độ.
Cuối cùng, tác giả xin bày tỏ lòng biết ơn sâu sắc đến các bậc sinh
thành kính mến và những người thân trong gia đình, đặc biệt là người vợ
hết mực thủy chung và hai con thân thương đã luôn dành những tình cảm
nồng ấm, sẻ chia và ủng hộ tác giả trong suốt thời gian học tập và nghiên
cứu ở xa nhà. Luận án này như là món quà quý giá nhất của tác giả xin
đáp lại những ân tình của bạn bè, đồng nghiệp và niềm tin tưởng, yêu
thương của tất cả mọi người.
Một lần nữa xin chân thành cảm ơn.
Hà Nội, tháng 7 năm 2016
Nghiên cứu sinh
Vũ Chí Cường
2Mục lục
Trang
Danh sách ký hiệu, chữ viết tắt 6
Danh sách bảng 8
Danh sách hình vẽ 10
Lời mở đầu 11
1 CƠ SỞ LÝ THUYẾT 15
1.1 Mở đầu .15
1.2 Tối ưu hóa .15
1.3 Thuật toán tiến hóa .19
1.3.1 Cách biểu diễn di truyền lời giải của bài toán .20
1.3.2 Cách khởi tạo quần thể ban đầu 21
1.3.3 Cách đánh giá cá thể 22
1.3.4 Các phép toán tiến hóa .22
1.3.5 Điều kiện dừng của thuật toán .23
1.4 Kết luận .25
2 NHỮNG NỘI DUNG NGHIÊN CỨU LIÊN QUAN 27
2.1 Mở đầu .27
2.2 Các thuật toán tìm kiếm dựa trên thông tin định hướng .28
2.2.1 Thuật toán tìm kiếm đơn hình (Simplex Search) .28
2.2.2 Thuật toán tìm kiếm phân tán (Scatter Search) 30
2.2.3 Tối ưu bầy đàn (Particle Swarm Optimization) 32
2.2.4 Tiến hóa vi phân (Differential Evolution) 34
2.3 Phương pháp niching .38
2.3.1 Phương pháp chia sẻ giá trị đánh giá (Fitness sharing) .38
32.3.2 Phương pháp đám đông (Crowding) 40
2.3.3 Phương pháp dựa vào loài (Species-based) 42
2.3.4 Phương pháp phân cụm (Clustering-based) 44
2.4 Kỹ thuật song song hóa thuật toán tiến hóa 47
2.4.1 Mô hình master/slave 47
2.4.2 Mô hình island .48
2.4.3 Mô hình tế bào (cellular) .49
2.4.4 Mô hình lai (hybrid) .50
2.4.5 Kỹ thuật đồng tiến hóa hợp tác (cooperation co-evolution) .51
2.5 Kết luận .52
3 THUẬT TOÁN TIẾN HÓA DỰA TRÊN THÔNG TIN
ĐỊNH HƯỚNG 54
3.1 Mở đầu .54
3.2 Thuật toán DEAL .56
3.2.1 Độ phức tạp tính toán 59
3.2.2 Các tùy chọn về bước nhảy định hướng .60
3.2.3 Các chiến lược lai ghép 60
3.3 Song song DEAL với kỹ thuật đồng tiến hóa hợp tác .61
3.3.1 Mô hình song song .61
3.3.2 Thuật toán song song 63
3.3.3 Thời gian thực thi và hệ số tăng tốc 65
3.4 Đánh giá thực nghiệm 69
3.4.1 Thực nghiệm DEAL và MDEAL 69
3.4.2 Thực nghiệm DEAL song song .76
3.5 Kết luận .81
4 THUẬT TOÁN TIẾN HÓA DỰA TRÊN THÔNG TIN
ĐỊNH HƯỚNG VỚI BÀI TOÁN TỐI ƯU ĐA CỰC TRỊ 83
4.1 Mở đầu .83
4.2 DEAL với phương pháp Fitness Sharing .84
4.3 DEAL với phương pháp Crowding .85
44.4 DEAL với phương pháp Species-based 86
4.5 DEAL với phương pháp Clustering-based 88
4.6 Thực nghiệm 91
4.6.1 Môi trường thực nghiệm .91
4.6.2 Thực nghiệm 1: Hiệu quả của SharingDEAL .93
4.6.3 Thực nghiệm 2: Hiệu quả của CrowdingDEAL 96
4.6.4 Thực nghiệm 3: Hiệu quả của SpeciesDEAL . 101
4.6.5 Thực nghiệm 4: Hiệu quả của NBCDEAL 106
4.6.6 So sánh các thuật toán đã đề xuât . 111
4.7 Kết luận . 116
Kết luận 117
Danh sách công trình của tác giả 119
Tài liệu tham khảo 120
Phụ lục 131
A CÁC SƠ ĐỒ THUẬT TOÁN 131
A.1Thuật toán Simplex Search . 132
A.2Thuật toán Scatter Search . 133
A.3Thuật toán Particle Swarm Optimization 134
B CÁC BÀI TOÁN THỰC NGHIỆM MẪU 135
B.1Các bài toán tối ưu cơ bản . 135
B.2Các bài toán tối ưu đa cực trị . 139
5Danh sách ký hiệu, chữ viết tắt
Ký hiệu Diễn giải
ACO Thuật toán tối ưu hóa đàn kiến
AIS Hệ miễn nhiễm nhân tạo
CC Kỹ thuật đồng tiến hóa hợp tác (Cooperative Coevolution)
CF Tham số Crowding Factor của phương pháp Crowding
CrowdingDEAL Thuật toán DEAL với phương pháp Crowding
D Số chiều của hàm mục tiêu (hàm đánh giá)
DE Thuật toán tiến hóa vi phân
DEAL Thuật toán tiến hóa dựa trên thông tin định hướng
EA Thuật toán tiến hóa (Evolutionary Algorithm)
EDA Thuật toán ước lượng các thuật toán phân phối
EP Quy hoạch tiến hóa (Evolutionary Programming)
ES Chiến lược tiến hóa (Evolution Strategies)
ETS Tập các cá thể ưu tú (Elite Set)
GA Giải thuật di truyền (Genetic Algorithm)
GP Lập trình di truyền (Genetic Programming)
MaxGens Số thế hệ tối đa
MaxFEs Số lần tính giá trị hàm đánh giá tối đa
(Maximum Fitness Evaluations)
MDEAL Thuật toán DEAL theo chiến lược lai ghép cải tiến
N, PopSize Kích thước quần thể
NBC Kỹ thuật phân cụm Nearest-better Clustering
NBCDEAL Thuật toán DEAL với phương pháp Clustering-based
PCCDEAL Thuật toán song song hóa DEAL theo kỹ thuật CC
PSO Thuật toán tối ưu bầy đàn
SharingDEAL Thuật toán DEAL với phương pháp Fitness Sharing
SpeciesDEAL Thuật toán DEAL với phương pháp Species-based
SSS Tập các cá thể hạt giống (Species Seed Set)
6Danh sách bảng
3.1 Danh sách các bài toán thực nghiệm cho DEAL 70
3.2 Thời gian thực thi thuật toán DEAL (Đơn vị tính: giây) . 70
3.3 So sánh giá trị tối ưu trung bình theo các tùy chọn bước nhảy
định hướng 74
3.4 So sánh hai chiến lược lai ghép . 74
3.5 So sánh DEAL với các thuật toán khác . 76
3.6 Danh sách các bài toán thực nghiệm cho DEAL song song 77
3.7 Thời gian thực thi với Evolution_Cycle = 1 (ĐVT: giây) 78
3.8 Thời gian thực thi với Evolution_Cycle = 5 (ĐVT: giây) 79
3.9 Thời gian thực thi với Evolution_Cycle = 10 (ĐVT: giây) 79
3.10 Giá trị tối ưu trung bình của PCCDEAL 81
4.1 Danh sách các bài toán thực nghiệm 92
4.2 Kết quả thực nghiệm của SharingDEAL 94
4.3 So sánh SharingDEAL với các thuật toán khác 95
4.4 Kết quả thực nghiệm của CrowdingDE . 98
4.5 Kết quả thực nghiệm của CDE . 98
4.6 Kết quả thực nghiệm của CrowdingDEAL . 99
4.7 Thống kê số trường hợp xếp hạng nhất theo các độ đo PR và SR 99
4.8 Kết quả thực nghiệm của SpeciesDEAL_Op1 . 102
4.9 Kết quả thực nghiệm của SpeciesDEAL_Op2 . 102
4.10 Kết quả thực nghiệm của SpeciesDEAL_Op3 . 103
4.11 Kết quả thực nghiệm của SpeciesDEAL_Op4 . 103
4.12 So sánh độ đo PR của SpeciesDEAL và các thuật toán khác . 105
4.13 Kết quả thực nghiệm của NBCDEAL_Op1 106
4.14 Kết quả thực nghiệm của NBCDEAL_Op2 107
4.15 Kết quả thực nghiệm của NBCDEAL_Op3 107
4.16 Kết quả thực nghiệm của NBCDEAL_Op4 108
74.17 Tổng hợp xếp hạng theo các tùy chọn của NBCDEAL 108
4.18 So sánh độ đo PR của NBCDEAL khi điều chỉnh φ 110
4.19 So sánh độ đo PR của NBCDEAL và các thuật toán khác 111
4.20 Giá trị độ đo PR ở độ chính xác  = 1.0E ư 01 của các thuật toán112
4.21 Giá trị độ đo PR ở độ chính xác  = 1.0E ư 02 của các thuật toán113
4.22 Giá trị độ đo PR ở độ chính xác  = 1.0E ư 03 của các thuật toán113
4.23 Giá trị độ đo PR ở độ chính xác  = 1.0E ư 04 của các thuật toán114
4.24 Giá trị độ đo PR ở độ chính xác  = 1.0E ư 05 của các thuật toán114
4.25 Kiểm định Friedman của các thuật toán 115
4.26 Thứ hạng của các thuật toán theo kiểm định Friedman 115
4.27 Kiểm định Wilcoxon của các thuật toán 116
8Danh sách hình vẽ
1.1 Phương án tối ưu địa phương và phương án tối ưu toàn cục . 17
1.2 Bài toán tối ưu đơn cực trị Sphere . 17
1.3 Bài toán tối ưu đa cực trị (Ackley và Shubert) . 18
2.1 Biễu diễn cộng trừ hai véc tơ 29
2.2 Thuật toán Simplex Search . 30
2.3 Các thủ tục của Scatter Search . 32
2.4 Cập nhật vị trí tìm kiếm trong PSO 32
2.5 Thông tin định hướng trong DE 34
2.6 Xác định tập hạt giống . 43
2.7 Kỹ thuật NBC 46
2.8 Mô hình Master/Slave 47
2.9 Mô hình Island 48
2.10 Mô hình Cellular . 50
3.1 Hai dạng thông tin định hướng của DEAL . 59
3.2 Các chiến lược lai ghép của DEAL . 60
3.3 Mô hình song song PCCDEAL . 62
3.4 Mô hình cập nhật cá thể tối ưu toàn cục 62
3.5 Mô hình thời gian thực thi PCCDEAL . 66
3.6 Đồ thị biểu diễn hệ số tăng tốc theo mô hình song song 3.3 69
3.7 Giá trị đánh giá tốt nhất của Sphere’ problem trong 100 lần chạy 71
3.8 Giá trị đánh giá tốt nhất của Ackley’ problem trong 100 lần chạy 72
3.9 Độ đa dạng quần thể của bài toán đơn cực trị Sphere’s Problem . 73
3.10 Độ đa dạng quần thể của các bài toán đa cực trị . 73
3.11 Giá trị tối ưu trung bình đạt được khi D = 30 của các bài toán . 77
4.1 Thuật toán SpeciesDEAL với bài toán Himmelblau 89
4.2 Thuật toán NBCDEAL với bài toán Himmelblau . 90
94.3 Thuật toán NBCDEAL với bài toán Shubert 91
4.4 Ảnh hưởng của thủ tục loại bỏ một nửa số cá thể . 96
4.5 Ảnh hưởng của kích thước quần thể 97
4.6 Giá trị tối ưu trung bình của hàm F 6 (2D) . 100
4.7 Giá trị tối ưu trung bình của hàm F 7 (3D) . 101
4.8 Giá trị tối ưu trung bình của SpeciesDEAL khi điều chỉnh r s . 104
4.9 Giá trị tối ưu trung bình của NBCDEAL khi điều chỉnh φ 110
10Lời mở đầu
1. Giới thiệu chung
Thuật toán phỏng tiến hóa sinh học hay gọi ngắn gọi là thuật toán tiến
hóa (Evolutionary Algorithms - EAs) là một lớp các thuật toán heuristic
trong tối ưu hóa và học máy. EAs đã được áp dụng rộng rãi và thu được
nhiều thành công trong việc giải quyết các bài toán tối ưu số và tối ưu
tổ hợp. Về nguyên tắc, EA là một thuật toán lấy ý tưởng từ quá trình
chọn lọc tự nhiên trong thuyết tiến hóa của Darwin. EAs hoạt động trên
tập các phương án (còn gọi là quần thể - population) để tìm kiếm phương
án tối ưu. Nguyên tắc tính toán dựa vào quần thể đã được khẳng định là
một mô hình tiềm năng cho việc giải quyết các bài toán tối ưu toàn cục
[4, 31, 32, 63, 65, 85].
Trong quá trình nghiên cứu và phát triển, đã có 4 dạng EAs truyền
thống được đề xuất, bao gồm Quy hoạch tiến hóa (Evolutionary Program-
ming - EP), Chiến lược tiến hóa (Evolutionary Strategies - ES), Giải thuật
di truyền (Genetic Algorithm - GA) và Lập trình di truyền (Genetic Pro-
gramming - GP). Các đặc điểm quan trọng nhất đối với các EAs là:
ã EAs điều khiển quá trình tiến hóa của một quần thể gồm nhiều cá
thể, mỗi cá thể đại diện (hay mã hóa) cho một phương án (hay một
lời giải) chấp nhận được của bài toán tối ưu.
ã Các cá thể con (offsprings) được sinh ra một cách ngẫu nhiên thông
qua các quá trình đột biến và lai ghép. Quá trình đột biến là một sự
thay đổi (rất nhỏ) của một cá thể trong khi đó quá trình lai ghép là
sự hoán đổi thông tin giữa 2 hay nhiều cá thể hiện tại.
ã Một hàm đánh giá được sử dụng để đo chất lượng hay tính toán mức
độ phù hợp của các cá thể. Cá thể có giá trị đánh giá cao hơn được
xem là tốt hơn cá thể khác. Quá trình lựa chọn thực hiện việc lựa chọn
và ưu tiên cho các cá thể tốt hơn với mục đích là tạo ra một thế hệ
mới với các cá thể tốt hơn.
Bên cạnh các lớp EAs, trong khoảng thời gian 15 năm gần đây, đã cómột số mô hình thuật toán phỏng tự nhiên mới được đề xuất, chẳng hạn
như Tối ưu bầy đàn (PSO) [43], Tối ưu đàn kiến (ACO) [19], Ước lượng các
thuật toán phân phối (EDA) [49], Hệ miễn nhiễm nhân tạo (AIS) [12], .
Trong các mô hình này, các thủ tục tính toán được lấy ý tưởng từ những
hiện tượng khác nhau của thế giới tự nhiên như bầy chim, đàn cá hay đàn
kiến, .
Trong thiết kế các thuật toán heuristic, cả truyền thống cũng như hiện
đại, vấn đề sử dụng thông tin định hướng luôn nhận được sự quan tâm
của các nhà nghiên cứu. Nếu có thông tin định hướng tốt thì quá trình
tìm kiếm phương án tối ưu sẽ diễn ra nhanh chóng và đạt kết quả tốt.
Phương pháp tụt Gradient (Gradient Descent), thuật toán tìm kiếm đơn
hình (Simplex Search) [66], thuật toán tìm kiếm phân tán (Scatter Search)
[30, 47] là những ví dụ điển hình trong việc sử dụng thông tin định hướng
để giải quyết các bài toán tối ưu. Trong các mô hình thuật toán tiến hóa
mới, lớp các thuật toán tiến hóa vi phân (Differential Evolution) [75] là
một ví dụ khác về những lợi ích đạt được khi sử dụng thông tin định
hướng để chỉ dẫn quá trình tìm kiếm lời giải. Tuy nhiên, trong các thuật
toán này, thông tin định hướng chỉ được xác định một cách cục bộ trong
từng thế hệ của quá trình tiến hóa mà chưa có tính toàn cục, cách tổ chức
quản lý thông tin hướng còn thiếu tính hệ thống. Bởi thế sẽ tồn tại những
trường hợp mà thông tin định hướng có thể làm suy giảm chất lượng (giá
trị đánh giá) của các phương án đã tìm được. Vấn đề xác định các thông
tin định hướng tốt và cách thức quản lý, sử dụng thông tin đó một cách
có hệ thống để hỗ trợ quá trình tiến hóa sẽ là chủ đề nghiên cứu chính của
luận án.
Ngoài ra, trong cách thức tổ chức quản lý các cá thể, có thể thấy rằng
một quần thể các cá thể có thể bao hàm các thông tin định hướng, các
thông tin định hướng này hoàn toàn có thể được xác định một cách có hệ
thống và hỗ trợ quá trình tìm kiếm tiến hóa.
2. Đóng góp của luận án
Đóng góp của luận án là phương pháp xác định và sử dụng thông tin
định hướng hỗ trợ các thuật toán tiến hóa. Chi tiết các đóng góp cụ thể
bao gồm:
1. Đề xuất thuật toán tiến hóa dựa trên thông tin định hướng
DEAL (Direction-guided Evolutionary ALgorithm) với một số
đặc trưng:
ã Sử dụng cân đối 2 dạng thông tin định hướng: (1) hướng hội tụ
(Convergence Direction) là hướng từ một cá thể kém hơn (hạng 2)
12đến một cá thể ưu tú và (2) hướng tản mát (Spread Direction) là
hướng giữa 2 cá thể ưu tú.
ã Các thông tin định hướng được quản lý một cách toàn cục. Các
cá thể ưu tú được lưu trữ trong tập ETS (Elite Set), liên tục được
cập nhật trong suốt quá trình tiến hóa. Tập ETS chứa đựng thông
tin định hướng.
ã Có 4 tùy chọn khác nhau về bước nhảy định hướng và 2 chiến lược
lai ghép.
ã Có thể mở rộng, nâng cao hiệu năng tính toán thông qua kỹ thuật
song song hóa. Thuật toán song song PCCDEAL được đề xuất sử
dụng mô hình song song kết hợp giữa mô hình master/slave truyền
thống với kỹ thuật đồng tiến hóa hợp tác. Các kết quả thực nghiệm
cho thấy tính hiệu quả của thuật toán và mô hình.
2. Đề xuất thuật toán tiến hóa dựa trên thông tin định hướng
nhằm giải quyết các bài toán đa cực trị: Gồm 4 thuật toán
SharingDEAL, CrowdingDEAL, SpeciedDEAL và NBCDEAL là giải
pháp kết hợp giữa DEAL và các phương pháp niching phổ biến. Kết
quả thực nghiệm của các thuật toán này đều cho thấy sự khả quan
của hướng nghiên cứu khi so sánh được với các thuật toán nổi tiếng
được xếp hạng trong thời gian gần đây.
3. Bố cục của luận án
Các nội dung nghiên cứu của luận án được bố trí trong 4 chương và 2
phụ lục, bao gồm:
Chương 1: Cơ sở lý thuyết. Chương này trình bày những khái niệm
lý thuyết cơ bản của tối ưu hóa, làm quen với các dạng bài toán tối ưu
đơn cực trị (uni-modal optimization problems) và đa cực trị (multi-modal
optimization problems). Phần lý thuyết về thuật toán tiến hóa, các thành
phần của một thuật toán cũng được trình bày một cách chi tiết.
Chương 2: Những nội dung nghiên cứu liên quan. Chương này
tập trung khảo sát những nội dung nghiên cứu liên quan đến luận án.
Trong phần đầu, luận án mô tả một cách chi tiết nội dung các thuật toán
tìm kiếm tiêu biểu dựa trên thông tin định hướng. Các thuật toán được
trình bày theo trình tự từ cổ điển đến hiện đại để thấy được sự quan tâm
của các nhà nghiên cứu đối với nội dung này. Trong các phần tiếp theo,
luận án lần lượt trình bày các phương pháp nhằm nâng cao hiệu năng của
các EAs đối với các lớp bài toán khác nhau như các phương pháp niching,
song song hóa, đồng tiến hóa hợp tác. Đối với mỗi phương pháp, luận án
13trình bày rõ ý tưởng, các bước thực hiện của phiên bản đề xuất, sau đó
khảo sát một số các nghiên cứu gần đây có liên quan.
Chương 3: Thuật toán tiến hóa dựa trên thông tin định hướng.
Chương này tập trung trình bày một cách chi tiết nội dung thuật toán tiến
hóa dựa trên thông tin định hướng (gọi tắt là DEAL) do tác giả đề xuất.
Bao gồm ý tưởng, bố cục thuật toán, các tùy chọn và chiến lược tiến hóa,
độ phức tạp tính toán. Các thực nghiệm được tổ chức cho thấy thuật toán
DEAL làm việc hiệu quả đối với lớp các bài toán tối ưu đơn cực trị và lớp
bài toán tối ưu đa cực trị nhưng chỉ có một phương án tối ưu toàn cục.
Trong phần thứ hai của chương, tác giả đã trình bày phương án mở rộng
nhằm nâng cao hiệu năng tính toán của thuật toán DEAL bằng phương
pháp song song hóa. Mô hình song song được sử dụng là một mô hình mới,
không hoàn toàn giống với mô hình master/slave truyền thống. Mô hình
và thuật toán song song được phân tích lý thuyết về thời gian thực thi, hệ
số tăng tốc và tổ chức kiểm chứng thông qua các thực nghiệm ở phần cuối
của chương.
Chương 4: Thuật toán tiến hóa dựa trên thông tin định hướng
với bài toán đa cực trị. Chương này trình bày các mở rộng của thuật
toán DEAL nhằm giải quyết các bài toán tối ưu đa cực trị (multi-modal
optimization problems). Đây là lớp bài toán thường gặp trong thực tế và
để giải quyết nó, thuật toán DEAL cần có những biến đổi phù hợp về mặt
hành vi bằng các phương pháp niching. Trong nội dung của chương, tác
giả lần lượt trình bày 4 thuật toán mới SharingDEAL, CrowdingDEAL,
SpeciesDEAL và NBCDEAL là sự kết hợp giữa các phương pháp niching
tương ứng với thuật toán DEAL. Các thực nghiệm với 20 bài toán tối ưu
đa cực trị phổ biến để kiểm tra, đánh giá và so sánh các thuật toán thuộc
luận án với các thuật toán nổi tiếng khác, đặc biệt có những thuật toán
được đánh giá cao trong các cuộc thi thiết kế thuật toán gần đây.
Phần cuối của luận án là kết luận với các đánh giá về những đóng góp
chính của luận án và một số ý tưởng về hướng nghiên cứu trong tương lai
của tác giả.