Skip to main content
main-content

Über dieses Buch

This volume is a comprehensive collection of extended contributions from the Workshop on Computational Optimization 2015. It presents recent advances in computational optimization. The volume includes important real life problems like parameter settings for controlling processes in bioreactor, control of ethanol production, minimal convex hill with application in routing algorithms, graph coloring, flow design in photonic data transport system, predicting indoor temperature, crisis control center monitoring, fuel consumption of helicopters, portfolio selection, GPS surveying 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 problems.

Inhaltsverzeichnis

Frontmatter

Fast Output-Sensitive Approach for Minimum Convex Hulls Formation

The paper presents an output-sensitive approach for the formation of the minimum convex hulls. The high speed and close to the linear complexity of this method are achieved by means of the input vertices distribution into the set of homogenous units and their filtration. The proposed algorithm uses special auxiliary matrices to control the process of computation. Algorithm has a property of the massive parallelism, since the calculations for the selected units are independent, which contributes to their implementation by using the graphics processors. In order to demonstrate its suitability for processing of the large-scale problems, the paper contains a number of experimental studies for the input datasets prepared according to the uniform, normal, log-normal and Laplace distributions.
Artem Potebnia, Sergiy Pogorilyy

Local Search Algorithms for Portfolio Selection: Search Space and Correlation Analysis

Modern Portfolio Theory dates back from the fifties, and quantitative approaches to solve optimization problems stemming from this field have been proposed ever since. We propose a metaheuristic approach for the Portfolio Selection Problem that combines local search and Quadratic Programming, and we compare our approach with an exact solver. Search space and correlation analysis are performed to analyse the algorithm’s performance, showing that metaheuristics can be efficiently used to determine optimal portfolio allocation.
Giacomo di Tollo, Andrea Roli

Optimization of Fuel Consumption in Firefighting Water Capsule Flights of a Helicopter

This article presents a possible use of ABC method for optimization of fuel consumption of helicopter which transport water capsule. There are lot of attibutes of flight e.g. the mass of the capsule, velocity, altitude, aerodynamic coefficients of the capsule, and horizontal and vertical winds. The presented method is focused on mentioned attributes. The problem is very important because helicopters are used in real hughe fire and it will be quite good if the fueal needed for this will be as low as possible. That is why authors presents theoretical models of flight of a bag filled with water which is then dropped from an aircraft moving horizontally. The resulet achived by numerical computations are later compared with the results measured for the trajectory of a capsule of water dropped from a helicopter. There ia also a discussion of the experimental and numerical results achieved in mentioned experiment.
Jacek M. Czerniak, Dawid Ewald, Grzegorz Śmigielski, Wojciech T. Dobrosielski, Łukasz Apiecionek

Practical Application of OFN Arithmetics in a Crisis Control Center Monitoring

In this paper there is a comparision of fuzzy arithmetic calculations in two different notations. The first is well-known L-R notation proposed by Dubois-Prade. It is well known for the researchers who deal with fuzzy logic. The second if OFN notation. This notation was introduced by Kosiński. The same data was used for comparative calculations using the benchmark “Dam and Crisis control center paradox”. There was an observation of water level at the dam with two trends: when the water level increases and decreases. This could cause the different short-term forecast for mentioned situation. The result which was achieved using two different fuzzy arithmetic showed, that OFN notation is sensitive to the trend differences. The authors showed that it provides an extra value which is a relationship between the fuzzy logic and the trend of the observer phenomena.
Jacek M. Czerniak, Wojciech T. Dobrosielski, Łukasz Apiecionek, Dawid Ewald, Marcin Paprzycki

Forecasting Indoor Temperature Using Fuzzy Cognitive Maps with Structure Optimization Genetic Algorithm

Fuzzy cognitive map (FCM) is a soft computing methodology that allows to describe the analyzed problem as a set of nodes (concepts) and connections (links) between them. In this paper the Structure Optimization Genetic Algorithm (SOGA) for FCMs learning is presented for prediction of indoor temperature. The proposed approach allows to automatically construct and optimize the FCM model on the basis of historical multivariate time series. The SOGA defines a new learning error function with an additional penalty for coping with the high complexity present in an FCM with a large number of concepts and connections between them. The aim of this study is the analysis of usefulness of the Structure Optimization Genetic Algorithm for fuzzy cognitive maps learning on the example of forecasting the indoor temperature of a house. A comparative analysis of the SOGA with other well-known FCM learning algorithms (Real-Coded Genetic Algorithm and Multi-Step Gradient Method) was performed with the use of ISEMK (Intelligent Expert System based on Cognitive Maps) software tool. The obtained results show that the use of SOGA allows to significantly reduce the structure of the FCM model by selecting the most important concepts, connections between them and keeping a high forecasting accuracy.
Katarzyna Poczęta, Alexander Yastrebov, Elpiniki I. Papageorgiou

