Trang chủ

Đá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!

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

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 - 9

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 trang tiếp theo?
⇦ Trang trước - Trang tiếp theo ⇨

Ngày đăng: 14/07/2022