Wyniki wyszukiwania - BazTech

1

The evolutionary heuristics applied to the analysis of multidimensional data

Jasińska-Suwada A.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

163-170

EN

This paper describes the pattern recognition system for analysis of multidimensional data, based on natural meta-heuristics. The system consists of tree modules: preprocessing, feature extraction and clustering. Feature extraction module is based on Molecular Dynamic (MD). In clustering are used two natural methods: Simulated Annealing (SA) and Taboo Search (TS). The system is used to analyze an evolving population of individuals equipped with 'genetic codes'. Clustering module extracts groups of data with similar genetic code named clusters and make of possible to observe their geographical localization. The feature extraction verifies the clustering and allows analyzing of clustering patterns, their shapes and the distances between them.

2

Zastosowanie metod naturalnych w problemach poszukiwania optymalnego rozwiązania

Jasińska-Suwada A., Dzwinel W., Rozmus K., Sołtysiak J.

Computer Science

|

2000

|

Vol. 2

13-51

PL

W artykule przedstawiona została nowa metoda, służąca do rozwiązywania problemów znajdowania najlepszego rozwiązania, bazująca na dynamice cząstek i szeroko stosowanej technice symulacji komputerowej - dynamice molekularnej. Efektywność zaproponowanej metody porównano z wynikami otrzymywanymi dla standardowego algorytmu genetycznego. Dla obu metod przeanalizowano sposoby przeszukiwania przestrzeni rozwiązań, doboru parametrów i zaproponowano heurystyki optymalizacyjne. Efektywność obu metod porównana została w oparciu o zestaw wielomodalnych, wielowymiarowych funkcji testowych, charakteryzujących się zwodniczością. Przeanalizowane zostały indeksy, stanowiące kryterium oceny. Przeprowadzone testy prowadzą do wniosku, że właściwy dobór metody jest zależny od rodzaju problemu. Metoda cząstek jest skuteczniejsza w przypadku badania funkcji o wyraźnie wyróżnionym ekstremum globalnym, natomiast do zwodniczej funkcji, posiadającej kilka lokalnych ekstremów, leżących daleko od globalnego, lepiej nadaje się algorytm genetyczny. Wynika to z charakterystycznych dla obu metod sposobów przeszukiwania przestrzeni rozwiązań. Opisana heurystyka bazująca na dynamice cząstek może być stosowana do wstępnej analizy funkcji, o których przebiegu nic ma żadnych informacji.

EN

In the paper we present a new method, which can be used as a natural solver for searching the best solution in the multidimensional and multimodal parameter space. The method is based on a well-known simulation technique, i.e., molecular dynamics. To show advantages and disadvantages of the particle method in comparison to the standard genetic algorithm, we analyse efficiency of the methods in finding the global minimum of multi-dimensional and multi-modal test-bed functions and we calculate the evaluation indices. We analyse also the ways the solution space is explored and the parameters of algorithms adjusted. The optimal heuristics are proposed. The tests carried out show that the choice of the most appriopriate optimization method depends on type of a problem considered. We show that the particle method is more efficient for finding the optimal solution for multi-modal problems with distinct global extreme, while the genetic algorithm is better for deceptive functions with several locals extreme, which are placed far away from the global optimum. This comes from the different ways in which the particle method and genetic algorithm explore the solution space. The particle method can be used for initial analysis of functions, which character is unknown.

3

Minimalizacja komunikacji pomiędzy subpopulacjami oraz wybór populacji początkowej dla lokalnych algorytmów genetycznych

Jasińska-Suwada A., Dzwinel W., Łagudza M.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2000

|

T. 12, z. 1

17-36

PL

W artykule omawiamy problemy minimalizacji komunikacji pomiędzy subpopulacjami i doboru odpowiedniej populacji początkowej w lokalnych algorytmach genetycznych, w których elementy populacji umieszczone są na dwuwymiarowej siatce, a operacja krzyżowania dozwolona jest jedynie dla sąsiadujących osobników. Algorytmy te pozwalają na rozwiązanie problemów zwodniczych o szeroko rozpiętych, podatnych na rozerwanie schematach. Populacja została podzielona na dwie części przegrodą z oknem umożliwiającym krzyżowanie elementów należących do różnych subpopulacji. Testy wykazały, że szerokość okna w niewielkim stopniu wpływa na efektywność poszukiwania ekstremum. Prowadzi to do wniosku, że dla opisanego algorytmu można znacznie zminimalizować komunikację pomiędzy subpopulacjami. Przedstawiono testy, wykazujące, że specyficzne sposoby przygotowania populacji początkowej mogą istotnie wpływać na uzyskane wyniki. Rozkład "szachownicy" i rozkład dwustronny umożliwiają odnalezienie rozwiązania dla niektórych problemów znacznie efektywniej niż losowa populacja początkowa.

EN

In this paper we are dealing with minimization of the communication between the subpopulations and selection of initial population for local genetic algorithms (LGA). For the LGA individuals are located at the nodes of two-dimensional grid. Crossover operation is allowed only between neighbors. This type of algorithms is suitable for multidimensional, multimodal and deceptive problems with widely spanned schemata, which can be easily disrupted by crossover operation. To minimize the communication between subpopulations in parallel implementation of LGA, the initial population was devided into two parts by the barrier. The "window" in the barrier allowsa for transfer of individuals from different subpopulations. The tests show, that for the narrow window width (25%) the algorithm efficiency is approximately the same as for an "open" subpopulation but enabling the lowest communication rate. The tests show that particular types of initial population affect the efficiency of LGA. The checkerboard and bilateral patterns enable one to find the solution more efficiently than the random population.