BazTech - Yadda

1

Risk management in the allocation of vehicles to tasks in transport companies using a heuristic algorithm

Izdebski Mariusz

Archives of Transport

|

2023

|

Vol. 67, iss. 3

139--153

EN

The work deals with the issue of assigning vehicles to tasks in transport companies, taking into account the minimization of the risk of dangerous events on the route of vehicles performing the assigned transport tasks. The proposed risk management procedure based on a heuristic algorithm reduces the risk to a minimum. The ant algorithm reduces it in the event of exceeding the limit, which differs from the classic methods of risk management, which are dedicated only to risk assessment. A decision model has been developed for risk management. The decision model considers the limitations typical of the classic model of assigning vehicles to tasks, e.g. window limits and additionally contains limitations on the acceptable risk on the route of vehicles' travel. The criterion function minimizes the probability of an accident occurring along the entire assignment route. The probability of the occurrence of dangerous events on the routes of vehicles was determined based on known theoretical distributions. The random variable of the distributions was defined as the moment of the vehicle's appearance at a given route point. Theoretical probability distributions were determined based on empirical data using the STATISTICA 13 package. The decision model takes into account such constraints as the time of task completion and limiting the acceptable risk. The criterion function minimizes the probability of dangerous events occurring in the routes of vehicles. The ant algorithm has been validated on accurate input data. The proposed ant algorithm was 95% effective in assessing the risk of adverse events in assigning vehicles to tasks. The algorithm was run 100 times. The designated routes were compared with the actual hours of the accident at the bottom of the measurement points. The graphical interpretation of the results is shown in the PTV Visum software. Verification of the algorithm confirmed its effectiveness. The work presents the process of building the algorithm along with its calibration.

2

Heurystyczna detekcja ataków sieciowych z wykorzystaniem środowiska Snort 3

Wnęk Sebastian, Kościej Rafał, Niemiec Marcin

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2022

|

nr 4

168--171

PL

Artykuł przedstawia algorytm detekcji ataków sieciowych, bazujący na podejściu heurystycznym. Szczegółowo opisany został sposób w jaki opracowane rozwiązanie klasyfikuje ruch sieciowy i podejmuje decyzję o zidentyfikowanym zdarzeniu. Algorytm został zaimplementowany w otwartoźródłowym środowisku Snort 3. Dodatkowo zaprezentowano model wspomagający detekcję, oparty na algorytmach uczenia maszynowego.

EN

The paper describes a heuristic algorithm for network attack detection. The principle of operation of this solution and attack classification were described in detail. The mechanizm was implemented in the Snort 3 ‒ the well-known open source environment for intrusion detection. Additionally, a model supporting attack detection based on machine learning was presented.

3

Exact and approximation algorithms for joint routing and flow rate optimization

Junosza-Szaniawski Konstanty, Nogalski Dariusz

Annals of Computer Science and Information Systems

|

2019

|

Vol. 20

29--36

EN

This paper addresses comparison of algorithms for a version of the NUM problem. The joint formulation of routing and transmission rate control within the multi-user and single-path setting is assumed within the NUM. Since problem is NP-hard, the efficient heuristics are designed, implemented and compared experimentally with other existing heuristics and exact linear programming solver. The linear approximation is applied for nonlinear utility function. The results of experiments demonstrate a trade-off between computing time and precision of goal value.

4

Ant colony optimisation algorithm for the facility localisation problem

Schiff K.

Technical Transactions

|

2018

|

Vol. 115, iss. 1

103--112

EN

This article describes a new ant colony optimisation algorithm for the facility localisation problem with a new heuristic pattern proposed by the author, which consists of three parts: the function of the average cost of client servicing; the total minimum cost of servicing from a site, which is selected and included into the solution; the function of improving the cost of already serviced clients. In this comparison, simulations were presented, and two parameters were observed: the number of sites and the cost of client servicing. The new algorithm allowed to improve the solution in both of these parameters.

PL