Correlation Clustering by Contraction, a More Effective Method

In this article we propose two effective methods to produce a near optimal solution for the problem of correlation clustering. We study their properties at different circumstances, and show that the inner structure generated by a tolerance relation has effect on the accuracy of the methods. Finally, we show that there is no royal road to the sequence of clusterings.
László Aszalós, Tamás Mihálydeák

Synthesis of Power Aware Adaptive Embedded Software Using Developmental Genetic Programming

In this paper we present a method of synthesis of adaptive schedulers for power aware real-time embedded software. We assume that the system is specified as a task graph, which should be scheduled on multi-core embedded processor with low-power processing capabilities. First, the developmental genetic programming is used to generate the scheduler and the initial schedule. The scheduler and the initial schedule are optimized taking into consideration power consumption as well as self-adaptivity capabilities. During the system execution the scheduler modifies the schedule whenever execution time of the recently finished task occurred shorter or longer than expected. The goal of rescheduling is to minimize the power consumption while all time constraints will be satisfied. We present real-life example as well as some experimental results showing advantages of our method.
Stanisław Deniziak, Leszek Ciopiński

Flow Design and Evaluation in Photonic Data Transport Network

Development of sophisticated photonic transmission systems enabled evolution of photonic data transport networks towards cost-efficient and energy-efficient platforms capable to carry enormous traffic. Given access to technologically advanced equipment, network operator faces a series of decision problems related to how to efficiently use this technology. In this paper, we propose a mathematical model of modern photonic network with wavelength division multiplexing (WDM). Proposed model is an instance of multi-commodity flow optimization formulation related to specific construction of network graph. Given optimal solution of the considered optimization problem can be evaluated through a series of indicators determining quality and performance of the solution.
Mateusz Dzida, Andrzej Ba̧k

Introducing the Environment in Ant Colony Optimization

Meta-heuristics are general-purpose methods for global optimization, which take generally inspiration from natural behaviors and phenomena. Among the others, Ant Colony Optimization (ACO) received particular interest in the last years. In this work, we introduce the environment in ACO, for the meta-heuristic to perform a more realistic simulation of the ants’ behavior. Computational experiments on instances of the GPS Surveying Problem (GSP) show that the introduction of the environment in ACO allows us to improve the quality of obtained solutions.
Antonio Mucherino, Stefka Fidanova, Maria Ganzha

Fast Preconditioned Solver for Truncated Saddle Point Problem in Nonsmooth Cahn–Hilliard Model

The discretization of Cahn–Hilliard equation with obstacle potential leads to a block \(2 \times 2\) non-linear system, where the (1, 1) block has a non-linear and non-smooth term. Recently a globally convergent Newton Schur method was proposed for the non-linear Schur complement corresponding to this non-linear system. The proposed method is similar to an inexact active set method in the sense that the active sets are first approximately identified by solving a quadratic obstacle problem corresponding to the (1, 1) block of the block \(2 \times 2\) system, and later solving a reduced linear system by annihilating the rows and columns corresponding to identified active sets. For solving the quadratic obstacle problem, various optimal multigrid like methods have been proposed. In this paper, we study a block tridiagonal Schur complement preconditioner for solving the reduced linear system. The preconditioner shows robustness with respect to problem parameters and truncations of domain.
Pawan Kumar

The Constraints Aggregation Technique for Control of Ethanol Production

In the article a new method for control and optimization of the ethanol production process was presented. The fed batch reactor for ethanol production can be described by the system of the nonlinear differential-algebraic equations. The new control approach base on the direct shooting method, which leads to a medium- or large-scale nonlinear optimization problem. In the presented research, three main aims of the optimization with the differential-algebraic constraints are indicated. The first one is the minimization of the cost function, which represents a process performance index. The second and third aims are to provide consistent initial conditions for the system to be solved and to ensure the continuity of the differential state trajectories. For these reasons, the large number of decision variables and equality constraints, connected with both consistent initial conditions for the differential-algebraic system and continuity of the differential state trajectories, was treated using the constraints aggregation technique. The direct shooting approach together with constraints aggregation technique enables us to obtain a new form of the nonlinear optimization task.
Paweł Dra̧g, Krystyn Styczeń

