Improving volunteer computing scheduling for evolutionary algorithms

摘要

Evolutionary Algorithms (EA) have been extensively used in research to resolve optimization problems involving computationally intensive objective function evaluations. It is even more interesting to use a low-cost distributed computing platform based on Volunteer Computing (VC), to perform such optimizations. The downside is that VC compute nodes' volatility and unreliability associated with the level of task dependency introduced by parallel EA's tend to delay the algorithm's progress. This work proposes an enhanced scheduling of the B01NC (Berkeley Open Infrastructure for Network Computing) tasks associated with a Genetic Algorithm (GA) that aims at improving the performance of the algorithm. BOINC is the most popular middleware used for VC. While the GA has been chosen as it is the most commonly used EA, this approach is applicable to most of iterative EA's. The scheduling performs a matchmaking between a pool of tasks, classified according to their potential (predicted) fitness, and the pool of available hosts, classified according to their reliability. The scheduling technique have been implemented in a simulation environment and tested with benchmark functions. It proved to be effective in increasing the convergence speed and reducing the execution time of the GA.