ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN QUANG ANH
MỘT SỐ PHƯƠNG PHÁP HEURISTIC GIẢI BÀI
TOÁN THIẾT KẾ MẠNG VIỄN THÔNG

Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

việc, giúp đỡ tác giả trong thời gian học tập và làm luận văn.
Xin chân thành cảm ơn anh chị em học viên lớp CAO HỌC K9A đã giúp đỡ,
động viên, khích lệ tác giả trong quá trình học tập và nghiên cứu.
Luận văn sẽ không hoàn thành đƣợc nếu không có sự quan tâm, động viên của
ngƣời thân trong gia đình tác giả. Đây là món quà tinh thần, tác giả xin gửi tặng gia
đình thân yêu của mình với lòng biết ơn sâu sắc.

Tác giả

iii
MỤC LỤC
LỜI CAM ĐOAN i
LỜI CẢM ƠN ii
MỤC LỤC iii
DANH MỤC CÁC HÌNH ẢNH, HÌNH VẼ v
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ vi
MỞ ĐẦU i
Chƣơng 1. GIỚI THIỆU MỘT SỐ PHƢƠNG PHÁP HEURISTIC 3
1.1. Thuật toán tham lam 3
1.1.1. Giới thiệu chung 3
1.1.2. Thuật toán cho phƣơng pháp tham lam 4
1.1.3. Ví dụ áp dụng 5
1.2. Giới thiệu về mạng nơ-ron 8
1.2.1. Mô hình mạng nơ-ron nhân tạo 8
1.2.2. Phân loại mạng nơ-ron nhân tạo 11
1.2.3. Luật học 13
1.2.4. Những bài toán thích hợp 16
1.3. Giải thuật di truyền 18
1.3.1. Các khái niệm cơ bản 18
1.3.2. Các bƣớc quan trọng trong giải thuật 18


v
DANH MỤC CÁC HÌNH ẢNH, HÌNH VẼ

Hình 1.1. Mô hình nơ-ron sinh học 9
Hình 1.2. Mô hình một nơ-ron 10
Hình 1.3. Mạng tuyền thẳng một lớp 12
Hình 1.4. Mạng truyền thẳng nhiều lớp 12
Hình 1.5. Mạng một lớp có nối ngƣợc 13
Hình 1.6. Mạng nhiều lớp có nối ngƣợc 13
Hình 3.1. Phân bố các thiết bị cuối kết nối vào các trạm 44
Hình 3.2. Thử nghiệm Giải thuật Tham lam với bộ dữ liệu thứ nhất 46
Hình 3.3. Thử nghiệm Giải thuật Tham lam với bộ dữ liệu thứ hai 47
Hình 3.4. Thử nghiệm Giải thuật Tham lam với bộ dữ liệu thứ ba 49
Hình 3.5. Thử nghiệm Giải thuật di truyền với bộ dữ liệu thứ nhất 51
Hình 3.6. Thử nghiệm Giải thuật di truyền với bộ dữ liệu thứ hai 52
Hình 3.7. Thử nghiệm Giải thuật di truyền với bộ dữ liệu thứ ba 54
Hình 3.8. Sự kết hợp mạng nơ-ron và giải thuật di truyền với bộ dữ liệu thứ nhất 57
Hình 3.9. Sự kết hợp mạng nơ-ron và giải thuật di truyền với bộ dữ liệu thứ hai 58
Hình 3.10. Sự kết hợp mạng nơ-ron và giải thuật di truyền với bộ dữ liệu thứ ba 60


Kế toán thống kê tài chính
TCCB
Tổ chức cán bộ
Tổ chức cán bộ
KD
Kinh doanh
Kinh doanh
HCQT
Hành chính quản trị
Hành chính quản trị
CT công đoàn
Chủ tịch công đoàn
Chủ tịch công đoàn
DNCCDV
Doanh nghiệp cung cấp dịch vụ
Doanh nghiệp cung cấp dịch vụ
VT
Viễn thông
Viễn thông
CNTT
Công nghệ thông tin
Công nghệ thông tin
SXKD
Sản xuất kinh doanh
Sản xuất kinh doanh
BC-VT
Bƣu chính - Viễn thông
Bƣu chính - Viễn thông
OMC
Operation Maintenane

