Wyniki wyszukiwania - BazTech

1

New ideas in Lagrangian relaxation for a scheduling problem with the weighted tardiness criterion

Rudy Jarosław, Idzikowski Radosław, Smutnicki Czesław, Banaszak Zbigniew, Bocewicz Grzegorz

International Journal of Applied Mathematics and Computer Science

|

2024

|

Vol. 34, no. 2

235--251

EN

We consider an extension of Lagrangian relaxation methods for solving the total weighted tardiness scheduling problem on a single machine. First, we investigate a straightforward relaxation method and decompose it into upper and lower subproblems. For the upper subproblem we propose an alternative solving method in the form of a local search metaheuristic. We also introduce a scaling technique by arbitrary numbers to reduce the complexity of the problem and confront it with greatest common divisor scaling. Next, we propose a novel alternative relaxation approach based on aggregating constraints. We discuss the properties and implementation of this new approach and a technique to further reduce its computational complexity. We perform a number of computer experiments on instances based on the OR-Library generation scheme to illustrate and ascertain the numerical properties of the proposed methods. The results indicate that for larger instances the proposed alternative relaxation and scaling approaches have a much better convergence rate with little to no decrease in solution quality. The results also show that the proposed local-search metaheuristic is a viable alternative to the existing solving methods.

2

Optimization of fractional order PI controller using metaheuristics algorithms applied to multilevel inverter for grid connected PV

Boucheriette Wafa, Mechgoug Raihane, Benguesmia Hani

Diagnostyka

|

2023

|

Vol. 24, No. 3

art. no. 2023311

EN

Due to its multiple advantages in industrial and grid-connected applications, Multi-Level Inverters (MLIs) have increased in popularity in recent years. To improve the efficiency of a grid-connected PV system's integrated multi-level inverter fractional order PI (FOPI) controllers are used to describe the control process. The control system is made up of three control loops based on FOPI controllers: one for controlling the intermediate circuit voltage (Vdc) and the other two for controlling the direct and quadratic currents (Id, Iq) supplied by the multilevel inverter. The proposed controller parameters (Kp, KI, λ) must be selected in order to increase the efficiency of the multi-level inverter while decreasing the total harmonic distortion (THD) of the output current of the inverter as well as voltage. For this we used three meta-heuristic algorithms (PSO, ABC, GWO). The performance of the three controllers PSO-FOPI, ABC-FOPI and GWO-FOPI controller is compared. The findings showed that GWO-FOPI performs better than the other PSO-FOPI and ABC-FOPI in accuracy and total harmonic distortion THD term. The simulation will be conducted using Matlab/Simulink.

3

Studium przypadku skuteczności nowych metod optymalizacji roju w porównaniu do metod znanych

Baumgart Jan, Sangho Belco

Studia i Materiały Informatyki Stosowanej

|

2021

|

nr 1

47--50

PL

Porównianie skuteczności nowych metod optymalizacji roju w porównaniu z metodami znanymi w dziedzinie. Inspirowane naturą algorytmy metaheurystyczne stają się coraz bardziej popularne w rozwiązywaniu problemów optymalizacyjnych. Dzięki ich popularności niemal codziennie możemy zobaczyć nowepodejścia i proponowane rozwiązania. W tym artykule przedstawię porównanie, które pokaże kilka najnowszychprac z tej dziedziny w porównaniu z niektórymi algorytmami traktowanymi jako podstawa dziedziny. Głównymcelem było porównanie ostatnio wprowadzonych algorytmów roju i określenie, kiedy nowe rozwiązania są faktycznie szybsze i bardziej precyzyjne. Podsumowując, czy przetestowane nowe podejścia są lepsze niż obecne,dobrze znane i ugruntowane w terenie algorytmy. Algorytmy brane pod uwagę w tej pracy to: Particle SwarmOptimization [5], Artifical Bee Colony [3], Elephant Herding Optimization [7], Whale Optimization [4] i Gras-shopper Optimization [6].Algorytmy uznawane za nowe w tej dziedzinie porównano z dwoma popularnymi idobrze znanymi algorytmami metaheurystycznymi pod względem dokładności znalezionych rozwiązań i szybkości. Zgodnie z wynikami eksperymentów większość porównywanych nowych algorytmów dawała zadowalającewyniki w użytkowaniu.

