HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA QUỐC TẾ & ĐÀO TẠO SAU ĐẠI HỌC
  
MÔN HỌC: KỸ THUẬT TỐI ƯU
CHUYÊN ĐỀ:
ĐIỀU KHIỂN LUỒNG THÔNG MINH THEO KHUÔN KHỔ LÝ THUYẾT TRÒ
CHƠI
GVHD: TS. Lê Nhật Thăng
HV:
Lớp: M11CQCK01-B
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 2
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 3
MỤC LỤC
MỤC LỤC 3
MỞ ĐẦU 13
Sự phức tạp trong phạm vi rộng lớn của các mạng viễn thông hiện đại ngày nay cung cấp cho chúng ta
nhiều thách thức cũng như những cơ hội mới. Trong chương này, chủ yếu chúng ta tập chung vào những
thách thức liên quan tới việc tối ưu hóa trong mạng viễn thông 15
Vậy tối ưu hóa mạng viễn thông là gì? 15
Đó là việc tìm ra phương pháp “tốt nhất” trong các phương pháp có thể giải quyết được bài toán. Ví dụ,
có một số phương pháp để thiết kế cấu trúc liên kết của mạng dữ liệu khu vực cho một công ty lớn. Làm
thế nào để tìm ra một phương pháp đặc biệt tốt trong tất cả các phương pháp trên? ví dụ khác là làm thế
nào tìm ra cách tốt nhất để gán các kênh tần số cho người dùng trong mạng di động. Tuy rằng mỗi
phương pháp đều có hạn chế nhưng cuối cùng chúng ta vẫn sẽ tìm ra một phương pháp “tốt nhất” 15
Đặc biệt, có một số các công nghệ phần mềm mới được nhắm vào các giải pháp tối ưu hóa hiện đang
được sử dụng trong các ngành công nghiệp, có tiềm năng và hiệu quả rất lớn giải quyết nhiều vấn đề
trong ngành viễn thông. Các kỹ thuật sử dụng bao gồm các phương pháp tìm kiếm cục bộ như mô phỏng
luyện kim (Aarts and Korst, 1989), tìm kiếm tabu (Glover, 1989; 1989a), các kỹ thuật tìm kiếm
‘population-based’ như thuật toán di truyền (Holland, 1975; Goldberg, 1989), quá trình tiến hóa chiến
lược (Schwefel, 1981; Back, 1996), lập trình tiến hóa (Fogel, 1995), lập trình di truyền (Koza, 1992).
Chúng ta sẽ tìm hiểu lần lượt qua những chủ đề này ở các phần dưới của chương này 15

cổ điển tốt hơn các phương pháp hiện đại 16
Quan sát này được dựa trên một khía cạnh quan trọng của việc giải quyết vấn đề tối ưu hóa. Bạn càng
biết về một kỹ thuật đặc biệt mà bạn đang áp dụng, có thể sẽ tốt hơn khi bạn điều chỉnh và khai thác
bằng cách khác nó để có được kết quả tốt nhất. 17
Trong phần này chúng ta chỉ cung cấp cơ sở chi tiết của một vài thuật toán tối ưu hiện đại, không đưa ra
thông tin đầy đủ đề giải các bài toán cụ thể. Các kỹ thuật chủ yếu rơi vào hai nhóm: tìm kiếm cục bộ và
tìm kiếm dựa trên quần thể 17
Hãy tưởng tượng bạn đang cố gắng để giải quyết một vấn đề P, và bạn có một tập lớn S các giải pháp
tiềm năng cho vấn đề này. Bạn không thực sự có tập hợp S, vì nó là quá lớn để liệt kê đầy đủ. 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 kết nối cấu trúc liên kết
cho một mạng, ứng cử viên của giải pháp là s, s', s", và như vậy, là ứng cử viên cụ thể cấu trúc liên kết mà
bạn đã đưa ra bằng cách nào đó. Ngoài ra, hãy tưởng tượng rằng bạn có hàm chức năng f(s) cho một số
điểm, đưa ra một ứng cử viên giải pháp. Các số điểm, các giải pháp tốt hơn. Ví dụ, nếu chúng ta cố gắng
để tìm thấy các 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 của liên kết
thất bại giữa hai nút đặc biệt quan trọng 17
Dưới đây chúng tôisẽ mô tả cơ bản tìm kiếm cục bộ. Trước khi tìm hiểu về chúng thì ta hãy xem xét một
trong những phương pháp tìm kiếm đơn giản cục bộ, được gọi là hillclimbing (leo núi), theo các bước
dưới đây: 17
Bước 1(Bắt đầu): tạo ra một giải pháp, ứng cử viên ban đầu (có lẽ là ngẫu nhiên); gọi giải pháp này là giải
pháp hiện hành c, Đánh giá c 17
Bước 2: Biến đổi c để tạo ra một m đột biến, và đánh giá các m 17
Bước 3: Nếu hàm f(m) là tốt hơn hoặc bằng với hàm f(c), thì ta thay thế c bởi m (tức là c bây giờ là một
bản sao của m) 17
Bước 4:Đến khi đạt được một tiêu chuẩn thì ta kế thúc kết thúc, sau đó quay trở về bước 2 17
Bây giờ chúng ta sẽ đi tìm hiểu qua các thuật toán cục bộ chính: 17
Phương pháp luyện thép giống như phương pháp leo đồi (hillclimbing). Sự khác biệt chỉ là ở việc nó dùng
một cặp thông số, thêm vào bước 1 và ở điểm chính trong bước 3chúng được thay đổi việc sử dụng các
tham số: 18
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 5
Bắt đầu: Tạo và đánh giá một giải pháp ban đầu (có lẽ là ngẫu nhiên); gọi là giải pháp hiện hành c, tham

