HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

TIỂU LUẬN
MÔN HỌC: CÁC KỸ THUẬT TỐI ƯU
Tên đề tài:
Thiết kế mạng hiệu quả sử dụng giải
thuật di truyền và Heuristic
Giảng viên hướng dẫn : PGS. TS. Lê Nhật Thăng
Người thực hiện : Đỗ Quang Đức
Đỗ Viết Dũng
Lớp : M13CQCS01 - B

Hà Nội, tháng 5, 2014
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
MỤC LỤC
MỤC LỤC 2
DANH MỤC HÌNH VẼ 4
DANH MỤC BẢNG BIỂU 4
CHƯƠNG 1: CÁC KỸ THUẬT TÍNH TOÁN HEURISTIC VÀ THÍCH ỨNG
TRONG VIỄN THÔNG: GIỚI THIỆU CHUNG 5
1.1 Các vấn đề tối ưu hóa trong viễn thông 5
1.2 Bài toán động và thích ứng 6
1.3 Các kỹ thuật Heuristic hiện đại 7
1.3.1 Tìm kiếm cục bộ 8
1.3.2 Tìm kiến dựa trên tập hợp (Population-Based Search) 14
1.4 Kỹ thuật tính toán thích ứng 16
1.4.1. Tính toán hệ thần kinh 18
1.4.2 Logic mờ 19
1.4.3 Lý thuyết trò chơi 20
1.5 Tổng kết 20
CHƯƠNG 2: THIẾT KẾ MẠNG HIỆU QUẢ SỬ DỤNG GIẢI THUẬT DI TRUYỀN

Hình 2.2: Cây bao trùm lớn nhất và đồ thị tuyến tính luồng tương ứng của nó 32
Hình 2.3: Cây bao trùm lớn nhán cảu đồ thị yêu cầu đầy đủ của bàng 2.1 33
Hình 2.4: Đồ thị luồng tương ứng tuyến tính tương ứng với câu bao trùm hình 2.3 34
Hình 2.5: quá trình lấy vòng dung lượng đồng nhất từ luồng tương đương tuyến tính 34
Hình 2.6: vòng dung lượng đồng đều trích từ đồ thị hình 2.4 34
Hình 2.7: Hình mạng sau khi áp dụng thuật toán union of rings 36
Hình 2.8: Kết quả các cấu trúc liên kết mạng từ mỗi phương pháp so sánh với vấn đề
10 thành phố của Trung Quốc. Mạng tận cùng bên trái là kết quả của phương pháp
Branch Exchange, mạng ở giữa là kết quả của thuật toán di truyền, và các mạng lưới
bên phải là kết quả từ thuật toán union of rings 36
DANH MỤC BẢNG BIỂU
Bảng 2.1: Yêu cầu luồng tối thiểu 33
Bảng 2.2: Tóm tắt của các thiết kế cuối cùng 41
Bảng 2.3: Kết quả cuối cùng 42
4
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
CHƯƠNG 1: CÁC KỸ THUẬT TÍNH TOÁN HEURISTIC VÀ
THÍCH ỨNG TRONG VIỄN THÔNG: GIỚI THIỆU CHUNG
1.1 Các vấn đề tối ưu hóa trong viễn thông
Sự phức tạp và kích thước của các mạng viễn thông hiện đại cung cấp cho
chúng ta nhiều thách thức và cơ hội. Trong cuốn sách này, những thách thức mà chúng
tôi tập trung vào là những liên quan đến việc tối ưu hóa. Điều này chỉ đơn giản đề cập
tới những trường hợp mà trong đó chúng ta đang hướng tới tìm một cách tiếp cận
phương án tốt nhất giữa nhiều phương án có thể có để giải quyết bài toán. Ví dụ, có
một số lượng lớn cách để thiết kế các cấu trúc liên kết một mạng dữ liệu riêng cho một
công ty lớn. Làm thế nào chúng ta có thể tìm thấy một thiết kế đặc biệt tốt trong tất cả
các khả năng? Ngoài ra, chúng ta có thể thử tìm một cách tốt để gán kênh tần số cho
nhiều người sử dụng mạng di động. Có một loạt các khó khăn phức tạp liên quan ở
đây, số lượng các phương án có thể đáp ứng các khó khăn vẫn còn quá lớn để chúng
tôi hy vọng sẽ kiểm tra lần lượt từng phương án trong số chúng. Vì vậy, một lần nữa,

