Podręcznik

Po co nam optymalizacja?

Wyobraźmy sobie codzienne sytuacje: chcemy dojechać do pracy jak najszybciej, wybrać najtańszy lot na wakacje czy zaprojektować konstrukcję mostu, który wytrzyma największe obciążenia przy jak najniższym koszcie. We wszystkich tych przypadkach chodzi o to samo: znaleźć najlepsze możliwe rozwiązanie, zgodne z przyjętym kryterium.

Tym właśnie zajmuje się optymalizacja. Matematycznie rzecz ujmując, optymalizacja to poszukiwanie minimum lub maksimum funkcji celu przy zadanych ograniczeniach. Funkcja celu to matematyczny opis tego, co chcemy zmaksymalizować (np. zysk) lub zminimalizować (np. koszt). Zmiennymi decyzyjnymi są parametry, które możemy kontrolować, a ograniczenia to zbiór warunków, które rozwiązanie musi spełniać, by było dopuszczalne.

Optymalizacja pojawia się wszędzie tam, gdzie trzeba podejmować decyzje. Trzeba jednak pamiętać, że nie każda decyzja intuicyjnie najlepsza jest naprawdę optymalna w sensie matematycznym — różnica ta staje się istotna w zastosowaniach inżynierskich czy ekonomicznych, gdzie nieoptymalny wybór może skutkować realnymi stratami.

Trudności w optymalizacji

Pierwszą trudnością w wielu problemach optymalizacyjnych jest rozmiar przestrzeni poszukiwań. Gdy liczba zmiennych jest duża, liczba możliwych rozwiązań rośnie wykładniczo, a pełne przeszukiwanie staje się praktycznie niemożliwe. Przykładowo, przy 100 zmiennych binarnych mamy do rozważenia wariantów. Nawet najpotężniejsze komputery nie są w stanie przetworzyć takiej ilości danych w sensownym czasie.

Drugi problem to natura samej funkcji celu. W praktyce funkcje te są często nieliniowe, nieciągłe, a czasem nawet stochastyczne. Może się okazać, że drobna zmiana parametrów powoduje duży i nieprzewidywalny skok wartości funkcji celu. Taka „dzika” topologia przestrzeni rozwiązań utrudnia klasyczne metody optymalizacji bazujące na pochodnych i gradientach.

Trzecią barierą są ograniczenia — formalne lub ukryte. Wiele rzeczywistych problemów zawiera trudne do opisania warunki dopuszczalności: fizyczne, techniczne, prawne, czy związane z bezpieczeństwem. Dodanie ich do modelu optymalizacyjnego komplikuje analizę i znacząco zmniejsza liczbę dopuszczalnych rozwiązań, często do bardzo nieregularnych obszarów.

Ostatni, ale nie mniej ważny problem to lokalne ekstrema. W przypadku funkcji nieliniowych algorytmy mogą „utknąć” w minimum lokalnym — rozwiązaniu, które wygląda na dobre, ale nie jest najlepsze globalnie. Problem ten jest szczególnie dotkliwy w optymalizacji dyskretnej i złożonych problemach inżynierskich, gdzie nie widać łatwej drogi ucieczki z takiego minimum bez globalnej wiedzy o przestrzeni rozwiązań

Przykłady zastosowania optymalizacji

Poniżej przedstawiamy kilka klasycznych przykładów pokazanych na slajdach prezentacji AE1 2020.

Optymalizacja konstrukcji

Transport 1000 m³ chemikaliów ma się odbywać w szczelnych, prostopadłościennych pojemnikach. Każdy pojemnik ma ściany boczne nazywane odpowiednio A i B, oraz dno i górę. Każdy pojemnik można zbudować przy zachowaniu konkretnych warunków: 

• materiał na górę kosztuje 65 PLN za metr kwadratowy
• materiał na boki A kosztuje 35 PLN za metr kwadratowy
• materiał na boki B oraz dno jest dostępny za darmo (pochodzi z odpadów), natomiast jest ograniczenie w jego ilości - możemy wykorzystać nie więcej niż 10 metrów kwadratowych na pojemnik

Transport pojemnika kosztuje 4 PLN, niezależnie od jego wielkości. Celem jest minimalizacja kosztu transportu. To klasyczny przykład zadania liniowego z ograniczeniami — zmienne decyzyjne to wymiary pojemników, a funkcja celu może zależeć np. od kosztów materiałów i liczby pojemników.

$k_j(x_1, x_2, x_3) = km_A \cdot 2(x_2 \cdot x_3) + km_{góra} \cdot (x_1 \cdot x_2) + k_{transport}$

gdzie: 

$\begin{align*}x_3 &\text{ — wysokość pojemnika,} \\x_1 &\text{ — szerokość pojemnika,} \\x_2 &\text{ — głębokość pojemnika,} \\k_{transport}&\text{ — koszt transportu pojedynczego pojemnika}\end{align*}$

Znając wymiary pojemnika możemy też obliczyć ile ich potrzebujemy: 

$z= \frac{V_{całkowita}}{x_1*x_2*x_3}$

No i finalnie dochodzimy do wzoru na koszt całkowity

$f(x_1,x_2,x_3)=z*k_j = \frac{V_{całkowita}}{x_1*x_2*x_3} * (km_A \cdot 2(x_2 \cdot x_3) + km_{góra} \cdot (x_1 \cdot x_2) + k_{transport} )$

Optymalizacja portfela inwestycyjnego

Optymalizacja portfela inwestycyjnego to jeden z klasycznych przykładów zastosowania metod optymalizacyjnych w finansach. Wyobraźmy sobie inwestora, który dysponuje pewnym kapitałem i chce go ulokować w różnych aktywach: np. akcjach dużych stabilnych spółek (tzw. blue chips), sektorze paliwowym, nieruchomościach oraz obligacjach. Każde z tych aktywów cechuje się określoną historyczną stopą zwrotu oraz zmiennością (czyli ryzykiem). Celem inwestora jest znalezienie takiego podziału środków, który zapewni możliwie wysoki zysk przy jednocześnie możliwie niskim ryzyku.

Zmiennymi decyzyjnymi w tym przypadku są procentowe udziały kapitału przeznaczone na każdą z czterech kategorii inwestycji, oznaczmy je odpowiednio jako x₁, x₂, x₃, x₄. Suma tych udziałów musi być równa 1 (czyli 100%), co stanowi podstawowe ograniczenie zadania. Dodatkowo mogą występować ograniczenia dolne i górne, np. minimalny udział w obligacjach albo maksymalny udział w akcjach wysokiego ryzyka.

Funkcja celu w tym problemie ma charakter dwuwymiarowy. Z jednej strony chcemy zmaksymalizować średnią wartość zysku (czyli kombinację średnich stóp zwrotu poszczególnych aktywów ważonych przez x₁ do x₄), a z drugiej strony zminimalizować ryzyko, które najczęściej mierzy się poprzez wariancję lub odchylenie standardowe wartości portfela. 

$V_{j j}=\frac{1}{n} \sum_{k=1}^n\left(r_{j k}-\mu_j\right)^2$

Wariancja całego portfela nie zależy tylko od wariancji poszczególnych aktywów, ale również od ich kowariancji — czyli tego, jak bardzo dane aktywa „poruszają się razem”. Dlatego do zadania wprowadza się macierz kowariancji pomiędzy wszystkimi parami inwestycji. Każda komórka tej macierzy pokazuje wariancję wzajemną: 

$V_{i j}=\frac{1}{n} \sum_{k=1}^n\left(r_{i k}-\mu_i\right)\left(r_{j k}-\mu_j\right)$

Teraz możemy już zapisać ryzyko: 

$\text{Ryzyko} = \mathbf{x}^T \mathbf{V} \mathbf{x}$

Potem powinniśmy jeszcze uwzględnić ograniczenia (zmienne decyzyjne muszą sumować się do jedynki - musimy podzielić całe środki, i jednocześnie nie przekroczyć budżetu). Drugim ograniczeniem będzie zysk - chcemy mieć średni zysk co najmniej 10%: 

$10.65*x_1+11.98*x_2+8,34*x_3+8,64*x_4 \geq10$

Ostatecznie zadaniem można zapisać jako

$min {x^TVx}$

Z ograniczeniami podanymi wyżej, przy dodatkowym założeniu, że żadna ze zmiennych decyzyjnych nie może być mniejsza od zera. 

Formalnie zapisane, zadanie optymalizacji portfela przyjmuje postać problemu kwadratowego z ograniczeniami. Funkcja celu jest funkcją kwadratową (ze względu na macierz kowariancji), a ograniczenia mają postać równań liniowych (suma udziałów równa 1) oraz ewentualnie nierówności (udziały nieujemne, minimalne progi). Dodatkowy warunek na minimalny oczekiwany zysk — np. inwestor deklaruje, że chce mieć co najmniej 10% średniego zwrotu - też jest ograniczeniem liniowym.

Tego rodzaju problemy są idealnym kandydatem dla zastosowania algorytmów ewolucyjnych, zwłaszcza gdy w grę wchodzą nieliniowe zależności, dyskretne zmienne (np. minimalny próg inwestycyjny), nietypowe ograniczenia lub wiele konkurencyjnych celów naraz (np. zysk, ryzyko, płynność). Algorytmy genetyczne pozwalają łatwo modelować takie złożone sytuacje i znaleźć zbiór kompromisowych rozwiązań — tzw. front Pareto — dający inwestorowi wachlarz dobrze zbilansowanych opcji inwestycyjnych.

Alokacja zasobów (środek owadobójczy)

Wyobraźmy sobie plantację w kształcie kwadratu, na której zlokalizowano 12 aktywnych gniazd os. Każde z nich stanowi zagrożenie dla ludzi i upraw, dlatego konieczne jest ich unieszkodliwienie. Do dyspozycji mamy trzy pojemniki ze środkiem owadobójczym, które należy rozmieszczać na tej przestrzeni w taki sposób, by skutecznie zneutralizować jak największą liczbę gniazd.

Zmiennymi decyzyjnymi w tym problemie są współrzędne położenia każdego z trzech pojemników, co oznacza, że mamy do czynienia z problemem optymalizacji w przestrzeni sześciowymiarowej: (x₁, y₁, x₂, y₂, x₃, y₃). Każdy punkt w tej przestrzeni określa możliwe ustawienie pojemników na polu. Ograniczenia wynikają z fizycznych granic plantacji (np. wszystkie współrzędne muszą mieścić się w zakresie od 0 do 100 metrów, jeśli pole ma 100 m długości) oraz z odległości minimalnych między pojemnikami (np. ze względów bezpieczeństwa nie mogą znajdować się zbyt blisko siebie).

Funkcja celu opisuje skuteczność działania rozmieszczenia. Załóżmy, że każdy pojemnik działa w sposób radialny — jego skuteczność maleje z odległością od centrum działania. Możemy przyjąć model, w którym środek owadobójczy działa z pełną skutecznością w promieniu np. 10 m, a dalej jego efektywność spada np. wykładniczo. Dla każdego gniazda obliczamy wtedy skumulowany wpływ wszystkich pojemników i określamy, czy dawka przekracza próg skuteczności. Jeśli tak — gniazdo uznaje się za unieszkodliwione.

W ten sposób funkcja celu przyjmuje postać nieliniową i niegładką: jest to liczba gniazd os, które udało się zneutralizować przy danym ustawieniu pojemników. Funkcja ta może mieć wiele lokalnych maksimów (np. ustawienia pojemników skupiające się na części pola) i dlatego stanowi poważne wyzwanie dla klasycznych metod optymalizacji bazujących na pochodnych.

Dodatkową trudnością jest to, że zmienne są ciągłe, a przestrzeń rozwiązań nie jest prostą siatką — ma nieregularny kształt. Oznacza to, że metody optymalizacji wymagają inteligentnych strategii przeszukiwania, które potrafią unikać minimum lokalnych i są odporne na brak ciągłości lub nieregularność funkcji celu. Algorytmy genetyczne doskonale się w tym sprawdzają — operując populacją rozwiązań i stosując operatory krzyżowania i mutacji, mogą eksplorować różnorodne konfiguracje rozmieszczenia pojemników i z czasem wyłaniać te najbardziej skuteczne.

