Neste trabalho foi realizada uma busca por relações, regras e transformações entre duas metodologias constituintes da Inteligência Computacional - a Computação Nebulosa e a Computação Evolutiva. Com a organização e sistematização da existência de tais transformações, obtém-se uma mudança na modelagem de soluções que as utilizam de forma conjunta, possibilitando que teorias e modelos bem estabelecidos em uma das metodologias possam ser aproveitados pela outra de uma forma mais robusta, correta por construção, intrínseca e transparente. Um modelo foi proposto para direcionar o trabalho de pesquisa. Através da análise desse modelo e de uma revisão bibliográfica realizada, transformações pontuais entre as metodologias foram elencadas, e posteriormente consolidadas por meio de experimentos práticos: uma Base de Conhecimento (BC) de um Controlador Lógico Nebuloso foi criada e modificada, conforme a necessidade, através de um Algoritmo Genético (AG). Com a abordagem desenvolvida, além da criação de BCs a partir de pouquíssimo conhecimento sobre o domínio do problema, tornou-se possível a inserção de novos \"comportamentos desejados\" em BCs já existentes, automaticamente, através de AGs. Os resultados desses experimentos, realizados sobre uma plataforma computacional especificada e implementada para este fim, foram apresentados e analisados. / This work addressed a search of relations, rules and transformations between two Computational Intelligence constituent methodologies - Fuzzy Computing and Evolutionary Computing. The existence of these relations changes the actual way of solutions modeling that uses these methodologies, allowing the utilization of well established theories and models of one technique by the other in a more robust, intrinsic and transparent way. Besides the research and systematization of points that indicate the existence of relations between the two methodologies, a model to guide these exploration was proposed. By this model analysis and by the bibliographic revision made, punctual transformations were pointed out, and further consolidated through practical experiments: a Knowledge Base (KB) of a Fuzzy Logic Controller was created and modified automatically by a Genetic Algorithm. With the developed approach, besides the creation of KBs, it became possible to automatically insert new \"desired behaviors\" to existent KBs. The results of such experiments, realized through a computational platform specified and implemented to this task, were presented and analyzed.

Neste trabalho foi realizada uma proposta de utilização de Sistemas de Inferência Nebulosos para controlar, em tempo de execução, parâmetros de Algoritmos Genéticos. Esta utilização busca melhorar o desempenho de Algoritmos Genéticos diminuindo, ao mesmo tempo: a média de iterações necessárias para que um Algoritmo Genético encontre o valor ótimo global procurado; bem como diminuindo o número de execuções do mesmo que não são capazes de encontrar o valor ótimo global procurado, nem mesmo para quantidades elevadas de iterações. Para isso, foram analisados os resultados de diversos experimentos com Algoritmos Genéticos, resolvendo instâncias dos problemas de Minimização de Funções e do Caixeiro Viajante, sob diferentes configurações de parâmetros. Com base nos resultados obtidos a partir destes experimentos, foi proposto um modelo com a troca de valores de parâmetros de Algoritmos Genéticos, em tempo de execução, pela utilização de Sistemas de Inferência Nebulosos, de forma a melhorar o desempenho do sistema, minimizando ambas as medidas citadas anteriormente. / This work addressed a proposal of the application of Fuzzy Systems to adjust parameters of Genetic Algorithms, during execution time. This application attempts to improve the performance of Genetic Algorithms by diminishing, at the same time: the average number of necessary generations for a Genetic Algorithm to find the desired global optimum value, as well as diminishing the number of executions of a Genetic Algorithm that are not capable of finding the desired global optimum value even for high numbers of generations. For that purpose, the results of many experiments with Genetic Algorithms were analyzed; addressing instances of the Function Minimization and the Travelling Salesman problems, under different parameter configurations. With the results obtained from these experiments, a model was proposed, for the exchange of parameter values of Genetic Algorithms, in execution time, by using Fuzzy Systems, in order to improve the performance of the system, minimizing both of the measures previously cited.

