DonNTU   Masters' portal

Abstract

Contents

Introduction

Evolutionary Algorithms (EA)[2] - is a stochastic search method that was used to solve many problems of search, optimization and machine learning. Unlike most other optimization techniques, EA test solutions containing population that competitively controlled by means of application of several different operators to search for significant, if not global, optimal solutions. Among the common subclasses EA widely studied genetic algorithms (GAs). Genetic algorithms[1] iteratively train a population of individuals, applying the operator of recombination (combining two or more parents to get one or more children), and mutations of their contents (random change of problem variables). However, if you adhere to the laws of natural evolution, you can not manage a population in which the individual claims to be taken interbreeding with any other partners in the same population (random mating). On the contrary, the view is developed within the community (sub), where there is a structural affinity, and is prone to playing within a subgroup. Among the types of extensions GA particularly popular. Distributed GA (RGA), Distributed evolutionary algorithms - a subclass of parallel genetic algorithms designed to reduce the premature convergence to a local optimum, the stimulation of diversity and alternative solutions to the same problem. They are based on dividing into several separate populations subpopulations, each of which is processed HA independently. Moreover, various individuals generate migration exchange of genetic material among populations which generally improve the accuracy and efficiency of the algorithm Power of evolutionary algorithms enhanced with the use of distributed computing. Here are trying to simulate a natural model of the interaction of individual populations, for the following tasks:

To address these two major problems there is a large number of works presented in the literature.

1. Theme urgency

Recently, the actively developing multi-core computers[4], which have the possibility of multi-threaded computing. When using multi-core systems to effectively use parallelization process[5] for the most productive use of computing power, concerning the use of parallel genetic algorithm seems more productive than using classical genetic algorithm[3].

2. Goal and tasks of the research

The purpose of this paper is to practically implement the concept of a parallel genetic algorithm[6] using freymverka Java concurrent multi-core systems.

Main tasks:

  1. Explore methods of implementation of the parallel genetic algorithm.
  2. Select the method of implementation of the parallel genetic algorithm.
  3. Examine the literature on parallel genetic algorithms.
  4. Implement the learned methods in a software project.

At the present time there are three main types of parallel genetic algorithms (PGA)[8]:

Master-Slave

Model "master - slave" is characterized by the fact that the algorithms of this type of selection takes into account the entire population, in contrast to the other two models. Also worth noting is that it is possible random mating, that is, any two individuals can interbreed, in other models of cross-breeding is limited to strictly defined set of individuals. In the algorithms of the second class, there is the main population, but the evaluation of the objective function is distributed among multiple processors. The owner keeps the population, GA operates and distributes individuals between subordinates. They only estimate the CF individuals. Odnopopulyatsionnye GA suitable for mainstream and parallel computers consist of a single population. Selection and crossing close kinship relations are limited. This class of PHAs can be efficiently implemented on parallel computers. Third grade - GA mnogopopulyatsionnye more complex model, as it consists of several sub-populations that periodically, according to the rules, sharing individuals. This exchange of individuals is called migration and controlled by several parameters. Of the multi-GA is very popular, yet complex enough so as to understand and to implement, because the consequences of the effect of migration, at the moment, is not fully explored. At the same time, of the multi-GA are similar to the "island model" in population genetics, which considers the relatively isolated communities, so that parallel GA in some cases referred to as "island" parallel GA.

Island model

