Phân tích tính hội tụ của thuật toán di truyền lai mới

Tạp chí Tin học và Điều khiển học, T.29, S.2 (2013), 165–172
PHÂN TÍCH TÍNH HỘI TỤ CỦA THUẬT TOÁN DI TRUYỀN LAI MỚI
LỤC TRÍ TUYÊN1, NGUYỄN HỮU MÙI2, VŨ ĐÌNH HÒA2
1Viện Công nghệ Thông tin, Viện Hàn Lâm Khoa học và Công nghệ Việt Nam
2Khoa Công nghệ Thông tin, Đại học Sư phạm Hà nội
Tóm tắt. Trong một bài báo gần đây, chúng tôi đã trình bày một thuật toán di truyền lai mới
(NHGA) cho bài toán lập lịch Job Shop (JSP). Phương pháp mã hóa chúng tôi sử dụng là mã hóa số
tự nhiên thay cho mã hóa nhị phân. Cách mã hóa này có nhiều ưu điểm, nhưng vấn đề hội tụ của nó
vẫn còn là vấn đề mở trong nhiều năm nay. Bài báo này phân tích các thuộc tính hội tụ của NHGA
bằng cách áp dụng các tính chất của xích Markov. Trên cơ sở phân tích xích Markov của thuật toán
di truyền, chúng tôi đã chứng minh tính hội tụ tới tối ưu toàn cục của phương pháp mã hóa số tự
nhiên.
Từ khóa. Lập lịch, giải thuật di truyền, hội tụ toàn cục, xích Markov.
Abstract. In this paper, we propose a new hybrid genetic algorithm (NHGA) for the job shop
scheduling problem (JSP). The method of encoding we used was Natural coding instead of traditional
binary coding. This manner of coding has a lot of advantages but its convergence has been still an
open issue so far. This paper analyzes the convergence properties of the NHGA by applying the
properties of Markov chain. Based on Markov chain analysis of the genetic algorithm, we show that
the proposed algorithm converges to the global optimum in term of Natural coding.
Key words. Job shop scheduling, genetic algorithm, global convergence, Markov chain.
1. GIỚI THIỆU
Thuật toán di truyền (GA) phỏng theo các quá trình tiến hoá tự thích nghi của các quần
thể sinh học để tối ưu hoá các hàm mục tiêu. Thuật toán này được phát triển bởi John
Holland [5], GA được đặc trưng bởi các chiến lược tìm kiếm dựa trên quần thể và các toán tử
di truyền: chọn lọc, đột biến và trao đổi chéo. Nakano và Yamada [11] nằm trong số những
người đầu tiên đã áp dụng GA cổ điển dùng phép biểu diễn các lời giải theo số nhị phân cho
bài toán lập lịch Job Shop (JSP). Sau đó họ còn đề xuất một số phương pháp kết hợp GA với
các kỹ thuật tìm kiếm khác và đã thu được nhiều thành tựu đáng kể trong việc chinh phục
JSP. Ulder và những người khác [10] là những người đầu tiên đề xuất phương pháp tìm kiếm
cục bộ di truyền, phương pháp này lai ghép giữa GA và kỹ thuật tìm kiếm cục bộ cho JSP.
Gần đây hơn, nhiều nhà nghiên cứu đã đề xuất các phương pháp lai kết hợp GA với nhiều kỹ
thuật tìm kiếm khác để giải quyết bài toán này phức tạp này. Chẳng hạn như: Lee Hui Peng
và những người khác [6], F. Guerriero [3], Rui Zhang và những người khác [12], Yamada [14],
... Tuy nhiên, cho tới nay chưa có phương pháp nào giải quyết triệt để bài toán này nhất là
trường hợp nhiều máy và nhiều công việc.
Trong công trình nghiên cứu đã được công bố gần đây chúng tôi đã trình bày một thuật
166 LUC TRI TUYEN, NGUYEN HUU MUI, VU DINH HOA.
toán di truyền lai mới cho JSP, để hiểu chi tiết về thuật toán này, bạn đọc có thể tham khảo
trong [9]. Trong bài báo này chúng tôi trình bày một vấn đề vướng mắc vẫn còn để ngỏ trong
mấy năm qua đó là: Chứng minh tính hội tụ của thuật toán di truyền lai mới cho bài toán
lập lịch Job Shop.
2. THUẬT TOÁN DI TRUYỀN LAI MỚI CHO BÀI TOÁN LẬP LỊCH JSP
Thuật toán di truyền là một thuật toán mà đã trở nên rất nổi tiếng và phổ biến, vì vậy
ở đây chúng tôi không đi sâu vào mô tả bài toán mà chỉ đưa ra thuật toán truyền thống và
thuật toán di truyền lai mới để tập trung phân tích tính hội tụ của chúng dựa trên lý thuyết
xác suất.
• Thuật toán di truyền truyền thống
Begin
t = 0
Khởi tạo P(t)
Xác định độ thích nghi của mỗi cá thể
repeat
Thực hiện lai ghép
Thực hiện đột biến
Xác định độ thích nghi của mỗi cá thể
Thực hiện chọn lọc
Xác định độ thích nghi mỗi cá thể
until một số tiêu chuẩn dừng được thỏa mãn
End
Thuật toán truyền thống trên không hội tụ hoàn toàn [4]. Vì vậy, chúng tôi cải tiến thuật
toán trên với sự bổ sung thêm cá thể tinh hoa và thêm vào toán tử sao chép như dưới đây.
• Thuật toán di truyền lai mới: Siêu cá thể là cá thể có tính chất đặc biệt, nó không
tham gia vào các quá trình lai ghép, đột biến hay chọn lọc, sau khi thao tác 3 toán tử
cơ bản trên với quần thể, chúng ta sẽ thực hiện thêm một toán tử mới, đó là toán tử
sao chép. Toán tử này có tác dụng sao chép cá thể có độ thích nghi cao hơn so với siêu
cá thể ở trạng thái tương ứng vào vị trí của siêu cá thể. Thuật toán tiến hóa với siêu cá
thể như sau
Begin
t = 0
Khởi tạo P(t) với siêu cá thể // cá thể có độ thích nghi tốt nhất//
Xác định độ thích nghi của mỗi cá thể //được chọn là siêu cá thể//
repeat
Thực hiện lai ghép
Thực hiện đột biến
Xác định độ thích nghi của mỗi cá thể
Thực hiện chọn lọc
Xác định cá thể có độ thích nghi cao nhất
Thực hiện sao chép
until một số tiêu chuẩn dừng được thỏa mãn
End
CONVERGENCE ANALYSIS OF THE NEW HYBRID GENETIC ALGORITHM 167
Với thuật toán di truyền lai mới này, chúng tôi sẽ sử dụng lý thuyết xích Markov để chứng
minh bài toán hội tụ đến lời giải tối ưu toàn cục với xác suất 1 theo thời gian.
3. PHÂN TÍCH TÍNH HỘI TỤ CỦA THUẬT TOÁN DI TRUYỀN CHO
BÀI TOÁN LẬP LỊCH JSP
3.1. Thuật toán di truyền truyền thống
3.1.1 Bài toán
Bài toán được giả sử với n công việc và m máy với một tuần tự công việc xác định. Mỗi
lời giải coi là một cá thể, mỗi phần công việc được xử lý trên mỗi máy là một gen. Gọi N là
số cá thể của quần thể. Khi đó, mỗi một trạng thái của quần thể có thể coi là một dãy mã
hóa theo số tự nhiên có dài n×m×N , trong đó phép chiếu pik(i) cho ta cá thể thứ k trong
quần thể. Không gian tìm kiếm có số các trạng thái là (n!)m×N .
3.1.2 Liên hệ giữa bài toán JSP và xích Markov
Như vậy, mỗi thế hệ trong thuật toán di truyền gồm một quần thể được đặc trưng bởi hàm
thích nghi, và mỗi giá trị này ta coi là một trạng thái. Vì thế hệ thứ t+ 1 (gọi là Zt+1) sinh
ra một cách ngẫu nhiên từ thế hệ thứ t (Zt) nên xác suất để quần thể chuyển từ trạng thái i
ở thế hệ t sang trạng thái j ở thế hệ t+1 chỉ phụ thuộc vào thế hệ thứ t nên dãy {Zt, t ≥ 1}
có thể coi là một xích Markov với không gian trạng thái chính là không gian tìm kiếm. Từ
đây, ta có thể phân tích sự hội tụ theo xác suất của xích Markov này.
Bây giờ ta đi tính ma trận xác suất chuyển của xích Markov có được từ thuật toán di
truyền.
• Ma trận xác suất chuyển trạng thái của quần thể gây ra bởi toán tử lai
ghép
Xét toán tử lai, gọi C là ma trận chuyển trạng thái của quần thể gây ra bởi toán tử lai
ghép, ta có:
C =


