TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THƠNG
──────── * ───────

TRÍ TUỆ NHÂN TẠO
Giải thuật di truyền với bài toán người du lịch
Sinh viên thực hiện

Trương Cơng Phú

20101991

Cấn Kim Tùng

20102465

Nguyễn Hồng Long

20101802

Đinh Quang Vinh

20102786

Trần Hữu Sơn

20102109

Đào Trọng Huấn

20101600

Hà N i - 2013

Bài tập lớn môn học Trí tuệ nhân tạo

0


M CL C
L I NÓI

U .................................................................................................................................... 2

CH ƠNG I : GI I THU T DI TRUY N (Genetic Algorithm - GA) ................................................. 3
1.

ng l c ..................................................................................................................................... 3

2. Thu t gi i di truy n................................................................................................................... 4
3. Các toán t di truy n ................................................................................................................... 8
4.

u tranh sinh t n ....................................................................................................................... 9

CH ƠNG II : BÀI TOÁN NG

I DU L CH (Travelling Salesman Problem - TSP) ....................... 10

1. L ch s bài toán : ....................................................................................................................... 10
2. Phát bi u bài toán : .................................................................................................................... 12

3. Phân tích
CH ƠNG III :
1. Gi i thu t

ph c t p : .............................................................................................................. 12
XU T GI I THU T DI TRUYÊN GI I BÀI TOÁN NG

I DU L CH .......... 13

xu t : .................................................................................................................... 13

1.1 Mã hóa bài toán : ................................................................................................................. 13
1.2 Kh i t o qu n th : .............................................................................................................. 15
1.3 Lai ghép : ............................................................................................................................ 15
1.4

t bi n : ............................................................................................................................ 17

1.5 Ch n l c t nhiên : .............................................................................................................. 18
1.6 Ti n hóa : ............................................................................................................................ 20
2. Gi i thi u v chương trình : ....................................................................................................... 21
3. K t qu ch y các b d li u chu!n : ........................................................................................... 22
3.1 B d li u wi29.tsp :............................................................................................................ 23
3.2 B d li u qa194.tsp: ........................................................................................................... 23
3.3 B d li u xit1083.tsp:......................................................................................................... 24
4. ánh giá gi i thu t và các c i ti n trong tương lai: ..................................................................... 25
T"NG K#T ...................................................................................................................................... 26
TÀI LI$U THAM KH O ................................................................................................................. 27
PH% L%C ......................................................................................................................................... 28


Bài tập lớn mơn học Trí tuệ nhân tạo

1


L I NĨI

U

Bài tốn ngư&i du l ch là m t trong nh ng bài toán ư'c nghiên c u sâu
nh t trong l(nh v c t)i ưu hóa. Báo cáo này s* trình bày 1 hư ng ti p c n gi i
quy t bài toán ngư&i du l ch s d+ng gi i thu t di truy n.
Gi i thu t di truy n v cơ b n mu)n mơ ph,ng l i q trình ti n hóa c-a
sinh v t trong t nhiên vào các bài toán t)i ưu hóa t. ó ưa ra l&i gi i t)t (có th
khơng là t)i ưu nh t) khi mà khơng th

ưa ra ư'c 1 gi i thu t chính xác hay

vi c vét c n các trư&ng h'p là b t kh thi.
M/c dù ã r t c) g0ng nhưng v1n khơng th tránh kh,i nh ng sai sót, mong
th y giáo ch2 b o thêm.

Bài tập lớn môn học Trí tuệ nhân tạo

2


CH

NG I : GI I THU T DI TRUY N (Genetic Algorithm - GA)

Gi i thu t di truy n c3ng như ti n hóa d a trên khái ni m cho r4ng q trình

ti n hóa t nhiên là hoàn h o nh t, h'p lý nh t và t nó ã mang tính t)i ưu. S
t)i ưu ó ư'c th hi n

ch5 th h sau bao gi& c3ng phát tri n t)t hơn th h

trư c. Ti n hóa t nhiên ư'c duy trì nh& hai q trình cơ b n: sinh s n và ch n
l c t nhiên, xun su)t q trình ti n hóa t nhiên, các th h m i luôn ư'c
sinh ra

b6 sung thay th th h c3, cá th nào thích ng v i môi trư&ng s* t n

t i, ngư'c l i s* b

ào th i.