A qualidade das hipóteses induzidas pelos atuais sistemas de aprendizado de máquina supervisionado depende da quantidade dos exemplos no conjunto de treinamento. Por outro lado, muitos dos sistemas de aprendizado de máquina conhecidos não estão preparados para trabalhar com uma grande quantidade de exemplos. Grandes conjuntos de dados são típicos em mineração de dados. Uma maneira para resolver este problema consiste em construir ensembles de classificadores. Um ensemble é um conjunto de classificadores cujas decisões são combinadas de alguma maneira para classificar um novo caso. Apesar de melhorar o poder de predição dos algoritmos de aprendizado, ensembles podem ser compostos por muitos classificadores, o que pode ser indesejável. Ainda, apesar de ensembles classificarem novos exemplos melhor que cada classificador individual, eles se comportam como caixas pretas, no sentido de não oferecer ao usuário alguma explicação relacionada à classificação por eles fornecida. Assim, neste trabalho propomos uma abordagem que utiliza algoritmos de aprendizado simbólico para construir ensembles de classificadores simbólicos que explicam suas decisões de classificação e são tão ou mais precisos que o mais preciso dos seus classificadores individuais. Além disso, considerando que algoritmos de aprendizado simbólico utilizam métodos de busca local para induzir classificadores quanto que algoritmos genéticos utilizam métodos de busca global, propomos uma segunda abordagem para aprender conceitos simbólicos de grandes bases de dados utilizando algoritmos genéticos para evoluir classificadores simbólicos em um u´ nico classificador simbólico, de maneira que o classificador evoluído é mais preciso que os classificadores iniciais. Ambas propostas foram implementadas em dois sistemas computacionais. Diversos experimentos usando diferentes conjuntos de dados foram conduzidos para avaliar ambas as propostas. Ainda que os resultados experimenta das duas soluções propostas são promissores, os melhores resultados foram obtidos utilizando a abordagem relacionada a algoritmos genéticos / The quality of hypotheses induced by most of the available supervised machine learning algorithms depends on the quantity and quality of the instances in the training set. However, several well known learning algorithms are not able to manipulate many instances making it difficult to induce good classifiers from large databases, as are needed in the Data Mining process. One approach to overcome this problem is to construct ensembles of classifiers. An ensemble is a set of classifiers whose decisions are combined in some way to classify new cases (instances). However, although ensembles improve learning algorithms power prediction, ensembles may use an undesired large set of classifiers. Furthermore, despite classifying new cases better than each individual classifier, ensembles are generally a sort of ?black-box? classifier, not being able to explain their classification decisions. To this end, in this work we propose an approach that uses symbolic learning algorithms to construct ensembles of symbolic classifiers that can explain their classification decisions so that the ensemble is as accurate as or more accurate than the individual classifiers. Furthermore, considering that symbolic learning algorithms use local search methods to induce classifiers while genetic algorithms use global search methods, we propose a second approach to learn symbolic concepts from large databases using genetic algorithms to evolve symbolic classifiers into only one symbolic classifier so that the evolved classifier is more accurate than the initial ones. Both proposals were implemented in two computational systems. Several experiments using different databases were conducted in order to evaluate both proposals. Results show that although both proposals are promising, the approach using genetic algorithms produces better results.

