Mở Đầu – Đề cập đến lý do chọn đề tài, mục tiêu của đề tài, các yêu cầu đặt ra của chương trình sắp xếp thời khóa biểu. - Chương 2: Các công trình liên quan - trình bày một số nghiên cứu liên quan đến bài toán lập lịch thời khoá biểu trong trường đại học. 7 - Chương 3: Cơ sở lý thuyết – Nêu ra các lý thuyết nền tảng được sử dụng trong luận văn. Trình bày giải thuật di truyền, kiến trúc của bộ đồng xử lý Xeonphi, các phương pháp song song được sử dụng cho giải thuật di truyền.
- Chương 4: Phương pháp giải bài toán sắp xếp thời khóa biểu - trình bày chi tiết việc hiện thực giải thuật di truyền để áp dụng vào bài toán lập lịch thời khoá biểu, tổ chức dữ liệu để sử dụng hiệu quả vector và kiến trúc của Xeonphi, phương pháp song song được sử dụng trong luận văn. - Chương 5: Hiện thực và thử nghiệm – Đưa ra kết quả đạt được sau khi hiện thực giải thuật, đồng thời so sánh với các kết quả và thời gian hiện thực của các giải thuật khác để đánh giá - Chương 6: Kết luận và hướng mở rộng đề tài 8 Chương 2 CÁC CÔNG TRÌNH LIÊN QUAN Có nhiều phương pháp để giải quyết bài toán lập lịch thời khoá biểu cho trường đại học dựa trên Meta-heuristic. Các phương pháp mô phỏng luyện kim, tìm kiếm Tabu, giải thuật di truyền và các phương pháp hỗn hợp đã được dùng để giải quyết bài toán lập lịch thời khoá biểu cho trường đại học. Meta-heuristic bắt đầu với một hay nhiều các lời giải ban đầu và dùng các chiến lược tìm kiếm để tránh các tối ưu cục bộ.
Tất cả các giải thuật tìm kiếm có thể tạo ra các kết quả tốt nhưng phải quan tâm đến thời gian thực thi của giải thuật 2.1 Phương pháp mô phỏng luyện kim (Simulated Annealing - SA) Giải thuật SA được bắt đầu bằng việc tính toán ngẫu nhiên các bước dịch chuyển đến các lời giải kế. Nhiệt độ và hàm lượng giá xác định việc có thể chấp nhận các bước di chuyển có kết quả không tốt. Nhiệt độ cao thì xác suất chấp nhận kết quả không tốt cao và nhiệt độ thấp thì xác suất chấp nhận kết quả không tốt thấp. Xác suất chấp nhận được định nghĩa bởi công thức exp(-δ /t).
Trong đó δ là sự thay đổi chất lượng của lời giải ( là thay đổi giá trị lượng giá) và t là nhiệt độ hiện tại. Hiệu quả của SA phụ thuộc vào thời gian làm mát và việc chọn cấu trúc cho các lời giải lân cận. Elmohamed [15] đã áp dụng giải thuật SA với các loại làm mát khác nhau (hình học, thích nghi và thích nghi với việc nung nóng) để giải bài toán lập lịch cho trường đại học. Họ thử nghiệm trên tập dữ liệu thực tế ở trường Syracuse University.
Kết quả cho thấy việc thực hiện SA với giải thuật làm mát thích nghi và nung nóng cho hiệu quả tốt nhất.2 Tìm kiếm Tabu (Tabu search - TS) 9 TS là một công cụ hiệu quả để giải quyết các vấn đề tối ưu dạng khó. Ý tưởng của TS được đề xuất đầu tiên bởi Glover. TS [14] là phương pháp tìm kiếm cục bộ có phương pháp heuristic để khai phá không gian tìm kiếm mà vượt qua được tối ưu cục bộ. Giải thuật TS bắt đầu từ một lời giải ban đầu sau đó được lặp để khai phá các lời giải kế cận.
Bước di chuyển tiếp theo được chọn sau khi đánh giá hết toàn bộ các lời giải kế cận của lời giải hiện tại. Một lời giải không tốt có thể được chấp nhận miễn là chất lượng lời giải đó tốt hơn toàn bộ các lời giải kế cận. Việc này có thể dẫn đến việc lặp vòng, như việc di chuyển lặp lại trong một phần của không gian tìm kiếm. Để tránh việc lặp vòng.
TS sử dụng bộ nhớ để lưu trữ danh sách tabu (tabu list). Nếu một lời giải được tìm thấy trong danh sách tabu, nó được gọi là một lời giải tabu (tabu solution) và lời giải tốt nhất trong các lời giải kế cận của lời giải hiện được khai phá, và cứ như vậy tiếp tục. Danh sách tabu cho phép giải thuật thoát khỏi việc tối ưu cục bộ. Các bước dịch chuyển trong tabu list được ngăn chặn bởi một số lần lặp nhất định gọi là “tabu tenure”.
Nhiều nghiên cứu đã thực hiện giải bài toán lập lịch thời khoá biểu bằng phương pháp TS. Hertz [14] lần đầu tiên sử dụng phương pháp TS để giải bài toán lập lịch thời khoá biểu. Tác giả đã kết luận rằng phương pháp này có thể cho kết quả thoả mãn yêu cầu lập lịch. Lợi ích chính của phương pháp này là nó cho phép các bước dịch chuyển hứa hẹn đến lời giải tốt, việc tìm kiếm nhanh chóng.3 Multi-Objective EA (Evolutionary algorithms) Giải thuật multi-objective EA (MOEA) đầu tiên được gọi là “vector evaluated GA”, đề xuất bởi Schaffer.
Sau đó những giải thuật MOEA khác như strength Pareto EA (SPEA), ε-multi-objective EA (ε-MOEA), the elitist non-dominated sorting GA (NSGA-II), được phát triển và áp dụng thành công. NSGA-II được đề xuất dựa trên khái niệm của sắp xếp các phần từ không trội (non- domiated) và độ đo đông đúc (crowding distance). Ban đầu, tập các lời giải với kích 10 thước N được tạo ra và sắp xếp dựa trên các phần tử không trội. Sau đó, tại mỗi thế hệ, một tập các cá thể con Q được tạo thành từ tập cá thể cha P bằng cách sử dụng phương pháp chọn “tournament” ( hai cá thể được lựa chọn ngẫu nhiên từ tập cha P, cá thể được lựa chọn dựa theo hạng và khoảng cách đông đúc), phép lai, phép đột biến.
Sau đó các cá thể con Q được hợp với P, tạo thành tập cá thể R có 2N phần tử, việc tính toán hạng và khoảng cách đông đúc được tính cho R, Tập N cá thể tốt nhất theo hạng và theo khoảng cách đông đúc được lựa chọn trong R để tạo thành thế hệ tiếp theo. Do đó, sau mỗi thế hệ, tập các cá thể không trội được duy trì. Datta [11], sử dụng NGSA-II để giải bài toán lập lịch thời khoá biểu. Họ phát triển mô hình tối ưu 2 mục tiêu để giảm thiểu các vi phạm của ràng buộc mềm, áp dụng 1 phép lai và 4 phép đột biến, và kiểm tra độ hiệu quả của giải thuật trên tập dữ liệu thực.
Họ đưa ra kết luận là độ hiệu quả của giải thuật phụ thuộc vào việc định nghĩa xác suất đột biến và lời giải được khởi tạo ban đầu. 11 Chương 3 CƠ SỞ LÝ THUYẾT Chương này gồm các phần: - Phần đầu giới thiệu về giải thuật di truyền - Phần tiếp theo giới thiệu về các phương pháp song song dành cho giải thuật di truyền - Giới thiệu về Xeon Phi và các loại lập trình với Xeon Phi 3.1 Giải thuật di truyền Giải thuật di truyền (GA-Genetic Algorithm) là kỹ thuật phỏng theo quá trình thích nghi tiến hóa của của các quần thể sinh học dựa trên học thuyết Darwin. Quá trình tiến hoá thể hiện tính tối ưu ở chỗ, thế hệ sau thường tốt hơn ( phát triển hơn, hoàn thiện hơn) so với thế hệ trước. Tiến hoá tự nhiên dựa vào hai quá trình chính là sinh sản và chọn lọc tự nhiên.
Trong quá trình tiến hoá tự nhiên, thế hệ sau được sinh ra để bổ sung cho các thế hệ đầu. Cá thể nào phát triển hơn, thích nghi cao hơn với môi trường sẽ tồn tại, cá thể nào không thích nghi sẽ bị đào thải. Các cá thể mới sinh ra trong quá trình tiến hoá nhờ sự lai ghép từ các cá thể bố mẹ. Cá thể mới có thể mang những tính trạng của cha mẹ (di truyền), cũng có thể mang những đặc tính mới (đột biến).
Di truyền và đột biến có vai trò quan trọng trong tiến hoá. Đột biến có sác xuất xảy ra nhỏ hơn nhiều so với quá trình di truyền. Vậy nên có thể nói giải thuật di truyền là phương pháp tìm kiếm tối ưu ngẫu nhiên bằng cách mô phỏng theo sự tiến hóa của con người hay của sinh vật. Ý tưởng của thuật toán di truyền là mô phỏng các hiện tượng tự nhiên, là kế thừa và đấu tranh sinh tồn được Holland [9] phát triển vào hệ thống nhân tạo năm 1975 để tối ưu hóa các vấn đề và xây dựng xây dựng thuật toán di truyền.
Cho đến ngày nay, giải thuật di truyền vẫn được coi 12 như là một công cụ mạnh mẽ để giải quyết những vấn đề về tìm kiếm và tối ưu hóa phức tạp như là lập thời gian biểu, lập lịch, hệ thống điều khiển, bài toán người du lịch… Dù rằng các giải thuật di truyền thực hiện được thay đổi theo bài toán cụ thể, nhưng nhìn chung đều có cấu trúc tiêu biểu sau: Hình 3.1 - Sơ đồ giải thuật GA Hình 3.1 Mô tả các bước cơ bản của một giải thuật GA, Khởi tạo quần thể, Lựa chọn cá thể cha, Phép Lai ghép, phép đột biến, loại bỏ các cá thể kém thích nghi 3.2 Các phương pháp song song cho giải thuật di truyền a) Master – Slave Quần thể được lưu trữ tại master, việc tính toán được phân bổ cho các slaves 13 Các thao tác trên GA Master Giá trị lượng giá Slave Tính toán Tính toán Tính toán Tính toán giá trị giá trị giá trị giá trị lượng giá lượng giá lượng giá lượng giá Hình 3.2 - Mô Hình Master – Slave Mô hình đồng bộ : chỉ có việc tính toán giá trị lượng giá được tính ở các slave, master phải đợi các slave để kết thúc, các thao tác chọn, thay thế, lai và đột biến được thực hiện tại master. Mô hình bất đồng bộ: các thao tác chọn, thay thế, lai và đột biến được thực hiện trên các slave, các slave không phải đợi để tiếp tục xử lý trên thế hệ tiếp theo. b) Fine-Grained Parallelization Quần thể được phân bố cho các processors qua một lưới 2D, các processor gần nhau chia sẽ các cá thể của mình trong việc lựa chọn cá thể làm cá thể cha.3 - Mô hình Fine-Grained với 8 nút ( processor) 14 Việc khởi tạo quần thể giống với việc khởi tạo quần thể của một giải thuật GA đơn giản, nhưng các cá thể được chia đều cho các processor. Các processor có thể lựa chọn phần tử làm phần tử cha từ các processor kế cận và cá thể con có thể thay thế một cá thể khác trong quần thể con.
Việc lai và đột biến giống với giải thuật GA đơn giản. c) Coarse-Grained Parallelization Ở phương pháp này, mỗi process được gán một một thuật GA đơn giản và giữa các processor có kết nối với nhau để có thể truyền các cá thể lẫn nhau.4 - Mô hình Coarse-Grained Từ Mô hình ở hình 3.