máy chủ, tuy nhiên giải pháp này trở nên không hợp lệ ngay sau khi có sự thay đổi
trung bình trong mô hình truy cập cơ sở dữ liệu của khách hàng. Một ví dụ khác là
định tuyến gói chung trong một mạng point-to -point. Theo truyền thống, bảng định
tuyến tại mỗi nút được sử dụng để tìm kiếm ' bước kế tiếp ' tốt nhất cho một gói dựa
trên điểm đến cuối cùng của nó. Chúng ta có thể tưởng tượng một kỹ thuật tối ưu hóa
áp dụng cho vấn đề này, kỹ thuật này dựa vào mô hình tổng thể và xác định các bảng
định tuyến thích hợp cho mỗi nút, do đó ùn tắc chung và sự chậm trễ có thể được giảm
thiểu, tức là trong nhiều trường hợp là ' bước kế tiếp " tốt nhất có thể không tìm được
nút tiếp theo trên con đường ngắn nhất, vì liên kết này có thể được được sử dụng nhiều
rồi. Tuy nhiên, đây rõ ràng là một chương trình cần được thực hiện lặp đi lặp lại như
những biểu đồ thay đổi lưu lượng truy cập.
Việc thực hiện lặp đi lặp lại của các kỹ thuật tối ưu hóa là một trong những
cách có thể để tiếp cận các bài toán động, nó thường là một cách khá phù hợp, đặc biệt
là khi các giải pháp tốt yêu cầu cần thiết phải rất nhanh, vì môi trường thay đổi rất
nhanh chóng. Thay vào đó, một phạm vi khác của các kỹ thuật tính toán hiện đại
thường thích hợp cho các bài toán như vậy. Chúng ta có thể gọi chung lớp này là kỹ
thuật "thích ứng", mặc dù việc sử dụng ở các chương sau trong cuốn sách này thực sự
khá đa dạng. Đặc biệt, chương sau sẽ sử dụng tính toán thần kinh (neural), logic mờ và
lý thuyết trò chơi để giải quyết tối ưu hóa thích nghi trong môi trường động, trong một
số trường hợp kết hợp với tìm kiếm cụ bộ hoặc dựa vào tập hợp. Về cơ bản, một kỹ
6
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
thuật tối ưu hóa cung cấp một cách nhanh chóng và hiệu quả để tìm một giải pháp tốt
trong nhiều giải pháp, một kỹ thuật thích ứng phải cung cấp một giải pháp tốt gần như
là ngay lập tức.
Thủ thuật ở đây đó là các phương pháp sử dụng tiến trình “off-line” để học về
vấn đề đang giải quyết sao cho khi mà các kết quả tốt và nhanh được yêu cầu thì chúng
sẽ được chuyển đi. Ví dụ, một cách tiếp cận thích hợp cho việc định tuyến gói tin trong
các mặt thay đổi trong mô hình giao thông sẽ bao gồm một số liên tục nhưng tôi thiểu
hóa xử lý mà được cập nhật liên tục trong bảng định tuyến tại mỗi nút dựa trên thông

