Đề tài: : PHƯƠNG PHÁP CHC SONG SONG

I. Tìm hiểu chung về thuật toán di truyềnGiả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ỏngtheo sự tiến hoá và đấu tranh sinhh tồn của sinh vật trong tự nhiên theo thuyếttiến hoá muôn loài của Darwin.Mục tiêu của giải thuật
Nội dung trích xuất từ tài liệu:
Đề tài:: PHƯƠNG PHÁP CHC 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ườita đã 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ộcsố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, ko gian tìmkiế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ápkhá 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 CHCsử 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ờigian, độ 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áchsử dụng thuật toán để giải quyết một số bài toán khác. Nhóm tác giả xin chân thành cảm ơn sự giúp đỡ tận tình của thầy giáo ĐỗTrung Kiên đã giúp cho nhóm trong quá trình thực hiện. 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ôngrực rỡ. Hà Nội, tháng 04 năm 2008. Nhóm tác giả. 1 MỤC LỤC[2]. Sushil J. Louis, A Genetic Algorithm.........................................................................24[3]. Helmut Pekari and Robert Clariso, MALLBA: instantiating SAT and MAXCUT.. ..24[4]. M.B Menai Département d’informatique, ‘Extremal Optimization’ for Max - SAT. 24 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 I. 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ỏngtheo sự tiến hoá và đấu tranh sinhh tồn của sinh vật trong tự nhiên theo thuy ếttiế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ảitố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ủaquá 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úckhoẻ 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ântạ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ị… 2 Tổng quan về phương pháp CHC II. 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, Heterogeneousrecombination, and Cat – aclysmic mutation. Giải thuật CHC được phát triển bởiEshelman (1991) được trình bày như hình vẽ: 3 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 đ ể sinhra con chung. Giải thuật sau đó sẽ chọn tập cá thể tốt nhất từ cha mẹ đ ược kếthợ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ệtthí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à đại diện chocrossover 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. 4 CHC không được sử dụng các toán tử độ ...