Gi i thu t di truy n bao g m 4 bư c chính: Mã hóa l&i gi i, kh i t o qu n
th , s d+ng các phép toán di truy n và ánh giá

thích nghi. Sau ó, chúng ta

l i sinh ra m t qu n th m i b4ng phép ch n l c r i ti p t+c s d+ng các phép
tốn di truy n và ánh giá

thích nghi c-a các cá th ( i n hình b i nhi7m s0c

th - NST) trong qu n th . Thu t gi i ư'c th c hi n qua càng nhi u th h thì
l&i gi i ưa ra càng t)i ưu.
1.


ng l c

Thu t gi i di truy n cung c p m t phương pháp h c ư'c thúc !y b i s
tương t v i s ti n hóa sinh h c. Thay vì tìm ki m các gi thuy t t. t6ng quát
n c+ th ho/c t. ơn gi n
cách l/p vi c

n ph c t p, GAs t o ra các gi thuy t k ti p b4ng

t bi n và vi c tái h'p các ph n c-a gi thuy t ư'c bi t hi n t i

là t)t nh t. 8 m5i bư c, m t t p các gi thuy t ư'c g i là qu n th hi n t i ư'c
c p nh t b4ng cách thay th vài ph n nh, qu n th b i cá th con c-a các gi
thuy t t)t nh t

th&i i m hi n t i. S ph6 bi n c-a GAs ư'c thúc !y b i các

y u t) sau:
• Ti n hóa là m t phương pháp m nh, thành công cho s thích nghi
bên trong các h th)ng sinh h c.

Bài tập lớn mơn học Trí tuệ nhân tạo

3


• GA có th tìm ki m trên các khơng gian gi thuy t có các ph n tương
tác ph c t p,


ó nh hư ng c-a m5i ph n lên tồn th

thích nghi

gi thuy t khó có th mơ hình.
• Thu t gi i GA có th

ư'c th c hi n song song và có th t n d+ng

thành t u c-a ph n c ng máy tính m nh.
2. Thu t gi i di truy n
Bài toán dành cho GAs là tìm ki m trên khơng gian các gi thuy t ng c
xác

nh gi thuy t t)t nh t. Trong GAs “gi thuy t t)t nh t” ư'c

như là m t gi thuy t t)i ưu hóa m t
toán s0p t i, ư'c g i là

i lư'ng s) ư'c

nh ngh(a

nh ngh(a trư c cho bài

thích nghi c-a gi thuy t. Ví d+, n u tác v+ h c h,i

là bài toán x p x2 m t hàm chưa bi t cho t p m1u hu n luy n g m d li u
vào và d li u


u ra, thì

thích nghi có th

ư'c

nh ngh(a như là

u

chính

xác c-a gi thuy t trên d li u hu n luy n này. N u tác v+ là h c chi n lư'c chơi
c&,

thích nghi có th là s) ván th0ng c-a chi n lư'c này khi

u v i các chi n

lư'c khác trong qu n th hi n t i.
M/c dù các thu t gi i di truy n ư'c th c hi n thay 6i theo bài toán c+ th ,
nhưng chúng chia s9 chung c u trúc tiêu bi u sau: Thu t gi i ho t

ng b4ng

cách c p nh t liên t+c t p gi thuy t – ư'c g i là qu n th . 8 m5i l n l/p, t t c
các cá th

trong qu n th


ư'c ư c lư'ng tương ng v i hàm thích nghi. R i

qu n th m i ư'c t o ra b4ng cách l a ch n có xác su t các cá th thích nghi t)t
nh t t. qu n th hi n t i. M t s) trong nh ng cá th

ư'c ch n ư'c ưa nguyên

v:n vào qu n th k ti p. Nh ng cá th khác ư'c dùng làm cơ s
cá th con b4ng cách áp d+ng các tác

ng di truy n: lai ghép và

t o ra các
t bi n.

GA( Fitness, Fitness_threshold, p, r, m)

Bài tập lớn mơn học Trí tuệ nhân tạo

4


{
// Fitness: hàm gán thang i m
// Fitness_threshold: Ng

cl

ng xác


ng cho m t gi thuy t

nh tiêu chu n d ng giài thu t tìm ki m

// p: S cá th trong qu n th gi thuy t
// r: Phân s cá th trong qu n th

ư'c áp d+ng toán t lai ghép

m5i

bư c
// m: T l cá th b

t bi n

• Kh i t o qu n th : P
•

T o ng1u nhiên p cá th gi thuy t

c lư'ng: ;ng v i m5i h trong P, tính Fitness(h)

• while [max Fitness(h)] < Fitness_threshold do
T o th h m i, PS
1. Ch n cá th : ch n theo xác su t (1 – r)p cá th trong qu n th P
thêm vào PS. Xác su t Pr(hi) c-a gi thuy t hi thu c P ư'c tính
b i công th c:
Pr(hi ) =


Fitness(hi )
p
j =1

Fitness(h j )

2. Lai ghép: ch n l c theo xác su t
P, theo Pr(hi) ã tính

r× p
c/p gi thuy t t. qu n th
2

bư c trên. ;ng v i m5i c/p , t o

ra hai con b4ng cách áp d+ng toán t lai ghép. Thêm t t các các
con vào PS.
3.

t bi n: Ch n m% cá th c-a PS v i xác su t cho m5i cá th là
như nhau. ;ng v i m5i cá th bi n 6i m t bit ư'c ch n ng1u
nhiên trong cách th hi n c-a nó.

4. Cãp nh t: P
5.

cl

PS.

ng: ;ng v i m5i h trong P, tính Fitness(h)

Bài tập lớn mơn học Trí tuệ nhân tạo

5


• Tr v gi thuy t trong P có

thích nghi cao nh t.

}
Figure 1 : Các bước cơ bản của giải thuật

Bài tập lớn mơn học Trí tuệ nhân tạo

6


Kh i t o qu n th
L a ch n cha m:
Lai ghép
t bi n
u tranh sinh t n
FALSE

i u ki n d.ng
TRUE

Các cá th t)t nh t