hiện đại, và do đó không cung cấp khá đầy đủ thông tin cho một người đọc để có thể
chỉnh cho phù hợp với các vấn đề cụ thể. Mặc dù chúng tôi không chỉ cho bạn cách để
sáng tạo với chúng, nhưng chúng tôi chỉ ra điểm mấu chốt ở đâu. Làm cách nào để áp
dụng sáng tạo chúng thì phụ thuộc và rất nhiều vấn đề, nhưng chương sau sẽ cung cấp
các thông tin cho từng trường hợp cụ thể. Những gì sẽ trở nên rõ ràng từ chương này,
tuy nhiên, đó là những kỹ thuật được đánh giá cao chung trong ứng dụng của chúng.
Trong thực tế, bất cứ khi nào cũng có một số cách khá sẵn để đánh giá hoặc tính điểm
giải pháp ứng cử viên cho vấn đề của bạn, sau đó các kỹ thuật này có thể được áp
dụng.
Về bản chất các kỹ thuật này được chia làm 2 nhóm: tìm kiếm địa phương, tìm
kiếm dựa trên dân số. Đó sẽ là những thứ sẽ được bàn đến tiếp theo đây.
1.3.1 Tìm kiếm cục bộ
Giả sử rằng bạn đang cố gắng để giải quyết một vấn đề P, và bạn có một tập
hợp S là các giải pháp tiềm năng cho vấn đề này. Bạn không nhất thiết phải có tập S, vì
nó quá lớn để có thể hiểu rõ toàn bộ. Tuy nhiên, bạn có một số cách để tạo ra các giải
pháp từ nó. Ví dụ, S có thể là một tập hợp các cấu trúc liên kết cho một mạng, và các
giải pháp ứng cử s, s ', s'',… là các đề cử cấu trúc kết nối cụ thể mà bạn đã đưa ra theo
cách nào đó. Thêm vào đó, hãy tưởng tượng rằng bạn có một hàm chuẩn hóa f(s)
(fitness function) có chức năng đưa ra kết quả của một giải pháp đề cử. Kết quả tốt hơn
đồng nghĩa với việc đó là giải pháp tốt hơn. Lấy ví dụ, chúng ta đang cố gắng tìm ra
những cấu trúc liên kết mạng đáng tin cậy nhất, sau đó f (s) có thể tính toán xác suất
thất bại của liên kết giữa hai nút đặc biệt quan trọng. Trong trường hợp chúng ta muốn
sử dụng nghịch đảo của giá trị này nếu chúng ta thực sự muốn gọi nó là ‘chuẩn hóa’
(fitness). Trong những trường hợp khi mà kết quả thấp hơn, thì tốt hơn và thường thì
thích hợp hơn đó là coi f(s) là một hàm chi phí.
8
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
Chúng ta còn cần thêm một điều nữa, mà chúng ta gọi là một toán tử lân cận
(neighbourhood operator). Đây là hàm có chức năng lấy ra một giải pháp đề cử s, và
tạo ra một giải pháp đề cử mới s’ - thường chỉ hơi khác một chút so với s. Chúng ta sẽ

9
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
Do vậy, bất kỳ việc cài đặt phướng pháp tìm kiếm tabu nào đều duy trì một vài
dạng bộ nhớ ghi lại những thuộc tính nhất định của những di chuyển gần đây. Những
thuộc tính này phụ thuộc nhiều vào vấn đề đang xem xét và đây là một phần của việc
áp dụng phương pháp tìm kiếm tabu. Ví dụ, nếu chúng ta cố gắng tối ưu hóa topo
mạng, một dạng của bộ biến đổi sẽ phải thay đổi đường cáp liên kết giữa nút a và nút
b. Hoặc là trong việc cài đặt phương pháp tìm kiếm tabu, chúng ta có lẽ chỉ ghi lại sự
kiện thay đổi đường cáp ở lần lặp thứ i, hoặc là đơn giản chỉ ghi lại sự thay đổi trong
liên kết giữa nút a với một nút mà liên kết với nút b. Nếu chúng ta chỉ ghi lại kiểu
thuộc tính trước đó thì những di chuyển có thể xảy ra gần thời điểm đó có thể không
được chấp nhận và không phụ thuộc vào các nút có liên quan. Nếu chúng ta chỉ ghi lại
thuộc tính sau đó thì những thay đổi tiềm năng bao gồm nút a và (hoặc) nút b có thể
không được chấp nhận nhưng những di chuyển thay đổi cáp có thể được chấp nhận.
Phương pháp tìm kiếm cục bộ Artful
Có một vài điểm chú ý về việc thuật toán tabu minh họa đó là khía cạnh quan
trọng của phương pháp tìm kiểm cục bộ tốt là quyết định láng giềng nào cần di chuyển
đến. Tất cả các phương pháp tìm kiếm cục bộ thực hiện các ý tưởng cơ bản về di
chuyển cục bộ đều là những ý tưởng tốt. Ví dụ, nếu giải pháp hiện tại của bạn tốt thì
có thể có một giải pháp tốt hơn gần đó và có thể có một giải pháp tốt hơn nữa
Tuy nhiên, rõ ràng là thỉnh thoảng (có lẽ là thường xuyên) chúng ta phải chấp
nhận thực tế là chúng ta chỉ có thể tìm kiếm các giải pháp được cải tiến bằng cách tạm
thời thực hiện các giải pháp khác tồi hơn. Thuật toán mô phỏng annealing và phương
pháp tìm kiếm tabu là hai cách tiếp cận để giải quyết vấn đề này. Tuy nhiên, đối với
một vấn đề cụ thể thì cách tốt nhất trong triển khai và thiết kế hai cách tiếp cận trên là
không rõ ràng. Có nhiều sự lựa chọn có thể đưa ra: cách đầu tiên có thể là làm cách
nào để trình bày một giải pháp đưa ra tại vị trí đầu tiên. Lấy ví dụ, một topo mạng có
thể được biểu diễn dưới dạng cách danh sách của các liên kết trong đó mỗi cặp liên kết
là một cặp nút (a,b). Việc giải mã danh sách đó thành một topo mạng đơn giản là vẽ
liên kết cho mỗi cặp nút trong danh sách đó. Nói cách khác, chúng ta có thể biểu diễn

