THệ VIEN ẹIEN Tệ TRệẽC TUYEN
TRNG I HC S PHM H NI

OBO
OK S
.CO
M

KHOA CễNG NGH THễNG TIN

BO CO KHOA HC
TI:

GII THUT DI TRUYN SONG SONG V NG DNG GII
BI TON MAX- SAT

Ging viờn hng dn : Thy Trung Kiờn
Sinh viờn thc hin

: Nguyn Th La K54C

KIL

Vn Quang K55B

Trn ng Doanh- K55B



THệ VIEN ẹIEN Tệ TRệẽC TUYEN

Chng III : s dng khung thut toỏn di truyn gii quyt bi toỏn Maxsat26
1. ci t bi toỏn Max-sat...26
1.1 file cu hỡnh .cfg.26
1.2 file u vo .dat .26
2. S dng khung thut toỏn di truyn gii bi toỏn Max-sat..27
Chng III : Kt qu thc nghim ..28
1. kt qu tun t ..28
2.Kt qu song song.28

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

2



THệ VIEN ẹIEN Tệ TRệẽC TUYEN

ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

KIL
OBO
OKS
.CO
M

LI M U

Vi kh nng hin nay, mỏy tớnh ó giỳp gii c rt nhiu bi toỏn khú m
trc õy thng bú tay. Mc dự vy vn cú mt s ln cỏc bi toỏn thỳ v m
cha cú gii thut hp lý gii chỳng. Trong ú cỏc bi toỏn ti u l nng bi


CHƯƠNG I : TỔNG QUAN
1. Tổng quan thuật tốn di truyền (Genetic Algorithm)
1.1 Khái niệm

Thuật tốn di truyền cổ điền là các kỹ thuật phỏng theo q trình thích nghi
tiến hóa của các quần thể sinh học dựa trên học thuyết Darwin.

Tư tưởng của thuật tốn di truyền là mơ phỏng các hiện tượng tự nhiên: Kế
thừa và đấu tranh sinh tồn để cái tiến lời giải và khảo sát khơng gian lời giải khái
niệm kế thừa và đấu tranh sinh tồn được giải thích qua thí dụ về sự tiến hóa của
một quần thể thỏ như sau:

Có một quần thể thỏ, trong đó có một số con nhanh nhẹn và thơng minh hơn
những con khác. Những chú thỏ nhanh nhẹn và thơng minh có xác suất bị chồn
cáo ăn thịt nhỏ hơn, do đó cũng tồn tại dể làm những gì tốt nhất có thể : Tạo
thêm nhiều thỏ tốt. Dĩ nhiên, một số thỏ chậm chạp đần độn cũng sống sót vì
may mắn. Quần thể những chú thỏ còn sống sót sẽ bắt đầu sinh sản. Việc sinh
sản này sẽ tạo ra một hỗn hợp tốt về "ngun liệu di truyền thỏ". Một số thỏ
chậm chạp có con với những con thỏ nhanh, một số nhanh nhẹn có con với thỏ
nhanh nhẹn, một số thơng minh với thỏ đần độn… Và trên tất cả thiên nhiên lại
ném vào một con thỏ "hoang dã" bằng cách làm đột biến ngun liệu di truyền
thỏ. Những chú thỏ con do kết quả này sẽ nhanh hơn và thơng minh hơn những
con thỏ trong quần thể gốc vì có nhiều bố mẹ nhanh nhẹn và thơng minh hơn đã
thốt chết khỏi chồn cáo.

Khi tìm kiếm lời giải tối ưu , thuật tốn di truyền cũng thực hiện các bước
tương ứng với câu chuyện đấu tranh sinh tồn của lồi thỏ.

Nguyến Thị Lụa k54C – Đỗ Văn Quang – Trần Đăng Doanh- K55B

phỏp tỡm kim (c lp min) to c s cõn i ỏng k gia vic khai thỏc v
kho sỏt khụng gian tỡm kim.

Thc ra, GA thuc lp cỏc thut gii xut sc, nhng li rt khỏc nhng thut
gii ngu nhiờn vỡ chỳng kt hp cỏc phn t tỡm kim trc tip v ngu nhiờn.
Khỏc bit quan trng gia tỡm kim ca GA v cỏc phng phỏp tỡm kim khỏc
l GA duy trỡ v x lý mt tp cỏc li gii (ta gi l mt qun th)
Theo xut ca giỏo s John Holland, mt vn bi toỏn t ra s
c mó húa thnh cỏc chui vi chiu di bit c nh. Núi mt cỏch chớnh xỏc
l cỏc thụng s ca bi toỏn s c chuyn i v biu din li di dng cỏc
chui nh phõn. Cỏc thụng s ny cú th l cỏc bin ca mt hm hoc h s ca
mt biu thc toỏn hc. Ngi ta gi cỏc chui bớt ny l mó genome ng vi
mi cỏ th, cỏc genome u cú cựng chiu di. Núi ngn gn, mt li gii s
c biu din bng mt chui bớt, cng nh mi cỏ th u c quy nh bng
gen ca cỏ th ú vy. Nh vy, i vi thut gii di truyn, mt cỏ th ch cú

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

