Category: Uncategorized

Scalability of generalized adaptive differential evolution for large-scale continuous optimization

Abstract  Differential evolution (DE) has become a very powerful tool for global continuous optimization problems. Parameter adaptations
are the most commonly used techniques to improve its performance. The adoption of these techniques has a…

Abstract  

Differential evolution (DE) has become a very powerful tool for global continuous optimization problems. Parameter adaptations
are the most commonly used techniques to improve its performance. The adoption of these techniques has assisted the success
of many adaptive DE variants. However, most studies on these adaptive DEs are limited to some small-scale problems, e.g. with
less than 100 decision variables, which may be quite small comparing to the requirements of real-world applications. The scalability
performance of adaptive DE is still unclear. In this paper, based on the analyses of similarities and drawbacks of existing
parameter adaptation schemes in DE, we propose a generalized parameter adaptation scheme. Applying the scheme to DE results
in a new generalized adaptive DE (GaDE) algorithm. The scalability performance of GaDE is evaluated on 19 benchmark functions
with problem scale from 50 to 1,000 decision variables. Based on the comparison with three other algorithms, GaDE is very
competitive in both the performance and scalability aspects.

  • Content Type Journal Article
  • Pages 1-15
  • DOI 10.1007/s00500-010-0643-6
  • Authors
    • Zhenyu Yang, Nature Inspired Computation and Applications Laboratory (NICAL), School of Computer Science and Technology, University of Science and Technology of China, Hefei, China
    • Ke Tang, Nature Inspired Computation and Applications Laboratory (NICAL), School of Computer Science and Technology, University of Science and Technology of China, Hefei, China
    • Xin Yao, Nature Inspired Computation and Applications Laboratory (NICAL), School of Computer Science and Technology, University of Science and Technology of China, Hefei, China

VXQR: derivative-free unconstrained optimization based on QR factorizations

Abstract  This paper presents basic features of a new family of algorithms for unconstrained derivative-free optimization, based on
line searches along directions generated from QR factorizations of past direction matrices. Emphasis is on fa…

Abstract  

