Một Số Thuật Toán Metaheuristic Tìm Nghiệm Gần Đúng

Baradaran có nhiều điểm tương đồng với luận án này về bài toán (MS-RCPSP), về cách lựa chọn giải pháp (là những thuật toán tiến hóa mới thay vì những thuật toán “truyền thống” như GA, PSO) và về việc lựa chọn bộ dữ liệu thực nghiệm (iMOPSE). Tuy nhiên những bài toán của Hosseinian và Baradaran mới chỉ dừng ở mô hình lý thuyết, chưa được gắn với thực tế cũng như chưa được thực nghiệm trên một bộ dữ liệu thực tế. Trong luận án này, ngoài thực nghiệm với bộ dữ liệu iMOPSE, các thuật toán mới còn được kiểm chứng bằng việc triển khai thực nghiệm trên các bộ dữ liệu thực tế.

Ngoài các nhóm nghiên cứu dài hạn với những chuỗi bài báo, nhiều tác giả đã công bố những công trình đơn lẻ, đại đa số dựa trên các thuật toán tiến hóa.

Năm 2017, Javanmard và cộng sự sử dụng 2 thuật toán tiến hóa truyền thống là GA và PSO để lên phương án lịch biểu cho các tài nguyên đa kỹ năng (trên thực tế là các công nhân và kỹ sư) thực hiện một dự án trong ngành hóa chất với mục tiêu tối thiểu hóa tổng chi phí của dự án [51]. Hai thuật toán đề xuất được kiểm chứng trên bộ dữ liệu PSPLIB [47], vốn không hoàn toàn thích hợp với những bài toán lập lịch có mục tiêu là tối thiểu hóa chi phí. Hơn nữa ở khâu thực nghiệm các tác giả không so sánh được các thuật toán truyền thống của mình với những thuật toán mới hơn mà chỉ so sánh với nhau.

Cũng nghiên cứu các bài toán đa mục tiêu như nhóm của Hosseinian, H. Davari-Ardakani [21] đề xuất một biến thể đa mục tiêu của bài toán MS- RCPSP nhằm tối thiểu hóa hai đại lượng là thời gian và chi phí thực hiện của dự án. Bài toán đề xuất, được tác giả ký hiệu là MSPSP [21], chỉ giới hạn trong những dự án có 2 đặc điểm (có thể nói là không quá phổ biến) sau đây:

- Thời điểm thực hiện là tùy ý, chẳng hạn dự án có thể được thực hiện vào các buổi tối hoặc ngày nghỉ cuối tuần

- Chi phí về năng lượng là rất cao, có thể so sánh được với tiền lương trả cho nhân viên.

Dừng lại ở việc phát biểu bài toán, H. Davari-Ardakani và đồng nghiệp [21] chưa đề xuất được giải pháp mới mà chỉ tiến hành thực nghiệm với những giải pháp đã có như Max-min, vì vậy bài toán có thể coi là vẫn còn để mở.

Để giải quyết bài toán MS-RCPSP, H. Dai [15] sử dụng thuật toán Memetic, là phiên bản cải tiến của thuật toán GA nhờ bổ sung thêm thao tác tìm kiếm lân cận (local search). Cách tiếp cận H. Dai khá tương đồng với luận án này ở các điểm sau:

- Lựa chọn iMOPSE làm bộ dữ liệu thực nghiệm;

- Lựa chọn các thuật toán của nhóm Myszkowski làm đối tượng so sánh do tính hiệu quả của chúng.

Tuy nhiên công trình của H. Dai có một số hạn chế sau:

- Lựa chọn những thuật không phải là hiệu quả nhất của nhóm Myszkowski làm đối tượng so sánh, chẳng hạn thuật toán GRASP;

- Thuật toán đề xuất (memetic) là một trong những thuật toán truyền thống, đã được sử dụng từ lâu nên không còn nhiều tính đột phá.

Nemati-Lafmejani [48] đã phát triển một mô hình tối ưu hóa tích hợp hai mục tiêu để giải quyết bài toán MS-RCPSP, mục tiêu của mô hình đề xuất là giảm thiểu chi phí và thời gian thực hiện dự án. Younis và cộng sự [38] đã đề xuất một thuật toán metaheuristic kết hợp các phương pháp tiếp cận tối ưu hóa đàn kiến và tìm kiếm lân cận để lập lịch trong điện toán lưới.

