Wyniki wyszukiwania - BazTech

1

Identification of a fitness function via a dynamical system generated by phenotypic evolution

Karcz-Dulęba I.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2009

|

z. 169

87-94

EN

Studies of a dynamical system model generated by a phenotypic evolution may be exploited to identify an unknown fitness function of a black-box" type. Depending on a fitness function itself and a standard deviation of mutation, the system converges either to stable fixed points or demonstrates a periodic and/or chaotic behavior. Stable fixed points locate fitness optima while the unstable behavior may indicate asymmetry of the function. A family of bimodal tent functions are analyzed with their parameters varied, in order to gain knowledge about their optima positions and heights, saddles widths and levels.

2

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

PL

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.

EN

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.

3

Adaptation Cost: what is the Repayment Time for the Evolutionary Saddle Crossings?

Galar R., Karcz-Dulęba I., Łojek R.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2007

|

z. 160

91-98

EN

It is usual to asses alternative optimization search algorithms in terms of the number of trials necessary to approach the optimum. In case of adaptive algorithms implemented in the real systems such assesment seems inadequate, as the loss of quality due to the exploration of the vicinity of the identified optimum should be also taken into account. We try to evaluate this aspect of adaptive search in the case of a path dependent evolution with proportional selection and normally distributed mutations, which involves saddle crossing in a bimodal adaptative landscape.

4

Identification of cyclic and chaotic behavior in a dynamical system generated by phenotypic evolution

Karcz-Dulęba I.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

195-202

EN

A discrete deterministic dynamical system generated by the expected value derived from the model of phenotypic evolution is considered. Depending on fitness functions and a standard deviation of mutation, the system converges not only to stable fixed points but also displays cyclic and chaotic behavior. To detect the phenomena an auto-correlation function, a phase space portrait and a power spectrum of trajectories of the system were exploited.

5

Time to the convergence of evolution in the space of population states

Karcz-Dulęba I.

International Journal of Applied Mathematics and Computer Science

|

2004

|

Vol. 14, no 3

279-287

EN

Phenotypic evolution of two-element populations with proportional selection and normally distributed mutation is considered. Trajectories of the expected location of the population in the space of population states are investigated. The expected location of the population generates a discrete dynamical system. The study of its fixed points, their stability and time to convergence is presented. Fixed points are located in the vicinity of optima and saddles. For large values of the standard deviation of mutation, fixed points become unstable and periodical orbits arise. In this case, fixed points are also moved away from optima. The time to convergence to fixed points depends not only on the mutation rate, but also on the distance of the points from unstability. Results show that a population spends most time wandering slowly towards the optimum with mutation as the main evolution factor.

6

Asymptotic behaviour of a discrete dynamical system generated by a simple evolutionary process

Karcz-Dulęba I.

International Journal of Applied Mathematics and Computer Science

|

2004

|

Vol. 14, no 1

79-90

EN

A simple model of phenotypic evolution is introduced and analysed in a space of population states. The expected values of the population states generate a discrete dynamical system. The asymptotic behaviour of the system is studied with the use of classical tools of dynamical systems. The number, location and stability of fixed points of the system depend on parameters of a fitness function and the parameters of the evolutionary process itself. The influence of evolutionary process parameters on the stability of the fixed points is discussed. For large values of the standard deviation of mutation, fixed points become unstable and periodical orbits arise. An analysis of the periodical orbits is presented.

7

Evolution of two-element population in the space of population states : equilibrium states for asymmetrical fitness functions

Karcz-Dulęba I.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2002

|

z. 139

35--46

EN

The analysis of a population in a factor space of population states sheds light on the dynamics of reaching the equilibrium state. The evolution of states follows two phases: the fast concentration of the population and a slow movement of the almost homogenous population towards the optimum. The location of equilibrium states depends on the fitness functions. For asymmetrical fitness functions, the same phenomena as for symmetrical ones are observed: the number of fixed points depends on the modality of the fitness function, there are stable and unstable fixed points. The latter ones appear when the standard deviation of mutation was increased.

8

The Cantor set generated by a simple evolutionary model

Karcz-Dulęba I.

Zeszyty Naukowe Uniwersytetu Jagiellońskiego. Prace Informatyczne

|

2000

|

z. 10

29-36

EN

Distributions of traits in a population provide important information about evolution of the population itself. In this paper an analysis of traits distributions in a phenotypic evolution is presented. A very simple model of evolution is under consideration - infinite populations evolve in one dimension space of a bimodal fitness function. The analysis of dynamic behavior of a population yields an interesting result concerning generation of the subsequent distributions. It appears that every normal distribution generates two offspring normal distributions. The evolutionary process initialized with a single normal distribution grows up to 2t normal distributions after t generations. The evolution of normal distributions is described equivalently by evolution of their parameters: means and variances. The evolution of distributions' means resembles fractals generated by an Iterated Function System (IFS). Equations describing the location of distrbutions' means in the next generation define contractive affine transformations. The defined iterative system maps the interval [0,1] into the Cantor set after infinite number of iterations.