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

LUẬN VĂN THẠC SỸ KHOA HỌC

GIẢI THUẬT DI TRUYỀN GIẢI
BÀI TOÁN P-MEDIAN
CÓ HẠN CHẾ KHẢ NĂNG
NGÀNH: CÔNG NGHỆ THÔNG TIN
MÃ SỐ: 04.3898
DƯƠNG MINH TUẤN

Người hướng dẫn khoa học: PGS.TS. NGUYỄN ĐỨC NGHĨA

HÀ NỘI 2008


-2-

Lời cảm ơn
Với tất cả lòng kính trọng và biết ơn sâu sắc em xin gửi lời cảm ơn chân thành
tới thầy Nguyễn Đức Nghĩa. Người đã tận tình dạy dỗ và hướng dẫn em trong
quá trình hoàn thành đồ án.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


-3-

MỤC LỤC
MỤC LỤC......................................................................................................... 3
Lời nói đầu........................................................................................................ 5
Chương 1........................................................................................................... 6
KIẾN THỨC CƠ SỞ ....................................................................................... 6
1.1.

Các kí hiệu tiệm cận ........................................................................... 6

1.2.

Độ phức tạp tính toán của bài toán..................................................... 9

1.3. NP- đầy đủ........................................................................................ 10
1.3.1. Bài toán quyết định.................................................................. 10
1.3.2. Bằng chứng ngắn gọn dễ kiểm tra ........................................... 11
1.3.3. Lớp bài toán P, NP và co-NP................................................... 13
1.3.4. Qui dẫn..................................................................................... 14
1.3.5. Lớp bài toán NP-khó và NP-đầy đủ ........................................ 15
1.4.

Sai số tỉ lệ của thuật toán gần đúng.................................................. 17

Chương 2......................................................................................................... 21
GIỚI THIỆU BÀI TOÁN P-MEDIAN CÓ HẠN CHẾ KHẢ NĂNG VÀ
CÁC HƯỚNG TIẾP CẬN ............................................................................ 21
2.1.

Giới thiệu chung về bài toán p-median có hạn chế khả năng .......... 21


2.2.

Các hướng tiếp cận để giải quyết bài toán p-median có hạn chế khả
năng .................................................................................................. 22
2.2.1. Phương pháp sinh cột .............................................................. 22
2.2.1.1.Giới thiệu.............................................................................. 22
2.2.1.2.Tổng quan............................................................................. 22
2.2.1.3.Mô hình toán học của bài toán CPMP ................................. 24
2.2.1.4.Nới lỏng Lagrăng rút gọn và sinh cột .................................. 26
2.2.1.5.Kết luận ................................................................................ 30
2.2.2. Phương pháp tìm kiếm địa phương heuristic........................... 31
2.2.2.1.Giới thiệu.............................................................................. 31
2.2.2.2.Cách tiếp cận Lagrăng rút gọn ............................................. 32
2.2.2.3.Lagrăng rút gọn ứng dụng vào bài toán CPMP .................. 36
2.2.2.4.Tìm kiếm địa phương Heuristics.......................................... 39
2.2.2.5.Kết luận ................................................................................ 43

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


-4-

2.2.3. Phương pháp Bionomic ........................................................... 44
2.2.3.1.Giới thiệu.............................................................................. 44
2.2.3.2.Công thức của bài toán CPMP ............................................. 44
2.2.3.3.Giải thuật Heuristic cho bài toán CPMP .............................. 46
2.2.3.4.Giải thuật Bionomic ............................................................. 49
2.2.3.5.Giải thuật bionomic cho bài toán CPMP ............................. 52
2.2.3. Kết luận.................................................................................... 55

Chương 3......................................................................................................... 56
GIẢI THUẬT DI TRUYỀN GIẢI QUYẾT BÀI TOÁN P-MEDIAN CÓ
HẠN CHẾ KHẢ NĂNG ................................................................................ 56
3.1

Giới thiệu chung về giải thuật di truyền........................................... 56

3.2

Giải thuật di truyền cho bài toán p-median có hạn chế khả năng .... 67
3.2.1 Mã hóa. .................................................................................... 67
3.2.2 Hàm đánh giá độ tốt của nhiễm sắc thể. .................................. 68
3.2.3 Khởi tạo quần thể ban đầu. ...................................................... 69
3.2.4 Lựa chọn bố mẹ lai ghép. ........................................................ 70
3.2.5 Đột biến.................................................................................... 73
3.2.6 Thay thế. .................................................................................. 77
3.2.7 Sơ đồ thuật toán. ...................................................................... 77

Chương 4......................................................................................................... 79
KẾT QUẢ THỰC NGHIỆM ........................................................................ 79
4.1

Mô tả dữ liệu thực nghiệm ............................................................... 79

4.2

Mô tả hệ thống chương trình............................................................ 81

4.3