5



THệ VIEN ẹIEN Tệ TRệẽC TUYEN

ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

mt gen duy nht v mt gen cng ch phc v cho mt cỏ th duy nhõt. Do ú,
gen chớnh l cỏ th v cỏ th chớnh l gen.

KIL

th h khi to ban u cú c tớnh cha phong phỳ v cha phự hp nờn cỏc cỏ
th khụng ri u c khụng gian ca bi toỏn (tng t nh trng hp leo
i, cỏc ngi leo i tp trung dn vo mt gúc trờn vựng t). T ú, khú cú
th tỡm ra li gii ti u cho bi toỏn. Thao tỏc t bin s giỳp gii quyt c

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

6



THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

Đề tài: thuật tốn di tuyền song song và ứng dụng giải quyết bài tốn Max-sat

vấn đề này. Đó là sự biến đổi ngẫu nhiên một hoặc nhiều thành phần gen của
một cá thể ở thế hệ trước tạo ra một cá thể hồn tồn mới ở thế hệ sau. Nhưng

KIL
OBO
OKS
.CO
M

thao tác này chỉ được phép sảy ra với tần xuất rất thấp (thường dưới 0.01), vì
thao tác này có thể gây xáo trộn và làm mất đi những cá thể chọn lọc và lai tạo
có tính thích nghi cao, dẫn đến thuật tốn khơng còn hiệu quả.

Thế hệ mới được tạo ra lại được xử lý như thế hệ trước cho đến khi có một cá
thể đạt được giải pháp mong muốn hoặc đạt đến thời gian giới hạn.


6.
7.
8.
9.
10.

in

P(t)

t=t+1

KIL
OBO
OKS
.CO
M

5.

structures

select

C(t) from

P(t - 1)

recombine


Phộp chn lc (select): Phộp chn l quỏ trỡnh loi b cỏc cỏ th xu trong qun
th ch d li trong qun th cỏc cỏ th tt.
Phộp chn c mụ phng:

Sp xp qun th theo th t thớch nghi gim dn.

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

8



THệ VIEN ẹIEN Tệ TRệẽC TUYEN

ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

Loi b cỏc cỏ th cui dóy ch gi li n cỏ th tt nht. Gi s õy
qun th cú kớch thc c nh n.

KIL
OBO
OKS
.CO
M

Cú nhiu phng phỏp chn lc Nhim sc th:
o

Chn lc Roulette (Roulett Wheel Selection).


o

Lai ghộp cú chu trỡnh (CX cycle Crossover).

o

Lai ghộp th t tuyn tớnh (LOX Linear order Crossover).

Phộp lai to xy ra vi xỏc sut pc, c mụ phng nh sau:

Chn ngu nhiờn mt hay nhiu cỏ th bt k trong qun th. Gi
s cỏc nhim sc th ca cha m u cú m gen.

To mt s ngu nhiờn trong khong t 1 n m - 1 (c gi l
im lai). im lai chia cỏc chui cha m cú di m thnh hai
nhúm chui con vi di m1, m2 hai chui nhim sc th mi l
m11 + m12 v m21 + m22

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

9



THệ VIEN ẹIEN Tệ TRệẽC TUYEN

ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

a hai cỏ th mi vo qun th tham gia cỏc quỏ trỡnh tin


1

1

1

1

0

0

1

1

1

0

Parent 2:

0

Thỡ vic trao i chộo cỏc nhim sc th sau gen th nm s to ra hai con:

Child 1:

1


0

0

1

Child 2:

0

Phộp t bin (mutalion): Phộp t bin l hin tng cỏ th con mang mt
(hoc mt s) tớnh trng cú trong mó di truyn ca cha m, tc l s sa i mt
hoc mt vi gen ca mt nhim sc th chn bng cỏch thay i ngu nhiờn vi
xỏc sut l t l t bin.

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

10



THệ VIEN ẹIEN Tệ TRệẽC TUYEN

ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

Khụng ai cú th ỏnh giỏ c phng phỏp t bin no tt hn, do ú cú
mt vi phng phỏp n gin, cng cú vi trng hp khỏ phc tp. Ngi ta

KIL


1

1

0

1

1

1

0

0

1

1

1

0

0

1

1

sut lai, t bin)

iu kin kt thỳc

