ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA
KHOA KHOA HỌC & KỸ THUẬT MÁY TÍNH
LUẬN VĂN TỐT NGHIỆP ĐẠI HỌC
XÂY DỰNG CÔNG CỤ EDITOR
WORKFLOW CHO ỨNG DỤNG TÌM KIẾM
DẠNG META-HEURISTIC
HỘI ĐỒNG: …………………………………
GVHD: TRẦN VĂN HOÀI
GVPB: LÊ NGỌC MINH
o0o
SVTH 1: DƯƠNG HỮU LỘC (50601371)
SVTH 2: NGUYỄN VĂN HIỆU (50600745)
TP. HỒ CHÍ MINH, THÁNG 1 NĂM 2011
1
2
LỜI CÁM ƠN
Để hoàn thành đề tài tốt nghiệp này, chúng em đã nhận được sự giúp đỡ tận tình về
chuyên môn cũng như sự hỗ trợ về mọi mặt của nhiều thầy, cô trường đại học Bách Khoa
thành phố Hồ Chí Minh, Khoa Khoa Học và Kỹ Thuật Máy Tính, gia đình và đặc biệt là
thầy Trần Văn Hoài. Chúng em xin chân thành cảm ơn:
Thầy Trần Văn Hoài, người đã tận tình giúp đỡ chúng em trong quá trình làm
luận văn.
Tập thể cán bộ Khoa Khoa Học và Kỹ Thuật Máy Tính đã tạo điều kiện thuận lợi
và giúp đỡ chúng em trong suốt thời gian làm luận văn.
Và cuối cùng, xin cảm ơn gia đình đã hỗ trợ, động viên về mọi mặt trong suốt thời
gian học tập và hoàn thành luận văn này.
Tp HCM, tháng 1 năm 2011
Dương Hữu Lộc
Nguyễn Văn Hiệu
3

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.
4
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) 24
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
5
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
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 82
7.3.1. Các tính năng của thư viện parallel meta-heuristic 82

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 84
7.3.2.1. Lý do cho việc generate và parse file XML dùng Java 84
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 87
7.4. Vấn đề kết nối giữa Workflow Editor và thư viện parallel meta-heuristic 90
CHƯƠNG 8. THỬ NGHIỆM CHƯƠNG TRÌNH 92
8.1. Các bước chạy chương trình 92
8.2. Kết quả quá trình thực thi 92
CHƯƠNG 9. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 96
9.1. Kết luận 96
9.2. Hướng phát triển 96
TÀI LIỆU THAM KHẢO 98
7
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
8
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 81
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 88
Hình 7.9: Giao thức TCP giữa Workflow Editor và thư viện 90
Hình 8.1: Hộp thoại yêu cầu nhập vào đường dẫn đến thư viện 92
Hình 8.2: Chạy workflow không có transition 93
Hình 8.3: Kết quả của hình 8.2 93
Hình 8.4: Chạy workflow có transition 94
Hình 8.5: Kết quả của hình 8.4 94
Hình 8.6: Stop một workflow 95
Hình 8.7: Kết quả của hình 8.6 95
Hình 9.1. Cải tiến Workflow Editor 97
9
Chương 1. Giới thiệu
CHƯƠNG 1. GIỚI THIỆU
1.1. Sơ lược về bài toán Travelling Salesman Problem
Ngày nay trong cuộc sống, có những công việc đòi hỏi con người phải thực hiện sao cho đạt

