GEP Book   Home   News   Author   Q&A   Tutorials   Downloads   GEP Biblio   Contacts   Visit Gepsoft

C. FERREIRA In J. M. Santos and A. Zapico, eds., Proceedings of the Argentine Symposium on Artificial Intelligence, pages 160-174, Santa Fe, Argentina, 2002. Combinatorial Optimization by Gene Expression Programming: Inversion Revisited Conclusions   In this work, a new chromosomal organization consisting of multigene families was described. Multigene families contain members of a particular class of terminals and are, therefore, very useful for solving scheduling problems. Furthermore, special combinatorial search operators were created so that both the chromosomal organization and the composition of multigene families could be fully exploited to solve combinatorial problems. Indeed, all the genetic modifications made by these combinatorial-specific operators always result in valid chromosomes, i.e., chromosomes in which both the structure of multigene families and the balance of its members are maintained. This is obviously a prerequisite for a good genetic operator. However, this is no guarantee that this kind of operator will be highly effective and, in fact, some perform better than others. The results presented here show that inversion astoundingly surpasses other combinatorial-specific operators such as the moderately performing gene deletion/insertion and restricted permutation, and the poorly performing sequence deletion/insertion and generalized permutation. And, no doubt, surpasses all the modified forms of crossover especially tailored to deal with combinatorial problems. In addition, it was also shown that solutions to scheduling problems are better found if the search is exclusively done by inversion. Indeed, mixing inversion with other operators, albeit combinatorial-specific, results in a decrease in performance. The performance of inversion was further evaluated on two scheduling problems: the difficult TSP with 19 cities that required only one multigene family and the task assignment problem that required two multigene families. In both cases, the new algorithm performed with high efficiency, solving, with less resources and with almost maximum success rate (96%), a problem the GA could not solve (TSP with 19 cities). Home | Contents | Previous | Next