We briefly review and compare the mathematical formulation of Markov decision processes (MDP) and evolutionary algorithms (EA). In so doing, we observe that the adaptive critic design (ACD) approach to MDP can be viewed as a special form of EA. This leads us to pose pertinent questions about possible expansions of the methodology of ACD. This expansive view of EA is not limited to ACD. We discuss how it is possible to consider the powerful chained Lin Kernighan (chained LK) algorithm for the traveling salesman problem (TSP) as a degenerate case of EA. Finally, we review some recent TSP results, using clustering to divide-and-conquer, that provide superior speed and scalability.
D. C. Wunsch and S. A. Mulder, "Evolutionary Algorithms, Markov Decision Processes, Adaptive Critic Designs, and Clustering: Commonalities, Hybridization and Performance," Proceedings of the International Conference on Intelligent Sensing and Information Processing, 2004, Institute of Electrical and Electronics Engineers (IEEE), Jan 2004.
The definitive version is available at http://dx.doi.org/10.1109/ICISIP.2004.1287704
International Conference on Intelligent Sensing and Information Processing, 2004
Electrical and Computer Engineering
Keywords and Phrases
Markov Decision Process; Markov Processes; Adaptive Critic Design; Chained Lin Kernighan Algorithm; Divide and Conquer Methods; Evolutionary Algorithms; Evolutionary Computation; Traveling Salesman Problem; Travelling Salesman Problems
Article - Conference proceedings
© 2004 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.