Tóm tắt Luận án Tiến sỹ Toán học: Một lớp thuật toán phỏng tiến hoá sinh học dựa trên thông tin định hướng giải bài toán đa cực trị

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Ị

TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC Chuyên ngành: Cơ sở toán học trong tin học

Hà Nội - Năm 2016

CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI HỌC VIỆN KỸ THUÂT QUÂN SỰ - BỘ QUỐC PHÒNG ——————————————————–

Người hướng dẫn khoa học: PGS. TS. Bùi Thu Lâm

Phản biện 1: PGS.TS Hoàng Xuân Huấn - ĐH Quốc gia Hà Nội

Phản biện 2: PGS.TS. Huỳnh Thị Thanh Bình - ĐH Bách khoa Hà Nội

Phản biện 3: TS. Nguyễn Đức Dũng - Viện Hàn lâm KH&CN Việt Nam

Luận án được bảo vệ tại Hội đồng đánh giá luận án cấp Học viện theo quyết định số 2506/QĐ-HV, ngày 08 tháng 7 năm 2016 của Giám đốc Học viện Kỹ thuật Quân sự, họp tại Học viện Kỹ thuật Quân sự vào hồi .... giờ ...., ngày .... tháng .... năm ......

Có thể tìm hiểu luận án tại:

- Thư viện Học viện Kỹ thuật Quân sự

- Thư viện Quốc gia

Lời mở đầu

Thuật toán phỏng tiến hóa sinh học hay gọi ngắn gọn 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 cảm hứ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 Pro- gramming - 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 Programming - 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 hóa bầy đàn (PSO) [43], Tối ưu hóa đà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

3

nhân tạo (AIS) [12],... Trong các mô hình này, các toán tử tính toán được lấy cảm hứ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.

Luận án được tổ chức thành 4 chương nội dung chính, bao gồm:

Chương 1: Cơ sở lý thuyết,

Chương 2: Những nội dung nghiên cứu 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 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ị.

4

Chương 1

CƠ SỞ LÝ THUYẾT

Mục đích của chương này là cung cấp các kiến thức cơ sở lý thuyết liên quan đến nội dung nghiên cứu của luận án. Cấu trúc của chương gồm 2 phần chính. Phần đầu trình bày những khái niệm lý thuyết tổng quan về tối ưu hóa, liên quan nhiều nhất đến thuật toán tiến hóa. Phần thứ hai mô tả các nội dung cơ bản của thuật toán tiến hóa như khái niệm, bản chất, các dạng phân loại truyền thống. Trong phần này, tác giả cũng dành thời gian để mô tả một cách cụ thể các thành phần chính của một thuật toán tiến hóa và cuối cùng là sơ đồ tổng quát của thuật toán.

Sơ đồ tổng quát của một EA có thể được mô tả như Algorithm 1.1.

Algorithm 1.1 Sơ đồ tổng quát của Thuật toán tiến hóa Input: µ, λ, κ, θι, θc, θm, θs Output: a∗ là cá thể tốt nhất hoặc P ∗ là quần thể tốt nhất tìm được.

(cid:48)

(cid:46) Khởi tạo quần thể ban đầu (cid:46) Đánh giá các cá thể của quần thể

(cid:48)

(t) ←− recombine(P (t), θc); (cid:46) Phép lai ghép (cid:46) Phép đột biến

1: t ←− 0; 2: P (t) ←− initialize(µ); 3: f (t) ←− evaluate(P (t), µ); 4: while (ι(P (t), θι) (cid:54)= true) do 5: 6: 7: 8: 9: 10: end while 11: return P ∗ = P (t); 12:

(cid:46) Phép lựa chọn P P ”(t) ←− mutate(P (t), θm); f (t) ←− evaluate(P ”(t), λ); P (t + 1) ←− select(P ”(t), f (t), µ, θs); t ←− t + 1;

a∗ = best(P (t));

5

Chương 2

NHỮNG NỘI DUNG NGHIÊN CỨU

LIÊN QUAN

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 trong việc thiết kế các thuật toán tính toán số, truyền thống cũng như hiện đại. Khảo sát, tìm hiểu các thuật toán này sẽ giúp làm rõ vấn đề sử dụng thông tin định hướng như thế nào trong tìm kiếm lời giải hay điều khiển quá trình tiến hóa. Hơn nữa, việc khảo sát còn giúp chỉ ra được những thiếu sót, những hạn chế của các thuật toán để từ đó tìm cách đề xuất thuật toán mới. Trong chương này, tác giả tiến hành khảo sát 4 thuật toán tìm kiếm nổi tiếng, bao gồm Thuật toán tìm kiếm đơn hình (Simplex Search) của J.A. Nelder và R. Mead [66], Thuật toán tìm kiếm phân tán (Scatter Search) của F. Glover, M. Laguna và R. Martin [30, 47], Thuật toán tối ưu hóa bầy đàn (Particle Swarm Optimization - PSO) của R.C. Eberhard và J. Kennedy [43], cuối cùng là Thuật toán tiến hóa vi phân (Differential Evolution - DE) của R. Storn và K. Price [75].

Phần thứ hai của chương, tác giả tiến hành khảo sát 4 kỹ thuật niching thường dùng là Fitness Sharing của D. E. Goldberg và J. J. Richardson [33], Crowding của K. A. De Jong [13], Species-based của Jian-Ping Li [50], Clustering-based của X. Yin và N. Germay [108]. Đây là các kỹ thuật đặc biệt được tích hợp trong các thuật toán tiến hóa nhằm giải quyết các bài toán tối ưu đa cực trị.

