A well-known paradigm for optimisation is the evolutionary algorithm (EA). An EA maintains a population of possible solutions to a problem which converges on a global optimum using biologically-inspired selection and reproduction operators. These algorithms have been shown to perform well on a variety of hard optimisation and search problems. A recent development in evolutionary computation is the Estimation of Distribution Algorithm (EDA) which replaces the traditional genetic reproduction operators (crossover and mutation) with the construction and sampling of a probabilistic model. While this can often represent a significant computational expense, the benefit is that the model contains explicit information about the fitness function. This thesis expands on recent work using a Markov network to model fitness in an EDA, resulting in what we call the Markov Fitness Model (MFM). The work has explored the theoretical foundations of the MFM approach which are grounded in Walsh analysis of fitness functions. This has allowed us to demonstrate a clear relationship between the fitness model and the underlying dynamics of the problem. A key achievement is that we have been able to show how the model can be used to predict fitness and have devised a measure of fitness modelling capability called the fitness prediction correlation (FPC). We have performed a series of experiments which use the FPC to investigate the effect of population size and selection operator on the fitness modelling capability. The results and analysis of these experiments are an important addition to other work on diversity and fitness distribution within populations. With this improved understanding of fitness modelling we have been able to extend the framework Distribution Estimation Using Markov networks (DEUM) to use a multivariate probabilistic model. We have proposed and demonstrated the performance of a number of algorithms based on this framework which lever the MFM for optimisation, which can now be added to the EA toolbox. As part of this we have investigated existing techniques for learning the structure of the MFM; a further contribution which results from this is the introduction of precision and recall as measures of structure quality. We have also proposed a number of possible directions that future work could take.

This thesis proposes a novel feature selection and classification method employing evolving spiking neural networks (eSNN) and evolutionary algorithms (EA). The method is named the Quantum-inspired Spiking Neural Network (QiSNN) framework. QiSNN represents an integrated wrapper approach. An evolutionary process evolves appropriate feature subsets for a given classification task and simultaneously optimises the neural and learning-related parameters of the network. Unlike other methods, the connection weights of this network are determined by a fast one-pass learning algorithm which dramatically reduces the training time. In its core, QiSNN employs the Thorpe neural model that allows the efficient simulation of even large networks. In QiSNN, the presence or absence of features is represented by a string of concatenated bits, while the parameters of the neural network are continuous. For the exploration of these two entirely different search spaces, a novel Estimation of Distribution Algorithm (EDA) is developed. The method maintains a population of probabilistic models specialised for the optimisation of either binary, continuous or heterogeneous search spaces while utilising a small and intuitive set of parameters. The EDA extends the Quantum-inspired Evolutionary Algorithm (QEA) proposed by Han and Kim (2002) and was named the Heterogeneous Hierarchical Model EDA (hHM-EDA). The algorithm is compared to numerous contemporary optimisation methods and studied in terms of convergence speed, solution quality and robustness in noisy search spaces. The thesis investigates the functioning and the characteristics of QiSNN using both synthetic feature selection benchmarks and a real-world case study on ecological modelling. By evolving suitable feature subsets, QiSNN significantly enhances the classification accuracy of eSNN. Compared to numerous other feature selection techniques, like the wrapper-based Multilayer Perceptron (MLP) and the Naive Bayesian Classifier (NBC), QiSNN demonstrates a competitive classification and feature selection performance while requiring comparatively low computational costs.

