Algoritmos genéticos: uso de lógica nebulosa e análise de convergência por cadeia de Markov

In this work, the Markov chain will be the tool used in the modeling and analysis of convergence of the genetic algorithm, both the standard version as for the other versions that allows the genetic algorithm. In addition, we intend to compare the performance of the standard version with the fuzzy version, believing that this version gives the genetic algorithm a great ability to find a global optimum, own the global optimization algorithms. The choice of this algorithm is due to the fact that it has become, over the past thirty yares, one of the more importan tool used to find a solution of de optimization problem. This choice is due to its effectiveness in finding a good quality solution to the problem, considering that the knowledge of a good quality solution becomes acceptable given that there may not be another algorithm able to get the optimal solution for many of these problems. However, this algorithm can be set, taking into account, that it is not only dependent on how the problem is represented as but also some of the operators are defined, to the standard version of this, when the parameters are kept fixed, to their versions with variables parameters. Therefore to achieve good performance with the aforementioned algorithm is necessary that it has an adequate criterion in the choice of its parameters, especially the rate of mutation and crossover rate or even the size of the population. It is important to remember that those implementations in which parameters are kept fixed throughout the execution, the modeling algorithm by Markov chain results in a homogeneous chain and when it allows the variation of parameters during the execution, the Markov chain that models becomes be non - homogeneous. Therefore, in an attempt to improve the algorithm performance, few studies have tried to make the setting of the parameters through strategies that capture the intrinsic characteristics of the problem. These characteristics are extracted from the present state of execution, in order to identify and preserve a pattern related to a solution of good quality and at the same time that standard discarding of low quality. Strategies for feature extraction can either use precise techniques as fuzzy techniques, in the latter case being made through a fuzzy controller. A Markov chain is used for modeling and convergence analysis of the algorithm, both in its standard version as for the other. In order to evaluate the performance of a non-homogeneous algorithm tests will be applied to compare the standard fuzzy algorithm with the genetic algorithm, and the rate of change adjusted by a fuzzy controller. To do so, pick up optimization problems whose number of solutions varies exponentially with the number of variables

Neste trabalho, a cadeia de Markov será a ferramenta usada na modelagem e na análise de convergência do algoritmo genético, tanto para sua versão padrão quanto para as demais versões que o algoritmo genético permite. Além disso, pretende-se comparar o desempenho da versão padrão com a versão nebulosa, por acreditar que esta versão dá ao algoritmo genético uma grande capacidade para encontrar um ótimo global, próprio dos algoritmos de otimização global. A escolha deste algoritmo deve-se também ao fato do mesmo ter se tornado, nos últimos anos, uma das ferramentas mais usadas para achar uma solução do problema de otimização. Esta escolha deve-se à sua comprovada eficácia na busca de uma solução de boa qualidade para o problema, considerando que o conhecimento de uma solução de boa qualidade torna-se aceitável tendo em vista que pode não existir um outro algorimo capaz de obter a solução ótima, para muitos desses problemas. Entretanto, esse algoritmo pode ser definido, levando em conta que o mesmo é dependente não apenas da forma como o problema é representado, mas também como são definidos alguns dos operadores, desde sua versão padrão, quando os parâmetros são mantidos fixos, até suas versões com parâmetros variáveis. Por isso, para se alcançar um bom desempenho com o aludido algoritmo é necessário que o mesmo tenha um adequado critério na escolha de seus parâmetros, principalmente da taxa de mutação e da taxa de cruzamento ou, até mesmo, do tamanho da população. É importante lembrar que as implementações em que parâmetros são mantidos fixos durante toda a execução, a modelagem do algoritmo por cadeia de Markov resulta numa cadeia homogênea, e quando permite a variação de parâmetros ao longo da execução, a cadeia de Markov que o modela passa a ser do tipo não-homogênea. Portanto, na tentativa de melhorar o desempenho do algoritmo, alguns trabalhos têm procurado realizar o ajuste dos parâmetros através de estratégias que captem características intrínsecas ao problema. Essas características são extraídas do estado presente de execução, com o fim de identificar e preservar algum padrão relacionado a uma solução de boa qualidade e, ao mesmo tempo, descartando aquele padrão de baixa qualidade. As estratégias de extração das características tanto podem usar técnicas precisas quanto técnicas nebulosas, sendo neste último caso feita através de um controlador nebuloso. Com o fim de avaliar empiriccamente o desempenho de um algoritmo não-homogêneo, apresenta-se testes onde se compara o algoritmo genético padrão com o algoritmo genético nebuloso, sendo a taxa de mutação ajustada por um controlador nebuloso. Para isso, escolhe-se problemas de otimização cujo número de soluções varia exponencialmente com o número de variáveis