Phần cuối của chương là các khảo sát về các mô hình, các kỹ thuật song song hóa thuật toán tiến hóa. Trong phần này, ngoài 4 dạng mô hình song song truyền thống là master/slave, island, cellular và hybrid [8, 9, 42], tác giả còn trình bày kỹ thuật đồng tiến hóa hợp tác (Co- operative Co-evolution - CC) do M. A. Potter đề xuất năm 1994 [70, 71].

6

Chương 3

THUẬT TOÁN TIẾN HÓA DỰA TRÊN

THÔNG TIN ĐỊNH HƯỚNG

3.1 Thuật toán DEAL

Một trong những chìa khóa dẫn đến thành công trong thiết kế thuật toán tiến hóa là có được các thông tin định hướng tốt để chỉ dẫn quá trình tìm kiếm. Trong luận án này, thông tin định hướng được xây dựng từ tập các cá thể ưu tú mà tác giả gọi là tập ETS (Elite Set). Đó là tập các cá thể có giá trị đánh giá tốt hơn các cá thể khác còn lại (cá thể xếp hạng hai) và được quản lý, duy trì trong suốt quá trình tiến hóa.

Có hai dạng thông tin định hướng được luận án quan tâm:

• Hướng hội tụ (CD - Convergence Direction) là hướng giữa một cá thể xếp hạng hai trong quần thể hiện tại với một cá thể ưu tú trong tập ETS.

• Hướng tản mát (SD - Spread Direction) là hướng giữa hai cá thể ưu tú trong tập ETS hiện tại.

Thuật toán tiến hóa mới dựa trên hai dạng thông tin định hướng trên được tác giả đặt tên là Direction-guided Evolutionary ALgorithm hay DEAL. Sơ đồ của thuật toán DEAL được mô tả trong Algo- rithm 3.2.

Trong thuật toán DEAL, thủ tục generation() là thủ tục quan trọng nhất, gồm 10 bước và được mô tả cụ thể ở trang sau.

7

1: t ←− 0; 2: P (t) ←− initialize(N ); 3: f (t) ←− evaluate(P (t)); 4: ET S(t) ←− selectElite(P (t)); 5: while (termination() (cid:54)= true) do 6: 7: 8:

Algorithm 3.2 Sơ đồ của Thuật toán DEAL Input: N là kích thước quần thể; θc, θm, σ1, σ2 là các tham số điều khiển. Output: a∗ là cá thể tốt nhất tìm được.

9: 10: 11: 12: end while 13: return a∗ = best(P (t));

M (t) ←− P (t); M (t) ←− generation(M (t), θc, θm, σ1, σ2); C(t) ←− M (t) ∪ ET S(t); ET S(t) ←− selectElite(C(t)); P (t + 1) ←− M (t); t ←− t + 1;

Bước 1: index = 0. Bước 2: Lựa chọn ngẫu nhiên một cá thể cha pr. Bước 3: Lựa chọn hướng hội tụ d1. Bước 4: Xác định cá thể thử nghiệm s1 bằng cách lai ghép pr với cá thể sinh ra khi dịch chuyển pr theo hướng hội tụ d1 với bước nhảy định hướng σ1 và xác suất lai ghép θc. Bước 5: Đánh giá s1, Nếu s1 tốt hơn pindex thì thay thế mindex = s1. Bước 6: Lựa chọn hướng tản mát d2. Bước 7: Xác định cá thể thử nghiệm s2 bằng cách lai ghép pr với cá thể sinh ra dịch chuyển pr theo hướng tản mát d2 với bước nhảy định hướng σ2 và xác suất lai ghép là θc. Bước 8: Đột biến s2 theo xác suất đột biến θm. Bước 9: Đánh giá s2, Nếu s2 tốt hơn pindex+1 thì mindex+1 = s2. Bước 10: index = index + 2, Lặp lại Bước 1 cho đến khi duyệt hết các cá thể của M.

8

3.1.1 Độ phức tạp tính toán

3.1.2 Các tùy chọn về bước nhảy định hướng

Độ phức tạp của thuật toán DEAL sẽ là O(mN logN ), trong đó N là kích thước quần thể, m là số thế hệ tiến hóa.

3.1.3 Các chiến lược lai ghép

DEAL sử dụng 2 tham số σ1 và σ2 để điều chỉnh độ lớn của véc tơ định hướng d1 và d2. Các tham số này được gọi là bước nhảy định hướng và các giá trị khác nhau của chúng có ảnh hưởng đến chất lượng của thuật toán.

Trong DEAL tác giả sử dụng một cá thể cha pr vừa làm cá thể đột biến vừa làm cá thể lai ghép để sinh ra các cá thể thử nghiệm s1 và s2. Đây là chiến lược lai ghép thứ nhất.

Chiến lược lai ghép thứ hai sử dụng các cá thể theo thứ tự pindex và pindex+1 làm cá thể lai ghép. Thuật toán mới gọi là MDEAL (Modified Strategy for DEAL).

3.2 Song song DEAL với kỹ thuật đồng

tiến hóa hợp tác

3.2.1 Mô hình song song

