5 ms·

Reminds me of good ol genetic algorithm search. Guess and check can be quite powerful, especially if you can toss in agent in the loop guidance. https://en.wik

Reminds me of good ol genetic algorithm search. Guess and check can be quite powerful, especially if you can toss in agent in the loop guidance. https://en.wikipedia.org/wiki/Evolved_antenna https://en.wikipedia.org/wiki/Evolved_antenna

ben_w 3mo ago
Was going to say much the same. I recall one story about a genetic algorithm to make an oscillator with the fewest possible components, and it successfully did so by surprising the humans with a single wire, i.e. an antenna picking up nearby stray RF.
- robviren 3mo ago
  That is my favorite part of GA. Gradient free optimization but it turns out making a good fitness function is hard and like 70% of the time it just exploits some assumptions or gap you have in your theories. Really reveals the problem in different ways that traditional ML.
  - deleted 3mo ago
    [deleted]
  - nz 3mo ago
    As someone who does a lot of genetic programming (like, old-school, without AI/LLMs, etc), I can confirm that the fitness function is very difficult to get right, especially if you are trying to evolve programs that have "adversarial fitness" -- you'd need to maintain a hall-of-fame, and that just makes the runs take _much_ longer, because, chances are, your fitness function is the bottle-neck. So, it is very hands-off, but also very expensive, and it is never clear if optimizing the fitness function is worth it, because the fitness function itself may be insufficiently or incorrectly specified. However, I do think that people should try, even with just a whiteboard or a notebook, to design a fitness-function, for their problem, as if they were going to try to evolve it, because (1) it forces them to explicate their correctness constraints, and (2) they may discover that the program that they are trying to write _is equivalent_ to the fitness function. I'll give you an example for point 2. Many years ago, I had to parse a gnarly language, and I chose to do it via Chomsky Grammars (that automatically build a tree based on the grammar-spec). Chomsky Grammars are cool, in that they are basically just a state-machine, but they are incredibly difficult to debug: when they work, they might work incorrectly (malformed tree), and when they fail, they give no reason for failure (because even with a trace, you are trying to figure out which backtrack should not have happened). So, out of desperation, I started to consider using genetic programming to just evolve a correct Chomsky Grammar. It became clear that there are only 2 possible fitness functions (1) a function that tests a hand-picked input against a hand-crafted tree-output (which is vulnerable to over-fitting), and (2) a function that is not (well, is much less) vulnerable to over-fitting, but is effectively a pre-existing, correct grammar that can produce those trees. If you are in situation 2, then the genetic programming is not necessary, unless you are trying to create an optimized (or obfuscated) parser, and even then the optimization may be overfit to the test-inputs (even if they are generated test-inputs from the grammar itself). If you are in situation 1, then you are better off re-evaluating your approach (I abandoned the Chomsky Grammar notation, and invented one that is much easier to understand and debug, without losing any of the expressiveness -- it also happens to be slower, but fast-and-broken is worthless compared to not-so-fast-and-works-fine). One place where genetic programming has been consistently awesome, is in parameter-search style problems (e.g. your genome is a long list of floats, representing weights and/or anti-weights, and you need to find out which weights give you more fitness (or less error)). I hear good things about variable-neighborhood-search, but have yet to try it.
    - deterministic 3mo ago
      Maybe you could have generated random test input, generated the trees, and then converted the trees back to the input, checking if they match?
      - nz 3mo ago
        Yeah, that is situation 2 mentioned above. A Chomsky Grammar is also a generator. So it can generate valid inputs, and then turn them into valid outputs -- and it can do the first part stochastically/randomly.
- formerly_proven 3mo ago
  That sounds apocryphal but there was a noted paper describing a frequency discriminator implemented using a genetic algorithm and it ended up tied to the exact piece of silicon used to evolve it, with logic cells not connected to anything still changing the output. https://osmarks.net/assets/misc/evolved-circuit.pdf https://osmarks.net/assets/misc/evolved-circuit.pdf
typinghole 3mo ago
This too: https://en.wikipedia.org/wiki/Evolvable_hardware https://en.wikipedia.org/wiki/Evolvable_hardware Starting with: https://sci-hub.ru/storage/moscow/4324/11d145b2c2c3ab320f70b4839b7590b2/thompson1997.pdf https://sci-hub.ru/storage/moscow/4324/11d145b2c2c3ab320f70b...
- knotimpressed 3mo ago
  That second paper is absolutely amazing, I’ve always heard this story and never bothered to find the source. The section with oscilloscope traces showing the progression of the “designs” over time was extremely interesting - I’d love to see what the 10x10 grid of functions looked like at each snapshot. Thank you!
smath 3mo ago
GA’s optimize only combinatorial problems though — where you have discrete set of choices (~genes) for each variable, and therefore do not have a gradient
- fc417fc802 3mo ago
  You can use a GA with continuous parameters and a smooth gradient but it probably isn't the most efficient method in that case.
mycall 3mo ago
The other side is Cognitive Radio [1] which also evolve the OTA protocols for cooperative diversity from IEEE 802.22 onwards. Now I can see AI, via a local SLM/NPU plus agentic GNURadio loops for new radio use cases. This is going to be much more wide spread in the upcoming 3GPP 6G releases in 2030. [1] https://en.wikipedia.org/wiki/Cognitive_radio https://en.wikipedia.org/wiki/Cognitive_radio

