vii
MC LC
Trang tựa TRANG
Quytăđnhăgiaoăđ tài
LÝ LCH KHOA HC i
LIăCAMăĐOAN iii
LIăCÁMăN iv
TÓM TT LUNăVĔN v
ABSTRACT vi
MC LC vii
DANH SÁCH CÁC CH VIT TT x
DANH SÁCH CÁC HÌNH xi
DANH SÁCH CÁC BNG xii
Chngă1ăTNG QUAN 1
1.1TNG QUAN CHUNG 1
1.2MC TIÊU CAăĐ TÀI 5
1.3NHIM V Đ TÀI VÀ GII HNăĐ TÀI 5
1.4PHNGăPHÁPăNGHIểNăCU 5
Chng2ăBĨIăTOÁNăĐIU PHI CÔNG SUT ED 6
2.1GII THIU 6
2.2BÀIăTOÁNăĐIU PHI KINH T C ĐIN 6
2.2.1Hàm mc tiêu 7
2.2.2Ràng bucăđẳng thc 7
2.2.3Ràng buc bấtăđẳng thc 8
2.3BÀIăTOÁNăĐIU PHI KINH T VI HÀM CHI PHÍ NHIÊN LIU
KHỌNGăTRN 8
2.3.1.Đặcăđim caăbƠiătoánăđiu phi kinh t viăđim van công suất 9
2.3.2.Biu thcăđiu phi kinh t viăđim van công suất 9
Chngă3ăTHUT TOÁN DI TRUYN 10
3.1GII THIU CHUNG 10
viii

5.1.THUT TOÁN LAI GA-HS 31
5.1.1Gii thiu 31
5.1.2ăCácăbc caăphngăphápălaiă2ăthut toán GA ậ HS 32
5.2LUăĐ GII THUT 34
5.2.1Luăđ HS cho bài toán ED vi hiu ngăđim van 34
5.2.2Luăđ GA-HS cho bài toán ED vi hiu ngăđim van 36
5.3NG DNG THUT TOÁN LAI GA-HS GII BÀI TOÁN ED VI
HIU NGăĐIM VAN 39
5.3.1H thng 13 nút 39
5.3.2H thng 40 nút 42
Chngă6ăKT LUNăVĨăHNG NGHIÊN CU PHÁT TRIN 47
6.1KT LUN 47
6.2HNG NGHIÊN CU VÀ PHÁT TRIN 47
6.3LI KT 48
TÀI LIU THAM KHO 49
PH LC 52 x
DANH SÁCH CÁC CH VIT TT

DE Differential Evolution.
ED Economic Dispatch.
fw Fret Width.
GA Genetic algorithm.
HM Harmony Memory.
HMCR Harmony Memory Considering Rate.
HMS Harmony Memory Size.
HS Harmony Search.
IFEP Improved Fast Evolutionary Program.

Hình 5.1: Luăđ gii thut HS cho bài toán Valve point. 36
Hình 5.2: Luăđ gii thut GA - HS cho bài toán Valve point. 37
Hình 5.3: Đặc tính hi t ca mngăđin 13 máy phát. 41
Hình 5.4: Đặc tính hi t ca mngăđin 40 máy phát. 45 xii
DANH SÁCH CÁC BNG

BNG TRANG
Bng 5.1: Thông s ca h thng 13 nút vi hiu ngăđim van 39
Bng 5.2: Công suất phát ra ca h thng 13 máy phát 40
Bng 5.3: Kt qu so sánh ca h thng 13 máy phát có xét nhăhng caăđim
van công suất 41
Bng 5.4: Thông s ca h thng 40 nút vi hiu ngăđim van 42
Bng 5.5: Công suất phát ra ca h 40 máy phát 43
Bng 5.6: Kt qu so sánh ca h thng 40 máy phát có xét nhăhng caăđim
van công suất 45

1
Chngă1
TNG QUAN

