Lời cam đoan

Tôi xin cam đoan luận văn này là công trình nghiên cứu của riêng tôi
dưới sự hướng dẫn của TS Trần Thanh Sơn.
Tôi cũng xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn
này đã được cảm ơn và các thông tin trích dẫn trong luận văn này đã được chỉ
rõ nguồn gốc.

Tác giả

Bùi Viết Văn

1


Mục lục
Lời cam đoan ............................................................................................ 1
Danh mục các ký hiệu, các ký tự viết tắt ................................................ 4
Danh mục các bảng biểu .......................................................................... 5
Danh mục hình vẽ, đồ thị ......................................................................... 6
Phần mở đầu ............................................................................................. 7
Chương 1: Giới thiệu chung .................................................................. 10
1.1 Lưới điện phân phối........................................................................ 10
1.1.1 Đặc điểm của lưới điện phân phối ........................................... 10
1.1.2 Cấu trúc vận hành của lưới điện phân phối ............................. 11
1.2 Mô hình toán học ............................................................................ 12
1.2.1 Sử dụng biến dòng điện nhánh ................................................ 14
1.2.2 Sử dụng biến công suất ............................................................ 15
1.3 Các thuật toán được nghiên cứu để giải bài toán tối ưu hóa vận hành
cấu trúc lưới điện phân phối .......................................................................... 16
1.3.1 Tái cấu trúc lưới điện bằng lập trình tuyến tính [5] ................. 16

1.3.2 Tái cấu trúc lưới điện bằng thuật toán “heuristic” ................... 17
1.3.3 Tái cấu trúc lưới điện bằng thuật toán “heuristic” cải biên ..... 17
1.3.4 Tái cấu trúc lưới điện bằng thuật toán di truyền ...................... 17
Chương 2: Tái cấu trúc lưới điện bằng thuật toán di truyền............. 19
2.1 Thuật toán di truyền........................................................................ 19
2.1.1 Nguồn gốc xuất sứ ................................................................... 19
2.1.2 Cấu trúc của giải thuật di truyền .............................................. 20
2.1.3 Các thành phần cơ bản của thuật toán di truyền ...................... 22
2.2 Ứng dụng thuật toán di truyền để tối ưu hoá cấu trúc lưới điện phân
phối ................................................................................................................ 25
2.2.1 Lưu đồ giải thuật ...................................................................... 26
2


2.2.2 Thuật toán mã hóa.................................................................... 28
2.2.3 Quá trình tiến hóa .................................................................... 30
2.2.4 Tính phân bố công suất ............................................................ 37
Chương 3: Chương trình tối ưu hoá cấu trúc lưới điện phân phối
bằng thuật toán di truyền ............................................................................... 39
3.1 Giới thiệu về Matlab ....................................................................... 39
3.2 Cấu trúc chương trình ..................................................................... 40
3.2.1 Nhập dữ liệu ............................................................................. 40
3.2.2 Chương trình chính .................................................................. 43
3.2.3 Dữ liệu đầu ra........................................................................... 45
3.3 Áp dụng .......................................................................................... 45
3.3.1 Giới thiệu bài toán mẫu của IEEE ........................................... 45
3.3.2 Thực thi giải thuật .................................................................... 47
3.3.3 Nhận xét ................................................................................... 54
Kết luận chung ........................................................................................ 55
Hướng phát triển cho đề tài .................................................................. 58

Tài liệu tham khảo.................................................................................. 59
Phụ lục 2: Các chương trình trong Matlab được sử dụng trong luận
văn .................................................................................................................... 71

3


Danh mục các ký hiệu, các ký tự viết tắt
Kí hiệu

Nội dung

FCO

Cầu chì tự rơi

LBFCO

Cầu chì tự rơi kết hợp cắt có tải

GA

Giải thuật di truyền

KCL

Định luật Kirchhoff về dòng điện

KVL


Định luật Kirchhoff về điện áp

Pc

Xác suất lai tạo

Pm

Xác suất đột biến

4


Danh mục các bảng biểu

Bảng 2.1 Mô phỏng mã hóa cá thể ........................................................... 28
Bảng 2.2 Mô phỏng mã hóa cá thể cho sơ đồ .......................................... 29
Bảng 2.3 Tính độ thích nghi ..................................................................... 32
Bảng 2.4 Kết quả chọn lọc cá thể ............................................................. 32
Bảng 2.5 Mô phỏng phép đột biến ........................................................... 37
Bảng 3.1 Các nhánh mở của quần thể 1 ................................................... 47
Bảng 3.2 Các nhánh mở của quần thể 2 ................................................... 48
Bảng 3.3 Các nhánh mở của quần thể 3 ................................................... 49
Bảng 3.4 Các nhánh mở của quần thể 4 ................................................... 50
Bảng 3.5 Các nhánh mở của quần thể 5 ................................................... 51
Bảng 0.1 Dữ liệu nút của lưới điện .......................................................... 60
Bảng 0.2 Dữ liệu nhánh của lưới điện...................................................... 61
Bảng 0.3 Dữ liệu nút nhánh của lưới điện ban đầu .................................. 63
Bảng 0.4 Quần thể 1 ................................................................................. 65
Bảng 0.5 Quần thể 2 ................................................................................. 66

