Tóm tắt Luận án tiến sĩ Toán học: 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

Chia sẻ: Phong Tỉ | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

56
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án đã đề xuất ba thuật toán gần đúng cho bài toán CLOS, để kiểm chứng các thuật toán đó phải so sánh lời giải của chúng với lời giải tối ưu. Chúng tôi đã tìm lời giải tối ưu thông qua phương pháp vét cạn, tuy nhiên phương pháp này chỉ khả thi đối với những bộ dữ liệu kích thước nhỏ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Toán học: 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

BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ PHAN THANH TOÀ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 Chuyên ngành : Cơ sở toán học cho tin học Mã số : 62 46 01 10 TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2018
Công trình được hoàn thành tại: VIỆN KH&CN QUÂN SỰ - BỘ QUỐC PHÒNG Người hướng dẫn khoa học: 1. TS Nguyễn Thế Lộc 2. TS Nguyễn Doãn Cường Phản biện 1:PGS.TS. Nguyễn Đức Nghĩa Trường Đại học Bách khoa Hà Nội Phản biện 2: PGS.TS. Lê Trọng Vĩnh Trường Đại học Khoa học tự nhiên Đại học Quốc gia Hà Nội Phản biện 3: PGS.TS. Nguyễn Xuân Hoài Trường Đại học Hà Nội Luận án tiến sĩ được bảo vệ trước Hội đồng chấm luận án cấp Viện, họp tại Viện KH&CNQS Vào hồi giờ ngày tháng năm 2018 Có thể tìm hiểu luận án tại thư viện: - Thư viện Viện Khoa học và Công nghệ quân sự - Thư viện Quốc gia Việt Nam
1 MỞ ĐẦU Tính cấp thiết của đề tài luận án Điện toán đám mây hoạt động dựa trên nền tảng công nghệ ảo hóa và mạng internet. Trong môi trường điện toán đám mây mọi tài nguyên phần cứng, phần mềm đều được cung cấp cho khách hàng dưới dạng dịch vụ và khách hàng sẽ phải trả chi phí cho các tài nguyên thực dùng. Điện toán đám mây [1] là môi trường phân tán không đồng nhất với sự kết hợp của nhiều máy chủ vật lý tạo nên các máy chủ ảo để phục vụ khách hàng. Bên cạnh các lợi ích mang lại như tài nguyên luôn sẵn dùng, giảm thiểu chi phí đầu tư hạ tầng và đội ngũ nhân viên công nghệ thông tin, điện toán đám mây cũng phải đối mặt với những thách thức như an toàn và bảo mật dữ liệu, điều phối tài nguyên hiệu quả tại các trung tâm dữ liệu, lập lịch luồng công việc,… Bài toán Lập lịch luồng công việc được ứng dụng trong nhiều lĩnh vực của khoa học và cuộc sống như lập lịch điều phối tài nguyên trong hệ điều hành, các hệ thống phân tán, lập lịch biểu cho các dây chuyền sản xuất. Các nhà khoa học đã sử dụng dữ liệu dạng luồng công việc trong nhiều lĩnh vực khoa học như nghiên cứu vũ trụ, động đất, tin sinh, vật lý….Đặc trưng của các loại ứng dụng này là cần phải xử lý một số lượng lớn tác vụ , khối lượng dữ liệu trao đổi giữa các tác vụ cũng rất lớn do vậy các ứng dụng này thường được triển khai trên các hệ thống tính toán phân tán như điện toán lưới hay điện toán đám mây. Thời gian hoàn thành và chi phí thực thi luồng công việc phụ thuộc vào nhiều yếu tố đầu vào như: • Số lượng tác vụ của luồng công việc. • Số tài nguyên của môi trường tính toán. • Quan hệ thứ tự giữa các tác vụ trong luồng công việc. • Độ trù mật của đồ thị luồng công việc.
2 Rất nhiều trường hợp riêng của bài toán lập lịch đã được chứng minh là thuộc lớp NP-Khó [2], do vậy để tìm ra lời giải tối ưu cho các bài toán với kích thước dữ liệu vào lớn nếu dùng phương pháp vét cạn sẽ mất rất nhiều thời gian. Một số cách tiếp cận theo Heuristic truyền thống như Min- min, Max-min,… thường cho chất lượng lời giải không tốt. Những giải pháp khác, chẳng hạn GA hay PSO, được các nhà nghiên cứu đề xuất cho tới nay đều không hướng tới mục tiêu là tối thiểu hóa thời gian thực hiện (makespan) như luận án này đặt ra. Do vậy việc nghiên cứu và đề xuất các thuật toán lập lịch tìm được lời giải gần tối ưu trong thời gian ngắn sẽ giúp nâng cao hiệu năng của trung tâm điều phối đám mây trong việc cung cấp dịch vụ tới khách hàng. Cấu trúc luận án Luận án gồm phần mở đầu, phụ lục, 03 chương, phần kết luận và hướng phát triển, danh mục các công trình khoa học đã công bố và tài liệu tham khảo. Phần mở đầu: trình bày tính cấp thiết của đề tài, những khái quát chung về mục tiêu, đối tượng, nội dung, phương pháp nghiên cứu, ý nghĩa khoa học và thực tiễn của luận án. 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 các khái niệm cơ bản về luồng công việc, cấu trúc và một số luồng công việc trong các ứng dụng khoa học thực tiễn. Mục 1.4 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 (từ đây gọi là CLOS - Cloud Scheduling), biểu diễn bài toán dưới dạng kí hiệu Graham và chứng minh độ phức tạp của bài toán. Mục 1.6 trình bày một số nghiên cứu liên quan đến bài toán lập lịch và đánh giá ưu nhược điểm của các cách tiếp cận giải bài toán lập lịch. Chương 2: Giải bài toán CLOS theo phương pháp Tối ưu bày đàn
3 Dựa theo phương pháp Tối ưu bày đàn, chương 2 trình bày hai thuật toán mới để giải bài toán CLOS là thuật toán PSOi_H và LPSO_H. Mục 2.2 trình bày thuật toán đề xuất PSOi_H với các nội dung về phương pháp mã hóa cá thể, cách thức cập nhật vector vị trí của các cá thể, phương pháp thoát khỏi cực trị địa phương, chi tiết thuật toán PSOi_H. Phần này cũng đã trình bày các kết quả thực nghiệm và đánh giá chất lượng lời giải thuật toán PSOi_H. Mục 2.3 trình bày chi tiết về thuật toán đề xuất LPSO_H và các kết quả thực nghiệm cùng với đánh giá chất lượng lời giải của thuật toán LPSO_H. 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 tổng quan về phương pháp tiến hóa vi phân, phương pháp đối xứng, phương pháp lựa chọn theo vòng dựa trên xếp hạng của cá thể. Mục 3.2 trình bày thuật toán đề xuất MODE để giải bài toán CLOS dựa theo phương pháp tiến hóa vi phân. Phần cuối chương này đã trình bày các kết quả thực nghiệm và đánh giá chất lượng lời giải của thuật toán đề xuất MODE. Ý nghĩa khoa học và thực tiễn Về mặt lý thuyết khoa học, trong số nhiều công trình nghiên cứu những dạng khác nhau của bài toán Lập lịch, theo hiểu biết của tác giả, luận án là công trình đầu tiên giải quyết bài toán Lập lịch cho dạng dữ liệu luồng công việc DAG với mục tiêu duy nhất là tối thiểu hóa makespan. Luận án đã đề xuất mô hình toán học chặt chẽ và tường minh cho bài toán - lấy bối cảnh thực hiện là trung tâm điện toán đám mây - trên cơ sở đó đưa ra cách phân loại bài toán theo phương pháp Graham và chỉ ra bài toán thuộc lớp NP-Khó. Luận án đã đề xuất ba thuật toán lập lịch mới dựa trên hướ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: Wi ; i  1,2,.., M P procTi  Thời gian truyền dữ liệu giữa tác vụ Ti và tác vụ Tk là: Dik ; i, k  1,2,.., M B procTi , procTk  Makespan của lịch biểu F được biểu diễn theo công thức sau:
6 makespan( F )  max{ t f (Ti )}  min{ t s (Ti )} TiT TiT 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 makespan( F )  min 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 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ế Căn cứ ra quyết định Tập trung Tĩnh Cục bộ Phân tán Động Toàn cục Phân bậc Hình 1.12: Phân loại các phương pháp lập lịch
7 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 Lập lịch dựa Lập lịch dựa Lập lịch dựa trên quyền trên phân trên bản sao ưu tiên các cụm các tác vụ tác vụ Thuật toán di Thuật toán đàn Phương pháp Thuật toán Phương… pháp truyền kiến tối ưu bày đàn luyện thép tiến hóa vi phân 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
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 : xik 1[t ]  j , P( S j )  ( xik [t ]  vik [t ])  P( S r )  ( xik [t ]  vik [t ]) S r  S ; t  1,2,.., M    B( xik , xq )   P( x )  qS B( x jk , xq ) ; k  1,2,..., M yk  P( xik )  qS   jk   N 1  N 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. S1 S2 S3 3.1 5.2 4.1 Sπ(1) Sπ(2) Sπ(3) 3.1 4.1 5.2 Sπ(1) Sπ(3) S1  S2 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
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 3 1 2 3 1 3 1 2 3 1 a) Toán tử RotateRight 3 3 2 1 1 b) Toán tử Exchange 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,
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: x  ab x Nếu a =0, b=1 thì ta có: x  1  x
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à p  ( x1 , x2 ,..., xn ) và được tính như sau: xi  ai  bi  xi ; i  1,2,..., n 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 p  ( x1 , x2 ,..., xn ) của p, nếu f ( p)  f ( p) 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ể xik = (Si(1), Si(2),..,Si(M)) với Si(j) {S1, S2,…,SN} j=1,2,…,M. k Định nghĩa 1: cá thể đối xứng của cá thể xik được định nghĩa là cá thể x i với các thành phần (S i (1) , S i ( 2) ,..., S i ( M ) ) được tính như sau: S i ( j )  a  b  P(Si ( j ) ); j  1,2,..., M (Error! No tex Với P( Si ( j ) ) là năng lực tính toán của máy chủ Si ( j ) 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 k x i  ( S i (1) , S i ( 2) ,..., S i ( N ) ) 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à S i ( j ) và gán định danh của máy chủ đó k cho thành phần thứ j trong vector x i . Công thức gán như sau: k x ij  k ; P( S k )  P( S i ( j ) )  P( S r )  P( S i ( j ) ) , S r (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