Search

In this paper we consider two closely related problems of selecting a diverse subset of points with respect to squared Euclidean distance. Given a set of points in Euclidean space, the first problem is to find a subset of a specified size M maximizing the sum of squared Euclidean distances between the chosen points. The second problem asks for a minimum cardinality subset of points, given a constraint on the sum of squared Euclidean distances between them. We consider the computational complexity of both problems and propose exact dynamic programming algorithms in the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, these algorithms have a pseudo-polynomial time complexity. We also develop an FPTAS for the special case of the first problem, where the dimension of the Euclidean space is bounded by a constant.

The basic principles of selectionism were transferred in a simplified form from population genetics to the field of evolutionary computation in order to solve applied problems of optimization and adaptation. Considerable practical experience has been gained for the almost half a century of development in this field of computer science, and interesting theoretical results have been obtained. One of the main properties of biological systems is modularity, which manifests itself at all levels of their organization, starting with molecular genetics and ending with entire organisms and their communities. In this survey, the phenomena and patterns associated with modularity in genetics and evolutionary computation are compared. The similarities and differences in the results from these areas of research are analyzed from the point of view of modularity, and the possibilities for sharing knowledge between them are discussed.

We propose a new genetic algorithm (GA) with optimal recombination and adaptive restarts for the asymmetric travelling salesman problem (ATSP). The optimal recombination problem (ORP) is solved in a crossover operator based on a new exact algorithm that solves the ATSP on cubic digraphs. We use an adaptive restart rule based on the Schnabel census estimate. A computational experiment on the known benchmark instances shows that the proposed algorithm yields results competitive to those of state-of-the-art algorithms for the ATSP and confirms that the ORP may be used successfully in genetic algorithms. This abstract for the Hot-off-the-Press track of GECCO 2021 summarizes work that has appeared in Eremeev A.V., Kovalenko Yu.V. A memetic algorithm with optimal recombination for the asymmetric traveling salesman problem. Memetic Computing 12, 23-36 (2020).

We propose a polylithic method for medium-term scheduling of a large-scale industrial plant operating in a continuous mode. The method combines a decomposition approach, a genetic algorithm (GA) an...

The paper presents a comparison between three approaches to solving the length-bounded maximum multicommodity flow problem with unit edge-lengths. Following the first approach, Garg and K?nemann?s, we developed an improved fully polynomial time approximation scheme for this problem. As the second alternative, we considered the well-known greedy approach. The third approach is the one that yields exact solutions by means of a standard LP solver applied to an LP model on the time-expanded network. Computational experiments are carried out on benchmark graphs and the graphs that model software defined satellite networks, to compare the proposed algorithms with an exact linear programming solver. The results of the experiments demonstrate a trade-off between the computing time and the precision of algorithms under consideration.

The field of evolutionary algorithms (EAs) emerged in the area of computer science due to transfer of ideas from biology and developed independently for several decades, enriched with techniques from probability theory, complexity theory and optimization methods. In this paper, we consider some recent results form the EAs theory transferred back into biology. The well-known biotechnological procedure SELEX (Systematic Evolution of Ligands by EXponential enrichment) is viewed as an experimental implementation of an evolutionary algorithm. Theoretical bounds on EAs runtime are applied to model SELEX search for a regulatory region consisting of promoter and enhancer sequences. A comparison of theoretical bounds to the results of computational simulation indicates some cases where the theoretical bounds give favorable prediction, while simulation requires prohibitive computational resource.

It has been shown before that some results from the theory of evolutionary algorithms (EAs) may be used for the analysis of population dynamics in biology. In the present paper, we study the EAs without elite individuals, where the fitness-proportionate selection is used, on the class of Royal Road fitness functions. The behavior of EAs with these fitness functions may be considered as a model of population dynamics in the case of fitness landscape with several neutrality regions. We obtain lower and upper bounds on the expected time of evolving the fittest possible genotype for the Royal Road fitness function. It is expected the obtained results to be useful in development of modeling tools for biological populations.

The paper considers the problem of scheduling software modules on a multi-core processor, taking into account the limited bandwidth of the data bus and the precedence constraints. Two problem formulations with different levels of problem-specific detail are suggested and both shown to be NP-hard. A mixed integer linear programming (MILP) model is proposed for the first problem formulation, and a greedy algorithm is developed for the second one. An experimental comparison of the results of the greedy algorithm and the MILP solutions found by CPLEX solver is carried out.

