An effective distributed caching strategy for partial result reuse for discrete optimization problems

Evolutionary Computation (EC) is one of the most advanced computational techniques. It has been frequently and successfully used to find good solutions to many complicated optimization problems with limited computational resources. EC is the iterative procedure of examining a set of possible solutions (called the population) and modifying the solutions based on a method relying on probability and randomization. As a result, the quality of the final solution achieved depends on the number of solutions investigated during the evolutionary procedure in general.;Although this procedure is essential to find good solutions efficiently, its computational load is a well known bottleneck of EC. In particular, for optimization problems whose objective function is highly complicated, population-based approaches may not be applicable and technical advancement to save computing time is necessary. Previously, several methods were studied to address this issue such as reusing partial fitness computations, approximating fitness function and hybridizing local and global searches. Parallel and distributed computation has been studied as well to enhance performance by increasing computational resources.;In particular, caching, which reuses partial values of objective (fitness) function computations, is one of the most promising techniques, because it maintains the accuracy of the original objective function, as opposed to approximation, and is easily compatible with other performance enhancement techniques. Previously, an effective caching strategy was developed to save overall computational time of single processor EC in solving a challenging Hydrophobic-Polar protein folding problem. Although employing this caching strategy saves a significant amount of time, performance is limited when the local population becomes very diverse. Since the performance of caching relies on the amount of redundant computation, highly redundant computation improves caching performance but hinders the exploratory capability of EC. In order to find good solutions with limited resources we need to cope with appropriate diversity. Thus, local caches should be diversified accordingly to enhance the overall performance of EC. To achieve this, we developed a caching migration using communication among neighboring processors as a means to diversify local caches. These local caches are diversified by migrating parts of them among neighboring processors, whereas previous caching strategy relied only on locally computed results. In caching migration, communication messages are composed of partial values of the objective function and their relations.;Our contribution in this thesis is the development of a theoretical model of parallel and distributed EC embedded with a distributed caching strategy and also to investigate its effectiveness in solving complex discrete optimization problems. From the theoretical and empirical study we have conducted so far, we conclude that our distributed caching strategy is a promising technique to enhance the time performance of parallel and distributed EC. This will broaden the applicability of EC as performance is improved by the migration of local caches in addition to the use of locally redundant computations through an effectively designed caching strategy.