Multidimensional Sequence Alignment Methods for Activity Pattern Analysis: A comparison of dynamic programming and genetic algorithms
Chang‐Hyeon Joh, Theo Arentze, Harry J.P. Timmermans · RePEc: Research Papers in Economics · 1999
Quantitative comparisons of space-time activity patterns are a critical element in several streams of research in regional science.Traditionally, Euclidean distance and the measures developed in botanical taxonomy have been widely used to measure the similarity between activity patterns that involve several attribute dimensions such as location, transport mode, accompanying persons, etc.Some other techniques, such as pattern recognition in signal processing theory, have also been introduced for this purpose.These measures however lack the ability to capture the information of the overall sequence of activity patterns of multiple attributes.Recently, the Sequence Alignment Methods (SAMs), developed in molecular biology that are concerned with the distances between DNA strings, have been introduced in time use research.The SAMs captures the similarity of activity patterns based on a single attribute only.Unfortunately, the extension of the unidimensional SAM to a multidimensional method induces the problem of combinatorial explosion.To solve this problem, this paper introduces effective heuristic methods for the comparison of multidimensional activity patterns.First, the combinatorial nature of the algorithm is discussed.The paper then develops alternative SAMs based on dynamic programming and genetic algorithms, respectively.These two SAMs are compared using empirical activity pattern data.The paper ends by discussing avenues of future research.