chuyến đến.Các tính năng phân biệt của tìm kiếm Tabu là làm thế nào lựa chọn được việc thực hiện này.
19
Chú ý tìm kiếm Tabukhông phải là chỉ đơn giản là một vấn đề của việc lựa chọn các lân cận của những
thử nghiệm thích hợp nhất.Tìm kiếm Tabu cũng sẽ đưa bạn vào một tài khoản và tập các đột biến. Ví dụ,
nếu vị trí lân cận tốt nhất của giải pháp hiện tại của bạn là có thể đạt được bằng cách thay đổi đầu kia
của một liên kết đang nổi lên từ nút k, nhưng chúng tôi một động thái đã được thực hiên gần đây như
vậy trong một phiên trước đó, sau đó một người hàng xóm khác nhau có thể là lựa chọn thay thế. Sau
đó, một lần nữa, ngay cả khi di chuyển tốt nhất hiện nay là của một loại đã được sử dụng gần đây, và
thường là không được phép (tức là coi là "điều Tabu '), tìm kiếm Tabu cung cấp một cơ chế dựa trên tiêu
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 6
chuẩn nguyện vọng, mà sẽ cho phép chúng ta lựa chọn mà nếu những lân cận trong câu hỏi là đủ tốt hơn
so với các giải pháp hiện tại (nói tới) 19
Do đó bất kỳ thực hiện tìm kiếm Tabu nào duy trì một số hình thức của bộ nhớ, ghi lại các thuộc tính
nhất định của động thái gần đây.Những thuộc tính này phụ thuộc nhiều vào vấn đề, và điều này là một
phần của nghệ thuật ứng dụng tìm kiếm Tabu. 19
Ví dụ, nếu chúng ta đang cố gắng để tối ưu hóa một cấu trúc liên kết mạng, một loại đột biến của nhà
điều hành sẽ làm thay đổi các hệ thống cáp liên kết với các liên kết giữa các nút 1 và b. Trong thực hiện
tìm kiếm Tabu của chúng ta, chúng ta có lẽ sẽ ghi lại chỉ có một thực tế rằng chúng ta đã di chuyển một
thay đổi hệ thống cáp 'lặp đi lặp lại tôi, hoặc nếu không, chúng ta có thể hoặc bổ sung, chỉ cần ghi lại
thực tế rằng chúng ta đã thực hiện một thay đổi kết hợp với một nút và khác liên kết với nút b. Nếu
chúng ta chỉ ghi lại các loại cũ của thuộc tính, sau đó trong tương lai gần có thể thay đổi hệ thống cáp, di
chuyển sẽ không được phép, độc lập với những gì các nút đã được tham gia.Nếu chúng ta ghi nhận chỉ có
các loại sau của thuộc tính, sau đó gần như thay đổi tiềm năng trong tương lai liên quan đến a / và b có
thể là không được phép, nhưng thay đổi hệ thống cáp, di chuyển, cho mỗi gia nhập sẽ được chấp nhận.
19
Ghi chú ngắn gọn của chúng tôi về loại tìm kiếm mô phòng và Tabu minh họa rằng các khía cạnh quan
trọng của một phương pháp tìm kiếm cục bộ tốt là quyết định mà người hàng xóm để di chuyển đến. Tất
cả các phương pháp tìm kiếm cục bộ sử dụng các ý tưởng cơ bản mà di chuyển cục bộ gần như luôn luôn
là một ý tưởng tốt, tức là nếu bạn có một giải pháp tốt hiện nay, có thể là một một tốt hơn gần đó, và có
thể dẫn đến những cái tốt hơn, và vv. Tuy nhiên, nó cũng rõ ràng mà đôi khi, có lẽ thường, chúng ta phải

đổi danh sách các đại diện nút đôi, đảm bảo rằng tất cả các giải pháp ứng cử viên có chứa một cây bao
trùm cho mạng, và do đó hiện đang kết nối. Một cách để làm điều này là liên quan đến việc giải thích đầu
tiên cặp node gián tiếp. Thay vì (a, b) chỉ ra rằng mạng lưới này có chứa một liên kết giữa a và b, nó thay
vào đó sẽ có nghĩa là nút ATH kết nối sẽ được kết nối với các nút không có liên quan BTH. Bằng cách này,
mỗi cặp nút tiếp theo cho thấy làm thế nào để tham gia vào một nút như được nêu ra không sử dụng
một cây trải rộng đang phát triển. Khi tất cả các nút được kết nối như vậy, còn lại nút cặp có thể được
giải thích trực tiếp 21
Vấn đề còn tốt hơn nữa là chúng ta có thể có địa chỉ có thể sẽ liên quan đến vấn đề chi phí, và chi phí của
các liên kết cụ thể sẽ đóng một vai trò quan trọng trong chức năng hoặc trung tâm. Sau đó cho chúng ta
biết rằng một số thuật toán cũng được biết đến và nhanh chóng thoát ra mà tìm thấy một cây minmal đề
cập tới vấn đề chi phí kéo dài (Kruskal, 1956; Prim, 1957). Vì vậy, để tốt hơn là tùy thuộc vào các chi tiết
khác nhau của vấn đề trong tay ta có, để khởi tạo mỗi giải pháp ứng cử viên với một cây chi phí tối thiểu,
và tất cả những gì chúng ta cần để đại diện cho các liên kết mà chúng ta thêm lên cây này 21
Có một số cách khác trong lĩnh vực kiến thức hoặc chẩn đoán hiện tại có thể được sử dụng để hưởng lợi
một cách tiếp cận tìm kiếm cục bộ cho một vấn đề tối ưu hóa. Một cái gì đó về vấn đề này có thể cho
chúng ta biết, ví dụ như là những loại đột biến có một cơ hội tốt hơn dẫn đến lân cận tốt. Một phương
pháp khám phá hiện có, nhanh chóng phân công các kênh trong một mạng lưới điện thoại di động, có
thể được sử dụng để cung cấp điểm khởi đầu cho một tìm kiếm cục bộ cố gắng tìm giải pháp tốt hơn 22
Đây là một phương cách của thuật toán thay thế, bây giờ trở nên rất phổ biến, được xây dựng trên ý
tưởng tìm kiếm địa phương bằng cách sử dụng quần thể. Có hai phương cách để tăng cường các cơ hội
của việc tìm kiếm giải pháp tốt. Đầu tiên, kể từ khi chúng tôi có một quần thể, chúng ta có thể dành
nhiều thời gian tìm kiếm trong các khu vực khác nhau cùng một lúc. Một thuật toán dựa trên quần thể có
xu hướng chia sẻ các nỗ lực tính toán đến các giải pháp ứng cử khác nhau . Một phần thời gian sẽ được
chi tiêu tìm kiếm trong khu vực của các giải pháp trung bình và điều này sẽ dẫn đến việc tìm kiếm được
đột biến đặc biệt , sau đó cân bằng tải nỗ lực tính toán sẽ được sửa đổi phù hợp. 22
Một cơ hội khác được cung cấp bởi các kỹ thuật dựa trên quần thể là chúng ta có thể thử vận hành tái tổ
hợp. Đây là những cách sản xuất đột biến, nhưng lần này từ hai hay nhiều giải pháp, chứ không phải chỉ
một. Do đó kết quả có thể được gọi là tái tổ hợp, chứ không phải là một đột biến. Tái tổ hợp là một
phương pháp cung cấp một cách lựa chọn tốt trong không gian rộng lớn của khả năng. 22
Ví dụ, nếu hai giải pháp cha mẹ là mỗi một vector của các yếu tố k, một nhà điều hành tái tổ hợp được

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, năm 1965, Goldberg, năm
1989), trong khi các tổ chức khác của các thuật toán gọi là tiến hóa lập trình (Fogel, 1995) và sự tiến
hóachiến lược (Quay lui, năm 1996), xu hướng sử dụng đột biến, nhưng được bỏ eclever 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à nhiễm sắc thể và các
yếu tố của nó được gọi là gen 23
Để giải quyết nhu cầu tối ưu hóa vốn có của môi trường viễn thông, việc trực tiếp sử dụng các kỹ thuật
tối ưu hóa địa phương hoặc dân số dựa trên đôi khi có thể là khá phù hợp. Bởi vì nó có thể mất quá lâu
để đưa một giải pháp tốt, và như vậy từ thời gian đến giải pháp, vấn đề đã được thay đổi ! 24
Những gì chúng ta cần thay vì trong bối cảnh này là một cách để đưa ra quyết định rất nhanh, nhưng rất
tốt,. Ví dụ, để quyết định những bước nhảy tiếp theo tốt nhất là cho một gói tin đến một nút đích d,
chúng ta có lẽ có thể chạy một mô phỏng của các mạng cho các mô hình tầng vận chuyểnhiện hành hiện
nay và ước tính thời gian đến khả năng ở các điểm đến cho cho có thể bước nhảy tiếp theo. Kết quả mô
phỏng như vậy sẽ cung cấp cho chúng tôi với một sự lựa chọn đầy đủ thông tin, và sau đó chúng tôi có
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 9
thể gửi các gói dữ liệu một cách thích hợp trên con đường của nó. Bây giờ, nếu chúng tôi có thể ở trên
trong một vài micro giây, chúng ta sẽ có một chiến lược định tuyến gói tin phù hợp và rất có lợi nhuận. 24
Tuy nhiên, kể từ khi nó có thể sẽ mất vài giờ để làm một mô phỏng chính xác bằng cách sử dụng các loại
sức mạnh xử lý và bộ nhớ thường có sẵn các thiết bị chuyển mạch mạng, trong thực tế nó là một ý tưởng
vô lý! Thay vào đó, chúng tôi cần một số cách làm cho quyết định đúng đắn một cách nhanh chóng,
nhưng quyết định bằng cách nào đó sẽ đưa vào tài khoản các trường hợp hiện hành. Lý tưởng nhất,
chúng tôi đang tìm kiếm một 'hộp đen', khi cho ăn với một câu hỏi và một số chỉ tiêu môi trường, cung
cấp một câu trả lời hợp lý và ngay lập tức. Một ví dụ của một hộp đen như là một bảng định tuyến của
các loại thường thấy trong các mạng chuyển mạch gói. Câu hỏi được hỏi bởi một gói tin truyền thông là:
cuối cùng tôi muốn để có được d, vì vậy mà tôi nên đi tiếp theo? Bảng định tuyến, thông qua một tra cứu
đơn giản được lập chỉ mục của d, rất nhanh chóng cung cấp một câu trả lời và gửi nó theo cách của mình.
24
Những rắc rối với điều này, tất nhiên, là nó về cơ bản là không thích nghi. Trừ khi các giao thức quản lý
mạng tiên tiến nhất định trong hoạt động, bảng định tuyến sẽ luôn luôn cung cấp cho các câu trả lời
tương tự, ngay cả khi các liên kết trở đi từ hop tiếp theo đề nghị d được rất nhiều tắc nghẽn tại thời
điểm này. Hộp đen của chúng tôi do đó thường được thay đổi bằng cách nào đó, và thích nghivới điều

