No description available.

Dentro da bioinformática uma das atividades mais realizadas é o alinhamento de seqüências biológicas [1]. Seus resultados são utilizados em várias atividades que desdobram-se em áreas de pesquisa interdisciplinares com geração de diversos subprodutos. Sendo uma das primeiras etapas de tais tarefas, o multialinhamento é então importante para garantir a qualidade dos resultados obtidos em vários estudos do material genético. Para este trabalho espera-se a reprodução dos resultados já publicados na área [2]; [3]; [4]; [5]; [6]). A implementação de um programa de multialinhamento global de seqüências biológicas utilizando uma abordagem iterativa estocástica por algoritmo genético, uma forma relativamente recente [7] de se atacar tal problema. Obtenção de um panorama sobre as soluções alternativas existentes / Multialignment of biological sequences is one of the most frequently used activities in bioinformatics. The results provided by sequence alignment are used in the solution of other bioinformatics problems. Since a multialignment procedure is one of the first steps of many bioinformatics problems, the condition of an alignment affects the quality of the results obtained for these problems. Multialignment of biological sequences is a complex problem (NP complete) and requires usually heuristics to obtain acceptable performance. Evolutionary algorithms have been used with relevant results. This work aims to find better solutions for the multialignment problem using evolutionary computation. In order to achieve that, this research investigates techniques using evolutionary computation applied to multialignment problem and searches to reproduce their results. Moreover, the development of an approach that performs global multialignment of biological sequences using evolutionary algorithms and an evaluation of the available multialignment techniques are also proposed

Dentro da bioinformática uma das atividades mais realizadas é o alinhamento de seqüências biológicas [1]. Seus resultados são utilizados em várias atividades que desdobram-se em áreas de pesquisa interdisciplinares com geração de diversos subprodutos. Sendo uma das primeiras etapas de tais tarefas, o multialinhamento é então importante para garantir a qualidade dos resultados obtidos em vários estudos do material genético. Para este trabalho espera-se a reprodução dos resultados já publicados na área [2]; [3]; [4]; [5]; [6]). A implementação de um programa de multialinhamento global de seqüências biológicas utilizando uma abordagem iterativa estocástica por algoritmo genético, uma forma relativamente recente [7] de se atacar tal problema. Obtenção de um panorama sobre as soluções alternativas existentes / Multialignment of biological sequences is one of the most frequently used activities in bioinformatics. The results provided by sequence alignment are used in the solution of other bioinformatics problems. Since a multialignment procedure is one of the first steps of many bioinformatics problems, the condition of an alignment affects the quality of the results obtained for these problems. Multialignment of biological sequences is a complex problem (NP complete) and requires usually heuristics to obtain acceptable performance. Evolutionary algorithms have been used with relevant results. This work aims to find better solutions for the multialignment problem using evolutionary computation. In order to achieve that, this research investigates techniques using evolutionary computation applied to multialignment problem and searches to reproduce their results. Moreover, the development of an approach that performs global multialignment of biological sequences using evolutionary algorithms and an evaluation of the available multialignment techniques are also proposed

