Zastosowanie hybrydowego operatora mutacji w obliczeniach ewolucyjnych

fot. vaxomatic/CC/Flickr

Optymalne planowanie wytwarzania energii elektrycznej w systemach elektroenergetycznych z zastosowaniem obliczeń ewolucyjnych.

Obecnie algorytmy ewolucyjne stanowią już dobrze ugruntowaną technikę obliczeniową, która wykorzystywana jest powszechnie na potrzeby rozwiązywania różnego typu zagadnień optymalizacyjnych [1]. Dużą zaletą algorytmów ewolucyjnych jest fakt, że są one metodą obliczeniową wymagającą minimum wiedzy o rozwiązywanym zagadnieniu [2]. Bowiem w celu zastosowania algorytmu ewolucyjnego należy tylko zdefiniować sposób kodowania rozwiązań na materiale genetycznym osobników oraz określić postać funkcji dopasowania, która pozwala rozstrzygnąć, które z dwóch różnych rozwiązań reprezentowanych przez odmienne osobniki jest lepsze [3, 4].

Niestety, w praktyce okazuje się, że zdefiniowanie odpowiedniego sposobu kodowania rozwiązań oraz określenie postaci funkcji dopasowania nie jest bynajmniej zadaniem łatwym, o czy świadczą między innymi prace [5–14].

Jeżeli chodzi o różne sposoby kodowania rozwiązań, to najstarszym ze znanych jest kodowanie binarne, w przypadku którego każdy z genów ewoluującego osobnika może przyjąć tylko jedną z dwóch dopuszczalnych wartości, czyli zero lub jeden [1–4].

Jednak na pewnym etapie badań nad algorytmami ewolucyjnymi zdano sobie sprawę, że w wielu przypadkach jest znacznie korzystniej, gdy na potrzeby kodowania wykorzystane zostaną liczby całkowite. W takim przypadku każdy z genów osobnika jest liczbą całkowitą zawartą w pewnym przedziale od N₁ do N₂.

Z kolei w przypadku niektórych zagadnień optymalizacyjnych można zastosować kodowanie oparte bezpośrednio na wykorzystaniu liczb rzeczywistych, które oczywiście w komputerze reprezentowane są przez najbliższe im co do wartości liczby wymierne, co wiąże się ze skończoną dokładnością reprezentacji liczb w maszynach cyfrowych. W takim przypadku każdy z genów osobnika jest w istocie liczbą wymierną zawartą w pewnym przedziale od W₁ do W₂.

Ponadto okazuje się, że istnieją także złożone zagadnienia optymalizacyjne, w przypadku których korzystnie byłoby zastosować hybrydowy system kodowania rozwiązań na materiale genetycznym osobników. W takim wypadku dla części genów mogłoby zostać na przykład zastosowane kodowanie binarne, a z kolei dla pozostałej części genów wykorzystane byłoby kodowanie oparte albo na liczbach całkowitych, albo na liczbach rzeczywistych.

Przykładem tego rodzaju zagadnienia, w przypadku którego można byłoby zastosować jednocześnie trzy różne sposoby kodowania rozwiązań na materiale genetycznym osobników, jest zagadnienie optymalnego planowania wytwarzania energii elektrycznej w systemach elektroenergetycznych.

Zagadnienie optymalizacji produkcji energii elektrycznej 

Każdy system elektroenergetyczny stanowi bardzo złożony układ, w skład którego wchodzą różnego typu urządzenia wytwarzające energie elektryczną, elektroenergetyczne linie przesyłowe, stacje transformatorowo-rozdzielcze oraz urządzenia odbiorcze [15].

Każdy system elektroenergetyczny musi przez cały czas znajdować się w stanie równowagi, tzn. w każdej chwili suma mocy generowanych w urządzeniach wytwórczych musi być równa sumie mocy pobieranych przez urządzenia odbiorcze i sumie mocy strat przesyłowych [16]. Ponadto w każdym systemie elektroenergetycznym suma mocy zapotrzebowanej przez odbiorców zmienia się nieustannie w trakcie każdej doby, przy czym można wyróżnić dwa charakterystyczne okresy, nazwane odpowiednio wieczornym szczytem zapotrzebowania oraz nocną doliną obciążenia [17]. Przykładowe dobowe zmiany zapotrzebowania na moc elektryczną przedstawiono na rys. 1.