ben_w 3mo ago

Was going to say much the same. I recall one story about a genetic algorithm to make an oscillator with the fewest possible components, and it successfully did so by surprising the humans with a single wire, i.e. an antenna picking up nearby stray RF.

robviren 3mo ago
That is my favorite part of GA. Gradient free optimization but it turns out making a good fitness function is hard and like 70% of the time it just exploits some assumptions or gap you have in your theories. Really reveals the problem in different ways that traditional ML.
- deleted 3mo ago
  [deleted]
- nz 3mo ago
  As someone who does a lot of genetic programming (like, old-school, without AI/LLMs, etc), I can confirm that the fitness function is very difficult to get right, especially if you are trying to evolve programs that have "adversarial fitness" -- you'd need to maintain a hall-of-fame, and that just makes the runs take _much_ longer, because, chances are, your fitness function is the bottle-neck. So, it is very hands-off, but also very expensive, and it is never clear if optimizing the fitness function is worth it, because the fitness function itself may be insufficiently or incorrectly specified. However, I do think that people should try, even with just a whiteboard or a notebook, to design a fitness-function, for their problem, as if they were going to try to evolve it, because (1) it forces them to explicate their correctness constraints, and (2) they may discover that the program that they are trying to write _is equivalent_ to the fitness function. I'll give you an example for point 2. Many years ago, I had to parse a gnarly language, and I chose to do it via Chomsky Grammars (that automatically build a tree based on the grammar-spec). Chomsky Grammars are cool, in that they are basically just a state-machine, but they are incredibly difficult to debug: when they work, they might work incorrectly (malformed tree), and when they fail, they give no reason for failure (because even with a trace, you are trying to figure out which backtrack should not have happened). So, out of desperation, I started to consider using genetic programming to just evolve a correct Chomsky Grammar. It became clear that there are only 2 possible fitness functions (1) a function that tests a hand-picked input against a hand-crafted tree-output (which is vulnerable to over-fitting), and (2) a function that is not (well, is much less) vulnerable to over-fitting, but is effectively a pre-existing, correct grammar that can produce those trees. If you are in situation 2, then the genetic programming is not necessary, unless you are trying to create an optimized (or obfuscated) parser, and even then the optimization may be overfit to the test-inputs (even if they are generated test-inputs from the grammar itself). If you are in situation 1, then you are better off re-evaluating your approach (I abandoned the Chomsky Grammar notation, and invented one that is much easier to understand and debug, without losing any of the expressiveness -- it also happens to be slower, but fast-and-broken is worthless compared to not-so-fast-and-works-fine). One place where genetic programming has been consistently awesome, is in parameter-search style problems (e.g. your genome is a long list of floats, representing weights and/or anti-weights, and you need to find out which weights give you more fitness (or less error)). I hear good things about variable-neighborhood-search, but have yet to try it.
  - deterministic 3mo ago
    Maybe you could have generated random test input, generated the trees, and then converted the trees back to the input, checking if they match?
    - nz 3mo ago
      Yeah, that is situation 2 mentioned above. A Chomsky Grammar is also a generator. So it can generate valid inputs, and then turn them into valid outputs -- and it can do the first part stochastically/randomly.
formerly_proven 3mo ago
That sounds apocryphal but there was a noted paper describing a frequency discriminator implemented using a genetic algorithm and it ended up tied to the exact piece of silicon used to evolve it, with logic cells not connected to anything still changing the output. https://osmarks.net/assets/misc/evolved-circuit.pdf https://osmarks.net/assets/misc/evolved-circuit.pdf

typinghole 3mo ago

This too: https://en.wikipedia.org/wiki/Evolvable_hardware https://en.wikipedia.org/wiki/Evolvable_hardware Starting with: https://sci-hub.ru/storage/moscow/4324/11d145b2c2c3ab320f70b4839b7590b2/thompson1997.pdf https://sci-hub.ru/storage/moscow/4324/11d145b2c2c3ab320f70b...

knotimpressed 3mo ago
That second paper is absolutely amazing, I’ve always heard this story and never bothered to find the source. The section with oscilloscope traces showing the progression of the “designs” over time was extremely interesting - I’d love to see what the 10x10 grid of functions looked like at each snapshot. Thank you!

smath 3mo ago

GA’s optimize only combinatorial problems though — where you have discrete set of choices (~genes) for each variable, and therefore do not have a gradient

fc417fc802 3mo ago
You can use a GA with continuous parameters and a smooth gradient but it probably isn't the most efficient method in that case.

mycall 3mo ago

The other side is Cognitive Radio [1] which also evolve the OTA protocols for cooperative diversity from IEEE 802.22 onwards. Now I can see AI, via a local SLM/NPU plus agentic GNURadio loops for new radio use cases. This is going to be much more wide spread in the upcoming 3GPP 6G releases in 2030. [1] https://en.wikipedia.org/wiki/Cognitive_radio https://en.wikipedia.org/wiki/Cognitive_radio