Simulated evolutionary optimization and local search: Introduction and application to tree search

Tree search and its more complicated variant, tree search and simultaneous multiple DNA sequence alignment, are difficult NP-complete optimization pro blems, which require the application of advanced computational techniques, if large data sets are to be solved within reasonable computation times. Tr aditionally tree search has been attacked with a search strategy that is be st described as multistart hill-climbing; local search by branch swapping h as been performed on several different starting trees. Recently a different tree search strategy was tested in the Parsigal parsimony program, which u sed a combination of evolutionary optimization and local search. Evolutiona ry optimization algorithms use principles adopted from biological evolution to solve technical optimization tasks. Evolutionary optimization is a stoc hastic global search method, which means that the method is able to escape local optima, and is in principle able to produce any solution in the searc h space (although this may take a long time). Local search techniques, such as branch swapping, employ a completely different search strategy; they ex ploit local information maximally in order to achieve quick improvement in the value of the objective function. However, local search algorithms lack the ability to escape from local optima, which is a fundamental requirement for any search algorithm that aims to be able to discover the global optim um of a multimodal optimization problem. Hence it seems that an optimizatio n strategy combining the good properties of both evolutionary algorithms an d local search would be ideal. In this study, aspects of global optimizatio n and local search are discussed, and the method of simulated evolutionary optimization is reviewed in detail. The application of simulated evolutiona ry optimization to tree search in Parsigal is then reviewed briefly. (C) 20 01 The Willi Hennig Society.