To przykład zadania nieliniowego z ograniczeniami, gdzie przestrzeń poszukiwań jest ciągła, ale funkcja celu — nieliniowa i trudna do zapisania analitycznie.

Optymalizacja produkcji

Przykład optymalizacji produkcji dotyczy zakładu przemysłowego, który wytwarza dwa rodzaje produktów przy użyciu dwóch różnych procesów technologicznych i dwóch rodzajów surowców: A i B. Zakład musi zaspokoić określone zapotrzebowanie rynkowe (np. 30 jednostek produktu X i 20 jednostek produktu Y), a jednocześnie działa w warunkach ograniczeń zasobów (np. dostępność 60 jednostek surowca A i 90 jednostek surowca B).

Zmiennymi decyzyjnymi są liczby cykli produkcyjnych w procesach I i II, oznaczane jako x₁ i x₂. Każdy cykl zużywa określoną ilość surowców A i B oraz dostarcza określoną liczbę produktów X i Y. Znając macierz współczynników technologicznych (ile surowca zużywa dany proces, ile produktu wytwarza), można sformułować model matematyczny całego systemu produkcyjnego.

Celem jest maksymalizacja zysku — różnicy między przychodem ze sprzedaży produktów a kosztem zużycia surowców. Zakłada się, że produkty X i Y mają znane ceny jednostkowe, a surowce A i B — znane koszty jednostkowe. Funkcja celu to więc wyrażenie liniowe zależne od zmiennych x₁ i x₂. Ograniczenia obejmują:

• dostępność surowców: łączne zużycie A i B w obu procesach nie może przekroczyć ich dostępnych zasobów,

• minimalne zamówienia: produkcja X i Y musi pokrywać popyt,

• nieujemność zmiennych: liczba cykli produkcyjnych nie może być ujemna.

Formalnie jest to typowe zadanie programowania liniowego z ograniczeniami liniowymi. Rozwiązanie można znaleźć metodami klasycznymi (np. Simplex), ale w sytuacjach bardziej złożonych — np. gdy:

• liczba produktów lub procesów wzrasta,

• pojawiają się nieliniowe koszty (np. rabaty przy dużych zamówieniach),

• występują zależności logiczne lub dyskretne zmienne (np. ograniczona liczba maszyn, minimalna seria produkcyjna), warto sięgnąć po algorytmy metaheurystyczne.

Algorytmy genetyczne dobrze radzą sobie w takich warunkach. Dzięki pracy na populacji rozwiązań i mechanizmowi selekcji, krzyżowania oraz mutacji są w stanie znajdować rozwiązania nie tylko poprawne, ale często zaskakująco dobre — zwłaszcza w przestrzeniach rozwiązań, w których metody klasyczne zawodzą lub wymagają znacznego uproszczenia modelu.

Celem jest maksymalizacja zysku. Zmiennymi są liczby cykli produkcyjnych dla obu typów procesów. Ograniczenia obejmują zużycie surowców i wymagania produkcyjne. To typowe zadanie liniowe z ograniczeniami.

Sterowanie napędem prądu stałego (DC)

Sterowanie napędem prądu stałego to klasyczny problem z zakresu automatyki, w którym celem jest tak dobrać parametry regulatora, aby układ reagował szybko, bez przeregulowań i z jak najmniejszym błędem ustalonym. Tu rozpatrujemy przypadek optymalizacji odpowiedzi skokowej układu napędowego z regulatorem typu PID (proporcjonalno-całkująco-różniczkującego).

Zmiennymi decyzyjnymi w tym zadaniu są trzy współczynniki regulatora PID: Kₚ (wzmocnienie proporcjonalne), Tᵢ (czas całkowania) i T_d (czas różniczkowania). To właśnie od ich wartości zależy jakość odpowiedzi układu: czas osiągania wartości zadanej, poziom przeregulowania oraz tłumienie oscylacji.

Aby ocenić jakość działania danego zestawu parametrów, definiujemy funkcję celu, która wyraża kompromis między różnymi wskaźnikami jakości regulacji. Najczęściej stosuje się kombinację:

• całkowego wskaźnika błędu (IAE, ISE lub ITAE),
• czasu regulacji (czas potrzebny do osiągnięcia zadanego poziomu z tolerancją),
• oraz maksymalnego przeregulowania.

W zależności od wag przypisanych poszczególnym składnikom funkcji celu, możemy preferować szybsze dojście do zadanej wartości kosztem większego przeregulowania, lub odwrotnie — stabilność kosztem szybkości.

Symulacja odpowiedzi skokowej dla każdego zestawu parametrów odbywa się numerycznie, najczęściej z użyciem pakietów typu MATLAB/Simulink lub podobnych narzędzi. Funkcja celu ma charakter nieliniowy i czarno-skrzynkowy, co oznacza, że nie jest znana w postaci analitycznej, a jej wartość można jedynie wyznaczyć przez symulację.

To czyni zadanie trudnym dla klasycznych metod optymalizacji gradientowej, ale bardzo dobrze przystosowanym do podejść ewolucyjnych. Algorytmy genetyczne pozwalają swobodnie eksplorować przestrzeń parametrów PID, a ich operatory krzyżowania i mutacji pomagają unikać utkwienia w minimach lokalnych. Dodatkowo, jeśli użyjemy podejścia wielokryterialnego, możemy uzyskać front Pareto przedstawiający kompromisy między czasem regulacji a przeregulowaniem.

Problem sterowania napędem DC ilustruje, jak teoria optymalizacji przekłada się na bardzo praktyczne, inżynierskie zastosowania — od przemysłu po robotykę mobilną i mechatronikę.

Dobór czynników do modelu predykcyjnego cen energii

W dziedzinie analizy szeregów czasowych jednym z ambitniejszych problemów jest przewidywanie przyszłych cen energii na podstawie danych historycznych. Zakładamy, że dysponujemy rozbudowanym zestawem zmiennych wejściowych: historyczne ceny energii, poziomy produkcji energii (np. z wiatru, fotowoltaiki, gazu), wskaźniki inflacyjne, indeksy giełdowe (np. WIG, S&P500), kursy walut (np. EUR/PLN), notowania surowców (ropa, gaz, węgiel), a także dane pogodowe (temperatura, siła wiatru, nasłonecznienie).

Zadanie polega na znalezieniu najlepszego modelu predykcyjnego (np. regresji liniowej, sieci neuronowej, drzewa decyzyjnego), który na podstawie wybranych zmiennych wejściowych pozwoli możliwie najdokładniej przewidzieć cenę energii w przyszłym kroku czasowym. Istotą problemu jest jednak dobór optymalnego podzbioru czynników wejściowych — nie chcemy używać ich wszystkich, ponieważ:

• część może nie wnosić informacji (szum),

• część może być redundantna,

• większy model oznacza większą złożoność i trudność interpretacji.

Zmiennymi decyzyjnymi są tutaj kombinacje czynników wejściowych — problem ma charakter kombinatoryczny, ponieważ dla potencjalnych zmiennych istnieje możliwych podzbiorów. Dla 20 zmiennych to już ponad milion kombinacji. Dodatkowo, możemy rozważać także wybór typu modelu, hiperparametrów, lagów czasowych — co czyni problem jeszcze bardziej złożonym.

Funkcja celu mierzy jakość predykcji — może to być np. średni błąd bezwzględny (MAE), średni błąd kwadratowy (MSE) lub inna miara dopasowania, obliczana na podstawie danych walidacyjnych. Ponieważ funkcja celu nie ma analitycznego wyrazu i zależy od wyników trenowania modelu, mamy do czynienia z czarną skrzynką, którą można ocenić tylko przez symulację lub eksperyment.

Algorytmy genetyczne są doskonale przystosowane do tego typu problemów. Przestrzeń przeszukiwań to zbiory binarne (czy dany czynnik uwzględniamy), a operatory krzyżowania i mutacji pozwalają dynamicznie eksplorować nowe kombinacje. Warianty permutacyjne i wielokryterialne algorytmów pozwalają uwzględniać równocześnie jakość predykcji i prostotę modelu (np. liczbę zmiennych). Dzięki temu można uzyskać front Pareto modeli — od prostych i umiarkowanie skutecznych, po złożone o bardzo wysokiej trafności.

Ten przykład pokazuje, że optymalizacja nie ogranicza się tylko do „fizycznych” problemów inżynierskich, ale odgrywa coraz większą rolę w eksploracji danych, sztucznej inteligencji i nowoczesnej energetyce.

Zanim zaczniemy szukać rozwiązań, warto wiedzieć, czego w ogóle szukamy. W optymalizacji chodzi o znajdowanie najlepszych możliwych rozwiązań dla danego problemu. A w przypadku minimalizacji – po prostu takich, które dają najmniejszą możliwą wartość jakiejś funkcji. To właśnie tę funkcję nazywamy funkcją celu.

Brzmi ogólnie? To dobrze – bo tak naprawdę minimalizować można praktycznie wszystko: czas produkcji, koszt transportu, ryzyko inwestycji, liczbę strat podczas rozładunku, ilość odpadów, czy nawet… liczbę popełnionych błędów przy projektowaniu mostu.

Funkcja celu – czyli co właściwie minimalizujemy?

Funkcja celu to matematyczny sposób na opisanie tego, co chcemy zoptymalizować. Zazwyczaj oznacza się ją jako $f(x)$, gdzie $x$ to zestaw tzw. zmiennych decyzyjnych – czyli tego, na co mamy wpływ.

Przykład? Proszę bardzo – wróćmy do zadania z poprzedniego rozdziału, w którym projektowaliśmy prostopadłościenne zbiorniki do transportu chemikaliów. Celem było zminimalizowanie kosztów transportu, a zmiennymi decyzyjnymi były wymiary pojemników (np. wysokość, szerokość i długość). Funkcja celu mogła więc wyglądać np. tak:

$f(x_1,x_2,x_3)=z*k_j = \frac{V_{całkowita}}{x_1*x_2*x_3} * (km_A \cdot 2(x_2 \cdot x_3) + km_{góra} \cdot (x_1 \cdot x_2) + k_{transport} )$

Szukaliśmy takiego zestawu wymiarów, który pozwala przewieźć zadaną objętość przy jak najmniejszym koszcie.

Ograniczenia – bo nie wszystko nam wolno

W rzeczywistości nie da się „po prostu” minimalizować. Zawsze są jakieś ograniczenia. To one wyznaczają granice naszej wolności w doborze zmiennych decyzyjnych. Ograniczenia pilnują, żeby proponowane rozwiązanie miało sens praktyczny, fizyczny, techniczny, ekonomiczny albo formalny.

Ograniczenia możemy podzielić na kilka rodzajów:

• Twarde (formalne) – muszą być spełnione zawsze. Ich naruszenie oznacza, że rozwiązanie nie ma prawa istnieć. Np.:

  • $x \geq 0$: długości, czasy, liczby jednostek nie mogą być ujemne,

  • $\sum x_i = 1$: suma udziałów w portfelu inwestycyjnym musi wynosić 100%,

  • $T_r \leq 10,\text{s}$: czas regulacji musi być mniejszy niż 10 sekund.

• Miękkie (preferencyjne) – nie są obowiązkowe, ale zalecane. Zwykle wprowadza się je jako dodatkowe funkcje kary. Np.:

  • "unikaj użycia aluminium, jeśli nie jest konieczne",

  • "preferuj rozwiązania o mniejszej liczbie elementów ruchomych".

• Geometryczne / fizyczne – wynikają z fizyki lub geometrii zadania:

  • pojemnik musi się zmieścić w kontenerze,

  • odległość między pojemnikami nie może być mniejsza niż 1 m,

  • długość pręta musi być większa niż 0, ale mniejsza niż 2,5 m.

• Logiczne – np. zakaz inwestowania w firmy z określonego sektora, ograniczenia zgodne z regulaminem czy normą prawną.

W języku matematyki ograniczenia zapisujemy najczęściej jako:

• nierówności: $g(x) \leq 0$,

• równości: $h(x) = 0$.

W przykładzie portfela inwestycyjnego (z rozdziału 1) ograniczenia wyglądały tak:

• $\sum_{i=1}^4 x_i = 1$ – całość kapitału musi być zainwestowana,