InterCriteria Analysis by Pairs and Triples of Genetic Algorithms Application for Models Identification

In this investigation the InterCriteria Analysis (ICrA) approach is applied. The apparatuses of index matrices and intuitionistic fuzzy sets are at the core of ICrA. They are used to examine the influences of two main genetic algorithms (GA) parameters—the rates of crossover (xovr) and mutation (mutr). A series of parameter identification procedures for S. cerevisiae and E. coli fermentation process models is fulfilled. Twenty GA with different xovr and mutr values are applied. Relations between ICrA criteria—GA parameters and outcomes, on the one hand, and fermentation process model parameters, on the other hand, are investigated. The ICrA approach is applied by pairs, as well as by triples. The obtained results are thoroughly analysed towards computation time and model accuracy and some conclusions about the derived criteria interactions are reported.
Olympia Roeva, Tania Pencheva, Maria Angelova, Peter Vassilev

Genetic Algorithms for Constrained Tree Problems

Given an undirected weighted connected graph \(G=(V,E)\) with vertex set V, edge set E and a designated vertex \(r \in V\), this chapter studies the following constrained tree problems in G. The first problem, called Constrained Minimum Spanning Tree Problem (CMST), asks for a rooted tree T in G that minimizes the total weight of T such that the distance between the r and any vertex v in T is at most a given constant C times the shortest distance between the two vertices in G. The second problem, Constrained Shortest Path Tree Problem (CSPT) requires a rooted tree T in G that minimizes the maximum distance between r and all vertices in V such that the total weight of T is at most a given constant C times the minimum tree weight in G. It is easy to conclude from the literatures that the above problems are NP-hard. This chapter presents efficient genetic algorithms that return (as shown by our experimental results) high quality solutions for those two problems.
Riham Moharam, Ehab Morsy

InterCriteria Analysis of Genetic Algorithms Performance

In this paper we apply InterCriteria Analysis (ICrA) approach based on the apparatus of Index Matrices and Intuitionistic Fuzzy Sets. The main idea is to use ICrA to establish the existing relations and dependencies of defined parameters in a non-linear model of an E. coli fed-batch cultivation process. We perform a series of model identification procedures applying Genetic Algorithms (GAs). We proposed a schema of ICrA of ICrA results to examine the obtained model identification results. The discussion about existing relations and dependencies is performed according to criteria defined in terms of ICrA. We consider as ICrA criteria model parameters and GAs outcomes on the one hand, and 14 differently tuned GAs on the other. Based on the results, we observe the mutual relations between model parameters and GAs outcomes, such as computation time and objective function value. Moreover, some conclusions about the preferred tuned GAs for the considered model parameter identification in terms of achieved accuracy for given computation time are presented.
Olympia Roeva, Peter Vassilev, Stefka Fidanova, Marcin Paprzycki

Exploring Sparse Covariance Estimation Techniques in Evolution Strategies

When considering continuous search spaces, evolution strategies are among the well-performing metaheuristics. In contrast to other evolutionary algorithms, their main search operator is mutation which necessitates its adaptation during the run. Here, the covariance matrix plays an important role. Modern Evolution Strategies apply forms of covariance matrix adaptation. However, the quality of the common estimate of the covariance is known to be questionable for high search space dimensions. This paper presents a new approach by considering sparse covariance matrix techniques together with a space transformation.
Silja Meyer-Nieberg, Erik Kropat

Parallel Metaheuristics for Robust Graph Coloring Problem

In this chapter a new formulation of the robust graph coloring problem (RGCP) is proposed. In opposition to classical GCP defined for the given graph \({ G(V, E)}\) not only elements of E but also Ē can be subject of color conflicts in edge vertices. Conflicts in Ē are assigned penalties \(0<\mathrm{P(e)}<1\). In addition to satisfying constraints related to the number of colors and/or a threshold of the acceptable sum of penalties for color conflicts in graph complementary edges (rigidity level), a new bound called the relative robustness threshold (RRT) is proposed. Then three metaheuristics—SA, TS, EA and their parallel analogues PSA, PTS, PEA—for that version of RGCP are presented and experimentally tested. For comparison we use DIMACS graph coloring instances in which a selected percentage of graph edges E is randomly moved to Ē. Since graph densities and chromatic numbers of DIMACS GCP instances are known in advance, the RGCP instances generated on their basis are more suitable for testing algorithms than totally random instances used so far. The results of the conducted experiments are presented and discussed.
Z. Kokosiński, Ł. Ochał, G. Chrząszcz

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise