Informatica

In the paper we propose a genetic algorithm based on insertion heuristics for the vehicle routing problem with constraints. A random insertion heuristic is used to construct initial solutions and to reconstruct the existing ones. The location where a randomly chosen node will be inserted is selected by calculating an objective function. The process of random insertion preserves stochastic characteristics of the genetic algorithm and preserves feasibility of generated individuals. The defined crossover and mutation operators incorporate random insertion heuristics, analyse individuals and select which parts should be reinserted. Additionally, the second population is used in the mutation process. The second population increases the probability that the solution, obtained in the mutation process, will survive in the first population and increase the probability to find the global optimum. The result comparison shows that the solutions, found by the proposed algorithm, are similar to the optimal solutions obtained by other genetic algorithms. However, in most cases the proposed algorithm finds the solution in a shorter time and it makes this algorithm competitive with others.

In this paper we focus on a specific class of XML schema inference approaches – so-called heuristic approaches. Contrary to grammar-inferring approaches, their result does not belong to any specific class of grammars and, hence, we cannot say anything about their features from the point of view of theory of languages. However, the heuristic approaches still form a wider and more popular set of approaches due to natural and user-friendly strategies. We describe a general framework of the inference algorithms and we show how its particular phases can be further enhanced and optimized to get more reasonable and realistic output. The aim of the paper is (1) to provide a general overview of the heuristic inference process and existing approaches, (2) to sum up the improvements and optimizations we have proposed so far in our research group, and (3) to discuss possible extensions and open problems which need to be solved. Hence, it enables the reader to get acquainted with the field fast.

The paper deals with the problem of high-school time-tabling that is important in applications, but hard for solving. The algorithm is presented for timetabling based on Multi-start and Simulated Annealing with parameters adapted using the Bayes approach. The algorithm proposed is compared with other timetabling algorithms using the web-based software. A multi-start algorithm is a simple way to provide the convergence, if the number of uniformly distributed starting points is large. A disadvantage is slow convergence.

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.

Estimation and modelling problems as they arise in many data analysis areas often turn out to be unstable and/or intractable by standard numerical methods. Such problems frequently occur in fitting of large data sets to a certain model and in predictive learning. Heuristics are general recommendations based on practical statistical evidence, in contrast to a fixed set of rules that cannot vary, although guarantee to give the correct answer. Although the use of these methods became more standard in several fields of sciences, their use for estimation and modelling in statistics appears to be still limited. This paper surveys a set of problem-solving strategies, guided by heuristic information, that are expected to be used more frequently. The use of recent advances in different fields of large-scale data analysis is promoted focusing on applications in medicine, biology and technology.

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.

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.

The objective of this paper is the description, justification, and web-based implementation of polynomial time algorithms for equilibrium search of Quadratic Bimatrix Games (QBG). An algorithm is proposed combining exact and heuristic parts. The exact part has the Irelevant Fraud (IF) component for cases when an equilibrium exists with no pure strategies. The Direct Search (DS) component finds a solution if an equilibrium exists in pure strategies. The heuristic Quadratic Strategy Elimination (QSE) part applies IF and DS to reduced matrices obtained by sequential elimination of strategies that lead to non-positive IF solutions. Finally, penalties needed to prevent unauthorized deals are calculated based on Nash axioms of two-person bargaining theory. In the numeric experiments QSE provided correct solution in all examples. The novel results include necessary and sufficient conditions when the QBG problem is solved by IF algorithm, the development of software and the experimental testing of large scale QBG problems up to n=800. The web-site http://pilis.if.ktu.lt/~jmockus includes this and accompanying optimization models.

Given a set of objects with profits (any, even negative, numbers) assigned not only to separate objects but also to pairs of them, the unconstrained binary quadratic optimization problem consists in finding a subset of objects for which the overall profit is maximized. In this paper, an iterated tabu search algorithm for solving this problem is proposed. Computational results for problem instances of size up to 7000 variables (objects) are reported and comparisons with other up-to-date heuristic methods are provided.

We study single machine scheduling problems, where processing times of the jobs are exponential functions of their start times. For increasing functions, we prove strong NP-hardness of the makespan minimization problem with arbitrary job release times. For decreasing functions, maximum lateness minimization problem is proved to be strongly NP-hard and total weighted completion time minimization problem is proved to be ordinary NP-hard. Heuristic algorithms are presented and computationally tested for these problems.