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

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

Warianty tytułu

EN

Minimization of communication between subpopulations and selection of initial population for local genetic algorithms

• Języki publikacji: PL

Abstrakty

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.

Słowa kluczowe

PL

lokalne algorytmy genetyczne; równoległość; komunikacja; populacja początkowa

EN

local genetic algorithm; communication; initial population; parallel algorithms

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2000
• Tom: T. 12, z. 1
• Strony: 17--36

Twórcy

autor

Jasińska-Suwada A.

autor

Dzwinel W.

autor

Łagudza M.

• Uczelniane Centrum Komputerowe Wydział Fizyki Technicznej i Modelowania Komputerowego Politechnika Krakowska ul. Podchorążych 1 30-084 Kraków