Kết quả tính toán .............................................................................. 83
4.3.1 Lựa chọn thông số. .................................................................. 83
4.3.2 Kết quả thực nghiệm................................................................ 86

4.4

Phân tích đánh giá ............................................................................ 93

TÀI LIỆU THAM KHẢO .......................................................................... 96

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


-5-

Lời nói đầu
Trong cuộc sống, việc đạt lợi nhuận cao hay thấp trong kinh doanh buôn
bán, cung cấp dịch vụ phụ thuộc rất nhiều yếu tố. Trong đó, có một yếu tố quan
trọng đầu tiên, đóng góp một phần rất lớn đó là xác định được địa điểm đặt
dịch vụ thuận lợi – nơi cung cấp dịch vụ. Có rất nhiều tiêu chí đặt ra khi chọn
địa điểm: thuận tiện về giao thông, là nơi tập trung đông dân cư, ... để làm sao
thu được lợi nhuận cao nhất. Đặc biệt, đối với các trường hợp khẩn cấp như
cứu thương, cứu hỏa thì yêu cầu về khoảng cách nhỏ nhất là vô cùng quan
trọng, có thể nói là quan trọng nhất trong các yếu tố. Bài toán đặt ra là: đặt các
trạm dịch vụ ở đâu để thời gian di chuyển bệnh nhân từ nơi xa bệnh viện nhất
(hoặc ngược lại, từ các trạm dịch vụ đến nơi bệnh nhân xa nhất) là nhỏ nhất có
thể. Còn với các dịch vụ phổ biến như trạm xăng, thùng phiếu, bốt điện thoại,
... thì yêu cầu lại là tổng chi phí từ các khách hàng (hay người có nhu cầu) đến
địa điểm phục vụ gần khách hàng nhất là nhỏ nhất.

Sau khi tìm hiểu kiến thức tổng quan cũng như một số giải thuật cơ bản
của bài toán p-median, mục tiêu của đồ án là: tập trung xây dựng giải thuật di
truyền để giải bài toán p-median có hạn chế khả năng.
Đồ án bao gồm 3 chương:
Chương 1: Nhắc lại một số kiến thức cơ sở liên quan đến các bài toán NP.
Chương 2: Giới thiệu về bài toán p-median có hạn chế khả năng, và các hướng
tiếp cận với bài toán.
Chương 3: Giải thuật di truyền để giải quyết bài toán p-median có hạn chế khả
năng
Chương 4: Kết quả thực nghiệm

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


-6-

Chương 1
KIẾN THỨC CƠ SỞ

1.1.

Các kí hiệu tiệm cận
Thông thường, trong các ứng dụng thực tế thời gian chính xác mà thuật

toán đòi hỏi để thực hiện nó được quan tâm ít hơn so với việc xác định tốc độ
tăng của thông số này khi tăng kích thước của đầu vào. Ví dụ, giả sử thời gian
tính tồi nhất của một thuật toán là:
t (n) = 90 n2 + 9n + 9
với đầu vào kích thước n. Khi n lớn số hạng 90n2 xấp xỉ bằng t(n) (xem bảng

1). Trong trường hợp này t (n) có tốc độ tăng giống như 90n2.
t(n) = 60n2 + 9n + 9

N

60n2

10

9099

6000

100

600909

600000

1000

60009009

60000000

10000

6000090009

6000000000


Nếu như t (n) được tính bằng giây, thì:
t (n) = n2 + 0.15 n + 0.15
sẽ cho ta thời gian tính đo bằng phút của thuật toán. Rõ hơn sự thay đổi này
không ảnh hưởng đến tốc độ tăng của thời gian tính khi kích thước đầu vào n
tăng, mà chỉ thay đổi đơn vị tính thời gian. Như vậy khi mô tả tốc độ tăng của

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


-7-

thời gian tính của thuật toán khi kích thước đầu vào tăng, không những chúng
ta chỉ cần quan tâm đến số hạng trội (60 n2), mà có thể bỏ qua các hằng số. Với
giả thiết như vậy, thời gian tính t (n) tăng giống như n2 khi n tăng. Ta sẽ nói
t (n) có bậc là n2 và viết:
t (n) = Θ(n2)
Tư tưởng cơ bản ở đây là thay thế biểu thức t(n) = 60n2 + 9n + 9 bởi biểu thức
đơn giản hơn n2 có cùng tốc độ tăng với t(n). Ta đi đến định nghĩa sau
Định nghĩa:
Giả sử f và g là các hàm đối số nguyên dương:
9

Ta viết f(n) = O(g(n)) và nói f(n) có bậc không quá g(n) nếu tồn
tại hằng số dương c và số nguyên dương n0 sao cho
| f(n) | ≤ c | g(n) | với mọi n ≥ n0

9