gia như 1 node chưa được sử dụng để phát triển cây spanning. Khi tất cả các node đã
được kết nối như vậy, cặp node còn lại có thể được giải thích trực tiếp.
Tuy nhiên vấn đề chúng ta giải quyết sẽ liên quan đến vấn đề chi phí, do đó chi
phí của các liên kết cụ thể sẽ đóng vai trò quan trọng trong “hàm thích hợp”. Miền tri
thức cho chúng ta biết một số thuật toán nổi tiếng và nhanh chóng đưa ra đáp án cho
việc tìm cây spanning chi phí nhỏ nhất (Kruskal, 1956; Prim, 1957). Do đó nó có thể
làm cho ý nghĩa tốt, tùy thuộc vào các chi tiết khác nhau của vấn đề, để khởi tạo mỗi
13
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
giải pháp ứng viên với cây chi phí nhỏ nhất, và tất cả những gì chúng ta cần là đại diện
cho các liên kết chúng ta thêm vào cây này.
Có rất rất nhiều cách trong đó miền tri thức hoặc chuẩn đoán tồn tại có thể được
sử dụng để hưởng lợi từ phương pháp tiếp cận tìm kiếm địa phương cho vấn đề tối ưu
hóa. Một số về vấn đề này có thể cho chúng ta biết, ví dụ những loại biến đổi có cơ hội
tốt hơn dẫn đến hàng xóm tốt. Một phương thức chuẩn đoán hiện có cho biết nhanh
chóng giao các kênh trong mạng di động, có thể được sử dụng để cung cấp điểm khởi
tạo cho tìm kiếm địa phương mà cố gắng để tìm ra giải pháp tốt hơn.
1.3.2 Tìm kiến dựa trên tập hợp (Population-Based Search)
Một lựa chọn khác của thuật toán, hiện giờ đang rất phổ biến, được xây dựng
dựa trên ý tưởng về tìm kiếm địa phương bằng cách sử dụng tập hợp các giải pháp
“hiện tại” thay vì chỉ một. Có 2 cách mà điều này có khả năng tương cường cơ hội tìm
kiếm giải pháp tốt. Đầu tiên, khi chúng ta có 1 tập hợp, chúng ta có thể dành thời gian
1 cách hiệu quả để tìm kiếm trong nhiều khu vực lân cận khác nhau như một. Thuật
toán dựa trên tập hợp có xu hướng chia sẻ effort tính toán đến các giải pháp ứng viên
khác nhau trong 1 cách thiên vị bởi sự thích hợp tương quan của chúng. Đó là, nhiều
thời gian sẽ được dùng để tìm kiếm các vùng lân cận của các giải pháp tốt hơn là các
giải pháp trung bình.
Tuy nhiên, tối thiểu cần một ít thời gian cho việc tìm kiếm trong những miền
nghiệm ôn hòa hoặc thô, nên điều này dẫn đến việc tìm kiếm một đột biến đặc biệt tốt
trên đường đi, sau đó các cân bằng tải của nỗ lực tính toán sẽ được sửa đổi cho phù

