Luận Văn Xây dựng công cụ Editor Workflow cho ứng dụng tìm kiếm dạng Meta - Heuristic

TÓM TẮT LUẬN VĂN
Thư viện parallel meta-heuristics dùng để giải bài toán dạng meta-heuristics dựa vào mô hình workflow. Để cải thiện lời giải tìm được tốt hơn, mô hình workflow sẽ được cải tiến với mô hình workflow Petri-net có khả năng chọn lời giải ở từng bước tính toán, mô hình workflow có lặp vòng và nhánh song song.
Để người dùng dễ dàng sử dụng mô hình workflow của thư viện, ta cần xây dựng công cụ trực quan giúp người dùng vẽ mô hình Petri-net (Workflow) đồng thời tự động sinh mã cho workflow từ ngôn ngữ mô tả workflow.
Ngôn ngữ mô tả workflow cho thư viện được xây dựng bằng ngôn ngữ XML. Nó được xây dựng đơn giản, linh động, người dùng có thể tùy biến thiết kế lại tên các tham số mô tả cho các giải thuật tìm kiếm mà không cần thay đổi bộ phân tích cú pháp.
Công cụ editor sẽ xây dựng ra ngôn ngữ mô tả workflow. Bộ phân tích cú pháp của thư viện meta-heuristics sẽ phân tích và thi hành workflow đó đồng thời sẽ trả kết quả để hiển thị trên công cụ editor. Người dùng có thể dùng công cụ trực quan với những loại bài toán tìm kiếm và chiến thuật tìm kiếm khác nhau.

MỤC LỤC
Đề mục Trang
Trang bìa 1
Lời cảm ơn .3
Tóm tắt .4
Mục lục 5
Danh sách hình vẽ 9