Esta tesis se encuadra en el análisis de las tecnologías de la información como herramientas para aumentar la eficiencia de la toma de decisiones en sistemas logísticos, en el marco de la gestión de la cadena de suministros. Más específicamente se busca desarrollar y aplicar una herramienta de gestión que mejore la eficiencia de la programación de operaciones en la planificación operativa de la distribución física de mercaderías (R&S: Routing and Scheduling) en el ámbito del transporte automotor de cargas refrigeradas fronteras adentro. En este sentido en este trabajo se definen las formulaciones más conocidas que se encuentran en la literatura de problemas de ruteo de vehículos en el contexto del servicio logístico objeto de la investigación, y se presenta un criterio para su clasificación de acuerdo a los aspectos principales que se desprenden de las investigaciones más relevantes. Luego se modela formalmente una variante del problema clásico de ruteo de vehículos con restricciones de capacidad y ventanas temporales (CVRPTW) en un entorno urbano de distribución. Para su resolución se desarrolla un procedimiento meta-heurístico evolutivo, específicamente un algoritmo genético dada su demostrada adaptación a este tipo de problemas. El procedimiento fue testeado sobre el conjunto de 56 problemas académicos de ruteo de vehículos con restricciones de capacidad y ventanas temporales de Solomon (1987) y se comparó su desempeño con los mejores resultados conocidos obtenidos por otros autores. La experimentación se realiza sobre un caso de aplicación con información real de un operador logístico (2PL second part logistic) bonaerense especializado en el transporte y distribución de mercadería a carga fraccionada en entornos urbanos de distribución. La mercadería tiene restricciones en materia fitosanitaria y requerimientos especiales en el mantenimiento de temperatura y humedad, al tratarse de productos frescos en los que un quiebre o interrupción en la cadena de frío repercute en la calidad del producto, alterando sus atributos organolépticos. La empresa abastece en un día de operatoria habitual, en promedio, unos doscientos clientes minoristas del Gran Buenos Aires. Del testeo del optimizador desarrollado en las instancias académicas de Solomon se desprende que presenta un mejor desempeño en problemas con características similares a los problemas de distribución urbana. Aunque el desempeño del algoritmo en problemas con características más cercanas a los de distribución de media a larga distancia es bueno, es inferior a los resultados obtenidos por otros autores. De los resultados obtenidos de la experimentación con información real se observa una notable calidad de las soluciones y una mejora en cuanto a eficiencia y productividad en comparación con la asignación realizada por la empresa en la instancia real. / This work fits into the analysis of information technologies as tools to enhance efficiency in decision making in logistics systems, and falls within the framework of supply chain management. More specifically, the aim is to develop and apply a management tool that improves the efficiency of operation scheduling in the operational planning of the physical delivery of goods (R&S: Routing and scheduling) in the area of road transportation of refrigerated cargo within the country. In this respect, this work defines the best-known formulations found in the literature on vehicle routing problems in the context of the logistics service being researched and a criterion for their classification according to the main aspects arising from the most relevant research is presented. Then, a variant of the classic capacitated vehicle routing problem with time windows (CVRPTW) in the delivery in an urban environment is formally modeled. To solve this problem, a meta-heuristic evolutionary procedure, specifically a genetic algorithm, is developed, since it has been shown that it is suitable for this type of problems. The procedure was tested in the set of 56 academic capacitated vehicle routing problems with time windows presented by Solomon (1987) and its performance was compared to the best known results obtained by other authors. The experiment is carried out on a case of application with real information of a Buenos Aires province logistics service provider (2PL second part logistic) specialized in transportation and distribution of break bulk cargo in urban environments. The goods have constraints in phitosanitary terms and special requirements related to temperature and humidity settings, since they are fresh products whose quality, and, consequently, organoleptic properties, are affected by breaks or interruptions in the cold chain. In a regular working day, the company supplies, in average, around two hundred retail clients in Buenos Aires metropolitan area. From Solomon's academic testing of optimizer it follows that it shows a better performance in problems similar to problems in the delivery in urban environments. While the algorithm performance in problems with more similar characteristics to those in middle and long distance transport is good, it is less successful than the results obtained by other authors. In the results obtained in the experiment with real data we can observe a remarkable quality in solutions and improvements as regards efficiency and productivity as compared to the assignment carried out by the company in real life.

