sử dụng thuật toán luyện kim song song giải quyết bài toán maxsat.doc

SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT

Chương I: ................................................................................................................ 3

Tổng quan thuật toán mô phỏng luyện kim (Simulated Annealing = SA) ........ 3

Sự hội tụ ................................................................................................................................................ 9

Điều kiện dừng ...................................................................................................................................... 9

Chương II: ............................................................................................................... 9

Xây dựng khung thuật toán SA .............................................................................. 9

Hàm Main_Seq ........................................................................................................................................ 22

Kết quả thực nghiệm ................................................................................................................................... 31

1. Kết quả tuần tự ................................................................................................................................... 31

2. Kết quả song song ............................................................................................................................... 31

TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 1

Solution Space:

Không gian lời giải

Initial State:

Trạng thái ban đầu

Local Minimum:

Tối ưu địa phương

Global Minimum:

Tối ưu toàn cục

SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT

BÁO CÁO KHOA HỌC

ĐỂ TÀI:

THUẬT TOÁN LUYỆN KIM SONG SONG

(Parallel Simulated Annealing Algorithms)

GIẢI QUYẾT BÀI TOÁN MAX-SAT

MỞ ĐẦU

- Nhiều bài toán tối ưu chưa có thuật toán chính xác để giải quyết cho nên cần có một

thuật toán gần đúng để tìm lời giải gần tối ưu.

- Không gian lời giải cần tìm là rất lớn nếu một máy tính tìm kiếm sẽ rất lâu nên cần

nhiều máy giải quyết và các máy phải thực hiện đồng thời. Điều này có thể thực hiện dễ

dàng nếu các máy tính tính toán song song. Vì vậy việc tìm hiểu về các thuật toán song

song là cần thiết và mang tính khả thi đối với các bài toán tối ưu

- Để rút ngắn thời gian lập trình chúng ta cần xây dựng khung thuật toán giúp giải quyết

các bài toán khác nhanh chóng hơn.

- Mục đích của đề tài này là sử dụng thuật toán luyện kim song song để giải quyết bài

toán tối ưu MAXSAT. Đề tài bao gồm các nhiệm vụ sau:

• Nghiên cứu lý thuyết về thuật toán luyện kim

• Xây dựng khung thuật toán chung cho các bài toán sử dụng thuật toán luyện kim

• Áp dụng khung thuật toán luyện kim cho bài toán MAXSAT

• Cài đặt bài toán MAXSAT và đưa ra kết quả thực nghiệm trên cả chương trình

tuần tự và chương trình song song.

• Từ đó sử dụng khung thuật toán luyện kim để giải quyết các bài toán tối ưu khác

trong thực tế như: Bài toán người du lịch, bài toán khôi phục ảnh, thiết kế mạch

IC, bài toán sắp xếp thời khoá biểu cho trường đại học…

TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 2

Solution Space:

Không gian lời giải

Initial State:

Trạng thái ban đầu

Local Minimum:

Tối ưu địa phương

Global Minimum:

Tối ưu toàn cục

SỬ DỤNG THUẬT TOÁN LUYỆN KIM SONG SONG GIẢI QUYẾT BÀI TOÁN MAXSAT

Chương I:

Tổng quan thuật toán mô phỏng luyện kim

(Simulated Annealing = SA)

I. Giới thiệu chung về thuật toán SA

SA là một thuật toán tìm kiếm xác suất di truyền, là phương pháp tối ưu hoá có

thể áp dụng để tìm kiếm tối ưu hoá toàn cục của hàm chi phí và tránh tối ưu hoá

địa phương bằng việc chấp nhận một lời giải tồi hơn với một xác suất phụ thuộc

nhiệt độ T.

 Sơ đồ:

Sơ đồ thể hiện trong một không gian lời giải thuật toán luyện kim sẽ tìm đến tối ưu

toàn cục với bước nhảy từ tối ưu địa phương

 Tiền thân của SA là thuật toán Monte Carlo năm 1953 của nhóm Metropolis.

Thuật toán SA được đề xuất bởi S. Kirk _ partrick năm 1982 và được công bố

trước công chúng năm 1983.

 SA có nguồn gốc từ cơ học hệ thống. SA thực thi đơn giản và tương tự quá trình

luyện kim vật lý. Trong luyện kim vật lý kim loại được đốt nóng tới nhiệt độ cao

và làm lạnh từ từ để nó kết tinh ở cấu hình năng lượng thấp (tăng kích thước của

tinh thể và làm giảm những khuyết điểm của chúng). Nếu việc làm lạnh không

TRƯƠNG THỊ THÚY LAN(K54A) – KIỀU TUẤN DŨNG(K55B) - NGUYỄN MINH CHÂU K55B 3

Solution Space:

Không gian lời giải

Initial State:

Trạng thái ban đầu

Local Minimum:

Tối ưu địa phương

Global Minimum:

Tối ưu toàn cục