c11 · · · c1(n!)m.N
...
. . .
...
c(n!)m.N1 · · · c(n!)m.N (n!)m.N


Với cij là xác suất của quần thể chuyển từ trạng thái i sang trạng thái j với xác suất lai
pc . Ta thấy với đầu vào của thuật toán tiến hóa truyền thống , xác suất lai là pc ∈ [0, 1],
quá trình lai diễn ra bằng việc chọn bất kỳ một cá thể cha mẹ ở trạng thái hiện thời i
với xác suất lai pc, tiến hành cho lai ghép 3 cá thể theo luật GT hoàn toàn ngẫu nhiên
[14], sau quá trình lai ghép, quần thể có thể ở trạng thái j bất kỳ với xác suất cij và
(n!)m.N∑
j=1
cij = 1
xác suất cij này không phụ thuộc vào việc quần thể đang ở thế hệ thứ bao nhiêu, đang
ở thời điểm nào, mà chỉ phụ thuộc vào xác suất lai pc cố định theo đầu vào của thuật
giải. Như vậy, ma trận chuyển trạng thái sinh ra bởi phép lai C của quần thể là một
ma trận ngẫu nhiên và cố định không phụ thuộc vào trạng thái hiện thời cũng như thời
điểm của quần thể.
• Ma trận xác suất chuyển trạng thái của quần thể gây ra bởi toán tử đột
biến
168 LUC TRI TUYEN, NGUYEN HUU MUI, VU DINH HOA.
Gọi i là trạng thái tại thời điểm t, và pik(i) là cá thể thứ k trong quần thể gồm N cá
thể, pih(pik(i)) là máy thứ h trong pik(i) và pil(pih(pik(i))) là gene vị trí thứ l, được mô tả
trong Hình 3.1. Thuật toán đột biến xảy ra với pik(i) có thể mô tả vắn tắt như sau:
Hình 3.1. Gene tại vị trí thứ 2 của trạng thái i của quần thể
1. Chọn cá thể pik(i) để thực hiện đột biến với xác suất pm > 0 (rất nhỏ). Vậy xác
suất để đột biến không xảy ra là 1− pm.
2. Khi đột biến xảy ra đối với pik(i), quá trình đột biến như sau:
Với các máy pih(pik(i)), h = 1, ..., m, tại mỗi máy trong số này:
+ Không gây đột biến với xác suất p > 0 (xấp xỉ 1).
+ Ngược lại, thay thế máy thứ h bởi một hoán vị bất kỳ, khác đồng nhất, với xác
suất ngang nhau. Vậy xác suất cho mỗi sự thay đổi này là:
1− p
n!− 1
. (3.1)
Với thuật toán trên, một cá thể có thể đột biến thành cá thể bất kỳ trong không gian tìm
kiếm với xác suất dương, xác suất này chỉ phụ thuộc vào p. Gọi mij là xác suất chuyển
của quần thể từ trạng thái i sang trạng thái j thông qua đột biến, thì mij > 0, ∀i, j.
Xác suất mij này chỉ phụ thuộc vào p (không tính các hằng số n đã cho), và có thể tính
cụ thể được như sau:
Xét hai trạng thái bất kỳ i, j. Giả sử i và j có K cá thể giống nhau và N −K cá thể
khác nhau ở cùng một thứ tự trong quần thể của chúng, thì:
+ Xác suất cho K cá thể đó giữ nguyên (không đột biến) là (1− pm)K .
+ Với N −K cặp cá thể khác nhau, pikt(i) và pikt(j), t = 1, 2, ..., N −K, gọi Lkt số các
máy mà có các gene giống nhau giữa pikt(i) và pikt(j), vậy m− Lkt là số máy mà có các
gene khác nhau.
- Xác suất xảy ra để Lkt máy giống nhau này là p
Lkt .
- Xác suất để m− Lkt máy khác nhau còn lại theo 3.1 là
(
1−p
n!−1
)m−Lkt
.
Do đó,
mij = (1− pm)
K .pN−Km .
N−K∏
t=1
(
pLkt .
(
1− p
n!− 1
)m−Lkt)
> 0. (3.2)
Vậy,M = [mij] là một ma trận xác suất dương.
• Ma trận xác suất chuyển trạng thái của quần thể gây ra bởi toán tử chọn
lọc
CONVERGENCE ANALYSIS OF THE NEW HYBRID GENETIC ALGORITHM 169
Toán tử thứ 3 sẽ được thực hiện để sinh ra một quần thể mới từ quần thể cũ là toán tử
chọn lọc. Gọi S là ma trận chuyển trạng thái của quần thể gây ra bởi toán tử chọn lọc,
ta có:
S =


