Metody optymalizacji zadań jednowymiarowych

1. 13.1 Ogólna metoda wyszukiwania
2. 13.2 Metoda połowy podziału (dzielenie segmentu na pół)
3. 13.3 Metoda dychotomii
4. 13.4 Metoda „złotej sekcji”
5. 13.5 Metoda Fibonacciego

Proces optymalizacji leży u podstaw wszystkich działań inżynierskich, ponieważ klasyczne funkcje inżyniera są z jednej strony projektowaniem nowych, bardziej wydajnych i tańszych systemów technicznych, az drugiej strony opracowywaniem metod poprawy jakości funkcjonowania istniejących systemów. Skuteczność metod optymalizacji, które pozwalają wybrać najlepszą opcję bez sprawdzania wszystkich możliwych opcji, jest ściśle powiązana z szerokim wykorzystaniem postępów w dziedzinie matematyki poprzez wdrożenie iteracyjnych schematów obliczeniowych opartych na dobrze ugruntowanych metodach i algorytmach z wykorzystaniem obliczeń.

Obecnie, ze względu na dostępność komputerów osobistych, dużą wagę przywiązuje się do stosowania numerycznych metod optymalizacji w praktyce inżynierskiej, które można podzielić na dwie duże grupy: metody optymalizacji bezwarunkowej i warunkowej. Ten rozkład jest powiązany z innym opisem przestrzeni projektowej. Dziedzina badań, czyli obszar, w którym inżynier próbuje określić optymalne zadanie, nazywa się przestrzenią projektową .

Przestrzeń projektowa, która jest określona przez parametry projektowe, jest zwykle ograniczona przez szereg warunków związanych z fizycznym charakterem problemu i jest rozpatrywana w postaci dwóch opcji:

1) jeśli parametr projektowy jest jeden, to zazwyczaj ograniczenia są związane z jego wartościami, czyli obszar projektowania jest zawężony do segmentu badania [a, b];

2) jeśli parametry projektowe są różne, ograniczenia mogą być nałożone albo na ich wartość, ograniczając zakres badania, albo w postaci współzależności między parametrami projektowymi, które muszą być brane pod uwagę przy poszukiwaniu rozwiązania (te zależności w rzeczywistych problemach mogą odzwierciedlać prawa natury, ekonomię, prawo, dostępność niezbędne materiały itp.).

Ta sekcja omawia metody bezwarunkowego jednowymiarowego wyszukiwania optymalnej funkcji celu, które opierają się na wykorzystaniu pierwszej wersji reprezentacji przestrzeni projektowej, gdzie funkcja docelowa jest wyrażeniem (funkcją), którego wartość inżynier stara się zminimalizować lub zmaksymalizować. Zakłada się, że badane funkcje docelowe są jednomodalne , to znaczy mają przedział badawczy, który jest uważany za jeden optymalny (rysunek 13.1). Takie ograniczenie charakteru funkcji celu nie jest tak sztywne, jak mogłoby się wydawać, ponieważ wiele zadań, z którymi spotyka się inżynier w swojej praktyce, jest jednomodalne.

Metody numeryczne kierowane przez rozwiązanie bezwarunkowych zadań optymalizacyjnych można podzielić na trzy klasy:

- metody bezpośredniego wyszukiwania oparte na obliczaniu tylko wartości funkcji celu;

Rysunek 13.1 - Funkcja unimodalnego celu

Rysunek 13.2 - Funkcja docelowa z optimum lokalnym i globalnym

- metody gradientowe, w których używane są dokładne wartości pierwszych pochodnych f (x);

- metody drugiego rzędu , w których, wraz z pierwszymi pochodnymi, używane są również drugie pochodne funkcji f (x).

Problem optymalizacji jednowymiarowej jest ustawiony w następujący sposób: wartość parametru X funkcji docelowej f (x), nazywanej parametrem projektowym , mieści się w przedziale badania [a, b]. W procesie poszukiwania optimum funkcji docelowej ten przedział, zwany interwałem niepewności , stale maleje (zwężenie), więc jednowymiarowe metody optymalizacji są czasami nazywane metodami zmniejszania przedziału niepewności.

Wybór metody numerycznej zależy przede wszystkim od rodzaju funkcji celu, która może być jednoparametrowa i wieloparametrowa (rys. 13.3, 13.4).

Rysunek 13.3 - Funkcja celu jednego parametru

Rysunek 13.4 - Funkcja dwóch parametrów celu

Niektóre algorytmy optymalizacji są dostosowane do znajdowania maksimum, podczas gdy inne - do wyszukiwania minimum.