Truyền hình qua giao thức IP
1 MỞ ĐẦU
Cơ sở khoa học của đề tài
Hiện nay, việc trao đổi thông tin qua các thiết bị không dây ngày càng trở nên
phổ biến. Để nâng cao chất lƣợng dịch vụ, các nhà mạng đang phải mở rộng hệ
thống mạng viến thông bằng cách tăng thêm số cột thu, nhận tín hiệu từ các thiết bị
không dây. Do đó các nhà mạng đều mong muốn có một mạng viễn thông hoạt
động hiệu quả, có hiệu suất cao và tiết kiệm đƣợc các chi phí mua thiết bị. Sử dụng
phƣơng pháp Heuristic là cách làm thiết thực để đƣa ra một thiết kế cho mạng viễn
thông một cách tối ƣu.
Nhận thấy tính thiết thực của bài toán này và đƣợc sự gợi ý của giảng viên
hƣớng dẫn, tôi đã chọn đề tài “Mt s t k
mng vi” làm đề tài cho luận văn tốt nghiệp của mình.
Mục tiêu và nhiệm vụ của luận văn
- Thu thập tài liệu và nghiên cứu về một số phƣơng pháp Heuristic
- Nghiên cứu để hiểu cách giải các bài toán tối ƣu bằng phƣơng pháp Heuristic
- Tìm hiểu bài toán thiết kế mạng viễn thông và vận dụng phƣơng pháp
heuristic để giải bài toán này.
- Xây dựng chƣơng trình mô phỏng bài toán trên máy tính và thực hiện các thử
nghiệm trên các bộ dữ liệu.
Đối tƣợng và phạm vi nghiên cứu
- Phƣơng pháp Heuristic nhƣ phƣơng pháp tham, giải thuật di truyền và mạng
nơ ron giải các bài toán tối ƣu tổ hợp
- Bài toán thiết kế mạng viễn thông
- Giải bài toán thiết kế mạng viễn thông bằng các phƣơng pháp Heurristic
Phƣơng pháp nghiên cứu
Tìm hiểu một số phƣơng pháp Heuristic giải bài toán thiết kế mạng Viễn

1.1.1. Gii thiu chung
* Định nghĩa
Giải thuật tham lam là một thuật toán giải quyết một bài toán dựa trên tri thức
về vấn đề để tìm kiếm một tối ƣu địa phƣơng ở mỗi bƣớc đi với hy vọng tìm đƣợc
tối ƣu toàn cục.
Giải thuật tham lam có 5 thành phần:
a) Một tập hợp các ứng viên để từ đó tạo ra lời giải;
b) Một hàm lựa chọn để lựa chọn ứng viên tốt nhất để bổ sung vào lời giải;
c) Một hàm khả thi dùng để quyết định một ứng viên có thể là một lời giải;
d) Một hàm mục tiêu để ấn định giá trị lời giải hoặc một lời giải chƣa hoàn chỉnh;
e) Một hàm đánh giá để chỉ ra khi nào ta tìm ra một lời giải hoàn chỉnh.
* Hai thành phần quyết định nhất tới quyết định tham lam
Tính chất lựa chọn tham lam: Chúng ta có thể lựa chọn giải pháp nào đƣợc cho là
tốt nhất ở thời điểm hiện tại và sau đó giải bài toán con nảy sinh từ việc thực hiện lựa chọn
vừa rồi. Lựa chọn của thuật toán tham lam có thể phụ thuộc vào các lựa chọn trƣớc đó.
Thuật toán tiến triển theo kiểu thực hiện các chọn lựa theo một vòng lặp, cùng lúc
đó thu nhỏ bài toán đã cho về một bài toán con nhỏ hơn. Giải thuật tham lam lựa chọn
sớm và thay đổi đƣờng đi thuật toán theo lựa chọn đó, và không bao giờ xét lại các lựa
chọn cũ. Đối với một số bài toán, đây có thể là một thuật toán không chính xác.
Cấu trúc con tối ưu: Một bài toán đƣợc gọi là "có cấu trúc tối ƣu", nếu một lời
giải tối ƣu của bài toán con chứa lời giải tối ƣu của bài toán lớn hơn.
* Ý tƣởng của phƣơng pháp tham lam
Phƣơng pháp tham lam là kỹ thuật thiết kế thƣờng đƣợc dùng để giải các bài
toán tối ƣu. Phƣơng pháp đƣợc tiến hành theo nhiều bƣớc. Tại mỗi bƣớc, theo một
lựa chọn nào đó (xác định bằng một hàm chọn), sẽ tìm một lời giải tối ƣu cho bài
toán nhỏ tƣơng ứng. Lời giải của bài toán đƣợc bổ sung dần từng bƣớc từ lời giải
4 của các bài toán con. Các lời giải tìm đƣợc bằng phƣơng pháp tham lam thƣờng chỉ


}
return S;
1 ng
* Bài toán:
Một ngƣời du lịch muốn tham quan n thành phố T
i
, …, T
n
. Xuất phát từ một
thành phố nào đó, ngƣời du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành
phố đi qua đúng một lần rồi quay trở lại thành phố đã xuất phát.
Gọi C
ij
là chi phí đi từ thành phố T
i
đến T
j
. Hãy tìm một hành trình thoả yêu
cầu bài toán sao cho tổng chi phí là nhỏ nhất.
*Ý tƣởng
Đây là bài toán tìm chu trình có trọng số nhỏ nhất trong một đơn đồ thị có
hƣớng có trọng số.
Thuật toán tham lam cho bài toán là chọn thành phố có chi phí nhỏ nhất tính từ
thành phố hiện thời đến các thành phố chƣa qua.
* Thuật toán
Input: C = ( C
i j
)
Output: TOUR // Hành trình tối ƣu,

