1

Li núi u

Nhng nm gn õy, cựng vi s phỏt trin ca khoa hc k thut, ngi ta
ó gii quyt c nhiu bi toỏn húc bỳa bng mỏy tớnh. Nhng bờn cnh ú, vn
cũn khỏ nhiu cỏc bi toỏn vn cha tỡm c gii thut phự hp gii nú, ú l
cỏc bi toỏn ti u, trớ tu nhõn to v cỏc bi toỏn xut phỏt t thc t cuc sng
nh bi toỏn lp lch, bi toỏn iu khin Robot, bi toỏn ngi du lch,... õy l
cỏc bi toỏn cú khỏ nhiu rng buc phc tp, khụng rừ rng, ko gian tỡm kim
ln. Do ú cỏc phng phỏp truyn thng nh quay lui vột cn, leo i, mụ phng
luyn thộp, t ra ớt hiu qu, v ngi ta ó s dng mt phng phỏp khỏ ti
u ú l phng phỏp CHC v s dng trong mụ hỡnh song song.
Trong bi nghiờn cu ny nhúm tỏc gi nghiờn cu v phng phỏp CHC
s dng mụ hỡnh song song gii quyt bi toỏn MAXSAT. Chỳng ta s thy
c s ti u khi s dng mụ hỡnh song song so vi mụ hỡnh tun t v thi
gian, thớch nghi
Trong tng lai nhúm s tip tc phỏt trin ti nghiờn cu bng cỏch s
dng thut toỏn gii quyt mt s bi toỏn khỏc.
Nhúm tỏc gi xin chõn thnh cm n s giỳp tn tỡnh ca thy giỏo
Trung Kiờn ó giỳp cho nhúm trong quỏ trỡnh thc hin.
Cui cựng xin chỳc hi ngh nghiờn cu khoa hc ca chỳng ta thnh cụng
rc r.
H Ni, thỏng 04 nm 2008.
Nhúm tỏc gi.

Chng III. S dng khung thut toỏn gii quyt bi toỏn MAXSAT ..................... 16
I. c file cu hỡnh .................................................................................................... 16
II. S dng khung thut toỏn gii quyt bai toỏn MAXSAT ................................ 17
III. Kt qu thc nghim .................................................................................... 24
1. Kt qu tun t ............................................................................................. 24
2. Kt qu song song ......................................................................................... 24
THệ VIEN ẹIEN Tệ TRệẽC TUYEN
3BÁO CÁO KHOA HỌC
Đề tài:: PHƯƠNG PHÁP CHC SONG SONG

Chương I: Tổng quan về phương pháp CHC

I. Tìm hiểu chung về thuật tốn di truyền
Giải thuật di truyền là kĩ thuật giúp giải quyết bài tốn bằng cách mơ phỏng
theo sự tiến hố và đấu tranh sinhh tồn của sinh vật trong tự nhiên theo thuyết tiến
hố mn lồi của Darwin.
Mục tiêu của giải thuật di truyền: giải thuật di truyền khơng đưa ra lời giải tối
ưu mà là đưa ra lời giải gần đúng (tương đối tối ưu).
Bản chất của thuật tốn di truyền là bài tốn tìm kiếm dựa theo qui luật của
q trình tiến hố tự nhiên. Thuật tốn di truyền kết hợp sự sống sót của cấu trúc
khoẻ nhất trong số các cấu trúc biểu diễn các nhiễm sắc thể (NST) với sự trao đổi
thơng tin được lựa chọn ngẫu nhiên để tạo thành một thuật tốn tìm kiếm.
Thuật tốn di truyền sử dụng các biểu diễn nhị phân kết hợp với sơ đồ để mơ
hình hố sự chọn lọc, lai ghép và đột biến.

thích đáng như được xác định bởi ngưỡng giao phối liên tục giảm. Tốn tử chéo
(crossover) được sử dụng bởi CHC là tốn tử HUX, với HUX là đại diện cho
crossover một nửa khơng đổi. Tốn tử HUX đảm bảo chính xác một nửa của số bit
khác nhau giữa cha mẹ được trao đổi để sản sinh ra con cái.
CHC khơng được sử dụng các tốn tử đột biến trong trường hợp thơng
thường, và thực tế cùng với những quần thể nhỏ trong CHC và sự lựa chọn thế hệ
giao làm cho quần thể được hội tụ nhanh chóng. Khi quần thể được hội tụ, CHC sẽ
được khởi động lại từng phần bởi việc sao chép bởi thành viên tốt nhất của quần
thể hiện tại sang một quần thể mới và sinh ra phần còn lại của quần thể mới với
những phiên bản được biến đổi ồ ạt (35% của các bit) của thành viên tốt nhất của
quần thể hiện tại.
3. Sự Chọn lọc Elitist
Trong suốt sự chọn lọc cho việc sinh sản thay vì sự thiên về chọn lọc C(t) cho
việc sinh sản hơn vì lợi ích của những thành viên thực hiện tốt hơn trong quần thể
cha mẹ P(t-1). Mỗi thành viên của P(t-1) được sao chép thành C(t) và được ghép
đơi một cách ngẫu nhiên. (Nói cách khác, C(t) đồng nhất với P(t-1) ngoại trừ khi
trật tự của các cấu trúc đã bị thay đổi). Mặt khác, trong suốt giai đoạn chọn lọc
sinh tồn thay vì thay thế quần thể cha mẹ cũ P(t-1) bằng quần thể con C’(t) để hình
thành P(t), thế hệ con mới được tạo ra phải được cạnh tranh với các thành viên của
quần thể cha mẹ P(t-1) cho sự sinh tồn - ví dụ cạnh tranh chính là thế hệ lai. Cụ thể
hơn, các thành viên của P(t-1) và C’(t) được hồ trộn và được xếp hạng theo sự
thích hợp, và P(t) được tạo ra bằng việc chọn lọc M tốt nhất (trong đó M là kích
thước quần thể), các thành viên của quần thể được hồ trộn. (Trong các trường
hợp mà một thành viên của P(t-1) và một thành việc của C’(t) có sự thích hợp
giống nhau, thành viên của P(t-1) được xếp hạng cao hơn). Ta sẽ gọi thủ tục giữ
lại các thành viên được xếp hạng tốt nhất của các quần thể con và quần thể cha mẹ
được xáo trộn là sự chọn lọc elitist bởi vì nó đảm bảo rằng các cá thể M tốt nhất sẽ
ln sống sót.
Một vài sự chọn lọc sinh tồn thiên về tính thích hợp sử dụng của giải thuật di
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