Figure 2 : Lưu đồ giải thuật cơ bản

Bài tập lớn môn học Trí tuệ nhân tạo

7


3. Các toán t di truy n
3.1 Lai ghép :
Phép lai là quá trình hình thành NST m i trên cơ s NST cha m:, b4ng cách
ghép m t hay nhi u o n gen c-a hai (hay nhi u) NST cha m: khác nhau.
Các c/p cha m: ư'c l a ch n ng1u nhiên và xác su t x y ra lai ghép v i
m5i c/p ư'c quy

nh t. trư c.

Có nhi u cách lai ghép khác nhau:
• Lai ghép m t i m c0t, nhi u i m c0t.

• Lai ghép nhi u o n.

3.2

t bi n :

t bi n là tình tr ng NST con khơng có m t (ho/c m t s)) tính tr ng có
trong mã di truy n c-a cha m:.
Các c/p cha m: ư'c l a ch n ng1u nhiên và xác su t x y ra
m5i c/p ư'c quy
Các phép

•

t bi n v i

nh t. trư c, thư&ng là r t nh,.

t bi n thư&ng ư'c s d+ng:

o bit.

• Hốn v : 6i v trí c-a các gen v i nhau.
•
•

6i giá tr : Thay 6i giá tr t i m t i m gen.
o o n:

o th t c-a m t o n NST b t kì.

Bài tập lớn mơn học Trí tuệ nhân tạo

8


4.

u tranh sinh t n

Ch n nh ng NST t. qu n th k t qu theo m t quy t0c nào ó thay th cho
cha m:

sinh ra th h m i. M t s) phương th c

u tranh sinh t n cơ b n:

• Tráo 6i hồn tồn cha m: b4ng con.
• Tráo 6i ng1u nhiên: Ch n ng1u nhiên k cha m: và thay th b4ng k
con m i.
• Ch n nh ng cá th ưu tú nh t trong qu n th .

Bài tập lớn môn học Trí tuệ nhân tạo

9


CH

NG II : BÀI TOÁN NG

I DU L CH (Travelling Salesman

Problem - TSP)
1. L ch s bài toán :
Bài toán ngư&i bán hàng (ti ng Anh: travelling salesman problem - TSP) là
m t bài toán NP-Hard thu c th lo i t)i ưu t6 h'p ư'c nghiên c u trong lý
thuy t khoa h c máy tính. N i dung bài tốn có th hi u khái qt như sau : Cho
trư c m t danh sách các thành ph) và kho ng cách gi a chúng, tìm chu trình
ng0n nh t i qua t t c các thành ph) úng 1 l n.

Figure 3 22,775 Cities in Vietnam, derived from data from the National Imagery and Mapping Agency database of

