- Độ thích nghi xếp hạng (rank method). - Chọn mô hình cá thể. - Độ thích nghi - chọn cá thể 31. - Chọn mô hình cá thể 32. - Độ thích nghi - chọn cá thể 33. - Nói ngắn gọn, một lời giải sẽ được biểu diễn bằng một chuỗi bit, cũng giống như mỗi cá thể đều được quy định bằng gen của cá thể đó vậy. - Như vậy, đối với thuật giải di truyền, một cá thể chỉ có một gen duy nhất và một gen cũng chỉ phục vụ cho một cá thể duy nhất.. - Ban đầu, ta sẽ phát sinh một số lượng lớn, giới hạn các cá thể có gen ngẫu nhiên. - Tập các cá thể này được gọi là quần thể ban đầu (initial population). - Vì phát sinh ngẫu nhiên nên độ "tốt" của lời giải hay tính thích nghi của các cá thể trong quần thể ban đầu là không xác định.. - Thao tác đầu tiên là sao chép nguyên mẫu một nhóm các cá thể tốt từ thế hệ trước rồi đưa sang thế hệ sau (selection). - Các cá thể được chọn thông thường là các cá thể có độ thích nghi cao nhất.. - Thao tác thứ hai là tạo các cá thể mới bằng cách thực hiện các thao tác sinh sản trên một số cá thể được chọn từ thế hệ trước – thông thường cũng là những cá thể có độ thích nghi cao. - Trong thao tác lai tạo, từ gen của hai cá thể được chọn trong thế hệ trước sẽ được phối hợp với nhau (theo một số quy tắc nào đó) để tạo thành hai gen mới.. - Tuy nhiên, nhiều khi do thế hệ khởi tạo ban đầu có đặc tính chưa phong phú và chưa phù hợp nên các cá thể không rải đều được hết không gian của bài toán . - Đó là sự biến đổi ngẫu nhiên một hoặc nhiều thành phần gen của một cá thể ở thế hệ trước tạo ra một cá thể hoàn toàn mới ở thế thệ sau. - Nhưng thao tác này chỉ được phép xảy ra với tần suất rất thấp (thường dưới 0.01), vì thao tác này có thể gây xáo trộn và làm mất đi những cá thể đã chọn lọc và lai tạo có tính thích nghi cao, dẫn đến thuật toán không còn hiệu quả.. - Thế hệ mới được tạo ra lại được xử lý như thế hệ trước (xác định độ thích nghi và tạo thế hệ mới) cho đến khi có một cá thể đạt được giải pháp mong muốn hoặc đạt đến thời gian giới hạn.. - 1.Khởi tạo một quần thể ban đầu với n cá thể.. - Chọn ngẫu nhiên một cặp hai cá thể cha mẹ B và M theo xác xuất Pl. - Sinh hai cá thể mới C1 và C2 từ B và M.. - Chọn ngẫu nhiên một cá thể X theo xác xuất Pd. - Đột biến cá thể X.. - Tính lại độ thích nghi của các cá thể.. - Chọn các cá thể có độ thích nghi tốt đưa vào quá trình mới.. - Đối với những vấn đề bài toán có nhiều tham số, việc biểu diễn gen bằng chuỗi số nhị phân đôi lúc sẽ làm cho kiểu gen của cá thể trở nên quá phức tạp. - “Tính tốt của một cá thể (lời giải) trong một quần thể chỉ là một cơ sở để xác định tính thích nghi của cá thể (lời giải) đó”. - Thông thường, độ thích nghi của lời giải cũng chính là xác suất để cá thể đó được chọn lọc hoặc lai ghép khi tiến hành sinh ra thế hệ kế tiếp. - Ta sẽ lần lượt tìm hiểu 3 phương pháp để xác định tính thích nghi của một cá thể.. - Hàm mục tiêu là hàm dùng để đánh giá độ tốt của một lời giải hoặc cá thể. - Hàm mục tiêu nhận vào một tham số là gen của một cá thể và trả ra một số thực. - Tùy theo giá trị của số thực này mà ta biết độ tốt của cá thể đó (chẳng hạn với bài toán tìm cực đại thì giá trị trả ra càng lớn thì cá thể càng tốt, và ngược lại, với bài toán tìm cực tiểu thì giá trị trả ra càng nhỏ thì cá thể càng tốt).. - Giả sử trong một thế hệ có N cá thể, cá thể thứ i được ký hiệu là ai. - Vậy độ thích nghi của một cá thể ai tính theo độ thích nghi tiêu chuẩn là Chẳng hạn, xét một thế hệ gồm có 6 cá thể với độ tốt (giá trị càng lớn thì cá thể càng tốt) lần lượt cho trong bảng sau Theo công thức trên, tổng tất cả G của 6 phần tử là : 17.5. - Hơn nữa, vì độ thích nghi sẽ ứng với khả năng được chọn lọc trong việc sinh ra thế hệ sau nên người ta thường chọn cách tính sao cho độ thích nghi cuối cùng là một xác suất, nghĩa là tổng độ thích nghi của các cá thể phải nhỏ hơn hoặc bằng 1.. - Cách tính độ thích nghi tiêu chuẩn như trên chỉ thực sự hiệu quả đối với những quần thể có độ tốt tương đối đồng đều giữa các cá thể. - Nếu, vì một lý do nào đó – có thể do chọn hàm mục tiêu không tốt - có một cá thể có độ tốt quá cao, tách biệt hẳn các cá thể còn lại thì các cá thể của thế hệ sau sẽ bị “hút” về phía cá thể đặc biệt đó. - Do đó, sẽ làm giảm khả năng di truyền đến thế sau của các cá thể xấu, tạo nên hiện tượng di truyền cục bộ, từ đó có thể làm giảm khả năng dẫn đến lời giải tốt nhất (vì cá thể đặc biệt đó chưa chắc đã dẫn đến lời giải tốt nhất).. - Phương pháp này không làm việc trên giá trị độ lớn của hàm mục tiêu G mà chỉ làm việc dựa trên thứ tự của các cá thể trên quần thể sau khi đã sắp xếp các cá thể theo giá trị hàm mục tiêu G. - Phương pháp này sẽ cho ta linh động đặt một trọng số để xác định sự tập trung của độ thích nghi lên các cá thể có độ tốt cao, mà vẫn luôn đảm bảo được quy luật: cá thể có độ thích nghi càng cao thì xác suất được tồn tại và di truyền càng cao.. - Một cách ngắn gọn, ta có độ thích nghi (hay xác suất được chọn) của cá thể thứ i được tính theo công thức sau:. - 1) Sắp xếp các cá thể của quần thể giảm dần theo thứ tự của giá trị hàm mục tiêu.. - Đây chính là trọng số xác định độ “hút” của các cá thể tốt.. - 3) Mỗi lượt chọn chỉ chọn một cá thể. - Trong một lượt chọn, lần lượt xét các cá thể theo thứ tự đã sắp. - Nếu xét đến cá thể thứ i mà cá thể đó được chọn thì lượt chọn kết thúc, ta thực hiện lượt chọn kế tiếp. - Ngược lại, nếu cá thể thứ i không được chọn, ta xét đến cá thể thứ i+1. - Ta quy ước rằng, khi đã xét đến một cá thể, thì xác suất để chọn cá thể đó (trong thao tác chọn lọc hoặc lai tạo) luôn là p. - Rất hiển nhiên, khi đã xét đến một cá thể thì xác suất (XS) để KHÔNG chọn cá thể đó sẽ là 1-p.. - Ta ký hiệu a[i] là cá thể thứ i. - Trong đó, XS a[1] được xét =1 vì cá thể đầu tiên luôn được xét đến.. - Dựa vào đặc tính này, ta có thể dễ dàng kiểm soát được tính “hút” của các cá thể tốt trong quần thể bằng cách tăng hoặc giảm trị p tương ứng.. - Nhiễm sắc thể A. - Nhiễm sắc thể B. - Nhiễm sắc thể B. - Chọn lọc cá thể 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ể. - Vì vậy, đánh giá độ thích nghi của cá thể để tìm ra cá thể tốt nhất. - Cá thể tốt nhất sẽ có điểm thấp nhất hoặc lớn nhất.. - Theo thuyết Darwin, cá thể tốt nhất sẽ tồn tại và tạo ra các cá thể con mới. - Các cá thể được chọn theo độ thích nghi của chúng. - Phương pháp này sẽ sắp hạng cá thể dựa trên độ thích nghi của chúng. - Cá thể xấu nhất sẽ có giá trị 1, kế tiếp là 2… Và cá thể tốt nhất có độ thích nghi N(N là số các nhiễm sắc thể trong quần thể).. - Trong bài toán dạng này, một cách tự nhiên thường sử dụng GA mã hóa số thực, mỗi cá thể được biểu thị bởi một vectơ Rn (tất nhiên phải thuộc miền xác định D). - Với hai cá thể cha mẹ p1 = (x1,x2,…,xn) và p2 = (y1,y2,…,yn) các cá thể con được sinh ra như sau.. - n), các cá thể con được sinh ra như sau:. - Sau đó cá thể con được sinh ra như sau:. - Phép lai ghép này chỉ tạo một cá thể con từ hai cá thể cha mẹ. - Mỗi thành phần zi của cá thể con được chọn theo phân phối ngẫu nhiên đều trong khoảng [min(xi,yi. - Việc chọn lọc các cá thể từ một quần thể dựa vào độ thích nghi của mỗi cá thể. - Các cá thể có độ thích nghi cao có nhiều khả năng được chọn lựa (những cá thể khỏe mạnh có nhiều khả năng được phối giống). - Với cá thể x. - Rõ ràng với cách chọn này, các cá thể có độ thích nghi càng cao (gây ra tổng lớn hơn q) thì càng được chọn. - Các cá thể có độ thích nghi cao có thể có một hay nhiều bản sao, các cá thể có độ thích nghi thấp có thể không có mặt trong thế hệ sau (nó bị chết đi).. - Trên các cá thể được chọn lọc (sau khi thực hiện xong toán tử chọn lọc), ta tiến hành toán tử lai ghép. - Xác suất này đưa ra hy vọng là có n.pc cá thể được lai ghép.. - pc thì cá thể đó được chọn để lai ghép. - Từ các cá thể được chọn để lại ghép, ta cặp đôi chúng một cách ngẫu nhiên. - Tổng quát, giả sử có hai cặp nhiễm sắc thể của hai cá thể được chọn lai ghép:. - Ta thực hiện đột biến trên các cá thể sau khi đã lai ghép. - Sinh sản hữu tính: sử dụng phép lai ghép từ cha me để tạo ra các cá thể mới mang một phần đặc điểm cha và một phần đặc điểm của mẹ.. - Kích thước quần thể: PopSize, là số cá thể duy trì qua mỗi thế hệ tiến hóa của thuật giải di truyền.Xác xuất đột biến: Pm là xác suất đột biến của gen.Xác suất lai: Pc là xác suất một cá thể được chọn cho phép lai ghép.. - 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 ba thành phần đó, các tiết 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 giáo viên, môn học làm đơn vị nhiễm sắc thể trong cá thể. - Tương ứng mỗi cá thể là một lịch học thực thụ của lớp. - 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. - Độ 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. - 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ể. - 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ịch 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 toàn trường. - Và tương tự, ta chọn 1 thời khóa biểu toàn trường 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. - Giống như trong lịch lớp, cá thể lịch toàn trường cũng phải qua một giai đoạn kiểm tra ban đầu, để có thể ở mức đạt được dạng đúng của một thời khóa biểu.. - 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.. - 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.. - 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 tại một đoạn và đột biến hoán vị điểm