This thesis proposes a novel feature selection and classification method employing evolving spiking neural networks (eSNN) and evolutionary algorithms (EA). The method is named the Quantum-inspired Spiking Neural Network (QiSNN) framework. QiSNN represents an integrated wrapper approach. An evolutionary process evolves appropriate feature subsets for a given classification task and simultaneously optimises the neural and learning-related parameters of the network. Unlike other methods, the connection weights of this network are determined by a fast one-pass learning algorithm which dramatically reduces the training time. In its core, QiSNN employs the Thorpe neural model that allows the efficient simulation of even large networks. In QiSNN, the presence or absence of features is represented by a string of concatenated bits, while the parameters of the neural network are continuous. For the exploration of these two entirely different search spaces, a novel Estimation of Distribution Algorithm (EDA) is developed. The method maintains a population of probabilistic models specialised for the optimisation of either binary, continuous or heterogeneous search spaces while utilising a small and intuitive set of parameters. The EDA extends the Quantum-inspired Evolutionary Algorithm (QEA) proposed by Han and Kim (2002) and was named the Heterogeneous Hierarchical Model EDA (hHM-EDA). The algorithm is compared to numerous contemporary optimisation methods and studied in terms of convergence speed, solution quality and robustness in noisy search spaces. The thesis investigates the functioning and the characteristics of QiSNN using both synthetic feature selection benchmarks and a real-world case study on ecological modelling. By evolving suitable feature subsets, QiSNN significantly enhances the classification accuracy of eSNN. Compared to numerous other feature selection techniques, like the wrapper-based Multilayer Perceptron (MLP) and the Naive Bayesian Classifier (NBC), QiSNN demonstrates a competitive classification and feature selection performance while requiring comparatively low computational costs.

Estimation of Distribution Algorithms (EDAs) belong to the class of population based optimisation algorithms. They are motivated by the idea of discovering and exploiting the interaction between variables in the solution. They estimate a probability distribution from population of solutions, and sample it to generate the next population. Many EDAs use probabilistic graphical modelling techniques for this purpose. In particular, directed graphical models (Bayesian networks) have been widely used in EDA. This thesis proposes an undirected graphical model (Markov Random Field (MRF)) approach to estimate and sample the distribution in EDAs. The interaction between variables in the solution is modelled as an undirected graph and the joint probability of a solution is factorised as a Gibbs distribution. The thesis describes a model of fitness function that approximates the energy in the Gibbs distribution, and shows how this model can be fitted to a population of solutions to estimate the parameters of the MRF. The estimated MRF is then sampled to generate the next population. This approach is applied to estimation of distribution in a general framework of an EDA, called Distribution Estimation using Markov Random Fields (DEUM). The thesis then proposes several variants of DEUM using different sampling techniques and tests their performance on a range of optimisation problems. The results show that, for most of the tested problems, the DEUM algorithms significantly outperform other EDAs, both in terms of number of fitness evaluations and the quality of the solutions found by them. There are two main explanations for the success of DEUM algorithms. Firstly, DEUM builds a model of fitness function to approximate the MRF. This contrasts with other EDAs, which build a model of selected solutions. This allows DEUM to use fitness in variation part of the evolution. Secondly, DEUM exploits the temperature coefficient in the Gibbs distribution to regulate the behaviour of the algorithm. In particular, with higher temperature, the distribution is closer to being uniform and with lower temperature it concentrates near some global optima. This gives DEUM an explicit control over the convergence of the algorithm, resulting in better optimisation.