đây là nơi mà các tải chia sẻ (load sharing) được thảo luận ở trên sẽ được áp dụng. Các
nghiệm ứng viên được tạo thành, càng nhiều cơ hội nó trở thành cha, và do đó có
nhiều cơ hội hơn để thuật toán tìm ra các vùng lân cận của nó. Có những kỹ thuật chọn
lựa khác nhau, hầu hết đều được tham số hóa để thay đổi mức độ để các tổ hợp cha
được tạo ra ưa thích hơn ( các áp lực chọn lọc). Bước 3 áp dụng các toán tử tái tổ hợp
hoặc đột biến, hoặc cả hai. Đây có tất cả các toán tử tái tổ hợp và đột biến, nhưng như
chung tôi gợi ý trên, những lợi ích thực sự đến khi một vài suy nghĩ đã được đưa vào
thiết kế cụ thể các loại toán tử sử dụng miền tri thức. Trong bước 4, nhớ rằng chúng ta
luôn duy trì một kích thước tổ hợp cố định. Vì vậy, nếu chúng ta có một tổ hợp 100,
nhưng 20 phần tử con được thêm vào, thì 20 của 120 phần tử phải được loại bỏ. Một
cách tiếp cận phổ biến nhất là chỉ đơn giản loại bò 20 phần tử ít phù hợp nhất với các
nhóm kết hợp, nhưng có một vài phương pháp khác; chúng ta có thể sử dụng công
nghệ được gọi là “dồn nén” (crowding), eg. De Jonh (1975), trong đó đa dạng đóng vai
15
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
trò quyết đinh về những giải pháp ứng viên để loại bỏ. Ví dụ, chúng ta chắc chắn sẽ
thích để loại bỏ giải pháp S có lợi và một giải pháp t ít phù hợp, nếu điều đó xảy ra là
trường hợp đó là một bản sao trong dân số, nhưng t là “mới”.
Ví dụ, chúng tôi chắc chắn sẽ thích để loại bỏ giải pháp tội ủng hộ một giải
pháp t ít phù hợp, nếu điều đó xảy ra là trường hợp đó salready có một bản sao trong
dân số, nhưng tis 'mới'. Cuối cùng, chúng ta phải chỉ ra một số vấn đề thuật ngữ. Có
rất nhiều thuật toán dựa trên dân số, và trong thực tế, họ thường được gọi là thuật toán
tiến hóa ( địa bàn ). Một thuật ngữ phổ biến được sử dụng là thuật toán di truyền, mà
đúng đề cập đến một gia đình của các phương pháp như vậy mà luôn luôn sử dụng một
nhà điều hành tái tổ hợp (Hà Lan, 1965; Goldberg, 1989), trong khi các gia đình khác
của thuật toán như vậy, gọi là lập trình tiến hóa ( Fogel, 1995) và tiến hóa chiến lược
( trở lại, 1996), xu hướng sử dụng đột biến một mình, nhưng khá thông minh về cách
họ sử dụng nó. Trong mọi trường hợp, một giải pháp ứng cử viên có xu hướng được
gọi là một phần tử của nó chromosomeand được gọi là gen.
1.4 Kỹ thuật tính toán thích ứng

hiện hành. Trong thực tế, chương tám và chín cả hai thảo luận về cách để làm điều này
liên quan đến các bảng định tuyến trong các mạng chuyển mạch gói.
Vì vậy, kỹ thuật thích ứng trong bối cảnh viễn thông có xu hướng liên quan đến
các hộp đen, hoặc các mô hình, mà bằng cách nào đó tìm hiểu và thích ứng với ' ẩn '
nhưng có thể phản ứng rất nhanh chóng và thích hợp khi được hỏi cho một quyết định.
Trong một số các chương có liên quan đến thích ứng, các kỹ thuật được sử dụng là
những người chúng ta đã thảo luận đã có trong phần 1.3, nhưng thay đổi một cách
thích hợp trong ánh sáng của sự cần thiết phải quyết định nhanh chóng. Mặc dù vậy, ở
những người khác, nhất định kỹ thuật quan trọng khác hiện đại được sử dụng, mà bây
giờ chúng tôi sẽ giới thiệu một thời gian ngắn.
Đây là sự ước lượng về thần kinh, logic mờ và lý thuyết trò chơi. Vai trò của
ước lượng thần kinh trong hoàn cảnh này là phát triển một mô hình ẩn, mô hình đó
nghiên cứu ( từ ví dụ) để làm thế nào có quyết định đúng đắn trong tập các trường hợp
khác nhau. Kết quả tạo ra sẽ như một mạng lưới thần kinh, sau đó để làm việc trực
tuyến như thế nào thì nhà sản xuất sẽ quyết định. Vai trò của logic mờ là đưa ra cách
để tạo ra các quy định vững chắc, đây là những quy định để ra quyết định. Điều này về
cơ bản là tạo ra cách giải quyết của hộp đen, giống như một mạng lưới thần kinh
nhưng với hoạt động bên trong khác nhau. Cuối cùng lý thuyết trò chơi sẽ đưa ra một
cách nhìn khác, đó là một kịch bản mạng năng động. Về cơ bản, nếu chúng ta xem một
17
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
số khía cạnh của quản lý mạng như là một 'trò chơi', một tập hợp các phương trình và
các mô hình được biết đến bắt đầu hoạt động, nó sẽ lần lượt cung cấp những phép tính
gần đúng của mạng năng động thực sự. Do đó, các quyết định quản lý mạng nào đó có
thể được hỗ trợ bằng cách sử dụng các phương trình này.
1.4.1. Tính toán hệ thần kinh
Tính toán hệ thần kinh (Rumelhart và MacClelland năm 1989; Haykin, 1998)
về cơ bản là một kỹ thuật phân loại mô hình, nhưng ngay từ cái nhìn đầu tiên nó đã
cho thấy khả năng ứng dụng rộng rãi hơn. Sức mạnh thực sự của phương pháp này
nằm trong thực tế và chúng ta không cần phải biết cách phân biệt các loại mô hình. Ta