được lợi ích càng nhiều càng tốt với một chi phí nhỏ có thể chấp nhận được. Ví dụ như công việc
chở hàng giữa các thành phố đã biết trước. Người chở hàng phải tính toán sao cho phải đi qua các
thành phố đúng một lần và phải quay về thành phố đầu tiên (nơi khởi hành). Việc quyết định sẽ
đi qua thành phố nào trước sẽ ước tính được chi phí nguyên liệu cần thiết trong cuộc hành trình.
Mỗi cách lựa chọn sẽ tính được các chi phí nguyên liệu khác nhau. Chi phí nguyên liệu nào là
nhỏ nhất trong các cách lựa chọn mà người này biết được sẽ được chọn để thực hiện cuộc hành
trình.
Hình 1.1: Bài toán TSP thực tế
10
Chương 1. Giới thiệu
Các yêu cầu trên được gọi là bài toán Travelling Salesman Problem (TSP). Hình 1.1 minh họa
bài toán TSP thực tế. Để giải quyết bài toán trên ngoài việc dự đoán và lựa chọn của người giao
hàng, chúng ta có thể sử dụng máy tính để giải quyết. Trên thực tế bài toán TSP rất phức tạp vì
cần phải giải quyết rất nhiều thành phố (độ phức tạp của bài toán tỷ lệ thuận với số thành phố cần
đi qua). Dĩ nhiên là con người không thể nào giải quyết được, còn máy tính có thể giải xấp xỉ để
cho ra nghiệm gần với nghiệm tối ưu bởi vì nó cần nhiều không gian tìm kiếm và thời gian tính
toán.
1.2. Giải quyết bài toán TSP
Nhiều giải pháp được đưa ra để giải quyết loại bài toán này. Meta-heuristics là một phương
pháp đã giải quyết được bài toán này bằng cách tìm những lời giải xấp xỉ trong một khoảng thời
gian có thể chấp nhận được. Tuy nhiên chất lượng của lời giải phụ thuộc vào nhiều yếu tố khác
nhau như không gian và chiến thuật tìm kiếm. Chúng ta có thể cải thiện lời giải bằng cách mở
rộng không gian tìm kiếm, chạy với nhiều giải thuật tìm kiếm khác nhau. Với sự hỗ trợ nhiều
máy tính chạy song song và giải thuật tìm kiếm tốt, lời giải có thể tốt hơn. Để triển khai việc tính
toán trên nhiều máy, cách tiếp cận của chúng ta là sử dụng tính toán lưới (Grid computing).
Để triển khai phương pháp meta-heuristics, chúng ta sẽ dùng thư viện parallel meta-heuristics.
Như đã biết, mô hình lập trình tính toán lưới là khá phức tạp và khó tiếp cận, người phát triển ứng
dụng thường không quen với mô hình này. Để giải quyết vấn đề này, thư viện parallel meta-
heuristics đã cung cấp framework giúp những người phát triển ứng dụng có thể viết các chương
trình tìm kiếm dạng meta-heuristics trên lưới dễ dàng. Framework cung cấp một số giải thuật tìm

kiếm heuristic phổ biến như: giải thuật leo đồi, giải thuật luyện kim, giải thuật Tabu search và cơ
chế giúp cho việc triển khai ứng dụng trên grid dễ dàng. Ngoài ra, framework của thư viện cũng
cung cấp mô hình workflow cho người dùng để viết những ứng dụng riêng. Framework của thư
viện hỗ trợ hai mô hình workflow tuần tự và song song cho người sử dụng dễ dàng phát triển ứng
dụng của mình. Workflow tuần tự dùng để thử nghiệm và debug chương trình, và sau khi chương
11
Chương 1. Giới thiệu
trình chạy ổn định trên mô hình workflow tuần tự, ta có thể tiến hành chạy trên các hệ thống phân
bổ với mô hình workflow song song.
1.3. Tính chất song song của thư viện parallel meta-heuristic
Ngày nay với sự phát triển mạnh mẽ của phần cứng, chúng ta có thể dùng nhiều máy tính
tham gia vào tính toán lưới để giải quyết bài toán TSP hoặc các bài toán khác như CSP Do ưu
điểm có nhiều processor, các máy tính có thể giải quyết các công việc độc lập với nhau. Vì vậy
chúng ta mới có thể tận dụng được sức mạnh của của các hệ thống đó. Đó chính là lý do lập trình
song song ra đời.
Quá trình song song hóa gồm ba giai đoạn chính:
• Phân chia chương trình thành các công việc con (Sub-task decomposition).
• Phân tích sự phụ thuộc (Dependence analysis).
• Định thời các công việc (Task scheduling).
Hình 1.2: Quá trình song song hóa
12
Chương 1. Giới thiệu
Hình 1.2 minh họa quá trình song song hóa. Sự song song hóa là quá trình biến đổi các
chương trình tuần tự thành chương trình song song có khả năng tận dụng tối đa sức mạnh của hệ
thống. Thư viện parallel meta-heuristic cũng được phát triển theo hướng song song hóa. Giả sử ta
có một tập hợp các giải thuật được chỉ định bởi một workflow, ta có một hệ thống gồm 2 máy có
thể thực thi một cách độc lập nhau.
Khi đó, thư viện parallel sẽ phân chia tập các giải thuật thành các tập con các giải thuật sao
cho thích hợp với kích thước chương trình, ngôn ngữ lập trình, kiến trúc của hệ thống máy tính…
ra thành các Task như trong hình trên. Giai đoạn này được gọi là Sub-taskdecomposition.