W artykule przedstawiono algorytm mrówkowy dla problemu lokalizacji fabryk z nową zaproponowaną heurystyką wyboru obiektów i został on porównany z innym znanym już z literatury przedmiotu algorytmem mrówkowym. Nowa heurystyka wyboru została wyrażona jako iloraz trzech funkcji pożądania wyboru, to jest funkcji określającej średni koszt obsługi klientów poprzez włączaną lokalizację do rozwiązania, funkcję określająca całkowitą minimalną sumę obsługiwania klientów z włączanej do rozwiązania lokalizacji oraz funkcję określająca maksymalną minimalizację kosztów obsługiwania klientów poprzez włączaną lokalizację, gdy ci klienci są już obsługiwani przez lokalizacje wybrane do rozwiązania. W artykule przedstawiono wyniki przeprowadzonych testów pod kątem uzyskania jak najmniejszej liczby lokalizacji i jak najmniejszego kosztu obsługiwania klientów w funkcji rozmiaru problemu i natężenia obsługiwania klientów z danej lokalizacji.

5

Optimization on permutations: related structures, problems interrelation, heuristic compositions, applications

Miatselski M.

Technical Sciences / University of Warmia and Mazury in Olsztyn

|

2018

|

nr 21(1)

37--47

EN

A heuristics based approach to practical solving theoretically intractable combinatory and network problems is discussed. Compound heuristics (heuristics compositions) are suggested to be more efficient procedures for real size problem instances. Some aspects of the heuristics compositions topic are illustrated by optimum permutation problems. We describe a uniform presentation of the chief types of the problems and their interrelations, including the relation “to be a special case of a problem”. We consider a number of algebraic structures and combinatory constructions on permutation sets and present an inclusion chain of these constructions. The chain enables us to establish and clarify many interrelations for the minimum permutation problems, with algorithmic and complexity aspects taken into account. We also concern the applications of some problems as well.

6

Method of determining the longest simple chain in a graph with the use of a genetic algorithm

Mielniczuk Ł., Strzelecki Ł.

Przegląd Teleinformatyczny

|

2018

|

T. 6, Nr 3-4 (47)

3--18

EN

This paper discusses the issue of determining the longest simple chain in a graph by using a heuristic algorithm - a genetic algorithm. A method enabling the effective determination of the longest chain in any connected, undirected graph without loops.

PL

W artykule rozpatrzono problem wyznaczania najdłuższego łańcucha prostego w grafie wykorzystującą algorytm heurystyczny – algorytm genetyczny. Przedstawiono metodę umożliwiającą efektywne wyznaczanie najdłuższego łańcucha w dowolnym grafie spójnym, nieskierowanym, bez pętli.

7

A method of loading unit formation taking into account mass, load-bearing strength and surfaces of packing units

Popiela K., Wasiak M.

Zeszyty Naukowe. Transport / Politechnika Śląska

|

2017

|

z. 96

151--160

EN

The problem of loading unit formation is computationally complex in nature. This article presents a heuristic algorithm of forming unit loads, which can be applied to unit load arrangement on unit load devices. This method accounts for dimensional, mass and load-bearing strength of loading units and loading devices. Moreover, the rotation of packages about a 90° vertical axis has been made possible. In this algorithm, the bearing surface of each packing unit is entirely supported. This guarantees the stability of additional unit load layers. A sample calculation of the arrangement of 30-unit loads is presented in this article.

8

Voice recognition through the use of Gabor transform and heuristic algorithm

Woźniak M., Połap D.

International Journal of Electronics and Telecommunications

|

2017

|

Vol. 63, No. 2

159--164

EN

Increasingly popular use of verification methods based on specific characteristics of people like eyeball, fingerprint or voice makes inventing more accurate and irrefutable methods of that urgent. In this work we present voice verification based on Gabor transformation. Proposed approach involves creation of spectrogram, which serves as a habitat for the population in selected heuristic algorithm. The use of heuristic allows for feature extraction to enable identity verification using classical neural network. The results of the research are presented and discussed to show efficiency of the proposed methodology.

