Download miễn phí Đề tài Phương pháp CHC song song
MỤC LỤC
Chương I: Tổng quan về phương pháp CHC 3
I. Tìm hiểu chung về thuật toán di truyền 3
II. Tổng quan về phương pháp CHC 4
1. Khái niệm 4
2. Tư tưởng của thuật toán CHC 4
3. Sự Chọn lọc Elitist 6
4. Tránh sự giao phối gần 7
Chương II: Xây dựng khung thuật toán CHC 8
I. Thiết kế khung thuật toán CHC 9
1. Các lớp đòi hỏi (Requires) 10
• Lớp bài toán (Problem) 10
• Lớp lời giải (Solution) 10
• Lớp toán tử người sử dụng (Uer_Operator) 10
• Lớp kiểm tra điều kiện dừng (StopCondition) 10
2. Các lớp cung cấp (Provided) 11
• Lớp thiết lập tham số đầu vào (SetUpParams) 11
• Lớp quần thể (Population) 11
• Lớp lựa chọn (Selection) 12
• Lớp chỉ định toán tử sử dụng (Intra_Operator): 13
• Lớp định nghĩa giao diện toán tử (Inter_Operator) 13
• Lớp lai ghép (Crossover) 13
• Lớp thực thi giải thuật (Solver) 14
II. Khung thuật toán tuần tự 14
1. Hàm void Solver_Seq:
oStep() 14III. Khung thuật toán song song 16
Chương III. Sử dụng khung thuật toán giải quyết bài toán MAXSAT 17
I. Đọc file cấu hình 17
II. Sử dụng khung thuật toán giải quyết bai toán MAXSAT 18
III. Kết quả thực nghiệm 24
1. Kết quả tuần tự 24
2. Kết quả song song 24
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
ution) • Lớp toán tử người sử dụng (Uer_Operator) • Lớp kiểm tra điều kiện dừng (StopCondition) 2. Các lớp cung cấp (Provided) • Lớp thiết lập tham số đầu vào (SetUpParams) • Lớp quần thể (Population) • Lớp lựa chọn (Selection) • Lớp chỉ định toán tử sử dụng (Intra_Operator): • Lớp định nghĩa giao diện toán tử (Inter_Operator) • Lớp lai ghép (Crossover) • Lớp thực thi giải thuật (Solver) II. Khung thuật toán tuần tự 1. Hàm void Solver_Seq:oStep() III. Khung thuật toán song song Chương III. Sử dụng khung thuật toán giải quyết bài toán MAXSAT I. Đọc file cấu hình II. Sử dụng khung thuật toán giải quyết bai toán MAXSAT III. Kết quả thực nghiệm 1. Kết quả tuần tự 2. Kết quả song song Lời nói đầu
Những năm gần đây, cùng với sự phát triển của khoa học kỹ thuật, người ta đã giải quyết được nhiều bài toán hóc búa bằng máy tính. Nhưng bên cạnh đó, vẫn còn khá nhiều các bài toán vẫn chưa tìm được giải thuật phù hợp để giải nó, đó là các bài toán tối ưu, trí tuệ nhân tạo và các bài toán xuất phát từ thực tế cuộc sống như bài toán lập lịch, bài toán điều khiển Robot, bài toán người du lịch,... Đây là các bài toán có khá nhiều ràng buộc phức tạp, không rõ ràng, không gian tìm kiếm lớn. Do đó các phương pháp truyền thống như quay lui vét cạn, leo đồi, mô phỏng luyện thép, … tỏ ra ít hiệu quả, và người ta đã sử dụng một phương pháp khá tối ưu đó là phương pháp CHC và sử dụng trong mô hình song song.
Trong bài nghiên cứu này nhóm tác giả nghiên cứu về phương pháp CHC sử dụng mô hình song song để giải quyết bài toán MAXSAT. Chúng ta sẽ thấy được sự độ tối ưu khi sử dụng mô hình song song so với mô hình tuần tự về thời gian, độ thích nghi …
Trong tương lai nhóm sẽ tiếp tục phát triển đề tài nghiên cứu bằng cách sử dụng thuật toán để giải quyết một số bài toán khác.
Cuối cùng xin chúc hội nghị nghiên cứu khoa học của chúng ta thành công rực rỡ.
MỤC LỤC
BÁO CÁO KHOA HỌC
Đề tài:: PHƯƠNG PHÁP CHC SONG SONG
Chương I: Tổng quan về phương pháp CHC
Tìm hiểu chung về thuật toán di truyền
Giải thuật di truyền 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 hoá và đấu tranh sinhh tồn của sinh vật trong tự nhiên theo thuyết tiến hoá muôn loài của Darwin.
Mục tiêu của giải thuật di truyền: giải thuật di truyền không đưa ra lời giải tối ưu mà là đưa ra lời giải gần đúng (tương đối tối ưu).
Bản chất của thuật toán di truyền là bài toán tìm kiếm dựa theo qui luật của quá trình tiến hoá tự nhiên. Thuật toán di truyền kết hợp sự sống sót của cấu trúc khoẻ nhất trong số các cấu trúc biểu diễn các nhiễm sắc thể (NST) với 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 sử dụng các biểu diễn nhị phân kết hợp với sơ đồ để mô hình hoá sự chọn lọc, lai ghép và đột biến.
Ứng dụng của thuật toán di truyền:
+ Trong tin học: xây dựng chương trình tin học đặc biệt như trí tuệ nhân tạo để hướng dẫn người sử dụng trong lĩnh vực giáo dục, quản trị.
+ Trong các công việc khác: Ứng dụng giải bài toán sắp xếp thời khoá biểu, điều khiển robot, bài toán vận tải, bài toán đồ thị…
Tổng quan về phương pháp CHC
1. Khái niệm
CHC là giải thuật di truyền phi truyền thống kết hợp chiến lược chọn lọc (dựa trên những cá thể đơn lẻ tốt nhất) để đưa ra con lai tốt nhất khác với cả cha và mẹ.
2. Tư tưởng của thuật toán CHC
CHC là từ viết tắt của cross – generational selection, Heterogeneous recombination, and Cat – aclysmic mutation. Giải thuật CHC được phát triển bởi Eshelman (1991) được trình bày như hình vẽ:
CHC lựa chọn một trang của quần thể có kích cỡ µ (µ =50) nhưng thay vì chọn những cha mẹ tốt để tái kết hợp giống cách làm của giải thuật gi truyền, cha mẹ được chọn một cách ngẫu nhiên một cặp duy nhất và điều kiện để sinh ra con chung. Giải thuật sau đó sẽ chọn tập cá thể tốt nhất từ cha mẹ được kết hợp và quần thể con được sinh ra ở thế hệ tiếp theo. Vì vậy giải thuật CHC sẽ duy trì được quần thể tốt nhất mà được bắt gặp qua quá trình tìm kiếm.
Cha mẹ không được phép giao phối nếu như chúng không có sự khác biệt thích đáng như được xác định bởi ngưỡng giao phối liên tục giảm. Toán tử chéo (crossover) được sử dụng bởi CHC là toán tử HUX, với HUX là thay mặt cho crossover một nửa không đổi. Toán tử HUX đảm bảo chính xác một nửa của số bit khác nhau giữa cha mẹ được trao đổi để sản sinh ra con cái.
CHC không được sử dụng các toán tử đột biến trong trường hợp thông thường, và thực tế cùng với những quần thể nhỏ trong CHC và sự lựa chọn thế hệ giao làm cho quần thể được hội tụ nhanh chóng. Khi quần thể được hội tụ, CHC sẽ được khởi động lại từng phần bởi việc sao chép bởi thành viên tốt nhất của quần thể hiện tại sang một quần thể mới và sinh ra phần còn lại của quần thể mới với những phiên bản được biến đổi ồ ạt (35% của các bit) của thành viên tốt nhất của quần thể hiện tại.
3. Sự Chọn lọc Elitist
Trong suốt sự chọn lọc cho việc sinh sản thay vì sự thiên về chọn lọc C(t) cho việc sinh sản hơn vì lợi ích của những thành viên thực hiện tốt hơn trong quần thể cha mẹ P(t-1). Mỗi thành viên của P(t-1) được sao chép thành C(t) và được ghép đôi một cách ngẫu nhiên. (Nói cách khác, C(t) đồng nhất với P(t-1) ngoại trừ khi trật tự của các cấu trúc đã bị thay đổi). Mặt khác, trong suốt giai đoạn chọn lọc sinh tồn thay vì thay thế quần thể cha mẹ cũ P(t-1) bằng quần thể con C’(t) để hình thành P(t), thế hệ con mới được tạo ra phải được cạnh tranh với các thành viên của quần thể cha mẹ P(t-1) cho sự sinh tồn - ví dụ cạnh tranh chính là thế hệ lai. Cụ thể hơn, các thành viên của P(t-1) và C’(t) được hoà trộn và được xếp hạng theo sự thích hợp, và P(t) được tạo ra bằng việc chọn lọc M tốt nhất (trong đó M là kích thước quần thể), các thành viên của quần thể được hoà trộn. (Trong các trường hợp mà một thành viên của P(t-1) và một thành việc của C’(t) có sự thích hợp giống nhau, thành viên của P(t-1) được xếp hạng cao hơn). Ta sẽ gọi thủ tục giữ lại các thành viên được xếp hạng tốt nhất của các quần thể con và quần thể cha mẹ được xáo trộn là sự chọn lọc elitist bởi vì nó đảm bảo rằng các cá thể M tốt nhất sẽ luôn sống sót.
Một vài sự chọn lọc sinh tồn thiên về tính thích hợp sử dụng của giải thuật di truyền khác - Whitley’s GENITOR (1989), Syswerda’s Steady State GA (SSSGA(1989), và Ackley’s Iterated Generic Search(IGS) (1987). CHC khác với tất cả ba loại giải thuật này trong đó việc cạnh tranh sinh tồn là thế hệ lai-thế hệ con chỉ thay thế một thành viên của quần thể cha mẹ nếu nó tốt hơn. Hơn nữa, không giống như ba giải thuât này, CHC vận hành trong các chu kỳ thế hệ với rất nhiều bạn đời chứ không phải chỉ một bạn đời cho mỗi chu kỳ. Sự tin cậy duy nhất đối với sự chọn lọc sinh tồn cho sự thiên lệch của nó vì lợi ích của những cá nhân thực thi tốt hơn hơn và cũng phân biệt nó với GENITOR và SSSGA nhưng không phải là IGS. Cu