Wyniki wyszukiwania - BazTech

1

Rack cell configuration problem: a mathematical model and effective combined heuristic

Ratkiewicz Andrzej, Lewczuk Konrad

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2021

|

Vol. 69, nr 1

art. no. e135836

EN

This paper discusses the configuration of a space-effective rack cell for storing a given set of heterogeneous items. Rack cells are the primary components of rack storage areas. A rack cell configuration problem (RCCP) for heterogeneous storage is formulated as a combinatorial mathematical model. An effective heuristic for solving the RCCP in practical cases is presented. The proposed heuristic consists of multistage brute force searching of defined sets of feasible solutions and solving linear integer assignment problems by the branch-and-bound method. The developed algorithm was implemented and tested, and the rack cell obtained meets the modularity requirements in the design and operation of heterogeneous storage areas.

2

Flying ant colony optimization algorithm for combinatorial optimization

Fidanova S., Atanassov K.

Studia Informatica

|

2017

|

Vol. 38, nr 4

31--40

EN

In this paper is introduce "flying" ants in Ant Colony Optimization (ACO). In traditional ACO algorithms the ants construct their solution regarding one step forward. In proposed ACO algorithm, the ants make their decision, regarding more than one step forward, but they include only one new element in their solutions.

PL

Artykuł przedstawia "latające" mrówki w problemie optymalizacji algorytmów mrówkowych. W tradycyjnych podejściach dla algorytmów mrówkowych agenci (mrówki) budują swoje rozwiązanie w kolejnych krokach. W zaproponowanym podejściu optymalizacji algorytmu mrówkowego agenci podejmują decyzję na podstawie więcej niż jednego kroku, jednakże tylko jeden element wprowadzany jest do rozwiązania.

3

Algorithms solving the Internet shopping optimization problem with price discounts

Musial J., Pecero J. E., Lopez-Loces M. C., Fraire-Huacuja H. J., Bouvry P., Blazewicz J.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2016

|

Vol. 64, nr 3

505--516

EN

The Internet shopping optimization problem arises when a customer aims to purchase a list of goods from a set of web-stores with a minimum total cost. This problem is NP-hard in the strong sense. We are interested in solving the Internet shopping optimization problem with additional delivery costs associated to the web-stores where the goods are bought. It is of interest to extend the model including price discounts of goods. The aim of this paper is to present a set of optimization algorithms to solve the problem. Our purpose is to find a compromise solution between computational time and results close to the optimum value. The performance of the set of algorithms is evaluated through simulations using real world data collected from 32 web-stores. The quality of the results provided by the set of algorithms is compared to the optimal solutions for small-size instances of the problem. The optimization algorithms are also evaluated regarding scalability when the size of the instances increases. The set of results revealed that the algorithms are able to compute good quality solutions close to the optimum in a reasonable time with very good scalability demonstrating their practicability.

4

Accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem

Nagórny Z.

Journal of Applied Computer Science

|

2012

|

Vol. 20, nr 1

51-67

EN

The objective of this work was to study the accuracy influence of the hardware implementation of the Hopfield network on the solution quality for the travelling salesman problem. In this work the 8-bit accuracy influence of the hardware implementation of weights, activation functions, and external input signals on the quality of achieved solutions for 100 randomly generated instances of the 10-city TSP was studied and comparable results in comparison with the simulation in which the network was simulated using double precision floating point numbers were obtained. The results show that the hardware implementation of the Hopfield network with the 8-bit accuracy allows to obtain satisfactory solutions for the TSP. It should be also noted that the network described in this work utilizes the novel method of auto-tuning of Hopfield network parameters and thanks to this method, in contrast to other works, none of the network parameters is tuned for a given solved TSP on the basis of preliminary simulations. The Hopfield network presented in this work is destined for the hardware implementation. The application of the hardware implementation of the network could significantly decrease the time required to obtain the combinatorial problem solution in comparison with methods using von Neumann architecture computers.

5

Zastosowanie algorytmu mrówkowego do wyznaczania maksymalnej grupy wzajemnie połączonych elementów

Schiff K.

Czasopismo Techniczne. Elektrotechnika

|

2008

|

R. 105, z. 1-E

63-78

PL

