Solutions to Parallel and Distributed Computing Problems: Lessons from Biological Sciences

2.5 TEST PROBLEMS

The main motivation for our experimental evaluation of the different variants of parallel evolutionary algorithms is the fact that analytical insights into their behavior have been obtained only with respect to rather simple theoretical models. That means these insights do not necessarily apply to realistic applications. Therefore, in order to obtain some empirical insights into the influence of the main parameters of parallel evolutionary algorithms, we selected several rather complex optimization problems that differ with respect to problem size and problem structure. An important criterion for the selection of problems was the availability of benchmark instances, because this allowed us to check the results of our implementation of the evolutionary algorithm against the results computed by other approaches. Furthermore, we designed a systematic method for comparing the results of different runs of an evolutionary algorithm over a range of problem sizes and problem types. This method is described in Section 2.6.

Below we list those test problems that have been used to obtain the most interesting results of our empirical study. For the complete list of problems and the comprehensive presentation of all the results, the reader is referred to [15].

• The Traveling Salesperson Problem (TSP) This is probably one of the most thoroughly investigated optimization problems and therefore suggests itself as a benchmark problem for testing the optimization quality of evolutionary ...