Submitted by Maria Cristina (library@lncc.br) on 2015-09-25T19:05:07Z No. of bitstreams: 1 thesis.pdf: 3598969 bytes, checksum: 03cf8e5a078613d707c68e89e449d6d3 (MD5) / Approved for entry into archive by Maria Cristina (library@lncc.br) on 2015-09-25T19:05:20Z (GMT) No. of bitstreams: 1 thesis.pdf: 3598969 bytes, checksum: 03cf8e5a078613d707c68e89e449d6d3 (MD5) / Made available in DSpace on 2015-09-25T19:05:31Z (GMT). No. of bitstreams: 1 thesis.pdf: 3598969 bytes, checksum: 03cf8e5a078613d707c68e89e449d6d3 (MD5) Previous issue date: 2015-05-27 / Conselho Nacional de Desenvolvimento Cientifico e Tecnológico / In this thesis, the evolutionary computation algorithm known as Genetic Programming has been explored as an alternative tool for improving the ensemble forecast of rainfall amount. The efficiency of Genetic Programming to deal with the problem of ensemble forecast of rainfall amount was confirmed on three artificial experiments. The work continued with the application of the evolutionary algorithms on some real-world data sets over south, southeast and central parts of Brazil during the period from October to February of 2008 to 2013. According to the results, Genetic Programming obtained a higher performance relative to two traditional statistical methods, reaching mean errors 27-49% lower than simple mean and the MASTER Super Model Ensemble System. In addition, the results revealed that the evolutionary algorithms outperformed the best individual forecasts, achieving an improvement of 30%. On the other hand, the evolutionary algorithms had a performance similar to the Bayesian Model Averaging technique, but the former are methods far more versatile. In general, the real and artificial experiments showed the potential of Genetic Programming and suggest that further research on the improvement of the technique is needed. / Na presente tese de doutorado, o algoritmo da computação evolutiva conhecido por Programação Genética foi explorado como ferramenta alternativa para o aperfeiçoamento da previsão quantitativa de chuva por conjunto. A aplicabilidade da Programação Genética no problema de previsão quantitativa de chuva por conjunto foi confirmada em três experimentos controlados. O trabalho seguiu com a aplicação dos algoritmos evolutivos sobre algumas bases de dados reais referentes a localidades situadas no sul, sudeste e parte do centro-oeste do Brasil durante o período de outubro a fevereiro de 2008-2013. Os resultados evidenciaram a superioridade da Programação Genética frente aos métodos estatísticos tradicionais: média simples e MASTER Super Model Ensemble System, com erros médios da ordem de 27-49% menores. Ademais, a previsão por conjunto via algoritmos evolutivos ofereceu previsões consideravelmente mais acuradas que as melhores previsões obtidas individualmente, chegando a uma melhora de 30%. Por outro lado, os algoritmos evolutivos apresentaram desempenho equivalente à técnica Bayesian Model Averaging, mas os primeiros são métodos bem mais versáteis. De maneira geral, os experimentos baseados em dados reais e artificiais revelaram a potencialidade da Programação Genética, e encorajam o seu aprimoramento para o problema de previsão quantitativa de chuva por conjunto.

Este trabalho realiza uma análise dos modelos pertencentes à Computação Neural e à Computação Evolutiva visando identificar semelhanças entre as áreas e sustentar mapeamentos entre as semelhanças identificadas. Neste contexto, a identificação de similaridades visando à resolução de problemas de otimização combinatorial resulta em uma comparação entre a Máquina de Boltzmann e os Algoritmos Evolutivos binários com população composta por um único indivíduo pai e um único indivíduo descendente. Como forma de auxiliar nas análises, o trabalho utiliza o Problema do Caixeiro Viajante como plataforma de ensaios, propondo mapeamentos entre as equações da Máquina de Boltzmann e os operadores evolutivos da Estratégia Evolutiva (1+1)-ES. / An analysis between the Evolutionary Computation and the Neural Computation fields was presented in order to identify similarities and mappings between the theories. In the analysis, the identification of similarities between the models designed for combinatorial optimization problems results in a comparison between the Boltzmann Machine and the Two-Membered Evolutionary Algorithms. In order to analyze the class of combinatorial optimization problems, this work used the Traveling Salesman Problem as a study subject, where the Boltzmann Machine equations were used to implement the evolutionary operators of an Evolution Strategy (1+1)-ES.

