Wyniki wyszukiwania - Biblioteka Nauki

1

Heuristic algorithms in topological design of telecommunication networks

100%

Karaś P.

|

tom nr 3

73-82

EN

The paper addresses the generic topological network design problem and considers the use of various heuristic algorithms for solving the problem. The target of the optimisation is to determine a network structure and demand allocation pattern that would minimise the cost of the network, which is given by fixed installation costs of nodes and links and variable link capacity costs described bv linear or concave functions. Input data for the optimisation consists of a list of potential node and link locations and their costs and a set of demands defined between the nodes. Since the problem is known to be NP-hard. The use of specialised heuristic algorithms is proposed. The presented approaches encompass original ideas as well as selected methods described in literature and their enhancements. The algorithms are based on the following ideas and methods: shifting of individual flows, local and global restoration of flows from chosen links or nodes, Yaged algorithm for finding local minima, Minoux greedy algorithm, simulated allocation and genetic algorithms. Efficiency of each of the proposed methods is tested on a set of numerical examples.

2

Zastosowanie algorytmów heurytycznych w systemach sterowania ruchem suwnic

100%

Smoczek J. , Szpytko J.

|

2009

|

tom Z. 12

CD-CD

PL

Przedmiotem artykułu jest wykorzystanie algorytmów heurystycznych w systemach sterowania ruchem suwnic między innymi w celu wyznaczania bezkolizyjnej trajektorii ruchu ładunku przemieszczanego przez urządzenie transportowe w trójwymiarowej przestrzeni roboczej OXYZ. Przedstawione zostało sprzętowo-programowe rozwiązanie układów kontrolno-pomiarowych umożliwiających programową realizację algorytmu wyznaczania bezkolizyjnej i optymalnej z uwagi na czas i drogę trajektorii ruchu, śledzenie zadanej trajektorii ruchu przez mechanizmy ruchu suwnicy oraz pozycjonowanie i tłumienie wahań przemieszczanego w przestrzeni roboczej ładunku.

EN

The aim of the paper is heuristic algorithms applying in control systems of cranes for designing no-collision movement trajectory of the load shifted by transportation device in three-dimensional workspace. In the paper is presented the hardware-software solution of the control-measurement system which enables to realize heuristic algorithm for optimal and no-collision movement trajectory assigning as well as realizes control task, movement trajectory following by crane's mechanisms, a load positioning and swinging reducing.

3

Adaptive improvement of resource utilization in goal-oriented multi-user systems

100%

Młyński M.

Theoretical and Applied Informatics

|

2011

|

tom Vol. 23, No. 1

37-53

EN

The material presents a real problem inherent in the management of computer systems, namely that of finding the appropriate system settings and thus being able to achieve the expected performance. The material also presents a prototype which aims to adapt the system in such a way as to achieve the objective, defined as the application efficiency. The prototype uses a resource-oriented mechanism that is built into the OS Workload Manager and is focused on a proposed goal-oriented subsystem based on fuzzy logic, managing resources to make the best use of them, and pursuing translation to the use of system resources, including nondeterministic technology-related factors such as duration of allocation and release of the resources, sharing the resources with the uncapped mode, and the errors of performance measurement.

PL

Artykuł przedstawia realny problem występującego w zarządzaniu systemami informatycznymi polegający na dynamicznym znajdowaniu odpowiednich ustawień systemu, dzięki którym można osiągnąć oczekiwaną wydajność aplikacji. Utrudnieniem jest kryterium, gdzie rozpatrywana, oczekiwana wydajność aplikacji również zmienia się dynamicznie. Artykuł przedstawia także prototyp, którego celem jest adaptacja systemu w taki sposób, aby osiągnąć cel, zdefiniowany jako wydajność aplikacji. Prototyp wykorzystuje zorientowanego na zasoby (ang. resource-oriented) wbudowanego w system operacyjny zarządcę obciążeniem (ang. Workload Manager), oraz zorientowany na cel (ang. Goal-oriented) autorski podsystem bazujący na logice rozmytej. Opisany autorski program gospodaruje zasobami informatycznymi tak, aby jak najlepiej je wykorzystać oraz realizuje translacje zdefiniowanego celu na zajętość wykorzystywanych zasobów systemowych z uwzględnieniem niedeterministycznych współczynników związanych z technologi˛ takich jak czas na alokację i zwalnianie tych zasobów, ich współdzielenie, oraz błędy pomiarów wydajności. Wyniki badań pokazują, że dzięki zastosowaniu prototypu możliwa jest dynamiczna zmiana celu określonego jako czas odpowiedzi aplikacji a czas znalezienia odpowiednich parametrów mieści się w akceptowalnych granicach mierzonych w sekundach. W artykule przedstawione jest także porównanie przedstawionego prototypu z podobnym, bazującym na koncepcji bazy wiedzy.

