Peer-to-peer evolutionary computationa study of viability

Resumen

Evolutionary Algorithms are a set of population based stochastic search techniques able to solve optimisation problems in reasonable time, However, the execution times of EAs can be high for very demanding problems and parallelism arises as an alternative to improve the algorithm performance and to speed up times to solutions. In that context, this thesis presents a spatially structured EA able to take full-advantage of the large amount of available resources in P2P platforms. Such an approach defines a decentralised population structure by means of a P2P protocol in which every individual has a limited number of neighbours with the mating choice locally restricted within the P2P neighbourhood. The emergent population structure behaves as a small-world topology and plays an important role in the preservation of the genetic diversity. That way, population sizes can be minimised and execution times improve. Nevertheless, there are remaining challenges towards an efficient design of P2P EAs. Questions such as decentralisation (such a computation paradigm is devoid of any central server), scalability (since P2P systems are large-scale networks) or fault tolerance (given that computational resources are added and eliminated dynamically) become of the maximum interest and have to be addressed. Therefore, this thesis focuses on analysing such issues (i.e. decentralisation, scalability and fault-tolerance) in order to conclude the viability of the Peer-to-Peer Evolutionary Computation paradigm.