GIỚI THIỆU CHUNG
ĐẶT VẤN ĐỀ
Vận hành hệ thống điện hiệu quả với chi phí thấp nhất, đồng thời đảm bảo các ràng buộc kỹ thuật, là mục tiêu hàng đầu trong ngành điện lực Chi phí phát điện từ các nhà máy sử dụng nhiên liệu hóa thạch thường rất cao, do đó việc tiết kiệm chi phí nhiên liệu là vô cùng quan trọng để tối ưu hóa hoạt động của hệ thống điện.
Bài toán điều độ kinh tế cho các nhà máy nhiệt điện liên quan đến việc phân bổ công suất phát cho từng tổ máy nhằm đáp ứng tải một cách kinh tế mà không vi phạm các ràng buộc của hệ thống Thông thường, giả định rằng tất cả các máy phát ra công suất lớn hơn P min và nhỏ hơn P max, với hàm chi phí nhiên liệu là hàm bậc 2 liên tục trong khoảng này Tuy nhiên, việc bỏ qua các ràng buộc như vùng cấm vận hành, giới hạn ramprate và ảnh hưởng của điểm van công suất đến hàm chi phí phát điện khiến cho bài toán trở nên thiếu thực tế Do đó, bài toán điều độ kinh tế thực tế là một bài toán tối ưu phi tuyến phức tạp, có nhiều ràng buộc, thường không thể giải quyết bằng phương pháp tối ưu truyền thống mà cần sử dụng các thuật toán tối ưu tìm kiếm ngẫu nhiên.
Giải thuật GSA, được E Rashedi công bố lần đầu vào năm 2009, là một trong những giải thuật tối ưu tìm kiếm ngẫu nhiên dựa vào tập hợp, lấy cảm hứng từ lực trọng trường và tương tác giữa các vật thể có khối lượng Từ khi ra mắt, GSA đã trải qua nhiều cải tiến và được ứng dụng rộng rãi trong các lĩnh vực như điện, cơ khí và viễn thông.
Luận văn này khảo sát việc áp dụng GSA cổ điển và GSA cải tiến trong việc giải quyết bài toán vận hành kinh tế cho các nhà máy nhiệt điện, đặc biệt khi hàm chi phí nhiên liệu không có tính chất lồi và không liên tục.
PHẠM VI NGHIÊN CỨU
Bài toán điều độ kinh tế không lồi đƣợc xem xét trong luận văn bao gồm:
+ Hệ thống có 13, 40 máy phát nhiệt điện với hàm chi phí nhiên liệu có xét đến điểm van công suất
+ Hệ thống 15 máy phát với vùng cấm vận hành và giới hạn thay đổi công suất và tổn thất công suất trên lưới
+ Hệ thống có 10 máy phát với đặc tính đa nhiên liệu và điểm van công suất
+ Hệ thống lớn gồm 20, 40, 80, 160 máy phát được xây dựng trên trường hợp cơ bản 10 máy phát với đặc tính đa nhiên liệu và điểm van công suất.
MỤC TIÊU CẦN ĐẠT ĐƢỢC
Áp dụng thuật toán GSA và GSA cải tiến để giải bài toán điều độ kinh tế với hàm chi phí nhiên liệu không liên tục, không lồi.
ĐIỂM MỚI CỦA LUẬN VĂN
Hiện chưa có luận văn, nghiên cứu nào trong nước về thuật toán GSA và GSA cải tiến để giải bài toán điều độ kinh tế.
KẾT CẤU LUẬN VĂN
Chương 2 Bài toán điều độ kinh tế
Chương 3 Giới thiệu về giải thuật GSA và GSA cải tiến
Chương 4 Áp dụng giải thuật GSA và GSA cải tiến để giải bài toán điều độ kinh tế Chương 5 Kết quả
BÀI TOÁN ĐIỀU ĐỘ KINH TẾ
GIỚI THIỆU
Phân bổ tối ưu mức công suất phát cho các tổ máy đang hoạt động là một trong những yếu tố quan trọng nhất trong việc vận hành hệ thống điện hiệu quả.
Bài toán điều độ kinh tế (ED) là quá trình xác định công suất phát điện của các tổ máy nhằm tối ưu hóa chi phí phát điện, đồng thời đảm bảo tuân thủ các ràng buộc kỹ thuật của toàn hệ thống.
Trong các phương pháp truyền thống, hàm mục tiêu của bài toán thường được xấp xỉ bằng hàm bậc 2 đơn giản Các phương pháp giải quyết bao gồm quy hoạch toán học, như phương pháp lặp lambda, quy hoạch động, quy hoạch tuyến tính, quy hoạch phi tuyến, kỹ thuật gradient và phương pháp Lagrange Khi xem xét các đặc tính thực tế của tổ máy, bài toán trở nên phức tạp hơn.
ED là một bài toán tối ưu phức tạp với nhiều cực trị địa phương và ràng buộc, điều này khiến các phương pháp thông thường không thể giải quyết hiệu quả.
Trong những năm gần đây, có nhiều cách tiếp cận để giải bài toán ED bằng phương pháp heuristic.
THÀNH LẬP BÀI TOÁN
Bài toán điều độ kinh tế nói chung về bản chất là một bài toán tối ƣu có ràng buộc với hàm mục tiêu và các ràng buộc
Mục tiêu của việc điều độ kinh tế trong các bài toán là tối thiểu hóa chi phí nhiên liệu phát điện hoặc chi phí vận hành của tất cả các tổ máy, đồng thời đảm bảo các ràng buộc của hệ thống Giả sử có N tổ máy cần phân bổ công suất, tổng chi phí nhiên liệu F T được sử dụng để phát điện sẽ được tính toán dựa trên các yếu tố này.
(2.1) a Hàm chi phí thông thường
Chi phí phát điện là thành phần quan trọng nhất trong tổng chi phí vận hành của các nhà máy nhiệt điện, chiếm tỷ lệ lớn so với các chi phí khác như bảo trì và nhân công Cụ thể, chi phí nhiên liệu cho công suất phát điện của tổ máy i, ký hiệu là F i, thường được biểu diễn bằng một hàm bậc.
Trong đó: a i , b i , c i là những hệ số chi phí nhiên liệu của tổ máy thứ i b Hàm chi phí khi xét đến ảnh hưởng của điểm van công suất
Trong nhà máy nhiệt điện, việc sử dụng các van đóng mở để điều chỉnh công suất phát là rất quan trọng, vì nó giúp duy trì sự cân bằng công suất tác dụng Tuy nhiên, việc này cũng tạo ra sự dao động trong hàm chi phí, dẫn đến một hàm mục tiêu phi tuyến cao Để mô hình hóa chính xác tác động của việc mở van đối với chi phí nhiên liệu, hàm mục tiêu cần được bổ sung thêm thành phần sin Hàm chi phí nhiên liệu của máy phát thứ i được biểu diễn qua công thức cụ thể.
Trong đó: e i , f i là những hệ số chi phí nhiên liệu của tổ máy i có xét đến hiệu ứng của các điểm van
Hình 2.1 Hàm chi phí nhiên liệu của tổ máy có 5 điểm van công suất c Hàm chi phí xét đến ảnh hưởng của nhiều loại nhiên liệu
Hàm chi phí tổ máy i gồm k đoạn bậc 2 thể hiện k loại nhiên liệu
2 min max ik i ik i ik ik 1 i i a P b P c ,fuel1, P P P a P b P c ,fuel2, P P P
Hệ số chi phí của nhà máy i khi sử dụng nhiên liệu k được biểu thị bằng aik, b ik và c ik Hàm chi phí này xem xét tác động của nhiều loại nhiên liệu cũng như điểm van công suất.
2 min min max ik i ik i ik ik ik ik ik ik 1 i i a P b P c e sin(f (P P )) ,fuel1, P P P a P b P c e sin(f (P P )) ,fuel2, P P P
Hình 2.2 Hàm chi phí nhiên liệu của tổ máy sử dụng 3 loại nhiên liệu
2.2.2 Các ràng buộc a Cân bằng công suất tác dụng
Tổng công suất tác dụng phát ra của các tổ máy P i phải bằng tổng công suất tiêu thụ của tải trong hệ thống P D cộng với lƣợng tổn thất P L
Tổn thất trên hệ thống có thể tính đƣợc nhờ sử dụng công thức tổn thất của Kron:
Trong đó: B ij , B i0 , B 00 gọi là các hệ số tổn thất b Giới hạn công suất thực phát ra
Mỗi tổ máy phát điện đều có giới hạn công suất tác dụng tối thiểu và tối đa, điều này phụ thuộc vào cấu trúc của máy phát.
P P P , i 1, , N (2.8) c Vùng cấm vận hành của tổ máy
Máy phát điện hoạt động trong một vùng nhất định, bị giới hạn bởi các yếu tố vật lý như thành phần máy, van hơi và rung động trong trục Việc xem xét vùng vận hành cấm này sẽ dẫn đến sự không liên tục trong đường cong chi phí và chuyển các ràng buộc tương ứng.
Giới hạn dưới và trên của vùng cấm vận hành thứ k của tổ máy thứ i được ký hiệu là P i,k L và P i,k U, trong đó k là chỉ số của vùng cấm và zi là tổng số vùng cấm vận hành.
Hình 2.3 Hàm chi phí nhiên liệu của tổ máy có 2 vùng cấm vận hành d Giới hạn tốc độ thay đổi công suất
Một giả thiết không thực tế trong việc giải bài toán ED là việc điều chỉnh công suất ra của các tổ máy tức thời Tuy nhiên, thực tế cho thấy các giới hạn về tốc độ thay đổi công suất đã hạn chế khả năng vận hành của tất cả các tổ máy nối lưới Sự phát điện có thể được điều chỉnh tăng hoặc giảm trong vùng tương ứng, đảm bảo rằng các tổ máy hoạt động trong giới hạn độ dốc cho phép.
Khi Ramp Rate Limits đƣợc xem xét, giới hạn vận hành đƣợc hiệu chỉnh nhƣ sau: min 0 max 0 i i i i i i i
Max(P , P DR ) P Min(P , P UR ) (2.11) Điểm vận hành trước của máy phát thứ i là P i 0
DRi và URi là giới hạn độ đốc xuống và dốc lên (MW/h).
MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN ĐIỀU ĐỘ KINH TẾ
Bài toán điều độ kinh tế là một dạng bài toán tối ưu với những đặc điểm riêng biệt Nghiên cứu về vấn đề này chủ yếu tập trung vào các giải thuật tối ưu, được phân chia thành ba nhóm kỹ thuật chính: (1) Kỹ thuật quy hoạch toán học; (2) Phương pháp trí thông minh nhân tạo; và (3) Phương pháp lai.
Nhóm phương pháp đầu tiên dựa vào quy hoạch toán học bao gồm các phương pháp như lặp lambda, gradient, lagrange relaxation, quy hoạch tuyến tính, phi tuyến, điểm trong và quy hoạch động Những phương pháp này có ưu điểm là tối ưu được chứng minh bằng toán học, có thể áp dụng cho bài toán lớn và thời gian tính toán nhanh Tuy nhiên, chúng cũng có nhược điểm như hội tụ ở cực trị địa phương, nhạy cảm với giá trị khởi tạo, và không thể đảm bảo giá trị tối ưu toàn cục khi giải bài toán với hàm chi phí không trơn hoặc không lồi Đặc biệt, quy hoạch tuyến tính thường có hiệu quả tính toán kém, trong khi quy hoạch động bị hạn chế bởi kích thước bài toán và cực trị địa phương.
Nhóm phương pháp thứ hai sử dụng trí tuệ nhân tạo, như mạng nơ ron nhân tạo và các phương pháp tìm kiếm ngẫu nhiên như GA, SA, EP, DE, PSO, đã chứng minh hiệu quả trong việc giải quyết các bài toán điều độ kinh tế Mạng nơ ron nhân tạo, ví dụ như HNN, cung cấp giải pháp chất lượng cao cho bài toán điều độ kinh tế với hàm chi phí trơn Các phương pháp tối ưu ngẫu nhiên có khả năng giải bài toán ED mà không bị ràng buộc bởi hình dạng của hàm chi phí nhiên liệu và không phụ thuộc vào đạo hàm cấp 1 hay cấp 2 của hàm mục tiêu Tuy nhiên, những kỹ thuật này gặp phải hạn chế về thời gian tính toán và việc xác định tham số cụ thể cho từng bài toán.
Phương pháp lai là nhóm phương pháp thứ 3, kết hợp hai hoặc nhiều kỹ thuật trước đó để tạo ra giải thuật mới, thừa hưởng các đặc tính ưu việt của các giải thuật đã có Ví dụ về các phương pháp lai bao gồm EP-SQP, PSO-SQP, HNN-QP, EP-PSO-SQP và DE-PSO.
Bài toán điều độ kinh tế trong luận văn được xác định là hàm chi phí không lồi do các yếu tố như vùng cấm vận hành, điểm van công suất và giới hạn thay đổi công suất (RRL), khiến nhóm phương pháp 1 không phù hợp Do đó, tôi sẽ giới thiệu một số giải thuật thuộc nhóm phương pháp thứ 2, đã được nhiều tác giả nghiên cứu và áp dụng để giải quyết bài toán điều độ kinh tế cho các tổ máy nhiệt điện.
2.3.2 Giải thuật mô phỏng luyện kim (Simulated Annealing)
SA (Simulated Annealing) là phương pháp được đề xuất bởi Kirt Patrick, Gelatt và Vecchi năm 1983 SA lấy ý tưởng từ việc luyện kim kim loại
Trong Simulated Annealing (SA), hàm mục tiêu phản ánh năng lượng của kim loại E, trong khi số lần lặp tương ứng với nhiệt độ của quá trình luyện kim Nhiệt độ đóng vai trò là tham số điều khiển cho thuật toán tối ưu, bắt đầu ở mức cao với ứng viên nghiệm hiện tại SA thực hiện nhiều lần lặp, mỗi lần lặp bao gồm nhiều thử nghiệm (trials) Mỗi thử nghiệm tạo ra một nghiệm mới bằng cách thêm thành phần ngẫu nhiên vào nghiệm hiện tại Ứng viên nghiệm mới được chấp nhận nếu năng lượng thấp hơn nghiệm hiện tại, hoặc nếu cao hơn thì chấp nhận với xác suất nhất định Những ứng viên nghiệm được chấp nhận sẽ được sử dụng để tạo ra các ứng viên nghiệm mới Trong các lần lặp tiếp theo, nhiệt độ sẽ giảm dần, và quá trình tìm kiếm nghiệm tiếp tục cho đến khi đạt số lần lặp tối đa hoặc không có cải thiện nào trong hàm mục tiêu so với các lần lặp trước.
Simulated Annealing (SA) có khả năng tránh được cực trị địa phương, cho phép tìm ra nghiệm tối ưu toàn cục hoặc nghiệm gần tối ưu mà không bị giới hạn bởi dạng hàm mục tiêu SA cũng tiêu tốn ít bộ nhớ, nhưng việc thiết lập tham số điều khiển cho thuật toán này khá khó khăn và thời gian tính toán có thể kéo dài Trong nghiên cứu của Panigrahi [9], kỹ thuật SA đã được áp dụng để giải quyết bài toán tối ưu hóa công suất điện (ED) với các ràng buộc như dự phòng quay, điểm van công suất và tổn thất truyền tải.
2.3.3 Giải thuật lai GA (Genetic Algorithm)
Thuật toán di truyền (GA) được phát triển bởi John Holland tại Đại học Michigan và lần đầu tiên được giới thiệu trong cuốn sách của ông vào năm 1975 GA là một cơ chế tìm kiếm dựa trên nguyên lý lai tự nhiên và tiến hóa, bắt đầu với một tập hợp các ứng viên được chọn ngẫu nhiên trong không gian tìm kiếm và mã hóa thành chuỗi nhị phân, tạo thành nhiễm sắc thể Mỗi thành viên trong tập hợp này được giải mã và đánh giá dựa trên hàm phù hợp, chủ yếu phụ thuộc vào giá trị hàm mục tiêu Tập hợp khởi tạo trải qua ba quá trình chính: lựa chọn, lai ghép và đột biến Quá trình lựa chọn chọn ra các thành viên bố mẹ để tiến hành lai ghép, trong khi lai ghép kết hợp các nhiễm sắc thể của bố mẹ với xác suất nhất định để tạo ra nhiễm sắc thể con Sau khi tập hợp mới được tạo thành, đột biến được áp dụng với xác suất nhỏ để tạo ra thông tin mới Quá trình này lặp lại cho đến khi đạt tiêu chuẩn hội tụ.
GA là một kỹ thuật tối ưu hóa toàn cục, có khả năng tìm kiếm song song để giải quyết bài toán ED với hàm mục tiêu không trơn và không lồi Li [11] đã áp dụng GA để giải quyết bài toán ED, đồng thời xem xét tổn thất truyền tải Tuy nhiên, GA có nhược điểm là thời gian tính toán dài và dễ bị hội tụ sớm.
2.3.4 Phương pháp EP (Evolutionary Programming)
EP là một kỹ thuật tìm kiếm ngẫu nhiên dựa trên tiến trình tiến hóa của chọn lọc tự nhiên Phương pháp này bắt đầu với một tập hợp các véc tơ đích bố mẹ ngẫu nhiên trong không gian tìm kiếm Thế hệ con được tạo ra thông qua quá trình đột biến, bằng cách thêm một đại lượng ngẫu nhiên vào thế hệ bố mẹ Các bố mẹ và con cái có hàm mục tiêu tốt nhất sẽ được chọn cho các vòng lặp tiếp theo Quá trình đột biến, cạnh tranh và lựa chọn sẽ tiếp tục cho đến khi đạt được điều kiện đã đặt ra.
Theo nghiên cứu, phương pháp Evolutionary Programming (EP) khác biệt với Genetic Algorithm (GA) ở hai điểm chính: EP sử dụng các giá trị thực làm tham số điều khiển thay vì mã hóa như GA, và nó chủ yếu dựa vào sự đột biến và lựa chọn hơn là lai ghép như GA truyền thống Thêm vào đó, thời gian tính toán trong EP cũng được cải thiện đáng kể.
EP có ưu điểm nổi bật là chỉ sử dụng thông tin từ hàm mục tiêu, không bị ảnh hưởng bởi đặc điểm của không gian tìm kiếm như độ trơn hay độ lồi Hơn nữa, EP không phụ thuộc vào đạo hàm bậc nhất và bậc hai của hàm mục tiêu cũng như các điều kiện ràng buộc của bài toán So với GA, EP không sử dụng phép lai tạo, sơ đồ mã hóa hay giải mã, do đó có tốc độ nhanh hơn Mặc dù EP có khả năng mang lại kết quả chất lượng tốt hơn GA, nhưng nó cần nhiều thời gian hơn và đôi khi vẫn gặp vấn đề về hội tụ.
2.3.5 Phương pháp DE (Differential Evolution)
Thuật toán DE, được Storn và Price đề xuất vào năm 1997, là một trong những phương pháp tốt nhất trong các giải thuật tiến hóa (Evolutionary Algorithms) và được sử dụng rộng rãi để giải quyết các bài toán tối ưu Phương pháp này là một kỹ thuật tìm kiếm song song dựa trên tập hợp, sử dụng các toán tử tiến hóa tương tự như các giải thuật khác.
GA, DE sử dụng thông tin về khoảng cách và hướng của tập cá thể hiện thời để định hướng việc tìm kiếm
Giải thuật bắt đầu bằng việc tạo ra các giải pháp ứng viên ngẫu nhiên trong không gian tìm kiếm để khám phá Sau đó, nó xác định vị trí tối ưu toàn cục bằng cách tinh chỉnh tập hợp thông qua các bước sinh sản, lựa chọn và tạo ra các thế hệ con thông qua quá trình đột biến, lai tạo và lựa chọn, cho đến khi tìm được lời giải tối ưu hoặc đạt số lần lặp tối đa.
Trong quá trình đột biến, ba véc tơ được chọn ngẫu nhiên từ tập hợp véc tơ, và véc tơ đột biến được tạo ra bằng cách trộn lẫn một véc tơ với sự khác biệt của hai véc tơ còn lại.
Hình 2.4 Sơ đồ lai tạo véc tơ trong giải thuật DE
GIẢI THUẬT GSA VÀ GSA CẢI TIẾN
GIẢI THUẬT GSA CỔ ĐIỂN
Giải thuật tối ưu GSA, được Rashedi đề xuất vào năm 2009, lấy cảm hứng từ luật trọng trường của Newton Trong thuật toán này, các cá thể được đánh giá dựa trên khối lượng của chúng, và tất cả các vật thể tương tác với nhau thông qua lực trọng trường Lực này không chỉ tạo ra chuyển động cho các vật thể mà còn khiến chúng có xu hướng di chuyển về phía các vật thể có khối lượng lớn hơn Những vị trí của các vật thể nặng được coi là những giải pháp tối ưu cho bài toán.
Trong GSA, mỗi vật thể được xác định bởi bốn thông số: vị trí, khối lượng quán tính, khối lượng trọng trường chủ động và khối lượng trọng trường thụ động Vị trí của vật thể tương ứng với lời giải của bài toán, trong khi khối lượng quán tính và trọng trường được tính toán từ hàm mục tiêu Mỗi vật thể đại diện cho một lời giải, và sau mỗi vòng lặp của thuật toán, khối lượng của các vật thể sẽ được điều chỉnh, với các vật thể bị hấp dẫn bởi vật nặng nhất Vật thể nặng nhất này sẽ phản ánh lời giải tối ưu trong không gian tìm kiếm.
Trong giải thuật GSA, các vật thể được coi là nằm trong một hệ cách ly, nơi mà chúng di chuyển theo quy luật trọng trường và các định luật chuyển động của Newton.
Luật trọng trường mô tả rằng mỗi phần tử hấp dẫn các phần tử khác, với lực trọng trường giữa chúng tỷ lệ thuận với tích khối lượng và tỷ lệ nghịch với khoảng cách giữa chúng, R Các tác giả đề xuất sử dụng R thay vì R², vì các kết quả thí nghiệm cho thấy R mang lại hiệu quả tốt hơn trong mọi trường hợp thử nghiệm.
Luật chuyển động cho biết rằng vận tốc tức thời của một vật thể bằng tổng vận tốc trước đó và sự thay đổi vận tốc Sự thay đổi vận tốc, hay còn gọi là gia tốc, được xác định bởi lực tác động lên hệ chia cho khối lượng quán tính của vật thể.
Bây giờ, xét một hệ có N phần tử (agents) Chúng ta định nghĩa vị trí của phần tử thứ i là: X i (x , x , x , , x ) 1 i 2 i d i n i với i = 1,2,…,N (3.1)
Trong đó x d i là vị trí của vật thể i theo chiều d
Tại thời điểm t, ta định nghĩa lực tác dụng lên vật thể i từ vật thể j là: pi aj d d d ij j i ij
+ M aj là khối lượng hấp dẫn chủ động của vật thể j
+ M pi là khối lượng hấp dẫn thụ động của vật thể i
+ G(t) là hằng số trọng trường tại thời điểm t
+ R ij (t) là khoảng cách Euclide của vật thể i và j: ij i j 2
Để đảm bảo giải thuật có tính ngẫu nhiên, giả định rằng lực tổng hợp tác động lên vật thể i theo chiều d là tổng ngẫu nhiên của các thành phần lực theo chiều d từ các vật thể khác.
Trong đó: rand j là một số ngẫu nhiên trong đoạn [0, 1]
Theo luật chuyển động, gia tốc của vật thể i, theo hướng d, ở thời điểm t là a (t) d i : d d i i ii
Trong đó: M ii là khối lượng quán tính (inertial mass) của vật thể i
Vận tốc của một vật thể tại thời điểm tiếp theo được xác định bằng vận tốc hiện tại cộng với gia tốc Do đó, vị trí và vận tốc của vật thể tại thời điểm tiếp theo có thể được tính theo công thức: d(i+1) = d(i) + v(t) + a(t).
Trong đó: rand i là một biến ngẫu nhiên chuẩn (uniform random variable) trong đoạn [0,1]
Hình 3.1 Lực và gia tốc tương tác lên vật thể 1 do các vật thể khác sinh ra
Hằng số trọng trường G được khởi tạo từ đầu và sẽ giảm dần theo thời gian để điều chỉnh độ chính xác tìm kiếm Nói cách khác, G là hàm của giá trị ban đầu G0 và thời gian t.
Khối lượng quán tính và trọng trường được xác định thông qua việc đánh giá giá trị hàm mục tiêu Khối lượng nặng hơn cho thấy vật thể có hiệu quả cao hơn trong việc tìm kiếm giải pháp, với lực hấp dẫn lớn hơn và tốc độ di chuyển chậm hơn Giả định rằng khối lượng quán tính và trọng trường tương đương, giá trị của chúng được tính toán dựa trên giá trị hàm mục tiêu Chúng ta cập nhật các khối lượng này theo phương trình đã cho.
Mai=Mpi=Mii=Mi, i=1,2,…N (3.9) i i fit (t) worst(t) m (t) best(t) worst(t)
+ fit i (t) là giá trị fitness của vật thể i tại thời điểm t
+ worst(t), best(t) đƣợc định nghĩa (trong bài toán tìm Min) nhƣ sau : best(t) min fit (t), j j 1 N (3.12) worst(t) maxfit (t), j j 1 N
Trong bài toán tìm max thì giá trị best(t) lấy max fit j (t) còn giá trị worst(t) lấy min fit j (t)
Một cách hiệu quả để kết hợp exploration và exploitation là giảm số lượng vật thể tương tác theo thời gian Tác giả đề xuất chỉ cho phép các vật thể có khối lượng lớn hơn tác động lên những vật thể khác, mặc dù điều này có thể làm giảm sức mạnh của exploration và tăng khả năng exploitation Để tránh kẹt ở cực trị địa phương, thuật toán sẽ bắt đầu bằng việc mở rộng không gian tìm kiếm, sau đó giảm dần khả năng exploration và tăng cường exploitation qua các lần lặp Hiệu suất của GSA được cải thiện bằng cách điều chỉnh exploration và exploitation, chỉ những vật thể trong tập Kbest mới tác động đến các vật thể khác Số lượng vật thể trong Kbest phụ thuộc vào thời gian, bắt đầu từ giá trị khởi tạo K0 và giảm dần Ví dụ, ban đầu tất cả các vật thể đều tương tác với nhau, nhưng theo thời gian, Kbest sẽ giảm và chỉ còn lại những vật thể nặng nhất tác động đến các vật thể khác Do đó, phương trình (3.4) có thể được điều chỉnh lại như sau: i d N j ij d j Kbest, j i.
Trong đó Kbest là tập của K phần tử đầu tiên có giá trị fitness tốt nhất và khối lƣợng lớn nhất
Lưu đồ của GSA như hình dưới:
Hình 3.2 Nguyên lý của giải thuật GSA
Các bước trong giải thuật GSA:
Bước 1- Khởi tạo vị trí các vật thể
Khởi tạo một tập hợp các vật thể với vị trí ngẫu nhiên trong không gian D chiều được thực hiện thông qua hàm phân bố xác suất Trong phương pháp này, GSA xem xét hệ thống gồm N phần tử, với vị trí thứ i được xác định theo công thức (3.15).
X (x , x , x , , x )với i = 1,2,…,N (3.15) Ở đây xi d là vị trí của vật thể i theo chiều d và D là số chiều không gian
Bước 2: Đánh giá hàm mục tiêu của các vật thể
Bước 3: Cập nhật G(t), best(t), worst(t), Mi(t) đối với i=1 N:
Trong GSA, hằng số trọng trường G, lúc đầy lấy một giá trị khởi tạo G 0 , sau đó sẽ đƣợc giảm dần theo thời gian: G(t)G(G , t)0 (3.16)
Khối lƣợng của vật thể đƣợc tính toán sau khi tính đƣợc hàm mục tiêu của tập hợp hiện tại: i i fit (t) worst(t) m (t) best(t) worst(t)
Trong bài toán tối ưu hóa, khối lượng và giá trị hàm mục tiêu của vật thể i tại thời điểm t được ký hiệu là M i (t) và fit i (t) Để xác định giá trị tốt nhất và kém nhất, ta sử dụng các công thức: giá trị tốt nhất tại thời điểm t được tính bằng cách lấy giá trị lớn nhất của fit(t) từ tất cả các vật thể, ký hiệu là best(t) = max fit(t), với j chạy từ 1 đến N Ngược lại, giá trị kém nhất được xác định bằng giá trị nhỏ nhất của fit(t), ký hiệu là worst(t) = min fit(t), với j cũng chạy từ 1 đến N.
Bước 4: Tính toán lực tổng hợp theo các hướng khác nhau:
Lực tổng hợp của tập các vật thể có khối lƣợng nặng hơn sẽ tác dụng lên vật thể i được tính dựa vào lực trọng trường: j i d d d i j j i j Kbest, j i ij
+ rand j là giá trị ngẫu nhiên từ [0,1]
+ ε là một số nhỏ và R ij (t) là khoảng cách Euclidian giữa 2 vật thể i và j
+ Kbest là tập hợp các phần tử có khả năng tác dụng lực lên các phần tử còn lại
Bước 5: Tính toán gia tốc và vận tốc:
Gia tốc của vật thể đƣợc tính nhờ luật chuyển động d d i i d d i j j i j Kbest, j i i ij
Trong đó rand j là số ngẫu nhiên trong đoạn [0,1]
Vận tốc mới của vật thể bằng vận tốc cũ của vật thể cộng gia tốc: d d d i i i i v (t 1) rand v (t) a (t) (3.23)
Bước 6-Cập nhật vị trí các vật thể: d d d i i i x (t 1) x (t) v (t 1) (3.24)
Bước 7-Lặp lại chu trình trên
Lặp lại từ bước 2 đến bước 6 đến khi gặp điều kiện dừng, thường điều kiện dừng là hàm mục tiêu đủ tốt hoặc số lần lặp đến tối đa
Một số lưu ý về giải thuật GSA:
+ Do mỗi phần tử có thể quan sát đặc tính của các phần tử khác, cho nên lực trọng trường là công cụ truyền thông tin
+ Do lực này tác dụng lên mỗi phần tử từ các phần tử lân cận, nên nó có thể quan sát đƣợc không gian xung quanh nó
Một vật thể nặng với bán kính tương tác hiệu quả lớn sẽ tạo ra cường độ hấp dẫn mạnh mẽ Do đó, các vật thể có hiệu quả cao hơn thường sở hữu khối lượng trọng trường lớn hơn Hệ quả là các vật thể có xu hướng di chuyển về phía phần tử tốt nhất.
Khối lượng quán tính của một vật thể thể hiện khả năng chống lại sự chuyển động, làm cho vật thể di chuyển chậm hơn Do đó, những vật thể có khối lượng quán tính lớn sẽ di chuyển chậm, điều này hỗ trợ hiệu quả trong việc tìm kiếm và xác định địa phương.
+ Hằng số trọng trường hiệu chỉnh độ chính xác tìm kiếm, cho nên nó được giảm theo thời gian
GSA là một giải thuật không cần nhớ, cập nhật vận tốc và vị trí dựa trên thông tin hiện tại của vật thể, khác với PSO cần thông tin quá khứ của cá thể như P besti và G best Tuy nhiên, GSA vẫn hoạt động hiệu quả tương tự như các giải thuật cần nhớ.
MỘT SỐ CẢI TIẾN TRONG GIẢI THUẬT GSA
Các phương pháp tối ưu dựa vào khái niệm exploration và exploitation rất quan trọng trong việc mô tả hoạt động của giải thuật Exploration cho phép điều tra toàn bộ không gian tìm kiếm để phát hiện những vị trí tốt hơn, trong khi exploitation tập trung vào việc tìm kiếm nghiệm tối ưu xung quanh một nghiệm tốt đã được phát hiện Do hai khái niệm này có tác động đối lập, giải thuật cần duy trì sự cân bằng giữa chúng để đạt được nghiệm tối ưu toàn cục Kể từ khi GSA ra đời vào năm 2009, đã có nhiều cải tiến giúp GSA hoạt động hiệu quả hơn trong các bài toán tối ưu.
Giải thuật GSA nổi bật với những ưu điểm như sự đơn giản, tính ổn định và khả năng thích ứng cao, cho phép ứng dụng hiệu quả trong nhiều bài toán tối ưu Đặc biệt, nó còn có khả năng tìm kiếm toàn cục, giúp nâng cao hiệu quả giải quyết vấn đề.
Khả năng tìm kiếm toàn cầu của GSA vượt trội hơn so với nhiều thuật toán nổi tiếng khác trong hầu hết các tình huống Tuy nhiên, khả năng tìm kiếm địa phương của GSA lại còn hạn chế Để cải thiện khả năng tìm kiếm địa phương, nhiều nghiên cứu đã đề xuất các giải pháp như kết hợp GSA với SA hoặc PSO.
3.2.2 Một số cải tiến trong giái thuật GSA a Sobol GSA [27] Để cải thiện hiệu quả của GSA, với tƣ cách là một giải thuật dựa vào tập hợp Thì việc phân bố các particle ban đầu rất quan trọng Thay vì phân bố theo uniform distribution thì dùng phân bố quasi-random trong giai đoạn khởi tạo vận tốc và vị trí của các vật thể đã giúp cải thiện hiệu quả của giải thuật GSA Đặc biệt, trong bài toán có nhiều chiều và số điểm cực trị địa phương nhiều, thì hiệu quả thấy rõ hơn a) Phân bố theo quasi-ramdom b) Phân bố theo uniform random
Hình 3.3 Phân bố các điểm khởi tạo theo quasi-random và uniform random
Kết quả thử nghiệm trên hàm tối ưu benchmark cho thấy Sobol GSA hiệu quả hơn GSA trong các bài toán có đa cực trị, trong khi đó, trong các bài toán với ít cực trị địa phương, hiệu quả của Sobol GSA và GSA là tương đương.
Sarafrazi trong nghiên cứu của mình đã chỉ ra rằng GSA sử dụng lực trọng trường để định hướng chuyển động của các vật thể Khi xảy ra hội tụ non, thuật toán sẽ dừng lại vì không có lực nào có thể kéo các vật thể ra khỏi điểm hội tụ đó Điều này dẫn đến việc thuật toán mất khả năng mở rộng không gian tìm kiếm và không còn hoạt động Để khắc phục vấn đề này, tác giả đã đề xuất bổ sung toán tử Disruption vào giải thuật GSA.
Các vật thể gần nhau sẽ không góp phần mở rộng không gian tìm kiếm, vì vậy chỉ những vật thể đáp ứng các điều kiện nhất định mới được xem xét để thực hiện Disruption ij ibest.
Điều kiện R (3.25) chỉ ra rằng nếu tỷ số giữa khoảng cách của vật thể i đến vật thể gần nhất j và khoảng cách của vật thể i đến vật thể tốt nhất nhỏ hơn ngưỡng xác định C, thì vật thể i sẽ bị Disrupted, tức là vị trí của nó sẽ bị dịch chuyển theo một hằng số.
D nhƣ công thức (3.26) ij ibest
X i (mới) = X i (cũ).D (3.26.2) Điều kiện (3.25) đảm bảo rằng các vật thể không quá gần nhau ở giai đoạn đầu (với C có giá trị lớn), trong khi ở giai đoạn cuối, việc các vật thể lại gần nhau hơn là chấp nhận được (với C có giá trị nhỏ hơn).
Toán tử này bắt đầu bằng cách mở rộng không gian tìm kiếm, sau đó sẽ chuyển sang tìm kiếm điểm tối ưu xung quanh một nghiệm tốt sau một khoảng thời gian nhất định.
Hình 3.4 Các bước của giải thuật IGSA c Opposition-based GSA [18]
Kể từ khi Tizhoosh giới thiệu phương pháp học dựa trên đối kháng (OBL) vào năm 2005, phương pháp này đã được áp dụng để cải thiện tốc độ hội tụ của các thuật toán tối ưu.
Phương pháp DE đối kháng (Opposition-based DE) do Tizhoosh phát triển vào năm 2008, tập trung vào việc xem xét đồng thời các lời giải và lời giải đối kháng để cải thiện chất lượng kết quả Bài báo này áp dụng OBL nhằm tăng tốc độ hội tụ của thuật toán GSA, dẫn đến một phương pháp cải tiến hiệu quả hơn.
GSA dựa trên sự đối lập, sử dụng các điểm đối lập (ứng viên nghiệm đối lập) trong quá trình khởi tạo tập hợp và tạo ra tập hợp mới.
Các phương pháp tối ưu tiến hóa bắt đầu bằng một tập khởi tạo và cải tiến các phần tử hướng đến lời giải tối ưu Quá trình này kết thúc khi các tiêu chuẩn đã được xác định được thoả mãn Do thiếu thông tin về nghiệm, chúng ta thường khởi đầu bằng các dự đoán ngẫu nhiên Thời gian tính toán phụ thuộc vào khoảng cách từ tập khởi tạo đến nghiệm tối ưu, và có thể được cải thiện bằng cách sử dụng một tập khởi tạo tốt hơn thông qua việc kiểm tra đồng thời giá trị hàm mục tiêu của tập khởi tạo và giải pháp đối ngược Điều này cho phép chọn một phần tử tốt hơn làm phần tử khởi tạo, từ đó tăng tốc độ hội tụ Cách tiếp cận tương tự cũng được áp dụng cho tập ứng viên nghiệm hiện tại.
Khái niệm Số đối lập (opposite number)
Cho x a, b là một số thực Số đối lập (opposite number) đƣợc định nghĩa nhƣ sau: x a b x (3.27)
Tương tự, định nghĩa này được mở rộng cho nhiều chiều hơn như trong section 3.2
Khái niệm Điểm đối lập (opposite point) Đặt P=(x 1 ,x 2 ,…,x d ) là một điểm trong không gian d chiều, ở đây x 1 , x 2 ,x 3 ,…x d ϵR và x i ϵ[a i , b i ] x i a , b i i i 1, 2 , d Điểm đối lập P=(x , x , ,x ) 1 2 d trong đó i i i i x a b x (3.28)
Giải thuật OGSA sử dụng điểm đối lập trong hai giai đoạn Giai đoạn đầu tiên là khởi tạo, nơi tạo ra một tập hợp điểm ngẫu nhiên cùng với tập hợp điểm đối lập tương ứng Tại đây, giá trị hàm mục tiêu được tính toán và chọn ra N điểm có giá trị tốt nhất từ 2N điểm Những điểm này sau đó tương tác theo luật trọng trường và di chuyển theo quy luật Newton Sau khi xác định vị trí mới, các điểm đối lập được tạo ra và tiếp tục chọn N điểm có giá trị hàm mục tiêu tốt nhất từ 2N điểm Trong giai đoạn thứ hai, điểm đối lập chỉ được sử dụng với xác suất nhất định Jr, không áp dụng cho tất cả các lần lặp.
ÁP DỤNG GIẢI THUẬT GSA VÀ GSA CẢI TIẾN GIẢI BÀI TOÁN ĐIỀU ĐỘ KINH TẾ
XỬ LÝ GIỚI HẠN CÔNG SUẤT LỚN NHẤT, NHỎ NHẤT CỦA TỔ MÁY
Để đảm bảo công suất của các tổ máy nằm trong giới hạn cho phép, các tổ máy sẽ được khởi tạo ngẫu nhiên trong khoảng Pmin và Pmax theo phân bố chuẩn.
Bài toán ED có ràng buộc đẳng thức liên quan đến cân bằng công suất giữa công suất phát và tải, do đó, phương pháp biến cân bằng công suất được áp dụng Trong trường hợp có N phần tử, chỉ cần tìm kiếm giá trị cho N-1 phần tử, phần tử còn lại sẽ được tính từ ràng buộc này, giúp giảm số chiều của bài toán từ N xuống N-1 Việc này cải thiện khả năng hội tụ và giảm thời gian tìm kiếm Công thức khởi tạo chỉ áp dụng cho N-1 tổ máy, ngoại trừ tổ máy cân bằng Để đảm bảo cân bằng công suất, chỉ có N-1 tổ máy được khởi tạo ngẫu nhiên; giả sử tổ máy 1 là tổ máy cân bằng, công suất của tổ máy 2 đến N sẽ được khởi tạo ngẫu nhiên, trong khi công suất của tổ máy 1 sẽ được xác định theo quy trình cụ thể.
Để đảm bảo công suất phát của tổ máy cân bằng nằm trong giới hạn cho phép, cần bổ sung thành phần hàm phạt vào hàm mục tiêu khi tổ máy vi phạm vùng giới hạn vận hành.
F' i 1 f (P ) K max(0, P P ) max(0, P P ) (4.3) Trong đó: K là hệ số phạt của tổ máy cân bằng f(Pi) là chi phí phát công suất P i của tổ máy i
ẢNH HƯỞNG CỦA TỔN THẤT TRUYỀN TẢI
Khi xem xét tổn thất công suất truyền tải, bài toán trở nên phức tạp hơn, vì công suất của nút cân bằng không thể tính đơn giản bằng cách lấy công suất tải yêu cầu trừ đi tổng công suất các tổ máy khác Thay vào đó, công suất nút cân bằng được xác định thông qua việc giải phương trình (4.2) với biến là công suất của tổ máy cân bằng Tổn thất truyền tải được xác định theo cách này.
Trong đó: [B] là ma trận vuông cỡ NxN
B 0 là véc tơ kích cỡ [1xN]
Từ (4.4) đƣợc viết lại nhƣ sau:
Giả sử tổ máy 1 là tổ máy cân bằng công suất thì rút P 1 ra khỏi phương trình trên ta đƣợc:
Như vậy, công suất tổ máy cân bằng P 1 được xác định theo phương trình sau:
4.3 XỬ LÝ RÀNG BUỘC GIỚI HẠN THAY ĐỔI CÔNG SUẤT VÀ VÙNG CẤM VẬN HÀNH
Khi xem xét giới hạn thay đổi công suất của tổ máy (RRL), công suất lớn nhất (P i,high) và nhỏ nhất (P i,low) của các máy phát được xác định dựa trên giới hạn công suất ra, công suất ra ban đầu và ràng buộc ramprate.
Khi công suất ra lớn nhất và nhỏ nhất của một máy phát vi phạm vùng cấm, các giá trị này sẽ được xác định lại Nếu công suất ra lớn nhất hoặc nhỏ nhất của máy phát i vi phạm vùng cấm k, giới hạn mới sẽ được thiết lập theo quy định mới.
Khi máy phát hoạt động trong vùng cấm, chiến lược hiệu chỉnh được áp dụng để đưa nó về dưới giới hạn tối thiểu hoặc nhảy lên giới hạn tối đa Để đưa ra quyết định dựa trên điểm vận hành của tổ máy trong vùng cấm, điểm chính giữa của vùng cấm P ik m sẽ được xác định.
Điểm giữa phân chia vùng cấm thành hai khu vực: vùng cấm bên phải và bên trái Nếu điểm vận hành P i của tổ máy i vi phạm vùng cấm, sẽ được hiệu chỉnh theo công thức l m new ik i ik i u m ik i ik.
Khi xem xét ramprate, chiến lược hiệu chỉnh trở nên phức tạp hơn Một phương pháp khả thi để điều chỉnh điểm vận hành i khi vi phạm vùng cấm k là dựa vào công suất ra ban đầu P i0 và vị trí vi phạm.
u u ik i,low i0 ik new u l u i ik i0 ik ik i,high l l u ik i,high i0 ik ik i,high max P , P if P P
P P , if P P and P P min P , P if P P and P P
l l ik i,high i0 ik new l u l i ik i0 ik ik i,low u u l ik i,low i0 ik ik i,low min P , P if P P
P P , if P P and P P max P , P if P P and P P
GIẢI THUẬT GSA CHO BÀI TOÁN ĐIỀU ĐỘ KINH TẾ
+ Thông số tải: PD + Thông số máy phát: N, ai,bi,ci,ei,fi, Pmin, Pmax + Thông số giải thuật GSA: G0, α , final_per, Itmax, D
2 Khởi tạo ngẫu nhiên xid (1) , vid (1) theo công thức 4.1và đặt it=1
3 Nếu it≤Itmax bước 4, ngược lại đến bước 11
4 Kiểm tra và hiệu chỉnh Xid đảm bảo trong giới hạn…
5 Tính hàm mục tiêu cho các cá thể
6 Tính khối lƣợng M d cho từng vật thể
7 Tính gia tốc Aid (it)
8 Tính vận tốc Vid (it+1
9 Tính vị trí các vật thể Xid (it+1
10 it=it+1 và quay lại bước 3
Bước 2: Khởi tạo pid, xid, vid cho các tổ máy (ngoại trừ tổ máy cân bằng) Chọn tổ máy 1 là tổ máy cân bằng id i,min i,max i,min
Nếu số lần lặp đã đạt tối đa, hãy in kết quả Nếu chưa, tiếp tục kiểm tra và điều chỉnh Xid trong giới hạn cho phép.
X P ,if X P id (i 1) min id (i 1) min
Bước 5: Tính toán hàm mục tiêu cho các cá thể
+ Nếu không xét tổn thất công suất thì:
+ Nếu xét đến tổn thất công suất thì X 1d (hay P 1d )được tính từ phương trình bậc 2 (4.5)
Công suất của các tổ máy: P id [X ; X ] 1d id
Hàm chi phí nhiên liệu từng tổ máy khi xét điểm van công suất:
2 id id id id id id id id i 1,min id f (P )a b * P c * P e *sin(f *(P P )) ,i 1 N
Hàm chi phí nhiên liệu từng tổ máy khi xét đến điểm van công suất+ đặc tính đa nhiên liệu:
2 min min max ik i ik i ik ik ik ik ik ik 1 i i a P b P c e sin(f (P P )) , fuel1, P P P a P b P c e sin(f (P P )) , fuel2, P P P f (P ) a P b P c e sin(f (P P )) , fuelk, P P P
Hàm chi phí nhiên liệu tổng:
N id 1d 1max 1min 1d fd i 1 f (P ) K * max(0, X P ) max(0, P X )
Bước 6 : Tính khối lượng M d , G, Kbest, best, worst best=min(fd); worst=max(fd)
Md=(fd-worst)./(best-worst)
Kbesth sách kbest% các vật thể nặng nhất
Bước 7 : Tính gia tốc Aid cho từng vật thể
Kbest N 1 (it ) id ik id kd k 1 i 1
Bước 8 : Tính vận tốc V id (it+1)
(it 1) (it ) (it ) id id id
Bước 9: Tính vị trí Xid (it+1)
(it 1) (it ) (it 1) id id id
Bước 10 Tăng số lần lặp lên 1 và kiểm tra đạt số lần lặp tối đa Bước 11 Xuất ra kết quả vị trí vật thể tốt nhất
GIẢI THUẬT DEGSA CHO BÀI TOÁN ĐIỀU ĐỘ KINH TẾ
Trong phần này, trình bày cải tiến giải thuật GSA bằng cách lai giữa GSA và
DE theo sơ đồ sau:
+ Thông số máy phát: N, ai,bi,ci,ei,fi, Pmin, Pmax
+ Thông số giải thuật GSA: G0, α , final_per, Itmax, D
2 Khởi tạo ngẫu nhiên xid (1) , vid (1) theo công thức 4.1và đặt it=1,d=1;
3 Kiểm tra số lần lặp tối đa Itmax
4 Kiểm tra các vật thể đã đƣợc xét trong tập hợp D
5 Lai tạo U(d) (it) của từng X(d) (it) theo tỷ lệ lai tạo Cr
6 Nếu F(u(d))