Giả sử tùy thuộc vào nội dung của workflow mà ta thấy Task A sẽ được thực thi đầu tiên, kế
đến là Task B,C và D đều phụ thuộc vào Task A nhưng chúng không phụ thuộc lẫn nhau. Giai
đoạn nhận biết các Task có phụ thuộc lẫn nhau hay không gọi là Dependence Analysis.
Kế đến là giai đoạn Task Scheduling dùng để định thời các Task trên và tìm được một biểu đồ
nhanh nhất có thể để thực thi chương trình. Các Task không phụ thuộc vào nhau được phân bố
trên 2 processor. Một Task chỉ có thể được thực thi trên một processor sau khi công việc trước
mà nó phụ thuộc được thực hiện. Còn lại các công việc không phụ thuộc nhau có thể tiến hành
song song trên mỗi processor. Nhờ đó có thể tiết kiệm được thời gian chạy của chương trình.
1.4. Vấn đề đặt ra cho Workflow
Do tính chất của bài toán TSP là phức tạp (hoặc các bài toán khác cũng có độ phức tạp không
kém) và do meta-heuristics không phải là dạng tìm kiếm chính xác. Do đó, các công việc tìm
kiếm ở những lần chạy khác nhau sẽ cho ra lời giải khác nhau, và người dùng phải thay đổi các
thông số của các giải thuật tìm kiếm để cho ra các kết quả khác. Việc chỉnh sửa và thi hành các
workflow được thực hiện thường xuyên và phải chỉnh sửa trong các đoạn code của chương trình
thực thi.
Vì vậy việc để có được một công cụ editor trực quan cho phép người dùng chỉnh sửa
workflow là rất cần thiết.
13
Chương 1. Giới thiệu
Luận văn này chúng ta sẽ nghiên cứu về việc tạo ra một công cụ editor cho phép người dùng
chỉnh sửa và giám sát quá trình thực thi của workflow dựa trên thư viện parallel meta-heuristices
có sẵn.
1.5. Sơ lược về các công cụ editor workflow và nhận xét
Hiện nay có khá nhiều công cụ editor là open source hoặc payed source. Chúng ta sẽ xem qua
một số loại tiêu biểu.
1.5.1. Java WorkflowTooling (JWT)
Workflow Editor (WE) là một bộ công cụ cho phép tạo, quản lý các workflow được tích hợp
trong Eclipse. Bộ công cụ này dùng giao diện sẵn có của Eclipse.
Trong hình 1.3, ta thấy có một vùng làm việc ở giữa và ba vùng làm việc ở xung quanh. Vùng
làm việc ngay giữa chính là nơi người dùng thao tác nhiều nhất.