hiện ở tất cả. Chúng ta có thể đào tạo một mạng lưới trung tâm để dự đoán những rủi ro xấu, tuy nhiên,
chỉ đơn giản bằng cách cung cấp một bộ các ví dụ được biết đến, chẳng hạn như p người từ r khu vực với
tiền lương và nghề y mặc định trên một khoản vay kích thước m; q người với mức lương t Với
những thứ như p, r, s, …như đầu vào, mạng lưới trung tâm dần dần điều chỉnh trong nội bộ một cách
cuối cùng sản xuất sản lượng chính xác (dấu hiệu cho thấy khả năng mặc định cho mượn) cho mỗi người
trong số các ví dụ được đào tạo. Đáng chú ý, và rất hữu ích, sau đó chúng tôi có thể mong đợi các mạng
trung tâm để cung cấp dự đoán tốt khi cung cấp đầu vào trước đó không thấy 26
Bên trong, một mạng lưới trung tâm là một cấu trúc rất đơn giản, nó chỉ là một bộ sưu tập của các nút
với liên kết liên kết đầu vào và đầu ra, mà không xử lý đơn giản: nó cho biết thêm các con số đến thông
qua các liên kết đầu vào của nó, mỗi trọng bằng một giá trị sức mạnh liên kết với các liên kết đến thông
qua, sau đó quá trình này tổng hợp (thường là chỉ để biến đổi nó với một số giữa 0 và 1), và gửi kết quả
qua các liên kết đầu ra của nó. Mạng lưới trung tâm của cái gọi là "thức ăn về phía trước là một bộ sưu
tập của các nút, tổ chức thành các lớp. Các đầu vào vấn đề đến như là đầu vào cho mỗi lớp đầu tiên của
các nút, các kết quả đầu ra từ lớp này thức ăn vào lớp thứ hai, và như vậy, mặc dù thường chỉ có ba lớp.
26
Rõ ràng, con số đó đi ra vào cuối phụ thuộc vào những gì đến các lớp đầu vào, một cách mật thiết xác
định bởi trọng lượng vào các liên kết. Precisley các trọng lượng bị thay đổi dần dần trong một thời trang
nguyên tắc của quá trình đào tạo. Cổ điển, điều này là một phương pháp gọi là backpropagation
(Rumelhart và MacClelland, 1989), nhưng có nhiều phiên bản hiện đại. Thật vậy, các loại của mạng 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) 26
Trong một số trường hợp, chúng ta có thể nghĩ ra các quy tắc ban đầu cho miền vấn đề của chúng ta. Ví
dụ, nếu giao thông là nặng, sử dụng nút a, và nếu giao thông là rất nặng nề, sử dụng nút b. Tuy nhiên,
quy định như vậy không phải là rất hữu ích mà không có một cách tốt để quyết định những gì nặng
"hoặc" rất nặng "thực sự có nghĩa là sử dụng liên kết, ví dụ. Trong một phương pháp tiếp cận hệ thống
cổ điển chuyên gia, chúng tôi sẽ áp dụng ngưỡng xác định trước cho những ngôn ngữ "biến" cái gọi là, và
quyết định, ví dụ, đó là giao thông là nặng "có nghĩa là việc sử dụng các liên kết trong câu hỏi là giữa 70%
và 85%. Điều này có thể có vẻ tốt đẹp, nhưng nó không phải là khó khăn để thấy rằng 69,5% sử dụng có
thể gây ra vấn đề, trong kịch bản như vậy, các quy định có điều kiện là 'giao thông vừa phải (55% đến
70%, có lẽ) sẽ được sử dụng, nhưng nó có thể có thích hợp hơn, và mang lại một kết quả tốt hơn, sử
dụng giao thông nặng 27

