Wyniki wyszukiwania - BazTech

1

Enhancing island model genetic programming by controlling frequent trees

Ono Keiko, Hanada Yoshiko, Kumano Masahito, Kimura Masahiro

Journal of Artificial Intelligence and Soft Computing Research

|

2019

|

Vol. 9, No. 1

51--65

EN

In evolutionary computation approaches such as genetic programming (GP), preventing premature convergence to local minima is known to improve performance. As with other evolutionary computation methods, it can be difficult to construct an effective search bias in GP that avoids local minima. In particular, it is difficult to determine which features are the most suitable for the search bias, because GP solutions are expressed in terms of trees and have multiple features. A common approach intended to local minima is known as the Island Model. This model generates multiple populations to encourage a global search and enhance genetic diversity. To improve the Island Model in the framework of GP, we propose a novel technique using a migration strategy based on textit frequent trees and a local search, where the frequent trees refer to subtrees that appear multiple times among the individuals in the island. The proposed method evaluates each island by measuring its activation level in terms of the fitness value and how many types of frequent trees have been created. Several individuals are then migrated from an island with a high activation level to an island with a low activation level, and vice versa. The proposed method also combines strong partial solutions given by a local search. Using six kinds of benchmark problems widely adopted in the literature, we demonstrate that the incorporation of frequent tree information into a migration strategy and local search effectively improves performance. The proposed method is shown to significantly outperform both a typical Island Model GP and the aged layered population structure method.

2

EASEA : a generic optimization tool for GPU machines in asynchronous island model

Baumes L. A., Kruger F., Collet P.

Computer Methods in Materials Science

|

2011

|

Vol. 11, No. 3

489-499

EN

Very recently, we presented an efficient implementation of Evolutionary Algorithms (EAs) using Graphics Processing Units (GPU) for solving microporous crystal structures. Because of both the inherent complexity of zeolitic materials and the constant pressure to accelerate R&D solutions, an asynchronous island model running on clusters of machines equipped with GPU cards, i.e. the current trend for super-computers and cloud computing, is presented. This last improvement of the EASEA platform allows an effortless exploitation of hierarchical massively parallel systems. It is demonstrated that supra-linear speedup over one machine and linear speedup considering clusters of different sizes are obtained. Such an island implementation over several potentially heterogeneous machines opens new horizon for various domains of application where computation time for optimization remains the principal bottleneck.

PL

W swojej poprzedniej pracy Autorzy przedstawili wydajną implementację Algorytmów Ewolucyjnych (ang. Evolutionary Algorithms - EA) z zastosowaniem procesorów graficznych (Graphics Processing Units GPU) do rozwiązywania struktur krystalicznych z mikroporami. Ze względu na skomplikowanie materiałów zeolitycznych oraz ciągłą presję na poprawę efektywności symulacji, w niniejszej pracy zaproponowano asyn-chroniczny model wyspowy na klastrach maszyn wyposażonych w karty GPU. Jest to najnowszy trend w zakresie superkomputerów oraz obliczeń w chmurze (ang. cloud computing). To ostatnie usprawnienie platformy EASEA (ang. EAsy Specification of Evolutionary Algorithms) łatwa specyfikacja algorytmów ewolucyjnych) pozwala na łatwą eksploatację rozbudowanych systemów (komputerów) masowo równoległych. Pokazano, że można osiągnąć ponadliniowe przyspieszenie w stosunku do jednej maszyny oraz liniowe przyspieszenie stosując klastery o różnych rozmiarach. Takie implementacje wyspowe dla kilku potencjalnie heterogenicznych maszyn otwiera nowe perspektywy dla różnych obszarów zastosowań, w których czasy obliczeń odgrywają kluczową rolę.

3

Zastosowanie algorytmów rojowych w rozwiązywaniu zagadnień permutacyjnych

Chmiel W., Kadłuczka P., Packanik G.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2011

|

T. 15, z. 2

117-126

PL

