Rand Là Số Ngẫu Nhiên Trong Đoạn [1,d], Giá Trị I Rand Đảm Bảo Vector X I Luôn

tính bởi hàm Ring() như sau:

Function Ring(xi)

Input: phương án đang xét xi

Output: x trong đó Fitness(x) = min{Fitness(xi), Fitness(Left(xi)), Fitness(Right(xi))}

Hàm tìm kiếm lân cận Variable_Neighborhood_Searching(), hạt nhân của thuật toán LPSO được mô tả như sau:

Function Variable_Neighborhood_Searching ( )

Input: vector vị trí xi

Output: vector vị trí xk có Fitness(xk) < Fitness(xi) Begin

1. t = 0; // Khởi tạo bước lặp

2. while (Fitness(xk) > Fitness (xi) and (t <

Max_Iteration))

3. r = random [1,M]; // Khởi tạo giá trị r ngẫu nhiên trong đoạn [1, M]

4. xi = RotateRight(xi, r);

5. rand1 = [1,M]; rand2 = [1,M]; // Khởi tạo ngẫu nhiên rand1, rand2 [1,M]

6. xk = Exchange (xi, rand1, rand2);

7. if Fitness(xk) < Fitness(xi) then

8. return xk

9. else

10. return xi;

12. end if 11. t = t+1;

12. end while

(a)

(b)

End.

Có thể bạn quan tâm!

Xem toàn bộ 156 trang tài liệu này.

3	1	2	3	1

Hình 1.8. Hàm RotateRight (a) và hàm Exchange (b)

trong đó hàm RotateRight() và hàm Exchange() được thiết kế để giúp tạo ra cá thể đột biến cho quần thể hiện tại.

Hàm RotateRight sẽ tịnh tiến toàn bộ các phần tử của phương án về bên phải, còn hàm Exchange sẽ hoán đổi hai phần tử của phương án như hình 1.8.

1.2.3. Thuật toán DE

Tiến hóa vi phân (Differential Evolution - DE) được đề xuất bởi R. Storn và K. Price vào năm 1997 [26], đây là một giải thuật tiến hóa dựa trên thông tin định hướng để tạo ra các cá thể ở thế hệ tiếp theo bằng cách sử dụng các toán tử lai ghép, đột biến và chọn lọc. Đặc trưng của thuật toán DE là sử dụng thông tin định hướng trong toán tử đột biến để làm đột biến các cá thể của quần thể hiện tại. Hoạt động của thuật toán DE được mô tả như sau:

Bước 1: Giả sử không gian tìm kiếm gồm D chiều, mỗi cá thể i được biểu diễn bởi một vector D chiều xi = (xi,1, xi,2,…,xi,D), trong đó xi,j R, i=1,2,…,N; j=1,2,…,D.

Để đột biến cá thể xi thuật toán DE lựa chọn 3 cá thể ngẫu nhiên từ quần thể xr1 xr2 xr3 xi. Khi đó cá thể vi được tính như sau:

vi = xr1 + F × (xr2 – xr3) (1.13)

trong đó F là một hằng số thuộc đoạn [0,1] và được gọi là hằng số đột biến, cá thể vi được gọi là cá thể đột biến của cá thể xi. Tham số F được sử dụng để điều chỉnh độ lớn của vector định hướng và được gọi là độ dài bước nhảy định hướng.

Bước 2: Tiếp theo, thuật toán DE sử dụng toán tử lai ghép để kết hợp thông tin giữa cá thể cha xi và cá thể đột biến vi. Toán tử lai ghép được thực hiện bằng cách chọn một số ngẫu nhiên CR  [0,1] làm xác suất lai ghép và các thành phần của cá thể sau lai ghép ui được tính như sau:

𝑢𝑖,𝑗