Ta viết f(n) = Ω(g(n)) và nói f(n) có bậc ít nhất là g(n) nếu tồn tại
hằng số dương c và số nguyên dương n0 sao cho
| f(n) | ≥ c | g(n) | với mọi n ≥ n0

9

Ta viết f(n) = Θ(g(n)) và nói f(n) có bậc là g(n) nếu
f(n) = O(g(n)) và f(n) = Ω(g(n))

9

Ta viết f(n) = o(g(n)) và nói f(n) có bậc thấp hơn g(n) nếu với mọi
hằng số c > 0 luôn tìm được số n0 sao cho 0 ≤ f(n) < cg(n) với
mọi n ≥ n0.

Hình vẽ dưới đây minh hoạ cho khái niệm O, Ω, Θ

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


-8-

Hình 1.1 Giải thích khái niệm O, Ω, Θ
Định nghĩa:
9

Nếu thuật toán đòi hỏi thời gian tính tốt nhất là t (n) với kích
thước đầu vào n và t(n) = O(g(n)) thì thời gian tính tốt nhất của
thuật toán có bậc không quá g(n) hay thời gian tính tốt nhất của

thuật toán là O(g(n)).

9

Nếu thuật toán đòi hỏi thời gian tính tồi nhất là t (n) với kích
thước đầu vào n và t (n) = O(g(n)) thì thời gian tính tồi nhất của
thuật toán có bậc không quá g(n) hay thời gian tính tồi nhất của
thuật toán là O(g(n)).

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


-9-

9

Nếu thuật toán đòi hỏi thời gian tính trung bình là t (n) với kích
thước đầu vào n và t(n) = O(g(n)) thì thời gian tính trung bình
của thuật toán có bậc không quá g(n) hay thời gian tính trung
bình của thuật toán là O(g(n)).

Thông thường khi nói thuật toán có thời gian tính là O(f(n)), ta hiểu là
thuật toán có thời gian tính trong tình huống tồi nhất là O(f(n)). Còn khi nói
thuật toán có thời gian tính là Ω(f(n)) ta hiểu là thời gian tính trong tình huống
tốt nhất của thuật toán là Ω(f(n)).
1.2.

Độ phức tạp tính toán của bài toán
Gọi TA(X) là thời gian tính của thuật toán A đối với đầu vào X. Khi đó,


thời gian tính trong tình huống tồi nhất của thuật toán A đối với dữ liệu đầu vào
kích thước n được định nghĩa như là:
TA (n) = max TA ( X )
| X |= n

Độ phức tạp trong tình huống tồi nhất của bài toán P là thời gian tính trong tình
huống tồi nhất của thuật toán nhanh nhất để giải nó:
T P(n) = min TA ( n) = min (max TA ( X ))
A∈∆

A∈∆

X =n

trong đó ∆ là tập tất cả các thuật toán giải bài toán P.
Việc đánh giá đúng độ phức tạp của bài toán là một vấn đề hết sức phức tạp. Vì
vậy chúng ta quan tâm đến việc đưa ra các cận trên và cận dưới cho nó.
Nếu ta có thuật toán A với thời gian tính trong tình huống tồi nhất là TA(n) =
O(f(n)) thì:
TP(n) ≤ TA(n) = O(f(n))

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 10 -

tức là ta có cận trên cho độ phức tạp của bài toán P. Thuật toán nhanh hơn sẽ
cho cận trên tốt hơn.

Chúng ta còn quan tâm đến việc đánh giá cận dưới độ phức tạp của bài toán,
nghĩa là quan tâm đến việc nó khó đến mức độ nào.
Để chỉ ra rằng:
TP(n) = Ω(f(n))
ta cần phải chỉ ra rằng:
i)

Có thuật toán với thời gian tính Ω(f(n)) để giải bài toán P

ii)

Mọi thuật toán giải bài toán P đều đòi hỏi thời gian tính trong tình
huống tồi nhất là Ω(f(n))

Đòi hỏi ii) có thể thay bởi:
ii*)
1.3.

Cận dưới cho độ phức tạp tính toán của bài toán P là Ω(f(n)).

NP- đầy đủ

1.3.1.

Bài toán quyết định
Bài toán quyết định là bài toán mà đầu ra chỉ có thể là ‘yes’ hoặc ‘no’

(Đúng/sai, 0/1, chấp nhận/từ chối, accept/reject). Đối với một bài toán quyết
định, có những bộ dữ liệu vào của nó có câu trả lời (đầu ra) là ‘yes’ và cũng có
những bộ dữ liệu vào có câu trả lời là ‘no’. Những bộ dữ liệu vào với câu trả

lời ‘yes’ (‘no’) sẽ được gọi là bộ dữ liệu vào ‘yes’ (‘no’).
Ví dụ 1:
9

Bài toán về tính nguyên tố: “Hỏi số nguyên n có là số nguyên tố
hay không?”. N=23 là bộ dữ liệu vào ‘yes’, còn n=24 là bộ dữ liệu
vào ‘no’ của bài toán.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 11 -

