Ví dụ 4.2:
Xem xét quần thể gồm 10 cá thể, với thời gian thực hiện của từng cá thể được thể hiện trong hình 4.3.a.
Mục tiêu: tìm 03 các thể khác là lân cận với cá thể thứ 5 theo cấu trúc hình sao. Ta thực hiện qua các bước sau:
Bước 1: sắp xếp quần thể theo thứ tự tăng dần của thời gian thực hiện, ta có kết quả như trong hình 4.3.b.
Bước 2: duyệt danh sách Pall đã sắp xếp để tính khoảng cách với với cá thể
P5, ta có d5 = 13.
Bước 3: duyệt Pall để lấy 3 cá thể lân cận với P5. Các cá thể lân cận lấy được gồm: P5S = {P2, P4, P6}.
Pall | Thời gian |
P1 | 123 |
P2 | 130 |
P3 | 175 |
P4 | 127 |
P5 | 137 |
P6 | 150 |
P7 | 201 |
P8 | 185 |
P9 | 162 |
P10 | 173 |
Có thể bạn quan tâm!
-
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán -
Xếp Loại Bài Toán Real-Rcpsp Thông Qua Phân Loại Graham -
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 - 13 -
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán -
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán -
Đánh Giá Chất Lượng Lời Giải Của Thuật Toán
Xem toàn bộ 156 trang tài liệu này.
Pall sorted | Thời gian | d5 |
P1 | 123 | 14 |
P4 | 127 | 10 |
P2 | 130 | 7 |
P5 | 137 | 0 |
P6 | 150 | 13 |
P9 | 162 | 25 |
P10 | 173 | 36 |
P3 | 175 | 38 |
P8 | 185 | 48 |
P7 | 201 | 64 |
(a) Quần thể ban đầu (b) Quần thể sau khi sắp xếp
Hình 4.3. Tìm các cá thể lân cận
4.2.1.2. Ý tưởng của phương pháp thích nghi
Mục tiêu của phương pháp thích nghi (Adaptive) là điều chỉnh hệ số lai ghép µCR qua mỗi thế hệ nhằm tăng hiệu quả của thuật toán, việc điều chỉnh
phụ thuộc vào kết quả thực hiện tiến hóa của quần thể. Để ứng dụng tốt trong bài toán Real-RCPSP, kỹ thuật thích nghi kết hợp với cấu trúc hình sao được sử dụng để tìm kiếm các lân cận. Các bước cụ thể như sau:
- Hệ số lai ghép của cá thể thứ i, ký hiệu là CRi được tính hàm ngẫu nhiên Cauchy của tham số lai ghép µCR, trong đo µCR được tính dựa trên số lượng cá thể đột biến thành công trong thế hệ trước đó.
- Khi thực hiện thuật toán DE, tại thời điểm xem xét đột biến cá thể, thay vì lựa chọn ngẫu nhiên 03 cá thể từ quần thể ban đầu, chúng ta sẽ sử dụng một cá thể là localbest được tính toán dựa trên kiến trúc hình sao.
- Số lượng cá thể lân cận trong kiến trúc hình sao được thay đổi theo mỗi thế hệ.
Ví dụ 4.3:
Xem xét ví dụ 4.2, tìm cá thể tốt nhất theo cấu trúc hình sao của cá thể thứ 5, biết rằng tại thời điểm thực hiện, số lượng cá thể lân cận để tìm cá thể tốt nhất là w = 4.
Sau bước 3 của ví dụ 4.2, ta có P5S = {P5, P2, P4, P6}.
Duyệt P5S để tìm ra cá thể tốt nhất, tức là cá thể có thời gian thực hiện tối thiểu. Căn cứ vào kết quả trong hình 4.3.b, ta dễ dàng tìm được cá thể tốt nhất là P4 với thời gian thực hiện là 127.
Với ý tưởng điều chỉnh trong quá trình tiến hóa, khi áp dụng phương pháp thích nghi vào thuật toán DE, sẽ mang lại các thay đổi như sau:
- Hệ số lai ghép thay đổi (thích nghi) theo kết quả thực hiện qua từng thế hệ giúp việc tính toán linh động hơn, đa dạng hơn về cách lai ghép, đột biến, lựa chọn.
- Sử dụng một cá thể localbest sẽ giúp việc đột biến thực hiện tốt hơn do tận dụng được kinh nghiệm của cá thể tốt trước đó, điều này giúp thuật toán
nhanh hội tụ
- Sử dụng cấu trúc hình sao, giúp mở rộng không gian tìm kiếm, sẽ hạn chế việc rơi vào cực trị địa phương.
Phương pháp thích nghi này được thể hiện thành hàm StarAdaptive dưới đây.
4.2.1.3. Hàm StarAdaptive
Các bước thực hiện tìm kiếm cá thể lân cận tốt nhất, được chi tiết trong Algorithm 4.1 StarAdaptive dưới đây. Đầu vào gồm: quần thể ban đầu, vị trí của cá thể hiện tại và số cá thể lân cận để duyệt tìm cá thể tốt nhất.
Begin 1. PR = {} 2. fitness ← f(Pall) // tính thời gian thực hiện của các cá thể 3. mp = fitness(i) 4. Psortall ← sort(Pall, fitness) // sắp xếp quần thể theo fitness 5. Di = findDistance(i) 6. For j=1 to size(Pall) // duyệt lần lượt từng cá thể 7. If abs( fitness(j) – mp) ≤ Di 8. PS= PS + {Pj} 9. End if 10. End for 11. Pibest = fbest(PS) 12. Return Pibest End Function |
Trong đó: findDistance: hàm tìm khoảng cách tối đa tính từ vị trí i để có thể lấy đủ số cá thể lân cận với Pi |
Hàm StarAdaptive sẽ được dùng trong thuật toán A-DEM để tìm kiếm cá thể tốt nhất trong các cá thể lân cận với cá thể hiện tại.
4.2.2. Thuật toán A-DEM
Thuật toán A-DEM sử dụng kỹ thuật thích nghi trên cơ sở thay đổi hệ số lai ghép và tìm cá thể tốt nhất dựa trên kiến trúc Star được thực hiện qua các bước như sau:
- Bước 1: Khởi tạo quần thể với N cá thể: Pall
- Bước 2: Khởi tạo các giá trị ban đầu
- Bước 3: Thực hiện các tiến hóa qua các thế hệ
- Bước 4: Với mỗi thế hệ, duyệt từng cá thể Pi và thực hiện
- Bước 4.1: Tính toán Pibest theo kiến trúc Star
- Bước 4.2: Tính toán hệ số lai ghép CR dựa trên tham số lai ghép µCR
- Bước 4.3: Lấy ngẫu nhiên 02 cá thể P1, P2 từ quần thể (khác với cá thể hiện tại)
- Bước 4.4: Tạo ra cá thể vi bằng phép đột biến theo công thức:
Vi Pi + F (Pbest – Pi) + F (P1 - P2)
- Bước 4.5: Tạo ra cá thể mới Ui theo công thức
𝑈𝑖,𝑗
𝑉𝑖,𝑗 𝑛ế𝑢 rand(0,1) ≤ 𝐶𝑅𝑖 ℎ𝑜ặ𝑐 𝑖 = 𝐼𝑟𝑎𝑛𝑑
= {𝑃𝑖,𝑗 𝑛ế𝑢 rand(0,1) > 𝐶𝑅𝑖 ℎ𝑜ặ𝑐 𝑖 ≠ 𝐼𝑟𝑎𝑛𝑑
j ∈ (1,taskcount)
- Bước 4.6: Thay thế Pi theo công thức
𝑖
𝑃 = {𝑈𝑖 𝑛ế𝑢 f(Ui) < 𝑓(𝑃𝑖)
𝑃𝑖 ngược lại
- Bước 4.7: Ghi nhận hệ số đột biến thành công vào tập SCR
- Bước 5: Tính toán lại tham số lai ghép µCR theo công thức
µCR = (1 - c) × µCR + c × mean(SCR)
- Bước 6: Hiệu chỉnh lại số cá thể lân cận theo công thức
w = wmax – i/N × (wmax – wmin)
- Bước 7: Tìm Pbest
Cải tiến chính của thuật toán A-DEM nằm trong các bước: 4.1, 4.2, 4.4, 4.7, 5,
6.
A-DEM được trình bày trong Algorithm 4.2 dưới đây.
Input: tmax: số thế hệ, dataset, N số cá thể ban đầu Output phương án tốt nhất Pbest và makespan |
1 Begin 2 t = 0 3 Load and valid Dataset 4 Pall initialize(N) // khởi tạo quần thể gồm N cá thể 5 {Pbest, makespan} fbest(Pall) // tìm cá thể tốt nhất 6 µCR = 0.5; wmin = 4; wmax = 10; w = 3 7 while(t 8 for (int i = 0; i< N; i++) 9 Pibest = StarAdaptive(Pall,i, w) 10 CRi = randci (µCR, 0.1) 11 Pi P1 P2 Random from Pall 12 Vi Pi + F (Pbest – Pi) + F (P1 - P2) 13 Irand = randi(1,N) 14 for(j=0; j 15 randi,j = rand(0,1) 𝑈𝑖,𝑗 𝑛ế𝑢 randi,j ≤ 𝐶𝑅𝑖 ℎ𝑜ặ𝑐 𝑖 = 𝐼𝑟𝑎𝑛𝑑 16 𝑈𝑖,𝑗 = {𝑃𝑖,𝑗 𝑛ế𝑢 randi,j > 𝐶𝑅𝑖 ℎ𝑜ặ𝑐 𝑖 ≠ 𝐼𝑟𝑎𝑛𝑑 17 end for 18 if(f(Ui) f(Pi)) 19 Pi = Ui 20 SCR = SCR + {µCR} 21 end if 22 end for // end duyệt quần thể 23 c = rand(0,1) 24 µCR = (1 - c) × µCR + c × mean(SCR) //Adaptive factor 25 w = wmax – i/N × (wmax – wmin) 26 t t+1 27 {Pbest, makespan} fbest(Pbest) 28 end while 29 return {Pbest, makespan} 30 end |
Trong đó: f: hàm mục tiêu |
fbest: hàm trả lại cá thể tốt nhất F: bước nhảy
µCR: tham số lai ghép w: số cá thể lân cận
randci: hàm phân phối Cauchy mean: hàm tính giá trị trung bình
4.2.3. Thực nghiệm
4.2.3.1. Dữ liệu thực nghiệm
Để kiểm chứng khả năng ứng dụng vào thực tế của thuật toán đề xuất cho bài toán Real-RCPSP, ngoài bộ dữ liệu iMOPSE [42][45], luận án còn sử dụng bộ dữ liệu TNG được số hóa từ dữ liệu dây chuyền sản xuất may công nghiệp.
a) Chỉnh sửa bộ dữ liệu iMOPSE cho phù hợp với bài toán Real-RCPSP
Bộ dữ liệu iMOPSE chuẩn không phù hợp để kiểm chứng các thuật toán cho bài toán Real-RCPSP vì mỗi tác vụ có thời gian thực hiện như nhau với bất kỳ tài nguyên thực hiện nào, không phân biệt mức kỹ năng. Vì thế luận án đã tiến hành điều chỉnh lại bộ iMOPSE, những số liệu chi tiết của việc điều chỉnh này theo 3 mức dựa trên mức kỹ năng (bậc thợ), cụ thể như sau:
Mức 1: với tài nguyên có mức kỹ năng bằng hoặc cao yêu cầu 1 bậc, thời gian thực hiện không thay đổi.
Mức 2: với tài nguyên có mức kỹ cao hơn yêu cầu từ 2 đến 3 bậc, thời gian thực hiện tác vụ được điều chỉnh giảm xuống 5% so với thời gian chuẩn.
Mức 3: với tài nguyên có mức kỹ cao hơn yêu cầu từ 4 đến 7 bậc, thời gian thực hiện tác vụ được điều chỉnh giảm xuống 7% so với thời gian chuẩn.
Việc điều chỉnh giảm thời gian thực hiện được đề xuất căn cứ trên dữ liệu thực tế của chuyền may công nghiệp được trình bày dưới đây.
Ví dụ 4.4:
Một tác vụ có thời gian thực hiện trong bộ dữ liệu iMOPSE là 200 giờ, sẽ được điều chỉnh như sau:
Mức 1: với tài nguyên có mức kỹ năng bằng hoặc cao hơn so với yêu cầu 1 bậc, thời gian thực hiện của tác vụ này không thay đổi, là: 200 giờ
Mức 2: với tài nguyên có mức kỹ năng cao hơn yêu cầu từ 2 đến 3 bậc, thời gian thực hiện tác vụ được điều chỉnh giảm xuống 5%, còn: 190 giờ.
Mức 3: với tài nguyên có mức kỹ năng cao hơn yêu cầu từ 4 đến 7 bậc, thời gian thực hiện tác vụ được điều chỉnh giảm xuống 7%, còn: 186 giờ.
b) Phương pháp số hóa dữ liệu chuyền may công nghiệp
Trong lĩnh vực sản xuất may công nghiệp, để hoàn thành một hợp đồng với nhiều sản phẩm cùng loại, công ty may sẽ tổ chức các chuyền may để thực hiện những công đoạn của sản phẩm. Mỗi chuyền may có nhiều công nhân với các mức tay nghề khác nhau; các công đoạn may trong một chuyền may được bố trí theo thứ tự ưu tiên của quy trình sản xuất thành phẩm. Dữ liệu chuyền may gồm các đặc trưng sau:
- Để hoàn thành một sản phẩm, cần thực hiện qua nhiều công đoạn.
- Các công đoạn có thời gian thực hiện khác nhau và có yêu cầu công nhân thực hiện cần có trình độ (bậc thợ) nhất định để thực hiện.
- Công nhân bậc cao có thể thực hiện được các công đoạn yêu cầu bậc thợ thấp hơn.
- Công nhân có trình độ cao hơn trình độ yêu cầu, có thể hoàn thành công việc sớm hơn.
- Các công đoạn có quan hệ ưu tiên chặt chẽ với nhau, không hoàn thành công đoạn trước sẽ không thực hiện được công đoạn sau, do vậy số lượng ràng buộc ưu tiên là rất nhiều.
- Các công nhân thực hiện trong một hợp đồng được tổ chức thành một tổ may
Các đặc trưng của dữ liệu chuyền may công nghiệp rất phù hợp với dữ liệu đầu vào của bài toán Real-RCPSP. Tuy nhiên, để có thể áp dụng dữ liệu chuyền may, ta cần chuyển đổi các thông tin này về định dạng mà Real-RCPSP có thể đọc và sử dụng được. Để số hóa dữ liệu chuyền may, ta thực hiện các quy tắc như sau:
- Mỗi hợp đồng may mặc là một dự án và có thể tạo thành nhiều file dữ liệu dựa vào cách bố trí tài nguyên thực hiện.
- Mỗi công đoạn trong chuyền may là một tác vụ
- Thời gian thực hiện một công đoạn là thời gian thực hiện một tác vụ
- Công nhân may có nhiều mức tay nghề hay bậc thợ khác nhau (từ 1 đến 7), bậc thợ sẽ tương ứng với mức kỹ năng trong mô hình bài toán MS-RCPSP.
- Mỗi công nhân là một tài nguyên, tài nguyên sẽ có mức kỹ năng (skill level) cụ thể
- Thứ tự thực hiện các công đoạn may thành phẩm chính là thứ tự ưu tiên thực hiện các tác vụ.
Kết quả của việc số hóa dữ liệu chuyền may công nghiệp sẽ đưa ra các bộ dữ liệu phù hợp với yêu cầu đầu vào của bài toán Real-RCPSP.
c) Bộ dữ liệu chuyền may TNG
Để phục vụ cho thực nghiệm các thuật toán, dữ liệu chuyền may công nghiệp của công ty TNG [54] được nghiên cứu và số hóa thành bộ dữ liệu chuẩn phù hợp với bài toán Real-RCPSP. Việc số hóa được thực hiện với hai hợp đồng may mặc như trong bảng 4.5.
Các hợp đồng này có thể bố trí thực hiện bởi 04 tổ may với số lượng công nhân tương ứng của mỗi tổ là 37,39,47,41.
Áp dụng quy tắc số hóa dữ liệu chuyền may với dữ liệu hợp đồng trong bảng 4.5, ta được bảng dữ liệu chuẩn, phù hợp với đầu vào của bài toán Real- RCPSP như trong bảng 4.6 dưới đây.