Add your own alternative version
Stats
46.3K views 1.3K downloads 85 bookmarked
Posted
14 Jun 2015

Comments and Discussions


Arthur,
None of the below is to take away from the article, which I continue to study with interest.
The English of your article may be good for people already familiar with the evolutionary algorithms, but for those of us from curious bunch, who are trying to learn something new from this topic, the article's English is horrible. It is hard to get details right, specifically in Background section, when linguistic details are ... stepped upon, resulting in semantic minefield. I think you may be using automatic translation software with resulting quality of English text such, that one needs evolutionary algorithm to understand your description of, well, evolutionary algorithm (aka "the following algorithm discussed"). In short, I have hard time following you as a creator . I don't believe that my difficulty stems from the underlying math, which isn't hard, or from lack of programming experience.
Can you, please, rework the English translation as a creative author you are, perhaps starting with the Background section?
Respectfully
modified 16Jul15 0:13am.





Yes, indeed, this article material is *NOT* intended for enterpreneurs or entry level programmers. Evolutionary (EA) and Genetic algorithms (GA) is a very serious long field of either computer science or the other sciences. It has a very rich theory, and it tried to compact the theory in the article as much as it possible. Unfortunately, English is not my native language and I composed my article at my very best efforts in English. As well, I cannot rewrite this article at the present time. The article was written not using any translators, that's all done by my own.
I'm sorry. Thanks a lot.





I am not an entrepreneur, nor an entry level programmer. Without trumping up my credentials, it will suffice to say that I work in the technology startup for the last 6+ years, write software for leaving since college days and like to study computer algorithms for fun of it.
I've read many articles in this site and can tell you that the background section in your article wasn't written with an effort to be understood by software engineers of any level, who are not familiar with the field of EA. Indeed.
Having code helps, but the article doesn't do justice to it.
Again, I do not diminish your work  just comment on poor presentation.





I've got you very well, but this is poor presentation because of my English. I'm very sorry. Thanks.





No worries. Hopefully I will get over these hurdles and will be able to understand the article properly.





O'key, I've got an idea to help you. Just give me your question if you're not understanding at a certain point.





It may help if you point me to Russian version. I assume you wrote original version in Russian (which is my native language).





For the answer, read my last post.





Just give me your questions. I anyway will give my reply.
It will be just amazing, if you point me at what is actually misleading in my article by placing the quotation in your next posts.





First, I've got a question: what timezone are you located in ? I'm raising up the question, because at the nighttime I'll not be able to reply your posts quick. And if you're located in ET timezone like in US or Canada, please learn some patients to wait for my reply posts. Sorry.
Second, Now I can't give you the Russian translation of the article, because I had been writing it in English. Just, first read this article. This is the russian translation of the Rick Riolo "Survival of the fittest bits". Perhaps, this article should point you at, because the main ideas of the article of mine had been brought from this particular article.
Thanks a lot.





I am in ET timezone.
Thank you for the the article! It is handy as original isn't available for free download.
Patience? I never complained, nor expressed my impatience for delays in any form. Let me just say that to say that one needs *to learn* 'some patience' is rather strong. That is in English. No worries  I take it to mean that English isn't your cup of tea





O'key you're free to give me any questions about the article.





The description of your algorithm reminds me more of a modified bubble sort than a genetic algorithm: it entirely lacks the random factor, and therefore is a deterministic algorithm. Can't say for sure if being deterministic automatically disqualifies the algorithm as genetic algorithm, but it sure looks odd to me. You do explain crossover and mutation, but if you applied either, I didn't spot it. Did you?
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)