9

Bài toán tổng con: “Cho tập I gồm n số nguyên dương x1, x2,..., xn
và số nguyên dương T. Hỏi có thể tìm được tập con S của I với
tổng các số trong S là bằng T?”

9

Bài toán người du lịch dạng quyết định (Dec-TSP): “Tồn tại
hay chăng hành trình của người du lịch với tổng chi phí không
vượt quá số K cho trước?”

1.3.2.

Bằng chứng ngắn gọn dễ kiểm tra
Rất nhiều các bài toán quyết định có một đặc điểm chung, đó là để xác


nhận câu trả lời ‘yes’ đối với bộ dữ liệu vào ‘yes’ của chúng, ta có thể đưa ra
bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời 'yes' cho bộ dữ liệu vào
'yes' đó.
Ví dụ 2:
9

Đối với bài toán kiểm tra tính hợp số: “Có phải số n là hợp số?”,
để xác nhận câu trả lời ‘yes’ cho đầu vào n, ta có thể đưa ra một
ước số b (1ta có thể thực hiện phép chia n cho b sau thời gian đa thức. Trong
ví dụ này b là bằng chứng ngắn gọn (vì bthuật toán thời gian tính đa thức để kiểm tra b đúng là ước số của
n.

9

Đối với bài toán tổng con, bằng chứng xác nhận câu trả lời ‘yes’
đối với bộ dữ liệu (x1,..., xn) là vectơ c = (c1,..., cn), trong đó ci = 1
nếu xi được chọn vào tập S và ci =0 nếu trái lại. Việc kiểm tra xem
tập S gồm các số được chọn có thoả mãn yêu cầu đặt ra hay
không, rõ ràng, có thể thực hiện sau thời gian đa thức.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 12 -

9

Đối với bài toán người du lịch dạng quyết định, bằng chứng xác
nhận câu trả lời ‘yes’ cho ma trận chi phí C = {cij: i, j = 1,...,n}
của bài toán là dãy các thành phố trên hành trình. Việc kiểm tra
xem dãy các thành phố đã cho có phải là hành trình với chi phí
không vượt quá K có thể thực hiện xong sau thời gian đa thức.

Ta gọi bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời 'yes' cho
bộ dữ liệu vào ‘yes’ của bài toán là một bằng chứng có độ dài bị chặn bởi một
đa thức bậc cố định của độ dài dữ liệu đầu vào của bài toán, và việc kiểm tra
nó là bằng chứng xác nhận câu trả lời ‘yes’ đối với đầu vào đã cho của bài toán
có thể thực hiện xong sau thời gian đa thức.
Như vừa chỉ ra ở trên, các bài toán trong ví dụ 2 đều có bằng chứng ngắn
gọn dễ kiểm tra để xác nhận câu trả lời ‘yes’ của bộ dữ liệu vào ‘yes’.
Hoàn toàn tương tự, có thể đưa ra khái niệm bằng chứng ngắn gọn dễ kiểm
tra để xác nhận câu trả lời 'no'.
Đối với một số bài toán việc đưa ra bằng chứng ngắn gọn xác định câu
trả lời ‘no’ là dễ hơn so với việc đưa ra bằng chứng ngắn gọn xác định câu trả
lời ‘yes’.
Ví dụ 3:
Đối với bài toán kiểm tra tính nguyên tố, để đưa ra bằng chứng ngắn gọn
dễ kiểm tra xác nhận câu trả lời ‘no’ cho đầu vào n của nó, ta có thể đưa ra một
ước số b của n.
Có những bài toán mà việc đưa ra bằng chứng ngắn gọn dễ kiểm tra xác
nhận câu trả lời ‘yes’ cũng như ‘no’ đều là không dễ dàng.
Ví dụ 4:
_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng

- 13 -

Cho đơn đồ thị vô hướng G = (V, E). Hỏi đường đi đơn dài nhất nối hai
đỉnh s và t của đồ thị G có tồn tại duy nhất?
1.3.3.

Lớp bài toán P, NP và co-NP
Trước hết, ta nêu khái niệm về lớp các bài toán dễ giải – đó là các bài

toán có thể giải được nhờ các thuật toán thời gian tính đa thức.
Định nghĩa: Ta gọi P là lớp các bài toán có thể giải được sau thời gian đa
thức.
Ví dụ 5:
Bài toán về tính liên thông của đồ thị có thể giải được nhờ thuật toán với
thời gian tính là O(n2), vì vậy, nó là bài toán thuộc lớp P. Bài toán cây khung
nhỏ nhất giải được nhờ thuật toán Prim với thời gian O(n2), cũng thuộc vào lớp
P.
Định nghĩa: Ta gọi NP là lớp các bài toán quyết định mà để xác nhận câu trả
lời ‘yes’ của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ 6:
Các bài toán trình bày trong ví dụ 2 đều thuộc lớp NP.
Định nghĩa. Ta gọi co-NP là lớp các bài toán quyết định mà để xác nhận câu
trả lời ‘no’ của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ 7:
Các bài toán nêu trong ví dụ 3 là thuộc lớp co-NP.
Bài toán trong ví dụ 4 còn chưa biết có thuộc vào lớp nào trong hai lớp NP và
co-NP hay không.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng

- 14 -

Rõ ràng, nếu một bài toán thuộc lớp P, thì ta có thể tìm được lời giải của nó
sau thời gian đa thức, và vì thế ta cũng có thể xác nhận được câu trả lời ‘yes’
của nó (bằng việc giải nó) sau thời gian đa thức. Vì vậy:
P ⊆ NP
Tương tự như vậy ta có
P ⊆ co-NP
Một trong những vấn đề trung tâm của lý thuyết tính toán, đó là chứng minh
hoặc bác bỏ đẳng thức:
P = NP
Cho đến hiện nay vấn đề này vẫn còn là vấn đề mở.
1.3.4.

Qui dẫn
Giả sử A và B là hai bài toán quyết định. Ta nói bài toán A có thể qui

dẫn sau thời gian đa thức về bài toán B nếu tồn tại thuật toán thời gian đa thức
R cho phép biến đổi bộ dữ liệu vào x của A thành bộ dữ liệu vào R(x) của B
sao cho x là bộ dữ liệu ‘yes’ (nghĩa là bộ dữ liệu mà câu trả lời cho nó là ‘yes’)
của A khi và chỉ R(x) là bộ dữ liệu ‘yes’ của B. Trong phần tiếp theo ta chỉ xét
phép qui dẫn sau thời gian đa thức, vì thế để ngắn gọn, ta sẽ gọi là phép qui
dẫn thay cho phép qui dẫn sau thời gian đa thức.
Nếu A qui dẫn được về B và để giải B đã có thuật toán đa thức thì A cũng sẽ
giải được sau thời gian đa thức.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng

- 15 -

x

Thụât toán
qui dẫn R

Đầu vào
cho A

R(x)
Đầu vào
cho B

Thụât toán
giải B

yes/no
Đầu ra
cho B

Đầu ra
cho A

Thuật toán giải A
Phép qui dẫn đưa đến thuật toán
Tư tưởng qui dẫn đã giải thích vai trò quan trọng của lớp bài toán P. Nếu ta có
bài toán A thuộc lớp P và một bài toán B có thể qui dẫn về A, thế thì B cũng

thuộc vào P.
1.3.5.

Lớp bài toán NP-khó và NP-đầy đủ

Ta sẽ đưa ra định nghĩa về những bài toán khó nhất trong lớp NP: bài toán NPđầy đủ (NP-complete).
Định nghĩa:
Một bài toán quyết định A được gọi là NP-đầy đủ nếu như:
i)

A là bài toán trong NP;

ii)