MacClelland 1989), nhưng cũng có nhiều phiên bản hiện đại. Trên thực tế, các loại
mạng mà chúng tôi đã mô tả ngắn gọn ở đây chỉ là một trong nhiều loại có sẵn
(Haykin, 1999)1989), nhưng có rất nhiều biến thể hiện đại. Trên thực tế, các loại mạng
chúng ta đã mô tả một cách ngắn gọn ở đây chỉ là một trong nhiều loại có sẵn.
1.4.2 Logic mờ
Trong một số trường hợp chúng ta có thể nghĩ về các quy tắc hợp lệ cho miền
giá trị của vấn đề. Ví dụ, “nếu lưu lượng đông đúc, sử dụng node a’ và ‘nếu lưu lượng
rất đông đúc, sử dụng node b’. Tuy nhiên, những quy luật như vậy không thực sự hữu
ích nếu không có một cách tốt để quyết định rằng “đông đúc” hay “rất đông đúc” thực
sự có ý nghĩa gì. Trong cách tiếp cận hệ thống chuyên gia cổ điển, chúng ta sẽ áp dụng
ngưỡng được xác định trước cho những cái gọi là “biến ngôn ngữ”, và quyết định, ví
dụ, “lưu lượng đông đúc” có nghĩa là việc sử dụng liên kết trong câu hỏi là giữa 70%
và 85%. Điều này có vẻ tốt, nhưng không khó để thấy rằng việc sử dụng 69.5% có thể
là nguyên nhân gây ra các vấn đề; trong một kịch bản như vậy, quy luật có điều kiện là
“lưu lượng trung bình” (có thể là từ 55% đến 70%) sẽ được sử dụng, nhưng nó có thể
thích hợp hơn, và mang lại một kết quả tốt hơn là sử dụng “lưu lượng đông đúc”.
Logic mờ cung cấp một cách để sử dụng các biến ngôn ngữ để giải quyết vấn
đề ngưỡng một cách rất tự nhiên và mạnh mẽ. Thực tế, nó gần như loại bỏ nhu cầu
ngưỡng, thay vì giới thiệu những thứ gọi là “các chức năng thành viên”. Chúng ta
không còn có lưu lượng đông đúc hay trung bình. Thay vào đó, một giá trị lưu lượng
nhất định cho lưu lượng ở mức đông đúc và một giá trị cho mức độ trung bình. Các
mức độ phụ thuộc vào các giá trị số thực tế bằng cách các chức năng thành phần,
thường đơn giản là “chức năng hình tam giác”. Ví dụ, mức độ lưu lượng nặng có thể là
0 giữa 0% và 35% sử dụng, sau đó nó có thể tăng lên 1 giữa 35% và 75%, và sau đó
lại giảm xuống 0 giữa 75% và 90%. Chức năng thành phần (membership function) cho
biến ngôn ngữ “rất nặng” sẽ chồng chéo nhau với điều này, bởi vậy một giá trị lưu
lượng 82.5% có thể là ‘nặng’ đến mức 0.5 và ‘rất nặng’ đến mức 0.7.
19
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
Với mỗi điều kiện môi trường nhất định, các quy tắc khác nhau sẽ áp dụng

