Báo cáo nghiên cứu khoa học: Chiến lược tiến hóa song song

Chiến lược tiến hóa song song<br /> TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI<br /> KHOA CÔNG NGHỆ THÔNG TIN<br /> <br /> BÁO CÁO NGHIÊN CỨU KHOA HỌC<br /> Đề tài: Chiến Lược Tiến Hóa Song Song<br /> <br /> Giảng viên : Đỗ Trung Kiên<br /> Sinh viên: Cao Thị Việt Hòa<br /> Lớp K54B<br /> <br /> Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN<br /> <br /> 1<br /> <br /> Chiến lược tiến hóa song song<br /> <br /> Phụ lục<br /> CHƢƠNG I: TỔNG QUAN VỀ CHIẾN LƢỢC TIẾN HOÁ………………..3<br /> 1.<br /> Tổng quan giải thuật di truyền………………………………………3<br /> 2.<br /> Tổng quan về chiến lược tiến hóa…………………………………...4<br /> 2.1<br /> <br /> Chiến lược tiến hóa là gì……………………………………4<br /> <br /> 2.2<br /> <br /> Lịch sử phát triển của thuật toán chiến lược tiến hóa………5<br /> <br /> 2.3<br /> <br /> Tính chất của thuật toán chiến lược tiến hóa. ……………...5<br /> <br /> 2.4<br /> <br /> Kỹ thuật chiến lược tiến hóa……………………………….5<br /> <br /> 2.5<br /> <br /> Giải thuật chiến lược tiến hóa………………………………6<br /> <br /> 3.<br /> Ví dụ minh họa……………………………………………...............6<br /> CHƢƠNG II: XÂY DỰNG KHUNG ES………………………………………..7<br /> 1.<br /> Thiết kế khung ES………………………………………………….7<br /> 1.1 Các lớp đòi hỏi (Requires)……………………………………...7<br /> 1.2 Các lớp cung cấp (Provided)…………………………………...8<br /> 2.<br /> Khung thuật toán tuần tự………………………………………….14<br /> 3.<br /> Khung thuật toán song song……………………………………….16<br /> 3.1 Mô hình phần cứng………………………………………….....16<br /> 3.2 Mô hình phần mềm…………………………………………….16<br /> 3.2.1. Mô hình máy chủ-khách (Master-slave)………………...16<br /> 3.2.2. Mô hình đảo (Island model)…………………………….17<br /> 3.2.3. Mô hình khuếch tán (Diffusion model)…………………17<br /> CHƢƠNG III: SỬ DỤNG KHUNG CHIẾN LƢỢC TIẾN HÓA ĐỂ GIẢI<br /> QUYẾT BÀI TOÁN SPHERE…………………………………………………17<br /> 1.<br /> Sử dụng khung ES giải quyết bài toán sphere…………………….17<br /> 1.1 Định nghĩa bài toán Sphere……………………………………17<br /> 1.2 Khung bài toán Sphere………………………………………...18<br /> 2.<br /> Kết quả thực nghiệm………………………………………………..20<br /> <br /> Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN<br /> <br /> 2<br /> <br /> Chiến lược tiến hóa song song<br /> <br /> LỜI NÓI ĐẦU<br /> Ngày nay song song với qúa trình phát triển khoa học công nghệ va kỹ<br /> thuật thì ngành khoa học tính toán đã đóng vai trò quan trọng. Nó đã đạt được<br /> nhiều thành tựu rực rỡ với những bước tiến nhảy vọt. Việc áp dụng các thành tựu<br /> này vào các lĩnh vực đời sống, xã hội của con người ngày càng tăng và có ảnh<br /> hưởng tới hầu hết các công việc trong đời sống hàng ngày, công nghệ thông tin là<br /> một trong những ngành khoa học đó. Trên thế giới cũng như ơ Việt Nam, công<br /> nghệ thông tin đã trở thành một ngành công nghiệp mũi nhọn, nó là một ngành<br /> khoa học không thể thiếu trong việc áp dụng vào các hoạt động xã hội như: Quản<br /> lý, Kinh tế, Thông tin…đặt biệt là để giải quyết các vấn đề mà trước đây tưởng<br /> như không thể làm được.<br /> Tối ưu hóa là một trong những bài toán kinh điển trong nhiều lĩnh vực của<br /> cuộc sống từ nhu cầu đơn giản của từng cá nhân đến nhu cầu phức tạp của các tổ<br /> chức kinh tế, chính trị và xã hội. Tuy nhiên các bài toán tố ưu trên thực tế lại hiếm<br /> khi đòi hỏi sự tối ưu tuyệt đối mà chỉ đòi hỏi sự tối ưu đủ tốt theo một tiêu chuẩn<br /> nào đó. Hơn nữa, việc tìm ra sự tối ưa tuyệt đối nhiều lúc không thể thực hiện<br /> được do bài toán đặt ra quá phức tạp. Chẳng hạn trong sản xuất kinh doanh, người<br /> ta thường tìm cách tối thiểu chi phí sản xuất. Và dĩ nhiên, họ chỉ cần một giải pháp<br /> mà theo đó, chi phí giảm đến một mức độ nào đó là đủ chứ không nhất thiết phải<br /> thực sự thấp nhất. Đây chính là một điều kiện rất thuận lợi để áp dụng “chiến lược<br /> tiến hóa”.<br /> Xuất phát từ một số nhược điểm của giải thuật di truyền: Các cá thể trong quần thể<br /> trong thuật toán di truyền chỉ là các chuỗi nhị phân. Do đó, rất khó khăn khi áp<br /> dụng thuật toán di truyền cổ điển cho các bài toán trong không gian nhiều chiều và<br /> mỗi NST có độ dài rất lớn,…Vì thế mà các nhà khoa học đã tìm kiếm các phát<br /> triển của giải thuật di truyền để khắc phục các nhược điểm này. Trong khóa Đề tài<br /> nghiên cứu khoa học này tôi đi sâu vào nghiên cứu “Chiến lược tiến hóa”.<br /> Chiến lược tiến hóa là một phát triển của giải thuật di truyền, là một kỹ thuật tối<br /> ưu hóa dựa trên những ý tưởng của sự thích nghi và tiến hóa.<br /> <br /> Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN<br /> <br /> 3<br /> <br /> Chiến lược tiến hóa song song<br /> CHƢƠNG I: TỔNG QUAN VỀ CHIẾN LƢỢC TIẾN HOÁ<br /> 1. Tổng quan giải thuật di truyền.<br /> Thuật toán di truyền (Genetic Algorithms) là kỹ thuật giúp giải quyết bài<br /> toán bằng cách mô phỏng theo sự tiến hóa của con người hay của sinh vật nói<br /> chung (dựa trên thuyết tiến hóa muôn loài của Darwin) trong điều kiện luôn thay<br /> đổi của môi trường sống. Thuật toán di truyền là một hướng tiếp cận tính toán gần<br /> đúng, nghĩa là mục tiêu của thuật toán di truyền không nhằm đưa ra lời giải chính<br /> xác tối ưu mà là đưa ra lời giải tương đối tối ưu. Thuật toán di truyền về bản chất<br /> là thuật toán tìm kiếm dựa theo quy luật của quá trình tiến hóa tự nhiên. Giải thuật<br /> kết hợp sự sống sót của cấu trúc khỏe nhất trong số các cấu trúc biểu diễn các<br /> nhiễm sắc thể với một sự trao đổi thông tin được lựa chọn ngẫu nhiên để tạo thành<br /> một thuật toán tìm kiếm. Thuật toán di truyền nằm trong lĩnh vực tính toán tiến<br /> hóa, sử dụng các biểu diễn nhị phân và các sơ đồ để mô hinhg hóa sự chọn lọc, lai<br /> ghép và đột biến.<br /> Các phát triển của giải thuật di truyền:<br /> -<br /> <br /> Các chiến lược tiến hóa (Evolution strategy) viết tắt là ESs.<br /> <br /> -<br /> <br /> Lập trình tiến hóa (Evolutionary Programming) viết tắt là EP.<br /> <br /> -<br /> <br /> Lập trình di truyền (Genetic Programming) viết tắt là GP.<br /> <br /> -<br /> <br /> Các chương trình tiến hóa (Evolution Programs) viết tắt là Eps.<br /> <br /> Ƣu điểm của giải thuật di truyền:<br />  Thuật toán di truyền duy trì một tập hợp các lời giải có thể do đó có nhiều<br /> cách để chọn lời giải thích hợp.<br />  Thuật toán di truyền giúp tìm ra lời giải tối ưu trong điều kiện thời gian và<br /> không cho phép.<br />  Thuật toán di truyền duyệt xét toàn bộ các lời giải của vấn đề, thay vì chỉ để<br /> ý đến lời giải chính xác và duy nhất như toán học giải thích đã dùng trước<br /> đây.<br /> Nhƣợc điểm của giải thuật di truyền:<br />  Thuật toán di truyền cổ điển đòi hỏi biểu diễn lời giải dưới dạng xâu nhị<br /> phân. Trong khi đó, lời giải của các bài toán trong thực tế thường có cấu<br /> trúc tự nhiên như mảng, bản ghi, cây.<br />  Các kết quả mà Thuật toán di truyền mang lại không được chính xác như<br /> các phương pháp tìm kiếm khác.<br />  Các cá thể trong quần thể trong thuật toán di truyền chỉ là các chuỗi nhị<br /> phân. Do đó, rất khó khăn khi áp dụng thuật toán di truyền cổ điển cho các<br /> bài toán trong không gian nhiều chiều và mỗi NST có độ dài rất lớn.<br /> <br /> Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN<br /> <br /> 4<br /> <br /> Chiến lược tiến hóa song song<br />  Đối với những bài toán có nhiều ràng buộc phức tạp thì các bài toán từ di<br /> truyền truyền thống tỏ ra kém hiệu quả.<br />  Nếu chọn mô hình không phù hợp, thuật tóan di truyền sẽ hội tụ sớm hơn<br /> và cuộc tìm kiếm lời giải chấm dứt sau một thời gian ngắn. Những cuộc tìm<br /> kiếm ngắn thường không tạo ra kết quả tốt, cũng giống như những gì đã<br /> xảy ra trong thực tế.<br /> Để khắc phục những nhược điểm trên, Ingo Rechenberg(1973) đã đưa ra một<br /> kỹ thuật tối ưu hóa dựa trên những ý tưởng của sự thích nghi và tiến hóa đó là<br /> “Chiến lược tiến hóa”.<br /> 2. Tổng quan về chiến lƣợc tiến hóa<br /> Chiến lược tiến hóa là một phát triển của thuật toán di truyền cổ điển còn<br /> có tên gọi là phương pháp tính toán tiến hóa.<br /> 2.1 Chiến lƣợc tiến hóa là gì?<br /> Trong khoa học máy tính, chiến lược tiến hóa (ES) là một kỹ thuật tối ưu<br /> hóa dựa trên những ý tưởng của sự thích nghi và tiến hóa.<br /> Chiến lược tiến hóa là một lớp con của việc tìm kiếm trực tiếp rất tự nhiên<br /> (và tối ưu), là những phương thức thuộc vào lớp của những thuật toán tiến hóa<br /> (EAs). Nó sử dụng sự đột biến, sự lai ghép, và sự lựa chọn thích ứng tới một quần<br /> thể của những cá thể chứa những giải pháp được đề xuất theo trình tự để tiến hóa<br /> lặp lại tốt hơn và những giải pháp tốt hơn.<br /> Dữ liệu đặc trưng của từng cá thể là những tham số sẽ được tối ưu hóa<br /> trong một quá trình tiến hóa cơ bản. Những tham số sẽ được sắp xếp trong những<br /> vector của những số thực, những thao tác cho sự lai ghép(tréo hóa) và đột biến<br /> được định nghĩa.<br /> 2.2 Lịch sử phát triển của thuật toán chiến lƣợc tiến hóa<br /> - Chiến lược tiến hóa (ES) được phát triển tại trường đại học Kỹ Thuật<br /> Berlin vào những năm 1960 và 1970 bởi Ingo Rechenberg (Rechenberg 1973).<br /> Hans Peter Schwefel (Schwefel 1981), giới thiệu sự lai ghép và những quần thể<br /> với nhiều hơn một cá thể, và cung cấp được sự so sánh của ESs với kỹ thuật tối ưu<br /> hóa truyền thống hơn.<br /> 2.3 Tính chất của thuật toán chiến lƣợc tiến hóa<br /> - Chiến lược tiến hóa không dựa vào sự mô phỏng chi tiết của những<br /> phương pháp được tìm thấy với sự tiến hóa tự nhiên. Mà có thể đã được kết luận<br /> bởi việc quan sát những thuật ngữ: tiến hóa và chiến lược.<br /> - Trong sự tiến hóa không có chiến lược.<br /> - Chiến lược tiến hóa đơn thuần tập chung vào dịch những cơ chế cơ bản<br /> của sự tiến hóa sinh học cho những vấn đề kỹ thuật tối ưu.<br /> 2.4 Kỹ thuật chiến lƣợc tiến hóa<br /> Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN<br /> <br /> 5<br /> <br />