7 ms·

Maybe someone more versed in the state-of-the-art can help me: has the concept of "speciation" ever been applied to genetic algorithms? In my instance, there a

• grinich 13y ago
  Actually, the thing genetic algorithms try to do is break out of this local maximum, mutating past a trait correlated with poor performance in hopes of finding a more fit solution.
  • IvyMike 13y ago
    In my hypothetcial algorithm, of course mutation would still take place. But my current instace of the web page is at a point where it's wasting a lot of time on unfit 'mutts' and it seems like I could get to a "best rhinoboat" and "best assdragger" solution faster if it would stop wasting time exploring the mediocre blend.
    • grinich 13y ago
      Yeah, most effective genetic algorithms take a hybrid approach where they only do more dramatic mutations for some of the population, and then optimize the rest with a regular fitness function and small variations. The goal with these systems is to have several different but effective breeds emerge. I didn't dig into this implementation, but it seems like it doesn't carry many (more than one?) individuals between cycles.
• icambron 13y ago
  Yes, what you're describing is niching. See, e.g., http://architects.dzone.com/articles/algorithm-week-niching-genetic http://architects.dzone.com/articles/algorithm-week-niching-...
  • IvyMike 13y ago
    That's it--thanks!
• ianterrell 13y ago
  You, sir, have mastered at least one of the two hard problems in computer science.
  • habosa 13y ago
    Seriously. I knew right away that I also had "rhinobat"s and "assdragger"s.
  • BHSPitMonkey 13y ago
    Two more to go!
• darkmighty 13y ago
  Also, I found these algorithms could always go more and more meta. For instance, in some situations a large "clone fraction" was optimal, or large "mutation rate", whilst in other cases it brought chaos and degraded the population. Successful parameters could also become more immune to mutation with time, a nice improvement along with "speciation" you cited.
  • Xcelerate 13y ago
    > Also, I found these algorithms could always go more and more meta. Haha, I've had this same thought before. I wrote a genetic algorithm to work on the sphere packing problem (in a periodic box) and I kept thinking about how I could mutate the settings within the program and optimize them, and then mutate the rate at which those settings themselves changed, and so on. I wonder if there's an optimal point to stop being "meta"?
    • gknoy 13y ago
      We could probably find it with some kind of Monte-Carlo technique...
    • darkmighty 13y ago
      There are information theoretic aspects behind this. You're essentially searching the design space for the fittest and want a fast way to get your answer -- this 'fastest way' is related to the way that 'grants' maximum information. I say this because this reminded me of a wonderful (and acessible) discussion I once glanced over on the following book: http://www.cs.toronto.edu/~mackay/itprnn/book.pdf http://www.cs.toronto.edu/~mackay/itprnn/book.pdf (Page 269, pdf 281) -- it offers answers to this sort of question :)
    • randomsearch 13y ago
      You're looking for "hyper-heuristics." So called, because unfortunately GAs etc. had already taken the name "meta-heuristics".
    • tripzilch 13y ago
      > I wonder if there's an optimal point to stop being "meta"? Perhaps this will help your thinking in the right direction: http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_optimization http://en.wikipedia.org/wiki/No_free_lunch_in_search_and_opt...
• hcarvalhoalves 13y ago
  This happens in nature, actually. When there's a genetic disparity between individuals, although offspring is possible, it ends up infertile. That's nature's way of doing a U-turn. When the hybridization is managed by humans though, it can be useful (e.g.: citrus, mules).
