Ask HN: Use Prolog to specify fitness function in a genetic programming context?

https://news.ycombinator.com/item?id=42528697

by 2ro • 2 years ago

3 3 2 years ago

news.ycombinator.com

Why not use Prolog to specify the fitness function in a genetic programming context?

Performance (fitness functions are usually high-volume/CPU intensive operations), state management (managing mutable state isn't Prolog's strong suit), and integration (you'll have to set up communication between whatever language/framework you're using and Prolog).

More generally, if you could completely specify what makes a solution "fit" using logic, you could just ask Prolog to find a solution that satisfies those predicates. The search would then be handled by Prolog's built-in resolution and backtracking mechanisms rather than needing a GA.

Do you have a specific type of problem in mind?

2ro• 2 years ago

So, I would like to create/discover patentable algorithms.

One would not even have to run the logic programs in the normal sense - just interpret the declarative constraints in a direct way as a fitness function in the GP system...

verdverm• 2 years ago

If you notice the GP research, they almost all focus on Symbolic Regression because the problem space is easier with commutativity and associativity. Generating programs is much harder because of state-space issues and Genetic Programming quickly falls into premature convergence. If you actually look at the breadth of research in this field, it is almost all efforts to combat premature convergence. As an algorithm, I don't think GP is all that great of an optimization technique. My PhD turned from GP research to developing an alternative called Prioritized Grammar Enumeration (PGE). This could be adapted to generate programs, but I suspect similar scaling and correctness issues from state-space complexity. PGE does offer more opportunity to create local generators that ensure some amount of correctness. Both algos still primarily benefit from noticing and ignoring bad solutions, which dominate the search space (the search space is sparse w.r.t. good solutions)

I agree with GP that you'll likely have to create cross language techniques to develop a system that has reasonable performance. I used a mix of Go & Python and used REST APIs to communicate between the processes. It was actually more performant overall by doing so, as certain subtasks had bad performance (small object allocation in Python was a bottleneck, Go lacks SymPy equivalent for mathematical simplification).

Ask HN: Use Prolog to specify fitness function in a genetic programming context?

Related Stories