La modelación individual de la interacción entre agentes en Economía ha recibido particular atención en los últimos años. Estos aportes han recaído inicialmente, y siguiendo la tradición académica, en modelos analíticos que contemplan la aparición de interacciones locales entre los individuos. Esta ineracción permite, en algún punto, determinar resultados de conducta diferentes comparados con un análisis en el que los agentes se comporten aisladamente. La moderación de dicha interacción en términos formales ha utilizado herramitentas matemáticas que permiten la traslación de efectos por parte de un individuo hacia otro. La teoría de juegos, dado que analiza en el comportamiento óptimo de un agente que se ve restringido en su accionar por las estrategias de otros agentes, resulta un modelo analítico clásico de ciertos casos de interacción. La tesis utiliza el enfoque basado en agentes para modelar las interacciones entre agentes y comprobar si los resultados teóricos pueden ser alcanzados a través de un modelo computacionalmente evolutivol. Sus resultados no son formales sino numéricos. Su sustento no es básicamente matemático sino computacional. Los agentes resultan ser bajo este marco de investigaciòn objetos de programas. Los objetos agente tienen estados y reglas de comportamiento. Correr un modelo de agentes comprende la inicialización de la población de agentes, el proceso subsiguientede interacción entre los mismos y el monitoreo del resultado final. En definitiva, correr el modelo en el tiempo la suficiente cantidad de veces, en caso de ser estocástico, es lo único que se necesita para "resolverlo". La tesos comprende 5 capítulos. El primero es una introducción general mientras que el segundo se aboca a explayar los modelos teóricos que serán testeados por modelos computacionales. El tercer capítulo presenta la metodología computacional de algoritmos evolutivos y el capítulo 4 analiza el resultado de los experimentos computacionales. Finalmente, la tesis concluye con el capítulo 5. Como síntesis del trabajo, los algoritmos evolutivos fueron exitosos en reproducir los resultados extremos de formación de redes (la red vacía y la red completa) pero fallaron en replicar los resultados de arquitecturas intermedias propuestas por la teoría. / The modeling of interaction between agents in economics has received particular attention in recent years. These contribu-tions have focused intially, and following the acaademic tradition, in analytically tracktable models that showed emer-gence of local interactions among individuals. This interaction can, at some point, determining different behavioral outcomes compared with an analysis in which agents behave in isolation. The modeling of this interaction in formal terms used mathematical tools that allow the translation of effects from one individual to another. Game theory, modelling the optimal behavior of an agent constrained in its actions by the strategies of other agents, is a classical analytic model for certain cases of interaction. The thesis uses agent-based approach to model interactions between agents and contrast if theoretical results can be achieved through an evolutionary computational model.Their results are not formal but numeri-cal. Their background is not mathematical but basically computing. The agents appear under this framework of re-search as program objects. Agent as objects have sates and rules of behavior.Running an agent model includes te initia-lization of the population of agents, the subsequent process of interaction among them and monitoring the outcome. In short, running the model a sufficient number of times, if it is stochastic, is all that is needed to "solve" it. The thesis consists of 5 chapters. The first is a general intoduction while in the second es summarized the theoretical models that are going to be tested by computer models. The third chapter presents the computational methodology of evolutionary algorithms and chapter 4 discusses the results of computa-tional experiments. Finally, the thesis concludes with Chapter 5. As a summary of the work, evolutionary algorithms were successful in reproducing the extreme results (the empty network and the complete network) of network formation games but failed to replicate the results of inter-mediate architectures proposed by the theory.