Bảng 0.6 Quần thể 3 ................................................................................. 67
Bảng 0.7 Quần thể 4 ................................................................................. 68
Bảng 0.8 Quần thể 5 ................................................................................. 69

5


Danh mục hình vẽ, đồ thị

Hình 2.1 Lưu đồ thuật toán của giải thuật di truyền ................................ 21
Hình 2.2 Bánh xe Roulette ....................................................................... 24
Hình 2.3 Lưu đồ thuật toán di truyền ...................................................... 27
Hình 2.4 Sơ đồ lưới điện 8 nút 10 nhánh ................................................ 29
Hình 2.5 Sơ đồ khối phép chọn lọc ......................................................... 31
Hình 2.6 Sơ đồ khối phép chéo hóa ........................................................ 34
Hình 2.7 Sơ đồ khối phép đột biến.......................................................... 36
Hình 3.1 Cấu trúc của chương trình ......................................................... 40
Hình 3.2 Sơ đồ khối chương trình chính .................................................. 43
Hình 3.2 Sơ đồ cấu trúc lưới điện ban dầu ............................................... 46
Hình 3.4 Sơ đồ cấu trúc lưới điện sau khi tái cấu trúc ............................. 53

6


Phần mở đầu

1. Lý do chọn đề tài
Lưới điện phân phối là khâu cuối cùng của hệ thống điện đưa điện năng trực
tiếp đến hộ tiêu dùng. Lưới điện phân phối bao gồm lưới điện trung áp và lưới
điện hạ áp, có cấu trúc phức tạp, bao gồm nhiều nút, nhiều nhánh và số lượng

đường dây lớn nhất trong hệ thống điện.
Tổn thất của lưới điện phân phối chiểm tỷ lệ rất cao: Theo báo cáo của Tập
đoàn Điện lực Việt Nam năm 2012 tổng tổn thất trên toàn bộ lưới điện 9,0%
trong đó tổn thất trên lưới truyền tải là 2,35%, lưới điện phân phối: 6,65% của
lượng điện sản xuất. Vì vậy việc chọn phương thức vận hành tối ưu ở lưới điện
phân phối có ý nghĩa rất quan trọng trong việc giảm tổn thất điện năng của toàn
bộ hệ thống điện.
Trong mạng lưới điện phân phối, với lượng phụ tải trên lưới ngày càng tăng
trong khi đó cấu trúc của của lưới điện lại không đổi. Từ đó sẽ làm cho tổn thất
của lưới điện phân phối ngày càng tăng lên. Muốn giảm tổn thất điện năng ta
phải áp dụng các phương thức như: thay thế các thiết bị cũ bằng các thiết bị
mới, nâng cao điện áp vận hành của lưới điện, tăng tiết diện dây dẫn, bù kinh tế
trên lưới điện, cải thiện cấu trúc lưới … Tuy nhiên các phương pháp này đều
đòi hỏi phi phí đầu tư và lắp đặt thiết bị rất lớn.
Một trong những phương pháp để giảm tổn thất điện năng trên lưới điện
phân phối là tìm cấu trúc vận hành tối ưu của lưới. Phương pháp tìm cấu trúc
vận hành tối ưu cho lưới điện phân phối là thay đổi dòng công suất trong các
nhánh bằng cách đóng/mở các cặp khóa điện để thay đổi cấu trúc lưới điện. Khi
đó lưới điện sẽ vận hành với chi phí thấp, trong khi vẫn thỏa mãn các yêu cầu
về chất lượng điện năng và độ tin cậy. Có nhiều phương pháp để tìm cấu trúc
vận hành tối ưu cho lưới điện phân phối như: phương pháp tìm cấu trúc tối ưu
dựa vào ứng dụng kĩ thuật đổi nhánh, kĩ thuật vòng kín, phương pháp lập trình
tuyến tính, thuật toán di truyền…

7


Luận văn này tập trung nghiên cứu ứng dụng của thuật toán di truyền để tìm
ra cấu trúc vận hành của lưới điện phân phối sao cho tổn thất công suất tác
dụng là nhỏ nhất.

Cấu trúc của luận văn gồm 3 chương:
Chương 1: Giới thiệu chung.
Chương này giới thiệu tổng quan về lưới điện phân phối và mô hình
toán học của bài toán tìm cấu trúc vận hành tối ưu của lưới điện để cực tiểu hoá
tổng tổn thất công suất tác dụng.
Chương 2: Tái cấu trúc lưới điện bằng thuật toán di truyền.
Chương này giới thiệu về thuật toán di truyền và cách áp dụng thuật
toán này để giải bài toán tìm cấu trúc vận hành tối ưu.
Chương 3: Chương trình tái cấu trúc lưới điện phân phối bằng
thuật toán di truyền.
Chương này giới thiệu chương trình tìm cấu trúc vận hành tối ưu viết
trong môi trường Matlab và ứng dụng của chương trình để tính toán cho một
lưới điện 33 nút.
2. Mục đích nghiên cứu
Luận văn này tập trung nghiên cứu cách giải bài toán tìm cấu trúc vận hành
tối ưu của lưới phân phối bằng thuật toán di truyền.
3. Nhiệm vụ nghiên cứu
Nghiên cứu tổng quan về lưới điện phân phối.
Nghiên cứu cơ sở lý thuyết bài toán tìm cấu trúc vận hành tối ưu của lưới
điện phân phối.
Nghiên cứu lý thuyết về thuật toán di truyền.
Nghiên cứu thành lập bài toán tối ưu hóa tái cấu trúc lưới điện phân phối
bằng thuật toán di truyền. Lập chương trình tính toán bằng phần mềm Matlab.
Ứng dụng tính toán cụ thể cho lưới điện cho trước.

