Skip to main content

Über dieses Buch

This volume is a comprehensive collection of extended contributions from the Workshop on Computational Optimization 2014, held at Warsaw, Poland, September 7-10, 2014.

The book presents recent advances in computational optimization. The volume includes important real problems like parameter settings for controlling processes in bioreactor and other processes, resource constrained project scheduling, infection distribution, molecule distance geometry, quantum computing, real-time management and optimal control, bin packing, medical image processing, localization the abrupt atmospheric contamination source and so on.

It shows how to develop algorithms for them based on new metaheuristic methods like evolutionary computation, ant colony optimization, constrain programming and others. This research demonstrates how some real-world problems arising in engineering, economics, medicine and other domains can be formulated as optimization tasks.



Finding Optimal Discretization Orders for Molecular Distance Geometry by Answer Set Programming

The Molecular Distance Geometry Problem (MDGP) is the problem of finding the possible conformations of a molecule by exploiting available information about distances between some atom pairs. When particular assumptions are satisfied, the MDGP can be discretized, so that the search domain of the problem becomes a tree. This tree can be explored by using an interval Branch & Prune (iBP) algorithm. In this context, the order given to the atoms of the molecules plays an important role. In fact, the discretization assumptions are strongly dependent on the atomic ordering, which can also impact the computational cost of the iBP algorithm. In this work, we propose a new partial discretization order for protein backbones. This new atomic order optimizes a set of objectives, that aim at improving the iBP performances. The optimization of the objectives is performed by Answer Set Programming (ASP), a declarative programming language that allows to express our problem by a set of logical constraints. The comparison with previously proposed orders for protein backbones shows that this new discretization order makes iBP perform more efficiently.
Douglas Gonçalves, Jacques Nicolas, Antonio Mucherino, Carlile Lavor

Estimation of Edge Infection Probabilities in the Inverse Infection Problem

Several methods have been proposed recently to estimate the edge infection probabilities in infection or diffusion models. In this paper we will use the framework of the Generalized Cascade Model to define the Inverse Infection Problem—the problem of calculating these probabilities. We are going to show that the problem can be reduced to an optimization task and we will give a particle swarm based method as a solution. We will show, that direct estimation of the separate edge infection values is possible, although only on small graphs with a few thousand edges. To reduce the dimensionality of the task, the edge infection values can be considered as functions of known attributes on the vertices or edges of the graph, this way only the unknown coefficients of these functions have to be estimated. We are going to evaluate our method on artificially created infection scenarios. Our main points of interest are the accuracy and stability of the estimation.
András Bóta, Miklós Krész, András Pluhár

On a Quantum Algorithm for the Resolution of Systems of Linear Equations

The numerical resolution of systems of linear equations is an important problem which recurs continously in applied sciences. In particular, it represents an indispensable tool in applied mathematics which can be utilized as a foundation to more complicated problems (e.g. optimization problems, partial differential equations, eigenproblems, etc.). In this work, we introduce a solver for systems of linear equations based on quantum mechanics. More specifically, given a system of linear equations we introduce an equivalent optimization problem which objective function defines an electrostatic potential. Then, we evolve a many-body quantum system immersed in this potential and show that the corresponding Wigner quasi-distribution function converges to the global energy minimum. The simulations are performed by using the time-dependent, ab-initio, many-body Wigner Monte Carlo method. Finally, by numerically emulating the (random) process of measurement, we demonstrate that one can extract the solution of the original mathematical problem. As a proof of concept we solve 3 simple, but different, linear systems with increasing complexity. The outcomes clearly show that our suggested approach is a valid quantum algorithm for the resolution of systems of linear equations.
J. M. Sellier, I. Dimov

Synthesis of Self-Adaptive Supervisors of Multi-Task Real-Time Object-Oriented Systems Using Developmental Genetic Programming

This chapter presents a procedure for automatic creation of self-adaptive artificial supervisors of multi-task real-time object-oriented systems (MT RT OOS). The procedure is based on developmental genetic programming. Early UML diagrams describing a MT RT OOS are used as input data to the procedure. Next, an artificial supervisor which optimizes the system use is automatically generated. The supervisor is self-adaptive what means that it is capable of keeping optimality of the system in spite of disruptions that may occur dynamically in time of the system work. A representative example of creation of a supervisor of building a house illustrates the procedure. Efficiency of the procedure from the point of view of self-adaptivity of the supervisor is investigated.
Krzysztof Sapiecha, Leszek Ciopiński, Stanisław Deniziak