EN

Comparing the effectiveness of new methods of swarm optimization in comparison with knownmethods. Nature-inspired metaheuristic algorithms are becoming more and more popular in solving optimization problems. Thanks to their popularity, we can see new approaches and proposed solutions almost everyday. In this article, I will present a comparison that will show some of the most recent works in this fieldcompared to some algorithms considered as the basis of the field. The main goal was to compare the recently introduced swarm algorithms and determine when new solutions are actually faster and more precise. Inconclusion, are the new approaches tested better than the current, well-known and field-grounded algorithms?The algorithms considered in this paper are Particle Swarm Optimization, Artifical Bee Colony, Elephant Herding Optimization, Whale Optimization, and Grasshopper Optimization. Algorithms considered new inthis field were compared with two popular and well-known metaheuristic algorithms in terms of accuracy ofsolutions found and speed. According to the experimental results, most of the compared new algorithms gave satisfactory results in use.

4

Scheduling trucks in a multi-door cross-docking system with time windows

Ozden G., Saricicek I.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2019

|

Vol. 67, nr 2

344--362

EN

Cross-docking is a strategy that distributes products directly from a supplier or manufacturing plant to a customer or retail chain, reducing handling or storage time. This study focuses on the truck scheduling problem, which consists of assigning each truck to a door at the dock and determining the sequences for the trucks at each door considering the time-window aspect. The study presents a mathematical model for door assignment and truck scheduling with time windows at multi-door cross-docking centers. The objective of the model is to minimize the overall earliness and tardiness for outbound trucks. Simulated annealing (SA) and tabu search (TS) algorithms are proposed to solve largesized problems. The results of the mathematical model and of meta-heuristic algorithms are compared by generating test problems for different sizes. A decision support system (DSS) is also designed for the truck scheduling problem for multi-door cross-docking centers. Computational results show that TS and SA algorithms are efficient in solving large-sized problems in a reasonable time.

5

Ant colony optimization algorithm for workforce planning: influence of the evaporation parameter

Fidanova Stefka, Luque Gabriel, Roeva Olympia, Ganzha Maria

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

177--181

EN

Optimization of the production process is important for every factory or organization. The better organization can be done by optimization of the workforce planing. The main goal is decreasing the assignment cost of the workers with the help of which, the work will be done. The problem is NP-hard, therefore it can be solved with algorithms coming from artificial intelligence. The problem is to select employers and to assign them to the jobs to be performed. The constraints of this problem are very strong and for the algorithms is difficult to find feasible solutions. We apply Ant Colony Optimization Algorithm to solve the problem. We investigate the algorithm performance according evaporation parameter. The aim is to find the best parameter setting.

6

An Analytical Study for the Role of Fuzzy Logic in Improving Metaheuristic Optimization Algorithms

Vij Sonakshi, Jain Amita, Tayal Devendra, Castillo Oscar

Journal of Automation Mobile Robotics and Intelligent Systems

|

2018

|

Vol. 12, No. 4

11--27

EN

The research applications of fuzzy logic have always been multidisciplinary in nature due to its ability in handling vagueness and imprecision. This paper presents an analytical study in the role of fuzzy logic in the area of metaheuristics using Web of Science (WoS) as the data source. In this case, 178 research papers are extracted from it in the time span of 1989-2016. This paper analyzes various aspects of a research publication in a scientometric manner. The top cited research papers, country wise contribution, topmost organizations, top research areas, top source titles, control terms and WoS categories are analyzed. Also, the top 3 fuzzy evolutionary algorithms are extracted and their top research papers are mentioned along with their topmost research domain. Since neuro fuzzy logic poses feasible options for solving numerous research problems, hence a section is also included by the authors to present an analytical study regarding research in it. Overall, this study helps in evaluating the recent research patterns in the field of fuzzy metaheuristics along with envisioning the future trends for the same. While on one hand this helps in providing a new path to the researchers who are beginners in this field as they can start exploring it through the analysis mentioned here, on the other hand it provides an insight to professional researchers too who can dig a little deeper in this field using knowledge from this study.

7

Minimal cycle time determination and golf neighborhood generation for the cyclic flexible job shop problem

Bożejko W., Pempera J., Wodecki M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2018

|

Vol. 66, nr 3

333--344