Niezależnie jednak od rodzaju zadania, które jest rozwiązane przez ekstremum (optimum), możliwe jest użycie tego samego algorytmu, ponieważ zadanie minimalizacji można łatwo przekształcić w zadanie wyszukiwania minimum, zmieniając znak funkcji celu na przeciwny (rysunek 13.5).

Rysunek 13.5 - Zmieniając cel funkcji docelowej na przeciwny, co najmniej, zamienia się w zadanie maksymalnie

Ogólne sformułowanie problemu dla metod optymalizacji jednowymiarowej jest następujące : niech wartość parametru X będzie w przedziale [a, b], a funkcja celu jest jednomodalna w regionie, który badamy. Większość metod numerycznych optymalizacji jednowymiarowej to metody zawężania segmentu, a mianowicie: metoda rozdzielania segmentu na pół, metoda dychotomii, metoda złotej sekcji, metoda Fibonacciego.

W procesie jednowymiarowej optymalizacji funkcji celu na komputerze można podzielić na dwa etapy:

1) ustawienie granic segmentu, w którym realizowana jest optymalna procedura wyszukiwania;

2) zmniejszenie segmentu do podanego błędu obliczeniowego .

Pierwszy etap jest implementowany za pomocą heurystycznych metod wyszukiwania i jest bardzo skomplikowany. Drugi nazywa się regułą wykluczania segmentów, implementując algorytm wyszukiwania, który umożliwia znalezienie optymalnego punktu poprzez sekwencyjne wykluczanie części początkowego ograniczonego segmentu [a, b], to znaczy przy użyciu algorytmów iteracyjnych. Jako warunek zakończenia procesu iteracyjnego, moment, w którym pozostała subinterferencja jest zredukowana do wystarczająco małego rozmiaru (zazwyczaj wartość danego błędu obliczeniowego jest podana dla tego )

13.1 Ogólna metoda wyszukiwania

Oczywiście najbardziej naturalnym sposobem zawężenia przedziału niepewności dla jednowymiarowej funkcji unimodalnej jest podzielenie jej na kilka równych części, a następnie obliczenie wartości funkcji celu w węzłach wynikowej siatki (rys. 13.6).

Rysunek 13.6 - Ogólna metoda wyszukiwania

W rezultacie przedział niepewności jest zawężany do dwóch kroków siatki. Zazwyczaj mówi się o rozdrobnieniu przedziału niepewności, który charakteryzuje się współczynnikiem f. Dzieląc przedział niepewności na N części otrzymujemy węzeł N + 1, a następnie

.

Aby uzyskać wartość f = 0,01 , konieczne jest obliczenie funkcji celu w 199 punktach, aw f = 0,001 N = 1999 . Z tego wynika, że ​​skuteczność tej metody szybko maleje wraz ze spadkiem przedziału niepewności. Inną opcją jest uzyskanie f = 0,01 , konieczne jest najpierw obliczenie funkcji w 19 punktach i uzyskanie f = 0,1 , a następnie obliczenie kolejnych 19 wartości funkcji w skróconym przedziale niepewności, otrzymanie f = 0,01 , a tym samym wykonanie wszystkich 38 zamiast 199 obliczeń. W ten sposób, dzięki pewnej pomysłowości, wydajność wyszukiwania może być znacznie zwiększona.

13.2 Metoda połowy podziału (dzielenie segmentu na pół)

Istotą tej metody jest ciągłe dzielenie segmentu badania funkcji celu [a, b] na pół i określanie na niej współrzędnych trzech punktów x1, x2, xm. Jednocześnie ich wartości są zdefiniowane jako:

, L = ba, , .

Rysunek 13.7 - Geometryczna interpretacja metody połowicznego podziału

Punkty , podziel segment [a, b] na cztery równe części (rys. 13.6), oblicz wartość funkcji celu Następnie porównaj wartość i , jeśli , następnie wykluczamy sekcję badania i powiedzmy to . Następnie punkt środkowy nowego segmentu [a, b] staje się . Ale jeśli , następnie porównaj wartość funkcji celu i ; jeśli , to wykluczamy segment , ujmujmy to ; jeśli , to wykluczamy segment i , ujmujmy to to znaczy tworzymy nowy segment badania. Obliczamy L = b - a jeśli jeśli nie, wróć ponownie na początek.

Algorytm ten jest iteracyjny, dlatego warunek zakończenia procesu iteracyjnego jest zazwyczaj wybierany to znaczy zwężenie segmentu jest wykonywane do momentu, gdy jego wartość zmniejszy się do podanego błędu obliczeniowego . Algorytm metody reprezentacji na ryc. 13.8

Rysunek 13.8 - Schemat algorytmu metody połowicznego podziału

Ta metoda jest bardzo skuteczna.

