4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean 'genetic program' or 'genetic algorithm'? $\endgroup$ – NietzscheanAI Oct 7 '16 at 12:22
  • $\begingroup$ @NietzscheanAI Genetic program $\endgroup$ – Tory Oct 7 '16 at 12:24
  • 1
    $\begingroup$ Of course, you will have to then assume that a solution to the problem is indeed expressible by some element of the program space. For example, if the problem is to compute Ackerman's function, then that can't be solved by GP with a primitive recursive function set. $\endgroup$ – NietzscheanAI Oct 7 '16 at 12:42
2
$\begingroup$

Yes.

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Of course this doesn't have much to do with genetic programming. If there is a solution, you can find it with random guessing given unlimited time. I would provide you even with an bounded time algorithm: If there is a solution, you can find it by trying all possible solutions. $\endgroup$ – BlindKungFuMaster Oct 7 '16 at 7:26
  • $\begingroup$ @BlindKungFuMaster You missed the magical words "Brute force" :) $\endgroup$ – Ankur Oct 7 '16 at 10:16
1
$\begingroup$

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:

  1. A function which takes on an optimal value iff it is applied to an optimal solution.
  2. 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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.