Mô hình song song DEAL với kỹ thuật đồng tiến hóa hợp tác được biểu diễn trong Hình 3.1.

Tại master node, một quần thể (Population) gồm các cá thể được khởi tạo ngẫu nhiên trong không gian tìm kiếm. Quần thể được phân chia (Decomposition) thành các quần thể con (subPopulation) tương ứng với một phần của bài toán. Một cá thể toàn cục tốt nhất được xác định và quản lý trong suốt quá trình tiến hóa (Current best). Các quần thể con (SubPop) và cá thể tốt nhất toàn cục hiện thời (Current best) sẽ được phân phát tới các slave node để được tiến hóa một cách độc lập và đồng thời.

9

Hình 3.1: Mô hình song song PCCDEAL

Tại mỗi slave node, quần thể con được tiến hóa bằng DEAL trong một số vòng lặp xác định trước (ký hiệu là Evolution_Cycle). Sau một Evolution_Cycle, mỗi slave lựa chọn một cá thể con tốt nhất làm đại diện cho nó (Representative) và gửi về cho master node nhằm tham gia quá trình cập nhật cá thể toàn cục tốt nhất.

Quá trình cập nhật được diễn ra như trong Hình 3.2.

Hình 3.2: Mô hình cập nhật cá thể tối ưu toàn cục

10

3.2.2 Thời gian thực thi và hệ số tăng tốc

Thời gian thực thi thuật toán

Sơ đồ bố trí thời gian thực thi của hệ thống với m slave được mô tả trong Hình 3.3.

Hình 3.3: Mô hình thời gian thực thi PCCDEAL

Khi đó, tổng thời gian thực thi của thuật toán song song được tính:

Tp = Tf + Tc

= + (8N D(N + 1)tc + 8F Dtc) m + 8N Dtc + 8F Dtc (N + 1)m + 1

= mF + F (N + 1) (N + 1)m + 1 (F tf + 8N D(N + 1)tc + 8F Dtc) m + F (N + 1)tf + 8N Dtc + 8F Dtc (N + 1)m + 1 (3.1)

Trong đó:

• m là số lượng Slave, N là kích thước quần thể, D là số chiều;

• F là tổng số lần tính giá trị đánh giá tối đa, G là số thế hệ tiến hóa.

Hệ số tăng tốc thuật toán

Hệ số tăng tốc của thuật toán song song theo mô hình 3.1 được tính: S = . (3.2) a1m + b1 a2m + b2

trong đó a1 = F (N + 1)α; a2 = F α + 8N D(N + 1) + 8F D; b1 = F α; b2 = F (N + 1)α + 8N D + 8F D.

11

3.2.3 Thuật toán song song

PCCDEAL tại master

Bước 1: Khởi tạo quần thể chính mainP OP . Bước 2: Đánh giá quần thể chính và xác định cá thể toàn cục tốt nhất globalBEST . Bước 3: Phân chia quần thể chính thành m quần thể con subP OP có số chiều bằng nhau. Bước 4: Phân phối các quần thể con subP OP cho các slaves. for i:=1 to m do sendToSlave(subP OP )

end for Bước 5: Vòng lặp chính while (termination criteria = false) do for i:=1 to m do

sendToSlaves(globalBEST ) (waiting for slaves) receiveFromSlaves(bestCOM P ON EN T )

end for Update(globalBEST ) end while

PCCDEAL tại các slave

Bước 1: Khởi tạo quần thể bằng cách nhận quần thể con subP OP từ master receiverFromMaster(subP OP ) Bước 2: Vòng lặp chính

while (termination criteria = false) do receiverFromMaster(globalBEST ) runDEAL(Evolution_Cycle) sendToMaster(bestCOM P ON EN T ) (waiting for master) end while

12

3.3 Đánh giá thực nghiệm

3.3.1 Thực nghiệm cho DEAL và MDEAL

Sphere’s Problem Schwefel’s Problem Rastrigin’s Problem Ackley’s Problem Griewank’s Problem Penalized Problem 1 Penalized Problem 2

30 30 30 30 30 30 30

Ranges [-100, 100] [−500, 500] [−5.12, 5.12] [−32, 32] [−600, 600] [−50, 50] [−50, 50]

fmin 0 -12569.5 0 0 0 0 0

ID Name of Problems Dim. (D) F0 F1 F2 F3 F4 F5 F6

Bảng 3.1: Danh sách các bài toán thực nghiệm cho DEAL

Các tham số thực nghiệm:

• Kích thước quần thể: N = 100,chiều của các bài toán: D = 30,

• Tổng số lần tính giá trị đánh giá lớn nhất cho phép: M axF Es = 5000×D = 150.000. Riêng bài toán F2, để đảm bảo cùng điều kiện so sánh với các thuật toán khác nên tác giả sử dụng M axF Es = 250.000,

• Xác suất lai ghép: θc = 0.90, xác suất đột biến: θm = 0.01

• Số lần chạy độc lập: N R = 100.

Phân tích thời gian thực thi

Phân tích về hành vi

Phân tích độ đa dạng của quần thể

So sánh hiệu quả với các tùy chọn về bước nhảy định hướng

So sánh hiệu quả với các tùy chọn về chiến lược lai ghép

So sánh hiệu quả với các thuật toán khác

Tác giả sử dụng kết quả của MDEAL thay cho DEAL khi so sánh với các thuật toán khác. Bên cạnh việc thực thi thuật toán MDEAL,