20
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
“hộp đen”.Trong một trường hợp, hộp đen là mạng tự nhiên, trường hợp khác, nó là
tập luật logic mờ hay 1 form được đặc tả trong bảng định tuyến.
Phần 3 xem xét phạm vi vấn đề, bao gồm phần mềm, chiến thuật, phương thức
quản lý lưu lượng. Phát triển phần mềm cũng có nhiều vấn đề trong lĩnh vực viễn
thông tuy nhiên nó cũng cung cấp nhiều giải pháp hợp lý trong việc cung cấp dịch vụ.
Các vấn đề cung cấp dịch vụ, trang bị trong mạng, đều cần tới những ưu điểm và tính
linh động của các phần mềm.Tuy nhiên các phần mềm cần nhiều thời gian để phát
triển. Phần 3 cũng chỉ ra tầm quan trọng của “chiến lược” bang cách xem xét các vấn
đề của việc quản lý 1 mạng động phức tạp. Các vấn đề bao gồm cấp phát dịch vụ, quản
trị luồng dữ liệu. Trong mỗi trường hợp, một cách tiếp cận dựa vào lý thuyết game
được tích hợp. Cuối cùng, ở phần 3 cũng chỉ ra vẫn đề quản lý băng thông trong cả
mạng cố định và mạng di động.
Chính vì vậy, chúng tôi đã bao quát một phạm vi rộng của các vấn đề tối ưu
mạng viễn thông trong quyển sách này. Chúng tôi đã trình bày một tập các vấn đề cần
được hoàn thiện. Các vấn đề tương tự trong việc kết nối các kĩ thuật lại cũng được
nhắc đến. Việc phát triển các kĩ thuật tính toán đã được tích hợp và cài đặt nhanh
chóng trong lĩnh vực viễn thông.
21
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
CHƯƠNG 2: THIẾT KẾ MẠNG HIỆU QUẢ SỬ DỤNG GIẢI
THUẬT DI TRUYỀN VÀ HEURISTIC
2.1 Giới thiêu
Tính hiệu quả của việc thiết kế mạng truyền thông là thử thách đối với vấn đề
tối ưu. Nó khó bởi các yêu cầu xung đột và phụ thuộc lẫn nhau cần được tối ưu để
nâng cao hiệu năng của mạng. Mục tiêu của các nhà thiết kế là đưa ra một mạng có chi
phí tối thiểu và luồng thông tin là cực đại giữa các cặp nút nguồn và kho (source-sink)
sử dụng mạng đồng thời. Một phương pháp thiết kế tối ưu cần đưa ra một hinh thái
mạng (topo mạng ) mà định tuyến hiệu quả các thông điệp trong một lượng thời gian

dung lượng của dòng đó. Ví dụ, một đường 6Mbps có chi phía là 2$/dặm, một đường
5Mbps có chi phía là 45$/dặm. Các loại đường thông tin liên lạc có sẵn trong năng lực
rời rạc, được thiết lập bởi các công ty điện thoại địa phương hoặc nhà cung cấp
phương tiện truyền thông. Việc tính phí tuân theo ‘economy of scale’ (giảm chi phí
sản phẩm khi sản phẩm được tiêu thụ với số lượng lớn), khi đó chi phí sẽ giảm khi
dung lượng cấc đường tăng. Ngoài ra, một số bảng phí có thể có một khoản phí cố
định cho mỗi loại đường, thêm vào một chi phí cho mỗi phí khoảng cách. Trong
trường hợp này, cả hai thành phần của chi phí dòng phải được kết hợp vào một đơn vị
chi phí trên mỗi kiểu đường, mỗi cạnh (vì mỗi cạnh có lẽ có chiều dài duy nhất). Chi
phí cố định được chia cho chiều dài của đường và bổ sung vào chi phí cho mỗi đơn vị
khoảng cách để mang lại một chi phí đơn vị cho mỗi loại đường, mỗi cạnh. Nếu một
đồ thị vô hướng G(V,E) có m cạnh và mỗi cạnh (i, j) có khoảng cách d(ij) và biểu diễn
l kiểu đường, mỗi loại có 1 đơn vị chi phí là u(ab) thì hàm mục tiêu của vấn đề tối ưu
là:
Với x(ab) số lượng kiểu đường b được lựa chọn cho cạnh a. Chú ý rằng mỗi
cạnh a có 2 cách biểu diễn khác nhau : (i, j) và ( j, i ) vì vậy d(ij) còn được gọi là d(a).
2.2.2 Luồng cực đại
Vì tổi thiểu chi phí và cực đại luồng là những mục tiêu trái ngược. Sẽ tạo thành
một ma trận R, trong đó r(st) biểu thị khả năng chịu tải liên tục tối thiểu đối với nút s
và t. Giá trị này còn được gọi là sự đòi hỏi (demand) giữa s và t. Tương tự như vậy
23
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
tổng đường giữa mọi cặp nút được đưa ra bởi ma trận luồng F và f(st) là luồng trong
G(V,E) từ nguồn s cho tới kho t, thì yêu cầu luông cực đại có thể viết như sau :

