MC LC
Trang
Đặt vấn đề 1
CHNG 1 : TNG QUAN 2
1.1. Sơ lc v hệ thống điện 2
1.2. Vai trò của li điện phân phối 3
1.3. Đặc đim chung của li điện phân phối 3
1.4. Gii thiệu bài toán 4
1.5. Phân loi các phơng pháp gii bài toán tái cấu trúc 4
1.6. Mc tiêu và nhiệm v của lun văn 10
1.6.1 Các mc tiêu 10

1.6.2 Các nhiệm v c th 10
1.6.3 Phơng pháp nghiên cứu 11
CHNG 2 : C S LÝ THUYT 12
2.1. Mô hình toán của tái cấu trúc mng điện 12
2.2 Thut toán di truyn (GA) 14
2.2.1 Gii thiệu . 14
2.2.2. Các phép toán của thut toán di truyn 14
2.2.3. Cấu trúc của thut toán di truyn tổng quát . 19
2.2.4. Kt lun . 20
2.3. Thut gii Heuristic . 22
2.3.1. Tổng quan . 22
2.3.2 Ni dung thut gii Heuristic 22
2.3.3. Các phơng pháp tìm kim Heuristic 25
2.3.3.1 Cấu trúc chung của bài toán tìm kim 25
2.3.3.2 Tìm kim chiu sâu và tìm kim chiu rng 26
2.3.3.3 Tìm kim leo đồi 29
2.3.3. Các phơng pháp tìm kim Heuristic 22
CHNG 3 : ÁP DNG THUT TOÁN HEURISTIC VÀO BÀI TOÁN. 31


CHNG 6 : KT LUN VÀ HNG PHÁT TRIN
6.1. Kt lun 61
6.2. Hng phát trin 61

Tài liệu tham kho 62
CÁC T VIT TT
GA Genetic algorithms
KCL Kirchhoff current law
KVL Kirchhoff voltage law
SCADA Supervisory Control and Data Acquisition
Xu th kinh t, chính trị và xã hi đang thịnh hành trên th gii chỉ ra rằng cần phi
làm cho việc phát điện, truyn ti điện và phân phối điện ngày càng có hiệu sut cao.
Trong quá khứ, các kỹ s điện chỉ quan tâm nghiên cứu trên lĩnh vực phát điện
và truyn ti, hệ thống điện phân phối ít đc quan tâm. Chỉ gần đơy các kỹ s mi
đc trang bị các phng tiện đ đng đầu vi khối lng tính toán ln trong hệ
thống phân phối trong việc mô phỏng và mô hình chính xác. Vì xã hi ngày càng lệ
thuc hn vƠo đ tin cy cung cp điện năng, hệ thống điện phân phối tr nên rt quan
trọng. Các nghiên cứu gần đơy đƣ chỉ ra rằng tn tht trên đng dây phân phối chim
13% tng công sut điện phát ra. Do đó mỗi phng cách lƠm gim tn tht, tăng đ
tin cy cung cp điện trong hệ thống phân phối đu xứng đáng đc nghiên cứu.
Hiện có nhiu gii pháp làm gim tn tht  cp phân phối: tái cu trúc, lắp đt
t bù, cân bằng ti, đa vƠo cp điện áp cao hn vƠ thay đi vt liệu dn điện. Mc dù
hiện có nhiu phng pháp lƠm gim tn tht, tuy nhiên khó có th đo lng, so sánh
các phng pháp v mt phí tn tài chánh. Trong những trng hp nht định, lắp
thit bị đ làm gim tn tht có th không hiệu qu v mt chi phí hoc nó có th làm
gim đ tin cy của hệ thống. Sự ra đi của hệ thống giám sát điu khin và thu nhn
dữ liệu (SCADA) đƣ cho phép sử dng đ quan sát vƠ điu khin từ xa các thit bị
đóng cắt của mng điện phân phối.
Nhiu chng trình máy tính đƣ đc lp ra đ tìm cu trúc mng điện vi tn tht nhỏ
nht dựa trên các ràng buc cho trc. Cu trúc này có th đt đc bằng cách thay
đi trng thái đóng/m của các thit bị đóng, cắt trên các đng dây liên kt (lƠ đng
dây có thit bị đóng cắt  c hai đầu). Thủ tc nƠy đc gọi là tái cu trúc mng điện.
Những ngi đi tiên phong trong lĩnh vực nƠy lƠ A. Merlin vƠ H. Back, đƣ
nghiên cứu vƠ đa ra vn đ nƠy vƠo năm 1975. Tuy nhiên mƣi đn những năm cuối
thp kỷ 1980 và suốt thp kỷ 1990, vn đ này mi đc nhiu nhà khoa học nghiên
cứu vƠ đa ra các phng pháp gii khác nhau.
Vn đ này nghe có vẻ đn gin, nhng ti sao li lôi cuốn nhiu nhà khoa học
nghiên cứu nh vy vƠ đn nay đƣ mang li kt qu, ứng dng nào trong thực tiễn hay
cha. Trong lun văn s nghiên cứu các vn đ nƠy vƠ đa ra mt phng pháp gii có
th áp dng đ tính toán, vn hƠnh li điện phân phối .

