Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: stochastical methods

Sortuj według:

Ogranicz wyniki do:

Metoda ewolucyjna jako narzędzie przeszukiwania przestrzeni Banacha

Arabas J.

Prace Naukowe Politechniki Warszawskiej. Elektronika

2005

z. 152

3--136

Praca stanowi próbę scharakteryzowania ewolucyjnej metody przeszukiwania przestrzeni Banach. Algorytm metody ewolucyjnej (algorytm ewolucyjny-AE) jest modelowany jako proces losowy - ciąg zmiennych losowych, których realizacjami są kolejne populacje punktów z przestrzeni poszukiwań. Uwagę skupiono na analizie rozkładów kolejnych zmiennych losowych tego procesu nazywajac te rozkłady rozkładami próbkowania. Zamierzeniem autora było prowadzenie rozważań na możliwie najwyższym poziomie ogólności, tak aby wskazać specyfikę sposobu poszukiwania przestrzeni charakterystyczną dla metody ewolucyjnej, nie przesłaniając jej szczegółowymi rozwiązaniami. Przyjęcie takiej zasady umożliwia jednolite spojrzenie na właściwości operacji przekształcających: perturbacji i rekombinacji, wykorzystywanych w różnych przestrzeniach przeszukiwań. Chcąc uczynić rozważania o rozkładzie próbkowania bardziej czytelnymi, starano sie stosować konsekwentnie notację dla przestrzeni R(n) i rozkładów zdefiniowanych w tej przestrzeni (ciągłych i dyskretnych), charakteryzowanych za pomocą funkcji gęstości prawdopodobieństwa. Na charakterystyke metody ewolucyjnej składają się zaróno elementy analizy działania AE, jak i zagadnienia metodologiczne, związane z rozwiązywaniem zadań praktycznych o właściwej im specyfice. W zakresie analizy sposobu działania AE, ograniczono się do AE z reprodukcją proporcjonalną i sukcesją prostą. Powodem była względna dostępność w literaturze przedmiotu wyników badań dotyczących tej klasy algorytmów. Praca stanowi próbę dyskusji z otrzymanymi wcześniej wynikami i uzupełnienie ich o rozważania autorskie. Wskazano na ograniczone niekiedy znaczenie praktyczne uzyskanych dotychczas wyników teoretycznych. Uogólniono twierdzenie o asymptotycznej poprawności AE na dowolne przestrzenie Banacha. Podano również jego drugą wersję, uwzględniając możliwość kumulacji przez AE niewielkich zmian rozwiązania mogących pogarszać jego jakość, lecz zarazem pozwalających na opuszczanie obszaru przyciągania ekstremum lokalnego funkcji celu. W pracy udowodniono na prostych przykładach, że mimo asymptotycznej poprawności AE, nie sposób traktować go jako algorytmu wykazującego zbieżność według rozkładu do takiego rozkładu, którego maksima globalne pokrywają się z odpowiednimi ekstremami globalnymi funkcji cdelu. Można przypuszczać, że jeśli AE wykazuje zbieżność według rozkładu, to kształt rozkładu granicznego zależy od przyjętego sposobu perturbacji i nie musi wykazywać cech pokrywania się jego maksimów z ekstremami funkcji celu. W ten sposób AE prowadzi do rozwiązań odpornych na niedokładność wykonania ( co może być istotne np. w zadaniach projektowania), uwzględnianą przez definicję rozkładu perturbacji. Ze względu na dostosowanie do formalizmu matematycznego, analiza teoretyczna rozkładu próbkowania jest z konieczności prowadzona dla modelu AE z populacjami zawierajacymi nieskończoną liczbę elementów. Uproszczenie takie umożliwia wprawdzie analizę, jednakże w ten sposób umykaja zjawiska specyficzne dla populacji o skończonej licznosci. W pracy zilustrowano eksperymentalnie dwa czynniki wpływające na szybkość generowania i jakość uzyskiwanych rozwiązań, a mianowicie sposób inicjowania populacji bazowej (rozważając różne siatki), a także liczność populacji bazowej. W tym drugim przypadku udało się potwierdzić pogląd o większej efektywności przeszukiwania AE z niewielką populacją bazową. Pogląd ten w literaturze przedmiotu podziela tylko niewielu autorów. W pracy podjęto próbę systematyzacji metodyki zastosowania AE w zadaniach praktycznych, kładąc szczególny nacisk na metody uwzględniania nierównościowych ograniczeń funkcyjnych. Algorytm ewolucyjny, z racji swej prostoty, jest chętnie łączony z charakterystycznymi dla rozwiązywanego zadania metodami optymalizacji lokalnej. Techniki takiej hybrydyzacji były również przedmiotem rozważań. Dostępna literatura z zakresu zastosowań praktycznych ogranicza się zazwyczaj do zagadnień eksperymentalnych, dlatego w pracy rozwijano analizę rozkładu próblowania dla AE wzbogaconego o różne techniki uwzględniania ograniczeń. W pracy starano się uogólnić doświadczenia autora nabyte w wyniku prób zastosowania AE do specyficznych zadań projektowania. W rozdziale kończącym zasadniczą część pracy są przedstawione trzy takie wybrane zastosowania. Na przykładach tych nie tylko zilustrowano prezentowaną metodykę i operacje przekształcające dostosowane do zadania, lecz takze dokonano eksperymentalnego porównania AE i niektórych innych technik optymalizacji.

This monograph attempts to characterize the evolutionary algorithm (EA) as a search method operating in a Banach space. EA is modeled as a random process - a series of random variables, each of them characterized by a probability distribution, called a sampling distribution - SD. Base populations in subsequent iterations of an EA are multiple samples derived according to the sampling dustribution. Characterization of the EA and the definition of the SD are given in section 1. Sections 2,3 present the dynamics of the SD using the EA model with infinite population size. Special attention is given to the unexpected behavior of the SD, i.e. preference of the localmaximum to the local maximum. Some effects which are invisible within the infinite population size model are also discussed, in particular the dependence of the algorithm`s robustness to local maxima on the population size and the population initialization method. Asymptotic correctness of the EA is proved using weaker assumptions than usually used in the literature about the probability distribution of the perturbation process. Sections 4,5 concentrate on vatious practical aspects of applying an EA to realistic optimization task. In particular, methods of handling constraints and issues of hybridization of EA with local optimization methods are extensively discussed. A framework methodology of applying an EA to practical problem is defined and illustrated with three cases study problems based on the author`s previous experience.