This paper presents basic features of a new family of algorithms for unconstrained derivative-free optimization, based on
line searches along directions generated from QR factorizations of past direction matrices. Emphasis is on fast descent with
a low number of function values, so that the algorithm can be used for fairly expensive functions. The theoretical total time
overhead needed per function evaluation is of order O(n
2), where n is the problem dimension, but the observed overhead is much smaller. Numerical results are given for a particular algorithm
VXQR1 from this family, implemented in Matlab, and evaluated on the scalability test set of Herrera et al. (http://www.sci2s.ugr.es/eamhco/CFP.php, 2010) for problems in dimensions n ∈ {50, 100, 200, 500, 1,000}. Performance depends a lot on the graph

{(t,f(x+th)) | t Î [0,1]}

of the function along line segments. The algorithm is typically very fast on smooth problems with not too rugged graphs,
and on problems with a roughly separable structure. It typically performs poorly on problems where the graph along many directions
is highly multimodal without pronounced overall slope (e.g., for smooth functions with superimposed oscillations of significant
size), where the graphs along many directions are piecewise constant (e.g., for problems minimizing a maximum norm), or where
the function overflows on the major part of the search region and no starting point with finite function value is known.

  • Content Type Journal Article
  • Pages 1-12
  • DOI 10.1007/s00500-010-0652-5
  • Authors
    • Arnold Neumaier, Fakultät für Mathematik, Universität Wien, Nordbergstr. 15, 1090 Wien, Austria
    • Hannes Fendl, Fakultät für Mathematik, Universität Wien, Nordbergstr. 15, 1090 Wien, Austria
    • Harald Schilly, Fakultät für Mathematik, Universität Wien, Nordbergstr. 15, 1090 Wien, Austria
    • Thomas Leitner, Fakultät für Mathematik, Universität Wien, Nordbergstr. 15, 1090 Wien, Austria

A MOS-based dynamic memetic differential evolution algorithm for continuous optimization: a scalability test

Abstract  Continuous optimization is one of the areas with more activity in the field of heuristic optimization. Many algorithms have
been proposed and compared on several benchmarks of functions, with different performance depending on the …

Abstract  

Continuous optimization is one of the areas with more activity in the field of heuristic optimization. Many algorithms have
been proposed and compared on several benchmarks of functions, with different performance depending on the problems. For this
reason, the combination of different search strategies seems desirable to obtain the best performance of each of these approaches.
This contribution explores the use of a hybrid memetic algorithm based on the multiple offspring framework. The proposed algorithm
combines the explorative/exploitative strength of two heuristic search methods that separately obtain very competitive results.
This algorithm has been tested with the benchmark problems and conditions defined for the special issue of the Soft Computing
Journal on Scalability of Evolutionary Algorithms and other Metaheuristics for Large Scale Continuous Optimization Problems.
The proposed algorithm obtained the best results compared with both its composing algorithms and a set of reference algorithms
that were proposed for the special issue.

  • Content Type Journal Article
  • Pages 1-13
  • DOI 10.1007/s00500-010-0646-3
  • Authors
    • Antonio LaTorre, Department of Computer Systems Architecture and Technology, Facultad de Informática, Universidad Politécnica de Madrid, Madrid, Spain
    • Santiago Muelas, Department of Computer Systems Architecture and Technology, Facultad de Informática, Universidad Politécnica de Madrid, Madrid, Spain
    • José-María Peña, Department of Computer Systems Architecture and Technology, Facultad de Informática, Universidad Politécnica de Madrid, Madrid, Spain

EM323: a line search based algorithm for solving high-dimensional continuous non-linear optimization problems

Abstract  This paper presents a performance study of a one-dimensional search algorithm for solving general high-dimensional optimization
problems. The proposed approach is a hybrid between a line search algorithm of Glover (The 3-2-3, strat…

Abstract  

This paper presents a performance study of a one-dimensional search algorithm for solving general high-dimensional optimization
problems. The proposed approach is a hybrid between a line search algorithm of Glover (The 3-2-3, stratified split and nested
interval line search algorithms. Research report, OptTek Systems, Boulder, CO, 2010) and an improved variant of a global method of Gardeux et al. (Unidimensional search for solving continuous high-dimensional
optimization problems. In: ISDA ’09: Proceedings of the 2009 ninth international conference on intelligent systems design
and applications, IEEE Computer Society, Washington, DC, USA, pp 1096–1101, 2009) that uses line search algorithms as subroutines. The resulting algorithm, called EM323, was tested on 19 scalable benchmark
functions, with a view to observing how optimization techniques for continuous optimization problems respond with increasing
dimension. To this end, we report the algorithm’s performance on the 50, 100, 200, 500 and 1,000-dimension versions of each
function. Computational results are given comparing our method with three leading evolutionary algorithms. Statistical analysis
discloses that our method outperforms the other methods by a significant margin.

  • Content Type Journal Article
  • Pages 1-11
  • DOI 10.1007/s00500-010-0651-6
  • Authors
    • Vincent Gardeux, EISTI, L@ris, Cergy-Pontoise, France
    • Rachid Chelouah, EISTI, L@ris, Cergy-Pontoise, France
    • Patrick Siarry, Université de Paris 12, LiSSi, Créteil, France
    • Fred Glover, OptTek Systems, Inc., 2241 17th Street, Boulder, CO 80302, USA

Optimization algorithms for large-scale real-world instances of the frequency assignment problem

Abstract  Nowadays, mobile communications are experiencing a strong growth, being more and more indispensable. One of the key issues
in the design of mobile networks is the frequency assignment problem (FAP). This problem is crucial at prese…

Abstract  

Nowadays, mobile communications are experiencing a strong growth, being more and more indispensable. One of the key issues
in the design of mobile networks is the frequency assignment problem (FAP). This problem is crucial at present and will remain
important in the foreseeable future. Real-world instances of FAP typically involve very large networks, which can be handled
only by heuristic methods. In the present work, we are interested in optimizing frequency assignments for problems described
in a mathematical formalism that incorporates actual interference information, measured directly on the field, as is done
in current GSM networks. To achieve this goal, a range of metaheuristics have been designed, adapted, and rigourously compared
on two actual GSM networks modeled according to the latter formalism. To generate quickly and reliably high-quality solutions,
all metaheuristics combine their global search capabilities with a local-search method specially tailored for this domain.
The experiments and statistical tests show that in general, all metaheuristics are able to improve upon results published
in previous studies, but two of the metaheuristics emerge as the best performers: a population-based algorithm (Scatter Search)
and a trajectory based (1+1) Evolutionary Algorithm. Finally, the analysis of the frequency plans obtained offers insight
about how the interference cost is reduced in the optimal plans.

  • Content Type Journal Article
  • Pages 1-16
  • DOI 10.1007/s00500-010-0653-4
  • Authors
    • Francisco Luna, Universidad de Málaga, Malaga, Spain
    • César Estébanez, Universidad Carlos III de Madrid, Madrid, Spain
    • Coromoto León, Universidad de La Laguna, Tenerife, Spain
    • José M. Chaves-González, Universidad de Extremadura, Badajoz, Spain
    • Antonio J. Nebro, Universidad de Málaga, Malaga, Spain
    • Ricardo Aler, Universidad Carlos III de Madrid, Madrid, Spain
    • Carlos Segura, Universidad de La Laguna, Tenerife, Spain
    • Miguel A. Vega-Rodríguez, Universidad de Extremadura, Badajoz, Spain
    • Enrique Alba, Universidad de Málaga, Malaga, Spain
    • José M. Valls, Universidad Carlos III de Madrid, Madrid, Spain
    • Gara Miranda, Universidad de La Laguna, Tenerife, Spain
    • Juan A. Gómez-Pulido, Universidad de Extremadura, Badajoz, Spain

Editorial scalability of evolutionary algorithms and other metaheuristics for large-scale continuous optimization problems

Abstract  This editorial note presents the motivations, objectives, and structure of the special issue on scalability of evolutionary
algorithms and other metaheuristics for large-scale continuous optimization problems. In addition, it provi…

Abstract  

This editorial note presents the motivations, objectives, and structure of the special issue on scalability of evolutionary
algorithms and other metaheuristics for large-scale continuous optimization problems. In addition, it provides the link to
an associated Website where complementary material to the special issue is available.

  • Content Type Journal Article
  • Pages 1-3
  • DOI 10.1007/s00500-010-0639-2
  • Authors
    • M. Lozano, Department of Computer Science and A.I., University of Granada, 18071 Granada, Spain
    • D. Molina, Department of Computer Languages and Systems, University of Cadiz, 11003 Cadiz, Spain
    • F. Herrera, Department of Computer Science and A.I., University of Granada, 18071 Granada, Spain

On the verification of membrane systems with dynamic structure

Abstract  We study computational properties of Gheorge Păun’s P-systems extended with rules that model in an abstract way creation,
dissolution, fusion and cloning of membranes. We investigate decision problems like reachability of a conf…

Abstract  

We study computational properties of Gheorge Păun’s P-systems extended with rules that model in an abstract way creation,
dissolution, fusion and cloning of membranes. We investigate decision problems like reachability of a configuration, boundedness
(finiteness of the state space), and coverability (verification of safety properties). Our analysis is aimed at understanding
the expressive power of rules that dynamically modify the structure of a membrane.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9214-0
  • Authors
    • Giorgio Delzanno, Università di Genova, Genova, Italy
    • Laurent Van Begin, Université Libre de Bruxelles, Brussels, Belgium

On the verification of membrane systems with dynamic structure

Abstract  We study computational properties of Gheorge Păun’s P-systems extended with rules that model in an abstract way creation,
dissolution, fusion and cloning of membranes. We investigate decision problems like reachability of a conf…

Abstract  

We study computational properties of Gheorge Păun’s P-systems extended with rules that model in an abstract way creation,
dissolution, fusion and cloning of membranes. We investigate decision problems like reachability of a configuration, boundedness
(finiteness of the state space), and coverability (verification of safety properties). Our analysis is aimed at understanding
the expressive power of rules that dynamically modify the structure of a membrane.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9214-0
  • Authors
    • Giorgio Delzanno, Università di Genova, Genova, Italy
    • Laurent Van Begin, Université Libre de Bruxelles, Brussels, Belgium

Grammar-based immune programming

Abstract  This paper describes Grammar-based Immune Programming (GIP) for evolving programs in an arbitrary language by immunological
inspiration. GIP is based on Grammatical Evolution (GE) in which a grammar is used to define a language and…

Abstract  

This paper describes Grammar-based Immune Programming (GIP) for evolving programs in an arbitrary language by immunological
inspiration. GIP is based on Grammatical Evolution (GE) in which a grammar is used to define a language and decode candidate
solutions to a valid representation (program). However, by default, GE uses a Genetic Algorithm in the search process while
GIP uses an artificial immune system. Some modifications are needed of an immune algorithm to use a grammar in order to efficiently
decode antibodies into programs. Experiments are performed to analyze algorithm behavior over different aspects and compare
it with GEVA, a well known GE implementation. The methods are applied to identify a causal model (an ordinary differential
equation) from an observed data set, to symbolically regress an iterated function f(f(x)) = g(x), and to find a symbolic representation of a discontinuous function.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9217-x
  • Authors
    • Heder S. Bernardino, Laboratório Nacional de Computação Científica, Av. Getulio Vargas, 333, 25.651-075 Petrópolis, RJ Brazil
    • Helio J. C. Barbosa, Laboratório Nacional de Computação Científica, Av. Getulio Vargas, 333, 25.651-075 Petrópolis, RJ Brazil

On the computational complexity of spiking neural P systems

Abstract  It is shown here that there is no standard spiking neural P system that simulates Turing machines with less than exponential
time and space overheads. The spiking neural P systems considered here have a constant number of neurons t…

Abstract  

It is shown here that there is no standard spiking neural P system that simulates Turing machines with less than exponential
time and space overheads. The spiking neural P systems considered here have a constant number of neurons that is independent
of the input length. Following this, we construct a universal spiking neural P system with exhaustive use of rules that simulates
Turing machines in linear time and has only 10 neurons.

  • Content Type Journal Article
  • DOI 10.1007/s11047-010-9213-1
  • Authors
    • Turlough Neary, Boole Centre for Research in Informatics, University College Cork, Cork, Ireland