. Li truyn ti (35, 110, 220KV).
. Li phân phối trung áp (6, 10, 15, 22, 35KV).
. Li phân phối h áp (0,4KV, 0,22KV).
1.2/ Vai trò của lưới điện phân phối:
Các nhƠ máy điện thng đc xây dựng  những ni gần ngun nhiên liệu
hoc việc chuyên ch nhiên liệu thun li, ít tốn kém. Trong khi đó các trung tơm ph
ti li  xa, do vy phi dùng li truyn ti đ chuyn ti điện năng đn các h ph
ti. Vì lý do kinh t cũng nh an toƠn, không th cung cp điện trực tip cho các ph
ti bằng li truyn ti, do vy phi dùng li điện phân phối.
Li điện phân phối thực hiện nhiệm v phân phối điện cho mt địa phng
(mt thành phố, qun, huyện,…) có bán kính cung cp điện nhỏ, di 50km.
Mng điện phân phối có nh hng ln đn các chỉ tiêu kinh t kỹ thut của
toàn hệ thống, c th là:
1/ Cht lng cung cp điện:  đơy lƠ đ tin cy cung cp điện vƠ đ dao đng của
điện áp ti h ph ti.
2/ Tn tht điện năng: Thng tn tht điện năng  li phân phối ln gp 3 đn 4 lần
so vi tn tht điện năng  li điện truyn ti.
3/ Giá đầu t xơy dựng: Nu chia theo tỷ lệ cao áp, phân phối trung áp, phân phối h
áp thì vốn đầu t mng cao áp là 1, mng phân phối trung áp thng từ 1,5 đn 2 và
mng phân phối h áp thng từ 2 đn 2,5 lần.
4/ Xác sut sự cố: sự cố gây ngừng cung cp điện sửa chữa bo dỡng theo k hoch,
ci to, đóng trm mi trên li phân phối cũng nhiu hn li truyn ti.
1.3/ Đặc điểm chung của lưới điện phân phối:
1/ Ch đ vn hƠnh bình thng của li điện phân phối là vn hành h, hình tia hoc
dng xng cá. Đ tăng cng đ tin cy cung cp điện, mng điện phân phối thng
đc thit k dng mch vòng nhng vn hành h.
2/ Trong mch vòng các xut tuyn đc liên kt vi nhau bằng dao cách ly, hoc thit
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 4
bị nối mch vòng (Ring Main Unit). Các thit bị này vn hành  trng thái m. Trong

vn đ xác định mt cây tối u của đ thị đƣ cho.
1.5 Phân loại các phương pháp giải bài toán tái cấu trúc
Các thut toán tái cu trúc trên th gii có th phơn loi theo phng pháp gii.
- Phng pháp hỗn hp heuristic vƠ tối u.
- Phng pháp thuần túy heuristic.
- Phng pháp tp các chỉ số.
- Phng pháp hỗn hp heuristic vƠ m.
- Phng pháp thông minh nhơn to: bao gm mng n ron, hệ chuyên gia,
gen, hỗn hp gen vƠ heuristic.
- Phng pháp trí thông minh bầy đƠn.
Phần tip theo trình bƠy lần lt theo từng phng pháp gii:
i/Phng pháp hỗn hp heuristic và tối u:

Merlin và Back lƠ ngi đầu tiên đt vn đ tái cu trúc hệ thống điện phân phối nhằm
gim tn tht điện năng. Họ sử dng phng pháp hỗn hp heuristic và tối u đ xác
định cu hình của mt hệ thống phân phối vn hành vi tn tht nhỏ nht.
Merlin và Back mô hình hệ thống phân phối bằng mt cu trúc cây m rng. Các đon
dây của hệ thống phân phối đc biu diễn bằng các nhánh và các thanh cái bằng các
nút. Nh mt vn đ m rng cây, cu hình mng tối u có th đc xác định từ các
giá trị bin nhị phơn tìm đc ứng vi các trng thái khóa điện. Trong thut gii
Merlin và Back bỏ qua các ràng buc của hệ thống. Sau đó Shirmohammadi vƠ Hong
đƣ hiệu chỉnh phng pháp nƠy bằng cách xét đn các ràng buc của dòng và áp trên
đng dây. Đng thi Shirmohammadi và Hong sử dng kỹ thut phân bố công sut
dựa trên sự bù đ mô phỏng mng nối vòng “yu” đc chính xác hn.
- Thut toán Merlin vƠ Back đƣ đc hiệu chỉnh:
Thut toán đầu tiên của Merlin và Back chỉ tính ti thành phần thực của dòng khi tính
tn tht và gi thit rằng có th bỏ qua góc điện áp. Đ biu thị cho hệ thống đƣ đc
phơn tích trc đó, Merlin vƠ Back đƣ xp xỉ đáp ứng của hệ thống phân phối bằng
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 6

tht trong mt khong thi gian (gim tn tht năng lng). Trong đó trình bƠy đầy đủ
nht, có th áp dng trong vn hƠnh thực t lƠ bƠi báo của Dariush Shirmohammadi và
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 7
các cng sự đa ra.
BƠi toán thứ ba đc Aoki vƠ các cng sự đ cp đn đầu tiên. Tuy nhiên  bƠi
báo nƠy Aoki vƠ các cng sự chỉ mi gii bƠi toán vi ti không đi. Sau đó thut toán
nƠy đƣ đc Yuan-Yih Hsu vƠ các cng sự gii chi tit hn vƠ có đ cp đn ti thay
đi.
iii/ Phng pháp tp các chỉ số:

Phng pháp nƠy do Whei-Min Lin và Hong-Chan Chin, thƠnh viên của phòng Kỹ
Thut Điện đi học Quốc gia Sun Yat-Sen ĐƠi Loan đa ra vƠ đc đăng trên tp chí
IEEE Trans. on Power Delivery vƠo năm 1998.
Trong bƠi báo nƠy định nghĩa 3 tp chỉ số đóng cắt. Điện áp nhánh vƠ các hằng số
đng dơy đc sử dng vi tt c các rƠng buc v điện. Mng vòng đc xét thay vì
mng hình tia bằng cách đóng tt c các khóa điện liên kt. Bằng cách chỉ xét các chỉ
số đóng cắt ln nht trong mỗi vòng, thut toán nƠy có th lƠm gim số trng thái cần
xét mt cách đáng k. Trong bƠi nƠy gii quyt hai vn đ: gim tn tht vƠ duy trì
dịch v cung cp điện.
iv/ Phng pháp hỗn hp heuristic vƠ m:

Phng pháp nƠy đc Whei-Min Lin, Hong-Chan Chin và Gyne-Jong Yu - thành
viên của phòng Kỹ Thut Điện đi học quốc gia Sun Yat-Sen, Kaohsiung, ĐƠi Loan
đa ra trong hi nghị khoa học v ngƠnh điện trên th gii năm 1999.
BƠi báo nƠy trình bƠy mt k hoch đóng cắt khóa điện dựa trên heuristic đ gii quyt
vn đ gim tn tht trên đng dơy phơn phối bằng các ký hiệu m. Bằng cách sử
dng thut toán đ nghị, có đc mt cu trúc mng có hiệu qu trong việc gim tn
tht. Trong bƠi báo nƠy định nghĩa mt vƠi hƠm thƠnh viên. Thông qua “tp hp” các
phép tính trên các hƠm thƠnh viên, có th xác định đc trng thái đóng-m của các

Ko vƠ Jung vƠo năm 1993. Trong đó tp hun luyện của các ANN lƠ cu hình hệ thống
điện tối u ứng vi các mô hình ph ti khác nhau, đt đc tn tht bé nht trong các
điu kiện cho trc.
Khi xác định cu trúc hệ thống điện tối u theo mô hình ph ti, ANN dựa trên sự hiu
bit c bn đƣ đc hun luyện trong tp hun luyện. Thay vì lp đi, lp li quá trình
chuyn ti vƠ đánh giá tn tht nh trong thut toán truyn thống.
Vi kh năng mô t các mối quan hệ phức tp vƠ kh năng lƠm việc song song trên
phần cứng máy tính, ANN có th tính toán cho ra đc mô hình tối u, điu khin
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 9
đc hệ thống điện phơn phối tự đng trong thi gian thực. Trong khi điu nƠy có th
không thực hiện đc bằng các kỹ thut tính toán truyn thống.
Tuy nhiên do sử dng máy tính đn gin (Compaq 386) đ mô phỏng vn đ nên các
tác gi đƣ đn gin hóa mô hình. Do đó sai số trong phép gii vn còn ln.
Sau đó năm 1996, Gauche vƠ Coelho đƣ đ nghị sử dng mô phỏng Monte Carlo đ
thống kê li nhu cầu ph ti theo cách tốt hn, cần thit trong quá trình hun luyện
ANN. Trong trng hp nƠy tng tự vi các công việc thực hiện của Lim, Ko vƠ
Jung, gii pháp tối u vn không đc đm bo.
Năm 1997, Gauche đ nghị sử dng thut toán lp trình số nguyên đƣ đc đa ra bi
Sarma vƠ Rao (1995) đ đm bo sự tối u của gii pháp. Thut toán nƠy bắt đầu bằng
kt qu đa ra bi ANN theo hng gii tối u vn đ.
Gần đơy nht lƠ năm 1999, trong hi nghị khoa học v ngƠnh điện hƠng năm trên th
gii, Gauche, Coelho vƠ Teive đƣ đa ra thut toán hỗn hp Back-Propagation và
Marquardt-Levenberg đ gii quyt vn đ.
v.2/ Phng pháp hệ chuyên gia:
Nh các thut toán dựa trên heuristic, các lut đc sử dng cho hệ chuyên gia dựa
trên các rƠng buc trong vn hƠnh hệ thống, không dựa trên kt qu đo đ gim tn
tht trực tip.
1/ Thut toán của Liu, Lee vƠ Vekata:
Thut toán nƠy đc các tác gi Chen-Ching Liu, Seung Jae Lee và S.S. Vekata

gim tn tht” của tác gi Joon-Ho Choi, thƠnh viên dự thính của IEEE vƠ Jae-Chul
Kim, thƠnh viên của IEEE đăng  hi nghị ngƠnh điện th gii năm 2000:
Thut toán gen lƠ mt phng pháp gii quyt vn đ bƠi toán dựa trên mô phỏng quá
trình tin hóa thích nghi của sinh vt, chủ yu đc sử dng nh các phng pháp tối
u. Trong thut toán nƠy, tp các chuỗi (hay nhiễm sắc th) đc sinh ra theo mt quá
trình chọn lựa, tng tự nh “chọn lựa tích cực” của Darwin. Thut toán gen hoƠn toƠn
đn gin, chỉ việc sao chép các chuỗi vƠ thay đi các phần chuỗi bằng 3 toán tử gen,
đó lƠ tái sn sinh, lai hóa vƠ đt bin. Sự tin hóa của dơn số đc thực hiện bằng sự
tái sn sinh của các cá nhơn theo đ thích nghi tng ứng của chúng. Thut toán gen
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 11
sử dng mt tp hp (dơn số) các chuỗi, có nghĩa lƠ có nhiu đim tìm kim. Vì vy nó
lƠ mt phng pháp tìm kim song song. Nó hiệu chỉnh các chuỗi (các đim tìm kim)
sử dng các chọn lựa tự nhiên vƠ các phép toán gen đó lƠ lai hóa vƠ đt bin.
A. Biu diễn chuỗi dựa trên các chin lc Heuristic:
Đối vi mng phơn phối, đóng mt khóa liên kt s to mt vòng. Thut toán đ nghị
bắt đầu bằng việc đóng tt c các khóa điện đ to mt mng vòng. Mng vòng nƠy s
bao gm nhiu vòng đóng vƠ mỗi vòng phi có mt đim m “tốt nht” đ tối thiu
tn tht. M mt khóa điện trong mỗi vòng s có đc cu trúc mng hình tia. Tip
theo lƠ các biu diễn chuỗi:
(1) Mỗi gen biu diễn cho mt khóa m trong vòng. Vì vy đ dƠi của chuỗi bằng số
vòng.
(2) Nu chuỗi có cùng mt gen thì mng có mt vòng. Vì vy mỗi gen trong chuỗi lƠ
khác nhau.
(3) Nu chuỗi có hai hay nhiu gen lƠ khóa điện thông thng trong hai vòng khác
nhau thì mng có mt nút bị cách ly.
B. Quá trình tái sn sinh, lai hóa vƠ đt bin:
Trong quá trình tái sn sinh, chọn mt tp hp các chuỗi cũ đ sn sinh mt tp các
chuỗi mi dựa theo tính hp lý đc xác định bằng mô phỏng bƠn Roulet có trọng số.
BƠn Roulet hng theo đ thích nghi của mỗi li gii ứng viên. Trong quá trình lai