Thoỏt ra quỏ trỡnh tin húa qun th, da vo bi toỏn m cú cỏc cỏch kt thỳc
vn khỏc nhau, mt khi ó t n mc yờu cu. Mt vi trng hp thụng
thng nh sau:

Kt thỳc theo kt qu: mt khi t n mc giỏ tr yờu cu thỡ chm dt
ngay quỏ trỡnh thc hin.

Kt thỳc da vo s th h: chn s th h, quỏ trỡnh s dng li ỳng
ngay s th h ó qui nh trc, khụng cn bit kt qu nh th no.
Tớnh theo thi gian: Khụng cn bit ó bao nhiờu th h hay kt qu th
no, ch cn da vo s gi qui nh m kt thỳc.

T hp: dung nhiu phng ỏn khỏc nhau cho vn , chng hn nh:
chy theo s th h xong sau ú ỏnh giỏ cho chy theo kt qu, hoc
ngc li.

2. Mt s vớ d minh ha.
2.1 Bi toỏn Max-sat.

Vn bi toỏn SAT (SATisfiability) l vn cú tớnh ng dng rng rói c
trong lý thuyt phc tp, trong Trớ tu nhõn to hay nhng lnh vc thc t
khỏc M cn a ra nhng gii phỏp tt gii quyt.

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

12

ca bi toỏn Max-Sat.

Gii thut cha y : Ch yu da vo tỡm kim cc b v gii thut
tin húa. Tỡm kim Tabu, mụ phng luyn thộp, gii thut di truyn,
GRASP, ú l nhng vớ d v gii thut cha y gii quyt bi
toỏn Max-Sat. Tỡm kim da vo heuristics l phng phỏp gii quyt tt
tỡm kim gii phỏp tng i cho nhng bi toỏn khụng bit c v
khụng tha món li gii.

Núi chung, phng phỏp y m bo c mt li gii ti u, nhng
thi gian thc thi ca bi toỏn thỡ t l thun vi kớch thc bi toỏn. Vỡ vy ch
cú nhng bi toan nh tht s cú th gii quyt c. gii quyt nhng bi
toỏn ln, ch cú kh nng gii quyt bng cỏch s dng tỡm kim heuristics tỡm
kim mt gii phỏp tng i ti u cho cỏc bi toỏn ln trong thi gian gii
hn, nhng kh nng ti u thỡ khụng c m bo. Thc t thỡ ú l nhng s
c gng khỏc nhau kt hp nhng gii phỏp chớnh xỏc v tỡm kim heuristics.
Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

13



THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN

Đề tài: thuật tốn di tuyền song song và ứng dụng giải quyết bài tốn Max-sat

Mục đích tìm giải pháp tối ưu cho bài tốn Max-Sat tương đối khó khăn

KIL
OBO

14



THệ VIEN ẹIEN Tệ TRệẽC TUYEN

ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

trin..

KIL
OBO
OKS
.CO
M

trỡnh song song hiu bi toỏn m cha cn hiu sõu v code v quỏ trỡnh phỏt

1. Thit k khung thut toỏn di truyn.

Khung thut toỏn di truyn bao gm hai lp chớnh l: lp Provides v
Requies

1.1 Lp Provides (lp cung cpi) lm nhim v thi hnh bờn trong b khung ca
bi toỏn, nú to ra nhiu phng ỏn cho bi toỏn.