13

tác giả còn tiến hành thực nghiệm thuật toán DE với mã nguồn được cung cấp tại [75]. Kết quả thực nghiệm của MDEAL và DE được so sánh với kết quả thực nghiệm của các thuật toán phổ biến khác đã được công bố trong [48], bao gồm các thuật toán RCCRO (Real-coded ver- sion of Chemical Reaction Optimization) [48], GA (Genetic Algorithm), FEP (Fast Evolutionary Programming), CEP (Classical Evolutionary Programming), FES (Fast Evolutionary Strategy), CES (Conventional Evolutionary Strategy), RCBBO (Real-coded Biogeography-based op- timization) [35], CMAES (Covariance Matrix Adaptation Evolution Strategy) [37] và G3PCX (Generalized Generation Gap model with PCX) [16]. Đây là các thuật toán tiến hóa nối tiếng đã có những thành công được ghi nhận trong lịch sử phát triển của thuật toán tiến hóa.

Kết quả thực nghiệm cho thấy: Trong khi MDEAL xếp hạng nhất với 4 bài toán (F2, F3, F5, F6) thì DE xếp hạng nhất với 1 bài toán (F4). Tuy nhiên, DE xếp hạng hai ở 5 bài toán còn lại. Một điều thú vị ở đây là cả MDEAL và DE đều là các thuật toán tiến hóa sử dụng thông tin định hướng để điều khiển quá trình tiến hóa. Điều này một lần nữa cho thấy tính hiệu quả của các thuật toán tiến hóa sử dụng thông tin định hướng.

3.3.2 Thực nghiệm cho DEAL song song

Phân tích hành vi của 2 thuật toán MDEAL và DE đối với cả 6 bài toán (xem Hình 3.4) ta dễ dàng nhận thấy MDEAL hội tụ nhanh hơn DE (đường màu đỏ nằm dưới đường màu xanh).

Properties Unimodal, Separable Unimodal, Non-separable Multimodal, Separable Multimodal, Non-separable Multimodal, Non-separable

Ranges [-100, 100] [-100, 100] [-5, 5] [-32, 32] [-600, 600]

ID Name of Problems Sphere’s Problem F0 Schwefel’s Problem 2.21 F1 F2 Rastrigin’s Problem F3 Ackley’s Problem F4 Griewank’s Problem

Bảng 3.2: Danh sách các bài toán thực nghiệm cho DEAL song song

Tác giả phức tạp hóa các bài toán thực nghiệm bằng cách tăng số chiều của bài toán D = 500. Khi đó: M axF Es = 5.000×D = 2.500.000. Các tham số thực nghiệm khác bao gồm như sau: Kích thước quần thể N = 100, θc = 0.90, θm = 0.01, số thế hệ tiến hóa trong mỗi slave Evolution_Cycle = 1, 5 và 10.

14

Hình 3.4: Giá trị tối ưu trung bình đạt được khi D = 30 của các bài toán

(a) Schwefed’s problem; (b) Rastrigin’s problem; (c) Ackley’s problem; (d) Griewank’s problem; (e) Pernalized problem 1; and (f) Pernalized problem 2

Phân tích thời gian thực thi và tính toán hệ số tăng tốc

Phân tích hiệu quả của thuật toán PCCDEAL

Thông thường các kỹ thuật song song hóa chỉ làm tăng hiệu suất về mặt thời gian thực thi của thuật toán. Tuy nhiên, trong trường hợp này, luận án đã sử dụng kết hợp song song với kỹ thuật đồng tiến hóa hợp tác. Do đó thuật toán PCCDEAL có thể làm tăng chất lượng của lời giải, nghĩa là giá trị của phương án tốt nhất tìm được cuối cùng của thuật toán có thể được cải thiện.

3.4 Kết luận

Thuật toán DEAL có một số đặc trưng như:

• Tổ chức và sử dụng cân đối 2 dạng thông tin định hướng: (1) hướng hội tụ là hướng từ một cá thể hạng hai đến một cá thể ưu tú và (2) hướng tản mát 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. Tập các cá thể ưu tú được tổ chức ngoài và liên tục được cập nhật

15

Hình 3.5: Hệ số tăng tốc của PCCDEAL

trong suốt quá trình tiến hóa.

• Có 4 tùy chọn về bước nhảy tiến hóa.

• Có 2 chiến lược lai ghép khác nhau tương ứng với 2 phiên bản DEAL và MDEAL.

Các kết quả thực nghiệm cho thấy DEAL và MDEAL làm việc tốt với lớp bài toán tối ưu đơn cực trị và các 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. Hiệu quả của thuật toán MDEAL có thể so sánh được với các thuật toán tiến hóa nổi tiếng khác. Đặc biệt tính hiệu quả của MDEAL và DE một lần nữa khẳng định lợi thế của các thuật toán tiến hóa dựa trên thông tin định hướng.

Cũng trong chương này, tác giả đã tiến hành song song hóa thuật toán DEAL nhằm nâng cao năng lực tính toán khi phải giải quyết các bài toán phức tạp. Mô hình song song mà tác giả sử dụng là mô hình song song được kết hợp giữa mô hình song song master/slave truyền thống và kỹ thuật đồng tiến hóa hợp tác.

16

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Ị

4.1 DEAL với kỹ thuật Fitness Sharing