Submitted by Caroline Xavier (caroline.xavier@pucrs.br) on 2017-06-29T11:51:00Z No. of bitstreams: 1 DIS_HENRY_EMANUEL_LEAL_CAGNINI_COMPLETO.pdf: 3650909 bytes, checksum: 55d52061a10460875dba677a9812fe9c (MD5) / Made available in DSpace on 2017-06-29T11:51:00Z (GMT). No. of bitstreams: 1 DIS_HENRY_EMANUEL_LEAL_CAGNINI_COMPLETO.pdf: 3650909 bytes, checksum: 55d52061a10460875dba677a9812fe9c (MD5) Previous issue date: 2017-03-20 / Extrair informa??es relevantes a partir de dados n?o ? uma tarefa f?cil. Tais dados podem vir a partir de lotes ou em fluxos cont?nuos, podem ser completos ou possuir partes faltantes, podem ser duplicados, e tamb?m podem ser ruidosos. Ademais, existem diversos algoritmos que realizam tarefas de minera??o de dados e, segundo o teorema do "Almo?o Gr?tis", n?o existe apenas um algoritmo que venha a solucionar satisfatoriamente todos os poss?veis problemas. Como um obst?culo final, algoritmos geralmente necessitam que hiper-par?metros sejam definidos, o que n?o surpreendentemente demanda um m?nimo de conhecimento sobre o dom?nio da aplica??o para que tais par?metros sejam corretamente definidos. J? que v?rios algoritmos tradicionais empregam estrat?gias de busca local gulosas, realizar um ajuste fino sobre estes hiper-par?metros se torna uma etapa crucial a fim de obter modelos preditivos de qualidade superior. Por outro lado, Algoritmos de Estimativa de Distribui??o realizam uma busca global, geralmente mais eficiente que realizar uma buscam exaustiva sobre todas as poss?veis solu??es para um determinado problema. Valendo-se de uma fun??o de aptid?o, algoritmos de estimativa de distribui??o ir?o iterativamente procurar por melhores solu??es durante seu processo evolutivo. Baseado nos benef?cios que o emprego de algoritmos de estimativa de distribui??o podem oferecer para as tarefas de agrupamento e indu??o de ?rvores de decis?o, duas tarefas de minera??o de dados consideradas NP-dif?cil e NP-dif?cil/completo respectivamente, este trabalho visa desenvolver novos algoritmos de estimativa de distribui??o a fim de obter melhores resultados em rela??o a m?todos tradicionais que empregam estrat?gias de busca local gulosas, e tamb?m sobre outros algoritmos evolutivos. / Extracting meaningful information from data is not an easy task. Data can come in batches or through a continuous stream, and can be incomplete or complete, duplicated, or noisy. Moreover, there are several algorithms to perform data mining tasks, and the no-free lunch theorem states that there is not a single best algorithm for all problems. As a final obstacle, algorithms usually require hyperparameters to be set in order to operate, which not surprisingly often demand a minimum knowledge of the application domain to be fine-tuned. Since many traditional data mining algorithms employ a greedy local search strategy, fine-tuning is a crucial step towards achieving better predictive models. On the other hand, Estimation of Distribution Algorithms perform a global search, which often is more efficient than performing a wide search through the set of possible parameters. By using a quality function, estimation of distribution algorithms will iteratively seek better solutions throughout its evolutionary process. Based on the benefits that estimation of distribution algorithms may offer to clustering and decision tree-induction, two data mining tasks considered to be NP-hard and NPhard/ complete, respectively, this works aims at developing novel algorithms in order to obtain better results than traditional, greedy algorithms and baseline evolutionary approaches.

Estimation of Distribution Algorithm (EDA) is a branch of evolutionary computation that learn a probabilistic model of good solutions. Probabilistic models are used to represent relationships between solution variables which may give useful, human-understandable insights into real-world problems. Also, developing an effective PM has been shown to significantly reduce function evaluations needed to reach good solutions. This is also useful for real-world problems because their representations are often complex needing more computation to arrive at good solutions. In particular, many real-world problems are naturally represented as permutations and have expensive evaluation functions. EDAs can, however, be computationally expensive when models are too complex. There has therefore been much recent work on developing suitable EDAs for permutation representation. EDAs can now produce state-of-the-art performance on some permutation benchmark problems. However, models are still complex and computationally expensive making them hard to apply to real-world problems. This study investigates some limitations of EDAs in solving permutation and scheduling problems. The focus of this thesis is on addressing redundancies in the Random Key representation, preserving diversity in EDA, simplifying the complexity attributed to the use of multiple local improvement procedures and transferring knowledge from solving a benchmark project scheduling problem to a similar real-world problem. In this thesis, we achieve state-of-the-art performance on the Permutation Flowshop Scheduling Problem benchmarks as well as significantly reducing both the computational effort required to build the probabilistic model and the number of function evaluations. We also achieve competitive results on project scheduling benchmarks. Methods adapted for solving a real-world project scheduling problem presents significant improvements.