14
Chương 1. Giới thiệu
Hình 1.3: Giao diện của JWT
JWT được phát triển dựa trên ngôn ngữ Java. Chương trình trên cho phép người dùng vẽ các
công việc (các node) và các đường liên kết giữa các công việc đó. Người dùng có thể thao tác
trên đồ thị workflow một cách trực quan bằng chuột, có thể di chuyển, thêm, sửa, xóa… trong
vùng làm việc chính giữa.
JWT sử dụng các biểu tượng trên workflow phù hợp cho việc tạo các quy trình (process) trong
doanh nghiệp, kiểm tra tính hợp lệ của các quy trình… Ví dụ JWT có thể cho phép người dùng vẽ
mô hình The Business Process Modeling Notation (BPMN) dùng trong doanh nghiệp.
15
Chương 1. Giới thiệu
Hình 1.4: Mô hình BPMN
Trong khuôn khổ của luận văn này, chúng ta sẽ dùng mô hình Petri-net cho việc giải bài toán
TSP (mô hình BPMN khá phức tạp chỉ thích hợp trong doanh nghiệp). Đi theo mô hình BPMN
JWT còn cung cấp định dạng file XML theo chuẩn BPMN.
Ngoài mô hình BPMN, JWT cũng hỗ trợ cho các mô hình khác cũng như các định dạng XML tương
ứng như STP-IM, XPDL, jPDL.
Trong khuôn khổ của luận văn này, chúng ta sẽ dùng XML theo định dạng DOM thích hợp với mô
hình Petri-net hơn.
Ngoài các tính năng trên, JWT còn có thêm chức năng Runtime đang trong giai đoạn phát
triển.
16
Chương 1. Giới thiệu
Chuẩn XML của BPMN
1.5.2. JGraph
JGraph là một công cụ được phát triển dựa trên thư viện Swing của Java. Nó được thiết kế
bằng cách dùng design patterns để cung cấp các hàm API mạnh mẽ, người sử dụng có thể hiển
thị, tương tác các đồ thị, hình vẽ và có khả năng tạo các ứng dụng dạng đồ thị với nhiều kiểu
khác nhau.

Hình 1.5: JGraph MVC
17
<xsd:element name="extension" type="tExtension"/>
<xsd:complexType name="tExtension">
<xsd:sequence>
<xsd:element ref="documentation" minOccurs="0" maxOccurs="unbounded"/>
</xsd:sequence>
<xsd:attribute name="definition" type="xsd:QName"/>
<xsd:attribute name="mustUnderstand" type="xsd:boolean" use="optional"/>
</xsd:complexType>
Chương 1. Giới thiệu
Vì JGraph là công cụ editor open source nên cho phép người dùng chỉnh sửa hay cải tiến lớp
chính Class JGraph. Hình 1.5 trình bày mô hình điều khiển hiển thị của JGraph (model-view-
controller pattern).
Hình 1.6: Giao diện Jgraph
Hình 1.6 trình bày giao diện của JGraph. Trên hình 1.6, ta thấy cũng có vùng làm việc chính ở
giữa và các vùng làm việc phụ ở xung quanh. Vùng làm việc chính cho phép người dùng chỉnh
sửa các node trong đồ thị, các vùng còn lại cho phép chỉnh sửa thông số của từng node hay cho
phép người dùng thao tác các đồ thị như thêm, xóa đồ thị.
Với JGraph, chúng ta có thể tạo ra các đồ thị như mô hình mạng viễn thông, biểu đồ dòng
chảy (flow charts), biểu đồ kiến trúc vi mạch, VLSI và CAD, biểu đồ quy trình của doanh
nghiệp… Ngoài ra JGraph cũng hỗ trợ XML.
18
Chương 1. Giới thiệu
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
Ngoài hai công cụ ở trên còn nhiều công cụ khác. Chúng ta nhận thấy chúng có chung các đặc
điểm như: tương tác trực quan với người dùng bằng cách cho phép người dùng chỉnh sửa đồ thị
workflow, cho phép xuất ra file XML theo chuẩn mà nhà phát triển quy định. Chúng cũng thích
hợp để giải quyết nhiều loại bài toán khác nhau cũng như tương thích với nhiều loại thư viện
khác nhau.

