Ứng dụng thuật toán đàn kiến để giải bài toán tái cấu trúc lưới điện phân phối quận Liên Chiểu thành phố Đà Nẵng

1 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG TRẦN NGUYÊN DỖN ỨNG DỤNG THUẬT TỐN ĐÀN KIẾN ĐỂ GIẢI BÀI TỐN TÁI CẤU TRÚC LƯỚI ĐIỆN PHÂN PHỐI QUẬN LIÊN CHIỂU THÀNH PHỐ ĐÀ NẴNG Chuyên ngành: Mạng và Hệ thống điện Mã số: 60.52.50 TĨM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng – Năm 2011 2 Cơng trình được hồn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học: TS. TRẦN VINH TỊNH Phản biện 1: PGS.TS. Ngơ Văn Dưỡng. Phản biện 2: PGS.TS Nguyễn Hồng Anh. Luận văn sẽ được bảo vệ tại Hội đồng chấm Luận văn tốt nghiệp thạc sĩ kỹ t huậ t họp tại Đại học Đà Nẵng vào ngày 11 tháng 6 năm 2011 Cĩ thể tìm hiểu luận văn tại: - Trung tâm Thơng tin – Học liệu, Đại học Đà Nẵng - Trung tâm Học liệu, Đại học Đà Nẵng 3 MỞ ĐẦU 1. Lý do chọn đề tài Trong hệ thống điện, tổn thất trên lưới điện phân phối (LĐPP) chiếm một tỷ lệ đáng kể. Theo thống kê của Điện lực Việt Nam thì tổng tổn thất điện năng khoảng từ 10-15% sản lượng điện sản xuất, trong đĩ lưới điện phân phối chiếm 5-7% . Vì vậy giảm tổn thất điện năng ở lưới phân phối cĩ ý nghĩa quyết định trong việc giảm tỷ lệ tổn thất chung của tồn bộ hệ thống điện. Cĩ rất nhiều phương pháp để làm giảm tổn thất điện năng trên lưới điện phân phối như: nâng cao điện áp vận hành, cải tạo, thay dây dẫn, giảm truyền tải cơng suất phản kháng trên lưới điện bằng cách đặt tụ bù.....Các biện pháp này địi hỏi chi phí đầu tư khá lớn và phải cĩ thời gian để thực hiện. Trong luận văn này nghiên cứu giảm tổn thất trên lưới phân phối bằng thuật giải tái cấu trúc. Ta biết rằng khi thay đổi cấu trúc lưới điện bằng cách đĩng mở các cặp thiết bị đĩng cắt (khĩa điện) thì dẫn đến sự phân bố dịng, áp trên lưới cũng thay đổi, dẫn đến tổn thất trên lưới cũng thay đổi theo. Tái cấu trúc lưới điện phân phối gĩp phần đáng kể trong việc giảm tổn thất mà khơng yêu cầu nhiều chi phí đầu tư cải tạo lưới điện. Hơn nữa, việc tái cấu trúc lưới điện cịn cân bằng cơng suất giữa các tuyến đường dây, giảm sụt áp cuối đường dây, giảm bớt khả năng quá tải các thiết bị trên lưới, giảm thiểu số lượng hộ tiêu thụ bị mất điện khi sự cố. Hiện nay, cĩ nhiều thuật tốn giải bài tốn tái cấu trúc trên lưới điện phân phối để giảm ∆P. * Các thuật tốn dựa trên phương pháp Heuristic Phương pháp thay đổi nhánh đơn giản 4 Nội dung cơ bản của phương pháp thay đổi nhánh Heuristic là tính tốn thay đổi tổn thất cơng suất bởi việc đĩng cắt từng cặp một (đĩng một nhánh và mở một nhánh trong cùng một thời điểm). Mơ hình dịng tối ưu Nội dung cơ bản của mơ hình dịng cơng suất tối ưu là mở nhánh của cây mà cĩ giá trị dịng điện nhỏ nhất của mạch kín . * Thuật tốn của Merlin và Back – kỹ thuật vịng kín Nội dung: Đĩng tất cả các khố điện, tạo thành lưới điện kín. Sau đĩ tiến hành giải bài tốn phân bố cơng suất và mở lần lượt các khĩa điện cĩ dịng chạy qua bé nhất cho đến khi khơng cịn mạch vịng tạo thành lưới điện phân phối hình tia. * Các thuật tốn dựa trên trí tuệ nhân tạo Thuật tốn di truyền Thuật tốn di truyền là kỹ thuật tối ưu hĩa và tìm kiếm ngẫu nhiên cĩ định hướng, dựa vào những khái niệm từ thuyết tiến hĩa của tự nhiên. Thuật tốn này được hình thành trên quan điểm cho rằng quá trình tiến hĩa tự nhiên là quá trình 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, hồn thiện hơn thế hệ trước bởi quy luật đấu tranh sinh tồn. Thuật tốn đàn kiến (Ant colony algorithm – ACA) Trong vịng 10 năm gần đây, cĩ nhiều bài tốn tối ưu tổ hợp được giải quyết bằng các thuật tốn đàn kiến (Ant colony Algorithm). Thuật tốn kiến mơ phỏng hành vi của đàn kiến trong tự nhiên nhằm tìm kiếm đường đi ngắn nhất giữa tổ kiến và nguồn thức ăn dựa trên lượng dấu chân (Pheromone) mà các con kiến để lại trên đường đi. 5 Hiệu quả của thuật tốn kiến đã được thể hiện khi so sánh với các thuật tốn nổi tiếng khác như thuật tốn di truyền (GA), mơ phỏng luyện kim (Simulated Annealing). Hiện nay đã cĩ các nghiên cứu giải bài tốn tái cấu trúc bằng nhiều thuật tốn khác nhau như thuật tốn di truyền, kỹ thuật vịng kín … Để cĩ cái nhìn tổng quát và so sánh đối chiếu kết quả giữa các thuật tốn với nhau, làm tiền đề cho hướng nghiên cứu tiếp theo là lai ghép giữa các thuật tốn với nhau, để giảm thời gian tính tốn, nhanh đến kết quả tối ưu. Với các lý do nêu trên, đề tài luận văn sẽ chọn thuật tốn đàn kiến để áp dụng tính tốn cho bài tốn tái cấu trúc lưới điện phân phối nhằm giảm tổn thất cơng suất tác dụng. 2. Đố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 thuật tốn đàn kiến nhằm giải bài tốn tái cấu trúc lưới điện phân phối giảm tổn thất cơng suất tác dụng ∆P, áp dụng tính tốn cụ thể cho lưới điện phân phối quận Liên Chiểu - thành phố Đà Nẵng. Sử dụng phần mềm PSS/ADEPT để tính tốn kiểm tra. 3. Mục tiêu và nhiệm vụ nghiên cứu Cơ sở lý thuyết giải bài tốn tái cấu trúc LĐPP để giảm tổn thất. Nghiên cứu lý thuyết về thuật tốn đàn kiến. Nghiên cứu thành lập bài tốn tái cấu trúc LĐPP giảm tổn thất bằng thuật tốn đàn kiến. Lập chương trình tính tốn bằng ngơn ngữ Matlab. Ứng dụng tính tốn cụ thể cho lưới điện phân phối quận Liên Chiểu thành phố Đà Nẵng. Sử dụng phần mềm PSS/ ADEPT để tính tốn kiểm tra. 6 4. Bố cục luận văn Bố cục của luận văn ngồi phần mở đầu và kết luận chung, nội dung luận văn được biên chế thành 4 chương: Chương 1: Cơ sở lý thuyết giải bài tốn tái cấu trúc LĐPP. Chương 2: Thuật tốn đàn kiến. Chương 3: Xây dựng chương trình tính tốn tái cấu trúc LĐPP sử dụng thuật tốn đàn kiến. Chương 4: Tính tốn tái cấu trúc cho LĐPP quận Liên Chiểu thành phố Đà Nẵng. Chương 1 CƠ SỞ LÝ THUYẾT GIẢI BÀI TỐN TÁI CẤU TRÚC LĐPP 1.1. Đặc điểm của lưới điện phân phối Lưới điện phân phối dùng để chuyển tải trực tiếp điện năng từ lưới truyền tải đến hộ tiêu thụ. Lưới điện phân phối thường cĩ cấp điện áp từ 6÷35kV. Cấu trúc của lưới điện phân phối rất phức tạp bao gồm nhiều nhánh, nhiều nút và cĩ khối lượng rất lớn. Trên mỗi xuất tuyến của lưới điện phân phối ngồi các thiết bị đĩng cắt đầu xuất tuyến thì người ta cịn đặt nhiều thiết bị đĩng cắt để phân đoạn trên trục chính hoặc nhánh rẽ. Giữa các xuất tuyến với nhau trên mạch vịng người ta cũng đặt các thiết bị đĩng cắt vận hành ở vị trí thường mở, gọi là các thiết bị liên lạc. Trong thực tế người ta thường thiết kế và xây dựng lưới điện phân phối tạo thành các mạch vịng kín giữa các xuất tuyến với nhau nhưng vận hành hở. Việc vận hành lưới phân phối luơn phải thoả mãn các điều kiện: 7 Cấu trúc vận hành hình tia. Tất cả các phụ tải đều được cung cấp điện, tổn thất điện áp nằm trong trong phạm vi cho phép. Các hệ thống bảo vệ relay phải thay đổi phù hợp. Đường dây, máy biến áp và các thiết bị khác khơng bị quá tải. 1.2. Các lý do để vận hành hình tia trên lưới điện phân phối 1.3. Tái cấu trúc lưới điện phân phối 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 đã nêu. Đối với lưới phân phối, chi phí chủ yếu được tối thiểu hố là chi phí tổn thất điện năng. 1.4. Các bài tốn tái cấu trúc LĐPP ở gĩc độ vận hành Các bài tốn vận hành lưới điện phân phối mơ tả các hàm mục tiêu tái cấu trúc lưới điện như sau: - Bài tốn 1: Xác định cấu trúc lưới điện theo đồ thị phụ tải trong 1 khoảng thời gian để chi phí vận hành bé nhất. - Bài tốn 2: Xác định cấu trúc lưới điện theo đồ thị phụ tải trong 1 khoảng thời gian để tổn thất năng lượng bé nhất. - Bài tốn 3: Tái cấu trúc lưới điện cân bằng tải (giữa các đường dây, máy biến thế nguồn ở các trạm biến áp) để nâng cao khả năng tải của lưới điện. - Bài tốn 4: Khơi phục lưới điện sau sự cố hay cắt điện sửa chữa. - Bài tốn 5: Xác định cấu trúc lưới theo nhiều mục tiêu như: tổn thất cơng suất bé nhất, mức độ cân bằng tải cao nhất, số lần chuyển tải ít nhất, sụt áp cuối lưới bé nhất cùng đồng thời xảy ra. (Hàm đa mục tiêu). - Bài tốn 6: Xác định cấu trúc lưới điện tại 1 thời điểm để tổn thất cơng suất bé nhất. 8 Theo tác giả của [1], trong các bài tốn nêu trên, bài tốn 6: Xác định cấu trúc LĐPP để giảm tổn thất cơng suất tác dụng được xem là bài tốn quan trọng nhất, làm nền tảng cho hầu hết các bài tốn khác trong hệ thống các bài tốn tái cấu trúc LĐPP. 1.5. Các nghiên cứu khoa học về tái cấu trúc lưới điện phân phối 1.5.1. Mơ hình tốn học của lưới điện phân phối 1.5.2. Bài tốn 1: Tái cấu trúc lưới điện để cực tiểu chi phí vận hành 1.5.3. Bài tốn 2: Tái cấu trúc lưới điện để giảm tổn thất năng lượng 1.5.4. Bài tốn 3: Cân bằng cơng suất giữa các đường dây và trạm biến áp 1.5.5. Bài tốn 4: Tái cấu trúc để khơi phục lưới điện phân phối sau sự cố và cân bằng tải 1.5.6. Bài tốn 5: Tái cấu trúc lưới điện theo hàm đa mục tiêu 1.5.7. Bài tốn 6: Tái cấu trúc lưới điện để giảm tổn thất cơng suất tác dụng Cĩ rất nhiều phương pháp tái cấu trúc giảm ∆P nhưng theo [1], các phương pháp này cĩ thể được chia thành 3 loại chính là giải thuật kết hợp tối ưu hĩa và heuristic (kỹ thuật vịng kín), giải thuật thuần túy dựa vào heuristic (Kỹ thuật chuyển nhánh) và giải thuật dựa vào trí tuệ nhân tạo (thuật tốn di truyền). 1.5.7.1. Kỹ thuật vịng kín 1.5.7.2. Kỹ thuật đổi nhánh 1.5.7.3. Thuật tốn di truyền 1.6. Kết luận Phần lớn các bài tốn tái cấu trúc theo các mục tiêu khác nhau, nhưng đều cĩ thể chuyển về và sử dụng bài tốn xác định cấu trúc 9 LĐPP giảm tổn thất cơng suất tác dụng làm modun chính trong suốt quá trình lặp [1]. Vì vậy, đề tài chọn bài tốn này để thực hiện trong luận văn. Chương 2 THUẬT TỐN ĐÀN KIẾN 2.1. Sự ra đời của thuật tốn 2.2. Giới thiệu thuật tốn Ban đầu, số con kiến bắt đầu từ tổ kiến để đi tìm đường đến nơi cĩ thức ăn. Từ tổ kiến sẽ cĩ rất nhiều con đường khác nhau để đi đến nơi cĩ thức ăn, nên 1 con kiến sẽ chọn ngẫu nhiên một con đường đi đến nơi cĩ thức ăn. Quan sát lồi kiến, người ta nhận thấy chúng tìm kiếm nhau dựa vào dấu chân mà chúng để lại trên đường đi (hay cịn gọi là dấu chân kiến để lại). Sau 1 thời gian lượng dấu chân (pheromone) của mỗi chặng đường sẽ khác nhau. Do sự tích lũy dấu chân của mỗi chặng đường cũng khác nhau đồng thời với sự bay hơi của dấu chân ở đoạn đường kiến ít đi. Sự khác nhau này sẽ ảnh hưởng đến sự di chuyển của những con kiến sau đi trên mỗi đoạn đường. Nếu dấu chân để lại trên đường đi nhiều thì sẽ cĩ khả năng thu hút các con kiến khác di chuyển trên đường đi đĩ, những chặng đường cịn lại do khơng thu hút được lượng kiến di chuyển sẽ cĩ xu hướng bay hơi dấu chân sau 1 thời gian qui định. Điều đặc biệt trong cách hành xử lồi kiến là lượng dấu chân trên đường đi cĩ sự tích lũy càng lớn thì cũng đồng nghĩa với việc đoạn đường đĩ là ngắn nhất từ tổ kiến đến nơi cĩ thức ăn. Phương pháp này đưa ra để giải quyết các bài tốn cĩ khơng gian nghiệm lớn để tìm ra lời giải cĩ nghiệm là tối ưu nhất trong khơng gian nghiệm đĩ với thời gian cho phép hay khơng tìm ra cấu trúc tối ưu hơn thì dừng. 10 2.3. Các lý thuyết cải tiến của thuật tốn để tiếp cận bài tốn tái cấu trúc lưới điện phân phối 2.3.1. Giới thiệu bài tốn tối ưu tổ hợp và các định lý chứng minh độ hội tụ của thuật tốn Năm 2002 M.Dorigo và T.Stuzle đã chứng minh được tính hội tụ của hai biến thể quan trọng nhất của thuật tốn đĩ là Max – Min. Điều này đã khiến cho thuật tốn đàn kiến cĩ một cơ sở lý thuyết vững vàng và mở ra một loạt các nghiên cứu đầy hứa hẹn về các tham số điều khiển trong thuật tốn. Sau đây chúng ta sẽ xem xét phát biểu hình thức của bài tốn tổ hợp, giải thuật và tính hội tụ của giải thuật [5]. − Cho 1 bộ (S, f, Ω) trong đĩ − S: tập hợp các lời giải − f: Hàm đánh giá f: S->R − Ω: các điều kiện ràng buộc − Cần tìm lời giải tối ưu S* thoả f(S*) min Trong ACA bài tốn tối ưu tổ hợp (S, f, Ω) được giải quyết qua sơ đồ gồm các thành phần sau: Tập hữu hạn C = {C1, C2 ... CNc} các đỉnh cần duyệt trong quá trình tìm kiếm. Tập hữu hạn X các trạng thái kết quả cĩ thể tìm được của bài tốn trong quá trình tìm kiếm: x ∈X = . Tập S các lời giải - là bộ phận của X (S ⊆ X). Tập ~ X ⊆ X các trạng thái thoả mãn Ω. S* ≠ φ: tập các lời giải tối ưu. S* ⊆ ~ X và S* ⊆⊆ S Dựa vào các thành phần kể trên, các thành phần kiến sẽ xây dựng các lời giải bằng cách thực hiện các di chuyển qua các đỉnh của 11 đồ thị G = (C, L, T). Trong đĩ các đỉnh được gắn các giá trị thuộc C, L là cung nối các cặp đỉnh (khơng cĩ đỉnh cơ lập), T là tập các pheromone trên L. Các định lý hội tụ của thuật tốn: Định lý 1, Định lý 2, Định lý 3, Định lý 4, Định lý 5. 2.3.2. Nguyên lý chuyển trạng thái và nguyên lý cập nhật cục bộ, tồn cục Bằng sự hướng dẫn của cường độ dấu chân, những con kiến sẽ lựa chọn đường đi thích hợp. Cuối cùng, đường ưa thích nhất giàu pheromone trở thành hành trình tốt nhất, đĩ là lời giải cho vấn đề. Khái niệm này nĩi lên sự xuất hiện của phương pháp ACA: Đầu tiên, mỗi con kiến trong đàn kiến được đặt ở trạng thái xuất phát, mỗi thành viên sẽ xây dựng trọn vẹn một đường đi từ điểm bắt đầu cho đến điểm kết thúc thơng qua việc áp dụng lặp đi lặp lại nguyên lý chuyển trạng thái. Trong khi xây dựng hành trình, mỗi con kiến cũng làm thay đổi lượng pheromone trên đoạn đường nĩ đã đi qua bằng cách áp dụng nguyên lý cập nhật cục bộ. Khi tất cả những con kiến đã hồn thành hành trình của chúng, lượng pheromone trên đường đi sẽ được hiệu chỉnh trở lại theo nguyên lý cập nhật tồn cục. * Nguyên lý chuyển trạng thái: [ ] [ ] [ ] [ ] k k k m J (i) k (i, j) (i, j) , j J (i)(i,m) (i,m)p (i, j) 0 , j J (i) α β α β ∈  τ η ∈ τ η=  ∉ ∑ (2-1) Trong đĩ: • τ là lượng pheromone đọng lại trên đường đi từ điểm i đến điểm j; • η là nghịch đảo khoảng cách từ i đến j; 12 • Jk(i) là tập hợp các điểm cịn lại mà kiến thứ k từ điểm i cĩ thể đi đến; • α, β là các hệ số xác định tương quan giữa pheromone và khoảng cách. Biểu thức (2-1) nĩi lên rằng nguyên lý chuyển trạng thái thiên về sự di chuyển đến những điểm được kết nối bằng đường ngắn hơn và cĩ lượng pheromone lớn hơn. * Nguyên lý cập nhật cục bộ và tồn cục: Trong khi xây dựng hành trình, mỗi con kiến làm thay đổi pheromone trên những đoạn đường đi qua bằng các nguyên lý cập nhật cục bộ và tồn cục. Nguyên lý cập nhật cục bộ được biểu diễn bằng biểu thức gán như sau: (i, j) (1 ) (i, j)τ = −ρ τ (2-2) Trong đĩ: ρ là hệ số biểu diễn sự bay hơi của pheromone. Nguyên lý cập nhật tồn cục được biểu diễn bằng biểu thức gán như sau: s (k) k 1 (i, j) (i, j) (i, j) = τ =τ + ∆τ∑ (2-3) Trong đĩ: • ∆τ(i,j)(k) là lượng pheromone đọng lại của kiến thứ k khi đi qua đoạn đường i-j. • s là số lượng kiến trong đàn. 2.4. Mơ hình và cách giải bài tốn tái cấu trúc lưới điện phân phối áp dụng thuật tốn đàn kiến Khi giải bài tốn tái cấu trúc áp dụng thuật tốn đàn kiến, những phần tử kiến nhân tạo được đưa vào và thực hiện đầy đủ các bước tính 13 tốn mơ phỏng theo hoạt động của đàn kiến trong tự nhiên. Về cơ bản, những bước tính tốn này bắt đầu từ một lời giải chưa hồn chỉnh (phép thử), và từng bước thay đổi cấu trúc (mỗi cấu trúc tượng trưng cho đoạn đường đi hồn chỉnh của kiến) cho đến khi cuối cùng xây dựng được một cấu trúc tối ưu, đáp ứng được yêu cầu ở hàm mục tiêu. Thay đổi cấu trúc chính là thay đổi các trạng thái đĩng cắt của các thiết bị liên lạc, phân đoạn trên lưới điện. Mỗi một thiết bị liên lạc, phân đoạn (ký hiệu – S) được biểu thị bằng hai trạng thái đĩng hoặc mở (1,0). Ngay sau khi một phần tử kiến xây dựng một lời giải, nĩ để lại một lượng pheromone trên đoạn đường đi qua và hướng dẫn phần tử kiến tiếp theo để đi đến lời giải cuối cùng. Quá trình này được lặp lại cho đến khi thỏa mãn điều kiện dừng nào đĩ (chẳng hạn như số bước lặp tối đa cho phép). Cách giải quyết bài tốn này được quyết định bởi các thơng tin như sau: 1. Mật độ dấu chân kiến để lại (pheromone). 2. Thơng tin khám phá. 3. Hàm mục tiêu và các điều kiện ràng buộc. 4. Các nguyên lý cập nhật. * Mơ tả lời giải: 14 Ban đầu chúng ta phải tạo ra khơng gian tìm kiếm nghiệm bằng cách tạo ra một số cấu trúc của lưới điện, ứng với mỗi cấu trúc tượng trưng cho đoạn đường đi của kiến sẽ để lại một lượng pheromone trên đoạn đường đi qua. Trong quá trình khám phá của tổ chức đàn kiến, tiêu chí mà phần tử kiến lựa chọn một đường đi ở mỗi bước đĩ là nguyên lý chuyển trạng thái, bao gồm thơng tin về mức pheromone và thơng tin khám phá. Cụ thể là một phần tử kiến k khi đặt ở vị trí xij(k) ở nút ij (nút đĩng cắt) cĩ xác suất lựa chọn là pij được cho bởi biểu thức: [ ] [ ] [ ] [ ]∑ = = n k ikik ijijk ij t t tp 1 .)( .)()( βα βα ητ ητ (2-4) Trong đĩ: • τ là ma trận pheromone, được mơ tả rõ hơn ở phần dưới đây • ηj là thơng tin khám phá liên quan với nút j, • α, β là các hệ số tỉ lệ (0 ≤ α, β ≤ 1). * Ma trận pheromone (Ma trận dấu chân): Ma trận pheromone là một ma trận kích thước m x n, m hàng biểu diễn cho các vị trí đĩng cắt, n cột biểu diễn cho đoạn đường đi của phần tử kiến. Những phần tử của ma trận pheromone τi,j được gán một giá trị đĩ là mức pheromone mơ tả khả năng đĩng mở của các thiết bị đĩng cắt. * Quá trình cập nhật pheromone trong bài tốn tái cấu trúc: Sau khi tất cả những phần tử kiến hồn thành nhiệm vụ của mình để tạo ra các cấu trúc lưới điện, những vệt pheromone sẽ được cập nhật. Hai sự kiện quan trọng được đưa ra trong quá trình cập nhật: Sự bay hơi và đọng lại của pheromone. 15 Sự bay hơi làm giảm mức pheromone tại tất cả các phần tử của ma trận pheromone, được thể hiện qua biểu thức gán như sau: (i, j) (1 ) (i, j)τ = −ρ τ (2-5) Trong đĩ: • ρ là hệ số biểu diễn sự bay hơi của pheromone, giá trị nằm trong khoảng 0 ≤ ρ ≤ 1; • i = 1,....., m và j = 1,....., n; Sự bay hơi pheromone giúp hạn chế lượng pheromone gia tăng quá mức trên một đoạn đường nào đĩ. Vì vậy, nĩ cĩ tác dụng ngăn ngừa sự hội tụ đến một lời giải tối ưu cục bộ của bài tốn đặt ra bằng cách qui định một giải pháp nhằm quên đi những quyết định khơng tốt trong quá khứ. Sau khi bay hơi, tiếp tục xảy ra sự tích tụ pheromone, những phần tử kiến để lại pheromone trong ma trận τ thơng qua biểu thức gán: s (k ) k 1 (i, j) (i, j) (i, j) = τ = τ + ∆τ∑ (2-6) Trong đĩ: • i = 1,....., s và j = 1,....., m; • s là số lượng kiến trong đàn; • ∆τ(i,j)(k) là lượng pheromone đọng lại trên phần tử τ(i,j) của kiến thứ k, được cho bởi: (k) j(k)(k) t (k) j K , i x L(i, j) 0 , i x  =∆τ =   ≠ (2-7) • K là một hằng số. 16 • Lt(k) là giá trị tổng tổn thất cơng suất của mạng điện • xj (k) là vị trí thiết bị đĩng cắt, cho lời giải tìm được bởi phần tử kiến k. 2.5. Sơ đồ cấu trúc tổng quát của thuật tốn đàn kiến 2.6. Kết luận Thuật tốn đàn kiến tìm lời giải tối ưu được xây dựng dựa trên 3 nguyên lý cơ bản: nguyên lý chuyển trạng thái (nguyên lý xác suất), nguyên lý cập nhật cục bộ và nguyên lý cập nhật tồn cục với lời giải ban đầu là hồn tồn ngẫu nhiên và các hệ số tương quan do người dùng thiết lập tùy theo điều kiện bài tốn. Thơng qua việc tìm hiểu lý thuyết về thuật tốn và áp dụng để xây dựng mơ hình và giải bài tốn tái cấu trúc lưới điện phân phối đã mở ra một phương pháp mới để giải quyết các bài tốn tối ưu hĩa trong quá trình vận hành hệ thống điện. Chương 3 XÂY DỰNG CHƯƠNG TRÌNH TÍNH TỐN TÁI CẤU TRÚC LƯỚI ĐIỆN PHÂN PHỐI SỬ DỤNG THUẬT TỐN ĐÀN KIẾN 3.1. Giới thiệu Chương này trình bày việc áp dụng thuật tốn đàn kiến vào bài tốn tái cấu trúc LĐPP để giảm tổn thất cơng suất. Bài tốn tái cấu trúc được thực hiện bằng cách ban đầu tạo ra các cấu trúc mạng phân phối một cách ngẫu nhiên, mỗi cấu trúc ứng với một đường đi của kiến. Các kết quả đạt được sau khi tái cấu trúc sẽ được so sánh với kết quả trước khi tái cấu trúc để chứng minh tính khả năng giải quyết bài tốn của thuật tốn đàn kiến. Kết quả đạt được cũng so sánh với kết quả thực hiện bài tốn của phần mềm PSS/ADEPT-phần mềm tính tốn lưới phân phối hiện đang được áp dụng rộng rãi trong EVN. 17 Việc tính tốn tái cấu trúc LĐPP được xây dựng trên ngơn ngữ lập trình Matlab vì phần mềm này cĩ thư viện các hàm tốn học hết sức phong phú và hỗ trợ rất mạnh các phép tốn xử lý ma trận. 3.2. Thành lập bài tốn 3.2.1. Hàm mục tiêu và các ràng buộc Hàm mục tiêu cần tối thiểu là tổn thất cơng suất tác dụng. f = min (∆P) (3-1) ( )[ ]∑∑ == +=         + =∆ N ij jiij N ij ij ijij ij SSV QP RP 11 2 22 Re (3-2) Và các điều kiện ràng buộc: Điện áp tại các nút i(j) : Vi(j)min ≤ Vi(j) ≤ Vi(j)max Dịng điện trên các nhánh ij ∈ N: Iij ≤ Iijmax với: Rij: Điện trở các nhánh nối nút i và j. Vi, Vj: Điện áp tại nút i và j. Sij, Sji: Cơng suất truyền từ nút i đến j và ngược lại. Bài tốn tái cấu trúc LĐPP phải thỏa mãn các ràng buộc sau đây: *Ràng buộc về cấu trúc hình tia của LĐPP. * Ràng buộc về việc tất cả các phụ tải đều được cấp điện. * Ràng buộc về chất lượng điện. Thơng thường, hiện nay điện áp tại đầu nguồn thường được chỉnh bằng 1,05Uđm. Đối với điện áp cuối nguồn theo luật Điện lực, trong điều kiện bình thường, độ lệch khơng quá 5%. Như vậy, điều kiện ràng buộc về cường độ điện áp tại nút i nào đĩ là: dmidm U05,1VU95,0 ≤≤ (3-3) 18 * Ràng buộc về việc quá tải trên dây dẫn: Dịng điện (cơng suất) chạy trên các nhánh phải nhỏ hơn mức cho phép Ii j ≤ Icp (3-4) * Ràng buộc về quá tải của các trạm trung gian nguồn và máy phát. 3.2.2. Biểu diễn nghiệm của bài tốn (các cấu trúc lưới điện) Vì mỗi thiết bị liên lạc hay phân đoạn trong lưới điện chỉ cĩ hai trạng thái đĩng (gán tương ứng giá trị bít bằng ‘1’ và mở (gán giá trị bít bằng ‘0’) nên sử dụng phương pháp biểu diễn nhị phân để biểu biễn mỗi cấu trúc lưới điện (tương ứng với đoạn đường đi của phần tử kiến). Ví dụ: Hình 3-1: Biểu diễn cấu trúc lưới bằng mã nhị phân (thể hiện các trạng thái đĩng cắt của các thiết bị liên lạc hay phân đoạn) 3.2.3. Ma trận dấu chân (Ma trận pheromone ) Ma trận pheromone là một ma trận kích thước m x n, m hàng biểu diễn cho các vị trí đĩng cắt của các thiết bị liên lạc (Phân đoạn), n cột biểu diễn cho đoạn đường đi của phần tử kiến. Những phần tử của ma trận pheromone τi,j được gán một giá trị đĩ là mức pheromone mơ tả khả năng đĩng mở của các thiết bị đĩng cắt. 3.2.4. Tạo một số cấu trúc ban đầu cho cho mạng phân phối Bài tốn tái cấu trúc được thực hiện bằng cách, ban đầu tạo ra các cấu trúc mạng phân phối một cách ngẫu nhiên, mỗi cấu trúc ứng với một đường đi của kiến là một chuỗi nhị phân. Sau đĩ mỗi cấu trúc (là một phương án) sẽ được kiểm tra ràng buộc về điều kiện tất cả các phụ tải đều được cấp điện. Nếu thỏa mãn sẽ đưa vào cấu trúc ban đầu. Quá trình lặp lại cho đến khi đủ số cấu trúc đã cho trước. 0 1 0 1 0 0 0 19 3.3. Thành lập ma trận tổng dẫn nút của lưới điện (Ybus) 3.4. Giải tích mạng điện theo phương pháp NEWTON-RAPHSON 3.5. Kiểm tra các điều kiện ràng buộc 3.6. Sơ đồ thuật tốn bài tốn tái cấu trúc LĐPP để giảm ∆P Các bước để tạo ra thuật giải đàn kiến áp dụng cho bài tốn tái cấu trúc lưới điện phân phối: Bước 1: Ban đầu tạo ra một số cấu trúc của mạng phân phối (tạo ngẫu nhiên) thỏa mãn các điều kiện ràng buộc. Bước 2: Mỗi cấu trúc tượng trưng cho đoạn đường đi mà kiến đã đi này sẽ được tính tốn ở hàm mục tiêu (∆P). Bước 3: Mỗi cấu trúc này sẽ được cập nhật vào ma trận dấu chân theo cơng thức P kTkT xyij xy ij ∆ +=+ min 1)()1( (3-26) )(kT xyij : Dấu chân của kiến trên chặng đường xy của con kiến thứ i∈x và con kiến thứ j∈y, ở lần lập thứ i. Sau khi các cấu trúc ban đầu tạo ra đã cập nhật vào ma trận dấu chân, ta sẽ chọn ra được cấu trúc tốt nhất trong số các cấu trúc ban đầu, các cấu trúc cịn lại thì ta sẽ làm bay hơi dấu chân của các cấu trúc này bằng cơng thức: )0()(*)1( xyijxyijxyij TkTkT +=+ ρ (3-27) ρ: Xác suất bay hơi dấu chân của những con kiến đi qua để lại. )0(xyijT : Dấu chân ban đầu được tạo ra cho mỗi đoạn đường. Bước 4: Dựa vào ma trận dấu chân ta sẽ xây dựng được danh sách các cấu trúc được chọn theo các cơng thức ;, max xi T T xyijn i ∈=Φ (3-28) xy ijT : Cường độ dấu chân lớn nhất của hàng thứ thứ i∈x 20 Tmax: Cường độ dấu chân lớn nhất của ma trận dấu chân. :niΦ Khả năng đĩng mở các khĩa trong từng vịng, giá trị này ∈ [0,1] Bước 5: Nếu thời gian cho phép vẫn cịn và các cấu trúc chọn vẫn cịn thì ta quay lại bước 2. Bước 6: Nếu thời gian cho phép chấm dứt hay cấu trúc được chọn khơng cịn thì ta dừng chương trình và xuất ra kết quả. 3.7. Chương trình tái cấu trúc lưới điện phân phối bằng thuật tốn đàn kiến Nội dung chương trình (phụ lục). Các file chính của chương trình bao gồm: chươngtrinhchinh, cautruc_bandau, tinhtoan_hammuctieu, capnhat_bayhoi, ktra_colap, kiemtra_vong, kiemtra_quatai, kiemtra_ap. Ngoại trừ chương_trinh_chinh, các chương trình cịn lại được viết dưới dạng hàm và lưu thành m.file để thuận tiện khi sử dụng. 3.8. Kết luận Chương trình tính tốn đã xác định được cấu trúc tối ưu cĩ ∆P nhỏ nhất của lưới điện phân phối bằng thuật tốn đàn kiến. Lưới điện phân phối sau khi tái cấu trúc để giảm ∆P thỏa mãn các điều kiện ràng buộc đã đưa ra, điện áp nằm trong giới hạn cho phép. Chương 4 TÍNH TỐN TÁI CẤU TRÚC CHO LƯỚI ĐIỆN PHÂN PHỐI QUẬN LIÊN CHIỂU THÀNH PHỐ ĐÀ NẴNG 4.1. Giới thiệu sơ lược quận Liên chiểu - thành phố Đà Nẵng 4.2. Tổng quan về lưới điện phân phối quận Liên Chiểu TP Đà Nẵng 4.2.1. Nguồn điện 4.2.2. Lưới điện phân phối 21 4.2.3. Mơ tả sự liên lạc và phân đoạn giữa các các xuất tuyến Liên lạc giữa các xuất tuyến (các vị trí thường mở): - Xuất tuyến 472-ELC liên lạc với xuất tuyến 473-ELC tại vị trí C-01/5 (Vị trí này hiện đang mở lèo). - Xuất tuyến 473-ELC liên lạc với xuất tuyến 471-ELC tại vị trí C-13 (Vị trí này hiện đang mở lèo). - Xuất tuyến 471-ELC liên lạc với xuất tuyến 475-ELC tại vị trí dao cách ly DCL128. Liên lạc với xuất tuyến 472–E9 tại vị trí cột C27 (Vị trí này hiện đang mở lèo). Liên lạc với xuất tuyến 474-E9 tại vị trí dao cắt cĩ tải LBS 48.1. Liên lạc với xuất tuyến 473-E9 qua hai vị trí cột C-06 và C31.1 Phân đoạn giữa các xuất tuyến (các vị trí thường đĩng): - Phân đoạn xuất tuyến 471-ELC qua 03 vị trí: Phân đoạn bằng máy cắt Recloser tại vị trí cột C99, bằng dao cách ly DCL 30- 4ĐS3, bằng dao cách ly DCL 48.44. - Phân đoạn xuất tuyến 475-ELC bằng dao cách ly DCL128A. - Phân đoạn xuất tuyến 474-E9 qua 02 vị trí: Phân đoạn bằng máy cắt Recloser và dao cắt cĩ tải LBS 86A.4. - Phân đoạn xuất tuyến 473-E9 bằng dao cách ly DCL 14- 4ĐS3. Hiện nay lưới điện quận Liên chiểu cĩ 14 thiết bị liên lạc liên quan đến việc thay đổi phương thức vận hành, trong đĩ 7 thiết bị liên lạc thường mở, 7 thiết bị liên lạc TBLL thường đĩng. Vị trí các thiết bị liên lạc trên lưới như bảng số 4.1. Sơ đồ nguyên lý kết lưới lưới điện phân phối quận Liên Chiểu thành phố Đà Nẵng như phụ lục số 1. 22 4.3. Tính tốn phương thức vận hành hiện tại Sơ đồ thay thế tính tốn lưới điện phân phối quận Liên Chiểu như hình vẽ ở phụ lục số 3. Kết quả tính tốn cơng suất các xuất tuyến và tổn thất cơng suất phương án này như phụ lục số 2. Bảng 4.3: Cơng suất trên các xuất tuyến và tổn thất ở phương thức vận hành hiện tại lưới điện phân phối quận Liên chiểu Cơng suất Tổn thất Xuất tuyến P (MW) Q (MAr) ∆P (MW) ∆Q (MVAr) Tuyến 471-ELC 47,582 20,270 Tuyến 472ELC 11,500 4,899 Tuyến 473ELC 14,012 5,969 Tuyến 475ELC 12,415 5,289 Tuyến 472E9 32,338 13,776 Tuyến 473E9 43,286 18,440 Tuyến 474E9 41,290 17,589 0,57735 1,68765 4.4. Tái cấu trúc lưới điện quận Liên Chiểu bằng chương trình PSS/ADEPT 4.4.1. Giới thiệu chương trình PSS/ADEPT 4.4.2. Mơ phỏng LĐPP trên chương trình PSS/ADEPT 4.4.3. Xây dựng cơ sở dữ liệu thơng số cấu trúc LĐPP 4.4.4. Tính tốn tìm điểm mở tối ưu (TOPO) Phương thức vận hành lưới điện sau tái cấu trúc : Nội dung Cấu trúc ban đầu PSS/ADEPT Khĩa mở S1, S2, S6, S8, S9, S11, S14 S1, S2, S3, S5, S6, S11, S14 Khĩa đĩng S3, S4, S5, S7 S10, S12, S13 S4, S7, S8, S9 S10, S12, S13 ∆P (kW) 577,354 456,770 23 Bảng 4.5: Cơng suất trên các xuất tuyến và tổn thất sau khi tái cấu trúc lưới điện phân phối quận Liên chiểu bằng chương trình PSS/Adept Cơng suất Tổn thất Xuất tuyến P (MW) Q (MAr) ∆P (MW) ∆Q (MVAr) Tuyến471-ELC 47,582 20,270 Tuyến 472ELC 11,500 4,899 Tuyến 473ELC 14,012 5,969 Tuyến 475ELC 12,415 5,289 Tuyến 472E9 32,338 13,776 Tuyến 473E9 43,286 18,440 Tuyến 474E9 41,290 17,589 0,456770 1,453947 4.5. Tái cấu trúc lưới điện quận Liên Chiểu bằng thuật tốn đàn kiến Sơ đồ thay thế tính tốn lưới điện phân phối quận Liên Chiểu - thành phố Đà Nẵng như hình vẽ ở phụ lục số 5. Thơng số tính tốn trong file dữ liệu nút busdata và file dữ liệu nhánh linedata được lấy như thơng số trong chương trình PSS/Adept. Phương thức vận hành lưới điện sau tái cấu trúc : Nội dung Cấu trúc ban đầu Chương trình Khĩa mở S1, S2, S6, S8, S9, S11, S14 S1, S2, S3, S5, S6, S11, S14 Khĩa đĩng S3, S4, S5, S7 S10, S12, S13 S4, S7, S8, S9 S10, S12, S13 ∆P (kW) 577,354 462,7123 Bảng 4.6: Cơng suất trên các xuất tuyến và tổn thất sau khi tái cấu trúc lưới điện phân phối quận Liên chiểu 24 Cơng suất Tổn thất Xuất tuyến P (MW) Q (MAr) ∆P (MW) ∆Q (MVAr) Tuyến 471-ELC 47,582 20,270 Tuyến 472ELC 11,500 4,899 Tuyến 473ELC 14,012 5,969 Tuyến 475ELC 12,415 5,289 Tuyến 472E9 32,338 13,776 Tuyến 473E9 43,286 18,440 Tuyến 474E9 41,290 17,589 0,4627123 1,476023 Hình 4-2: Đặc tính hội tụ của bài tốn tái cấu trúc LĐPP quận Liên Chiểu TP Đà Nẵng 4.6. Nhận xét Cấu trúc của lưới điện sau khi thực hiện tái cấu trúc bằng chương trình PSS/Adept và thuật tốn đều cho kết quả giống nhau. 25 Theo kết quả tính tốn phương án cĩ tổn thất cơng suất tác dụng bé nhất, đáp ứng các điều kiện ràng buộc khi S3, S5 mở và S8, S9 đĩng. Tuy nhiên, hiện nay tại hai vị trí S8, S9 vẫn chưa cĩ thiết bị liên lạc (đây là 2 vị trí mở lèo). Để giảm cơng suất tác dụng LĐPP 22kV quận Liên Chiểu thành phố Đà Nẵng, cần thiết phải khảo sát lắp đặt bổ sung 2 thiết bị liên lạc tại hai vị trí này. KẾT LUẬN VÀ KIẾN NGHỊ 1. Kết luận Tái cấu trúc lưới điện là một bài tốn tối ưu hĩa phức tạp với hàm mục tiêu phi tuyến và phải thỏa mãn nhiều ràng buộc. Tái cấu trúc lưới điện phân phối giúp tìm ra phương án vận hành tối ưu lưới điện theo từng hàm mục tiêu cụ thể. Cĩ nhiều hàm mục tiêu trong bài tốn tái cấu trúc lưới điện phân phối nhưng bài tốn tái cấu trúc lưới điện phân phối giảm tổn thất cơng suất tác dụng là bài tốn quan trọng nhất, đây là một modul cho hầu hết các bài tốn tái cấu trúc khác. Thuật tốn đàn kiến trình bày trong luận văn là một phương pháp để giải quyết bài tốn tái cấu trúc lưới điện phân phối, giảm tổn thất cơng suất tác dụng và ban đầu thu được một số kết quả đáng khích lệ. Kết quả thực hiện phù hợp với kết quả thực hiện của các phương pháp đã được nghiên cứu áp dụng trước đây. Tổn thất cơng suất tác dụng sau khi tái cấu trúc đã giảm một lượng đáng kể. Áp dụng thuật tốn đàn kiến để tính tốn tái cấu trúc LĐPP quận Liên Chiểu thành phố Đà Nẵng đã tìm ra được phương án vận hành tối ưu hơn phương án hiện tại. Thuật tốn đàn kiến đơn giản, dễ dàng áp dụng vào nhiều bài tốn tái cấu trúc LĐPP với các hàm mục tiêu khác nhau. Mặc dù 26 khơng chứng minh được phương án tối ưu là tối ưu tồn cục, nhưng kết quả tính tốn của thuật giải là chấp nhận được, giảm được khả năng rơi vào cực trị cục bộ. Bên cạnh những ưu điểm, giải thuật cũng bộc lộ những nhược điểm như thời gian tính tốn và kết quả phụ thuộc nhiều vào các các cấu trúc ban đầu. Do vậy, cần phải thực hiện thử nghiệm chương trình nhiều lần đối với một lưới điện cụ thể để đúc kết kinh nghiệm lựa chọn các tham số nhằm nâng cao tốc độ hội tụ và chất lượng của giá trị hàm mục tiêu tìm được. 2. Kiến nghị Do khả năng và thời gian cĩ hạn, đề tài chưa khảo sát và phân loại được cơng suất của lưới điện ở các chế độ thấp điểm, bình thường trong ngày, cũng như các chế độ theo mùa nắng, mưa, chế độ sự cố, để tìm ra cấu trúc tối ưu linh hoạt cho mỗi chế độ. Hơn nữa, giải thuật kiến cĩ thời gian thực hiện rất lớn. Tuy nhiên, việc tìm hiểu được một giải thuật mới, xây dựng được một chương trình tính tốn sẽ là kết quả dùng để tham khảo và tạo điều kiện thuận lợi trong việc so sánh đối chiếu kết quả giữa các thuật tốn với nhau, làm tiền đề cho hướng nghiên cứu tiếp theo là lai ghép giữa các thuật tốn, để giảm thời gian tính tốn, nhanh đến kết quả tối ưu.