l mt th h. Tt nhiờn, th h con khụng c giao phi li vi mt trong nhng
t tiờn xa ca nú nhng bi vỡ cỏc cỏ th tt hn s cú nhiu hu du hn. Vỡ vy,
s rt hp lý khi mt cỏ th c giao phi vi mt trong nhng h hng gn nht
ca nú. Cho n bõy gi, iu ny dn n vic lai cỏc cỏ th m chia s rt nhiu
Alen, s thụng dũ i vi s tỏi t hp nhanh chúng thoỏi hoỏ. Mc dự luụn luụn
lai mt na nhng s khỏc nhau( s dng HUX) s lm chm i quỏ trỡnh ny
THệ VIEN ẹIEN Tệ TRệẽC TUYEN
7
nhng ụi khi cỏc cỏ th c ghộp ụi li cú mt vi s khỏc bit. Nu mt hay
hai th h con sng sút i vi s giao phi ny thỡ nú chc chn s vic nh vy
cng s xy ra th h k tip.
CHC cú mt c ch b sung lm chm li tc ca s quy t- mt c ch
giỳp trỏnh s giao phi gn. Trong sut thi k sinh sn, mi thnh viờn ca
qun th cha m c chn mt cỏch ngu nhiờn m khụng thay th v c ghộp
ụi cho vic giao phi. Tuy nhiờn, trc khi giao phi thỡ khong cỏch tớn hiu
gia cỏc th h cha m tim nng c tớnh toỏn, v nu mt na khong cỏch ú (
khong cỏch tớn hiu ca cỏc th h con c mong i t cỏc th h cha m) s
khụng vt quỏ ngng khỏc nhau. Chỳng khụng c giao phi v b loi ra t
qun th con.(ngng khỏc nhau c thit lp phn bt u cho n L/4).
Chớnh vỡ vy, ch mt phn qun th c giao phi to ra th h con mi trong
bt k th h no. Khụng cú th h con no c chp nhn vo qun th cha m (
hoc l bi vỡ khụng cú bn giao phi tim nng hay bi vỡ khụng mt th h con
no tt hn qun th cha m), thỡ ngng khỏc nhau s b gim i. Hu qu ca c
ch ny ú l ch cú cỏc qun th cha m tim nng v a dng hn c giao phi
nhng s a dng c ũi hi bng ngng khỏc nhau t ng gim khi qun th
quy t mt cỏch t nhiờn. S lng nhng con sng sút cho mi th h s c
xem l thớch hp nht trong sut quỏ trỡnh tỡm kim bi vỡ khi CHC gp khú khn
trong vic tng tin trỡnh thỡ ngng khỏc nhau s gim xung nhanh hn khong
cỏch tớn hiu trung bỡnh cú nhiu cỏ nhõn hn c ỏnh giỏ. Ngc li, khi
CHC c xem l d dng to ra th h con m sng sút thỡ ngng khỏc nhau

2 initialize P(t)
3 evaluate structures in P(t)
4 while not end do
5 t = t + 1
6 select: C(t) = P(t-1)
7 recombine: C'(t) = 'incest prevention' + HUX(C'(t))
8 evaluate structures in C'(t)
9 replace P(t) from C''(t) and P(t-1)
10 if convergence(P(t))
11 diverge P(t)

Khung thuật tốn gồm hai phần cơ bản là Provides và Requires.
THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
9
Lớp Provided thực thi phía bên trong khung bao hàm các thủ tục chung cho
các bài tốn giải bằng giải thuật di truyền. Thơng thường đối với mỗi giải thuật thì
thường có một số giải pháp, tất cả các mơ hình tuần tự được nhóm vào lớp
Solver_Seq. Các mơ hình song song được nhóm vào các lớp Solver_Lan và
Solver_Wan.
Lớp Required chỉ định thơng tin liên quan đến vấn đề (bài tốn). Để cho tồn
bộ khung hoạt động thì các lớp này phải được bổ xung thơng tin về bài tốn phụ
thuộc .
1.
Các lớp đòi hỏi (Requires)
Các lớp đòi hỏi được sử dụng để lưu trữ dữ liệu cơ bản của thuật tốn. Ta có
thể hình dung các lớp Requre được xây dựng giống như một cái sườn, cái mẫu, và
đối với từng bài tốn cụ thể lại phải đắp thêm những thơng tin riêng của bài tốn
đó cho hồn chỉnh.
Nhóm các lớp Requires bao gồm các lớp sau:
• Lớp bài tốn (Problem)