Direct Shooting Method for Optimal Control of the Highly Nonlinear Differential-Algebraic Systems

In the paper the optimal control of highly nonlinear differential-algebraic systems (DAEs) is discussed. The direct shooting method is seen as an efficient tool for control of the complex real-life technological processes, where dynamics and conservation laws are presented. To stabilize the optimization algorithm, the multiple shooting method was proposed. The multiple shooting approach introduces new decision variables and constraints to the problem, but it can preserve the stability of the process, the continuity of the differential state trajectories and enables parallel computation of the mathematical model. The conditions for the frequency of shots, to establish the well-conditioned optimization problem, are considered. The proposed method was tested on the mathematical model of the fed-batch fermentor for penicillin production process, which is a highly nonlinear multistage differential-algebraic system. The numerical simulations were executed in MATLAB environment using Wroclaw Center for Networking and Supercomputing.
Paweł Dra̧g, Krystyn Styczeń

A Review on the Direct and Indirect Methods for Solving Optimal Control Problems with Differential-Algebraic Constraints

In the article the main features of direct and indirect approaches for solving optimal control problems were presented. The mentioned methods can be effectively applied in the Model Predictive Control of the complex technological systems in electrical, chemical and aerospace engineering, often described by nonlinear differential-algebraic equations. Among the direct and indirect methods for solving optimal control problems one can mention Euler-Lagrange equations, direct optimization methods and indirect gradients methods.
Paweł Dra̧g, Krystyn Styczeń, Marlena Kwiatkowska, Andrzej Szczurek

InterCriteria Analysis of ACO and GA Hybrid Algorithms

In this paper, the recently proposed approach for multicriteria decision making—InterCriteria Analysis (ICA)—is presented. The approach is based on the apparatus of the index matrices and the intuitionistic fuzzy sets. The idea of InterCriteria Analysis is applied to establish the relations and dependencies of considered parameters based on different criteria referred to various metaheuristic algorithms. A hybrid scheme using Genetic Algorithm (GA) and Ant Colony Optimization (ACO) is used for parameter identification of E. coli MC4110 fed-batch cultivation process model. In the hybrid GA-ACO, the GA is used to find feasible solutions to the considered optimization problem. Further ACO exploits the information gathered by GA. This process obtains a solution, which is at least as good as—but usually better than—the best solution devised by GA. Moreover, a comparison with both the conventional GA and ACO identification results is presented. Based on ICA the obtained results are examined and conclusions about existing relations and dependencies between model parameters of the E. coli process and algorithms parameters and outcomes, such as number of individuals, number of generations, value of the objective function and computational time, are discussed.
Olympia Roeva, Stefka Fidanova, Marcin Paprzycki

A Two-Stage Look-Ahead Heuristic for Packing Spheres into a Three-Dimensional Bin of Minimum Length

In this work we propose a two-stage look-ahead heuristic for packing a given set of spheres into a three-dimensional bin of fixed height and depth but variable length. The problem consists to pack all the spheres into the bin of minimum length. This problem is also known under the name of three-dimensional strip packing problem. The computational results conducted on a set of benchmark instances taken from the literature indicates that the proposed method is effective since it improves most of the best known results by finding new upper bounds for the length of the bin.
Hakim Akeb

Handling Lower Bound and Hill-Climbing Strategies for Sphere Packing Problems

In this paper the 3-dimensional sphere packing problem is solved by using an iterative tree search-based heuristic. The goal of the problem is to determine a minimum length of the container that contains all available spheres/items without overlapping. Such a length is searched by applying a tree search that combines hill-climbing and bounding strategies. All branches of the tree are created following eligible positions associated to successive items to pack and the bounds are computed by applying a greedy procedure. Because the number of positions is large, the hill-climbing strategy is introduced in order to filter the search by choosing some best paths. The proposed algorithm is evaluated on benchmark instances taken from the literature and on new benchmark instances: the provided results are compared to those reached by recent methods available in the literature. The proposed method remains competitive and it yields new results.
Mhand Hifi, Labib Yousef

