Chương 1 trình bày lý do chọn đề tài, mục tiêu nghiên cứu, xác định đối tượng và phạm vi nghiên cứu, phương pháp và kế hoạch thực hiện đề tài, sơ đồ phương pháp luận và cấu trúc của đề tài. CƠ SỞ LÝ THUYẾT VÀ LƯỢT KHẢO TÀI LIỆU Cơ sở lý thuyết là hệ thống hóa các lý thuyết và quan điểm lý luận để làm luận điểm khoa học xuyên suốt cho đề tài nghiên cứu. Các lý thuyết về điều độ, các phương pháp giải bài toán lập thời khóa biểu, lý thuyết về giải thuật di truyền và phương pháp áp dụng giải thuật được trình bày tại Chương này để làm cơ sở cho việc vận dụng. Các tài liệu liên quan được lượt khảo để tổng quan về hướng nghiên cứu liên quan đến đề tài, điểm mới trong hướng nghiên cứu của đề tài.1 Giới thiệu về điều độ Điều độ là một quá trình ra quyết định đóng vai trò rất quan trọng trong hầu hết các hoạt động, các ngành công nghiệp sản xuất và dịch vụ.
Kỹ thuật điêu độ được sử dụng trong mua bán và sản xuất, trong vận chuyển và phân bố, trong xử lý thông tin và truyền thông [7]. Chức năng của điều độ trong một tổ chức là sử dụng các kỹ thuật toán học hay một số phương pháp định lượng khác để phân phối hợp lý các nguồn tài nguyên có hạn phục vụ công việc. Sự phân phối tài nguyên thích hợp sẽ cho phép tổ chức đạt được mục tiêu tối ưu mong muốn. Nguồn tài nguyên (resources) có thể là các máy móc trong phân xưởng, các đường băng trong sân bay, các công nhân ở các công trường xây dựng hay các đơn vị xử lý trong môi trường tính toán,… Các công việc (task) có thể là các sự vận hành trong các công xưởng, các lần cất cánh hay đáp xuống tại sân bay, các giai đoạn trong một dự án xây dựng hay các chương trình máy tính được thi hành tương ứng với các nguồn tài nguyên.
Mỗi công việc có thể có một mức độ ưu tiên, một thời gian có thể bắt đầu sớm nhất và một ngày tới hạn riêng biệt. Các mục tiêu trong điều độ sản xuất, có thể có nhiều dạng khác nhau, ví dụ như cực tiểu thời gian hoàn thành các công việc hay cực tiểu các công việc trễ hạn [7] Chức năng điều độ trong một hệ thống sản xuất hay một tổ chức dịch vụ phải tương tác với nhiều chức năng khác nhau. Các sự tương tác này thường thông qua 7 mạng máy tính, nhưng trong nhiều tình huống, sự tương tác giữa điều độ và các chức năng ra quyết định khác xảy ra tròn các buổi họp hay qua thư báo.2 Các phương pháp giải bài toán lập thời khóa biểu Đối với phương pháp tiếp cận truyền thống, một số phương pháp để giải bài toán lập thời khóa biểu như sau: - Giải thuật vét cạn (tìm kiếm theo chiều rộng hoặc chiều sâu) về mặt nguyên tắc luôn tìm được nghiệm nếu bài toán có nghiệm. Nhưng trên thực tế, các bài toán thời khóa biểu không nên áp dụng phương pháp này, vì ta phải phát triển một không gian trạng thái cực lớn trước khi đi đến trạng thái đích.
Do các hạn chế về thời gian tính toán và dung lượng bộ nhớ, không cho phép ta thực hiện được. Chẳng hạn, với bài toán thời khóa biểu cho 50 lớp học, mỗi lớp có 15 môn học, mỗi lớp có 30 tiết mỗi tuần thi không gian tìm kiếm rất lớn là 50*15*30 trường hợp. Dễ nhận thấy rằng, nếu dùng phương pháp vét cạn thì thời gian chạy để tìm lời giải tối ưu rất lớn, khó chấp nhận được. - Giải thuật leo đồi (Hill Climbing) sử dụng kỹ thuật nâng cấp lặp, áp dụng cho một số điểm đơn (điểm hiện hành) trong không gian tìm kiếm.
Mỗi lần nâng cấp, một điểm trong lân cận của điểm hiện hành được chọn làm điểm kế tiếp, nếu nó cho kết quả tốt hơn của hàm mục tiêu. Việc tìm kiếm kết thúc khi không thể nâng cấp được nữa. Rõ ràng, giải thuật leo đồi chỉ cho kết quả tối ưu cục bộ, kết quả này phụ thuộc vào sự chọn lựa điểm xuất phát, mặt khác ta không có được thông tin về sai số giữa tối ưu cục bộ tìm được và tối ưu toàn cục. Mặc dù đã cải tiến bằng cách tăng số lượng điểm xuất phát (chọn ngẫu nhiên hoặc chọn theo kết quả của lần chạy trước), nhưng khi có nhiều giá trị lân cận thì khả năng tìm được kết quả tối ưu toàn cục của giải thuật leo đồi còn rất thấp.
Các phương pháp tiếp cận hiện nay để giải bài toán xếp thời khóa biểu Đã có nhiều giải thuật được đề xuất đề giải các bài toán thời khóa biểu. Các giải thuật này tìm được lời giải gần tối ưu và là một trong các xu thế phát triển hiện 8 nay đối với các bài toán chưa thể tìm được lời giải tối ưu thực sự. Các giải thuật này đều mô phỏng theo tự nhiên như giải thuật luyện kim, giải thuật di truyền, giải thuật Tabu-search, giải thuật luyện kim. trong đó giải thuật di truyền và tối ưu hóa đàn kiến được xem là những phương pháp hiệu quả cao nhất.
- Giải thuật Tabu-search là một trong những metaheuristic được áp dụng nhiều nhất cho các bài toán tối ưu tổ hợp khó. Bắt nguồn từ một lời giải ban đầu, thuật giải Tabu Search sẽ lập đi lặp lại việc tìm kiếm trong miền không gian tìm kiếm của bài toàn nhằm mục đích tìm ra lời giải tối ưu. Tại mỗi bước lặp của mình, thuật giải Tabu Search sẽ tìm kiếm và chỉ ra một lời giải duy nhất để làm cơ sở cho bước lập tiếp theo. Để tránh việc duyệt trở lại những lời giải đã được duyệt, thuật giải Tabu Search sử dụng Tabu-list.
Danh sách này chứa những lời giải đã được thực hiện trong các bước lặp trước, chúng sẽ không được sử dụng lại chừng nào nó còn nằm trong Tabu-list [8]. - Giải thuật luyện kim (Annealing Algorithm), người ta dùng kỹ thuật thay đổi entropy của hệ và điều khiển tốc độ hội tụ của quần thể bằng cách biến đổi nhiệt động học với một tham số nhiệt độ T toàn cục [9]. Để hạn chế sự tối ưu cục bộ và tăng khả năng khám phá không gian tìm kiếm, người ta dùng thủ thuật giam từng bước nhiệt độ T (đến một mức nào đó). Tuy nhiên, do T chỉ giảm đến một mức nhất định, nên kỹ thuật luyện kim không tránh khỏi hạn chế trong việc khám phá không gian tìm kiếm và sự hội tụ lân cận.
- Giải thuật di truyền là sự kết hợp ý tưởng của giải thuật leo đồi và luyện kim. Đặc trưng của giải thuật này là duy trì một tập hợp các lời giải tiềm năng (gọi là tập các cá thể hay quần thể), khuyến khích việc hình thành và trao đổi thông tin giữa các cá thể trong quần thể thông qua phép lai và phép biến dị. Một quá trình tiến hóa được thực hiện trên một quần thể thực chất là sự tìm kiếm trong một không gian các lời giải tiềm năng. Sự tìm kiếm này đòi hỏi sự cân bằng giữa hai mục tiêu tìm lời giải tốt nhất và khám phá không gian tìm kiếm mới.
- Giải thuật tối vụ đàn kiến (ACO – Ant Colony Optimization) do Dongo đề xuất là phương pháp tiếp cận hiện đại nhất. Một lần thần ngẫu nhiên trong ACO cho phép các con kiến xây dựng được một lượng lớn các lời giải khác 9 nhau hơn các phương pháp khác. Tại cùng một thời gian việc sử dụng các thông tin kinh nghiệm sẽ hướng dẫn các con kiến tìm kiếm được các lời giải tối ưu. Quan trọng hơn, kinh nghiệm tìm kiếm của con kiến sẽ được sử dụng để tăng cường trong quá trình lặp xây dựng giải thuật.
Thêm vào đó, việc tham gia của đàn kiến kiến làm cho giải thuật ACO có được một tập hợp các tác nhân lặp hiệu quả để giải quyết bài toán. Tuy nhiên, giải thuật tối ưu đàn kiến phức tạp hơn phương pháp tính toán tiến hóa nhiều. Hiện nay giải thuật di truyền, giải thuật luyện kim và giải thuật tối ưu đàn kiến là các phương pháp được sử dụng nhiều nhất để giải quyết bài toán lập thời khóa biểu [10, 11]. Giải thuật luyện kim sẽ hội tụ biến, cho kết quả với tốc độ nhanh hơn, code dễ nhưng gặp vấn đề tối ưu cục bộ [12].
Giải thuật tối ưu đàn kiến và giải thuật di truyền là hai giải thuật tối ưu toàn cục [12, 13]. Tuy nhiên, giải thuật tối ưu đàn kiến thích hợp cho bài toán tìm đường đi ngắn nhất hơn là trong các vấn đề khác [13]. Trên thực tế việc lập thời khóa biểu chỉ diễn ra khoảng hai đến ba lần trong một năm tương ứng với từng học kỳ. Vì vậy để phù hợp trong luận văn này, tác giả sử dụng giải thuật di truyền để tiếp cận bài toán lập thời khóa biểu cho trường học do thời gian và chi phí cho việc lập thời khóa biểu nằm trong khoảng chấp nhận được.3 Lý thuyết về giải thuật di truyền 2.1 Giải thuật di truyền (GAs) Thuật toán di truyền (Genetic Algorithm - GA) phỏng theo các quá trình tiến hoá tự thích nghi của các quần thể sinh học để tối ưu hoá các hàm mục tiêu.
Thuật toán này lần đầu tiên được phát triển bởi John Holland [14] và đã được áp dụng rất thành công trong nhiều lĩnh vực khác nhau của khoa học máy tính bao gồm: Học máy, lí thuyết điều khiển và tối ưu tổ hợp,. Trong thuật toán di truyền, người ta sử dụng các thuật ngữ vay mượn từ di truyền học như: cá thể, nhiễm sắc thể (NST), gen, quẩn thể, thể trạng, chọn lọc, lai, đột biến, v.v… Trong số đó, một cá thể (cá thể, kiểu gen, cẩu trúc) đại diện cho một giải pháp để giải quyết vấn đề. Không giống như trong tự nhiên, một cá thể có thể có nhiều NST, thì ở đây mỗi cá thể chỉ có một NST. NST có thể là một chuỗi tuyến tính và có thể có các đơn vị gen nhỏ hơn trong NST.
Mỗi gen 10 đại diện cho một thuộc tính, một tính trạng và có một vị trí nhất định trong NST. Một quần thể là một nhóm giới hạn của các cá thể. Cụ thể, một tập hợp các biến cho một vấn đề nhất định được mã hóa thành chuỗi (hoặc cấu trúc mã hóa khác) tương tự như NST trong tự nhiên. Mỗi trình tự chứa một giải pháp khả thi cho vấn đề.
