Đánh Giá Chất Lượng Lời Giải Của Thuật Toán

bước di chuyển lớn của cá thể. Tuy nhiên, vấn đề này sẽ ít gặp phải trong bài toán với số lượng tài nguyên thực hiện lớn hơn.

2.3.1.2. Hàm Migration

Algorithm 2.2. Migration

Input: Pall – quần thể hiện tại Output: Pnew – quần thể sau khi di chuyển Begin 1. Pnew = {}

2. For i=1 to size(P) // duyệt lần lượt từng cá thể 3. Pi = Pall[i]; // lấy cá thể thứ i từ quần thể 4. For j = 1 to y // duyệt lần lượt từng task 5. Wi = Danh sách tài nguyên thực hiện Wi 6. Wi = Sort(Wi) // sắp xếp chỉ số tài nguyên trong Wi 7. idx = Chỉ số tài nguyên thực hiện task i 8. idx = size(Wi) – idx + 1 9. Li = Wi[idx] 10. End for // j 11. Pnew = Pnew + {Pi} 12. End for // i 13. Return Pnew; End Function

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

• 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 - 7
• 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
• Phương Pháp Tái Thiết Lập Tài Nguyên Thực Hiện
• Đá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

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

2.3.2. Thuật toán M-PSO

M-PSO được trình bày trong Algorithm 2.3 với đầu vào của thuật toán là số thế hệ thực hiện để tìm phương án tốt nhất (tmax) và ngưỡng phát hiện cực trị địa phương (nmax). Các bước chạy chi tiết như sau:

Algorithm 2.3. M-PSO

Input: nmax: ngưỡng áp áp dụng migration, 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 nfail = 0

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

7 for i=1 to size(Pall) do

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

9 end for

10 for i = 1 to size(Pall) do

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

12 pbesti = Pi

13 f(pbesti) = f(Pi)

14 end if

15 end for

16 for i=1 to size(Pall) do

17 if(f(Pi) < f(gbest)) then

18 gbest = Pi

19 f(gbest) = f(Pi)

20 end if

21 if f(Pi)!= f(Pi-1) then

22 nfail = 0

23 else

24 nfail += 1

25 end if

26 end for

27 for i=1 to size(Pall) do

28 cập nhật vector dịch chuyển theo (1.1.a)

29 Cập nhật vector vị trí theo (1.1.b)

30 end for

31 if (nfail = nmax)

32 Pall = Migration(Pall)

33 nfail = 0

34 end if

35 end while

36 return gbest

37 end

f: objective function

Các dòng 21 đến 25 thể hiện biến đếm để phát hiện cực trị địa phương.

Các dòng 31 đến 34 xử lý việc áp dụng kỹ thuật di cư quần thể khi đã phát hiện ra cực trị địa phương.

2.3.3. Thực nghiệm

2.3.3.1. Dữ liệu thực nghiệm

Để đánh giá, thuật toán đã được cài đặt, chạy thử nghiệm với bộ dữ liệu iMOPSE [42],[45], đây là bộ dữ liệu chuẩn đã được chứng minh phù hợp với bài toán MS-RCPSP và đã có nhiều nhóm nghiên cứu sử dụng.

Bộ dữ liệu được lưu trữ dưới dạng file def, mỗi file bao gồm các thông tin:

 Số tác vụ (Task) cần thực hiện;

 Số tài nguyên (Resource) sử dụng để thực hiện các tác vụ;

 Số lương ràng buộc giữa các tác vụ (Precedence Relation), chỉ ra thứ tự ưu tiên trong việc thực hiện các tác vụ;

 Số lượng kỹ năng của các tài nguyên (Skill);

 Kỹ năng và mức kỹ năng của mỗi tài nguyên, một tài nguyên có thể bao gồm nhiều kỹ năng.

Chi tiết bộ dữ liệu iMOPSE được trình bày trong bảng 2.11 dưới đây.

Bảng 2.11: Bộ dữ liệu iMOPSE cho bài toán MS-RCPSP

Dataset instance

Tasks	Resources	Precedence Relations	Skills
100_5_20_15	100	5	22	15
100_5_48_9	100	5	48	9
100_5_48_15	100	5	46	15

Dataset instance