• $x_i \geq 0$ – nie można inwestować ujemnych pieniędzy,

• $\sum_{i=1}^4 x_i \mu_i \geq 0.1$ – oczekiwany zysk powyżej 10%.

W przykładzie sterowania napędem, ograniczenia dotyczyły:

• zakresów parametrów regulatora PID (np. $K_r \in [0.1, 2.5]$),

• dopuszczalnych wartości odchyłki regulacji ($e_\infty \leq 0.05$ mm),

• fizycznych ograniczeń wynikających z modelu siłownika.

A w zadaniu rozmieszczenia pojemników z insektycydem mieliśmy np.:

• pozycje pojemników musiały mieścić się na polu uprawnym,

• minimalna odległość między nimi musiała gwarantować efektywne działanie,

• niektóre rejony mogły być wykluczone ze względów bezpieczeństwa.

Dobre zdefiniowanie ograniczeń to często połowa sukcesu – od nich zależy, czy algorytm będzie przeszukiwał rozsądny obszar przestrzeni, czy błądził w miejscach kompletnie nieużytecznych.

Przestrzeń poszukiwań i rozwiązań dopuszczalnych

Zmiennych decyzyjnych zwykle jest kilka lub kilkanaście. Ich wszystkie możliwe kombinacje tworzą tzw. przestrzeń poszukiwań – czyli wszystkie teoretycznie dostępne rozwiązania.

Ale tylko część z nich spełnia wszystkie ograniczenia – i to właśnie ta część nazywa się przestrzenią rozwiązań dopuszczalnych. Przykładowo: możemy mieć 10 miliardów potencjalnych rozwiązań, ale tylko 5 milionów z nich spełnia warunki techniczne, prawne albo biznesowe.

Z punktu widzenia algorytmu optymalizacyjnego najważniejsze pytanie brzmi:

Przykłady z życia – optymalizacja jako chleb powszedni

Spróbujmy wrócić do przykładów z poprzedniego rozdziału:

1. Portfel inwestycyjny – minimalizujemy ryzyko inwestycji (wariancję zysków), ale przy założeniu, że średni zysk musi wynosić co najmniej 10%. Zmiennymi decyzyjnymi są udziały różnych aktywów. Ograniczenia? Łączna suma udziałów = 100%, żaden nie może być ujemny, zysk powyżej 10%.

2. Rozmieszczenie pojemników z insektycydem na polu – minimalizujemy liczbę przeżywających os (czyli maksymalizujemy skuteczność środka). Zmiennymi są współrzędne pojemników, a ograniczenia wynikają z rozmiarów pola, działania środka, bezpiecznych odległości.

3. Sterowanie napędem – minimalizujemy czas reakcji albo przeregulowanie, dbając o to, żeby układ był stabilny. Ograniczenia: dopuszczalne zakresy parametrów regulatora, wymogi na odpowiedź skokową, granice fizyczne układu.

Wszystkie te zadania są przykładami problemów minimalizacji, które pojawiają się w prawdziwej inżynierii, ekonomii i logistyce. A skoro już wiemy, że są – czas dowiedzieć się, jak się za nie zabrać.

Zanim zaczniemy wybierać konkretne algorytmy optymalizacji, musimy się zastanowić: jak wygląda przestrzeń, w której będziemy szukać rozwiązań? To jedno z najważniejszych pytań, jakie należy sobie zadać w kontekście minimalizacji.

Przestrzeń poszukiwań – nie tylko zbiór liczb

W poprzednim rozdziale wprowadziliśmy pojęcie przestrzeni poszukiwań – zbioru wszystkich możliwych konfiguracji zmiennych decyzyjnych. Teraz dodajmy coś istotnego: ten zbiór może mieć bardzo różną strukturę.

Najczęściej spotykamy dwie sytuacje:

• zmienne decyzyjne mogą przyjmować wartości ciągłe – np. długość pręta w metrach: 1.37 m, 2.03 m, 0.88 m, itd.

• lub wartości dyskretne – np. wybór trasy w problemie komiwojażera, rozmieszczenie urządzeń na siatce, przypisanie pracowników do zadań.

Niektóre problemy można też przedstawić jako mieszane – część zmiennych jest ciągła, a część dyskretna. Takie przypadki są typowe np. w inżynierii procesowej.

Przestrzeń ciągła – gładka, ale nie zawsze łatwa

Przestrzeń ciągła to taka, w której zmienne mogą przyjmować dowolne wartości z pewnego przedziału. Matematycznie mówimy wtedy, że $x \in \mathbb{R}^n$.

Zaletą przestrzeni ciągłej jest to, że możemy używać narzędzi analizy matematycznej – np. obliczać pochodne, badać gradienty, korzystać z metod iteracyjnych typu Newtona czy spadku gradientu. Tyle że jest pewien haczyk: takie metody zakładają gładkość funkcji celu (czyli że nie ma skoków, ostrych minimów ani zerwań ciągłości).

Problemy:

• minimum może być lokalne, a nie globalne,

• funkcja może być „płaska” – przez co gradient nic nie mówi,

• ograniczenia mogą tworzyć bardzo wąskie lub nieregularne obszary.

Przestrzeń dyskretna – przeliczalna, ale ogromna

Z kolei przestrzeń dyskretna to taka, w której zmienne mogą przyjmować jedynie określone, policzalne wartości – np. liczby całkowite, ciągi permutacji, konfiguracje binarne.

Przykład:

• Problem komiwojażera: przestrzeń to zbiór wszystkich permutacji miast (czyli $n!$ możliwości).

• Alokacja pracowników do zmian: przestrzeń to zbiór możliwych macierzy przydziału z warunkami logicznymi.

Zaletą przestrzeni dyskretnej jest to, że nie potrzebujemy pochodnych, a każdy punkt jest „jednostką”, którą da się jednoznacznie opisać. Ale przestrzenie dyskretne rosną wykładniczo – tzn. liczba możliwych rozwiązań może szybko przekroczyć zdolność obliczeniową nawet dużych komputerów.

Problemy:

• przeszukiwanie wyczerpujące staje się niemożliwe,

• często nie ma pojęcia "bliskich" rozwiązań – trudno stosować pojęcie lokalnego minimum,

• konieczne są sprytne strategie eksploracji (np. losowe skoki, heurystyki).

Różnice w optyce algorytmów

Wybór algorytmu powinien być dostosowany do rodzaju przestrzeni, bo algorytmy myślą (a raczej "liczą") w zupełnie inny sposób zależnie od tego, czy mają do czynienia z przestrzenią ciągłą czy dyskretną.

W przestrzeni ciągłej algorytmy często opierają się na lokalnej analizie funkcji celu:

• szukają kierunku największego spadku (gradient),

• opierają się na pochodnych, macierzy Hessego lub metodach quasi-Newtona,

• iteracyjnie poprawiają rozwiązanie w stronę minimum,

• zakładają pewną gładkość i regularność przestrzeni.

Typowe algorytmy:

• metoda największego spadku,

• metoda Newtona i quasi-Newtona (BFGS),

• algorytmy ewolucyjne z kodowaniem rzeczywistoliczbowym.

W przestrzeni dyskretnej wszystko wygląda inaczej:

• nie mamy pojęcia o "nachyleniu", bo między punktami nie istnieje pojęcie pochodnej,

• bliskość rozwiązań nie zawsze przekłada się na podobieństwo funkcji celu,

• konieczne są inne strategie eksploracji: permutacje, losowanie, heurystyki lokalne.

Typowe podejścia:

• algorytmy zachłanne i lokalne przeszukiwanie (hill climbing),

• algorytmy metaheurystyczne: symulowane wyżarzanie, algorytmy genetyczne,

• strategie oparte na populacjach i losowym próbkowaniu.

Przykład porównawczy

Załóżmy, że projektujemy most i chcemy:

• w przestrzeni ciągłej: dobrać grubości, długości i przekroje belek,

• w przestrzeni dyskretnej: wybrać z katalogu gotowe komponenty (typu prefabrykaty).

Pierwszy problem daje więcej swobody, ale może prowadzić do rozwiązań nierealnych. Drugi wymaga kompromisów, ale łatwiej go uwzględnić w kosztorysie i harmonogramie.

Zanim rzucimy się w wir algorytmów ewolucyjnych, warto poznać kilka klasycznych podejść do przeszukiwania przestrzeni rozwiązań. Choć czasem uznawane za przestarzałe, wciąż stanowią punkt odniesienia dla każdej bardziej zaawansowanej metody. W tym podrozdziale skupimy się na przestrzeni dyskretnej – czyli takiej, gdzie liczba możliwych rozwiązań jest skończona (choć może być bardzo duża).

Przeszukiwanie pełne (brute force)

Najbardziej oczywista metoda: sprawdź wszystkie możliwe rozwiązania i wybierz najlepsze. Działa idealnie... pod warunkiem, że masz do przeszukania małą przestrzeń. Niestety, w praktyce:

• liczba możliwych rozwiązań rośnie wykładniczo z liczbą zmiennych,
• przy nawet kilku zmiennych dyskretnych zakres możliwości może sięgać miliardów,
• szybko przekraczamy możliwości obliczeniowe dostępnego sprzętu.

Przykład: jeśli mamy 10 zmiennych całkowitych przyjmujących po 10 wartości, to mamy $10^{10} = 10,000,000,000$ rozwiązań.

Zalety:

• gwarantuje znalezienie najlepszego rozwiązania (jeśli istnieje),
• działa niezależnie od natury funkcji celu,
• bardzo prosta implementacja.

Wady:

• totalnie niepraktyczne dla większych problemów,
• nie wykorzystuje żadnej wiedzy o strukturze przestrzeni.

Przeszukiwanie losowe

Zamiast sprawdzać wszystko – losujemy. Algorytm losowy wybiera kolejne rozwiązania zupełnie przypadkowo z przestrzeni dyskretnej i ocenia ich jakość. Jeśli uda się znaleźć dobre – super. Jeśli nie – próbujemy dalej.

Jak to wygląda w praktyce:

• losujemy rozwiązanie $x$,
• obliczamy wartość funkcji celu $f(x)$,
• zapamiętujemy najlepszy wynik dotąd,
• powtarzamy przez ustaloną liczbę iteracji.

Zalety:

• prostota implementacji – dosłownie kilka linijek kodu,
• możliwość działania równoległego (każdy proces może losować osobno),
• działa w każdej przestrzeni dyskretnej (nie wymaga żadnych założeń).

Wady:

• zupełna przypadkowość – możemy długo błądzić zanim trafimy coś sensownego,
• nie wykorzystuje wiedzy z poprzednich prób – "ślepe strzelanie",
• nie gwarantuje znalezienia rozwiązania lepszego od startowego.

Mimo wad, algorytmy losowe bywają zaskakująco skuteczne w przestrzeniach, gdzie lokalne strategie często wpadają w minima lokalne – np. przy wielu zaporowych ograniczeniach.

Przeszukiwanie losowe z pamięcią

Wariant bardziej zaawansowany: próbujemy wykorzystać doświadczenia z poprzednich losowań. Czyli: pamiętamy coś o przeszłości i nie działamy całkiem na oślep. Oto dwie popularne techniki:

Symulowane wyżarzanie (simulated annealing)

Metoda inspirowana procesami fizycznymi – konkretnie wyżarzaniem metali. Algorytm:

• zaczyna od losowego rozwiązania,
• losowo modyfikuje je (tworzy sąsiada),
• jeśli sąsiad jest lepszy – przyjmuje go,
• jeśli jest gorszy – może go przyjąć z pewnym prawdopodobieństwem $p = e^{-\Delta f / T}$,
• temperatura $T$ maleje w czasie – co zmniejsza prawdopodobieństwo akceptowania gorszych rozwiązań.

To podejście pozwala wyjść z minimum lokalnego, ale z czasem staje się coraz bardziej zachowawcze – koncentruje się na najlepszych rozwiązaniach.

Algorytm tabu (tabu search)

Tutaj z kolei prowadzimy rodzaj "czarnej listy" – pamiętamy, gdzie już byliśmy i unikamy powtórek. Algorytm:

• przechodzi od rozwiązania do jego najlepszego sąsiada,
• jeśli sąsiad był niedawno odwiedzony – jest oznaczany jako tabu (czyli zakazany),
• lista tabu działa jak bufor cykliczny (np. ostatnie 100 odwiedzin),
• pozwala to uniknąć cyklicznego krążenia wokół tego samego minimum.

Algorytmy z pamięcią są inteligentniejszą odmianą przeszukiwania losowego – uczą się w czasie, nie pozwalają wracać do kiepskich punktów, próbują eksplorować nowe rejony przestrzeni.

Dyskretyzowane problemy ciągłe

W tym rozdziale skupiliśmy się na problemach dyskretnych, ale czy nie da się tego zastosować dla czasu ciągłego? Pewnie się da ... przecież komputery w naturalny sposób nie są w stanie pamiętać liczb rzeczywistych, ale rozwiązują problemy z nimi związane. Można więc działać tak jak typowy system cyfrowy - zastosować  podejście zwane dyskretyzacją przestrzeni ciągłej.

Jak to działa:

• dzielimy przestrzeń ciągłą na siatkę (np. co 0.1 jednostki),
• traktujemy punkty siatki jako osobne, dyskretne rozwiązania,
• stosujemy klasyczne metody dyskretne (np. losowe przeszukiwanie, tabu search).

Zalety:

• umożliwia stosowanie metod dyskretnych tam, gdzie oryginalnie są zmienne ciągłe,
• pozwala testować algorytmy bez potrzeby obliczania pochodnych.

Wady:

• precyzja zależy od gęstości siatki – im dokładniej, tym więcej punktów do przeszukania,
• może prowadzić do pomijania istotnych cech funkcji celu (np. minimów między węzłami siatki).

W przypadku optymalizacji w przestrzeni ciągłej, jedną z najstarszych i najbardziej klasycznych grup metod są algorytmy gradientowe. Ich zasada działania opiera się na założeniu, że funkcja celu jest gładka – czyli ciągła i różniczkowalna.

Intuicja: jak zejść po schodach w ciemności

Wyobraź sobie, że stoisz na środku zbocza i chcesz zejść na sam dół. Nie widzisz całej doliny – widzisz tylko to, co masz bezpośrednio wokół siebie. Możesz dotknąć ziemi wokół i ocenić, gdzie jest najstromiej w dół – i właśnie w tę stronę zrobisz krok. To właśnie jest gradient: wektor wskazujący kierunek najszybszego spadku wartości funkcji.

Gradient i krok

Jeśli funkcja celu to $f(x)$, a $x \in \mathbb{R}^n$, to gradient to:

$\nabla f(x) = \left[ \frac{\partial f}{\partial x_1}, \ldots, \frac{\partial f}{\partial x_n} \right]$

Podstawowa iteracyjna formuła wygląda następująco:

$x_{k+1} = x_k - \alpha \nabla f(x_k)$

• $x_k$ to punkt aktualny,
• $\alpha$ to współczynnik uczenia (długość kroku),
• $\nabla f(x_k)$ to gradient w punkcie $x_k$.

Metoda największego spadku

To najprostszy algorytm gradientowy. Za każdym razem idziemy w kierunku przeciwnym do gradientu – czyli w stronę, gdzie funkcja maleje najszybciej. W praktyce ważne jest dobranie odpowiedniej wartości $\alpha$, bo:

• zbyt duży krok może przeskoczyć minimum,
• zbyt mały krok prowadzi do powolnej zbieżności.

Metoda Newtona i quasi-Newtona

Metoda Newtona wykorzystuje nie tylko gradient, ale też drugą pochodną – tzw. hesjan (macierz drugich pochodnych cząstkowych):

$H(x) = \left[ \frac{\partial^2 f}{\partial x_i \partial x_j} \right]$

Formuła iteracyjna:

$x_{k+1} = x_k - H^{-1}(x_k) \nabla f(x_k)$

Dlaczego druga pochodna daje nam przewagę? Bo zawiera informację o krzywiźnie funkcji celu. Gradient mówi tylko, w którą stronę funkcja maleje – ale nie mówi, jak szybko. Hesjan dostarcza wiedzy o tym, jak zakrzywiona jest funkcja w danym punkcie. Dzięki temu można:

• lepiej dobrać długość kroku (adaptacyjnie, zamiast na sztywno),
• szybciej zbliżyć się do minimum – zwłaszcza w pobliżu punktu optymalnego,
• unikać efektu "zygzakowania" w przypadku funkcji o bardzo różnych krzywiznach w różnych kierunkach.

Warunki stopu

W algorytmach gradientowych zatrzymujemy się, gdy:

• $\| \nabla f(x_k) \| < \epsilon$ – gradient jest prawie zerowy,
• $\| x_{k+1} - x_k \| < \delta$ – zmiana rozwiązania jest minimalna,
• osiągnięto maksymalną liczbę iteracji.

Ograniczenia i trudności

• Minimum lokalne – mogą "utknąć" w lokalnym minimum, nie docierając do globalnego,
• Brak gładkości – jeśli funkcja celu nie jest różniczkowalna, nie możemy użyć pochodnych,
• Siodła i płaskowyże – gradient może nie prowadzić w dobrą stronę.

Przykłady zastosowań

• Optymalizacja kształtów elementów mechanicznych,
• Minimalizacja strat w sieciach neuronowych (np. SGD w ML),
• Wyznaczanie parametrów modeli analitycznych,
• Problemy portfela inwestycyjnego, gdzie funkcja ryzyka i zwrotu ma formę analityczną.

W kolejnym rozdziale zobaczymy, jak w algorytmach klasycznych i gradientowych można wprowadzać ograniczenia – zarówno twarde (jawne) jak i miękkie (np. kary za przekroczenie dopuszczalnego zakresu).

Uwzględnianie ograniczeń w optymalizacji – kiedy nie wszystko wolno

W większości realistycznych problemów optymalizacyjnych nie możemy swobodnie dobierać zmiennych – jesteśmy ograniczeni przez warunki fizyczne, ekonomiczne, prawne czy techniczne. W tym rozdziale przyjrzymy się, jak klasyczne algorytmy radzą sobie z ograniczeniami. Omówimy metody jawne i niejawne, twarde i miękkie, dokładne i przybliżone.

Rodzaje ograniczeń

Zacznijmy od klasyfikacji. Ograniczenia w problemie optymalizacji można zapisać jako:

• Ograniczenia równościowe: $h_i(x) = 0$
• Ograniczenia nierównościowe: $g_j(x) \leq 0$

Mogą one dotyczyć jednej zmiennej lub całego ich zestawu, np. $x_i \in [a_i, b_i]$.

Z punktu widzenia praktyki dzieli się je na:

• twarde (hard) – muszą być spełnione bez wyjątku,
• miękkie (soft) – można je naruszyć, ale z konsekwencjami (np. kara w funkcji celu).

Dodatkowo, wyróżniamy:

• ograniczenia jawne – znane i zapisane bezpośrednio,
• ograniczenia niejawne – wynikające z ukrytej logiki zadania lub symulacji.

Metoda eliminacji – tylko to, co dopuszczalne

Najprostsza strategia to nie wpuszczać do przestrzeni przeszukiwania żadnego punktu, który nie spełnia ograniczeń. To tzw. metoda eliminacji (feasibility filter).

Jak to działa?

• Generujemy kandydatów (np. losowo lub iteracyjnie),
• Sprawdzamy, czy spełniają wszystkie ograniczenia,
• Jeśli nie – odrzucamy i szukamy dalej.

Zalety:

• prostota,
• 100% pewności, że rozwiązania są dopuszczalne.

Wady:

• może być ekstremalnie nieefektywna, jeśli dopuszczalna przestrzeń jest wąska,
• problematyczna w przestrzeniach ciągłych o trudnych ograniczeniach geometrycznych.

Metoda ta jest powszechna w prostych algorytmach przeszukiwania losowego.

Kara - niedobrze jak opuścisz obszar poszukiwań

Inna popularna strategia to włączenie ograniczeń do funkcji celu w postaci dodatkowej kary (penalty function). To pozwala naruszać ograniczenia, ale z kosztami.

Nowa funkcja celu ma postać:

$f'(x) = f(x) + P(x)$

gdzie $P(x)$ to funkcja kary, np.:

$P(x) = \sum_{i} r_i \cdot \max(0, g_i(x))^2 + \sum_{j} s_j \cdot h_j(x)^2$

Parametry $r_i$ i /(s_j\) to współczynniki kar. Ich dobór jest krytyczny – zbyt małe kary powodują lekceważenie ograniczeń, zbyt duże całkowicie blokują eksplorację.

Zalety:

• łatwa do zastosowania w istniejących algorytmach,
• działa także z funkcjami niegładkimi.

Wady:

• trudność w doborze wag kary,
• ryzyko, że dobre rozwiązania dopuszczalne będą pominięte, jeśli punkt niedopuszczalny ma niską wartość oryginalnej funkcji celu.

Metoda barier – podejście od wewnątrz

Alternatywą dla kar jest metoda barier, szczególnie w przestrzeni ciągłej. Zamiast pozwalać wejść do strefy niedozwolonej, bariera zapobiega zbliżaniu się do granicy dopuszczalności.

Typowa postać funkcji barierowej:

$f'(x) = f(x) + \mu \cdot \sum_j \frac{1}{-g_j(x)}$

Bariera działa tylko dla punktów wewnątrz dopuszczalnego obszaru – im bliżej granicy, tym kara większa. to współczynnik kontrolujący siłę działania bariery.

Zalety:

• zachowujemy się "bezpiecznie", nie przekraczając granic,
• sprzyja optymalizacji wewnątrz trudnych wielowymiarowych obszarów.

Wady:

• nie działa dla równości,
• wymaga funkcji różniczkowalnej i pochodnych,
• może prowadzić do utknięcia daleko od minimum globalnego.

Metody rzutowania – powrót na ścieżkę

Jeśli w kolejnych krokach algorytmu zdarza się, że punkt wyjdzie poza dopuszczalną przestrzeń, możemy go ręcznie przywrócić do niej – poprzez tzw. rzutowanie.

Mamy ograniczenie $x \in [0,1]$. Jeśli nowy punkt $x_k = 1.3$, to zamiast odrzucić, robimy ustawiamy $x_k = 1.0$.

Rzutowanie działa na granicy dopuszczalności i zachowuje sens matematyczny przeszukiwania.

Zalety:

• prosta implementacja,
• pozwala używać standardowych algorytmów nawet w obecności ograniczeń.

Wady:

• może prowadzić do "ślizgania się" po granicy,
• nie uwzględnia geometrii problemu.

Naprawianie (repair) – sprytna korekta

Zamiast odrzucać lub karać – można próbować naprawiać niedopuszczalne rozwiązania. Np. jeśli suma udziałów w portfelu przekracza 100%, można je przeskalować. Jeśli punkt leży poza granicą, można przesunąć go najkrótszą drogą do wnętrza.

Zalety:

• elastyczne i skuteczne w praktyce,
• pozwala korzystać z silnych heurystyk bez komplikowania algorytmu.

Wady:

• często wymaga znajomości problemu i specjalnych procedur,
• może zaburzać rozkład rozwiązań (np. w metodach losowych).

Metody hybrydowe i adaptacyjne

W rzeczywistości często stosuje się kombinacje powyższych metod:

• kara + rzutowanie,
• bariera + naprawianie,
• kara adaptacyjna – która zmienia siłę działania w czasie (np. rośnie w miarę trwania optymalizacji).

Szczególnie algorytmy ewolucyjne często korzystają z adaptacyjnych funkcji kary, które uwzględniają np. liczbę spełnionych ograniczeń w danej populacji.

Uwagi praktyczne

Dobór odpowiedniej strategii postępowania z ograniczeniami w optymalizacji zależy od wielu czynników. Przede wszystkim trzeba wziąć pod uwagę naturę problemu: czy mamy do czynienia z przestrzenią ciągłą, gdzie możemy wykorzystać pochodne i gładkość funkcji celu, czy z przestrzenią dyskretną, gdzie takie założenia nie obowiązują. Problemy ciągłe z ograniczeniami równościowymi wymagają często stosowania metod analitycznych lub przybliżających – na przykład przez przekształcenie równości w funkcje kary kwadratowe. W przypadku ograniczeń nierównościowych dobrze sprawdzają się metody barierowe lub adaptacyjne kary. Z kolei w przestrzeniach dyskretnych bardziej praktyczne okazują się metody naprawcze lub prosta eliminacja rozwiązań niedopuszczalnych.