1.1 TNG QUAN CHUNG
Trong nhng thp kỷ qua, nhu cầuănĕngălngăđin trên toàn th giiăđƣăđt
ngtătĕngătheoăđƠ tĕngătrng kinh t. Bên cnhăđóăcácăngunănĕngălng hóa thch
vn là nguyên liuăchínhăđ sn xuất dinăđangăđngătrênănguyăcăcn kit, ngun
cung không năđnh giá c binăđng…Vic s dng hiu qu và tiăuăcácăngun
cung cấp là mt vấnăđ mà các nhà nghiên cu rất quan tâm.Mcăđíchăca h thng
đin là chấtălngăđinănĕng,ănơngăcaoăhiu qu s dng,ăđ tin cy cấpăđinăđng

công suất sao cho h thng vn hành tiău:
Các bài báo nước ngoài:
BƠiăbáo:ăắLuận văn Thạc Sĩ, Ứng dụng thuật toán di truyền phân bố công suất
tối u trong Hệ Thống Điện, Phạm Việt Cờng, 7 /2003, 700998, Th viện Đại Học
Bách Khoa TPHCM. [2]
Lunăvĕnăđ cpăđn vic ng dng gii thut di truyn vào tính toán tiăuă
công suấtăphátăcácănhƠămáyăđin và phân b tiăuăcôngăsuấtătrongăliăđin vi hàm
mc tiêu là cực tiuăchiăphíăphátăđinăđng thi tha mãn các ràng buc v công suất
tác dng và phnăkháng,ăđin áp nút và ng dng vào mng IEEE 30 nút.
Bài báo: “Optimal Scheduling of Multiple Dam System Using Harmony
Search Algorithm”. Tác gi Zong Woo Geem. [3]
Lấy cm hng t hành vi ca nhcăsĩăsự thut toán tìm kim hòa hp (HS) lần
đầuătiênăđc áp dng cho vic lp k hoch hotăđng tiăuăca mt h thng
nhiuăđp. Mô hình HS gii quyt mt h thng chuẩn mực ph bin vi bnăđp.
Kt qu cho thấy mô hình HS tìm thấyănĕmăgii pháp tiăuătoƠnăcầu khác nhau vi
li ích tiăđaăging ht nhau t thyăđin và thy li,ătrongăkhiătĕngăcng mô hình
GA (mã hóa giá tr thực t, lựa chn, lai to, và binăđiăđt bin)ăđc tìm thấy ch
có các gii pháp gần tiăuătrongăcùngămt s đánhăgiáăchcănĕng.ăHnăna, mô
3
hìnhăHSăđn tiăuătoƠnăcầu mà không cần thực hin bất kỳ phơnătíchăđ nhy ca
thut toán các tham s trong khi các mô hình GA yêu cầu vic phơnătíchăđ nhy.
Bài báo: “A new meta-heuristic algorithm for continuous
engineeringoptimization: harmony search theory and practice”. Tác gi: Kang Seok
Lee, Zong Woo Geem. [4]
Bài vit này mô t mt tìm kim sự hòa hp miă(HS)ăphngăphápătip cn
thut toán dựa trên meta-heuristic cho vấnăđ tiăuăhóa kỹ thut vi các bin liên
tc. Thut toán HS s dng mt tìm kim ngu nhiên ngu nhiên thay vì tìm kim
gradientăđ thông tin phát sinh là không cần thit. Vấnăđ tiăuăhóaăkỹ thut khác
nhau, bao gm c chcănĕngătoánăhc gim thiu và các vấnăđ tiăuăhóaăkỹ thut
kt cấu,ăđcătrìnhăbƠyăđ chng minh hiu qu và vng mnh ca các thut toán