A new tool for kinetic evaluation of kinetic rate constants is enabled by a 3rd generation biosensor. The tool is developed to meet the need of reliably experimental information and communication between pharmaceutical companies and regulatory agencies to increase the productivity and decrease the associated risks. Too obtain the necessary competences and resources for this, a project consisting of Attana AB, AstraZeneca AB, Waters Nordic AB and Karlstad University was established. The main aim of the project is to achieve a comprehension understanding of interactions of different character e.g. fast and slow kinetics. This report concerns a fast interaction system. By analyzing a parathyroid hormone system using standard biosensor assays and single cycle kinetics with Attana Cell™ 200 instruments the fast interaction was characterized. The experimental data was analyzed using standard kinetic evaluation and an adaptive interaction distribution algorithm. The latter tool is developed at Karlstad university in order to describe the heterogeneity of interactions. The idea is to use the heterogeneity information as a decision support in drug development. A sub aim was to investigate the feasibility of the single cycle kinetic assays compared to the standard biosensors assays. The results shows a decrease of experimental time by 70% for homogene interaction and the protocol enables assay without or with less regeneration.

Les métaheuristiques sont une famille d'algorithmes stochastiques destinés à résoudre des problèmes d 'optimisation difficile . Utilisées dans de nombreux domaines, ces méthodes présentent l'avantage d'être généralement efficaces, sans pour autant que l'utilisateur ait à modifier la structure de base de l'algorithme qu'il utilise. Parmi celles-ci, l'Optimisation par Essaim Particulaire (OEP) est une nouvelle classe d'algorithmes proposée pour résoudre les problèmes à variables continues. Les algorithmes d'OEP s'inspirent du comportement social des animaux évoluant en essaim, tels que les oiseaux migrateurs ou les poissons. Les particules d'un même essaim communiquent de manière directe entre elles tout au long de la recherche pour construire une solution au problème posé, en s'appuyant sur leur expérience collective. Reconnues depuis de nombreuses années pour leur efficacité, les métaheuristiques présentent des défauts qui rebutent encore certains utilisateurs. Le réglage des paramètres des algorithmes est un de ceux-ci. Il est important, pour chaque probléme posé, de trouver le jeu de paramètres qui conduise à des performances optimales de l'algorithme. Cependant, cette tâche est fastidieuse et coûteuse en temps, surtout pour les utilisateurs novices. Pour s'affranchir de ce type de réglage, des recherches ont été menées pour proposer des algorithmes dits adaptatifs . Avec ces algorithmes, les valeurs des paramètres ne sont plus figées, mais sont modifiées, en fonction des résultats collectés durant le processus de recherche. Dans cette optique-là, Maurice Clerc a proposé TRIBES, qui est un algorithme d'OEP mono-objectif sans aucun paramètre de contrôle. Cet algorithme fonctionne comme une boite noire , pour laquelle l'utilisateur n'a qu'à définir le problème à traiter et le critàre d'arrêt de l'algorithme. Nous proposons dans cette thèse une étude comportementale de TRIBES, qui permet d'en dégager les principales qualités et les principaux défauts. Afin de corriger certains de ces défauts, deux modules ont été ajoutés à TRIBES. Une phase d'initialisation régulière est insérée, afin d'assurer, dès le départ de l'algorithme, une bonne couverture de l'espace de recherche par les particules. Une nouvelle stratégie de déplacement, basée sur une hybridation avec un algorithme à estimation de distribution, est aussi définie, afin de maintenir la diversité au sein de l'essaim, tout au long du traitement. Le besoin croissant de méthodes de résolution de problèmes multiobjectifs a conduit les concepteurs à adapter leurs méthodes pour résoudre ce type de problème. La complexité de cette opération provient du fait que les objectifs à optimiser sont souvent contradictoires. Nous avons élaboré une version multiobjectif de TRIBES, dénommée MO-TRIBES. Nos algorithmes ont été enfin appliqués à la résolution de problèmes de seuillage d'images médicales et au problème de dimensionnement de composants de circuits analogiques / Metaheuristics are a new family of stochastic algorithms which aim at solving difficult optimization problems. Used to solve various applicative problems, these methods have the advantage to be generally efficient on a large amount of problems. Among the metaheuristics, Particle Swarm Optimization (PSO) is a new class of algorithms proposed to solve continuous optimization problems. PSO algorithms are inspired from the social behavior of animals living in swarm, such as bird flocks or fish schools. The particles of the swarm use a direct way of communication in order to build a solution to the considered problem, based on their collective experience. Known for their e ciency, metaheuristics show the drawback of comprising too many parameters to be tuned. Such a drawback may rebu some users. Indeed, according to the values given to the parameters of the algorithm, its performance uctuates. So, it is important, for each problem, to nd the parameter set which gives the best performance of the algorithm. However, such a problem is complex and time consuming, especially for novice users. To avoid the user to tune the parameters, numerous researches have been done to propose adaptive algorithms. For such algorithms, the values of the parameters are changed according to the results previously found during the optimization process. TRIBES is an adaptive mono-objective parameter-free PSO algorithm, which was proposed by Maurice Clerc. TRIBES acts as a black box , for which the user has only the problem and the stopping criterion to de ne. The rst objective of this PhD is to make a global study of the behavior of TRIBES under several conditions, in order to determine the strengths and drawbacks of this adaptive algorithm. In order to improve TRIBES, two new strategies are added. First, a regular initialization process is defined in order to insure an exploration as wide as possible of the search space, since the beginning of the optimization process. A new strategy of displacement, based on an hybridation with an estimation of distribution algorithm, is also introduced to maintain the diversity in the swarm all along the process. The increasing need for multiobjective methods leads the researchers to adapt their methods to the multiobjective case. The di culty of such an operation is that, in most cases, the objectives are con icting. We designed MO-TRIBES, which is a multiobjective version of TRIBES. Finally, our algorithms are applied to thresholding segmentation of medical images and to the design of electronic components

