„Optymalizacja metodami ciemnoszarej skrzynki – rozwój nowej klasy wysoce skutecznych optymalizatorów ogólnego przeznaczenia” – to projekt prof. Michała Przewoźniczka z naszego wydziału, na który otrzymał ponad milion zł grantu z Narodowego Centrum Nauki.

Dr hab. inż. Michał Przewoźniczek, prof. uczelni pracuje w Katedrze Systemów i Sieci Komputerowych. Zajmuje się m.in. obliczeniami ewolucyjnymi (ang. Evolutionary Computation, EC), które dostarczają narzędzi do optymalizacji w różnych dziedzinach nauki i techniki. NCN doceniło projekt naukowca WIT pt. „Optymalizacja metodami ciemnoszarej skrzynki – rozwój nowej klasy wysoce skutecznych optymalizatorów ogólnego przeznaczenia”, zgłoszony do konkursu w ramach 23. edycji programu Opus, i przyznało 1 362 600 zł na jego realizację.

– Optymalizacja to jedna z podstaw naszej cywilizacji, z czego rzadko zdajemy sobie sprawę. Ma zastosowanie absolutnie wszędzie. Celem naukowym projektu jest zaproponowanie nowych optymalizatorów i operatorów wykorzystujących koncepcję optymalizacji metodami ciemnoszarej skrzynki (dark-gray-box). Najnowsze badania pokazują, że w dziedzinie obliczeń ewolucyjnych takie metody mają potencjał zapewnienia wyników o jakości znacznie wyższej niż optymalizatory obecnie uznawane za aktualne – mówi prof. Michał Przewoźniczek.

Metody ciemnoszarej skrzynki wywodzą się z tzw. algorytmów genetycznych (ang. Genetic Algorithms, GA), które są podgrupą algorytmów ewolucyjnych. Można je wykorzystywać do rozwiązywania trudnych problemów obliczeniowych, z którymi klasyczne algorytmy sobie nie radziły.

– Problemy tego typu są powszechne i można je spotkać w niemal każdej dziedzinie nauki, techniki, czy innych obszarach otaczającego nas świata. Przykładów jest mnóstwo, choćby ułożenie planu produkcji w fabryce, wyznaczenie jak najlepszej trasy dla kuriera, zaprojektowanie kształtu anteny, zaprojektowanie składników leków, wygenerowanie programów sterujących autonomicznymi robotami, ale również odpowiednia aranżacja pomieszczeń, opracowanie wydajnej siatki komunikacji miejskiej, czy lepsze wykorzystanie zasobów naturalnych w celu jednoczesnej poprawy jakości życia i zapobieganiu dewastacji środowiska naturalnego – wylicza naukowiec.

Biała i czarna skrzynka

Czym jest ciemnoszara skrzynka? Zacznijmy od tego, że aby cokolwiek optymalizować, trzeba zakodować rozwiązanie. Dwa główne typy to: optymalizacja białej skrzynki (white-box optimization) i czarnej skrzynki (black-box optimization). Metody białej skrzynki wymagają dokładnej znajomości funkcji, którą optymalizujemy, wiemy, jakie są jej własności i możemy policzyć np. jej pochodną. Metody czarnej skrzynki są stosowane, gdy umiemy ocenić rozwiązanie, ale nie znamy dokładnie zależności między zmiennymi problemu, nie wiemy, jak zachowuje się optymalizowana funkcja bo np. jest zbyt skomplikowana, lub policzenie jej pochodnej jest niemożliwe. Optymalizacja prowadzona tymi metodami ma jednak istotne ograniczenia. Około 10 lat temu Darrell Whitley (obecnie jeden wiodących naukowców w dziedzinie optymalizacji ewolucyjnej) zaproponował optymalizację metodą szarej skrzynki. Stosujemy ją wtedy, kiedy o problemie wiemy tylko jedną rzecz – które zmienne są od siebie zależne, a które nie.

– Wykorzystując wiedzę o zależnościach między zmiennymi, naukowcy zajmujący się metodami gray-box zaproponowali szereg różnych sposobów, jak optymalizować dużo bardziej świadomie niż w klasycznej optymalizacji czarnej skrzynki – wyjaśnia prof. Michał Przewoźniczek. – Algorytmy szarej skrzynki są ogólnego przeznaczenia, można je stosować do dowolnego problemu, pod warunkiem, że znamy zależności między zmiennymi. Niestety jest wiele problemów, dla których człowiek nie potrafi określić, które zmienne są od siebie zależne, a które nie – dla nich zostają tylko algorytmy czarnej skrzynki.

Ani biała, ani czarna, tylko… ciemnoszara

Część badaczy postanowiła zastosować różnego rodzaju analizę statystyczną do wykrycia zależności między zmiennymi, co stanowiło przełom w dziedzinie obliczeń ewolucyjnych. Jednak, jak zauważa badacz z naszego wydziału, metody te także mają istotną wadę.

– Statystyka nie daje pewności, że zmienne są faktycznie zależne (lub nie). Zawsze można się mylić. Sytuacja zmieniła się w 2020 roku. Wtedy razem z Marcinem Komarnickim zaproponowaliśmy tzw. Empiryczne Wykrywanie Powiązań (Empirical Linkage Learning, ELL) – mówi prof. Michał Przewoźniczek. – ELL pozwala na wykrycie zależności w optymalizacji typu czarna skrzynka i do tego daje pewność, że wykryte zależności naprawdę istnieją. Zatem dla problemów, dla których nie znamy zależności między zmiennymi (a więc nie możemy stosować szarej skrzynki), wykrywamy te zależności za pomocą ELL. Dzięki temu możemy stosować bardzo skuteczne techniki szarej skrzynki w optymalizacji czarnej skrzynki! Kolor pomiędzy szarym a czarnym to ciemnoszary – stąd nazwa dla tej grupy metod.

Dwie prace, które dr hab. inż. Michał Przewoźniczek i Marcin Komarnicki opublikowali na ten temat  w zeszłym roku, spotkały się z bardzo dobrym przyjęciem (w tym nominacją do nagrody Best Paper na najlepszej konferencji dziedzinowej). Te prace to:

• R. Tinos, M. W. Przewozniczek, D. Whitley, Iterated Local Search with Perturbation based on Variables Interaction for Pseudo-Boolean Optimization, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22), pp. 296–304, ACM, 2022.
• M. W. Przewozniczek, R. Tinos, B. Frej, M. M. Komarnicki, On turning Black- into Dark Gray-optimization with the Direct Empirical Linkage Discovery and Partition Crossover, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '22), pp. 269–277 ACM, 2022.

W projekcie „Optymalizacja metodami ciemnoszarej skrzynki – rozwój nowej klasy wysoce skutecznych optymalizatorów ogólnego przeznaczenia” badacze z naszego wydziału proponują rozwój zupełnie nowej klasy optymalizatorów ewolucyjnych odwołujących się właśnie do idei tzw. ciemnoszarej skrzynki. Jak wyjaśniają naukowcy, metody te są w stanie proponować wyniki o znacznie wyższej jakości niż optymalizatory dotychczas uznawane za najskuteczniejsze. Poszukiwania prowadzone w taki sposób są bardzo obiecujące, ponieważ zakładają celowe i świadome działanie polegające na zrozumieniu natury problemu. Optymalizatory oparte o koncepcję black-box czy dark-gray-box można wykorzystać wszędzie, do każdego problemu optymalizacji.