s11 · · · s1(n!)m.N
...
. . .
...
s(n!)m.N · · · s(n!)m.N (n!)m.N


Với sij là xác suất quần thể chuyển từ trạng thái i sang trạng thái j gây ra bởi toán tử
chọn lọc.
Xác suất để một cá thể pik(i) trong quần thể hiện thời ở trạng thái i được giữ lại trong
quần thể mới là
pk = f(pik(i))/
N∑
h=1
f(pih(i)) (3.3)
Như vậy, xác suất biến đổi từ trạng thái i sang trạng thái j của quần thể gây ra bởi
toán tử chọn lọc chỉ phụ thuộc vào hàm f mà không phụ thuộc vào trạng thái hiện thời
cũng như thời điểm hiện tại của quần thể.
Từ 3.3, xác suất để quần thể hiện thời giữ nguyên trạng thái i sau phép chọn lọc sẽ là:
sii =
∏N
k=1 f(pik(i))(∑N
h=1 f(pih(i))
)N . (3.4)
Vì hàm f là một hàm luôn dương nên từ 3.4 ta suy ra: sij > 0.
Ma trận chuyển trạng thái S luôn có ít nhất một phần tử trên một cột là dương nên ma
trận S là ma trận thỏa mãn cột.
Tóm lại, quá trình sinh ra một thế hệ mới từ thế hệ cũ theo giải thuật tiến hóa truyền thống
sẽ được thực hiện thông qua 3 toán tử lai ghép, đột biến và chọn lọc với các ma trận chuyển
trạng thái C,M và S tương ứng. Gọi P là ma trận chuyển trạng thái tổng hợp từ thế hệ t
sang thế hệ t+ 1, ta có:
P =