W artykule zaprezentowano algorytmy mrówkowe wyznaczające największą klikę w grafie, za pomocą której modeluje się problem wyznaczania największego ze skupień wzajemnie połączonych elementów elektronicznych na płytce drukowanej w celu minimalizacji długości połączeń między nimi, a w konsekwencji minimalizacji ilości materiału zużytego na ich wytworzenie. W artykule zaprezentowano algorytm oparty na odmiennych aspektach zachowania się mrówek w porównaniu z dotychczas opracowanymi algorytmami. Główną różnicą między algorytmami jest faza eksploracji, która została wprowadzona w prezentowanym algorytmie. Opracowany algorytm porównano z Algorytmem 457 pod względem wyznaczanego wymiaru klik. Dokonano również porównania procedur lokalnego przeszukiwania (2,1)-wymiany i procedury opartej na metaheurystyce kolonii mrówek.

EN

In this paper an ANT algorithm, which is used to find a maximum group of mutually connected electronic elements in order to minimize the total length of connections, is presented. The new algorithm differs from algorithms which have been presented in scientific papers until now. The main difference is a phase of ANT exploration which is absent in other ANT algorithms. Sizes of maximum clique indicated by ANT algorithm and the Algorithm 457 are compared. The influence of the local search was presented also and the (2,1)-exchange local procedure and the ANT procedure of local search was compared.

6

Algorytm genetyczny z mutacją ruletkową

Dudek G.

Informatyka Teoretyczna i Stosowana

|

2007

|

R. 7, nr 12

91-107

PL

Przedstawiono algorytm genetyczny z reprezentacją binarną i nowym operatorem mutacji wykorzystującym metodę koła ruletki. Prawdopodobieństwo mutacji bitu w klasycznym algorytmie genetycznym jest stałe. W proponowanej metodzie uzależnia się to prawdopodobieństwo od przebiegu procesu ewolucyjnego. Loci, których mutacja z 0 na 1 (z 1 na 0) we wcześniejszych generacjach poprawiła ocenę chromosomu, mutowane są częściej z 0 na 1 (z 1 na 0). Do ustalenia prawdopodobieństwa mutacji bitu używa się metody koła ruletki. Metodę zobrazowano przykładami optymalizacji kombinatorycznej ze zmiennymi binarnymi. W jednomodalnych problemach optymalizacji kombinatorycznej odnotowano przyspieszenie zbieżności algorytmu do optimum.

EN

A genetic algorithm with binary representation and a new operator or mutation using the roulette wheel method is presented. The probability of the bit mutation in a classical genetic algorithm is fixed. In the proposed method this probability is dependent on the history of the evolutionary process. Loci, whose mutation from 0 to 1 (from 1 to 0) improved the evaluation of the chromosome in early generations, are mutated frequently tram 0 to 1 (from 1 to 0). The roulette mutation bas adaptive control of the probability of the lotus mutation. Each locus of the chromosome bas two coefficients of mutation intensity: from 0 to 1- w 0-1 and from 1 to 0 - w 1-0. The values of these coefficients are updated in each generation after mutation. If the mutation from 0 to 1 (from 1 to 0) brings positive effects (an increase in the chromosome fitness), the value of the appropriate w 0-1 (w 1-0) coefficient increases. In case of negative effects the value of the coefficient decreases. A high value of w 0-1(i) gives information that in the previous realization of the evolutionary process the change of ith bit from 0 to 1 (from 1 to 0) in most cases brought the improvement in fitness. The probability of the bit mutation from 0 to l (from 1 to 0) - p 0-1(i) (p 1-0(i)) is proportional to the w 0-1(i) (w 1-0(i)) value for this bit. The bits for mutation are chosen using the roulette wheel method. The roulette wheel is composed of two sectors "0-1" and "1-0". Each locus bas the subsector S 0-1(i) in the "0-1" sector and subsector S 1-0(i) in the "1-0" sector. The sizes of these subsectors are dependent on the probabilities p 0-1(i) and p 1-0(i). The operation of mutation consists of: sampling with replacement of q chromosomes and a number indicating subsector on the roulette wheel which in turn determines the lotus for mutation and direction of mutation (from 0 to 1 or from 1 to 0) for each of the above mentioned chromosomes. The experiments showed that the operator of roulette mutation significantly speeds up the convergence of the algo-rithm in the unimodal tasks of the combinatorial optimization. The effectiveness of the roulette mutation depends on the availability of information about the sensitivity of objective function to the changes in the variable values. If the direction of an influence of a certain variable on the value of the objective function depends on the values of others variables, it may lead to the improper operation of the roulette mutation, deterioration of the exploratory properties and to the convergence of the algorithm to the local optimum.

7

Neural networks for the N-Queens Problem : a review

Mańdziuk J.

Control and Cybernetics

|

2002

|

Vol. 31, no 2

217-248

EN

Neural networks can be successfully applied to solving certain types of combinatorial optimization problems. In this paper several neural approaches to solving constrained optimization problems are presented and their properties discussed. The main goal of the paper is to present various improvements to the wellknown Hopfield models which are intensively used in combinatorial optimization domain. These improvements include deterministic modifications (binary Hopfield model with negative self-feedback connections and Maximum Neural Network model), stochastic modifications (Gaussian Machine), chaotic Hopfield-based models (Chaotic Neural Network and Transiently Chaotic Neural Network), hybrid approaches (Dual-mode Dynamic Neural Network and Harmony Theory approach) and finally modifications motivated by digital implementation feasibility (Strictly Digital Neural Network). All these models are compared based on a commonly used benchmark prohlem - the N-Queens Problem (NQP). Numerical results indicate that each of modified Hopfield models can be effectively used to solving the NQP. Coonvergence to solutions rate of these methods is very high - usually close to 100%. Experimental time requirements are generally low - polynomial in most casos. Some discussion of non-neural, heuristic approaches to solving the NQP is also presented in the paper.

8

Neural network models for combinatorial optimization : a survey of deterministic, stochastic and chaotic approaches

Smith K., Potvin J., Kwok T.

Control and Cybernetics

|

2002

|

Vol. 31, no 2

183-216

EN

This paper serves as a tutorial on the use of neural networks for solving combinatorial optimization problems. It reviews the two main classes of neural network models : the gradient-based neural networks such as the Hopfield network, and the deformable template approaches such as the elastic net method and self organizing maps. In each class, the original model is presented, its limitations discussed, and subsequent developments and extensions are reviewed. Particular emphasis is placed on stochastic and chaotic variations on the neural network models designed to improve the optimization performance. Finally, the performance of these neural network models is compared and discussed relative to other heuristic approaches.

9

Binary neural networks for N-queens problems and their VLSI implementations

Funabiki N., Kurokawa T., Ohta M.

Control and Cybernetics

|

2002

|

Vol. 31, no 2

271-296

EN

Combinatorial optimization problems compose an important class of matliematical problems that include a variety of practical applications, such as VLSI design automation, communication network design and control, job scheduling, games, and genome informatics. These problems usually have a large number of variables to be solved. For example, problems for VLSI design automation require several million variables. Besides, thieir computational complexity is often intractable due to NP-hardness. Neural networks have provided elegant solutions as approximation algorithms to these hard problems due to their natural parallelism and their affinity to hardware realization. Particularly, binary neural networks have great potential to conform to current digital VLSI design technology, because any state and parameter in binary neural networks are expressed in a discrete fashion. This paper presents our studies on binary neural networks to the N-queens problem, and the three different approaches to VLSI implementations focusing on the efficient realization of the synaptic connection networks. Reconfigurable devices such as CPLDs and FPGAs contribute the realization of a scalable architecture with the ultra high speed of computation. Based on the proposed architecture, more than several thousands of binary neurons can be realized on one FPGA chip.

10

Modyfikacja widoczności w algorytmach mrówkowych rozwiązujących problem dostawy

Skórczyński A.

Studia Informatica

|

2001

|

Vol. 22, nr 4

235-244

PL

Problem dostawy jest przykładem złożonej optymalizacji kombinatorycznej i należy do grupy problemów NP-zupełnych. Rodzina algorytmów mrówkowych doskonale radzi sobie ze złożonymi problemami tej grupy. W niniejszej pracy zaproponowano modyfikację algorytmów mrówkowych rozwiązujących problem dostawy. W pracy przedstawiono wpływ zastosowanej modyfikacji na działanie algorytmów mrówkowych oraz jakość uzyskanych rozwiązań dla zbiorów danych wejściowych o różnych rozmiarach.

EN

The delivery problem is an example of a complex combinatorial optimization, which belongs to the NP-complete group. The family of algorithms is suitable for solving the problems of this group. In this paper we present a new modification of algorithms solving the delivery problem. We present the effect of applied modification to the results of some algorithms for the sets of various sizes.

11

Wielomianowy heurystyczny algorytm wyznaczania kliki maksymalnej O(n4)

Schiff K.

Elektrotechnika i Elektronika

|

2000

|

T. 19, z. 1

17--20

PL

W artykule przedstawiono wielomianowy heurystyczny algorytm wyznaczania kliki maksymalnej o złożoności obliczeniowej rzędu O(n4). Algorytm został oparty o opracowaną metodę sukcesywnego wyznaczania, bezpośrednio z macierzy sąsiedztwa wierzchołków najbardziej nadających się do utworzenia kliki o maksymalnym wymiarze.

EN

In this paper heuristic algorithm with poły nominal computational complexity O(n4) for maximal clique problem is presented. This algorithm is based on successive designation of vertex from incidence matrix, which are the most suitable for maximal clique creation.

12

Declarativity in modelling and problem solving

Niederliński A.

Control and Cybernetics

|

2000

|

Vol. 29, no 1

325-339

EN

The paper discusses a new trend in the modelling software for combinatorial and mixed combinatorial-continuous decision problems. The trend, aiming at solving those problems by the simple activity of properly describing them, is best exemplified by a constantly inereasing spectrum of Constraint Logic Programming (CLP) languages. The first such language was Prolog. After a short historical survey concentrating mainly on Prolog, main characteristics of a modern, commercially successful CLP language - CHIP - are presented, discussed and illustrated. The CLP approach to problem solving is compared with traditional Operation Research approaches.

13

Rozmyte podejście do wielokryterialnego programowania sieciowego w warunkach niepewności

Hapke M., Jaszkiewicz A., Słowiński R.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 123

155-168

PL

W pracy proponuje się dwuetapową metodę rozwiązywania problemu rozmytego wielokryterialnego programowania sieciowego. Rozmyte są parametry czasowe poszczególnych operacji. Pierwszy etap polega na wygenerowaniu zbioru uszeregowań niezdominowanych, który następnie jest przeglądany przez decydenta w drugim etapie w celu wyboru najbardziej kompromisowego uszeregowania. Do realizacji pierwszego etapu stosuje się rozmytą wersję metaheurystycznej procedury Paretosymulowanego wyżarzania. W etapie drugim do wyboru uszeregowania najbardziej kompromisowego postanowiono wykorzystać ideę dialogowej metody Przeglądu Wiązką Światła, w której decydent może sam kierować poszukiwaniem najlepszego kompromisu.

EN

A new two-stage method for solving fuzzy project scheduling problems with multiple objectives is presented. The method accepts fuzzy time parameters of project activities. In the first stage a set of non-dominated schedules is calculated using a fuzzy version of the Pareto-simulated annealing metaheuristic procedure. Then in the second this set is interactively analyzed using a fuzzy version of the 'Light Beam Search' - procedure. It supports the decision maker in selecting the best compromise schedule.

14

Algorytmy sprawiedliwego kolorowania grafów

Damrath H.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

1998

|

z. 123

111-120

PL

Problemy kolorowania grafów należą do najtrudniejszych problemów optymalizacji kombinatorycznej z punktu widzenia złożoności obliczeniowej. W niniejszej pracy rozważono zagadnienie sprawiedliwego kolorowania wierzchołków grafu, tj. takiego kolorowania, że krotności użycia dowolnych kolorów różnią się najwyżej o 1. Pokazano, że problem ten jest NP-trudny i sformułowano dwa algorytmy heurystyczne dla usprawiedliwienia rozwiązań uzyskanych innymi algorytmami kolorowania. Podano doświadczenia komputerowe z implementacji i testowania tych algorytmów na identycznych seriach grafów pseudolosowych.

EN

Graph coloring problems belong to the hardest combinatorial optimization problems with respect to the computational complexity. In this paper we consider the problem of equitable coloring the vertices of a graph, i.e. such a coloring that the sizes of color classes differ by at most 1. We show that the problem is NP-hard and give two heuristic algorithms for tranforming colorings obtained by other standard algorithms into equitable solutions. General considerations are supported by computational experience gained with implementation and profiling of these algorithms on identical series of pseudorandom graphs.