Wyniki wyszukiwania - BazTech

1

Meta-heuristic approach based on genetic and greedy algorithms to solve flexible job-shop scheduling problem

Rezaeipanah Amin, Sarhangnia Fariba, Abdollahi Mohammad Javad

Computer Science

|

2021

|

T. 22 (4)

463--488

EN

Job-shop scheduling systems are one of the applications of group technology in industry, the purpose of which is to take advantage of the physical or operational similarities of products in their various aspects of construction and design. Additionally, these systems are identified as cellular manufacturing systems (CMS). In this paper, a meta-heuristic method that is based on combining genetic and greedy algorithms has been used in order to optimize and evaluate the performance criteria of the flexible job-shop scheduling problem. In order to improve the efficiency of the genetic algorithm, the initial population is generated by the greedy algorithm, and several elitist operators are used to improve the solutions. The greedy algorithm that is used to improve the generation of the initial population prioritizes the cells and the job in each cell and, thus, offers quality solutions. The proposed algorithm is tested over the P-FJSP dataset and compared with the state-of-the-art techniques of this literature. To evaluate the performance of the diversity, spacing, quality, and run-time criteria were used in a multi-objective function. The results of the simulation indicate the better performance of the proposed method as compared to the NRGA and NSGA-II methods.

2

A Reactive Search-Based Algorithm for Scheduling Multiprocessor Tasks on Two Dedicated Processors

Aïder Méziane, Baatout Fatma Zohra, Hifi Mhand

Annals of Computer Science and Information Systems

|

2020

|

Vol. 21

257--261

EN

In this paper, we propose a reactive search-based algorithm for solving the problem of scheduling multiprocessor tasks on two dedicated processors. An instance of the problem is characterized by a set of tasks divided into three subsets and two processors, where some tasks can be executed either on one processor or two processors. The goal of the problem is to determine the scheduling of all tasks minimizing the execution of the last assigned task. The proposed reactive search starts with a starting greedy solution. Next, a series of local operators combined with a tabu list are introduced in order to intensify the search process. The method is also reinforced with a drop and rebuild operator that is applied for diversifying the search process. Finally, the performance of the proposed method is evaluated on a set of benchmark instances, where its provided results are compared to those achieved by a recent method available in the literature. Encouraging results have been reached.

3

Interfejs do zdalnego sterowania ploterem z funkcją rozpoznawania obrazów

Kamiński M., Morawiec M.

Zeszyty Naukowe Wydziału Elektrotechniki i Automatyki Politechniki Gdańskiej

|

2017

|

Nr 57

37--42

PL

Maszyny numeryczne takie jak obrabiarki CNC, plotery czy drukarki 3D są coraz powszechniejsze w użytku. Na Politechnice Gdańskiej przygotowano pracę magisterską [12], której rezultaty przedstawiono w niniejszym artykule. Ze względu na objętość referatu, przedstawiono jedynie wybrane aspekty budowy plotera, aplikacji na urządzenie mobilne oraz przegląd zastosowanych algorytmów optymalizacji pod kątem szybkości rysowania. Aplikacja funkcjonuje w systemie Android, a komunikuje się z maszyną za pomocą interfejsu bluetooth. Aplikacja oferuje także możliwość optymalizacji tras, zarówno tych rysowanych, jak i nierysowanych, pokonywanych przez ploter. Jest to problem komiwojażera bez powrotu, który rozwiązany może być poprzez algorytmy: zachłanny, genetyczny, wspinaczkowy lub symulowanego wyżarzania.

EN

The topic is to build a CNC machine working as a plotter, and also create an application running on the Android operating system, which processes images, optimizes the code and allows to control the built machine. The examination is an estimation which of the methods used in this thesis is optimal and gives the best results in this type of problem, which is choosing the shortest path of the salesman problem. The purpose of the paper is to obtain the code processed by the numerical machine in the shortest possible time, which will be carried out in a short period of time with the proper accuracy of the work. Another important aspect is the implementation of an intuitive user interface that does not cause problems with support. The optimization methods used produce satisfactory results that are more or less practical depending on the problem. The effect in the form of drawn images is at a high level of accuracy. After many hours of working with the CNC machine using the created application, it can be seen that this is a useful set for both people who want to create their own images as well as for those seeking education in this field. The great advantage is that the design is very easily expandable so that it can acquire new, very useful features for a small amount of extra work in the form of adding new functionality.

4

Optymalizacja częściowych reguł asocjacyjnych względem liczby pomyłek

Zielosko B., Robaszkiewicz M.

