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

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, ko 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.

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ông

rự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.........................................................................23

[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

I. 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ị…

2