Hình 1.12 mô phỏng 1000 bước dịch chuyển Lévy flight trong không gian hai chiều với tọa độ xuất phát là [0,0], hướng dịch chuyển được phân bố đều, độ lớn các bước tuân theo phân phối Lévy.
Bước dịch chuyển ngẫu nhiên Lévy Flight đã được các nhà khoa học xác nhận là phù hợp để mô tả quỹ đạo di chuyển của các động vật (chim, thú) khi đi kiếm mồi. Vì thế trong thuật toán Cuckoo Search, Lévy Flight được sử dụng để biến đổi các phương án (tức là các cá thể) từ vòng đời trước sang vòng đời sau.
Trong hình 1.12, lưu ý rằng khi được cài đặt với những tham số phù hợp, Lévy flight thực hiện thao tác Exploration tốt hơn nhờ có những bước nhảy tầm xa, ngược lại chuyển động Brown thực hiện thao tác Exploitation kỹ càng hơn để lục soát trong phạm vi lân cận.
Hình 1.12. 1000 bước dịch chuyển Lévy flight và chuyển động Brown
1.2.4.3. Thuật toán
Thuật toán Cuckoo Search(CS) [60],[61] được Yang và Deb đưa ra vào năm 2009, đến nay CS đã được nhiều nhà khoa học nghiên cứu và áp dụng cho các bài toán tối ưu khác nhau, trong đó có bài toán MS-RCPSP [CT5]. Thuật
toán này được phát triển dựa trên đặc tính sinh hoạt của loài chim Cuckoo và hành vi bay của một số loài chim và ruồi giấm - gọi là Lévy flight. CS được xây dựng dựa trên ba quy luật như sau:
- Mỗi lần, một con chim Cuckoo chỉ đẻ một quả trứng vào một tổ được chọn ngẫu nhiên;
- Tổ tốt nhất với trứng chất lượng cao nhất sẽ được chuyển qua các thế hệ tiếp theo;
- Số lượng tổ là không đổi và trứng bị chim chủ phát hiện với xác suất pa ∈ [0, 1], khi đó chim chủ có thể vứt bỏ quả trứng hoặc bỏ cả tổ và xây dựng một cái tổ hoàn toàn mới.
CS phù hợp với các bài toán tối ưu tính toán trên dữ liệu lớn bằng cách tạo ra sự cân bằng trong các kỹ thuật tìm kiếm nghiệm toàn cục và tìm kiếm cục bộ nhằm tạo ra các nghiệm tốt hơn ở thế hệ tiếp theo.
CS dạng đơn giản quy định tổ cũng đồng nghĩa với trứng. Mục tiêu của thuật toán là sinh ra những tổ mới có tiềm năng tốt hơn thay thế các tổ (nghiệm) có chất lượng kém. Việc tạo ra tổ mới áp dụng kỹ thuật Lévy Flight với các phép Tìm kiếm toàn cục (Global Search) và Tìm kiếm cục bộ (Local Search). Hai kỹ thuật tìm kiếm trên giúp CS mở rộng được không gian tìm kiếm, thoát khỏi được cực trị địa phương.
Thế hệ tiếp theo tạo ra bằng phép tìm kiếm cục bộ, áp dụng công thức (1.19):
t t t
xit+1 = xi + αs 
H(pa-e) 
(xj - xk ) (1.19)
trong đó:
- xi: lịch biểu (các thể) ở thế hệ thứ i;
- t: vị trí của tác vụ trong một phương án (lịch biểu, cá thể);
t
- j, k: là hai cá thể bất kỳ, khi đó (xjt - xk ) là độ chênh 2 phương án;
- H(x): hàm bước = 0 (khi x<0) hoặc 1 (khi x>0);
- α: là hằng số, nhận giá trị {1, 0.1, 0.01};
- s: stepsize – bước di chuyển ngẫu nhiên [0,1].
Thế hệ tiếp theo tạo ra bằng phép tìm kiếm toàn cục, áp dụng công thức (1.20).
xit+1 = xit + α L(s,λ) (1.20)
với:
𝐿(𝑠, 𝜆) = 𝜆 𝛤(𝜆)𝑠𝑖𝑛(𝜋𝜆/2)
𝜋
1
𝑠1+𝜆
, 𝑠 >> 𝑠0 > 0 (1.21)
trong đó:
- λ: là một hằng số, 0 < λ ≤ 2
- Γ(λ): là hàm trả lại giá trị (λ-1)!
Chi tiết thuật toán CS được trình bày trong Algorithm 1.3.
Algorithm 1.3. Thuật toán CS
Input : dataset
tmax : số thế hệ tiến hóa Output : cá thể tốt nhất và makespan
1. Begin
2. Load and Valid dataset 3. t = 0
4. Pall = {Initial population}
5. f = {Calculate the fitness, makespan, bestnest}
6. while(t
7. Pnew = {Tạo cá thể mới bằng Lévy Flight (1.20)}
8. Pi = {Lấy ngẫu nhiên một cá thể từ Pall }
9. if f(Pnew) < f(Pi) { Pi = Pnew } 10.
11. Ppa = pa% tổ kém nhất từ Pall
12. For j = 1 to size(Ppa)
13. Pnew = {Tạo cá thể mới bằng Lévy Flight (1.19)}
14. if f(Pnew) < f(Pjpa) { Pjpa = Pnew }
15. End For
16. Pall = {Thay thế Ppa vào Pall}
17. f = {Calculate the fitness, bestnest}
18. makespan = f(bestnest)
19. t = t+1
20. End while
Với: - f: hàm tính makespan của một lịch biểu |
Có thể bạn quan tâm!
-
Một Số Ứng Dụng Thực Tế Của Bài Toán Ms-Rcpsp -
Một Số Thuật Toán Metaheuristic Tìm Nghiệm Gần Đúng -
![Rand Là Số Ngẫu Nhiên Trong Đoạn [1,d], Giá Trị I Rand Đảm Bảo Vector X I Luôn Luôn Khác Vector V I .](https://tailieuthamkhao.com/uploads/2022/07/14/mot-so-phuong-phap-gan-dung-giai-bai-toan-lap-lich-voi-tai-nguyen-gioi-6-6-120x90.jpg)
Rand Là Số Ngẫu Nhiên Trong Đoạn [1,d], Giá Trị I Rand Đảm Bảo Vector X I Luôn Luôn Khác Vector V I . -
Một số phương pháp gần đúng giải bài toán lập lịch với tài nguyên giới hạn - 8 -
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán -
Phương Pháp Tái Thiết Lập Tài Nguyên Thực Hiện
Xem toàn bộ 156 trang tài liệu này.
Thuật toán CS thực hiện bằng cách tiến hóa quần thể qua nhiều thế hệ khác nhau. Ở mỗi thế hệ, CS thực hiện tạo một cá thể mới bằng kỹ thuật tìm kiếm toàn cục (Global Search). Sau khi tính toán, tiến hóa, thuật toán sẽ thay thế một số cá thể kém nhất bằng các cá thể mới, các cá thể mới tạo ra bằng kỹ thuật tìm kiếm cục bộ (Local Search). Kết quả của thuật toán là một cá thể (lịch biểu) với thời gian thực hiện tối thiểu.
Kết luận chương 1
Bài toán MS-RCPSP là bài toán thuộc lớp NP-Khó và có nhiều ứng dụng trong thực tế. Tuy nhiên, do không gian lời giải rất lớn, nên khó tìm ra được nghiệm tối ưu. Do vậy, người ta thường dùng các thuật toán tiến hóa để tìm ra các nghiệm tốt, chấp nhận được cho các bộ dữ liệu theo yêu cầu cụ thể.
Chương 1 của luận án đã trình bày phát biểu toán học của bài toán MS- RCPSP, các ứng dụng trong thực tế của bài toán này. Để phục vụ cho việc giải bài toán này trong Chương 2, chương này cũng giới thiệu một số thuật toán metaheuristic hiệu quả, thường được áp dụng để tìm ra nghiệm gần đúng trong thời gian chấp nhận được như PSO, DE, CS.
Kết quả nghiên cứu của chương này được công bố tại:
- Tạp chí HNUE Journal of Science, Vol. 62, No. 3, pp. 88-96, 2017 [CT1];
- Tạp chí Nghiên cứu khoa học và công nghệ quân sự, Tin học, điều khiển và ứng dụng, Viện KHCNQS/11-2018, số đặc san, pp. 63-73, 2018 [CT3];
- Hội thảo Quốc gia: Ứng dụng công nghệ cao vào thực tiễn, 2019 [CT4].
CHƯƠNG 2
GIẢI BÀI TOÁN MS-RCPSP BẰNG PHƯƠNG PHÁP TỐI ƯU BẦY ĐÀN VÀ PHƯƠNG PHÁP TIẾN HÓA VI PHÂN
Bài toán lập lịch thực hiện dự án với tài nguyên giới hạn và đa kỹ năng (MS-RCPSP) [31],[42],[43] có nhiều ứng dụng trong thực tế do bổ sung thêm yếu tố kỹ năng của tài nguyên thực hiện tác vụ. Theo đó, mỗi tài nguyên có thể có nhiều loại kỹ năng, mỗi loại kỹ năng có một mức độ kỹ năng cụ thể. Trong môi trường sản xuất, có thể hiểu kỹ năng chính là chuyên môn của nhân công và chuyên môn sẽ được phân làm các mức độ (tay nghề) khác nhau. Để thực hiện một tác vụ, tài nguyên cần đáp ứng về loại kỹ năng và mức kỹ năng phù hợp với yêu cầu của tác vụ.
Chương 2 nghiên cứu sinh đề xuất một số giải thuật metaheuristic để giải bài toán MS-RCPSP. Các nội dung chính của chương này gồm:
Phần 2.1: Trình bày phương pháp biểu diễn cá thể của bài toán MS-RCPSP.
Phần 2.2: Trình bày thang đo độ chênh giữa các cá thể, phục vụ trong việc tính toán, lai ghép cá thể trong quá trình tiến hóa.
Phần 2.3: Trình bày thuật toán đề xuất M-PSO đề giải bài toán MS-RCPSP. Thuật toán này được xây dựng trên cơ sở của thuật toán tối ưu bầy đàn PSO với việc bổ sung kỹ thuật di cư nhằm thoát khỏi cực trị địa phương và mở rộng khả năng tìm kiếm được các nghiệm tốt hơn.
Phần 2.4: Trình bày thuật toán đề xuất DEM đề giải bài toán MS-RCPSP. Đây là thuật toán được xây dựng trên cơ sở của thuật toán tiến hóa vi phân với cải tiến mới bằng việc bổ sung hàm tái thiết lập tài nguyên thực hiện tác vụ.
Với mỗi thuật toán, tác giả sẽ trình bày các thực nghiệm cụ thể trên bộ dữ liệu iMOPSE - bộ dữ liệu chuẩn cho bài toán MS-RCPSP. Sau đó đưa ra các phân tích, đánh giá cụ thể từ kết quả thực nghiệm.
2.1. Phương pháp biểu diễn cá thể
Trong giải thuật lập lịch, một lịch biểu được thể hiện như một vector có chiều dài bằng số tác vụ cần thực hiện, mỗi phần tử của vector sẽ lưu giá trị là chỉ số của tài nguyên thực hiện tác vụ đó.
Với bài toán MS-RCPSP, một cá thể hay một lịch biểu là một vector có số phần tử bằng số tác vụ của dữ liệu đầu vào, giá trị mỗi phần tử của vector lịch biểu là chỉ số của tài nguyên sử dụng để thực hiện tác vụ đó. Tài nguyên này cần đáp ứng các yêu cầu ràng buộc theo điều kiện của bài toán, tức là có loại kỹ năng giống với kỹ năng yêu cầu và mức kỹ năng (level) phải lớn hơn hoặc bằng mức kỹ năng yêu cầu.
Ví dụ 2.1: Xét một dự án gồm 10 tác vụ, 2 tài nguyên thực hiện.
- Tập hợp tác vụ W={W1, W2, W3, W4, W5, W6, W7, W8, W9, W10}
- Tập hợp tài nguyên L = {L1, L2}.
Đồ thị ưu tiên của các tác vụ thể hiện như trong hình 2.1 dưới đây.
W1
W2
W3
W4
W5
W6
W7
W8
W9
W10
Hình 2.1. Đồ thị ưu tiên các tác vụ trong dự án
Thời gian thực hiện từng tác vụ (tính theo giờ) được thể hiện trong bảng 2.1.
Bảng 2.1: Thời gian thực hiện các tác vụ
W1 | W2 | W3 | W4 | W5 | W6 | W7 | W8 | W9 | W10 | |
Thời gian | 2 | 4 | 3 | 5 | 2 | 2 | 5 | 3 | 4 | 2 |
Hình 2.2 biểu diễn việc bố trí tài nguyên thực hiện các dự án theo thời gian.
Việc bố trí tài nguyên thực hiện tác vụ cần đáp ứng được thứ tự ưu tiên của bài toán cũng như đáp ứng yêu cầu về kỹ năng, mức kỹ năng của tài nguyên.
L1
L2
3
W2
4
W5
W3
W8
W9
0 1 2
5
6
7
8
9 10
11 12 13 14 15 16
17 time
W1
W4
W6
W10
W7
Hình 2.2. Tài nguyên thực hiện tác vụ theo thời gian
Với phương án lịch biểu được thể hiện trong hình 2.2, ta có thể biểu diễn lịch biểu này dưới dạng một vector như sau:
W1 | W2 | W3 | W4 | W5 | W6 | W7 | W8 | W9 | W10 | |
Tài nguyên | 1 | 2 | 2 | 1 | 1 | 1 | 1 | 2 | 2 | 1 |
Như vậy, tài nguyên L1 sẽ thực hiện các tác vụ: W1, W4, W5, W6, W7, W10; tài nguyên L2 thực hiện các tác vụ: W2, W3, W8, W9.
2.2. Thang đo độ chênh của cá thể
Với bài toán MS-RCPSP, một tác vụ có thể được thực hiện bởi nhiều tài nguyên khác nhau. Để phục vụ cho việc tính toán và hiệu chỉnh cá thể, chúng ta định nghĩa một thang đo cas the như sau.
Các ký hiệu sử dụng trong thang đo độ chênh:
• p: thang đo độ chênh, pi: vector thang độ chênh của tác vụ i. pi,j: giá trị của phần tử thứ j trên thang đo của tác vụ i;
• pS: thang đo của cá thể S;
• Si: chỉ số tài nguyên thực hiện tác vụ i trong cá thể S;
• ∆: khoảng cách giữa các phần tử trong thang đo, mỗi phần tử trong thang đo thể hiện chỉ số của một tài nguyên thực hiện tác vụ ∆i: khoảng cách giữa các tài nguyên trong thang đo của tác vụ i;
• d: vector độ chênh giữa 02 cá thể, có số phần tử bằng số tác vụ của cá thể.
Định nghĩa 2.1:thang đo cho một tác vụ là một vector thể hiện chỉ số của