Tuy nhiên xét về đặc thù của luận văn, các mô hình đồ thị workflow phải giải quyết bài toán
TSP dùng thư viện paralell meta-heuristics. Ngoài ra, công cụ editor phải được phát triển sao cho
có thể chạy được nhiều thư việc khác cũng như chạy được nhiều bài toán khác nhau. Chúng ta
liệt kê những thách thức trong việc phát triển công cụ editor workflow như sau:
• Thiết kế phải đơn giản nhưng hiệu quả. Thiết kế sao cho công cụ editor phải dùng
được nhiều thư viện khác nhau (ngoài parallel meta-heuristics).
• Dùng ngôn ngữ lập trình Java vì ngôn ngữ này cung cấp các hàm API dùng để thiết kế
giao diện khá hiệu quả.
• Tập trung vào các giải thuật Hill Climbing, Simulated Annealing, Tabu Search. Đây là
các giải thuật mà thư viện parallel meta-heuristics đã cung cấp sẵn. Ngoài ra ta cũng có
thể phát triển các giải thuật trên cho việc tìm kiếm đạt hiệu quả cao hơn hoặc tự thiết
kế giải thuật khác cho bài toán TSP.
• Việc xuất ra file XML cũng phải tuân theo chuẩn mô hình DOM để thư viện xử lý.
• Tìm cách liên kết giữa 2 ngôn ngữ Java (phía giao diện) và POPC++ (phía thư viện) để
trong lúc vận hành, chúng ta có thể dừng việc thực thi ở bất kỳ lúc nào trên giao diện
đồ họa hay giám sát quá trình thực thi đồng thời hiển thị kết quả trên giao diện. Bằng
cách đó ta có thể liên kết giữa editor với các thư viện khác nhau.
Việc phát triển giao diện trực quan giúp cho người sử dụng có thể điều khiển workflow một
cách linh hoạt hơn, việc thử nghiệm và tìm kiếm các kết quả mong muốn từ bài toán TSP sẽ trở
nên đơn giản hơn. Chương trình cũng dùng được cho các thư viện hay giải quyết các bài toán
khác nhau.
19
Chương 1. Giới thiệu
1.6. Cấu trúc của luận văn
Cấu trúc của luận văn gồm có:
• Khái niệm về meta-heuristics và một số giải thuật meta-heuristices tiêu biểu.
• Sơ lược về kiến trúc framework của thư viện parallel meta-heuristics.
• Giới thiệu về bài toán TSP và không gian nghiệm.
• Khái niệm về workflow.
• Khái niệm về mô hình Petri-net cho workflow.

• Sơ đồ của hệ thống, sơ đồ thiết kế của chương trình editor.
• Giới thiệu công cụ Xerces2 Java dùng để sinh mã cho workflow.
• Giới thiệu về cơ chế Socket.
• Thử nghiệm chương trình.
• Kết luận.
20
Chương 2. Meta-Heuristic
CHƯƠNG 2. META-HEURISTIC
2.1. Khái niệm Heuristic
Heuristic theo cách hiểu đơn giản là tìm kiếm theo kinh nghiệm. Khi áp dụng heuristic thì bài
toán có khả năng loại bỏ những trường hợp không cần thiết. Có thể nói Heuristic là tri thức về bài
toán cụ thể được sử dụng để dẫn dắt quá trình tìm ra lời giải của giải thuật. Nhờ sự thêm vào các
heuristic mà giải thuật trở nên hữu hiệu hơn.
Giải thuật heuristic là giải thuật sử dụng thông tin hàm lượng giá heuristic để thực hiện việc
tìm kiếm. Hàm lượng giá dùng để thu gọn các không gian bài toán.
Bất kỳ thủ tục để tìm một giải pháp khả thi , với là một nghiệm của bài toán.
Hầu như chắc chắn với f được xem như hàm lượng giá.
Phần lớn các heuristic cổ điển có nhiều vòng lặp.
• miền lân cận, với là không gian nghiệm của bài toán.
• m(x): ứng dụng chuyển đổi, tùy thuộc vào từng giải thuật cụ thể mà ứng dụng chuyển
đổi sẽ khác nhau.
• trạng thái của bài toán sau khi di chuyển.
Các bước đơn giản của thuật toán heuristic:
1. Xác định và khởi tạo nghiệm ban đầu
2. k = k + 1
3. Sinh ra các trạng thái của bài toán, từ đó tìm được các nghiệm khác. Hay nói cách khác
tìm
4. Nếu trạng thái mới xấu hơn trạng thái cũ hay f( ) , ngừng
21
Chương 2. Meta-Heuristic