A segurança nos voos de Veículos Aéreos Não Tripulados (VANTs) é uma importante questão e vem ganhando destaque devido a uma série de acidentes com tais aeronaves. O aumento do número de aeronaves no espaço aéreo e a autonomia cada vez maior para realizar missões estão entre outros elementos que merecem destaques. No entanto, pouca atenção tem sido dada a autonomia da aeronave em casos emergenciais [Contexto]. Nesse contexto, o desenvolvimento de algoritmos que efetuem o planejamento de rotas na ocorrência de situações críticas é fundamental para obter maior segurança aérea. Eventuais situações de insegurança podem estar relacionadas a uma falha nos equipamentos do veículo aéreo que impede a continuação da missão em curso pela aeronave [Lacuna]. A presente pesquisa avança o estado da arte considerando um conceito chamado In-Flight Awareness (IFA), que estabelece consciência situacional em VANTs, visando maior segurança de voo. Os estudos também avançam na proposição de modelos matemáticos que representem o estado da aeronave avariada, viabilizando o pouso emergencial e minimizando possíveis danos [Propósito]. Este trabalho utiliza técnicas de computação evolutiva como Algoritmos Genéticos (AG) e Algoritmos Genéticos Multi-Populacional (AGMP), além de uma Heurística Gulosa (HG) e um modelo de Programação Linear Inteira Mista (PLIM) no tratamento de falhas críticas juntamente com o conceito de IFA [Metodologia]. As soluções obtidas foram avaliadas através de experimentos offline usando os modelos matemáticos desenvolvidos, além de validadas em um simulador de voo e em um voo real. De forma geral, o AG e AGMP obtiveram resultados equivalentes, salvando o VANT em aproximadamente 89% dos mapas. A HG conseguiu trazer a aeronave até uma região bonificadora em 77% dos mapas dentro de um tempo computacional abaixo de 1 segundo. No modelo PLIM, o tempo gasto foi de cerca de quatro minutos já que garantia a otimalidade da solução encontrada. Devido ao seu elevado tempo computacional, uma estratégia evolvendo rotas pré-calculadas foi definida a partir do PLIM, mostrando-se bastante promissora. Nos experimentos envolvendo simulador de voo foram testadas diferentes condições de vento e se verificou que mesmo sobre tais condições os métodos desenvolvidos conseguiram efetuar o pouso com segurança [Resultado]. O trabalho apresentado colabora com a segurança de Veículos Aéreos Não Tripulados e com a proposta de modelos matemáticos que representem a aeronave em caso de situações críticas. Os métodos, de forma geral, mostraram-se promissores na resolução do problema de pouso emergencial já que trouxeram a aeronave com segurança até regiões interessantes ao pouso em um baixo tempo computacional. Isso foi atestado pelos resultados obtidos a partir das simulações offline, em simulador de voo e em voo real [Conclusão]. As principais contribuições do trabalho são: modelagem de regiões adequadas ao pouso, modelagem de falhas, arquitetura do sistema planejador de rotas e modelo linear para para pouso emergencial [Contribuição]. / The security involved in flights of Unmanned Aerial Vehicles (UAVs) is an important issue and is achieving prominence due to a number of accidents involving such aircraft. Other elements that deserve highlights are the increase in the number of aircraft in the airspace and autonomy to perform missions, however, little attention has been given to the autonomy of the aircraft in emergency cases [Context]. In this context, the development of algorithms that contribute significantly to the path planning in the event of critical situations is essential for more air traffic. Possible situations of insecurity may be related to a failure in the equipment of vehicle that prevents the continuation of the current mission by aircraft [Gap]. The research advances the state of the art considering a concept called In-Flight Awareness (IFA), which provides situational awareness in UAVs aiming at greater flight safety. Advances also in the developing of mathematical models that represent the state of the damaged aircraft, with the purpose to execute the emergency landing by minimizing damages [Purpose]. Thus, this work applies evolutionary computation techniques such as Genetic Algorithms (GA) and Multi-Population Genetic Algorithms (MPGA), as well as a Greedy Heuristic (GH) and a Mixed Integer Linear Programming (MILP) model to deal with critical situations along with the concept of IFA [Methodology]. The solutions obtained were evaluated through offline experiments using the developed mathematical models, which were validated in a flight simulator and a real-world flight. In General, the GA and MPGA reached similar results by saving the UAV in approximately 89% of the maps, while the GH was able to bring the aircraft to a bonus region for 77% of maps within a feasible computational time lower than 1 second. In the MILP model, the time spent was about four minutes since it guarantees optimality of the solution found. Due to such high computational time, a strategy involving nearby routes pre-calculated was defined from the MILP which was very promising. In experiments involving flight simulator, different wind conditions were tested and it was found that even under such conditions the methods developed have managed to execute the landing safely [Result]. The work presented collaborates with the safety of Unmanned Aerial Vehicles and with the proposal of mathematical models that represent the aircraft under critical situations. The methods, in general, were promising since they brought the aircraft to execute a safe landing within a low computational time as shown by offline simulations, flight simulator and real flight [Conclusion]. The main contributions are: fault modeling, system architecture planner routes and linear model for emergency landing. [Contribution].