geographic feature names.

Bài toán ư'c nêu ra l n

u tiên n
ư'c nghiên c u sâu nh t trong t)i ưu hóa. Nó thư&ng ư'c dùng làm thư c o
cho nhi u phương pháp t)i ưu hóa. M/c dù bài tốn r t khó gi i trong trư&ng h'p
t6ng quát, có nhi u phương pháp gi i chính xác c3ng như heuristic ã ư'c tìm
ra

gi i quy t m t s) trư&ng h'p có t i hàng ch+c nghìn thành ph).
Ngay trong hình th c phát bi u ơn gi n nh t, bài tốn TSP ã có nhi u

ng d+ng trong l p k ho ch, h u c n, c3ng như thi t k vi m ch, …
Ngu n g)c c-a bài toán ngư&i bán hàng v1n chưa ư'c bi t rõ. M t cu)n s6
tay dành cho ngư&i bán hàng xu t b n n
Bài tập lớn mơn học Trí tuệ nhân tạo

c p

n bài tốn này và

10


có ví d+ cho chu trình trong nư c

c và Th+y S(, nhưng khơng ch a b t kì n i

dung toán h c nào.
Bài toán ngư&i bán hàng ư'c

nh ngh(a trong th k2 19 b i nhà toán h c

Ireland William Rowan Hamilton và nhà toán h c Anh Thomas Kirkman.
Trư&ng h'p t6ng qt c-a TSP có th
tốn h c

ư'c nghiên c u l n

u tiên b i các nhà

Vienna và Harvard trong nh ng ni h c Princeton ưa ra tên bài toán ngư&i bán hàng

Hassler Whitney
ngay sau ó.

Trong nh ng nnghiên c u khoa h c

nên ph6 bi n trong gi i

Châu Âu và M=. George Dantzig, Delbert Ray Fulkerson

và Selmer M. Johnson

công ty RAND t i Santa Monica ã có óng góp quan

tr ng cho bài tốn này, bi u di7n bài toán dư i d ng quy ho ch nguyên và ưa ra
phương pháp m/t ph>ng c0t

tìm ra l&i gi i. V i phương pháp m i này, h

ã

gi i ư'c t)i ưu m t trư&ng h'p có 49 thành ph) b4ng cách xây d ng m t chu
trình và ch ng minh r4ng khơng có chu trình nào ng0n hơn. Trong nh ng th p
niên ti p theo, bài toán ư'c nghiên c u b i nhi u nhà nghiên c u trong các l(nh
v c toán h c, khoa h c máy tính, hóa h c, v t lý, và các ngành khác.
Nlà NP- y -, kéo theo bài toán TSP c3ng là NP- y -.

ây là m t lý gi i toán

h c cho s khó khM t bư c ti n l n

ư'c th c hi n cu)i th p niên 1970 và 1980 khi

Grötschel, Padberg, Rinaldi và c ng s

ã gi i ư'c nh ng trư&ng h'p lên t i

2392 thành ph), s d+ng phương pháp m/t ph>ng c0t và nhánh c n.
Trong th p niên 1990, Applegate, Bixby, Chvátal, và Cook phát tri n m t
chương trình mang tên Concorde gi i ư'c nhi u trư&ng h'p có

l n k2 l+c

hi n nay. Gerhard Reinelt xu t b n m t b d li u các trư&ng h'p có

khó

khác nhau mang tên TSPLIB n
Bài tập lớn mơn học Trí tuệ nhân tạo

11


nghiên c u

so sánh k t qu . N
ã gi i ư'c m t

trư&ng h'p có 33810 thành ph), xu t phát t. m t bài toán thi t k vi m ch.

ây

là trư&ng h'p l n nh t ã ư'c gi i trong TSPLIB.
n nay bài toán TSP v1n ư'c ti p t+c nghiên c u tìm ra l&i gi i cho các
b d li u l n hơn. Ch>ng h n b d li u c-a nư c M( v i 115,475 thành ph)
ngư&i gi i ra chu trình t)i ưu ư'c trao thư ng 500$ (thông tin chi ti t t i
/>2. Phát bi u bài toán :
(*) Các khái ni m c b n v
Phát bi u bài toán : Cho

E). Tìm chu trình

→

th s khơng

