Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: adaptacja lokalna i globalna

Sortuj według:

Ogranicz wyniki do:

Dynamika adaptacji ewolucyjnych metod fenotypowych

Karcz-Dulęba I.

Prace Naukowe Instytutu Informatyki, Automatyki i Robotyki Politechniki Wrocławskiej. Monografie

2008

Vol. 30, Nr 106

156--156

W dysertacji przedstawiono rezultaty analizy teoretycznej metody poszukiwań ewolucyjnych z miękką selekcją. Metoda bazuje na prostym modelu darwinowskiej ewolucji fenotypowej działającej z selekcją proporcjonalną i mutacją gaussowską (z rozkładem normalnym). Połączenie obu mechanizmów reprodukcji powoduje, że ewoluujące populacje są w stanie eksplorować nieograniczone wielowymiarowe rzeczywiste przestrzenie w poszukiwaniu wyższych przystosowań funkcji celu. Algorytmy optymalizacyjne implementujące metodę mają pożądane w optymalizacji właściwości: zdolność przekraczania siodeł pomiędzy optimami funkcji celu, a tym samym znajdowania optimów globalnych, niewielki spadek efektywności wraz ze wzrostem wymiarowości przestrzeni poszukiwań oraz małą wrażliwość na niedokładności i zaszumienia w odczycie wartości funkcji celu. Zaprezentowano analizę teoretyczną dynamiki ewoluujących populacji dla skrajnych liczebności populacji: nieskończonych i dwuelementowych, w jednowymiarowych rzeczywistych przestrzeniach poszukiwań bez ograniczeń. Wyniki teoretyczne uzyskano, jak do tej pory, tylko przy tych upraszczających założeniach, ponieważ metody ewolucyjne są skomplikowanymi nieliniowymi procesami stochastycznymi. Badano zarówno dynamikę lokalną - przy poszukiwaniu jedynego optimum jednomodalnych funkcji celu, jak i globalną - gdy funkcja celu była wielomodalna. Dla jasności wywodu w przypadku dynamiki globalnej ograniczono się głównie do funkcji dwumodalnych i analizy mechanizmu przejścia siodła pomiędzy optimami, aczkolwiek niektóre badania rozszerzono na funkcje o więcej niż dwóch optimach. Nieskończone populacje scharakteryzowano za pomocą rozkładów cech i opisano przez funkcje gęstości prawdopodobieństwa rozkładu osobników z daną cechą. Ustalono, że dla Instytut Informatyki, Automatyki i Robotyki Politechniki Wrocławskiej, ul. Janiszewskiego 11/17, 50-372 Wrocław. jednomodalnych funkcji celu populacja dąży do stanu równowagi wokół optimum, a jej rozkład jest normalny. Nieskończone populacje są więc zbieżne według średniej i z prawdopodobieństwem do optimum jednomodalnej funkcji celu. Dla funkcji wielomodalnych rozkład nieskończonych populacji jest mieszaniną rozkładów gaussowskich, których parametry określono. Rozkład sumaryczny mieszaniny jest przesunięty w stronę optimum globalnego. Jego wartość oczekiwana leży w pobliżu optimum globalnego, w odległości zależnej od wariancji mutacji. Symulacyjnie zbadano wpływ postaci funkcji celu oraz parametrów procesu ewolucyjnego na rozkłady populacji. Analizę dwuelementowych populacji przeprowadzono w przestrzeni stanów populacji, w której każdy punkt odpowiada całej populacji. Obliczono wartości oczekiwane stanów populacji, które generują dwuwymiarowy dyskretny układ dynamiczny. Głównym przedmiotem zainteresowań były trajektorie oraz zachowania asymptotyczne układu. Analizowano liczbę i położenie punktów stałych oraz określono warunki ich stabilności. Badano obszary przyciągania punktów stałych oraz szybkość zbieżności do nich. Liczba punktów stałych układu zależy od modalności funkcji celu, a także od wartości odchylenia standardowego mutacji. Punkty stałe są zwykle położone w pobliżu optimów funkcji celu i siodeł pomiędzy optimami. Udowodniono, że punkty stałe leżące w pobliżu siodeł są niestabilne. Stabilne punkty stałe położone w pobliżu optimów mogą stracić stabilność dla dużych wartości odchylenia standardowego mutacji. Pojawiają się wtedy orbity periodyczne. Dla niesymetrycznych funkcji celu obserwowano ciąg bifurkacji podwajania okresu prowadzący do zachowań chaotycznych. Zachowania chaotyczne badano następującymi metodami: wykresów fazowych, widma mocy, funkcji autokorelacji oraz wykładników Lapunowa. Uzyskane rezultaty badań dynamiki nieskończonych i dwuelementowych populacji wykorzystano do analizy innych aspektów działania metod ewolucyjnych. Badano wpływ różnych mechanizmów ewolucyjnych: selekcji, rekombinacji i mutacji, na różnorodność populacji. Wyniki symulacyjne potwierdziły wcześniejsze obserwacje dotyczące zmian różnorodności populacji w trakcie procesu ewolucyjnego. Początkowo znacznie rozproszone populacje szybko się skupiają, a początkowo jednorodne populacje zwiększają swą różnorodność. W efekcie, populacja w zaledwie kilku generacjach tworzy zwarty klaster osobników o zbliżonych typach. Największy wpływ na zwiększanie lub podtrzymywanie różnorodności populacji ma mutacja. Selekcja i w większości przypadków rekombinacja powodują zmniejszenie rozproszenia. Parametry krytyczne układu dynamicznego, dla których punkty stałe zmieniają stabilność, posłużyły do opracowania heurez dotyczących sposobów doboru parametrów algorytmu ewolucyjnego oraz identyfikacji nieznanej jednowymiarowej funkcji celu. W pracy dokonano także przeglądu znanych w literaturze, a związanych z tematem pracy, sposobów analizy metod ewolucyjnych: modele algorytmów fenotypowych oraz modele wykorzystujące łańcuchy Markowa i teorię układów dynamicznych. Przegląd uzupełniono krótkim opisem innych popularnych sposobów analizy metod ewolucyjnych.