Stefan_Lang wrote: The description of your algorithm reminds me more of a modified bubble sort than a genetic algorithm...
Answer: The genetic algorithm discussed in this article is not a "bubble sort", because it actually does *NOT* perform any sorting, instead it performs metaheuristic searching of the most fittest the linear approximation problem's solutions.
Stefan_Lang wrote: it entirely lacks the random factor, and therefore is a deterministic algorithm. Can't say for sure if being deterministic automatically disqualifies the algorithm as genetic algorithm, but it sure looks odd to me...
Answer: It does lacks the either random selection or fitness factors, but it's not the deterministic. The main difference between is that the *GENETIC* algorithm described guarantees of finding the population of most fittest chromosomes (e.g. solutions of the linear approximation problem) for the *FINITE* number of chromosome generations (epochs), while the other methods are quite stochastic and perform chromosome selection, crossover and mutation ethernally, during the infinite number of epochs, which causes the efficiency degrade of the genetic algoritm you have recalled.
Conclusion: Instead of performing either tournament or proportionate selection the algorithm described in my article provides the binary distribution selection, in which we actually perform selection based on the "phenome" fitness for each particular chromosome in the population. The "phenome" fitness is *NOT* evaluated as the fitness function value. Instead, we're performing the heuristic search or the search by partitial match in the population of chromosomes to find those individual chromosomes, whose "phenome" is the most or the least relevant to be the phenome of the sample chromosome that represents the parameter value of x for the linear approximation problem. In the other words, the chromosome which represents the value of x and the most likely fittest chromosomes obtained during selection, should belong to the same population. And then, we select among those values that the most closely to be the "nearest" neighbor values of x, based on their "phenome" value.
P.S. You know, I'm very sorry, but it's too long topic to fit in the single forum's post. You'd better refer to the guidelines listed at the bottom of this article such as [2,3], or if you wish I can provide the more detailed answers for your questions raised later on, because at now, I have a short of time writing the long posts. Just in a day or two, I will post the additional reply to your message. I'm promising that I'll publish the detailed explanation of the genetic algoritm described, in the next revisions of the following article. Thanks a lot.





I beg to disagree:
 you do definitely sort your chromosomes into good and bad candidates, and that's very similar to what many sort algorithms do
 Read up the definition of deterministic. Your algorithm is.
 You can't actually guarantee finding the fittest member(s) of a population in any GA, no matter whether you restrict the number of generations or not. It is not even possible to prove this in a general case! A bad choice of genetic operators can always get you stuck in a local minimum.
Either this is a GA with the consequence that you cannot guarantee to find the best solution, or you can guarantee it because it is not a GA. Pick your choice.  There are two positive properties of GAs: (a) being guranteed to converge under very trivial conditions, and (b) being able to get out of local minima and thereby increase the chance of finding the global best, depending on the quality of your operators and chromosome encoding. These properties can only be achieved on the basis of random genetic operators. Without randomness, you won't get these properties, and you suffer from the same limitations as every other classical algorithm.
As for your references, [2] is behind a paywall and [3] describes random genetic operators. Why do you think that is a basis for the argument your algorithm is a GA without randomness, and without operators?
Conclusion:
You've used GA terminology and converted a problem into a form that a GA could work on, but then implemented a classical algorithm on top of that. This does not make it a GA, nor does it invoke GA properties. The algorithm may work, and it may even be efficient, but without random operators there's no gurantee it will even converge  you'd need to prove that manually (although I suspect that won't be hard).
At the very least, your references to GAs are misleading, and the needless complication of the original problem by introducing a "chromosome" encoding and organizing "populations" rather than using the typical terminology of classical algorithms are needlessly complicating things and potentially confusing readers.
I suggest to remove the references to GAs, rename your chromosomes and phenomes into something more 'classical', and then I'd be willing to offer a good vote (haven't voted yet)  the algorithm as such is quite interesting, and you've put in a lot of work  that is worth something!
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)





O'KEY, I will follow your recomendations and will revise the theory background of the following algorithm, *BUT*, could you spend a little bit more time to my further explaination, I've not posted yet in my previous message. I'm going to post them shortly, as soon as I can. I absolutely agree with you that this algorithm borrows some properties of the GA classical algorithms, but it is not the GA as such.
And my final question is: I need some more time to revise the theory discussed in this article and update it. Do you actually want to wait for a little bit more, to give me the chance of having all this work done, before you will vote?
Thanks for your post. I'll be waiting for your further posts with reply to my question above.
P.S.I beleive that I'll make all those changes during a week or two, or probably faster.





Thank you very much for your understanding. I do appreciate this very much!
I am looking forward to your next revision
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)