This paper aims to present the thesis developed in the Doctoral Programin Computer Science and Computational Mathematics of the ICMC/USP. The thesis theme seeks to advance the state of the art by solving the problems of scalability and representation present in mission planning algorithms for Unmanned Aerial Vehicle (UAV). Techniques based on mathematical programming and evolutionary computation are proposed. Articles have been published, submitted or they are in final stages of preparation.These studies report the most significant advances in the representation and scalability of this problem. Mission planners worked on the thesis deal with stochastic problems in non-convex environments,where collision risks or failures in mission planning are treated and limited to a tolerated value. The advances in the representation allowed to solve violations in the risks present in the original literature modeling, besides making the models more realistic when incorporating aspects such as effects of the air resistance. Efficient mathematical modeling techniques allowed to advance from a Mixed Integer Nonlinear Programming (MINLP) model, originally proposed in the literature, to a Mixed Integer Linear Programming (MILP) problem. Modeling as a MILP led to problem solving more efficiently through the branch-and-algorithm. The proposed new representations resulted in improvements from scalability, solving more complex problems within a shorter computational time. In addition, advances in scalability are even more effective when techniques combining mathematical programming and metaheuristics have been applied to the problem. / O presente documento tem por objetivo apresentar a tese desenvolvida no Programade Doutorado em Ciência da Computação e Matemática Computacional do ICMC/USP. O tema da tese busca avançar o estado da arte ao resolver os problemas de escalabilidade e representação presentes em algoritmos de planejamento para missões com Veículos Aéreos Não Tripulados (VANTs). Técnicas baseadas em programação matemática e computação evolutiva são propostas. Artigos foram publicados, submetidos ou se encontram em fase final de elaboração. Esses trabalhos reportamos avanços mais significativos obtidos na representação e escalabilidade deste problema.Os planejadores de missão trabalhados na tese lidam com problemas estocásticos em ambientes não convexos, onde os riscos de colisão ou falhas no planejamento da missão são tratados e limitados a um valor tolerado. Os avanços na representação permitiram solucionar violações nos riscos presentes na modelagem original, além de tornar os modelos mais realistas ao incorporar aspectos como efeitos da resistência do ar. Para isso, técnicas eficientes de modelagem matemática permitiram avançar de um modelo de Programação Não-Linear Inteira Mista(PNLIM), originalmente proposto na literatura, para um problema de Programação Linear Inteira Mista (PLIM). A modelagem como um PLIM levou à resolução do problema de forma mais eficiente através do algoritmo branch-and-cut. As novas representações propostas resultaram em melhorias na escalabilidade, solucionando problemas mais complexos em um tempo computacional menor.Além disso,os avanços em escalabilidade mostraram-se mais efetivos quando técnicas combinando programação matemática e metaheurísticas foram aplicadas ao problema.

Este trabalho realiza uma análise dos modelos pertencentes à Computação Neural e à Computação Evolutiva visando identificar semelhanças entre as áreas e sustentar mapeamentos entre as semelhanças identificadas. Neste contexto, a identificação de similaridades visando à resolução de problemas de otimização combinatorial resulta em uma comparação entre a Máquina de Boltzmann e os Algoritmos Evolutivos binários com população composta por um único indivíduo pai e um único indivíduo descendente. Como forma de auxiliar nas análises, o trabalho utiliza o Problema do Caixeiro Viajante como plataforma de ensaios, propondo mapeamentos entre as equações da Máquina de Boltzmann e os operadores evolutivos da Estratégia Evolutiva (1+1)-ES. / An analysis between the Evolutionary Computation and the Neural Computation fields was presented in order to identify similarities and mappings between the theories. In the analysis, the identification of similarities between the models designed for combinatorial optimization problems results in a comparison between the Boltzmann Machine and the Two-Membered Evolutionary Algorithms. In order to analyze the class of combinatorial optimization problems, this work used the Traveling Salesman Problem as a study subject, where the Boltzmann Machine equations were used to implement the evolutionary operators of an Evolution Strategy (1+1)-ES.

Neste trabalho foi realizada uma proposta de utilização de Sistemas de Inferência Nebulosos para controlar, em tempo de execução, parâmetros de Algoritmos Genéticos. Esta utilização busca melhorar o desempenho de Algoritmos Genéticos diminuindo, ao mesmo tempo: a média de iterações necessárias para que um Algoritmo Genético encontre o valor ótimo global procurado; bem como diminuindo o número de execuções do mesmo que não são capazes de encontrar o valor ótimo global procurado, nem mesmo para quantidades elevadas de iterações. Para isso, foram analisados os resultados de diversos experimentos com Algoritmos Genéticos, resolvendo instâncias dos problemas de Minimização de Funções e do Caixeiro Viajante, sob diferentes configurações de parâmetros. Com base nos resultados obtidos a partir destes experimentos, foi proposto um modelo com a troca de valores de parâmetros de Algoritmos Genéticos, em tempo de execução, pela utilização de Sistemas de Inferência Nebulosos, de forma a melhorar o desempenho do sistema, minimizando ambas as medidas citadas anteriormente. / This work addressed a proposal of the application of Fuzzy Systems to adjust parameters of Genetic Algorithms, during execution time. This application attempts to improve the performance of Genetic Algorithms by diminishing, at the same time: the average number of necessary generations for a Genetic Algorithm to find the desired global optimum value, as well as diminishing the number of executions of a Genetic Algorithm that are not capable of finding the desired global optimum value even for high numbers of generations. For that purpose, the results of many experiments with Genetic Algorithms were analyzed; addressing instances of the Function Minimization and the Travelling Salesman problems, under different parameter configurations. With the results obtained from these experiments, a model was proposed, for the exchange of parameter values of Genetic Algorithms, in execution time, by using Fuzzy Systems, in order to improve the performance of the system, minimizing both of the measures previously cited.

Neste trabalho foi realizada uma busca por relações, regras e transformações entre duas metodologias constituintes da Inteligência Computacional - a Computação Nebulosa e a Computação Evolutiva. Com a organização e sistematização da existência de tais transformações, obtém-se uma mudança na modelagem de soluções que as utilizam de forma conjunta, possibilitando que teorias e modelos bem estabelecidos em uma das metodologias possam ser aproveitados pela outra de uma forma mais robusta, correta por construção, intrínseca e transparente. Um modelo foi proposto para direcionar o trabalho de pesquisa. Através da análise desse modelo e de uma revisão bibliográfica realizada, transformações pontuais entre as metodologias foram elencadas, e posteriormente consolidadas por meio de experimentos práticos: uma Base de Conhecimento (BC) de um Controlador Lógico Nebuloso foi criada e modificada, conforme a necessidade, através de um Algoritmo Genético (AG). Com a abordagem desenvolvida, além da criação de BCs a partir de pouquíssimo conhecimento sobre o domínio do problema, tornou-se possível a inserção de novos \"comportamentos desejados\" em BCs já existentes, automaticamente, através de AGs. Os resultados desses experimentos, realizados sobre uma plataforma computacional especificada e implementada para este fim, foram apresentados e analisados. / This work addressed a search of relations, rules and transformations between two Computational Intelligence constituent methodologies - Fuzzy Computing and Evolutionary Computing. The existence of these relations changes the actual way of solutions modeling that uses these methodologies, allowing the utilization of well established theories and models of one technique by the other in a more robust, intrinsic and transparent way. Besides the research and systematization of points that indicate the existence of relations between the two methodologies, a model to guide these exploration was proposed. By this model analysis and by the bibliographic revision made, punctual transformations were pointed out, and further consolidated through practical experiments: a Knowledge Base (KB) of a Fuzzy Logic Controller was created and modified automatically by a Genetic Algorithm. With the developed approach, besides the creation of KBs, it became possible to automatically insert new \"desired behaviors\" to existent KBs. The results of such experiments, realized through a computational platform specified and implemented to this task, were presented and analyzed.