The fruit fly optimization algorithm (FOA) was a recently proposed. FOA has a number of advantages over other nature-inspired algorithms such as its simple structure and ease of implementation. However, the FOA’s search procedures present a problem. FOA has a low success rate search and a slow convergence when it has to deal with complex problems. This is because FOA generates a new position around its swarm location using a random uniform distribution. To eliminate this drawback, our paper presents an improved fruit fly algorithm called RO-FOA. The RO-FOA technique takes knowledge of a mutualistic relationship common in ecosystems and biological theory. Our strategy blends two popular algorithms, i.e., the random walk (RW) and the opposition-based learning (OBL) algorithms, to establish a two-characteristic swarm for searching procedures. RO-FOA’s structure is very compact as the implementation uses only three fruit flies. Furthermore, the advantages of including a two-characteristic population and dynamic distribution adaptation in the evolving process can produce an algorithm with the necessary search efficiency to find an optimal solution. A comprehensive set of 34 benchmark functions, containing a wide range of dimensions were used to validate the capability of the proposed algorithm. The results show that RO-FOA outperformed the existing FOA, as well as seven comparatively well-known meta-heuristic algorithms. RO-FOA can efficiently train multi-layer perceptrons for 5-bit and 8-bit auto-encoder problems. These results demonstrate that the RO-FOA can enhance the diversity of population distributions, solution quality and the convergence rate of the algorithm.