8


4. Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu trọng tâm của đề tài là áp dụng thuật toán di truyền

nhằm giải bài toán tìm cấu trúc vận hành tối ưu cho lưới phân phối theo hàm
mục tiêu tổn thất công suất trên lưới phân phối là nhỏ nhất.
5. Phương pháp nghiên cứu
Phương pháp nghiên cứu của đề tài là nghiên cứu lý thuyết, xây dựng thuật
toán và chương trình để tính toán cho các lưới điện phân phối cụ thể.

9


Chương 1: Giới thiệu chung
1.1 Lưới điện phân phối
1.1.1 Đặc điểm của lưới điện phân phối
Lưới điện phân phối là khâu cuối cùng của hệ thống điện đưa điện năng
trực tiếp đến hộ tiêu dùng. Lưới điện phân phối bao gồm lưới điện trung áp và
lưới điện hạ áp. Lưới điện phân phối có cấu trúc phức tạp, bao gồm nhiều nút,
nhiều nhánh.
Lưới điện phân phối trung áp có cấp điện áp 6; 10; 15; 22; 35kV phân
phối điện năng cho các trạm phân phối trung áp và trạm phân phối phụ tải.
Lưới điện hạ áp 380/220 V cung cấp điện cho các phụ tải hạ áp.
Mạng lưới điện phân phối cung cấp trực tiếp điện năng đến các hộ tiêu
thụ điện, do đó so với mạng lưới điện truyền tải thì mạng lưới điện phân phối
được trải rộng trên toàn bộ phạm vi, số lượng các thiết bị, các đường đây dây
cũng nhiều nhất trong hệ thống điện.
Phương án vận hành của lưới điện phân phối thường được thay đổi
thường xuyên khi có yêu cầu để đảm bảo cho phụ tải luôn được cung cấp điện.
Do đó trên lưới điện phân phối thường có nhiều các thiết bị đóng cắt.
Một trong những đặc điểm quan trọng của lưới điện phân phối đó là có
cấu trúc mạch vòng kín nhưng thường vận hành hở.
Các yêu cầu đối với lưới điện phân phối:
 Lưới điện phân phối cung cấp điện năng trực tiếp tới khách hàng tiêu

thụ do đó chất lượng điện áp là yêu cầu quan trọng cần được đảm bảo.
Điện áp của lưới phân phối nằm trong giới hạn cho phép từ 5% đến
10% Uđm.
 Các thiết bị như máy biến áp, đường dây, cầu chì…phải được đảm bảo
không bị quá tải.

10


 Để đảm bảo việc cung cấp điện liên tục và ít gây mất điện nhất cho
khách hàng, lưới điện phân phối phải được cung cấp từ nhiều nguồn
điện khác nhau, có đường dây dự phòng, có nguồn thay thế…
 Việc sửa chữa bảo dưỡng cho lưới điện phân phối phải đảm bảo chi phí
nhỏ nhất.
Tổng quan lưới điện phân phối Việt Nam
Tất cả các công ty điện lực hiện nay điều hoạt động gần như theo hợp
đồng với khách hàng. Những hợp đồng này quy định về số lượng và chất lượng
điện năng được cung cấp. Chất lượng điện năng bao gồm các chất lượng về:
 Tần số ổn định.
 Điện áp giữ không đổi.
 Độ tin cậy cung cấp điện .
Cấp điện áp phân phối gồm các cấp điện áp sơ cấp hay điện áp phát tuyến
tương đối cao: 10kV, 15kV, 22kV, 35kV. Cấp điện áp thứ cấp hay điện áp tiêu
thụ là điện áp thấp: 220V, 380V.
Một đường dây phân phối luôn có nhiều loại phụ tải khác nhau: Chiếu
sáng, động cơ, thương mại dịch vụ, công nghiệp…Và các loại phụ tải này phân
bố không đồng đều giữa các đường dây. Mỗi loại tải lại có thời điểm đỉnh tải
khác nhau và luôn thay đổi trong ngày, trong tuần, trong từng mùa và trong
từng năm. Vì vậy, trên các đường dây đồ thị phụ tải không bằng phẳng và luôn
có sự chênh lệch công suất tiêu thụ. Điều này gây ra quá tải đường dây, mất đối

xứng giữa các pha và làm tăng tổn thất trên lưới điện phân phối dẫn đến thiệt
hại về kinh tế.
1.1.2 Cấu trúc vận hành của lưới điện phân phối
Việc lưới điện phân phối phải vận hành hở xuất phát từ các đặc trưng của
lưới điện phân phối:
 Số lượng phần tử như: Lộ ra, nhánh rẽ, thiết bị bù, phụ tải của lưới điện
phân phối nhiều hơn truyền tải từ 5 đến 7 lần nhưng mức đầu tư chỉ
hơn từ 2 đến 5 lần.
11


 Tổng trở của lưới điện phân phối vận hành hở lớn hơn nhiều so với vận