p11 · · · p1(n!)m.N
...
. . .
...
p(n!)m.N · · · p(n!)m.N (n!)m.N

 = C×M× S
Vì các ma trận C,M và S là các ma trận ngẫu nhiên không phụ thuộc vào thời điểm cũng
như trạng thái hiện thời của quần thể nên ma trận P với các phần tử pij cũng không phụ
thuộc vào trạng thái hiện thời cũng như thời điểm của quần thể.
Lại có ma trận C,M và S là các ma trận ngẫu nhiên, M là ma trận dương và S là ma
trận thỏa mãn cột, từ Bổ đề 3.1 sau đây ta suy ra ma trận xác suất chuyển trạng thái tổng
hợp P là một ma trận ngẫu nhiên dương.
Bổ đề 3.1. (xem [4])
Gọi C,M,S là các ma trận ngẫu nhiên, trong đó M là một ma trận dương và S là ma
trận thỏa mãn cột. Khi đó tích C×M× S là một ma trận ngẫu nhiên dương.
Như vậy thuật toán tiến hóa truyền thống có thể được mô tả thông qua một xích Markov
với trạng thái của quần thể nằm trong không gian trạng thái và ma trận xác suất chuyển
trạng thái P dương. Ta suy ra thuật toán này chính là một xích Markov Ergodic (xích Markov
Ergodic xem [7]).
170 LUC TRI TUYEN, NGUYEN HUU MUI, VU DINH HOA.
3.2. Thuật toán di truyền lai mới với siêu cá thể
Với sự xuất hiện của siêu cá thể, lực lượng của quần thể sẽ tăng lên N +1, như vậy không
gian trạng thái của quần thể sẽ không còn là (n!)m×N nữa, mà sẽ là (n!)m×(N+1).
Ta đặt vị trí của siêu cá thể ở đầu của chuỗi mã hóa chiều dài (N + 1) ×m × n và ta
có thể truy xuất đến siêu cá thể đó thông qua phép chiếu pi0(i) khi quần thể ở trạng thái
i. Với mỗi trạng thái của quần thể, chúng ta có 1 siêu cá thể tương ứng đứng ở đầu, ta sắp
xếp không gian các trạng thái theo thứ tự giảm dần độ thích nghi của siêu cá thể (tức là
i f(pi0(j))) .
Khi đó ma trận chuyển trạng thái gây ra bởi các toán tử lai, đột biến và chọn lọc sẽ có
kích thước là (n!)m×(N+1) × (n!)m×(N+1), gọi C+,M+,S+ lần lượt là ma trận chuyển trạng
thái gây ra bởi các toán tử lai ghép, đột biến và chọn lọc lên quần thể có chứa siêu cá thể,
vì các siêu cá thể không tham gia vào quá trình tiến hóa nên các ma trận C+,M+,S+ sẽ có
dạng:
C
+ =