The results of a theoretical analysis of an evolutionary search with the soft selection method are presented. The method is based on a simple model of Darwinian phenotypic evolution operating with proportional selection and Gaussian (normally distributed) mutation. In effect of superposition of both processes, populations could explore unbounded real-valued spaces, “searching” for better adaptations. Computer implementations of the method seem to be the key to the global optimisation in unbounded spaces of search. Especially, they have the ability to cross saddles between optima of a fitness function (thus capability of finding global optima), they display little sensitivity to an increase of the search space dimensionality and the robustness of inaccuracies and noise in a fitness function evaluation. The studied evolutionary process follows a Markov process with uncountable states, thus it is difficult to analyse it theoretically. In order to obtain theoretical results, some simplifying assumptions should be made. Two extremes of the population size are analysed: infinite and two-element ones. The search spaces are one-dimensional and without constraints. The local dynamics - in search of the only optimum of an unimodal fitness, and global dynamics - when a fitness function is multimodal, are studied. In the case of global dynamics, the studies are restricted to bimodal functions and the process of crossing saddle is a main issue. Then, some results are extended to fitness functions with more than two optima. Infinite populations are characterised by the distributions of traits and described by density of trait’s distribution functions. It is shown that for unimodal fitness functions, the distribution is normal and a population converges toward a selection- -mutation equilibrium state close to the optimum. For multimodal fitness functions, the distribution of population is a mixture of Gaussian distributions. Parameters of the mixture and component distributions are described. The influence of a fitness function topology and the parameters of evolutionary process on infinite population distribution is studied. Two-element populations are analysed in the space of population states, where each point corresponds to the whole population. The expected values of population states are calculated. These values generate a two-dimensional discrete dynamical system. Trajectories and asymptotic behaviour of the system are studied. The number and location of fixed points are analysed and the conditions of their stability are given. The number of fixed points depend on the modality of the fitness and on the standard deviation of mutation. Fixed points are usually located in the vicinity of 152 Dynamics of adaptation of phenotypic evolution methods optima and saddles of fitness functions. The basins of attraction of fixed points and the speed of convergence toward the points are studied. Fixed points being close to saddles are unstable. Stable fixed points close to optima can loose their stability at high values of the standard deviation of mutation and then periodical orbits appear. For an asymmetrical fitness, the sequences of double-period bifurcations leading to chaos are observed. Cyclic and chaotic behaviour is analysed using techniques for the dynamical systems’ theory: phase space portraits, auto-correlation function, power spectrum and Lyapunov exponents. The results obtained from the studies of the dynamics of infinite and two-elements populations are applied to investigate different aspects of evolutionary methods. The influence of various evolutionary operators on population diversity is studied. Simulation results confirmed our earlier observations that a population diversity does not change significantly during the evolutionary process. In initially widely distributed populations, the diversity is decreasing while in almost homogeneous populations, the diversity is increasing. As a result, a compact cluster of individuals with similar types drifts through a search space. Critical parameters derived from the dynamical system, for which fixed points change their stability, are used to set parameters of the evolutionary process and to identify unknown one-dimensional fitness functions. The survey of the known literature methods devoted to the theoretical analysis of evolutionary algorithms is also presented in the monograph. The models of phenotypic evolution, models exploiting the Markov chains, the theory of dynamical systems, schemes, etc., are described.