In genetic science, it is well known that a specific genetic behavior is influenced by one or several other genes. There is a similar subject in Genetic Algorithm (GA), called Epistasis, which is in fact the interaction between genes. In the attached paper (which is under review), it has been claimed that in spite of what is generally supposed, GA is not an efficient optimization tool; because, its main operator, mating (crossover), cannot operate properly in Epistatic problems. On the other hand, in non-Epistatic problems, although GA can possibly lead to a correct answer, it will be an inefficient and time-consuming algorithm. In that paper, to evaluate the efficiency of optimization algorithms, several Epistatic and non-Epistatic commonly used benchmark examples were investigated. Moreover, some new test functions are also introduced for efficiency evaluation of GA which have the capability of being analyzed in both Epistatic and non-Epistatic conditions. As it is claimed, simulation results show that GA does not perform efficiently in Epistatic problems and non-Epistatic problems can be solved by less complex algorithms.
I think that, without restricting the algorithm scope, it is not possible to state optimization criteria. To illustrate this fact, consider the problem of constructing an object satisfying a given property set P. Even the smartest man cannot find out any solution, if the set of properties is complex enough. This is why this kind of algorithms are termed heuristic.
However, by restricting the set properties P it is possible, for instance, to define an ordering ≤, such that O1 ≤ O2 if and only if O2 fits better than O1 to the required property set. In this case, a maximal element is the best solution; however perhaps it does not satisfy every property in P. Analogously, under some constraints, a map F can be defined such that, for every object O, the relation O ≤ F(O) holds. In this case the optimal solution is a fixed point for F and the problem can be reduced to find fixed points. Notice that ordered sets are fixed points for any sorting algorithm.
Dear Sajad,
Thanks for sharing your question and your paper. The difficulty you describe has been studied by several authors since early 1990's. See, in particular the following important work by Y. Davidor (1991).
Epistasis Variance: A Viewpoint on GA-hardness.
In: Fondations of GA 1, ed. G.J.E. Rawlins, M. Kaufmann Publishers, (San Mateo).
If you work on GA hardness, you might be interested also by the so-called "Royal Road Functions" for testing GA performance. See, for example:
Melanie Mitchell, Stephanie Forrest and John H. Holland (1991)
http://www.sci.brooklyn.cuny.edu/~sklar/teaching/f05/alife/papers/mitchell-91royal.pdf
Two other very interesting papers on epistasis are :
Colin R. Reeves and Christine C. Wright (1995)
Epistasis in Genetic Algorithms : An Experimental Design Perspective
Proc. of the 6th Int. Conf. on GA (pp 217-224)
M.T. Iglesias, C.Vidal and A.Verschoren (2005)
Computing Epistasis of Template Functions Through Walsh Transforms.
Computing and Informatics, Vol.24, (pp. 263-279)..
Hope this helps.
In my opinion, you should say efficient instead of effective. Effective (effectiveness) is a term used by economists. In computer science, it is common to express an algorithm as efficient.
For example, you can refer to this book:
Types and Programming Languages by Benjamin C. Pierce, page. 8.
Kind regards,
Pawel.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Artificial Intelligence