Stefan_Lang wrote: you do definitely sort your chromosomes into good and bad candidates, and that's very similar to what many sort algorithms do
I don't actually "sort" the chromosomes populations, but perform the "selective" linear search.
Stefan_Lang wrote: Read up the definition of deterministic. Your algorithm is.
Every AI genetic algorithm, in general programming, consists of the multiple search methods, some of which could be really "deterministic", like the binary distributive selection phase.
Stefan_Lang wrote: You can't actually guarantee finding the fittest member(s) of a population in any GA, no matter whether you restrict the number of generations or not. It is not even possible to prove this in a general case! A bad choice of genetic operators can always get you stuck in a local minimum.
Either this is a GA with the consequence that you cannot guarantee to find the best solution, or you can guarantee it because it is not a GA. Pick your choice.
An AI genetic algorithm should guarantee the finding of a problem's solutions, it's the main point of the AI genetic algorithm implementation.
Stefan_Lang wrote: There are two positive properties of GAs: (a) being guranteed to converge under very trivial conditions, and (b) being able to get out of local minima and thereby increase the chance of finding the global best, depending on the quality of your operators and chromosome encoding. These properties can only be achieved on the basis of random genetic operators. Without randomness, you won't get these properties, and you suffer from the same limitations as every other classical algorithm.
For the exact explanation, refer to the following guidelines: Genetic Algorithms
Thanks a lot for reading this post.





Arthur V. Ratz wrote: Every AI genetic algorithm, in general programming, consists of the multiple search methods, some of which could be really "deterministic", like the binary distributive selection phase.
Did you follow the link I provided? Your entire program is deterministic. Anyway, I explained in the other branch of that discussion why you do need random elements, and where.
Arthur V. Ratz wrote: An AI genetic algorithm should guarantee the finding of a problem's solutions, it's the main point of the AI genetic algorithm implementation.
As explained in the other branch, a guarantee can be provided only as long as you do provide operators that guarantee the exploration of the entire solution space.
Of course, in the context of a problem definition that includes all possible solution condidates into the initial population, there is no point applying a GA because it should immediately stop. For that reason it doesn't matter what operators you have or not  there is no GA at work.
Arthur V. Ratz wrote: For the exact explanation, refer to the following guidelines: Genetic Algorithms
I followed the link. It offers a very comprehensible overview of GAs. It also points out the things I've already told you, although sometimes only by implication: check out what it says about search space and genetic operators.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)





Thanks. I'll keep it in mind. I've already replied your post.





P.S.: please don't take my arguments personally  I am leading this discussion solely for the purpose of eliminating inproper use of GA terminology. My reason for that is the big AI bubble that burst in the 80s, caused by an incredible amount of articles posted by people who didn't really understand the terminology of the varying AI methods to start with, nor how to pick a problem that a given AI method is even suitable for. People new to the field may be misled by such articles and themselves fail to understand what the AI method in question really is, and what it is good for.
I've learned about GA's and ANNs at university 30 years ago, programmed a lot myself, visited AI conferences, and was in contact with groups from other universities. At my first job, I even imlpemented ANNs and GAs for practical purposes. Sadly, I haven't really worked with AI the past 20 years, because, privately, after the AI bubble burst I lost interest, and in my job, likewise no one was interested in AI methods anymore.
Now, with more powerful computers and much wider choice of algorithms, AI is coming back, but I also see tons of pseudoAI articles sprouting. I don't want AI to die once again because of unfortunately labeled articles swamping the actually good ones, and that is why I'm here, discussing with you.
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)





I'm understanding what you mean. Thanks for your guidelines. When I will revise my article I'll let you know with the new post inside this forum's topic (!).
But I've got a question for you. Revising theory and changing it from AI genetic to binary operations description, can I refer to a bit of theory left from the AI genetic programming? I actually need your advise for.
Thanks a lot.





Well, you could refer to evolutionary algorithms instead: https://en.wikipedia.org/wiki/Evolutionary_algorithm[^]. Unlike GAs, they put less stress on random factors, just on the general idea of populations, and new generations inheriting properties from older generations. That should fit your algorithm much better than GA.
P.S.: I've just read up on the even more general category Evolutionary Coputation ( https://en.wikipedia.org/wiki/Evolutionary_computation[^] ) , and found that it does in fact emphasize random search. So, technically, your algorithm is not evolutionary, although it uses the ideas of populations of potential solutions in the spirit of global opimization techniques: https://en.wikipedia.org/wiki/Global_optimization[^]
GOTOs are a bit like wire coat hangers: they tend to breed in the darkness, such that where there once were few, eventually there are many, and the program's architecture collapses beneath them. (Fran Poretto)