quyt các vấnă đ điuăđ kinh t (ED) vi chcănĕngăchiăphíă không li. Đ xuất
phngăphápătìmăkim hài hòa toàn cầu (NGHS). Vấnăđ ED thực t có chcănĕngă
chi phí không li vi hn ch bìnhăđẳng và bấtăbìnhăđẳng mà làm cho các vấnăđ
ca vic tìm kim tiăuătoƠnăcầu khó s dng hnăbất kỳ phngăphápătiăuăhóa
khác. Trong bài báo này, các NGHS là gii quyt vi sự bìnhăđẳng và bấtăbìnhăđẳng
khóăkhĕnătrongăbƠiătoánăđiuăđ kinh t.ăĐ xác nhn các kt qu thuăđc bằng
cáchăđ xuất, NGHS và phiên bn ci tin khác ca sự hòa hp tìm kimă(IHS)ăđc
áp dngăđ so sánh. Ngoài ra, các kt qu thuăđc t vicăNGHSăđc so sánh vi
cácăphngăphápătrcăđơyăđc báo cáo trong các tài liu. Kt qu cho thấyăcácăđ
xuất NGHS to ra gii pháp ttăhnăchoătất c các h thng nghiên cu.
Bài báo:“A Genetic Algorithm for Solving the Optimal Power Flow Problem”.
Tác gi:Tarek Bouktir, Linda Slimani, M. Belkacemi. [8].
Bài báo trình bày vic gii bài toán OPF trong mngăđin ln s dngăphngă
pháp gii thut gen. Hàm mcătiêuădùngăđ tính toán là cực tiu chi phí nhiên liu
máy phát vi các ràng buc công suấtămáyăphát,ăđin áp các nút, t bù,ăđầu phân áp
nằm trong gii hn cho phép. Thi gian tính toán có th gim xung bằng cách phân
chia các ràng buc tiăuăthƠnhărƠngăbuc tích cựcăđ thao tác trực tip bằng gii
thut GA, duy trì các ràng buc th đng trong gii hn mm s dng bài toán dòng
công suất truyn thng. Mng IEEE 30 nút đc ng dngăđ kim tra sự hiu qu
5
ca gii thut. Kt qu đc so sánh vi các cách gii khác ca gii thut GA và
phngăphápăEP.
BƠiăbáo:ăắImproved Genetic Algorithm for Power Economic Dispatch of Units
With Valve-Point Effects and Multiple Fuels”. Tác gi Chao-Lung Chiang. [9]
Bài vit này trình bày mt thut toán di truynăđc ci thin vi h s cp
nhtă(IGA_MU)ăđ gii quyt công bƠiătoánăđiuăđ kinh t (ED) vi các hiu ng
vanăđim và nhiu nhiên liu.ăĐ xuất IGA-MU tích hp các thut toán di truyn
đc ci thin (IGA) và các h s cp nht (MU). Các IGA trang b mt ci thin
tinăhóaăđiu hành ch đo và hotăđng chuynăđi có tìm kim hiu qu và ch
đng tìm hiu các giiăpháp,ăvƠăMUăđc s dngăđ x lý sự bìnhăđẳng và bất bình

tìmăđim hotă đng tiă uă đ phân phi công suất thực gia các nhà máy nhằm
gim thấp nhất chi phí sn xuất. Điu phi công suất phn khángădùngăđ cực tiu
tn thất h thng, nâng cao hiu suất và kh nĕngătn dng ngun.
BƠiătoánăđiu phi công suất làm ci thin vic hotăđng năđnh ca h thng
đin.ăThng làm gim mô hình h thngăđin,ălƠmăđnăgin các gii pháp chi phí
v chất lng. Vic s dngăđúngăđnăvƠăchínhăxácăhnăcácămôăhìnhăsnălng đin
làm cho li gii bài toán ttăhnănhngăvấnăđ khóăkhĕnăcũngătĕngălênăđángăk.
Mô hình ph bin ci tinăbƠiătoánăđiu phi kinh t bao gm: hàm chi phí có
xét nhăhng caăđim van công suất, vùng hotăđng không liên tc và sự chuyn
đi các loi nhiên liu; các loi ràng buc an ninh h thngăđinănhăgii hn dòng
công suất, dự tr công suất máy phát và cấuăhìnhăđin áp. Trong chngănƠy chúng
tôi trình bày h thng các biu thc caăbƠiătoánăđiu phi kinh t vi hàm chi phí
trnădng bc hai c đin và hàm chi phí có xét nhăhng caăđim van công suất.
2.2 BĨIăTOÁNăĐIU PHI KINH T C ĐIN
BƠiătoánăđiu phi kinh t c đin là bài toán tiăuănhằmăxácăđnh công suất
phát ra caăcácănhƠămáyăđ đtăđn kt qu là cực tiu chi phí vn hành. Hàm mc
tiêu caăbƠiătoánăđiu phi kinh t c đin là cực tiu tng chi phí h thng đin vi
hàm mc tiêu có dng tng ca hàm chi phí  mi nhà máy. Phân phi công suất
sao cho cân bằng gia công suất phát và ph ti viăđiu kin nằm trong vùng kh
nĕngăphátăca mi nhà máy.
7
2.2.1 Hàm mc tiêu
Hàm mc tiêu caăbƠiătoánăđiu phi kinh t c đin là cực tiu tng chi phí h
thngăđin (2.1) bằng cách hiu chnh công suất phát ca mi nhà máy kt ni vi
liăđin. Tngăchiăphíăđc biu din bằng hàm tng ca các chi phí  mi nhà máy.
1
min ( )
G
i
N

