Phương pháp tối ưu hàm kernel của thuật toán MPM

hình khác nhau ñược ñưa ra trong phương pháp trích chọn. ðiển hình là hai mô hình: Filter và Wrapper. Hình 2.2. Mô hình Filter 1 2 Filter 3 A ht t p : / / e t r i t h u c . v n Hình 2.3. Mô hình Wrapper Giải thích hình vẽ: A: Tập ñặc trưng ñầu vào. 1: Bộ sinh tập con (Feature Subset Generator). 2: Bộ ñánh giá (Feature Subset Evaluator). 3: Các thuật toán học máy (Followed Machine learning Algorithm) 4: Thuật toán học máy ñiều khiển (Central Machine learning Algorithm). Mô hình Filter ñánh giá mỗi cá thể bằng một vài tiêu chuẩn, rồi chọn ra tập con các thuộc tính có ñộ ñánh giá cao nhất. Nhìn chung, Filter coi tiến trình của trích chọn thuộc tính như tiến trình thực thi trước, sau ñó mới sử dụng thuật toán ñể phân lớp. Wrapper sử dụng một thuật toán tìm kiếm ñể ñánh giá tập con các thuộc tính coi như là một nhóm hơn là một cá thể riêng lẻ. Mô hình Wrapper ñược ñặt vào trung tâm của một thuật toán máy học cụ thể. Nó ñánh giá ñộ tốt của những tập con ñặc trưng tùy theo ñộ chính xác học của tập con, ñiều này xác ñịnh thông qua tỷ lệ. Những thuật toán tìm kiếm cũng sử dụng hàm ñánh giá kinh nghiệm (heuristics) ñể hướng dẫn việc tìm kiếm tập trung vào các ñối tượng có triển vọng. 1 2 4 Wrapper Model 3 A ht t p : / / e t r i t h u c . v n 2.2.2. ðánh giá hai mô hình Filter và Wrapper 2.2.2.1. Filter • Ưu ñiểm: - Không có xử lý học máy trong quá trình lựa chọn các ñặc trưng. - Dễ dàng nhận diện và thời gian tiêu thụ ít hơn mô hình Wrapper. • Nhược ñiểm: - Hiệu suất sản sinh các tập con ñặc trưng là không ñảm bảo vì nó thường ñánh giá một tập con ñặc trưng chỉ dựa trên ñặc trưng nhỏ thiên về nguyên lý mà không tính tới ñộ chính xác của kết quả học máy. - Kết quả thu ñược bị giảm sút về ñộ chính xác học ở những giai ñoạn sau vì các hàm ñánh giá hiện thời ñược sử dụng thường thiên về giá trị ở một vài phạm vi, do ñó sẽ không ñánh giá một cách khách quan tầm quan trọng của các ñặc trưng. 2.2.2.2. Mô hình Wrapper • Ưu ñiểm: - ðảm bảo hiệu suất của kết quả học hơn mô hình Filter. • Nhược ñiểm: - Ít ñược sử dụng hơn môt hình Filter trên thực tế vì:
Tiến trình học tốn kém về thời gian ñến mức thời gian thực hiện ñưa ra bởi một thuật toán sử dụng mô hình Wrapper là không chấp nhận ñược.
Với một hệ thống kích thước cực lớn, mô hình này không thực tế do phạm vi của nó buộc phải thu nhỏ lại trước khi thuật toán học máy ñược áp dụng. ht t p : / / e t r i t h u c . v n
Kết quả ñánh giá của mô hình phụ thuộc nhiều vào thuật toán học máy ñiều khiển. 2.3. Một số kỹ thuật xử lý 2.3.1. Bộ sinh tập con (Feature Subset Generator) Tùy từng chiến lược cụ thể, bộ sinh tập con sẽ tạo ra những tập con ñặc trưng từ một tập ñầu vào tương ứng. ðầu ra của bộ sinh sẽ xác ñịnh thuật toán trích chọn ñặc trưng của việc tìm ñường và tìm kiếm phạm vi trong một không gian ñặc trưng tương ứng. Nói chung, bộ sinh có hai chiến lược ñể sản sinh ra những tập con ñặc trưng: • ðầy ñủ (Completely): Một bộ khởi tạo ñầy ñủ có thể sản sinh ra tất cả các tập con từ một tập ñặc trưng ñầu vào, do vậy phạm vi tìm kiếm của chiến lược này là NP ñầy ñủ, tuy nhiên ñiều này không phải lúc nào cũng chứng tỏ tìm kiếm vét cạn là cần thiết trong thực tế, bởi vì một số công nghệ như: ñường biên và rẽ nhánh có thể ñược áp dụng ñể lược bớt phạm vi tìm kiếm tốt nhất. Bởi vậy nếu là thuật toán trích chọn với bộ khởi tạo ñầy ñủ, thực nghiệm chỉ ra rằng không gian tìm kiếm lớn nhất là O(2k). Mà ñối với hầu hết những hệ thống học máy thực, ñiều này là không cần thiết phải ñánh giá tất cả những tập con từ một tập ñặc trưng tương ứng. Thường thì, thuật toán trích chọn với bộ khởi tạo ñầy ñủ có thể tìm ra một tập con ñặc trưng tối ưu của hệ thống học máy nhưng ñòi hỏi thời gian thực thi phức tạp. Liu H. [12] ñã ñưa ra bộ khởi tạo ñầy ñủ ñặc biệt mà sản sinh một cách ngẫu nhiên ra những tập con ñặc trưng dựa vào thuật toán Las Vegas (LV). Thuật toán LV có thể tìm kiếm trên toàn bộ không gian ñáp án rồi sau ñó ñưa ra kết quả tối ưu ñảm bảo. Tuy nhiên khác với những bộ khởi tạo ñầy ñủ khác, ñối với một ứng dụng thực tế, khả năng thực thi của bộ khởi tạo Liu là hoàn toàn thay ñổi, nó phụ thuộc nhiều vào quá trình phân chia dữ liệu ngẫu nhiên trong toàn bộ hệ thống học máy. • Kinh nghiệm (Heuristically): ðể lược bớt không gian tìm kiếm, bộ khởi tạo kinh nghiệm sản sinh ra các tập con ñặc trưng dựa vào những kinh nghiệm chiến lược nào ñó. Có ba kỹ thuật tìm kiếm tập con ñiển hình là: ht t p : / / e t r i t h u c . v n - Lựa chọn tiến (Forward Selection): các tập con ñặc trưng ñược khởi tạo trước hết là rỗng (null), sau ñó liên tục gán những tính năng tốt nhất hiện thời cho tập con ñó cho ñến khi không còn tính năng nào nữa hay các ñiều kiện thực thi ñưa ra ñã ñược tiếp nhận hết. - Lược bỏ lùi (Backward Elimination): Các tập con ñặc trưng ñược khởi tạo trước hết là ñầy ñủ các ñặc trưng, sau ñó loại bỏ lần lượt những ñặc trưng kém nhất hiện thời từ các tập con ñó, cho ñến khi không còn ñặc trưng nào hoặc các ñiều kiện thực thi ñưa ra ñã ñược triệt tiêu hết. - Lựa chọn hai hướng (Bi – direction Selection): các tập con ñặc trưng ñược khởi tạo trước hết là rỗng, ñầy, hoặc sản sinh ngẫu nhiên một tập con ñặc trưng, sau ñó liên tục hoặc là gán tính năng tốt nhất hiện thời cho tập con ñó hoặc là triệt tiêu tính năng kém nhất từ các tập con ñó. ðể từ ñó ñưa ra những giá trị ñịnh hướng tốt nhất ở mỗi lần lặp lại ñó. Quá trình tiếp tục cho tới khi tất cả ñiều kiện ñược ñưa ra từ trước ñã ñược tiếp nhận hết. Bộ phận khởi tạo kinh nghiệm giảm thiểu phạm vi tìm kiếm ña thức số mũ, do ñó giảm thời gian thực hiện thuật toán phức tạp trong phương pháp trích chọn. Tuy nhiên, thuật toán chỉ ñưa ra một lượng nhỏ kết quả tối ưu, khi thực hiện tìm ñường và tìm kiếm phạm vi của bộ phận khởi tạo, kết quả này ñược ñảm bảo thông qua những thuật toán này. 2.3.2. Bộ ñánh giá tập con ñặc trưng (Feature Subset Evaluator) Hiệu suất của một tập con ñặc trưng ñược ñánh giá dựa trên cơ sở nào ñó mà bộ ñánh giá ñạt ñược. Bộ ñánh giá của những mô hình thuật toán khác nhau là khác nhau. Bộ ñánh giá của mô hình Filter thường là các hàm ñánh giá, trong khi của mô hình Wrapper là ñộ học chính xác ñạt ñược bởi quá trình thực thi thuật toán học máy ñiều khiển trên hệ thống học. • Hàm ñánh giá ht t p : / / e t r i t h u c . v n Những hàm ñánh giá ñiển hình dùng ñể ño ñạc và phân biệt khả năng phân lớp của những ñặc ñiểm khác nhau trên các mẫu. Thực tế, các hàm ñánh giá khác nhau thường ñược dùng hiện nay như: xấp xỉ chất lượng (Approximation Quality), ñộ quan trọng của thuộc tính (Feature Importance), trọng số của thuộc tính (Feature Weight) … • Học chính xác Trong mô hình Wrapper, ñể ước lượng ñộ học máy chính xác, trước hết, các mẫu của hệ thống học phải ñược chia ngẫu nhiên làm hai hệ thống con, chẳng hạn như: hệ thống huấn luyện và hệ thống kiểm tra, trong ñó, cấu trúc của hai hệ thống con có cùng ñặc ñiểm và ñược tạo ra bởi bộ sinh; sau ñó thuật toán học máy ñiều khiển sẽ thực hiện trên hệ thống con huấn luyện (training) và tiếp thu ñộ học chính xác ñược xác ñịnh nhờ quá trình kiểm tra kết quả học ñược với hệ thống kiểm tra (testing). Hiển nhiên, ñộ chính xác ñạt ñược trong trường hợp này là giá trị ngẫu nhiên, nó phụ thuộc lớn vào kết quả của việc chia mẫu. ðể giảm thiểu mức ñộ ngẫu nhiên của việc ước lượng ñộ chính xác học máy, bộ ñánh giá của mô hình Wrapper thường xuyên tính toán ñộ chính xác học máy thông qua thuật toán ñánh giá chéo k – lần. 2.3.3. Thuật toán học ñiều khiển (Central Machine learning Algorithm) Trong mô hình Wrapper, thuật toán học máy ñiều khiển có ảnh hưởng lớn tới ước lượng ñộ chính xác học của một tập con ñặc trưng. Do vậy, thuật toán ñóng vài trò quyết ñịnh trong mô hình Wrapper. Thuật toán thường ñược chọn ở ví trí trung tâm mô hình thường là: ID3, CN2, C4.5 … 2.4. Kết luận Trích chọn ñược xem như bước tiền xử lý dữ liệu. Phương pháp này lọc ra những ñặc trưng tốt nhất, ñồng thời loại bỏ nhiễu, giảm bớt chiều trong dữ liệu. Hai mô hình phổ biến trong phương pháp trích chọn thuộc tính ñặc trưng là Filter và Wrapper. Mỗi mô hình ñều có những ưu ñiểm và nhược ñiểm riêng. Tùy từng yêu cầu và trường hợp cụ thể ht t p : / / e t r i t h u c . v n mà ta có thể áp dụng một trong hai mô hình này. ht t p : / / e t r i t h u c . v n Chương 3: Genetic Algorithms 3.1. Giới thiệu Thuật toán di truyền là thuật toán tối ưu ngẫu nhiên dựa trên cơ chế chọn lọc tự nhiên và tiến hóa di truyền. Thuật toán di truyền ñược ứng dụng ñầu tiên trong hai lĩnh vực chính: tối ưu hóa và học tập của máy. Trong lĩnh vực tối ưu hóa thuật toán di truyền ñược phát triển nhanh chóng và ứng dụng trong nhiều lĩnh vực khác nhau như tối ưu hàm, xử lý ảnh, bài toán hành trình người bán hàng, nhận dạng hệ thống và ñiều khiển. Thuật toán di truyền cũng như các thuật toán tiến hóa nói chung, hình thành dựa trên quan niệm cho rằng, quá trình tiến hóa tự nhiên là quá trình hoàn hảo nhất, hợp lý nhất và tự nó ñã mang tính tối ưu. Quan niệm này có thể xem như một tiên ñề dúng, không chứng minh ñược, nhưng phù hợp với thực tế khách quan. Quá trình tiến hóa thể hiện tính tối ưu ở chỗ, thế hệ sau bao giờ cũng tốt hơn (phát triển hơn, hoàn thiện hơn) thế hệ trước bởi tính kế thừa và ñấu tranh sinh tồn. 3.2. ðộng lực Thuật giải di truyền cung cấp một phương pháp học ñược thúc ñẩy bởi sự tương tự với sự tiến hóa sinh học. Thay vì tìm kiếm các giả thuyết từ tổng quát ñến cụ thể hoặc từ ñơn giản ñến phức tạp, GAs tạo ra các giả thuyết kế tiếp bằng cách lặp việc ñột biến và việc tái hợp các phần của giả thuyết ñược biết hiện tại là tốt nhất. Ở mỗi bước, một tập các giả thuyết ñược gọi là quần thể hiện tại ñược cập nhật bằng cách thay thế vài phần nhỏ quần thể bởi cá thể con của các giả thuyết tốt nhất ở thời ñiểm hiện tại. Sự phổ biến của GAs ñược thúc ñẩy bởi các yếu tố sau: • Tiến hóa là một phương pháp mạnh và thành công cho sự thích nghi bên trong các hệ thống sinh học. ht t p : / / e t r i t h u c . v n • GA có thể tìm kiếm trên các không gian giả thuyết có các phần tương tác phức tạp, ở ñó ảnh hưởng của mỗi phần lên toàn thể ñộ thích nghi giả thuyết khó có thể mô hình hóa. • Thuật giải GA có thể ñược thực hiện song song và có thể tận dụng thành tựu của phần cứng máy tính. 3.3. Thuật giải di truyền 3.3.1. Nội dung thuật toán Bài toán dành cho GAs là tìm kiếm trên không gian các giả thuyết ứng cử ñể xác ñịnh giả thuyết tốt nhất. Trong GAs “giả thuyết tốt nhất” ñược ñịnh nghĩa như là một giả thuyết tối ưu hóa một ñại lượng số ñược ñịnh nghĩa trước cho bài toán sắp tới, ñược gọi là ñộ thích nghi của giả thuyết. Ví dụ, nếu tác vụ học hỏi là bài toán xấp xỉ một hàm chưa biết cho tập mẫu huấn luyện gồm dữ liệu ñầu vào và dữ liệu ñầu ra, thì ñộ thích nghi có thể ñược ñịnh nghĩa như là ñộ chính xác của giả thuyết trên dữ liệu huấn luyện này. Nếu tác vụ là học chiến lược chơi cờ, ñộ thích nghi có thể là số ván thắng của chiến lược này khi ñấu với các chiến lược khác trong quần thể hiện tại. Mặc dù các thuật giải di truyền ñược thực hiện thay ñổi theo bài toán cụ thể, nhưng chúng chia sẻ chung cấu trúc tiêu biểu sau: Thuật giải hoạt ñộng bằng cách cập nhật liên tục tập giả thuyết – ñược gọi là quần thể. Ở mỗi lần lặp, tất cả các cá thể trong quần thể ñược ước lượng tương ứng với hàm thích nghi. Rồi quần thể mới ñược tạo ra bằng cách lựa chọn có xác suất các cá thể thích nghi tốt nhất từ quần thể hiện tại. Một số trong những cá thể ñược chọn ñược ñưa nguyên vẹn vào quần thể kế tiếp. Những cá thể khác ñược dùng làm cơ sở ñể tạo ra các cá thể con bằng cách áp dụng các tác ñộng di truyền: lai ghép và ñột biến. GA( Fitness, Fitness_threshold, p, r, m) { // Fitness: hàm gán thang ñiểm ước lượng cho một giả thuyết. // Fitness_threshold: Ngưỡng xác ñịnh tiêu chuẩn dừng giài thuật tìm kiếm. // p: Số cá thể trong quần thể giả thuyết. ht t p : / / e t r i t h u c . v n // r: Phân số cá thể trong quần thể ñược áp dụng toán tử lai ghép ở mỗi bước. // m: Tỉ lệ cá thể bị ñột biến. • Khởi tạo quần thể: P  Tạo ngẫu nhiên p cá thể giả thuyết • Ước lượng: Ứng với mỗi h trong P, tính Fitness(h) • while [max Fitness(h)] < Fitness_threshold do Tạo thế hệ mới, PS 1. Chọn cá thể: chọn theo xác suất (1 – r)p cá thể trong quần thể P thêm vào PS. Xác suất Pr(hi) của giả thuyết hi thuộc P ñược tính bởi công thức: 2. Lai ghép: chọn lọc theo xác suất 2 r p× cặp giả thuyết từ quần thể P, theo Pr(hi) ñã tính ở bước trên. Ứng với mỗi cặp , tạo ra hai con bằng cách áp dụng toán tử lai ghép. Thêm tất các các con vào PS. 3. ðột biến: Chọn m% cá thể của PS với xác suất cho mỗi cá thể là như nhau. Ứng với mỗi cá thể biến ñổi một bit ñược chọn ngẫu nhiên trong cách thể hiện của nó. 4. Cập nhật: P  PS. 5. Ước lượng: Ứng với mỗi h trong P, tính Fitness(h) • Trả về giả thuyết trong P có ñộ thích nghi cao nhất. } Bảng 3.1. Thuật giải di truyền mẫu Quần thể gồm p cá thể. Ở mỗi lần lặp, quần thể kế tiếp PS ñược hình thành từ việc lựa chọn theo xác suất các giả thuyết hiện tại theo ñộ thích nghi của chúng và bằng cách thêm vào các giả thuyết mới. Các giả thuyết mới ñược tạo ra bằng cách áp dụng toán tử lai ghép cho cặp giả thuyết thích nghi nhất và bằng cách tạo ra các ñột biến ñiểm ñơn trong thế hệ giả thuyết kết quả. Quá trình này ñược lặp cho ñến khi các giả thuyết thích hợp ñược phát hiện. Các toán tử lai ghép và ñột biến tiêu biểu ñược ñịnh nghĩa trong bảng kế tiếp. Một thuật giải di truyền mẫu ñược mô tả trong bảng 3.1. Các ñầu vào cho thuật giải này bao gồm hàm tính ñộ thích nghi ñể tính hạng cho các giả thuyết ứng cử, một giá trị ngưỡng ñược ñịnh nghĩa cấp ñộ thích nghi có thể chấp nhận ñể kết thúc thuật giải, kích thước quần thể, và các tham số quyết ñịnh các quần thể kế tiếp ñược tạo ra như thế nào: phần quần thể bị thay thế ở mỗi thế hệ và tỉ lệ ñột biến. ht t p : / / e t r i t h u c . v n Lưu ý trong thuật giải này, ở mỗi bước lặp qua vòng lặp chính tạo ra một thế hệ mới các giả thuyết dựa vào quần thế hệ hiện tại. Trước tiên, một số giả thuyết ñược chọn từ quần thể hiện tại ñể ñưa vào thế hệ kế tiếp. Những giả thuyết này ñược chọn theo xác suất, ở ñây xác suất của giả thuyết ñược tính bởi: Vì vậy, xác suất ñể giả thuyết ñược chọn tỉ lệ với ñộ thích nghi của nó và tỉ lệ nghịch với ñộ thích nghi của các giả thuyết cạnh tranh khác trong quần thể hiện tại. Một khi các cá thể này của thế hệ hiện tại ñã ñược chọn ñể ñưa vào quần thể thế hệ kế tiếp, các cá thể thêm vào ñược tạo ra dùng toán tử lai ghép. Lai ghép, ñược ñịnh nghĩa chi tiết trong phần kế tiếp, lấy hai giả thuyết từ thế hệ hiện tại và tạo ra hai giả thuyết con bằng cách kết hợp các phần của hai giả thuyết cha. Các giả thuyết cha ñược chọn theo xác suất từ quần thể hiện tại, sử dụng hàm xác suất ñược cho bởi phương trình (2.1). Sau khi các cá thể mới ñược tạo ra từ hoạt ñộng lai ghép này, quần thế thế hệ mới bây giờ có ñủ số lượng thành viên mong muốn. Lúc này, một phân số m nào ñó các cá thể này ñược chọn một cách ngẫu nhiên, và tất cả các ñột biến ngẫu nhiên ñược thực hiện ñể thay ñổi các cá thể này. 3.3.2. Thể hiện các giả thuyết Các giả thuyết trong GAs thường ñược thể hiện dưới dạng chuỗi các bit, ñể chúng có thể dễ dàng ñược thực hiện bởi các toán tử di truyền là ñột biến và lai ghép. Các giả thuyết ñược thể hiện bởi chuỗi bit này có thể khá phức tạp. Ví dụ, tập các luật if-then có thể dễ dàng ñược thể hiện theo cách này, bằng cách chọn một cách thức mã hóa các luật ñể phân bố các chuỗi con riêng cho mỗi ñiều kiện trước và ñiều kiện sau của luật. ðể thấy các luật if-then có thể ñược mã hóa bằng các chuỗi bit như thế nào, trước tiên hãy xem chúng ta có thể sử dụng chuỗi bit như thế nào ñể mô tả ràng buộc trên giá trị của thuộc tính ñơn. Lấy một ví dụ, hãy xem xét thuộc tính Outlook, thuộc tính này có thể lấy bất kì giá trị nào trong ba giá trị: Sunny, Overcast hoặc Rain. Một cách rõ ràng ñể thể ht t p : / / e t r i t h u c . v n hiện ràng buộc cho Outlook là dùng một chuỗi bit có chiều dài 3, mỗi vị trí bit tương ứng với một trong ba giá trị có thể của nó. ðặt giá trị 1 ở một vài vị trí ñể chỉ ra rằng thuộc tính ñược phép lấy giá trị tương ứng. Ví dụ, chuỗi 010 thể hiện ràng buộc Outlook phải lấy giá trị thứ hai trong các giá trị này, hay là Outlook = Overcast. Một cách tương tự, chuỗi 011 thể hiện ràng buộc tổng quát hơn là cho phép hai giá trị có thể, hay là Outlook = Overcast Rain. Chú ý 111 thể hiện ràng buộc có thể tổng quát nhất, chỉ ra rằng chúng ta không quan tâm giá trị nào trong các giá trị có thể của nó mà thuộc tính giữ. ðưa ra phương pháp này ñể thể hiện các ràng buộc trên thuộc tính ñơn, các liên kết của các ràng buộc trên nhiều thuộc tính có thể dễ dàng ñược thể hiện bằng cách nối các chuỗi bit tương ứng. Ví dụ, xem xét thuộc tính thứ hai, Wind có thể lấy giá trị Strong hoặc Weak. ðiều kiện trước của luật chẳng hạn như: Có thể ñược biểu diễn bởi chuỗi bit có chiều dài là 5 sau: Outlook Wind 011 10 Các ñiều kiện sau của luật (chẳng hạn như PlayTennis = yes) có thể ñược thể hiện theo kiểu tương tự. Vì vậy, toàn bộ luật có thể ñược mô tả bởi móc nối các chuỗi bit mô tả các ñiều kiện ñầu, cùng với chuỗi bit mô tả ñiều kiện sau của luật. Ví dụ, luật IF Wind = Strong THEN PlayTennis = yes sẽ ñược thể hiện bởi chuỗi: Outlook Wind PlayTennis 111 10 10 ở ñây 3 bit ñầu tiên mô tả ràng buộc “không quan tâm” trên Outlook , hai bit kế tiếp mô tả ràng buộc trên Wind, và hai bit cuối cùng mô tả ñiều kiện sau của luật (ở ñây chúng ta giả sử PlayTennis có thể lấy giá trị Yes hoặc No). Chú ý chuỗi bit thể hiện luật chứa một chuỗi con cho mỗi thuộc tính trong không gian giả thuyết, thậm chí thuộc tính không ht t p : / / e t r i t h u c . v n bị ràng buộc bởi các ñiều kiện trước. ðiều này tạo ra một chuỗi bit có chiều dài cố ñịnh ñể thể hiện các luật, trong ñó các chuỗi con ở các vị trí cụ thể mô tả các ràng buộc trên các thuộc tính cụ thể. ðưa ra cách thể hiện này cho các luật ñơn, chúng ta có thể thể hiện tập các luật bằng cách móc nối các thể hiện chuỗi bit của các luật riêng biệt. Trong thiết kế mã hóa chuỗi bit cho một vài không gian giả thuyết, thật là hữu ích ñể sắp xếp cho mọi chuỗi bit tuân thủ theo cú pháp ñể thể hiện một giả thuyết ñược ñịnh nghĩa tốt. ðể mô tả, chú ý cách mã hóa luật ở ñoạn trên, chuỗi bit 111 10 11 thể hiện luật có ñiều kiện trước không ràng buộc thuộc tính mục tiêu PlayTennis. Nếu tránh xem xét giả thuyết này, chúng ta có thể mượn một cách mã hóa khác (ví dụ phân bố chỉ một bit cho ñiều kiện sau ñể chỉ ñịnh giá trị là Yes hoặc No), thay ñổi các toán tử di truyền ñể tránh một cách tường minh việc xây dựng các chuỗi bit như thế, hoặc ñơn giản gán một ñộ thích nghi rất thấp cho các chuỗi bit như vậy. 3.3.3. Các toán tử di truyền Những thế hệ sau trong GAs ñược quyết ñịnh bởi tập các toán tử tái hợp và ñột biến các cá thể ñược chọn từ quần thể hiện tại. Các toán tử GAs tiêu biểu ñể thực hiện các giả thuyết chuỗi bit ñược mô tả trong bảng 3.2. Các toán tử này tương ứng với các phiên bản ñược ý tưởng hóa của các hoạt ñộng di truyền trong tiến hóa sinh học. Hai toán tử phổ biến nhất là lai ghép và ñột biến. Toán tử lai ghép tạo ra hai con từ hai chuỗi cha bằng cách sao chép các bit ñược chọn lựa từ mỗi cha. Bit ở vị trí i trong mỗi con ñược sao chép từ bit ở vị trí i của một trong hai cha. Chọn lựa cha nào phân phối bit cho vị trí i ñược quyết ñịnh bởi thêm vào một chuỗi mặt nạ lai ghép. ðể minh họa, xem xét toán tử lai ghép ñiểm ñơn (single-point) ở ñầu bảng 3.2. Xem xét hai con trên nhất trong trường hợp này. Con này lấy năm bit ñầu tiên của nó từ cha thứ nhất và sáu bit còn lại từ cha thứ hai, bởi mặt nạ lai ghép là 11111000000 xác ñịnh các lựa chọn này cho mỗi vị trí bit. Con thứ hai dùng cùng mặt nạ lai ghép, nhưng ñổi vai trò của hai cha. Do ñó, nó chứa các bit không ñược dùng bởi con ñầu tiên. Trong lai ghép ht t p : / / e t r i t h u c . v n ñiểm ñơn, mặt nạ lai ghép luôn luôn ñược xây dựng sao cho nó bắt ñầu với chuỗi chứa n giá trị 1 liên tục, ñược theo sau một số giá trị 0 cần thiết ñể hoàn chỉnh chuỗi. Cách này tạo ra cá thể con có n bit ñầu ñược phân phối bởi một cha và các bit còn lại bởi cha thứ hai. Mỗi lần toán tử lai ghép ñiểm ñơn ñược áp dụng, ñiểm lai ghép n ñược chọn ngẫu nhiên, rồi mặt nạ lai ghép ñược tạo và áp dụng. Bảng 3.2. Các toán tử chung cho thuật giải di truyền. Trong lai ghép hai ñiểm(ñiểm kép), cá thể con ñược tạo ra bởi thay thế các ñoạn trung gian của một cá thể cha vào giữa của chuỗi cha thứ hai. Nói một cách khác, mặt nạ lai ghép là một chuỗi bắt ñầu với n0 trị 0, ñược theo sau bởi chuỗi liên tục n1 trị 1, ñược theo sau bởi một số trị 0 cần thiết ñể hoàn chỉnh chuỗi. Mỗi lần toán tử lai ghép hai ñiểm ñược áp dụng, một mặt nạ ñược tạo ra bằng cách chọn ngẫu nhiên các số nguyên n0 và n1. Thí 11101001000 00001010101 11101010101 00001001000 11111000000 11101001000 00001010101 11001011000 00101000101 00111110000 11101001000 00001010101 10001000100 01101011001 00111110000 11101001000 11101011000 Các chuỗi ban Mặt nạ lai ghép Các cá thể con Lai ghép ñiểm ñơn: Lai ghép ñiểm kép: Lai ghép ñồng nhất: ðột biến ñiểm: ht t p : / / e t r i t h u c . v n dụ, trong ví dụ ñược chỉ ra ở bảng 3.2 cá thể con ñược tạo ra dùng một mặt nạ với n0 = 2 và n1 = 5. Như lai ghép trước, hai cá thể con ñược tạo ra bằng cách hoán ñổi vai trò của hai cá thể cha. Lai ghép ñồng nhất kết hợp các bit ñược lấy mẫu ñồng nhất từ hai cá thể cha, như ñược minh họa trong trong bảng 3.2. Trong trường hợp này, mặt nạ lai ghép ñược tạo ra như là một chuỗi bit ngẫu nhiên với mỗi bit ñược chọn ngẫu nhiên và ñộc lập với các bit khác. Thêm vào các toán tử tái kết hợp - tạo ra cá thể con bằng cách kết hợp các phần của hai cá thể cha, một loại toán tử thứ hai tạo ra cá thể con từ một cá thể cha. Cụ thể là toán tử ñột biến tạo ra những thay ñổi ngẫu nhiên nhỏ cho chuỗi bit bằng cách chọn một bit ở vị trí ngẫu nhiên, rồi thay ñổi giá trị của nó. ðột biến thường ñược thực hiện sau khi lai ghép ñược áp dụng như trong giải thuật mẫu trong bảng 3.1. Một vài hệ thống GAs mượn thêm một vài toán tử, các toán tử ñặc biệt ñược chuyên biệt hóa cho biểu diễn giả thuyết cụ thể ñược sử dụng bởi hệ thống.Ví dụ, Grefenstette et al. (1991) mô tả hệ thống học tập luật ñiều khiển robot. Nó sử dụng ñột biến và lai ghép cùng với một toán tử ñể chuyên biệt hóa các luật. 3.3.4. Hàm thích nghi và sự chọn lọc Hàm thích nghi ñịnh nghĩa tiêu chuẩn ñể xếp hạng các giả thuyết tiềm ẩn và ñể chọn lọc chúng theo xác suất ñể ñưa vào quần thể thế hệ kế tiếp. Nếu tác vụ là học các luật phân loại, thì hàm thích nghi thông thường có một thành phần cho ñiểm ñộ chính xác phân loại của luật trên tập mẫu huấn luyện ñược cho. Thường các tiêu chuẩn khác có thể ñược bao hàm, chẳng hạn như ñộ phức tạp và mức ñộ tổng quát của luật. Một cách tổng quát hơn, khi giả thuyết chuỗi bit ñược hiểu như là một thủ tục phức tạp (ví dụ, khi chuỗi bit thể hiện tập chọn lọc, các luật if-then sẽ ñược móc xích với nhau, ñể ñiều khiển thiết bị robot), hàm thích nghi có thể ño hiệu suất tổng của thủ tục kết quả hơn là hiệu suất của các luật riêng biệt. ht t p : / / e t r i t h u c . v n Trong thuật giải GA mẫu ñược chỉ trong bảng 3.1, xác suất ñể một giả thuyết ñược chọn ñược cho bởi tỉ số của ñộ thích nghi của nó với ñộ thích nghi của các thành viên khác của quần thể hiện tại, như ñã thấy trong phương trình tính giá trị thích nghi. Phương pháp này thỉnh thoảng thường ñược gọi là sự chọn lọc tỉ lệ ñộ thích nghi, hoặc sự chọn lọc vòng roulette. Các phương pháp khác dùng ñộ thích nghi ñể chọn lọc các giả thuyết cũng sẽ ñược ñề xuất. Ví dụ, sự chọn lọc kiểu vòng thi ñấu, hai giả thuyết ñầu tiên ñược chọn ngẫu nhiên từ quần thể hiện tại. Với một vài xác suất p ñược ñịnh nghĩa trước hai cá thể này càng phù hợp càng ñược chọn và với xác suất (1 – p) giả thuyết càng ít phù hợp càng ñược chọn. Sự chọn lọc theo vòng thi ñấu thường tạo ra quần thể khác nhau nhiều hơn so với sự chọn lọc tỉ lệ với ñộ thích nghi (Goldberg và Deb 1991). Trong phương pháp sự chọn lọc theo hạng, các giả thuyết trong quần thể hiện tại ñầu tiên sẽ ñược sắp xếp theo ñộ thích nghi. Xác suất ñể giả thuyết sẽ ñược chọn tỉ lệ với hạng của nó trong danh sách ñã sắp xếp hơn là ñộ thích nghi của nó. ht t p : / / e t r i t h u c . v n Chương 4: Minima