In this paper, we consider the problem of finding a minimum cardinality subset of vectors, given a constraint on the sum of squared Euclidean distances between all vectors of the chosen subset. This problem is closely related to the well-known Maximum Diversity Problem. The main difference consists in swapping the constraint with the optimization criterion. We prove that the problem is NP-hard in the strong sense. An exact algorithm for solving this problem is proposed. The algorithm has a pseudo-polynomial time complexity in the special case of the problem, where the dimension of the space is bounded from above by a constant and the input data are integer.

We study a problem in which at least a given quantity of a single product has to be partitioned into lots, and lots have to be assigned to the unrelated parallel machines for processing so that the maximum machine completion time or the sum of machine completion times is minimized. Machine dependent lower and upper bounds on the lot size are given. The product can be continuously divisible or discrete. We derive optimal polynomial time algorithms for several special cases of the problem. For other cases we provide NP-hardness proofs and demonstrate existence of fully polynomial time approximation schemes.

Under consideration is the electric power flow optimization problem for an electric power system which typically arises in calculation of electrical power auctions in the “day-ahead” and balancing markets. It was established that the problem of finding a feasible flow in the balancing market is NP-hard in the strong sense even in case of one generator. The problem of finding an optimal flow in the day-ahead market is proved to be NP-hard even with one generator and without controlled cuts.

We consider a multicriterial optimization problem for volumes of buffers in a production line. We assume that the line has a series-parallel structure, and during its operation equipment stops occur due to failures, stops that are random in the moments when they arise and in their durations. The volumes of buffers are integer-valued and bounded from above. As criteria we consider the average production rate of the line, capital costs for installing buffers, and the inventory cost for intermediate products. To approximate the Pareto optimal set we use evolutionary algorithms SIBEA and SEMO. Problems with larger dimension experimentally support the advantage of the modified SEMO algorithm with respect to the hypervolume of the resulting set of points.

The paper is devoted to upper bounds on the expected first hitting times of the sets of local or global optima for non-elitist genetic algorithms with very high selection pressure. The results of this paper extend the range of situations where the upper bounds on the expected runtime are known for genetic algorithms and apply, in particular, to the Canonical Genetic Algorithm. The obtained bounds do not require the probability of fitness-decreasing mutation to be bounded by a constant less than one., Comment: Submitted to Yugoslav Journal of Operations Research. arXiv admin note: text overlap with arXiv:1512.02047

In this paper, we consider the problem of estimation of physical performance level of cosmonauts in long-term space flight, given the data collected during regular locomotor training exercises. The physical performance level of a cosmonaut is measured in terms of “physiological cost” of work, which is calculated as a function of heart rate, running speed and axial load. An algorithm for estimation of the physical performance level, using the data on the regular training on a treadmill is proposed. The algorithm is based on the principles of linear extrapolation and bisection search. The proposed algorithm is tested on the real data measured in the regular training of Russian cosmonauts on board of the International Space Station and compared to a more simple approach and the standard onboard test of physical performance level. The experimental results suggest that the proposed algorithm may be useful for the estimation of the physical performance level of cosmonauts in long-term space flights.

In this paper we consider the following Maximum Diversity Subset problem. Given a set of points in Euclidean space, find a subset of size M maximizing the squared Euclidean distances between the chosen points. We propose an exact dynamic programming algorithm for the case of integer input data. If the dimension of the Euclidean space is bounded by a constant, the algorithm has a pseudo-polynomial time complexity. Using this algorithm, we develop an FPTAS for the special case where the dimension of the Euclidean space is bounded by a constant. We also propose a new proof of strong NP-hardness of the problem in the general case.

The success of a modern enterprize is substantially determined by the effectiveness of staff selection and formation of various kinds of functional groups. Creation of such groups requires consideration of different factors depending on the activity of the groups. The problem of production groups formation, considered in this paper, asks for an assignment of workers to jobs taking into account the implicational constraints. The first result of the paper states the NP-hardness of the problem under consideration. The second result is a branch and bound method, which uses supplementary assignment problems for computing bounds. A software implementation of the algorithm is made, and a computational experiment is carried out, comparing the proposed algorithm with the CPLEX solver on randomly generated input data.

In this paper, we describe a non-convex constrained quadratic programming problem arising in short wave transmitting antenna array synthesis and provide preliminary computational results. We consider problem instances for three different antenna designs including up to 25 radiators. In the computational experiments, BARON package is compared to the gradient optimization method, applied to the unconstrained problem formulation using the penalty function method. Global optimality of the obtained solutions is established using BARON package the smallest instances of 4 radiators. On small instances, both methods have demonstrated similar results, while on larger instances significant difference has been observed. The set of local optima is studied experimentally. It is established that even though the problem instances have numerous local optima, the objective function in many local optima has the same value.