Hello friends,
after weeks of mind-battling, I have finally made up my mind to take a break from Competitive Programming. My plan is to pay a visit to other fields of Computer Science, to see if there are any other things interesting in life, and I have found the first stop in my journey... Genetic Algorithms.
The thing is, I have recently come across a problem, "input a number and output any equation that equals to it". Sound simple :v??? Indeed, but just after I read the code, I felt like "what the heck I am reading". The program is a few hundreds of lines in length, and the algorithm is exactly what I learnt in my high school biology lessons: create a 'population' of equations, encode them into binary 'genes', choose 'dad' and 'mom' genes in a way resembling 'natural selection', let them marry and produce children by crossover and mutation of their genes. Just like the way organisms evolved, isn't it? Why this "crazy" approach works is still mysterious to me.
Link to the problem and solution (code): http://www.ai-junkie.com/ga/intro/gat3.html
Now I feel really interested in such algorithms, and I want to learn more about them, but you know, it is really difficult because I cannot find any similar problems and even if I can, there is just no one around to evaluate my work. Therefore, I wonder if there is any online judge like Codeforces or Topcoder that has such problems. It would be very nice if someone can recommend some learning materials and some communities that focus on this field. At the moment I am following the book An Introduction to Genetic Algorithms by Mitchell, but when I am not clear about something, I cannot ask anyone :'( at all.
Thank you for your time and consideration. HAPPY CODING.
Here is one problem from UVA online judge. Also another problem from this year's SWERC. Happy coding :)
Yeah, "what the heck I am reading" is really one of things that is happening in CS+CP fields. Actually, my studies says that getting rid of one-to-one compliance with some strange interpretations of actual computations and ideas is quite meaningful (as much as caming up with some funny invariants like CP problem statements). Michelangelo seems to do the same. I even have a metaphoric interpretation of what this specific effect that you've mentioned comes to, I call it "Coal dust".
It's quite cold in Siberia so you need to burn some coal, but the problem is to keep your house clean inside, and another problem is that heating systems are built to keep it warm inside (not clean). Washing your hands, using latex gloves (even disposable) just won't help against the dust that left after breaking big coal pieces into small, washing out the ash, etc. The coal dust will be around wherever you go, whatever you do. My father said that it's simple to keep dust amount under small limit, but it's just impossible to get rid of it without spending time taking care of that as a big problem (it may appear that you need to build another house). I'm always have some other things to take care of, but the limit mentioned above is not "cleany" enough methinks, so it bothers me a lot and I'm sure I'll find an easy way to fix that surely non-physical-lore thing.
For example, my words about father really look like a star wars replica. BTW Rogue one is quite good I think.
In other words, you really should work on more or less fundamental books like one you've found. Mix them with scientific publications that you're interested in (for example, I saw an article saying about gray codes usage in genetic algorithms of youtube, that was interesting for me as I was amateur filmmaker in school). Create an interesting customizable visualization or anything else that fits your professional (or purely functional) and social interests better. Don't sit for hours while re-reading some hard part on page 20-40, try to understand what's next. One day you'll start successively mix words and phrases that is really don't have any connection from the first view, but sums to a critical meaning as a google requests or even eventually existing website domain names. That's the moment of non-misteriousity I think.
I think It's hard to find a problem solved by Genetic Algorithms in programming contests because Genetic algorithms usually used to find an approximate answer for the problem not the optimal answer.
For example : it can find an approximate answer for traveling salesman problem very fast, but can't find the optimal solution every time you run the program.