Stefan_Lang wrote: Well, you could refer to evolutionary algorithms instead: https://en.wikipedia.org/wiki/Evolutionary_algorithm[^]. Unlike GAs, they put less stress on random factors, just on the general idea of populations, and new generations inheriting properties from older generations. That should fit your algorithm much better than GA.
Great idea. Thanks a lot, Stefan.





I've carefully read all your posts and before revising the article composed, I have a couple of comments to the either GA and EA programming and the evolutional process mimics and the algoritm implementation described in my article:
Stefan_Lang wrote: P.S.: I've just read up on the even more general category Evolutionary Coputation ( https://en.wikipedia.org/wiki/Evolutionary_computation[^] ) , and found that it does in fact emphasize random search. So, technically, your algorithm is not evolutionary, although it uses the ideas of populations of potential solutions in the spirit of global opimization techniques: https://en.wikipedia.org/wiki/Global_optimization[^]
But my question is WHY SHOULD IT BE ACTUALLY RANDOM (?). Suppose we're implementing the tournament selection algorithm in which, at each selection phase, we select the two or more chromosomes from a population randomly and then performing the recombination to breed the new population. In this case, obviously the selection process is random (stochastic) and is mainly based on a certain probability. The final result of finding the most fittest chromosomes that represent the various solutions of a certain optimization problem is initially unpredictable. You never know what particular population, in which generation, will contain the most fittest solutions of a problem. That's why the random selection process is endless.
But there're also the other selection methods that are *NOT* using the randomization factor, such as truncation selection or the binary distribution selection method I've proposed and discussed in my article. The main benefit of this method is that it allows to find the most fittest solutions of the calculus approximation problem for a finite number of epochs, which will *NOT* be performed endlessly. Please refer to the following guidelines Genetic Algorithms
Please note, that if the implementation of the binary distribution selection method guarantees that we'll find the population of the most fittest chromosomes for a descrete number of generations (epochs), that does not actually mean that this particular number of epochs is initially known or defined. We simply assume that the evolutional process simulation will proceed during a certain finite number of epochs which value is also unknown, but, definitely, is not exceeding the initially calculated number of epochs. Typically, the actual number of epochs, during which we're able to find the most fittest chromosomes, is much less than the maximum number of epochs. The maximum number of epochs calculated at the initialization phase of the algorithm is typically different for each initial set of the possible problem's solutions represented as the initial "parent" population of chromosomes.
2. During binary distribution selection, described in this article we actually don't perform either crossing over or mutation. At each epoch we're breeding the two "child" populations of either the most or the least fittest chromosomes respectively. We don't eliminate the least fittest chromosomes from a population because the chromosomes in the least fittest population also contain the most fittest particular genes inherited from the chromosomes in the "parent" population that existed in the previous epoch and vise versa. The binary distribution selection is like the natural cells division in biology.
3. We also don't use the fitness function calculation, instead we're determining the fitness of each particular chromosome using the properties of the integer values in binary representation. In binary distribution selection method,we actually are performing the distribution (division)of either least or most fittest chromosomes, which allows to "narrow" the potential size of the initial population by splitting it into the descrete subsets of chromosomes, and after that, determine in which particular population the most fittest chromosomes could be found. This method is also called quantization and is described in "Ming Shao, Liang Zhou. A summary of the Study on Quantum Evolutionary Algorithm. Shanghai Univerisity of Engineering Science, school of management, 333 Longteng Road, Shanghai, 201600, China.".
4. We don't perform crossing over and mutation, because we initially already have the "root" population that consists of the most fittable chromosomes by hypothesis. Our goal is just to find the variety of the most fittest chromosomes in population starting at the root parent population by determining the fitness of each particular chromosome distributed. Before publishing my article I've wrote a C++ program that simulates the process of tournament selection performing crossing over and mutation. Finally, we've got the chromosome population which is identical to the initially population, provided at the initialization phase. That's why I've made the conclusion that the use of the tournament selection for solving the problem of finding the "nearst" neighbors of the value of x specified is *NOT* efficient.
That's all. I would ask you to read my explanation and post your comment.
If you don't agree with my arguments, please provide the reason why you're not.
Finally, I can follow your recomendation and revise the genetic theory provided in this article into binary computations.
Waiting for your reply.
modified 2Jul15 14:43pm.






General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

 Best C++ Article of June 2015 (First Prize)