4

Heuristic Rating Estimation Approach to The Pairwise Comparisons Method

88%

Kułakowski K.

Fundamenta Informaticae

|

2014

|

tom Vol. 133, nr 4

367--386

EN

The Heuristic Ratio Estimation (HRE) approach proposes a new way of using the pairwise comparisons matrix. It allows the assumption that the weights of some alternatives (herein referred to as concepts) are known and fixed, hence the weight vector needs to be estimated only for the other unknown values. The main purpose of this paper is to extend the previously proposed iterative HRE algorithm and present all the heuristics that create a generalized approach. Theoretical considerations are accompanied by a few numerical examples demonstrating how the selected heuristics can be used in practice.

5

Joint allocation and transportation problem in supply network optimisation

88%

Filcek G.

Management and Production Engineering Review

|

2012

|

tom Vol. 3, No. 3

3-10

EN

The paper concerns joint allocation and transportation as an optimization problem in selected supply networks. The network consists of a set of suppliers of the raw material, a set of production units and a set of product receivers. The raw material is treated as fast perishing good like vegetables or fruits. The production units are described by time models. In the optimization process, the time of the production and cost of the transportation is taken into account. The objective function is in general non-convex function of raw material allocation and transportation plans of the raw material and the product. To solve the problem considered, exact and heuristic algorithms have been developed and presented. To solve convex problems, solver Lingo developed by Lindo systems is proposed. The idea of a computer decision supported system integrating all presented algorithms is presented as well as four numerical examples illustrating some properties of the assumed supply network model.

6

Heuristic algorithms for the optimization of total weighted completion time for asynchronous transmission in a packet data transmission system

88%

Piórkowski A. , Werewka J. , Bielecka M.

|

2014

|

tom Vol. 43, no. 4

507--529

EN

In this paper, the minimization of total weighted completion time (total cost) for asynchronous transmission in distributed systems is discussed. Special attention has been paid to the problem of message scheduling on the sender side. Messages to be sent form a queue, therefore the order in which they are to be sent has to be set. Scheduling algorithms can be chosen to optimize scheduling criteria such as total completion time or total weighted completion time. The message scheduling problem becomes complicated considerably when the transmitted data stream between the sender and the receiver is formed into packets. TheWSPT (Weighted Shortest Processing Time) scheduling rule, which orders messages according to non-decreasing length and weight ratios has been proven to be non-optimal. It has been demonstrated that the problem of minimizing the total weighted completion time is NP-hard. Here, we propose heuristic algorithms for scheduling messages and experimentally evaluate the performance of these scheduling algorithms.

7

Constrained optimization of line-start PM motor based on the gray wolf optimizer

88%

Knypińskia Ł.

Eksploatacja i Niezawodność

|

2021

|

tom Vol. 23, no. 1

1--10

EN

This paper presents the algorithm and computer software for constrained optimization based on the gray wolf algorithm. The gray wolf algorithm was combined with the external penalty function approach. The optimization procedure was developed using Borland Delphi 7.0. The developed procedure was then applied to design of a line-start PM synchronous motor. The motor was described by three design variables which determine the rotor structure. The multiplicative compromise function consisted of three maintenance parameters of designed motor and one non-linear constraint function was proposed. Next, the result obtained for the developed procedure (together with the gray wolf algorithm) was compared with results obtained using: (a) the particle swarm optimization algorithm, (b) the bat algorithm and (c) the genetic algorithm. The developed optimization algorithm is characterized by good convergence, robustness and reliability. Selected results of the computer simulation are presented and discussed.

8

A new elastic scheduling task model in the node of a control and measurement system

88%

Miczulski W. , Powroźnik P.

Metrology and Measurement Systems

|

2013

|

tom Vol. 20, nr 1

87-98

EN

The paper presents a new elastic scheduling task model which has been used in the uniprocessor node of a control measuring system. This model allows the selection of a new set of periods for the occurrence of tasks executed in the node of a system in the case when it is necessary to perform additional aperiodic tasks or there is a need to change the time parameters of existing tasks. Selection of periods is performed by heuristic algorithms. This paper presents the results of the experimental use of an elastic scheduling model with a GRASP heuristic algorithm.

9

Heuristic algorithm to predict the location of C0 separators for efficient isogeometric analysis simulations with direct solvers

