Obviously this is hypothetical, but is true? I know "perfect fitness function" is a bit hand-wavy, but I mean it as we have a perfect way to measure the completion of any problem.
A totally random algorithm could solve any problem given unlimited time and a perfect fitness function. All you need to do is give the GA some new random population members each generation and you're guaranteed to find the solution eventually. Even if you keep only descendants of the previous generation, setting the mutation rate and number of crossovers high enough could effectively get you random individuals.
As per the answer to this AI SE question, the presence of mutation makes a GA into a global search algorithm, i.e. it will eventually visit each point in the search space.
How efficiently it will do so is indeed related to the quality of the fitness function:
A 'perfect fitness function' could conceivably mean any of the following:
- A function which takes on an optimal value iff it is applied to an optimal solution.
- A function which forms a quadratic bowl (Newton's method can solve this in one step).
A degenerate case of 1. is a 'Needle in a haystack' function, which returns the same arbitrarily poor value everywhere that isn't an optimum, and 2. unfortunately doesn't arise very often in practice.
Hence, the role of a well-designed fitness function is to impose a gradient on the search process, which in practice will generally lie somewhere in-between 'Needle in a haystack' and 'Quadratic bowl'.
The presence of some form of smoothness in the fitness function is one mechanism that allows better performance than random or exhaustive methods.