Wyniki wyszukiwania - BazTech

1

An improvement of the sequential algorithm for modeling the chain-like-bodies motion

Bartłomiejczyk K.

Journal of Applied Mathematics and Computational Mechanics

|

2018

|

Vol. 17, nr 2

5--16

EN

Numerous simulation studies in statistical physics make use of various algorithms that are designed for modeling of the chain-like-body (CLB) motion. In recent years within this group a new sequential algorithm was proposed. The main idea of this new approach to the algorithmization of the CLB motion is based on the incorporation of the tension propagation mechanism into each simulated move. In this paper, improvement of this algorithm by implementation of the direction-preference-mechanism is proposed. This modification enables one to better mimic the real behavior of the CLB. The impact of the new procedure on the simulation process is studied with the help of metamodels that relate to some important characteristics of the CLB motion with the algorithm’s new parameters.

2

Integracja algorytmów ewolucyjnych z sekwencyjnymi metodami numerycznymi w optymalnym projektowaniu konstrukcji

Krenich S.

Logistyka

|

2014

|

nr 3

3297--3305

PL

Artykuł prezentuje integrację algorytmów ewolucyjnych z algorytmami sekwencyjnymi w celu poprawy lokalnej eksploracji przestrzeni rozwiązań dla problemów jedno i wielokryterialnej optymalizacji konstrukcji. Zaproponowano algorytmy hybrydowe wykorzystujące znane algorytmy sekwencyjne (metodę zmiennej tolerancji, zmiennej metryki, metodę poszukiwań prostych, metodę sympleksu), a dla analizy wielokryterialnej znane podejście Min-Max oraz połączenie algorytmów ewolucyjnych z sekwencyjnymi w sposób umoŜliwiający generowanie pełnego zbioru rozwiązań Pareto optymalnych. W metodzie pierwszej punkty startowe dla algorytmu sekwencyjnego są generowane przez algorytm ewolucyjny zarówno na etapie poszukiwania minimów poszczególnych funkcji kryterialnych, jak i na etapie zastosowania podejścia Min-Max. Metoda druga polega na poprawie uzyskanego algorytmem ewolucyjnym zbioru Pareto przez zastosowanie wielokierunkowego algorytmu sekwencyjnego. W ramach badań wykorzystano kilka typów algorytmów ewolucyjnych połączonych z kilkoma algorytmami sekwencyjnymi. Przeprowadzono eksperymenty obliczeniowe dla wielu problemów, w tym problemu optymalizacji zbiornika powietrza, dwukryterialnej optymalizacji mechanizmu dźwigniowego oraz belki wielostopniowej. Uzyskane wyniki pokazują poprawę efektywność działania algorytmów ewolucyjnych.

EN

In the paper a new hybrid methods to single and multicriteria design optimization are presented. In these methods an evolutionary algorithm is combined with a sequential search method in the way that in each generation, each individual is under a learning process which results from applying several steps of the sequential search method. For the evolutionary part of the method, the constraint tournament selection method is applied here, whereas, for the sequential part, flexible tolerance, variable metrics, Hooke’a-Jeeves direct search and simplex methods are used. In the first approach, the starting points for the sequential algorithm are generated by the evolutionary algorithm, both at the stage of searching minima of each criterion functions, as well as in the application of the approach Min-Max. The second approach is to improve the Pareto set generated using the evolutionary algorithm by applying sequential algorithms. As examples, a numerical problem and three design optimization problems of a robot gripper, a 6-th step beam and a air reservoir are considered. For these examples the comparison between the classical evolutionary algorithm and the proposed approaches show the efficiency of the latter.

3

Sekwencyjne i równolegle algorytmy znajdowania podciągów

Deorowicz S.

Studia Informatica

|

2010

|

Vol. 31, nr 4B

239-239

PL

Pierwsza cześć niniejszej pracy poświęcona jest problemowi najdłuższego podciągu rosnącego (LIS) oraz jego wariantom (podciąg otrzymuje sie z ciągu przez usuniecie zera bądź większej liczby symboli). Problem ten znajduje zastosowania m.in. w bioinformatyce do uliniawiania genomów, wyszukiwania nowych genów. Pierwszym z wariantów problemu LIS rozważanym w niniejszej pracy jest problem podciągów rosnących, które są pod pewnymi względami ekstremalne. Kolejnym wariantem jest problem podciągu rosnącego o zadanym pochyleniu. Dalsze dwa warianty to problemy cyklicznych podciągów rosnących oraz podciągów rosnących w oknie ustalonego rozmiaru ciągu wejściowego. Dla tych ostatnich wariantów zaproponowano w pracy wykorzystanie reprezentacji ciągu za pomocą pokrycia zachłannego oraz opracowano wydajne algorytmy łączenia takich pokryć. Algorytmy te są kluczowe do efektywnego rozwiązywania wspomnianych problemów. Druga cześć pracy dotyczy problemu najdłuższego wspólnego podciągu i jego wariantów. Zastosowania tych problemów są bardzo liczne i dotyczą przede wszystkim porównywania ciągów w celu oceny ich podobieństwa. Dla problemu LCS niezmienniczego względem transpozycji LCTS) zaproponowano kilka algorytmów sekwencyjnych, które, jak wynika z eksperymentów praktycznych, okazały sie znacznie szybsze od algorytmów istniejących. Dla problemu ukierunkowanego LCS (CLCS) zaproponowano algorytmy sekwencyjne, również szybsze od dotychczas istniejących. Ponadto, zaproponowano dla tego problemu pierwszy algorytm równoległości bitowej. Dla problemu scalonego LCS (MerLCS) zaproponowano pierwszy algorytm równoległości bitowej, który w eksperymentach praktycznych okazał sie kilkudziesięciokrotnie szybszy od znanych algorytmów. Dla problemów LCS, LCTS, CLCS zaproponowano także algorytmy równoległe przeznaczone do wykonywania w procesorach graficznych. Dla wszystkich algorytmów proponowanych w niniejszej pracy przeprowadzono analizę złożoności czasowej i pamięciowej w przypadku pesymistycznym(dla niektórych także w przypadku średnim). Dzięki temu często można było wykazać, ze proponowane algorytmy są także najszybsze w sensie asymptotycznym.

EN

The first part of this work is on the longest increasing subsequence problem (LIS) and its variants (a subsequence can be obtained from a sequence by removing zero or more symbols). The problem has applications in bioinformatics, e.g., in sequence alignment, searching new genes. The first variant of the LIS problem, which is considered in this work, is a problem of longest increasing subsequences that are extremal from some point of view. Next variant is a slope-constrained longest increasing subsequence problem. The last two discussed variants of the LIS problem are a longest increasing cyclic subsequence problem (LICS) and a longest increasing subsequence in a sliding window problem (LISW). The algorithms for the recent two problems use cover representation of a sequence. Original algorithms for cover merging are crucial to the proposed algorithms for the LICS and LISW problems. The second part of this work is on the longest common subsequence problem (LCS) and its variants. The applications of these problems are numerous and concentrate mainly on the sequence comparison. For the transposition-invariant LCS problem (LCTS), a few sequential algorithms were proposed. Experiments show that they are much faster than the existing algorithms. For the constrained LCS problem (CLCS), a few sequential algorithms were also proposed. They are faster than the known algorithms. Moreover, for the CLCS problem, the first bit-parallel algorithm was invented. For the merged LCS problem (MerLCS), a bit parallel algorithm, tens times faster than the existing algorithms was proposed. For the LCS, LCTS, CLCS problems also algorithms for graphical processors were invented. All the proposed algorithms were analysed and their time and space complexities in the worst case were determined. For some algorithms the average case was also analysed. Obtained time complexities allow to show that the proposed algorithms are usually faster than the existing algorithms also in an asymptotic sense.

4

Problem gniazdowy z ograniczeniem bez czekania. Równoległe algorytmy tabu

Makuchowski M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 150

175-181

PL

W pracy opisane są równoległe algorytmy poszukiwania z zabronieniami, dedykowane gniazdowemu problemowi z ograniczeniem bez czekania. Proponowane algorytmy zbudowane są z nadrzędnego algorytmu bazującego na wspomnianej technice oraz sterowanego algorytmu konstrukcyjnego. Poszukiwania ograniczone są tylko do rozwiązań możliwych do wygenerowania przez wspomniany algorytm konstrukcyjny. W pracy przedstawia się analizę porównawczą zaproponowanych algorytmów.

EN

This paper deals with parallel tabu search algorithms for a job shop problem with a no-wait constraint and a makespan criterion. The proposed algorithms consist of a master algorithm based on the mentioned technique and slave constructive algorithm. This approach reduces the number of solutions to check only to solutions that can be generated by means of the constructive algorithm. In this paper a comparative analysis of the proposed algorithms is presented.

5

Implicit and explicit constructions of sunny nonexpansive retractions in Banach spaces

Aleyner A., Reich S.

Journal of Mathematics and Applications

|

2007

|

Vol. 29

5-16

EN

Implicit and explicit processes for eonstructing the unique sunny nonexpansive retraction onto the common fixed point set of either a finite or infmite family of nonexpansive mappings in a Banach space are proposed and corresponding convergence theorems are established.

6

Algorytmy radiowego kolorowania grafów

Kubale M., Kosowski A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2002

|

z. 136

133-144

PL

W pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.

EN

The basic principles and features of graph radiocoloring are presented in this paper. Lower and upper bounds for the radiochromatic number of graphs are given, in the general case as well as for paths and cycles. Exact values of the radiochromatic number are given for complete k-parite graphs, wheels and double stars. The paper also contains a comparison of the quality of suboptimal, sequential radiocoloring algorithms having polynomial-time complexity.