(2.2)
Trongăđóăa
i
, b
i
, c
i
là h s chi phí ca hàm chi phí nhà máy th i.
2.2.2 Ràng bucăđẳng thc
Ràng buc cân bằng công suất: Ràng buc cân bằng công suất là ràng buc
đẳng thcădùngăđ gim bt công suất h thng dựaătrênănguyênălỦăcăbn cân bằng
gia tng công suất nhà máy phát vi tng ti ca h thng. Cân bằng ch xy ra khi
8
tng công suất nhà máy phát
i
G
P

bằng vi tng ti trong h thng P
D
cng thêm
mtălng tn hao P
L
đc biu dinănhătrongă(2.3).
1
G
i
N
G D L
i

Gii hn công suất thực phát ra: Mi nhà máy có gii hn thấp nhất
min
i
G
P
và
gii hn cao nhất
max
i
G
P
phát công suất vì nó ph thuc vào cấu trúc ca máy phát.
Các gii hnătrênăđcăđnhănghĩaăbằng mt cặp ca ràng buc bấtăđẳng thc (2.5).
min max
i i i
G G G
P P P
, i = 1, , N
G
(2.5)
2.3 BĨIă TOÁNă ĐIU PHI KINH T VI HÀM CHI PHÍ NHIÊN
LIU KHÔNG TRN
CácănhƠă máyăphátăthngăđc mô hình hóa s sngăhƠmăchiăphíătrnănhă
trongăhìnhă2.1ăđ biu din mi quan h gia công suất phát ra và chi phí sn xuất.
Hàm chi phí loiănƠyăcóăuăđimălƠălƠmăđnăginăbƠiătoánăđiu phi kinh t và kh
nĕngăs dng nhiu kỹ thut áp dngăvƠoăđ gii bài toán này. Trong mt s trng
hp, biu dinădi dng bc hai không mô hình htăđcăđặcăđim ca nhà máy
đin, doăđó cầnămôăhìnhăchínhăxácăhnăđ cho kt qu ttăhnătrongăvic gii bài
toánăđiu phi kinh t. Mô hình chínhăxácăhnăthng có dng hàm phi tuynăhn,ă
khôngătrnăvƠănằm trong min lõm. Mt s ví d caăhƠmăchiăphíăkhôngătrnălƠ:ă

, c
i
, e
i
và f
i
là h s chi phí ca nhà máy th i.
Biu thcăcăbn ca bài toán này là các vấnăđ ràng buc cân bằng công suất
(2.3) và gii hn máy phát (2.5). Nhng ràng buc khác có th thêm vào tùy thuc
vào mô hình yêu cầu.
10
Chngă3
THUTăTOÁNăDIăTRUYN

