Query optimization in object-oriented databases requires new techniques for supporting features such as methods, path expressions, and so on. In this paper we address the optimization of path predicates in object-oriented queries. We apply the genetic search strategies to our optimization problem, and show that our formulation is well-suited to genetic algorithms.