Luận Văn So sánh các giải thuật song song Metaheuristic trong việc tìm kiếm lời giải gần tối ưu của bài tóan

So sánh các giải thuật song song Metaheuristic trong việc tìm kiếm lời giải gần tối ưu của bài tóan TSP

Tổng quan

Bài viết này so sánh hiệu quả của một vài giải thuật metaheuristic trong việc giải bài toán người du lịch. Các mô hình song song hóa dựa trên MPI được sử dụng để đánh giá cho các giải thuật GA (gentetic algorithm) ,SA (simulated annealing), ACO ( Ant Colony Optimization). Các kết quả đánh giá dựa trên hiệu quả song song hóa của các mô hình song song cho cùng 1 giải thuật và giữa các giải thuật khác nhau.

Keyword : parallel metaheuristic , gentetic algorithm , simulated annealing, ant colony optimization , MPI , TSP , speedup.

Giới thiệu chung

Mục đích của bài toán tối ưu tổ hợp là tìm lời giải tốt nhất trong các lời giải có thể và không gian tìm kiếm lời giải của bài toán là rời rạc .Nhiều bài toán tối ưu tổ hợp có độ phức tạp tính toán cao và được phân lọai thuộc lớp NP khó .Việc tìm ra lời giải tối ưu cho các bài toán này cho các hệ thống song song lớn nhất cũng không thể hoàn thành được trong giới hạn thời gian cho phép vì vậy các kỹ thuật heuristic cho việc giải các bài toán tổ hợp theo hướng xấp xỉ đã được phát triển để tìm ra các lời giải gần tối ưu (hay xấp xỉ )trong giới hạn thời gian cho phép. Bài toán người du lịch (TSP) là một bài toán cổ điển thuộc lớp NP được nghiên cứu sâu trong lĩnh vực tối ưu tổ hợp.

Metaheuristic là một cách gọi chung cho các giải thuật heuristic trong việc giải quyết các bài toán tổ hợp khó. Metaheuristic bao gồm những chiến lược khác nhau trong việc khám phá không gian tìm kiếm bằng cách sử dụng những phương thức khác nhau và phải đạt được sự cân bằng giữa tính đa dạng và chuyên sâu của không gian tìm kiếm. Một cài đặt thành công của metaheuristic trong một bài toán tổ hợp phải cân bằng giữa sự khai thác được kinh nghiệm thu thập được trong quá trình tìm kiếm để xác định được những vùng với những lời giải có chất lượng cao gần tối ưu. Những ví dụ của metaheuristic bao gồm giải thuật luyện thép (SA) , giải thuật di truyền (GA) , giải thuật đàn kiến (ACO) , Giải thuật đàn kiến là metaheuristic dùng chiến lược của kiến trong thế giới thực để giải bài toán tối ưu. SA xuất phát từ phương thức xác suất và kỹ thuật luyện bao gồm việc nung và điều khiển làm nguội các kim loại để đạt được trạng thái năng lượng nhỏ nhất .Trong khi đó giải thuật di truyền dựa trên ý tưởng từ cơ chế di truyền trong sinh học và tiến trình tiến hóa trong cộng đồng các cá thể của 1 lòai.

Với độ phức tạp tính toán cao của các bài toán tối ưu tổ hợp cũng như đòi hỏi về mặt thời gian , việc giải các bài toán này yêu cầu cần phải có những cài đặt song song hóa hiệu quả của các giải thuật để giải quyết chúng. Song song hóa các giải thuật metaheuristic phải đạt được 2 yêu cầu : đa dạng hóa để khám phá được nhiều vùng trong không gian tìm kiếm và tăng tốc độ tìm kiếm . Nhiều mô hình song song hoái đã được đề xuất cho nhiều metaheuristic. ACO và GA đều là các cách tiếp cận dựa trên tập cá thể và vì vậy khá tự nhiên cho việc xử lý song song . Tuy nhiên SA thì vốn đã mang tính tuần tự và rất chậm cho các bài toán với không gian tìm kiếm lớn nhưng vẫn có một vài kỹ thuật song song hóa có thể được áp dụng để tăng tốc độ tìm kiếm.

Bài viết này so sánh hiệu quả song song hóa của các mô hình song song cho một vài giải thuật metaheuristic cho việc tìm kiếm lời giản gần tối ưu của bài tóan TSP. Các mô hình song song được đề xuất cho giải thuật đàn kiến, luyện thép và giải thuật di truyền. Mô hình thực nghiệm dùng MPI và một vài bài toán trong thư viện TSPLIB.



Contents

Tổng quan 1

Giới thiệu chung 1

1. Các kiến thức cơ bản 9

1.1 Các khái niệm cơ bản về đồ thị 9

Định nghĩa đồ thị 9

1.1.1. Các thuật ngữ cơ bản 11

1.1.2. Đường đi, chu trình và đồ thị liên thông 12

1.1.3. Chu trình Euler 13

1.1.4. Chu trình Hamilton 14