Thuật toán DEAL kết hợp với kỹ thuật Fitness Sharing được gọi tên là SharingDEAL. Trong SharingDEAL, thủ tục generation() của thuật toán DEAL được viết lại như sau:

Bước 1: Xây dựng quần thể trộn M. Tương tự như 10 bước của thủ tục generation() của thuật toán DEAL. Tuy nhiên các cá thể thử nghiệm S1 và S2 không được đánh giá so sánh nhằm thay thế các cá thể cha mẹ mà tiếp tục được bổ sung vào quần thể M. Bước 2: Tính toán giá tri chia sẻ (fitness sharing) của tất cả các cá thể trong quần thể M. Bước 3: Sắp xếp quần thể M theo thứ tự giảm dần của giá trị chia sẻ. Bước 4: Loại bỏ nửa cá thể xấu của M. Trong bước này, một nửa số cá thể của M có giá trị chia sẻ thấp sẽ bị loại bỏ. Tuy nhiên, cần phải bảo tồn cá thể ưu tú nhất (có giá trị đánh giá cao nhất) của quần thể M. Quần thể M có kích thước bằng kích thước quần thể P tiếp tục được thực hiện các bước tiếp theo của thuật toán DEAL.

Độ phức tạp tính toán của SharingDEAL được tính là O(mN 2), m là số thế hệ tiến hóa, N là kích thước quần thể.

17

4.2 DEAL với kỹ thuật Crowding

CrowdingDEAL có thủ tục generation() được viết lại như sau:

Bước 1: index = 0. Bước 2: Lựa chọn ngẫu nhiên một cá thể cha pr. Bước 3: Lựa chọn hướng hội tụ d1. Bước 4: Xác định cá thể thử nghiệm s1 bằng cách lai ghép pr với cá thể sinh ra khi dịch chuyển pr theo hướng d1 với bước nhảy định hướng σ1 và xác suất lai ghép θc. Bước 4+: Tìm kiếm cá thể cha m1 tương tự nhất với cá thể s1. Bước 5: Đánh giá s1 và so sánh s1 với m1 Nếu s1 tốt hơn m1 thì thay thế m1 = s1. Bước 6: Lựa chọn hướng tản mát d2. Bước 7: Xác định cá thể thử nghiệm s2 bằng cách lai ghép pr với cá thể sinh ra khi dịch chuyển pr theo hướng d2 với bước nhảy định hướng σ2 và xác suất lai ghép là θc. Bước 8: Đột biến s2 theo xác suất đột biến θm. Bước 8+: Tìm kiếm cá thể cha m2 tương tự nhất với cá thể s2. Bước 9: Đánh giá s2 và so sánh s2 với m2 Nếu s2 tốt hơn m2 thì thay thế m2 = s2. Bước 10: index = index + 2 Lặp lại Bước 1 cho đến khi duyệt hết các cá thể của M.

Độ phức tạp tính toán của CrowdingDEAL sẽ là O(mN 2) với m là số thế hệ tiến hóa, N là kích thước quần thể.

4.3 DEAL với kỹ thuật Species-based

Thuật toán tiến hóa mới gọi là SpeciedDEAL. SpeciesDEAL sử dụng các điều kiện khởi động lại như sau:

• TC01 (tình huống hội tụ sớm): Khởi động lại nếu sự chênh lệch các giá trị đánh giá của tất cả các cá thể trong tiểu quần thể là bé hơn T olf un = 10−12.

• TC02 (tình huống hội tụ sớm): Khởi động lại nếu độ lệch chuẩn của các giá trị đánh giá của tất cả các cá thể trong tiểu quần thể

18

là bé hơn T olX = 10−12.

• TC03 (tình huống bị kẹt): Khởi động lại nếu sự chênh lệch các giá trị đánh giá tốt nhất (giá trị tối ưu) đạt được trong glast = 10 thế hệ gần đây là bằng 0.

Bước 1: Khởi tạo quần thể chính P có kích thước N . Bước 2: Xác định tập SSS và phân chia các loài tương ứng. Nếu kích thước của loài nhỏ hơn n0 thì khởi tạo ngẫu nhiên một số cá thể trong miền xác định của loài cho đến khi mọi loài đều có kích thước lớn hơn hoặc bằng n0. Bước 3: Với mỗi loài, thực hiện thuật toán DEAL cho đến khi điều kiện khởi động lại được thỏa mãn. Bước 4: Kết hợp tất cả các loài và chỉ giữ lại N cá thể tốt nhất. Bước 5: Quay lại bước 2 cho đến khi tất cả các loài đều thỏa mãn điều kiện khởi động lại. Bước 6: Quay lại bước 1 cho đến khi điều kiện dừng thuật toán được thỏa mãn.

Thuật toán SpeciesDEAL có độ phức tạp tính toán sẽ là O(mN 2logN ).

4.4 DEAL với kỹ thuật Clustering-based

Thuật toán NBCDEAL bổ sung 01 tiêu chí TC04:

• TC04 (tình huống lãng phí): Khởi động lại nếu miền xác định của cụm chứa một phương án tối ưu đã được tìm thấy.

Cấu trúc dạng bước của thuật toán NBCDEAL được mô tả như sau:

Bước 1: Khởi tạo quần thể chính P một cách ngẫu nhiên. Bước 2: Áp dụng kỹ thuật NBC để phân tách quần thể P thành các cụm cá thể riêng biệt. Bước 3: Với mỗi cụm cá thể Thực hiện thuật toán DEAL cho mỗi cụm cá thể

