Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Archiwum Informatyki Teoretycznej i Stosowanej

1 2000

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: lokalne algorytmy genetyczne

Sortuj według:

Ogranicz wyniki do:

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

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.

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.