Tóm tắt Luận án Các phương pháp gần đúng dựa trên tối ưu bày đàn và tiến hóa vi phân giải bài toán lập lịch luồng công việc trong môi trường điện toán đám mây

ng tiếp cận metaheuristic bao gồm Tối ưu bày đàn, và Tiến hóa vi phân. Về thực tiễn, kết quả nghiên cứu của luận án là cơ sở khoa học để thực thi các thuật toán lập lịch luồng công việc trong môi trường điện toán đám 4 mây phù hợp cho từng loại đồ thị luồng công việc và các tham số của môi trường như tốc độ tính toán các máy chủ, băng thông giữa các máy chủ. Chương 1: Giới thiệu bài toán và các nghiên cứu liên quan Chương này trình bày mô hình bài toán lập lịch luồng công việc trong môi trường điện toán đám mây, phân lớp các phương pháp giải bài toán lập lịch và chứng minh bài toán đề xuất CLOS thuộc lớp NP-Khó. Mô hình bài toán lập lịch luồng công việc trong môi trường điện toán đám mây Hệ thống tính toán Giả thiết cho trước hệ thống tính toán bao gồm: • Tập hợp N máy chủ trong môi trường điện toán đám mây S = {S1, S2, ... SN}. • Luồng công việc cần thực hiện biểu diễn bởi đồ thị có hướng, không có chu trình G=(V,E), mỗi đỉnh biểu thị một tác vụ, mỗi cạnh biểu diễn mối quan hệ cha-con giữa một cặp tác vụ. • Tập các tác vụ T={T1, T2, ... TM} với M là số lượng tác vụ. • Khối lượng tính toán của tác vụ Ti ký hiệu là Wi , đo bằng đơn vị flop (floating point operations: phép tính trên số thực dấu phảy động). • Tốc độ tính toán của máy tính, đo bằng đơn vị flop/s (số phép tính thực hiện được trên giây), ký hiệu P(), là hàm số được định nghĩa như sau: P: S R+ Si  P(Si) • Mọi cặp máy chủ (Si, Sk) bất kỳ đều có đường truyền để trao đổi dữ liệu với nhau (1≤i, k≤N). 5 • Băng thông của đường truyền, ký hiệu B(), là tốc độ truyền dữ liệu giữa các máy chủ, đo bằng đơn vị bit trên giây (bps), là hàm số được định nghĩa như sau: B: SS  R+ (Si, Sk)  B(Si, Sk) • Hàm băng thông B() tuân theo các ràng buộc sau: - B(Si,Si) =: thời gian truyền từ một máy chủ tới chính nó bằng 0, nghĩa là nếu tác vụ cha và tác vụ con được bố trí trên cùng một máy chủ thì không mất thời gian để truyền dữ liệu giữa chúng vì dữ liệu đó được lưu trữ và sử dụng ngay tại chỗ. - B(Si,Sk ) = B(Sk,Si): kênh truyền hoạt động từ hai đầu với tốc độ tương đương nhau. Khối lượng dữ liệu cần truyền giữa hai tác vụ Ti và Tk, ký hiệu là Dik, là các giá trị cho trước, Dik  0 khi và chỉ khi Ti là tác vụ cha của Tk, ngược lại Dik =0. Khái niệm lịch biểu Một phương án xếp lịch F, còn gọi là lịch biểu F, được xác định bởi hai hàm (ts , proc) trong đó • ts: T  R+; ts(Ti) là thời điểm mà tác vụ Ti T bắt đầu được thực hiện • proc: T  S; proc(Ti) là máy tính được phân công thực hiện tác vụ Ti T Từ các giả thiết trên suy ra: Thời gian tính toán của tác vụ Ti:    Mi TprocP W i i ,..,2,1;  Thời gian truyền dữ liệu giữa tác vụ Ti và tác vụ Tk là:      Mki TprocTprocB D ki ik ,..,2,1,; ,  Makespan của lịch biểu F được biểu diễn theo công thức sau: 6 )}(min{)}(max{)( is TT if TT TtTtFmakespan ii   với tf(Ti) là thời điểm kết thúc và ts(Ti) là thời điểm bắt đầu thực hiện của tác vụ Ti Mục tiêu của bài toán Mục tiêu của bài toán là tìm lịch biểu F sao cho min)( Fmakespan Xếp loại bài toán CLOS thông qua phân loại Graham • Bài toán CLOS có thể được biểu diễn theo ký pháp Graham như sau: Q|outtree, cij |Cmax Độ phức tạp của bài toán CLOS Dựa theo bài toán SCHED đã được O. Sinnen chứng minh thuộc lớp NP-khó, tác giả đã chứng minh bài toán CLOS cũng thuộc lớp NP-khó bằng cách qui dẫn bài toán SCHED về bài toán CLOS. Các nghiên cứu liên quan Phân loại các phương pháp giải bài toán lập lịch Hình 1.12: Phân loại các phương pháp lập lịch Phân loại các phương pháp giải bài toán lập lịch Cấu trúc Cơ chế Tập trung Phân tán Phân bậc Tĩnh Động Căn cứ ra quyết định Cục bộ Toàn cục 7 Hình 1.13: Phân lớp các giải thuật lập lịch tĩnh Các phương pháp giải bài toán lập lịch Các thuật toán Heuristic giải bài toán lập lịch Có nhiều thuật toán Heuristic giải bài toán lập lịch, điển hình trong họ này là các thuật toán Myopic, Min-min, Max-min, HEFT, TANH, Random, RRTSM. Các thuật toán Metaheuristic giải bài toán lập lịch Đã có nhiều công trình nghiên cứu giải bài toán lập lịch dựa trên cách tiếp cận metaheuristic như thuật toán EGA, GATSM, GAPSO, PSO_H, MPSO, So sánh các thuật toán Các thuật toán heuristic và metaheuristic thường cho chất lượng lời giải chấp nhận được trong thời gian đa thức, tuy nhiên các thuật toán heuristic thường hoạt động dựa vào các tính chất của từng tác vụ rời rạc trong qua trình xếp lịch do vậy chỉ hiệu quả trong một số luồng công việc Thuật toán di truyền Thuật toán đàn kiến Phương pháp tối ưu bày đàn Thuật toán luyện thép Phương pháp tiến hóa vi phân Lập lịch dựa trên quyền ưu tiên các tác vụ Lập lịch dựa trên phân cụm Lập lịch dựa trên bản sao các tác vụ Các giải thuật lập lịch tĩnh Các giải thuật dựa trên heuristics Các giải thuật dựa trên Metaheuristics 8 cụ thể như luồng công việc có cấu trúc đơn giản dạng tiến trình, đường ống (pipeline), và dữ liệu truyền qua lại giữa các tác vụ là nhỏ. Các thuật toán metaheustic hoạt động dựa trên tri thức của cả quần thể do vậy có thường có hiệu quả đối với nhiều dạng bài toán lập lịch và các cấu trúc luồng công việc phức tạp. Chương 2: Giải bài toán CLOS theo phương pháp tối ưu bày đàn Chương này gồm hai nội dung chính: (i) Đề xuất thuật toán PSOi_H giải bài toán CLOS (ii) Đề xuất thuật toán LPSO_H giải bài toán CLOS 2.1. Thuật toán đề xuất PSOi_H Thuật toán đề xuất hoạt động theo phương pháp tối ưu bày đàn, tuy nhiên thuật toán được cải tiến ở các điểm sau: (i) Thay đổi phương pháp cập nhật vị trí cho các cá thể nhằm tăng tính đa dạng cho quần thể. (ii) Đề xuất thủ tục Inverse nhằm giúp quần thể thoát khỏi cực trị địa phương. Mã hóa cá thể Vector vị trí và vector dịch chuyển đều được biểu diễn bằng cấu trúc dữ liệu bảng băm trong ngôn ngữ lập trình java. T1 T2 T3 T4 T5 S1 S2 S1 S3 S2 Phương thức cập nhật vị trí của cá thể Định nghĩa 1: điểm năng lực tính toán cơ bản của máy chủ (base score) là một đại lượng được sử dụng để đánh giá hiệu suất của máy chủ, được tính toán dựa trên điểm của các thành phần khác trong máy tính như tốc độ bộ vi xử lý, dung lượng và tốc độ bộ nhớ RAM, tốc độ ổ đĩa cứng. Trong luận 9 án này điểm năng lực tính toán được ưu tiên theo tốc độ tính toán của bộ vi xử lý trên máy chủ. Công thức cập nhật các thành phần của vector vị trí và vector dịch chuyển như sau : MtSStvtxSPtvtxSPjtx r k i k ir k i k ij k i ,..,2,1;])[][()(])[][()(,][ 1  Mk N xxB xP N xxB xPy Sq qjk jk Sq qik ikk ,...,2,1; 1 ),( )( 1 ),( )(                        Biện pháp thoát khỏi cực trị địa phương Phương pháp tối ưu bày đàn nói riêng và các phương pháp tìm kiếm dựa trên heuristic và metaheuristic nói chung đôi khi bị mắc kẹt tại các lời giải cực trị địa phương mà không thể thoát ra để đi tới lời giải tốt hơn.Phần này đề xuất thủ tục Inverse như một biện pháp được áp dụng mỗi khi vòng lặp chương trình sa vào một cực trị địa phương và các cá thể bị hút vào gần lời giải cực trị đó mà không thể thoát ra. Hình 2.2:Thủ tục Inverse Thuật toán PSOi_H hoạt động theo phương pháp tối ưu bày đàn theo đó tại mỗi bước lặp các cá thể cập nhật vị trí của mình hướng tới vị trí tốt nhất của cả quần thể (gbest) đồng thời có dựa trên kinh nghiệm cá nhân 3.1 4.1 5.2 Sπ(2) Sπ(1) Sπ(3) Sπ(1) Sπ(3) S1  S2 3.1 5.2 4.1 S2 S1 S3 10 (pbesti). Nếu sau K thế hệ liên tiếp không cải thiện được một cách đáng kể giá trị gbest (mức chênh không vượt quá ) thì chứng tỏ quần thể đang hội tụ tại một cực trị địa phương. Khi đó thủ tục Inverse được áp dụng cho một nửa cá thể tồi nhất trong quần thể, và di cư chúng tới một vùng không gian mới, tại đó quá trình tìm kiếm được tái khởi động. Thực nghiệm Để kiểm chứng thuật toán PSOi_H tác giả đã sử dụng các bộ dữ liệu thực nghiệm được xây dựng trong phụ lục PL1, PL2 và công cụ mô phỏng môi trường điện toán đám mây CloudSim [64], các hàm của gói thư viện Jswarm. Kết quả của thuật toán được so sánh với các giá trị tối ưu tìm được bằng phương pháp vét cạn và các thuật toán heuristic và metaheuristic là Random [38], RRTSM [39], PSO_H [28], EGA [40]. Chi tiết về kết quả thực nghiệm được trình bày trong các bảng 2-3, 2-4 và 2-5 của luận án. So sánh thuật toán PSOi_H với các thuật toán khác Hình 2.4: So sánh thuật toán PSOi_H và các thuật toán khác với bộ dữ liệu T1052 11 Hình 2.5: So sánh thuật toán PSOi_H và các thuật toán khác với bộ dữ liệu T2032 Đánh giá chất lượng lời giải thuật toán PSOi_H Với mỗi bộ dữ liệu chuẩn chúng tôi đã tiến hành thực nghiệm các thuật toán một cách độc lập với 30 lần thử, các tham số về băng thông giữa các máy chủ, tốc độ tính toán của các máy chủ được thiết lập trong môi trường mô phỏng CloudSim một cách nhất quán cho tất cả các thuật toán trong các lần thử nghiệm. Với hai thuật toán PSOi_H và PSO_H các tham số về hệ số quán tính: ; hệ số gia tốc c1, c2; số cá thể trong quần thể và số thế hệ được thiết lập như nhau. Kết quả thực nghiệm đã chỉ ra chất lượng lời giải của thuật toán PSOi_H luôn tốt hơn các thuật toán Random, RRTSM ở cả 3 tham số là độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất trong tất cả các bộ dữ liệu thực nghiệm. Kết quả thực nghiệm với các bộ dữ liệu ngẫu nhiên trong bảng 2-3 đã chỉ ra thuật toán PSOi_H luôn cho chất lượng lời giải tốt hơn thuật toán PSO_H ở cả 3 tham số độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất trong hầu hết các bộ dữ liệu thực nghiệm. Một số bộ dữ liệu như T1035, T2051, T2053 thì thuật toán 12 PSOi_H có giá trị trung bình và độ lệch chuẩn nhỏ hơn so với kết quả tìm được bởi thuật toán PSO_H. Kết quả thực nghiệm với các bộ dữ liệu trong ứng dụng thực tiễn Montage, Epigenomics (xem bảng 2-4, 2-5) đã chỉ ra chất lượng lời giải của thuật toán PSOi_H tốt hơn thuật toán PSO_H ở cả 3 tham số độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất. So với thuật toán EGA thì thuật toán PSOi_H tốt hơn ở 2 tham số giá trị trung bình và giá trị tốt nhất. Độ lệch chuẩn tìm được bởi thuật toán PSOi_H nhỏ hơn độ lệch chuẩn tìm được bởi các thuật toán PSO_H từ 2% - 11% cho các bộ dữ liệu thực nghiệm có các tham số môi trường đám mây đồng đều về băng thông và tốc độ tính toán, và nhỏ hơn từ 16% - 51% cho các bộ dữ liệu thực nghiệm có tham số môi trường đám mây không đồng đều về băng thông và tốc độ tính toán giữa các máy chủ. Giá trị trung bình tìm được bởi thuật toán PSOi_H nhỏ hơn giá trị trung bình tìm được bởi thuật toán PSO_H từ 1% - 7%, đặc biệt với các bộ dữ liệu thực nghiệm có hệ số  nhỏ (đồ thị luồng công việc có số cạnh ít, hay sự phụ thuộc dữ liệu giữa các tác vụ không nhiều) thì thuật toán PSOi_H có giá trị trung bình nhỏ hơn so với thuật toán PSO_H từ 8% - 16%. So với thuật toán EGA giá trị trung bình tìm được bởi thuật toán PSOi_H nhỏ hơn từ 2% - 9%. Giá trị tốt nhất tìm được bởi thuật toán PSOi_H nhỏ hơn giá trị tốt nhất tìm được bởi các thuật toán Random và RRTSM với tất cả các bộ dữ liệu thực nghiệm. So với thuật toán PSO_H thì giá trị tốt nhất tìm được bởi PSOi_H nhỏ hơn 2% - 7% , đặc biệt với các bộ dữ liệu thực nghiệm từ ứng dụng thực tiễn Epinogenmic thì giá trị tốt nhất tìm được bởi PSOi_H nhỏ hơn PSO_H từ 8% - 15%. Giá trị tốt nhất tìm được bởi thuật toán PSOi_H nhỏ hơn giá trị tốt nhất tìm được bởi thuật toán EGA từ 2.3% - 8%. 13 Với một số bộ dữ liệu thực nghiệm thì giá trị tốt nhất tìm được bởi thuật toán PSOi_H bằng giá trị tối ưu tìm được theo phương pháp vét cạn; như các bộ dữ liệu chuẩn T531, T532, T533. Với các bộ dữ liệu thực nghiệm khác giá trị tốt nhất tìm được bởi thuật toán PSOi_H có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 0.8% đến 4% (theo công thức 1-10). Với các bộ dữ liệu thực nghiệm có băng thông giữa các máy chủ trong môi trường đám mây thấp thì giá trị tốt nhất tìm được bởi thuật toán PSOi_H có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 11.5% - 20.7%. Kết quả được trình bày chi tiết trong bảng 2-6 của luận án. 2.2. Thuật toán LPSO_H Thuật toán LPSO_H là một thuật toán tối ưu bày đàn lai, trong đó sử dụng kết hợp phương pháp tối ưu bày đàn và phương pháp tìm kiếm lân cận. Thuật toán LPSO gồm các điểm cải tiến cơ bản sau: (i) Thay đổi phương pháp cập nhật vị trí của các cá thể nhằm tăng tính đa dạng trong quần thể. (ii) Kết hợp với thủ tục tìm kiếm lân cận nhằm giúp quần thể thoát khỏi các điểm cực trị địa phương. Phương pháp tìm kiếm lân cận Tìm kiếm lân cận là một phương pháp tìm kiếm heuristic. Phương pháp này thường bắt đầu từ một giải pháp khởi tạo của bài toán, sau đó sẽ áp dụng một dãy các toán tử biến đổi trên lời giải ban đầu để thu được lời giải mới với giá trị hàm mục tiêu tốt hơn [70]. Tác giả đã đề xuất hai toán tử Exchange và RotateRight sử dụng cho quá trình tìm kiếm lân cận như hình sau: 14 Hình 2.14: Toán tử RotateRight và Exchange Thực nghiệm Tham số môi trường điện toán đám mây và luồng dữ liệu thực nghiệm được trình bày chi tiết trong các bảng PL1-1 đến PL1-39 và PL2-1 đến PL2-3. Kết quả thực nghiệm thuật toán LPSO_H được trình bày chi tiết trong các bảng 2-9, 2-10 và 2-11 của luận án. Đánh giá chất lượng lời giải thuật toán LPSO_H Với mỗi bộ dữ liệu chuẩn tác giả đã tiến hành thực nghiệm các thuật toán một cách độc lập với 30 lần thử, các tham số về băng thông giữa các máy chủ, tốc độ tính toán của các máy chủ được thiết lập trong môi trường mô phỏng CloudSim một cách nhất quán cho tất cả các thuật toán trong các lần thử nghiệm. Với hai thuật toán LPSO_H và PSO_H các tham số về hệ số quán tính: ; hệ số gia tốc c1, c2; số cá thể trong quần thể và số thế hệ được thiết lập như nhau. Kết quả thực nghiệm trong các bảng 2-9, 2-10 và 2-11 đã chỉ ra chất lượng lời giải của thuật toán LPSO_H luôn tốt hơn các thuật toán Random, RRTSM, PSO_H ở cả 3 tham số là độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất. So sánh với thuật toán EGA, thuật toán LPSO_H luôn cho lời giải tốt hơn thuật toán EGA ở cả 3 tham số độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất trong hầu hết các bộ dữ liệu thực nghiệm. Với một số bộ dữ liệu như T2054, T2055, M2531, M5081, 3 1 2 3 1 a) Toán tử RotateRight 3 1 2 3 1 3 3 2 1 1 b) Toán tử Exchange 15 E10081 thuật toán LPSO_H luôn cho chất lượng lời giải tốt hơn thuật toán EGA ở 2 tham số là giá trị trung bình và giá trị tốt nhất. Độ lệch chuẩn tìm được bởi thuật toán LPSO_H nhỏ hơn độ lệch chuẩn tìm được bởi thuật toán PSO_H từ 7% - 14% trong hầu hết các bộ dữ liệu thực nghiệm, đặc biệt trong các bộ dữ liệu thực nghiệm từ ứng dụng thực tế Montage và Epigenomics thì độ lệch chuẩn tìm được bởi thuật toán LPSO_H nhỏ hơn so với thuật toán PSO_H từ 16% - 31%. Giá trị trung bình tìm được bởi thuật toán LPSO_H nhỏ hơn giá trị trung bình tìm được bởi thuật toán PSO_H từ 2.7% - 9.8%, đặc biệt với các bộ dữ liệu thực nghiệm có khối lượng dữ liệu cần truyền giữa các tác vụ nhỏ thì giá trị trung bình tìm được bởi thuật toán LPSO_H nhỏ hơn so với thuật toán PSO_H từ 21% - 33%. So với thuật toán EGA giá trị trung bình tìm được bởi LPSO_H nhỏ hơn từ 2.4% - 11.8%. Giá trị tốt nhất tìm được bởi thuật toán LPSO_H nhỏ hơn giá trị tốt nhất tìm được bởi PSO_H từ 2.1% - 11% và nhỏ hơn so với thuật toán EGA từ 1.2% - 15.4%. Với một số bộ dữ liệu thực nghiệm thì giá trị tốt nhất tìm được bởi thuật toán LPSO_H bằng giá trị tối ưu tìm được theo phương pháp vét cạn; như các bộ dữ liệu chuẩn T531, T532, T533. Với các bộ dữ liệu thực nghiệm khác giá trị tốt nhất tìm được bởi thuật toán LPSO_H có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 0.1% đến 5.4% (theo công thức 1-10). Với các dữ liệu thực nghiệm có tham số môi trường đám mây không đồng đều về băng thông và tốc độ tính toán giữa các máy chủ thì giá trị tốt nhất tìm được bởi thuật toán LPSO_H có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 8.5% - 20.7%. Kết quả được trình bày chi tiết trong bảng 2-12 của luận án. So sánh thuật toán LPSO_H với các thuật toán khác 16 Hình 2.18: So sánh thuật toán LPSO_H và các thuật toán khác với bộ dữ liệu M5081 Chương 3: Giải bài toán CLOS theo phương pháp tiến hóa vi phân Chương này trình bày các nội dung chính sau: (i) Phương pháp tiến hóa vi phân dựa trên thông tin định hướng (ii) Đề xuất thuật toán mới lập lịch luồng công việc trong môi trường điện toán đám mây MODE dựa trên phương pháp tiến hóa vi phân. Phương pháp tiến hóa vi phân dựa trên thông tin đối xứng Định nghĩa 1 (Tính đối xứng): cho x là một số thực, x  [a,b]. Khi đó phần tử đối xứng của x, ký hiệu là x được tính như sau: xbax  -1) Nếu a =0, b=1 thì ta có: xx 1 17 Định nghĩa 2 ( Tính đối xứng trong không gian n chiều): xét điểm p(x1, x2,..,xn) trong không gian n chiều, với xi R và xi [ai, bi]. Khi đó điểm đối xứng của p kí hiệu là ),...,,( 21 nxxxp  và được tính như sau: nixbax iiii ,...,2,1;  2) Phương pháp OBL: trong mỗi bước lặp của phương pháp OBL với mỗi điểm p(x1, x2,,xn) ta sẽ tính điểm đối xứng ),...,,( 21 nxxxp  của p, nếu )()( pfpf  thì điểm p sẽ thay thế điểm p (với f là hàm mục tiêu của bài toán) và quá trình tìm kiếm sẽ được tiếp tục với tập các điểm mới tìm được. Thuật toán đề xuất MODE Thuật toán MODE (Modified Opposition-Based Differential Evolution) là thuật toán lập lịch luồng công việc trong môi trường điện toán đám mây nhằm cực tiểu hóa makespan, thuật toán làm việc theo nguyên tắc của thuật toán tiến hóa vi phân dựa trên thông tin đối xứng, tuy nhiên thuật toán được cải tiến ở các điểm sau: (i) Định nghĩa phương pháp lấy đối xứng cho các cá thể trong quần thể. (ii) Sử dụng phương pháp lựa chọn theo vòng dựa trên xếp hạng của cá thể để chọn các cá thể cho quá trình đột biến nhằm sinh ra được cá thể tốt cho thế hệ kế tiếp. (iii) Sử dụng thông tin đối xứng của các cá thể dựa theo đặc trưng của bài toán CLOS trong quá trình tìm kiếm. Phương pháp tìm cá thể đối xứng Theo phương pháp tiến hóa vi phân dựa trên thông tin đối xứng, trong bước khởi tạo và các bước lặp của thuật toán cần phải tìm ra quần thể đối xứng với quần thể hiện tại. Dựa trên đặc trưng của bài toán CLOS, phần này đề xuất phương pháp tìm các cá thể đối xứng như sau: 18 Kí hiệu: a = Max{P(Si )}; i=1,2,,N; P(Si) là năng lực tính toán của máy chủ Si b = Min{P(Si)}; i=1,2,,N. Cá thể xi k = (Si(1), Si(2),..,Si(M)) với Si(j) {S1, S2,,SN} j=1,2,,M. Định nghĩa 1: cá thể đối xứng của cá thể xi k được định nghĩa là cá thể k ix với các thành phần ),...,,( )()2()1( Miii SSS  được tính như sau: MjSPbaS jiji ,...,2,1);( )()(   (Error! No text of specified style in document..3) Với )( )( jiSP  là năng lực tính toán của máy chủ )( jiS  Cách thức gán định danh máy chủ cho các thành phần của vector vị trí: để gán định danh cho thành phần thứ j của vector ),...,,( )()2()1( Niii k i SSSx  ta sẽ tìm máy chủ có năng lực tính toán gần nhất với giá trị của thành phần j là )( jiS  và gán định danh của máy chủ đó cho thành phần thứ j trong vector k ix . Công thức gán như sau: rjirjik k ij SSPSPSPSPkx  ,)()()()(; )()(  (Error! No text of specified style in document..4) Phương lựa chọn theo vòng dựa trên xếp hạng của cá thể Trong phương pháp DE và ODE toán tử đột biến được tính toán dựa trên việc lựa chọn một cách ngẫu nhiên hai cá thể cha mẹ, sau đó sẽ tính vector đột biến vi theo công thức: vi(t)  pbest + F(p1- p2). Sử dụng chiến lược đột biến best/1 thường cho chất lượng lời giải tốt và tốc độ hội tụ nhanh hơn các chiến lược rand/1, rand/2. Thuật toán cải tiến MODE tác giả đã sử dụng phương pháp lựa chọn theo vòng dựa trên xếp hạng của cá thể (RBRWS) để chọn ra các cá thể cho 19 quá trình đột biến, phương pháp RBRWS đã được sử dụng trong nhiều thuật toán tiến hóa và đã được kiểm chứng là giảm sự hội tụ sớm tới các vùng cực trị địa phương, và tránh được sự phụ thuộc vào tính chất đồng đều của giá trị hàm mục tiêu trong quá trình lựa chọn [76]. Phương lựa chọn theo vòng dựa trên xếp hạng của cá thể (Rank-based Roulette Wheel Selection – RBRWS) [76] là phương pháp lựa chọn cá thể trong đó xác suất lựa chọn mỗi cá thể được quyết định dựa trên hạng của cá thể đó trong quần thể, với hạng của cá thể được tính toán theo giá trị hàm mục tiêu đạt được của cá thể. Phương pháp này đầu tiên sẽ tính giá trị hàm mục tiêu cho tất cả các cá thể trong quần thể và sắp xếp chúng theo chiều tăng dần của giá trị hàm mục tiêu tính được, sau đó mỗi cá thể được gán một giá trị vị trí từ 1 đến NP (NP là số cá thể trong quần thể) theo nguyên tắc cá thể có giá trị hàm mục tiêu nhỏ nhất ứng với vị trí là NP, cá thể tiếp theo là NP -1,, và cá thể có giá trị hàm mục tiêu lớn nhất có vị trí là 1. Hạng của mỗi cá thể trong quần thể được tính theo công thức sau: 1 1 )1(22    P i i N pos SPSPrank (Error! No text of specified style in document..5) trong đó: + pos là giá trị vị trí của cá thể i + SP là một hằng số trong đoạn [1.0, 2.0] Thực nghiệm Tham số môi trường điện toán đám mây và luồng dữ liệu thực nghiệm được trình bày chi tiết trong các bảng PL1-1 đến PL1-39 và PL2-1 đến PL2-3. Kết quả thực nghiệm thuật toán MODE được trình bày chi tiết trong các bảng 3-2, 3-3 và 3-4 của luận án. 20 Đánh giá chất lượng lời giải thuật toán MODE Với mỗi bộ dữ liệu chuẩn tác giả tiến hành thực nghiệm các thuật toán một cách độc lập với 30 lần thử, các tham số về băng thông giữa các máy chủ, tốc độ tính toán của các máy chủ được thiết lập trong môi trường mô phỏng CloudSim một cách nhất quán cho tất cả các thuật toán trong các lần thử nghiệm. Kết quả thực nghiệm trong các bảng 3-2, 3-3 và 3-4 đã chỉ ra chất lượng lời giải của thuật toán MODE luôn tốt hơn các thuật toán Random, RRTSM, PSO_H và EGA ở cả 3 tham số là độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất. Giá trị trung bình tìm được bởi thuật toán MODE nhỏ hơn giá trị trung bình tìm được bởi thuật toán PSO_H từ 2% - 9%, với các bộ dữ liệu thực nghiệm có khối lượng dữ liệu truyền giữa các tác vụ nhỏ thì giá trị trung bình tìm được bởi thuật toán MODE nhỏ hơn thuật toán PSO_H từ 13% - 29%. So với thuật toán EGA giá trị trung bình tìm được bởi MODE nhỏ hơn từ 1.1% - 11%. Giá trị tốt nhất tìm được bởi thuật toán MODE nhỏ hơn giá trị tốt nhất tìm được bởi thuật toán PSO_H từ 2.1% - 12.5%, với các bộ dữ liệu thực nghiệm có khối lượng dữ liệu truyền qua lại giữa các tác vụ trong luồng công việc nhỏ thì giá trị tốt nhất tìm được bởi thuật toán MODE nhỏ hơn giá trị tốt nhất tìm được bởi thuật toán PSO_H từ 14.5% - 24.6%. Giá trị tốt nhất tìm được bởi MODE nhỏ hơn so với giá trị tốt nhất tìm được bởi thuật toán EGA từ 1.2% - 9.4%. Với một số bộ dữ liệu chuẩn thì lời giải tốt nhất tìm được bởi thuật toán MODE bằng với giá trị tối ưu tìm được bởi thuật toán vét cạn như các bộ dữ liệu chuẩn T1032, T1031, T1034, T1035,, với các bộ dữ liệu khác lời giải tốt nhất tìm được bởi thuật toán MODE có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 0.2% đến 4.3%. Kết quả chi tiết được trình bày trong bảng 3-5, thuật toán MODE có độ lệch chuẩn nhỏ trong hầu 21 hết các bộ dữ liệu đã thử nghiệm, giá trị lệch chuẩn của thuật toán MODE nằm trong đoạn [0, 4.2], đồng thời sự chênh lệch giữa giá trị trung bình và giá trị tốt nhất trong các bộ dữ liệu thực nghiệm cũng khá nhỏ, điều đó chứng tỏ chất lượng lời giải của thuật toán MODE tốt và ổn định trong hầu hết các bộ dữ liệu thực nghiệm So sánh thuật toán MODE với các thuật toán khác Định hướng các trường hợp sử dụng các thuật toán đề xuất PSOi_H, LPSO_H và MODE Trên cơ sở những khảo sát thực nghiệm các thuật toán theo các tham số về độ lệch chuẩn, giá trị trung bình, giá trị tốt nhất và thời gian chiếm dụng CPU, luận án đề xuất về hướng áp dụng các thuật toán PSOi_H, LPSO_H và MODE cho các loại dữ liệu cụ thể như sau: • Các đồ thị luồng công việc phức tạp có nhiều tác vụ phân chia và tập hợp dữ liệu, với số tác vụ lớn và khối lượng dữ liệu cần truyền giữa các tác vụ trong luồng công việc lớn thì thuật toán MODE cho chất lượng lời giải tốt nhất, tuy nhiên thời gian sử dụng CPU của các máy chủ trong thuật toán MODE là lớn nhất (xem bảng 3-6). Do vậy khi cần thực hiện việc lập lịch cho các luồng công việc phức tạp với khối 22 lượng dữ liệu cần truyền giữa các tác vụ lớn thì nên sử dụng thuật toán MODE. • Các đồ thị luồng công việc có cấu trúc đơn giản với hệ số  nhỏ hoặc các đồ thị luồng công việc có cấu trúc dạng đường ống song song, và dữ liệu truyền qua lại giữa