BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------HUỲNH QUANG ĐỆ

HUỲNH QUANG ĐỆ

NGÀNH CÔNG NGHỆ THÔNG TIN

ĐÁNH GIÁ HIỆU QUẢ CỦA GIẢI THUẬT DI TRUYỀN GIẢI
BÀI TOÁN CÂY KHUNG TRUYỀN THÔNG TỐI ƯU VỚI CÁC
KỸ THUẬT MÃ HÓA CÂY

LUẬN VĂN THẠC SĨ KHOA HỌC
Chuyên ngành Công nghệ thông tin

KHOÁ 2009
Hà Nội – Năm 2012


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------Huỳnh Quang Đệ

ĐÁNH GIÁ HIỆU QUẢ CỦA GIẢI THUẬT DI TRUYỀN GIẢI BÀI TOÁN
CÂY KHUNG TRUYỀN THÔNG TỐI ƯU VỚI CÁC KỸ THUẬT MÃ HÓA
CÂY

Chuyên ngành : Công Nghệ Thông Tin

LUẬN VĂN THẠC SĨ KHOA HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN



1.4.5 Bài toán NP-khó................................................................................................. 36 
1.5 Một số cách tiếp cận giải các bài toán NP............................................................... 37 
1.5.1 Phương pháp xấp xỉ ........................................................................................... 38 
1.5.2 Phương pháp xác xuất........................................................................................ 38 
1.5.3. Phương pháp heuristic....................................................................................... 39 
1.5.4. Phương pháp tính toán tiến hóa ........................................................................ 40 

CHƯƠNG 2............................................................................................................ 43 
BÀI TOÁN CÂY KHUNG TRUYỀN THÔNG TỐI ƯU.................................. 43 
2.1. Giới thiệu................................................................................................................... 43 
2.2 Các bài toán tối ưu cây khung OCST ...................................................................... 46 
2.2.1 Bài toán MRCT................................................................................................... 46 
2.2.2. Bài toán cây khung truyền thông tối ưu tích yêu cầu (PROCT) ....................... 48 
2.2.3. Bài toán cây khung truyền thông tối ưu tổng yêu cầu (SROCT) ...................... 49 
2.2.4. Bài toán nhiều nguồn (Multiple Source)........................................................... 49 
2.3. Một số ứng dụng của bài toán cây khung truyền thông ....................................... 51 

CHƯƠNG 3............................................................................................................ 53 
THUẬT TOÁN DI TRUYỀN VÀ CÁC PHƯƠNG PHÁP MÃ HÓA CÂY.... 53 
3.1 Giải thuật di truyền................................................................................................... 53 
3.1.1 Tổng quan về giải thuật di truyền và các ứng dụng ..................................... 53 
3.1.2  Giải thuật di truyền ......................................................................................... 53 
3.2 Một số phương pháp mã hóa cây............................................................................. 56 
3.2.1 Mã hóa Prufer .................................................................................................... 56 
3.2.2. Mã hóa NetKeys (Network Random Keys Encoding) ...................................... 59 
3.2.3 Mã hóa NB (Node Biased Encoding) ................................................................. 61 
3.2.4 Mã hóa LB (Link Biased Encoding) .................................................................. 63 



2

Bin packing problem

3

Crossover, Recombination

Lai ghép

4

Evolutionary computation

Tính toán tiến hóa

5

Evaluation function

Hàm mục tiêu

6

Feasible solution

lời giải chấp nhận được

7


Toán tử di truyền

13

K-point crossover

Lai ghép tại điểm cắt k

14

Local search

Tìm kiếm cục bộ

15

Mutation

Đột biến

16

Optimal Communication
Spanning Tree

17

Objective function




Communication Spanning Tree
20

Order-based crossover

Lai ghép theo thứ tự

21

Probabilistic method

Phương pháp xác xuất

22

Primitive operations

Số phép toán cơ bản

23

Population