Studia Informatica

|

2016

|

Vol. 37, nr 1

187--198

PL

Artykuł przedstawia optymalizację częściowych reguł asocjacyjnych generowanych przez algorytm zachłanny względem liczby pomyłek (błędnych zaklasyfikowań). Zaproponowana optymalizacja ma na celu: (i) uzyskanie reguł o stosunkowo dobrej jakości, które w kolejnych etapach badań zostaną wykorzystane do budowy klasyfikatorów, (ii) zmniejszenie liczby konstruowanych reguł, co ma znaczenie z punktu widzenia reprezentacji wiedzy. Praca przedstawia wyniki eksperymentalne dla zbiorów danych umieszczonych w Repozytorium Uczenia Maszynowego.

EN

In the paper, an optimization of partial association rules relative to number of misclassifications is presented. The aims of proposed optimization are: (i) construction of rules with small number of misclassifications, what is important from the point of view of construction of classifiers, (ii) decreasing the number of rules, what is important from the point of view of knowledge representation. The paper contains experimental results for data sets from UCI Machine Learning Repository.

5

A Minimum-Spanning-Tree-Inspired Algorithm for Channel Assignment in 802.11 Networks

Dolińska I., Jakubowski M., Masiukiewicz A., Rządkowski G., Piórczyński K.

International Journal of Electronics and Telecommunications

|

2016

|

Vol. 62, No. 4

379--388

EN

Channel assignment in 2.4 GHz band of 802.11 standard is still important issue as a lot of 2.4 GHz devices are in use. This band offers only three non-overlapping channels, so in crowded environment users can suffer from high interference level. In this paper, a greedy algorithm inspired by the Prim’s algorithm for finding minimum spanning trees (MSTs) in undirected graphs is considered for channel assignment in this type of networks. The proposed solution tested for example network distributions achieves results close to the exhaustive approach and is, in many cases, several orders of magnitude faster.

6

Approximation of Reset Thresholds with Greedy Algorithms

Ananichev D. S., Gusev V. V.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

221--227

EN

The problem of approximate computation of reset thresholds of synchronizing automata has gained a lot of attention recently. We introduce a broad class of algorithms that compute reset words and analyze their approximation ratios. We present three series of automata that reveal inherent limitations of greedy strategies for approximation of reset thresholds.

7

Sieci kognitywne MANET

Gajewski P., Łopatka J., Suchański M.

Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne

|

2014

|

nr 6

132--137

PL

Dokonano przeglądu zagadnień związanych z tworzeniem kognitywnych, mobilnych sieci doraźnych - MANET CR. Opisano dotychczasowe wyniki realizacji projektów związanych z opracowaniem i standaryzacją sieci radia kognitywnego - CR. Scharakteryzowano wybrane kognitywne rozwiązania dla mobilnych sieci doraźnych, głównie na podstawie wyników projektu CORASMA (Cognitive Radio for Spectrum Management) Europejskiej Agencji Obrony - EDA. Opisano przykład zastosowania algorytmu zachłannego dla rozproszonego zarządzania widmem w wojskowej sieci z grupowaniem węzłów. W zakończeniu omówiono drogę do uzyskania kognitywnej sieci radiowej dla potrzeb obronności kraju.

EN

In this paper a survey of the cognitive radio (CR) techniques for Mobile Ad Hoc Networks (MANET CR) is presented. The main results of up to now projects concerning development and standardization CR networks are described. The chosen solutions for MANET CR are also characterized. Here we mainly discuss the results of EDA project CORASMA, in which the greedy algorithm for frequency distributed management have been proposed for clustered MANET CR. The way to CR networks for national security is shown in the context of national and international activities in this area.

8

A Greedy Algorithm for Construction of Decision Trees for Tables with Many-Valued Decisions : A Comparative Study

Azad M., Chikalov I., Moshkov M., Zielosko B.

Fundamenta Informaticae

|

2013

|

Vol. 128, nr 1-2

1--15

EN

In the paper, we study a greedy algorithm for construction of decision trees. This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. Experimental results for data sets from UCI Machine Learning Repository and randomly generated tables are presented. We make a comparative study of the depth and average depth of the constructed decision trees for proposed approach and approach based on generalized decision. The obtained results show that the proposed approach can be useful from the point of view of knowledge representation and algorithm construction.

9

Greedy Algorithms for Construction of Approximate Tests for Decision Tables with Many-Valued Decisions

Azad M., Chikalov I., Moshkov M., Zielosko B.

Fundamenta Informaticae