Los modelos utilizados en el diseño de redes hidráulicas pueden ser muy variados, en función del objetivo que se pretende abordar. Este trabajo se centra fundamentalmente en el dimensionado hidráulico de redes de distribución de agua, de modo que se cumplan una serie de requerimientos de servicio, entre los que se incluyen condiciones mínimas de presión, velocidad, etc. Una de las complejidades del diseño de redes de distribución de agua (RDA) radica en la elección de los diámetros como variables de decisión; puesto que en este caso las restricciones son funciones implícitas de estos mismos diámetros, el espacio de soluciones se convierte en no convexo y la función objetivo en multimodal. En este punto, los métodos tradicionales basados en técnicas matemáticas quedan limitados a la localización de mínimos locales de la función objetivo, que depende del punto de inicio del proceso de convergencia. Numerosos investigadores han diseñado aplicaciones en lo que a métodos de diseño de redes de agua se refiere, planteando los costes de la red como la función objetivo a optimizar. La aplicación de técnicas evolutivas de optimización permite la búsqueda de soluciones más allá de estos mínimos locales, lo que amplía en muchas ocasiones el campo de búsqueda, y por tanto, la capacidad de obtener buenas soluciones. Este tipo de técnicas son muy versátiles, por lo que tienen multitud de posibles aplicaciones, siendo el diseño óptimo de redes de agua una de ellas. El carácter aleatorio de los algoritmos evolutivos provoca que no exista la certeza absoluta de explorar el espacio completo de soluciones. No obstante, las distintas técnicas evolutivas son capaces de obtener un conjunto de buenas soluciones que mejoran de modo progresivo. En términos generales, el modelo de optimización desarrollado para todas estas técnicas incluye una función objetivo cuyo valor trata de minimizarse. En este sentido, la mayoría de las metodologías que trata esta tesis han sido ya aplicadas con ciert / Mora Meliá, D. (2012). Diseño de redes de distribución de agua mediante algoritmos evolutivos. Análisis de eficiencia [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/16803

[EN] The identification process of the parameters of a nominal model and its uncertainty, when it is used for Robust Control, is known as Parametric Robust Identification (RI). A possible approach to RI, which is appropriate when noise statistical properties unknown and/or model error invalidate statistical approaches, is the deterministic one (Set Membership Estimation). This deterministic approach assumes that identification error (IE), differences between the simulated outputs of the model and the measured outputs of the process, although unknown, will be bounded. Therefore, the objective is to estimate the parameters set of a model which keeps the identification error bounded by a certain norm and bound. This set is known as the feasible parameter set (FPS). For linear in their parameters models, the FPS is, if it exists, a convex polytope. In nonlinear models, the polytope can be non-convex even disjoint. In this thesis a RI methodology, which permits to estimate any kind of FPS in nonlinear models when IE is bounded by several norms simultaneously, is presented. This methodology converts the RI problem into a multimodal optimization problem with optimal global infinities, which constitute the FPS. For its optimization a specific evolutionary algorithm e-GA has been developed, to characterize the FPS by means of a discrete set of models FPS^* adequately distributed along the FPS. The methodology comes accompanied by a procedure that makes easy the determination of bounds, associated to the norms of the IE, in order to guarantee an FPS\neq\emptyset. For that, the Pareto Front information, which is obtained by means of minimization norms of the IE in a multobjective context is used. To solve the multobjective problem an evolutionary algorithm e-MOGA has been developed. In addition, a nominal model of restricted interpolated projection which belongs to the FPS is proposed. It is optimal in both identification and estimation errors in the parameter space. The RI of three nonlinear models, with real data, is presented as application examples of the proposed methodology: a thermal process, a model which shows the blockage that produces a given drug on the ionic currents of a cardiac cell and a greenhouse climate model (temperature and humidity) with roses hydroponic crop. / [ES] Al proceso de identificación de los parámetros de un modelo nominal y su incertidumbre para su utilización en Control Robusto se le conoce como Identificación Robusta Paramétrica (IR). Un posible enfoque para abordar la IR, que resulta apropiado cuando el desconocimiento de las propiedades estadísticas del ruido y/o la dinámica no modelada invalidan los enfoques estocásticos, es el determinístico (Set Membership Estimation). Este enfoque asume que el error de identificación (EI), diferencia entre las salidas medidas de proceso y las simuladas del modelo, aunque es desconocido, está acotado. De ahí que, bajo este enfoque, se persiga la determinación del conjunto de parámetros que consiguen mantener el EI acotado para una determinada norma y cota. Dicho conjunto es conocido como el conjunto de parámetros factibles (FPS). Cuando el modelo es lineal respecto de sus parámetros, el FPS, si existe, es un politopo convexo. En modelos no lineales dicho politopo puede ser no convexo e incluso inconexo. En esta tesis se presenta una metodología de IR que permite determinar FPS, de cualquier tipo, en modelos no lineales cualesquiera, acotando el EI simultáneamente mediante varias normas. La metodología transforma el problema de IR en un problema de optimización multimodal con infinitos óptimos globales, los cuales constituyen el FPS. Para su optimización se ha desarrollado un algoritmo evolutivo (EA) específico e-GA, que caracteriza el FPS mediante un conjunto discreto de modelos FPS* adecuadamente distribuido a lo largo del FPS. La metodología viene acompañada de un procedimiento que facilita la determinación de las cotas, asociadas a las normas que acotan el EI, para asegurar que FPS no se aun conjutno vacío. Para ello, se utiliza la información que genera el frente de Pareto resultante de la minimización simultánea de las normas mediante una optimización multiobjetivo.Para resolver este problema de optimización se ha desarrollado el algoritmo evolutivo e-MOGA. Adicionalmente, se propone como modelo nominal un modelo de proyección interpolada restringida que, pertenenciendo al FPS, resulta óptimo respecto del error de identificación y respecto del error de estimación en el espacio de parámetros. Como ejemplos de aplicación de la metodología propuesta se presenta la IR, con datos reales, de los parámetros de tres modelos no lineales: un sistema térmico, un modelo que refleja el bloqueo que produce un determinado fármaco sobre las corrientes iónicas de una célula cardíaca y el modelo climático de un invernadero (temperatura y humedad) con cultivo hidropónico de rosas. / [CA] Al procés d'identificació dels paràmetres d'un model nominal i la seua incertesa per a la seua utilització en Control Robust se'l coneix com a Identificació Robusta Paramètrica (IR). Un possible enfocament per a abordar l'IR, que resulta apropiat quan el desconeixement de les propietats estadístiques del soroll i/o la dinàmica no modelada invaliden els enfocaments estocàstics, és el determinístic (Set Membership Estimation). Aquest enfocament assumeix que l'error d'identificació (EI), diferència entre les eixides mesurades del procés i les simulades del model, encara que és desconegut, està acotat. Davall aquest enfocament, es persegueix la determinació del conjunt de paràmetres que aconsegueixen mantenir l'EI acotat per a una determinada norma i cota. Dit conjunt és conegut com el conjunt de paràmetres factibles (FPS). Quan el model és lineal respecte dels seus paràmetres, el FPS, si existeix, és un politop convex. En models no lineals dit politop pot ser no convex i fins i tot inconnex. En aquesta tesi es presenta una metodologia d'IR que permet determinar FPS, de qualsevol tipus, en models no lineals qualsevol, acotant l'EI simultàniament mitjançant diverses normes. La metodologia transforma el problema d'IR en un problema d'optimització multimodal amb infinits òptims globals, els quals constitueixen el FPS. Per a la seua optimització s'ha desenvolupat un algoritme evolutiu (EA) específic e-GA, que caracteritza el FPS mitjançant un conjunt discret de models FPS^* adequadament distribuït al llarg del FPS. La metodologia ve acompanyada d'un procediment que facilita la determinació de les cotes, associades a les normes que acoten l'EI, per a assegurar que FPS\neq\emptyset. Per a això, s'utilitza la informació que genera el front de Pareto resultant de la minimització simultània de les normes mitjançant una optimització multiobjetiu. Per a la resoldre, el problema multiobjectiu s'ha desenvolupat l'algoritme evolutiu e-MOGA. Addicionalment, es proposa com a model nominal un model de projecció interpolada restringida que, pertanyent al FPS, resulta òptim respecte de l'error d'identificació i respecte de l'error de estimació en l'espai de paràmetres. Com a exemples d'aplicació de la metodologia proposada es presenta l'IR, amb dades reals, dels paràmetres de tres models no lineals: un sistema tèrmic, un model que reflecteix el bloqueig que produeix un determinat fàrmac sobre els corrents iònics d'una cèl·lula cardíaca i el model climàtic d'un hivernacle (temperatura i humitat) amb cultiu hidropònic de roses. / Herrero Durá, JM. (2006). Identificación Robusta de Sistemas no Lineales mediante Algoritmos Evolutivos [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/131396

Nesta tese, são estudados algoritmos para agrupamento de dados, com particular ênfase em Agrupamento de Dados com Restrições, no qual, além dos objetos a serem agrupados, são fornecidos pelo usuário algumas informações sobre o agrupamento desejado. Como fundamentação para o agrupamento, são considerados os modelos de mistura finitos, em especial, com componentes gaussianos, usualmente chamados de modelos de mistura de gaussianas. Dentre os principais problemas que os algoritmos desenvolvidos nesta tese de doutorado buscam tratar destacam-se: (i) estimar parâmetros de modelo de mistura de gaussianas; (ii) como incorporar, de forma eficiente, restrições no processo de aprendizado de forma que tanto os dados quanto as restrições possam ser adicionadas de forma online; (iii) estimar, via restrições derivadas de conceitos pré-determinados sobre os objetos (usualmente chamados de classes), o número de grupos destes conceitos. Como ferramenta para auxiliar no desenvolvimento de soluções para tais problemas, foram utilizados algoritmos evolutivos que operam com mais de uma solução simultaneamente, além de utilizarem informações de soluções anteriores para guiar o processo de busca. Especificamente, foi desenvolvido um algoritmo evolutivo baseado na divisão e união de componentes para a estimação dos parâmetros de um modelo de mistura de gaussianas. Este algoritmo foi comparado com o algoritmo do mesmo gênero considerado estado-da-arte na literatura, apresentando resultados competitivos e necessitando de menos parâmetros e um menor custo computacional. Nesta tese, foram desenvolvidos dois algoritmos que incorporam as restrições no processo de agrupamento de forma online. Ambos os algoritmos são baseados em algoritmos bem-conhecidos na literatura e apresentaram, em comparações empíricas, resultados melhores que seus antecessores. Finalmente, foram propostos dois algoritmos para se estimar o número de grupos por classe. Ambos os algoritmos foram comparados com algoritmos reconhecidos na literatura de agrupamento de dados com restrições, e apresentaram resultados competitivos ou melhores que estes. A estimação bem sucedida do número de grupos por classe pode auxiliar em diversas tarefas de mineração de dados, desde a sumarização dos dados até a decomposição de problemas de classificação em sub-problemas potencialmente mais simples. / In the last decade, researchers have been giving considerable attention to the field of Constrained Clustering. Algorithms in this field assume that along with the objects to be clustered, the user also provides some constraints about which kind of clustering (s)he prefers. In this thesis, two scenarios are studied: clustering with and without constraints. The developments are based on finite mixture models, namely, models with Gaussian components, which are usually called Gaussian Mixture Models (GMMs). In this context the main problems addressed are: (i) parameter estimation of GMMs; (ii) efficiently integrating constraints in the learning process allowing both constraints and the data to be added in the modeling in an online fashion; (iii) estimating, by using constraints derived from pre-determined concepts (usually named classes), the number of clusters per concept. Evolutionary algorithms were adopted to develop solutions for such problems. These algorithms analyze more than one solution simultaneously and use information provided by previous solutions to guide the search process. Specifically, an evolutionary algorithm based on procedures that perform splitting and merging of components to estimate the parameters of a GMM was developed. This algorithm was compared to an algorithm considered as the state-of-the-art in the literature, obtaining competitive results while requiring less parameters and being more computationally efficient. Besides the aforementioned contributions, two algorithms for online constrained clustering were developed. Both algorithms are based on well known algorithms from the literature and get better results than their predecessors. Finally, two algorithms to estimate the number of clusters per class were also developed. Both algorithms were compared to well established algorithms from the literature of constrained clustering, and obtained equal or better results than the ones obtained by the contenders. The successful estimation of the number of clusters per class is helpful to a variety of data mining tasks, such as data summarization and problem decomposition of challenging classification problems.

Problemas de projeto de redes (PPRs) são muito importantes uma vez que envolvem uma série de aplicações em áreas da engenharia e ciências. Para solucionar as limitações de algoritmos convencionais para PPRs que envolvem redes complexas do mundo real (em geral modeladas por grafos completos ou mesmo esparsos de larga-escala), heurísticas, como os algoritmos evolutivos (EAs), têm sido investigadas. Trabalhos recentes têm mostrado que estruturas de dados adequadas podem melhorar significativamente o desempenho de EAs para PPRs. Uma dessas estruturas de dados é a representação nó-profundidade (NDE, do inglês Node-depth Encoding). Em geral, a aplicação de EAs com a NDE tem apresentado resultados relevantes para PPRs de larga-escala. Este trabalho investiga o desenvolvimento de uma nova representação, baseada na NDE, chamada representação nó-profundidade-grau (NDDE, do inglês Node-depth-degree Encoding). A NDDE é composta por melhorias nos operadores existentes da NDE e pelo desenvolvimento de novos operadores de reprodução possibilitando a recombinação de soluções. Nesse sentido, desenvolveu-se um operador de recombinação capaz de lidar com grafos não-completos e completos, chamado EHR (do inglês, Evolutionary History Recombination Operator). Foram também desenvolvidos operadores de recombinação que lidam somente com grafos completos, chamados de NOX e NPBX. Tais melhorias tem como objetivo manter relativamente baixa a complexidade computacional dos operadores para aumentar o desempenho de EAs para PPRs de larga-escala. A análise de propriedades de representações mostrou que a NDDE possui redundância, assim, foram propostos mecanismos para evitá-la. Essa análise mostrou também que o EHR possui baixa complexidade de tempo e não possui tendência, além de revelar que o NOX e o NPBX possuem uma tendência para árvores com topologia de estrela. A aplicação de EAs usando a NDDE para PPRs clássicos envolvendo grafos completos, tais como árvore geradora de comunicação ótima, árvore geradora mínima com restrição de grau e uma árvore máxima, mostrou que, quanto maior o tamanho das instâncias do PPR, melhor é o desempenho relativo da técnica em comparação com os resultados obtidos com outros EAs para PPRs da literatura. Além desses problemas, um EA utilizando a NDE com o operador EHR foi aplicado ao PPR do mundo real de reconfiguração de sistemas de distribuição de energia elétrica (envolvendo grafos esparsos). Os resultados mostram que o EHR possibilita reduzir significativamente o tempo de convergência do EA / Network design problems (NDPs) are very important since they involve several applications from areas of Engineering and Sciences. In order to solve the limitations of traditional algorithms for NDPs that involve real world complex networks (in general, modeled by large-scale complete or sparse graphs), heuristics, such as evolutionary algorithms (EAs), have been investigated. Recent researches have shown that appropriate data structures can improve EA performance when applied to NDPs. One of these data structures is the Node-depth Encoding (NDE). In general, the performance of EAs with NDE has presented relevant results for large-scale NDPs. This thesis investigates the development of a new representation, based on NDE, called Node-depth-degree Encoding (NDDE). The NDDE is composed for improvements of the NDE operators and the development of new reproduction operators that enable the recombination of solutions. In this way, we developed a recombination operator to work with both non-complete and complete graphs, called EHR (Evolutionary History Recombination Operator). We also developed two other operators to work only with complete graphs, named NOX and NPBX. These improvements have the advantage of retaining the computational complexity of the operators relatively low in order to improve the EA performance. The analysis of representation properties have shown that NDDE is a redundant representation and, for this reason, we proposed some strategies to avoid it. This analysis also showed that EHR has low running time and it does not have bias, moreover, it revealed that NOX and NPBX have bias to trees like stars. The application of an EA using the NDDE to classic NDPs, such as, optimal communication spanning tree, degree-constraint minimum spanning tree and one-max tree, showed that the larger the instance is, the better the performance will be in comparison whit other EAs applied to NDPs in the literatura. An EA using the NDE with EHR was applied to a real-world NDP of reconfiguration of energy distribution systems. The results showed that EHR significantly decrease the convergence time of the EA

In many real classification problems, the data set used for model induction is significantly imbalanced. This occurs when the number of examples of some classes is much lower than the other classes. Imbalanced datasets can compromise the performance of most classical classification algorithms. The classification models induced by such datasets usually present a strong bias towards the majority classes, tending to classify new instances as belonging to these classes. A commonly adopted strategy for dealing with this problem is to train the classifier on a balanced sample from the original dataset. However, this procedure can discard examples that could be important for a better class discrimination, reducing classifier efficiency. On the other hand, in recent years several studies have shown that in different scenarios the strategy of combining several classifiers into structures known as ensembles has proved to be quite effective. This strategy has led to a stable predictive accuracy and, in particular, to a greater generalization ability than the classifiers that make up the ensemble. This generalization power of classifier ensembles has been the focus of research in the imbalanced learning field in order to reduce the bias toward the majority classes, despite the complexity involved in generating efficient ensembles. Optimization meta-heuristics, such as evolutionary algorithms, have many applications for ensemble learning, although they are little used for this purpose. For example, evolutionary algorithms maintain a set of possible solutions and diversify these solutions, which helps to escape out of the local optimal. In this context, this thesis investigates and develops approaches to deal with imbalanced datasets, using ensemble of classifiers induced by samples taken from the original dataset. More specifically, this theses propose three solutions based on evolutionary ensemble learning and a fourth proposal that uses a pruning mechanism based on dominance ranking, a common concept in multiobjective evolutionary algorithms. Experiments showed the potential of the developed solutions. / Em muitos problemas reais de classificação, o conjunto de dados usado para a indução do modelo é significativamente desbalanceado. Isso ocorre quando a quantidade de exemplos de algumas classes é muito inferior às das outras classes. Conjuntos de dados desbalanceados podem comprometer o desempenho da maioria dos algoritmos clássicos de classificação. Os modelos de classificação induzidos por tais conjuntos de dados geralmente apresentam um forte viés para as classes majoritárias, tendendo classificar novas instâncias como pertencentes a essas classes. Uma estratégia comumente adotada para lidar com esse problema, é treinar o classificador sobre uma amostra balanceada do conjunto de dados original. Entretanto, esse procedimento pode descartar exemplos que poderiam ser importantes para uma melhor discriminação das classes, diminuindo a eficiência do classificador. Por outro lado, nos últimos anos, vários estudos têm mostrado que em diferentes cenários a estratégia de combinar vários classificadores em estruturas conhecidas como comitês tem se mostrado bastante eficaz. Tal estratégia tem levado a uma acurácia preditiva estável e principalmente a apresentar maior habilidade de generalização que os classificadores que compõe o comitê. Esse poder de generalização dos comitês de classificadores tem sido foco de pesquisas no campo de aprendizado desbalanceado, com o objetivo de diminuir o viés em direção as classes majoritárias, apesar da complexidade que envolve gerar comitês de classificadores eficientes. Meta-heurísticas de otimização, como os algoritmos evolutivos, têm muitas aplicações para o aprendizado de comitês, apesar de serem pouco usadas para este fim. Por exemplo, algoritmos evolutivos mantêm um conjunto de soluções possíveis e diversificam essas soluções, o que auxilia na fuga dos ótimos locais. Nesse contexto, esta tese investiga e desenvolve abordagens para lidar com conjuntos de dados desbalanceados, utilizando comitês de classificadores induzidos a partir de amostras do conjunto de dados original por meio de metaheurísticas. Mais especificamente, são propostas três soluções baseadas em aprendizado evolucionário de comitês e uma quarta proposta que utiliza um mecanismo de poda baseado em ranking de dominância, conceito comum em algoritmos evolutivos multiobjetivos. Experimentos realizados mostraram o potencial das soluções desenvolvidas.