o Hm Solver: Hin th trng thỏi, xỏc sut, xỏc sut t bin v chn ra
cha m v con cỏi. Solver gm mt s hm:
Class Solver {



1.2 Lp Requied (lp yờu cu) Cỏc lp ũi hi c s dng lu tr d liu
c bn ca thut toỏn : bi toỏn, trng thỏi khụng gian tỡm kim v vo/ra. C

KIL
OBO
OKS
.CO
M

th bao gm cỏc lp.
o Bi toỏn Problem: nh ngha bi toỏn cn gii quyt bao gm mt s
hm:

Khai bỏo lp Problem cho bi toỏn Maxsat.

Class Problem {
Public:

int numvar() const;

// S bin a vo ca bi toỏn

int numclause() const;

// S mnh ca bi toỏn

int lenclause() const;

// Chiu di mnh


ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

chiu kớch thc s mnh , di mnh . Lu cỏc phn t mnh
vo mng. To ra bin _dimension. Truyn giỏ tr s mnh trong

KIL
OBO
OKS
.CO
M

pbm.numlause() ca lp Pro vo _numclause trong mng clause.
- Direction Problem::direction() const{}: Tr ra kớch thc mnh
ln nht.

- int Problem::dimension() const{}: Tr ra kớch thc mnh .
- int Problem::numclause() const : tr ra s mnh .

- int Problem::lenclause() const : tr ra di mnh
- int *Problem::clause(const int i) const:tr ra giỏ tr ca mnh th i

o Lp Solution :nh ngha mt gii phỏp cú kh thi hay khụng
Khai bỏo lp Sulutioncho bi toỏn Maxsat:
Class Solution {

friend ostream& operator> (istream& is, Solution& sol); // nhn vo cỏc

toỏn xỏc nh giỏ tr ca mnh l ỳng hay sai, v tr ra giỏ tr cho
mnh ỳng.

- double Solution::fitness(): Hm ỏnh giỏ li gii bi toỏn.
- void Solution::to_Solution(char *_string_) : duyt tng phn t ca
mnh .

- void Solution::add(unsigned long element) :Phng thc thờm vo
mt li gii phự hp.

- void Solution::initialize_feasibles(Feasibles &_feasibles): khi to giỏ
tr ban u cho li gii kh thi. Nu (_freedomV[i] > 0) thỡ thờm giỏ tr
ú vo danh sỏch li gii kh thi.

- void Solution::update(Feasibles &f,unsigned long &selection) : cp
nht li gii kh thi vo trong danh sỏch li gii kh thi
o Lp kim tra iu kin dng (StopCondition).

xỏc nh iu kin dng ca bi toỏn, trong tng bi toỏn thỡ iu kin
dng s khỏc nhau, thng cn c vo mt hoc mt vi tham s nh s th h,
thi gian chy, cỏc iu kin c thự ca bi toỏn.
o Lp chộo húa Crossover.

requires class Crossover: public Intra_Operator
{
public:

Crossover();

virtual ~Crossover();

requires class Mutation: public Intra_Operator
{
public:

Mutation();

virtual ~Mutation();

friend ostream& operator

time_spent_in_trial = _used_time(start_trial);
total_time_spent

= start_global + time_spent_in_trial;

// ly li trng thỏi vi nhng giỏ tr ny
RefreshState();

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

20



THệ VIEN ẹIEN Tệ TRệẽC TUYEN

ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

KIL
OBO
OKS
.CO
M

RefreshCfgState();

if( (current_iteration() % params.refresh_global_state()) == 0)
UpdateFromCfgState();





THệ VIEN ẹIEN Tệ TRệẽC TUYEN

ti: thut toỏn di tuyn song song v ng dng gii quyt bi toỏn Max-sat

a ta thớch nghi tt nht;

KIL
OBO
OKS
.CO
M

}

3. Khung thut toỏn song song.

3.1 La chn mụ hỡnh phn cng:

Cú hai mụ hỡnh ú l: mụ hỡnh phn cng phõn tỏn v mụ hỡnh phn cng dựng
chung.

+ Mụ hỡnh phn cng dung chung:
u im: tc nhanh

Nhc im: giỏ thnh cao.
+ Mụ hỡnh phn cng phõn tỏn:
u im: d ci t.

thut tin húa mt cỏch c lp, s dng cỏc qun th ph riờng bit cỏc b vi x

KIL
OBO
OKS
.CO
M

lý hp tỏc vi nhau bng vic thay i v trớ mt cỏch u n. Mụ hỡnh o c
bit thớch hp cho cỏc nhúm mỏy tớnh khi giao tip b hn ch.

- Mụ hỡnh khuch tỏn (Diffusion model): mi cỏ nhõn l mt khụng gian
c sp xp v kt hp vi cỏ nhõn khỏc t mt mng ni b bờn cnh. Khi x
lý song song cú rt nhiu b vi x lý giao tip vi nhau (nh l nhng cỏ nhõn
giao tip vi hng xúm trong mi tng tỏc), nhng giao tip ch trong ni b.
Vỡ vy mụ hỡnh ny ch phự hp vi h thng mỏy tớnh song song ln vi mng
ni b tc cao.

Do ú ta s la chn mụ hỡnh phn mm l mụ hỡnh o (Island model).
Hm void Solver_lan:: DoStep()

Voi Solver_lan::DoStep()
{

current_iteration(current_iteration()+1);
current_population.evolution();

current_evaluations(current_population.evaluations());
_netstream

time_spent_in_trial = _used_time(start_trial);
total_time_spent

= start_global + time_spent_in_trial;

// refresh state with these values
RefreshState();

RefreshCfgState();

// in this iteration i have to send data about my local state to the

global state

if ((int)current_iteration() % params.refresh_global_state()

==0)

{

send_local_state_to(mypid);
UpdateFromCfgState();

}

_stat.update(*this);

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B


Solver.run(); // thc hin hm run
Nu l mỏy ch (pid()= =0) thỡ
{

Gi n hm hin trng thỏi (show_state());
a ra gii phỏp tt nht;

a ta thớch nghi tt nht;

}

Nguyn Th La k54C Vn Quang Trn ng Doanh- K55B

25