C
. . .
C

 ;M+ =


M
. . .
M

 ; S+ =


S
. . .
S


Với mỗi đường chéo bao gồm (n!)m ma trận C,M,S đã được xét trong Mục 3.1 với giải thuật
tiến hóa chưa có siêu cá thể, từ đó ta có:
C
+
M
+
S
+ =


CMS
. . .
CMS

 =


P
. . .
P


Toán tử copy được thực hiện bằng một ma trận nâng cấp U với kích thước (n!)m.(N+1) ×
(n!)m.(N+1), trong đó các phần tử được định nghĩa như sau:
Xét một quần thể có siêu cá thể và quần thể đang ở trạng thái i, gọi pil(i) là cá thể có độ
thích nghi cao nhất trong số các cá thể thường, nghĩa là:
f(pil(i)) = max{f(pik(i))|k = 1, ..., N} (3.5)
thì, uij = 1 nếu f(pi0(i)) < f(pil(i)) với j = (pil(i), pi1(i), ..., piN(i)) thuộc không gian trạng
thái. Các trường hợp còn lại, uii = 1.
Toán tử sao chép sẽ thay thế cá thể thường có độ thích nghi cao hơn so với siêu cá thể
ở cùng thế hệ vào vị trí của siêu cá thể, nếu không có cá thể nào thỏa mãn, quần thể sẽ giữ
nguyên. Ta thấy ma trận U cũng chỉ phụ thuộc vào giá trị của hàm f , như vậy ma trận U
đối với một bài toán có kích thước cố định là cố định, vì các siêu cá thể được sắp xếp theo
thứ tự giảm dần của độ thích nghi của siêu cá thể nên ma trận U sẽ có dạng:
U =