hành vòng kín nên dòng ngắn mạch bé khi có sự cố. Vì vậy chỉ cần
chọn các thiết bị đóng cắt có dòng ngắn mạch và dòng cắt ngắn mạch
nhỏ nên mức đầu tư giảm đáng kể.
 Trên lưới phân phối có rất nhiều khách hàng tiêu thụ điện năng với công
suất nhỏ và nằm trên diện rộng, nên khi có sự cố, mức độ thiệt hại do
gián đoạn cung cấp điện ở lưới điện phân phối gây ra cũng ít hơn so
với lưới truyền tải.
 Trong vận hành hở các rơle bảo vệ lộ ra chỉ cần sử dụng các loại rơle
đơn giản có chi phí thấp như rơle quá dòng, kém áp…mà không nhất
nhiết phải trang bị các rơle phức tạp chi phí cao như rơle định hướng,
khoảng cách, so lệch...nên việc phối hợp bảo vệ rơle cũng đơn giản
hơn rất nhiều.
 Chỉ cần dùng cầu chì tự rơi (FCO) hay cầu chì tự rơi kết hợp cắt có tải
(LBFCO) để bảo vệ các nhánh rẽ hình tia trên cùng một đoạn trục và
phối hợp với Recloser để tránh sự cố thoáng qua.
 Khi có sự cố, do vận hành hở nên sự cố chỉ gây mất điện ở nhánh đó,
việc điều khiển điện áp trên từng tuyến dây dễ dàng hơn và giảm được
phạm vi mất điện trong thời gian giải trừ sự cố.

1.2 Mô hình toán học
Trong mạng lưới điện phân phối, với lượng tải trên lưới ngày càng tăng
nhưng sự gia tăng tải phải nằm trong giới hạn cho phép, trong khi đó cấu trúc
của của lưới điện lại không đổi. Từ đó sẽ làm cho tổn thất của lưới điện phân
phối tăng lên. Muốn giảm tổn thất điện năng ta phải áp dụng các phương thức
như: thay thế các thiết bị cũ bằng các thiết bị mới, nâng cao điện áp vận hành
của lưới điện, tăng tiết diện dây dẫn, bù kinh tế trên lưới điện, cải thiện cấu trúc
lưới và vật liệu để sản xuất các thiết bị có tổn thất nhỏ…
Tuy nhiên, các phương pháp này cần vốn đầu tư rất nhiều mà hiệu quả
giảm tổn thất điện năng lại không đáng kể. Vì:
12


 Nếu ta tăng tiết diện của đường dây nó đòi hỏi tốn rất nhiều lượng kim
loại nhưng song theo đó ta phải gia cố thêm trụ đỡ mới có sức chống
chịu hợp lý.
 Nếu ta tiến hành tăng điện áp thì cũng chỉ đạt một giới hạn nhất định
nào đó, vì nếu tăng điện áp quá cao thì cách điện cho đường dây không
được đảm bảo.
 Nếu bù công suất kháng cho đường dây đòi hỏi mắc thêm các thiết bị bù
rất tốn kém.
Trong khi đó cũng có một phương pháp cũng nhằm giảm tổn thất điện
năng hay tổn thất công suất tác dụng với hiệu quả cao mà không cần tốn chi phí
đầu tư hay cải tạo đó chính là phương pháp tái cấu trúc vận hành lưới điện phân
phối. Phương pháp này nhằm mục đích là thay đổi cấu trúc hình học lưới phân
phối sao cho thích hợp nhất mà đồng thời cũng có tổn thất nhỏ nhất, phương
pháp này dựa trên các thiết bị sẵn có trên lưới phân phối. Phương pháp này
cũng nhằm mục đích làm giảm tổn thất công suất không cần đầu tư thêm về
kinh tế như các phương pháp khác. Vì vậy việc nghiên cứu cải tiến vấn đề tìm
điểm mở trên lưới điện phân phối trong điều kiện thực tế sẽ mang lại hiệu quả

về kinh tế và có ý nghĩa thực tiễn rất quan trọng.
Tái cấu trúc lưới điện là quá trình vận hành các khóa điện để thay đổi
phương thức nhằm giảm chi phí vận hành mà vẫn thoả mãn các ràng buộc. Đối
với lưới phân phối, chi phí chủ yếu được tối thiểu hoá là tổn thất công suất tác
dụng.
Có nhiều phương pháp để tối ưu hóa tái cấu trúc lưới điện phân phối như:
 Các thuật toán dựa trên phương pháp Heuristic.
 Kỹ thuật vòng kín.
 Thuật toán lập trình tuyến tính.
 Giải thuật Kiến (ACS).
 Giải thuật Di truyền (GA)…

13