1.1.5. Đồ thị có trọng số 15

1.1.6. Các cấu trúc dữ liệu biểu diễn đồ thị 15

1.2 Khái niệm về lớp các bài toán P và NP 16

1.2.1 Khái niệm các loại thời gian tính 16

1.2.2 Bằng chứng ngắn gọn dễ kiểm tra 17

1.2.3 Khái niệm quy dẫn 18

1.2.4 Lớp bài toán P. 18

1.2.5 Lớp bài toán NP. 18

1.2.6 Lớp bài toán Co-NP. 19

1.2.7 Lớp bài toán NP-đầy đủ (NP-Complete). 19

1.2.8 Lớp bài toán NP- khó (NP-Hard). 19

1.3 Các thuật toán xấp xỉ 21

1.4 Bài toán tối ưu hóa tổ hợp (Combinatorial optimization) 22

 Bài toán tối ưu hóa tổ hợp tĩnh (Static Combinatorial optimization): 22

 Bài toán tối ưu hóa tổ hợp động (Dynamic Combinatorial optimization): 22

2. Bài toán người du lịch 23

2.1 Giới thiệu bài toán 23

2.2 Lịch sử bài toán TSP 24

2.3 Mô tả bài toán TSP 25

2.4 Phân loại bài toán 25

 Đối xứng và bất đối xứng 25

 Với khoảng cách là metric 26

 Với khoảng cách không là metric 26

2.5 Các giải thuật giải bài toán TSP 27

 Các giải thuật để tìm lời giải chính xác 27

 Heuristic và các giải thuật xấp xỉ 28

3. Giao thức truyền gói tin(MPI) và các vấn đề song song hóa 30

3.1 Kiến trúc máy tính song song 30

3.2 Phân tách bài toán 30

3.3 Phân tách dữ liệu 30

3.4 Phân tách công việc 31

3.5 Song song hóa dữ liệu và mô hình truyền tin 31

3.6 Tối ưu chương trình song song 31

3.7 Phân chia công việc 32

3.8 Tối thiểu hóa trao đổi dữ liệu 32

3.9 Giảm chồng chéo giữa trao đổi dữ liệu và tính toán: 32

3.10 MPI 32

3.11 Lịch sử phát triển MPI 33

3.12 Mục đích của MPI 33

3.13 Các đặc tính cơ bản của một chương trình MPI 34

4. Giải thuật di truyền và di truyền song song 35

4.1 Giới thiệu về giải thuật di truyền 35

4.1.1 Lịch sử phát triển: 35

4.2 Các khái niệm cơ bản 37

4.2.1 Cá thể, nhiễm sắc thể 37

4.2.2 Quần thể 37

4.2.3 Các toán tử di truyền 37

4.3 Mô hình giải thuật di truyền 38

4.4 Các tham số của GA 39

Xác suất lai ghép 39

Xác suất đột biến 39

Kích thước quần thể 39

4.5 Các cách mã hoá NST 40

Mã hoá nhị phân 40

Mã hoá hoán vị 40

Mã hoá theo giá trị 41

4.6 Khởi tạo quần thể ban đầu 41

Hàm tính độ thích nghi 41

Cơ chế lựa chọn 41

Lựa chọn tỷ lệ 42

Lựa chọn xếp hạng 42

Lựa chọn theo cơ chế lấy mẫu ngẫu nhiên 42

Lựa chọn tranh đấu 43

4.7 Các toán tử di truyền (GA operators) 43

Mã hoá nhị phân 43

Mã hoá hoán vị 44

Mã hoá theo giá trị 44

4.8 Chiến lược nạp lại quần thể 45

Nạp lại hoàn toàn 45

Nạp lại ngẫu nhiên 45

Nạp lại theo mô hình cá thể ưu tú 45

4.9 GA song song 46

4.9.1 Giới thiệu 46

4.9.2 Các giải thuật GA song song 46

4.9.3 Mô hình GA song song đa quần thể phân tán 49

5. Thuật toán bầy kiến và bầy kiến song song 53

5.1 Sơ đồ chung của thuật toán bầy kiến 53

5.1.1 Giới thiệu chung về thuật toán bầy kiến 53

5.1.2 Nội dung thuật toán 59

5.2 Các sơ đồ thuật toán 63

5.2.1 Thuật toán Ant System (AS) 63

5.2.2 Thuật toán Ant Colony System(ACS) 65

5.2.3 Thuật toán Max–Min Ant System(MMAS) 67

5.2.4 Thuật toán Rank-Based Ant System(RBAS) 68

5.2.5 Thuật toán Best-Worst Ant System(BWAS) 69

5.3 Thuật toán đàn kiến song song 71

5.4 Giới thiệu giải thuật luyện thép 73

5.5 Sơ đồ giải thuật 73

5.6 Giải thuật luyện thép song song 75

5.6.1 Song song bằng chia nhỏ dữ liệu 75

5.6.2 Mô hình chạy nhiều lần 75

5.6.3 Các bước di chuyển song song 76