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ị

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG

HỌC VIỆN KỸ THUẬT QUÂN SỰ

Vũ Chí Cường

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Ị

LUẬN ÁN TIẾN SỸ TOÁN HỌC

Chuyên ngành: Cơ sở toán học trong tin học

Mã số: 62.46.01.10

Hà Nội - Năm 2016

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG

HỌC VIỆN KỸ THUẬT QUÂN SỰ

Vũ Chí Cường

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Ị

Chuyên ngành: Cơ sở toán học trong tin học

Mã số: 62.46.01.10

LUẬN ÁN TIẾN SỸ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. BÙI THU LÂM

Hà Nội - Năm 2016

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tác giả dưới

sự hướng dẫn khoa học của PGS.TS. Bùi Thu Lâm. Các kết quả được công

bố với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa

vào luận án. Các kết quả nêu trong luận án là trung thực và chưa từng

được công bố trong bất cứ công trình nào khác.

Hà Nội, tháng 7 năm 2016

Nghiên cứu sinh

Vũ Chí Cường

1

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

2

Mụ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

3

2.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

4

4.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

5

Danh 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)

M axGens Số thế hệ tối đa

M axF Es 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, P opSize 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)

6

Danh 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

7

4.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

8

Danh 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

9

4.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 F6(2D) . . . . . . . . . . . . . 100

4.7 Giá trị tối ưu trung bình của hàm F7(3D) . . . . . . . . . . . . . 101

4.8 Giá trị tối ưu trung bình của SpeciesDEAL khi điều chỉnh rs . . . 104

4.9 Giá trị tối ưu trung bình của NBCDEAL khi điều chỉnh φ . . . . 110

10

Lờ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