cho đến khi điều kiện khởi động lại được thỏa mãn Bước 4: Nếu điều kiện dừng chương trình chưa thỏa mãn thì Quay lại bước 1.

19

Độ phức tạp tính toán của NBCDEAL sẽ là O(mN 2logN ).

4.5 Các thực nghiệm

4.5.1 Môi trường thực nghiệm

Các bài toán thực nghiệm

Luận án sử dụng tập các bài toán thực nghiệm được đề xuất gần đây trong IEEE CEC’2013 được liệt kê trong Bảng 4.1.

Dimension No. of optima

Five-Uneven-Peak Trap Equal Maxima Uneven Decreasing Maxima Himmelblau Six-Hump Camel Back Shubert Shubert Vincent Vincent

1 1 1 2 2 2 3 2 3 2 2 2 2 3 5 10 3 5 10 20

2 5 1 4 4 18 81 36 216 12 6 8 6 6 6 6 8 8 6 8

ID Name F1 F2 F3 F4 F5 F6 F6 F7 F7 F8 Modified Rastrigin F9 Composition Function 1 F10 Composition Function 2 F11 Composition Function 3 F11 Composition Function 3 F11 Composition Function 3 F11 Composition Function 3 F12 Composition Function 4 F12 Composition Function 4 F12 Composition Function 4 F12 Composition Function 4

Bảng 4.1: Danh sách các bài toán thực nghiệm

Các tham số thực nghiệm

• N = 40 ∗ D với các bài toán có số chiều D ≤ 3 và N = 120 với các bài toán còn lại.

20

• M axF Es = 5 × 104 với các bài toán từ F1 − F5, M axF Es = 2 × 105 với các bài toán có D = 2 còn lại, M axF Es = 4 × 105 với các bài toán có D ≥ 3.