U11
. . .
U(n!)m1 U(n!)m(n!)m


trong đó các ma trận Uij có kích thước (n!)m.N × (n!)m.N .
Giả sử Bài toán 3.1 chỉ có một nghiệm tối ưu, như vậy các trạng thái từ 1 đến (n!)m×N
là các trạng thái mà tất cả có siêu cá thể (chung một siêu cá thể) mang nghiệm tối ưu (do
cách đánh số không gian trạng thái), như vậy trong ma trận nâng cấp U ở trên, chỉ có ma
CONVERGENCE ANALYSIS OF THE NEW HYBRID GENETIC ALGORITHM 171
trận con U11 là ma trận đơn vị trong khi tất cả các ma trận Uaa với a ≥ 2 là các ma trận
đơn vị với một vài phần tử trên đường chứo bằng 0. Với P = CMS thì ma trận chuyển cho
bài toán NHGA, P+, trở thành
P
+ =


P
. . .
P




U11
. . .
U(n!)m1 U(n!)m(n!)m


=


PU11
...
. . .
PU(n!)m1 · · · PU(n!)m(n!)m


Từ đây, ta có thể chứng minh được thuật toán tiến hóa với siêu cá thể có tính chất hội tụ
hoàn toàn.
Thật vậy, vì U11 là ma trận đơn vị nên PU11 = P là một ma trận ngẫu nhiên và dương.
Từ các ma trận Uaa với a ≥ 2 là các ma trận đơn vị với vài phần tử trên đường chéo chính
bằng 0 nên PUk1 6= 0 với mọi k ∈ {2, ..., (n!)m}. Do đó, các ma trận con PUa1 với a ≥ 2 có
thể hợp lại thành ma trận chữ nhật R 6= 0 và ma trận phụ hợp của ma trận P trong P+, T,
cũng khác 0:
T


PU22
...
. . .
PU(n!)m2 · · · PU(n!)m(n!)m

 6= 0