một phương pháp luật xấp xỉ mới sử dụng biểu diễn hàm thuộc tham số gia tử ngôn ngữ. Hiện nay có
nhiều nhà nghiên cứu đang sử dụng Đại số gia tử để khắc phục một vài nhược điểm của logic mờ. Để
hiểu thêm về Đại số gia từ bạn có thể đọc các tài liệu tiếng việt của tác giả Nguyễn Cát Hồ(do phạm vi
tiểu luận này không tập chung nhiều vào phần này nên chúng tôi không trình bày chi tiết về các lý thuyết
logic mờ cũng như giới thiệu tới Đại số gia từ) 28
Cuối cùng, lý thuyết trò chơi cung cấp một cách khác để nhìn vào các loại ertain hoàn thành, năng động,
các vấn đề liên quan đến commuications, đặc biệt là về quản lý mạng và cung cấp dịch vụ. Hãy xem xét
quá trình quyết định phức tạp liên quan đến quyết định về thuế cho các thiết lập cho kết nối cuộc gọi
hoặc cung cấp dịch vụ dữ liệu trong một môi trường mạng năng động, liên quan đến cạnh tranh với
nhiều nhà cung cấp dịch vụ khác. Theo giả định, sự năng động của mạng, bao gồm bộ nhất định, ví dụ,
hoạt động liên tục của người sử dụng chuyển đổi cho các nhà cung cấp dịch vụ khác nhau đôi khi dựa
trên mức thuế mới được quảng cáo, sẽ chịu sự tương đồng đáng kể với các mô hình khác nhau của cuộc
thi đã được phát triển trong lý thuyết sinh học, kinh tế, và các khu vực khác. Đặc biệt, phương trình nhất
định sẽ được áp dụng cho phép dự đoán xem một đề xuất mới thuế quan sẽ dẫn đến một tình hình
không ổn định (ở đâu, ví dụ, nhiều khách hàng hơn sẽ chuyển sang dịch vụ mới của bạn hơn bạn có thể
đối phó với) 28
Đặc biệt là trong các mạng trong tương lai, nhiều quyết định quản lý khá phức tạp có thể cần phải được
thực hiện một cách nhanh chóng và thường xuyên. Ví dụ, để duy trì thị phần, mức thuế mới có thể cần
phải được thiết lập theo giờ, và hoàn toàn tự động, trên cơ sở của hoạt động hiện hành về đăng ký mới,
khách hàng mất hiệu lực, và tin tức của các mức thuế mới được thiết lập bởi các nhà cung cấp dịch vụ
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 12
đối thủ. Phương pháp tiếp cận lý thuyết trò chơi được phát triển bởi một số người đóng góp vào cuốn
sách này sẽ có một vai trò lớn hơn để chơi trong các tình huống như vậy, có thể trở thành công cụ trung
tâm trong một loạt các kỹ thuật tối ưu hóa thích nghinhằm vào một số vấn đề cung cấp dịch vụ 29
Kỹ thuật chẩn đoán và thích nghi được áp dụng cho một loạt các vấn đề liên quan đến viễn thông tối ưu
hóa 29
Qua chương một chúng ta đã tìm hiểu được một số nội dung: 29
+ Các khái niệm tối ưu hóa trong viễn thông 29
+ Các vấn đề động và thích nghi 29
+ Các mô hình kỹ thuật chẩn đoán với 2 cách tìm kiếm chính: Tìm kiếm cục bộ và tìm kiếm dựa trên quần

