4

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.

Tory
  • 175
  • 6
  • 1
    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. – NietzscheanAI Oct 07 '16 at 12:42
  • This question is unclear to me. What is a genetic program? Do you mean a _genetic programming **algorithm**_ (which is able to evolve programs)? – nbro Dec 07 '20 at 17:44

2 Answers2

1

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.

Nuclear Hoagie
  • 288
  • 1
  • 4
  • 1
    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. – BlindKungFuMaster Oct 07 '16 at 07:26
  • @BlindKungFuMaster You missed the magical words "Brute force" :) – Ankur Oct 07 '16 at 10:16
1

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.

Community
  • 1
NietzscheanAI
  • 7,206
  • 22
  • 36