ra phng pháp gii quyt bài toán:
Chuyn ti giữa các trm bin áp trung gian 110/15KV vƠ các tuyn dơy 15KV
thông qua điu khin đóng/cắt các khóa điện (Recloser, Load Break Switch,
Disconnection Switch,…) đ đt tối thiu tn tht công sut vi các điu kiện rƠng
buc thực t. 








n
i
i
lossf
1
/1
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 13
CHNG 2 : C S LÝ THUYT
2.1 Mô hình toán của tái cấu trúc mạng điện
Các mô hình toán học của tái cu trúc mng điện có th đc th hiện bi dòng điện
nhánh hoc công sut nhánh.
(1) Sử dng bin dòng điện


N: Tp các nút.
NL: Tp các nhánh.
Trong mô hình trên, phng trình (2) là ràng bun v dòng điện trong nhánh. Phng
trình (3) là ràng buc điện áp nút. Phng trình (4) đi diện cho lut Kirchhoff 1
(KCL), vƠ phng trình (5) đi diện lut Kirchhoff 2 (KVL). Phng trình (6) là ràng
buc v hình học đ đm bo cu trúc tia của mỗi cu trúc liên kt ứng viên. Nó bao
gm hai cu trúc ràng buc:
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 14
(a) Tính kh thi: Tt c các nút trong mng phi đc kt nối bi mt số nhánh, tức là,
không có nút riêng biệt.
(b) Cu hình tia: Số lng nhánh trong mng li phi nhỏ hn số lng các nút bi
mt đn vị (K
l
* NL = N - 1)
Do đó, cu hình mng cuối cùng phi đc bố trí hình tia và tt c các ti duy trì kt
nối.
(2) Sử dng bin công sut

Vi điu kiện
g
i
(P,k)=0 (10)
g
i
(Q,k)=0 (11)
g

Thut toán di truyn cũng nh các thut toán tin hóa nói chung, hình thành dựa trên
quan niệm cho rằng, quá trình tin hóa tự nhiên là quá trình hoàn ho nht, hp lý nht
và tự nó đƣ mang tính tối u. Quan niệm này có th xem nh mt tiên đ đúng,
không chứng minh đc, nhng phù hp vi thực t khách quan. Quá trình tin
hóa th hiện tính tối u  chỗ, th hệ sau bao gi cũng tốt hn (phát trin hn, hoƠn
thiện hn) th hệ trc bi tính k thừa và đu tranh sinh tn.
Các tính chất đặc thù của thuật toán di truyền
‹ GA lp lun mang tính cht ngu nhiên (stochastic) thay vì xác định (deterministic)
nh toán học gii tích.
‹ GA xét duyệt toàn b các gii pháp, sau đó lựa chọn gii pháp tốt nht dựa trên hệ số
thích nghi.
‹ GA chỉ tp trung vào gii pháp (dãy số tng trng cho gii pháp) mà không cần
quan tâm đn chi tit vn đ.
‹ GA thích hp cho việc tìm điu kiện tối u cho việc điu hành và phân nhóm những
gii pháp có đc.
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 16
2.2.2 Các phép toán của thut toán di truyn
1. Tái sinh (Reproduction)
Tái sinh là quá trình chọn quần th mi thỏa phân bố xác sut dựa trên đ thích nghi.
ð thích nghi là mt hàm gán mt giá trị thực cho cá th trong quần th. Các cá th có
đ thích nghi ln s có nhiu bn sao trong th hệ mi. Hàm thích nghi có th không
tuyn tính, không đo hàm, không liên tc bi vì thut toán di truyn chỉ cần liên kt
hàm thích nghi vi các chuỗi số.
Quá trình này đc thực hiện dựa trên bánh xe quay roulette (bánh xe s xố) vi các
rãnh đc định kích thc theo đ thích nghi. Kỹ thut này đc gọi là lựa chọn
cha mẹ theo bánh xe roulette. Bánh xe roulette đc xây dựng nh sau (gi định rằng,
các đ thích nghi đu dng, trong trng hp ngc li thì ta có th dùng mt vài
phép bin đi tng ứng đ định li tỷ lệ sao cho các đ thích nghi đu dng).
-Tính đ thích nghi f