9

Rozwiązanie problemu komiwojażera przy użyciu algorytmu genetycznego

Ochelska-Mierzejewska J.

Logistyka

|

2016

|

nr 1

350--356, CD1

PL

Firmy związane z dystrybucją i transportem próbują opracować trasy swoich pojazdów, aby możliwie zminimalizować koszty i umożliwić dostarczenie ich towarów w wystarczająco krótkim czasie. Rozwiązaniem tego zagadnienia może być znalezienie optymalnego rozwiązanie dla problemu komiwojażera przy zastosowaniu algorytmu genetycznego. W artykule przeanalizowano dobór parametrów wejściowych dla tego algorytmu umożliwiającego znalezienie rozwiązania i przedyskutowano otrzymane wyniki.

EN

Companies associated with the distribution and transport are trying to develop their vehicles and routes to minimize costs and delivery of their goods in a sufficiently short time. The solution to this problem is to find the optimal solution for the traveling salesman problem using genetic algorithm. The article analyzes the selection of input parameters for this algorithm which allows to find a solution and discussed the results.

10

A novel heuristic algorithm for minimum compliance topology optimization

Bochenek B., Mazur M.

Engineering Transactions

|

2016

|

Vol. 64, iss. 4

541--546

EN

The implementation of efficient and versatile methods to the generation of optimal topologies for engineering structural elements is one of the most important issues stimulating progress within the structural topology optimization area. Over the years, optimization problems have been typically solved by the use of classical gradient-based mathematical programming algorithms. Nowadays, these traditional techniques are more often replaced by other algorithms, usually by the ones based on heuristic rules. Heuristic optimization techniques are gaining widespread popularity among researchers because they are easy to implement numerically, do not require gradient information, and one can easily combine this type of algorithm with any finite element structural analysis code. In this paper, a novel heuristic algorithm for a minimum compliance topology optimization is proposed. Its effectiveness is illustrated by the results of numerical generation of optimal topologies for selected plane structures.

11

Real-Time Cloud-based Game Management System via Cuckoo Search Algorithm

Połap D., Woźniak M., Napoli C., Tramontana E.

International Journal of Electronics and Telecommunications

|

2015

|

Vol. 61, No. 4

333-338

EN

This paper analyses the idea of applying Swarm Intelligence in the process of managing the entire 2D board game in a real-time environment. For the proposed solution Game Management System is used as a cloud resource with a dedicated intelligent control agent. The described approach has been analysed on the basis of board games like mazes. The model and the control algorithm of the system is described and examined. The results of the experiments are presented and discussed to show possible advantages and isadvantages of the proposed method.

12

On Some Aspects of Genetic and Evolutionary Methods for Optimization Purposes

Woźniak M., Połap D.

International Journal of Electronics and Telecommunications

|

2015

|

Vol. 61, No. 1

7-16

EN

In this paper, the idea of applying some hybrid genetic algorithms with gradient local search and evolutionary optimization techniques is formulated. For two different test functions the proposed versions of the algorithms have been examined. Research results are presented and discussed to show potential efficiency in optimization purposes.

13

Is Swarm Intelligence Able to Create Mazes?

Połap D., Woźniak M., Napoli C., Tramontana E.

International Journal of Electronics and Telecommunications

|

2015

|

Vol. 61, No. 4

305-310

EN

In this paper, the idea of applying Computational Intelligence in the process of creation board games, in particular mazes, is presented. For two different algorithms the proposed idea has been examined. The results of the experiments are shown and discussed to present advantages and disadvantages.

14

Algorytm hybrydowy wielokrotnego startu dla rozwiązywania problemu sekwencyjnego uporządkowania

Widuch J., Klyta A.

Studia Informatica

|

2014

|

Vol. 35, nr 1

29--55

PL

