PHẦN MỞ ĐẦU L Lý do chọn đề tài Đề đáp ứng mục tiêu cơ bản của các dự án Tin học hoá quản lý trong các thời kỳ mới là tạo được một hệ thống thông tin thống nhất phục vụ điều hành và quản lý, chúng tôi chọn hướng phát triển phần mềm sắp xếp thời khóa biểu cho trường THCS nhằm: 1. Tổ chức quản lý, lưu trữ dữ liệu trên hệ thống máy vi tính làm tăng tính an toàn. Sắp xếp, tính toán, phân chia thời khóa biểu một cách nhanh chóng và chính xác. Chi phí đào tạo sử dụng phần mềm không tốn kém.
Tổ chức quản lý, phù hợp với các ứng dụng triển khai trên diện rộng. Bảo trì, phát triển phần mềm, phát triển ứng dụng và tích hợp với các ứng dụng khác một cách dễ dàng nhanh chóng. Nên việc mở rộng ít tốn kém nhất. Mục tiêu của đề tài Hệ thống dữ liệu đảm bảo việc nhập dữ liệu, quản lý, tra cứu, khai thác dữ liệu được nhanh chóng, thuận tiện.
Phần mềm giúp sắp xếp thời khóa biểu nhanh chóng giảm thiều tối đa thời gian và công sức so với việc thực hiện thủ công. Phần mềm có giao diện hài hòa, dễ nhìn, linh hoạt, năng động hơn và đáp ứng được yêu cầu ngày càng cao trong công tác quản lý giáo viên, lớp học, môn học. và nhu cầu của người sử dụng. Đối tượng nghiên cứu Toàn bộ cán bộ giáo vụ khoa của trường THCS Hồng Bàng, tỉnh Hải Phòng, các thành phần tin học liên quan đến SVTH: Nguyễn Duy Tứ; 12TLT.CNTT Trang 1 Phan mềm sắp xếp thời khóa biểu THCS công tác quản lý bao gồm: hệ quản trị cơ sở dữ liệu, phân tích thiết kế hệ thống, ngôn ngữ lập trình C#.
Phương pháp thực hiện Quan sát trục tiếp, trao đổi giao tiếp với cán bộ giáo vụ khoa, xin số liệu cụ thể. Gi athu di truyêên và Tính tiễn hóa 1. Giải thuật di truyền 1111 Ý trưởng Giải thuật di truyền (GA- Genetic Algorithm) là mô phỏng theo quá trình tiến hóa tự nhiên của sinh vật theo thuyết Darwin. Trong quá trình tiến hóa, mỗi cá thể đều phải tự tìm cách thích nghi tốt nhất với môi trường sống rất phức tạp và luôn luôn thay đổi.
Cá thể nào có khả năng thích nghỉ với môi trường cao hơn thì sẽ có khả năng tồn tại, phát triển và sinh sản cao hơn, ngược lại cá thể nào có khả năng thích nghi thấp sẽ có nhiều nguy cơ bị tiêu vong hoặc phát triển chậm. Sự thích nghi đó được đúc kết và ghi lại trong cất trúc của nhiễm sắc thể của chúng. Việc giải bài toán thực tế có thể xem là việc tìm kiếm trong một thời gian các lời giải tiềm năng nhằm tìm ra lời giải tốt nhất hoặc chấp nhận được mà ta có thể gọi là quá trình tối ưu hóa. Đối với không gian tìm kiếm nhỏ, đơn giản nhất là dùng kỹ thuât “vét cạn”, nghĩa là liệt kê toàn bộ lời giải tiềm năng, sau đó kiểm tra điều kiện để chọn ra lời giải.
Đối với không gian tìm kiếm khá lớn thì kỹ thuật vét cạn có độ phức tạp rất lớn, khó chấp nhận được. Khi đó, giải thuật di truyền được xem là thích hợp cho việc giải quyết bài toán tìm kiếm lời giải tối ưu. SVTH: Nguyễn Duy Tứ; 12TLT.CNTT Trang 2 Phan mềm sắp xếp thời khóa biểu THCS GA không chú trọng đến giải pháp duy nhất và chính xác như các phương thức cổ điển, trái lại GA xét đến toàn bộ các giải pháp và chọn lấy giải pháp tương đối tốt nhất. GA dựa trên tính ngẫu nhiên như trong thế giới tự nhiên của sinh vật, nhưng được hướng dẫn bởi hàm thích nghỉ (Anh, 2011).
Đặc trưng GA làm việc với một mã hóa của tập hợp tham số mà không phải một tham số. GA tìm kiếm từ một quần thể các điểm chứ không phảo một điểm hoặc một vài điểm như phương pháp tìm kiếm leo đồi. GA đánh giá thông tin với hàm mục tiêu mà không đưa vào đạo hàm hay thông tin bổ sung khác. GA sử dụng các luật biến đổi theo xác suất mà không sử dụng luật quyết định (Anh, 2011).
Cau tric GA sử dụng ý tưởng và các thuật ngữ trong di truyền học như được trình bày sau đây. Trong tự nhiên, mỗi cá thể có các tính chất và đặc điểm riêng được thể hiện ra ngoài gọi là kiểu hình. Kiểu hình này được quyết định bởi các cấu trúc gen trong cơ thể, gọi là kiểu gen (genotype). Các gen tạo thành các nhiễm sắc thể, mỗi tế bào có tập hợp các nhiễm sắc thể như nhau.
Các nhiễm sắc thể là các chuỗi DNA hoạt động như một mô hình cho toàn bộ cơ thể. Sự đa dạng về kiểu gen của các cá thể dẫn đến dự đa dạng về kiểu hình của một quần thể sinh học. Quá trình phát triển của mỗi quần thể tuân theo quy luật chọn lọc tự nhiên mà tiến hóa qua các thế hệ nối tiếp nhau. Trong đó, các hậu duệ được sinh ra từ thế hệ trước thông qua quá trình sinh sản (di truyền và biến dị) cạnh tranh tự nhiên với nhau, cá thể nào SVTH: Nguyễn Duy Tứ; 12TLT.CNTT Trang 3 Phan mềm sắp xếp thời khóa biểu THCS có kiểu hình (và do đó kiểu gen) thích nghi cao hơn teong môi trường phát triển thì sẽ có khả năng cao hơn tồn tại và sinh sản con cháu.
Do đó, kiểu gen này sẽ tiến hóa và hoàn thiện. Quá trình tiến hóa nầu được lặp đi lặp lại, các cá thể có kiểu gen phù hợp sẽ sống sót và phát triển, các cá thể yếu sẽ bị loại bỏ dần. GA là kỹ thuật tối ưu dựa trên khái niệm chọn lọc tự nhiên và di truyền. Do vậy, lời giải của bài toán được trình bày như các gen trong nhiễm sắc thể.
GA mô tả một nhóm các lời giải tiềm năng được đề cử. Qua tiến hóa và chọn lọc tự nhiên các nhiễm sắc thể với độ thích nghi tốt hon sẽ xuất hiện. Chọn lọc tự nhiên đảm bảo cho cá thể độ thích nghỉ tốt nhất sẽ được truyền lại cho các thế hệ con cháu (các quần thể tương lai). Phép lai ghép kết hợp các gen từ hai cá thể bố mẹ để tạo thành hai cá thể con mói với độ thích nghi có chiều hướng cao hơn bố mẹ.
Phép biến dị cho phép tạo tra chất liệu di truyền mới, tạo ra những đột phá trong tìm kiếm thông tin mới. GA cung cấp sự cải tiến thế hệ về độ thích nghi của các cá thể và sau nhiều thế hệ sẽ tạo ea các cá thể chữa những thiết lập biến đổi đã được tối ưu. Mỗi cá thể trong GA thường chỉ gồm một nhiễm sắc thể. Do vậy thuật ngữ cá thể và nhiễm sắc thế được dùng không phân biệt ngữ nghĩa (Anh, 2011).
Khởi tạo J Đánh giá độ thích nghi của P(t) | SVTH: Nguyễn Dụy Tứ; 12TLT.CNTT t=t+1 Chọn Q (t) từ P (t-1)// chọn lọc Roulette Tait @P(t)t UQ(t)//b các toán t ứủi truyeän Phần mềm sắp xếp thời khóa biểu THCS | Đánh giá độ thích nghi cua P (t) va chọn cá thể tdat nhaat Ki mếtra điêâu ki 4 kéat thúc thuật toán thỏa mãn chưa Hình 1-1: Thuật toán chương trình Trong đó: - P(t) la quần thể tại thế hệ thứ t. - Q(t) la quan thé trung gian. Nhiễm sắc thê và quân thể Trong GA, mỗi cá thể (hay nhiễm sắc thể) được mã hóa bởi chuỗi nhị phân. Ví dụ: mỗi NST gồm 8 gens như sau: [19191119 ]1]1|9, Mỗi cá thể (một nhiễm sắc thể cụ thể) biểu thị một lời giải tiềm năng của bài toán.
Một quá trình tiến hóa được thực SVTH: Nguyễn Duy Tứ; 12TLT.CNTT Trang 5 Phan mềm sắp xếp thời khóa biểu THCS hiên trên một quần thể (một tập hợp các cá thể) tương đương 225. và trao đổi thông tin giữa các hướng. Tập lời giải qua quá trình tiến hóa và cuối cùng cho ta mộ lời giải đủ tốt theo yêu cầu. Tại mỗi thế hệ, các lời giải tương đối tốt được tái sinh, và các lời giải tương đối xấu bị loại bỏ dần.
Để đánh giá mức độ tốt xấu của từng lời giải, người ta xây dựng hàm thích nghi, hàm này đóng vai trò như môi trường sống trong thuyết tiến hóa của Darwin. Mã hóa nhiễm sắc thể: biểu diễn mã nhị phân của mỗi lời giải tiềm năng. Ta có công thức: (b;- a¡)*10° 2m, ~ 1 Trong đó: - _ 10P sai số đến p chữ số thập phan -_ bị là điểm cuối trên miền giới hạn - ajla diém đầu trên miền giới hạn - mila dé dai chudi nhi phan Ví dụ: tìm giá trị cực đại của hàm số hai biến: f(X1,X2) = 10+x¡*sin x¡+x¿*sin x; trên miền với sai số các biến là 107. Hàm đánh giá Hàm đánh giá (eval) trên tập nhiễm sắc thể để đánh giá độ thích nghi của mỗi cá thể: eval(z) = f(x), trong đó x là vector tương ứng với Z.
Thủ tục chọn lọc Các cá thể được chọn lọc theo độ thích nghi của chúng để tham gia vào pha tiếp theo của quá trình tiến hóa. Cá thể có độ thích nghi cao hơn có cơ hội được chọn nhiều hơn, nghĩa là có nhiều con cháu trong các hệ tiếp theo. Phép chọc lọc các cá thể trong mỗi quần thể được thực hiện nhờ bánh xe xổ số (Roulette Wheel). Với mỗi quần thể P(t-1) gồm N nhiễm sắc thể: P(t-1)= {V¡,Vạ,.,va} ta xây dựng bánh xe xổ số như sau: SVTH: Nguyễn Duy Tứ; 12TLT.CNTT Trang 6 Phan mềm sắp xếp thời khóa biểu THCS - Đánh giá độ phù hợp toàn phần, còn gọi là tổng độ thích nghi của quần thể.
-_ Tính xác suất chọn lọc p¡ của mỗi cá thể v;: -_ Tính xác suất tích lũy q¡ cho mỗi cá thé v;: Quá trình chọn lọc quần thể Q(t) từ P(t-1) dựa vào bánh xe xổ số được thực hiện như sau: Đối với mỗi số tự nhiên k = 1,2,.N phát sinh một số thực ngẫu nhiên r, [0,1]. Nếu r, q¡ thì chọn cá thể v:, ngược lại chọn cá thể vị sao cho q1 < í( Q¡; 2iN. Với cách thực hiện như thế, có thể có một số cá thể được chọn nhiều lần và Q(t) vẫn được xem là có N phần tử. Các cá thể được chọn nhiều lần, các cá thể trung bình thì bình ổn và các cá thể xấu bị giảm dần.
Minh họa bánh xe xổ số với quần thể có 5 cá thể: Hình 1-2: Bánh xex G66 Cá thể 1 có xác suất chọn lọc là 20% nghĩa là mỗi lần quay bánh xe xổ số , nó có khả năng được chọn là 0. Tương tự vậy cho các cá thể thứ 2,3,4,5. Với ví dụ trên ta có: SVTH: Nguyễn Duy Tứ; 12TLT.