1
2
1
1
3
5
1
2
7 * Độ phức tạp của thuật toán
Thao tác chọn đỉnh thích hợp trong n đỉnh đƣợc tổ chức bằng một vòng lặp
để duyệt. Nên chi phí cho thuật toán xác định bởi 2 vòng lặp lồng nhau,
nên T(n) = V(n
2
).
* Cài đặt:
Int GTS ( mat a, int n, int TOUR [ max ], int Ddau )
{
int v, // Dinh dang xet

COST + = mini;
}
COST + = a [ v ] [ Ddau ];
return COST;
}
1.1.4 
Bài toán đƣợc giải quyết bằng thuật toán tham lam (thƣờng là các bài toán tối
ƣu) nếu nhƣ nó có hai đặc điểm sau:
 Tính lựa chọn tham lam (greedy choice property): Một nghiệm tối ƣu
có thể nhận đƣợc bằng cách thực hiện các lựa chọn có vẻ nhƣ tốt nhất
tại mỗi thời điểm mà không cần quan tâm tới các gợi ý của nó đối với
các nghiệm của các bài toán con. Hay nói một cách khác là nghiệm tối
ƣu của bài toán có thể nhận đƣợc bằng cách thực hiện các lựa chọn tối
ƣu cục bộ.
9  Cấu trúc con tối ƣu (optimal substructure):Một nghiệm tối ƣu có thể
nhận đƣợc bằng cách gia tăng các nghiệm thành phần đã đƣợc xây
dựng với một nghiệm tối ƣu của bài toán con còn lại. Có nghĩa là một
nghiệm tối ƣu sẽ chứa các nghiệm tối ƣu đối với các bài toán con kích
thƣớc nhỏ hơn
1.2. Giới thiệu về mạng nơ-ron
1.2.1. -o
* Nơ-ron sinh học
Hệ thần kinh ở ngƣời có khoảng 10
10
tế bào thần kinh đƣợc gọi là các nơ-ron.
Mỗi nơ-ron gồm có ba phần: Thân nơ-ron với nhân ở bên trong (soma), một đầu
thần kinh ra (axon) và một hệ thống hình cây thần kinh (dendrite). Có nhiều loại nơ-

tín hiệu vào đƣợc gán một trọng số tƣơng ứng. Ta có thể ƣớc lƣợng tổng tín
hiệu đi vào nơ- ron theo một số dạng : tuyến tính, toàn phƣơng, mặt cầu
- Hàm kích hoạt: Hàm biến đổi tín hiệu đầu vào net cho tín hiệu đầu ra out
đƣợc gọi là hàm kích hoạt. Hàm này có đặc điểm là không âm và bị chặn. Có nhiều
dạng hàm kích hoạt, ngƣời ta thƣờng sử dụng một hàm kích hoạt chung cho toàn
mạng.
Một số hàm kích hoạt thường được sử dụng: McCuloch-Pitts,

McCuloch-Pitts
trễ, Sigmoid.
- Nút bias: một nút thêm vào nhằm tăng khả năng thích nghi của mạng nơ-ron
trong quá trình học. Trong các mạng nơ-ron có sử dụng bias, mỗi nơ-ron có thể có
một trọng số tƣơng ứng với bias. Trọng số này luôn có giá trị là 1.
* Mô hình của một nút xử lý (nút thứ i)