Este proyecto se centra en el estudio de la empresa “Pacifico Seguros” que opera principalmente en el sector de seguros. El desarrollo del trabajo está enfocado en el subproceso de “Emisión” que es uno de los procesos importantes de la empresa porque acá se inicia todo el proceso de las emisiones de los clientes para las afiliaciones de sus trabajadores. La oportunidad de mejora se presenta en la mayoría de actividades del subproceso de “Emisión” que suelen ser repetitivas y operativas; y en su mayoría son ejecutadas de forma manual. Por tal motivo, el proyecto contempla una solución para la optimización del sub proceso que permitirá reducir el tiempo de atención como principal objetivo. La propuesta consta de un software RPA que permita a los usuarios crear “bots” que pueden aprender, imitar y luego ejecutar procesos del negocio basados en reglas para la gestión administrativa que ayudará a la descarga y respuestas de los correos, también contará con un motor de asignación para la distribución equitativa y atención de las solicitudes de afiliación. El propósito del trabajo es llevar a cabo la gestión del desarrollo del software y la arquitectura empresarial dentro del marco de trabajo de TOGAF y PMBOK sobre el objeto estudio para la evaluación de los procesos y para una correcta arquitectura de software lo cual se podrá desarrollar en fases y actividades para formular el plan estratégico y el control de su cumplimiento. / This project focuses on the study of the company “Pacificos Seguros” that operates mainly in the insurance sector. The development of the work focuses on the sub-process “Emisión” which is one of the important processes of the company because here begins the process of customer emissions for the affiliations of its workers. The opportunity for improvement occurs in most of the activities of the sub-process “Emisión”, that tend to be repetitive and operational and they are mostly run manually. Therefore, the project contemplates a solution for the optimization of the sub-process that will reduce the attention time as main objective. The proposal consists of an RPA software that allows users to create "bots" that can learn, imitate and then execute business processes based on rules for the administrative management that help download and reply to emails also there will be a queue engine for the distribution and attention of the affiliation requests. The purpose of the work is to carry out the management of the software development and business architecture in the TOGAF and PMBOK framework on the study object for the evaluation of processes and a correct software architecture which can will be developed in phases and activities to formulate a strategic plan and control its compliance. / Tesis