Funkcja celu
W funkcji celu odwzorowuje się cele optymalizacji. Obejmuje ona parametry działania grup sygnalizacji, które pochodzą z modelu ruchu i działania oraz dostarcza jako wynik kondycję (= wartość funkcji celu) indywiduum, tzn. skalarną wartość jakości dla jednej alternatywy sterowania.
W ramach projektu badawczego jako cel ustalono minimalizację czasów postoju. Odpowiednio zdefiniowano funkcję celu:

przy czym
Α = waga dla grupy sygnalizacyjnej sg
W = czas postoju przed grupą sygnalizacyjną sg

Poprzez ustalenie wag czasów postoju można uwzględnić polityczne dyrektywy jak np. ze względu na ustalony kierunek koordynacji. Wykorzystuje się dodatkowo ilość zatrzymań, można dobierać wagi w ten sposób, że wartość funkcji celu odzwierciedla zużycie paliwa albo emisji.

Metoda optymalizacji GALOP
BALANCE wykorzystywał dotychczas algorytm Hill-Climbing (HC) jako metodę optymalizacji. W ramach projektu TRAVOLUTION i GALOP stworzono nową metodę optymalizacji, która została zaimplementowana do BALANCE. Wyróżniającą się zaletą genetycznego algorytmu jest możliwość jednoczesnej optymalizacji wszystkich parametrów sterowania.

Kodowanie parametrów sterowania ma wyjątkową ważność dla jakości i funkcjonowania optymalizacji. Pod pojęciem kodowania rozumie się przy algorytmach genetycznych tłumaczenie (w naszym przypadku) planów sygnalizacyjnych na indiwiduum, które algorytm genetyczny jest w stanie przetwarzać. Dla danego zadania istotne dla kodowania są następujące warunki brzegowe:

• Wytyczne pod względem planowania (dozwolone czasy trwania cyklów, dozwolone kolejności faz)
• Obowiązujące warunki (czasy międzyzielone, minimalne czasy zielonego)
• Uwarunkowania lokalnego sterowania akomodacyjnego

Na rysunku 2 przedstawiono warunki brzegowe sterowania luką czasową na podstawie wartości zmierzonej, które w Niemczech jest często spotykane.

Ramowy plan sygnalizacyjny dla lokalnego sterowania luką czasową na podstawie  wartości zmierzonej ustala się poprzez granice T-czasów (T_iA , T_iB).

Dla całej sieci optymalizuje się najpóźniejsze punkty startu przejść faz  T_iB dla wszystkich sygnalizacji świetlnych w obszarze sterowania. Aby zapewnić funkcjonalność lokalnego sterowania, podano dla T_iB interwał [T_iB^min ; T_iB^max], w którym musi się zmieścić  T_iB .

W metodzie optymalizacji GALOP alternatywy sterowania są reprezentowane poprzez tzw. kodowanie w postaci indiwiduów. Jedno indiwiduum ma następującą postać:

Zawiera ono jeden gen φ dla wspólnego czasu trwania cyklu, jak i n tzw. chromosomy dla n punktów węzłów sieci, która ma być optymalizowana. Każdy chromosom składa się z genu σ do ustalenia kolejności faz, z genu ω dla globalnego offsetu, z genu ο dla lokalnego offsetu, jak i z m genów θ dla czasów trwania faz albo punktów startu przejść faz. Każdy gen przyjmuje wartość rzeczywistą pomiędzy 0 i 1.

Z powodu ograniczeń czasów przesunięć i warunków lokalnych sterowań akomodacyjnych, geny dla globalnego i lokalnego offsetu w realizowanej implementacji algorytmu w TRAVOLUTION nie zostały uaktywnione. Stworzono specjalne sekwencyjne kodowanie, którego zasada działania jest opisana w BRAUN i KEMPER (2008) oraz w BRAUN (2008). Ta metoda integruje ponad obowiązującymi warunkami, jak przestrzeganie czasów międzyzielonych, również bezpośrednio warunki lokalnego sterowania, poprzez co powstają tylko ważne indywidua.

Konstrukcja operatorów genetycznego algorytmu i ich parametryzacja mają duży wpływ na jakość procesu optymalizacji. Ze względu na to, że jedno indiwiduum reprezentuje wszystkie węzły, operatory muszą być dopasowane do kodowania. Jeden węzeł w indywiduum jest przedstawiony jako zestaw genów (chromosomów). Przy rekombinacji standardowo wykorzystuje się losowo wybrane, pojedyncze geny chromosomów indiwiduów rodzicielskich do stworzenia indiwiduów potomstwa. Operatora rekombinacji rozszerzono w ten sposób, że przeprowadzi on rekombinację z prawdopodobieństwem p także na wszystkich chromosomach (węzłach). Przy mutacji genów trzeba zwrócić uwagę na to, że mutacja odbywa się w granicach T-czasów. Z tego powodu można ustawić długość kroku mutacji dla każdego genu indywidualnie albo dla całego indiwiduum. W razie potrzeby długość kroku mutacji może się dostosować w sposób adaptacyjny.

W przeciwieństwie do algorytmu genetycznego, który optymalizuje wszystkie parametry jednocześnie, algorytm Hill-Climbing przetwarza parametry sterowania w sposób sekwencyjny. Tak stworzona alternatywa sterowania zależy od wybranej kolejności. Jeżeli tylko dla jednego parametru sterowania nie znajdzie się lepszej alternatywy sterowania, to szukanie przeprowadzone jest w innym kierunku. Przykład dla odmiennego zachowania algorytmu Hill-Climbing i algorytmu ewolucyjnego dla tej samej sieci przy dokładnie tym samym zapotrzebowaniu komunikacyjnym przedstawia rysunek 3.

Algorytm Hill-Climbing rozpoczyna obliczenia planami sygnalizacyjnymi sterowania bazowego, stanowiącymi wynik startowy, który osiągnął już relatywnie dobrą jakość. W przeciwieństwie do HC algorytm ewolucyjny startuje z przypadkową populacją. Najlepsze indiwiduum pierwszej generacji jeszcze nie osiąga takiej jakości (po 175 ocenianych indiwiduach), przy czym algorytm Hill-Climbing po 2 404 ocenianych alternatywach sterowania skończy jednak obliczenia przy wartości jakości 241 742, ze względu na to, że nie znajdzie lepszej alternatywy (zahaczył sie w lokalnym optimum). Ewolucyjny algorytm osiągał już po 2 300 indiwiduach w 18 generacji kondycję o wartości 236 556. Po 80 generacjach i 10 050 ocenianych alternatywach sterowania, GALOP osiągał kondycję o wartości 186 559.

Herwig Wulffius

Przypisy:
¹ TRAVOLUTION jest projektem badawczym wspieranym przez Republikę Bawarską, zakończony powodzeniem w czerwcu 2008 r. Partnerami projektu są: miasto Ingolstadt, Urząd do Spraw Zarządzania Ruchem Drogowym i Geoinformacji, GEVAS software,  Audi AG oddział Ruch Drogowy i Środowisko, Uniwersytet Techniczny w Monachium, Wydział Planowania i Techniki Ruchu Drogowego.
² BALANCE jest oprogramowaniem firmy GEVAS software GmbH, Monachium. BALANCE (BALancing Adaptive Network Control mEthod) pierwotnie wynaleziono na TU Monachium (FRIEDRICH, 1999) w ramach unijnych projektów badawczych Munich Comfort i TABASCO. W roku 2002 firma  GEVAS software GmbH przejmowała dalszy rozwój BALANCE i wprowadziła produkt do zastosowań w praktyce.

Tweet