Chú ý vì R và F là hai ma trận đối xứng : f(st) = f(ts), r(st) = r(ts), f(ii) = r(ii) =
0; Khái niệm về đồ thị vô hướng và ma trận đối xứng ở đây được hỗ trợ bởi thực tế là
luồng vận chuyển vốn hai chiều (ví dụ, một đường T-2 đồng thời mang hai tín hiệu tại
6 Mbps trong cả hai hướng).
2.2.3 Luồng nhiều hàng hóa

của một cạnh được xác định. Trong một số mô hình, chiều dài có thể biểu thị khoảng
cách vật lý. Ở những mô hình khác, nó có thể chỉ ra sự chậm trễ (tính bằng giây) hoặc
đơn vị chi phí. Khi chiều dài của mỗi cạnh là một, sau đó con đường với số lượng tối
24
Thiết kế mạng hiệu quả sử dụng giải thuật di truyền và Heuristic
thiểu của 'bước nhảy' được chọn. Trừ khi có quy định khác, khoảng cách ngắn nhất
định tuyến sẽ được sử dụng bằng các phương pháp được trình bày trong chương này.
2.2.5. Dự phòng đủ (Sufficient Redundancy)
Trong một số trường hợp của các vấn đề thiết kế mạng, mục tiêu đạt được chi
phí tối thiểu được thực hiện bởi một đồ thị của kết nối tối thiểu. Ví dụ, một cây là một
đồ thị mà kết nối tất cả các nút với một số lượng tối thiểu của các cạnh. Tuy nhiên, bất
kỳ nút duy nhất (hoặc cạnh) thất bại sẽ ngắt kết nối mạng. Hai tuyến đường được cho
là cạnh rời nhau nếu họ kết nối cùng một nguồn và đích và không có cạnh chung.
Tương tự như vậy, hai tuyến đường được cho là node- disjoint nếu các nút duy nhất
chúng chia sẻ là nguồn và đích. Trong trường hợp điểm duy nhất là phổ biến trong các
mạng, một phương pháp thiết kế được chấp nhận phải cung cấp đủ dự phòng để tồn tại
thất bại nút duy nhất. Tuy nhiên, bất kỳ dư thừa nào cũng làm tăng chi phí của mạng.
Để cân bằng các mục tiêu mâu thuẫn nhau, tối thiểu là hai con đường node -disjoint
phải tồn tại giữa mỗi cặp nút. Trong trường hợp của một sự thất bại mạng điểm duy
nhất, lưu lượng truy cập có thể được gửi đi cùng một con đường thay thế, mặc dù với
tốc độ chậm hơn nhiều (trong đó, rất có thể, sẽ không tiếp tục đáp ứng các yêu cầu tối
thiểu chế về năng lực trong R).
2.2.6 Độ trễ chấp nhận
Sự chậm trễ chi nhánh trung bình, T, là một thước đo mạng lưới rộng khắp mà
các biện pháp số tiền trung bình của thời gian (tính bằng giây) mà một gói tin sẽ chờ
đợi trước khi được truyền dọc theo một cạnh trong mạng. Kleinrock (1964) đã phát
triển một mô hình được chấp nhận rộng rãi cho sự chậm trễ trong các mạng truyền
thông, trong đó mỗi cạnh được mô phỏng như một hàng đợi M/M/1 độc lập trong một
mạng lưới các hàng đợi. Mỗi hàng đợi có thời gian phục vụ trung bình phân theo cấp
số nhân, và một tỷ lệ xuất hiện trung bình của các gói mới tuân theo một phân phối