CHƯƠNG 1. GIỚI THIỆU 10
1.1. Sơ lược về bài toán Travelling Salesman Problem 10
1.2. Giải quyết bài toán TSP 11
1.3. Tính chất song song của thư viện parallel meta-heuristic 12
1.4. Vấn đề đặt ra cho Workflow 13
1.5. Sơ lược về các công cụ editor workflow và nhận xét 14
1.5.1. Java WorkflowTooling (JWT) 14
1.5.2. JGraph 17
1.5.3. Nhận xét các công cụ editor workflow và hướng phát triển của luận văn 19
1.6. Cấu trúc của luận văn 20
CHƯƠNG 2. META-HEURISTIC 21
2.1. Khái niệm Heuristic 21
2.2. Khái niệm Meta-Heuristic 22
2.3. Một số giải thuật Heuristic tiêu biểu 23
2.3.1. Hill Climbing (HC) 23
2.3.2. Simulate Annealing (SA) 23
2.3.3. Tabu Search (TS) 24
2.4. Sự song song hóa các Meta-heuristics 25
2.5. Kiến trúc và tính năng của Framework Meta-heuristics 26
2.5.1. Kiến trúc của Framework 26
2.5.2. Các tính năng của Framework 27
CHƯƠNG 3. THƯ VIỆN META-HEURISTIC 28
3.1. Giới thiệu về thư viện Meta-heuristic 28
3.2. Thiết kế của thư viện 29
3.2.1. Cách sử dụng thư viện 29
3.2.2. Quá trình thực thi tìm kiếm 29
3.2.3. Vấn đề đóng gói dữ liệu 30
CHƯƠNG 4. BÀI TOÁN TSP VÀ KHÔNG GIAN NGHIỆM 32
4.1. Giới thiệu bài toán TSP 32
4.2. Không gian nghiệm tìm kiếm 33
4.3. Các giải thuật heuristic hỗ trợ giải bài toán TSP 34
4.3.1. Nearest Neighbor 34
4.3.2. 2-opt 35
4.3.3. 3-opt 36
4.3.4. Lin-Kernighan 37
CHƯƠNG 5. WORKFLOW VÀ NGÔN NGỮ MÔ TẢ WORKFLOW 38
5.1. Workflow 38
5.1.1. Khái niệm workflow 38
5.1.2. Hệ thống quản lý workflow 38
5.2. Directed Acyclic Graph (DAG) 39
5.3. Một số mô hình workflow 40
5.3.1. Business Process Execution Language (BPEL) 40
5.3.2. Grid Workflow Description Language (GWorkflowDL) 41
5.4. Mô hình Petri-net 41
5.4.1. Tổng quan về Petri-net 41
5.4.2. Đặc tả Petri-net 42
5.4.3. Một số mô hình Petri-net 42
5.4.4. Một số mô hình workflow 43
5.4.4.1. Các mô hình điều khiển dòng cơ bản 44
5.4.4.2. Mô hình rẽ nhánh và đồng bộ cấp cao 45
5.5. Ngôn ngữ mô tả workflow 46
5.5.1. Lý do dùng XML làm ngôn ngữ mô tả workflow 46
5.5.2. Cú pháp của ngôn ngữ mô tả workflow tìm kiếm 46
5.5.2.1. Element Workflow 47
5.5.2.2. Element Place 48
5.5.2.3. Element Argument 48
5.5.2.4. Element Transition 50
5.5.2.5. Element Edge 52
CHƯƠNG 6. THIẾT KẾ CÔNG CỤ EDITOR 53
6.1. Tổng quan về thư viện Swing 53
6.1.1. Giới thiệu 53
6.1.2. Các thành phần của thư viện Swing 54
6.2. Sơ lược về giao diện và sơ đồ hoạt động của Workflow Editor 55
6.2.1. Giao diện của Workflow Editor 55
6.2.2. Sơ đồ hoạt động của Workflow Editor 56
6.3. Giới thiệu các chức năng của Workflow Editor 58
6.3.1. Các chức năng cơ bản 58
6.3.1.1. Tạo workflow mới 58
6.3.1.2. Lưu workflow 58
6.3.1.3. Mở workflow 60
6.3.1.4. Edit một workflow 61
6.3.1.5. Các tác vụ liên quan tới node 62
6.3.2. Các chức năng nâng cao 65
6.3.2.1. Export 65
6.3.2.2. Giám sát và điều khiển quá trình thực thi của workflow 66
6.4. Hướng thiết kế, các sơ đồ mô tả cấu trúc và hoạt động của Workflow Editor 66
6.4.1. Hướng thiết kế của chương trình 66
6.4.2. Mô hình cơ bản của Workflow Editor 67
6.4.3. Mô hình các tác vụ quản lý workflow 68
6.4.4. Mô hình các tác vụ liên quan đến node 70
6.5. Sơ đồ một số chức năng cơ bản của Workflow Editor 71
6.5.1. Tạo một workflow mới 71
6.5.2. Xóa một workflow 72
6.5.3. Tạo một node mới 73
6.5.4. Tạo Edge giữa các node 74
6.5.5. Di chuyển một node 75
6.5.6. Xóa một node 76
6.5.7. Chỉnh sửa thông tin của node 77
CHƯƠNG 7. CHỨC NĂNG NÂNG CAO CỦA WORKFLOW EDITOR 79
7.1. Mô hình chính của Workflow Editor kèm theo thư viện parallel meta-heuristic 79
7.2. Kiểm tra tính liên thông của đồ thị workflow 80
7.2.1. Sơ lược về đồ thị liên thông 80
7.2.2. Kiểm tra tính liên thông của đồ thị workflow 81
7.3. Vấn đề về generate và parse file XML 81
7.3.1. Các tính năng của thư viện parallel meta-heuristic 81
7.3.1.1. Kiến trúc của hệ thống sinh mã 82
7.3.1.2. Bộ phân tích cú pháp XML 82
7.3.2. Bổ sung tính năng generate và parse file XML dựa vào ngôn ngữ Java 83
7.3.2.1. Lý do cho việc generate và parse file XML dùng Java 83
7.3.2.2. Các lớp dùng cho việc generate XML 84
7.3.2.3. Các lớp dùng cho việc parse file XML trên ngôn ngữ Java 86
7.4. Vấn đề kết nối giữa Workflow Editor và thư viện parallel meta-heuristic 89
CHƯƠNG 8. THỬ NGHIỆM CHƯƠNG TRÌNH 91
8.1. Các bước chạy chương trình 91
8.2. Kết quả quá trình thực thi 91
CHƯƠNG 9. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 95
9.1. Kết luận 95
9.2. Hướng phát triển 95
TÀI LIỆU THAM KHẢO 97




