  The increasing complexity of fog computing environments calls for efficient
resource optimization techniques. In this paper, we propose and evaluate three
distributed designs of a genetic algorithm (GA) for resource optimization in
fog computing, within an increasing degree of distribution. The designs
leverage the execution of the GA in the fog devices themselves by dealing with
the specific features of this domain: constrained resources and widely
geographical distribution of the devices. For their evaluation, we implemented
a benchmark case using the NSGA-II for the specific problem of optimizing the
fog service placement, according to the guidelines of our three distributed
designs. These three experimental scenarios were compared with a control case,
a traditional centralized version of this GA algorithm, considering solution
quality and network overhead. The results show that the design with the lowest
distribution degree, which keeps centralized storage of the objective space,
achieves comparable solution quality to the traditional approach but incurs a
higher network load. The second design, which completely distributes the
population between the workers, reduces network overhead but exhibits lower
solution diversity while keeping enough good results in terms of optimization
objective minimization. Finally, the proposal with a distributed population and
that only interchanges solution between the workers' neighbors achieves the
lowest network load but with compromised solution quality.