= {𝑣𝑖,𝑗 𝑛ế𝑢 𝑟𝑎𝑛𝑑𝑖,𝑗 ≤ 𝐶𝑅 ℎ𝑜ặ𝑐 𝑖 = 𝐼𝑟𝑎𝑛𝑑

𝑥𝑖,𝑗 𝑛ế𝑢 𝑟𝑎𝑛𝑑𝑖,𝑗 > 𝐶𝑅 ℎ𝑜ặ𝑐 𝑖 ≠ 𝐼𝑟𝑎𝑛𝑑

(1.14)

với i=1,2,…,N; j=1,2,..,D, trong đó:

randi,j là một số ngẫu nhiên trong đoạn [0,1],

Irand là số ngẫu nhiên trong đoạn [1,D], giá trị Irand đảm bảo vector xi luôn luôn khác vector vi.

Bước 3: Sau cùng, phép chọn theo công thức (1.15) được áp dụng trên cá thể cha xi và cá thể ui để chọn ra cá thể cho thế hệ tiếp theo.

𝑥 (𝑡 + 1) = {𝑢𝑖 (𝑡) 𝑛ế𝑢 𝑓(𝑢𝑖 (𝑡)) < 𝑓(𝑥𝑖 (𝑡))

(1.15)

𝑖 𝑥𝑖 (𝑡) 𝑛ế𝑢 𝑛𝑔ượ𝑐 𝑙ạ𝑖

Chi tiết thuật toán DE được trình bày như trong Algorithm 1.2 dưới đây.

Algorithm 1.2. DE

Input: N :kích thước quần thể, CR : xác suất lai ghép Output: phương án tối ưu

1. Begin

2. t = 0

3. P = initialize(N)

4. gbest = fbest(P)

5. while(t < tmax)

6. for (int i = 0; i< N; i++)

7. xr1 xr2 xr3 xi = rand(1,N)

8. vi(t) = xr1 + F (xr2- xr3)

9. Irand = randi(1,D)

10. for(j=0; j < D;j++)

11. if (i = Irand OR rand(0,1) <= CR)

12. ui,j= vi,j

13. else

14. ui,j= xi,j

15. end if

16. end for

17. if(f(ui(t))f(xi(t)))

18. xi(t+1) = ui(t)

19. else

20. xi(t+1) = xi(t)

21. end if

22. end for

23. gbest = fbest(P)

24. t = t+1

25. end while

26. return gbest 27.End

Trong đó:

f: hàm mục tiêu

fbest: hàm tìm cá thể tốt nhất trong quần thể

Điểm khác biệt cơ bản của thuật toán DE với các thuật toán tiến hóa khác là ở toán tử đột biến. R. Storn và K. Price[26] đã đề xuất nhiều chiến lược lược đột biến khác nhau và tạo ra các phiên bản DE khác nhau. Sau đây là một số phiên bản khác của DE:

- rand/1

- best/1

vi = xr1 + F(xr2 – xr3) vi = xbest + F(xr1 – xr2)

- current to best /1

vi = xi + K(xbest – xi)+F(xr1 – xr2)

- best/2

- rand/2

- current/2

vi = xbest + K(xr2 – xr3) + F(xr3 – xr4) vi = xr1 + K(xr2 – xr3) + F(xr4 – xr5)

vi = xi + K(xr3 – xi) + F(x1 – xr2)

- phương pháp bánh xe quay vòng dựa trên hạng cá thể [CT1]

trong đó F và K là các bước nhảy định hướng, xr1, xr2, xr3, xr4, xr5 là các cá thể được chọn một cách ngẫu nhiên từ quần thể, xbest là cá thể tốt nhất trong quần thể.

1.2.4. Thuật toán Cuckoo Search

1.2.4.1. Khái niệm bước dịch chuyển ngẫu nhiên

Thuật ngữ “random walk” được đưa ra lần đầu bởi Karl Pearson[27] vào năm 1905. Bước dịch chuyển ngẫu nhiên, đôi khi còn gọi là bước đi ngẫu nhiên hay quá trình ngẫu nhiên (Random walk)[30], được thể hiện bởi một chuỗi những biến đổi không xác định trước, chẳng hạn như chuỗi biến đổi của các dữ liệu tài chính như giá cổ phiếu chứng khoán, tỷ giá ngoại tệ, các dữ liệu y khoa như huyết áp, các bước di chuyển để kiếm mồi của động vật... Năm 2020, hai nhà khoa học Hillel Furstenberg (Mỹ) và Gregory Margulis (Nga) đã được trao giải thưởng Abel - được đánh giá như giải Nobel toán học- cho một nghiên cứu về bước dịch chuyển ngẫu nhiên.

Về mặt toán học, bước dịch chuyển ngẫu nhiên được đặc trưng bởi một biến mô tả một quá trình biến đổi ngẫu nhiên trong miền giá trị nào đó. Một cách tổng quát, random walk là một quá trình ngẫu nhiên bao gồm một chuỗi biến đổi liên tiếp và được thể hiện như công thức 1.16 dưới đây.

𝑖=1

𝑆𝑁 = ∑𝑁

𝑋𝑖 = 𝑆𝑁−1 + 𝑋𝑁

(1.16)

trong đó bước dịch chuyển thứ i, Xi, có độ lớn và hướng tuân theo một phân phối xác suất nào đó. Trạng thái hiện tại (SN) phụ thuộc vào trạng thái trước đó (SN-1) và bước dịch chuyển XN.

Hình 1.8 là ví dụ đơn giản nhất về 5 lần dịch chuyển ngẫu nhiên trong tập các số nguyên Z, trong đó độ lớn của mỗi bước theo 2 trục tọa độ là 1 hoặc 0.

Hình 1.8. Năm lần dịch chuyển ngẫu nhiên trong tập số nguyên Z2

Một ví dụ nổi tiếng hơn về bước dịch chuyển ngẫu nhiên là chuyển động Brown[63]. Khi thả một hạt phấn hoa xuống nước, dùng kính hiển vi quan sát ta thấy hạt phấn hoa chuyển động hỗn loạn không ngừng. Chuyển động đó của các hạt rất nhỏ (cỡ micromet) trong chất lỏng hay chất khí được gọi là chuyển động Brown, gây ra bởi sự va chạm với các phân tử nước hay không khí chuyển động, động năng của các phân tử này được cung cấp bởi nhiệt độ môi trường.

Hình 1.9 [63] là mô phỏng quỹ đạo chuyển động Brown của 5 hạt phấn hoa (hình vuông) được thúc đẩy bởi các va chạm với 800 phần tử chuyển động

khác. Vector chuyển động của một trong năm hạt phấn hoa được biểu thị bằng mũi tên. Hình 1.9 cũng gợi ý cho một thuật toán tiến hóa nhằm tìm kiếm lời giải gần đúng bằng cách sử dụng quần thể gồm nhiều cá thể (trong trường hợp này là 5).

Hình 1.9. Chuyển động Brown của 5 hạt phấn hoa

Hình 1.10[63] mô tả quỹ đạo chuyển động của 3 hạt keo kích thước 0,53

µm trong môi trường nước được quan sát dưới kính hiển vi. Các vị trí liên tiếp sau mỗi 30 giây được nối bằng các đoạn thẳng, kích thước mỗi mắt lưới là 3,2

µm.

Hình 1.10. Chuyển động Brown của 3 hạt keo

Về mặt toán học, chuyển động Brown được biểu diễn bởi quá trình Wiener

(X0, X1, X2,...) một quá trình ngẫu nhiên liên tục được đặt tên theo Norbert

Wiener và được sử dụng nhiều trong vật lý, toán học và kinh tế, trong đó:

X0 = 0;

Xt là một biến ngẫu nhiên liên tục theo thời gian, chẳng hạn như tọa độ của hạt phấn hoa hay giá trị cổ phiếu (khác với những biến ngẫu nhiên rời rạc như trong ví dụ gieo xúc sắc hay bắn bia);

Xj - Xi (0, j-i) trong đó N(,2) là phân phối chuẩn (còn gọi là phân phối Gauss) với kỳ vọng và phương sai 2.

Bước dịch chuyển ngẫu nhiên có nhiều loại phụ thuộc vào phân phối xác suất nào sẽ chi phối độ lớn của các bước dịch chuyển. Ứng dụng của mỗi loại khác nhau, không gian dịch chuyển có thể chỉ là tập số nguyên (Z) hay số thực (R), không gian hình học 2 hay 3 chiều, các bề mặt cong trong không gian N chiều.

Bước dịch chuyển ngẫu nhiên có nhiều ứng dụng thực tế. Trong lĩnh vực tài chính, chuyển động Brown thường được dùng để mô phỏng sự dao động phức tạp của những đại lượng trên thị trường chứng khoán như giá cổ phiếu, quyết định đặt lệnh niêm yết, gọi vốn, mua, bán cổ phiếu.

Trong lĩnh vực sinh thái học, tâm lý học, khoa học máy tính, vật lý, hóa học, sinh học, kinh tế học và xã hội học, bước dịch chuyển ngẫu nhiên được sử dụng để mô hình hóa nhiều quá trình trong các lĩnh vực này và đóng vai trò như một mô hình cơ bản cho các hoạt động mang tính không xác định. Trong toán học, giá trị của π có thể được tính gần đúng bằng cách sử dụng bước dịch chuyển ngẫu nhiên. Trong phạm vi luận án này, mục tiêu đặt ra là tìm các lời giải gần đúng trong một không gian tìm kiếm rộng thì bước dịch chuyển ngẫu nhiên chính là công cụ phù hợp để vừa lục soát kỹ vùng lân cận xung quanh vị trí hiện thời (thao tác Exploitation) vừa thực hiện những bước nhảy vọt xa để khám phá những khu vực mới (thao tác Exploration).

Một bước dịch chuyển ngẫu nhiên điển hình đồng thời cũng là cơ sở toán học của thuật toán Cuckoo Search là bước dịch chuyển Lévy Flight.

1.2.4.2. Bước dịch chuyển Lévy Flight

Được đặt tên theo nhà toán học Pháp Paul Lévy, Lévy Flight là bước dịch chuyển ngẫu nhiên trong đó độ lớn của bước dịch chuyển biến đổi theo phân phối xác suất Lévy, hướng dịch chuyển là bình đẳng giữa các chiều của không gian dịch chuyển (từ nay gọi là “không gian tìm kiếm” hay “không gian lời giải” cho phù hợp với vấn đề đặt ra trong luận án).

Phân phối xác suất Lévy là phân phối xác suất liên tục của một biến ngẫu nhiên không âm. Hàm mật độ xác suất của phân phối Lévy trong miền giá trị x [, +) là:

𝑓(𝑥, 𝜇, 𝑐) = √ 𝑐

−2( 𝑐 𝜇)

𝑥−

𝑒

(1.17)

2𝜋

Có thể nhận thấy:

(𝑥−𝜇)3/2

√

𝑓(𝑥, 𝜇, 𝑐)~ 𝑐

2𝜋

𝑥3/2

𝑘ℎ𝑖 𝑥 → ∞ (1.18)

Hàm mật độ này được thể hiện như trong hình 1.11.

Hình 1.11. Đồ thị hàm mật độ xác suất của phân phối Lévy