Đề 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

ĐẠ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 Vũ Duy Anh – 1212002 - 2 - 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 ĐẠ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 - 3 - 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 ĐẠ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 - 4 - 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 ĐẠI HỌC KHOA HỌC TỰ NHIÊN Vũ Duy Anh – 1212002 - 5 - 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 ĐẠ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 - 6 - - 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 đó. ĐẠ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 - 7 - 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ữ ĐẠ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 - 8 - 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. ĐẠ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 - 9 - 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, một vật chuyển động trên mặt đẳng thế thì không sinh công. Nghĩa là, phải đạt được kết quả cần thiết với năng lượng và chi phí thấp nhất. Ví dụ: Yêu cầu của lập trình viên khi lập trình là phải viết code trong sáng và tối ưu thời gian chạy, tối ưu bộ nhớ để project đạt yêu cầu tốt nhất. 13) Nguyên tắc đảo ngược: Nội dung: - Làm ngược lại với yêu cầu ban đầu của bài toán. - Làm phần chuyển động của đối tượng(hay môi trường bên ngoài) thành đứng yên và ngược lại, phần đứng yên thành chuyển động. - Lật ngược đối tượng. Áp dụng nguyên lý này sẽ giúp khắc phục được tính ỳ tâm lý, không bị chi phối bởi suy nghĩ lối mòn là phải làm yêu cầu của bài toán. Làm ngược lại có thể cho đối tượng thêm những chức năng, tính chất, khả năng mới. Đối với những bài toán có yêu cầu quá phức tạp, nếu lật ngược vấn đề có thể được giải quyết nhanh chóng và hiệu quả. Ví dụ: Trong mã hóa thông tin, ta sử dụng phương pháp đảo bít để mã hóa. Khi giải mã sẽ đảo bít trở lại. 14) Nguyên tắc cầu hóa: Nội dung: - Chuyển những phần thẳng của đối tượng thành cong, mặt phẳng thành mặt cầu, kết cấu hình hộp thành kết cấu hình cầu. - Sử dụng các con lăn, viên bi, hình xoắn. - Chuyển sang chuyển động quay, sử dụng lực ly tâm. Ví dụ: Người ta sử dụng đĩa CD hình tròn để ghi dữ liệu theo những vòng tròn trên đĩa, có thể tận dụng tối đa không gian ghi dữ liệu cũng như tiện trong việc ghi đĩa : chỉ cần quay tròn đĩa để ghi dữ liệu lên. 15) Nguyên tắc linh động: Nội dung: - Cần thay đổi các đặc trưng của đối tượng hay môi trường bên ngoài sao cho chúng tối ưu trong từng giai đoạn làm việc. - Phân chia đối tượng thành từng phần, có khả năng dịch chuyển với nhau. Nguyên tắc này đòi hỏi phải có cái nhìn bao quát cả quá trình để làm đối tượng hoạt động tối ưu trong từng giai đoạn. Muốn thế đối tượng không thể ở dạng cố định, cứng nhắc mà phải trở nên điều khiển được. Các mối liên kết trong đối tượng phải mềm dẻo, có nhiều trạng thái để từng phần đối tượng có khả năng “dịch chuyển”. ĐẠ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 - 10 - Ví dụ: Kiểu Object trong lập trình có thể linh động chứa các giá trị kiểu Integer, String, Long, … 16) Nguyên tắc giải “thiếu” hoặc “thừa”: Nội dung: - Nếu kết quả vấn đề không đạt được 100% hiệu quả cần thiết thì có thể nhận ít hơn hoặc nhiều hơn “một chút”. Đối với những bài toán quá khó, ta cần giảm bớt yêu cầu để dễ giải quyết hơn, mặc dù kết quả không hoàn toàn như mong muốn. Ví dụ: Trong 1 project, nếu giải quyết 1 yêu cầu ban đầu của khách hàng quá khó, lập trình viên có thể đề xuất 1 cách khác không giống như yêu cầu ban đầu( có thể tăng hoặc giảm số bước thực hiện) để đạt được kết quả mong muốn. 17) Nguyên tắc chuyển sang chiều khác: Nội dung: - Những khó khăn do chuyển động (hay sắp xếp) đối tượng theo đường (một chiều) sẽ được khắc phục nếu cho đối tượng khả năng di chuyển trên mặt phẳng (hai chiều). Tương tự, những bài toán liên quan đến chuyển động( hay sắp xếp) các đối tượng trên mặt phẳng sẽ được đơn giản hóa khi chuyển sang không gian (ba chiều). - Chuyển các đối tượng có kết cấu một tầng thành nhiều tầng. - Đặt các đối tượng nằm nghiêng. - Sử dụng mặt sau của diện tích cho trước. - Sử dụng các luồng ánh sáng tới diện tích bên cạnh hoặc tới mặt sau của diện tích trước. Ví dụ: Đối với các bài toán trong Kỹ thuật đồ họa, phép tịnh tiến trong không gian 3D quá phức tạp sẽ được chuyển về không gian 2D để dễ giải quyết hơn. 18) Nguyên tắc sử dụng các dao động cơ học: Nội dung: - Làm cho đối tượng dao động. Nếu đã có dao động, tăng tần số dao động (đến tần số siêu âm). - Sử dụng tần số cộng hưởng. - Thay vì dùng các bộ rung cơ học, dùng các bộ rung áp điện. - Sử dụng siêu âm kết hợp với trường điện từ. - 19) Nguyên tắc tác động theo chu kỳ: Nội dung: - Chuyển tác động liên tục thành tác động theo chu kỳ (xung) - Nếu đã có tác động theo chu kỳ, hãy thay đổi chu kỳ. - Sử dụng khoảng thời gian giữa các xung để thực hiện tác động khác. ĐẠ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 - 11 - Ví dụ: CPU hoạt động theo các xung, có thể tận dụng khoảng thời gian rỗi giữa các xung này để điều phối 1 tiến trình khác (đa nhiệm). 20) Nguyên tắc liên tục tác động có ích: Nội dung: - Thực hiện công việc một cách liên tục (tất cả các phần của đối tượng cần luôn luôn làm việc ở chế độ đủ tải). - Khắc phục vận hành không tải và trung gian. - Chuyển từ chuyển động tịnh tiến qua lại thành chuyển động quay. Ví dụ: Trong việc truyền tin, đối với gói tin truyền không thành công, ta cho truyền liên tục cho đến khi được nhận thành công. 21) Nguyên tắc vượt nhanh: Nội dung: - Vượt qua các giai đoạn có hại hoặc nguy hiểm với vận tốc lớn. - Vượt nhanh để có được hiệu ứng cần thiết. Nếu tác động là nguy hiểm, có hại thì có thể làm cho nó không còn có hại nữa bằng cách giảm thời gian tác động đến tối thiểu, nói cách khác, phải vượt thật nhanh để có độ an toàn cao. Trong nhiều trường hợp, đối tượng phải làm việc với những quá trình xảy ra nhanh. Để có sự phù hợp, để có được những kết quả cần thiết, bản thân đối tượng phải chuyển sang trạng thái “vượt nhanh”. Ví dụ: Đối với những vòng lặp while, for cần có break hay continue để bỏ qua những trường hợp không cần thiết phải lặp. 22) Nguyên tắc biến hại thành lợi: Nội dung: - Sử dụng những tác nhân có hại (thí dụ tác động có hại của môi trường) để thu được hiệu ứng có lợi. - Khắc phục tác nhân có hại bằng cách kết hợp nó với tác nhân có hại khác. Tăng cường tác nhân có hại đến mức nó không còn có hại nữa. 23) Nguyên tắc quan hệ phản hồi: Nội dung: - Thiết lập quan hệ phản hồi. - Nếu có quan hệ phản hồi, hãy thay đổi nó. Khi thành lập quan hệ phản hồi cần chú ý tận dụng những nguồn dự trữ có sẵn trong hệ để đưa ra cấu trúc tối ưu. Nguyên tắc này phản ánh khuynh hướng phát triển: làm tăng tính điều khiển đối tượng, tự động hóa. ĐẠ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 - 12 - Ví dụ: Chức năng tự động gửi mail đến lập trình viên có liên quan khi server tự động deploy 1 project bị lỗi. 24) Nguyên tắc sử dụng trung gian: Nội dung: - Sử dụng đối tượng trung gian, chuyển tiếp. Có những vấn đề cần phải có đối tượng trung gian để giải quyết vấn đề nhanh chóng và dễ dàng hơn. Ví dụ: Trong bài toán hoán vị giá trị của 2 số a và b, ta sử dụng 1 biến trung gian temp để gán giá trị của a cho temp, sau đó gán b cho a và gán temp cho b. 25) Nguyên tắc tự phục vụ: Nội dung: - Đối tượng phải tự phục vụ bằng cách thực hiện các thao tác phụ trợ, sửa chữa. - Sử dụng phế liệu, chất thải, năng lượng dư. - 26) Nguyên tắc sao chép: Nội dung: - Thay vì sử dụng những cái không được phép, phức tạp, đắt tiền, không tiện lợi hoặc dễ vỡ, ta có thể sử dụng bản sao. - Thay thế đối tượng hoặc hệ các đối tượng bằng bản sao quang học với các tỉ lệ cần thiết. - Nếu không thể sử dụng bản sao quang học ở vùng biểu kiến, chuyển sang sử dụng các bản sao hồng ngoại hoặc tử ngoại. Đối tượng nhận được do sao chép, nhiều khi có thêm những tính chất mới mà trước đây đối tượng cũ không có như gọn, nhẹ, dễ bảo quản, lưu trữ,.. Nếu thường xuyên sử dụng bản sao, mô hình của đối tượng cần chú ý đề phòng tính ỳ tâm lý: coi mô hình chính là đối tượng thật có trên thực tế, có thể đi đến những kết luận chủ quan, duy ý chí. Ví dụ: Các loại ebook trên mạng được sao chép cho cộng đồng mạng để việc chia sẻ tri thức được nhanh chóng hơn là sử dụng sách giấy thông thường. 27) Nguyên tắc “rẻ” thay cho “đắt”: Nội dung: - Thay thế đối tượng đắt tiền bằng các đối tượng rẻ có chất lượng kém hơn. Nguyên tắc này đòi hỏi người giải quyết không cứng nhắc, cầu toàn, chờ đợi điều kiện lý tưởng khi pải giải các bài toán khó. Cần chú ý tới khả năng nâng chất lượng kèm theo hạ giá thành của đối tượng. Ví dụ: Các thiết bị điện tử hiện nay giảm giá thành hơn so với trước kia có thể do nhiều nguyên nhân như: thay thế các phần không cần phải sử dụng nguyên liệu đắt tiền(các phần không cần thiết) thành nguyên liệu rẻ tiền hơn, như vỏ bọc USB,… ĐẠ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 - 13 - 28) Nguyên tắc thay thế sơ đồ cơ học: Nội dung: - Thay thế sơ đồ cơ học bằng điện, quang, nhiệt, âm hoặc mùi vị. - Sử dụng điện trường, từ trường và điện từ trường trong tương tác đối với đối tượng. - Chuyển các trường đứng yên sang chuyển động, các trường cố định sang thay đổi theo thời gian, các trường đồng nhất sang có cấu trúc nhất định. - Sử dụng các trường kết hợp với các hạt sắt từ. Ví dụ: Thao tác log in vào máy tính bằng cách nhận diện khuôn mặt thay cho việc nhập password từ bàn phím. 29) Nguyên tắc sử dụng các kết cấu khí và lỏng: Nội dung: - Thay cho các phần của đối tượng ở thể rắn, sử dụng các chất khí và lỏng: nạp khí, nạp chất lỏng, đệm không khí, thủy tĩnh, thủy phản lực. Sử dụng được các kết cấu khí và lỏng, trên thực tế là khai thác những nguồn dự trữ có sẵn trong hệ và môi trường. 30) Nguyên tắc sử dụng vỏ dẻo và màng mỏng: Nội dung: - Sử dụng các vỏ dẻo và màng mỏng thay cho các kết cấu khối. - Cách ly đối tượng với môi trường bên ngoài bằng các vỏ dẻo và màng mỏng. Nguyên tắc này liên quan đến bề mặt, lớp ngăn cách đối tượng, tại đó có những yêu cầu mà kết cấu khối không đáp ứng được hoặc đáp ứng nhưng với mức độ hiệu quả không lớn. Vỏ dẻo và màng mỏng có nhiều ưu điểm như nhẹ, linh động, chiếm ít không gian, có chức năng bảo vệ tốt, cho phép đối tượng có những bề mặt đa dạng về trang trí, mỹ thuật, tiết kiệm nguyên vật liệu… Ví dụ: Bàn phím có loại được chế tạo từ vỏ nhựa dẻo có thể bẻ cong. 31) Nguyên tắc sử dụng vật liệu nhiều lỗ: Nội dung: - Làm đối tượng có nhiều lỗ hoặc sử dụng thêm những chi tiết có nhiều lỗ (miếng đệm, tấm phủ…) - Nếu đối tượng đã có nhiều lỗ, sơ bộ tẩm nó bằng chất nào đó. Ví dụ: Mặt dưới của laptop thường có nhiều lỗ trống để làm mát các bộ phận bên trong. ĐẠ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 - 14 - 32) Nguyên tắc thay đổi màu sắc: Nội dung: - Thay đổi màu sắc của đối tượng hay môi trường bên ngoài. - Thay đổi độ trong suốt của đối tượng hay môi trường bên ngoài. - Để có thể quan sát được những đối tượng hoặc những quá trình, sử dụng các chất phụ gia màu, huỳnh quang. - Nếu các chất phụ gia đó đã được sử dụng, dùng các nguyên tử đánh dấu. - Sử dụng các hình vẽ, ký hiệu thích hợp. Màu sắc có nhiều, do đó cần tránh thói quen chỉ sử dụng một loại màu nào đó. Cần quy ước mỗi loại màu tương ứng với cái gì, trên cơ sở đó dễ bao quát, xử lý thông tin nhanh. Các hình vẽ, ký hiệu thích hợp rất có tác dụng, giúp cho suy nghĩ thoáng, thấy được các mối liên hệ giữa các bộ phận. Nếu có thể, nên vẽ sơ đồ khối. Ví dụ: Giao diện window thân thiện với người dùng với các quy định về màu sắc, hình vẽ đặc sắc. Các cửa sổ thông báo có màu sắc tương ứng như, màu vàng đối với các câu cảnh báo, màu đỏ đối với thông báo lỗi, và chữ i màu xanh đối với những câu thông báo thông thường. 33) Nguyên tắc đồng nhất: Nội dung: - Những đối tượng, tương tác với đối tượng cho trước, phải được làm từ cùng một vật liệu (hoặc từ vật liệu gần về các tính chất) với vật liệu chế tạo đối tượng cho trước. Sự tương hợp, trên thực tế là sự thống nhất mới của các mặt đối lập, cho phép đối tượng hoặt động một cách hiệu quả hơn trước. Để tạo sự tương hợp, cần chú ý khai thác những nguồn dự trữ có sẵn trong đối tượng, đặc biệt những nguồn dự trữ không mất tiền. 34) Nguyên tắc phân hủy hoặc tái sinh các phần: Nội dung: - Phần đối tượng đã hoàn thành nhiệm vụ hoặc trở nên không cần thiết phải tự phân hủy (hòa tan, bay hơi…) - Các phần mất mát của đối tượng phải được phục hồi trực tiếp trong quá trình làm việc. Ví dụ: Ổ ứng máy tính sau thời gian lưu trữ dữ liệu bị đầy, cần phải xóa 1 phần dữ liệu không cần thiết để giải phóng không gian nhớ, dành chỗ để lưu trữ dữ liệu mới. 35) Nguyên tắc thay đổi các thông số hóa lý của đối tượng: Nội dung: - Thay đổi trạng thái đối tượng. - Thay đổi nồng độ hay độ đậm đặc. - Thay đổi độ dẻo. - Thay đổi nhiệt độ, thể tích. Việc sử dụng các trạng thái khác nhau của đối tượng chính là sự thể hiện cụ thể của “khai thác các nguồn dự trữ có sẵn trong đối tượng”. ĐẠ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 - 15 - Khi thay đổi thông số của đối tượng, cần chú ý “lượng đổi, chất đổi” để có được những tính chất mới mà trước đây đối tượng chưa có. 36) Nguyên tắc sử dụng sự chuyển pha: Nội dung: - Sử dụng các hiện tượng nảy sinh trong quá trình chuyển pha như: thay đổi thể tích, tỏa hay hấp thu nhiệt lượng…. - 37) Nguyên tắc sử dụng sự nở nhiệt: Nội dung: - Sử dụng sự nở nhiệt (hay co) nhiệt của các vật liệu. - Nếu đã dùng sự nở nhiệt, sử dụng với vật liệu có các hệ số nở nhiệt khác nhau. Sự nở (co) nhiệt tạo nên sự thống nhất mới giữa các mặt đối lập, như ngắng và dài, thẳng và cong, nóng và lạnh….. 38) Nguyên tắc sử dụng chất oxy hóa mạnh: Nội dung: - Thay không khí thường bằng không khí giàu oxy. - Thay không khí giàu oxy bằng chính oxy. Dùng các bức xạ ion hóa tác động lên không khí hoặc oxy. 39) Nguyên tắc thay đổi độ trơ: Nội dung: - Thay đổi môi trường thông thường bằng môi trường trung hòa. - Đưa thêm vào đối tượng các phần, các chất, phụ gia trung hòa. - Thực hiện quá trình trong chân không. Thay đổi độ trơ có thể dùng để giải quyết các mâu thuẫn như ít mà nhiều, nhỏ mà lớn… 40) Nguyên tắc sử dụng vật liệu hợp thành composit: Nội dung: Chuyển từ các vật liệu đồng nhất sang sử dụng những vật liệu hợp thành (composit). Hay nói chung, sử dụng các vật liệu mới. ĐẠ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 - 16 - 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 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. ĐẠ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 - 17 -  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. 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). ĐẠ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 - 18 - Xâu con chung dài nhất bằng quy hoạch động a) Công thức quy hoạch động: Gọi L(i,j) là độ dài xâu con chung dài nhất của xâu X(i) gồm i ký tự của X (X(i) = X[1..i]) và xâu Y(j) gồm j ký tự của Y (Y(j) = Y[1..j]) Công thức quy hoạch động như sau: L(0,j) = L(i,0) = 0. L(i,j) = L(i-1, j-1) + 1 nếu X[i] = Y[j]. L(i,j) = MAX (L(i-1, j), L(i, j -1)) nếu X[i] Y[j]. b) Cài đặt: Bảng phương án là một mảng 2 chiều L[0.m, 0..n] để lưu các giá trị của hàm Quy hoạch động L(i, j). Đoạn chương trình cài đặt công thức Quy hoạch động trên như sau: for i = 0 to m do L[i, 0] = 0 for j - 0 to n do L[0, j ] = 0 for i = 1 to m do for j = 1 to n do if X[i] = Y[j] L[i,j] = L[i-1, j-1] + 1 Else L(i,j) = MAX (L(i-1, j), L(i, j -1)) Như vậy chi phí không gian của bài toán là O(n2) , chi phí thời gian là O(n2). Có phương pháp cài đặt tốt hơn, chỉ với chi phí không gian O(n) dựa trên điểm sau: để tính ô L[i,j], ta chỉ cần 3 ô L[i-1, j-1], L[i-1, j] và L[i, j-1]. Tức là để tính dòng L[i] chỉ cần dòng L[i-1]. Do đó, ta chỉ cần 2 mảng 1 chiều để lưu dòng vừa tính (P) và dòng đang tính (L) mà thôi. Cách cài đặt mới như sau: for j = 0 to n do P[j] = 0 for i = 1 to m do begin L[0] = 0; For j =1 to n do If X[i] = Y[j] then L[i,j] = P[j-1] + 1 Else L[i,j] = MAX(P[j], L[j-1]) P = L; End 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 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 Bài toán tìm kiếm được xây dựng lại như sau: “cho văn bản V có độ dài N và mẫu tìm kiếm Vm có độ dài M (M= k”. Với cách phát biểu như trên, ta xác định k là giá trị ngưỡng cho trước (0<= k<= Fmax(x), k đóng vai trò là tham số xác định độ chính xác của hàm tìm kiếm. Bài toán đặt ra là tìm các giá trị x sao cho F(x) đạt giá trị lớn hơn hoặc bằng ngưỡng k cho trước. Nếu tìm được các giá trị xmax để cho F(xmax) = M thì xmax chính là vị trí xuất hiện mẫu Vm cần tìm trong văn bản V. Trường hợp bài toán chỉ cho kết quả tương đối tốt thì x là các vị trí mà trong đoạn [x, x+M] có xuất hiện một phần trong mẫu tìm kiếm Vm (gần giống ĐẠ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 - 19 - nhất với mẫu tìm kiếm Vm). Trong trường hợp này, có giữ kết quả này hay không phụ thuộc vào ngưỡng k. Với H(x) khống chế sự trùng khớp về vị trí và giá trị giữa hai chuỗi, sự kết hợp của H(x) và G(x) sẽ cho hàm F(x) đạt kết quả gần hơn, sát hơn so với mục tiêu tìm kiếm. Tùy thuộc vào độ dài mẫu tìm kiếm, ta có thể điều chỉnh tham số a và b sao cho kết quả tìm kiếm là tốt nhất. Nếu a lớn hơn b, có nghĩa là ưu tiên dùng hàm quy hoạch động, ngược lại là ưu tiên dùng hàm so khớp vị trí để đánh giá hàm F(x). 4) Cách biểu diễn di truyền cho lời giải của bài toán Ta sử dụng một vecto nhị phân V làm nhiễm sắc thể để biểu diễn các giá trị nguyên của biến X. Chiều dài của vecto chính là số bit trong dãy bit nhị phân biểu được số nguyên lớn nhất trong miền giá trị của X, tức là chiều dài vecto nhị phân length = log2n. Như vậy, vecto nhị phân sẽ có chiều dài length sẽ biễu diển số nguyên là 2length. Ví dụ văn bản có chiều dài tối đa (số ký tự) là n = 4000 thì cần có 12 bit cho vecto nhị phân V: 2048 = 211 < 4000 < 212 = 4096. Nhiễm sắc thể v1 = (110001100010) thể hiện số 3170 và cũng là vị trí thứ x = 3170 trong văn bản. Nhiễm sắc thể v2 = (000000001100) thể hiện x = 12. 5) Cách khởi tạo quần thể lời giải ban đầu Tạo một quần thể các nhiễm sắc thể, trong đó mỗi nhiễm sắc thể là một vecto nhị phân 12 bit, tất cả 12 bit cảu mỗi nhiễm sắc thể được khởi tạo ngẫu nhiên. 6) Xây dựng hàm thích nghi đóng vai trò môi trường và đánh giá lời giải Hàm thích nghi chính là hàm tím kiếm đã trình bày trong mục 3.0. 7) Sử dụng các toán tử lai ghép  Toán tử chọn lọc Sử dụng toán tự chọn lọc tỷ lệ, ta thực hiện tiến trình chọn lọc bằng cách quay bánh xe rulet pop-size lần; mỗi lần ta chọn một nhiễm sắc thể từ quần thể hiện hành vào quần thể mới. Xác suất lựa chọn của mỗi cá thể tỷ lệ thuận với giá trị độ thích hợp của nó.  Toán tử lại ghép Sự dụng toán tử lai ghép một điểm (One - point Crossover). Với cặp cha mẹ X, Y là các vecto m chiều như ký hiệu trên, toán tử lai ghép 1 điểm chọn ngẫu nhiên một vị trí k (1 <= k <= m) rồi sinh ra 2 cá thể con theo công thức: X ' = (x1,..., xk, yk+1,..., ym) Y ' = (y1,..., yk, xk+1,..., xm) Nếu cá thể con X' thích nghi tốt hơn cá thể cha mẹ X thì ta thay thể cá thể mẹ X bởi cá thể con X', tương tự Y' cũng được thay thế Y nếu Y' có thích nghi tốt hơn.  Toán tử đột biến - Chọn ngẫu nhiên 01 nhiễm sắc thể trong quần thể. - Tạo một số ngẫu nhiên k trong khoảng 1 tới m (1 <= k <= m) - Thay đổi bit thứ k trong nhiễm sắc thể vừa chọn, nếu nhiễm sắc thể này không xấu hơn nhiễm sắc thể ban đầu thì đưa nhiễm sắc thể vào quần thể để tham gia quá trình tiến hóa ở thế hệ kế tiếp. ĐẠ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 - 20 - PHẦN III : Các nguyên tắc sáng tạo sử dụng trong Thuật toán di truyền a) Nguyên tắc Vượt nhanh: - Vượt qua những giai đoạn có hại hoặc nguy hiểm với vận tốc lớn. - Vượt nhanh để có được hiệu ứng cần thiết. b) b. Nguyên tắc giải thừa hoặc thiếu: Nếu như khó nhận 100% hiệu quả cần thiết, nên nhận ít hơn hay nhiều hơn “một chút”. Lúc đó bài toán có thể trở nên đơn giản hơn. Thuật toán Di truyền xét một nhiểm sắc thể có phù hợp hay không dựa vào kết quả của hàm thích nghi. Hàm thích nghi có thể cao hơn hay thấp hơn một chút so với ngưỡng do người dùng thiết lập. Đây là sự áp dụng Nguyên tắc giải thiếu hoặc thừa. c) Nguyên tắc Sao chép: Trong thuật toán di truyền, các nhiểm sắc thể con được hình thành từ việc sao chép một phần của nhiểm sắc thể cha và một phần của nhiểm sắc thể mẹ. Sự sao chép này theo tỷ lệ thế nào là phụ thuộc vào sự tính toán của người dùng sao cho tối ưu nhất. d) Nguyên tắc Tự phục vụ: - Đối tượng phải tự phục vụ bằng cách thực hiện các thao tác phụ trợ, sửa chữa. - Sử dụng phế liệu, chất thải, năng lượng dư. Trong thuật toán di truyền, các nhiễm sắc thể phải liên tục thực hiện việc lai ghép và đột biến gen để có thể dần tiến đến việc tạo lập những thế hệ tốt và tối ưu hơn thế hệ trước. e) Nguyên tắc phân hủy hoặc tái sinh các phần: Nhiễm sắc thể cha và mẹ sau khi thực hiện lai ghép hay đột biến để tạo thành nhiễm sắc thể con. Nếu như nhiểm sắc thể con đạt được kết quả hàm thích nghi cao hơn hay tối ưu hơn so với thế hệ cha mẹ, thì nhiễm sắc thể cha mẹ sẻ được loại bỏ đi. Để kết quả của thuật toán di truyền sẽ đạt được tối ưu nhất, hoàn thiện nhất. ĐẠ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 - 21 - PHẦN IV : Nguồn tham khảo 1) 2) vi.wikipedia.org/wiki/Giải_thuật_di_truyền 3) portal.uct.edu.vn 4)