Multi-Objective Meta-Evolution Method for Large-Scale Optimization Problems

The paper deals with the method for searching the proper values of behavioural (relevant) parameters of optimization algorithms for large-scale problems. The authors formulate the optimization task as multi-objective problem taking into account two criteria. The first criterion corresponds to the estimation of the accuracy of a solution, whereas the second one represents the time computational complexity of the main optimization algorithm. In the present study, predominant Pareto optimality concept is used to solve this problem. Moreover, the authors propose to use a much less complicated algorithm in the main optimization engine, while a more advanced approach in the meta-evolution core. The engine of the target optimization algorithm is realised applying the particle swarm optimization algorithm, while the core of the meta-evolution process is implemented by means of the multi-objective evolutionary algorithm. The advantages and limitations of the proposed meta-evolution method were examined employing well-practised test functions described in the literature.
Piotr Przystałka, Andrzej Katunin

Dispersive Flies Optimisation and Medical Imaging

One of the main sources of inspiration for techniques applicable to complex search space and optimisation problems is nature. This paper introduces a new metaheuristic—Dispersive Flies Optimisation (DFO)—whose inspiration is beckoned from the swarming behaviour of flies over food sources in nature. The simplicity of the algorithm facilitates the analysis of its behaviour. A series of experimental trials confirms the promising performance of the optimiser over a set of benchmarks, as well as its competitiveness when compared against three other well-known population based algorithms. The convergence-independent diversity of DFO algorithm makes it a potentially suitable candidate for dynamically changing environment. In addition to diversity, the performance of the newly introduced algorithm is investigated using the three performance measures of accuracy, efficiency and reliability and its outperformance is demonstrated in the paper. Then the proposed swarm intelligence algorithm is used as a tool to identify microcalcifications on the mammographs. This algorithm is adapted for this particular purpose and its performance is investigated by running the agents of the swarm intelligence algorithm on sample mammographs whose status have been determined by the experts. Two modes of the algorithms are introduced in the paper, each providing the clinicians with a different set of outputs, highlighting the areas of interest where more attention should be given by those in charge of the care of the patients.
Mohammad Majid al-Rifaie, Ahmed Aber

An Efficient Solution of the Resource Constrained Project Scheduling Problem Based on an Adaptation of the Developmental Genetic Programming

An adaptation of the Developmental Genetic Programming (DGP) for solving an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) is investigated in the paper. In DGP genotypes (the search space) and phenotypes (the solution space) are distinguished and a genotype-to-phenotype mapping (GPM) is used. Thus, genotypes are evolved without any restrictions and the whole search space is explored. RCPSP is a well-known NP-hard problem but in its original formulation it does not take into consideration initial resource workload and it minimises the makespan. We consider a variant of the problem when resources are only partially available and a deadline is given but it is the cost of the project that should be minimized. The goal of the evolution is to find a procedure constructing the best solution of the problem for which the cost of the project is minimal. The paper presents new evolution process for the DGP as well as a comparison with other genetic approaches. Experimental results showed that our approach gives significantly better results compared with other methods.
Grzegorz Pawiński, Krzysztof Sapiecha

Bayesian-Based Approach to Application of the Genetic Algorithm to Localize the Abrupt Atmospheric Contamination Source

We apply the Bayesian inference in combination with the Genetic algorithm (GA) to the problem of the atmospheric contaminant source localization. The algorithm input data are the on-line incoming concentrations of released substance registered by sensors network. The proposed reconstruction algorithm is firstly adjusted and tested based on the data from the synthetic experiment. The proposed GA scan 5-dimensional parameters space searching for the contaminant source coordinates (x,y), release strength (Q) and the atmospheric transport dispersion coefficients. Based on the performed tests the most efficient GA configuration is identified. To speed up the algorithm the dynamical termination criteria, founded on the probabilistic requirements regarding the searched parameters value, is proposed. Then, we apply developed algorithm to localize the release source utilizing data from the field tracer experiment conducted in May 2001 at the Kori nuclear site. We demonstrate successful localization of the continuous contamination source in very complicated hilly terrain surrounding the Kori nuclear site. Results indicate the probability of a source to occur at a particular location with a particular release strength.
A. Wawrzynczak, M. Jaroszynski, M. Borysiewicz
Weitere Informationen

Premium Partner