Bảng 1:Các nhiễm sắc thvà các giá trị thích nghi
Nhiễm sắc th
Chuỗi mã hóa
Trị thích nghi f(i)
1
01110
8
2
11000
15
3
00100
2
4
10010
5
5
01100
12
6
00011
8

-Tìm tng giá trị thích nghi toàn quần th:
-Tính xác sut chọn p
i
cho mỗi nhiễm sắc th:

-Tính vị trí xác sut q
i

4
10010
5
0,1
0,6
5
01100
12
0.24
0.84
6
00011
8
0.16
1

Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 18
Bây gi ta quay bánh xe roulette 6 lần, mỗi lần chọn mt nhiễm sắc th cho quần th
mi. Giá trị ngu nhiên của 6 sốtrong khong [0÷1] và các nhiễm sắc th tng ứng
đc chọn đc cho trong bng 2.

Bảng 3:Quần th mi
Số lần quay
1
2
3
4
5
6

có mt số nhiễm sắc th đc chọn nhiu lần, các nhiễm sắc th có đ thích nghi cao
hn s có nhiu bn sao hn, các nhiễm sắc th có đ thích nghi kém nht thì dần dần
cht đi.
Sau khi lựa chọn đc quần th mi, bc tip theo trong thut toán di truyn là thực
hiện các phép toán lai ghép vƠ đt bin.
2. Lai ghép (Crossover)
Phép lai là quá trình hình thành nhiễm sắc th mi trên c s các nhiễm sắc th cha -
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 19
mẹ, bằng cách ghép mt hay nhiu đon gen của hai (hay nhiu) nhiễm sắc th cha -
mẹ vi nhau. Phép lai xy ra vi xác sut p
c
, đc thực hiện nh sau:
- Đối vi mỗi nhiễm sắc th trong quần th mi, phát sinh ngu nhiên mt số r
trong khong [0÷1], nu r < p
c
thì nhiễm sắc th đó đc chọn đ lai ghép.
- Ghép đôi các nhiễm sắc th đƣ chọn đc mt cách ngu nhiên, đối vi mỗi cp
nhiễm sắc th đc ghép đôi, ta phát sinh ngu nhiên mt số nguyên pos trong khong
[0 ÷ m-1] (m là tng chiu dài của mt nhiễm sắc th - tng số gen). Số pos cho bit vị
trí của đim lai. Điu này đc minh họa nh sau:

- Chuyn đi các gen nằm sau vị trí lai.

Nh vy phép lai này to ra hai chuỗi mi, mỗi chui đu đc thừa hng
những đc tính ly từ cha và mẹ của chúng. Mc dù phép lai ghép sử dng lựa chọn
ngu nhiên, nhng nó không đc xem nh lƠ mt lối đi ngu nhiên qua không
gian tìm kim. Sự kt hp giữa tái sinh và lai ghép làm cho thut toán di truyn hng
việc tìm kim đn những vùng tốt hn.
3. Đt bin (Mutation)

Ta xây dựng hàm thích nghi f(x) nhn giá trị không ơm. Có 2 trng hp:
‹ đối vi bài toán tìm cực tiu hàm g(x)

Có th ly C
max
là giá trị g ln nht trong quần th hiện ti.
‹ đối vi bài toán tìm cực đi hàm g(x)

Có th ly C
min
là trị tuyệt đối của u bé nht trong quần th hiện ti.
2.2.3 Cu trúc của thut toán di truyn tng quát
Thut toán di truyn bao gm các bc sau:
Lun văn tốt nghiệp Cao học GVHD:PGS-TS Quyn Huy Ánh
HVTH: Hà Huy Chin 21
Bc 1: Khi to quần th các nhiễm sắc th. Chọn mô hình cho gii pháp của
vn đ. Chỉ định cho mỗi gii pháp mt ký hiệu.
Bc 2: Tìm hàm thích nghi và xác định giá trị thích nghi của từng nhiễm sắc
th.
Bc 3: Sao chép li các nhiễm sắc th dựa vào giá trị thích nghi của chúng
(to sinh) và to ra những nhiễm sắc th mi bằng các phép toán di truyn (lai ghép
hay đt bin).
Bc 4: Tính hệ số thích nghi cho các thành viên mi đ loi bỏ những
thành viên không phù hp trong quần th.
Bc 5: Nu cha tìm đc gii pháp tối u thì tr li bc 3. Nu mc tiêu
tìm kim đƣ đt đc thì dừng li. Báo cáo kt qu.