Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 1
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
KHOA KHOA HỌC MÁY TÍNH
TIẾU LUẬN MÔN HỌC
THUẬT TOÁN VÀ PHƯƠNG PHÁP GIẢI QUYẾT VẤN ĐỀ:
THUẬT TOÁN TỐI ƯU HÓA ĐÀN KIẾN VÀ BÀI
TOÁN NGƯỜI ĐƯA THƯ
Giảng viên hướng dẫn: PGS TS. ĐỖ VĂN NHƠN
Học viên thực hiện: LÊ DUY ĐẮC NHÂN
MSHV: CH1301045
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 2
TP. Hồ Chí Minh, tháng 01 năm 2014
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 3
LỜI CẢM ƠN
Em xin bày tỏ lòng biết ơn sâu sắc đến PGS TS. Đỗ Văn Nhơn, trường Đại học Công
Nghệ Thông Tin, ĐHQG TP.HCM đã tận tình hướng dẫn, cung cấp kiến thức, truyền đạt
những kinh nghiệm quí báu giúp em hoàn thành tốt bài thu hoạch này.
Xin cám ơn cha, mẹ, các anh, chị em trong gia đình đã hỗ trợ, lo lắng và động viên.
Đồng thời, xin cám ơn tất cả các bạn lớp cao học khóa 08 đã ủng hộ, giúp đỡ tôi trong
quá trình thực hiện bài tiểu luận này.
Dù đã có nhiều cố gắng nhưng chắc chắn sẽ không tránh khỏi những thiếu sót, em
rất mong nhận được sự đóng góp ý kiến của các Thầy giáo, Cô giáo và các bạn để đề tài
này được hoàn thiện hơn.
Em xin chân thành cảm ơn!
Tp Hồ Chí Minh, tháng 01 năm 2014
Học viên
Lê Duy Đắc Nhân
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Hiện nay có rất nhiều bài báo, luận văn, cũng như các công trình nghiên cứu đề cập
đến vấn đề tối ưu tổ hợp. Nhiều phương pháp mới mẻ đã được đưa ra và đạt hiệu quả
cao. Tuy nhiên phần lớn các bài toán tối ưu tổ hợp được giải từ trước tới nay đều là các
bài toán tĩnh. So với bài toán tĩnh thì bài toán động phức tạp hơn và ứng dụng của nó
trong thực tế là nhiều hơn. Chẳng hạn các ứng dụng trong định tuyến các gói tin trên
mạng internet, trong các tổng đài điện thoại. Một trong những cách tiếp cận có hiệu
quả đối với bài toán tối ưu tổ hợp tĩnh đó là phương pháp tối ưu hóa đàn kiến (Ant
Colony Optimization- ACO). ACO là một phương pháp metaheuristic mới và đang được
nhiều người quan tâm. Thuật toán ACO đầu tiên (1991) đã mang lại nhiều ý tưởng và
cảm hứng với mục đích cải tiến các thuật toán ACO để có thể áp dụng nó cho nhiều bài
toán khác nhau.
Luận văn này trình bày một cách khái quát về các thuật toán ACO và kiểm chứng
một phương pháp áp dụng ACO việc giải quyết bài toán người đưa thư một dạng bài
toán tối ưu tổ hợp động. Bài toán Người Đưa Thư thực chất là tên gọi khác của bài
toán người chào hàng (Travelling Salesman Problem - TSP) nổi tiếng.
1.2 Ý nghĩa
Qua việc thực hiện bài tiểu luận, giúp cho tác giả hiểu rõ hơn về về bài toán “Người
đưa thư” và các phương pháp tiếp cận giải bài toán “Người đưa thư”, qua đó có sự so
sánh đánh giá các thuật toán.
Tìm hiểu sâu về thuật toán đàn kiến và các biến thể, ứng dụng vào giải bài toán
“Người đưa thư” nh8a2m có những cải tiến trong các buốc của thuật giải đàn kiến với
bài toán cụ thể như biểu diễn tìm đường đi, các xây dựng các hàm đánh giá
TSP có một vài ứng dụng thậm chí trong dạng thức nguyên thuỷ của nó như lập kế
hoạch , logistic , và sản xuất các microchip. Thay đổi đi chút ít nó xuất hiện như một bài
toán con trong rất nhiều lĩnh vực như việc phân tích gen trong sinh học. Trong những ứng
dụng này, khái niệm thành phố có thể thay đổi thành khách hàng, các điểm hàn trên bảng
mạch, các mảnh DNA trong gen, và khái niệm khoảng cách có thể biểu diễn bởi thời gian
du lịch hay giá thành , hay giống như sự so sánh giữa các mảnh DNA với nhau. Trong
nhiều ứng dụng, các hạn chế truyền thống như giới hạn tài nguyên hay giới hạn thời gian
thậm chí còn làm cho bài toán trở nên khó hơn
Nó nhanh chóng trở thành bài toán khó thách thức toàn thế giới bởi độ phức tạp
thuật toán tăng theo hàm số mũ (trong chuyên ngành thuật toán người ta còn gọi
chúng là những bài toán NP-khó). Người ta bắt đầu thử và công bố các kết quả giải
bài toán này trên máy tính từ năm 1954 (49 đỉnh), cho đến năm 2004 bài toán giải
được với số đỉnh lên tới 24.978, và dự báo sẽ còn tiếp tục tăng cao nữa.
2.2 Bài toán Người đưa thư
2.2.1 Giới thiệu bài toán
3
4 Hình 1
TSP có thể được mô hình như một đồ thị , các đỉnh của đồ thị tương ứng với các thành
phố và các cạnh thì tương ứng với đường nối giữa các thành phố, chiều dài của một
cạnh tương ứng với khoang cách giữa 2 thành phố. Một đường đi trong bài toán TSP là
một chu trình Hamilton trên đồ thị và một lời giải tối ưu của bài toán là chu trình
Hamilton ngắn nhất.
Thường thì đồ thị là đồ thị đầy đủ , vì vậy mọi cặp cạnh đều được nối bởi các cạnh.
Đây là bước đơn giản hóa bài toán vì việc tìm chu trình Hamilton trong một đồ thị đầy
đủ là dễ. Các bài toán mà không phải 2 thành phố nào cũng được nối với nhau có thể
được chuyển đổi thành đồ thị đầy đủ bằng cách thêm những cạnh có độ dài lớn giữa
cách thành phố này , những cạnh sẽ không xuất hiện trong chu trình tối ưu.
Bài toán TSP có thể phát biểu dưới dạng đồ thị như sau: Cho G = (N, A,) là đồ thị có
hướng đầy đủ có trọng số, trong đó N là tập hợp của n = |N| nút (thành phố) , A =
{(i,j)| (i,j) є VxV} là tập tất cả các cung của đồ thị. Mỗi cung (i, j) được gán một trọng
số dij để biểu diễn khoảng cách giữa 2 thành phố i và j. Bài toán TSP trở thành bài
toán tìm chu trình Hamilton có độ dài ngắn nhất trên đồ thị G. Ta cần phân biệt hai
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 8
loại TSP, symmetric TSP có khoảng cách giữa các thành phố không phụ thuộc vào
hướng dij = dji với mọi thành phố i, j và asymmetric TSP – ATSP tồn tại ít nhất một
cặp cạnh sao cho dij ≠ dji. Đối với đồ thị không đối xứng có (n-1)! đường đi chấp
nhận được còn đối với đồ thị đối xứng có (n-1)!/2 đường đi có khả năng. Khi n lớn
đường đi.
Giả sử tại thời điếm ban đầu có 2 con kiến ra đi tìm thức ăn. Vì ban đầu chưa có
pheromone nên chung chọn 2 hướng đi khác nhau một cách ngẫu nhiên. Một hướng có
đường đi đến nguồn thức ăn dài hơn hướng kia. Trong giai đoạn đầu các con kiến đi
sau sẽ cảm nhận thấy nồng độ pheromone của cả 2 hướng là như nhau nên cũng chọn
đi theo một trong 2 hướng một cách ngẫu nhiên. Tuy nhiên đương đi ngắn hơn làm cho
khoảng cách di chuyển từ tổ đến nguồn thức ăn rồi quay trở lại của mỗi con kiến theo
đường đo cũng ngắn hơn và do đó mật độ di chuyển qua lại của đàn kiến tại mỗi vị trí
của con đường ngắn sẽ cao hơn con đường dài. Do mật độ qua lại lớn hơn dẫn đến kết
quả là nồng độ pheromone trên con đường ngắn càng ngày càng cao hơn con đường
dài. Kết quả là đàn kiến ngày càng từ bỏ con đường dài và đi theo con đường ngắn.
Đến một lúc nào đó sẽ không còn con kiến nào đi theo con đường dài nữa mà tất cả
đều đi theo con đường ngắn.
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 10
Thuật toán ACO lấy ý tưởng từ việc kiếm thức ăn của đàn kiến ngoài thực tế để
giải quyết các bài toán tố ưu tổ hợp. Chúng dựa trên cơ sở một đàn kiến nhân tạo,
chúng được tính toán tìm kiếm thức ăn nhờ mùi lạ nhân tạo
Các thuật toán kiến lần đầu tiên được giới thiệu bởi Dorigo và các cộng sự như là
cách tiếp cận đa tác tử tới các vấn đề về tối ưu tổ hợp khó, như bài toán người du lịch
(TSP), bài toán người đưa thư. Hiện nay số lượng các ứng dụng càng ngày càng tăng
và các nhà khoa học đã ứng dụng nó vào rất nhiều các vấn đề tối ưu rời rạc. Các ứng
dụng gần đây có thể kể đến như các bài toán lập lịch, tô màu đồ thị, định hướng trong
mạng truyền thông, v.v…
3.1.2 Giới thiệu về thuật toán
Sau đây là ví dụ về luồng đi của đàn kiến thực tế
a. Kiến đi theo đường thẳng giữa A và E
b. Khi có chướng ngại vật kiến sẽ chọn hướng đi, có hai hướng với khả năng kiến sẽ
chọn là như nhau.
c. Trên đường ngắn hơn thì nhiều mùi (pheromone) hơn
phương thức tìm kiếm thích hợp cho một tập các vấn đề khác nhau. Hay nói cách
khác, một siêu tìm kiếm ( meta-heuristic) có thể coi là một phương thức tìm kiếm đa
năng.
ACO là một meta-heuristic, trong đó một tập các con kiến nhân tạo phối hợp tìm
kiếm các giải pháp tốt cho các vấn đề về tối ưu rời rạc. Sự phối hợp là yếu tố cối lõi
của các thuật toán ACO. Các con kiến nhân tạo liên lạc với nhau thông qua trung gian
mà ta thường gọi là mùi.
Các thuật toán ACO được sử dụng để giải quyết các vấn đề về tối ưu tổ hợp tĩnh và
động. Các vấn đề tĩnh là các vấn đề mà ở đó các đặc tính của vấn đề là không thay đổi
trong suốt quá trình giải quyết vấn đề. Còn các vấn đề động thì ngược lại là một hàm
các tham số mà giá trị của nó là động hay thay đổi trong quá trình giải quyết vấn đề, ví
dụ bài toán người đưa thư là một vấn đề dynamic problem.
3.1.3 Sơ đồ chung thuật toán đàn kiế
Procedure ACO
Initial();
While (!ĐK dừng) do
ConstructSolutions();
LocalSearch(); /*Tuỳ ý, có thể có hoặc không
UpdateTrails();
End;
End;
trong đó:
ĐK dừng (tức là điều kiện dừng) là điều kiện đạt được khi thuật toán ở trạng thái
kết thúc. Với bài toán người đưa thư thì ĐK dừng là điều kiện đạt được khi số vòng
lặp của thuật toán = số vòng lặp lớn nhất do người dùng tự định nghĩa hoặc là tất cả
đàn kiến đều đi theo một đường (tức là đường đi ngắn nhất).
ConstrucSolutions() là hàm xây dựng một giải pháp có thể theo phương pháp siêu
tìm kiếm(meta-heuristic), với bài toán người đưa thư thì đó là hàm xây dựng chu trình
cho mỗi kiến .
UpdateTrails() là hàm cập nhật mùi cho hành trình mà kiến đã đi qua.
Từ việc nghiên cứu cơ chế hoạt động của đàn kiến tự nhiên đã cho ra đời thuật toán
bầy kiến. Một cách không chính thức có thể nói thuật toán bầy kiến là một bầy kiến
nhân tạo để giải bài toán đưa ra.
Hệ thống Ant Colony – Thuật toán bầy kiến: Là một đàn kiến nhân tạo
(Artificial Ants) mô phỏng các hoạt động của đàn kiến tự nhiên. Tất nhiên là có một số
thay đổi, điều chỉnh so với đàn kiến tự nhiên để tăng tính hiệu quả của thuật toán.
Trong đó hoạt động chính của các con kiến nhân tạo là tìm đường đi dựa vào lượng
thông tin Pheromone đã để lại trên mỗi đoạn đường. Chi tiết về hoạt động của đàn kiến
nhân tạo:
Bài toán cần giải sẽ được đưa về dạng một đồ thị đầy đủ với các ràng buộc của bài
toán được thể hiện bằng các công thức toán học. Việc giải bài toán đặt ta có sẽ đưa về
là tìm một đường đi (hoặc tập các đỉnh) thỏa mãn các ràng buộc của bài toán. Các
nguyên tắc sau được đưa ra:
Thông tin pheromone được tính toán và đặt trên mỗi đoạn đường.
Nút ban đầu cho đường đi của mỗi con kiến được chọn một cách ngẫu nhiên.
Đường đi được lựa chọn dựa trên các nguyên tắc sau:
Dựa vào thông tin pheromone có trên các đoạn đường để tính xác suất
của các đoạn tiếp theo được chọn vào làm đường đi của con kiến.
Xác suất lớn hơn cho đoạn đường đi có nhiều lượng pheromone được đặt
hơn. Và các đường đi có lượng thông tin pheromone bé sẽ có xác suất được
chọn thấp hơn.
Con kiến tiếp tục việc tìm đường đi cho tới khi hoàn thành một đường đi của nó
(thỏa mãn điều kiện dừng của con kiến).
Một đường đi hoàn chỉnh được gọi là một lời giải (solution) cho bài toán đặt ra.
Các lời giải sẽ được phân tích, so sánh và đánh giá để tìm phương án tối ưu nhất
có thể. Đó là lời giải tối ưu của bài toán.
Sau khi con tất cả kiến trong đàn hoàn thành lời giải của nó thì sẽ tiến hành cập
nhật thông tin pheromone cho các cung. Số lượng của pheromone sẽ được tính
toán và điều chỉnh để tìm được phương án tối ưu tốt hơn.
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
6 pheromone_evaporation ( )
7 daemon_actions ( ) {optional}
8 end schedule_activities
9 end while
10 end Procedure
1 Procedure ants_generation_and_activity ( )
2 repeat in parallel for k=1 to m (number_of_ants)
3 new_ant (k)
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 16
4 end repeat in parallel
5 end Procedure
1 Procedure new_ant (ant_id)
2 initialize_ant (ant_id)
3 L = update_ant_memory ( )
4 While (current_state target_state)
5 P = compute_transition_probabilities (A , L , )
6 next_state = apply_ant_decision_policy (P , )
7 move_to_next_state (next_state)
If (on_line_step-by-step-pheromone_update)
8 deposit_pheromone_on_the_visited_edge ( )
end if
9 L = update-internal_state ( )
10 end while
if (online_delayed_pheromone_update)
11 for each visited edge
12 deposit_pheromone_on_the_visited_edge ( )
13 end for
end if
14 release_ant_resources (ant_id)
(online delayed pheromone update). Đây là mô hình cho kết quả tốt nhất và
được coi như là thuật toán AS.
Như vậy theo mô hình của AS-cycle thì pheromone sẽ cập nhật khi tất cả con kiến
hoàn thành lời giải của mình.Việc cập nhật pheromone được tiến hành như sau:
Đầu tiên tất cả pheromone trên các cung sẽ được giảm đi bởi một hằng số
(pheromone evaporation).
Với ρ trong khoảng (0,1) là tốc độ bay hơi của pherromone.
Tiếp theo mỗi con kiến trong đàn sẽ đặt thêm một lượng thông tin pheromone,
lượng pheromone này là hàm của chất lượng lời giải mà con kiến xây dựng.
Trong đó:
Ban đầu AS không sử dụng daemon action, tuy nhiên sẽ càng tốt hơn nếu thêm
vào đó một thủ tục tìm kiếm cục bộ để làm tăng chất lượng của lời giải. Còn phương
trình để xác định nút tiếp theo trong quá trình xây dựng lời giải của con kiến như sau:
Tóm tắt về thuật toán này như sau:
1 Procedure new_ant (ant_id)
2 k = ant_id ; r = generate_initial_state ;
3
4 while (current-state target_state)
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 18
5 for each s (r) do
6 next_state = apply_ant_decision_policy (P , )
7 r = next_state ;
8
9
10 end while
Trong đó φ là một tham số để giảm pheromone thứ hai sau ρ. Còn được chọn là
một tham số rất bé (như là ngưỡng dưới của pheromone).
Tóm tắt về thuật toán này như sau:
1 Procedure new_ant (ant_id)
2 k = ant_id ; r = generate_initial_state ;
3
4 while (current-state target_state)
5 for each do compute
6 q = generate_random_value_in_[0 , 1]
If ( )
Next_state = max )
else
for each do
next_state = apply_ant_decision_policy (P , )
end if
7 r = next_state ;
8
9
10 end while
11
12 release_ant_resources (ant_id)
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 20
13 end Procedure.
Và thủ tục cập nhật:
1 Procedure daemon_actions
2 for each do local_search ( ) {optional}
3 best_solution ( )
trong tính toán.
Cách chọn cận dưới , thông thường người ta chọn để thỏa mãn theo tỷ lệ
giữa cận trên và cận dưới / = 2n.
Do đó tính = / 2n. Tỉ lệ này phải chọn không nên quá cao, bởi vì khi đó
xác suất để chọn đường đi có mức độ Pheromone thấp là quá nhỏ. Mặt khác nếu
chọn tỉ lệ này quá lớn thì xác suất chọn đường đi co Pheromone cao là gần với
xác suất chọn đường đi có mức độ Pheromone thấp.
Khi khởi tạo thông tin pheromone cho các thành phần thì tất cả nhận giá trị
lớn nhất có thể của Pheromone là nhằm tăng cường việc khai phá không
gian tìm kiếm. Một chú ý trong hệ thống MMAS là khi xảy ra hội tụ cục bộ thì
có cơ chế khởi tạo lại thông tin pheromone cho các nút và giá trị để khởi tạo lại
là .
Hàm cập nhật Daemon action của thuật toán MMAS như sau:
1 Procedure daemon_actions
2 for each do local_search ( )
3 best_solution ( )
4 if (best ( , ))
5 =
6 end if
7 = decision ( , )
8 for each edge do
9
10 if (
11 end for
12 if (stagnation_condition)
13 for each edge do
14 end if
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 22
15 end Procedure.
3 rank in decreasing order of solution
quality into
4 if (best ( , ))
5 =
6 end if
7 for to do
8 for each edge do
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 23
9
10 end for
11 end for
12 for each edge do
13
14 end for
15 end Procedure
3.2.5 Thuật toán Best-Worst Ant System(BWAS)
Thuật toán được đưa ra bởi Cordon vào năm 1999. Thuật toán này bao gồm một
thuật toán mở rộng khác của AS là MMAS (về luật di chuyển và việc bay hơi của
pheromone). Bên cạnh đó trong thuật toán này còn quan tâm tới của việc tối ưu cục bộ
một cách hệ thống để nâng cao chất lượng lời giải của con kiến. Trong thuật toán
BWAS có 3 daemon action thêm vào gồm có:
Đầu tiên, áp dụng luật có tên best-worst pheromone update để tăng cường
pheromone trên các đoạn đường đi qua bởi lời giải tốt nhất toàn cục (global best
solution). Thêm vào đó luật này sẽ phạt những cạnh của lời giải tồi nhất trong
lần lặp S
current-worst
.
Áp dụng Pheromone trail mutation để đi theo các hướng khác nhau trong
quá trình tìm kiếm.
26 if (stagnation_condition)
27 for each do
28 end if
29 end Procedure
Mục này chỉ đưa ra 5 mô hình thuật toán ACO phát triển từ hệ thống Ant System.
Nhưng đó chỉ là một số các dạng tiêu biểu của thuật toán ACO, còn tồn tại rất nhiều
các biến thể khác. Và trong đồ án sẽ áp dụng thuật toán theo mô hình hệ thống
MMAS để giải bài toán CPMP. Mô hình thuật toán MMAS là một trong các thuật toán
hiệu quả nhất của các thuật toán bầy kiến.
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân
Tiểu luận Thuật toán & PPGQVD: TT Tối Ưu Hóa Đàn Kiến và Người Đưa Thư Trang 25
CHƯƠNG 4: ỨNG DỤNG THUẬT GIẢI ĐÀN KIẾN VÀO BÀI TOÁN
NGƯỜI ĐƯA THƯ
4.1 Phát biểu bài toán
Một người đưa thư đi giao thư qua n địa điểm T
1
T
n
. Xuất phát từ bưu điện, người
đưa thư muốn giao thư qua tất cả địa điểm cần giao, mỗi địa điểm chỉ đi đúng một lần
rồi trở lại bưu điện xuất phát. Gọi C
ij
là chi phí từ T
I
đến T
j
. Tìm hành trình với tổng chi
phí là nhỏ nhất
Định nghĩa bài toán:
- Một tập các địa điểm giao thư: V={V
p
ij
k
: xác suất con kiến k lựa chọn cạnh (i, j)
α: hệ số điều chỉnh ảnh hưởng của t
ij
η
ij
: thông tin heuristic giúp đánh giá chính xác sự lựa chọn của kiến đi từ đỉnh I đến
đỉnh j
β: hệ số điều chỉnh ảnh hường η
ij
N
j
k
: tập các đỉnh láng giềng của I mà con kiến k chưa đi qua
∆ t
ij
: là lượng pheromone mà con kiền k đặt lên cạnh mà nó đã đi qua
NC: là số bước lặp của thuật toán
S
k
: đường đi của kiến k (tập các đỉnh mà kiến k đi qua)
GVHD: PGS TS. Đỗ Văn Nhơn Học viên: Lê Duy Đắc Nhân