An Empirical Study of Population and Non-population Based Search Strategies for Optimizing a Combinatorical Problem

The performance of several algorithms for optimizing a combinatorical problem is compared empirically. The following topics are studied: • Can population based search strategies find good solutions faster than non-population ones? • Are strategies that recombine two individuals to form new solutions better than those who use one individual only?• Does the size of the population affect on the performance?• Does the way how individuals are selected from the population affect on the performance?The test problem used in these experiments is knapsack. 5000 variations of the test problem were solved. The number of the test function evaluations was recorded in the simulations. Statistical data was obtained in the form of cumulative frequencies and average values.Based on these simulations the short answers to the four questions above are: yes; not necessarily; yes, but it depends on the selection strategy; and yes.