• Độ chính xác ((cid:15) = 10−i với i = 1, 2, . . . , 5.

• Số lần chạy độc lập: N R = 50

• Tham số điều khiển của DEAL: pc = 0.90, pm = 0.01.

Các độ đo

• Tỷ lệ đạt đỉnh PR

4.5.2 Thực nghiệm 1: Hiệu suất của SharingDEAL

• Tỷ lệ thành công SR

4.5.3 Thực nghiệm 2: Hiệu suất của CrowdingDEAL

Trong phần này, tác giả tiến hành thực nghiệm thuật toán Shar- ingDEAL trong N R = 50 lần chạy độc lập. Để so sánh luận án sử dụng các kết quả thực nghiệm của DE/nrand/1, DEAL và SharingDE. Trong đó DE/nrand/1 là một phiên bản chuẩn của thuật toán tiến hóa vi phân DE, các kết quả thực nghiệm của DE/nrand/1 được lấy từ công bố trong bài báo [54]. DEAL là thuật toán gốc, không sử dụng kỹ thuật niching. SharingDE là thuật toán của R. Thomsen được đề xuất trong [33].

4.5.4 Thực nghiệm 3: Hiệu suất của SpeciesDEAL

Bên cạnh thực nghiệm CrowdingDEAL, tác giả còn tiến hành thực nghiệm và sử dụng kết quả của 2 thuật toán khác là CDE của R. Thomsen [99] và CrowdingDE của M. G. Epitropakis [21]. Kết quả của thuật toán CDE được tác giả lập trình lại với thông tin thuật toán và các điều kiện thực nghiệm được công bố trong [99] còn kết quả của CrowdingDE là kết quả của CrowdingDE/nrand/1 đã nêu trong [54].

Để so sánh, đánh giá SpeciesDEAL, tác giả thực hiện lại thuật toán SpeciesDE của Xiadong Li với các thông tin được công bố trên [51,

21

4.5.5 Thực nghiệm 4: Hiệu suất của NBCDEAL

53]. Các điều kiện thực nghiệm SpeciesDE tuân thủ sự khuyến cáo của Xiaodong Li trong [51, 53] và cũng phù hợp với SpeciesDEAL.

4.5.6 So sánh đồng thời các thuật toán đã đề xuât

Để so sánh, đánh giá NBCDEAL với các thuật toán khác, luận án sử dụng kết quả thực nghiệm thuật toán NEA2 (Niching the CMA-ES via Nearest-Better Clustering) của M. Preuss đã đạt hạng nhất trong cuộc thi thiết kế thuật toán năm 2013 [55] và kết quả thực nghiệm của thuật toán LSEAGP (Localised Search Evolutionary Algorithm using a Gaussian Process) của J.E. Fieldsend đã đạt hạng hai trong cuộc thi năm 2015 [56]. Số liệu của NBCDEAL là kết quả tốt nhất của NBCDEAL_Op1 khi điều chỉnh tham số φ.

Trong phần này, tác giả lựa chọn 04 thuật toán được đánh giá cao trong thời gian gần đây với đầy đủ các đặc trưng của một thuật toán tiến hóa để so sánh với các thuật toán do tác giả đề xuất khi cùng giải quyết một lớp các bài toán tối ưu đa cực trị.

• NEA2 - Niching the CMA-ES via Nearest-Better Clustering

• dADE/nrand/1 - A Dynamic Archive Niching Differential Evolu- tion algorithm for Multimodal Optimization

• LSEAGP - Localised Search Evolutionary Algorithm using a Gaus- sian Process

• LSEAEA - Localised Search Evolutionary Algorithm using an Evolutionary Algorithm

Thực hiện kiểm định Friedman giá trị trung bình độ đo PR trong toàn bộ cả 5 trường hợp mức độ chính xác, tác giả thu được các số liệu ở Bảng 4.2.

Từ Bảng 4.2, giá trị Asymp.Sig = 9.46E − 32 < 0.05 bởi vậy có đủ cơ sở để khẳng định có sự khác biệt về độ đo PR của các thuật toán ở mức ý nghĩa 5%. Tiến hành xếp hạng các thuật toán theo trung bình thứ hạng theo kiểm định Friedman ta có kết quả so sánh ở Bảng 4.3.

Kết quả của Bảng 4.3 cho thấy thuật toán NBCDEAL đạt thứ hạng tốt nhất, thuật toán NEA2 đạt hạng nhì và dADE/nrand/1 đạt hạng

22

N

Mean

Descriptive Statistics Max Min Std.

100 dADE 100 NEA2 LSEAGP 100 LSEAEA 100 100 ShDEAL 100 CrDEAL SpDEAL 100 100 NDEAL

0.7425 0.7939 0.7302 0.7477 0.3698 0.5012 0.6842 0.7549

0.3030 0.2333 0.3268 0.3236 0.3927 0.4178 0.3738 0.3020

0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000

1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000

Percentiles 50th 0.8300 0.8515 0.7900 0.9030 0.1670 0.4595 0.8915 0.9570

75th 1.0000 1.0000 1.0000 1.0000 0.9395 1.0000 1.0000 1.0000

25th 0.6308 0.6670 0.6670 0.6150 0.0990 0.0778 0.3898 0.5378

Test Statistics

N Chi-Square df Asymp. Sig.

100 162.520 7 9.46E-32

Bảng 4.2: Kiểm định Friedman của các thuật toán

Mean Rank Rank

4.84 5.52 4.80 4.83 2.82 3.19 4.33 5.69

3 2 5 4 8 7 6 1

dADE NEA2 LSEAGP LSEAEA ShDEAL CrDEAL SpDEAL NDEAL

Bảng 4.3: Thứ hạng của các thuật toán theo kiểm định Friedman

ba. Các thuật toán SpeciesDEAL, CrowdingDEAL và SharingDEAL đạt thứ hạng kém hơn.

Ngoài kiểm định Friedman Test, tác giả còn thực hiện kiểm định Wilcoxon nhằm xác định sự khác biệt giữa các cặp thuật toán NBCDEAL với dADE/nrand/1, NBCDEAL với NEA2, NBCDEAL với LSEAGP và NBCDEAL với LSEAEA. Kết quả của kiểm định Wilcoxon được biểu diễn trong Bảng 4.4.

Kết quả từ Bảng 4.4 cho thấy có thể khẳng định sự khác nhau giữa các cặp thuật toán dADE/nrand/1 và NBCDEAL, LSEAGP và NBCDEAL do các giá trị Asymp.Sig tương ứng là 0.031 < 0.05 và 0.036 < 0.05. Tuy nhiên các giá trị Asymp.Sig = 0.074 > 0.05 của cặp

23

dADE - NDEAL

35.00 36.46

Sum of Ranks 1610.00 875.00

NEA2 - NDEAL

24.37 44.53

853.00 1425.00

Negative Ranks Positive Ranks Ties Total Negative Ranks Positive Ranks Ties Total

29.41 40.39

1353.00 727.00

LSEAGP - NDEAL Negative Ranks Positive Ranks Ties Total

28.70 44.22

1349.00 796.00

LSEAEA - NDEAL Negative Ranks Positive Ranks Ties Total

N Mean Rank 46 24 30 100 35 32 33 100 46 18 36 100 47 18 35 100

Test Statistics NEA2 -NDEAL -1.787 .074

dADE -NDEAL -2.151 .031

LSEAGP -NDEAL -2.093 .036

LSEAEA -NDEAL -1.807 .071

Z Asymp. Sig (2-tailed)

Bảng 4.4: Kiểm định Wilcoxon của các thuật toán

NEA2 và NBCDEAL và Asymp.Sig = 0.071 > 0.05 của cặp LSEAEA và NBCDEAL cho thấy chưa đủ cơ sở thống kê với mức ý nghĩa 5% để khẳng định sự khác nhau giữa các thuật toán này.

4.6 Kết luận

Trong chương này, luận án đã trình bày 4 thuật toán SharingDEAL, CrowdingDEAL, SpeciesDEAL và NBCDEAL là sự kết hợp thuật toán DEAL với các kỹ thuật niching phổ biến.

Các kết quả thực nghiệm và so sánh kiểm định thống kê cho thấy các thuật toán mới đề xuất có lợi thế so với các thuật toán tiến hóa cùng loại trong việc giải quyết một lớp bài toán tối ưu đa cực trị phổ biến. Thuật toán NBCDEAL có thể so sánh được với các thuật toán tiến hóa được đánh giá tốt hiện nay.

24

Kết luận

Thuật toán tiến hóa là một lĩnh vực nghiên cứu khó khăn nhưng hấp dẫn và đầy tiềm năng. Việc nghiên cứu, đề xuất các thuật toán mới luôn nhận được sự quan tâm của nhiều nhà khoa học. Một trong các xu hướng thiết kế là dựa vào thông tin định hướng, các thuật toán theo xu hướng này đã và đang khẳng định ưu thế trong tính toán tiến hóa nói riêng và tính toán số nói chung.

Với mục tiêu thiết kế một thuật toán tiến hóa mới, có thể so sánh được với các thuật toán tiến hóa mới được đề xuất. Luận án đã tập trung nghiên cứu từ các nội dung mang tính lý thuyết như tối ưu hóa, như tính toán tiến hóa với các thuật toán tiến hóa đến các nội dung mang tính kỹ thuật như thiết kế và thực nghiệm các thuật toán. Cho đến nay luận án đã đạt được một số kết quả sau đây:

1. Luận án đã đề 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ụ - là hướng từ một cá thể kém hơn (hạng 2) đến một cá thể ưu tú và (2) hướng tản mát - 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. Tập các cá thể ưu tú được tổ chức lưu trữ trong tệp ETS và liên tục được cập nhật trong suốt quá trình tiến hóa.

• 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 hóa DEAL có tên là PCCDEAL (Parallel CoOperative CoEvolution for DEAL) được xây dựng trên mô hình song song kiểu mới không hoàn toàn giống với mô hình master/slaves truyền thống. Các kết quả lý thuyết và thực nghiệm được kiểm tra đánh giá cho thấy tính hiệu quả của mô hình.

25

2. Luận án đã đề 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 tối ưu đa cực trị với 4 thuật toán SharingDEAL, CrowdingDEAL, Specied- DEAL 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 cho thấy: Trong các giải pháp kết hợp giữa một thuật toán EA với các phương pháp niching nhằm giải quyết các bài toán tối ưu đa cực trị được lựa chọn thì thuật toán DEAL đang cho kết quả tốt, có thể so sánh được với một số thuật toán tiến hóa đã thành công trong thời gian gần đây.

Tuy nhiên, từ những kết quả nghiên cứu đã đạt được có thể nhận thấy một số vấn đề cần được tiếp tục đầu tư nghiên cứu thêm, đó là:

1. Đối với vấn đề sử dụng 2 dạng thông tin định hướng. Luận án đang tổ chức và sử dụng cân đối giữa thông tin hướng hội tụ và thông tin hướng tản mát nhằm đảm bảo sự cân đối chung giữa tính hội tụ và tính đa dạng của một thuật toán ngẫu nhiên. Sự cân đối này có thể giải quyết được nhiều lớp bài toán. Tuy nhiên đối với các lớp bài toán cụ thể khác nhau, vấn đề thích nghi khi ưu tiên hướng hội tụ hay hướng tản mát cũng cần được quan tâm hơn.

2. Đối với vấn đề song song hóa thuật toán DEAL. Để đánh giá hiệu quả của mô hình song song được đề xuất, luận án sử dụng kỹ thuật chia đều về chiều khi thực hiện phân tách bài toán thành các bài toán thành phần. Tuy nhiên, kỹ thuật này là đơn giản và chỉ thực sự có hiệu quả đối với lớp bài toán tối ưu khả tách. Còn đối với các bài toán không khả tách, các kết quả thực nghiệm cho thấy nhiều khó khăn và vướng mắc. Bởi vậy quan tâm đến kỹ thuật chia bài toán sẽ là một nhiệm vụ nghiên cứu tiếp theo.

3. Thuật toán DEAL đã được thiết kế và thực nghiệm với rất nhiều bài toán, các kết quả thử nghiệm đều cho thấy sự khả quan. Tuy nhiên đây chỉ mới là các bài toán thử nghiệm mang tính lý thuyết, được xây dựng từ kinh nghiệm thiết kế và vận hành các thuật toán. Sẽ tròn vẹn hơn nếu thuật toán DEAL được thử nghiệm với một bài toán thực tế.

26

Danh sách công trình của tác giả

Ct1. Chi Cuong Vu, Huu Hung Nguyen, and Lam Thu Bui. A parallel cooperative coevolution evolutionary algorithm. In Third International Conference on Knowledge and Systems Engineering, KSE 2011, October 14-17, 2011, pages 48–53, 2011, IEEE Press.

Ct2. Chi Cuong Vu, Lam Thu Bui, and Huu Hung Nguyen. Towards a theoretic model for parallelization of cooperative co- evolutionary algorithms. Journal of Science and Technology: the Section on Information and Communication Technology (JICT), (150):32–48, 2012

Ct3. Chi Cuong Vu, Lam Thu Bui, and Hussein A. Abbass. DEAL: A direction-guided evolutionary algorithm. In Simulated Evolution and Learning - 9th International Conference 2012, Lec- ture Notes in Computer Science, vol 7673, December 16-19, 2012, pages 148–157, 2012, Springer Berlin Heidelberg.

Ct4. Chi Cuong Vu and Lam Thu Bui. Fitness sharing for the direction-guided evolutionary algorithm. Journal of Science and Technology: the Section on Information and Communication Technology (JICT), (4):34–46, 2014.

Ct5. Chi Cuong Vu and Lam Thu Bui. The direction-based evo- lutionary algorithm with a crowding mechanism. In Ad- vanced Technologies for Communications (ATC), 2014 Interna- tional Conference on, pages 175–180, Oct 2014, IEEE Press.

27

Tài liệu tham khảo

28