Wyniki wyszukiwania - BazTech

1

An ant algorithm for the maximum number of 3-cliques in 3-partite graphs

Schiff Krzysztof

Control and Cybernetics

|

2021

|

Vol. 50, No. 2

347--358

EN

The problem of finding the maximum number of d- vertices cliques (d = 3) in d-partite graph (d = 3) when graph density q is lower than 1 is an important problem in combinatorial optimization and it is one of many NP-complete problems. For this problem a meta-heuristic algorithm has been developed, namely an ant colony optimization algorithm. In this paper a new development of this ant algorithm and experimental results are presented. The problem of finding the maximum number of 3-vertices cliques can be encountered in computer image analysis, computer vision applications, automation and robotic vision systems. The optimal solution of this problem boils down to finding a set of 3-vertices cliques in a 3-partite graph and this set should have cardinality as high as possible. The elaborated ant colony algorithm can be easily modified for d-dimensional problems, that is for finding the maximum number of d-vertices cliques in a d-partite graph.

2

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.

3

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.

4

On necessary and suﬃcient conditions for stability and quasistability in combinatorial multicriteria optimization

Kuzmin K. G., Nikulin Y. V., Makela M. M.

Control and Cybernetics

|

2017

|

Vol. 46, no. 4

361--382

EN

We consider a multiple objective combinatorial optimization problem with an arbitrary vector-criterion. The necessary and suﬃcient conditions for stability and quasistability are obtained for large classes of problems with partial criteria possessing certain properties of regularity.

5

Analysis of a multimodal transport network in the region with an extremely cold climate

Shevtsov A. A., Zhuravskaya M. A.

Archiwum Wiedzy Inżynierskiej

|

2017

|

T. 2, Nr 1

75--77

EN

The role and importance of a multimodal transport network for the territory of the Republic of Sakha (Yakutia) – a region with harsh climatic conditions are defined. The experience of European and, in particular, Scandinavian countries is analyzed with the integration of multimodal technologies into a real operating transport and logistics network. The transport and logistics potential of Yakutia is analyzed. The importance of settlements as potential multimodal centers of transport and logistics network based on combinatorial optimization methods is determined.

6

Shift Design with Answer Set Programming

Abseher M., Musliu N., Woltran S., Gebser M., Schaub T.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 1

1--25

EN

Answer Set Programming (ASP) is a powerful declarative programming paradigm that has been successfully applied to many different domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling and travel allotment. In this paper, we approach another important task, namely, the shift design problem, aiming at an alignment of a minimum number of shifts in order to meet required numbers of employees (which typically vary for different time periods) in such a way that over- and understaffing is minimized. We provide an ASP encoding of the shift design problem, which, to the best of our knowledge, has not been addressed by ASP yet. Our experimental results demonstrate that ASP is capable of improving the best known solutions to some benchmark problems. Other instances remain challenging and make the shift design problem an interesting benchmark for ASP-based optimization methods.

7

Optimization of linear functions on a cyclic permutation. Based on the random search

Grebennik I., Baranov O., Chorna A., Gorbacheva E.

ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes

|

2016

|

Vol. 5, No 3

211--216

EN

For creating adequate mathematical models of combinatorial problems of constructing optimal cyclic routes, mathematical modeling and solving a number of planning and control tasks solutions of optimization problems on the set of cyclic permutations are required. Review of the publications on combinatorial optimization demonstrates that the optimization problem on the cyclic permutations have not been studied sufficiently. This paper is devoted to solving optimization problem of a linear function with linear constraints on the set of cyclic permutations. For solving problems of this class using of known methods, taking into account the properties of a combinatorial set of cyclic permutations, is proposed. For this purpose we propose a method based on the ideology of random search. Heuristic method based on the strategy of the branch and bound algorithm is proposed to solve auxiliary optimization problem of a linear function without constraints on the set of cyclic permutations. Since application of the branch and bound algorithm immediately leads to an exponential growth of the complexity with increasing the dimension of the problem a number of modifications are suggested. Modifications allow reducing computational expenses for solving higher dimension problems. The effectiveness of the proposed improvements is demonstrated by computational experiments.

8

Combinatorial approaches to the capital-budgeting problem

Pichugina O.

ECONTECHMOD : An International Quarterly Journal on Economics of Technology and Modelling Processes

|

2016

|

Vol. 5, No 4

29--36

EN

Optimization approaches, combinatorial and continuous, to a capital-budgeting problem (CBP) are presented. This NP-hard problem, traditionally modelled as a linear binary problem, is represented as a biquadratic over an intersection of a sphere and a supersphere. This allows applying nonlinear optimization to it. Also, the method of combinatorial and surface cuttings (MCSC) is adopted to (CBP). For the single constrained version (1CBP), new combinatorial models are introduced based on joint analysis of the constraint, objective function, and feasible region. Equivalence of (1CBP) to the multichoice knapsack problem (MCKP) is shown. Peculiarities of Branch&Bound techniques to (1CBP) are described.

9

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.

10

Parameter Synthesis for Timed Kripke Structures

Knapik M., Penczek W.

Fundamenta Informaticae

|

2014

|

Vol. 133, nr 2/3

211--226

EN

We show how to synthesise parameter values under which a given property, expressed in a certain extension of CTL, called RTCTLP, holds in a parametric timed Kripke structure. We prove the decidability of parameter synthesis for RTCTLP by showing how to restrict the infinite space of parameter valuations to its finite subset and employ a brute-force algorithm. The bruteforce approach soon becomes intractable, therefore we propose a symbolic algorithm for RTCTLP parameter synthesis. Similarly to the fixed-point symbolic model checking approach, we introduce special operators which stabilise on the solution. The process of stabilisation is essentially a translation from the RTCTLP parameter synthesis problem to a discrete optimization task. We show that the proposedmethod is sound and complete and provide some complexity results. We argue that this approach leads to new opportunities in model checking, including the use of integer programming and related tools.

11

New evaluations of ant colony optimization start nodes

Fidanova S., Marinov P., Atanassov K.

Control and Cybernetics

|

2014

|

Vol. 43, no. 3

471--485

EN

Ant Colony Optimization (ACO) is a stochastic search method that mimics the social behavior of real ant colonies, managing to establish the shortest route to the feeding sources and back. Such algorithms have been developed to arrive at near-optimal solutions to large-scale optimization problems, for which traditional mathematical techniques may fail. In this paper, the semi-random start procedure is applied. A new kind of evaluation of start nodes of the ants is developed and several starting strategies are prepared and combined. The idea of semi-random start is related to a better management of the ants. This new technique is tested on the Multiple Knapsack Problem (MKP). A Comparison among the strategies applied is presented in terms of quality of the results. A comparison is also carried out between the new evaluation and the existing one. Based on this comparative analysis, the performance of the algorithm is discussed. The study presents the idea that should be beneficial to both practitioners and researchers involved in solving optimization problems.

12

Graph based discrete optimization in structural dynamics

Blachowski B., Gutkowski W.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2014

|

Vol. 62, nr 1

91--102

EN

In this study, a relatively simple method of discrete structural optimization with dynamic loads is presented. It is based on a tree graph, representing discrete values of the structural weight. In practical design, the number of such values may be very large. This is because they are equal to the combination numbers, arising from numbers of structural members and prefabricated elements. The starting point of the method is the weight obtained from continuous optimization, which is assumed to be the lower bound of all possible discrete weights. Applying the graph, it is possible to find a set of weights close to the continuous solution. The smallest of these values, fulfilling constraints, is assumed to be the discrete minimum weight solution. Constraints can be imposed on stresses, displacements and accelerations. The short outline of the method is presented in Sec. 2. The idea of discrete structural optimization by means of graphs. The knowledge needed to apply the method is limited to the FEM and graph representation. The paper is illustrated with two examples. The first one deals with a transmission tower subjected to stochastic wind loading. The second one with a composite floor subjected to deterministic dynamic forces, coming from the synchronized crowd activities, like dance or aerobic.

13

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.

14

Predictive Maintenance Sensors Placement by Combinatorial Optimization

Borissova D. I., Mustakerov I. C., Doukovska L. A.

International Journal of Electronics and Telecommunications

|

2012

|

Vol. 58, No. 2

153-158

EN

The strategy of predictive maintenance monitoring is important for successful system damage detection. Maintenance monitoring utilizes dynamic response information to identify the possibility of damage. The basic factors of faults detection analysis are related to properties of the structure under inspection, collect the signals and appropriate signals processing. In vibration control, structures response sensing is limited by the number of sensors or the number of input channels of the data acquisition system. An essential problem in predictive maintenance monitoring is the optimal sensor placement. The paper addresses that problem by using mixed integer linear programming tasks solving. The proposed optimal sensors location approach is based on the difference between sensor information if sensor is present and information calculated by linear interpolation if sensor is not present. The tasks results define the optimal sensors locations for a given number of sensors. The results of chosen sensors locations give as close as possible repeating the curve of structure dynamic response function. The proposed approach is implemented in an algorithm for predictive maintenance and the numerical results indicate that together with intelligent signal processing it could be suitable for practical application.

15

Qualitative stability analysis of multicriteria combinatorial minimin problems

Emelichev V. A., Karelkina O. V., Kuzmin K. G.

Control and Cybernetics

|

2012

|

Vol. 41, no. 1

57-79

EN

A multicriteria combinatorial problem with minimin partial criteria is considered. Necessary and sufficient conditions for the five known stability types of the problem are obtained. These stability types describe in different ways the behavior of the Pareto and lexicographic sets of the problem under initial data perturba- tions of the vector criteria.

16

On the robustness of optimal solutions for combinatorial optimization problems

Libura M.

Control and Cybernetics

|

2009

|

Vol. 38, no 3

671-685

EN

We consider the so-called generic combinatorial optimization problem, where the set of feasible solutions is some family of subsets of a finite ground set with specified positive initial weights of elements, and the objective function represents the total weight of elements of a feasible solution. We assume that the weights of all elements may be perturbed simultaneously and independently up to a given percentage of their initial values. A feasible solution which minimizes the worst-case relative regret, is called a robust solution. The maximum percentage level of perturbations, for which an initially optimal solution remains robust, is called the robustness radius of this solution. In this paper we study the robustness aspect of initially optimal solutions and provide lower bounds for their robustness radii.

17

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.

18

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.

19

On the computational complexity of designing DNA randomizations in a combinatorial protein experiment

Błażewicz J., Dziurdza B., Markiewicz W. T., Oguz C.

Foundations of Computing and Decision Sciences

|

2007

|

Vol. 32, No. 3

185-197

EN

In combinatorial protein experiments based on phage display and similar methods, protein libraries are constructed by expressing a partially randomized DNA (gene) libraries. Since the distribution of proteins in the output library depends on nucleotides frequencies in DNA library one has to adjust them carefully taking into account diversity-completeness trade-off and results from possible previous cycles of experiments (i.e. knowledge about sequences that have been already obtained and tested). The approach considered in this paper allows to maximize the number of new amino acid sequences physically generated in each cycle of the experiment. The mathematical model of the described approach is presented and its computational complexity is analyzed.

20

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.