3.1 GIIăTHIUăCHUNG
ĐcămtăsănhƠăsinhăvtăhcănêuăraătăthpăniênă50,ă60ăcaăthăkỷă20trongăđó
A.S.ăFraserălƠăngiăđầuătiênănêuălênăsựătngăđngăgiaăsựătinăhóaăcaăsinhăvtăvƠă
chngă trìnhă tính toán giă tngă vă thută toánă diă truyn.ă Tuyă nhiênă chínhă Johnă
Henry Holland, ĐiăhcăMichigan,ămiălƠăngiătrinăkhai phngăthcăgiiăquytă
vấnăđădựaătheoăsựătinăhóaăcaăsinhăvt.
ThutătoánădiătruynălƠăthutătoánătìmăkimădựaătrênăcăchăchnălcătựănhiên,
diătruynăvƠătinăhóa.ăCũngănhăcácăthutătoánătinăhóaănóiăchungăhìnhăthƠnhă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.ăQuáătrìnhătinăhóaăthăhinătínhătiăuăăchăthă
hăsauăbaoăgiăcũngă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.[2]
3.2 TNGăQUANăGIAăTHUTăTOÁNăGENăVĨăQUÁăTRỊNHăTINă
HịAăCAăSINHăVT
Trc tiên chúng ta tìm hiu v ngành di truyn hc (Genetics) là khoa hc
nhằm tìm hiu v huyt thng và sự di truyn ca các th h. Các nhà di truyn hc

Quần th
00110110
00110010
Đt bin
11001011
. . .
10111010
00110010
Li gii
Gii mã
Xácăđnh
đ phù hp
Đánhăgiá
Bánh xe
roulette
Chn lc cá th
Mã hóa
Li gii
11001010
10111011
00110110
11001100
Lai to
12
3.3.1. Cu trúc tng quát ca thut toán di truyn
Thut toán di truyn bao gmăcácăbc sau:
- Bc 1: Khi to quần th bao gm nhiu cá th.
- Bcă2:ăXácăđnhăđ phù hp ca các cá th.
- Bc 3: Chn lc các cá th tngăng viăđ phù hp ca chúng và to ra
các cá th mi bằng cách kt hp các cá th hin có, áp dng các toán t lai to và

và bài toán c th cần gii quyt. Kỹ thut mã hóa li gii có th rấtăkhácănhauăđi
vi tngăbƠiătoánăvƠăđi vi tng dng thut toán di truynăkhácănhau.ăHƠmăđánhăgiáă
xácăđnhăđ phù hp ca các cá th đi vi bài toán cần gii.ăHƠmăđánhăgiáătrongă
thut toán di truynăđóngăvaiătròănhămôiătrng trong chn lc tự nhiên.
3.3.2. Các thành phầnăcăbn ca thut toán di truyn
Thut toán di truyn bao gm các thành phầnăcăbnăsauăđơy:
- Phngăphápămã hóa (biu din) các li gii ca bài toán (các nhim sc th
hay cá th).
- Phngăphápăkhi to quần th banăđầu.
- Các toán t di truyn bao gm chn lc cá th, lai toăvƠăđt bin.
- HƠmăđánhăgiáăđóngăvaiătròăcaămôiătrng,ăđánhăgiáăcácăcáăth (li gii) theo
đ phù hp ca chúng.
- Giá tr ca các thông s (kíchăthc quần th, xác suất lai to, xác suấtăđt bin, ).
3.3.3. Cácăphngăphápămƣăhóa
Bcăđầu tiên trong thut toán di truyn là mã hóa li gii, ánh x các bin
điu khin ca bài toán tiăuăthƠnhăcác cá th (nhim sc th). Có nhiuăphngă
phápămƣăhóaăkhácănhau,ătrongăđóăphngăphápămƣăhóaănh phơnăvƠăphngăphápă
mã hóa thpăphơnălƠăhaiăphngăphápăđc s dng ph bin nhất.
14
Mtăđặcătrngăcăbn ca thut toán di truyn là thut toán luân phiên làm vic
gia không gian mã hóa (không gian kiu gen) và không gian li gii (không gian
kiuăhình)ănhăhìnhăv sau: Hình 3.3: Các không gian làm vic ca thut toán di truyn

Phân loại thuật toán di truyền theo phương pháp mã hóa:
- Theo kiu ký tự: mã hóa nh phân, thp phân, mã hóa theo s thực, s
nguyên, mã hóa bằng các ký tự ch cái, mã hóa theo cấu trúc d liu.
- Theo cấu trúc mã hóa: mã hóa mt chiu và mã hóa nhiu chiu.

 
 