Quần thể

24

Selection



Danh mục bảng vẽ
Bảng 1.1- Tóm tắt một số hàm tính độ phức tạp của thuật toán....................................22
Bảng 1.2 - Cho biết thời gian tính toán của thuật toán có độ phức tạp thường gặp. .....23
Bảng 1.3- Mối tương quan giữa quá trình tiến hóa và tính toán tiến hóa.....................41
Bảng 2.1- Các bài toán tối ưu OCT và tỉ lệ xấp xỉ tốt nhất được biết. ..........................51
Bảng 3.1- Chuỗi NetKeys cùng nhãn của các cạnh trong đồ thị ban đầu.....................60
Bảng 3.2 - Chuỗi NetKeys sau khi được sắp xếp ...........................................................60
Bảng 4.1 - Các bộ test chuẩn .........................................................................................74
Bảng 4.2 - Kết quả chạy các bộ test chuẩn sử dụng mã hóa Prufer và Netkey Encoding
................................................................................................................................76
Bảng 4.3- Kết quả chạy các bộ test chuẩn sử dụng mã hóa LB và NB..........................77
Bảng 4.4 - Kết quả chạy các bộ test chuẩn sử dụng mã hóa LNB.................................78

7


Danh mục hình vẽ
Hình 1.1 - Minh họa thuật toán......................................................................................16
Hinh 1.2- Minh họa bài toán chọn lịch xem phim. ........................................................17
Hình 1.3 Phản ví dụ của thuật toán 1. ...........................................................................17
Hình 1.4 - Phản ví dụ của thuật toán 2..........................................................................17
Hình 1.5 - Ký hiệu O – lớn. ............................................................................................20
Hình 1.6- Ký hiệu

-lớn. ..............................................................................................20

Hình 1. 7 Ký hiệu



Lời cam đoan

Tôi cam đoan kết quả của luận văn là chính tôi thực hiện, các số liệu thực
nghiệm là theo đúng kết quả của chương trình. Nếu sai tôi xin chịu hoàn toàn trách
nhiệm.

10


Lời cảm ơn
Tác giả đã nhận được sự hướng dẫn nhiệt tình, chu đáo, nghiêm khắc và đầy
khoa học của PGS.TS Nguyễn Đức Nghĩa trong suốt thời gian học tập, nghiên cứu và
hoàn thành đề tài. Tác giả xin bày tỏ lòng biết ơn chân thành và kính trọng sâu sắc đối
với Thầy.
Nhân dịp này tác giả cũng xin chân thành gởi lời cảm ơn đến quý thầy, cô trong
và ngoài Viện Công nghệ Thông tin và Truyền thông, Viện Đào tạo Sau đại học Đại
học Bách khoa Hà Nội đã dày công giảng dạy trong suốt khóa học và tạo điều kiện
thuận lợi cho tác giả hoàn thành luận văn này.
Tác giả xin chân thành cảm ơn các bạn cùng lớp Cao học Tin khóa 1 đã đùm
bọc giúp đỡ nhau trong học tập và sinh hoạt.
Mặc dù luận văn đã được thực hiện với sự nổ lực cố gắng hết sức của bản thân
song do hạn chế về trình độ và sự hiểu biết nên khó tránh khỏi những sai lầm thiếu sót.
Đồng thời tác giả cũng nhận thức được rằng còn rất nhiều vấn đề mở đặt ra chưa giải
quyết được. Tác giả rất mong nhận được những góp ý, phê bình quý báu của quý thầy
cô và các bạn đọc quan tâm.

11



The Link and Node Biased Encoding.
Thuật toán với các kỹ thuật mã hóa cây khác nhau đã được chạy thử nghiệm trên
các bộ dữ liệu thường dùng bởi các nhà khoa học để đánh giá hiệu quả các thuật toán
giải của bài toán OCST.

Tóm tắt cô đọng các luận điểm cơ bản và đóng góp mới của tác giả
Luận văn được trình bày trong 4 chương và lời kết luận.
Chương 1 trình bày các khái niệm cơ bản của lý thuyết độ phức tạp tính toán, định
nghĩa lớp bài toán NP-khó.
Chương 2 trình bày tổng quan về bài toán cây khung truyền thông tối ưu.
Chương 3 trình bày thuật toán di truyền và một số phương pháp mã hóa cây.
Chương 4 trình bày kết quả thực nghiệm thu được khi sử dụng thuật toán di truyền đề
xuất để giải bài toán cây khung truyền thông tối ưu với các kỹ thuật mã hóa cây khác
nhau. Phân tích kết quả đạt được của thuật toán di truyền với năm phương pháp mã hóa
cây khung.
Về đóng góp mới của tác giả: Đưa ra kết quả so sánh giữa các kỹ thuật mã hóa
cây khác nhau. Để từ đó có thể chọn được kỹ thuật mã hóa cây cho kết quả tốt trong
bài toán cây khung truyền thông.

13


Phương pháp nghiên cứu
Nghiên cứu lý thuyết về thuật toán di truyền và bài toán tối ưu cây khung truyền
thông.
Nghiên cứu các kỹ thuật mã hóa cây.
Xây dựng và cài đặt chương trình cho các kỹ thuật mã hóa cây.
So sánh kết quả đạt được của các kỹ thuật mã hóa cây.
Kết luận và hướng phát triển.
Phần kết luận chung đánh giá tổng quan lại những kết quả đã thực hiện được


Algorithm(thuật toán )

Input (Đầu vào)

Output (Đầu ra)

Hình 1.1 - Minh họa thuật toán.
1.2 Các đặc trưng của thuật toán:
y Đầu vào (Input): là tập các dữ liệu cần cung cấp thuật toán từ lúc đầu để xử lý.
y Đầu ra (Output): với mỗi một bộ dữ liệu vào, thuật toán sẽ cho ra bộ các dữ liệu
ra tương ứng với lời giải của bài toán cho bộ dữ liệu vào.
y Hữu hạn: với mọi đầu vào thì thuật toán vẫn cần phải đưa được đầu ra sau một
số hữu hạn (có thể rất lớn) bước thực hiện.
y Tính xác định: Thuật toán yêu cầu ở mỗi bước các thao tác phải hết sức rõ ràng,
không gây nên sự nhập nhằng, lẫn lộn. Khi thực hiện thuật toán trong cùng một
điệu kiện phải cho cùng một kết quả.
y Tổng quát: Tức là thuật toán có thể áp dụng để giải mọi bài toán có dạng đã cho.
y Tính hiệu quả: Với dữ liệu vào, sau một số hữu hạn bước thực hiện thuật toán sẽ
dừng và cho đúng kết quả mong muốn với thời gian chấp nhận được.
Hai tính chất quan trọng nhất của thuật toán là tính xác định và tính hiệu quả.
Tính xác định của thuật toán không phải lúc nào cũng dễ thấy.
-

Ví dụ: Bài toán chọn lịch xem phim.
Đầu vào: Một tập G gồm thời gian chiếu trong ngày của n bộ phim.
Đầu ra: Tập con của G chứa số bộ phim lớn nhất có thể xem (không được

chồng lên nhau về thời gian).
Chúng ta có thể biểu diễn các bộ phim dưới dạng các đoạn thẳng không giao


+ Thuật toán 3: Duyệt toàn bộ: duyệt

tập con của tập n bộ phim trong G. Chọn ra

tập con nào có số lượng phần tử lớn nhất. Đảm bảo thu được kết quả tối ưu. Thuật toán
chạy rất chậm, vì với

thì số tập con là 220.