Một số nghiên cứu tập trung giải quyết các lớp bài toán con khác của MS- RCPSP. Zhu và cộng sự [29] đã đề xuất một thuật toán tiến hóa dựa trên kỹ thuật multi-verse kết hợp với một số thuật toán heuristic khác.

Một số tác giả cũng đã nghiên cứu để áp dụng bài toán MS-RCPSP cho nhiều lĩnh vực khoa học và tài chính. O.P. Mejia [40] đã phát triển một thuật toán lập lịch để quản lý các hoạt động của phòng thí nghiệm hạt nhân. Để giải

quyết vấn đề của các cảm biến dày đặc trong mạng cảm biến không dây, R. Wan [49] đề xuất một thuật toán lập lịch tiết kiệm năng lượng, sắp xếp một số cảm biến dự phòng vào chế độ nghỉ để giảm xung đột truyền dữ liệu và tiêu hao năng lượng. W. Guo [56] đã phát triển một thuật toán dựa trên PSO có được hiệu suất tốt hơn so với các phương pháp tiếp cận trước đây về sử dụng năng lượng. H. Cheng [14] và cộng sự đã xây dựng một thuật toán dựa trên PSO khác có tên là DPSO-CA dựa trên PSO rời rạc nhằm mục đích giảm thiểu nhiễu đồng kênh trong mạng. MS-RCPSP cũng được nghiên cứu và áp dụng trong lĩnh vực tài chính ngân hàng bởi Black and Scholes [11] và Chen[58].

Bảng 1.3 dưới đây tổng hợp lại các nghiên cứu chính liên quan đến bài toán MS-RCPSP.

Bảng 1.3: Tổng hợp các nghiên cứu về bài toán MS-RCPSP

Năm	Nhóm tác giả	Thuật toán	Bộ dữ liệu
1	2017	Javanmard [47],[51]	GA, PSO	PS-LIB
2	2013- 2019	Myszkowski và cộng sự [31],[42],[43],[44],[45]	GA, Ant, Greedy,...	iMOPSE
3	2018	Hosseinian [4],[5],[6],[7]	GA, PSO	ProGen, iMOPSE
4	2019	H. Davari-Ardakani [21]	Min-Max	iMOPSE
5	2019	Huafeng Dai [15]	Memetic	iMOPSE

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

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

Luận án tập trung giải quyết bài toán MS-RCPSP bằng các thuật toán Metaheuristic mới, các thuật toán được kiểm chứng qua việc thực nghiệm với bộ dữ liệu iMOPSE. Đồng thời, để gắn với thực tế, luận án cũng đề xuất bài toán mới Real-RCPSP, các thuật toán giải bài toán này và triển khai thực nghiệm với các bộ dữ liệu thực tế để kiểm chứng.

1.2. Một số thuật toán metaheuristic tìm nghiệm gần đúng

Để tìm nghiệm gần đúng có rất nhiều thuật toán đã được đề xuất và sử dụng như Thuật toán nhánh cận [CT3], Tabu Search [CT6], PSO, DE, Cuckoo

Search,... Luận này sử dụng các thuật toán PSO, DE, Cuckoo Search.

1.2.1. Thuật toán PSO

Tối ưu bầy đàn (Particle Swarm Optimization - PSO) [23],[33],[56],[59], [CT2] là một thuật toán tiến hóa. Tương tự như các thuật toán tiến hóa khác, PSO sẽ tiến hành tìm kiếm dựa trên quần thể, ban đầu quần thể được khởi tạo một cách ngẫu nhiên với số cá thể xác định. Tuy nhiên PSO khác với các thuật toán tiến hóa khác là mỗi cá thể trong quần thể được xác định bởi hai tham số cơ bản là vector vị trí (đại diện cho kinh nghiệm của cá thể qua các thế hệ) và vector vận tốc (vector dịch chuyển - đại diện cho kinh nghiệm của quần thể qua các thế hệ). Mỗi cá thể sẽ dịch chuyển trong không gian tìm kiếm với một vận tốc riêng, sau mỗi thế hệ các cá thể sẽ dịch chuyển theo hướng về vị trí tốt nhất của chính cá thể đó trong quá khứ và vị trí tốt nhất của quần thể và sau mỗi thế hệ các cá thể sẽ hướng tới các vùng tìm kiếm tốt hơn trong không gian tìm kiếm. Trong quá trình tìm kiếm các cá thể sẽ cập nhật vector dịch chuyển và vector vị trí theo giá trị tốt nhất của chính cá thể đó trong quá khứ và vị trí tốt nhất của quần thể theo công thức sau:

vik+1 = 𝜔.vik+c1.rand1().(pbesti – xik) + c2.rand2().(gbest – xik) (1.10)

xik+1 = xik + vik+1 (1.11)

Trong đó:

- vik+1: là vector dịch chuyển của cá thể i ở thế hệ k+1;

- vik: là vector dịch chuyển của cá thể i ở thế hệ k;

- xik+1: là vector vị trí của các thể i ở thế hệ k+1;

- xik: là vector vị trí của cá thể i ở thể hệ k;

- pbesti: là vector vị trí tốt nhất của cá thể i tính tới thời điểm hiện tại;

- gbest: là vector vị trí tốt nhất của quần thể tính tới thời điểm hiện tại.

- Các hệ số trong công thức PSO với ý nghĩa như sau:

o : hệ số quán tính;

o c1, c2: là các hệ số gia tốc thể hiện cho đặc trưng về mặt kinh nghiệm của các thể và kinh nghiệm của quần thể.

rand1, rand2: là các hệ số ngẫu nhiên trong đoạn [0,1]

𝑐1 × 𝑟1 × (𝑔𝑏𝑒𝑠𝑡 − 𝑥𝑘 )

𝑖

𝑤 × 𝑣𝑘

𝑐1 × 𝑟1 × (𝑝𝑏𝑒𝑠𝑡𝑖 − 𝑥𝑘 )

𝑖

𝑥𝑘+1

𝑖

𝑔𝑏𝑒𝑠𝑡

𝑥𝑘

𝑖

𝑔 − 𝑥𝑘

𝑏𝑒𝑠𝑡

𝑖

𝑝𝑏𝑒𝑠𝑡𝑖 − 𝑥𝑘

𝑖

𝑝𝑏𝑒𝑠𝑡𝑖

Hình 1.6. Sơ đồ di chuyển của một cá thể i trong PSO

Chi tiết thuật toán PSO được thể hiện như trong Algorithm 1.1 dưới đây.

Algorithm 1.1. PSO

Input: tmax: số thế hệ

Output phương án tốt nhất gbest

1 Begin

2 Pall = Load dữ liệu iMOPSE và khởi tạo quần thể ban đầu 3 t = 0

4 while ( t < tmax ) 5 t = t + 1

6 for i=1 to size(Pall) do

7 tính giá trị hàm mục tiêu f(Pi)

8 end for

9 for i = 1 to size(Pall) do

10 if f(Pi) < f(fitnessi) then

11 pbesti = Pi

12 f(pbesti) = f(Pi)

13 end if

14 end for

15 for i=1 to size(Pall) do

16 gbest = Pi

17 f(gbest) = f(Pi)

18 end for

19 for i=1 to size(Pall) do

20 cập nhật vector dịch chuyển theo (1.3)

21 Cập nhật vector vị trí theo (1.4)

22 end for

23 end while

24 return gbest

25 end

Trong đó:

- f: objective function

- fitnessi: Giá trị tốt nhất của cá thể thứ i trong quần thể từ thế hệ đầu tiên cho đến thế hệ hiện tại.

1.2.2. Thuật toán PSO kết hợp với tìm kiếm lân cận

Phương pháp Tìm kiếm lân cận [16] (hay còn gọi là Tìm kiếm cục bộ, Local Search) là phương pháp heuristic thường được áp dụng để tìm phương án tối ưu hoặc cận tối ưu trong một không gian tìm kiếm mà khoảng cách giữa hai phương án bất kỳ đã được định nghĩa, tức là đã có một phép đo khoảng cách giữa hai phương án. Dựa trên đại lượng khoảng cách đó, khái niệm vùng lân cận sẽ được xác định. Ý tưởng chung của phương pháp Tìm kiếm lân cận là thực hiện vòng lặp gồm các bước sau:

1. Khởi tạo phương án ban đầu (theo kiểu ngẫu nhiên hoặc bằng một kỹ thuật nào đó).

2. Áp dụng một phép biến đổi cho phương án hiện có để thu được một tập phương án lân cận, đây là những phương án có khoảng cách (được xác định theo một độ đo xác định trước) tới phương án ban đầu nhỏ hơn hoặc bằng một ngưỡng quy định.