Ważną rolę odgrywa także geometria przestrzeni rozwiązań – w niektórych problemach dopuszczalny obszar jest nieregularny, pełen dziur i nieciągłości. W takich przypadkach warto rozważyć metody rzutowania lub adaptacyjne przekształcanie przestrzeni przeszukiwania. W praktyce inżynierskiej, zwłaszcza w dziedzinach takich jak projektowanie mechaniczne, inżynieria materiałowa czy chemiczna, dobrze działa połączenie strategii optymalizacji z wiedzą ekspercką. Na przykład zamiast jedynie penalizować naruszenie granic geometrycznych, można wprowadzić sprytne algorytmy naprawcze, które przekształcają rozwiązania w realne i wykonalne, zgodnie z zasadami fizyki czy standardami technicznymi.

Warto też zauważyć, że sposób traktowania ograniczeń może wpływać nie tylko na skuteczność optymalizacji, ale również na jakość znalezionych rozwiązań – zwłaszcza w problemach, gdzie między ograniczeniami a funkcją celu istnieje subtelna zależność. Dlatego wybór metody powinien być dokonywany świadomie, w oparciu o analizę problemu, a nie przez przyzwyczajenie czy wygodę implementacyjną. (np. optymalizacja konstrukcji) warto wspomagać się informacjami z domeny.

Kodowanie genomu w algorytmach genetycznych

Kodowanie genomu to sposób reprezentacji potencjalnych rozwiązań problemu optymalizacyjnego w postaci chromosomów – czyli łańcuchów danych, na których operują algorytmy genetyczne. Wybór odpowiedniego rodzaju kodowania ma kluczowe znaczenie dla efektywności działania algorytmu, ponieważ wpływa na to, jak łatwo można zastosować operatory genetyczne (krzyżowanie, mutację) oraz jak dobrze przestrzeń poszukiwań jest odwzorowywana.

Klasyfikacja metod kodowania

Najczęściej stosowane techniki kodowania genotypu dzielą się na:

Kodowanie klasyczne (wektorowe)

W tym podejściu genotyp reprezentowany jest jako wektor wartości – może być to wektor binarny, liczbowy, całkowity itp. Każdy gen odpowiada za jedną cechę rozwiązania. To najczęściej stosowane podejście, zwłaszcza w problemach optymalizacji ciągłej lub dyskretnej.

Kodowanie permutacyjne

Tutaj chromosom zawiera permutację elementów – typowe zastosowanie to problemy kombinatoryczne, takie jak problem komiwojażera (TSP), harmonogramowanie zadań, kolejki produkcyjne itp. Operatory krzyżowania muszą być specjalnie przystosowane, by nie generowały nieprawidłowych permutacji.

Kodowanie drzewiaste

Stosowane głównie w programowaniu genetycznym. Genotyp ma strukturę drzewa – węzły to funkcje lub operatory, a liście to argumenty lub dane wejściowe. Struktura ta umożliwia reprezentację złożonych wyrażeń matematycznych, reguł lub algorytmów. Przykład: $(x + y) * z$.

Kodowanie grafowe

Zamiast drzew czy wektorów, genotypem może być graf – używane np. w ewolucyjnej optymalizacji sieci (np. topologie połączeń neuronów w neuroewolucji). Pozwala to na reprezentowanie bardziej ogólnych struktur i zależności.

Kodowanie listy instrukcji (linearne kodowanie genów)

Popularne w ewolucyjnych algorytmach programujących. Genotyp zawiera liniową sekwencję poleceń lub instrukcji, podobnych do kodu asemblera. Taka reprezentacja ułatwia mutacje i krzyżowanie na poziomie składni.

Kodowanie symboliczne

Używane w problemach, gdzie rozwiązania mają strukturę symboliczną – np. ewolucja formuł logicznych, automaty, reguły IF-THEN. Genotyp zawiera symbole ze skończonego alfabetu, np. {A, B, C, ¬, ∧, ∨}.

Reprezentacja pojedynczych genów

Poza strukturą całego genotypu, istotne jest to, w jaki sposób kodowane są pojedyncze geny. Najczęściej stosuje się dwa podejścia: reprezentację binarną (w tym kod Graya) oraz reprezentację rzeczywistoliczbową.

Kodowanie binarne

W tym przypadku każda zmienna kodowana jest jako ciąg bitów. Długość ciągu określa precyzję odwzorowania. Na przykład, wartość z przedziału $[a, b]$$ reprezentujemy za pomocą $n$ bitów, co pozwala wyróżnić $2^n$ wartości dyskretnych. Zamiana bitów na wartość rzeczywistą wymaga przeskalowania:

$x = a + \frac{b - a}{2^n - 1} \cdot \text{wartość binarna}$

Zaletą tego podejścia jest prostota operacji krzyżowania i mutacji. Wadą – ograniczona rozdzielczość i nieliniowość odwzorowania, szczególnie w problemach ciągłych.

Kodowanie Graya

Kod Graya to wariant kodowania binarnego, w którym dwie kolejne wartości różnią się tylko jednym bitem. Redukuje to problem „skokowych” zmian wartości przy małych mutacjach. Przydatny zwłaszcza tam, gdzie zmiana jednego bitu nie powinna prowadzić do dużej zmiany w wartości odwzorowanej.

Kodowanie rzeczywistoliczbowe

Zamiast bitów, gen przyjmuje bezpośrednio wartość rzeczywistą z określonego przedziału. Przykład: gen $x_i \in [0, 10]$ może mieć wartość 7.35. Operatory genetyczne muszą być dostosowane do przestrzeni ciągłej – mutacja może np. polegać na dodaniu losowego zakłócenia $\sim N(0, \sigma)$, a krzyżowanie – na liniowej kombinacji rodziców.

Zaletą tego podejścia jest jego naturalność i brak potrzeby dekodowania. Dobrze sprawdza się w optymalizacji ciągłej. Wadą jest większe ryzyko wyjścia poza dopuszczalne zakresy oraz konieczność dostosowania operatorów.

Podsumowanie

Dobór odpowiedniego kodowania zależy od rodzaju rozważanego problemu:

• dla problemów ciągłych preferowane jest kodowanie rzeczywiste,
• dla problemów kombinatorycznych – kodowanie permutacyjne,
• dla problemów strukturalnych – kodowanie drzewiaste, grafowe lub instrukcyjne.

Dodatkowo należy pamiętać, że rodzaj kodowania wpływa na konstrukcję operatorów genetycznych oraz na efektywność przeszukiwania przestrzeni rozwiązań. W praktyce często konieczne jest eksperymentalne dobranie najbardziej efektywnej reprezentacji.

Czym są operatory inicjalizacji?

Operatory inicjalizacji to procedury odpowiedzialne za wygenerowanie pierwszej populacji w algorytmie genetycznym. To, jak zostaną rozłożone początkowe punkty w przestrzeni rozwiązań, może mieć ogromne znaczenie dla skuteczności dalszego poszukiwania. Celem inicjalizacji jest zapewnienie odpowiedniej różnorodności genetycznej, by uniknąć przedwczesnej zbieżności populacji.

Typowe metody inicjalizacji

W literaturze i praktyce algorytmów genetycznych spotyka się kilka głównych podejść:

Inicjacja równomierna (jednorodna)

Inicjalizacja równomierna (jednorodna) to najprostszy i najczęściej stosowany sposób generowania początkowej populacji w algorytmach genetycznych. Polega na tym, że każda zmienna decyzyjna (gen) losowana jest niezależnie z rozkładu jednostajnego w zadanym przedziale dopuszczalnych wartości. Dzięki temu cała przestrzeń poszukiwań jest wstępnie przeszukiwana z równym prawdopodobieństwem, co zapewnia dobrą eksplorację już od pierwszej generacji.

Wzór opisujący losowanie jednego genu $g_i$ z rozkładu jednostajnego wygląda następująco:

$g_i = a_i + (b_i - a_i) \cdot U(0,1)$

• $a_i$ i  $b_i$ to odpowiednio dolna i górna granica przedziału dla genu $g_i$,
• $U(0,1)$ to liczba losowa z rozkładu jednostajnego w przedziale .

Zaletą inicjalizacji równomiernej jest jej prostota i niskie wymagania obliczeniowe. Nie wymaga żadnych dodatkowych parametrów (jak np. średnia i odchylenie standardowe w rozkładzie normalnym), ani wstępnej wiedzy o funkcji celu. Jest idealna do zadań, gdzie brakuje jakiejkolwiek wiedzy wstępnej o położeniu optymalnych rozwiązań.

Wadą tej metody może być jednak zbyt rzadkie pokrycie przestrzeni w wysokich wymiarach — przy dużej liczbie zmiennych liczba możliwych kombinacji rośnie wykładniczo, przez co nawet duże populacje mogą „nie trafić” w istotne obszary.

Rozkład normalny (Gaussa)

Rozkład normalny (Gaussa) to klasyczny rozkład symetryczny, którego kształt opisywany jest przez funkcję dzwonową. Jego parametrami są średnia , wokół której skupiają się wartości, oraz odchylenie standardowe , określające szerokość rozrzutu. Rozkład ten jest szeroko stosowany w algorytmach genetycznych do lokalnej inicjalizacji populacji, szczególnie gdy znane jest przybliżone położenie optimum.

Funkcja gęstości prawdopodobieństwa rozkładu normalnego zapisana w postaci matematycznej wygląda następująco:

Rozkład normalny (Gaussa) to klasyczny rozkład symetryczny, którego kształt opisywany jest przez funkcję dzwonową. Jego parametrami są średnia , wokół której skupiają się wartości, oraz odchylenie standardowe , określające szerokość rozrzutu. Rozkład ten jest szeroko stosowany w algorytmach genetycznych do lokalnej inicjalizacji populacji, szczególnie gdy znane jest przybliżone położenie optimum.

Funkcja gęstości prawdopodobieństwa rozkładu normalnego zapisana w postaci matematycznej wygląda następująco:

$f(x) = \frac{1}{\sigma \sqrt{2\pi}} \exp\left( -\frac{(x - \mu)^2}{2\sigma^2} \right)$

Rozkład normalny pozwala w naturalny sposób regulować intensywność eksploracji poprzez manipulowanie – im większe odchylenie, tym większy zasięg losowanych wartości. Jest często stosowany jako alternatywa dla rozkładu jednostajnego, gdy zależy nam na zbliżeniu się do konkretnych obszarów przestrzeni decyzyjnej.

Kiedy używać rozkładu normalnego do inicjalizacji?

Rozkład normalny (Gaussa) jest szczególnie użyteczny w sytuacjach, gdy chcemy skoncentrować generowane punkty w pobliżu znanego lub przypuszczalnego optimum. Jest to korzystne np. w zadaniach, gdzie:

• przestrzeń poszukiwań jest bardzo duża, a eksploracja całej przestrzeni byłaby nieefektywna,
• dysponujemy wcześniejszą wiedzą o typowym zakresie dobrych rozwiązań,
• potrzebujemy szybko zbliżyć się do dobrego punktu początkowego,
• wymagane jest utrzymanie populacji w ograniczonym zasięgu wokół konkretnego rozwiązania,
• zależy nam na dokładnej eksploracji lokalnej okolicy (eksploatacja zamiast eksploracji).

Stosując rozkład normalny, możemy łatwo regulować „rozrzut” poprzez parametr odchylenia standardowego σ – co czyni ten rozkład bardzo praktycznym narzędziem do lokalnego poszukiwania rozwiązań.

Inne operatory inicjalizacji spotykane w literaturze

