Tiểu luận: 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

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.
Nội dung trích xuất từ tài liệu:
Tiểu luận: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 CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG ________________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: Mai Ngọc Tùng MSSV: CH1101055 TP. HCM, năm 2012ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINHCHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG 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ênquan 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áclĩ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ệuquả 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ácphươ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ủakết quả thu được. Chính vì vậy, thuật giải di truyền (Genetic Algorithm) đã trở thành đề tàinghiê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 ditruyề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ửilờ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 đạtnhữ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 khoahọ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.Mai Ngọc Tùng – CH1101055 -1-ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINHCHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG MỤC LỤCCHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG............................................. 1Mở đầu ................................................................................................................................ 1PHẦN I : ỨNG DỤNG THUẬT GIẢI DI TRUYỀN ĐỂ TÌM KIẾM THÔNG TIN TRONGVĂN BẢN ............................................................................................................................ 3 I. Thuật giải di truyền:................................................................................................. 3 I.1. Khái niệm........................................................................................................................................ 3 I.2. Động lực ......................................................................................................................................... 3 I.3. Tính chất quan trọng của Giải thuật di truyền (GA): ......................................................................... 4 II. Sử dụng thuật giải di truyền để tìm kiếm mẫu trong Văn bản .......................................... 4 II.1. Xây dựng hàm tìm kiếm ................................................................................................................. 4 II.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 .................... 5 II.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................................................... 5 II.4. Cách biểu diễn di truyền cho lời giải của bài toán ............................................................................ 6 II.5. Cách khởi tạo quần thể lời giải ban đầu ........................................................................................... 6 II.6. Xây dựng hàm thích nghi đóng vai trò môi trường và đánh giá lời giải ............................................ 6 II.7. Sử dụng các toán tử lai ghép ........................................................................................................... 6 II.7.1. Toán tử chọn lọc ..................................................................................................................... 6 II.7.2. Toán tử lại ghép ...................................................................................................................... 6 II.7.3. Toán tử đột biến .................................................................................................. ...