y - n 2nh vơ hư ng, có tr ng s) G = (V,

th

→. . .

s) hành trình trên các c nh ( ,

c trình bày trong báo cáo.

→

v i

) và ( ,

∈ , = 1,

sao cho t6ng tr ng

) là nh, nh t.

M t chu trình như v y cịn g i là chu trình Hamilton, nó i qua t t c các
2nh c-a

th

úng 1 l n.

3. Phân tích

th

y -, ln t n t i chu trình Hamilton.

ph c t p :

Bài tốn TSP thu c l p bài tốn NP-Khó (l p các bài tốn khơng có gi i
thu t trong th&i gian a th c).
Vi c th c hi n li t kê h t t t c các chu trình là i u g n như không th v i
s) 2nh l n (

th n 2nh ph i duy t n! chu trình). S) chu trình ph i duy t t
r t nhanh khi s) 2nh n càng l n. Ngay v i 1

th 100 2nh, vi c duy t toàn b

c3ng là i u r t khó th c hi n.

Bài tập lớn mơn học Trí tuệ nhân tạo

12

CH

NG III :

NG

I DU L CH
1. Gi i thu t
Nhóm

XU T GI I THU T DI TRUYÊN GI I BÀI TOÁN

xu t :

xu t gi i thu t di truy n ơn gi n gi i bài toán ngư&i du l ch. Gi i

thu t ư'c cài /t b4ng ngôn ng java.
Các b d li u ki m th

ư'c l y t i (cung c p

các b d li u chu!n trên th c t )
1.1 Mã hóa bài tốn :
1.1.1 Mã hóa
th

th :

ư'c mã hóa b4ng danh sách m ng các i m và t a

c-a chúng. Dư i ây là ví d+ v b d li u

tương ng

th chu!n.

NAME : xit1083
COMMENT : Bonn VLSI data set with 1083 points
COMMENT : Uni Bonn, Research Institute for Discrete Math
COMMENT : Contributed by Andre Rohe
TYPE : TSP
DIMENSION : 1083
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
1

0

105

2

0

111

3

0

15

…

…

…

Bài tập lớn mơn học Trí tuệ nhân tạo

13


u tiên là s) hi u c-a 2nh, trong s) th 2 là hoành

Tr ng s) trong c t
tr ng s) th 3 là tung

. Kho ng cách gi a 2 2nh

( , ) và

,

,

c-a

th (tr ng s) cho c nh) ư'c tính theo cơng th c :

=

,

−

+

−

1.1.2 Mã hóa chu trình (cá th - gen) :
Chu trình ư'c mã hóa b4ng m ng có th t các s) hi u c-a 2nh. V i
th n 2nh thì m ng có kích thư c n ph n t . Ví d+ chu trình c-a

th 10 2nh :

C1 1

3

2

4

6

9

8

7

5

10

C2 10

7

9

6

4

2

8

3

1

5

Ngồi ra m5i chu trình c n ph i có thêm thơng s) v chi phí c-a tồn b
chu trình ó. Chi phí này ư'c tính b4ng t6ng
trình ó (theo cơng th c tính kho ng cách ã

dài t t c các c nh t o nên chu
c p

trên).

M5i chu trình là 1 l&i gi i, trong gi i thu t di truy n coi ó như 1 cá th .
Vi c ti n hóa v sau ta s* d a trên t p chu trình kh i t o ban

u và tìm ra k t

qu t)t nh t sau m t s) th h .
Dư i ây là ví d+ v b d li u chu trình chu!n.
NAME: xit1083
COMMENT: Tour length 3558
TYPE: TOUR
DIMENSION: 1083
TOUR_SECTION

Bài tập lớn mơn học Trí tuệ nhân tạo

14


1
23
55
24
2
56
64

79
…
1.2 Kh i t o qu n th :
Qu n th ban

u ư'c kh i t o b4ng cách sinh ng1u nhiên các chu trình, s)

lư'ng chu trình kh i t o là m t n a s) kích thư c cá th t)i a. Vi c sinh ng1u
nhiên s d+ng hàm

t bi n (s* nói rõ phía dư i). S) kích thư c cá th t)i a có

th tùy bi n theo s) 2nh c-a

th c n gi i, sau nhi u l n ch y nhóm ch n kích

thư c qu n th là 100 cá th .
1.3 Lai ghép :
Phương th c lai ghép ư'c th c hi n d a trên 2 cá th

u vào :

C1 1

3

2

4

6

9

