Abstract
A new mutation operator based on a surrogate model of the fitness function is introduced. The original features of this approach are 1-the model used to approximate the fitness, namely Support Vector Machines; 2-the adaptive granularity of the approximation, going from space-wide to closely localized around the best-so-far individual of the population; 3-the use of a deterministic optimization method on the surrogate model. The goal is to accelerate the convergence of the evolutionary algorithm, and not to reduce the number of evaluations of the actual fitness by evaluating the surrogate model instead. First results on benchmark functions of high dimensions show the potential improvement that this approach can bring in high-dimensional search spaces, and points out some limitations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J-F.M. Barthelemy and R.T. Haftka. Approximation concepts for optimum structural design— a review. Structural Optimization, 5:129–144, 1993.
F. Bonnans, J.C. Gilbert, C. Lemarechal, and C. Sagastizábal. Optimisation Numérique, aspects théoriques et pratiques, volume 23 of Mathématiques & Applications. Springer Verlag, 1997.
A.J. Booker, J.E. Dennis Jr., P.D. Frank, D.B. Serafini, V. Torczon, and M.W. Trosset. A rigorous framework for optimization of expensive functions by surrogates. Structural Optimization, 17(1):1–13, 1999.
R. H. Byrd, P. Lu, and J. Noceda. A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific and Statistical Computing, 16(5):1190–1208, 1995.
R. H. Byrd, J. Nocedal, and R. B. Schnabel. Representation of quasi-newton matrices and their use in limited memory methods. Mathematical Programming, 63(4):129–156, 1994.
R. Collobert and S. Bengio. Support Vector Machines for Large-Scale Regression Problems. IDIAP-RR-00-17, 2000.
N. Cristianini and J. Shawe-Taylor. An introduction to Support Vector Machines. Cambridge University Press, 2000.
M.A. El-Beltagy, P.B. Nair, and A.J. Keane. Metamodeling techniques for evolutionary optimization of computationally expensive problems: Promises and limitations. In D.E. Goldberg & al., editor, GECCO’99, pages 196–203. Morgan Kaufmann, 1999.
P. Galinier and J. Hao. Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3(4):379–397, 1999.
J. J. Grefenstette. Predictive models using fitness distributions of genetic operators. In L. D. Whitley and M. D. Vose, editors, FOGA 3, pages 139–161. Morgan Kaufmann, 1995.
J. J. Grefenstette and J. M. Fitzpatrick. Genetic search and approximate function evaluation. In J. J. Grefenstette, editor, Proceedings of ICGA, pages 160–168. Laurence Erlbaum Associates, 1985.
P. Husbands, G. Jermy, M. McIlhagga, and R. Ives. Two applications of genetic algorithms to component design. In T. Fogarty, editor, AISB Workshop on Evolutionary Computing, pages 50–61. Springer Verlag, 1996.
Y. Jin, M. Olhofer, and B. Sendho.. On evolutionary optimisation with approximate fitness functions. In D. Whitley & al., editor, GECCO’2000, pages 786–793, 2000.
P. Merz and B. Freisleben. A genetic local search approach for the QAP. In Th. Bäck, editor, Proceedings of ICGA’97, pages 465–470. Morgan Kaufmann, 1997.
P. Merz and B. Freisleben. Genetic local search for the TSP: New results. In Proceedings of ICEC’97, pages 159–164. IEEE Press, 1997.
K.-H. Liang, X. Yao, and C. Newton. Combining landscape approximation and local search in global optimization. In Proceedings of the CEC’99, pages 1514–1520, Piscataway, NJ, 1999. IEEE Press.
P. Merz and B. Freisleben. Fitness landscapes and memetic algorithm design. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization, pages 245–260. McGraw-Hill, London, 1999.
G. Mosetti and C. Poloni. Aerodynamic shape optimization by means of hybrid genetic algorithms. In 3rd International Congress on Industrial and APplied Mathematics, 1995.
C. Poloni and V. Pediroda. GA coupled with computationaly expensive simulations: tools to improve efficiency. In Genetic Algorithms and Evolution Strategies in Engineering and Computer Sciences, pages 267–288. John Wiley, 1997.
N. J. Radcliffe and P. D. Surry. Formal memetic algorithms. In T.C. Fogarthy, editor, Evolutionary Computing, pages 1–16. Springer Verlag LNCS 865, 1994.
A. Ratle. Accelerating the convergence of evolutionary algorithms by fitness landscape approximation. In Th. Bäck et al. editors, Proceedings of PPSN V, pages 87–96. Springer-Verlag, LNCS 1498, 1998.
V. N. Vapnik. The Nature of Statistical Learning. Springer Verlag, 1995.
D. Waagen, P. Diercks, and J. McDonnell. The stochastic direction set algorithm: A hybrid technique for finding function extrema. In D. B. Fogel and W. Atmar, editors, Proceedings of EP’92, pages 35–42, 1992.
C. Zhu, R. H. Byrd, and J. Nocedal. L-BFGS-B, Fortran routines for large scale bound constrained optimization. ACM Transactions on Mathematical Software, 23(4):550–560, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-VerlagBerlin Heidelberg
About this paper
Cite this paper
Abboud, K., Schoenauer, M. (2002). Surrogate Deterministic Mutation: Preliminary Results. In: Collet, P., Fonlupt, C., Hao, JK., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2001. Lecture Notes in Computer Science, vol 2310. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46033-0_9
Download citation
DOI: https://doi.org/10.1007/3-540-46033-0_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43544-0
Online ISBN: 978-3-540-46033-6
eBook Packages: Springer Book Archive