+ Thuật toán 4: Sắp xếp các lịch chiếu phim theo thứ tự tăng theo thời gian kết thúc
(thuật toán tối ưu). Lần lượt xem xét các phim trong danh sách đã sắp xếp, bổ sung vào
danh sách xem bộ phim đang xét nếu nó không chồng lên các bộ phim đã có trong
danh sách xem.
Để chỉ ra thuật toán là không cho lời giải đúng ta chỉ cần đưa ra một phản ví dụ
của thuật toán. Tuy nhiên chưa chỉ ra được một phản ví dụ của thuật toán không có
nghĩa là thuật toán luôn cho lời giải đúng. Để chứng minh một thuật toán là cho lời giải
đúng thì ta phải chứng minh bằng toán học.
Chú ý rằng có những bài toán còn không có thuật toán để giải, chẳng hạn bài
toán về tính dừng của thuật toán.
1.3 Độ phức tạp của thuật toán
1.3.1 Tiêu chí đánh giá thuật toán
Để đánh giá hiệu quả của một thuật toán người ta thường đánh giá độ phức
tạp thời gian thực hiện của thuật toán như là hàm theo kích thước của dữ liệu đầu
vào. Kích thước của dữ liệu đầu vào (the size of the input) thường tùy thuộc vào
từng bài toán cụ thể, có thể là tổng số bit cần thiết để biểu diễn nhị phân của dữ liệu
(chẳng hạn, bài toán xác định tính nguyên tố của số tự nhiên n, thì kích thước dữ liệu
đầu vào không phải là n, mà là số chữ số của n hay tổng số bit cần thiết trong biểu
diễn nhị phân của n). Đối với bài toán sắp xếp tăng dần dãy n phần tử a1, a2, a3,…,
an cho trước thì kích thước dữ liệu đầu vào n.

: nếu tồn tại hằng số
mọi

•

. Ta nói

và số tự nhiên

. Ta nói

: nếu tồn tại hằng số
với mọi

và

. Ta nói

19

với

sao cho

với

sao cho

và


Nghĩa là tồn tại c = 8, n0 = 1 . Do đó n2+4n+2=O(n2).
Tổng quát : aknk+ak-1nk-1+…+a0=O(nk) (giả thiết ak >0).
Chú ý rằng, 2n không có bậc của một đa thức, vì mọi số nguyên dương k và
mọi số dương C > 0, chúng ta có 2n >

với n đủ lớn.

•

vì chọn

•

vì với bất kỳ giá trị
lớn (

nếu

•

,

thì

nếu

khi
thì

.

•
•
O-lớn nhóm các hàm thành các lớp hàm, các hàm
có quan hệ theo các ký hiệu tiệm cận
hàm thì có quan hệ theo

thuộc hai lớp khác nhau

khác nhau. Còn các hàm thuộc cùng 1 lớp

.

+ Một số hàm tính độ phức tạp tính toán thường gặp của thuật toán:
Các hàm 1, logn, n, nk, được xếp vào hàm đa thức. Các hàm còn lại nlogn, an, n!
được xếp vào loại hàm mũ. Những thuật toán có độ phức tạp tính toán cấp loại hàm
21


đa thức thường là chấp nhận được, những thuật toán như thế được gọi là thuật toán đa
thức (polynomial algorithm). Những thuật toán có độ phức tạp tính toán cấp loại hàm
mũ thì tốc độ tính toán thường rất chậm.
STT

Độ phức tạp

Tên gọi

1

O(1)


O(

)

Hàm mũ

7

O(

8

O(n!)

Hàm mũ

), b>1, n

Giai thừa

Bảng 1.1- Tóm tắt một số hàm tính độ phức tạp của thuật toán.
Vì vậy hàm logb(n) tăng trưởng

Lưu ý thêm, với mọi x >-1,

chậm hơn hàm đa thức na với a, b là các số thực dương . Với a>1, hàm mũ an là đơn
điệu tăng theo n. Với hằng số k nguyên dương bất kỳ, ta có

hay nk =O(an).

If a[j+1]