13.3 Metoda dychotomii

Obliczenie funkcji celu w dwóch punktach w przedziale niepewności umożliwia jej zawężenie. Możesz więc wybrać te punkty, aby przedział niepewności był minimalny. Na rys. 13.9 pokazuje symbole używane w tym schemacie.

Rysunek 13.9 - Notacja używana w metodzie dychotomii

Jeśli wartość funkcji celu dla x1 jest większa niż dla x2, nowy przedział niepewności jest równy Z1 = z1 + z2 . W przeciwnym razie jest zdefiniowane przez wyrażenie Z2 = z2 + z3 . Zadaniem jest jednoczesne zminimalizowanie Z1 i Z2 poprzez spełnienie warunków

z1 + z2 + z3 = z,

z1> 0,

z2> 0,

z3> 0.

Z równości można wykluczyć z2. Potem

Z - z3 = min, Z - z1 = min .

Ponieważ podano wartość Z , prawe części tych równań będą mniejsze niż większe z1 i z3 . Optymalność spełnia więc warunek

z1 = z3 = 0,5Z.

Ale potem z2 = 0 , co przeczy warunkowi z2> 0 .

Rysunek 13.10 - Metoda dychotomii

Niech z2 ma jakąś bardzo małą wartość . Następnie z1 i z3 są odejmowane od . W rezultacie, po obliczeniu pierwszej pary wartości funkcji celu przy wartościach bliskich x, przedział niepewności jest zawężany, jak pokazano na Rys. 13.10, a współczynnik podziału będzie równy

.

Wewnątrz, na , . W przyszłości, przy użyciu metody dychotomii, operacje te są wykonywane, co jest takie samo, jak przy zastosowaniu metody segmentacji na pół.

13.4 Metoda „złotej sekcji”

Z trzech wartości funkcji celu, które zostały obliczone w przedziale niepewności, tylko dwie są używane w przyszłości, a trzecia nie dostarcza dodatkowych informacji i nie jest wykorzystywana w przyszłości. W metodzie złotej sekcji funkcja celu jest obliczana w punktach przedziału niepewności, które są rozmieszczone tak, że każda obliczona wartość funkcji celu daje nowe przydatne informacje.

Rysunek 13.11 - Oznaczenia stosowane w metodzie złotej sekcji

Istota tej metody jest następująca. Odstęp niepewności jest podzielony na dwie nierówne części, stosunek długości większego segmentu do długości całego przedziału jest równy stosunkowi długości mniejszego segmentu do długości większego segmentu. Na rys. 13.11 pokazuje przedział niepewności Z, który składa się z segmentów z1 i z2, których stosunek jest określony przez zasadę złotej sekcji.

Ponadto z1 + z2 = Z. Z pierwszego równania wypływa . Zastępowanie wartości Z z drugiego równania i dzielenie obu części przez , otrzymamy

Rozwiązując to równanie kwadratowe, znajdujemy dodatnią wartość pierwiastka

Na rys. 13.12 pokazuje podział przedziału niepewności w tym zakresie, a odpowiednie wartości funkcji celu są wykreślone, co pozwala zmniejszyć przedział niepewności w 1 / 0,618 razy.

Rysunek 13.12 - Metoda złotej sekcji

Na tym etapie zalety metody złotej sekcji w porównaniu z metodą dychotomii nie są jeszcze widoczne, ale są one wyraźnie widoczne w kolejnym podziale przedziału, ponieważ okazuje się, że jedna z wartości funkcji celu, która musi być obliczona w następnym kroku, jest już znana. Dlatego, aby zmniejszyć niepewność o 1 / 0,618 razy, konieczne jest dalsze obliczenie tylko jednej wartości funkcji celu w punkcie, który jest określony przez zasadę złotej sekcji.

Przy n> 2 efektywność metody złotej sekcji jest wyższa niż dychotomii, ponieważ przy każdym kolejnym obliczeniu funkcji celu przedział niepewności zmniejsza się o 1 / 0,618 razy. Po obliczeniu N wartości funkcji docelowej współczynnik fragmentacji przedziału niepewności wynosi

f = 0,618 N-1.

Metoda złotej sekcji pozwala zauważyć interesujący wzór: największą redukcję następujących przedziałów niepewności uzyskuje się przy obliczaniu funkcji celu w punktach w równych odległościach od jej środka. Jeśli będziemy kontynuować w ten sposób i za każdym razem, obliczając funkcję celu, aby zmniejszyć przedział niepewności, następujące relacje będą sprawiedliwe:

ZJ-2 = ZJ-1 + ZJ, 1

gdzie ZJ jest długością przedziału niepewności po obliczeniu J-tej funkcji celu.

