Tiếp cận thuật giải di truyền để tăng hiệu quả phân lớp dữ liệu

Nội dung text: Tiếp cận thuật giải di truyền để tăng hiệu quả phân lớp dữ liệu

1. TIẾP CẬN THUẬT GIẢI DI TRUYỀN ĐỂ TĂNG HIỆU QUẢ PHÂN LỚP DỮ LIỆU Th.S Đào Thị Nha Trang GV khoa Cơ sở - Cơ bản I. ĐẶT VẤN ĐỀ lời giải tương đối tối ưu. Tính tối ưu Ý niệm về thuật giải di truyền được thể hiện ở chỗ thế hệ sau bao giờ (Genetic Algorithms: GA) đã được các cũng tốt hơn thế hệ trước (phát triển nhà sinh vật đưa ra vào khoảng năm hơn, hoàn thiện hơn). 1950. S. Fraser là người đầu tiên đưa ra II. NỘI DUNG sự tương đồng giữa quá trình tiến hóa Tiến hoá tự nhiên được quy định của sinh vật và chương trình máy tính giả duy trì nhờ hai quá trình cơ bản: sinh sản tưởng về thuật giải di truyền. J. H. và chọn lọc tự nhiên. Trong quá trình tiến Holland là người triển khai ý tưởng và hoá tự nhiên các cá thể mới luôn được phương thức giải quyết vấn đề dựa trên sinh ra để bổ sung, thay thế thế hệ cũ. Cá sự tiến hoá của con người. thể nào phát triển hơn, thích nghi hơn, Với tập sách xuất bản năm 1975 của thích ứng hơn với môi trường sẽ có nhiều mình - “ Adaptation in natural and artificical khả năng tồn tại hơn. Cả thể mới sinh ra systems ” - là tập sách đầu tiên đề cập đến trong quá trình tiến hoá có thể mang lĩnh vực này, J. H. Holland được xem là cha những tính trạng của cha mẹ (di truyền), đẻ của thuật giải di truyền. cũng có thể mang những tính trạng hoàn J. H. Holland và các đồng nghiệp toàn mới (đột biến) và chọn lọc tự nhiên. của ông ở trường đại học Michigan đã Cách tiếp cận giải quyết vấn đề - bài không ngừng phát triển và tạo nên cơ sở toán bằng thuật giải di truyền, theo đề lý thuyết vững chắc cho thuật giải di xuất ban đầu của J. H. Holland, bài toán truyền. Thuật giải di truyền được ứng sẽ được mã hoá thành các chuỗi bit với dụng trong nhiều lĩnh vực khác nhau, chiều dài cố định. Nên một lời giải tương trong đó thích hợp nhất là ứng dụng tìm ứng cũng biểu diễn bằng một chuỗi bit. kiếm giải pháp tối ưu. Trong thuật giải di truyền, ta gọi các lời Thuật giải di truyền hoạt động dựa giải là cá thể và chuỗi bit này được gọi là trên sự mô phỏng quá trình thích nghi và mã gen của cá thể . tiến hoá của tự nhiên trong điều kiện Trong thuật giải di truyền các quy định sẵn môi trường. Mục tiêu của thuật ngữ gen, cá thể, lời giải được sử thuật giải di truyền không nhằm đưa ra dụng lẫn lộn với ý nghĩa giống nhau. 2.1. Tìm hiểu thuật giải di truyền Cho bảng quyết định Dt = trong đó:
2. U = { x12, x , , xN } Tập thuộc tính quyết định : D = {d} chỉ có một thuộc tính. AD Thuộc tính d có r(d) giá trị. Khi đó, quan hệ bất khả phân IND(d) tách U thành r(d) lớp quyết định. . Với mọi aA, quan hệ tương tự Ra trên Va: xyUaxRay,:,aa Sxy ta với t(a) 0,1 , gọi là giá trị ngưỡng tương tự của thuộc tính a, và : d a x, a y Sa x,1 y dmax Trong đó : o d a x,: a y khoảng cách giữa hai giá trị thuộc tính a(x) và a(y). o dmax : khoảng cách lớn nhất có thể giữa hai giá trị thuộc tính a(x) . Quan hệ dung sai ( tương tự ) A trên U : x,:, y U xAA Y S x y t A Với t(A) 0,1 , gọi là giá trị ngưỡng tương tự của tập A. 1 Và : SAa x,, y S x y A aA Vấn đề đặt ra là tối ưu các giá trị ngưỡng tương tự t(A), t(a), aAtheo yêu cầu: “ Nếu các đối tượng có quan hệ dung sai với nhau thi chúng cùng nằm trong một lớp càng nhiều càng tốt Nếu các đối tượng cùng nằm trong một lớp thì chúng có quan hệ dung sai với nhau càng nhiều càng tốt ”. Bài toán đặc tả như sau : Input : DT U,,, A D V f D d; A D Output : t A t a: a A Ta giải bài toán bằng cách sử dụng - Đánh giá độ thích nghi của các cá thể. thuật giải di truyền. Để thực hiện điều này, -Thực hiện các phương thức tiến hoá đầu tiên ta tìm hiểu cơ chế thực hiện thuật để tạo ra các quần thể mới tốt hơn (có giải di truyền, sau đó vận dụng vào việc độ thích nghi cao hơn). xác định giá trị ngưỡng tương tự tối ưu. Ý Như vậy, thuật giải di truyền là tưởng của thật giải di truyền như sau: phương pháp tìm kiếm ngẫu nhiên được - Đầu tiên, phát sinh ngẫu nhiên nhiều định hướng bởi số thích nghi. Thuật giải di cá thể, gọi là quần thể ban đầu. truyền không chắc lúc nào cũng tìm được
3. giải pháp tối ưu, nhưng chắc là trong thời sản thế hệ kế tiếp sẽ lớn hơn. Điều đó gian cho phép, thuật giải di truyền cung không có nghĩa những cá thể có độ thích cấp các giải pháp tốt nhất cho vấn đề. nghi thấp không được chọn. Có nhiều 2.1.1. Hàm thích nghi ( Fitness): quy tắc chọn, ở đây ta tìm hiểu quy tắc Khả năng chọn lọc vào quá trình chọn theo ban Roulete. sinh sản quần thể kế tiếp phụ thuộc vào Đây là nguyên tắc chọn lọc dựa giá trị thích nghi của các cá thể trong quần theo hoạt động của bàn Roulete. Mỗi thể. Các cá thể có độ thích nghi cao thì cá thể sẽ chiếm một cung trên bàn xác xuất được chọn sẽ lớn và ngược lại. Roulete. Cá thể có độ thích nghi càng Để tính giá trị thích nghi ta dựa cao thì góc tương ứng với cung đó vào một hàm, gọi là hàm thích nghi. càng lớn. Việc chọn lọc theo bàn Hàm thích nghi được xây dựng Roulete được tiến hành như sau : từ hàm mục tiêu của bài toán. Hàm - Sắp xếp các cá thể theo độ mục tiêu (được xác định ban đầu) chỉ thích nghi giảm dần (có thể không cần độ tốt của các cá thể. sắp xếp). Độ tốt của một cá thể chỉ là cơ - Lần lượt đặt giá trị thích nghi của sở để xác định tính thích nghi của cá các cá thể kề nhau trên cung một đoạn thể đó. Chỉ đơn giản vì cá thể tốt nhất [0,1]. Như vậy mỗi cá thể sẽ chiếm một ở thế hệ trước vẫn có khả năng bị kẹt đoạn con trong đoạn [0,1]. Để chọn một trong các thế hệ sau và cá thẻ chưa tốt cá thể, ta phát sinh một số ngẫu nhiên p ở thế hệ trước vẫn có thê tiềm tàng trên đoạn [0,1]. Giá trị của p nằm trong khả năng dẫn đến lời giải tối ưu. khoảng con nào thì cá thể chiếm khoảng Thông thường độ thích nghi của cá con đó sẽ được chọn. thể cũng là xác xuất để cá thể đó được Còn có nhiều quy tắc chọn lọc khác chọn lọc hay lai ghép khi thực hiên tạo ra như: quy tắc chọn lọc xén ( xác định bao thế hệ kế tiếp. Có nhiều phương pháp nhiêu phần trăm cá thể tốt nhất trong xác định độ thích nghi của cá thể, chẳng quần thể sẽ được chọn), quy tắc chọn lọc hạn như các phương pháp sau : theo kiểu rải, quy tắc chọn lọc cục bộ, *) Phương thức Tạo Sinh quy tắc chọn lọc nhiều lần, (Preprodution) và Chọn ( Select) *) Lai ghép (CrossOver): Phép tạo sinh là quá trình các cá Phép lai ghép là quá trình hình thể được sao chép dựa trên độ thích thành các cá thể mới trên cơ sở những nghi của nó. cá thể cha mẹ. Có nhiều quy tắc lai Cá thể nào có độ thích nghi cao thì ghép, đơn giản nhất là quy tắc lai xác suất được chọn vào quá trình sinh ghép đơn điểm.
4. Lấy hai cá thể cha mẹ A và B từ tập k này chia gen của hai cá thể cha mẹ A các cá thể đã được chọn lọc theo phương thành A1A2 và B1B2. Lai ghép đơn điểm pháp chọn đã nêu ở trên. Phát sinh ngẫu tạo ra hai cá thể mới có gen là A1B2 và nhiên một số tự nhiên k nằm trong đoạn B1A2. Phép lai xảy ra với xác suất lai plai [1,N-1] với N là chiều dài của gen. Điểm cho trước. Ví dụ : ( biểu diễn gen bằng chuỗi nhị phân) A 001101 A 000101 k 2 ( lai ghép tại vị trí k = 2) B 110101 B 111101 Quy tắc lai ghép đa điểm là một ghép này sẽ chia gen của hai cá thể cha dạng tổng quát của lai ghép đơn điểm. mẹ A, B thành n +1 đoạn. Hai gen mới Trong lai ghép đa điểm, thay vì chỉ sẽ được tạo ra theo cách : các đoạn ở vị chọn một điểm lai ghép, ta chọn nhiều trí lẻ được giữ nguyên, các đoạn ở vị trí điểm lai ghép k1, k2 , , kn . n điểm lai chẵn được hoán chuyển với nhau. Ví dụ: AA001101 ' 010101 k1 1, k 2 3, k 3 5 BB110101 ' 101101 ( lai ghép tại vị trí k1= 1, k2= 3, k3= 5) Còn một quy tắc lai ghép khác như mặt nạ, quy tắc tạo sinh đường *) Đột biến ( mutation) Trong quá trình thực hiện thuật giải Đột biến là hiện tượng cá thể con di truyền phải luôn duy trì một quần thể mang một số tính trạng không có trong có tính đa dạng. Tính đa dạng thể hiện gen di truyền của cha mẹ. Phép đột biến trong quần thể không chỉ gồm những cá chỉ được phép xảy ra với xác suất thấp p thể có độ thích nghi cao sẽ chiếm tỉ lệ độtbiến cho trước ( hoặc có thể lấy p độtbiến = nhiều hơn do quy tắc chọn lọc quy định. 1/N với N là chiều dài gen cá thể). Đột Quá trình sinh sản (lai ghép, đột biến) biến có thể xảy ra tại một hay nhiều nhằm tạo ra những cá thể có gen mới. Cá thành phần gen nhưng do xác suất đột thể mới có thể có độ thích nghi cao hơn biến thấp nên người ta chỉ cho đột biến hoặc thấp hơn cá thể cha mẹ. Chính điều trên một thành phần gen là tối đa. đó tạo nên tính đa dạng của quần thể. Khi đó phép đột biến thực hiện 2.2. Mô tả thuật giải di truyền : như sau : phát sinh ngẫu nhiên một số Thuật giải di truyền bao gồm các thực k nằm trong khoảng [1,N] với N thành phần chính: là chiều dài của gen theo một công - Cách khởi tạo quần thể ban đầu. thức đột biến cho trước. - Hàm đánh giá độ thích nghi của các cá thể. Nhận xét: - Các phương thức tiến hoá
5. Thuật giải di truyền mô tả như sau: thì xác suất chọn sẽ lớn và ngược lại. Bắt đầu Nhưng điều này không có nghĩa là t = 0; những cá thể có độ thích nghi thấp Khởi tạo P( t); không được chọn. Tính độ thích nghi cho các cá thể + Thao tác thứ hai là tạo ra các thuộc P( t ); cá thể mới từ các cá thể được chọn có Khi ( điều kiện dừng chưa thoả) lặp độ thích nghi cao từ thế hệ hiện tại Bắt đầu bằng cách thực hiện kết hợp các t = t + 1; phương thức lai ghép và đột biến. Chọn lọc P(t) từ P( t - 1); * Phép lai ghép thực hiện bằng Tính độ thích nghi cho các cá thể cách kết hợp hai cá thể cha mẹ theo thuộc P(t); một quy tắc để tạo ra hai cá thể con Kết thúc mới. Phép lai ghép diễn ra theo một 2.3. Cơ chế thực hiện thuật giải di xác suất lai cho trước. truyền Phương thức chọn và lai ghép -Tại thời điểm ban đầu ( t = 0) ta cho phép tạo ra các thế hệ sau : khởi tạo quần thể P(t) (gọi là quần thể * Trong trường hợp quần thể phát ban đầu): phát sinh một số lượng lớn, sinh ngẫu nhiên ban đầu có đặc tính chưa hữu hạn các cá thể có gen ngẫu nhiên. phong phú hay chưa phù hợp. Ta tạo ra Sau đó dựa vào một hàm số mà quần thể mới chỉ bằng thao tác chọn lọc ta gọi là hàm thích nghi để xác định và lai ghép thì các cá thể lời giải trong độ thích nghi các cá thể. Do phát sinh quần thể sẽ chỉ tập trung trong một ngẫu nhiên nên tính thích nghi của cá khoảng giới hạn mà không tiến tới được thể trong quần thể không xác định. lời giải tối ưu. Để giải quyết vấn đề trên - Để cải thiện tính thích nghi của quẩn ta phải thực hiện phương thức đột biến. thể, ta tạo ra các quần thể mới. Từ thế hệ Tuy nhiên phép đột biến chỉ được phép hiện tại, ta dùng các thao tác sau để tạo ra diễn ra với xác suất thấp vì phép đột biến các thế hệ sau có tính thích nghi tốt hơn: có thể làm mất đi những cá thể được + Đầu tiên là sao chép nguyên các cá chọn lọc và lai ghép có độ thích nghi cao. thể có độ thích nghi cao từ thế hệ hiện tại - Thế hệ mới sẽ được xử lí như đưa sang thế hệ kế tiếp bằng phương thế hệ trước đó. Việc xử lý sẽ dừng thức chọn, để đảm bảo tính thích nghi khi đạt được lời giải tối ưu hoặc thời của thế hệ sau luôn ở mức hợp lý. gian cho phép kết thúc Phương thức này thực hiện theo 2.4. Các bước thực hiện quan trọng nguyên tắc cá thể có độ thích nghi cao trong thuật giải di truyền
6. Giải quyết bài toán bằng thuật các cá thể để thực hiện việc tạo sinh giải di truyền, cần phải thực hiện các và chọn lọc, thực hiện các phương bước quan trọng sau đây : thức tiến hoá như lai ghép, đột biến . Bước 1: Chọn mô hình cho giải pháp của Bước 5: Tính độ thích nghi của các cá bài toán: Chọn một số tượng trưng cho toàn thể mới. Loại bỏ các cá thể kém nhất bộ các giải pháp có thể có của bài toán. và chỉ giữ lại các cá thể tương đối tốt. Bước 2: Chỉ định cho mỗi giải pháp một Bước 6: Nếu chưa tìm được lời giải (cá ký hiệu. Ký hiệu có thể là một dãy các số thể) tối ưu hay tương đối tối ưu hay chưa nhị phân, hoặc dãy số thập phân, dãy các hết thời gian cho phép thì quay lại bước 4. chữ, hoặc dãy hỗn hợp các số và chữ. Bước 7: Tìm được lời giải tối ưu hay Thường dùng nhất là dãy các số nhị phân. hết thời gian cho phép thì báo cáo kết Bước 3: Tìm hàm số thích nghi và quả, kết thúc thuật giải . tính độ thích nghi của các cá thể. Sơ đồ minh họa quá trình tối ưu Bước 4: Dựa vào độ thích nghi của của thuật giải di truyền: Xác định độ thích Có cá thể nào đạt Trình bày lời lời giải tối ưu nghi các cá thể giải chưa? Tạo quần thể ban đầu Chọn lọc Lai ghép Bắt đầu Xây dựng quần thể mới Đột biến Xây dựng thế hệ kế tiếp
7. 2.5. Áp dụng thuật giải di truyền xác . định ngưỡng tương tự tối ưu 3. Hoàng Kiếm - Lê Hoàng Thái (2000), "Thuật Giải Cũng như các bài toán tối ưu mà Di Truyền- Cách Giải Tự Nhiên Các Bài Toán Trên thuật giải di truyền giải quyết, ta cần giải Máy Tính", NXB Giáo Dục Hà Nội. quyết các vấn đề sau: Tài liệu tiếng Anh: - Biểu diễn các biến của vấn đề. 4. Han Yin Shi, A clasification study of Ruogh - Tạo quần thể ban đầu. Sets generalization, A thesis Master of science in - Xác định hàm thích nghi của vấn đề, xác Lakehead University 2004 định giá trị thích nghi của các cá thể. 5. Z. Pawlak, Rough Sets - Theorycal Aspect of - Thực hiện các phương thức tiến hoá. Reasoning about Data, Kluwer Akademic Mô tả thuật giải; publishers 1991 1. Khởi tạo : 6. J. H. Holland, "Adaptation in natural and - Đọc bảng quyết định; artifical systems" 1975 - Định nghĩa độ đo tương tự; - Tạo quần thể ban đầu: Lấy các ngưỡng ban đầu trong khoảng [0,1]; - Tính độ thích nghi của quần thể ban đầu; 2. Tiến hành thuật giải di truyền while ( not( điều kiện kết thúc )) {Tạo sinh; Lai ghép; Đột biến; Tính hàm thích nghi của quần thể mới:} 3. Xác định giá trị ngưỡng tương tự tối ưu. III. KẾT LUẬN Khi sử dụng giá trị ngưỡng tối ưu tìm được bằng thuật giải di truyền để làm đầu vào cho thuật giải phân lớp, chưa chắc ta đã có kết quả phân lớp tốt theo nghĩa có ít phân tử không phân lớp được. Tuy nhiên bằng cách xử lý tiếp theo là chọn giá trị lớn nhất cho mỗi thành phần trong bộ ngưỡng tối ưu trong nhiều lần thực hiện, kết quả thu được thường tốt hơn. TÀI LIỆU THAM KHẢO Tài liệu tiếng việt: 1. (2011), Cơ sở dữ liệu Quan hệ & Ứng dụng . 2. Hoàng Kiếm (2001), ", Tập 2, NXB 7