W artykule przedstawiono wyniki badań nad zastosowaniem algorytmów rojowych w optymalizacji zagadnienia szeregowania zadań, jako przykładu AP-trudnego zagadnienia optymalizacyjnego. W oparciu o instancje testowe dla zagadnienia szeregowania zadań zaproponowane przez E. Taillarda, przeprowadzono eksperymenty obliczeniowe, porównując wyniki otrzymywane przez algorytm ptasi oraz algorytm pszczeli. Przebadano także wpływ implementacji poszczególnych elementów algorytmów, takich jak liczba, dokładność i sposób przeszukiwania otoczenia rozwiązań obiecujących, na uzyskiwane wyniki optymalizacji. Pozwoliło to na sformowanie ogólnych wniosków dotyczących własności obu algorytmów.

EN

The objective of this paper is to examine the most important properties of a multi-population genetic algorithm. These elements include: connection topology, migration size, migration interval and a method for migrant selection. A short review of the existing papers on multi-population algorithms is presented. A new diversity measure that applies to permutation encoding is introduced. The proposed measure has proved effective in helping to retain balance between population diversity and convergence. A multi-population genetic algorithm, with different parameters like type of topology, migration interval, migration size and selection method was tested against several different test instances of traveling salesman problem, that belongs to the NP-hard permutational problem class.

4

Efektywność wielopopulacyjnego algorytmu ewolucyjnego dla zagadnień permutacyjnych

Filipowicz B., Chmiel W., Dudek M., Kadłuczka P.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2011

|

T. 15, z. 2

147-158

PL

W artykule przedstawiono wyniki badań najistotniejszych elementów wielopopulacyjnego algorytmu ewolucyjnego. W zastosowanym modelu wyspowym należą do nich: topologia połączeń, rozmiar i częstotliwość migracji oraz metoda selekcji migrantów. Zaproponowana miara różnorodności populacji może być wykorzystywana dla szerokiej klasy zagadnień permutacyjnych, których przykładem jest rozważane zagadnienie komiwojażera (TSP). Badania eksperymentalne przeprowadzono dla standardowych zagadnień testowych zaczerpniętych z biblioteki TSPLib95.

EN

The objective of this study is to examine the most important traits of a multi-population genetic algorithm. These elements include: connection topology, migration size, migration interval and migrant seleetion method. A review of the existing papers on multi-population algorithms is presented. A new diversity measure that applies to permutation encoding is introduced. It has proved effective in helping to retain balance between population diversity and convergence. For each trait, several algorithm configurations have been tested. Every configuration was tested against 25 different test instances, which were derived from the TSPLib95 library. Test results showed that, among the tested parameters, the most important was topology. Of the eleven topologies, a circular (ring) topology consisting of 16 islands obtained the best results. Varying of migration interval showed little correlation with the solution quality, but it did affect the convergence time. In comparison to other parameters, migration size exerts a relatively strong influence on performance. Moreover, a medium migration size proved to be reasonable. Among migrant selection methods, random selection outperformed these methods that exert selective pressure.

5

Layout of functional modules and routing for preliminary design of automatic teller machines

Inoue K., Masuyama T., Osaki H., Ito T.

Journal of Automation Mobile Robotics and Intelligent Systems

|

2007

|

Vol. 1, No. 4

30-40

EN

In this study we address the preliminary design for the module layout and bill conveyance routes of automatic teller machines (ATMs). We determine a two-dimensional layout for the modules as below that are approximately rectangular if the ATM is viewed from the side. ATMs require the compact placement of modules within the chassis and conveyance routes that smoothly circulate bills. However, the intersection and overlapping of routes by which the bills are conveyed in opposite directions are not allowed. Applying the bottom-left method and route-design-oriented packing method to the layout of the modules and the direction-oriented maze routing expediting branching and interflow of routes to the bill conveyance route, the application orders are optimized simultaneously using genetic algorithms (GAs). Results show that suitable designs for the ATM including the case when modules are selected as well as placed are achievable using the above simultaneous optimization. The design intention is expressible by changing the weights associated with chassis dimensions, route lengths and the number of route bends, which compose the objective function. The proposed method is useful for efficiently advancing the preliminary design of ATMs. Finally, if island models pursuing individual targets are used along with a GA, the design becomes even more efficient.