Future Directions in Soft Computing

Future Directions in Soft Computing: Mieres (Asturias)

Francisco Herrera (University of Granada)

Talk: Genetic Algorithms. Basic Notions and some AdvancedTopics
Course: Future Directions in Soft Computing (Mieres, Asturias).

This lecture provide a introduction to genetic algorithms, search algorithms based on the natural processes of evolution and genetics, and discuss some extensions to tackle specific problem.

First, we present the general structure of genetic algorithms ad the basic components. Then, we will deal with some specific problems and the use of genetic algorithms for tackling them:

  1. Multiobjective optimization problems. We introduce the multiobjective genetic algorithms that provide a tool for getting the non-dominated solutions set for multiobjective problems.
  2. Multimodal problems with multiple solutions. The simple genetic algorithm is not able to maintain different solutions, but it shows a genetic derivation to a solution in the evolution. Research studies based on preservation of the diversity by niching techniques in genetic algorithtms have provided very promising results from the multi-solution based efficacy point of view.
  3. The integration of local and global search. Memetic algorithms apply a separete local search process for refining individuals, integrating the local search into the genetic search process.

Finally, we introduce, the conexion of genetic algorithms with other soft computing areas, discussing the use of genetic algorithms for evolving neural networks and fuzzy systems, presenting the basic ideas of the genetic learning processes.

Documentation

  • Genetic Algorithms. Basic Notions and some Advanced Topics: Part 1
  • Genetic Algorithms. Basic Notions and some Advanced Topics: Part 2

