Giải thuật metaheuristic bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST

Báo xấu

4
lượt xem 2
download

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

Bài viết đề xuất kết hợp giữa giải thuật local search và giải thuật metaheuristic để giải quyết bài toán trên, cụ thể: dùng giải thuật luyện thép (Simulated Annealing – SA) để tìm lời giải ban đầu, sau đó dùng các hành vi của đàn linh cửu đốm của giải thuật Spotted hyena optimizer (SHO) để tối ưu lời giải ban đầu để tìm ra một thời khóa biểu phù hợp với năng lực sinh viên, kết quả này có thể tối ưu quá trình học tập của sinh viên, như thời gian tốt nghiệp và cải thiện kết quả học tập của sinh viên.

Chủ đề:

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

Lưu

Nội dung Text: Giải thuật metaheuristic bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên

CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 231 GIẢI THUẬT METAHEURISTIC BÀI TOÁN XẾP THỜI KHÓA BIỂU PHÙ HỢP VỚI NĂNG LỰC SINH VIÊN TS Nguyễn Thị Phương Trâm* TS Nguyễn Dũ* TÓM TẮT Vấn đề lập lịch được dùng để giải quyết nhiều ứng dụng trong thực tế cho nhiều lĩnh vực như lập lịch các nguồn tài nguyên trong sản xuất, xếp lịch các ca trực, xếp thời khóa biểu.., được nhiều nhà khoa học quan tâm. Bài toán xếp thời khóa biểu có vai trò quan trọng trong ngành giáo dục, vì nó ảnh hưởng trực tiếp đến con người, cơ sở vật chất,… của Trường học. Bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên cũng có vai trò quan trọng, vì ảnh hưởng trực tiếp đến quá trình học tập của sinh viên, cụ thể: nếu sinh viên tự xếp thời khóa biểu không đúng với năng lực của sinh viên, thì quá trình ra trường của sinh viên sẽ bị kéo dài và dẫn đến nhiều vấn đề phát sinh. Bài toán xếp thời khóa biểu phù hợp với năng lực sinh là dạng bài toán tối ưu tổ hợp. Do đó, trong bài báo này, chúng tôi đề xuất kết hợp giữa giải thuật local search và giải thuật metaheuristic để giải quyết bài toán trên, cụ thể: dùng giải thuật luyện thép (Simulated Annealing – SA) để tìm lời giải ban đầu, sau đó dùng các hành vi của đàn linh cửu đốm của giải thuật Spotted hyena optimizer (SHO) để tối ưu lời giải ban đầu để tìm ra một thời khóa biểu phù hợp với năng lực sinh viên, kết quả này có thể tối ưu quá trình học tập của sinh viên, như thời gian tốt nghiệp và cải thiện kết quả học tập của sinh viên. Từ khóa: bài toán xếp thời khóa biểu, bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên, bài toán tối ưu, giải thuật metaheuristic, giải thuật luyện thép (SA), giải thuật tối ưu đàn linh cẩu đốm (SHO) 1. Giới thiệu Cùng với quá trình đổi mới và hội nhập quốc tế sâu rộng hiện nay, giáo dục đại học Việt Nam cần được đổi mới trên cơ sở vẫn giữ được những nét đặc thù của giáo dục đại học trong nước, đồng thời tiệm cận được các chuẩn chung của thế giới. Hiện nay, hầu hết các trường đại học, cao đẳng đều tiến hành đổi mới mạnh mẽ nội dung chương trình và phương pháp dạy học theo hướng hội nhập quốc tế. Nội dung chương trình và giáo trình cần được tổ chức xây dựng và triển khai theo hướng mở (cho phép cập nhật thường xuyên về kiến thức trong và ngoài nước, sử dụng giáo trình, học liệu Trường Đại học Nông Lâm TPHCM *
232 KỶ YẾU HỘI THẢO KHOA HỌC trong nước hoặc ngoài nước một cách linh hoạt để giảng dạy cho người học), nội dung giảng dạy phải gắn chặt và phù hợp với yêu cầu thực tiễn của ngành nghề mà người học đang theo đuổi. Về phương pháp, cho phép sử dụng đa dạng các phương pháp dạy học theo nguyên tắc “lấy người học là trung tâm”, giảm tải tối đa giờ giảng trên lớp để người học có thời gian tự học và tự nghiên cứu. Hiện nay, các trường đều xây dựng chương trình đào tạo theo học chế tín chỉ, giảm số tín chỉ so với chương trình đào tạo niên chế, nhằm tăng khả năng tự học, tự nghiên cứu cho sinh viên, và sinh viên tự lên kế hoạch học tập cho mình trong suốt quá trình học đại học. Tất nhiên, các Trường cũng cần thường xuyên thực hiện việc kiểm tra, đánh giá khách quan, chặt chẽ để bảo đảm tính hiệu quả của việc dạy và học. Bên cạnh đó, các Trường đại học, cao đẳng đã đổi mới vai trò quản lý trong tổ chức giáo dục đại học trong điều kiện hội nhập quốc tế. Theo đó, về mặt pháp lý, cần tiếp tục bổ sung, hoàn thiện các quy định về pháp luật đối với các hoạt động giáo dục đại học trong điều kiện hội nhập quốc tế. Các trường đã áp dụng công nghệ thông tin vào quá trình quản lý thông qua các phần mềm: quản lý nhân sự, kế toán, phần mềm xếp thời khóa biểu, tạo các đề thi trắc nghiệm (Bui và cộng sự, 2018; Nguyen và cộng sự, 2019; Bui và cộng sự, 2020; Nguyen và cộng sự, 2021). Trong đó, phần mềm xếp thời khóa biểu để giải quyết bài toán xếp thời khóa biểu Giảng Viên là phần mềm luôn được các Trường quan tâm nhất. Tuy nhiên, với chương trình đào tạo theo học chế tín chỉ, sinh viên phải tự chủ động xếp thời khóa biểu dựa trên khung chương trình đào tạo, năng lực học tập của cá nhân và thời khóa biểu của Giảng viên. Bài toán sinh viên tự xếp thời khóa biểu cho cá nhân mình bằng phương pháp thủ công đã gặp một số bất cập nhất định, cụ thể: sinh viên xếp lịch các môn học dồn lại trong cùng một ngày để hạn chế thời gian đến trường học mà không quan tâm đến năng lực học tập, có tiếp thu tốt khối kiến thức được học trong cả ngày hôm đó hay không? Chính vấn đề này làm ảnh hưởng không nhỏ đến thời gian hoàn thành khóa học của sinh viên. Để khắc phục những bất cập cho sinh viên, bài toán xếp thời khóa biểu cho sinh viên dựa trên năng lực học tập của từng cá nhân là vấn đề cần quan tâm. Dựa vào những nhận định trên, bài toán xếp thời khóa biểu (TKB) có thể được phân thành hai loại: xếp thời khóa biểu Giảng Viên và xếp thời khóa biểu Sinh Viên. Bài toán xếp thời khóa biểu (TKB) nói chung rất phổ biến, nhưng rất khó khăn khi giải quyết trong thực tế, đó là bài toán tối ưu các ràng buộc, bài toán sắp xếp các lớp môn học ứng với nguồn lực hiện hữu của nhà trường (giảng viên, sinh viên, phòng học, lớp học, ca học,…). Hiện nay, công nghệ thông tin ngày càng phát triển mạnh mẽ và có ảnh hưởng sâu rộng đến tất cả mọi lĩnh vực đời sống, kinh tế, khoa học, xã hội. Nhiều công việc khó có thể giải quyết thỏa đáng bằng phương pháp thủ công thì khoa học máy tính có thể giải quyết một cách nhanh chóng và dễ dàng hơn. Đặc biệt là trong vấn đề xếp lịch, lập thời gian biểu thì sự hữu ích của nó càng thấy rõ. Trong đời sống ta có thể thấy rất nhiều công việc đòi hỏi phải được sắp xếp về thời gian, tài nguyên... một cách hợp lý sao cho đạt hiệu quả và thỏa mãn một số yêu cầu, ràng buộc nào đó như: xếp lịch trực y tá, xếp lịch nhà máy, xếp thời khóa biểu, xếp lịch cửa hàng...và thường khó đạt được giải pháp tối ưu. Với sự hỗ trợ của khoa học máy tính, người ta đã nghiên cứu và tìm hiểu rất nhiều phương pháp, kỹ thuật để nhằm giải quyết
CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 233 cho các vấn đề này nhưng vẫn chưa có kỹ thuật nào đủ tổng quát để có thể giải quyết được mọi bài toán. Từ đó, việc xếp lịch tự động đã được nhiều nhà khoa học quan tâm. Sắp xếp thời khóa biểu là bài toán NP-complete. Nhiều công bố khoa học đã tập trung vào việc giải quyết bài toán này và những giải pháp khả thi đã được giới thiệu ứng với từng tình huống của bài toán. Cho đến nay đã có rất nhiều cách tiếp cận khác nhau được đưa ra để giải quyết bài toán xếp thời khóa biểu cho các trường đại học, cao đẳng sử dụng các phương pháp tiến hóa: random, local search (Cimr & Hynek, 2018; June và cộng sự, 2018), metaheuristic algorithms (Nguyen & Nguyen, 2021)... Song tiếc thay tính đặc thù của từng bài toán như vậy đã dẫn đến khó áp dụng các giải pháp đó để lập thời khóa biểu của một trường cụ thể. Đến thời điểm hiện tại, đa số công trình nghiên cứu trong và ngoài nước phần lớn tập trung đưa ra nhiều giải pháp khác nhau để tối ưu hóa lời giải cho bài toán xếp thời khóa biểu Giảng Viên/ Giáo Viên. Do đó, trong bài báo này, chúng tôi đề xuất dùng giải thuật metaheuristic giải quyết bài toán xếp thời khóa biểu cho sinh viên. Hướng chúng tôi đề xuất cụ thể như sau: thứ nhất, chúng tôi đề xuất cải thiện giải thuật tối ưu đàn linh cẩu đốm (SHO) để tạo ra thời khóa biểu của sinh viên; thứ hai, chúng tôi dựa trên năng lực học tập của sinh viên ở học kỳ liền trước đó, để lựa chọn thời khóa biểu phù hợp với năng lực hiện tại của sinh viên. Kết quả này giúp sinh viên tối ưu thời gian khóa học của sinh viên (đúng thời gian quy định của khóa học). Phần hiện thực giải thuật và dữ liệu thực nghiệm được lấy tại Khoa Công Nghệ Thông Tin, Trường Đại học Nông Lâm Thành phố Hồ Chí Minh. 2. Các công trình liên quan Hiện tại, các công trình nghiên cứu trong và ngoài nước phần lớn tập trung đề xuất nhiều giải pháp khác nhau để tối ưu hóa lời giải cho bài toán xếp thời khóa biểu Giảng Viên, cụ thể: Phần mềm xếp thời khóa biểu của công ty Anh Quân dựa trên giải thuật tìm kiếm cục bộ (local search). Tuy nhiên, một trong những hạn chế của giải thuật này chính là lời giải của bài toán dễ rơi vào tối ưu cục bộ. Nói cách khác, lời giải không đạt đến trạng thái tối ưu toàn cục. Hiện nay, chương trình này đang được nhiều trường đại học ở khu vực Miền Nam sử dụng, trong đó có Trường Đại học Nông Lâm TP. HCM, tuy nhiên với kết quả đạt được như hiện nay thì cần sự can thiệp rất nhiều từ con người và chưa tối ưu được ràng buộc mềm, ví dụ: Giảng viên dạy 4 ca thực hành liên tục trong một ngày nhưng lại phân bổ trên 4 phòng khác nhau, chưa thuận tiện cho việc chuyển ca cho Giảng viên. Phần mềm xếp thời khóa biểu của EduMan dùng giải thuật GA để giải quyết bài toán, tuy nhiên với các thao tác: khởi tạo, đánh giá, lựa chọn, lai tạo, đột biến mà triển khai với tập dữ liệu lớn như ở Trường ĐH Nông Lâm TP. HCM thì tốn rất nhiều thời gian. Goh và cộng sự (2018) đã dùng giải thuật SA để xếp thời khóa biểu và xếp lịch thi, kết quả đã tìm được lời giải thỏa mãn yêu cầu của các bài toán. Tiếp đó, để nâng cao chất
234 KỶ YẾU HỘI THẢO KHOA HỌC lượng xếp thời khóa biểu nhóm tác giả Srisamutr và cộng sự (2018), Hosny và Fatima (2011) đã dùng giải thuật GA, Phuc và cộng sự (2011) dùng GA kết hợp giải thuật đàn Ong. Trong các công trình (Cimr & Hynek, 2018; Morrow và cộng sự, 2016; Koyuncu & Seçir, 2007; Almeida và cộng sự, 2015), (Goh và cộng sự, 2018; June và cộng sự, 2018, Srisamutr và cộng sự, 2018), các tác giả đã đề xuất hướng tiếp cận mới hơn, dùng giải thuật GA kết hợp với các phương pháp khác để nâng cải thiện thời gian thực hiện và chất lượng lời giải. Ngoài ra nhóm tác giả khác cũng dùng PSO (Foong & Rahim, 2013), ACO Mazlan và cộng sự (2018) để xếp thời khóa biểu và đạt được kết quả nhất định. Năm 2019, Nhóm tác giả Lemos và cộng sự (2019) đã kết hợp giữa lập trình tuyến tính và các thuật toán local search để tối ưu phòng học trong bài toán xếp thời khóa biểu. Đến năm 2020 và 2021, nhóm tác giả của Alghamdi và cộng sự (2020), Chen và cộng sự (2021) tóm tắt các công trình đã công bố kết quả tối ưu cho thời khóa biểu, mỗi công trình đều đạt được những thành công nhất định. Tuy nhiên, việc áp dụng một nghiên cứu chung cho tất cả các trường đại học vào thời điểm hiện tại là đều chưa khả thi, vì bài toán phụ thuộc nhiều vào nguồn lực con người và cơ sở vật chất. Do tình hình Covid-19 kéo dài, các nhà khoa học đã bắt đầu tập trung nghiên cứu tối ưu các vấn đề học tập cho sinh viên, như Samah và cộng sự (2022) dùng giải thuật tham lam (Greedy) tạo kế hoạch học tập cho sinh viên dựa vào kết quả khảo sát thông tin về sinh để xếp thời khóa biểu chung cho tất cả sinh viên. Năm 2020, Richards và Tsay (2020) dùng giải thuật Slack-Based lên kế hoạch học tập trong một học kỳ cho sinh viên, dựa vào những câu trả lời về thông tin sinh viên về sở thích cá nhân, các yêu cầu của môn học,...Tiếp đó, Albalooshi và Shatnawi (2021) đề xuất thay đổi thuật toán cây FP-Tree để tạo lịch học cho sinh viên dựa trên các sở thích của sinh viên và giảng viên trong quá trình đào tạo trước đó. Mỗi công trình đều đạt được những kết quả nhất định ở những trường đại học được chọn làm đối tượng nghiên cứu và triển khai ứng dụng. Song, khi áp dụng chung cho tất cả các trường đại học vẫn chưa khả thi. Chính điều này, đã thúc đẩy các nhà khoa học tiếp tục nghiên cứu để tìm ra tạo ra kế hoạch học tập tối ưu hơn cho sinh viên. Cụ thể, tại Trường Đại Học Nông Lâm Thành phố Hồ Chí Minh, căn theo quy chế giảng viên, giảng viên sẽ được phân công làm cố vấn học tập (CVHT) cho một lớp học, nhiệm vụ của CVHT là hướng dẫn sinh viên lên kế hoạch học tập (các môn học sẽ được đăng ký học) của từng học kỳ, dựa vào khung chương trình đào tạo vào năng lực học tập của sinh viên. Sinh viên căn cứ vào kế hoạch học tập đó, tự thực hiện đăng ký thời khóa biểu cho riêng mình. Tuy nhiên, việc sinh viên tự xếp thời khóa biểu các môn học có nhiều bất cập nhất định, như sinh viên không đánh giá được độ khó các môn học và năng lực của mình để sắp xếp thời gian lên lớp sao cho phù hợp. Thông thường, phần lớn sinh viên sẽ xếp dồn các môn học vào trong một ngày để hạn chế thời gian đến lớp ít nhất, điều này không khả thi, vì không phải ai cũng có thể tiếp thu những kiến thức các môn học trong cùng một ngày, dẫn đến kết quả học tập không như mong đợi, có thể điều này làm kéo dài thời gian ra trường thay vì ra trường đúng thời gian quy định của khóa học.
CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 235 Với những lý do trên, trong bài báo này, chúng tôi đề xuất dùng giải thuật SA để khởi tạo lời giải ban đầu cho SHO, thông qua các hành vi của đàn linh cửu đóm như tìm kiếm con mồi, bao vây,và tấn công con mồi để tìm được lời giải tối ưu cho bài toán xếp thời khóa biểu phù hợp với năng lực của sinh viên. Cấu trúc của bài báo được mô tả như sau: phần một là giới thiệu chung bài toán xếp thời khóa biểu, phần hai trình bày những công bố liên quan đến bài toán tối ưu tổ hợp. Tiếp đó, phần ba là đề xuất giải thuật kết hợp giữa SA và SHO để giải quyết bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên sao cho tối ưu; phần bốn phân tích kết quả dự kiến, và phần cuối là kết luận và hướng phát triển. 3. Đề xuất giải thuật SHOSA giải quyết bài toán xếp thời khóa biểu Sinh viên 3.1. Tìm kiếm cục bộ Tìm kiếm cục bộ là một họ những thủ thuật sử dụng trong việc giải các bài toán tìm kiếm và tối ưu hóa, dựa trên một vài biến thể của ý tưởng đơn giản. Ứng dụng của kỹ thuật này cho bài toán tối ưu hóa đã xuất hiện từ đầu thập niên 1960. Từ lúc đó việc quan tâm đến vấn đề này đã phát triển trên nhiều lĩnh vực của nghiên cứu thao tác, khoa học máy tính, và trí tuệ nhân tạo. Các giải thuật tìm kiếm cục bộ phải là giải pháp cuối cùng cho bài toán thấu đáo vì nó không bảo đảm tìm ra được một giải pháp khả thi hoặc tối ưu, chúng tìm kiếm một cách không hệ thống cho đến khi thỏa một điều kiện dừng nào đó. Tuy nhiên, những kỹ thuật này lại rất đáng chú ý vì tính hiệu quả và tính ứng dụng rộng rãi của nó. Các điểm bất lợi của tìm kiếm cục bộ cũng khá dễ nhận ra: tìm kiếm miền lân cận dựa trên các thuật toán là các heuristic cải thiện và do đó lệ thuộc nhiều vào giải pháp khởi đầu; Giải pháp kết quả chỉ mang tính tối ưu cục bộ như ngay cả trong Simulate Annealing (SA) và Tabu Search cũng vậy. Cho nên việc chọn lựa giải pháp khởi đầu là cực kỳ quan trọng vì một chọn lựa không phù hợp có thể dẫn đến một giải pháp với giá trị mục tiêu thấp và do đó tạo khoảng cách lớn với giải pháp tối ưu (Nguyen và cộng sự, 2021). Trong SHO (Dhiman & Kumar, 2017, 2018, 2019) khả năng chọn một cấu hình khởi tạo phù hợp được cực tiểu hóa do việc chọn lựa một số lượng lớn các giải pháp khởi tạo được phân bố trên khắp không gian tìm kiếm. Lúc đó, việc tìm kiếm được tập trung vào các khu vực nhiều hứa hẹn trong không gian tìm kiếm bằng cách liên tục thu hẹp các khu vực cho đến khi việc tìm kiếm được xem là đã đồng quy. Chính vì vậy sự kết hợp giữa hai thuật giải Local Search và SHO nó hỗ trợ cho nhau trong qua trình tìm kiếm để đạt được độ thích nghi cao hơn. 3.2. Giải thuật tối ưu đàn linh cẩu đốm (Spotted hyena optimizer (SHO)) Nhóm tác giả Dhiman và Kaur (2018) đã xây dựng một thuật toán tiến hóa mới dựa trên cách thức săn mồi của đàn linh cẩu đốm là SHO (Spotted hyena optimizer). Ý tưởng chính của thuật toán này bắt nguồn từ mối quan hệ xã hội giữa linh cẩu đốm và hành vi
236 KỶ YẾU HỘI THẢO KHOA HỌC hợp tác của chúng khi săn mồi. Thuật toán này gồm ba bước cơ bản: tìm kiếm con mồi, bao vây, và tấn công con mồi. Bao vây con mồi: Giải pháp tốt nhất hiện tại được coi là con mồi hoặc có vị trí gần với con mồi bởi vì không gian tìm kiếm không được biết trước. Nhóm các linh cẩu (tác nhân tìm kiếm) sẽ cố gắng cập nhật vị trí của nó sau khi con mồi được xác định. Sau đó linh cẩu dần tiến tới tấn công con mồi. ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗(𝑋𝑋𝑋𝑋) − 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋)� 𝐷𝐷𝐷𝐷ℎ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ (1) 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋 + 1) = ��⃗(𝑋𝑋𝑋𝑋) − 𝐸𝐸𝐸𝐸 . ��⃗ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ 𝐷𝐷𝐷𝐷ℎ ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗(𝑋𝑋𝑋𝑋) − 𝑃𝑃𝑃𝑃(𝑋𝑋𝑋𝑋)� 𝐷𝐷𝐷𝐷ℎ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ (2) ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗(𝑋𝑋𝑋𝑋) − 𝑃𝑃𝑃𝑃(𝑋𝑋𝑋𝑋)� 𝐷𝐷𝐷𝐷ℎ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗(𝑋𝑋𝑋𝑋) − 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋)� 𝐷𝐷𝐷𝐷ℎ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ Với ��⃗ = �𝐵𝐵𝐵𝐵diễn khoảng cách giữa con mồi và linh cẩu, x là lần lặp hiện tại,�𝐵𝐵𝐵𝐵 .và (𝑋𝑋𝑋𝑋)𝐷𝐷𝐷𝐷− 𝑃𝑃𝑃𝑃(𝑋𝑋𝑋𝑋)� 𝐷𝐷𝐷𝐷ℎ biểu . ��⃗(𝑋𝑋𝑋𝑋) − 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋)� �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ �⃗ ��⃗ ��⃗ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ ��⃗ 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋 + 1)𝐷𝐷𝐷𝐷= =𝑝𝑝𝑝𝑝 (𝑋𝑋𝑋𝑋) ��⃗ 𝐸𝐸𝐸𝐸 .là ℎ �⃗ ℎ 𝑃𝑃𝑃𝑃 − �⃗ 𝐷𝐷𝐷𝐷 𝑃𝑃𝑃𝑃 của 1) ℎcẩu.�𝐵𝐵𝐵𝐵 . ��⃗ 𝐸𝐸𝐸𝐸 . được tính các𝑃𝑃𝑃𝑃(𝑋𝑋𝑋𝑋số, 1) = ��⃗(𝑋𝑋𝑋𝑋) −trí. của con��⃗ P là vị trí (𝑋𝑋𝑋𝑋 +linh= =𝑝𝑝𝑝𝑝 (𝑋𝑋𝑋𝑋)và (𝑋𝑋𝑋𝑋)��⃗ 𝑃𝑃𝑃𝑃(𝑋𝑋𝑋𝑋)� như ��⃗ �⃗ + sau: 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 là vị 𝐸𝐸𝐸𝐸 ��⃗ �⃗ ��⃗ ��⃗ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ 𝐷𝐷𝐷𝐷ℎ �⃗ 𝐷𝐷𝐷𝐷 𝑃𝑃𝑃𝑃 − − 𝑃𝑃𝑃𝑃(𝑋𝑋𝑋𝑋 + 1) = ��⃗(𝑋𝑋𝑋𝑋) − 𝐸𝐸𝐸𝐸 . 𝐷𝐷𝐷𝐷ℎ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 ℎ �⃗ 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋 + 1) = 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 (𝑋𝑋𝑋𝑋) − 𝐸𝐸𝐸𝐸 . ��⃗ �⃗ �⃗ 𝐷𝐷𝐷𝐷ℎ 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋 + 1) = ��⃗(𝑋𝑋𝑋𝑋) − 𝐸𝐸𝐸𝐸 . ��⃗ �⃗ �⃗ 𝐷𝐷𝐷𝐷ℎ hệ mồi, �⃗ ��⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 𝐵𝐵𝐵𝐵 = 2. ��⃗ �⃗ 𝑟𝑟𝑟𝑟 𝑟𝑟𝑟𝑟1 𝐵𝐵𝐵𝐵 = 2. 𝑟𝑟𝑟𝑟 𝑟𝑟𝑟𝑟1 �⃗ ��⃗ �⃗ ��⃗ 𝐵𝐵𝐵𝐵 = 2. 𝑟𝑟𝑟𝑟 𝑟𝑟𝑟𝑟 𝐸𝐸𝐸𝐸 = 2. ��⃗ − �⃗ (4)1 𝑟𝑟𝑟𝑟 𝑑𝑑𝑑𝑑2 ℎ �⃗ (3) �⃗ 𝐸𝐸𝐸𝐸 = 2. 𝑟𝑟𝑟𝑟 𝑑𝑑𝑑𝑑2 − ℎ (4) �⃗ 𝐸𝐸𝐸𝐸 = 2.5��⃗ − ℎ (4) �⃗ 𝑟𝑟𝑟𝑟 𝑑𝑑𝑑𝑑2 �⃗ �⃗ = 5 − (𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼 𝑟𝑟𝑟𝑟 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 ∗ ( 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 𝑀𝑀𝑀𝑀 5 ℎ 𝐼𝐼𝐼𝐼 )) (4) ℎ = 5 − (𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼�⃗ 𝑟𝑟𝑟𝑟 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 ∗ ( 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 𝑀𝑀𝑀𝑀 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼)) 5 ℎ = 5 − (𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝑟𝑟𝑟𝑟 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼∗𝐼𝐼𝐼𝐼( 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 𝑀𝑀𝑀𝑀 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 )) (5) 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 ��⃗ �⃗ 𝐵𝐵𝐵𝐵 = 2. 𝑟𝑟𝑟𝑟 𝑟𝑟𝑟𝑟1 (5) (5) (5) Với ℎ giảm tuyến tính từ 5 tới 0 qua các lần = 2. ��⃗ =và ��⃗ − các (4) trị ngẫu nhiên �⃗ �⃗ �⃗ �⃗ 𝐵𝐵𝐵𝐵 lặp, 𝑟𝑟𝑟𝑟 𝑟𝑟𝑟𝑟1 2. 𝑟𝑟𝑟𝑟 𝑑𝑑𝑑𝑑2 là ℎ giá 𝐸𝐸𝐸𝐸 thuộc [0, 1]. �⃗ �⃗ ��⃗ �⃗ 5 ℎ = 5 − (𝐼𝐼𝐼𝐼𝑑𝑑𝑑𝑑𝐼𝐼𝐼𝐼 𝑟𝑟𝑟𝑟 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼ℎ𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 (4) 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 𝑀𝑀𝑀𝑀 𝐸𝐸𝐸𝐸 = 2. 𝑟𝑟𝑟𝑟 𝐼𝐼𝐼𝐼 2 − 𝐼𝐼𝐼𝐼 ∗ ( )) �⃗ Tìm kiếm con mồi: Linh cẩu đốm thường𝐼𝐼𝐼𝐼sống𝐼𝐼𝐼𝐼 và săn mồi theo)) (5) dựa trên sự ℎ = 5 − (𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝑟𝑟𝑟𝑟 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 ∗ ( 𝑀𝑀𝑀𝑀𝑀𝑀𝑀𝑀 𝑀𝑀𝑀𝑀 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 (5) 5 nhóm và tin tưởng ở các con linh cẩu khác về vị trí của con mồi. Để mô hình hóa cách tìm kiếm con 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 mồi của linh cẩu, tác giả đã xem xét linh cẩu tốt nhất trong đàn biết vị trí của con mồi, các linh cẩu khác dựa vào đó mà tạo thành nhóm và săn con mồi cũng như cập nhật lại vị trí của nó để tiến tới gần con mồi nhất. ��⃗ = �𝐵𝐵𝐵𝐵 ��⃗ − ��⃗� 𝐷𝐷𝐷𝐷ℎ �⃗ ��⃗ = �𝐵𝐵𝐵𝐵 .. ��⃗ − ��⃗� ��⃗ (6) �⃗ 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝐷𝐷𝐷𝐷ℎ ��⃗ = 𝑃𝑃𝑃𝑃ℎ . ��⃗𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃 � (6) (6) 𝐷𝐷𝐷𝐷ℎ �⃗ �𝐵𝐵𝐵𝐵 𝑃𝑃𝑃𝑃ℎ − 𝑘𝑘𝑘𝑘 ��⃗ = ��⃗ − 𝐸𝐸𝐸𝐸 ��⃗ ��⃗ = ��⃗ − 𝐸𝐸𝐸𝐸 .. ��⃗ ��⃗ �⃗ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 ��⃗𝑃𝑃𝑃𝑃ℎ ��⃗ −𝐷𝐷𝐷𝐷𝐸𝐸𝐸𝐸 . 𝐷𝐷𝐷𝐷 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃ℎ �⃗ 𝐷𝐷𝐷𝐷ℎ (6) 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 = 𝑃𝑃𝑃𝑃ℎ ℎ ℎ �⃗ ��⃗ = ��⃗ + ��⃗ + ⋯ + ��⃗ (8) 𝐶𝐶𝐶𝐶ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘 ��⃗ = ��⃗ + ��⃗ + ⋯ + ��⃗ (8) 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 (7) 𝐶𝐶𝐶𝐶ℎ ��⃗𝑃𝑃𝑃𝑃= ��⃗𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 ��⃗ 𝑃𝑃𝑃𝑃+ ��⃗ (7) (7) (7) ��⃗ = �⃗ ��⃗ − ��⃗ 𝐶𝐶𝐶𝐶ℎ 𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 + ��⃗ + ⋯ 𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 ��⃗(8)�⃗ 𝑃𝑃𝑃𝑃ℎ ��⃗ là vị�𝐵𝐵𝐵𝐵 . 𝑃𝑃𝑃𝑃ℎ nhất � linh(6) ��⃗ là vị trí của các .con− 𝑃𝑃𝑃𝑃 cẩu khác trong đàn và N là 𝐷𝐷𝐷𝐷 𝑃𝑃𝑃𝑃 𝐷𝐷𝐷𝐷ℎ = �𝐵𝐵𝐵𝐵 ��⃗ 𝑘𝑘 𝑃𝑃𝑃𝑃 � 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃 cẩu, 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃 Với ��⃗ℎlà vị trí tố nhất 𝑘𝑘𝑘𝑘của linh cẩu, ��⃗ là vị trí của các con linh𝑘𝑘𝑘𝑘cẩu khác trong đàn và N là Với Với ��⃗ là vị trí tố nhất của linh cẩu, ��⃗ là vị trí của các con linh cẩu khác trong đàn và N là 𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃 (8) số lượng đàn= ��⃗ cẩu, .được tính theo công thức sau: = ��⃗ − 𝐸𝐸𝐸𝐸 . ��⃗các con linh cẩu khác trong đàn lượng ��⃗ linh cẩu, được tính theo công thức sau: là 𝑃𝑃𝑃𝑃ℎ trí �⃗ 𝐷𝐷𝐷𝐷ℎ đàn linh − 𝐸𝐸𝐸𝐸 ��⃗ tố nhất (7) linh cẩu, ��⃗ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃 là �⃗ 𝐷𝐷𝐷𝐷ℎ 𝑃𝑃𝑃𝑃 (6) ℎ 𝑘𝑘𝑘𝑘 trí tố của linh số số lượng đànℎlinhvị trí được tính theo công thức 𝑘𝑘𝑘𝑘sau: vị ��⃗ = 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 + ��⃗ + ⋯ + ��⃗ (8) và N là��⃗ lượng đàn linh cẩu, được tính theo công��⃗ sau: ��⃗ 𝐶𝐶𝐶𝐶ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 ��⃗ = ��⃗ + 𝑃𝑃𝑃𝑃thức ⋯ + 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 (8) 𝐶𝐶𝐶𝐶ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘 𝑘𝑘 + Với của của (7) ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗ − ��⃗� �⃗ 𝑃𝑃𝑃𝑃ℎ cẩu, 𝐷𝐷𝐷𝐷ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 số í tố nhất của linh cẩu, ��⃗ làVớitríℎcủa vị tríconnhất𝑐𝑐𝑐𝑐của𝐼𝐼𝐼𝐼linh𝑛𝑛𝑛𝑛 (𝑃𝑃𝑃𝑃ℎ , ��⃗, ��⃗ ,của �𝑃𝑃𝑃𝑃ℎ con linh cẩu khác trong (9) và N là 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 vị ��⃗ là các tố linh cẩu kháccẩu, 𝑃𝑃𝑃𝑃ℎ+1 𝑃𝑃𝑃𝑃và N … , các + 𝑀𝑀𝑀𝑀�) 𝑃𝑃𝑃𝑃 𝑁𝑁𝑁𝑁 = 𝐼𝐼𝐼𝐼 𝑐𝑐𝑐𝑐 𝐼𝐼𝐼𝐼 𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛 ��⃗ ��⃗đànvị +2 là ��⃗ ��⃗ 𝑃𝑃𝑃𝑃 ��⃗ = ��⃗ − 𝐸𝐸𝐸𝐸 . ��⃗ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃ℎ �⃗ 𝐷𝐷𝐷𝐷ℎ (6) trong𝑘𝑘𝑘𝑘 là ℎ trí đàn , ��⃗, ��⃗ , … , �𝑃𝑃𝑃𝑃ℎ + 𝑀𝑀𝑀𝑀�) giá trị ngẫu nhiên thuộc [0.5, 1], nos là số các giải pháp, ��⃗ = ��⃗ + ��⃗ giải + ��⃗ 𝑃𝑃𝑃𝑃ℎ+1 𝑃𝑃𝑃𝑃ℎ+2 ��⃗ ��⃗ là 𝐶𝐶𝐶𝐶ℎ là nhóm𝑃𝑃𝑃𝑃các + ⋯ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 cẩu, được tính theo công thức sau: linh cẩu, được tính theo công thức sau: số lượng đàn (7) 𝑘𝑘𝑘𝑘 𝑘𝑘 Với ��⃗ là vị trí tố nhất của linh cẩu, ��⃗ là vị trí của các con l 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 Với pháp tối ưu. số lượng đàn linh cẩu, được tính theo công thức sau:
CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 237 ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗(𝑋𝑋𝑋𝑋) − 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋)� 𝐷𝐷𝐷𝐷 �⃗ 𝑃𝑃𝑃𝑃 �⃗ Để tìm kiếm con mồi, các linh cẩu thường di chuyển ra ℎ nhau để tìm kiếm và tấn 𝑝𝑝𝑝𝑝 công con mồi. Để thực hiện được việc này, các tác giả sử dụng (𝑋𝑋𝑋𝑋 + 1) = ��⃗nhiên 𝐸𝐸𝐸𝐸 . với các 𝑃𝑃𝑃𝑃 giá trị ngẫu𝑝𝑝𝑝𝑝 (𝑋𝑋𝑋𝑋) − �⃗ ��⃗ �⃗ 𝑃𝑃𝑃𝑃 𝐷𝐷𝐷𝐷ℎ xa giá trị lớn hơn 1 hoặc nhỏ hơn -1. Cơ chế này cho phép giải thuật SHO thoát khỏi tình ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗(𝑋𝑋𝑋𝑋) − 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋)� 𝐷𝐷𝐷𝐷ℎ �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 �⃗ trạng tối ưu cục bộ. 𝑃𝑃𝑃𝑃 trị của �⃗ 𝑃𝑃𝑃𝑃𝑝𝑝𝑝𝑝 đó, �⃗ ��⃗ giá(𝑋𝑋𝑋𝑋 + 1) ℎ . ��⃗(𝑋𝑋𝑋𝑋) − 𝐸𝐸𝐸𝐸 . cũng giảm theo sự thay đổi của h sau mỗi lần lặp �⃗ = Khi 𝐷𝐷𝐷𝐷ℎ Tấn công con mồi: Để mô hình hóa hành động tấn công con mồi, tác giả đã cho giảm �⃗ 𝑃𝑃𝑃𝑃 (𝑋𝑋𝑋𝑋 + 1) = ��⃗ 𝐶𝐶𝐶𝐶ℎ 𝑁𝑁𝑁𝑁 (10) �⃗ Với 𝑃𝑃𝑃𝑃(𝑋𝑋𝑋𝑋 + 1) sẽ làℎgiải pháp tốt nhất và các linh cẩu khác sẽ cập nhật lại vị trí của nó = ��⃗ 𝐶𝐶𝐶𝐶 𝑁𝑁𝑁𝑁 theo linh cẩu tìm kiếm tốt nhất (tức linh cẩu gần với con mồi nhất). Hiện tại, các nghiên cứu liên quan đến SHO vẫn đang dừng lại ở việc áp dụng trên các dữ liệu thử nghiệm. Chưa có công trình nào áp dụng vào giải quyết các bài toán cụ thể như xếp thời khóa biểu phù hợp với năng lực sinh viên. Vì thế, trong bài báo này nhóm nghiên cứu muốn áp dụng thuật toán này vào giải quyết bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên. Cho tập hợp X = {ℓ, 𝒸, 𝓉, 𝓇, o} là tập thời khóa biểu của môn học đã được xếp cho kỳ 3.3. Định nghĩa bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên của CVHT, dùng để đăng ký học cho học kỳ tới. Z = {𝓈, 𝒸, 𝓉, 𝓇} là một thời khóa biểu của kế tiếp cho giảng viên, và Y = {𝒸} là tập các môn học của sinh viên đã chọn dưới sự tư vấn sinh viên dựa trên tập X và Y. – ℓ: hông tin về giảng viên gồm: mã giảng viên, tên giảng viên Trong đó: – 𝒸: thông tin về môn học gồm: mã môn học, tên môn học, độ khó môn học t – 𝓉: thời gian giảng dạy môn học gồm: thứ (từ thứ 2 đến thứ 7), phân ca (một ngày – 𝓇: phòng học gồm: mã phòng học, tên phòng học có 4 phân ca) – o: ố lượng của một lớp môn học – 𝓈: thông tin về sinh viên, gồm: mã sinh viên, tên sinh viên, điểm trung bình của học s kỳ gần nhất (với những trường hợp đặc biệt bài toán sẽ xét thêm điểm của môn học trước/môn học tiên quyết cùng với điểm trung bình học kỳ gần khi đánh giá năng lực sinh viên, để đưa ra kết quả xếp thời khoá biểu chính xác hơn, ví dụ trường hợp xét cho sinh viên năm nhất,...). Xếp thời khóa biểu sinh viên là bài toán xếp thời khóa biểu (TKB), về bản chất sẽ có hai loại ràng buộc cần phân biệt: Ràng buộc cứng là những ràng buộc mà một TKB bắt
238 KỶ YẾU HỘI THẢO KHOA HỌC buộc phải thỏa; Ràng buộc mềm là những ràng buộc mà TKB lập ra cần đáp ứng càng nhiều càng tốt. Những giải pháp xếp TKB không vi phạm các ràng buộc cứng gọi là những giải pháp khả thi. Chất lượng của một giải pháp khả thi được phản ánh qua mức độ đáp ứng các ràng buộc mềm của giải pháp đó. Do đó, để Z là một thời khóa biểu phù hợp với năng lực của sinh viên, Z phải thỏa mãn ràng buộc cứng, và số phân ca lên lớp trong một ngày của sinh viên phải phù hợp với năng lực học tập của mỗi cá nhân. Nghĩa là, hàm đánh giá độ thích ghi của Z có giá trị nhỏ nhất. 3.4. Hàm đánh giá độ thích nghi Với hướng tiếp cận bài toán như phân tích trên, bài báo đề xuất hàm đánh giá đa mục tiêu cho lựa chọn thời khóa biểu tối ưu nhất (TKBNLSV), cụ thể: maximum(f) f = f1(n) + f2(m) Giả sử bài toán gồm: n ràng buộc cứng và m ràng buộc mềm, Hci là số ràng buộc cứng đáp ứng được, với i = 1,…, n. Sci là số ràng buộc mềm j = 1,…, m Chúng ta tính giá trị của ràng buộc cứng f1(n) như sau: f1(n) = ∑n Hci i=1 (11) Tương tự, chúng ta tính giá trị f2(m) của ràng buộc mềm, f2(m) = α∑m Scj j=1 (11) Do đó, nếu thời khóa biểu sinh viên nào có số ràng buộc đáp ứng được càng nhiều, thì giá trị độ thích ghi f1(n) và f2(m) càng cao. Giải thuật SA là được đánh giá là thuật toán cho kết quả tốt nhất trong các kỹ thuật tìm kiếm cục bộ, vì SA có thể chấp nhận những lời giải tốt và xấu làm phong phú lời giải, và điều này giúp thuật toán thoát khỏi tối ưu cục bộ. Do đó, SA sẽ tìm được lời giải tốt, với độ thích ghi f1(n) cao nhất hoặc hoặc tìm tời khi giá trị f1(n) chưa cải thiện sau 1.000 thế hệ. Giải thuật SHO được thiết kế để tìm ra độ thích ghi cao nhất. Đây là tìm kiếm metaheuristic, vì thế chúng ta sẽ tìm kiếm cho tới khi nào tìm được giải pháp tốt nhất f2(m) hoặc tìm tời khi giá trị f2(m) chưa cải thiện sau 1000 thế hệ. 3.5. Đề xuất kết hợp giải thuật SHO và SA cho bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên Trong phần này, bài báo này sẽ trình bày sự kết hợp giữa giải thuật tìm kiếm cục bộ SA với thuật giải SHO cho việc xếp thời khóa biểu phù hợp với năng lực sinh viên học trong một học kỳ tại Trường ĐH Nông Lâm TPHCM thỏa các yêu cầu sau: 3.5.1. Ràng buộc cứng – Các phân ca xung đột nhau không được diễn ra trong thời gian phủ lấp nhau.
CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 239 – Các phân ca phải được học trọn vẹn trong một buổi. – Tại một thời điểm một phòng chỉ được gán cho một phân ca duy nhất. – Các phân ca phải được học tại phòng học tương ứng. – Số lượng sinh viên đăng ký đúng số chỗ mở cho mỗi môn học 3.5.2. Ràng buộc mềm – Rút ngắn số buổi đến trường học của sinh viên nhưng phải phù hợp với năng lực của chúng, cụ thể: sinh viên có học lực trung bình hoặc trung bình khá, không được xếp học một ngày 4 phân ca, vì với lực năng lực hạn chế sinh viên sẽ tiếp thu không tốt lượng kiến thức các môn học do giảng viên truyền đạt trong một ngày, làm ảnh hưởng đến kết quà thi, dẫn đến có thể kéo dài thời gian ra trường của sinh viên. – Một ngày không được xếp quá hai môn học có độ khó cao, nghĩa là một ngày có thể có hai môn học khó và các môn học có độ khó bình thường tùy theo năng lực học tập của sinh viên. – Thời khóa biểu của một sinh viên các ca học phải liên tục, hạn chế ca trống xen giữa. Hạn chế xếp thời khóa biểu học vào thứ bảy và chủ nhật. 3.5.3. Đề xuất cách giải quyết bài toán xếp thời khóa biểu phù với hợp năng lực sinh viên Trong bài báo này, chúng tôi dùng thuật toán SA để khởi tạo tập lời giải ban đầu tốt nhất, nghĩa là giá trị độ thích ghi của hàm f1(n) đạt giá trị lớn nhất. Sau đó, chúng tôi dựa trên tập lời giải này, dùng các kỹ thuật chính của giải thuật SHO để tìm lời giải tối ưu phù hợp với năng lực của sinh viên, nghĩa là giá trị độ thích ghi của hàm f2(m) càng lớn càng tốt. 3.5.3.1. Khởi tạo lời giải ban đầu Việc chọn lựa giải pháp khởi đầu là cực kỳ quan trọng vì một chọn lựa không phù hợp có thể dẫn đến một giải pháp với giá trị mục tiêu thấp và do đó tạo khoảng cách lớn với giải pháp tối ưu. Xây dựng thời khóa biểu khả thi ban đầu nhằm thỏa mãn các ràng buộc cứng. Giải thuật để tối ưu ràng buộc cứng được sử dụng trong bài báo này là giải thuật SA. Các bước của thuật toán SA vào bài toán xếp thời khóa biểu sinh viên (TKBSV), được mô tả như sau: Thuật toán 1: giải thuật SA khởi tạo TKBSV ban đầu - Đầu vào: danh sách các môn học đã xếp thời khóa biểu cho giảng viên, danh sách các môn học sinh viên đã chọn cho kỳ. - Đầu ra: thời khóa biểu sinh viên tối ưu
240 KỶ YẾU HỘI THẢO KHOA HỌC Thuật toán 1: giải thuật SA khởi tạo TKBSV ban đầu Khởi tạo các hệ số ban đầu của thuật toán SA Bước 1: Dùng giải thuật random để khởi tạo TKBSV ban đầu. Bước 2: Tính độ thích nghi của TKBSV theo công thức (11). Bước 3: Đánh giá TKBSV, nếu gặp điều kiện dừng kết thúc. Bước 4: Tìm TKBSV lân cận dựa trên TKBSV hiện tại bằng cách thay đổi ngẫu nhiên vị trí (ngày, phòng, ca) các môn học sinh viên đã chọn của từng TKBSV hướng tới thời khóa biểu tốt nhất. Kiểm tra TKBSV có vi phạm ràng buộc cứng nào hay không và điều chỉnh nó. Bước 5: So sánh TKBSV lân cận với TKBSV hiện tại dựa trên độ thích ghi, nếu nó có độ thích tốt hơn TKBSV hiện tại, cập nhật. Nếu không cải thiện, xét điều kiện sác xuất chấp nhận, dựa vào đó để chọn TKBSV lân cận là TKBSV mới. Bước 6: Lặp lại Bước 3, cho tới khi tìm được TKBSV tối ưu ràng buộc cứng. 3.5.3.2. Dựa trên thời khóa biểu thỏa mãn ràng buộc cứng, để tối ưu thời khóa biểu phù hợp với năng lực sinh viên (TKBNLSV) Như đã trình bày ở trên, giải thuật tối ưu đa mục tiêu SHO được đề xuất bởi Dhiman và Kaur (2018) dựa trên cách thức săn mồi của đàn linh cẩu. Cho đến nay, các kết quả nghiên cứu dựa trên giải thuật SHO đã cho thấy tính hiệu quả của nó so với các giải thuật tối ưu khác nhau PSO, GA,... thậm chí là đối với các bài toán có nhiều loại ràng buộc khác nhau. Trong bài báo này, chúng tôi đề xuất áp dụng giải thuật SHO để tìm ra thứ tự sắp xếp thời khóa biểu có độ thích nghi tốt nhất. Các bước áp dụng thuật toán SHO vào bài toán được mô tả cụ thể như sau: Thuật toán 2: Kết hợp giải thuật SA với SHO - Đầu vào: quần thể con linh cẩu đốm là danh sách TKBSV ban đầu P = (1.2.3...n) được khởi tạo bằng giải thuật SA Khởi tạo các tham sốℎban�𝐵𝐵𝐵𝐵 . ��⃗của��⃗� thuật SHO ��⃗ = đầuℎ − 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝐷𝐷𝐷𝐷 �⃗ 𝑃𝑃𝑃𝑃 - Đầu ra: thời khóa biểu phù hợp năng lực sinh viên (TKBNLSV) Bước 1: Chọn con mồi ( ��⃗ ) –𝐸𝐸𝐸𝐸là𝐷𝐷𝐷𝐷một TKBSV với độ tối ưu có thể nhỏ hơn so với các ��⃗ = 𝑃𝑃𝑃𝑃ℎ − �⃗ . ��⃗ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 giải (6) ℎ ��⃗ ��⃗ ��⃗ ��⃗ 𝐶𝐶𝐶𝐶ℎ = 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 + 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘 + ⋯ + 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 (7) Bước 2: Tính độ thích nghi của từng TKBSV bằng công��⃗ − ��⃗� ��⃗ = �𝐵𝐵𝐵𝐵 . 𝑃𝑃𝑃𝑃thức 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝐷𝐷𝐷𝐷ℎ �⃗ ℎ TKBSV khác trong quần thể. Với ��⃗ là vị trí tố nhất của linh cẩu, ��⃗ là vị trí của các con linh cẩu khác trong đàn và N là 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 (8) Bước 3: Xác tính TKBSV tốt nhất trong quần��⃗ =( ��⃗ ). 𝐸𝐸𝐸𝐸 . ��⃗ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃ℎ − �⃗ 𝐷𝐷𝐷𝐷ℎ (12) (6) ��⃗ = ��⃗ + ��⃗ + ⋯ + ��⃗ 𝐶𝐶𝐶𝐶ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 ố lượng đàn linh cẩu, đượcđịnh theo công thức sau: thể (7) Với ��⃗ là vị trí tố nhất của linh cẩu, ��⃗ là vị trí của các con linh cẩu khác trong đàn và N là 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 (8) số lượng đàn linh cẩu, được tính theo công thức sau:
��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗ − ��⃗� 𝐷𝐷𝐷𝐷ℎ �⃗ 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 241 ��⃗ = ��⃗ − 𝐸𝐸𝐸𝐸 . ��⃗ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃ℎ �⃗ 𝐷𝐷𝐷𝐷ℎ (6) ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗ − ��⃗� 𝐷𝐷𝐷𝐷 �⃗ 𝑃𝑃𝑃𝑃 𝑃𝑃𝑃𝑃 Bước 4: Xác định nhóm các giải pháp tối ưu ( ��⃗ )= ��⃗ +dựa 𝑘𝑘 + ⋯ + ��⃗ nhất ở thời 𝐶𝐶𝐶𝐶ℎ khác ��⃗ TKBSV𝑘𝑘𝑘𝑘𝑘 (8) Thuật toán 2: Kết hợp giải thuật SA với SHO 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 vào 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 tốt (7) ℎ ℎ 𝑘𝑘𝑘𝑘 điểm hiện𝑃𝑃𝑃𝑃tại ( ��⃗ ). 𝐸𝐸𝐸𝐸 . ��⃗ ��⃗ ��⃗ = 𝑃𝑃𝑃𝑃ℎ − �⃗ 𝐷𝐷𝐷𝐷ℎ (6) ��⃗ Với 𝑃𝑃𝑃𝑃ℎ là vị ��⃗ tố nhất ��⃗ linh cẩu, 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 là vị trí của các con linh cẩu khác trong đàn v 𝐷𝐷𝐷𝐷ℎ = �𝐵𝐵𝐵𝐵 . 𝑃𝑃𝑃𝑃ℎ − ��⃗� �⃗ của 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘 ��⃗ = ��⃗ + vị trí (ngày, ��⃗ cẩu, được tính theo công thức sau: Bước 5: Thay𝑘𝑘𝑘𝑘đổi ��⃗ + ⋯đànphòng, ca) các phân công giảng dạy của từng TKBSV hướng 𝐶𝐶𝐶𝐶ℎ 𝑃𝑃𝑃𝑃 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘 số lượng + 𝑃𝑃𝑃𝑃linh (8) (7) trí 𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 tới thời khóa biểu tốt nhất tìm được ( ��⃗ ). Kiểm tra TKBSV có vi phạm ràng buộc cứng ��⃗ = 𝑃𝑃𝑃𝑃 − 𝐸𝐸𝐸𝐸 . ��⃗ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 �⃗ 𝐷𝐷𝐷𝐷ℎ (6) à vị trí tố nhất của linh cẩu, ��⃗ là vị trí của các con linhℎcẩu khác trong đàn và N là 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗ − ��⃗� �⃗ 𝑃𝑃𝑃𝑃ℎ nào hay không và điều chỉnh ��⃗ ��⃗ ��⃗ 𝐷𝐷𝐷𝐷ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝐶𝐶𝐶𝐶ℎ = 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 + 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘𝑘𝑘 + ⋯��⃗ ��⃗�⃗ ��⃗ ��⃗ + 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘 (8) (7) 𝐷𝐷𝐷𝐷ℎ = �𝐵𝐵𝐵𝐵 . 𝑃𝑃𝑃𝑃ℎ − 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 � Bước 6: ��⃗ lại giá trị tối ưu của từng TKBSV và cập nhật TKBSV tốt nhất ( ��⃗ ) nếu��⃗ ��⃗ = 𝑃𝑃𝑃𝑃ℎ − 𝐸𝐸𝐸𝐸 . 𝐷𝐷𝐷𝐷 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 �⃗ có nó. (6) Với 𝑃𝑃𝑃𝑃ℎ là vị trí tố nhất của linh cẩu, ��⃗ là vị trí của các ��⃗ linh cẩu khác trong đàn và N ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 n linh cẩu, được tính theo công thức sau: ��⃗ = 𝑃𝑃𝑃𝑃ℎ − 𝐸𝐸𝐸𝐸 . 𝐷𝐷𝐷𝐷ℎ 𝑃𝑃𝑃𝑃 con �⃗ ��⃗ (6) ��⃗ =(7)𝑘𝑘𝑘𝑘 + ��⃗ + ⋯ + ��⃗ ( 𝐶𝐶𝐶𝐶ℎ ��⃗ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘 𝑃𝑃𝑃𝑃 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘 Tính (7) số lượng đàn linh cẩu, được tính theo công thức sau: 𝑘𝑘𝑘𝑘 ��⃗ = �𝐵𝐵𝐵𝐵 . ��⃗ − ��⃗� 𝐷𝐷𝐷𝐷ℎ �⃗ 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 là Bước 7: Cập nhật lại nhóm giải pháp tối ưu ( ��⃗ )= ��⃗ + ��⃗ + ⋯ +tốt𝑘𝑘𝑘𝑘 nhất ở thời điểm 𝐶𝐶𝐶𝐶ℎ dựa trên TKBSV ��⃗ (8) 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑘𝑘 𝑃𝑃𝑃𝑃 𝑘𝑘𝑘𝑘𝑘 giải pháp tốt hơn giải pháp tối ưu trước đó. Với ��⃗ là vị trí tố nhất của linh cẩu, ��⃗ là vị trí của các con lin 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 hiện𝑃𝑃𝑃𝑃tại ( ��⃗ ). 𝐸𝐸𝐸𝐸 . ��⃗ ��⃗ = 𝑃𝑃𝑃𝑃ℎ − �⃗ 𝐷𝐷𝐷𝐷ℎ (6) 𝑘𝑘𝑘𝑘 Với ��⃗ là vị trí tố nhất của linh cẩu, ��⃗ là vị trí của các con linhthức khác trong đàn và 𝑃𝑃𝑃𝑃ℎ 𝑃𝑃𝑃𝑃 số lượng đàn linh𝑘𝑘𝑘𝑘cẩu, được tính theo công cẩu sau: ��⃗ = ��⃗ + ��⃗ + lượng𝑘𝑘𝑘𝑘đàn (8)cẩu, được trả theo công thức sau: Bước 8: Nếu 𝑘𝑘𝑘𝑘tiêusố⋯ + ��⃗ linhthỏa mãn, tính về TKBSV tốt nhất tìm được đây chính là 𝐶𝐶𝐶𝐶ℎ 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃 𝑘𝑘 chí dừng𝑘𝑘𝑘𝑘𝑘 𝑃𝑃𝑃𝑃 được (7) í tố nhất của linh cẩu, ��⃗ là vị trí của các con linh cẩu khác trong đàn và N là 𝑃𝑃𝑃𝑃𝑘𝑘𝑘𝑘 thời khóa biểu phù hợp với năng lực sinh viên (KTBNLSV). Nếu không, quay lại Bước 4. cẩu, được tính theo công thức sau: 4. Phân tích kết quả dự kiến Trong phần này chúng tôi trình bày môi trường thực nghiệm với tập dữ liệu tại Khoa Công nghệ Thông tin, Trường Đại học Nông Lâm TPHCM, và kết quả dự kiến của thuật toán mà bài báo đã trình bày trọng phần 3.5. 4.1. Xây dựng môi trường sẽ triển khai thực nghiệm 4.1.1. Tham số giải thuật Bảng 1. Các tham số của giải thuật Các tham số của giải thuật SA Các hệ số - T = 0.001 - α = 0.999 Số lần lặp 1000 Các tham số của giải thuật SHO �⃗ ℎ : [5,0] Kích thước quần thể ban đầu 30 𝑁𝑁𝑁𝑁 = 𝑐𝑐𝑐𝑐 𝐼𝐼𝐼𝐼 𝑐𝑐𝑐𝑐 𝐼𝐼𝐼𝐼 𝐼𝐼𝐼𝐼 𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛 𝑛𝑛𝑛𝑛 (𝑃𝑃𝑃𝑃ℎ , ��⃗, ��⃗ , … , �𝑃𝑃𝑃𝑃ℎ + 𝑀𝑀𝑀𝑀�)[0.5, 1] ��⃗ 𝑃𝑃𝑃𝑃ℎ+1 𝑃𝑃𝑃𝑃ℎ+2 ��⃗ ��⃗ : Các hệ số Số lần lặp 1000 4.1.2. Dữ liệu thực nghiệm – Thời khóa biểu của giảng viên, gồm các thông tin: mã môn học, tên môn học, mã lớp, nhóm môn học, số chỗ, phòng học, tiết bắt đầu, số tiết dạy, mã giảng viên, và tên giảng viên.
242 KỶ YẾU HỘI THẢO KHOA HỌC – Các môn học của sinh viên chuẩn bị học trong học kỳ tới, dưới sự tư vấn của hệ thống Cố Vấn Học Tập, gồm các thông tin: mã môn học, tên môn học, độ khó môn học. Trong bài báo này, chúng tôi sử dụng cách đánh giá độ khó môn học dựa trên khung chương trình đào tạo, có ba cấp độ từ 1- 3, cụ thể tại Bảng 2. Bảng 2. Độ khó môn học STT Nhóm môn học Độ khó 1 Khối kiến thức đại cương 1 2 Khối cơ sở ngành 2 3 Khối chuyên ngành 3 – Thông tin về sinh viên, gồm: mã lớp, mã sinh viên, họ tên, điểm trung bình của học kỳ gần nhất. 4.2. Phân tích các kết quả dự kiến 4.2.1. Đề xuất cách đánh giá hàm đa mục tiêu trong bài toán xếp thời khóa biểu phù hợp với năng lực sinh viên Chúng tôi đánh giá hàm đa mục tiêu cho bài toán như mô tả sau: f = f1(n) + αf2(m) Trong đó, max(f1(n)) → 50: thỏa mãn tất cả ràng buộc cứng max(f2(m)) → 50: tối ưu các ràng buộc mềm α hệ số năng lực của từng sinh viên dựa vào điểm trung bình gần nhất, cụ thể được miêu tả trong Bảng 3. Bảng 3. Hệ số năng lực Điểm trung bình Xếp loại Hệ số năng lực (α) 5.0 – 6.4 TRUNG BÌNH 0.5 6.5 – 6.9 TRUNG BÌNH KHÁ 0.6 7.0-7.9 KHÁ 0.7 >=8.0 GIỎI 1 Qua đó, cho thấy rằng giá trị hàm đa mục tiêu của càng lớn thì lời giải càng tối ưu. – Giai đoạn 1: tìm ra lời giải thỏa mãn ràng buộc cứng nên giá trị hàm mục tiêu đều đạt giá trị tối đa là 50. Các ràng buộc cứng trong bài toán bao gồm: • Các phân ca xung đột nhau không được diễn ra trong thời gian phủ lấp nhau. • Các phân ca phải được học trọn vẹn trong một buổi. • Tại một thời điểm một phòng chỉ được gán cho một phân ca duy nhất.
CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 243 • Các phân ca phải được học tại phòng học tương ứng. • Số lượng sinh viên đăng ký đúng số chỗ mở cho mỗi môn học – Giai đoạn 2: Tối ưu hóa ràng buộc mềm dựa trên những lời giải thỏa mãn ràng buộc cứng, giá trị ràng buộc mềm càng cao thì lời giải càng tối ưu, giá trị tối đa là 50. • Các phân ca trong ngày không liên tục, tương ứng bị trừ 10. • Số buổi học của sinh viên phải trên trường 6 ngày (thứ 2 đến thứ 7), tương ứng bị trừ 20. • Trong một ngày sinh viên học từ 3 môn học có độ khó cao (level 3) trở lên, tương ứng bị trừ 10. • Một tuần có hơn 3 ngày học suốt 4 ca trong một ngày, tương ứng bị trừ 10. 4.2.2. Kết quả sinh viên tự xếp TKB Trong mục này, chúng tôi đưa ra 6 kết quả tự xếp thời khóa biểu sinh viên, tại Bảng 4, cho thấy sinh viên xếp thời gian đến trường học quá suốt tuần (từ thứ 2 đến thứ 6) của mã số 19130145, Nguyễn Thu Nga và mã số 18130192, Huỳnh Ái Quốc, vấn đề này có thể làm ảnh hưởng đến khả thời gian tự học – tự nghiên cứu của sinh viên. Đặc biệt sinh viên Nguyễn Thu Nga, xếp lịch học trong suốt một tuần, trong đó có 2 ngày học suốt từ tiết 1 đến tiết 12, ảnh hưởng đến khả năng tiếp thu kiến thức trong một ngày của sinh viên. Các sinh viên còn lại xếp lịch học trong một ngày chưa tốt, cụ thể học một môn học ở ca 1, xong sinh viên ngồi đợi tới ca 4 học môn thứ 2 trong một ngày. Tại Bảng 5, dựa vào kết quả thống kê dựa trên thời khóa biểu tự xếp của sinh viên, các giá trị của hàm đa mục tiêu của f chưa đạt giá trị tối ưu, do hạn chế việc đạt được các tiêu chuẩn của ràng buộc mềm của bài toán.
Bảng 4. Kết quả tự xếp thời khóa biểu của sinh viên 244 Mã số sinh viên 19130145 Mã lớp DH19DTC Tên sinh viên Nguyễn Thu Nga Điểm TB 7.25 Mã MH Tên MH NMH STC Mã lớp Thứ Tiết BD ST Phòng CBGD Level DH19DTC, 214492 Máy học 1 4 Ba 7 3 PV333 695 3 DH19DTC DH19DTC, 214492 Máy học 1 4 Ba 4 3 P4 695 3 DH19DTC DH21DTA, 214331 Lập trình nâng cao 5 4 Ba 10 3 P2 1017 2 DH21DTA DH19DTC, 214370 Nhập môn công nghệ phần mềm 3 4 Bảy 1 3 RD203 787 2 KỶ YẾU HỘI THẢO KHOA HỌC DH19DTC DH19DTC, 214370 Nhập môn công nghệ phần mềm 3 4 Bảy 7 3 P3 787 2 DH19DTC DH20DTA, 214351 Lý thuyết đồ thị 1 4 Hai 1 3 RD200 1017 2 DH20DTA DH19DTC, 214388 Lập trình Front End 1 4 Hai 10 3 TV101 92 3 DH19DTC DH20DTB, 214251 Hệ điều hành nâng cao 21 3 Hai 4 3 P2 372 2 DH20DTB DH19DTB, 214461 Phân tích và thiết kế hệ thống thông tin 2 4 Hai 7 3 P4 641 2 DH19DTB DH20DTB, 214251 Hệ điều hành nâng cao 21 3 Năm 1 3 PV325 372 2 DH20DTB 202502 Giáo dục thể chất 2* 65 1 DH21CC Năm 7 3 NTD7 758 1 DH21DTA, 214331 Lập trình nâng cao 5 4 Năm 10 3 TV101 1017 2 DH21DTA DH20DTA, 214351 Lý thuyết đồ thị 1 4 Năm 4 3 P3 1017 2 DH20DTA
DH19DTB, 214461 Phân tích và thiết kế hệ thống thông tin 2 4 Sáu 7 3 RD203 641 2 DH19DTB DH19DTC, 214388 Lập trình Front End 1 4 Tư 1 3 P4 92 3 DH19DTC Mã số sinh viên 20130215 Mã lớp DH20DTC Tên sinh viên Nguyễn Đắc Cường Điểm TB 7.75 Mã MH Tên MH NMH STC Mã lớp Thứ Tiết BD ST Phòng CBGD Level DH20DTA, 214251 Hệ điều hành nâng cao 20 3 Ba 1 3 PV233 372 2 DH20DTA DH20DTA, 214442 Nhập môn cơ sở dữ liệu 1 4 Ba 4 3 P1 T800 2 DH20DTA DH20DTA, 214351 Lý thuyết đồ thị 1 4 Hai 1 3 RD200 1017 2 DH20DTA DH20DTA, 214442 Nhập môn cơ sở dữ liệu 1 4 Hai 4 3 TV101 T800 DH20DTA 2 200107 Tư tưởng Hồ Chí Minh 24 2 DH20SM Hai 10 3 RD100 112 1 DH20DTA, 214353 Đồ họa máy tính 20 3 Hai 7 3 TH.P03 671 3 DH20DTA DH20DTB, 214352 Thiết kế hướng đối tượng 2 4 Năm 4 3 RD104 603 2 DH20DTB DH20DTA, 214351 Lý thuyết đồ thị 1 4 Năm 1 3 P3 1017 2 DH20DTA DH20DTB, 214352 Thiết kế hướng đối tượng 2 4 Năm 10 3 P2 603 2 DH20DTB DH20DTA, 214353 Đồ họa máy tính 20 3 Tư 4 3 RD306 671 3 DH20DTA CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ DH20DTA, 214251 Hệ điều hành nâng cao 20 3 Tư 1 3 P3 372 2 DH20DTA 245
Mã số sinh viên 20130074 Mã lớp DH20DTB 246 Tên sinh viên Huỳnh Quốc Nam Điểm TB 7.34 Mã MH Tên MH NMH STC Mã lớp Thứ Tiết BD ST Phòng CBGD Level DH20DTA, 214251 Hệ điều hành nâng cao 20 3 Ba 1 3 PV233 372 2 DH20DTA DH20DTA, 214442 Nhập môn cơ sở dữ liệu 1 4 Ba 4 3 P1 T800 2 DH20DTA DH20DTA, 214351 Lý thuyết đồ thị 1 4 Hai 1 3 RD200 1017 2 DH20DTA DH20DTA, 214442 Nhập môn cơ sở dữ liệu 1 4 Hai 4 3 TV101 T800 DH20DTA 2 KỶ YẾU HỘI THẢO KHOA HỌC 200107 Tư tưởng Hồ Chí Minh 11 2 DH20CK Hai 7 3 TV103 422 1 DH20DTB, 214352 Thiết kế hướng đối tượng 2 4 Năm 4 3 RD104 603 2 DH20DTB DH20DTA, 214351 Lý thuyết đồ thị 1 4 Năm 1 3 P3 1017 2 DH20DTA DH20DTB, 214352 Thiết kế hướng đối tượng 2 4 Năm 10 3 P2 603 2 DH20DTB DH20DTA, 214353 Đồ họa máy tính 20 3 Tư 4 3 RD306 671 3 DH20DTA DH20DTA, 214251 Hệ điều hành nâng cao 20 3 Tư 1 3 P3 372 2 DH20DTA DH20DTA, 214353 Đồ họa máy tính 20 3 Tư 7 3 P3 671 3 DH20DTA
Mã số sinh viên 19130158 Mã lớp DH19DTB Tên sinh viên Nguyễn Thành Nhân Điểm TB 7.58 Mã MH Tên MH NMH STC Mã lớp Thứ Tiết BD ST Phòng CBGD Level DH19DTC, 214492 Máy học 1 4 Ba 7 3 PV333 695 3 DH19DTC DH19DTC, 214492 Máy học 1 4 Ba 4 3 P4 695 3 DH19DTC DH21DTA, 214331 Lập trình nâng cao 5 4 Ba 10 3 P2 1017 2 DH21DTA DH19DTB, 214370 Nhập môn công nghệ phần mềm 2 4 Bảy 4 3 RD203 787 2 DH19DTB DH19DTB, 214461 Phân tích và thiết kế hệ thống thông tin 2 4 Hai 1 3 P4 641 2 DH19DTB DH21DTA, 214331 Lập trình nâng cao 5 4 Năm 10 3 TV101 1017 2 DH21DTA DH19DTB, 214461 Phân tích và thiết kế hệ thống thông tin 2 4 Sáu 7 3 RD203 641 2 DH19DTB DH19DTB, 214370 Nhập môn công nghệ phần mềm 2 4 Sáu 4 3 P1 787 2 DH19DTB CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 247
Mã số sinh viên 18130192 Mã lớp DH18DTB 248 Tên sinh viên Huỳnh Ai Quốc Điểm TB 7.3 Mã MH Tên MH NMH STC Mã lớp Thứ Tiết BD ST Phòng CBGD Level 200105 Lịch sử Đảng Cộng sản Việt Nam 25 2 DH20TY Ba 1 3 TV302 105 1 DH18DTC, 214286 Chuyên đề Java 1 4 Bảy 4 3 P3 694 3 DH18DTC DH20DTA, 214351 Lý thuyết đồ thị 1 4 Hai 1 3 RD200 1017 2 DH20DTA DH20DTC, 214352 Thiết kế hướng đối tượng 3 4 Hai 4 3 CT101 104 2 DH20DTC 214984 Đồ án chuyên ngành 1 2 DH18DTA Hai 7 6 RD206 603 3 KỶ YẾU HỘI THẢO KHOA HỌC DH20DTA, 214351 Lý thuyết đồ thị 1 4 Năm 1 3 P3 1017 2 DH20DTA DH20DTC, 214352 Thiết kế hướng đối tượng 3 4 Năm 10 3 P1 104 2 DH20DTC DH18DTC, 214286 Chuyên đề Java 1 4 Sáu 1 3 TV101 694 3 DH18DTC DH18DTC, 214374 Chuyên đề WEB 1 4 Tư 4 3 RD305 603 3 DH18DTC 202622 Pháp luật đại cương 12 2 DH21KE Tư 7 3 TV103 183 1 DH18DTC, 214374 Chuyên đề WEB 1 4 Tư 10 3 P4 603 3 DH18DTC
Mã số sinh viên 19130083 Mã lớp DH19DTC Tên sinh viên Lê Võ Khánh Hưng Điểm TB 6.53 Mã MH Tên MH NMH STC Mã lớp Thứ Tiết BD ST Phòng CBGD Level DH21DTA, 214331 Lập trình nâng cao 5 4 Ba 10 3 P2 1017 2 DH21DTA DH19DTC, 214370 Nhập môn công nghệ phần mềm 3 4 Bảy 1 3 RD203 787 2 DH19DTC DH19DTC, 214370 Nhập môn công nghệ phần mềm 3 4 Bảy 7 3 P3 787 2 DH19DTC DH19DTC, 214461 Phân tích và thiết kế hệ thống thông tin 3 4 Hai 1 3 P3 640 2 DH19DTC DH19DTC, 214274 Lập trình trên thiết bị di động 1 3 Hai 10 3 P2 674 3 DH19DTC DH19DTC, 214274 Lập trình trên thiết bị di động 1 3 Năm 4 3 CT101 674 3 DH19DTC DH21DTA, 214331 Lập trình nâng cao 5 4 Năm 10 3 TV101 1017 2 DH21DTA DH19DTC, 214461 Phân tích và thiết kế hệ thống thông tin 3 4 Tư 4 3 PV233 640 2 DH19DTC CHUYỂN ĐỔI SỐ: XU HƯỚNG VÀ ỨNG DỤNG CÔNG NGHỆ 249
Bảng 5. Kết quả thống kê dựa trên Bảng 4 250 Điểm Số buổi Số ca học/1 ngày Độ thích ghi STT Mã số SV Họ tên Mã lớp trung học/ bình tuần 1 ca 2 ca 3 ca 4 ca f1(n) α∑ f2(m) f = f1(n) + α∑ f2(m) 1 20130215 Nguyễn Đắc Cường DH20DTC 7.75 4 0 2 1 1 50 28 78 2 20130074 Huỳnh Quốc Nam DH20DTB 7.34 4 0 1 3 0 50 28 78 3 19130145 Nguyễn Thu Nga DH19DTC 7.25 6 2 1 1 2 50 14 64 4 19130158 Nguyễn Thành Nhân DH19DTB 7.58 5 3 1 1 0 50 21 71 KỶ YẾU HỘI THẢO KHOA HỌC 5 18130192 Huỳnh Ái Quốc DH18DTB 7.3 6 3 1 3 0 50 14 64 6 19130083 Lê Võ Khánh Hưng DH19DTC 6.43 5 2 3 0 0 50 24 74