Rys. 1. Wykres zapotrzebowania na moc elektryczną w okresie 24 godzin

Na osi odciętych wykresu przedstawionego na rys. 1 zamieszczono kolejne godziny doby, natomiast na osi rzędnych zamieszczono poziom sumarycznego zapotrzebowania na moc w systemie elektroenergetycznym wyrażoną w megawatach.

Z zamieszczonych powyżej rozważań wynika, że urządzenia wytwarzające energię elektryczną muszą ciągle nadążać z poziomem generowanej przez siebie mocy za zmieniającym się nieustannie zapotrzebowaniem na moc zgłaszanym ze strony odbiorców. Ponadto ilość paliwa spalonego w jednostce czasu w danym bloku energetycznym zależy w sposób nieliniowy od mocy tego bloku. W efekcie prowadzi to do złożonego problemu optymalizacyjnego, polegającego na tym, w jaki sposób należy rozłożyć zapotrzebowanie na moc pomiędzy poszczególne bloki energetyczne, aby całkowita masa paliwa spalonego we wszystkich blokach energetycznych w ciągu doby była możliwie jak najmniejsza [17].

Dodatkowo należy także uwzględnić fakt występowania w systemach elektroenergetycznych elektrowni wodnych, w przypadku których energia elektryczna uzyskiwana jest w zasadzie za darmo, dzięki wykorzystaniu energii potencjalnej mas wodnych.

W takim wypadku rozważane zagadnienie optymalizacyjne zostaje dodatkowo skomplikowane o problem, w jakim okresie czasu należy uruchomić turbiny wodne, aby prowadziło to do minimalizacji łącznej ilości paliwa spalonego we wszystkich blokach energetycznych [16].

Ponadto należy pamiętać o konieczności spełnienia licznych ograniczeń nałożonych na poszukiwane rozwiązanie. Mianowicie, oprócz konieczności zbilansowania całego systemu elektroenergetycznego pod kątem generowanej w nim sumarycznej mocy, należy zapewnić jeszcze, aby moce poszczególnych bloków mieściły się w zakresach mocy dla nich dopuszczalnych, tzn. aby dla i-tego bloku generowana w nim moc nie była mniejsza niż dopuszczalna wartość mocy minimalnej P_MIN i większa niż dopuszczalna wartość mocy maksymalnej P_MAX.

Dodatkowo pamiętać należy o tym, aby zbiorniki elektrowni wodnych były zbilansowane w cyklu dobowym, tzn. aby w przeciągu zadanej doby na łopatki turbin wodnych nie została wypuszczona większa ilość wody, niż napływa z rzeki do zbiornika wodnego, na którym wybudowana jest zapora wodna wraz z zainstalowanymi na niej urządzeniami energetycznymi.

Wszystkie wymienione czynniki powodują, że zagadnienie planowania produkcji energii elektrycznej pod kątem minimalizacji sumarycznej masy paliwa spalonego w ciągu doby we wszystkich blokach elektroenergetycznych jest bardzo złożonym problemem optymalizacyjnym, w przypadku którego nie są znane żadne wzory analityczne pozwalające na wyliczenie poszukiwanego rozwiązania.

Taki stan rzeczy uzasadnia w pełni użycie inspirowanych biologicznie metod poszukiwań, takich jak na przykład wzorowane na darwinowskiej teorii doboru naturalnego algorytmy ewolucyjne.

Hybrydowy system kodowania rozwiązań 

Niech dany będzie system elektroenergetyczny, w którym istnieje K bloków energetycznych. Znając prognozę zapotrzebowania na moc w systemie elektroenergetycznym na najbliższą dobę, można podjąć stosowną decyzję odnośnie tego, które z K bloków energetycznych będą przez najbliższą dobę pracować, a które będą odstawione z ruchu. Bowiem okazuje się, że w sytuacji stosunkowo niewielkiego zapotrzebowania na moc korzystniej jest nie uruchamiać wszystkich dostępnych bloków energetycznych, tylko bardziej dociążyć pozostałe będące już w ruchu, ponieważ zwykle przyczynia się to do minimalizacji sumarycznej ilości paliwa zużytego w całym systemie elektroenergetycznym. W związku z powyższym w przypadku pierwszych K genów materiału genetycznego osobnika zastosowano kodowanie binarne. Mianowicie z każdym blokiem energetycznym powiązano jeden z K pierwszych genów osobników. Jeżeli dany gen miał wartość jeden, wówczas oznaczało to, że powiązany z nim blok energetyczny pracował będzie przez okres najbliższej doby. W przypadku przeciwnym rozpatrywany blok energetyczny będzie wyłączony z ruchu.

