Đề tài Chiến lược tiến hóa song song

TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI KHOA CÔNG NGHỆ THÔNG TIN BÁO CÁO NGHIÊN CỨU KHOA HỌC Đề tài: Chiến Lược Tiến Hóa Song Song Giảng viên : Đỗ Trung Kiên Sinh viên: Cao Thị Việt Hòa Lớp K54B Phụ lục CHƯƠNG I: TỔNG QUAN VỀ CHIẾN LƯỢC TIẾN HOÁ………………..3 Tổng quan giải thuật di truyền………………………………………3 Tổng quan về chiến lược tiến hóa…………………………………...4 Chiến lược tiến hóa là gì……………………………………4 Lịch sử phát triển của thuật toán chiến lược tiến hóa………5 2.3 Tính chất của thuật toán chiến lược tiến hóa. ……………...5 2.4 Kỹ thuật chiến lược tiến hóa……………………………….5 2.5 Giải thuật chiến lược tiến hóa………………………………6 Ví dụ minh họa……………………………………………...............6 CHƯƠNG II: XÂY DỰNG KHUNG ES………………………………………..7 1. Thiết kế khung ES………………………………………………….7 1.1 Các lớp đòi hỏi (Requires)……………………………………...7 1.2 Các lớp cung cấp (Provided)…………………………………...8 2. Khung thuật toán tuần tự………………………………………….14 Khung thuật toán song song……………………………………….16 Mô hình phần cứng………………………………………….....16 Mô hình phần mềm…………………………………………….16 3.2.1. Mô hình máy chủ-khách (Master-slave)………………...16 3.2.2. Mô hình đảo (Island model)…………………………….17 3.2.3. Mô hình khuếch tán (Diffusion model)…………………17 CHƯƠNG III: SỬ DỤNG KHUNG CHIẾN LƯỢC TIẾN HÓA ĐỂ GIẢI QUYẾT BÀI TOÁN SPHERE…………………………………………………17 Sử dụng khung ES giải quyết bài toán sphere…………………….17 1.1 Định nghĩa bài toán Sphere……………………………………17 1.2 Khung bài toán Sphere………………………………………...18 2. Kết quả thực nghiệm………………………………………………..20 LỜI NÓI ĐẦU Ngà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 được 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 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 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à một trong những ngành khoa học đó. Trên thế giới cũng như ơ Việt Nam, công 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 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 lý, Kinh tế, Thông tin…đặt biệt là để giải quyết các vấn đề mà trước đây tưởng như 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ủa 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ổ 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 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 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 đượ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 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 mà theo đó, chi phí giảm đến một mức độ nào đó là đủ chứ không nhất thiết phải 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 tiế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 áp 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à 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 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 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”. 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. CHƯƠ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ài 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 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 đổ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ính 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 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 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 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 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 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 ghép và đột biến. Các phát triển của giải thuật di truyền: Các chiến lược tiến hóa (Evolution strategy) viết tắt là ESs. Lập trình tiến hóa (Evolutionary Programming) viết tắt là EP. Lập trình di truyền (Genetic Programming) viết tắt là GP. Các chương trình tiến hóa (Evolution Programs) viết tắt là Eps. Ưu điểm của giải thuật di truyền: 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 cách để chọn lời giải thích hợp. 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à không cho phép. 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ỉ để ý đế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 đây. Nhược điểm của giải thuật di truyền: 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ị 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 trúc tự nhiên như mảng, bản ghi, cây. Các kết quả mà Thuật toán di truyền mang lại không được chính xác như các phương pháp tìm kiếm khác. 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 áp 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à mỗi NST có độ dài rất lớn. Đố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 truyền truyền thống tỏ ra kém hiệu quả. 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 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 kiếm ngắn thường không tạo ra kết quả tốt, cũng giống như những gì đã xảy ra trong thực tế. Để khắc phục những nhược điểm trên, Ingo Rechenberg(1973) đã đưa ra 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 đó là “Chiến lược tiến hóa”. 2. Tổng quan về 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 thuật toán di truyền cổ điển còn có tên gọi là phương pháp tính toán tiến hóa. 2.1 Chiến lược tiến hóa là gì? 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 hóa dựa trên những ý tưởng của sự thích nghi và tiến hóa. 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 (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 (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 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 lặp lại tốt hơn và những giải pháp tốt hơn. Dữ liệu đặc trưng của từng cá thể là những tham số sẽ được tối ưu hóa 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 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 được định nghĩa. 2.2 Lịch sử phát triển của thuật toán chiến lược tiến hóa - Chiến lược tiến hóa (ES) được phát triển tại trường đại học Kỹ Thuật Berlin vào những năm 1960 và 1970 bởi Ingo Rechenberg (Rechenberg 1973). Hans Peter Schwefel (Schwefel 1981), giới thiệu sự lai ghép và những quần thể 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 hóa truyền thống hơn. 2.3 Tính chất của thuật toán chiến lược tiến hóa - 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 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 bởi việc quan sát những thuật ngữ: tiến hóa và chiến lược. - Trong sự tiến hóa không có chiến lược. - 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 của sự tiến hóa sinh học cho những vấn đề kỹ thuật tối ưu. 2.4 Kỹ thuật chiến lược tiến hóa Có 5 kỹ thuật chính như sau: Đưa ra những vector giá trị thực. Lai ghép: riêng biệt hay trung bình. Đột biến: Đột biến Gaussian. Lựa chọn cha mẹ: lựa chọn ngẫu nhiên và duy nhất. Lựa chọn cá thể phát sinh (m,l) hoặc (m+l). 2.5 Giải thuật chiến lược tiến hóa. Sau đây là giải thuật chiến lược tiến hóa: procedure ES;{ t =0; initialize population P(t); evaluate P(t); until (done) { t =t + 1; parent_selection P(t); recombine P(t) mutate P(t); evaluate P(t); survive P(t); } } 3. Ví dụ minh họa: Chiến lược tiến hóa được áp dụng để giải bài tóan Sphere Tìm một vector giá trị X để tối giản biểu thức sau đây (Sphere Function): CHƯƠNG II: XÂY DỰNG KHUNG ES * Lý do: Chúng ta phải đi xây dựng khung thuật toán vì: - Giảm thiểu quá trình code cho những người đi sau. - Cho những người chưa nắm vững về thuật toán vẫn có thể thử nghiệm bài. 1. Thiết kế khung ES Khung thuật toán gồm hai phần cơ bản là Provides và Requires. Lớp Required chỉ định thông tin liên quan đến vấn đề (bài toán). Để cho toàn bộ khung hoạt động thì các lớp này phải được bổ xung thông tin về bài toán phụ thuộc . Lớp Provided thực thi phía bên trong khung bao hàm các thủ tục chung cho các bài toán giải bằng giải thuật di truyền. Thông thường đối với mỗi giải thuật thì thường có một số giải pháp, tất cả các mô hình tuần tự được nhóm vào lớp Solver_Seq. Các mô hình song song được nhóm vào các lớp Solver_Lan và Solver_Wan. 1.1 Các lớp đòi hỏi (Requires) Các lớp đòi hỏi được sử dụng để lưu trữ dữ liệu cơ bản của thuật toán. Ta có thể hình dung các lớp Requre được xây dựng giống như một cái sườn, cái mẫu, và đối với từng bài toán cụ thể lại phải đắp thêm những thông tin riêng của bài toán đó cho hoàn chỉnh. Nhóm các lớp Requires bao gồm các lớp sau: Lớp bài toán (Problem) Diễn tả thông tin bài toán cần giải quyết. Dưới đây là các thủ tục chính trong lớp bài toán Trong đó: - Toán tử chồng cout: Đưa ra các thông số của bài toán pbm theo luồng os. - Toán tử chồng cin: nhận vào các thông số của bài toán pbm từ luồng is. Lớp lời giải (Solution) Lớp lời giải diễn tả lời giải của bài toán, trong quá trình tiến hoá, chúng ta luôn duy trì một quần thể các lời giải có thể của bài toán và áp dụng các thao tác của quá trình tiến hoá lời giải trên quần thể để tìm ra lời giải tối ưu cho bài toán. Dưới đây là các thủ tục chính trong lớp lời giải: Trong đó - operator<< đưa ra các thông số của một lời giải theo os. - operator>> nhận vào các thông số của một lời giải theo luồng is. - char *to_String(): Chuyển nhiễm sắc thể biểu diễn lời giải thành một xâu ký tự - initialize(): Hàm khởi tạo bộ giá trị ngẫu nhiên cho các phần tử trong lời giải - fitness (): Hàm tính độ thích nghi làm cơ sở đánh giá lời giải. Lớp toán tử người sử dụng (Uer_Operator) Thừa kế từ lớp Intra_Operator. Lớp kiểm tra điều kiện dừng (StopCondition) Để xác định điều kiện dừng của bài toán, trong từng bài toán thì điều kiện dừng sẽ khác nhau, thường căn cứ vào một hoặc một vài tham số như số thế hệ, thời gian chạy, các điều kiện đặc thù của bài toán. Lớp provided thi hành bên trong bộ khung của bài toán, nó tạo ra nhiều các phương án cho bài toán. Các lớp cung cấp (Provided) Bao gồm các thủ tục chung cho các bài toán giải bằng giải thuật ES. Ta có thể hình dung các lớp loại provide giống như một thư viện, và khi giải các bài toán chỉ việc gọi nó ra. Trong file .pro gồm các lớp chính là: Intra_Operator, Crossover, Mutation, StopCondition, SetUpParams, Statics, Population, Inter_Operator, Migration, Selection, Selection_Tournament, Selection_Roulette_Wheel, Selection_Rank, Selection_Best, Selection_Worst, Operator_Pool, Solver, Solver_Seq, Solver_Lan. Lớp thiết lập tham số đầu vào (SetUpParams) Lớp này chứa các thủ tục để thiết đặt các tham số cho bài toán như đã nêu trên và cho các toán tử của giải thuật từ 1 file đầu vào: independent_runs : số lần thực hiện quá trình tiến hóa trong một lần thực hiện chương trình population_size : kích thước quần thể nb_evolution_steps : số bước tiến hóa select_parents : phương thức lựa chọn cha select_offsprings : phương thức lựa chọn con combine : có kết hợp quần thể cũ hay chỉ lựa chọn từ quần thể mới. Hàm istream& operator>> (istream& is, SetUpParams& setup) có nhiệm vụ thiết đặt các tham số cho bài toán. Cụ thể, nó nhận vào các thông số cấu hình từ một file dữ liệu (file này sẽ được gọi là file cấu hình), dựa vào các thông số nhận vào này mà chương trình sẽ chọn phương pháp lựa chọn dùng trong bài toán (trong 5 phương pháp lựa chọn đã kể trên), tham số lựa chọn dấu hiệu dừng của thuật toán, ... làm cơ sở cho cấu hình của giải thuật giải bài toán. Crossover: Chéo hóa Hàm khởi tạo giá trị xác suất lai ghép Crossover::Crossover():Intra_Operator(0) { probability = new float[1]; } Đây là hàm khởi tạo xác suất lai ghép từng cặp cá thể trong quần thể. Giá trị này được lưu vào một biến probability. Hàm thực hiện các phép lai ghép void Crossover::execute(Rarray& sols) const Mutation: Đột biến Hàm thực thi sự đột biến void Mutation::execute(Rarray& sols) const Trong hàm này, ta sẽ sử dụng một biến ngẫu nhiên được tạo ra trong đoạn [0,1]. Bằng việc so sánh giá trị của biến ngẫu nhiên này với một giá trị xác suất đột biến nào đó thể xem xét sự đột biến có xảy ra hay không và nếu xảy ra thì kết quả sẽ thay đổi thế nào. void Mutation::execute(Rarray& sols) const { if((N == NULL) && (sols.size() > 0)) { N = new Matrix(sols[0]->pbm().dimension()); for(int i = 0;i pbm().dimension(); i++) { (*N)[i] = (float) rand01()*2.0 - 1.0; } } for (int i=0;i<sols.size();i++) { float aux = rand01(); if(aux < probability[0]) { mutateAngles(*sols[i]); mutateParameters(*sols[i]); mutateVariables(*sols[i]); } } } Statistics: Thống kê số liệu Để nắm rõ được con số, để so sánh được sự khác nhau giữa quần thể ban đầu và quần thể sau quá trình tiến hóa ta cần thống kê lại các thông số cho quần thể mới được sinh ra này. Sau đó căn cứ vào các con số này ta sẽ có những đánh giá cụ thể về sự tiến hóa của quần thể. Lớp quần thể (Population) Lớp này lưu trữ các thông tin về quần thể các nhiễm sắc thể. Dưới đây là các thủ tục chính trong lớp quần thể. Trong đó : Evaluate(Solution *sol, struct individual &_f) : tạo ra cá thể _f (độ thích nghi, vị trí ) tương ứng với nhiễm sắc thể sol. initialize() : Sinh ra một tập các cá thể mới trong quần thể evolution() : Tiến hóa quần thể bằng các phương pháp: lụa chọn, lai ghép, đột biến. evaluate_parents() : Tạo ra một mảng chứa đựng độ thích nghi của tất cả các cá thể và vị trí của nó trong quần thể. Cùng với việc đánh giá độ thích nghi của cha tốt nhất, cha tồi nhất và giá trị trung bình evaluate_offsprings() : Tạo ra một mảng chứa đựng độ thích nghi của tất cả các cá thể và các con cùng vị trí của nó trong quần thể. select_parents() : Lựa chọn cha để tiến hành lai ghép, sử dụng một trong 5 phương pháp để tiến hành lựa chọn. select_offsprings() : Lựa chọn các cá thể cho quần thể mới. Có hai phương pháp hoặc là chỉ lựa chọn từ quần thể mới (combine = 0) hoặc là lựa chọn từ quần thể mới và quần thể cũ (combine = 1) Hàm quan trọng nhất trong lớp này là hàm evolution(), nó để thực hiện công việc tiến hoá quần thể hay sinh quần thể mới qua các phép chọn lọc, lai ghep, đột biến như trên đã tìm hiểu. Selection: Chọn lọc Có 5 kiểu chọn lọc: Một là: Selection_Tournament: chọn lọc cạnh tranh Ta có thể hiểu đây là sự lựa chọn dựa trên “thi đấu” giữa các cá thể. Thuật toán lựa chọn cá thể dựa trên phương pháp này, mỗi một lần thực hiện chỉ lựa chọn được một cá thể duy nhất. Hai là: Selection_Roulette_Wheel: chọn lọc Roulette_Wheel Đây là thuật toán lựa chọn dựa trên một cái vòng quay. Trên vòng quay có gắn một con trỏ, kết thúc lượt quay con trỏ chỉ vào vị trí cá thể nào thì cá thể ấy được chọn. Ba là: Selection_Rank: chọn lọc xếp hạng Đây là thuật toán mà sau mỗi vòng ta chỉ chọn được một cá thể duy nhất. Cá thể được chọn là cá thể có thứ hạng, có vị trí cao nhất trong quần thể (xét với một phạm vi được xét nào đó) Bốn là: Selection_Best: chọn lọc tốt nhất Đây là thuật toán mà mỗi một vòng ta chỉ chọn được duy nhất một phần tử, đó là phần tử tốt nhất. Thuật toán này đánh giá dựa trên 2 chiến lược chọn lựa là Selection_Rank và selection_best_position. Năm là: Selection_Worst: chọn lọc tồi nhất Đây là thuật toán mà mỗi một vòng ta chỉ chọn được duy nhất một phần tử, đó là phần tử xấu nhất (khác biệt với các chiến lược chọn lựa trên). Thuật toán này cũng được đánh giá dựa trên 2 chiến lược chọn lựa là Selection_Rank và selection_Worst_position. => Ta có thể thực hiện chiến lược chọn lựa khác nhau bằng việc nhập các giá trị tương ứng với các giá trị trong trường hợp sau đây: ostream& operator<< (ostream& os, const Selection& sel) { switch (sel.number_selection()) { case 0: os << "Random Selection"; break; case 1: os << (Selection_Tournament&)sel; break; case 2: os << (Selection_Roulette_Wheel&)sel; break; case 3: os << (Selection_Rank&)sel; break; case 4: os << (Selection_Best&)sel; break; case 5: os << (Selection_Worst&)sel; break; } return os; } Lớp thực thi giải thuật (Solver) Đưa ra và duy trì các thông tin có liên quan tới trạng thái tìm kiếm trong suốt quá trình thực hiện. có thể nói đây là lớp tổng hợp, được gọi trực tiếp từ chương trình chính, nó sử dụng thành quả xây dựng được của các lớp trình bày phía trên và là lớp trung gian giữa các lớp, thủ tục ta xây dựng phục vụ cho quá trình tiến hoá với chương trình thực thi với các bài toán cụ thể. Dưới đây là các hàm chính trong lớp thực thi giải thuật Trong đó : StartUp() : Khởi tạo quần thể, khởi tạo giá trị cho các biến trạng thái tiến hoá, các tham số cho quần thể trước khi bắt đầu một quá trình tiến hoá mới. Cập nhật các biến kiểm soát quá trình chạy của cả bài toán. DoStep() : Thực hiện các công việc trong một bước tiến hoá của quần thể, cập nhật lại các tham số của quần thể sau một bước tiến hoá Run () : là thủ tục thực hiện toàn bộ quá trình tìm kiếm của bài toán dựa vào các thông tin về bài toán, về các tham số, các điều kiện đầu vào được đọc vào từ 2 file là file cấu hình và file bài toán. Có hai lớp kế thừa từ lớp Solver Lớp Solver_Seq : Chứa thủ tục run() để giải quyết bài toán một cách tuần tự Lớp Solver_Lan : Chứa thủ tục run để giải quyết bài toán một cách song song trên môi trường mạng LAN. Với tham số truyền vào của hàm chính là các tên máy tham gia vào quá trình tính toán. Người sử dụng muốn thực hiện theo phương thức nào (song song hay tuần tự) thì tạo ra một đối tượng tương ứng sau đó gọi tới thủ tục run . 2. Khung thuật toán tuần tự 2.1 Solver_Seq: void Solver_Seq::StartUp // Khởi tạo quần thể, khởi tạo giá trị cho các biến trạng thái tiến hoá, các tham số cho quần thể trước khi bắt đầu một quá trình tiến hoá mới. Cập nhật các biến kiểm soát quá trình chạy của cả bài toán. void Solver_Seq::StartUp(const Population& pop) { // Khởi tạo những biến trạng thái trong thử nghiệm hiện tại. // Bắt đầu những giá trị trong quần thể hiện tại. // refresh trạng thái với những giá trị này. RefreshState(); RefreshCfgState(); _stat.update(*this); _userstat.update(*this); if (display_state()) show_state(); } void Solver_Seq::DoStep() // Thực hiện các công việc trong một bước tiến hoá của quần thể, cập nhật lại các tham số của quần thể sau một bước tiến hoá. { // Tăng bước lặp hiện tại lên 1 current_iteration(current_iteration()+1); current_population.evolution(); current_evaluations(current_population.evaluations()); // gets current interesting values in the current population // Bắt đầu những giá trị trong quần thể hiện tại. best_cost=current_population.best_cost(); best_solution=current_population.best_solution(); worst_cost=curren