• Houshalter 13y ago
  Well it's a bit more difficult, but you could let the organisms themselves decide who to mate with. Or you could have a smarter genetic algorithm that keeps sufficiently different organisms and tries evolving them for a few generations and see which type is superior. There is really no advantage in speciation if you only want the single best solution, but it does make sense to try different evolutionary paths as they can end up in totally different places.
  • tinco 13y ago
    That's a bit of a weird assertion. Genetic algorithms are always a greedy heuristic to find a solution for a problem. It is not guaranteed at all that it will find the single best solution faster than straight bruteforcing solutions. If speciation is a better heuristic for finding a better solution faster than the algorithm used here then its advantage is real and useful in any case.
    • Houshalter 13y ago
      What I meant by that dividing the population has a cost. Only one evolutionary path is going to end up with the best solution. By best I mean the best one you find, not necessarily the most optimal solution possible, which may never be found. If you divide the population in two, at least half of your resources are wasted on doing tests and evolving traits which will just be discarded. Resources which could have been used to speed up the evolution of the other population. Even if the evolutionary path you choose isn't the optimal one, by putting twice as much resources too it, it still might end up further. And if you divide it into more than 2 species than it's just getting insane. That's not to say that speciation isn't a useful heuristic, just that it's a costly one. However there are a lot of cases where just throwing more resources at the problem doesn't help, because it's stuck in a local maxima. In that case, going back to an earlier point in the simulation and running it to see if it ends up somewhere else isn't a bad idea, and that's exactly the same as what speciation is (except that you are doing it after the fact, rather than testing both evolutionary paths simultaneously.)
• Laremere 13y ago
  Check out darwin pond: http://www.ventrella.com/darwin/darwin.html http://www.ventrella.com/darwin/darwin.html It's not fancy hmtml, but it's the best genetic simulation I've seen. The "swimmers" exist in 2d space, seek out food and mate. Only the best will reach the food fast enough, and there are colors which a given swimmer will prefer to mate with, and space separating different populations. It's very possible to get several distinct populations which behave in entirely different ways.
  • freehunter 13y ago
    I'm just fascinated with a program that isn't full screen, yet resizes my entire desktop down to 800x600 even still. Fancy HTML it is not.
  • Houshalter 13y ago
    Darwninbots is a pretty good alife simulator if you are interested http://wiki.darwinbots.com/w/Main_Page http://wiki.darwinbots.com/w/Main_Page
• Yourfags 13y ago
  honestly I started crying a little bit at how funny I found your description. funniest thing i've read on HN
  • Yourfags 13y ago
    seriously I got 2 downvotes for saying I thought HN wasn't very funny? what?? It's not like there arn't plenty of other silly comments in this thread, why am I the one being singled-out, I guess it's probable that a comment like that would only offend people who even have the ability to downvote, since it takes 500rep to do so, but what? it wasn't even that offensive...
    • Yourfags 13y ago
      alright, whatever I'll stop commenting
• jwilliams 13y ago
  You're supposing that there is "sex" - i.e. two genders - in this simulation. I can't see that though? I suspect - would be interested in anyone who's worked it out - that each individual is mutated between each generation. I tried 10 Elites with high rate of mutation. I'd have expected this to have more "breeding" from the Elites, but it doesn't. It tends to plateau. Occasionally an outlier jumps into the "10", but it's pretty flat. So.. Is there any concept of "fitness"? If so, it ends up being pretty random, since there is no penalty for a less adaptive mutation.
  • klodolph 13y ago
    Sex does not mean two genders, neither in the simulation nor in real life. It just means that offspring inherit genes from two (or more!) parents rather than one.
• IanCal 13y ago
  Yes it has, it's one of the core things you adjust in most real applications. It's a trade-off between exploration and exploitation. If you speciate then you have little sub-populations exploiting the local maxima, so they might do better. However, now you're not searching such a wide area so you're more likely to spend your time struggling to the top of the molehill that's next to the mountain. In nature this also happens. Not having crossovers between ludicrously different things is generally a good idea because the landscape is full of tiny maxima. If you change a load of base pairs in your DNA you're less likely to be able to do things like form cells or process glucose than you are to add some awesome new power (unless we're in comic books). One of the major differences for nature is that it can run all this jazz in parallel. If there are resources, it can happily have 10 trillion bacteria rather than 5 without any cost. When we're simulating, every fitness measurement on a piss-poor crossover is a waste that we should have spent on a more likely solution. It all depends on the fitness landscape, but both approaches can be better on different real world problems.
• danielbarla 13y ago
  You could introduce speciation by only allowing relatively similar genomes to successfully breed. My guess is that such an operator would be quite expensive, and its benefits would need to be weight against that. A typical work-around for scenarios like this would be to have the various parameters change as the simulation carries on; e.g. later on it might make more sense to increase the number of elites as a way of limiting crossover.