Oprócz standardowych metod, w literaturze opisywane są również bardziej zaawansowane operatory inicjalizacji, które zwiększają jakość pokrycia przestrzeni poszukiwań. Przykładem jest Latin Hypercube Sampling (LHS), który zapewnia, że próbki są równomiernie rozmieszczone wzdłuż każdego wymiaru. Dzięki temu unika się sytuacji, w której populacja początkowa przypadkowo pomija duże obszary przestrzeni rozwiązań. LHS znajduje zastosowanie głównie w zadaniach o dużej liczbie zmiennych ciągłych, gdzie losowanie niezależnych wartości z rozkładu jednostajnego mogłoby prowadzić do nadmiernego skupienia próbek.

Rozkład Cauchy’ego zasługuje na osobne omówienie ze względu na jego unikalne właściwości. W przeciwieństwie do rozkładu normalnego, Cauchy charakteryzuje się tzw. grubymi ogonami – co oznacza, że wartości znacznie oddalone od średniej mają wyraźnie większe prawdopodobieństwo wystąpienia. Dzięki temu inicjalizacja z wykorzystaniem rozkładu Cauchy’ego może skutecznie wspierać eksplorację przestrzeni poszukiwań, zwłaszcza w problemach, gdzie dobre rozwiązania mogą występować daleko od środka przestrzeni decyzyjnej. Jest to zatem doskonała opcja w przypadkach, gdy zależy nam na agresywnym przeszukiwaniu całej przestrzeni, a nie tylko jej wycinka.

Drugą rodziną podejść są tzw. sekwencje niskiej dyskrepancji, takie jak Sobola, Haltona czy Faure’a. Są to quasi-losowe ciągi, które rozmieszczają punkty bardziej równomiernie niż czysto losowe próbkowanie. Dzięki temu zapewniają systematyczne i powtarzalne pokrycie przestrzeni, co czyni je przydatnymi np. w testowaniu algorytmów lub optymalizacji deterministycznej. Ich zaletą jest pełna kontrola nad rozkładem punktów oraz możliwość odwzorowania przestrzeni nawet w wysokich wymiarach.

Ciekawą propozycją jest również inicjalizacja warstwowa (layered), która łączy różne podejścia w jednej populacji. Na przykład, część populacji może być losowana z rozkładu jednostajnego dla szerokiej eksploracji, a inna część z rozkładu normalnego wokół znanych dobrych punktów – dla precyzyjnej eksploatacji. Takie połączenie działań eksploracyjnych i eksploatacyjnych już na etapie inicjalizacji pozwala algorytmowi rozpocząć poszukiwania z bardziej zrównoważonym rozkładem potencjalnych rozwiązań.

Nadinicjalizacja

Pojęcie nadinicjalizacji oznacza sytuację, w której generuje się znacznie więcej osobników niż wynosi docelowa liczność populacji – a następnie wybiera z nich najlepsze bądź najbardziej zróżnicowane. Pomaga to w uzyskaniu lepszej jakości początkowej populacji, ale wiąże się z większym kosztem obliczeniowym.

Można też rozumieć „nadinicjalizację” jako próbę kompensacji ubogiej struktury inicjalnej populacji przez sztuczne zwiększenie jej rozrzutu – np. przez silną mutację na etapie inicjalizacji lub przez celowe zwiększenie zakresów poszukiwań.

Podsumowanie

Wybór operatora inicjalizacji nie jest błahy:

• dla eksploracji warto korzystać z rozkładu równomiernego, Cauchy’ego lub LHS,
• dla eksploatacji – z rozkładów skoncentrowanych (np. normalnego, beta, wykładniczego),
• inicjalizacja hybrydowa (np. kilka punktów heurystycznych + losowanie) daje często najlepsze efekty.

Dobrze zaprojektowana inicjalizacja może zdecydować, czy algorytm w ogóle znajdzie sensowne rozwiązania.

Operatory selekcji w algorytmach genetycznych

Selekcja to kluczowy etap algorytmu genetycznego, w którym wybierane są osobniki do reprodukcji – czyli do krzyżowania i/lub mutacji. Celem selekcji jest premiowanie lepiej przystosowanych jednostek, a zarazem zachowanie pewnej różnorodności genetycznej w populacji. Istnieje wiele technik selekcji, z których każda ma inne właściwości pod względem presji selekcyjnej i zbieżności.

Selekcja ruletkowa (proporcjonalna)

Selekcja ruletkowa (ang. "roulette wheel selection") jest jedną z najprostszych i najbardziej intuicyjnych metod. Każdemu osobnikowi przypisywany jest wycinek koła proporcjonalny do jego wartości funkcji przystosowania (fitness). Im lepszy osobnik, tym większe ma szanse na wybór. Wyobrażamy to sobie jak koło fortuny, w którym sektory odpowiadają poszczególnym osobnikom – im większy sektor, tym większe prawdopodobieństwo trafienia.

Z matematycznego punktu widzenia, prawdopodobieństwo selekcji osobnika wyraża się jako:

$P(i) = \frac{f_i}{\sum_{j=1}^{N} f_j}$

gdzie:

• $f_i$ to wartość funkcji przystosowania osobnika $i$,
• $N$ to liczba osobników w populacji.

Selekcja ruletkowa jest szybka i prosta, ale ma kilka wad. Przede wszystkim, jeśli w populacji znajduje się jeden bardzo dobrze przystosowany osobnik, to dominuje on selekcję – co może prowadzić do przedwczesnej zbieżności. Z drugiej strony, gdy wartości funkcji przystosowania są zbliżone, presja selekcyjna spada, a algorytm „drepcze w miejscu”.

Selekcja rankingowa

W selekcji rankingowej osobniki są najpierw sortowane według przystosowania (od najlepszego do najgorszego), a następnie każdemu przypisywana jest wartość selekcyjna zależna od jego pozycji (rangi), a nie od bezwzględnej wartości funkcji celu. Dzięki temu unika się problemów związanych z dużymi różnicami w wartościach funkcji przystosowania.

Presję selekcyjną można regulować poprzez funkcję przekształcającą rangę na prawdopodobieństwo – np. liniowo, wykładniczo lub z wykorzystaniem rozkładów losowych. Rankingowa metoda zapewnia bardziej kontrolowaną presję selekcyjną i pozwala uniknąć dominacji pojedynczych osobników, ale kosztem większej złożoności obliczeniowej (sortowanie).

Selekcja turniejowa

W selekcji turniejowej tworzy się losowo grupy (turnieje) złożone z osobników (zwykle lub ). W każdej grupie wygrywa najlepszy osobnik, który trafia do puli reprodukcyjnej. Metoda ta jest prosta do zaimplementowania i nie wymaga znajomości wartości funkcji przystosowania całej populacji.

Presję selekcyjną reguluje się wielkością turnieju – większe oznacza silniejszą presję. Przykładowo, turniej zachowuje sporo losowości, natomiast może szybko prowadzić do utraty różnorodności. Istnieją też warianty turnieju probabilistycznego, w którym zwycięzca wybierany jest z prawdopodobieństwem zależnym od jego jakości.

Porównanie technik

• Ruletka – szybka, ale wrażliwa na rozkład przystosowań; może prowadzić do dominacji jednego osobnika.
• Ranking – stabilna i odporna na ekstremalne wartości funkcji celu; presja zależna od rangi.
• Turniej – bardzo elastyczny, szybki i łatwy do równoleglenia; dobrze sprawdza się w praktyce.

Dobór operatora selekcji ma istotny wpływ na zachowanie algorytmu – jego zbieżność, eksplorację i eksploatację przestrzeni. W praktyce często testuje się różne metody dla konkretnego problemu, by dobrać najbardziej efektywną konfigurację.

Ciekawostka: Uruchamiając poniższy program możecie zobaczyć / testować jak działają omówione operatory selekcji:

import numpy as np
import matplotlib.pyplot as plt

# Generowanie populacji i przypisanie funkcji przystosowania
np.random.seed(42)
population_size = 20
fitness = np.sort(np.random.rand(population_size))[::-1]  # Posortowane od najlepszego

# Selekcja ruletkowa
def roulette_selection(fitness, num_selected):
    probabilities = fitness / fitness.sum()
    return np.random.choice(len(fitness), size=num_selected, p=probabilities)

# Selekcja rankingowa (liniowa)
def ranking_selection(fitness, num_selected):
    ranks = np.argsort(np.argsort(-fitness))  # 0 - najlepszy
    rank_weights = (len(fitness) - ranks)
    probabilities = rank_weights / rank_weights.sum()
    return np.random.choice(len(fitness), size=num_selected, p=probabilities)

# Selekcja turniejowa
def tournament_selection(fitness, num_selected, tournament_size=3):
    selected = []
    for _ in range(num_selected):
        participants = np.random.choice(len(fitness), tournament_size, replace=False)
        winner = participants[np.argmax(fitness[participants])]
        selected.append(winner)
    return np.array(selected)

# Zastosowanie selekcji
num_selected = 1000
roulette_counts = np.bincount(roulette_selection(fitness, num_selected), minlength=population_size)
ranking_counts = np.bincount(ranking_selection(fitness, num_selected), minlength=population_size)
tournament_counts = np.bincount(tournament_selection(fitness, num_selected), minlength=population_size)

# Wizualizacja
plt.figure(figsize=(12, 6))
plt.plot(roulette_counts, label='Ruletkowa', marker='o')
plt.plot(ranking_counts, label='Rankingowa', marker='s')
plt.plot(tournament_counts, label='Turniejowa (k=3)', marker='^')
plt.title("Porównanie technik selekcji w algorytmie genetycznym")
plt.xlabel("Indeks osobnika (0 = najlepszy)")
plt.ylabel("Liczba wybrań w selekcji (z 1000 prób)")
plt.legend()
plt.grid(True)
plt.tight_layout()
plt.show()

Krzyżowanie (ang. crossover) to kluczowy operator genetyczny odpowiedzialny za wymianę informacji pomiędzy osobnikami w populacji. Jego celem jest tworzenie nowych rozwiązań poprzez kombinację cech rodziców. Skuteczny operator krzyżowania powinien z jednej strony umożliwiać eksploatację dobrych rozwiązań, a z drugiej zachować wystarczającą różnorodność w populacji.

W zależności od rodzaju kodowania genotypu, stosuje się różne techniki krzyżowania. Poniżej przedstawiamy najważniejsze z nich.

Krzyżowanie dla kodowania binarnego (klasycznego)

Jednopunktowe (single-point crossover)

Losowany jest jeden punkt podziału chromosomu. Dzieci dziedziczą część genów od jednego rodzica przed punktem, a drugą część od drugiego rodzica.

Dwupunktowe (two-point crossover)

Losowane są dwa punkty podziału. Fragment między nimi jest zamieniany pomiędzy rodzicami. Pozwala to na bardziej zróżnicowaną rekombinację.

Jednorodne (uniform crossover)

Dla każdego genu losowo (z prawdopodobieństwem np. 0.5) wybierany jest jeden z rodziców. Zapewnia to największe wymieszanie cech.

Zalety tych metod to prostota, niska złożoność i szerokie zastosowanie w kodowaniu binarnym. Wadą może być generowanie dziwnych struktur rozwiązań – operacje są niezależne od semantyki problemu.

Krzyżowanie dla kodowania rzeczywistego

Krzyżowanie arytmetyczne

Potomkowie wyznaczani są jako liniowa kombinacja rodziców:

$\text{Potomek} = \alpha \cdot \text{Rodzic}_1 + (1 - \alpha) \cdot \text{Rodzic}_2$

gdzie $\alpha \in [0,1]$ to losowy współczynnik.

Krzyżowanie blendowane (BLX-$\alpha$)}

Nowe geny losowane są z przedziału szerszego niż zakres między genami rodziców. Umożliwia eksplorację nowych wartości:

$x = U[\text{min} - d \cdot \alpha,\ \text{max} + d \cdot \alpha]$

gdzie $d = |x_1 - x_2|$.

Krzyżowanie z zakłóceniem (SBX)

Imituje rozkład krzyżowania binarnego, ale w przestrzeni ciągłej, operując bezpośrednio na liczbach rzeczywistych. Simulated Binary Crossover (SBX) jest zaprojektowany tak, aby zachowywać podobne statystyczne właściwości jak klasyczne krzyżowanie dwupunktowe, ale działa w przestrzeni rzeczywistej, co czyni go użytecznym w optymalizacji ciągłej. Główna idea polega na losowym generowaniu wartości potomnych wokół wartości rodziców z kontrolowaną zmiennością, regulowaną parametrem rozkładu (ang. distribution index).

