A comprehensive survey of fitness approximation in evolutionary computation
Inhaltsverzeichnis
Reference
Yaochu Jin: A comprehensive survey of fitness approximation in evolutionary computation. Soft Computing journal, vol 9, pp. 3-12, 2005.
DOI
http://dx.doi.org/10.1007/s00500-003-0328-5
Abstract
Evolutionary algorithms (EAs) have received increasing interests both in the academy and industry. One main difficulty in applying EAs to real-world appli- cations is that EAs usually need a large number of fitness evaluations before a satisfying result can be obtained. However, fitness evaluations are not always straightfor- ward in many real-world applications. Either an explicit fitness function does not exist, or the evaluation of the fitness is computationally very expensive. In both cases, it is necessary to estimate the fitness function by con- structing an approximate model. In this paper, a com- prehensive survey of the research on fitness approxima- tion in evolutionary computation is presented. Main is- sues like approximation levels, approximate model man- agement schemes, model construction techniques are re- viewed. To conclude, open questions and interesting is- sues in the field are discussed.
Extended Abstract
Bibtex
Used References
1. L. Albert and D.E. Goldberg. Efficient disretization scheduling in multiple dimensions. In Proceedings of Genetic and Evolutionary Computation Conference, pages 271–278. Morgan Kaufmann, 2002.
2. J.D. Anderson. Computational Fluid Dynamics: The Basics with Applications. McGraw Hill, 1995.
3. K. Anderson and Y. Hsu. Genetic crossover strat- egy using an approximation concept. In IEEE Congress on Evolutionary Computation, pages 527– 533, Washington D.C., 1999. IEEE.
4. J.-F.M. Barthelemy. Approximation concepts for op- timimum structural design - a review. Structural Optimization, 5:129–144, 1993.
5. J. A. Biles. Genjam: A genetic algorithm for gen- erating jazz solos. In Proceedings of International Computer Music Conference, pages 131–137, 1994.
6. P. Bradshaw, G.A. Mizner, and K. Unsworth. Cal- culation of compressible turbulent boundary layers on straight-tapered swept wings,. AIAA Journal,, 14:399–400, 1976.
7. J. Branke. Creating robust solutions by means of evolutionary algorithms. In Proceedings of Paral- lel Problem Solving from Nature, Lecture Notes in Computer Science, pages 119–128. Springer, 1998.
J. Branke, C. Schmidt, and H. Schmeck. Efficient fitness estimation in noisy environment. In L. Spec- tor et al, editor, Proceedings of Genetic and Evolu- tionary Computation, pages 243–250, San Francisco, CA, July 2001. Morgan Kaufmann.
L. Breiman. Bagging predictors. Machine Learning, 24:123–140, 1996.
L. Breiman. Using adaptive bagging to debias re- gressions. Technical Report 547, Dept. of Statistics, University of California, Berkeley, 1999.
A. J. Brooker, J. Dennis, P. D. Frank, D. B. Ser- afini, V. Torczon, and M. Trosset. A rigorous frame- work for optimization of expensive functions by sur- rogates. Structural Optimization, 17:1–13, 1998. L. Bull. On model-based evolutionary computation. Soft Computing, 3:76–82, 1999.
W. Carpenter and J.-F. Barthelemy. A compari- son of polynomial approximation and artificial neu- ral nets as response surface. Technical Report 92- 2247, AIAA, 1992.
W. Carpenter and J.-F. Barthelemy. Common mis- conceptions about neural networks as approxima- tors. ASCE Journal of Computing in Civil Engi- neering, 8(3):345–358, 1994.
J.-H. Chen, D.E. Goldberg, S.-Y. Ho, and K. Sastry. Fitness inheritance in multi-objective optimization. In Proceedings of genetic and Evolutionary Compu- tation Conference. Morgan Kaufmann, 2002.
M.H. Choueiki and C.A. Mount-Campbell. Training data development with the D-optimality criterion. IEEE Transactions on Neural Networks, 10(1):56– 63, 1999.
J. Dennis and V. Torczon. Managing approximate models in optimization. In N. Alexandrov and M. Hussani, editors, Multidisciplinary design op- timization: State-of-the-art, pages 330–347. SIAM, 1997.
D. Eby, R. Averill, W. Punch, and E. Goodman. Evaluation of injection island model GA perfor- mance on flywheel design optimization. In Third Conference on Adaptive Computing in Design and manufacturing, pages 121–136. Springer, 1998.
B. Efron and R. Tibshirani. An Introduction to the Bootstrap. Chapman and Hall, 1993.
M.A. El-Beltagy and A.J. Keane. Optimization for multi-level problems: A comparison of various algo- rithms. In I. Parmee, editor, Proceedings of Third International Conference on Adaptive Computing in Design and Manufacture, pages 111–120. Springer, 1998.
M.A. El-Beltagy, P.B. Nair, and A.J. Keane. Meta- modeling techniques for evolutionary optimization of computationally expensive problems: promises and limitations. In Proceedings of Genetic and Evo- lutionary Conference, pages 196–203, Orlando, 1999. Morgan Kaufmann.
22. M. Emmerich, A. Giotis, M. Ozdenir, T. B ̈ack,and K. Giannakoglou. Metamodel-assisted evolution strategies. In Parallel Problem Solving from Nature, number 2439 in Lecture Notes in Computer Science, pages 371–380. Springer, 2002.
23. M. Farina. A minimal cost hybrid strategy for Pareto optimal front approximation. Evolutionary Optimization, 3(1):41–52, 2001.
24. M. Farina. A neural network based generalized response surface multiobjective evolutionary algo- rithms. In Congress on Evolutionary Computation, pages 956–961. IEEE Press, 2002.
25. J.M. Fitzpatrick and J.J. Grefenstette. Genetic al- gorithms in noisy environments. Machine Learning, 3:101–120, 1988.
26. Y. Freund. Boosting a weak learning algo- rithm by majority. Information and Computation, 121(2):256–285, 1995.
27. A. Giotis, M. Emmerich, B. Naujoks, and K. Gi- annakoglou. Low kost stochastic optimization for engineering applications. In Proceedings of Interna- tional Conference on Evolutionary Methods for De- sign, Optimization and Control with Applications to Industrial Problems, 2001.
28. A.A. Giunta and L. Watson. A comparison of ap- proximation modeling techniques: Polynomial ver- sus interpolating models. Technical Report 98-4758, AIAA, 1998.
29. J.J. Grefenstette and J.M. Fitzpatrick. Genetic search with approximate fitness evaluations. In Pro- ceedings of the International Conference on Genetic Algorithms and Their Applications, pages 112–120, 1985.
30. D.E. Grierson and W.H. Pak. Optimal sizing, geo- metrical and topological design using a genetic algo- rithm. Structural Optimization, 6(3):151–159, 1993.
31. R.T. Haftka, E.P. Scott, and J.R. Cruz. Optimiza- tion and experiments: A survey. Applied Mechanics Review, 51(7):435–448, 1998.
32. Y.-S. Hong, H.Lee, and M.-J. Tahk. Acceleration of the convergence speed of evolutionary algorithms using multi-layer neural networks. Engineering Op- timization, 35(1):91–102, 2003.
33. M. H ̈usken, Y. Jin, and B. Sendhoff. Structure opti- mization of neural networks for evolutionary design optimization. In 2002 GECCO Workshop on Ap- proximation and Learning in Evolutionary Compu- tation, pages 13–16, 2002.
34. M. H ̈usken and B. Sendhoff. Evolutionary optimiza- tion for problem classes with lamarckian inheritance. In IEEE Symposium on Combinations of Evolution- ary Computation and Neural Networks, pages 98– 109, 2000.
35. R. Jin, W. Chen, and T.W. Simpson. Compara- tive studies of metamodeling techniques under milti- ple modeling criteria. Technical Report 2000-4801, AIAA, 2000.
36. Y. Jin. Knowledge in Evolutionary and Learning Systems. Shaker, Aachen, 2002.
37. Y. Jin, M. Olhofer, and B. Sendhoff. On evolu- tionary optimization with approximate fitness func- tions. In Proceedings of the Genetic and Evolution- ary Computation Conference, pages 786–792. Mor- gan Kaufmann, 2000.
38. Y. Jin, M. Olhofer, and B. Sendhoff. Managing ap- proximate models in evolutionary aerodynamic de- sign optimization. In Proceedings of IEEE Congress on Evolutionary Computation, volume 1, pages 592– 599, May 2001.
39. Y. Jin, M. Olhofer, and B. Sendhoff. A framework for evolutionary optimization with approximate fit- ness functions. IEEE Transactions on Evolutionary Computation, 6(5):481–494, 2002.
40. Y. Jin and B. Sendhoff. Knowledge incorporation into neural networks from fuzzy rules. Neural Pro- cessing Letters, 10(3):231–242, 1999.
41. B. Johanson and R. Poli. GP-music: An interactice genetic programming system for music generation with automated fitness raters. In John R. Koza, Wolfgang Banzhaf, Kumar Chellapilla, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max H. Gar- zon, David E. Goldberg, Hitoshi Iba, and Rick Riolo, editors, Proceedings of the Third Annual Conference on Genetic Programming, pages 181–186, 1998.
42. F. Kenji. Statistical active learning in multilayer perceptrons. IEEE Transactions Neural Networks, 11(1):16–26, 2000.
43. H.-S. Kim and S.-B. Cho. An efficient genetic al- gorithms with less fitness evaluation by clustering. In Proceedings of IEEE Congress on Evolutionary Computation, pages 887–894. IEEE, 2001.
44. S. Kodiyalam, S. Nagendra, and J. DeStefano. Com- posite sandwich structural optimization with ap- plication to satellite components. AIAA Journal, 34(3):614–621, 1996.
45. J. Lee and P. Hajela. Parallel genetic algorithms implementation for multidisciplinary rotor blade de- sign. Journal of Aircraft, 33(5):962–969, 1996.
46. K.-H. Liang, X. Yao, and C. Newton. Combining landscape approximation and local search in global optimization. In 1999 Congress on Evolutionary Computation, pages 1514–1520, 1999.
47. K.-H. Liang, X. Yao, and C. Newton. Evolutionary search of approximated n-dimensional landscape. International Journal of Knowledge-based Intelli- gent Engineering Systems, 4(3):172–183, 2000.
48. D. MacKay. Information-based objective functions for active data selection. Neural Computation, 4(4):305–318, 1992.
49. T. Morimoto, J. De Baerdemaeker, and Y. Hashimoto. An intelligent approach for op- timal control of fruit-storage process using neural networks and genetic algorithms. Computers and Electronics in Agriculture, 18:205–224, 1997.
50. R. Myers and D. Montgomery. Response Surface Methodology. John Wiley & Sons, Inc., New York, 1995.
51. P. Nain and K. Deb. A computationally effective multi-objective search and optimization techniques using coarse-to-fine grain modeling. In 2002 PPSN Workshop on Evolutionary Multiobjective Optimiza- tion, 2002.
52. P.B. Nair and A.J. Keane. Combining approx- imation concepts with algorithm-based structural optimization procedures. In Proceedings of 39th AIAA/ASMEASCE/AHS/ASC Structures, Struc- tural Dynamics and Materials Conference, pages 1741–1751, 1998.
53. A. Neumaier. Molecular modeling of proteins and mathematical prediction of protein structures. SIAM Review, 39(3):407–460, 1997.
54. V. Oduguwa and R. Roy. Multiobjective opti- mization of rolling rod product design using meta- modeling approach. In Genetic and Evolution- ary Computation Conference, pages 1164–1171, New York, 2002. Morgan Kaufmann.
55. M. Olhofer, Y. Jin, and B. Sendhoff. Adaptive encoding for aerodynamic shape optimization us- ing evolutiona stratgies. In Proceedings of IEEE Congress on Evolutionary Computation, volume 1, pages 576–583, May 2001.
56. Y.S. Ong, P.B. Nair, and A.J. Keane. Evolutionary optimization of computationally expensive problems via surrogate modeling. AIAA Journal, 2003.
57. M. Papadrakakis, N. Lagaros, and Y. Tsompanakis. Structural optimization using evolution strategies and neural networks. In Fourth U.S. National Congress on Computational Mechanics, San Fran- cisco, 1997.
58. M. Papadrakakis, N. Lagaros, and Y. Tsompanakis. Optimization of large-scale 3D trusses using evolu- tion strategies and neural networks. Int. J. Space Structures, 14(3):211–223, 1999.
59. A. Piccolboni and G. Mauri. Application of evolu- tionary algorithms to protein folding prediction. In J.-K. Hao et al, editor, Proceedings of the Artificial Evolution 97, volume 1363 of Lecture Notes in Com- puter Science, pages 123–136. Springer, 1997.
60. S. Pierret. Turbomachinery blade design using a Navier-Stokes solver and artificial neural network. ASME Journal of Turbomachinery, 121(3):326–332, 1999.
61. M. Plutowski and H. White. Selecting concise train- ing sets from clean data. IEEE Transactions on Neu- ral Networks, 4(2):305–318, 1993.
62. M. Powell. Radial basis functions for multi-variable interpolation: A review. In C. Mason and M.G. Cox, editors, Algorithms for Approximation, pages 143– 167. Oxford University Press, Oxford, U.K., 1987.
63. K. Rasheed. Informed operators: Speeding up genetic-algorithm-based design optimization using reduced models. In Proceedings of genetic and Evo- lutionary Computation Conference, pages 628–635, Las Vegas, 2000. Morgan Kaufmann.
64. K. Rasheed, S. Vattam, and X. Ni. Comparison of methods for using reduced models to speed up design optimization. In Proceedings of Genetic and Evolu- tionary Computation Conference, pages 1180–1187, New York, 2002. Morgan Kaufmann.
65. A. Ratle. Accelerating the convergence of evolution- ary algorithms by fitness landscape approximation. In A. Eiben, Th. B ̈ack, M. Schoenauer, and H.-P. Schwefel, editors, Parallel Problem Solving from Na- ture, volume V, pages 87–96, 1998.
66. A. Ratle. Optimal sampling strategies for learning a fitness model. In Proceedings of 1999 Congress on Evolutionary Computation, volume 3, pages 2078– 2085, Washington D.C., July 1999.
67. J. Redmond and G. Parker. Actuator placement based on reachable set optimization for expected dis- turbance. Journal Optimization Theory and Appli- cations, 90(2):279–300, August 1996.
68. R.D. Reed and R.J. Marks II. Neural Smithing. MIT, Cambridge, MA, 1999.
69. G. M. Robinson and A. J. Keane. A case for multi- level optimisation in aeronautical design. In Pro- ceedings of the RAeS Conf. on Multidisciplinary De- sign and Optimisation, pages pp. 9.1–9.6. The Royal Aeronautical Society, 1998.
70. Y. Sano and H. Kita. Optimization of noisy fitness functions by means of genetic algorithms using his- tory. In M. Schoenauer et al, editor, Parallel Problem Solving from Nature, volume 1917 of Lecture Notes in Computer Science. Springer, 2000.
71. K. Sastry, D.E. Goldberg, and M. Pelikan. Don’t evaluate, inherit. In Proceedings of genetic and Evo- lutionary Computation Conference, pages 551–558. Morgan Kaufmann, 2001.
72. G. Schneider. Neural networks are useful tools for drug design. Neural Networks, 13:15–16, 2000.
73. G. Schneider, W. Schr ̈odl, and G. Wallukat. Peptide design by artificial neural networks and computaer- based evolutionary search. Proceedings of National Academy of Science, 95:12197–12184, 1998.
74. G. Schneider, J. Schuchhardt, and P. Wrede. Artifi- cial neural networks and simulated molecular evolu- tion are potential tools for sequence-oriented protein design. CABIOS, 10(6):635–645, 1994.
75. K. Abboud M. Schoenauer. Surrogate deterministic mutation. In Artificial Evolution’01, pages 103–115. Springer, 2002.
76. H.-P. Schwefel. Evolution and Optimum Seeking. Wiley, 1995.
77. M. Sefrioui and J. Periaux. A hierarchical genetic algorithm using multiple models for optimization. In Parallel Problem Solving from Nature, volume 1917 of Lecture Notes in Computer Science, pages 879– 888. Springer, 2000.
W. Shyy, P. K. Tucker, and R. Vaidyanathan. Re- sponse surface and neural network techniques for rocket engine injector optimization. Technical Re- port 99-2455, AIAA, 1999.
T. Simpson, T. Mauery, J. Korte, and F. Mistree. Comparison of response surface and Kriging models for multidiscilinary design optimization. Technical Report 98-4755, AIAA, 1998.
R. Smith, B. Dike, and S. Stegmann. Fitness inheri- tance in genetic algorithms. In Proceedings of ACM Symposiums on Applied Computing, pages 345–350. ACM, 1995.
H. Takagi. Interactive evolutionary computation. In Proceedings of the 5th International Conference on Soft Computing and Information / Intelligent Systems, pages 41–50, Iizuka, Japan, October 1998. World Scientific.
V. Vapnik. Statistical Learning Theory. Wiley, 1998.
H. Vekeria and I. Parmee. The use of a cooperative multi-level CHC GA for structuralshape optimiza- tion. In Proceedings of fourth European Congress on Intelligent Techniques and Soft Computing, vol- ume I, pages 471–475, Aachen, 1996.
S. Vijayakumar and H. Ogawa. Improving gen- eralization ability through active learning. IE- ICE Transactions on Information and Systems, E82- D(2):480–487, 1999.
D. Yang and S.J. Flockton. Evolutionary algorithms with a coarse-to-fine function smoothing. In IEEE International Conference on Evolutionary Compu- tation, pages 657–662, Perth, Australia, 1995. IEEE Press.
X. Zhang, B. Julstrom, and W. Cheng. Design of vector quantization codebooks using a genetic algo- rithm. In Proceedings of the IEEE Conference on Evolutionary Computation, pages 525–529. IEEE, 1997.
Links
Full Text
http://www.soft-computing.de/SC2005.pdf
Sonstige Links
http://www.soft-computing.de/ page of Prof. Yaochu Jin