Problem sekwencyjnego uporządkowania (SOP) jest podobny do asymetrycznego problemu komiwojażera. Celem jest wyznaczenie w skierowanym grafie ważonym ścieżki Hamiltona o minimalnej wadze, przy dodatkowym spełnieniu relacji pierwszeństwa wierzchołków. W niniejszej pracy zaprezentowano algorytm hybrydowy wielokrotnego startu rozwiązywania problemu SOP. Algorytm ten jest połączeniem algorytmów symulowanego wyżarzania i lokalnej optymalizacji. Dodatkowo przedstawiono wyniki przeprowadzonych badań eksperymentalnych.

EN

The sequential ordering problem (SOP) is similar to the asymmetric traveling salesman problem. The goal is to find a minimum weight Hamiltonian path on a directed weighted graph satisfying precedence relationships among the vertices. In the paper, a multistart hybrid algorithm to solving SOP is presented. The algorithm based on simulated annealing algorithm and local optimization method. Apart from that results of experimental tests are presented.

15

Model–based energy efficient global path planning for a four–wheeled mobile robot

Jaroszek P., Trojnacki M.

Control and Cybernetics

|

2014

|

Vol. 43, no. 2

337--363

EN

This paper concerns an energy efficient global path planning algorithm for a four-wheeled mobile robot (4WMR). First, the appropriate graph search methods for robot path planning are described. The A* heuristic algorithm is chosen to find an optimal path on a 2D tile-decomposed map. Various criteria of optimization in path planning, like mobility, distance, or energy are reviewed. The adequate terrain representation is introduced. Each cell in the map includes information about ground height and type. Tire-ground interface for every terrain type is characterized by coefficients of friction and rolling resistance. The goal of the elaborated algorithm is to find an energy minimizing route for the given environment, based on the robot dynamics, its motor characteristics, and power supply constraints. The cost is introduced as a function of electrical energy consumption of each motor and other robot devices. A simulation study was performed in order to investigate the power consumption level for diverse terrain. Two 1600 m2 test maps, representing field and urban environments, were decomposed into 20x20 equal-sized square-shaped elements. Several simulation experiments have been carried out to highlight the differences between energy consumption of the classic shortest path approach, where cost function is represented as the path length, and the energy efficient planning method, where cost is related to electrical energy consumed during robot motion.

16

Non-Monotonic Attribute Reduction in Decision-Theoretic Rough Sets

Li H., Zhou X., Zhao J., Liu D.

Fundamenta Informaticae

|

2013

|

Vol. 126, nr 4

415--432

EN

For most attribute reduction in Pawlak rough set model (PRS), monotonicity is a basic property for the quantitative measure of an attribute set. Based on the monotonicity, a series of attribute reductions in Pawlak rough set model such as positive-region-preserved reductions and condition entropy-preserved reductions are defined and the corresponding heuristic algorithms are proposed in previous rough sets research. However, some quantitative measures of attribute set may be non-monotonic in probabilistic rough set model such as decision-theoretic rough set (DTRS), and the non-monotonic definition of the attribute reduction should be reinvestigated and the heuristic algorithm should be reconsidered. In this paper, the monotonicity of the positive region in PRS and DTRS are comparatively discussed. Theoretic analysis shows that the positive region in DTRS model may be expanded with the decrease of the attributes, which is essentially different from that in PRS model. Hereby, a new non-monotonic attribute reduction is presented for the DTRS model in this paper, and a heuristic algorithm for searching the newly defined attribute reduction is proposed, in which the positive region is allowed to be expanded instead of remaining unchanged in the process of attribute reduction. Experimental analysis is included to validate the theoretic analysis and quantify the effectiveness of the proposed attribute reduction algorithm.

17

Ant colony optimization algorithm for the 0-1 knapsack problem

Schiff K.

Czasopismo Techniczne. Automatyka

|

2013

|

R. 110, z. 3-AC

39--52

EN