SBX jest szczególnie popularny w strategiach ewolucyjnych i algorytmach różnicowych. Dzięki parametrowi rozkładu można kontrolować zakres eksploracji: niska wartość parametru sprzyja dużym odchyleniom (eksploracja), natomiast wyższe wartości skutkują generowaniem potomków bardzo bliskich rodzicom (eksploatacja). To czyni SBX elastycznym narzędziem, dobrze dostosowanym do różnych etapów procesu optymalizacji.

Krzyżowanie dla kodowania permutacyjnego

W przypadku permutacji, celem jest zachowanie unikalności elementów – klasyczne krzyżowanie nie może być stosowane. Zamiast tego stosujemy: 

Krzyżowanie cykliczne (CX)

Krzyżowanie cykliczne (CX) polega na identyfikowaniu pozycyjnych cykli pomiędzy dwoma rodzicami. Dla każdego osobnika wyznacza się cykl elementów, które w tych samych pozycjach znajdują się u obojga rodziców, zachowując ich wzajemne relacje. Potomkowie dziedziczą cyklicznie pozycje z jednego rodzica, a pozostałe wypełniają elementami z drugiego, z zachowaniem unikalności.

Metoda ta dobrze zachowuje strukturę pozycyjną oryginalnych rozwiązań i jest odporna na utratę informacji porządkowej. W porównaniu do innych operatorów dla permutacji, CX generuje poowy niż np. PMX czy OX, co czyni go dobrym wyborem tam, gdzie istotne jest zachowanie względnych pozycji w permutacjach.

Krzyżowanie PMX

Krzyżowanie PMX (Partially Mapped Crossover) polega na losowym wybraniu fragmentu permutacji z jednego z rodziców i bezpośrednim przepisaniu go do potomka. Następnie dla pozostałych pozycji stosowane jest odwzorowanie elementów z drugiego rodzica na podstawie zależności utworzonych przez wspólny fragment. Dzięki temu zachowana zostaje zgodność z permutacyjną strukturą – każdy element występuje tylko raz.

PMX dobrze radzi sobie z zachowaniem względnych pozycji i unikalności elementów, co czyni go popularnym w problemach typu TSP i alokacyjnych. Metoda ta jest bardziej „lokalna” niż krzyżowanie cykliczne – silniej zachowuje lokalne fragmenty jednego z rodziców, przez co umożliwia zarówno eksploatację, jak i pewien stopień eksploracji przestrzeni rozwiązań.

Order Crossover (OX)

Krzyżowanie OX (Order Crossover) to technika, która zachowuje porządek występowania elementów oraz ich względną kolejność. Proces polega na losowym wybraniu fragmentu permutacji z jednego rodzica i bezpośrednim przepisaniu go do potomka. Następnie, uzupełnia się pozostałe miejsca w chromosomie, przechodząc kolejno przez elementy drugiego rodzica, pomijając te już zapisane, zachowując ich oryginalną kolejność.

Metoda ta jest niezwykle skuteczna w zachowywaniu informacji o sąsiedztwie elementów – co jest istotne np. w problemach trasowania czy harmonogramowania. Pozwala na przenoszenie całych sekwencji z rodziców do potomków, co może wspomóc zachowanie lokalnych struktur rozwiązania, które wykazują dobrą jakość.

OX, w porównaniu do innych operatorów dla permutacji, takich jak PMX czy CX, lepiej nadaje się do problemów, gdzie kolejność elementów ma większe znaczenie niż ich konkretne pozycje. Jest także stosunkowo łatwy do zaimplementowania, co czyni go jednym z najpopularniejszych operatorów krzyżowania w problemach kombinatorycznych.

Krzyżowanie dla kodowania drzewiastego

Krzyżowanie poddrzew

Krzyżowanie poddrzew (subtree crossover) to najczęściej stosowany operator w programowaniu genetycznym. Działa poprzez losowe wybranie węzła w drzewie każdego z rodziców, a następnie zamianę odpowiadających im poddrzew. Operacja ta pozwala na generowanie potomków, którzy łączą elementy strukturalne obu rodziców, zachowując przy tym składniową poprawność wyrażeń.

Zaletą tego podejścia jest jego naturalność w kontekście drzewiastych reprezentacji – poddrzewa mogą reprezentować całe podfunkcje, wyrażenia lub bloki instrukcji. Dzięki temu krzyżowanie może wprowadzać znaczące zmiany w funkcjonalności osobników, co sprzyja eksploracji przestrzeni rozwiązań. Jednocześnie zachowuje spójność semantyczną potomków, co jest kluczowe dla unikania błędnych lub niekompilowalnych struktur.

Aby zapobiec nadmiernemu wzrostowi rozmiarów drzew (tzw. "bloat"), często stosuje się ograniczenia na maksymalną głębokość drzewa potomka lub kontroluje się prawdopodobieństwo wyboru węzłów w zależności od ich poziomu. Taka regulacja pozwala zachować równowagę między eksploracją a stabilnością populacji, ograniczając tworzenie zbyt dużych, trudnych do zinterpretowania struktur.

Krzyżowanie jedno- i wielopunktowe

Zamiast zamiany całych poddrzew, możliwa jest zamiana pojedynczych gałęzi lub zestawów gałęzi, zgodnie z zadanymi regułami syntaktycznymi. Taki sposób krzyżowania pozwala na bardziej precyzyjne operowanie strukturą drzewa – można np. wymieniać tylko konkretne operatory matematyczne, fragmenty wyrażeń lub konkretne funkcje warunkowe. Podejście to umożliwia drobniejsze i bardziej kontrolowane modyfikacje, co może być korzystne w końcowych etapach ewolucji, gdy poszukiwane są optymalne drobne zmiany.

Wersje jedno- i wielopunktowe krzyżowania na poziomie drzewa mogą także uwzględniać kontekst syntaktyczny, np. tylko zamianę węzłów o tej samej arności (liczbie argumentów) albo tej samej kategorii (np. operatorów logicznych). Zapewnia to zachowanie poprawności semantycznej i składniowej potomków oraz pozwala utrzymać strukturę kodu w granicach oczekiwanej złożoności. Dobrze zaprojektowane krzyżowanie na poziomie gałęzi może skutkować bardziej stabilną i przewidywalną ewolucją programu.

Te operatory pozwalają generować złożone struktury, np. funkcje matematyczne, ale wymagają kontroli poprawności składniowej potomków.

Inne techniki krzyżowania

Krzyżowanie heurystyczne

Tworzy potomek przesunięty w kierunku lepszego z rodziców:

$x = x_1 + r \cdot (x_1 - x_2)$

gdzie $$x_1$ jest lepszy od $x_2$, a $r$ – losowa liczba.

Krzyżowanie topologiczne

Krzyżowanie topologiczne znajduje zastosowanie przede wszystkim w algorytmach, które operują na strukturach grafowych, takich jak ewolucja architektury sieci neuronowych (neuroewolucja) czy optymalizacja połączeń logicznych. W takich przypadkach genotypem nie jest prosty ciąg bitów czy liczb, lecz graf reprezentujący połączenia pomiędzy węzłami (neurony, funkcje, jednostki przetwarzające). Krzyżowanie polega na łączeniu części struktury dwóch rodziców w sposób, który tworzy nową sensowną topologię – np. przez zachowanie wspólnych połączeń oraz wstawienie unikalnych fragmentów z każdego z rodziców.

Dla sieci neuronowych najczęściej krzyżowane są zarówno struktury połączeń (czyli które węzły są ze sobą połączone), jak i wagi tych połączeń. Przykładem jest algorytm NEAT (NeuroEvolution of Augmenting Topologies), który identyfikuje odpowiadające sobie węzły i połączenia poprzez mechanizm numerowania genów, a następnie tworzy potomka z części wspólnych oraz zmutowanych nowych połączeń. Dzięki temu możliwe jest ewolucyjne rozwijanie złożonych sieci, które zachowują funkcjonalność poprzedników.

Zaletą krzyżowania topologicznego jest możliwość tworzenia coraz bardziej zaawansowanych i nieliniowych architektur, jednak jego projektowanie wymaga dużej ostrożności. Istotne jest zachowanie poprawności strukturalnej (np. unikanie cykli w sieciach jednokierunkowych) oraz funkcjonalności potomków. Operatory te bywają złożone, ale stanowią fundament dla nowoczesnych metod neuroewolucyjnych i programowania strukturalnego.

Podsumowanie

Wybór operatora krzyżowania zależy bezpośrednio od typu kodowania i charakteru problemu. Odpowiedni operator powinien:

• zachowywać poprawność semantyczną rozwiązań,
• sprzyjać eksploracji i eksploatacji,
• być dopasowany do struktury genotypu.

W praktyce operator krzyżowania bywa kluczowym czynnikiem wpływającym na skuteczność algorytmu genetycznego. Dobór operatora często wymaga eksperymentalnej walidacji i dostosowania do konkretnego zadania.

Mutacja to podstawowy operator różnicowania genetycznego w algorytmach ewolucyjnych. Jej głównym zadaniem jest wprowadzanie losowych zmian w strukturze genotypu, co pozwala na eksplorację nowych rejonów przestrzeni rozwiązań. Mutacja uzupełnia działanie operatora krzyżowania – podczas gdy krzyżowanie miesza informacje już istniejące w populacji, mutacja wprowadza nowy materiał genetyczny.

Dobór odpowiedniej techniki mutacji zależy od typu kodowania rozwiązania – inne metody stosuje się dla chromosomów binarnych, inne dla rzeczywistych, permutacyjnych czy drzewiastych.

Mutacja w kodowaniu binarnym

Najprostszą i najczęściej stosowaną metodą jest tzw. mutacja bitowa (bit flip mutation). Polega na odwróceniu wartości bitu z 0 na 1 lub odwrotnie z pewnym prawdopodobieństwem $p_m$. Dla każdego bitu w chromosomie generowany jest losowy wynik, który decyduje o tym, czy dany bit zostanie odwrócony.

Z matematycznego punktu widzenia, dla chromosomu $g = (g_1, g_2, ..., g_n)$, po mutacji:

$g_i' = \begin{cases} 1 - g_i & \text{z prawdopodobieństwem } p_m \\ g_i & \text{w przeciwnym razie} \end{cases}$

Parametr $p_m$ (np. 0.01 lub 1/n) określa siłę mutacji. Zbyt wysoka wartość może prowadzić do losowej eksploracji (efekt "szumu"), zbyt niska – do stagnacji populacji.

Mutacja w kodowaniu rzeczywistoliczbowym

W tej klasie problemów mutacja polega na dodaniu niewielkiego zaburzenia do wartości genu. Najczęściej stosuje się mutację gaussowską (normalną), gdzie do każdego genu dodawana jest wartość losowa z rozkładu normalnego:

$g_i' = g_i + N(0, \sigma^2)$

gdzie $\sigma$ to parametr określający intensywność mutacji.

Wadą mutacji gaussowskiej może być ryzyko wyjścia poza dopuszczalny przedział. Aby tego uniknąć, wartości są zwykle przycinane lub odbijane od granic. Alternatywnie można stosować mutację Cauchy'ego (o grubych ogonach), która częściej generuje większe zmiany – sprzyja eksploracji globalnej.

Inną metodą jest tzw. unbounded mutation, gdzie nowe wartości są losowane z całego przedziału zmienności, np.:

$g_i' = U(a_i, b_i)$

Mutacja permutacyjna

W problemach, gdzie rozwiązania są reprezentowane jako permutacje (np. TSP), standardowe metody mutacji nie mają zastosowania. Zamiast tego stosuje się modyfikacje struktur permutacyjnych:

• Swap mutation – losowo wybierane są dwa indeksy i ich wartości są zamieniane: $g = (..., g_i, ..., g_j, ...) \Rightarrow (..., g_j, ..., g_i, ...)$
• Insertion mutation – jeden element jest usuwany i wstawiany w innym miejscu w permutacji.
• Inversion mutation – losowy fragment permutacji jest odwracany.

Mutacja w strukturach drzewiastych

W programowaniu genetycznym mutacja najczęściej dotyczy struktury drzewa – np. podmiany pojedynczego węzła, zastąpienia poddrzewa nowym lub modyfikacji terminali.

• Subtree mutation – losowy węzeł drzewa zostaje zastąpiony losowo wygenerowanym poddrzewem.
• Point mutation – zmiana wartości operatora lub terminala w wybranym węźle.

Inne techniki mutacji

• Mutacja ograniczona (boundary mutation) – gen może przyjąć wartość jednego z krańców dopuszczalnego zakresu.
• Non-uniform mutation – siła mutacji zmniejsza się w miarę upływu czasu, np.:$g_i' = g_i + \Delta(t, b_i - g_i)$
  gdzie 
  • $\Delta(t, d)$ to funkcja malejąca wraz z czasem (np. logarytmiczna),
  • $t$ – numer pokolenia.
• Adaptive mutation – parametr mutacji (np. $\sigma$) zmienia się w trakcie działania algorytmu w odpowiedzi na tempo poprawy rozwiązania.

Podsumowanie

Mutacja pełni niezwykle ważną rolę w utrzymywaniu różnorodności populacji. W zależności od typu kodowania, należy dobierać odpowiednie operatory:

• binarne – odwracanie bitów,
• rzeczywiste – zakłócenia losowe (np. gaussowskie),
• permutacyjne – przekształcenia pozycji,
• drzewiaste – manipulacje strukturą drzewa.

Dobór intensywności mutacji i jej rodzaju wpływa na zdolność algorytmu do eksploracji i unikania zbieżności do lokalnych minimów. W praktyce często stosuje się również mechanizmy adaptacyjne, które dynamicznie dostosowują siłę mutacji w trakcie działania algorytmu.

Warunki zakończenia są istotnym elementem sterującym działaniem algorytmu genetycznego. To one decydują, kiedy proces ewolucyjny zostaje zatrzymany, a najlepsze znalezione rozwiązanie uznane za wynik końcowy. Ich odpowiedni dobór wpływa zarówno na jakość rozwiązań, jak i na czas działania algorytmu.

W praktyce stosuje się kilka klas warunków zakończenia, często wykorzystywanych równolegle.

Zakończenie po ustalonej liczbie pokoleń

Najczęstszy i najprostszy sposób zatrzymania działania algorytmu. Proces ewolucyjny kończy się po osiągnięciu ustalonej liczby iteracji (pokoleń).

$\text{Stop, jeśli } t \geq T_{max}$

gdzie $t$ to aktualny numer pokolenia, a $T_{max}$ – maksymalna liczba pokoleń.

Zaletą tej metody jest jej przewidywalność i łatwość implementacji. Wadą – brak związku z faktyczną jakością rozwiązań. Może prowadzić do zakończenia przedwcześnie lub kontynuowania obliczeń mimo osiągnięcia optimum.

Zakończenie po czasie działania

Algorytm zatrzymuje się po upływie określonego czasu rzeczywistego. Stosowane w systemach o ograniczonych zasobach obliczeniowych lub tam, gdzie wymagane są wyniki w czasie rzeczywistym.

$\text{Stop, jeśli } \text{czas} \geq T_{czasowy}$

Ten sposób pozwala dostosować pracę algorytmu do ograniczeń środowiska (np. wbudowane systemy, przetwarzanie online). Jednak, podobnie jak poprzedni, nie uwzględnia postępu jakościowego.

Zakończenie przy braku poprawy

Algorytm zatrzymuje się, gdy przez kolejne $N$ pokoleń nie następuje istotna poprawa najlepszego osobnika:

$\text{Stop, jeśli } \max(F_{best}^{(t - N)} \dots F_{best}^{(t)}) - F_{best}^{(t)} \leq \epsilon$

gdzie $F_{best}^{(t)}$ to wartość funkcji celu najlepszego osobnika w pokoleniu $t$, a $\epsilon$ to zadana tolerancja.

Metoda ta jest bardziej adaptacyjna – pozwala zakończyć działanie algorytmu, gdy dalsze przeszukiwanie nie przynosi postępu. Często używana w połączeniu z limitem pokoleń.

Zakończenie po osiągnięciu wartości celu

Jeśli algorytm znajdzie rozwiązanie o jakości przekraczającej z góry określony próg, zatrzymuje się natychmiast:

$\text{Stop, jeśli } F_{best}^{(t)} \geq F_{target}$

To podejście jest szczególnie przydatne w sytuacjach, gdy znamy wartość globalnego optimum lub poziom, który uznajemy za wystarczający.

Zakończenie na podstawie różnorodności populacji

Zanik różnorodności (np. ujednolicenie genotypów) może wskazywać, że algorytm osiągnął stagnację. Wówczas możemy zakończyć jego działanie:

$\text{Stop, jeśli } \text{diversity}(P_t) \leq \delta$

gdzie $\text{diversity}(P_t)$ mierzy zróżnicowanie populacji $P_t$.

Miara różnorodności może opierać się na odległości Hammingowej, wariancji genów, entropii lub innych statystykach. To podejście pozwala wykryć, że populacja „utknęła” w jednym optimum lokalnym.

Złożone i adaptacyjne warunki zakończenia

W praktyce często łączy się kilka kryteriów – np. maksymalna liczba pokoleń ORAZ brak poprawy przez $N$ pokoleń. Stosuje się także warunki adaptacyjne, gdzie próg tolerancji czy oczekiwany postęp zmieniają się w czasie działania algorytmu.

Możliwe jest także zastosowanie monitorowania pochodnych, prędkości zbieżności lub metryk pochodzących z uczenia maszynowego do przewidywania zatrzymania.

Podsumowanie

Warunki zakończenia to jeden z kluczowych parametrów kontrolnych algorytmu genetycznego. Wpływają na jego efektywność, koszt obliczeniowy i jakość wyniku końcowego. Ich dobór powinien uwzględniać:

• charakterystykę problemu,
• wymagania czasowe lub sprzętowe,
• oczekiwany poziom dokładności,
• strategię eksploracji i eksploatacji.

Stosowanie złożonych i wielokryterialnych warunków zakończenia może znacząco poprawić skuteczność i elastyczność algorytmu.

Na podstawie pracy Abrahama, Das i Roya (2007) można zidentyfikować kilka fundamentalnych powodów, dla których algorytmy rojowe – w szczególności PSO (Particle Swarm Optimization) – są skuteczne w rozwiązywaniu problemów optymalizacyjnych, zarówno w przestrzeniach dyskretnych, jak i ciągłych. Ich efektywność wynika z kombinacji prostoty lokalnych reguł, mechanizmów komunikacji oraz emergencji zachowań grupowych.

Proste zasady, złożone efekty

Jednym z najważniejszych argumentów przytoczonych przez Abrahama i współautorów jest to, że złożone wzorce mogą wyłaniać się z prostych zachowań jednostek. W PSO każda cząstka kieruje się tylko kilkoma regułami: porusza się po przestrzeni rozwiązań pod wpływem własnego najlepszego doświadczenia oraz najlepszej znalezionej dotąd pozycji w swoim otoczeniu. To wystarczy, by cała populacja, nawet w bardzo złożonym krajobrazie funkcji celu, stopniowo zbiegała się do optymalnych (lub bliskich optymalnym) regionów.

Wymiana informacji i adaptacja

Drugi kluczowy element skuteczności PSO to zdolność komunikacji i adaptacji. Cząstki nie działają niezależnie – dzielą się informacją. W zależności od zastosowanej topologii (np. sąsiedztwa globalnego lub lokalnego), każda cząstka może korzystać z doświadczenia innych. To „uczenie się od innych” sprawia, że zamiast losowego błądzenia, mamy do czynienia z kierunkowym przeszukiwaniem, przy jednoczesnym zachowaniu różnorodności.

Brak potrzeby informacji gradientowej

W klasycznych algorytmach optymalizacyjnych, jak np. metoda gradientu, potrzebna jest znajomość pochodnych funkcji celu. PSO, podobnie jak inne algorytmy ewolucyjne, działa wyłącznie na podstawie wartości funkcji celu, bez potrzeby jej analitycznego opisu. To sprawia, że PSO jest odporny na nieliniowości, nieciągłości i szum – a zatem doskonale sprawdza się tam, gdzie tradycyjne metody zawodzą.

Eksploracja vs. eksploatacja

Według Abrahama, Das i Roya algorytmy rojowe osiągają skuteczność dzięki naturalnemu balansowi między eksploracją (badaniem nowych obszarów przestrzeni) a eksploatacją (lokalnym udoskonalaniem znanych rozwiązań). Początkowo cząstki przemieszczają się bardziej chaotycznie, dzięki czemu mogą „zajrzeć” do wielu regionów. Z czasem jednak, gdy znajdą obiecujące obszary, ich ruch staje się bardziej skupiony i następuje zbieżność.

Elastyczność i skalowalność

PSO działa dobrze niezależnie od wymiarowości przestrzeni problemu i może być z łatwością dostosowany do różnych zastosowań. Autorzy podkreślają, że dzięki temu algorytmy rojowe są elastyczne, łatwe do implementacji i wydajne obliczeniowo – szczególnie w środowiskach, gdzie wiele jednostek może działać równolegle.

Przejdźmy zatem do formalnej definicji algorytmu PSO, zaczynając od założeń: 

Założenia algorytmu PSO – co wie każda cząstka?

W algorytmie PSO (Particle Swarm Optimization) modelujemy rozwiązania problemu jako cząstki poruszające się w przestrzeni przeszukiwań. Każda z tych cząstek (zwanych też osobnikami) posiada zestaw cech, który pozwala jej podejmować decyzje na podstawie lokalnych i sąsiedzkich informacji.

Wiedza i pamięć cząstki

Każda cząstka w roju:

• zna swoje aktualne położenie w przestrzeni (np. współrzędne),
• potrafi ocenić jakość swojego położenia, czyli zna wartość funkcji celu w swoim punkcie,
• porusza się z określoną prędkością i w zadanym kierunku,
• zapamiętuje najlepsze położenie, jakie kiedykolwiek odwiedziła (tzw. pozycję własnego optimum),
• zna wartość funkcji celu w tym najlepszym punkcie.

Interakcje społeczne

Cząstka nie działa w izolacji:

• wie, kim są jej sąsiedzi – czyli z kim „wymienia się” informacją,
• zna najlepsze pozycje osiągnięte przez sąsiadów,
• zna też wartość funkcji celu w tych pozycjach.

Efekt emergentny

Ten zestaw prostych właściwości daje niesamowicie efektywne zachowanie: cząstki potrafią samodzielnie, bez centralnego sterowania, gromadzić się wokół optymalnych punktów przestrzeni.

Dzięki połączeniu pamięci własnej i „inteligencji zbiorowej” algorytm PSO jest w stanie skutecznie eksplorować przestrzeń rozwiązań, a jednocześnie zbiegać do punktów optymalnych.

Realizacja

Założenie jednak mówiło, że nie tylko moja wiedza jest istotna - także mam dzielić się informacjami z innymi. Mogę więc podglądać sąsiadów: 

No i - last but not least - mogę patrzeć na ideały, czyli podążać w kierunku definiowanym przez najlepszą cząstkę w całym roju: 

I to już całe wyrażenie które kieruje ruchem każdej cząstki. Finalnie więc mamy wyrażenie: 

$v_i^{k+1}=w_i^k v_i^k + c_1 r_1(p_i-x_i^k)+c_2r_2(p_i^{n,k}-x_i^k)+c_3r_3(p^{g}-x_i^k)$

gdzie:

• $v_i^k$ – prędkość cząstki i w chwili k,
• $x_i^k$ - aktualna pozycja cząstki i.
• $p_i$ - najlepsza dotąd pozycja cząstki i
• $p_i^{n,k}$ - najlepsza pozycja w sąsiedztwie cząstki
• $p^g$ - najlepsza w ogóle pozycja w roju, 
• $w$ - współczynnik inercji
• $c_1,c_2, c_3$ - współczynniki socjalne (przyciąganie do własnego, lokalnego i globalnego optimum)
• $r_1,r_2, r_3$ - wartości losowe generowane niezależnie dla każdego wymiaru i każdej cząstki