j
S
ij
W
i
net


Hình 1.2. Mô hình một nơ-ron
11 







 












Trong đó : là tín hiệu vào tại nơ-ron i
là tín hiệu ra tại nơ-ron i
là trọng số liên kết từ nơ-ron j đến nơ-ron i
là ngƣỡng (đầu vào ngoài ) kích hoạt nơ-ron i

f
(1.1)
(1.2)
12 * Mạng truyền thẳng:
- Mạng truyền thẳng một lớp
Mô hình mạng nơ-ron truyền thẳng một lớp là mô hình liên kết cơ bản và đơn
giản nhất. Các nơ-ron tổ chức lại với nhau tạo thành một lớp, đƣờng truyền tín hiệu
đƣợc truyền theo một hƣớng nhất định nào đó. Các đầu vào đƣợc nối với các nơ-ron
theo các trọng số khác nhau, sau quá trình xử lý cho ra một chuỗi các tín hiệu ra.
Nếu mạng nơ-ron là mô hình LTU thì nó đƣợc gọi là mạng Percception, còn mạng
nơ-ron là mô hình LGU thì nó đƣợc gọi là mạng Adaline.
Với mỗi giá trị đầu vào x = [ x
1
,x
2
,. . . . ,x
n
]
T
. Qua quá trình xử lý của mạng ta
sẽ thu đƣợc một bộ tƣơng ứng các giá trị đầu ra là y = [y
1
,y
2
,. . . ,y
n
]