Using a small number of relatively large sub-populations and migration between them - is one of the main characteristics of multi-communal PGA. We can assume that the first systematic study of the parallel GA with many populations of the thesis was R.B.Grosso (Grosso). His goal was to simulate the interaction of parallel sub-components of the evolving population. Thus Grosso simulated diploid individuals (use two subcomponents for each "gene"), and the population was divided into five communities. Each community was exchanged by individuals with all other communities in establishing fixed ratios of migration. By experimenting Grosso has determined that an average improvement of CF population was faster in small communities than in a single population. This confirms the well-established principle in population genetics: the favorable signs spread faster when communities are small than when they are large. However, he also noticed that when communities were isolated, the rapid growth of TF stopped at a smaller value than the population at large. In other words, the quality of the solution found until convergence was worse than in the isolated case than in the single population. At the low rate of migration of the community still behaved (work) independently of each other and exploring different regions of the search space. Workers do not have a significant effect on the behavior of communities and the quality of decisions was comparable with the case where the communities were isolated. However, the average migration rate of population separation has found solutions that are similar to those found for the single population. These observations show that there is a critical value of the coefficient of migration, below which the performance of the algorithm is difficult due to isolation of communities. For the higher-lying values ??of this coefficient divided population finds solutions of the same quality as the conventional single population. Typically, the model developed for clustered architectures that consist of multiple independent workstations with its local memory. In each of these systems is implementing its own copy of the GA (the construction of new generations of populations). At the same genetic parameters of these algorithms must be somewhat different from each other. This will send a search on each of these "island" in a different direction other. After a specified number of iterations of the island are sharing the best individuals that allows you to adjust the search direction for the less fortunate islands. The effectiveness of the parallel GA built on such a scheme, it defines the interaction of components. You can highlight the main features of this exchange:

Note also that although the population evolve independently and equally, in realizations of this type of algorithms is allocated server that initiates work and implements the topology data. Moreover, synchronization of copies of the GA on the islands requires the manner in which they interact. Accurate and correct implementation of the interaction between different copies of the GA model in the islands is a challenge. The popularity of multi-communal parallel GA due to the fact that:

Generalized scheme of the migration pattern of GA you may have seen in Figure 1.

Migration Model GA

Picture 1 – Migration Model GA
(animation: 3 shots, the constant repetition, 150 kb)

Conclusion

The capabilities of modern computing devices can be used at full capacity only in asynchronous models, because the complexity of optimization problems to increase in the need for rapid decision-making company in a difficult economic environment. Due to the need to deepen research in the field of parallel genetic algorithms, the proposed model appears to be very relevant. Genetic algorithms for multi-communal required to investigate the effect of the structure of relations in the work of the parallel GA. In the future we plan to implement hybrid methods in parallel genetic algorithm at different stages of the operation.

This master's work is not completed yet. Final completion: December 2013. The full text of the work and materials on the topic can be obtained from the author or his head after this date.

References

  1. Курейчик В.М., Кныш Д.С. Параллельный генетический алгоритм. Модели и проблемы построения // – С.1 – 3.
  2. Интернет-ресурс. - Режим доступа:www/ URL: http://www.gotai.net/ – сайт по ИИ.
  3. Гладков Л.А., Курейчик В.М., Курейчик В.В. Генетические алгоритмы [Текст]/под ред. В.М. Курейчика . – 2-е издн., испр. и доп. – М.:ФИЗМАТЛИТ ,2006 .-320 с.
  4. Иванов Д.Е., Чебанов П.А. Взаимодействие компонент в распределённых генетических алгоритмах генерации тестов / Д.Е. Иванов, П.А. Чебанов // Наукові праці Донецького національного технічного університету. Серія: “Обчислювальна техніка та автоматизація”. Випуск 16(147).- Донецьк: ДонНТУ.- 2009.- С.121-127.
  5. Grosso P.B. Computer Simulations of Genetic Adaptation: Parallel Subcomponent Interaction in a Multilocus Model// Unpublished doctoral dissertation, The University of Michigan. (University Microfilms №8520908), 1985.
  6. Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование. Обзор // Известия РАН. Теория и системы управления.-2002.-№1.-С.127-137.
  7. SDN for Java Concurrent / Интернет-ресурс. - Режим доступа: http://docs.oracle.com/javase...
  8. Mitchell M. An Introduction to Genetic Algorithms [Текст]/M.Mitchell. — Cambridge: MIT Press, 1999 —158 c. — ISBN 0-262-13316-4 (HB), 0-262-63185-7 (PB).
  9. Java Concurrency in Practice Brian - Goetz, Tim Peierls, Joshua Bloch — Москва: Sun Press, 2012 —983 c. — ISBN 0-262-13316-4 (HB), 63185(P).
  10. Java 2. Библиотека профессионала. Том 1. Основы - Кей С. Хорстманн, Гари Корнелл. - Москва: Sun Press, 2012 —989 c. — ISBN 0-262-13316-4 (HB), 0-262-63185-7 (PB).