This article describes a new ant colony optimisation algorithm for the discrete knapsack problem with a new heuristic pattern, based on the ratio of the square of the profit coefficient to the square of the weight coefficient of the original problem. This new heuristic is used in order to choose objects that should be packed into the knapsack. This pattern was compared with two used in ant algorithms and which have been presented in the literature on the subject of ant colony optimisation algorithms for the 0-1 Knapsack Problem. The two other patterns are based on the ratio of the profit coefficient to the weight coefficient multiplied respectively by the total and the current knapsack load capacity. Results of tests under a width range of ant algorithm parameters such as the number of cycles, the number of ants, the evaporation rate, and the load knapsack capacity are shown and discussed.

PL

W artykule przedstawiono algorytm mrówkowy dla dyskretnego problemu plecakowego z nową heurystyką wyboru obiektów i został on porównany z dwoma innymi algorytmami spotkanymi w literaturze przedmiotu pod względem uzyskiwanego całkowitego zysku z załadowanych do plecaka przedmiotów. Nowa heurystyka wyboru została wyrażona poprzez stosunek kwadratu zysku do kwadratu wagi wybranego przedmiotu, gdy dwie znane już heurystyki to stosunek zysku do wagi odpowiednio pomnożony przez całkowitą i bieżącą ładowność plecaka. W artykule przedstawiono wyniki przeprowadzonych testów dla szerokiego zakresu parametrów algorytmów mrówkowych takich jak: współczynnik parowania, liczba cykli, liczba mrówek, ładowności plecaka jak i dla różnej liczby dostępnych przedmiotów do załadunku.

18

Evolutionary Algorithms Approach for Cutting Stock Problem

Romanowski A., Nowotniak R., Kawecki K, Jaworski T., Chaniecki Z., Grudzień K.

Image Processing & Communications

|

2012

|

Vol. 17, no. 4

297--306

EN

This paper contain study of three algorithms for optimisation of use of materials for cutting process. Cutting Stock Problem (CSP) and one dimensional guillotine cat variant of the CSP is introduced. Afterwards three different way of solving the problem are presented. For each of theme one algorithm is proposed. First is creating all the possible solutions and choosing the best one. Second is trying to recreate a human thinking process by using a heuristic search. Third one is inspired by an evolution process in the nature. Design and implementation of each of them is presented. Proposed algorithms are tested and compared to each other and also to the other known solutions.

19

Algorytm dla problemu losowego przydziału personelu

Klimek M., Łebkowski P.

Logistyka

|

2011

|

nr 2

PL

Artykuł prezentuje problem losowego przydziału personelu, który występuje w rzeczywistej firmie. Sformułowano model matematyczny dla tego zagadnienia. Następnie zaproponowano algorytm priorytetowy rozwiązujący problem losowej alokacji personelu. Na koniec przedstawiono przykład ilustrujący działanie algorytmu.

EN

This paper presents random personnel assignment problem which is found in real company. Mathematic model for this problem is formulated. Next priority algorithm solving random personnel allocation problem is proposed. Finally an illustrative example working of this algorithm is described.

20

Szeregowanie zadań o zmiennych wartościach z różnymi terminami dostępności – algorytmy rozwiązania

Janiak A., Kołodka P., Krysiak T.

Przegląd Elektrotechniczny

|

2010

|

R. 86, nr 9

91-96

PL

Praca dotyczy problemu szeregowania zadań o zmiennych wartościach i niezerowych terminach dostępności na pojedynczej maszynie. Analizowano potęgowy model wartości zadań, a jako kryterium – maksymalizację sumy wartości wszystkich zadań. Problem powyższy jest co najmniej NP-trudny. Do jego rozwiązania skonstruowano algorytm dokładny typu podziału i ograniczeń oraz szereg algorytmów heurystycznych typu konstrukcyjnego, a także jeden typu popraw. Efektywność skonstruowanych algorytmów przebadano eksperymentalnie.

EN

The paper deals with a problem of scheduling jobs with changeable job values and non-zero release dates on a single machine. A power model of job values and the criterion of maximization of the total job values are analyzed. The above problem is at least NP-hard. Thus, a branch and bound exact algorithm and some heuristic algorithms (constructive and improving type) have been developed. Their efficiency have been examined experimentally.