Luận văn Quy hoạch mở rộng lưới truyền tải sử dụng thuật toán mặt cắt tối thiểu

c cho giải pháp tối ưu nhất. Nếu một bước tabu từ các giải pháp hiện tại 𝑋𝑐𝑢𝑟𝑟𝑒𝑛𝑡 có thể đạt được một giải pháp tốt hơn so với các giải pháp tốt nhất được tìm thấy, khi đó mức kỳ vọng cho bước tabu này là đạt được và có thể được ghi đè. Như vậy, dựa trên mô hình phân bố công suất DC, bài toán được công thức hóa dưới dạng quy hoạch nguyên 0 – 1 và sử dụng thuật toán TS để giải. Các ví dụ mẫu cho kết quả khả quan: Sơ đồ Graver 6 bus cho kết quả sau 14s với 30 lần lặp; sơ đồ 18 bus cho kết quả sau 32s với 30 lần lặp; sơ đồ 39 bus với 47s và 50 lần lặp.  Áp dụng TS với bộ nhớ trung-dài hạn Khi sử dụng mô hình DC xây dựng bài toán STEP, (2.7) là một tập các trang bị truyền dẫn mới cần phải xây dựng. Chi phí cho mỗi giải pháp gồm chi phí đầu tư và chi phí cắt giảm tải (được đại diện bởi 2.10, là bài toán LP). Tuy nhiên, trong trường hợp một số nhà máy mới hoặc trung tâm phụ tải không kết nối được, thì (2.10) không có lời giải. Được đề xuất tại [10], để tìm giải pháp cho (2.10), thực hiện thêm vào các mạch ứng viên không bị cấm với chi phí tối thiểu để kết nối lưới, quá trình này dừng lại khi lưới được kết nối đầy đủ. Thuật toán thực hiện được thể hiện tại Hình 2.2, trong đó:  (1) Giai đoạn mở rộng (Expansion Phase - EP): 21 Để tìm kiếm các phương án khả thi, bằng cách chạy EP một số lần hoặc từ một số các giải pháp mạng kết nối đầy đủ khác nhau ban đầu hoặc sửa đổi các tiêu chí tại các bước chuyển. Dựa vào bộ nhớ trung hạn, lựa chọn được các giải pháp xuất hiện nhiều nhất trên các EP khác nhau, độc lập với cấu hình ban đầu và phù hợp với các tiêu chí tại các bước chuyển. Trong trường hợp EP không đạt yêu cầu, giải pháp không được cập nhật và bắt đầu một EP mới. Start D=0 Cấu hình lưới ban đầu Xử lý mở rộng (EP) - Xác định các mạch thường gặp - Xây dựng danh sách Tabu D=D+1 Y End D≤Dmax Tăng cường giai đoạn 1 (IP1) Tăng cường giai đoạn 2 (IP2) Lưu giữ giải pháp Giải pháp cuối = Giải pháp chi phí tối thiểu N Hình 2.2. Lưu đồ thuật toán Tabu Search với bộ nhớ trung-dài hạn  (2) Giai đoạn tăng cường (Intensification Phase - IP): 22 Trong giai đoạn tăng cường IP, một bước chuyển gồm sự hoán đổi hai hay nhiều mạch, tức là, thay thế một mạch ứng viên bởi một mạch khác bằng cách ưu tiên chỉ tiêu điện dẫn trong khi các tiêu chí khác là như nhau. IP được chia thành hai vòng lặp, IP1 cho phép bước chuyển các giải pháp có chi phí đầu tư nhỏ và IP2 cho phép bước chuyển các giải pháp chi phí lớn hơn (với dung sai cho trước) để bỏ qua các giải pháp tối ưu địa phương. Tuy nhiên, tất cả các bước chuyển của IP1 và IP2 đều ở trong vùng khả thi.  (3) Giai đoạn đa dạng hóa (Diversification Phase - DP): Dùng để thực hiện một tìm kiếm tích cực hơn, với mục tiêu tìm kiếm hướng tới khu vực chưa khám phá trong không gian tìm kiếm. Giai đoạn đa dạng hóa sử dụng bộ nhớ dài hạn của TS và thực hiện đưa mạch ứng viên xuất hiện nhiều nhất vào TL cho EP tiếp theo; thủ thuật này nhằm thúc đẩy EP và IP tìm các giải pháp thử nghiệm khác nhau cho STEP tại các khu vực chưa được khám phá. 2.2.2.2. Thuật toán di truyền GA  Giới thiệu chung về thuật toán GA Được xây dựng bởi J.H.Hoolland năm 1975, thuật toán GA là một phương pháp hiệu quả để giải các bài toán tối ưu hóa tổ hợp với chi phí tính toán thấp, đặc biệt là đối với các bài toán lớn và trung bình. Thuật toán GA dựa trên quy luật chọn lọc tự nhiên, trong đó các cá nhân thích nghi hơn có nhiều cơ hội để tồn tại và truyền mã di truyền cho thế hệ sau. Về mặt toán học, thuật toán GA được xem là một kỹ thuật tối ưu hóa tổ hợp có khả năng cao trong việc tìm kiếm các giải pháp tối ưu toàn cục cho các bài toán lớn và phức tạp có nhiều giải pháp tối ưu địa phương. Về cơ bản, thuật toán GA gồm:  (1) Mã hóa và khởi tạo: - Mã hóa: Mã hóa các thông số hoặc giải pháp không gian thành các chuỗi nhị phân (nhiễm sắc thể). - Khởi tạo: Thường được thực hiện bởi sự tạo ngẫu nhiên một quần thể (các lời giải cho bài toán) từ các nhiễm sắc thể. 23  (2) Quá trình lựa chọn: Cung cấp tiêu chuẩn đánh giá thích nghi cho từng đối tượng theo bài toán đã đưa ra.  (3) Các hoạt động di truyền: Có ba hoạt động cơ bản trong quá trình này: - Hoạt động sinh sản: Các chuỗi có các giá trị thích nghi lớn hơn sẽ có xác suất cao hơn trong việc tạo ra một số lượng lớn các bản sao của chúng trong thế hệ sau thông qua hoạt động sinh sản. Trong quá trình chọn lọc, chuỗi tốt nhất hiện hữu được đảm bảo tồn tại lâu dài từ thế hệ này sang thế hệ khác bằng cách tạo ra một bản sao trực tiếp của chính nó vào thế hệ kế tiếp. Các chuỗi sao chép sau đó được đặt trong một “bể kết hợp” để sử dụng tiếp cho thế hệ sau. - Hoạt động lai ghép: Các chuỗi có thể trao đổi thông tin theo xác suất của hoạt động lai ghép. Hai chuỗi được lựa chọn từ “bể kết hợp” và được sắp xếp để trao đổi những thành phần tương ứng của các chuỗi nhị phân ở vị trí được lựa chọn một cách ngẫu nhiên dọc theo nhiễm sắc thể. Quá trình này có thể kết hợp những phẩm chất tốt giữa các chuỗi với nhau. - Hoạt động đột biến: Thỉnh thoảng, các chuỗi có thể thay đổi cấu trúc của mình đột ngột bằng hoạt động đột biến thông qua việc xen kẽ một giá trị tại một vị trí của bit được lựa chọn ngẫu nhiên dọc theo nhiễm sắc thể. Quá trình đột biến có thể nhanh chóng tạo ra những chuỗi có thể không tạo ra từ hoạt động lai ghép. Bởi vì điều này cũng có thể làm hỏng cơ hội của thế hệ tiếp theo, đột biến thường xảy ra với một xác suất nhỏ. Bước 2 và 3 thường cần được lặp trước khi có lời giải tối ưu toàn cục cuối cùng được tìm thấy. GA lặp đi lặp lại quá trình này cho đến khi đạt được điều kiện kết thúc xác định trước. Cuối cùng, giải pháp có thể chấp nhận thu được và được giải mã thành nguyên mẫu ban đầu.  Thuật toán GA giải bài toán STEP Được phát triển dựa trên thuật toán GA được đề xuất bởi Chu và Beasley (GACB) với một số điểm khác biệt như: (1) Sử dụng một hàm thích nghi để xác định giá trị của hàm mục tiêu, và cũng sử dụng một hàm không thích nghi định lượng không khả thi của giải pháp thử nghiệm; (2) Chỉ thay thế một cá thể trong quần thể 24 trong mỗi lần lặp; (3) Thực hiện cải thiện địa phương cho mỗi cá thể được kiểm tra; [11] đề xuất thuật toán giải bài toán STEP (xem Hình 2.3).  (1) Mã hóa: Theo số thập phân (ứng với giải pháp được đề xuất/số lượng các đường dây bổ sung). Với cá thể là một giải pháp được đề xuất cho bài toán quy hoạch hoặc cấu trúc liên kết tạo thành từ tất cả các đường dây bổ sung vào hệ thống tương ứng với một đề nghị đầu tư. Cá thể được đại diện bởi vector kích thước 𝑛𝑙, mỗi phần tử trong vector tương ứng với một đường dây. Giá trị phần tử có thể thay đổi từ 0 tới số lượng đường dây lớn nhất có thể được thêm vào của nhánh tương ứng. Số lượng các cá thể trong quần thể GACB phụ thuộc vào kích cỡ của hệ thống. Lựa chọn dựa trên sự cạnh tranh Tái kết hợp sử dụng điểm đơn Đột biến Y Cải thiện không khả thi N Khởi tạo quần thể ban đầu Không khả thi? Cải thiện hàm mục tiêu Thay thế quần thể Thỏa mãn tiêu chí? Kế hoạch mở rộng tối ưu YN Hình 2.3. Lưu đồ thuật toán di truyền Chu và Beasley (GACB) 25  (2) Khởi tạo quần thể: Thực hiện dựa trên mô hình DC giản lược (2.7), trong đó chỉ xem xét ràng buộc (2.8) - định luật Kirchhoff dòng (KCL).  (3) Hàm mục tiêu và không khả thi: Hàm mục tiêu (thích nghi) là tổng chi phí đường dây được xây dựng, được sử dụng để lựa chọn và thay thế cá thể khi tất cả các phần tử của quần thể là khả thi; không khả thi (không thích nghi) là tổng lượng tải bị cắt bởi một cá thể, được sử dụng để thay thế một cá thể trong quần thể khi có các đề xuất giải pháp không khả thi trong quần thể ban đầu.  (4) Sự lựa chọn: Lựa chọn thế hệ cha mẹ dựa trên sự cạnh tranh. Cá thể có thích nghi tốt nhất sẽ được chọn làm cha mẹ số 1, kế tiếp là cha mẹ thứ 2.  (5) Tái kết hợp: Sử dụng tái kết hợp điểm đơn. Một điểm tái kết hợp được chọn ngẫu nhiên và sinh ra hai con; mỗi con có một đoạn cấu trúc liên kết của mỗi cha mẹ, được phân cách bởi các điểm tái kết hợp; và chỉ một con được chọn ở thế hệ kế tiếp. Thuật toán áp dụng trên các ví dụ mẫu cho kết quả khích lệ: Sơ đồ Graver 6 bus cho kết quả sau 51 phép tính tuyến tính với 30 cá thể trong quần thể ban đầu (trong khi TS từ 600-700 phép tính); trường hợp thực hiện tái cấu trúc máy phát cho kết quả sau 51 phép tính tuyến tính với 30 cá thể trong quần thể ban đầu (trong khi TS từ 400-500 phép tính). Sơ đồ 24 bus IEEE cho kết quả sau 80 phép tính tuyến tính với 50 cá thể trong quần thể ban đầu. 2.2.2.3. Thuật toán tối ưu hóa bầy đàn PSO  Giới thiệu chung về thuật toán PSO Được phát triển trong những năm 1990 bởi James Kennedy và Russell Eberhart, tương tự như GA, PSO khởi tạo một quần thể các giải pháp ngẫu nhiên (gọi là vị trí hạt trong PSO), nhưng khác với GA, mỗi giải pháp tiềm năng được gán một vận tốc ngẫu nhiên, và không cần mã hóa cho mỗi giải pháp. Mỗi hạt bị ảnh hưởng bởi ba yếu tố: tốc độ riêng, vị trí tốt nhất nó đạt được (gọi là 𝑝𝑏𝑒𝑠𝑡) và vị trí tổng thể tốt nhất đạt được bởi tất cả các hạt (gọi là 𝑔𝑏𝑒𝑠𝑡). Thuật toán PSO gồm các bước cơ bản sau:  (1) Khởi tạo một quần thể của các hạt với các vị trí ngẫu nhiên và vận tốc tại 𝑚 chiều trong không gian bài toán. 26  (2) Ước tính hàm thích nghi tối ưu hóa mong muốn trong các biến 𝑚 cho mỗi hạt.  (3) So sánh sự ước tính thích nghi của hạt với 𝑝𝑏𝑒𝑠𝑡 của hạt. Nếu giá trị hiện tại tốt hơn 𝑝𝑏𝑒𝑠𝑡, thì thiết lập giá trị 𝑝𝑏𝑒𝑠𝑡 bằng với giá trị hiện tại và vị trí 𝑝𝑏𝑒𝑠𝑡 bằng với vị trí trong không gian 𝑚 chiều.  (4) So sánh sự ước tính thích nghi của hạt với tổng thể quần thể tốt nhất trước đó. Nếu giá trị hiện tại tốt hơn 𝑔𝑏𝑒𝑠𝑡, thì thiết lập lại giá trị 𝑔𝑏𝑒𝑠𝑡 bằng với giá trị hiện tại, và vị trí 𝑔𝑏𝑒𝑠𝑡 bằng với vị trí hiện tại.  (5) Thay đổi vận tốc và vị trí của hạt theo phương trình (2.39) và (2.40) 𝑣𝑖𝑑 𝑘+1 = 𝑤𝑣𝑖𝑑 𝑘 + 𝑐1𝑟1(𝑝𝑖𝑑 − 𝑥𝑖𝑑 𝑘 ) + 𝑐2𝑟2 (𝑝𝑔𝑑 − 𝑥𝑖𝑑 𝑘 ) (2.39) 𝑥𝑖𝑑 𝑘+1 = 𝑥𝑖𝑑 𝑘 + 𝑣𝑖𝑑 𝑘+1, 𝑖 = 1,2, . , 𝑛, 𝑑 = 1,2, 𝑚 (2.40) Trong đó 𝑤 là hàm trọng lượng; 𝑐1, 𝑐2 hệ số trọng lượng; 𝑟1, 𝑟2 số ngẫu nhiên giữa 0 và 1; các chỉ số viết trên cao là thế hệ lặp; 𝑛 quy mô quần thể; 𝑚 chiều của hạt; 𝑣𝑖𝑑 và 𝑥𝑖𝑑 vận tốc và vị trí của hạt thứ 𝑖 trên chỉ số chiều 𝑑; 𝑝 𝑖𝑑 và 𝑝 𝑔𝑑 là vị trí 𝑝𝑏𝑒𝑠𝑡 và 𝑔𝑏𝑒𝑠𝑡 trên chỉ số chiều 𝑑. Biến 𝑥𝑖 tương đương với mạch thêm vào trên nhánh thứ 𝑖 trong TEP.  (6) Vòng lặp tới bước (2) cho đến khi đạt tiêu chí.  Thuật toán DPSO giải bài toán STEP Các thông số của bài toán TEP là kiểu rời rạc, trong khi việc thực hiện PSO được dựa trên số thực, như vậy PSO không thể sử dụng trực tiếp để giải STEP. Có hai phương pháp để giải bài toán STEP dựa trên kỹ thuật PSO: (1) tối ưu hóa bầy đàn nhị phân (BPSO) và (2) tối ưu hóa bầy đàn rời rạc (DPSO). Phương pháp (2) được sử dụng để tránh những khó khăn trong giai đoạn mã hóa và giải mã bài toán, tăng tốc độ hội tụ và đơn giản hóa. Được đề xuất tại [12], lưu đồ thuật toán DPSO xem xét lưới với nguyên tắc kiểm tra an ninh N – 1 (xem Hình 2.4). 27 Trong đó vị trí của hạt được đại diện bởi ba mảng: Số thanh cái bắt đầu, số thanh cái kết thúc và số mạch trong nhánh. Trong quá trình lặp, chỉ thay đổi số đường dây trong nhánh với giá trị từ 0 tới giới hạn trên mạch thêm vào nhánh. Vị trí hạt có thể được biểu diễn: (𝑥1, 𝑥2, , 𝑥𝑖 , 𝑥𝑚) với 𝑥𝑖 là số mạch trong nhánh 𝑖, 𝑚 là số nhánh có thể thêm đường dây. Tốc độ của hạt được đại diện bởi sự thay đổi của mạch trong mỗi nhánh: (𝑣1, 𝑣2, , 𝑣𝑖 , 𝑣𝑚), trong đó 𝑣𝑚𝑖𝑛 ≤ 𝑣𝑖 ≤ 𝑣𝑚𝑎𝑥. Với 𝐹1 là lưới kết nối gồm ba phần: Chi phí đường dây mới, chi phí tổn thất lưới, chi phí phạt do quá tải với 𝑈 là hệ số phạt. Khi lưới không kết nối, 𝐹2 bằng giá trị rất lớn 𝑊 là hàm phạt. Cài đặt thông số tính toán Khởi tạo vị trí và tốc độ hạt Tính phân bố công suất Tính giá trị thích nghi theo (2.37) Dữ liệu đầu vào lưới Cập nhật gbest và pbest Kết quả hội tụ Kết quả đầu ra Y N Cập nhật vị trí và tốc độ hạt theo (2.35)&(2.36) Hình 2.4. Lưu đồ tính toán DPSO cho lưới kiểm tra an ninh N – 1 Vị trí và vận tốc của hạt được cập nhật trong mỗi lần lặp theo (2.39) và (2.40); hàm thích nghi DPSO được tính toán dựa trên mô hình DC: 28 {𝐹1 = ∑ 𝐶𝑖𝑥𝑖 + 𝑚 𝑖=1 𝐵(∑ 𝑒𝑖𝐼𝑖 2𝑟𝑖𝑡 𝑚0 𝑖 +∑ (𝑥𝑖 + 𝑒𝑖)𝐼𝑖 2𝑟𝑖𝑡 𝑚 𝑖 ) + 𝑈∑ max ((|𝑝| − 𝑝𝑖 𝑚𝑎𝑥), 0)𝑚+𝑚 0 𝑖=1 𝐹2 = 𝑊 (2.41) Trong đó 𝐶𝑖 là chi phí của một mạch mà có thể bổ sung vào nhánh i, 𝑥𝑖 là số mạch thêm vào nhánh i, B là chi phí tổn thất cho 1kWh, 𝑒𝑖 là số mạch hiện thời trong lưới, 𝐼𝑖 là dòng điện trong mạch i, 𝑟𝑖 là điện trở của mạch i, 𝑚 là nhánh cho phép thêm đường dây, 𝑚0 là nhánh không cho phép thêm đường dây, 𝑝𝑖 𝑚𝑎𝑥 là công suất hữu công cực đại trên mạch i. Bằng gải thuật đề xuất, kết quả đạt được rất khả quan. Với sơ đồ 6 bus, kích cỡ quần thể 100 thời gian tính toán từ 6-7 giây và nhanh hơn giải thuật GA (9-11 giây); với sơ đồ 16 bus, kích cỡ quần thể 300 thời gian tính toán từ 57-92 giây và nhanh hơn giải thuật GA (64-101 giây). Cũng sử dụng thuật toán DPSO, xuất phát từ quan điểm chi phí đầu tư mở rộng tỷ lệ thuận với năng lực tải của đường dây, xem xét bài toán STEP dưới góc độ tối ưu hóa về cả tính kinh tế và kỹ thuật, [13] đề xuất hàm thích nghi 𝑇𝑜𝑣𝑒𝑟𝑙𝑜𝑎𝑑 là thời gian quá tải đường dây sau mở rộng lưới 𝐹𝑖𝑡𝑛𝑒𝑠𝑠 = 𝑇𝑜𝑣𝑒𝑟𝑙𝑜𝑎𝑑 . Thời gian này phụ thuộc vào chi phí đầu tư, chi phí càng lớn thì thời gian càng dài. Đây là thông tin hữu ích giúp nhà quy hoạch chọn phương án tối ưu trong quy hoạch lưới điện truyền tải. 2.2.2.4. Kết hợp CHA và PSO giải bài toán STEP Được đề xuất tại [14], gồm có hai giai đoạn. Giai đoạn 1 sử dụng thuật toán CHA nhằm giảm tập các ứng viên từ đó dẫn tới giảm không gian tìm kiếm; Giai đoạn 2, thuật toán PSO sử dụng tập các ứng viên được chọn từ giai đoạn 1 và các giải pháp cuối từ CHA để gia tăng hiệu quả của quá trình tìm kiếm.  Thuật toán CHA Sử dụng mô hình phân bố công suất DC (2.7), với các mạch ứng viên 𝑛𝑖𝑗 được đại diện bởi thông số mở rộng 𝐸𝑃𝑘 ∈ {0,1}. Với giá trị 0 nghĩa là mạch ứng viên không cần xây dựng, giá trị 1 là cần xây dựng; thuật toán CHA được chia thành hai giai đoạn (xem Hình 2.5): 29  (1) Giai đoạn liên tục: Nhằm đạt được các giá trị liên tục cho tất cả các mạch ứng viên (0 < 𝐸𝑃 < 1), sau đó phân bố luồng công suất hữu công cho các mạch ứng viên. Với các giá trị đã biết, bước tiếp theo là xác định mạch ứng viên nào cần phải được xây dựng. Mạch ứng viên cần phải xây dựng phải truyền tải được lượng công suất hữu công tuyệt đối lớn nhất, tính theo công thức 𝑓𝑖𝑗 = 𝐸𝑃𝑖𝑗𝛾𝑖𝑗𝜃𝑖𝑗. Khi đã biết mạch ứng viên cần phải xây dựng, chuyển sang giai đoạ