|

2012

|

Vol. 120, nr 3/4

231-242

EN

The paper is devoted to the study of a greedy algorithm for construction of approximate tests (super-reducts). This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. We consider bounds on the precision of this algorithm relative to the cardinality of tests.

10

Approximate algorithm for β -decision rule optimization

Zielosko B., Moshkov M.

Studia Informatica

|

2011

|

Vol. 32, nr 2A

329-335

EN

In the paper greedy algorithm for construction of β decision rules and algorithm for construction of β -complete systems of decision rules are studied. Obtined bounds on accuracy of the considered algorithms are presented.

PL

W artykule został przedstawiony algorytm zachłanny dla konstruowania β -reguł decyzyjnych oraz dla konstruowania β -kompletnych systemów reguł decyzyjnych. Zostały zaprezentowane granice dokładności wyników uzyskiwanych za pomocą rozważanych algorytmów.

11

A greedy algorithm for the DNA sequencing by hybridization with positive and negative errors and information about repetitions

Kwarciak K., Formanowicz P.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2011

|

Vol. 59, nr 1

111-115

EN

In this paper a greedy algorithm for some variants of the sequencing by hybridization method is presented. In the standard version of the method information about repetitions is not available. In the paper it is assumed that a partial information of this type is a part of the problem instance. Here two simple but realistic models of this information are taken into consideration. The first one assumes it is known if a given element of a spectrum appears in the target sequence once or more than once. The second model uses the knowledge is a given element of a spectrum occurs in the analyzed sequence once, twice or at least three times. The proposed greedy algorithm solves the variant of the problem with positive and negative errors. Results of a computational experiment are reported which, among others, confirm that the additional information leads to the improvement of the obtained solutions. They also show that the more precise model of information increases the quality of reconstructed sequences.

12

Algorytm zachłanny dla konstruowania częściowych reguł asocjacyjnych

Zielosko B.

Studia Informatica

|

2010

|

Vol. 31, nr 2A

225-236

PL

W artykule przedstawiono sposób konstruowania częściowych reguł asocjacyjnych z wykorzystaniem algorytmu zachłannego. Podejście to jest odmienne od znanego algorytmu A priori i jego modyfikacji, wykorzystujących zbiory częste. Przedstawione wyniki badań oraz rezultaty z przeprowadzonych eksperymentów pokazują, że algorytm zachłanny pozwala konstruować stosunkowo małą liczbę krótkich, częściowych reguł asocjacyjnych o dobrej jakości, które pokrywają wszystkie obiekty danego systemu informacyjnego.

EN

The paper presents greedy algorithm for partial association rule construction. This approach is different from the known algorithm Apriori and its modifications based on frequent itemsets. Theoretical and experimental results show, that the greedy algorithm constructs relatively small number of short partial association rules which have good accuracy and cover all objects from given information system.

13

Greedy Algorithm with Weights for Decision Tree Construction

Moshkov M.Ju.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 3

285-292

EN

An approximate algorithm for minimization of weighted depth of decision trees is considered. A bound on accuracy of this algorithm is obtained which is unimprovable in general case. Under some natural assumptions on the class NP, the considered algorithm is close (from the point of view of accuracy) to best polynomial approximate algorithms for minimization of weighted depth of decision trees.

14

Sprzętowa implementacja zachłannego algorytmu kolorowania grafu

Wyrwoł B.

Elektronika : konstrukcje, technologie, zastosowania

|

2010

|

Vol. 51, nr 9

21-23

PL

Kolorowanie grafów znajduje zastosowanie wszędzie tam, gdzie konieczny jest podział zbioru na rozłączne podzbiory wg określonego kryterium jakie spełniają lub nie elementy zbioru. Większość algorytmów kolorowania realizowana jest zwykle na drodze programowej. W sytuacji, kiedy dużą rolę odgrywają uwarunkowania czasowe, konieczna jest realizacja sprzętowa z wykorzystaniem dedykowanego układu. W artykule przedstawiony został zachłanny algorytm kolorowania wierzchołków grafu oraz jego sprzętowa implementacja w układzie programowalnym FPGA. Dodatkowo omówiona została metoda reprezentacji danych opisujących strukturę grafu i przykład wykorzystania sprzętowego modułu kolorowania grafu, wspomagającego proces dekompozycji lingwistycznej, w systemie wnioskowania przybliżonego.

EN

Graph coloring algorithms are used wherever it is necessary to divide set on disjoint subsets according to specified criteria or not they meet the elements of the set. Most of the coloring algorithms are usually implemented as a computer or microcontroller program. To reduce computing time of the coloring result it is necessary to implement hardware using a dedicated chip. The paper presents graph greedy vertex algorithm and its hardware implementation in an FPGA chip. It describes also a graph data structure and finally implementation of the graph coloring module in the fuzzy hierarchical inference system. It is used in linguistic decomposition process of the knowledge base in the stage of the partitioning the rule base.

15

Greedy Algorithm for Construction of Partial Association Rules

Moshkov M.Ju., Piliszczuk M.

Fundamenta Informaticae

|

2009

|

Vol. 92, nr 3

259-277

EN

Partial association rules can be used for representation of knowledge, for inference in expert systems, for construction of classifiers, and for filling missing values of attributes. This paper is devoted to the study of approximate algorithms for minimization of partial association rule length. It is shown that under some natural assumptions on the class NP, a greedy algorithm is close to the best polynomial approximate algorithms for solving of this NP-hard problem. The paper contains various bounds on precision of the greedy algorithm, bounds on minimal length of rules based on an information obtained during the greedy algorithm work, and results of theoretical and experimental study of association rules for the most part of binary information systems.

16

Greedy Algorithm for Attribute Reduction

Zielosko B., Piliszczuk M.

Fundamenta Informaticae

|

2008

|

Vol. 85, nr 1-4

549-561

EN

In the paper the accuracy of greedy algorithm for construction of partial tests (superreducts) and partial decision rules is considered. Results of experiments with greedy algorithm are described.

17

Evolutionary and greedy exploration of the space of decision trees

Biedrzycki R., Arabas J.

Prace Naukowe Politechniki Warszawskiej. Elektronika

|

2006

|

z. 156

61-68

EN

This paper addresses the issue of the decision trees induction. We define the space of all possible trees and try to find good trees by searching that space. We compare performance of an evolutionary algorithm and standard, problem-specific algorithms (ID3, C4.5).

18

Dijkstra's algorithm revisited: the dynamic programming connexion

Sniedovich M.

Control and Cybernetics

|

2006

|

Vol. 35, no 3

599-620

EN

Dijkstra's Algorithm is one of the most popular algorithms in computer science. It is also popular in operations research. It is generally viewed and presented as a greedy algorithm. In this paper we attempt to change this perception by providing a dynamic programming perspective on the algorithm. In particular, we are reminded that this famous algorithm is strongly inspired by Bellman's Principle of Optimality and that both conceptually and technically it constitutes a dynamic programming successive approximation procedure par excellence. One of the immediate implications of this perspective is that this popular algorithm can be incorporated in the dynamic programming syllabus and in turn dynamic programming should be (at least) alluded to in a proper exposition/teaching of the algorithm.

19

Canonical greedy algorithms and dynamic programming

Lew A.

Control and Cybernetics

|

2006

|

Vol. 35, no 3

621-643

EN

There has been little work on how to construct greedy algorithms to solve new optimization problems efficiently. Instead, greedy algorithms have generally been designed on an ad hoc basis. On the other hand, dynamic programming has a long history of being a useful tool for solving optimization problems, but is often inefficient. We show how dynamic programming can be used to derive efficient greedy algorithms that are optimal for a wide variety of problems. This approach also provides a way to obtain less efficient but optimal solutions to problems where derived greedy algorithms are nonoptimal.

20

Prowadzenie połączeń przez kanał dla problemów MID-DCRP

Chmiel K.

Studia z Automatyki i Informatyki

|

1998

|

T. 23

53-82

PL

W pracy rozważana jest podklasa problemów o maksymalnej gęstości międzykolumnowej (MID-DCRP) klasy problemów gęstych DCRP. Przebadana została struktura tej klasy z punktu widzenia charakterystyki rozwiązania (Is, II, Ip), gdzie Is oznacza liczbę ścieżek, a II i Ip liczbę odpowiednio, lewych i prawych kolumn dodatkowych. Na tej podstawie wskazany został wielomianowy algorytm, prowadzący do optymalnego rozwiązania przy dwustopniowym kryterium liczby ścieżek i liczby kolumn.

EN

In the paper the class of maximum intercolumn density dense channel routing problems (MID-DCRP) is considered. The structure of the class with respect to the solution characteristic (Is, II, Ip) is investigated, where Is denotes the number of tracks and II, Ip denote the number of left and right additional columns, respectively. Presented results indicate a polynomial time algorithm, leading to the optimal solution in terms of the two level criterion: number of tracks - number of columns.