88%

Paszyńska A. , Jopek K. , Woźniak M. , Paszyński M.

|

nr 6

10

Optimization of links cost for unicast and anycasttraffic

88%

Gładysz J.

Theoretical and Applied Informatics

|

2011

|

tom Vol. 23, No. 3-4

163-176

EN

This work presents optimization model and computational results of Capacity and Flow Assignment Problem for multilayer networks with unicast and anycast traffic. Capacity of each channel is expressed in a set of link proposal. Anycast is a network addressing and routing methodology in which datagrams from a single sender are routed to the topologically nearest node in a group of potential receivers all identified by the same destination address. We propose two heuristic algorithms based on Flow Deviation and Tabu Search method. The results of algorithms will be compared with optimal solution obtained using CPLEX package. To improve execution time of exact algorithm we introduce cut inequalities. Cut inequalities are added to the optimization problem, enabling the branching phase to use this information in calculation of more effective bounds. Next, we want to examine testing networks depend on different percentage of anycast traffic, number of distribution centers (servers or replicas) and the different size of network (number of nodes, links, routes).

PL

Poniższa praca prezentuje model optymalizacyjny oraz eksperymenty obliczeniowe dla problemu jednoczesnego wyznaczania przepustowości kanałów oraz przepływów unicast oraz anycast. Jako przepustowości kanałów użyte zostaną tzw. przepustowości kandydujące - spośród dostępnych przepustowości w danym kanale wybieramy dokładnie jedną. Takie rozwiązanie przyjęte zostanie w górnej warstwie. W dolnej warstwie będziemy rozważać przepustowości modularne - przepustowość kanału wyrażona jest w ilości modułów potrzebnych do zainstalowania w łączu. Anycast jest nowym rodzajem przepływów w sieciach komputerowych, możliwym do zastosowania w szóstej wersji protokołu IP. Jest to transmisja jeden do wielu, w której użytkownik może wysłać/pobrać dane do jednego spośród serwerów w sieci oferujących daną usługę. W pracy zaproponowane zostały dwa algorytmy heurystyczne. Pierwszy oparty jest o metodę FlowDeviation, drugi na zaproponowanej przez Glovera metodzie Tabu Search. Oba algorytmy zostały wcześniej zaproponowane i opisane przez autora dla przepustowości modularnych. Do znalezienia rozwiązań optymalnych zostanie użyty pakiet programowania liniowego CPLEX. Rozważany problem jest problemem NP.- zupełnym. Oznacza to iż dla dużych sieci komputerowych znalezienie rozwiązania optymalnego może okazać się niemożliwe. Z tego powodu do badanego problemu wprowadzone zostały tzw. funkcje odcinające. Zadaniem funkcji odcinających jest zmniejszenie przestrzeni dopuszczalnych rozwiązań, a co za tym idzie skrócenie czasu poszukiwania rozwiązania optymalnego. Do konstrukcji odpowiednich funkcji odcinających wykorzystywane są właściwości badanego problemu. Zaproponowane funkcje odcinające oraz algorytmy heurystyczne zostały przebadane dla trzech sieci komputerowych. Są to sieci komputerowe o różnej topologii, różnej liczby węzłów oraz połączeń pomiędzy węzłami. Badania miały na celu zbadanie wpływu ruchu anycast w sieci, porównanie czasu rozwiązań optymalnych z zastosowaniem funkcji odcinających oraz ocenę algorytmów heurystycznych. Wyniki przeprowadzonych eksperymentów pokazują, iż zastosowanie przepływów anycast (kosztem unicast) zmniejsza sumaryczny przepływ w sieci przy takim samym strumieniu danych wprowadzanych do sieci. Można to zaobserwować porównując proporcje przepływów unicast oraz anycast. W przypadku badań dotyczących funkcji odcinających można zaobserwować zmniejszenie czasu poszukiwania rozwiązania po dodaniu ograniczenia dotyczącego górnego ograniczenia funkcji kryterialnej. Wartość ta pochodzi z algorytmów heurystycznych. Jest to kolejny powód do dalszych prac nad tymi algorytmami. W badaniach dotyczących algorytmów heurystycznych można zaobserwować iż algorytm FlowDevation znajduje rozwiązanie dopuszczalne w czasie rzędu kilku sekund, jednak jest ono odległe od rozwiązania optymalnego o ok. 7-9%. W przypadku algorytmu Tabu Search otrzymujemy rozwiązanie dopuszczalne odległe od optymalnego o 1-3%, niemniej jednak czas działania algorytmu jest dłuższy i wynosi kilkanaście do kilkudziesięciu sekund. Należy zatem odpowiednio dobrać parametry algorytmy Tabu Search - długość listy tabu oraz liczba iteracji. W pracy dotyczącej przepustowości modularnych znajdują się szczegółowe badania dotyczące tych dwóch parametrów.

11

Utilization Balancing Algorithms for Dynamic Multicast Scheduling Problem in EON

75%

Markowski M.

|

tom Vol. 62, No. 4

363--370

EN

Dynamic data transfer demands are often being a challenge for present communication networks, as they appear in unpredictable time and must be satisfied prior to deadline. Important kind are the multi-target demands occurring in task of replication, backup, database synchronization or file transferring in pear-to-pear networks. Optimal scheduling usually depends of the nature of transport network. In the paper dynamic deadlinedriven multicast scheduling problem over elastic optical network is considered. Particularly, the method for improving link utilization by traffic balance for multicast demands is proposed. Few heuristic algorithms and results of experiments, proving the benefits of balancing concept are presented

12

Dependence of mobile robot task scheduling on fitness functions

75%

Miczulski W. , Powroźnik P.

|

2014

|

tom R. 90, nr 7

43--47

EN

The results of simulation studies designed to assess two of the fitness functions (Or1 and Or2) for the GRASP algorithm used in the elastic scheduling task model (ESTM) have been presented in the paper. The obtained results indicate that the GRASP algorithm with the fitness function Or2 was better at choosing new settings for Tsel to exploit the hardware resources of a mobile robot. Furthermore, it has been found that for Or2 new settings for Tsel are closer to Tnom than Tmax (task cycle execution is reduced which enables a quicker response of a mobile robot to events).

PL

W artykule przedstawiono wyniki badań symulacyjnych umożliwiających ocenę dwóch opracowanych funkcji celu (Or1 i Or2) dla algorytmu GRASP zastosowanego w elastycznym modelu szeregowania zadań. Otrzymane wyniki badań wskazują, że dla funkcji celu Or2 nowe nastawy Tsel lepiej dopasowały wykorzystanie zasobów sprzętowych robota mobilnego do założonej wartości. Ponadto dla Or2 stwierdzono bliższy dobór wartości Tsel do Tnom niż Tmax (cykl wykonywania zadań skraca się, przez co robot mobilny może szybciej reagować na zdarzenia).

13

Wpływ parametrów funkcji celu na dobór nastaw okresów w elastycznym modelu szeregowania zadań

75%

Powroźnik P.

Studia Informatica

|

2012

|

tom Vol. 33, nr 3A

101-110

PL

Elastyczny model szeregowania zadań umożliwia zapewnienie warunku realizowalności zadań w węźle systemu pomiarowo - sterującego, w którym występują zadania aperiodyczae lub periodyczne, zmieniające swoje parametry czasowe. W elastycznym modelu algorytmy heurystyczne poszukają i oceniają nowe dobory okresów zadań za pomocą funkcji celu. W artykule przedstawiono wyniki badań symulacyjnych sprawdzające poprawność opracowanej funkcji celu.

EN

Elastic task model scheduling allows to ensnre reliability condition for node that has aperiodic and periodic tasks changing their tiining parameters. ln this model heuristic algorithms seek and evaluate new periods of tasks with fitness function. This paper presents the results of simulation studies validate the developed fitness functions.

14

Heurystyczny algorytm planowania rozdziału zadań dla systemu z maszynami równoległymi o ograniczonych zasobach

75%

Buchalski Z.

|

2007

|

tom T. 11, z. 1-2

61-69

PL

Praca dotyczy zagadnienia czasowo-optymalnego przydziału n zadań niezależnych i zasobu nieodnawialnego do m maszyn równoległych. Dla zadanej funkcji czasu realizacji zadań sformułowano model matematyczny zagadnienia oraz zaprezentowano algorytm heurystyczny dla rozwiązania postawionego problemu. Przedstawiono wyniki badań komputerowych wykonanych na bazie zaproponowanego algorytmu heurystycznego.

EN

In the paper problem of time-optimal allocation of n independent tasks and nonrenewable resources to m parallel machines is considered. For some tasks execution time function the mathematical model of this problem is formulated and an heuristic algorithm for solution this problem is presented. Some results of executed computer research for basis of proposed heuristic algorithm are presented.

15

Allocation of real power generation based on computing over all generation cost: an approach of Salp Swarm Algorithm

75%

