- 1.3 Bài toán lập thời khóa biểu 4. - 3.1.1 Chọn mô hình cá thể 12. - 3.1.3 Độ thích nghi - chọn cá thể 15. - 3.1.4 Thuật toán lai ghép và đột biến 16. - 3.2.1 Chọn mô hình cá thể 16. - 3.2.3 Độ thích nghi - chọn cá thể 17. - 3.2.4 Thuật toán lai ghép và đột biến 18. - 4.3 Biểu diễn nhiễm sắc thể 19. - 4.4.1 Phép lai ghép 21. - Trong thuật giải di truyền, một tập các biến của bài toán đưa ra được mã hóa sang một chuỗi (hay một cấu trúc mã hóa khác) tương tự như một nhiễm sắc thể trong tự nhiên. - Quá trình lai ghép (phép lai) quá trình này diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha-mẹ để hình thành nhiễm sắc thể mới mang đặc tính của cả cha lẫn mẹ.. - Chọn ngẫu nhiên hai hay nhiều cá thể trong quần thể. - Giả sử chuỗi nhiễm sắc thể của cha và mẹ đều có chiều dài là m. - Như vậy, điểm lai này sẽ chia hai chuỗi nhiễm sắc thể cha-mẹ thành hai nhóm nhiễm sắc thể con là m1 và m2. - Hai chuỗi nhiễm sắc thể con lúc này sẽ là m11+m22 và m21+m12. - Đưa hai chuỗi nhiễm sắc thể con vào quần thể để tiếp tục tham gia quá trình tiến hóa quá trình đột biến (phép đột biến) quá trình tiến hóa được gọi là quá trình đột biến khi một hoặc một số tính trạng của con không được thừa hưởng từ hai chuỗi nhiễm sắc thể cha-mẹ. - Đưa nhiễm sắc thể con vào quần thể để tham gia quá trình tiến hóa tiếp theo. - Phép tái sinh: là quá trình các cá thể được sao chép dựa trên độ thích nghi của nó. - Độ thích nghi là một hàm được gán các giá trị thực cho các cá thể trong quần thể của nó. - Tính độ thích nghi của từng cá thể trong quần thể, lập bảng cộng dồn các giá trị thích nghi đó (theo thứ tự gán cho từng cá thể) ta được tổng độ thích nghi. - Giả sử quần thể có n cá thể. - Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i là Ft. - Chọn cá thể k đầu tiên thỏa mãn F ≥ Ft đưa vào quần thể của thế hệ mới.. - Phép chọn: là quá trình loại bỏ các cá thể xấu và để lại những cá thể tốt.. - Loại bỏ các cá thể cuối dãy, chỉ để lại n cá thể tốt nhất.. - Toán tử lai ghép. - Lai ghép một điểm (one-point crossover). - Lai ghép hai điểm (two-point crossover). - Lai ghép N điểm (N-point crossover). - Lai ghép đồng nhất (Uniform crossover) 2.3 Các tham số của giải thuật di truyền.. - Nếu không có lai ghép, cá thể con sẽ chính là bản sao của cá thể “cha mẹ”. - Nếu xác suất lai ghép bằng 100%, khi đó mọi cá thể con đều được tạo ra qua quá trình lai ghép.. - Xác suất đột biến: là tham số cho biết tần suất đột biến của nhiễm sắc thể.. - Ngược lại, một hoặc một số phần của nhiễm sắc thể sẽ bị thay đổi. - Nếu xác suất đột biến là 100%, toàn bộ nhiễm sắc thể sẽ bị thay đổi. - Kích thước quần thể: là tham số cho biết có bao nhiêu cá thể (NST) trong 1 thế hệ của quần thể. - Tính độ thích nghi eval(vi) của mỗI nhiễm sắc thể vi(i=1…. - Mỗi lần chọn ra một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới theo cách sau:. - q1thì chọn nhiễm sắc thể v1, ngược lại chọn nhiễm sắc thể vi (2. - Trước một bài toán áp dụng thuật giải di truyền, ta cần phải xác định rõ nhiễm sắc thể và cá thể cho vấn đề, và thông thường đó sẽ kết quả cuối cùng. - Đánh giá cá thể Chắc chắn rằng việc chọn cá thể sẽ thông qua kết quả, hay mục đích của vấn đề. - Dựa trên mức độ thích nghi của cá thể, bao gồm những vướng mắc mà cá thể gặp phải. - Cá thể tốt nhất sẽ có số điểm thấp nhất hoặc lớn nhất. - Theo thuyết tiến hóa của Darwin, nhiễm sắc thể tốt nhất sẽ tồn tại và tạo ra các cá thể con mới. - Có nhiều phương pháp để chọn các nhiễm sắc thể tốt nhất.. - Còn tùy thuộc vào cách tổ chức và phân bố các nhiễm sắc thể mà chúng ta có xác suất lai ghép nhanh hay chậm. - 3) Lai ghép dựa trên vị trí (Position Based Crossover). - 4) Lai ghép dựa trên thứ tự (Order Base Crossover). - 3.1.1 Chọn mô hình cá thể. - Như vậy một lớp học tương ứng sẽ có nhiều lịch học khác nhau, do đó ta chọn mỗi lịch học làm cá thể trong thuật giải di truyền và trong hai thành phần đó, thì các giờ học là thành phần ổn định hơn về số lượng cũng như về giá trị của chúng, cho nên ta chọn môn học làm đơn vị nhiễm sắc thể trong cá thể. - Vì đối với môn học việc làm nhiễm sắc thể là phù hợp với tính không ổn định của nó : với số lượng các môn phụ thuộc từng lớp học, cũng giống như số lượng nhiễm sắc thể trong cá thể, có chiều dài không nhất thiết phải cố định hay bằng nhau. - Mô hình cá thể trong lịch lớp Thay vì chọn ngẫu nhiên môn học vào các tiết học như đã trình bày, chúng ta sẽ làm ngược lại: chọn ngẫu nhiên tiết học theo môn, vì chúng ta đã chọn môn học làm đơn vị trong cá thể ( theo mô hình trên. - Có nghĩa là, với một cá thể của mô hình xếp lịch lớp, ở bất kỳ thời điểm nào, khi ta đặt nhiễm sắc thể đầu tiên như là môn thứ nhất, nhiễm sắc thể kế tiếp sẽ là môn thứ hai, và tiếp tục cho các nhiễm sắc thể còn lại. - Trong trường hợp một môn được học nhiều lần trong tuần, do có nhiều chứng chỉ / học phần, nên sẽ gây khó khăn cho việc xếp chúng vào trong cá thể. - Cách giải quyết vấn đề này rất đơn giản, chỉ cần đưa chúng vào cá thể với nhiễm sắc thể tương ứng, chẳng khác gì một môn học bình thường khác. - Chúng ta sẽ phân bổ các nhiễm sắc thể như sau: Mỗi nhiễm sắc thể sẽ mang một giá trị số nguyên. - Như ta đã nói phần trên, tương ứng mỗi cá thể là một lịch học thực thụ của lớp. - Chọn qui định đọc và ghi nhận nhiễm sắc thể.. - Giống như cá thể được mô tả ở trên, hàng loạt các cá thể được tạo ra và được xem như quần thể ban đầu trong mô hình thuật giải di truyền của phần xếp lịch lớp. - 3.1.3 Độ thích nghi - chọn cá thể. - Tương ứng với mỗi loại ràng buộc, chúng ta sẽ gán cho chúng một giá trị thích nghi nào đó, mà một khi cá thể đi qua, các ràng buộc được lắp đặt vào, và sẽ cho ra giá trị thích nghi cụ thể cho cá thể đó, kết thúc công việc tính độ thích nghi. - Có nhiều cách để chọn một cá thể tốt. - 3.1.4 Thuật toán lai ghép và đột biến. - Về thuật toán lai ghép, ta dùng lai ghép đoạn: lấy ngẫu nhiên một đoạn nhiễm sắc thể bên nhiễm sắc thể cha, số còn lại sẽ lấy ở bên nhiễm sắc thể mẹ.. - Còn thuật toán đột biến : chỉ việc hoán vị hai nhiễm sắc thể một cách ngẫu nhiên trong cá thể. - Phần này áp dụng thực thi cho tất cả các lớp trong một cơ sở, tương ứng với mỗi lớp sẽ có một file lưu trữ tất cả các lịch lớp mà có thể sử dụng, dưới hình thức các nhiễm sắc thể trong quẩn thể. - 3.2.1 Chọn mô hình cá thể. - Nhìn mô hình cá thể trong lịch lớp ta thấy lớp học trong cơ sở có tính chất như môn học trong lớp, cho nên ta chọn lớp học làm đơn vị của nhiễm sắc thể trong mô hình thuật toán di truyền trong xếp lịch cơ sở. - Và tương tự, ta chọn lịch cơ sở làm cá thể.. - Ở mỗi nhiễm sắc thể là một con số mang tính chất như một trong những chỉ số trong file lưu trữ thông tin cá thể của lịch lớp ( chỉ số một lịch học của lớp). - Như vậy phạm vi giá trị các nhiễm sắc thể sẽ khác nhau, nhưng ta luôn xác định được phạm vi đó một cách rõ ràng, chỉ cần đọc giá trị kích thước của file tương ứng của lớp mà thôi.. - Mô hình cá thể trong lịch cơ sở.. - Giống như trong lịch lớp, cá thể lịch cơ sở cũng phải qua một giai đoạn kiểm tra ban đầu, để có thể ở mức đạt dược dạng đúng của một lịch cơ sở. - Quần thể khởi đầu gồm những cá thể được tạo ra như mô hình trên, nhưng thông tin các lớp học phải được chọn cùng trong một buổi học thuộc cơ sở, và có file lịch lớp đầy đủ. - ở đây kích thước cá thể là số lớp hiện có, cho nên dài hay ngắn tùy theo cơ sở, cũng giống như lịch lớp chiều dài được tính theo số môn hiện có của lớp.. - 3.2.3 Độ thích nghi - chọn cá thể. - Giai đoạn hội tụ cá thể trong quần thể, trên cơ bản việc đánh giá cơ sở tùy theo số lớp, số giờ học và số phòng học. - Với các lần kiểm tra tương ứng với một giá trị thích nghi, cuối cùng tổng các giá trị này chính là độ thích nghi của cá thể. - Công việc không khác gì trong lịch lớp, cá thể được chọn là cá thể tốt nhất, giá trị thích nghi đạt ở mức đỉnh là 0.. - 3.2.4 Thuật toán lai ghép và đột biến. - Sử dụng lại của phần xếp lịch lớp, chọn cá thể theo độ thích nghi, lai ghép ngẫu nhiên đoạn và đột biến hoán vị điểm. - 4.3 Biểu diễn nhiễm sắc thể. - Để trình bày một nhiễm sắc thể ta cần một slot cho mỗt phòng học hàng ngày trong thời khóa biểu. - Nhiễm sắc thể với số lượng là 100 được biểu diễn bằng một lớp Schedule và nó được lưu trữ trong 2 thuộc tính. - Bảng lớp dành cho nhiễm sắc thể dược dùng để quyết định slot đầu tiên. - Đồng thời nhiễm sắc thể được lưu trữ những giá trị phù hợp và những tham số bằng việc sử dụng các thao táo của giải thuật Những giá trị phù hợp được lưu trữ tại:. - Xác suất lai ghép sẽ xảy ra. - 4.4.1 Phép lai ghép. - Như đã nói ở trên phép lai ghép diễn ra bằng cách ghép một hay nhiều đoạn gen từ hai nhiễm sắc thể cha-mẹ để hình thành nhiễm sắc thể mới mang đặc tính của cả cha lẫn mẹ.. - Trong hệ thống này thao tác lai ghép ban đầu kiểm tra một số bất kì với xác suất lai ghép nếu lớn hơn sẽ tiến hành lai ghép và trả ra một nhiễm sắc thể gọi là nhiễm sắc thể đầu tiên. - Quá trình lai ghép kết hợp các dữ liệu trong bảng băm của hai nhiễm sắc thể cha mẹ, và sau đó nó tạo ra véc tơ của các slot theo nội dung của bảng băm mới. - Lai ghép 'Tách' bẳng băm của cả hai nhiễm sắc thể cha mẹ thành các phần có kích thước ngẫu nhiên. - Số của các thành phần được xác định bởi số lượng các điểm lai ghép (cộng thêm một) theo các tham số của nhiễm sắc thể. - Sau đó, nó sao chép thay luân phiên các phần nhiễm sắc thể cha mẹ mẫu thành các nhiễm sắc thể mới, và các hình thức thao tác lai ghép. - Số điểm lai ghép. - Cũng giống như vậy phép đột biến diễn ra bằng cách khi một hoặc một số tình trạng của con không được thừa hưởng từ hai chuỗi nhiễm sắc thể cha mẹ. - Sau đó thao tác đột biến tạo ra một lớp ngẫu nhiên và di chuyển nhiễm sắc thể đến một slot cũng được lựa chọn ngẫu nhiên khác. - Số của lớp học đó sẽ được di chuyển vào một thao tác đơn lẻ được xác định bởi kích thước đột biến trong các tham số của nhiễm sắc thể. - 4.5 Độ thích nghi. - Tương ứng với mỗi loại ràng buộc chúng ta sẽ gán cho chúng một giá trị thích nghi nào đó, mà một khi cá thể đi qua, các ràng buộc được lắp đặt vào, và sẽ cho ra giá trị thích nghi cụ thể cho cá thể đó, kết thúc công việc tính độ thích nghi Bây giờ chúng ta cần phải ấn định một giá trị thích hợp cho các nhiễm sắc thể