Um algoritmo auxiliar paralelo inspirado na fertilização in vitro para melhorar o desempenho dos algoritmos genéticos

Abstract

There are several techniques applied to optimization problems. However, few achieve satisfactory performance when the problem is complex, for example multi-modal or multi- objective. The metaheuristics, examples of optimization techniques, are heuristic algo- rithms that can not guarantee the global optimum, but usually ¯nd good solutions. There are several metaheuristics, as an example: Simulated Anneling, Tabu Search, GRASP, VND, VNS and Ant Colony. Among the metaheuristics, the algorithms of Evolu- tionary Computation is one of the most used, since the e®ectiveness and modular/adaptive features. Evolution strategy, Genetic programming and Evolutionary programming are examples of evolutionary algorithms, however, the pioneer and the most popular in the literature is the Genetic Algorithm, despite the di±culties of convergence in some cases. Genetic Algorithms (GA) are optimization and search methods inspired by the evolu- tion of living beings population. Algorithms, based on this technique, follow the principle of natural selection and survival of the fittest (Charles Darwin). When we analyze the GA, where several generations are produced, one on each itera- tion, and considering that each new generation the old one is partially or totally discarded, the GA may be removing relevant information within individuals discarded, which were not transmitted or evaluated by the algorithm. Therefore, and considering the few studies that address the improvement in the use of the information, and the need to present evolutionary solutions with wider applicability, this paper proposes the Algoritmo Auxiliar Paralelo (AAP), which aims to assist the GA with good individuals from better treatment of the structures present in parents populations. The AAP is an auxiliary module running on a parallel °ow to the GA and that recombine chromosomes to maximize the use of the information present in individuals. As a result, the module can generate artificial fittest individuals, which are inserted in the new generation and manipulated by the GA in the next iteration. Inspired by In Vitro Fertilization and the Preimplantation Genetic Diagnosis, which reviews and selects good pre-embryos to be transferred to the mother, the AAP following a °ow of Collection, Manipulate, Select and Transfer of good individuals. To test the performance of the proposed algorithm (AAP), and their operators, when linked to the GA, we chose two benchmark problems. The ¯rst, Rastrigin function by ha- ving a large search space, non-linear and have a high degree of multimodality. The second, the Multidimensional Knapsack Problem, as a multidimensional and highly combinatorial problem. Therefore, it was possible to measure the performance of the proposal in two dif- ferent types of problem: non-restrictive multimodal function and restrictive combinatorial optimization. The AAP has been tested and compared with the canonical GA, identifying the performance of the proposal, and with a hybrid algorithm GA-TS (Tabu Search), which has characteristics of global and local search. We constructed 39 sets of the addressed problems for the tests. The results show the AAP as a good tool to assist the GA to improve the convergence performance. It is noticed also that there was a considerable improvement in the speed of convergence without a®ecting the quality of the ¯nal solution. Given the results and the modular structure of AAP, allowing other changes and new operators, we believed that the AAP may be useful in various applications and applicable to other populations heuristics.