8

7

5

10

C2 10

7

9

6

4

2

8

3

1

5

Th c hi n lai ghép 1 i m c0t v i v trí c0t là ng1u nhiên :
• C0t t. i m p

n h t chu trình c-a C2 ưa vào chu trình m i, l y

m t ví d+ p = 5 :

Bài tập lớn mơn học Trí tuệ nhân tạo

15


Con 2
• Xét t.

8
u

3

1

5

n cu)i chu trình 1, n p d n các i m chưa có trong con

lai theo th t duy t ta ư'c chu trình m i :
Con 2

8

3

1

5

4

6

9

7

10

• Tính l i chi phí cho chu trình m i sinh.
m b o con lai m i là 1 chu trình th a mãn.

(*) Cách lai ghép này
Cài /t code :

! "
$

%

'

$

#
&

$

(

))
!*%+

!* +

%))
,
'

$
'

(

%

))

$

% (

'

#

%))

!* +

!*%+

&
'

%

#

#

&))
!*% ) &+

!* +

,
,
,

Bài tập lớn mơn học Trí tuệ nhân tạo

16


.
,

t bi n :

1.4

t bi n ư'c th c hi n d a trên 1 cá th

Phương th c
C1 1

3

2

4

6

9

8

7

u vào :
5

10

t bi n b4ng tráo 6i các i m trên gen cho nhau. S) l n tráo

Th c hi n

)i ư'c sinh ng1u nhiên t. trong kho ng 5% chi u dài chu trình (t c là có t)i a
t bi n), v trí i m tráo c3ng ư'c sinh ng1u

10% v trí trên 1 gen có th b
nhiên trong quá trình ch y.

t bi n C1 b4ng tráo 6i 2 l n : tráo 3 và 9, tráo 4 và 10. Khi ó

Ví d+ v i

ta ư'c chu trình m i :
C2 1
(*) Cách

9

2

t bi n này

10

6

3

8

7

5

4

m b o cá th m i sinh là 1 chu trình th a mãn.

Cài /t code :
.
!
!

.

! "

.

.

''

)

/ $
! "
! "
!

!*

!

!*

+

!

!*

+

Bài tập lớn mơn học Trí tuệ nhân tạo

+
!

!*

+

17


.

##

,
.

!

,

1.5 Ch n l c t nhiên :
Kích thư c qu n th là c)
th m i sinh b4ng lai ghép và

nh qua các th h . 8 m5i th h ta l i có các cá
t bi n do ó c n ph i có s ch n l c

mb o

tính cân b4ng c-a qu n th c3ng chính là tránh các l5i phát sinh v b nh khi
kích thư c qu n th quá l n.
!ố $á &ℎể ở 1 &ℎế ℎệ, = -í$ℎ &ℎướ$ 1ặ$ đị ℎ, + !ố $á &ℎể 1ớ 5 ℎ,
Cách th c ch n l c cá th
Cá th

ư'c ánh giá d a trên chi phí c-a m5i chu trình.

ư'c ch n làm l&i gi cu)i cùng là cá th có chi phí nh, nh t trong qu n

th sau m t s) th h ti n hóa.
Ban

u tồn b qu n th s* ư'c s0p x p t
nh ng cá th thích nghi nh t (có chi phí nh, nh t). Tuy nhiên cách làm này có
h n ch v i nh ng b d li u l n. Khi s) th h

t

n 1 m c nh t

nh, vi c

tìm ra chu trình nh, hơn ngày càng khó khg n như không bi n 6i, i u này làm gi m s

a d ng ngu n gen cho ti n hóa

các th h sau.
Do v y nhóm ưa ra cách ch n l c t nhiên như sau :
• S0p x p qu n th theo chi phí t• L a ch n ng1u nhiên 1 ch2 s) : 6 (0 < 6 < 1)

• Lo i cá th th 6 -í$ℎ &ℎướ$ 1ặ$ đị ℎ, kém thích nghi nh t t.

-í$ℎ &ℎướ$ 1ặ$ đị ℎ, cá th

• Lo i

ng

u danh sách qu n th .

n khi s) cá th cịn l i b4ng kích thư c m/c

Bài tập lớn mơn học Trí tuệ nhân tạo

nh.

18


Cách th c ch n l c này

m b o s phong phú c-a qu n th sau nhi u th

