Bài thu hoạch Nghiên cứu ứng dụng thuật giải di truyền để tìm kiếm thông tin trên văn bản

ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN ________________ BÀI THU HOẠCH MÔN HỌC PHƯƠNG PHÁP NGHIÊN CỨU KHOA HỌC TRONG TIN HỌC Đề tài: Nghiên cứu ứng dụng thuật giải di truyền để tìm kiếm thông tin trên văn bản. Giảng viên hướng dẫn: GS. TSKH HOÀNG KIẾM Học viên thực hiện: Vũ Duy Anh MSSV: 1212002 TP. HCM, năm 2012 ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN Vũ Duy Anh – 1212002 - 1 - ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN MỤC LỤC Mở đầu ...................................................................................................................................... 4 PHẦN I : CÁC NGUYÊN LÝ SÁNG TẠO .............................................................................. 5 I. Tổng quan về các nguyên lý sáng tạo: ........................................................................ 5 II. Phân tích: ................................................................................................................. 6 1) Nguyên tắc phân nhỏ: ......................................................................................................................... 6 2) Nguyên tắc tách khỏi: ......................................................................................................................... 6 3) Nguyên tắc phẩm chất cục bộ: ............................................................................................................ 6 4) Nguyên tắc phản đối xứng: ................................................................................................................. 7 5) Nguyên tắc kết hợp: ............................................................................................................................ 7 6) Nguyên tắc vạn năng: ......................................................................................................................... 7 7) Nguyên tắc chứa trong: ....................................................................................................................... 7 8) Nguyên tắc phản trọng lượng: ............................................................................................................ 8 9) Nguyên tắc gây ứng suất sơ bộ: .......................................................................................................... 8 10) Nguyên tắc thực hiện sơ bộ:........................................................................................................... 8 11) Nguyên tắc dự phòng: .................................................................................................................... 8 12) Nguyên tắc đẳng thế: ..................................................................................................................... 9 13) Nguyên tắc đảo ngược: .................................................................................................................. 9 14) Nguyên tắc cầu hóa: ....................................................................................................................... 9 15) Nguyên tắc linh động: .................................................................................................................... 9 16) Nguyên tắc giải “thiếu” hoặc “thừa”: ........................................................................................... 10 17) Nguyên tắc chuyển sang chiều khác: ........................................................................................... 10 18) Nguyên tắc sử dụng các dao động cơ học: ................................................................................... 10 19) Nguyên tắc tác động theo chu kỳ: ................................................................................................ 10 20) Nguyên tắc liên tục tác động có ích: ............................................................................................ 11 21) Nguyên tắc vượt nhanh: ............................................................................................................... 11 22) Nguyên tắc biến hại thành lợi: ..................................................................................................... 11 23) Nguyên tắc quan hệ phản hồi: ...................................................................................................... 11 24) Nguyên tắc sử dụng trung gian: ................................................................................................... 12 25) Nguyên tắc tự phục vụ: ................................................................................................................ 12 26) Nguyên tắc sao chép: ................................................................................................................... 12 27) Nguyên tắc “rẻ” thay cho “đắt”: .................................................................................................. 12 28) Nguyên tắc thay thế sơ đồ cơ học: ............................................................................................... 13 29) Nguyên tắc sử dụng các kết cấu khí và lỏng: ............................................................................... 13 30) Nguyên tắc sử dụng vỏ dẻo và màng mỏng: ................................................................................ 13 31) Nguyên tắc sử dụng vật liệu nhiều lỗ: .......................................................................................... 13 32) Nguyên tắc thay đổi màu sắc: ...................................................................................................... 14 33) Nguyên tắc đồng nhất: ................................................................................................................. 14 34) Nguyên tắc phân hủy hoặc tái sinh các phần: .............................................................................. 14 35) Nguyên tắc thay đổi các thông số hóa lý của đối tượng: .............................................................. 14 36) Nguyên tắc sử dụng sự chuyển pha:............................................................................................. 15 37) Nguyên tắc sử dụng sự nở nhiệt: .................................................................................................. 15 38) Nguyên tắc sử dụng chất oxy hóa mạnh: ..................................................................................... 15 39) Nguyên tắc thay đổi độ trơ: .......................................................................................................... 15 40) Nguyên tắc sử dụng vật liệu hợp thành composit: ....................................................................... 15 Vũ Duy Anh – 1212002 - 2 - ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN PHẦN II : ỨNG DỤNG THUẬT GIẢI DI TRUYỀN ĐỂ TÌM KIẾM THÔNG TIN TRONG VĂN BẢN................................................................................................................. 16 I. Thuật giải di truyền: .................................................................................................. 16 1) Khái niệm ......................................................................................................................................... 16 2) Động lực ........................................................................................................................................... 16 3) Tính chất quan trọng của Giải thuật di truyền (GA): ........................................................................ 17 II. Sử dụng thuật giải di truyền để tìm kiếm mẫu trong Văn bản..................................... 17 1) Xây dựng hàm tìm kiếm ................................................................................................................... 17 2) Xác định mức độ trùng khớp theo thứ tự của các ký tự trong mẫu tìm kiếm và văn bản ................. 18 3) Đặt vấn đề áp dụng giải thuật di truyền cho bài toán tìm kiếm trên ................................................. 18 4) Cách biểu diễn di truyền cho lời giải của bài toán ............................................................................ 19 5) Cách khởi tạo quần thể lời giải ban đầu ............................................................................................ 19 6) Xây dựng hàm thích nghi đóng vai trò môi trường và đánh giá lời giải ........................................... 19 7) Sử dụng các toán tử lai ghép ............................................................................................................. 19  Toán tử chọn lọc .......................................................................................................................... 19  Toán tử lại ghép ........................................................................................................................... 19  Toán tử đột biến ........................................................................................................................... 19 PHẦN III : Các nguyên tắc sáng tạo sử dụng trong Thuật toán di truyền .......................... 20 PHẦN IV : Nguồn tham khảo ............................................................................................... 21 1) ................................................................... 21 2) vi.wikipedia.org/wiki/Giải_thuật_di_truyền ..................................................................................... 21 3) portal.uct.edu.vn ............................................................................................................................... 21 4) ..................................................................................................................... 21 Vũ Duy Anh – 1212002 - 3 - ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN Mở đầu Thuật giải di truyền, cũng như các thuật toán tiến hoa 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à 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ể được xem là một tiên đề đú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 và hoàn thiện hơn thế hệ trước. Hiện nay, thuật toán di truyền cùng với logic mờ được ứng dụng rất rộng rãi trong các lĩnh vực tương đối phức tạp. Thuật toán di truyền kết hợp logic mờ đã chứng tỏ được hiệu quả của nó trong các vấn đề khó giải quyết bằng các phương pháp thông thường hay các phương pháp cố điển, nhất là trong các bài toán cần có sự lượng giá, đánh giá sự tối ưu của kết quả thu được. Chính vì vậy, thuật giải di truyền (Genetic Algorithm) đã trở thành đề tài nghiên cứu thú vị và mang đến nhiều ứng dụng thực tiễn ngày nay. Trong phạm vi của bài thu hoạch nhỏ này, em sẽ trình bày một số vấn đề thuật toán di truyền và ứng dụng của nó trong việc tìm kiếm trên văn bản. Qua đây, em cũng xin được gửi lời cảm ơn đến Giáo sư - Tiến sỹ Khoa Học Hoàng Văn Kiếm, người đã tận tâm truyền đạt những kiến thức nền tảng cơ bản cho chúng em về môn học “Phương pháp nhiên cứu khoa học trong tin học” và em xin gửi lời cảm ơn đến toàn thể các bạn bè học viên trong lớp. Vũ Duy Anh – 1212002 - 4 - ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN PHẦN I : CÁC NGUYÊN LÝ SÁNG TẠO I. Tổng quan về các nguyên lý sáng tạo: Theo Atshuler , quy luật phát triển của khoa học kỹ thuật hiện nay, cũng như các ngành khác, đều tuân theo các nguyên lý sáng tạo cơ bản. Đó là 40 nguyên lý sáng tạo mà ông đã đúc kết trong “Lý thuyết giải các bài toán sáng chế”(TRIZ), đã được GS.TS Phan Dũng biên soạn thành tiếng Việt. 40 nguyên lý sáng tạo này bao gồm: - Nguyên tắc phân nhỏ. - Nguyên tắc tách khỏi - Nguyên tắc phẩm chất cục bộ - Nguyên tắc phản đối xứng - Nguyên tắc kết hợp - Nguyên tắc vạn năng - Nguyên tắc chứa trong - Nguyên tắc phản trọng lượng - Nguyên tắc gây ứng suất sơ bộ - Nguyên tắc thực hiện sơ bộ - Nguyên tắc dự phòng - Nguyên tắc đẳng thế - Nguyên tắc đảo ngược - Nguyên tắc cầu hóa - Nguyên tắc linh động - Nguyên tắc giải “thiếu” hoặc “thừa” - Nguyên tắc chuyển sang chiều khác - Nguyên tắc sử dụng các dao động cơ học - Nguyên tắc tác động theo chu kỳ - Nguyên tắc liên tục tác động có ích - Nguyên tắc “vượt nhanh” - Nguyên tắc biến hại thành lợi - Nguyên tắc quan hệ phản hồi - Nguyên tắc sử dụng trung gian - Nguyên tắc tự phục vụ - Nguyên tắc sao chép - Nguyên tắc “rẻ” thay cho “đắt” - Nguyên tắc thay thế sơ đồ cơ học - Nguyên tắc sử dụng các kết cấu khí và lỏng - Nguyên tắc sử dụng vỏ dẻo và màng mỏng - Nguyên tắc sử dụng vật liệu nhiều lỗ - Nguyên tắc thay đổi màu sắc - Nguyên tắc đồng nhất - Nguyên tắc phân hủy hoặc tái sinh các phần - Nguyên tắc thay đổi các thông số hóa lý của đối tượng - Nguyên tắc sử dụng sự chuyển pha - Nguyên tắc sử dụng sự nở nhiệt Vũ Duy Anh – 1212002 - 5 - ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN - Nguyên tắc sử dụng chất oxy hóa mạnh - Nguyên tắc thay đổi độ trơ - Nguyên tắc sử dụng vật liệu hợp thành composit Dưới đây chúng ta sẽ tiến hành phân tích các nguyên lý sáng tạo này và việc vận dụng chúng vào mô hình “Điện toán đám mây” như thế nào. II. Phân tích: 1) Nguyên tắc phân nhỏ: Nội dung: - Chia đối tượng thành các phần độc lập: - Làm đối tượng trở nên tháo lắp được - Tăng mức độ phân nhỏ của đối tượng. Nguyên tắc này thường dùng trong những trường hợp khó làm trọn gói, nguyên khối. Phân nhỏ đối tượng ra cho vừa sức, dễ thực hiện, cho phù hợp với những phương tiện hiện có… Sự thay đổi về lượng dẫn đến sự thay đổi về chất, cho nên, sự phân nhỏ đối tượng có thể làm cho đối tượng thêm những tính chất mới. Ví dụ: Phân nhỏ 1 chức năng lớn thành các module nhỏ hơn để dễ xử lý, dễ kiểm soát lỗi. 2) Nguyên tắc tách khỏi: Nội dung: - Tách phần gây “phiền phức” ra khỏi đối tượng. - Tách phần duy nhất “cần thiết” ra khỏi đối tượng. Một đối tượng có thể có nhiều tính chất “gây nhiễu”, ảnh hưởng xấu đến đối tượng, do đó cần phải tách phần “gây nhiễu” này ra để chỉ giữ lại những tính chất tốt. Đối tượng cũng có thể chỉ có duy nhất 1 phần là tốt, cần thiết, còn các phần khác không quan trọng, nên cần tách thành phần cần thiết này ra khỏi đối tượng để sử dụng tính chất cần thiết này. Ví dụ: Sử dụng phương pháp lọc nhiễu để tách nhiễu âm ra khỏi âm thanh được thu, để được chất lượng âm thanh tốt hơn. 3) Nguyên tắc phẩm chất cục bộ: Nội dung: - Chuyển đối tượng ( hay môi trường bên ngoài, tác động bên ngoài) có cấu trúc đồng nhất thành không đồng nhất. - Các phần khác nhau của đối tượng phải có các chức năng khác nhau. - Mỗi phần của đối tượng phải ở trong những điều kiện thích hợp nhất của công việc. Nguyên tắc này phản ánh khuynh hướng phát triển từ đơn giản sang phức tạp, từ đơn điệu sang đa dạng. Các đối tượng đầu tiên thường có tính đồng nhất cao về vật liệu, cấu hình, chức năng, thời gian, không gian… với các phần trong đối tượng. Dưới sự tác động của thời gian và ngoại cảnh, một số tính chất của đối tượng thay đổi cho phù hợp với hoàn cảnh nhằm phục vụ tốt nhất chức năng chính hoặc mở rộng chức năng chính đó. Vũ Duy Anh – 1212002 - 6 - ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN Ví dụ: Bàn phím máy tính, thay vì sắp xếp theo thứ tự chữ cái ABC( phẩm chất toàn cục), người ta sắp xếp theo vị trí những chữ cái thường hay được đánh nhất để tiện cho việc gõ phím ( phẩm chất cục bộ). 4) Nguyên tắc phản đối xứng: Nội dung: - Giảm bậc đối xứng của đối tượng: chuyển đối tượng có hình dạng đối xứng thành dạng không đối xứng. Nguyên tắc này có tác dụng quan trọng trong việc khắc phục tính ỳ tâm lý, cho rằng các đối tượng phải có hình dạng đối xứng. Giảm bậc đối xứng của đối tượng có thể làm xuất hiện những tính chất mới có lợi hơn, như tận dụng được không gian, làm đối tượng ổn định hơn, bền vững hơn. Ví dụ: Khai báo kiểu số tự nhiên(kiểu bất đối xứng) thay vì kiểu integer(kiểu đối xứng) để giảm thiểu việc tốn tài nguyên bộ nhớ. 5) Nguyên tắc kết hợp: Nội dung: - Kết hợp các đối tượng đồng nhất hoặc các đối tượng dùng cho các hoạt động kế cận. - Kết hợp về mặt thời gian các hoạt động đồng nhất hoặc kế cận. Các đối tượng có những tính chất bổ sung cho nhau có thể kết hợp lại để tạo thành 1 đối tượng mới có những tính năng ưu việt của các đối tượng con đã kết hợp. Ví dụ: 1 máy tính có thể cài nhiều hệ điều hành (máy thực, máy ảo) để có thể thao tác nhiều việc trên các hệ điều hành khác nhau. 6) Nguyên tắc vạn năng: Nội dung: - Đối tượng thực hiện một số chức năng khác nhau, không cần sự tham gia của đối tượng khác. Đây là trường hợp riêng của nguyên tắc kết hợp: kết hợp nhiều chức năng trên cùng 1 đối tượng. Ví dụ: Bàn phím, ngoài chức năng gõ phím, còn có các phím chức năng dùng để thay thế chuột khi cần thiết, có các phím media để chỉnh âm lượng… 7) Nguyên tắc chứa trong: Nội dung: - Một đối tượng được đặt bên trong đối tượng khác và bản thân nó lại có thể chứa những đối tượng khác. - Một đối tượng chuyển động xuyên suốt bên trong đối tượng khác. Ví dụ: Phương thức kế thừa trong lập trình hướng đối tượng áp dụng nguyên tắc chứa trong với việc đối tượng được kế thừa nằm bên trong đối tượng kế thừa, những phương thức, dữ Vũ Duy Anh – 1212002 - 7 - ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN liệu của đối tượng được kế thừa được đối tượng kế thừa sử dụng lại(đối với phạm vi public và protected). 8) Nguyên tắc phản trọng lượng: Nội dung: - Bù trừ trọng lượng của đối tượng bằng cách gắn nó với các đối tượng khác, có lực nâng. - Bù trừ trọng lượng của đối tượng bằng tương tác với môi trường như sử dụng các lực thủy động, khí động… Nguyên tắc này có thể hiểu theo nghĩa thoáng như sau: đối tượng cho trước có nhược điểm, cần kết hợp với đối tượng khác, có ưu điểm, mà ưu điểm đó có thể bù trừ cho nhược điểm. Thủ thuật này đòi hỏi sự mềm dẻo trong cách tiếp cận giải quyết vấn đề, nếu khắc phục trực tiếp nhược điểm là khó thì nên nghĩ cách bù trừ nó bằng sự kết hợp với ưu điểm nào đó. 9) Nguyên tắc gây ứng suất sơ bộ: Nội dung: - Gây ứng suất trước với đối tượng để chống lại ứng suất không cho phép hoặc không mong muốn khi đối tượng làm việc ( hoặc gây ứng suất trước để khi làm việc sẽ dùng ứng suất ngược lại). Ví dụ: Lập trình viên nếu muốn làm việc với công nghệ mới thì phải tìm hiểu kỹ công nghệ. 10) Nguyên tắc thực hiện sơ bộ: Nội dung: - Thực hiện trước sự thay đổi cần có, hoàn toàn hoặc từng phần đối với đối tượng. - Cần sắp xếp đối tượng trước, sao cho chúng có thể hoạt động từ vị trí thuận lợi nhất, không mất thời gian dịch chuyển. Nguyên tắc này gần giống với nguyên tắc gây ứng suất sơ bộ, nghĩa là cần có sự chuẩn bị trước một cách toàn diện, chu đáo. Ví dụ: Đối với project chạy lâu dài với những thay đổi khác nhau cho từng version, khi xây dựng database cần thiết kế sao cho có thể đáp ứng được các yêu cầu mới này mà ko ảnh hưởng đến version trước đó. 11) Nguyên tắc dự phòng: Nội dung: - Bù đắp độ tin cậy không lớn của đối tượng bằng cách chuẩn bị các phương tiện báo động, ứng cứu an toàn. Ví dụ: Khi lập trình, cần suy tính đến các trường hợp lỗi có thể xảy ra để thông báo các mã lỗi cho người dùng. Vũ Duy Anh – 1212002 - 8 - ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH ĐẠI HỌC KHOA HỌC TỰ NHIÊN 12) Nguyên tắc đẳng thế: Nội dung: - Thay đổi điều kiện làm việc để không phải nâng lên hay hạ xuống các đối tượng. Theo lý thuyết vật lý, quỹ tích của những điểm có cùng một thế năng, gọi là mặt đẳng thế. Người ta chứng minh được rằng