Tasks	Resources	Precedence Relations	Skills
100_5_64_9	100	5	64	9
100_5_64_15	100	5	64	15
100_10_26_15	100	10	26	15
100_10_47_9	100	10	47	9
100_10_48_15	100	10	48	15
100_10_64_9	100	10	64	9
100_10_65_15	100	10	65	15
100_20_22_15	100	20	22	15
100_20_47_9	100	20	47	9
100_20_46_15	100	20	46	15
100_20_65_9	100	20	65	9
100_20_65_15	100	20	65	15
200_10_50_9	200	10	50	9
200_10_50_15	200	10	50	15
200_10_84_9	200	10	84	9
200_10_85_15	200	10	85	15
200_10_128_15	200	10	128	15
200_40_144_15	200	40	133	15
200_20_55_9	200	20	55	9
200_20_54_15	200	20	54	15
200_20_97_9	200	20	97	9
200_20_97_15	200	20	97	15
200_20_145_15	200	20	145	15
200_40_45_9	200	40	45	9
200_40_45_15	200	40	45	15
200_40_90_9	200	40	90	9
200_40_91_9	200	40	91	15

2.3.3.2. Cấu hình thực nghiệm

Các tham số thực nghiệm:

- Dữ liệu: 30 file dữ liệu trong bộ dữ liệu iMOPSE như trong bảng 2.11;

- Khởi tạo quần thể ban đầu với 100 cá thể;

- Số thế hệ tiến hóa: 100.000;

- Số lần chạy thực nghiệm trên mỗi bộ dữ liệu: 50;

- Hệ số phát hiện cực trị địa phương nmax: 30. Môi trường thực nghiệm:

- Thực nghiệm được tiến hành trên môi trường Matlab 2014

- Máy tính thực nghiệm: CPU Intel Core i5, tốc độ 2.2 GHz, RAM 6GB, hệ điều hành Windows 10 (64 bit).

2.3.3.3. Kết quả thực nghiệm

Kết quả thực nghiệm được thể hiện trong bảng 2.12 dưới đây. Kết quả thực nghiệm của M-PSO được so sánh với:

- Thuật toán GA-M: là thuật toán di truyền cải tiến của nhóm Myszkowski, thuật toán này được nhóm tác giả công bố cùng với bộ công cụ GA Runner để chạy và kiểm chứng kết quả, nên kết quả của GA-M là khách quan và tin cậy [42],[45].

- Một số thuật toán lai (hybrid) như: HAntCO, GRASP[44]. Đây là các thuật toán tiến hóa được lai ghép tính ưu việt của hai hoặc nhiều thuật toán hoặc kỹ thuật khác nhau.

Bảng 2.12: Kết quả thực nghiệm M-PSO

TT

Dataeset	GA-M			HAntCO			GRASP			M-PSO
	Best	Avg	Std	Best	Avg	Std	Best	Avg	Std	Best	Avg	Std
1	100_5_22_15	517	524	5.3	504	505	0.8	503	504	0.5	485	486	1.7
2	100_5_46_15	584	587	4.7	604	604	0	552	556	2.6	530	531	0.5
3	100_5_48_9	528	535	9.7	521	523	1.6	510	510	0.8	490	492	1.6
4	100_5_64_15	527	530	2.5	516	523	2.9	501	502	0.8	478	479	1.3
5	100_5_64_9	508	521	9.9	507	515	3.9	494	494	0.6	471	474	2.5
6	100_10_26_15	292	292	0.0	266	270	2.2	251	258	3.2	233	233	0.4
7	100_10_47_9	296	296	0.0	297	302	4	263	264	0.7	257	261	3.7
8	100_10_48_15	279	282	2.9	278	286	4.4	256	257	1.2	244	245	0.6
9	100_10_64_9	296	305	6.6	287	296	5.1	255	257	1.9	240	246	5.9
10	100_10_65_15	286	290	5.0	281	287	3.5	256	260	1.9	244	245	1.3
11	100_20_22_15	163	169	5.8	161	170	3.6	134	137	1.6	128	131	3.1
12	100_20_46_15	197	207	6.9	194	199	2.6	170	174	3.1	162	165	2.9
13	100_20_47_9	185	186	0.5	180	187	3.7	133	140	2.2	124	128	3.6
14	100_20_65_15	240	240	0.5	218	220	2.7	213	213	0	228	230	1.8
15	100_20_65_9	181	187	4.5	180	185	3.1	135	135	1.4	125	125	0.3
16	200_10_128_15	577	583	4.9	522	528	3.1	491	496	4.2	461	464	2.7