DANH SÁCH HÌNH VẼ
Hình 1.1: Bài toán TSP thực tế 10
Hình 1.2: Quá trình song song hóa 12
Hình 1.3: Giao diện của JWT 15
Hình 1.4: Mô hình BPMN 16
Hình 1.5: JGraph MVC 17
Hình 1.6: Giao diện Jgraph 18
Hình 2.1: Kiến trúc Framework 26
Hình 4.1. Ví dụ bài toán TSP 32
Hình 4.2: Không gian nghiệm tổng quát 33
Hình 4.3: Minh họa Nearest Neighbor Algorithm 34
Hình 4.4: Minh họa 2-opt 35
Hình 4.5: Minh họa 3-opt 36
Hình 5.1: Directed Acyclic Graph 40
Hình 5.2: Mô hình workflow được mô tả bằng BPEL 40
Hình 5.3: Mô hình workflow được mô tả bằng GworkflowDL 41
Hình 5.4: Mô hình workflow được mô tả bằng Petri-net 42
Hình 5.5: Các thành phần của mô hình Petri-net 42
Hình 5.6: Các mô hình workflow được thể hiện bằng Petri-net 43
Hình 6.1: Năm thành phần của thư viện JFC 53
Hình 6.2: Mối liên hệ giữa Swing, AWT, JDK 1.1 và JDK 1.2 trở về sau 54
Hình 6.3: Mô hình phân cấp của thư viện Swing và một vài component của nó 55
Hình 6.4: Giao diện của Workflow Editor trên Linux 56
Hình 6.5: Use Case các tác vụ của Workflow Editor 56
Bảng 6.1: Danh sách các tác vụ của Workflow Editor 57
Hình 6.6: Tạo mới workflow bằng cách click vào nút New 58
Hình 6.7: Tạo mới workflow bằng cách chọn menu File -> New Workflow 58
Hình 6.8: Save workflow bằng cách click vào nút Save 59
Hình 6.9: Save workflow bằng cách chọn menu File -> Save hoặc Save As 59
Hình 6.10: Khung Save As cho phép người dùng chọn vị trí để lưu file XML 60
Hình 6.11: Mở workflow bằng cách click vào nút Open 60
Hình 6.12: Mở workflow bằng cách chọn menu File -> Open 61
Hình 6.13: Khung Open cho phép người dùng chọn file XML cần mở 61
Hình 6.14: Xóa một workflow bằng cách chọn Delete 62
Hình 6.15: Cửa sổ cho phép nhập các thuộc tính của workflow 62
Hình 6.16: Chọn loại node để vẽ 63
Hình 6.17: Right Click lên node sẽ hiện lên các tác vụ thực hiện trên node đó 63
Hình 6.18: Hai mũi tên trên ToolBar dùng cho việc vẽ Edge 64
Hình 6.19: Ví dụ về các thông số của node SA 65
Hình 6.20: Chỉ cần đưa con trỏ vào node thì information popup sẽ tự động hiện ra 65
Hình 6.21: Các button dùng điều khiển quá trình thực thi của workflow 66
Hình 6.22: Mô hình top-down của Workflow Editor 67
Hình 6.23: Mô hình UML tổng quát của Workflow Editor 68
Hình 6.24: Mô hình UML các tác vụ quản lý workflow 69
Hình 6.25: Mô hình UML các tác vụ liên quan đến node 70
Hình 6.26: Sơ đồ tuần tự các hoạt động khi tạo một workflow 72
Hình 6.27: Sơ đồ tuần tự các hoạt động khi xóa một workflow 73
Hình 6.28: Sơ đồ tuần tự các hoạt động khi tạo một node 74
Hình 6.29: Sơ đồ tuần tự các hoạt động khi tạo một Edge 75
Hình 6.30: Sơ đồ tuần tự các hoạt động khi di chuyển một node 76
Hình 6.31: Sơ đồ tuần tự các hoạt động khi xóa một node 77
Hình 6.32: Sơ đồ tuần tự các hoạt động khi chỉnh sửa thông tin của node 78
Hình 7.1. Mô hình chính của Worklfow Editor và thư viện parallel meta-heuristic 79
Hình 7.2: Hai đồ thị liên thông 80
Hình 7.3: Đồ thị liên thông mạnh (trái) và đồ thị liên thông yếu (phải) 81
Hình 7.4: Mô tả kiến trúc của hệ thống sinh mã 82
Hình 7.5: Dạng element phân cấp trong ngôn ngữ mô tả workflow 83
Hình 7.6: Cấu trúc chi tiết bên trong bộ phân tích cú pháp 83
Hình 7.7: Sơ đồ tuần tự các hoạt động khi tạo file XML 86
Hình 7.8: Sơ đồ quá trình parse một tài liệu XML sang cấu trúc DOM 87
Hình 7.9: Giao thức TCP giữa Workflow Editor và thư viện 89
Hình 8.1: Hộp thoại yêu cầu nhập vào đường dẫn đến thư viện 91
Hình 8.2: Chạy workflow không có transition 92
Hình 8.3: Kết quả của hình 8.2 92
Hình 8.4: Chạy workflow có transition 93
Hình 8.5: Kết quả của hình 8.4 93
Hình 8.6: Stop một workflow 94
Hình 8.7: Kết quả của hình 8.6 94
Hình 9.1. Cải tiến Workflow Editor 96