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

Đề tài "Chiến lược tiến hóa song song" trình bày nội dung tổng quan về chiến lược tiến hóa, xây dựng khung chiến lược tiến hóa và sử dụng khung chiến lược tiến hóa để giải quyết bài toán Sphere. Để biết rõ nội dung chi tiết, mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Báo cáo nghiên cứu khoa học: Chiến lược tiến hóa song songChiến lược tiến hóa song songTRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘIKHOA CÔNG NGHỆ THÔNG TINBÁO CÁO NGHIÊN CỨU KHOA HỌCĐề tài: Chiến Lược Tiến Hóa Song SongGiảng viên : Đỗ Trung KiênSinh viên: Cao Thị Việt HòaLớp K54BCao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN1Chiến lược tiến hóa song songPhụ lụcCHƢƠNG I: TỔNG QUAN VỀ CHIẾN LƢỢC TIẾN HOÁ………………..31.Tổng quan giải thuật di truyền………………………………………32.Tổng quan về chiến lược tiến hóa…………………………………...42.1Chiến lược tiến hóa là gì……………………………………42.2Lịch sử phát triển của thuật toán chiến lược tiến hóa………52.3Tính chất của thuật toán chiến lược tiến hóa. ……………...52.4Kỹ thuật chiến lược tiến hóa……………………………….52.5Giải thuật chiến lược tiến hóa………………………………63.Ví dụ minh họa……………………………………………...............6CHƢƠNG II: XÂY DỰNG KHUNG ES………………………………………..71.Thiết kế khung ES………………………………………………….71.1 Các lớp đòi hỏi (Requires)……………………………………...71.2 Các lớp cung cấp (Provided)…………………………………...82.Khung thuật toán tuần tự………………………………………….143.Khung thuật toán song song……………………………………….163.1 Mô hình phần cứng………………………………………….....163.2 Mô hình phần mềm…………………………………………….163.2.1. Mô hình máy chủ-khách (Master-slave)………………...163.2.2. Mô hình đảo (Island model)…………………………….173.2.3. Mô hình khuếch tán (Diffusion model)…………………17CHƢƠNG III: SỬ DỤNG KHUNG CHIẾN LƢỢC TIẾN HÓA ĐỂ GIẢIQUYẾT BÀI TOÁN SPHERE…………………………………………………171.Sử dụng khung ES giải quyết bài toán sphere…………………….171.1 Định nghĩa bài toán Sphere……………………………………171.2 Khung bài toán Sphere………………………………………...182.Kết quả thực nghiệm………………………………………………..20Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN2Chiến lược tiến hóa song songLỜI NÓI ĐẦUNgày nay song song với qúa trình phát triển khoa học công nghệ va kỹthuật thì ngành khoa học tính toán đã đóng vai trò quan trọng. Nó đã đạt đượcnhiề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ựunà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ó ảnhhưở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àmột trong những ngành khoa học đó. Trên thế giới cũng như ơ Việt Nam, côngnghệ thông tin đã trở thành một ngành công nghiệp mũi nhọn, nó là một ngànhkhoa 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ảnlý, Kinh tế, Thông tin…đặt biệt là để giải quyết các vấn đề mà trước đây tưởngnhư không thể làm được.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ủacuộ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ổ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ếmkhi đò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ẩnnà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đượ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ườita 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ápmà theo đó, chi phí giảm đến một mức độ nào đó là đủ chứ không nhất thiết phảithự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ượctiến hóa”.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ểtrong thuật toán di truyền chỉ là các chuỗi nhị phân. Do đó, rất khó khăn khi ápdụ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à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áttriể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àinghiê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”.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ưu hóa dựa trên những ý tưởng của sự thích nghi và tiến hóa.Cao Thị Việt Hòa- Lớp K54B- Khoa CNTT- Trường ĐHSPHN3Chiến lược tiến hóa song songCHƢƠNG I: TỔNG QUAN VỀ CHIẾN LƢỢC TIẾN HOÁ1. Tổng quan giải thuật di truyền.Thuật toán di truyền (Genetic Algorithms) là kỹ thuật giúp giải quyết bàitoá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óichung (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đổ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đú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ínhxá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ấtlà 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ậtkế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ácnhiễ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ànhmộ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ếnhó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, laighép và đột biến.Các phát triển của giải thuật di truyề ...