TT

Dataeset	GA-M			HAntCO			GRASP			M-PSO
	Best	Avg	Std	Best	Avg	Std	Best	Avg	Std	Best	Avg	Std
17	200_10_50_15	553	577	17.5	529	543	8	524	528	3.8	489	490	0.7
18	200_10_50_9	585	589	5.0	546	556	4.8	506	508	1.4	487	491	3.7
19	200_10_84_9	567	583	11.4	571	581	6.9	526	527	0.8	508	510	2.1
20	200_10_85_15	549	555	4.9	526	538	6.5	496	498	1.1	473	476	2.5
21	200_20_145_15	326	328	2.0	309	314	4.4	262	271	4.2	236	237	1.4
22	200_20_54_15	363	385	20.8	336	349	6.6	304	308	3.7	256	256	0.3
23	200_20_55_9	312	318	4.2	313	317	3.1	257	258	0.6	251	255	3.5
24	200_20_97_15	424	438	9.7	356	368	4.8	347	347	0	334	337	3.3
25	200_20_97_9	321	326	6.2	326	332	4.1	253	256	1.6	255	256	0.9
26	200_40_133_15	215	222	6.2	214	221	3.4	163	170	4.1	147	151	4.1
27	200_40_45_15	201	210	6.3	206	212	2.6	164	164	0	163	167	4
28	200_40_45_9	209	213	2.9	209	215	3.8	144	147	1.6	152	162	9.5
29	200_40_90_9	211	215	3.1	211	214	1.8	148	153	4.5	145	152	7.1
30	200_40_91_15	200	205	3.4	207	212	2.9	153	159	2.6	135	143	8.3

Bảng 2.13: So sánh kết quả thực nghiệm M-PSO với các thuật toán khác

Thuật toán

BEST			AVG			Tổng STD
Số lượng	Tỉ lệ (%)		Số lượng	Tỉ lệ (%)
	Từ	Đến		Từ	Đến
M-PSO							85.3
GA-M	30/30	5.0	32.97	30/30	4.3	33.56	173.3
HAntCO	29/30	-4.59	34.78	29/30	-4.55	32.55	110.9
GRASP	27/30	-7.04	15.79	26/30	-10.2	16.88	56.7

Trong bảng 2.13:

- Cột “Số lượng” thể hiện số bộ dữ liệu (trên tổng số 30 bộ) mà thuật toán M-PSO có kết quả tốt hơn thuật toán ở hàng tương ứng.

- Tỉ lệ (%) cho biết kết quả của M-PSO tốt hơn/kém hơn kết quả của các thuật toán. Giá trị âm thể hiện một vài trường hợp mà M-PSO cho kết quả kém hơn.

2.3.4. Đánh giá chất lượng lời giải của thuật toán

Luận án đã tiến hành thực nghiệm thuật toán M-PSO áp dụng cho bài toán MS-RCPSP. Thực nghiệm được chạy trên 30 bộ dữ liệu iMOPSE, với số lần chạy thực nghiệm là 50 lần, số thế hệ tiến hóa là 100.000, thuật toán được cài đặt trên môi trường thử nghiệm Matlab 2014. Kết quả thực nghiệm được trình bày trong bảng 2.12. Kết quả thực nghiệm được tổng hợp và so sánh trong bảng 2.13.

So sánh với GA-M cải tiến của nhóm Myszkowski, ta thấy:

- Về giá trị BEST và AVG: M-PSO tốt hơn GA-M trong tất cả các trường hợp, trong đó giá trị BEST tốt hơn GA-M từ 5.0% đến 32.97%, giá trị AVG tốt hơn GA-M từ 4.3% đến 33.56%.

- Về giá trị độ lệch chuẩn STD, tổng độ lệch chuẩn của GA-M là 173,3,

Xem tất cả 156 trang.