Search

To solve multimodal optimization problems, a new niching genetic algorithm named tournament crowding genetic algorithm based on Gaussian mutation is proposed. A comparative analysis of this algorithm to other crowding algorithms and to parallel hill-climbing algorithm has shown the advantages of the proposed algorithm in many cases. The FPR criterion to estimate the distribution of population elements is proposed and it is shown that computation of this criterion is advisable to estimate algorithms solving multimodal problems of finding global and local maxima.

Two modifications of the repeated iterated tabu algorithm for solving the quadratic assignment problem (with and without kernel allocation technology) are proposed. These modifications are analyzed and compared with the best modern algorithms for solving this problem. The efficiency of the developed algorithms is shown, in particular, for large-scale problems for which new records were found with their help.

This article briefly reviews software and hardware means of modern computer engineering that allow to construct efficient systems of parallel computing. Structural schemes are presented and the execution of combinations of parallel optimization algorithms such as a portfolio and a team are described in detail. Special features of organizing the execution of combinations of algorithms are indicated that are related to both the synchronization of parallel execution of the algorithms of a team and the coordinated processing of the data obtained by the algorithms.

The kernel technology is proposed to solve discrete optimization problems. It forms solution kernel and allows efficient stochastic perturbations of this solution in iterative schemes. Comparative analysis of the two versions of the new algorithm for the quadratic assignment problem (with and without kernel allocation technology) and modern algorithms demonstrated the efficiency of this technology in terms of speed and solution quality. The kernel technology can be easily incorporated into the available algorithms.

This paper investigates the impact of communication between optimization algorithms running in parallel. In particular, we focus on the weighted maximum cut (WMAXCUT) problem and compare different communication strategies between teams of GES algorithms running in parallel. The results obtained by teams encourage the development of team algorithms. They were significantly better than the algorithmic portfolio (no communication) approach and suggest that the communication between algorithms running in parallel is a promising research direction.

A new algorithm based on the global equilibrium search (GES) is developed to solve the weighted max-cut problem and is compared with currently the best solution algorithms. The advantages of the GES algorithm both in the performance and in the possibility of finding the best solutions are shown.

A new algorithm based on global equilibrium search (GES) is developed to solve an unconstrained binary quadratic programming (UBQP) problem. It is compared with the best methods of solving this problem. The GES algorithm is shown to be better both in speed and solution quality.

The authors propose an approach to the solution of the maxcut problem. It is based on the global equilibrium search method, which is currently one of the most efficient discrete programming methods. The efficiency of the proposed algorithm is analyzed.

In this note we investigate the performance of global equilibrium search based heuristics on the weighted MAX-SAT problem. Three variants of the approach are implemented and compared with other existing algorithms on publicly available benchmark instances. The reported computational results indicate high efficiency of the method considered.

We describe a heuristic method for solving the unconstrained binary quadratic optimization problem based on a global equilibrium search framework. We investigate performance of the proposed approach and compare it with the best available solver [G. Palubeckis, Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Ann. Oper. Res., 131 (2004), pp. 259-282; G. Palubeckis, Unconstrained binary quadratic optimization. Available at http://www.soften.ktu.lt/∼gintaras/binqopt.html (Last accessed December 2006).] on well-known benchmarks instances. The reported computational results indicate a high efficiency of the heuristic.

This paper briefly reviews the current state of the art in the field of discrete optimization problems. Emphasis is on the generalization of the experience gained at the V. M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine in research and development of solution methods and software for various classes of complicated discrete programming problems.

Some of the fundamental problems in coding theory can be formulated as extremal graph problems. Finding estimates of the size of correcting codes is important from both theoretical and practical perspectives. We solve the problem of finding the largest correcting codes using previously developed algorithms for optimization problems in graphs. We report new exact solutions and estimates.

New results are presented concerning binary correcting codes, such as deletion-correcting codes, transposition-correction codes, and codes for the Z-channel. These codes are important due to the possibility of packet loss and corruption on internet transmissions. It is known that the problem of finding the largest correcting codes can be reduced to a well-known combinatorial optimization problem on graphs, the maximum independent set problem. A general scheme of organizing a local search for the maximum independent set problem is discussed. Based on the developed heuristics, an exact branch-and-bound algorithm is proposed, which is able to find exact solutions for graphs with over 500 vertices within a reasonable time.