An Examination of Lamarckian Genetic Algorithms

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


C. Wellock and Brian J. Ross: An Examination of Lamarckian Genetic Algorithms. GECCO-2001 Late-breaking papers, pp.474-481.



In keeping with the spirit of Lamarckian evolution, variations on a simple genetic algorithm are compared, in which each individual is optimized prior to evaluation. Four different optimization techniques in all are tested: random hillclimbing, social (memetic) exchange, and two techniques using artificial neural nets (ANNs). These techniques are tested on a set of three sample problems: an instance of a minimum-spanning tree problem, an instance of a travelling salesman problem, and a problem where ANNs are evolved to generate a random sequence of bits. The results suggest that in general, social exchange provides the best performance, consistently outperforming the non-optimized genetic algorithm; results for other optimization techniques are less compelling.

Extended Abstract


Used References

Ackley, D. H. & Littman, M. L. A Case for Lamarckian Evolution. (1994). In C. G. Langton (Ed.), Artificial Life III. (pp. 3-11). Reading, MA: Addison-Wesley.

Arora, Sanjeev. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. (1996). In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. (pp. 2-12).

Burkhardt, Richard W., Jr. (1977). The Sprit of System. Cambridge, MA: Harvard University Press.

Cheng, R. & Gen, M. (1997). Parallel Machine Scheduling Problems Using Memetic Algorithms. Computers & Industrial Engineering, 33(3-4), 761-764.

Cheng, R., Gen, M., & Tsujimura, Y. (1999). A tutorial survey of job-shop scheduling problems using genetic algorithms, part II: hybrid genetic search strategies. Computers & Industrial Engineering, 36, 343-364.

Darwin, Charles. (1859) . On the Origin of Species by Means of Natural Selection. London: J. Murray.

Dozier, G., Bowen, J., & Homaifar, A. (1998). Solving Constraint Satisfaction Problems Using Hybrid Evolutionary Search. IEEE Transactions on Evolutionary Computation, 2(1), 23-32.

Gen, M., Ida, K. & Li, Y. (1998). Bicriteria Transportation Problem by Hybrid Genetic Algorithm. Computers & Industrial Engineering, 35(1-2), 363-366.

Grefenstette, J. Lamarckian Learning in Multi-agent Environments. (1991). In Proceedings of the Fourth International Conference on Genetic Algorithms. (pp. 303-310). San Mateo, CA: Morgan Kaufmann.

Grimaldi, R. (1994). Discrete and Combinatorial Mathematics. Reading, MA: Addison-Wesley.

Han, J., Moraga, C., & Sinne, S. (1996). Optimization of Feedforward Neural Networks. Engineering Applications of Artificial Intelligence, 9(2), 109-119.

Hart, W. E., & Belew, R. K.. Optimization with Genetic Algorithm Hybrids that Use Local Search. (1996). In R.K. Belew & M. Mitchell (Eds.), Adaptive Individuals in Evolving Populations. (pp. 483-496). Reading, MA: Addison-Wesley.

Hinton, G. E. & Nowlan, S. J. How Learning Can Guide Evolution. (1996). In R. K. Belew & M. Mitchell (Eds.), Adaptive Individuals in Evolving Populations. (pp. 447- 457). Reading, MA: Addison-Wesley.

Katayama, K., Sakamoto, H. & Narihisa, H. (2000). The Efficiency of Hybrid Mutation Genetic Algorithm for the Travelling Salesman Problem. Mathematical and Computer Modelling, 31, 197-203.

Kim, K. & Han, I. (2000). Genetic algorithms approach to feature discretization in artificial neural networks for the prediction of stock price index. Expert Systems with Applications, 19, 125-132.

Knuth, Donald. (1969). The Art of Computer Programming, vol. 2. Reading, MA: Addison-Wesley.

Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Reading, MA: MIT Press.

Lamarck, Jean-Baptiste. (1801). Système des animaux sans vertèbres. Paris.

Li, Y., Tan, K. C., & Gong, M. Model reduction in control systems by means of global structure evolution and local parameter learning. (1996). In D. Dasgupta & Z. Michaelwicz (Eds.), Evolutionary Algorithms in Engineering Applications. New York: Springer-Verlag.

Mitchell, Melanie. (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press.

Pinker, S. (1997). How the Mind Works. New York: W. W. Norton & Co.

Watson, M. (1997). Intelligent Java Applications for the Internet and Intranets. San Francisco: Morgan Kaufmann Publishers.

Whitley, D., Gordon, V. S., & Mathias, K. Lamarckian Evolution, the Baldwin Effect and Function Optimization. (1994). In Y. Davidor et al. (Eds.), Parallel Problem Solving From Nature, vol. 3. (pp. 6-15). New York: Springer-Verlag.


Full Text

intern file

Sonstige Links