Complementary Bibliography

  • Genetic Algorithms
    • D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, 1989.
    • Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Springer Verlag, 1996.
    • D.B. Fogel (Ed.) Evolutionary Computation. The Fossil Record. (Selected Readings on the History of Evolutionary Computation). IEEE Press, 1998.
    • A.E. Eiben, J.E. Smith. Introduction to Evolutionary Computation. Springer Verlag 2003. (Natural Computing Series)
    • D. Whitley "A Genetic Algorithm Tutorial". Statistics and Computing, 4, (1994), 65-85.
    • F. Herrera, M. Lozano, J.L. Verdegay, Tackling Real-Coded Genetic Algorithms: Operators and tools for the Behaviour Analysis. Artificial Intelligence Review 12 (1998) 265-319.
    • S. Ventura, C. Romero, A. Zafra, J.A. Delgado, C. Hervás-Martínez. JCLEC: A Java Framework for Evolutionary Computing. Soft Computing, 2007, in press.
  • Niching Genetic Algorithms
    • B. Sareni, L. Krähenbühk, Fitness Sharing and Niching Methods Revisited. IEEE Transactions on Evolutionary Computation, Vol. 2, No. 3, Septiembre 1998, 97-106.
    • Pétrowski, A. (1996). A clearing procedure as a niching method for genetic algorithms. In Proc. IEEE International conference on evolutionary computation. Japan. Pp. 798-803.
    • Pérez, E., Herrera, F. and Hernández, C. (2003). Finding multiple solutions in job shop scheduling by niching genetic algorithms. Journal of Intelligent Manufacturing, (14) Pp. 323-341.
  • Multiobjective Genetic Algorithms
    • C.A. Coello, D.A. Van Veldhuizen, G.B. Lamont, Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, 2002.
    • K. Deb, Multi-Objective Optimization using Evolutionary Algorithms. John Wiley & Sons, 2001
    • E. Zitzler, L. Thiele. Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation 3:4 (1999) 257-217.
    • E. Zitzler, K. Deb, L. Thiele. Comparison of Multiobjetive Evolutionary Algorithms: Empirical Results. Evolutionary Computation 8:2 (2000) 173-195.
    • Eckart Zitzler, Marco Laumanns, Lothar Thiele: SPEA2: Improving the Strength Pareto Evolutionary Algorithm. Zürich, TIK Report Nr. 103, Computer Engineering and Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich, May, 2001.
    • K. Deb, A. Pratap, S. Agarwal and T. Meyarivan. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6:2 (2002) 182-197.
    • C.A. Coello. Evolutionary Multiobjective Optimization: Current and Future Challenges. In J. Benitez, O. Cordon, F. Hoffmann, and R. Roy (Eds.), Advances in Soft Computing---Engineering, Design and Manufacturing. Springer-Verlag, September, 2003, pp. 243 - 256.
    • E. Zitzler, L. Thiele, M. Laumanns, C.M. Fonseca, and V. Grunert da Fonseca. Performance Assessment of Multiobjective Optimizers: An Analysis and Review. IEEE Transactions on Evolutionary Computation 7:2, April, 2003, pp. 117 - 132.
    • M. Laumanns, L. Thiele, K. Deb, and E. Zitzler. Combining Convergence and Diversity in Evolutionary Multi-objective Optimization. Evolutionary Computation 10:3, Fall, 2002, pp. 263 - 282.
    • K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalable Test Problems for Evolutionary Multiobjective Optimization. In A. Abraham, L. Jain, and R. Goldberg (Eds.), Evolutionary Multiobjective Optimization. Theoretical Advances and Applications. Springer, USA, 2005, pp. 105 - 145.
  • Memetic Algorithms
    • Recent Advances in Memetic Algorithms Studies in Fuzziness and Soft Computing, Vol. 166 Hart, William E.; Krasnogor, N.; Smith, J.E. (Eds.) 2005, X, 408 p., Hardcover ISBN: 3-540-22904-3
    • N. Krasnogor and J.E. Smith. A tutorial for competent memetic algorithms: model, taxonomy and design issues. IEEE Transactions on Evolutionary Computation 9(5):474- 488, 2005.
    • Y.S. Ong and M.-H. Lim and N. Zhu and K.W. Wong. Classification of Adaptive Memetic Algorithms: a Comparative Study IEEE Transactions on System, Man. and Cybernetic 36:1, 141-152, 2006.
    • P. Moscato, C. Cotta, “Una Introducción a los Algoritmos Memeticos”, Inteligencia Artificial. Revista Iberoamericana de IA, No. 19,2003, 131-148.
    • Knowles, J.D.; Corne, D.W.; M-PAES: a memetic algorithm for multiobjective optimization Evolutionary Computation, 2000. Proceedings of the 2000 Congress on Volume 1, 16-19 July 2000 Page(s):325 - 332 vol.1
    • Andrzej Jaszkiewicz Genetic Local Search for Multi-Objective Combinatorial Optimization European Journal of Operational Research 137, 2002, 50-71.
    • Ishibuchi, H.; Yoshida, T.; Murata, T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling Evolutionary Computation, IEEE Transactions on 7:2 (2003), 204 – 223
  • Genetic Learning
    • O. Cordón, F. Herrera, F. Hoffmann, L. Magdalena. GENETIC FUZZY SYSTEMS. Evolutionary Tuning and Learning of Fuzzy Knowledge Bases. World Scientific, Julio 2001.
    • M.L. Wong, K.S. Leung, Data Mining using Grammar Based Genetic Programming and Applications. Kluwer Academics Publishers, 2000.
    • A. Ghosh, L.C. Jain (Eds.), Evolutionary Computation in Data Mining. Springer- Verlag, 2005.
    • A.A. Freitas, Data Mining and Knowledge Discovery with Evolutionary Springer-Verlag, 2002.
    • John J. Grefenstette (Eds.) Genetic Algorithms for Machine Learning. Kluwer-Academic, 1993.
    • Sankar K. Pal and Paul P. Wang (Eds.)Genetic Algorithms for Pattern Recognition CRC Press, 1996.
    • J. Alcalá, et al. KEEL: A Software Tool to Assess Evolutionary Algorithms to Data Mining Problems. Soft Computing, 2007, submitted.