Na rys. 13.13 przedstawia algorytm wyboru następnego punktu wyszukiwania. Określona dokładność może oczywiście zmienić wartość wyboru. Dla funkcji , wyszukiwanie miało miejsce w zakresie (0, 2).

Rysunek 13.13 - Kolejność etapów wyboru następnego punktu wyszukiwania

Prawdziwe minimum to 1.76322211, gdzie wartością funkcji jest -0, 0972601313.

Rysunek 13.14 - Schemat algorytmu metody „złotej sekcji”

Podczas opracowywania programów do rozwiązywania problemów z optymalizacją jednoparametrową używane są następujące zależności:

13.5 Metoda Fibonacciego

Załóżmy, że musisz określić minimalną funkcję celu tak dokładnie, jak to możliwe, to znaczy z najmniejszym możliwym przedziałem niepewności, ale można to wykonać tylko funkcja obliczeniowa. Jak wybrać punkty, w których funkcja jest obliczana? Na pierwszy rzut oka wydaje się jasne, że nie należy szukać rozwiązania dla wszystkich punktów uzyskanych w wyniku eksperymentu. Przeciwnie, musimy starać się, aby wartości funkcji uzyskane w poprzednich eksperymentach określały położenie następujących punktów. W rzeczywistości, znając wartość funkcji, mamy zatem informacje o samej funkcji i pozycji jej minimum, a my wykorzystamy tę informację w kolejnym wyszukiwaniu.

Załóżmy, że istnieje przedział niepewności i znać wartość funkcji wewnątrz tego przedziału (patrz Rysunek 13.15).

Rysunek 13.15 - Unimodalna funkcja celu. Geometryczna interpretacja metody Fibonacciego

Jeśli możesz obliczyć funkcję tylko raz w punkcie , to gdzie powinieneś umieścić punkt , w celu uzyskania najmniejszego możliwego przedziału niepewności?

Przypuśćmy i i , jak pokazano na rys. 13.15, a te wartości zostaną ustalone, jeśli są znane i . Jeśli jest w zasięgu wtedy:

1. Jeśli , wtedy będzie nowy przedział niepewności długość .

2. Jeśli , wtedy będzie nowy przedział niepewności długość .

Ponieważ nie wiadomo, która z tych sytuacji nastąpi, wybierzemy w taki sposób, aby minimalna długość była jak największa i . Możesz to osiągnąć, wykonując długość i nawet, to znaczy, umieszczając go wewnątrz przedziału symetrycznie względem punktu , który jest już w przedziale. Każda inna pozycja punktowa może prowadzić do tego, że wynikowy interwał będzie większy . Umieszczając symetrycznie względne , nie mamy żadnego ryzyka.

Jeśli okaże się, że można wykonać inne obliczenie funkcji, należy zastosować procedurę opisaną w interwale , która ma już wartość funkcji obliczonej w punkcie . Tak więc strategia jest jasna od samego początku. Konieczne jest symetryczne umieszczenie następnego punktu wewnątrz przedziału niepewności względem punktu, który już tam jest. Paradoksalnie jednak, aby zrozumieć, jak rozpocząć obliczenia, konieczne jest zrozumienie, w jaki sposób należy je wykonać.

W n-tej kalkulacji n-ty punkt musi być umieszczony symetrycznie względem ( - 1) punkty. Pozycja tego ostatniego punktu w zasadzie zależy od nas. W celu uzyskania największej redukcji interwału na tym etapie konieczne jest podzielenie poprzedniego interwału na pół. Więc o to chodzi zbiegnie się z punktem . Nie otrzymujemy jednak żadnych nowych informacji. Zwykle punkty i są oddalone od siebie, aby określić, w której połowie, w lewo lub w prawo, występuje przedział niepewności. Znajdują się w pewnej odległości po obu stronach środka segmentu ; możesz niezależnie ustawić wartość lub wybierz tę wartość równą minimalnej możliwej odległości między dwoma punktami. (Załóżmy, że w naszym przykładzie inżynier może regulować temperaturę w odstępie 1 ° C .)

Przedział niepewności będzie miał długość w konsekwencji (Rys. 13.16, dolna część).

Rysunek 13.16 - Geometryczna interpretacja iteracyjnego procesu Fibonacciego

Na poprzednim etapie wskazuje i należy umieścić symetrycznie wewnątrz przedziału za pomocą na odległość od końca tego przedziału. Więc (Rys. 13.16, środkowa część).

Uwagi Ze zdjęcia widać, że na przedostatnim etapie pozostaje jako punkt wewnętrzny.

Podobnie

. (Rys. 13.16, górna część)

W ogólnym przypadku