5. Ngược lại, chuyển trạng thái cũ thành trạng thái mới bằng cách dùng hàm m(x):
trở lại bước 2
2.2. Khái niệm Meta-Heuristic
Meta-heuristic là một phương pháp heuristic để giải quyết một lớp các vấn đề tính toán bằng
cách kết hợp các thủ tục hộp đen của người sử dụng (thường trong hộp đen cũng là các heuristic)
với hy vọng thu được nhiều hiệu quả hoặc nhiều thủ tục mạnh hơn. Cho nên meta-heuristic là loại
heuristic tổng quát có thể áp dụng cho nhiều lớp bài toán.
Meta-heuristics nói chung được áp dụng cho các vấn đề mà không có thuật toán hay heuristic
cụ thể nào thỏa mãn; hoặc khi không thể hiện thực như một phương pháp. Hầu hết sử dụng meta-
heuristic để nhắm vào các vấn đề tối ưu hóa tổ hợp (combinatorial optimization), nhưng tất nhiên
có thể xử lý bất kỳ vấn đề nào được đúc kết lại theo hình thức đó, chẳng hạn như giải quyết các
phương trình boolean.
Meta-heuristics được sử dụng trong nhiều lĩnh vực như: toán học, nghiên cứu các tác vụ,
trí tuệ nhân tạo.
Meta-heuristics còn được sử dụng trong rất nhiều ứng dụng như thiết kế, lập kế hoạch, điều
khiển các hệ thống và mạng phức tạp; quản lý, chỉ định, định thời và sử dụng tài nguyên; thiết kế
VLSI…
Đối với bài toán TSP, meta-heuristic là sự kết hợp giữa việc thực hiện các giải thuật heuristic
và sự thăm dò không gian lân cận của nghiệm hiện tại.
Ưu điểm của meta-heuristic:
• Tránh được tối ưu cục bộ.
• Tránh được lặp vòng.
• Không nhất thiết phải cải thiện trong mỗi lần lặp.
Các bước thực hiện của meta-heuristic:
1. Khởi tạo nghiệm ban đầu.
2. Lựa chọn vùng lân cận của nghiệm hiện tại.
22
Chương 2. Meta-Heuristic
3. Trong vùng lân cận lựa chọn vùng dự tuyển
4. Đánh giá di chuyển / thăm dò vùng lân cận

5. Thực hiện di chuyển
6. Đánh giá trạng thái, cập nhật các tham số tìm kiếm
7. Kiểm tra ngừng các yêu cầu: ngừng hoặc trở về bước 3 hoặc bước 2
2.3. Một số giải thuật Heuristic tiêu biểu
Heuristic bao gồm nhiều giải thuật như Hill Climbing, Simulate Annealing, Tabu Search,
Genetic Algorithms, Ant Systems… Trong khuôn khổ của luận văn này sẽ trình bày 3 giải thuật
mà thư viện parallel meta-heuristic hướng đến.
2.3.1. Hill Climbing (HC)
Đây là giải thuật tiêu biểu cho các giải thuật meta-heuristic. Giải thuật này dựa theo ý tưởng
của việc một người phải leo từ dưới mặt đất lên đến đỉnh cao nhất trong dãy các ngọn đồi mà
không nhìn thấy trước được đỉnh đó ở đâu. Giải thuật này sử dụng hàm lượng giá. Đối với giải
thuật leo đồi đơn giản, khi thử một trạng thái kề trạng thái hiện tại (trạng thái mới chưa được
duyệt qua), nếu hàm lượng giá được cải thiện thì bài toán sẽ chuyển đến trạng thái mới. Nói cách
khác hàm lượng giá là một cách để đưa tri thức cụ thể cho nhiệm vụ của bài toán vào trong quá
trình điều khiển.
Các bước cơ bản của giải thuật HC:
1. Lượng giá trạng thái khởi đầu.
2. Lặp cho đến khi đạt đến trạng thái mục tiêu hoặc không còn tác vụ để thử:
- Chọn một tác vụ để thử.
- Lượng giá trạng thái mới do tác vụ sinh ra.
- Nếu đó là trạng thái mục tiêu thì kết thúc.
Nếu trạng thái mới tốt hơn trạng thái hiện tại thì chuyển sang trạng thái mới.
23
Chương 2. Meta-Heuristic
2.3.2. Simulate Annealing (SA)
Do S. Kirkpatrick, C. D. Gelatt và M. P. Vecchi đưa ra vào 1983.
Giải thuật mô phỏng luyện kim là một kỹ thuật tìm kiếm ngẫu nhiên (stochastic search) mà tỏ
ra rất hữu hiệu cho những bài toán tối ưu hóa qui mô lớn. Trong kỹ thuật này, nhiệt độ là biến
được khởi tạo ở một giá trị cao và dần dần giảm dần xuống trong quá trình tìm kiếm. Tại những
trị nhiệt độ cao, các bước chuyển được chấp nhận một cách ngẫu nhiên bất luận chúng là bước