i
: là ngƣỡng của nơ ron thứ i.
- Mạng truyền thẳng nhiều lớp.
Với mạng nơ-ron truyền thẳng một lớp ở trên, khi phân tích một bài toán phức
tạp sẽ gặp rất nhiều khó khăn, để khắc phục vấn đề này ngƣời ta đƣa ra mô hình
nixwfy
ijij
m
j
ii
,1).(
1


θ
y
1
y
n
y
2
X
m
x
1
x
2
Hình 1.3. Mạng truyền thẳng một lớp
(1.3)
13

hệ học thích nghi. Mặt khác, với khả năng tổng quát hoá của mạng nơ-ron, nó có thể
Y
1
Y
2
Y
M
. . .

. . .

X
1
X
2
X
N
. . .

. . .

Hình 1.6. Mạng nhiều lớp có nối ngƣợc
. . .
. . .

. . .

X
1
X

là tốc độ học, nằm trong khoảng (0,1).
r là hằng số học.
Vấn đề đặt ra ở đây là tín hiệu học r đƣợc sinh ra nhƣ thế nào để hiệu chỉnh
trọng số của mạng.
Có thể chia thủ tục học tham số ra thành ba lớp nhỏ hơn: Học có chỉ đạo, học
tăng cƣờng và học không chỉ đạo. Việc xác định r phụ thuộc vào từng kiểu học.
+ Học có tín hiệu chỉ đạo: Là quá trình mạng học dựa vào sai số giữa đầu ra
thực và đầu ra mong muốn để làm cơ sở cho việc hiệu chỉnh trọng số. Sai số này
chính là hằng số học r. Luật học điển hình của nhóm này là luật học Delta của
Widrow (1962) nêu ra đầu tiên dùng để xấp xỉ trọng số của Adaline dựa trên
nguyên tắc giảm gradient.
Trong nhóm luật học này cũng cần phải kể đến luật học Perceptron của
Rosenblat (1958). Về cơ bản luật học này thay đổi các giá trị trọng số trong thời
gian học, còn luật Perceptron thì thêm hay bỏ trọng tuỳ theo giá trị sai số là dƣơng
hay âm.
MjNirxW
jij
,1,,1, 


(1.4)
15 Một loạt các luật học khác cũng đƣợc dựa trên tƣ tƣởng này. Luật Oja là cải
tiến và nâng cấp của luật Delta. Luật truyền ngƣợc là luật mở rộng của luật Delta
cho mạng nhiều lớp. Đối với mạng truyền thẳng thƣờng sử dụng luật truyền ngƣợc
để chỉnh trọng số với tín hiệu chỉ đạo từ bên ngoài và ngƣời ta gọi mạng này là
mạng lan truyền ngƣợc.
+ Học không có tín hiệu chỉ đạo: Luật học này sử dụng đầu ra của mạng làm

jiij
,1,,1, 


(1.5)
16 + Học tăng cƣờng: Trong một số trƣờng hợp, thông tin phản hồi chỉ là tín hiệu
bao gồm hai trạng thái cho biết tín hiệu đầu ra của mạng là đúng hay sai. Quá trình
học dựa trên các thông tin hƣớng dẫn nhƣ vậy đƣợc gọi là học có củng cố (học tăng
cƣờng) và tín hiệu mang thông tin phản hồi đƣợc gọi là tín hiệu củng cố cho quá
trình học. Ta có thể thấy rằng quá trình học này là một dạng của quá trình học có tín
hiệu chỉ đạo bởi vì mạng nhận đƣợc một số thông tin phản hồi từ bên ngoài.
Học cấu trúc: Tìm kiếm các tham số của cấu trúc mạng để tìm ra một cấu trúc
mạng hoạt động tốt nhất. Trong thực tế, việc học cấu trúc là tìm ra số lớp ẩn và tìm
ra số nơ-ron trên mỗi lớp đó. Giải thuật di truyền thƣờng đƣợc sử dụng trong các
cấu trúc nhƣng thƣờng chạy rất lâu, thậm chí ngay cả đối với mạng có kích thƣớc
trung bình. Ngoài ra kỹ thuật gọt tỉa mạng hay mạng tăng dần cũng đƣợc áp dụng
trong việc học cấu trúc của mạng có kích thƣớc tƣơng đối nhỏ.
Ƣu và nhƣợc điểm của mạng nơ-ron
* Ƣu điểm:
– Xử lý song song.
– Thiết kế hệ thống thích nghi.
– Không đòi hỏi các đặc trƣng mở rộng của bài toán (chủ yếu dựa trên tập
học).
* Nhƣợc điểm:
– Không có các quy tắc và các hƣớng dẫn thiết kế một cách rõ ràng đối với
một ứng dụng nhất định.
– Không có cách tổng quát để đánh giá hoạt động bên trong mạng.

các đặc điểm mà chúng ta không thể nhận thấy khi chúng thuộc không gian nhiều
chiều. Theo một chừng mực nào đó, biến đổi tƣơng tự nhƣ việc nhóm các đối tƣợng
hay phân loại thể hiện ở chỗ biểu diễn các kết quả ra. Trong phân loại, chúng ta
muốn định danh các nhóm hoặc lớp mà đối tƣợng thuộc vào, còn trong biến đổi,
chúng ta quan tâm đến toàn bộ các đối tƣợng và từ đó chúng ta thu nhận đƣợc các
nhóm từ các đối tƣợng học. Điểm quan trọng trong biến đổi là các đối tƣợng đƣợc
biểu diễn bởi toạ độ của nơ-ron trung tâm chứ không phải là giá trị của tín hiệu ra.
d) Liên kết
18 Liên kết là tìm ra đối tƣợng đích có mối quan hệ với một đối tƣợng vào, thậm
chí cả khi đối tƣợng vào bị hỏng hoặc hoàn toàn không biết. Theo một nghĩa nào
đó, liên kết có thể đƣợc coi là phân loại. Thủ tục học cho vấn đề này là học có tín
hiệu chỉ đạo.
1.3. Giải thuật di truyền
1n
* Giới thiệu chung
Thuật di giải di truyền là kỹ thuật giúp giải quyết vấn đề bắt chƣớc theo sự
tiến hóa của con ngƣời hay của sinh vật nói chung trong điều kiện quy định sẵn của
môi trƣờng. Phƣơng tiện để thực hiện cách giải quyết vấn đề này là chƣơng trình tin
học gồm các bƣớc phải thi hành, từ việc chọn giải pháp tiêu biểu cho vấn đề, cho
đến việc chọn các hàm số thích nghi cũng nhƣ các phƣơng pháp biến hóa để tạo cho
giải pháp ngày càng thích nghi hơn. Nhƣ vậy GA ( Genetic Algorithms ) không chú
trọng đến giải pháp duy nhất và chính xác nhƣ phƣơng pháp cổ điển, trái lại GA xét
đến toàn bộ các giải pháp và tuy dựa trên tính ngẫu nhiên nhƣng có hƣớng dẫn bởi
hàm số thích nghi, do đó không có nghĩa là “đoán mò”. Chúng ta sẽ xét đến các
phần dƣới đây.
* Các tính chất của giải thuật
- GA lập luận mang tính chất ngẫu nhiên (stochastic), thay vì xác định