Như vậy, ma trận P+ có thể được viết thành:
P
+ =
(
P 0
R T
)
(3.6)
Mặt khác, một định lý trong lý thuyết xích Markov phát biểu như sau:
Định lý 3.1. ([7], page 126) Gọi P là ma trận chuyển cỡ n × n của một xích Markov thỏa
mãn P =
(
C 0
R T
)
, với C cỡ m×m là ma trận ngẫu nhiên Ergodic và R,T 6= 0, thì ta có:
P
∞ = lim
k→∞
P
k = lim
k→∞
(
Ck 0∑k
i=0T
iRCk−i Tk
)
=
(
C
∞ 0
R∞ 0
)
là một ma trận ổn định với P∞ = 1′Π∞ (1′ là ma trận cột toàn phần tử 1) và Π∞ = Π(0)×P∞
là các vector hàng ổn định của ma trận P∞ mà không phụ thuộc vào phân phối xác suất ban
đầu Π(0) của xích Markov và thỏa mãn điều kiện: pi∞i > 0 với mọi 1 ≤ i ≤ m và pi
∞
i = 0 với
mọi m ≤ i ≤ n.
Theo 3.6, ma trận P+ thỏa mãn các điều kiện của Định lý 3.1, nên ta có ngay
(P+)∞ =
(
P
∞ 0
R∞ 0
)
(3.7)
Như vậy, khi số thế hệ tiến tới vô cùng, phân phối xác suất trạng thái của quần thể tập trung
hoàn toàn vào (n!)m×N trạng thái đầu, mà tất cả các trạng thái này đều chứa nghiệm tối ưu
(gọi là f∗). Như vậy:
lim
t→∞
P (Zt → f
∗) = 1. (3.8)
Tức là thuật toán tiến hóa với siêu cá thể có tính chất hội tụ hoàn toàn.
172 LUC TRI TUYEN, NGUYEN HUU MUI, VU DINH HOA.
4. KẾT LUẬN
Bài báo này đã chứng minh tính hội tụ tới tối ưu toàn cục của một thuật toán di truyền
lai mới mà chúng tôi đề xuất cho bài toán lập lịch Job Shop [9]. Trường hợp chứng minh cho
tính hội tụ của thuật toán di truyền dùng mã hóa nhị phân đã được Gu¨nter Rudolph giải
quyết vào năm 1994. Tuy nhiên, mã hóa nhị phân có nhiều hạn chế trong áp dụng thuật toán
di truyền cho các bài toán phức tạp trong thực tế. Trong bài báo này, trên cơ sở phân tích
xích Markov của thuật toán di truyền, chúng tôi đã chứng minh tính hội tụ tới tối ưu toàn
cục của phương pháp mã hóa số tự nhiên. Đây là vấn đề vẫn để ngỏ trong nhiều năm qua.
TÀI LIỆU THAM KHẢO
[1] B. Giffler and G. L. Thompson, Algorithms for solving production scheduling problems, Oper-
ations Research 8 (4) (1960) 487–503.
[2] E. Seneta, None-nagative Matrices and Markov Chains, 2nd edition, New York, Springer,
1981.
[3] F. Guerriero, Hybrid rollout approaches for the job shop scheduling problem, Jounal Optimiza-
tion Theory and Applications 139 (2008) 419–438.
[4] Gu¨nter Rudolph, Convergence analysis of canonical genetic algorithms, IEEE Transactions on
Neural Networks, special issue on evolutonary computation 5 (1) (1994).
[5] J. H. Holland, “Adaptation in natural and artificial systems”, Univ. of Michigan Press, 1975.
[6] Lee Hui Peng, Sutinah Salim. A Modified Giffer and Thompson Genetic Algorithm on the job
shop scheduling problem, MATEMATIKA (Universiti Teknologi Malaysia), Vol. 22, No. 2,
pp.91-107, 2006.
[7] M. Iosifescu, Finite Markov Prosseses and Their Applications, Chichester: Wiley, 1980.
[8] Nguyen Duy Tien, Probability Madels and Applications, Part 1-Markov Chains and Its
Application, Publisher of Hanoi National University, 2001.
[9] Nguyen Huu Mui & Vu Dinh Hoa, A new hybrid genetic algorithm for Job Shop Scheduling
Problem, Proceedings of the 5-th National Conference Of Science And Technology (FAIR
2011), Đồng Nai, 2011 (238–248).
[10] N. L. J. Ulder, E. Pesch, P. J. M. Van Laarhoven, J. H. Bandelt, and E. H. L. Aarts, Genetic local
search algorithm for the traveling salesman problem, Parallel Problem Solving from Nature
1 (1994) 109–116.
[11] R. Nakano and T. Yamada, Conventional genetic algorithm for job shop problems, Proceedings
of the fourth International Conference on Genetic Algorithms, (ICGA’ 91), University of
California, San Diego, July 13-16, 1991 (474–479).
[12] Rui Zhang and Cheng Wu, A hybrid approach to large-scale job shop scheduling, Application
Intelligence 32 (2010) 47–59.
[13] T.E. Davis and J.C. Principe, A simulated annealing like convergent theory for the simple genetic
algorithm, Proceedings of the fourth International Conference on Genetic Algorithms,
(ICGA’ 91), University of California, San Diego, July 13-16, 1991 (174–181).
[14] T. Yamada, “Studies on metaheuristics for jobshop and flowshop scheduling problems”, Kyoto
University, Kyoto - Japan, 2003.
Ngày nhận bài 14 - 7 - 2012
Nhận lại sau sửa ngày 16 - 6 - 2013