h . B4ng cài /t c+ th , cách th c ch n l c này em l i k t qu t i u h n r t
nhi u so v i cách ch n l c trư c v i m t s) b d li u.
(*) T i u Ch n l c t nhiên : Cách th c ch n l c c n

n vi c s0p x p

các cá th theo chi phí. Vi c s0p x p là r t t)n kém khi qu n th có kích thư c
l n. Gi i thu t s0p x p ã ư'c s d+ng là Selection Sort (
Ban

u,

m5i bư c ch n l c

ph c t p Θ(

)).

u s0p x p l i toàn b qu n th . Tuy nhiên có th

ch2 c n th c hi n s0p x p -í$ℎ &ℎướ$ 1ặ$ đị ℎ, cá th

u tiên

gi m b t s)

lư'ng phép so sánh và 6i ch5.
$
'

%
$

'

// Selection sort ch a t i u

$
(

%

.

)

'

-

% (

#

.

.

%

))

-

(

%))
.

-

%
,
.
.
.

.
)

.
.
,
,

T)i ưu th- t+c s0p x p trên b4ng thay vịng l/p th nh t :

Bài tập lớn mơn học Trí tuệ nhân tạo

19


•

T. : '

$

• Thành : '

.

(
$

.
(

!0

.

#
#

là !ố $á &ℎể ở 1 &ℎế ℎệ, cịn

-

-í$ℎ &ℎướ$ 1ặ$ đị ℎ,.

))
))
!0

là

.

C i ti n này em l i hi u n ng t t h n cho gi i thu t v th&i gian ch y.

Tuy nhiên so sánh trong 1 s) trư&ng h'p, cách ch n l c này cho k t qu t i hơn
kho ng 5%.
1.6 Ti n hóa :
V i qu n th kh i t o ban

u, chúng ư'c ti n hóa m t cách ng1u nhiên và

thích nghi v i i u ki n ch n l c, các cá th kém thích nghi s* b lo i th i và cá
th t)t nh t ư'c ch n làm l&i gi i.
Vi c ti n hóa di7n ra qua m t s) th h ,
và

m5i th h ta th c hi n lai ghép

t bi n ng1u nhiên trên tồn qu n th .
• Lai ghép : ng1u nhiên trong 50% s) cá th

ng

u tiên c-a qu n th

(L a ch n cha m: ng1u nhiên).
•

t bi n cho toàn b qu n th 100% (tuy i u này có v9 trái t nhiên
nhưng vi c tìm ra ngu n gen m i c n ưu tiên hơn h t).

Sau m t s) th h

nh trư c (10,000

n 10,000,000) chương trình s* d.ng

và xu t ra k t qu .
(*) C i ti n a lu ng :

t n d+ng hi u n
thu t ư'c thi t k v i 2 lu ng ch y song song. M5i lu ng ch y

c l p, th c

hi n ti n hóa cho 1 qu n th riêng bi t. K t tr v l a ch n t. k t qu t)t hơn.

Bài tập lớn mơn học Trí tuệ nhân tạo

20


2. Gi i thi u v ch ơng trình :

Figure 4 : Giao diện chương trình

Chương trình v i giao di n ơn gi n g m 1 c-a s6 nh p thông tin và hi n
k t qu . M/c

nh chương trình s*

c d li u trong các t p tin i kèm :

u vào inputGraph.txt và 1 chu trình m1u
li u trong các t p tin ph i
hóa

th

so sánh k t qu inputCircle.txt. D

nh d ng chu!n như ã

c p trong các m+c mã

th , mã hóa chu trình. N u thơng tin khơng úng

nh d nh, chương trình

s* khơng ch y.
Ngồi ra chương trình cung c p thêm 1 s) thi t l p thông s) v s) lư'ng cá
th

trong qu n th

(Population size) và s) lư'ng th

Generation). S) li u m/c

nh ban

h

ti n hóa (Max

u là 100 cá th và 10.000 th h .

gi i

h n các l5i v b nh và h n ch th&i gian ch y quá lâu, chương trình /t s?n s)
lư'ng cá th l n nh t là 1.000 và s) th h là 10.000.000 (n u nh p l n hơn s* t
ng s d+ng giá tr l n nh t).
M t thông s) n a c n ư'c nh p vào ó là Threads : thơng s) thi t l p cho
s) lu ng ch y song song c-a chương trình (s) qu n th cùng ti n hóa cùng lúc).