Devarapalli R. , Sinha N. K. , Rao B. V. , Knypinski Ł. , Lakshmi N. J. N. , Márquez F. P. G. , Devarapalli R. , Sinha N. K. , Rao B. V. , Knypinski Ł. , Lakshmi N. J. N. , Márquez F. P. G.

|

16

Methodology of Optimization of the Design of an Orthopedic Implant

75%

Muzalewska M. , Moczulski W.

|

2015

|

tom Vol. 39, No. 2

133-141

EN

The scientific goal of the project is multicriterial optimization of the design of an orthopedic implant responsible for supporting the reconstruction of the anterior cruciate ligament. The implant should not only precisely anchor the tendon in the tunnel but, above all, - thanks to appropriately selected geometric shape and other design features - accelerate the ingrowth of bone tissue into the grafted tendon. The condition for the correct ingrowth of the bone tissue is to enable optimal perfusion of blood and other body fluids into the ligament prosthesis (grafted tendon). Therefore, the geometrical shape of the implant should allow accumulating active biological factors in the vicinity of the grafted tendon, thus accelerating the healing process. The research hypothesis is that there is a specific number of holes of a certain shape and a specific arrangement of these holes, which ensure optimum blood perfusion by maintaining adequate mechanical properties. Finding the optimum is possible by methods such as Artificial Immune Systems from heuristic algorithms class.

17

A New Elastic Scheduling Task Model in the Node of a Control and Measurement System

75%

Miczulski W. , Powroźnik P.

|

2013

|

nr 1

18

Heuristic algorithm to predict the location of C0 separators for efficient isogeometric analysis simulations with direct solvers

75%

Paszyńska A. , Jopek K. , Woźniak M. , Paszyński M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2018

|

tom Vol. 66, nr 6

907--917

EN

We focus on two and three-dimensional isogeometric finite element method computations with tensor product Ck B-spline basis functions. We consider the computational cost of the multi-frontal direct solver algorithm executed over such tensor product grids. We present an algorithm for estimation of the number of floating-point operations per mesh node resulting from the execution of the multi-frontal solver algorithm with the ordering obtained from the element partition trees. Next, we propose an algorithm that introduces C0 separators between patches of elements of a given size based on the stimated number of flops per node. We show that the computational cost of the multi-frontal solver algorithm executed over the computational grids with C0 separators introduced is around one or two orders of magnitude lower, while the approximability of the functional space is improved. We show O(NlogN) computational complexity of the heuristic algorithm proposing the introduction of the C0 separators between the patches of elements, reducing the computational cost of the multi-frontal solver algorithm.

19

The influence on network topology on the efficiency of multicast heuristic algorithms

75%

Piechowiak M. , Żmudziński P.

Image Processing & Communications

|

2006

|

tom Vol. 11, no 1

41-51

EN

The article investigates representative heuristic algorithms finding the cheapest spanning trees between a source node and the group of destination nodes (multicast connections). Reliable comparison and analysis of the efficiency of algorithms require the usage of network structures reflecting real Internet topology. This article also presents method for generation that topologies. The key part of the article includes the efficiency analysis and the influence of the parameters of a given structure (network model generated by BRITE tool) upon the efficiency of the algorithms under scrutiny.

20

Zastosowanie algorytmu hybrydowego do wyznaczenia przydziału pojazdów do zadań w przedsiębiorstwach usług komunalnych

75%

Izdebski M. , Jacyna M.

Logistyka

|

2015

|

tom nr 4

321--332

PL

W artykule przedstawiono problem przydziału pojazdów do zadań w przedsiębiorstwach usług komunalnych oraz model matematyczny problemu przydziału. Opisano metodę rozwiązującą omawiane zagadnienie oraz zaproponowano algorytm hybrydowy rozwiązujący zagadnienia optymalizacyjne przedstawionej metody. Algorytm hybrydowy jest kombinacją algorytmu genetycznego i mrówkowego. Algorytm mrówkowy generuje populację początkową dla algorytmu genetycznego. Wyniki algorytmu hybrydowego porównano z wynikami algorytmu mrówkowego, genetycznego z losową populacją początkową i algorytmu przeszukiwania losowego.

EN

This paper presents the assignment problem of vehicles to tasks in municipal services companies and the mathematical model of this problem. The article describes the method solving the discussed issue and proposes the hybrid algorithm solving the optimization problems of the presented method. The hybrid algorithm is a combination of the genetic and ant algorithm. The ant algorithm generates the initial population for the genetic algorithm. Results of the hybrid algorithm were compared with results of the ant algorithm, the genetic algorithm with the initial population selected randomly and random search algorithm.