Mọi bài toán trong NP đều có thể qui dẫn về A.

Như vậy, có thể nói khái niệm về “bài toán khó nhất” trong lớp NP được xây
dựng trên cơ sở phép qui dẫn. Nếu tất cả các bài toán trong NP có thể qui dẫn
về một bài toán A thì A khó không kém bất cứ bài toán nào trong số chúng.
Điều đáng ngạc nhiên là sự tồn tại của những bài toán có tính chất như vậy.
Khó khăn nhất là việc tìm ra được một bài toán như vậy. Bởi vì hễ chúng ta đã
có một bài toán NP-đầy đủ thì để ta có thể dễ dàng chứng minh nhiều bài toán
khác là NP-đầy đủ nhờ sử dụng kết quả sau đây.
_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 16 -

Bổ đề: Giả sử bài toán A là NP-đầy đủ, bài toán B là thuộc NP, và bài toán A

qui dẫn về B. Khi đó bài toán B cũng là NP-đầy đủ.
Định nghĩa: Một bài toán A được gọi là NP-khó (NP-hard) nếu như sự tồn tại
thuật toán đa thức để giải nó kéo theo sự tồn tại thuật toán đa thức để giải mọi
bài toán trong NP.
Một cách không hình thức, có thể nói rằng nếu ta có thể giải được một cách
hiệu quả một bài toán NP-khó cụ thể, thì ta cũng có thể giải hiệu quả bất kỳ bài
toán nào trong NP bằng cách sử dụng thuật toán giải bài toán NP-khó như là
một chương trình con.
Từ định nghĩa NP-khó suy ra rằng mỗi bài toán NP-đầy đủ đều là NP-khó. Tuy
nhiên, như đã nêu ở trên, một bài toán là NP-khó không nhất thiết phải là NPđầy đủ.
Từ Bổ đề suy ra rằng để chứng minh một bài toán A nào đó là NP-khó, ta chỉ
cần chỉ ra phép qui dẫn một bài toán đã biết là NP-khó về nó.
Ta có bức tranh tạm thời đầy đủ hơn về phân lớp các bài toán trên hình 2:

Hình 1.1.5 Phân lớp tạm thời các bài toán

Từ phần trình bày trên, ta thấy rằng có rất nhiều bài toán ứng dụng quan trọng
thuộc vào lớp NP-khó, và vì thế khó hy vọng xây dựng được thuật toán đúng

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 17 -

hiệu quả để giải chúng. Một trong những hướng phát triển thuật toán giải các
bài toán như vậy là xây dựng các thuật toán gần đúng.
1.4.

Sai số tỉ lệ của thuật toán gần đúng

Xét bài toán tối ưu:
(P) f(x) → extr,

x∈D

để đánh giá chất lượng của lời giải gần đúng ta đưa ra khái niệm cận sai số tỷ
lệ.
Định nghĩa:
Ta nói thuật toán A giải bài toán (P) có cận sai số tỷ lệ là p(n), nếu với mọi bộ
dữ liệu vào độ dài n ta có
⎧ f (x ) f * ⎫
max ⎨ *A ,
⎬ ≤ p ( n)
f
f
(
x
)
A ⎭
⎩

trong đó f* là giá trị tối ưu, xA là phương án tìm được theo thuật toán A.
Đối với bài toán tìm max:
⎧ f ( xA ) f * ⎫
f*
,
=
⎬
*

f ( xA ) ⎭
f ( xA )
⎩ f

p(n) ≥ max ⎨

vì thế p(n) cho biết giá trị tối ưu không vượt quá giá trị gần đúng bao nhiêu lần.
Đối với bài toán tìm min:
⎧ f ( xA ) f * ⎫
f (xA )
,
⎬ =
*
f*
f ( xA ) ⎭
⎩ f

p(n) ≥ max ⎨

vì thế p(n) cho biết giá trị gần đúng không vượt quá bao nhiêu lần giá trị tối ưu
Nếu biết cận sai số tỷ lệ p(n) thì có thể đánh giá được sai số tương đối:
_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 18 -

9

Trong trường hợp bài toán max, ta có:

⎧ f (x ) f * ⎫
f*
=
p (n) ≥ max ⎨ *A ,
⎬
f (xA ) ⎭ f (xA )
⎩ f

suy ra: p (n) − 1 ≥
9

f * − f (xA )
f*
−1 =
f (xA )
f (xA )

Trong trường hợp bài toán min, ta có:
⎧ f (x ) f * ⎫ f (xA )
p (n) ≥ max ⎨ *A ,
⎬=
f
x
(
)
f
f*
A
⎩
⎭

f (xA ) − f *
f (xA ) − f *
−1 =
suy ra p (n) − 1 ≥
f*
f*

Trong những năm gần đây một trong những hướng phát triển thuật toán để giải
các bài toán NP-khó là xây dựng các thuật toán gần đúng đảm bảo chất lượng
của lời giải gần đúng, nghĩa là thuật toán gần đúng với cận sai số tỷ lệ bị chặn
bởi hằng số: p(n) ≤ c (trong đó c là hằng số, c > 1).
Đối với một số bài toán ta có thể xây dựng được thuật toán gần đúng thời gian
tính đa thức với cận tỷ lệ bị chặn bởi δ = 1 + ε, với mọi số ε > 0. Thời gian tính
của các thuật toán như vậy phụ thuộc vào cả kích thước dữ liệu n và cả vào ε.
Ví dụ: Bài toán phủ định
Input: Đồ thị vô hướng G = (V, E)
Output: Phủ định với lực lượng nhỏ nhất. Thuật toán gần đúng được mô tả
như sau: Bắt đầu từ tập S = ∅. Chọn e = (u,v) ∈ E. Đặt S = S ∪{u, v}. Loại bỏ
khỏi đồ thị cạnh e và tất cả các cạnh có ít nhất một đầu mút trong S. Ký hiệu
G* là đồ thị thu được. Lặp lại quá trình với đồ thị G*.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 19 -

procedure ApproxVC;
S:= ∅;
while E ≠ ∅ do

begin
Chọn e = (u,v) ∈ E; (* e được chọn tuỳ ý *) S:= S ∪{u, v};
Loại bỏ khỏi E tất cả các cạnh có ít nhất một đầu mút trong S;
end;
Ta có kết quả sau đây về chất lượng của lời giải thu được theo thuật toán
ApproxVC:
Định lý: ApproxVC có sai số tỷ lệ bị chặn bởi 2
Chứng minh:
Xét tập phủ đỉnh S cho bởi ApproxVC. Gọi S* là phủ đỉnh tối ưu. Gọi A là tập
các cạnh được chọn trong thuật toán ApproxVC. Do ở mỗi lần lặp ta đã thêm
cả hai đầu mút của cạnh được chọn vào S nên:
|S|=2|A|
Mặt khác, rõ ràng S* phải chứa ít nhất một trong hai đầu mút của mỗi cạnh
trong A, suy ra:
| S* | ≥ | A |
Từ đó suy ra :
|S|
=| A | ≤ | S * |
2

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 20 -