Bài tập lớn mơn học Trí tuệ nhân tạo

21


Thông s) này m/c
4. Thi t l p

nh thi t l p là 2 và cho phép thi t l p trong kho ng t. 1

y - các thông s), b m calculate

n

th c hi n tính tốn.

K t qu tr v g m chi phí cho ư&ng i t)t nh t mà chương trình tính tốn
ư'c và chi phí tính tốn t. chu trình m1u nh p vào (có th khơng c n nh p chu

trình

u vào). Ngồi ra chương trình hi n th th&i gian ch y theo giây và tồn b

chi ti t v chu trình tính ư'c ư'c lưu trong t p tin outputCircle.txt, b m nút
show circle

hi n xem n i dung chu trình.

Trong quá trình tính tốn, chương trình s d+ng các file t m

lưu k t qu

tính tốn trung gian và k t qu t)t nh t sau các l n ch y. Khi kh i ch y n u nh p
s?n 1 chu trình vào t p tin tempCircle.txt tương ng v i

th thì chương trình

có th s* nhanh chóng tìm ư'c k t qu t)t hơn.
3. K t qu ch y các b d! li u chu"n :
S

d+ng các b d

li u chu!n cho bài toán TSP ư'c t i v t. trang

/>D li u trong m5i b bao g m thông tin v tên b d li u, s) 2nh, d ng
th và danh sách 2nh cùng v i t a

m5i 2nh.

Nhóm l a ch n các b d li u sau

th nghi m gi i thu t :

Tên b d li u

S) 2nh

Chi phí c-a l&i gi i t)i ưu ã tìm ư'c

wi29.tsp

29

27603

qa194.tsp

194

9352

xit1083.tsp

1083

3617,26/3558

Gi i thu t ư'c cài /t b4ng ngôn ng java (jdk 7u9 - win64)

Bài tập lớn mơn học Trí tuệ nhân tạo

22


C u hình máy tính ch y gi i thu t :
Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
RAM DDR3 4GB bus 1600MHz
OS Windows 7 x64
Trong quá trình ch y s d+ng thi t l p s) cá th t)i a là 100 và s) th h
l n lư't

các m c 10.000, 50,000, 100.000, 500.000, 1.000.000, 5.000.000 tùy

b d li u. M5i m c thi t l p cho ch y 10 l n và l y ra giá tr nh, nh t

so

sánh v i chi phí t)i ưu m1u (l y t. b d li u chu!n). Chi ti t v k t qu các l n
ch y có trong Ph+ l+c i kèm báo cáo này.
Sau ây là th)ng kê k t qu ch y chương trình v i m t s) b d li u :
3.1 B d! li u wi29.tsp :
• Tên b d li u wi29.tsp (Western Sahara)
• Kích thư c

th : 29 2nh

• Chi phí chu trình t)i ưu : 27603
K t qu ch y :

Pop size

Max Gen

Min cost

%

Time

Optimal
found

100

10.000

27601,17

99,99

59

Yes

100

500.000

27601,17

99,99

903

Yes

(*) Có th do k t qu t)i ưu ư'c cung c p theo b d li u khi tính tốn ã
làm trịn nên có sai s).
K t lu n : tìm th y chu trình t)i ưu.
3.2 B d! li u qa194.tsp:
• Tên b d li u qa194.tsp (Quatar)
• Kích thư c

th : 194 2nh

Bài tập lớn mơn học Trí tuệ nhân tạo

23


• Chi phí chu trình t)i ưu : 9352
K t qu ch y :
Time

Optimal
found

122,6

17

No

10147.12

108,5

192

No

10137,51

108,4

1783

No

Pop size

Max Gen

Min cost

100

1000

11465,45

100

10000

100

100.000

%

K t lu n : chưa tìm th y chu trình t)i ưu

3.3 B d! li u xit1083.tsp:
• Tên b d li u xit1083.tsp (VLSI - XIT1083 – Vi m ch tích h'p)
• Kích thư c

th : 1083 2nh

• Chi phí chu trình t)i ưu : 3617,26/3558
K t qu ch y :
Pop size

Max Gen

Min cost

%

Time

Optimal
found

100

1000

10774,26

297,86

80

No

100

10000

8694,27

240,36

241

No

K t lu n: chưa tìm th y chu trình t)i ưu

Bài tập lớn mơn học Trí tuệ nhân tạo

24