Ý Tưởng Của Phương Pháp Thích Nghi

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.

Algorithm 4.1. StarAdaptive

Input: Pall: quần thể

i: vị trí của cá thể hiện tại w: số cá thể lân cận

Output: Pibest: cá thể tốt nhất trong

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.

Algorithm 4.2. A-DEM

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(tmax) 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.