Hybrid clouds, consisting of multiple individual smaller clouds with heterogeneous capabilities, are becoming more and more popular through concepts such as inter-clouds, fog-and edge-computing. They provide fast computations without introducing large network latency. However, such cloud environments often contain unreliable nodes and links that are failure prone. Therefore, the deployment of applications requiring availability guarantees is a current research challenge. If such a placement algorithm is CPU-, memory-, network-and availability-aware, the applications can use the resources as optimal as possible with a small failure probability. The optimal deployment of applications in the network infrastructure is a NP-hard problem and, as a consequence, exact algorithms to solve it are not scalable. In this paper we propose GRECO, a distributed genetic algorithm to place service-oriented applications on a hybrid cloud, by defining a representation of an application placement in a biased-random-key chromosome and using a fault-tolerance distributed pool model. When compared with an existing Integer Linear Programming approach, simulations show that GRECO is scalable (speedup of a factor of 1000) and obtain near optimal performance results.