truyền thông hiện có, một cơ cấu giá nhất thiết phải tùy tiện áp đặt bài trên thực tế. Bằng
cách tham gia một cách tiếp cận thị trường dựa trên hệ thống phân phối, Michigan Marx
Project ( tìm kiếm giải pháp để cho phép phân bổ nguồn
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 14
lực thích ứng của các hệ thống thông tin quy mô lớn. Một bộ sưu tập rất hữu ích của liên
kết và các nguồn lực khác nhau về kinh tế mạng và các vấn đề liên quan được duy trì tại
Berkeley của HR Varian
( Tuy nhiên, có một số
ít tác phẩm được công bố mà cố gắng để giải quyết điều khiển nhận cuộc gọi cũng như
quản lý lưu lượng trong các mạng viễn thông từ một quan điểm lý thuyết của trò chơi xem
bằng cách sử dụng trí thông minh tính toán. Chúng tôi tổ chức công việc của chúng tôi
thành hai chương. Chương đầu tiên là giới thiệu các kỹ thuật chẩn đoán trong viễn thông,
chương thứ hai bao gồm hai phần: Phần đầu tiên giành riêng cho điều khiển nhận kết nối
(CAC) xử lý trong mạng lưới máy ATM. Bằng cách năng động CAC như một vấn đề chia
sẻ tài nguyên, chúng tôi sử dụng một mô hình trò chơi hợp tác với các hình thức sản phẩm
của một sự kết hợp một số sở thích của người dùng để tối ưu hóa khả năng chặn cuộc gọi
trong khi duy trì QoS đàm phán ở giai đoạn thiết lập cuộc gọi. Sau khi thu được những
hình thức sản phẩm của các chức năng ưu tiên người sử dụng, chúng tôi sử dụng một
thuật toán di truyền để tối ưu hóa hàm mục tiêu này để duy trì chia sẻ công bằng trong
giai đoạn truyền tải lưu lượng truy cập. Phần thứ hai của các mô hình làm việc của chúng
tôi không hợp tác hành vi người dùng trong quá trình phân bổ tài nguyên theo một khuôn
khổ bán đấu giá tổng quát. Chúng tôi đề xuất một quy tắc bán đấu giá tối ưu dẫn đến trạng
thái cân bằng trong một trò chơi năng động lặp đi lặp lại. Chúng tôi cũng sử dụng các
mạng thần kinh để mô hình hóa các chiến lược người sử dụng trong đấu thầu, và một thời
gian ngắn thảo luận về sự hình thành của kiến thức phổ biến trong các trò chơi lặp đi lặp
lại và hiệu quả phân bổ. Các đặc điểm phổ biến cho hai phần này là chúng tôi sử dụng các
kỹ thuật tình báo một số tính toán để giải quyết các mô hình phức tạp và các vấn đề tối ưu
hóa trong phân bổ tài nguyên.
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 15
CHƯƠNG 1: GIỚI THIỆU CÁC KỸ THUẬT CHẨN ĐOÁN TRONG VIỄN

trên các 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 vừa phải 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 lưới rộng lớn điểm-điểm
cơ bản. Theo truyền thống, các bảng định tuyến tại mỗi nút được sử dụng để tìm hop tiếp
theo là tốt nhất cho một gói tin dựa vào đ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, như việc nhìn vào các mô hình
giao thông tổng thể để xác định các bảng định tuyến thích hợp cho mỗi nút, vì vậy mà sự
tắc nghẽn và sự chậm trễ có thể được giảm thiểu.
Chạy lặp các các kỹ thuật tối ưu hóa là một trong những cách có thể để tiếp cận
vấn đề năng động, nhưng nó là một cách không thích hợp cho lắm khi giải pháp tốt cần
nắm bắt rất nhanh, khi môi trường thay đổi rất nhanh chóng. Thay vào đó, một phạm vi
khác của kỹ thuật tính toán hiện đại thường thích hợp cho các vấn đề như vậy. Chúng ta
gọi kỹ thuật này là kỹ thuật thích ứng.
III. MÔ HÌNH CÁC KỸ THUẬT CHẨN ĐOÁN(HEURISTIC)
Một loạt các phương pháp nổi tiếng trong lĩnh vực nghiên cứu tối ưu hoá, như lập
trình động, lập trình số nguyên, dó là các phương pháp truyền thống được sử dụng để giải
quyết các loại khác nhau của các vấn đề tối ưu hóa. Tuy nhiên, một cộng đồng lớn gồm
các nhà khoa học máy tính và các nhà nghiên cứu trí tuệ nhân tạo đã dành rất nhiều nỗ lực
đưa ra thành những ý tưởng hiện đại được gọi là "metaheuristics" hoặc "heuristic ". Sự
khác biệt cơ bản của phương pháp hiện đại là dễ dàng được áp dụng hơn so với các
phương pháp cổ điển.
Đó không thể nói là phương pháp hiện đại tốt hơn phương pháp cổ điển mà phải
tùy theo các trường hợp mà có thể áp dụng cả hai phương pháp:
• Một chuyên gia metaheuristics so sánh hai loại kỹ thuật: các phương pháp hiện
đại nhanh hơn so với phương pháp cổ điển.
• Một chuyên gia nghiên cứu hoạt động phương pháp cổ điển so sánh hai loại kỹ
thuật: các phương pháp cổ điển tốt hơn các phương pháp hiện đại.
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 17
Quan sát này được dựa trên một khía cạnh quan trọng của việc giải quyết vấn đề
tối ưu hóa. Bạn càng biết về một kỹ thuật đặc biệt mà bạn đang áp dụng, có thể sẽ tốt hơn

Bắt đầu: Tạo và đánh giá một giải pháp ban đầu (có lẽ là ngẫu nhiên); gọi là giải
pháp hiện hành c, tham số nhiệt độ khởi tạo T, độ làm mát r (0 <r <1).
Thuật toán bao gồm 4 bước chính như sau:
Bước 1: Biến đổi c để tạo ra một m đột biến, đánh giá m.
Bước 2: Nếu hàm test(f(m), f(c), T) đánh giá đúng sự thật, thì thay thế c bởi m(Ví
dụ: c bây giờ là một bản sao của m).
Bước 3: Cập nhật các thông số nhiệt độ (ví dụ như T trở thành rT)
Bước 4:Khi đạt được tiêu chí thì dừng sau đó trở về bước 2.
Câu hỏi đặt ra là liệu điều gì sẽ xảy ra trong quá trình mô phỏng luyện kim khi
chúng ta cho phép có sự biến đổi(ngay cả khi giải pháp đó không tốt hơn các giải pháp
hiện hành). Chúng ta sẽkhông thực hiện điều này bới có ít có khả năng để thực hiện nếu
như đột biến như thế xảy ra. Thuật toán có hiệu quả toàn cục, có cơ hội tốt thoát khỏi cục
bộ tối ưu, do đó có thể tìm kiếm các khu vực tốt hơn của các không gian sau. Điều cơ bản
là phải hướng đến các vùng tốt hơn. Điều này được thể hiện ở hàm test trong bước 3.
Ví dụ một hàm test được thực hiện như sau: e
( f (m)-f (c))/T
Giả định là chúng ta đang cố gắng để tối đa hóa chi phí (Nếu không chỉ cần chuyển
đổi hai hàm f(m) và f(c)). Nếu như giải pháp biến đổi tốt hơn hoặc bằng giải pháp hiện
hành, biểu thức trên sẽ lớn hơn hoặc bằng 1. Nếu biến đổi không tốt thì kết quả sẽ nhỏ
hơn 1, và biến đổi không tốt hơn sẽ gần đến 0. Do đó, kết quả củabiểu thức này được sử
dụng như xác suất. Một số ngẫu nhiên được tạo ra(rand), 0 < rand < 1, test ở bước 3 sẽ
kiểm tra biểu thức trên nhỏ hơn hoặc bằng rand (chúng ta chấp nhận biến đổi). T là tham
số "nhiệt độ". Nó bắt đầu tăng cao và giảm dần (xem bước 4) với thời gian. Như ta có thể
cho biết từ biểu thức trên, điều này có nghĩa là xác suất chấp nhận đột biến tồi tệ hơn
cũng sẽ giảm theo thời gian. Chính bởi thế mà mô phỏng luyện kim là phương pháp rất
mạnh, mặc dù khá khó khăn để có được các thông số đúng (xem thêm Dowsland (1995)).
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 19
1.2 Tìm kiếm Tabu
Một cách khác để thực hiện việc tối ưu cục bộ được cung cấp bởi công cụ tìm kiếm
Tabu (Glover năm 1989; 1989a; Glover và Laguna, 1997). Có rất nhiều khía cạnh tinh tế

ta ghi nhận chỉ có các loại sau của thuộc tính, sau đó gần như thay đổi tiềm năng trong
tương lai liên quan đến a / và b có thể là không được phép, nhưng thay đổi hệ thống cáp,
di chuyển, cho mỗi gia nhập sẽ được chấp nhận.
1.3 Tìm kiếm cục bộ Artful
Ghi chú ngắn gọn của chúng tôi về loại tìm kiếm mô phòng và Tabu minh họa rằng
các khía cạnh quan trọng của một phương pháp tìm kiếm cục bộ tốt là quyết định mà
người hàng xóm để di chuyển đến. Tất cả các phương pháp tìm kiếm cục bộ sử dụng các
ý tưởng cơ bản mà di chuyển cục bộ gần như luôn luôn là một ý tưởng tốt, tức là nếu bạn
có một giải pháp tốt hiện nay, có thể là một một tốt hơn gần đó, và có thể dẫn đến những
cái tốt hơn, và vv. Tuy nhiên, nó cũng rõ ràng mà đôi khi, có lẽ thường, chúng ta phải
chấp nhận thực tế rằng chúng ta chỉ có thể tìm thấy các cải thiện các giải pháp hiện tại
bằng cách tạm thời chúng ta hy vọng di chuyển đến những người tồi tệ hơn. Mô phỏng
luyện kim và tìm kiếm Tabu là hai cách tiếp cận chính để đối phó với vấn đề này. Thật
không may, tuy nhiên, nó gần như là không bao giờ rõ ràng, đưa ra một vấn đề cụ thể,
cách tốt nhất để thiết kế và thực hiện phương pháp là gì. Có nhiều sự lựa chọn để thực
hiện, đầu tiên là quyết định làm thế nào để đại diện cho một giải pháp ứng cử viên ở nơi
đầu tiên.
Ví dụ, một cấu trúc liên kết mạng có thể được biểu diễn như là một danh sách các
liên kết, nơi mà mỗi liên kết là một cặp của các nút (a, b). Giải mã một danh sách vào một
cấu trúc liên kết mạng chỉ đơn giản là số tiền để vẽ một liên kết điểm-điểm cho mỗi cặp
nút trong danh sách. Ngoài ra, chúng ta có thể đại diện cho một cấu trúc liên kết mạng
như là một chuỗi nhị phân, có chứa nhiều bit như là các liên kết có thể. EAC h vị trí trong
chuỗi bit sẽ giới thiệu cụ thể một liên kết điểm-điểm tiềm năng, Vì vậy, một giải pháp
candidiate như '10010'chỉ ra rằng có một liên kết điểm-điểm giữa các nút 1 và 2, không có
giữacác nút 1 và 3, 1 và 4, nhưng có một trong giữa nút 1 và 5, và vv… Nói chung, có rất
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 21
nhiều cách sáng tạo ra một phương pháp để đại diện cho các giải pháp cho một vấn đề. Sự
lựa chọntất nhiêncũng ảnh hưởng đến thiết kế của các nhà khai thác khu vực.
Trong ví dụ trên việc loại bỏ một liên kết từ cấu trúc liên kết liên quan đến hai loại
khác nhau của hoạt động trong hai đại diện. Trong trường hợp danh sách các node đôi,

cây này.
Có một số cách khác trong lĩnh vực kiến thức hoặc chẩn đoán hiện tại có thể được
sử dụng để hưởng lợi một cách tiếp cận tìm kiếm cục bộ cho một vấn đề tối ưu hóa. Một
cái gì đó về vấn đề này có thể cho chúng ta biết, ví dụ như là những loại đột biến có một
cơ hội tốt hơn dẫn đến lân cận tốt. Một phương pháp khám phá hiện có, nhanh chóng
phân công các kênh trong một mạng lưới điện thoại di động, có thể được sử dụng để cung
cấp điểm khởi đầu cho một tìm kiếm cục bộ cố gắng tìm giải pháp tốt hơn.
2. Tìm kiếm dựa trên quần thể
Đây là một phương cách của thuật toán thay thế, bây giờ trở nên rất phổ biến, được
xây dựng trên ý tưởng tìm kiếm địa phương bằng cách sử dụng quần thể. Có hai phương
cách để tăng cường các cơ hội của việc tìm kiếm giải pháp tốt. Đầu tiên, kể từ khi chúng
tôi có một quần thể, chúng ta có thể dành nhiều thời gian tìm kiếm trong các khu vực
khác nhau cùng một lúc. Một thuật toán dựa trên quần thể có xu hướng chia sẻ các nỗ lực
tính toán đến các giải pháp ứng cử khác nhau . Một phần thời gian sẽ được chi tiêu tìm
kiếm trong khu vực của các giải pháp trung bình và điều này sẽ dẫn đến việc tìm kiếm
được đột biến đặc biệt , sau đó cân bằng tải nỗ lực tính toán sẽ được sửa đổi phù hợp.
Một cơ hội khác được cung cấp bởi các kỹ thuật dựa trên quần thể là chúng ta có
thể thử vận hành tái tổ hợp. Đây là những cách sản xuất đột biến, nhưng lần này từ hai
hay nhiều giải pháp, chứ không phải chỉ một. Do đó kết quả có thể được gọi là tái tổ hợp,
chứ không phải là một đột biến. Tái tổ hợp là một phương pháp cung cấp một cách lựa
chọn tốt trong không gian rộng lớn của khả năng.
Ví dụ, nếu hai giải pháp cha mẹ là mỗi một vector của các yếu tố k, một nhà điều
hành tái tổ hợp được gọi là thống nhất chéo sẽ xây dựng một trẻ em từ cha mẹ, cho mỗi
phần tử lần lượt, ngẫu nhiên giá trị của nó từ một trong hai nơi. Đứa trẻ có thể có được
50% khác nhau từ mỗi cha mẹ của nó.
Dưới đây là các bước cho một thuật toán dựa trên quần thể chung.
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 23
Bước 1(Bắt đầu): tạo ra một kế cận ban đầu của các giải pháp ứng cử viên. Đánh
giá mỗi người trong số họ.
Bước 2: Chọn một số dân là cha mẹ.

sử dụng đột biến, nhưng được bỏ eclever 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à nhiễm sắc thể và các yếu tố của nó
được gọi là gen.
IV. KỸ THUẬT TÍNH TOÁN THÍCH NGHI
Để giải quyết nhu cầu tối ưu hóa vốn có của môi trường viễn thông, việc trực tiếp
sử dụng các kỹ thuật tối ưu hóa địa phương hoặc dân số dựa trên đôi khi có thể là khá phù
hợp. Bởi vì nó có thể mất quá lâu để đưa một giải pháp tốt, và như vậy từ thời gian đến
giải pháp, vấn đề đã được thay đổi !
Những gì chúng ta cần thay vì trong bối cảnh này là một cách để đưa ra quyết định
rất nhanh, nhưng rất tốt,. Ví dụ, để quyết định những bước nhảy tiếp theo tốt nhất là cho
một gói tin đến một nút đích d, chúng ta có lẽ có thể chạy một mô phỏng của các mạng
cho các mô hình tầng vận chuyểnhiện hành hiện nay và ước tính thời gian đến khả năng ở
các điểm đến cho cho có thể bước nhảy tiếp theo. Kết quả mô phỏng như vậy sẽ cung cấp
cho chúng tôi với một sự lựa chọn đầy đủ thông tin, và sau đó chúng tôi có thể gửi các gói
dữ liệu một cách thích hợp trên con đường của nó. Bây giờ, nếu chúng tôi có thể ở trên
trong một vài micro giây, chúng ta sẽ có một chiến lược định tuyến gói tin phù hợp và rất
có lợi nhuận.
Tuy nhiên, kể từ khi nó có thể sẽ mất vài giờ để làm một mô phỏng chính xác bằng
cách sử dụng các loại sức mạnh xử lý và bộ nhớ thường có sẵn các thiết bị chuyển mạch
mạng, trong thực tế nó là một ý tưởng vô lý! Thay vào đó, chúng tôi cần một số cách làm
cho quyết định đúng đắn một cách nhanh chóng, nhưng quyết định bằng cách nào đó sẽ
đưa vào tài khoản các trường hợp hiện hành. Lý tưởng nhất, chúng tôi đang tìm kiếm một
'hộp đen', khi cho ăn với một câu hỏi và một số chỉ tiêu môi trường, cung cấp một câu trả
lời hợp lý và ngay lập tức. Một ví dụ của một hộp đen như là một bảng định tuyến của các
loại thường thấy trong các mạng chuyển mạch gói. Câu hỏi được hỏi bởi một gói tin
truyền thông là: cuối cùng tôi muốn để có được d, vì vậy mà tôi nên đi tiếp theo? Bảng
định tuyến, thông qua một tra cứu đơn giản được lập chỉ mục của d, rất nhanh chóng cung
cấp một câu trả lời và gửi nó theo cách của mình.
Điều khiển luồng thông minh theo khuôn khổ lý thuyết trò chơi 25
Những rắc rối với điều này, tất nhiên, là nó về cơ bản là không thích nghi. Trừ khi