Jump to content
  • Advertisement
Sign in to follow this  
larspensjo

Fitness function for self modifying programming

This topic is 1514 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Problem: How to make a good fitness function?

 

Assumptions:

  • There is a specially designed programming language.
  • The program will not directly modify itself, but indirectly through the use of genetic algorithms.
  • Using mutations combined with child generation from random parents.
  • The language is fairly resilient to bit mutations.
  • The merger of two parents will have a high chance of producing a new algorithm that is not completely broken.

A problem with using randomly created algorithms, compared to e.g. neural networks, is that these algorithms are unlikely to produce any usable output. At least initially. Designing a fitness function for a numerical output can be easy, which could be a measurement of the distance from the result to the target. But what about a fitness function for a sorting algorithm?

 

Using a fitness function limited to the outputs 0 and 1 is not good enough. It will almost always produce 0, not providing any help for the genetic algorithms. Given my preconceptions about sorting, I could create a fitness function that gives some score for actually reproducing some input on the output. And gradually increase the score the better the output is ordered.

 

But there are drawbacks with this kind of fitness functions:

  • It presumes that a certain intermediary result is good, a step on the way to a final solution. But that may prevent the algorithm from finding the non obvious solutions I didn't know about.
  • It requires a lot of effort to formulate. A different function will be needed for different algorithm problems.

I am not sure there a solution to this problem. Any feedback or references are welcome!

Share this post


Link to post
Share on other sites
Advertisement

I would suggest a fitness function that is based on how sorted it is vs an estimate of the big Oh complexity.

 

I realise that there are many potential metrics for how sorted something is, and some may not be ideal in all conditions. A few possibilities are:

  • RMS of distance of elements from their correct sorted position.
  • Proportion of elements which moved in the correct direction vs the wrong direction.
  • An estimate of how many swaps would be required to finish sorting.

The big Oh complexity could be:

  • Based on the time to execute.
  • Based on the number of instructions actually executed running it on a large input.
  • A comparison of the number of instructions executed for different sized inputs.
  • Based on some static analysis of the algorithm.

Share this post


Link to post
Share on other sites
EDIT: Never mind. The problem is sorting, although it takes a while to learn that in the original post.

Why would you use any of these techniques for sorting? Sorting is a well solved problem.

Share this post


Link to post
Share on other sites

Problem is not specifically for sorting, but the more general case. I just used sorting as an example.

 

It may be that it is impossible to formulate general purpose fitness functions for problems that are not numerical in nature, unless using detailed knowledge of the specific problem.

 

Jeferytitan had some interesting suggestions I can build on. That is, it is easier to define penalties on behavior. 

Edited by larspensjo

Share this post


Link to post
Share on other sites

Karl Simms had great success with pure generic algorithms, the "programs" are boolean logic components that evolve genetically (pdf).

I haven't tried, but I think it might work with a similar setup based purely on Feed forward Neural Network (since they can represent equally complex mathematical functions).

Cheers,

/Thomas

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!