ĐẠ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Í MINH
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Mai Ngọc Tùng – CH1101055 - 1 -
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.
ĐẠ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
Mai Ngọc Tùng – CH1101055 - 2 -
MỤC LỤC
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG............................................. 1
Mở đầu ................................................................................................................................ 1
PHẦN I :
ỨNG DỤNG THUẬT GIẢI DI TRUYỀN ĐỂ TÌM KIẾM THÔNG TIN TRONG
VĂ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 ...................................................................................................................... 6
PHẦN II :
Các nguyên tắc sáng tạo sử dụng trong Thuật toán di truyền ............................ 7
PHẦN IV :
Demo ................................................................................................................. 8
PHẦN V :
Nguồn tham khảo ............................................................................................... 8
I. http://tailieu.vn/tim-kiem/tai-lieu/mang%20noron.html................................................. 8
II. vi.wikipedia.org/wiki/Giải_thuật_di_truyền ................................................................ 8
III. portal.uct.edu.vn ................................................................................................... 8
IV. http://www.igi.tugraz.a .......................................................................................... 8
ĐẠ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
Mai Ngọc Tùng – CH1101055 - 3 -
PHẦN I :
ỨNG DỤNG THUẬT GIẢI DI TRUYỀN ĐỂ TÌM KIẾM
THÔNG TIN TRONG VĂN BẢN
I.
Thuật giải di truyền:
1) Khái niệm
Thuật giải di truyền cung cấp một cách tiếp cận cho việc học dựa vào mô
phỏng sự tiến hóa. Các giả thuyết thường được mô tả bằng các chuỗi bit, việc hiểu các
chuỗi bit này tùy thuộc vào ứng dụng, ý tưởng các giả thuyết cũng có thể được mô tả
bằng các biểu thức kí hiệu hoặc ngay cả các chương trình máy tính. Tìm kiếm giả
thuyết thích hợp bắt đầu với một quần thể, hay một tập hợp có chọn lọc ban đầu của
các giả thuyết. Các cá thể của quần thể hiện tại khởi nguồn cho quần thể thế hệ kế tiếp
bằng các hoạt động lai ghép và đột biến ngẫu nhiên – được lấy mẫu sau các quá trình
tiến hóa sinh học. Ở mỗi bước, các giả thuyết trong quần thể hiện tại được ước lượng
liên hệ với đại lượng thích nghi được cho, với các giả thuyết phù hợp nhất được chọn
theo xác suất là các hạt giống cho việc sản sinh thế hệ kế tiếp. Thuật giải di truyền đã
được ứng dụng một cách thành công cho những tác vụ học khác nhau và cho các vấn
đề tối ưu hóa khác. Ví dụ, chúng đã được dùng để học tập luật điều khiển robot và để
tối ưu hóa các thông số học và tôpô cho mạng nơron nhân tạo
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, thành công cho sự thích nghi bên trong
các hệ thống sinh học.
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.
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 mạnh.
ĐẠ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
Mai Ngọc Tùng – CH1101055 - 4 -
3) Tính chất quan trọng của Giải thuật di truyền (GA):
GA lập luận có tính chất ngẫu nhiên để tìm giải pháp tối ưu cho những vấn đề phức
tạp. Tuy nhiên, đây là hình thức ngẫu nhiên có hướng dẫn bởi giá trị hàm thích nghi.
- Vấn đề thích hợp nhất cho GA là tìm điều kiện tối ưu. Tối ưu không nhất
thiết là tuyệt đối, mà có thể chỉ là tương đối trong hoàn cảnh và thời gian cho phép
- Một trong những bước quan trọng và khó khăn nhất là tìm hàm thích nghi.
Hàm thích nghi cần phải có liên hệ trực tiếp đến vấn đề cần giái quyết.
- GA và Mạng Nơron nhân tạo đề thuộc vào nhóm khoa học trí tuệ nhân tạo,
tuy nhiên GA lập luận dựa vào sự tiến hóa và xét vấn đề ở mức độ của gen và nhiễm
sắc thể, khác với mạng Nơron nhân tạo dựa vào kinh nghiệm và cách giải quyết vấn
đề mà bộ óc con người thường dùng.
Sự khác biệt giữa giải thuật di truyền so với các giải thuật khác bởi 4 đặc điểm sau:
- GA làm việc với sự mã hóa một bộ các thông số chứ không phải bản thân
các thông số.
- GA tìm kiếm từ một số điểm quần thể chứ không phải bắt đầu từ 1 điểm.
- GA sử dụng các thông tin về hàm mục tiêu chứ không phải đạo hàm hay
những tri thức phụ khác.
- GA sử dụng các luật chuyển đổi theo xác suất chứ không phải các luật
chuyển đổi tiền định.
II.
Sử dụng thuật giải di truyền để tìm kiếm mẫu trong Văn bản
Hiện nay, trong bài toán tìm kiếm con người quan tâm đến những nội dung có liên
quan đến mẫu tìm kiếm hoặc có chứa một phần trong mẫu tìm kiếm. Theo dó, vấn đề đặt ra
là tìm trong toàn bộ văn bản V (độ dài N) vị trí xuất hiện của (các) đoạn văn bản gần
giống với văn bản mẫu Vm (độ dài M) nhất.
1) Xây dựng hàm tìm kiếm
Hàm tìm kiếm được xây dựng bởi sự liên kết giữa hai đại lượng:
+ Độ dài xâu con chung dài nhất giữa văn bản (độ dài N) và mẫu tìm kiếm (độ dài M) (G(x))
+ Độ dài trùng khớp về giá trị và vị trí của đoạn văn bản và mẫu (H(x))
Xâu con chung dài nhất ở đây là dãy ký tự dài nhất theo thứ tự giống nhau giữa hai xâu
(không yêu cầu tính liền mạch). Để tìm xâu con chung dài nhất, thuật toán hiệu quả nhất là
dung quy hoạch động có độ phức tạp O(M2). Thực tế, độ dài M cùa mẫu tìm kiếm thường
không lớn nền hoàn toàn có thể chấp nhận độ phức tạp này.
Hàm tìm kiếm có dạng sau: F(x) = a*G(x) + b*H(x) , 1 <= x <= N
* G(x) là tần suất xuất hiện Vm trong đoạn V[x..x+M] của V (tính từ vị trí x đến vị trí x+M
trong văn bản V).
* H(x) là độ đo thứ tự, thể hiện thứ tự xuất hiện các ký tự trong V[x..x+M] trùng với Vm.
H(x) được tính bằng cách so khớp lần lượt các ký tự, giá trị trả về chính là số lượng ký tự
trùng khớp (chữ cái và vị trí chữ cái đó) của Vm và V[x..x+M].
* a và b là tham số đóng vai trò điều tiết mức độ đóng góp của hàm G(x) và H(x) vào kết quả
cuối cùng của hàm F(x).
Xâu con chung dài nhất bằng quy hoạch động
a) Công thức quy hoạch động: