Pub. online:5 Aug 2022Type:Research ArticleOpen Access
Journal:Informatica
Volume 16, Issue 2 (2005), pp. 213–240
Abstract
The article describes a hierarchical decision making framework for the evaluation and improvement/redesign of composite systems. The framework is based on Hierarchical Morphological Multicriteria Design (HMMD) and corresponding morphological clique problem which realize “partitioning/synthesis macroheuristic”. The system evaluation process consists in hierarchical integration of expert judgment (as ordinal estimates): a method of integration tables or the above-mentioned morphological approach. As a result, ordinal multi-state classification is realized. The system improvement/redesign process is examined as the selection and planning of redesign operations while taking into account operations attributes (e.g., required resources, effectiveness) and binary relations (equivalence, complementarity, precedence) on the operation sets. For modeling the system improvement process several combinatorial optimization models are used (knapsack problem, multiple choice problem, etc.) including HMMD.
The suggested approach is illustrated by realistic numerical example for two-floor building. This applied problem is examined from the viewpoint of earthquake engineering.
Pub. online:1 Jan 2018Type:Research ArticleOpen Access
Journal:Informatica
Volume 29, Issue 3 (2018), pp. 499–516
Abstract
Crossover operators play a very important role by creation of genetic algorithms (GAs) which are applied in various areas of computer science, including combinatorial optimization. In this paper, fifteen genetic crossover procedures are designed and implemented using a modern C# programming language. The computational experiments have been conducted with these operators by solving the famous combinatorial optimization problem – the quadratic assignment problem (QAP). The results of the conducted experiments on the characteristic benchmark instances from the QAP instances library QAPLIB illustrate the relative performance of the examined crossover operations.
All crossover procedures are publicly available with the intention that the GA researchers will choose a procedure which suits the individual demand at the highest degree.
Journal:Informatica
Volume 27, Issue 2 (2016), pp. 463–487
Abstract
This paper improves an infra-chromatic bound which is used by the exact branch-and-bound maximum clique solver BBMCX (San Segundo et al., 2015) as an upper bound on the clique number for every subproblem. The infra-chromatic bound looks for triplets of colour subsets which cannot contain a 3-clique. As a result, it is tighter than the bound obtained by widely used approximate-colouring algorithms because it can be lower than the chromatic number. The reported results show that our algorithm with the new bound significantly outperforms the state-of-the-art algorithms in a number of structured and uniform random graphs.
Journal:Informatica
Volume 26, Issue 3 (2015), pp. 509–522
Abstract
The Generalized Traveling Salesman Problem is one of a well known complex combinatorial optimization problems. Equality-Generalized Traveling Salesman Problem is a particular case of it. The main objective of the problem it is to find a minimum cost tour passing through exactly one node from each cluster of a large-scale undirected graph. Multi-agent approaches are successfully used nowadays for solving real life complex problems. The aim of the current paper is to illustrate some agent-based algorithms, including particular ant-based models and virtual robots-agents with specific properties for solving Equality-Generalized Traveling Salesman Problem.
Journal:Informatica
Volume 26, Issue 1 (2015), pp. 17–32
Abstract
Abstract
In several areas like Global Optimization using branch-and-bound methods, the unit n-simplex is refined by bisecting the longest edge such that a binary search tree appears. This process generates simplices belonging to different shape classes. Having less simplex shapes facilitates the prediction of the further workload from a node in the binary tree, because the same shape leads to the same sub-tree. Irregular sub-simplices generated in the refinement process may have more than one longest edge when . The question is how to choose the longest edge to be bisected such that the number of shape classes is as small as possible. We develop a Branch-and-Bound (B&B) algorithm to find the minimum number of classes in the refinement process. The developed B&B algorithm provides a minimum number of eight classes for a regular 3-simplex. Due to the high computational cost of solving this combinatorial problem, future research focuses on using high performance computing to derive the minimum number of shapes in higher dimensions.
Journal:Informatica
Volume 23, Issue 3 (2012), pp. 391–404
Abstract
The article describes multi-function system testing based on fusion (or revelation) of clique-like structures. The following sets are considered: (i) subsystems (system parts or units/components/modules), (ii) system functions and a subset of system components for each system function, and (iii) function clusters (some groups of system functions which are used jointly). Test procedures (as units testing) are used for each subsystem. The procedures lead to an ordinal result (states, colors) for each component (e.g., ‘out of service’, ‘major faults’, ‘minor faults’, ‘trouble free service’). For each system function a graph over corresponding system components is examined while taking into account ordinal estimates/colors of the components. Further, an integrated graph for each function cluster is considered (this graph integrates the graphs for corresponding system functions). For the integrated graph structure revelation problems are under examination (revelation of some subgraphs which can lead to system faults). Numerical examples illustrate the approach and problems.
Journal:Informatica
Volume 20, Issue 4 (2009), pp. 519–538
Abstract
The article addresses the issues of combinatorial evolution of standards in transmission of multimedia information including the following: (a) brief descriptions of basic combinatorial models as multicriteria ranking, knapsack-like problems, clustering, combinatorial synthesis, multistage design, (b) a description of standard series (MPEG) for video information processing and a structural (combinatorial) description of system changes for the standards, (c) a set of system change operations (including multi-attribute description of the operations and binary relations over the operations), (d) combinatorial models for the system changes, and (e) a multistage combinatorial scheme (heuristic) for the analysis of the system changes. Expert experience is used. Numerical examples illustrate the suggested problems, models, and procedures.
Journal:Informatica
Volume 20, Issue 2 (2009), pp. 255–272
Abstract
In this paper, an efficient hybrid genetic algorithm (HGA) and its variants for the well-known combinatorial optimization problem, the quadratic assignment problem (QAP) are discussed. In particular, we tested our algorithms on a special type of QAPs, the structured quadratic assignment problems. The results from the computational experiments on this class of problems demonstrate that HGAs allow to achieve near-optimal and (pseudo-)optimal solutions at very reasonable computation times. The obtained results also confirm that the hybrid genetic algorithms are among the most suitable heuristic approaches for this type of QAPs.
Journal:Informatica
Volume 17, Issue 2 (2006), pp. 237–258
Abstract
Recently, genetic algorithms (GAs) and their hybrids have achieved great success in solving difficult combinatorial optimization problems. In this paper, the issues related to the performance of the genetic search in the context of the grey pattern problem (GPP) are discussed. The main attention is paid to the investigation of the solution recombination, i.e., crossover operators which play an important role by developing robust genetic algorithms. We implemented seven crossover operators within the hybrid genetic algorithm (HGA) framework, and carried out the computational experiments in order to test the influence of the recombination operators to the genetic search process. We examined the one point crossover, the uniform like crossover, the cycle crossover, the swap path crossover, and others. A so-called multiple parent crossover based on a special type of recombination of several solutions was tried, too. The results obtained from the experiments on the GPP test instances demonstrate promising efficiency of the swap path and multiple parent crossovers.
Journal:Informatica
Volume 13, Issue 3 (2002), pp. 311–332
Abstract
Real life scheduling problems are solved by heuristics with parameters defined by experts, as usual. In this paper a new approach is proposed where the parameters of various heuristics and their random mixtures are optimized to reduce the average deviations from the global optimum.
In many cases the average deviation is a stochastic and multi-modal function of heuristic parameters. Thus a stochastic global optimization is needed. The Bayesian heuristic approach is developed and applied for this optimization. That is main distinctive feature of this work. The approach is illustrated by flow-shop and school scheduling examples. Two versions of school scheduling models are developed for both traditional and profiled schools. The models are tested while designing schedules for some Lithuanian schools. Quality of traditional schedules is defined by the number of teacher “windows”. Schedules of profiled schools are evaluated by user defined penalty functions. That separates clearly subjective and objective data. This is the second specific feature of the proposed approach.
The software is developed for the Internet environment and is used as a tool for research collaboration and distance graduate studies. The software is available at web-sites and can be ran by standard net browsers supporting Java language. The care is taken that interested persons could easily test the results and apply the algorithms and software for their own problems.