Để giải quyết bài toán tái cấu trúc vận hành hệ thống lưới điện phân phối,
trước tiên phải xây dựng hàm mục tiêu cực tiểu hóa tổn thất công suất tác dụng
trên toàn bộ hệ thống.
Vấn đề tái cấu trúc hệ thống lưới điện phân phối cũng tương tự như việc
tính toán phân bố công suất tối ưu. Tuy nhiên, tái cấu trúc hệ thống lưới điện
phân phối yêu cầu một khối lượng tính toán lớn do có nhiều biến số tác động
đến các trạng thái khóa điện, và điều kiện vận hành như: Lưới điện phân phối
phải vận hành hở, không quá tải máy biến áp, đường dây, thiết bị đóng cắt ...và
sụt áp tại các nút phụ tải tiêu thụ trong phạm vi cho phép.
Về mặt toán học, tái cấu trúc hệ thống lưới điện phân phối có thể được
tính toán bằng hai phương pháp đó là: Sử dụng biến dòng điện nhánh, và
phương pháp sử dụng biến công suất.
1.2.1 Sử dụng biến dòng điện nhánh
Để tính tổn thất công suất tác dụng ta dựa vào dòng điện nhánh, ta có hàm
mục tiêu chính là hàm cực tiểu của tổn thất công suất tác dụng như sau:

(1.1)

NL

Min f =  k l R l Il2
l 1

Với các rằng buộc:

kl I l  I l max

(1.2)

Vimin ≤ Vi ≤ Vimax i N

(1.3)

gi(I,k)=0

(1.4)

gi(V,k)=0

(1.5)

 (k)=0

(1.6)

Trong đó:

 Ii: Dòng trên nhánh i
 Ri: Điện trở của nhánh i
 Vi : Điện áp nút i
14


 Ki: hệ số trạng thái của các khóa trên các nhánh (ki =1 nếu khóa đóng,
và ki =0 nếu nhánh i là mở)
 N: Số lượng nút
 NL: Số lượng nhánh
Trong mô hình trên, phương trình (1.2) là giới hạn của dòng điện nhánh.
Phương trình (1.3) là giới hạn cho phép của điện áp nút. Phương trình (1.4) là
phương trình Kirchhoff một (KCL), và phương trình (1.5) là phương trình
Kirchhoff hai (KVL). Phương trình (1.6) là điều kiện đảm bảo tính liên thông
của hệ thống. Nó bao gồm hai hạn chế cơ cấu:
 Tính khả thi: Không có nút nào bị cô lập.
 Số lượng nhánh trong mạng lưới phải nhỏ hơn số nút một đơn vị (NL =
N-1)
Do đó, cấu hình mạng lưới điện cuối cùng phải đảm bảo tính liên thông
và vận hành hở.
1.2.2 Sử dụng biến công suất
Ngoài phương pháp sử dụng biến dòng điện để tính tổn thất công suất tác
dụng ta còn có thể sử dụng biến công suất như sau:

 Pi2 +Qi2 
Min f=  k i R i 
 với i  NL
2
V
i=1



i
NL

(1.7)

Với các rằng buộc:

kl Pl  Pl max

(1.8)

kl Ql  Ql max

(1.9)

Vimin ≤ Vi ≤ Vimax i N

(1.10)

gi(P,k)=0

(1.11)

gi(Q,k)=0

(1.12)

gi(V,k)=0


(1.13)

 (k)=0

(1.14)
15


Trong đó:
 Pi: Công suất tác dụng trên nhánh i, công thức (1.8) là giới hạn cho phép
của công suất tác dụng trên nhánh i.
 Qi: Công suất phản kháng trên nhánh i, công thức (1.9) là giới hạn cho
phép của công suất phản kháng trên nhánh i.
 Vi : Điện áp tại nút i, công thức (1.10) giới hạn cho phép của điện áp tại
nút i.
Phương trình (1.14) là điều kiện đảm bảo tính liên thông của hệ thống.
Trong luận văn này tác giả chọn mô hình sử dụng biến dòng điện nhánh.
1.3 Các thuật toán được nghiên cứu để giải bài toán tối ưu hóa vận hành
cấu trúc lưới điện phân phối
Hiện nay có rất nhiều các phương pháp được sử dụng để giải bài toán tối
ưu hóa vận hành cấu trúc lưới điện phân phối, một số phương pháp phổ biến có
thể kể đến:
1.3.1 Tái cấu trúc lưới điện bằng lập trình tuyến tính [5]
Lập trình tuyến tính là lĩnh vực toán học nghiên cứu các bài toán tối ưu
mà hàm mục tiêu và các ràng buộc đều là hàm và các phương trình. Phương
pháp này sử dụng toán học để tuyến tính hóa hàm mục tiêu của lưới điện và tìm
giá trị tối ưu bằng toán học.
Liu và các cộng sự đã đề xuất hai giải thuật mà họ cho là có khả năng áp
dụng trên diện rộng. Các tác giả cho rằng các giải thuật này có tính khả thi

trong điều kiện vận hành cũng như trong công tác dự báo. Họ chứng minh rằng,
bằng cách xem các phụ tải có dòng điện tiêu thụ không phụ thuộc vào điện áp
thanh cái, khi dòng điện chạy qua một nhánh bất bất kể cấu trúc đều có thể thể
hiện bằng một dòng điện cơ bản yk và một hằng số ak. Nếu dòng điện nhánh
được xem xét theo cách này hàm biểu diễn dòng điện tại lộ ra và một hàm liên
tục giảm dần. Với cách sử dụng mô hình tải như trên, vấn đề tái cấu trúc được
chuyển thành xác định cực trị của hàm bậc hai và đảm bảm được cực trị toàn
16