Vì thế:
|S|
≤2
| S* |

Định lý được chứng minh.
Ví dụ:

Đồ thị G và S*

Xây dựng phủ đỉnh gần đúng S

Hình 1.4 Minh hoạ cho ApproxVC
Trong ví dụ này ta có |S| = 6, |S*| = 3. Ví dụ này cho thấy bất đẳng thức trong
bổ đề có thể xảy ra dưới dạng dấu bằng.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 21 -

Chương 2
GIỚI THIỆU BÀI TOÁN P-MEDIAN CÓ HẠN CHẾ KHẢ NĂNG
VÀ CÁC HƯỚNG TIẾP CẬN

2.1.

Giới thiệu chung về bài toán p-median có hạn chế khả năng
Bài toán p-median là dạng bài toán đặt ra yêu cầu xác định các địa điểm

tối ưu (hoặc gần tối ưu) đặt các dịch vụ phục vụ sinh hoạt hàng ngày ở sân bay,
nhà máy, kho hàng, trường học, nhà tù… cũng như các dịch vụ trong trường
hợp khẩn cấp như cứu thương, cứu hoả…, với điều kiện các địa điểm phải

được chọn từ một tập giới hạn các vị trí (site) cho trước.
Cần xác định vị trí đặt một số các trạm chức năng (dịch vụ) cho trước
sao cho chi phí vận chuyển trung bình (thời gian vận chuyển trung bình) từ
người dùng đến các chức năng đó hoặc ngược lại từ các chức năng đến người
dùng là cực tiểu.
Bài toán p-median có hạn chế khả năng phục vụ (Uncapacitated pmedian problems): Cho trước một tập các địa điểm, chi phí mở dịch vụ tại mỗi
địa điểm, và lợi nhuận thu được ở các địa điểm từ việc phục vụ các khách
hàng, vấn đề đặt ra là cần chọn ra các địa điểm để đặt dịch vụ và gắn các khách
vào các dịch vụ để có được một mạng lưới dịch vụ đem lại tổng lợi nhuận lớn
nhất và quan tâm đến khả năng phục vụ của mỗi điểm phục vụ. Tổng khả năng
phục vụ của điểm phục vụ phải lớn hơn tổng yêu cầu từ các điểm yêu cầu.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 22 -

2.2.

Các hướng tiếp cận để giải quyết bài toán p-median có hạn chế khả
năng

2.2.1.

Phương pháp sinh cột

2.2.1.1. Giới thiệu
Bài toán định vị vị trí phục vụ có ý nghĩa rất quan trọng cho nhiều quyết
định. Rất nhiều ứng dụng trong thực tế sử dụng kết quả bài toán. Trong phần

này chúng ta nghiên cứu phương pháp sinh cột để giải quyết bài toán p-median
có hạn chế khả năng. Phương pháp sinh cột nhanh tương đối nhanh hơn so với
một số phương pháp khác. Tuy nhiên trong một số trường hợp nó có thể hội tụ
chậm. Trong phần này chúng ta nghiên cứu cách để làm ổn định phương pháp
sinh cột khi ứng dụng giải bài toán định vị vị trí.
Trong phần này chúng ta sử dụng phương pháp sinh cột để giải quyết bài
toán p-median có hạn chế khả năng (CPMP). Trước tiên phải giải bài toán tối
ưu 1-median mà đáp ứng điều kiện về khả năng phục vụ của median sau đó các
cột mới được sinh ra như là bài toán cái túi. Các phương pháp Lagrăng rút gọn
gần đây được sử dụng để thực hiện gradient con. Trong phần này nới lỏng
Lagrăng được xác định trực tiếp từ bái toán đối ngẫu chính và cung cấp các cận
mới và các cột hiệu quả thông qua bài toán cái túi cải biên.
2.2.1.2. Tổng quan
CPMP được biết như là một bài toán NP khó. Một vài cách tiếp cận gần
đây ứng dụng Lagrăng heuristics vào bài toán CPMP Koskosidis and Powell
[1] and in [2]. Các phương pháp gần đây sử dụng metaheuristics như
simulated annealing and tabu search và giải thuật di truyền. Các kết quả ghi

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 23 -

nhận

và bộ dữ liệu test chuẩn được báo cáo trên trang web

/>Phương pháp sinh cột là một công cụ mạnh để giải quyết bài toán quy
hoạch tuyến tính. Quy hoạch tuyến tính xuất hiện khi số lượng cột chưa biết và

