Description: We present a new quantum-inspired evolutionary algorithm, the attractor population QEA (apQEA). Our benchmark problem is a classical and difficult problem from Combinatorics, namely finding low-discrepancy colorings in the hypergraph of arithmetic progressions on the first n integers, which is a massive hypergraph (e.g., with approx. 3.88 ×1011 hyperedges for n = 250 000). Its optimal low-discrepancy coloring bound is known and it has been a long-standing open problem to give practically and/or theoretically efficient algorithms. We show that apQEA outperforms known QEA approaches and the classical combinatorial algorithm (Sárközy 1974) by a large margin. Regarding practicability, it is also far superior to the SDP-based polynomial-time algorithm of Bansal (2010), the latter being a breakthrough work from a theoretical point of view. Thus we give the first practical algorithm to construct optimal colorings in this hypergraph, up to a constant factor. We hope that our work will spur further applications of Algorithm Engineering to Combinatorics.

Description: Methods and results for parameter optimization and uncertainty analysis for a one-dimensional marine biogeochemical model of NPZD type are presented. The model, developed by Schartau and Oschlies, simulates the distribution of nitrogen, phytoplankton, zooplankton and detritus in a water column and is driven by ocean circulation data. Our aim is to identify parameters and fit the model output to given observational data. For this model, it has been shown that a satisfactory fit could not be obtained, and that parameters with comparable fits can vary significantly. Since these results were obtained by evolutionary algorithms (EA), we used a wider range of optimization methods: A special type of EA (called quantum-EA) with coordinate line search and a quasi-Newton SQP method, where exact gradients were generated by Automatic/Algorithmic Differentiation. Both methods are parallelized and can be viewed as instances of a hybrid, mixed evolutionary and deterministic optimization algorithm that we present in detail. This algorithm provides a flexible and robust tool for parameter identification and model validation. We show how the obtained parameters depend on data sparsity and given data error. We present an uncertainty analysis of the optimized parameters w.r.t. Gaussian perturbed data. We show that the model is well suited for parameter identification if the data are attainable. On the other hand, the result that it cannot be fitted to the real observational data without extension or modification, is confirmed. (C) 2010 Elsevier Ltd. All rights reserved.

Description: Sensitivity computations, parameter identification and optimiza-tion for an 1-D marine biogeochemical model ofN P ZDtype are pre-sented. For the optimization a hybrid algorithm combining quantum-evolutionary and local gradient-based search methods is used. It turnsout to be an efficient and flexible tool for optimization and can beeasily adopted for other simulation models. For the model under in-vestigation attainable data could be exactly identified. For realisticmeasurement data we argue that a certain parameter set leading toa non-optimal fit cannot be improved. Moreover we show that datauncertainty leads to a significant parameter spread. Thus we concludethat theN P ZDmodel needs to be modified or extended, maybe in-cluding a modification of external forcings and/or initial conditions.