EN

In the paper, a problem of scheduling operations in the cyclic flexible job shop system is considered. A new, very fast method of determining the cycle time for any order of tasks on machines is also presented. It is based on the analysis of the paths in the graph representing the examined problem. The theorems concerning specific properties of the graph are proven and used in the construction of the heuristic algorithm searching the solutions space by using the so-called golf neighborhood, which is generated in a way similar to the game of golf, which helps to intensify and diversify calculations. The conducted computational experiments fully confirmed the effectiveness of the proposed method. The proposed methods and properties can be adapted and used in the construction of local search algorithms for solving many other optimization problems.

8

Performance comparison of hybrid electromagnetism-like mechanism algorithms with descent method

Miyajima H., Shigei N., Miyajima H.

Journal of Artificial Intelligence and Soft Computing Research

|

2015

|

Vol. 5, No. 4

271--282

EN

Electromagnetism-like Mechanism (EM) method is known as one of metaheuristics. The basic idea is one that a set of parameters is regarded as charged particles and the strength of particles is corresponding to the value of the objective function for the optimization problem. Starting from any set of initial assignment of parameters, the parameters converge to a value including the optimal or semi-optimal parameter based on EM method. One of its drawbacks is that it takes too much time to the convergence of the parameters like other meta-heuristics. In this paper, we introduce hybrid methods combining EM and the descent method such as BP, k-means and FIS and show the performance comparison among some hybrid methods. As a result, it is shown that the hybrid EM method is superior in learning speed and accuracy to the conventional methods.

9

Using tabu search for feature selection in discriminant analysis

Stąpor K.

Studia Informatica

|

2014

|

Vol. 35, nr 4

45--58

EN

The well known statistical software packages like STATISTICA [11] continue to use classic variable selection methods in stepwise Discriminant Analysis such as the sequential forward/backward ones. Such stepwise procedures suffer from the nesting effect. Moreover, due to the criterion used for evaluation of variable subsets they are designed for descriptive purposes, not for predictive ones. We propose the new solution to the mentioned problems, the feature selection algorithm based on metaheuristic tabu search. After performing some tests it is found that our tabu search-based algorithm obtains significantly better results than stepwise procedures of statistical package.

PL

W znanych szeroko pakietach do obliczeń statystycznych (np. STATISTICA [11]) selekcja zmiennych wejściowych w module krokowej Analizy Dyskryminacyjnej wykonywana jest z wykorzystaniem klasycznych metod sekwencyjnych w przód/w tył, których wadą jest efekt zagnieżdżania. Również kryterium ewaluacyjne w tychże metodach jest dostosowane do celów deskryptywnych, a nie predyktywnych. Artykuł proponuje nowe rozwiązania wspomnianych problemów – algorytm selekcji z wykorzystaniem metaheurystyki przeszukiwania z tabu. Wykonane, wstępne testy wykazały znacznie lepszą sprawność klasyfikacji w porównaniu z metodami krokowymi.

10

Algorytmy inspirowane naturą w kryptoanalizie

Polak I., Boryczka M.

Studia Bezpieczeństwa Narodowego

|

2014

|

R. 4, Nr 6

185--197

PL

W dzisiejszych czasach ochrona informacji jest niezwykle istotna, a jednym z elementów zapewniających ową ochronę jest kryptograﬁa. Tu z kolei ważną rolę odgrywa kryptoanaliza, która pozwala badać bezpieczeństwo używanych szyfrów. Oprócz typowo analitycznego podejścia do łamania szyfrów (jak kryptoanaliza różnicowa, kryptoanaliza liniowa czy analiza statystyczna) od kilkunastu lat do tego celu zaprzęga się różnego rodzaju niedeterministyczne systemy inspirowane naturą. Użycie takich technik nie jest do końca intuicyjne – w kryptoanalizie często ważne jest znalezienie jednego konkretnego klucza (rozwiązania optymalnego), a każde inne rozwiązanie daje kiepskie rezultaty, nawet jeśli jest blisko optimum globalnego.

EN

Nowadays protection of information is very crucial and cryptography is a signiﬁcant part of keeping information secure. Here in turn cryptanalysis plays an important role by examining the safety of ciphers used. Besides the analytical approach to ciphers breaking (eg. diﬀerential cryptanalysis, linear cryptanalysis, statistical analysis) for this purpose there are several kinds of non-deterministic, inspired by nature systems applied. It is not intuitive - as in cryptanalysis often it is important to ﬁnd the exact key used (optimal solution) and every other solution is giving poor results, even if it is near global optimum.

11

Challenges for nurse rostering problem and opportunities in hospital logistics

Simić D., Simić S., Milutinović D., Djordjević J.

Journal of Medical Informatics & Technologies

|

2014

|

Vol. 23

195--202

EN

In the last 45 years nurse scheduling has received considerable attention in the research community. Nurse rostering can be described as a task of finding a duty roster for a set of nurses in such a way that the rosters comply with work regulations and meet the management’s requests. The objective varies from minimizing the costs of float nurses or minimizing under-staffing to maximizing the degree to which the nurses’ requests are met. In logistics, one aspect is optimization of the steady flow of materials through a network of transport links and storage nodes, and the other is, coordination of a sequence of resources, such as staffing and scheduling clinical resources. The period up to 2000 is characterized by using mathematical programming and objective functions to solve nurse rostering problem. In the period after 2000 the focus of researches aimed at solving nurse rostering and scheduling problem becomes implementation of meta-heuristics and multi-objective functions. The aim of this paper is to present the latest researches conducted in last ten years.

12

A new metaheuristic algorithm for long-term open-pit production planning

Sattarvand J., Niemann-Delius C.

Archives of Mining Sciences

|

2013

|

Vol. 58, no. 1

107--118

EN

Paper describes a new metaheuristic algorithm which has been developed based on the Ant Colony Optimisation (ACO) and its efficiency have been discussed. To apply the ACO process on mine planning problem, a series of variables are considered for each block as the pheromone trails that represent the desirability of the block for being the deepest point of the mine in that column for the given mining period. During implementation several mine schedules are constructed in each iteration. Then the pheromone values of all blocks are reduced to a certain percentage and additionally the pheromone value of those blocks that are used in defining the constructed schedules are increased according to the quality of the generated solutions. By repeated iterations, the pheromone values of those blocks that define the shape of the optimum solution are increased whereas those of the others have been significantly evaporated.

PL

W artykule zaprezentowano nowy meta-heurystyczny algorytm oparty na zasadach optymalizacji mrowiska i zbadano jego skuteczność w zastosowaniach do planowania wydobycia w kopalniach. Uwzględniono szereg zmiennych w każdym bloku schematu i przeanalizowano „ślady feromonów” które przedstawiają „dążność” poszczególnych bloków w danej kolumnie do stania się najgłębszym punktem kopalni w trakcie określonego okresu prowadzenia prac wydobywczych. W ramach kolejnych iteracji generuje się kilka harmonogramów prowadzenia wydobycia. Następnie wartości poziomu feromonów przypisane do kolejnych bloków redukowane są do wielkości wyrażonych w procentach a wartości poziomu feromonów przypisane do bloków wykorzystywanych do wygenerowania danego harmonogramu zostają powiększone, zgodnie z wymogami odnośnie jakości uzyskanych rozwiązań. Drogą kolejnych iteracji, wartości poziomu feromonów przypisane do bloków generujących rozwiązania optymalne zostają powiększane podczas gdy wartości przypisane do bloków pozostałych zostają odpowiednio pomniejszone.

13

An ant colony system for team orienteering problems with time windows

Montemanni R., Gambardella L.M.

Foundations of Computing and Decision Sciences

|

2009

|

Vol. 34, No. 4

287-306

EN

This paper discusses a heuristic approach for Team Orienteering Problems with Time Windows. The method we propose takes advantage of a solution model based on a hierarchic generalization of the original problem, which is combined with an Ant Colony System algorithm. Computational results on benchmark instances previously adopted in the literature suggest that the algorithm we propose is effective in practice.

14

Asemblacja długich łańcuchów peptydowych przy wykorzystaniu metaheurystyki GRASP

Głowacki T., Kozak A., Formanowicz P.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 151

203-208

PL