toàn bộ việc liệt kê các cột không phải là lựa chọn hoặc bài toán được viết lại
sử dụng phân tích Dantzig-Wolfe (Các cột ứng với các điểm xa nhất của tập
điều kiện) [3]. Cách tiệp cận này trước đó chưa được ứng dụng để giải quyết
bài toán CPMP nhưng đã thành công trong một số ứng dụng khác như bài toán
cutting-stock, vedicle routing [3,4, 5, 6, 7, 8, 9,10, 11, 12]. Tuy nhiên trong
một số trường hợp việc sử dụng phương pháp sinh cột gây ra hội tụ chậm cho
bài toán. Nới lỏng Lagrăng rút gọn được giới thiệu trong phần này làm tăng tốc
quá trình xử lý với phương pháp sinh cột. Tạo ra các tập cột hữu ích.
Trong phần này chúng ta ứng dụng phương pháp sinh cột vào bài toán
CPMP. Bài toán chính giới hạn tối ưu bài toán 1-median thỏa mãn các điều
kiện của bài toán CPMP về hạn chế khả năng. Các cột mới sinh ra để giải
quyết các khả năng của bài toán con mà có tính đến các biến đối ngẫu chính có
giới hạn và khả năng của các median. Trong phần này nới lỏng Largăng rút
gọn được xác định trực tiếp từ bài toán đối ngẫu chính và cung cấp các cận
mới, các cột hữu ích từ bài toán cái túi cải biên. Toàn bộ quá trình sinh cột
được thực hiện nhanh chóng.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 24 -

2.2.1.3. Mô hình toán học của bài toán CPMP
Mô hình toán học của bài toán CPMP được trình bày theo 2 cách:
Cách thứ nhất:
Theo bài toán quy hoạch tuyến tính nguyên (P)
(P) v( P ) = Min ∑

∑ d ij xij

(1)

∑ xij = 1; i ∈ N

(2)

∑ xij = p

(3)

∑ qi x ji ≤ Qx jj ; j ∈ N

(4)

xij ∈ {0,1}; i ∈ N , j ∈ N

(5)

i∈N

trong đó

j∈N

j∈N

j∈N

i∈N

9

N={1,..,n} là tập các chỉ số của các nút và của các median, p là số lượng
median

9

qi là nhu cầu phục vụ của nút i và Q là tổng khả năng phục vụ của mỗi
median

9
9

[d ]
[x ]

ij n×n

ij n×n

là ma trận khoảng cách giữa các nút
là ma trận định vị, nếu xij = 1 tức là median j phục vụ cho nút i

Ngược lại thì xij = 0 . Nếu x jj = 1 thì nút j là median, ngược lại x jj = 0
Điều kiện (2) và (3) để ràng buộc mỗi một nút được phục vụ bởi duy nhất 1
median và tổng số median là p. Điều kiện (4) để ràng buộc về khả năng phục
vụ của median. Điều kiện (5) ràng buộc về giá trị của xij .
Để đơn giản hóa ta giả sử khả năng phục vụ của các median là bằng nhau.

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng


- 25 -

Cách thứ 2:

Bài toán CPMP cũng có thể được chia thành tập các bài toán con với các điều
kiện (SPP):
(SPP)

m

v( SPP) = Min∑ ck xk
k =1

trong đó

m

∑ Ak xk = 1

(6)

k =1
m

∑ xk = p

(7)

k =1

xk = {0,1}
S={S1,S2,…,Sm} là tập các tập con của N
A = [aik ]n×m , là ma trận với [aik ] = 1 nếu i ∈ S k và ngược lại, thỏa mãn:

⎛
⎞
⎜
⎟
⎜
⎟ , S k1 = {i ∈ S k | aik = 1}
và
c
=
d
q
a
≤
Q
∑
Min
∑ i ik
k
ij
⎜
⎟
i∈N

⎟
i ∈ S1 ⎜ j ∈ S1
k⎝
k
⎠
Công thức này được mô tả trong Minoux[13]. Cùng một công thức đạt được từ
bài toán P bằng cách áp dụng phân rã Dantzig-Wolfe. Với mỗi tập con S k1 ,
median mở được quyết định khi chi phí cột ck được tính toán và các cột của
SPP có tính đến tập điều kiện (4) của P. Các điều kiện (1) và (2) được duy trì
và lần lượt cập nhật thành (6), (7) theo quá trình phân rã Dantzig-Wolfe [3].
Nếu S là tập chứa tất cả các tập con của N. Công thức có thể đưa ra một lời
giải cho CPMP. Tuy nhiên số lượng tập con của N có thể rất lớn, có thể thay
bằng một phần tập các cột. SPP được xác định ở trên cũng đc biết đến như là
một bài toán giới hạn chính trong phương pháp sinh cột[4].

_________________________________________________________________
Giải thuật di truyền giải bài toán p-median có hạn chế khả năng