3. Lựa chọn phương án tốt nhất trong tập phương án lân cận, gán giá trị này cho phương án hiện có rồi quay trở lại đầu vòng lặp (bước 2).

Vòng lặp trên được thực hiện cho tới khi tìm được phương án đủ tốt để thỏa mãn điều kiện dừng.

Phương pháp Tìm kiếm lân cận đã được các nhóm nghiên cứu tích hợp vào PSO để cải thiện chất lượng của cá thể tại mỗi vòng đời [3],[19]. Trong không gian tìm kiếm, các phương án không hoàn toàn độc lập mà thường có mối quan hệ, mối quan hệ đó chi phối nhiều đặc tính của chúng. Chẳng hạn như trong bài toán Scheduling thì hai lịch biểu càng có nhiều thành phần trùng nhau thì giá trị makespan của chúng càng có khả năng gần nhau. Dựa vào quy luật tự nhiên này, các nhà nghiên cứu đã đề xuất nhiều kiểu lân cận (topology) khác nhau

như kiểu Ring, kiểu Von Neuman. Mỗi topology đó mô tả một cách xác định thứ tự giữa các phương án trong tập lân cận. Hình sau là một số kiểu lân cận được mô tả trong [3].

k-1

...

k+1

m-1

m+1

k-1

k+1

n-1

n+1

k-1

k+1

(a)

(b)

Hình 1.7. Kiểu lân cận Ring (a) và Von Neumann (b)

Sau khi đã xác định được thứ tự giữa các phương án lân cận, phương án

xik+1 ở vòng đời tiếp theo sẽ được xác định là:

xik+1 = xik + vik (1.12)

với vector dịch chuyển được định nghĩa bằng công thức:

vik+1 = ×vik + c1 rand1× (pbesti - xik) + c2rand2× (lbesti - xik)

Công thức này tương tự như công thức gốc của PSO được xây dựng bởi Kennedy và Eberhart, chỉ thay phương án tốt nhất của quần thể gbesti bằng phương án tốt nhất lbesti trong tập lân cận của phương án đang xét xik.

Trong bài báo [CT2] đã xây dựng thuật toán L-PSO áp dụng phương pháp Tìm kiếm lân cận, tuy nhiên bài toán đặt ra trong [CT2] không phải là đối tượng nghiên cứu của luận án này, vì vậy phần phát biểu bài toán và phần thực nghiệm không được giới thiệu ở đây, mà chỉ trình bày việc tích hợp phương pháp lân

cận tích hợp trong thuật toán PSO. Trong [CT2], áp dụng phương pháp lân cận Ring với vùng lân cận có phạm vi k = 2, nghĩa là phương án đang xét xi sẽ có tập lân cận bao gồm 2 phần tử là left (xi) và right (xi). Thuật toán đề xuất L- PSO được mô tả trong [CT2] như sau:

Algorithm LPSO()

Input: T,S,dữ liệu công việc W[1×M],P[1×N],B[N×N],D[M×M], hằng số K, độ lệch , số lượng cá thể của quần thể NoP

Output: phương án gần đúng tốt nhất gbest

Begin

1. For i=1 to NoP do

2. xi= random vectors; vi= random vectors; // Khởi tạo giá trị ngẫu nhiên cho vector vị trí và vector dịch chuyển của cá thể i

3. end for

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

5. While (the deviation of gbest >) Do

6. for i=1 to NoP do

7. Compute new position xi // Tính vector vị trí xi

theo công thức (1.12)

8. end for

9. for i=1 to NoP do

10. Update pbesti; // Cập nhật pbesti

11. end for

12. Update gbest; // Cập nhật gbesti

13. for i=1 to NoP do

14. lbesti = Ring(xi) ; // Cập nhật lbesti

15. end for

16. for i=1 to NoP do

17. Update vik and compute xi ; // Cập nhật vector dịch chuyển vik và xi

19. end for

20. t++ ;

21. if (the deviation of gbest ≤ after K generations)

// nếu sau K thế hệ mà độ lệch giữa các gbest

không vượt quá 

then gbest= Variable_Neighborhood_Searching (gbest);

23. End while;

24. Return gbest;

End Function

Trong đó phương án lân cận tốt nhất lbesti của phương án hiện tại xi sẽ được