chuyển có cải thiện hàm chi phí của lời giải hay không. Khi nhiệt độ được giảm xuống, xác suất
để chấp nhận một lời giải có cải thiện sẽ tăng lên và xác suất để chấp nhận một lời giải không cải
thiện sẽ giảm xuống. Có một số cách thức giảm nhiệt độ dần xuống được dùng trong giải thuật
luyện kim, được gọi là lịch biểu làm nguội (cooling schedule).
Các bước cơ bản của giải thuật SA:
1. Lượng giá trạng thái khởi đầu.
2. Lặp cho đến khi đạt đến trạng thái mục tiêu hoặc không còn tác vụ để thử:
- Thiết lập giá trị T theo cách điều chỉnh nhiệt độ trong quá trình luyện kim.
- Chọn một tác vụ để thử.
- Lượng giá trạng thái mới do tác vụ sinh ra.
- Nếu đó là trạng thái mục tiêu thì kết thúc.
Nếu trạng thái mới tốt hơn trạng thái hiện tại thì chuyển sang trạng thái mới.
Nếu trạng thái mới xấu hơn trạng thái hiện tại thì chuyển sang trạng thái mới với
xác suất , trong đó ΔE là hiệu số của giá trị của trạng thái hiện tại và giá trị
của trạng thái mới.
2.3.3. Tabu Search (TS)
Tìm kiếm Tabu được đề xuất bởi Glover năm 1986. Phương pháp dò tìm trong không gian lời
giải bằng cách di chuyển từ một lời giải s tại lượt lặp t về một lời giải tốt nhất s’ trong tập con N*
của miền lân cận N(s). Vì s’ không nhất thiết cải thiện chi phí của s, một cơ chế được đặt ra để
ngăn chặn quá trình khỏi lặp vòng trên một chuỗi các lời giải. Một cách để tránh sự lặp vòng là
cấm quá trình tìm kiếm quay về những lời giải đã gặp rồi, nhưng làm như vậy đòi hỏi phải lưu trữ
24
Chương 2. Meta-Heuristic
khá nhiều thông tin. Thay vì làm thế, chỉ một vài thuộc tính của những lời giải đã gặp sẽ được lưu
trong danh sách Tabu (Tabu list) và bất kỳ lời giải nào sở hữu những thuộc tính này sẽ không
được xét đến trong lần lặp. Cơ chế này thường được gọi là bộ nhớ ngắn hạn và được gọi là kỳ
hạn Tabu.
Các bước cơ bản của giải thuật TS:
1. Lượng giá trạng thái khởi đầu.
2. Khởi tạo danh sách Tabu.

3. Lặp cho đến khi đạt đến trạng thái mục tiêu hoặc không còn tác vụ để thử:
- Chọn một tác vụ để thử.
- Lượng giá trạng thái mới do tác vụ sinh ra.
- Nếu đó là trạng thái mục tiêu thì kết thúc.
- Nếu trạng thái mới tốt hơn trạng thái hiện tại và không nằm trong danh sách Tabu
thì chuyển sang trạng thái mới.
- Lưu trạng thái mới vào danh sách Tabu.
2.4. Sự song song hóa các Meta-heuristics
Tối ưu hóa bài toán phụ thuộc vào không gian và chiến lược tìm kiếm bằng cách mở rộng
không gian tìm kiếm và chạy trên nhiều chiến lược tìm kiếm khác nhau. Tuy nhiên, điều đó có
thể dẫn tới việc tăng thời gian tìm kiếm.
Để giải quyết vấn đề này ta sử dụng mô hình tính toán song song. Mục tiêu chính là tăng khả
năng tính toán bằng cách chia nhỏ công việc ra cho nhiều process thực hiện. Chiến lược tìm kiếm
cho meta-heuristics có 3 loại:
• Loại 1: chiến lược này cố gắng song song hóa việc lượng giá các bước move trong
vòng lặp nhằm gia tăng thời gian tính toán.
• Loại 2: tiếp cận mục tiêu song song bằng cách phân chia ra tập biến xác định. Việc
phân chia này làm giảm không gian tìm kiếm nhưng cần nhiều bước lặp để tìm hết tất
cả các tập không gian.
25