cục. Vấn đề được giải quyết bằng cách tuyến tính hóa từng đoạn của hàm mục
tiêu. Tuy nhiên tính tối ưu hóa không được đảm bảo vì tính không liên tục của
của phụ tải trên đường dây.
1.3.2 Tái cấu trúc lưới điện bằng thuật toán “heuristic”
Bản chất phi tuyến rời rạc của bài toán tái cấu trúc lưới điện phân phối đã
tạo tiền đề cho nỗ lực nghiên cứu theo hướng sử dụng kỹ thuật chỉ thuần túy
dựa trên giải thuật heuristic. Các giải thuật này đề có chung đặc trưng là sử
dụng công thức thực nghiệm để đánh giá mức độ giảm tổn thất liên quan đến
các thao tác đóng cắt và giới thiệu một số quy luật nhằm giảm số lượng xem
xét các khóa điện. Các quy tắc heuristics dựa trên giả định rằng việc giảm tải
trên thiết bị và nguồn phát đồng nghĩa với giảm tổn thất.
1.3.3 Tái cấu trúc lưới điện bằng thuật toán “heuristic” cải biên
Có nhiều nghiên cứu đã và đang nỗ lực tìm cách vận dụng kĩ thuật kết
hợp giữa “heuristic” và tối ưu hóa.
Tái cấu trúc lưới điện bằng thuật toán “heuristic” cải biên có nhiều ưu
điểm hơn so với bài toán tái cấu trúc lưới điện bằng thuật toán “heuristic” thuần
túy. Đó là việc kết hợp giữa giải thuật “heuristic” và tối ưu hóa, lưới điện đạt
được cực tiểu toàn cục và không phụ thuộc vào cấu trúc lưới ban đầu.
Phương pháp đưa ra là loại bỏ những nhánh có tổn thất công suất lớn nhất
bài toán sẽ chấm dứt khi lưới điện được vận hành hở. Các giải thuật tìm kiếm

nhánh và biên ứng dụng luật “heuristic” này mất rất nhiều thời gian do khả
năng xảy ra đến 2n cấu trúc khi lưới điện có n đường dây được trang bị khóa
điện.
1.3.4 Tái cấu trúc lưới điện bằng thuật toán di truyền
Đây là thuật toán dựa trên sự tiến hóa tự nhiên, qua nhiều phép chọn lọc
ngẫu nhiên. Thuật toán di truyền không giống như phương pháp giải tích dựa
trên các công thức toán học hay phương pháp suy luận dựa trên kinh nghiệm
của các chuyên gia chỉ xét một số giới hạn các lời giải. Ngược lại, thuật toán di
17


truyền tìm kiếm trong toàn bộ không gian lời giải bằng cách xét trước hết một
số lời giải sau đó loại bỏ những thành phần không phù hợp và chọn những
thành phần thích nghi hơn để thực hiện các quá trình tiến hóa nhằm tạo ra nhiều
lời giải sau đó loại bỏ những thành phần không phù hợp và chọn các thành
phần thích nghi hơn để thực hiện quá trình tiến hóa nhằm tạo ra nhiều lời giải
mới có độ phù hợp ngày càng cao. Kết quả là bằng quá trình tiến hóa qua nhiều
thế hệ, thuật toán di truyền sẽ tìm được lời giải tối ưu cho bài toán.
Kết luận:
Chương này giới thiệu tổng quan về lưới điện phân phối và mô hình toán
học của bài toán tìm cấu trúc vận hành tối ưu của lưới điện để cực tiểu hoá tổng
tổn thất công suất tác dụng.
Để giải quyết bài toán cực tiểu hóa tổn thất công suất tác dụng trên thực tế
có nhiều phương pháp khác nhau. Trong bản luận văn này tác giả đã chọn sử
dụng giải thuật di truyền để thực hiện bài toán tìm cấu trúc vận hành tối ưu cho
lưới phân phối.

18



Chương 2: Tái cấu trúc lưới điện bằng thuật toán di truyền
2.1 Thuật toán di truyền
Trong thực tế ngày nay có nhiều bài toán tối ưu quan trọng đòi hỏi những
giải thuật có chất lượng cao. Những bài toán này có thể xem như bài toán tìm
kiếm giải pháp tốt nhất trong không gian vô cùng lớn, khi không gian tìm kiếm
lớn cần phải dùng đến kỹ thuật trí tuệ nhân tạo đặc biệt thuật toán di truyền
(GA) là giải thuật có thể giải quyết bài toán với không gian nghiệm lớn và thời
gian hội tụ nhanh.
2.1.1 Nguồn gốc xuất sứ
Khái niệm về “Thuật toán di truyền” (GENETIC ALGORITHM – GA)
được một số nhà sinh vật học nêu ra ở những năm 50 – 60 của thế kỷ trước.
Tuy nhiên John Henry Holland của trường Đại học Michigan, là người triển
khai ý tưởng và phương thức giải quyết vất đề dựa vào sự tiến hóa của con
người. Ông bắt đầu bằng những bài giảng và bài báo, sau đó đúc kết các ý
tưởng thành sách “Adaptation in Natural and Artificail Sytems” xuất bản năm
1975 J.H.Holland được xem là người khai sáng và phát minh ra thuật toán di
truyền.[1]
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. 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 hà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à 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.
Thuật toán di truyền sử dụng các thuật ngữ vay mượn của ngành di truyền
học. Khi tìm kiếm lời giải tối ưu, thuật toán di truyền cũng thực hiện các bước
tương tự như quá trình tiến hóa nói chung của sự vật. Đó là quá trình chọn lọc
tự nhiên những cá thể có độ phù hợp kém hay những cá thể xấu sẽ bị loại bỏ,
những cá thể có độ phù hợp cao hay cá thể tốt sẽ được giữ lại.
19



Hiện nay thuật toán di truyền được ứng dụng trong rất nhiều lĩnh vực
khác nhau, từ khoa học tự nhiên đến khoa học nhân văn, từ kỹ thuật đến thương
mại và kinh tế tài chính...
Thuật toán di truyền làm việc và xử lý song song một tập các lời giải
trong khi những phương pháp khác chỉ xử lý một điểm riêng lẻ trong không
gian tìm kiếm. Do vậy thuật toán di truyền có thể tìm ra được lời giải làm giảm
và thoát khỏi được cực trị địa phương, tiến đến lời giải toàn cục.
Thuật toán di truyền sử dụng các hàm mục tiêu và độ phù hợp thay vì
việc tính đạo hàm hay các thông tin hỗ trợ khác.
Thuật toán di truyền sử dụng những luật thay đổi ngẫu nhiên, xác suất
thay thế với những quy luật xác định.
Thuật toán di truyền làm việc với các thông số cần xác định dưới dạng mã
hóa chứ không phải là bản thân trực tiếp của thông số đó.
2.1.2 Cấu trúc của giải thuật di truyền
Để thuật toán di truyền làm việc tốt đòi hỏi phải có rất nhiều yếu tố, thành
phần, những thành phần và yếu tố chính trong cấu trúc của giải thuật di truyền
có thể kể đến:
 Kỹ thuật mã hóa (cấu trúc của nhiễm sắc thể)
 Hàm đánh giá, xác định độ phù hợp
 Quá trình sản sinh ban đầu
 Hoạt động của gen (lai tạo, đột biến…)
 Xác định thông số.
Sơ đồ khối của thuật toán di truyền như sau:

20


Hình 2.1 Lưu đồ thuật toán của giải thuật di truyền
Lưu đồ trên có thể mô tả vắn tắt như sau:

 Bước 1: Khởi tạo dân số ban đầu gồm nhiều nhiễm sắc thể
 Bước 2: Mã hóa các các thể trong quần thể
 Bước 3: Đánh giá độ thích nghi của các nhiễm sắc thể trong quần thể
 Bước 4: Khởi tạo nhiễm sắc thể mới bằng các lai tạo các nhiễm sắc thể
hiện tại
 Bước 5: Cho đột biến và tái tổ hợp những nhiễm sắc thể của các thể đời
trước đã lai tạo.
 Bước 6: Loại bỏ các thành phần của dân số nhường chỗ cho các nhiếm
sắc thể mới.
21


 Bước 7: Đánh giá các nhiễm sắc thể mới vừa đưa chung vào trong dân
số
 Bước 8: Khi gặp luật dừng thì đưa ra các nhiễm sắc thể tốt nhất; nếu
không quay lại Bước 3.
Như vậy thuật toán di truyền không giống như phương pháp giải tích dựa
trên các công thức toán học hay phương pháp suy luận dựa trên kinh nghiệm
của các chuyên gia chỉ xét một số giới hạn các lời giải. Ngược lại, thuật toán di
truyền tìm kiếm trong toàn bộ không gian lời giải bằng cách xét trước hết một
số lời giải sau đó loại bỏ những thành phần không phù hợp và chọn những
thành phần thích nghi hơn để thực hiện các quá trình tiến hóa nhằm tạo ra nhiều
lời giải sau đó loại bỏ những thành phần không phù hợp và chọn các thành
phần thích nghi hơn để thực hiện quá trình tiến hóa nhằm tạo ra nhiều lời giải
mới có độ phù hợp ngày càng cao. Kết quả là bằng quá trình tiến hóa qua nhiều
thế hệ, thuật toán di truyền sẽ tìm được lời giải tối ưu cho bài toán
2.1.3 Các thành phần cơ bản của thuật toán di truyền
a) Dân số ban đầu

Bất kỳ kỹ thuật tìm kiếm và tối ưu nào, dân số ban đầu cần phải có để

“bắt đầu không bị gián đoạn – start the ball rolling”. Dân số ban đầu thường
được tạo ra một cách ngẫu nhiên để ở đó có ít sự thay đổi các giá trị. Kích cỡ
ban dầu của quần thể càng lớn thì thuật toán di truyền sẽ càng thực hiện lâu.
Tuy nhiên, tập dân số ban đầu càng lớn thì số lần lặp sẽ ít hơn.
b) Mã hóa cá thể

Đây là bước đầu tiên trong thuật toán di truyền. Mã hóa liên quan đến
mẫu tượng trưng mỗi thành phần (Một tập các thông số tượng trưng của vấn đề
cần giải quyết thành một tập hợp nối kết với nhau) của dân số thành một chuỗi
các giá trị gọi là “nhiễm sắc thể” hay “cá thể”. Có nhiều phương pháp để mã
hóa thành tập các dân số, một vài phương pháp có thể kể đến như sau:
 Mã hóa nhị phân (chuỗi bao gồm các giá trị 0 và 1)
 Mã hóa thập phân (chuỗi bao gồm các giá trị từ 0 đến 9)
22


 Mã hóa theo số thực, số nguyên,
 Mã hóa bằng ký tự chữ cái,
 Mã hóa theo cấu trúc dữ liệu..
Mã hóa nhị phân thường được sử dụng nhiều nhất bởi vì nó thích hợp để
mã hóa bất kỳ các mẫu thành bit nhị phân. Hơn hết, cơ chế vận hành để lại tạo
và đột biến rất dễ thực hiện hơn. Đối với mẫu nhị phân, chiều dài của chuỗi
chính là số phần tử đưa vào mã hóa.
c) Xác định độ phù hợp

Độ phù hợp là một trong những đặc trưng chính của giải thuật di truyền,
nó tùy thuộc vào hàm mục tiêu của bài toán.
Thông thường, hàm xác định độ phù hợp được lấy từ hàm mục tiêu và sử
dụng liên tục vào trong cơ chế hoạt động của thuật toán. Một các thể hoạt động
ổn định đòi hỏi phải có hàm xác định phù trợ là hàm không âm.

d) Chọn lọc cá thể

Trong bước đầu tiên, quá trình chọn lọc được thực hiện nhiều lần đối với
các cá thể trong quần thể. Trong bước này mỗi cá thể được tái tạo với xác suất
tương ứng về cỡ với nó liên quan đến độ phù hợp trong quần thể. Quần thể thứ
N là một bản sao của các thể thay thế quần thể ban đầu.
e) Lai tạo

Trong bước kế tiếp này, quá trình lai tạo được thực hiện với xác suất Pc,
độc lập với cá thể được sử dụng. Hai cá thể ban đầu (cá thể cha mẹ) được lựa
chọn kết hợp lại để sản sinh ra hai cá thể mới (cá thể con). Sự kết hợp này thực
hiện bằng cách lựa chọn ngẫu nhiên một điểm ngắt mà ở đó mỗi cá thể cha
được chia làm 2 phần; sự trao đổi hình thành 2 các thể con được thay thế từ
hai cá thể cha của chúng trong quần thể.
f) Đột biến

Trong bước cuối cùng, quá trình đột biến thay đổi giá trị trong việc lựa
chọn ngẫu nhiên vị trí trong dân số với xác suất pm.
23


Một thuật toán di truyền đơn giản trình bày như sau:
 Đầu vào: Chiều dài chuỗi nhiễm sắc thể, kích cỡ quần thể, số lượng các
cá thể trong quần thể, xác suất đột biến Pm, xác suất lai tạo Pc, số thế
hệ tối đa.
 Đầu ra: Chuỗi tốt nhất từ dân số hiện tại.
Trong quá trình chọn lọc cá thể được thực hiện qua việc quay bánh xe
Roulette. Mỗi lần quay bánh xe Roulette thì sẽ chọn được một nhiễm sắc thể từ
quần thể hiện hành. Quá trình này được thực hiện như sau:
Tạo ngẫu nhiên một số thực r trong khoảng [0,1].


Hình 2.2 Bánh xe Roulette
Nếu r ≤ q1 thì chọn cá thể đầu tiên
Ngược lại chọn cá thể thứ i nếu qi-1 ≤ r ≤ qi
Trong đó:
P là xác suất chọn lọc:

24


pi 

fi
n

f
i 1

(2.1)
i

fi : là độ phù hợp của mỗi cá thể trong quẩn thể hiện hành (i=1…n)
Q là xác suất tích lũy:
q1 = p 1
Từ phần tử thứ 2 xác suất tích lũy được xác định từ công thức:

qi = pi + qi-1

(2.2)


Giải thích cơ chế hoạt động của thuật toán di truyền:
 Tạo chuỗi thứ N có chiều dài l một cách ngẫu nhiên từ quần thể ban đầu.
 Đánh giá chuỗi trong dân số hiện tại bằng cách xác định giá trị phù hợp
cho mỗi cá thể.
 Chọn lựa chuỗi có độ phù hợp cao, thực hiện chọn lọc cá thể và lặp lại
quá trình này N lần để tạo ra quần thể mới cho thế hệ tiếp theo.
 Ngẫu nhiên chọn một cặp của chuỗi và thực hiện lai tạo với xác suất pc
để sản sinh ra chuỗi con. Quá trình trao đổi bit thực hiện giữa hai
chuỗi ở một hoặt nhiều vị trí.
 Xác định bit đột biến với xác suất pm và đột biến giá trị của bit đó (Nếu
bit đột biến là 0 thì đột biến thành 1 và ngược lại)
 Bước 2 đến bước 5 tạo thành một thế hệ. Lặp lại bước 2 đến bước 5 cho
đến khi đạt đến thế hệ cần thiết và dừng lại. Ngõ ra là chuỗi tốt nhất từ
dân số hiện tại.
2.2 Ứng dụng thuật toán di truyền để tối ưu hoá cấu trúc lưới điện phân
phối
Bài toán tìm cấu trúc lưới điện vận hành tối ưu là bài toán xác định cấu
trúc lưới điện để có tổn thất công suất nhỏ nhất trong thời gian khảo sát khi biết
công suất phụ tải là công suất trung bình trong thời gian khảo sát.
Dạng tổng quát của bài toán là: P = f(x)  Min
25