Następnie w przypadku kolejnych genów materiału genetycznego osobnika zastosowane zostało kodowanie oparte na liczbach rzeczywistych. Również w tym przypadku każdy z genów powiązany został z odpowiadającym mu blokiem energetycznym i kodował wartość mocy danego bloku wyrażoną w megawatach.

Ponieważ wartości mocy bloków energetycznych kodowane były oddzielnie dla każdej godziny doby, tego rodzaju genów, w przypadku których zastosowano kodowanie oparte na liczbach rzeczywistych, było 24K.

Dodatkowo założono, że w rozpatrywanym systemie elektroenergetycznym znajduje się jedna elektrownia wodna zbiornikowa, w przypadku której na zaporze zainstalowano M identycznych turbin wodnych. W związku z powyższym materiał genetyczny osobnika musiał zostać uzupełniony o kolejne 24 geny, w przypadku których zastosowano kodowanie oparte na liczbach całkowitych.

Jak łatwo można się domyślić, każdy z rozważanych genów mógł przyjąć jedynie wartości całkowite z przedziału od 0 do M, kodując tym samym liczbę turbin wodnych, które powinny pracować przez daną godzinę doby.

Jak wynika z powyższych rozważań, w przypadku rozpatrywanego w artykule zagadnienia optymalizacji pracy urządzeń wytwórczych systemu elektroenergetycznego w materiale genetycznym osobników zastosowano jednocześnie aż trzy różne systemy kodowania rozwiązań. Sposób budowy materiału genetycznego osobnika został przedstawiony w sposób poglądowy na rys. 2.

Rys. 2. Materiał genetyczny z trzema różnymi sposobami kodowania rozwiązań

Zastosowanie hybrydowego systemu kodowania rozwiązań na materiale genetycznym osobników wymusza jednocześnie zastosowanie hybrydowego operatora mutacji. Działanie tego typu operatora jest różne, w zależności od tego, jaki sposób kodowania został zastosowany w przypadku genu, na którym operator mutacji ma właśnie działać.

Jeżeli w przypadku wylosowanego genu zastosowane zostało klasyczne kodowanie binarne, wówczas działanie hybrydowego operatora mutacji sprowadzało się będzie jedynie do zamiany wartości genu równej jeden na wartość równą zero i na odwrót. Z kolei w przypadku, gdy wartość wylosowanego genu zakodowana została przy użyciu liczb całkowitych, działanie hybrydowego operatora mutacji sprowadzało się będzie do zamiany wartości danego genu na inną wartość całkowitą wygenerowaną w sposób losowy i mieszczącą się w dopuszczalnym zakresie.

Natomiast, gdy wartość wylosowanego genu zakodowana została przy użyciu liczb rzeczywistych sposób działania hybrydowego operatora mutacji jest nieco odmienny. W takim wypadku do wartości wylosowanego genu z jednakowym prawdopodobieństwem dodawana jest lub jest odejmowana pewna niewielka wartość. Na przykład w przypadku rozważanego w artykule kodowania wartości mocy bloków energetycznych wartością taką może być na przykład wartość 0,1 MW, która determinuje jednocześnie dokładność odnajdywanych rozwiązań. Dodatkowo po wykonaniu tego rodzaju mutacji należy jeszcze sprawdzić, czy zakodowana na danym genie wartość mocy bloku energetycznego mieści się w dopuszczalnym przedziale zdeterminowanym wartościami jego mocy minimalnej i maksymalnej. Jeżeli warunek ten jest spełniony, wówczas rezultat wykonanej operacji mutacji jest zatwierdzany. W przypadku przeciwnym wynik przeprowadzenia operacji mutacji jest anulowany, a danemu genowi przypisywana jest ponownie jego uprzednia wartość. Ten rodzaj mutacji można określić mianem mutacji warunkowej, ponieważ wykonywana jest ona jedynie w przypadku spełnienia określonych warunków, gwarantujących, że wartość zakodowanego rozwiązania nigdy nie wyjdzie poza dopuszczalny zakres.

Zakończenie

W artykule zaproponowano zastosowanie hybrydowego sposobu kodowania rozwiązań na materiale genetycznym ewoluujących osobników na potrzeby rozwiązywania złożonych zagadnień optymalizacyjnych. Przyjęcie w algorytmach genetycznych tego rodzaju kodowania pozwala na znaczne usprawnienie procesu kodowania rozwiązań w przypadku optymalizacji złożonych systemów technicznych, takich jak na przykład systemy elektroenergetyczne.

Zaproponowany w artykule hybrydowy sposób kodowania wraz z hybrydowym operatorem mutacji pozwala na jednoczesne wykorzystanie trzech różnych sposobów zakodowania rozwiązania (binarnego, na liczbach całkowitych i na liczbach rzeczywistych), co pozwala na pełną elastyczność algorytmu ewolucyjnego w zależności od charakteru optymalizowanego systemu.

Literatura:

[1] Goldberg D. E.: Algorytmy genetyczne i ich zastosowania, Wydawnictwa Naukowo-Techniczne, Warszawa, 1996.

[2] Rutkowska D., Piliński M., Rutkowski L.: Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, Wydawnictwo Naukowe PWN, Warszawa-Łódź, 1997.

[3] Michalewicz Z.: Algorytmy genetyczne + struktury danych = programy ewolucyjne, Wydawnictwa Naukowo-Techniczne, Warszawa, 2003.

[4] Arabas J.: Wykłady z algorytmów ewolucyjnych, Wydawnictwa Naukowo-Techniczne, Warszawa, 2004.

[5] Gajer M.: Accelerating the rate of evolutionary processes with the use of constant learning, Przegląd Elektrotechniczny, vol. 87, n. 1, 2011, pp. 204–209.

[6] Gajer M.: Implementation of evolutionary algorithms in the discipline of Artificial Chemistry, Przegląd Elektrotechniczny, vol. 87, n. 4, 2011, pp. 198–202.

[7] Gajer M.: The implementation of the evolutionary computations in the domain of electrical circuits theory, Przegląd Elektrotechniczny, vol. 87, n. 6, 2011, pp. 150–153.

[8] Gajer M.: Visualization of particle swarm dynamics with the use of Virtual Reality Modeling Language, Przegląd Elektrotechniczny, vol. 87, n. 11, 2011, pp. 20–24.

[9] Gajer M.: The analysis of impact of learning on the rate of evolution in the case of a multimodal fitness function, Przegląd Elektrotechniczny, vol. 86, n. 2, 2010, pp. 24–29.

[10] Gajer M.: The implementation of the evolutionary algorithm for the analysis of nonlinear electrical circuits, Przegląd Elektrotechniczny, vol. 86, n. 7, 2010, pp. 342–345.

[11] Gajer M.: The optimization of power flow in high-voltage transmission lines with the use of the evolutionary algorithm, Przegląd Elektrotechniczny, vol. 86, n. 8, 2010, pp. 239–244.

[12] Gajer M.: The optimization of load distribution with the use of the evolutionary algorithm, Przegląd Elektrotechniczny, vol. 86, n. 11a, 2010, pp. 265–270.

[13] Gajer M.: Task scheduling in real-time computer systems with the use of an evolutionary computations technique, Przegląd Elektrotechniczny, vol. 86, n. 10, 2010, pp. 293–298.

[14] Gajer M.: Determining the working points of bipolar transistors with the use of the evolutionary strategy, Przegląd Elektrotechniczny, vol. 87, n. 12a, 2011, pp. 124–128.

[15] Kujszczyk S., Brociek S., Flisowski Z., Gryko J., Nazarko J., Zdun Z.: Elektroenergetyczne układy przesyłowe, Wydawnictwa Naukowo-Techniczne, Warszawa, 1997.

[16] Laudyn D., Pawlik M., Strzelczyk F.: Elektrownie, Wydawnictwa Naukowo-Techniczne, Warszawa, 2000.

[17] Marecki J.: Podstawy przemian energetycznych, Wydawnictwa Naukowo-Techniczne, Warszawa, 2000.