Ustalenie kolejności aminokwasów w cząsteczce białka nosi nazwę sekwencjonowania. Brak bezpośrednich metod sekwencjonowania długich peptydów powoduje, że potrzebne są dedykowane metody asemblacyjne, które odpowiednio poskładają krótkie łańcuchy w jeden długi łańcuch aminokwasów. W pracy tej został zaproponowany algorytm asemblacyjny typu GRASP. Przedstawiony algorytm został zaimplementowany i przetestowany dla zbioru rzeczywistych peptydów, a uzyskane rozwiązanie zostało przedyskutowane.

EN

Determining an order of amino acids in peptide structure is called sequencing method. Lack of direct sequencing methods for long peptides causes that assembling methods to combine many short peptides into one long structure are necessary. In this paper assembling algorithm based on GRASP method was proposed. The algorithm was implemented and tested on real peptides set and the obtained results was discussed.

15

Wykorzystanie algorytmów genetycznych i mrówkowych w problemach transportowych

Zduńczuk J., Przystupa W.

Inżynieria Rolnicza

|

2008

|

R. 12, nr 7(105)

237-243

PL

W pracy przedstawiono możliwości zastosowania metaheurystyk w transporcie. Przy użyciu algorytmu genetycznego i mrówkowego dokonano optymalizacji długości trasy przejazdu, a rezultaty porównano ze znanymi wynikami. Przedstawiono również próbę optymalizacji tras ze względu na czas trwania przejazdu.

EN

The paper presents possibilities to employ metaheuristics in transport. The research involved using genetic and ant algorithm to optimise drive/ride route length, and obtained results were compared to known results. Moreover, the paper presents an effort to optimise routes with regard to drive duration.

16

The evolutionary heuristics applied to the analysis of multidimensional data

Jasińska-Suwada A.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

163-170

EN

This paper describes the pattern recognition system for analysis of multidimensional data, based on natural meta-heuristics. The system consists of tree modules: preprocessing, feature extraction and clustering. Feature extraction module is based on Molecular Dynamic (MD). In clustering are used two natural methods: Simulated Annealing (SA) and Taboo Search (TS). The system is used to analyze an evolving population of individuals equipped with 'genetic codes'. Clustering module extracts groups of data with similar genetic code named clusters and make of possible to observe their geographical localization. The feature extraction verifies the clustering and allows analyzing of clustering patterns, their shapes and the distances between them.

17

Simulation-based optimization; methods and practical application

Niewiadomska-Szynkiewicz E.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

291-300

EN

The paper is concerned with computational research for complex systems. The simulation-based optimization approach, which is widely used in applied science and engineering, is formulated and discussed. The numerical techniques that optimize performance of system by using simulation to evaluate the objective value are reviewed. The focus is on random search and metaheuristics. The practical example - application of simulation optimization to calculate the optimal decisions for controlling the river-basin reservoir system during flood period is presented and discussed.

18

Parallel tabu search for graph coloring problem

Dąbrowski J., Kubale M.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

87-95

EN

Tabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of parallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experirnental results are based on graphs available from the DIMACS benchmark suite.

19

Application of the population learning algorithm to training feed-forward ANN

Czarnowski I., Jędrzejowicz P.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2002

|

z. 139

147--161

EN

The chapter investigates the application of the new metaheuristic called the population learning algorithm (PLA) to training feed-forward artificial neural networks. This chapter introduces the population learning algorithm and proposes several implementations developed with a view to training several benchmark neural networks. The approach is compared with two alternative methods of training: quick propagation and genetic programming. Computer experiments show the high effectiveness and good quality of the suggested approach.

20

Multiobjective simulated annealing - a metaheuristic technique for multiobjective optimization of a constrained problem

Suman B.

Foundations of Computing and Decision Sciences

|

2002

|

Vol. 27, No. 3

171-191

EN

The paper presents a multiobjective metaheuristic procedure - Weight based Multiobjective Simulated Annealing (WMOSA). The aim is to produce a set of potentially Pareto-optimal solutions of a constrained multiobjective optimization problem in a short time. In this method, the weight vector depends on the number of constraints to be satisfied by the solution vector and by the objective function vector, and the number of constraints of the problem. The weight vector is used in the acceptance criterion to handle constraints. Solution explores its neighborhood in a way similar to that of Classical Simulated Annealing. A computational experiment shows that WMOSA algorithm produces Pareto-optimal solutions of better quality than Suppapitanrm Multiobjective Simulated Annealing (SMOSA) with a penalty function approach at a lower computational cost.