max
maxmax
)(0
)(,
Cxg
CxgxgC
xf
(3.1)
Vi C
max
là h s đầu vào, chẳng hnănhăgiáătr g(x) ln nhất trong quần th
hin ti hoặc giá tr g(x) ln nhất sau k bc lặp.
Khi hàm mc tiêu nguyên thy là hàm li nhunăhayăđ v li u(x) cần cực
đi hóa, có th chuyn thành hàm phù hpăđnăginănhăsau:

 







'
(3.4)

tb
fCf .
'
max

(3.5)
16
Vi:
f
tb
,
'
tb
f
:ăđ phù hp trung bình ca quần th trcăvƠăsauăkhiăđiu chnh.

'
max
f
:ăđ phù hp ca cá th tt nhất trong quần th (đ phù hp ln nhất
trong quần th).

C: s phiên bn mong munăđi vi cá th tt nhất,ăđi vi quần th nh (n =
50 ậ 100 cá th)ăthng chn C = 1,2 ậ 2.
Điu kin (3.4) boăđm rằng mi cá th cóăđ phù hp trung bình có kh
nĕngăđóngăgópămt phiên bn trong th h k tip.ăĐiu kin (3.5)ăđiu chnh s
lng phiên bn ca cá th tt nhất trong quần th. Chú ý rằng ánh x tuyn tính có

iX
XN
f
1
1
)(
(3.7)
TrongăđóăX là nghim caăđaăthc:
(SP ậ 1).X
N-1
+ SP.X
N-2
+ . . .+ SP.X + SP = 0 (3.8)
Vi:
SP: áp suất chn lcăđc chn trong khongă[1,ă2]ăđi viăphngăphápătuyn
tính và trong khong [1, (chiu dài cá th ậ 2)]ăđi viăphngăphápăphiătuyn.
17
Pos: v trí ca cá th sau khi sp xp.
N: s cá th trong quần th.
3.3.6. Tiêu chuẩn ngng lp
Vì thut toán di truynălƠăphngăphápătìmăkim ngu nhiên nên rất khó xác
đnh tiêu chuẩn hi t c th.ăDoăđ phù hp ca quần th có th duy trì năđnh trong
mt s bc lặpătrcăkhiătìmăđc cá th ttăhnănênăvic áp dng các tiêu chuẩn hi
t truyn thng tr nên rấtăkhóăkhĕn.ăTrongăthực t ngiătaăthng cho phép thut
toán di truyn tìm kim li gii tiăuătrongămt s bc lặpăxácăđnhătrc.
Mt s tác gi đaăraătiêuăchuẩn ngng lặp dựa trên mcăđ ci thinăđ phù
hp: ngng lặp nu mcăđ ci thinăđ phù hp duy trì  mc thấp trong mt s
bc lặp,ănghĩaălƠăngng lặp nu f = f
i
ậ f




n
i
i
fF
1
, vi n lƠăkíchăthc ca
quần th (s cá th trong quần th).
- Tính xác suất chn p
i
cho mi cá th:
F
f
p
i
i

, i =1 n
- Tính xác suấtătíchălũyăq
i
ca mi cá th:



i
j
ji
pq

i

1
01110
8
0.16
0.16
2
11000
15
0.30
0.46
3
00100
2
0.04
0.50
4
10010
5
0.10
0.60
5
01100
12
0.24
0.84
6
00011
8


i
j
ji
fg
1
, i =1 n.
- Tìm tng giá tr đ phù hp ca quần th :



n
i
i
fF
1
.
- To mt s ngu nhiên r
1
trong khong [0,
k
F
].
- Tính k ậ 1 s còn li bit rằng chúng to thành mt cấp s cng ci công sai là
k
F

r
2
= r

j
 g
i
vi j = 1 k.
Gingănhăphngăphápăchn lc cá th bằng bánh xe roulette, xác suất mt
cá th đc chnătheoăphngăphápănƠyălƠ: