Luận văn tốt nghiệp thạc só MỤC LỤC CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI VÀ NGHIỆP VỤ BÀI TOÁN 1.1 Động mục tiêu 1.2 Đóng góp luận văn 1.3 Giới thiệu nghiệp vụ toán xếp phòng sinh viên ký túc xá 1.3.1 Giới thiệu ký túc xá Đại học Bách Khoa .5 1.3.2 Các sách quản lý việc đăng ký vào ký túc xá 1.4 Sơ lược cấu trúc luận văn .7 1.5 Quy ước thuật ngữ ký hiệu .8 CHƯƠNG 2: CÁC CÔNG TRÌNH LIÊN QUAN VÀ CƠ SỞ LÝ THUYẾT .9 2.1 Các công trình liên quan 2.2 Tìm kiếm cục 10 2.2.1 Giải thuật Hill-Climbing .10 2.2.2 Giải thuật Tabu search 11 2.2.3 Giải thuật mô trình luyeän kim hay Simulated Annealing .11 2.2.4 So sánh ba kỹ thuật tìm kiếm cục 11 2.2.5 Lựa chọn kỹ thuật giải toán .11 2.3 Kỹ thuật mô luyện kim (Simulated Annealing) 12 2.3.1 Tiêu chuẩn để chấp nhaän 13 2.3.2 Mối liên hệ trình luyện kim thực mô trình luyện kim 13 2.3.3 Giải thuật Simulated Annealing 14 2.3.4 Lịch biểu làm nguội 16 2.4 Kỹ thuật mô luyện kim cải tiến .19 CHƯƠNG 3: THIẾT KẾ CHƯƠNG TRÌNH 20 3.1 Giới thiệu ràng buộc hệ thống 20 i Luận văn tốt nghiệp thạc só 3.1.1 Ràng buộc cứng 20 3.1.2 Ràng buộc mềm 21 3.1.3 Các ràng buộc phòng – sinh viên .22 3.1.4 Các ràng buộc sinh vieân – sinh vieân 23 3.2 Hàm mục tiêu .27 3.2.1 Giới thiệu hàm mục tiêu 27 3.2.2 Công thức xác định hàm mục tiêu 27 3.3 Lịch biểu làm nguội 28 3.3.1 Lịch biểu làm nguội cấp số nhân .29 3.3.2 Lịch biểu làm nguội tái nhung nóng cấp số nhân 29 3.4 Lời giải lân cận 30 3.5 Thiết kế hệ thống .30 3.5.1 Khoái chức quản lý sinh viên 32 3.5.2 Khối chức sinh cách xếp phòng ban đầu 32 3.5.3 Khối chức tối ưu hoá 32 3.5.4 Khối chức quản lý ký túc xá .33 3.5.5 Công nghệ dùng để xây dựng chương trình .33 3.6 Thiết kế liệu cho chương trình .33 3.6.1 Dữ liệu quản lý ký túc xá 33 3.6.2 Dữ liệu đăng ký vào sinh viên 36 3.6.3 Dữ liệu chi phí cho ràng buộc 38 3.6.4 Dữ liệu cấu hình cho giải thuật SA 40 3.7 Thieát keá giao diện người dùng 41 3.7.1 Hệ thống 42 3.7.2 Quản lý sinh vieân 43 3.7.3 Quản lý ký túc xá 43 3.7.4 Xếp phòng 44 ii Luận văn tốt nghiệp thạc só 3.7.5 Báo cáo 44 3.7.6 Trợ giuùp .45 CHƯƠNG 4: HIỆN THỰC VÀ KẾT QUẢ THỰC NGHIỆM 46 4.1 Hiện thực chương trình .46 4.1.1 Kỹ thuật chọn lời giải lân cận 46 4.1.2 Hàm mục tieâu 48 4.1.3 Giải thuật SA với lịch biểu làm nguội cấp số nhân có số lần thực thi xác định trước .48 4.1.4 Giải thuật SA với lịch biểu làm nguội tái nung nóng cấp số nhân 50 4.2 Hiện thực giao diện người dùng 52 4.3 Kết thực nghieäm 56 4.3.1 Kết thực nghiệm giải thuật SA với số lần chạy giải thuật xác định trước .57 4.3.2 Kết thực nghiệm giải thuật SA với giải thuật tái nung nóng cấp số nhân 59 4.3.3 So sánh hai kết thực nghiệm .61 CHƯƠNG 5: TỔNG KẾT VÀ ĐÁNH GIÁ 62 5.1 Tổng kết 62 5.2 Ñaùnh giaù .63 5.2.1 Ưu điểm .64 5.2.2 Hạn chế 64 5.3 Hướng phát triển luận văn 65 TÀI LIỆU THAM KHẢO 67 PHUÏ LUÏC i Phụ lục A: Hướng dẫn cài đặt i Phụ lục B: Bảng thuật ngữ Việt-Anh đối chiếu ii iii Luận văn tốt nghiệp thạc só DANH MỤC HÌNH VÀ BẢNG Danh mục hình Hình 2-1: Lưu đồ giải thuật mô luyện kim 16 Hình 3-1: Mô tả tổng quan hệ thống 31 Hình 3-2: Mô tả liệu quản lý ký túc xá 34 Hình 3-3: Mô tả liệu đăng ký vào ký túc xá sinh viên 36 Hình 3-4: Giao diện tổng quan chương trình 41 Hình 4-1: Lưu đồ giải thuật chọn lời giải lân cận 46 Hình 4-2: Lưu đồ tính chi phí cho giải thuật SA 47 Hình 4-3: Lưu đồ giải thuật SA với lịch biểu làm nguội cấp số nhân có số lần chạy xác định trước 49 Hình 4-4: Lưu đồ giải thuật SA với lịch biểu làm nguội tái nung nóng cấp số nhân 50 Hình 4-5: Giao diện đăng ký thông tin sinh viên vào ký túc xá 51 Hình 4-6: Giao diện cho phép sinh viên chọn tiêu chí chọn phòng 52 Hình 4-7: Giao diện quản lý chi phí ràng buộc phòng-sinh viên 53 Hình 4-8: Giao diện quản lý chi phí ràng buộc sinh viên-sinh viên 54 Hình 4-9: Giao diện mô tả kết xếp phòng 55 Hình 4-10: Kết thực nghiệm giải thuật SA với lịch biểu làm nguội cấp số nhân có số bước chạy 1500 56 Hình 4-11: Kết thực nghiệm giải thuật SA với lịch biểu làm nguội cấp số nhân có số bước chạy 10000 57 Hình 4-12: Kết thực nghiệm giải thuật SA với lịch biểu làm nguội tái nung nóng cấp số nhân, N0=200 58 Hình 4-13: Kết thực nghiệm giải thuật SA với lịch biểu làm nguội tái nung nóng cấp số nhân, N0=300 59 Hình P-1: Mô tả attach sở liệu 68 iv Luận văn tốt nghiệp thạc só Danh mục bảng Bảng 2-1: So sánh ba giải thuật tìm kiếm cục 11 Bảng 3-1: Tổng kết loại ràng buộc cho toán xếp phòng 26 Bảng 3-2: Mô tả liệu bảng sinh viên 34 Bảng 3-3: Mô tả liệu bảng phòng 35 Bảng 3-4: Mô tả liệu bảng giường 35 Bảng 3-5: Mô tả liệu bảng xếp phòng 35 Bảng 3-6: Mô tả liệu bảng tiêu chí chọn bạn 37 Bảng 3-7: Mô tả liệu bảng tiêu chí chọn phòng 37 Bảng 3-8: Mô tả liệu bảng sở thích 37 Bảng 3-9: Mô tả liệu bảng đăng ký lại 38 Bảng 3-10: Mô tả liệu bảng chi phí chọn bạn 38 Bảng 3-11: Mô tả liệu bảng chi phí chọn phòng 39 Bảng 3-12: Mô tả liệu bảng chi phí sở thích 39 Bảng 3-13: Mô tả liệu bảng chi phí sách quản lý 40 Bảng 3-14: Mô tả cấu hình giải thuật SA với lịch biểu làm nguội cấp số nhân có số lần chạy xác định trước 40 Bảng 3-15: Mô tả cấu hình giải thuật SA với lịch biểu làm nguội tái nung nóng cấp số nhân 41 Bảng 4-1: Thời gian thực thi giải thuật SA với số bước chạy cho trước 56 Bảng P-1: Bảng thuật ngữ Việt-Anh đối chiếu 69 v Luận văn tốt nghiệp thạc só LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ kết tham khảo từ công trình khác ghi rõ luận văn, công việc trình bày luận văn thực chưa có phần nội dung luận văn nộp để lấy cấp trường hay trường khác TPHCM, ngày tháng 12 năm 2004 Lê Trung Hiếu vi Luận văn tốt nghiệp thạc só LỜI CẢM ƠN Em xin gửi lời cảm ơn trân trọng đến Thầy hướng dẫn đề tài, T.S Dương Tuấn Anh, người Thầy hướng dẫn, nâng đỡ quan tâm sâu sắc đến em suốt trình thực đề tài Xin cảm ơn gia đình động viên tinh thần suốt trình học tập giảng đường Đại học trình làm luận văn Xin gửi lời cảm ơn chân thành đến bạn bè Cao học khóa 12 chia sẻ kinh nghiệm, tình cảm chân thành giai đoạn học tập vii Luận văn tốt nghiệp thạc só TÓM TẮT Hiện nay, ký túc xá Trường Đại Học Bách Khoa Tp HCM, ký túc xá trường đại học khác thành phố xếp phòng cho sinh viên ký túc xá đầu học kỳ, việc xếp thường giao cho nhân viên quản lý ký túc xá thực tay chưa tự động hoá Hậu việc xếp phòng tay tốn nhiều thời gian không hiệu quả, hầu hết tất ký túc xá không quan tâm đến sở thích sinh viên như: sở thích nghe nhạc, sở thích thể thao, sở thích chọn bạn phòng… Luận văn ứng dụng kỹ thuật mô luyện kim để cung cấp chương trình xếp phòng cho sinh viên ký túc xá với tài nguyên số lượng phòng, số lượng giường có giới hạn với lượng lớn sinh viên tương ứng; đồng thời việc xếp phải quan tâm đến nguyện vọng sở thích sinh viên Để áp dụng giải thuật mô luyện kim, luận văn có nhiệm vụ xác định qua thực nghiệm thông số giải thuật xác định nhiệt độ ban đầu, xác định hệ số giảm nhiệt độ α, ß cho lịch biểu làm nguội Hệ thống thử nghiệm liệu thật (khoảng 3000 sinh viên) kết thực nghiệm cho thấy giải thuật hữu hiệu thời gian chạy đem lại lời giải chất lượng cao viii Luận văn tốt nghiệp thạc só ABSTRACT Dormitories of Ho Chi Minh City Univerity of Polytechnic as well as other universities and colleges currently have to assign rooms to their students at the beginning of every semester So far, this kind of arrangement has been processed manually and maintained by the dormitories’ staffs and it has not been automated by computer yet Consequently, the rooms assignment to students is time-consuming and ineffective Actually, almost dorms ignore the legitimate demands of the students such as: their preferences of room types, their hobbies of music, sports and their favorite room-mates In this thesis, we employ the simulated annealing technique to provide a dorms assignment system for students in such a way that limited resources such as an certain amount of rooms, beds can accomodate a great number of students Moreover, the arrangements have to meet preferences and hobbies of the students In order to make Simulated Annealing algorithm applicable, this research has to determine parameters of the algorithm, such as cooling factors α, ß in the cooling schedules, initial temparature and final temparature This system has been experimented on real data set (approximately 3000 students) and the result show the effectiveness of the algorithm: time efficiency and qualified solutions ix Luận văn tốt nghiệp thạc só CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI VÀ NGHIỆP VỤ BÀI TOÁN 1.1 Động mục tiêu Vào đầu năm học, trường đại học, cao đẳng lại có thêm hàng ngàn tân sinh viên nhập học Bên cạnh việc tổ chức học tập, nghiên cứu mối quan tâm hàng đầu trường đại học, việc giải nơi ăn chốn cho sinh viên ngày cán quản lý trường xã hội quan tâm nhằm giải chỗ ổn định cho sinh viên để em có đủ điều kiện môi trường sống tốt để yên tâm học tập Ký túc xá nơi ưu tiên hàng đầu mà sinh viên lựa chọn nơi trường mong muốn xếp cho sinh viên tính an toàn, kỷ luật, tiện lợi chi phí phải chăng, phù hợp với hoàn cảnh sinh viên xa nhà sinh hoạt phí eo hẹp hầu hết sinh viên Mặc dù thời điểm tại, ký túc xá chưa đáp ứng đầy đủ nhu cầu sinh viên việc mở rộng, nâng cấp hạ tầng ký túc xá cung cách quản lý ký túc xá, xếp phòng cho sinh viên quan tâm bước xây dựng có nhiều thay đổi rõ rệt Ký túc xá đại học Bách Khoa không nằm tiến trình cải tiến thay đổi Tuy nhiên với số lượng sinh viên đông đảo với nhiều loại hình đào tạo chuyên ngành đa dạng đại học Bách Khoa, việc mở rộng xây dựng đại hóa ký túc xá, việc cải tiến quy trình quản lý cần đặc biệt quan tâm Trong vấn đề quản lý ký túc xá, qui trình xếp phòng cho sinh viên cho tiện lợi đáp ứng nguyện vọng, sở thích sinh viên thực toán phức tạp Luận văn tốt nghiệp thạc só server=server_name;database=Dorm;user id=username;password=password Với server_name, username, password lần lược tên máy chủ chứa hệ quản trị sở liệu, tên mật tài khoản để đăng nhập vào hệ quản trị sở liệu Phụ lục B: Bảng thuật ngữ Việt-Anh đối chiếu Tiếng việt Tiếng Anh Điều kiện dừng Stopping condition Giải thuật tìm kiếm cục Local search Giải thuật leo đồi Hill- Climbing Giải thuật tìm kiếm tabu Tabu search Hàm mục tiêu Cost function Kỹ thuật mô luyện kim Simulated annealing Lời giải lân cận Neighbourhood solution Lịch biểu làm nguội Cooling schedule Lịch biểu làm nguội cấp số nhân Geometric cooling schedule Lịch biểu làm nguội cấp số nhân với Geometric multiple cooling rates nhiều tỉ lệ làm nguội Lịch biểu làm nguội tái nung nóng Geometric reheating cấp số nhân Quay lui Backtracking Quá trình làm nguội Annealing Ràng buộc cứng Hard constraint Ràng buộc mềm Soft constraint Bảng P-1: Bảng thuật ngữ Việt – Anh đối chiếu ii ... vụ toán xếp phòng cho sinh viên ký túc xá, phần nghiệp vụ toán mô tả sách quản lý việc xếp phòng cho sinh viên ký túc xá vào đầu năm học Chương 2: Trước thiết kế thực hệ thống xếp phòng cho sinh. .. sinh viên: chức cho phép ban quản lý ký túc xá chỉnh sửa thông tin sinh viên • Xoá sinh viên: chức cho phép ban quản lý ký túc xá xoá sinh viên sinh viên không ký túc xá 3.7.3 Quản lý ký túc xá... để quản lý tài nguyên ký túc xá phòng, giường thông tin cá nhân sinh viên ký túc xá, chương trình thực việc xếp phòng cho sinh viên ký túc xá, cụ thể ký túc xá chọn ký túc xá trường Đại học Bách