This work deals with the issue of swarm intelligence as a subdiscipline of artificial intelligence. It describes biological background of the dilemma briefly and presents the principles of searching paths in ant colonies as well. There is also adduced combinatorial optimization and two selected tasks are defined in detail: Travelling Salesman Problem and Quadratic Assignment Problem. The main part of this work consists of description of swarm intelligence methods for solving mentioned problems and evaluation of experiments that were made on these methods. There were tested Ant System, Ant Colony System, Hybrid Ant System and Max-Min Ant System algorithm. Within the work there were also designed and tested my own method Genetic Ant System which enriches the basic Ant System i.a. with development of unit parameters based on genetical principles. The results of described methods were compared together with the ones of classical artificial intelligence within the frame of both solved problems.

Das Zusammenleben in Gruppen ist im Tierreich ein weit verbreitetes Phänomen. Einer der Vorteile des Gruppenlebens könnte die sogenannte „Schwarmintelligenz“ sein, das heißt die Fähigkeit von Gruppen kognitive Probleme zu lösen, die die Problemlösekompetenz einzelner Individuen übersteigt. In der vorliegenden Dissertation untersuchte ich, ob die Gruppengröße beim Menschen und bei Fischen mit einer verbesserten Entscheidungsfindung einhergeht. Beim Menschen analysierte ich zunächst das Abschneiden von Einzelpersonen, die später als Teil einer Gruppe getestet wurden, in einfachen Einschätzungsaufgaben sowie komplizierteren Satz-Rekonstruktionstests. Meine Frage war, ob es Individuen in Gruppen gelingt bessere Entscheidungen zutreffen als das einem durchschnittlichen Individuum der Gruppe alleine möglich wäre und ob Gruppen sogar die Leistung ihres besten Mitglieds in den individuellen Tests überbieten könnten. Tatsächlich konnte ich zeigen, dass Gruppen die Leistung des besten Mitglieds übertreffen, wenn die Problemstellung für Einzelpersonen zu komplex ist oder sich häufig wiederholt. Weiterhin gelang mir zu zeigen, dass Gruppen von Menschen bei einer simulierten Prädationssituation, ähnlich wie es bereits für andere Tierarten beschrieben wurde, anhand von so genannten „Quorum“-Regeln durch non-verbale Kommunikation entscheiden, ob sie bleiben oder flüchten. Dabei dienen einfache Bewegungsmuster als Schlüsselreiz. Individuen einer Gruppe erhöhen durch diesen Mechanismus gleichzeitig ihre echt positiven und verringern ihre falsch positiven Entscheidungen. Beim Guppy, einem Süßwasserfisch aus Trinidad, untersuchte ich in deren natürlichem Habitat, ob die Fähigkeit einzelner Individuen zwischen einer genießbaren und einer ungenießbaren Futterquelle zu unterscheiden, mit der Gruppengröße ansteigt. Meine Ergebnisse zeigen, dass Guppys mit größerer Wahrscheinlichkeit eine genießbare Futterquelle identifizierten, sobald sie Teil einer größeren Gruppe waren. / Group living is a widespread phenomenon. One of its assumed advantages is collective cognition, the ability of groups to solve cognitive problems that are beyond single individuals’ abilities. In this thesis, I investigated whether decision-making improves with group size in both humans and fish, thus using the strengths of each system. In humans, I tested individual performance in simple quantity estimation tasks and a more difficult sentence reconstruction task first alone and then as part of a group. My question was whether groups were able to improve not only on average individual decisions, but also to beat their best members. Indeed, when a given problem is recurrent or too complex for individuals, groups were able to outperform their best members in different contexts. Furthermore, I showed that in a simulated predation experiment, groups of humans decided to stay or to escape using quorum thresholds based on movement behaviour without verbal communication, as has been shown in other animals. This simple movement mechanism allowed individuals in groups to simultaneously increase true positives and decrease false positives. In the guppy, a freshwater fish from Trinidad, I tested in their natural environment whether individuals’ ability to distinguish between an edible and a non-edible food item increases with group size. My results indicate that guppies had better chances to identify the edible food item when part of bigger groups. By investigating several populations with different ecological backgrounds, in particular differing in predation levels, I found that, despite a lower sampling activity in high predation habitats, predation did not affect the improvement of decisions in groups.

Este trabajo analiza la idoneidad de dos de los principales métodos de asignación de tareas en entornos con restricciones temporales. Se pondrá de manifiesto que ambos tipos de mecanismos presentan carencias para tratar tareas con deadlines, especialmente cuando los robots han de formar coaliciones. Uno de los aspectos a los que esta tesis dedica mayor atención es la predicción del tiempo de ejecución, que depende, entre otros factores, de la interferencia física entre robots. Este fenómeno no se ha tenido en cuenta en los mecanismos actuales de asignación basados en subastas. Así, esta tesis presenta el primer mecanismo de subastas para la creación de coaliciones que tiene en cuenta la interferencia entre robots. Para ello, se ha desarrollado un modelo de predicción del tiempo de ejecución y un nuevo paradigma llamado subasta doble. Además, se han propuesto nuevos mecanismos basados en swarm

Most of the real world problems in water resources involve nonlinear formulations in their solution construction. Obtaining optimal solutions for large scale nonlinear optimization problems is always a challenging task. The conventional methods, such as linear programming (LP), dynamic programming (DP) and nonlinear programming (NLP) may often face problems in solving them. Recently, there has been an increasing interest in biologically motivated adaptive systems for solving real world optimization problems. The multi-member, stochastic approach followed in Evolutionary Algorithms (EA) makes them less susceptible to getting trapped at local optimal solutions, and they can search easier for global optimal solutions. In this thesis, efficient optimization techniques based on swarm intelligence and evolutionary computation principles have been proposed for single and multi-objective optimization in water resource systems. To overcome the inherent limitations of conventional optimization techniques, meta-heuristic techniques like ant colony optimization (ACO), particle swarm optimization (PSO) and differential evolution (DE) approaches are developed for single and multi-objective optimization. These methods are then applied to few case studies in planning and operation of reservoir systems in India. First a methodology based on ant colony optimization (ACO) principles is investigated for reservoir operation. The utility of the ACO technique for obtaining optimal solutions is explored for large scale nonlinear optimization problems, by solving a reservoir operation problem for monthly operation over a long-time horizon of 36 years. It is found that this methodology relaxes the over-year storage constraints and provides efficient operating policy that can be implemented over a long period of time. By using ACO technique for reservoir operation problems, some of the limitations of traditional nonlinear optimization methods are surmounted and thus the performance of the reservoir system is improved. To achieve faster optimization in water resource systems, a novel technique based on swarm intelligence, namely particle swarm optimization (PSO) has been proposed. In general, PSO has distinctly faster convergence towards global optimal solutions for numerical optimization. However, it is found that the technique has the problem of getting trapped to local optima while solving real world complex problems. To overcome such drawbacks, the standard particle swarm optimization technique has been further improved by incorporating a novel elitist-mutation (EM) mechanism into the algorithm. This strategy provides proper exploration and exploitation throughout the iterations. The improvement is demonstrated by applying it to a multi-purpose single reservoir problem and also to a multi reservoir system. The results showed robust performance of the EM-PSO approach in yielding global optimal solutions. Most of the practical problems in water resources are not only nonlinear in their formulations but are also multi-objective in nature. For multi-objective optimization, generating feasible efficient Pareto-optimal solutions is always a complicated task. In the past, many attempts with various conventional approaches were made to solve water resources problems and some of them are reported as successful. However, in using the conventional linear programming (LP) and nonlinear programming (NLP) methods, they usually involve essential approximations, especially while dealing withdiscontinuous, non-differentiable, non-convex and multi-objective functions. Most of these methods consider multiple objective functions using weighted approach or constrained approach without considering all the objectives simultaneously. Also, the conventional approaches use a point-by-point search approach, in which the outcome of these methods is a single optimal solution. So they may require a large number of simulation runs to arrive at a good Pareto optimal front. One of the major goals in multi-objective optimization is to find a set of well distributed optimal solutions along the true Pareto optimal front. The classical optimization methods often fail to attain a good and true Pareto optimal front due to accretion of the above problems. To overcome such drawbacks of the classical methods, there has recently been an increasing interest in evolutionary computation methods for solving real world multi-objective problems. In this thesis, some novel approaches for multi-objective optimization are developed based on swarm intelligence and evolutionary computation principles. By incorporating Pareto optimality principles into particle swarm optimization algorithm, a novel approach for multi-objective optimization has been developed. To obtain efficient Pareto-frontiers, along with proper selection scheme and diversity preserving mechanisms, an efficient elitist mutation strategy is proposed. The developed elitist-mutated multi-objective particle swarm optimization (EM-MOPSO) technique is tested for various numerical test problems and engineering design problems. It is found that the EM-MOPSO algorithm resulting in improved performance over a state-of-the-art multi-objective evolutionary algorithm (MOEA). The utility of EM-MOPSO technique for water resources optimization is demonstrated through application to a case study, to obtain optimal trade-off solutions to a reservoir operation problem. Through multi-objective analysis for reservoir operation policies, it is found that the technique can offer wide range of efficient alternatives along with flexibility to the decision maker. In general, most of the water resources optimization problems involve interdependence relations among the various decision variables. By using differential evolution (DE) scheme, which has a proven ability of effective handling of this kind of interdependence relationships, an efficient multi-objective solver, namely multi-objective differential evolution (MODE) is proposed. The single objective differential evolution algorithm is extended to multi-objective optimization by integrating various operators like, Pareto-optimality, non-dominated sorting, an efficient selection strategy, crowding distance operator for maintaining diversity, an external elite archive for storing non- dominated solutions and an effective constraint handling scheme. First, different variations of DE approaches for multi-objective optimization are evaluated through several benchmark test problems for numerical optimization. The developed MODE algorithm showed improved performance over a standard MOEA, namely non-dominated sorting genetic algorithm–II (NSGA-II). Then MODE is applied to a case study of Hirakud reservoir operation problem to derive operational tradeoffs in the reservoir system optimization. It is found that MODE is achieving robust performance in evaluation for the water resources problem, and that the interdependence relationships among the decision variables can be effectively modeled using differential evolution operators. For optimal utilization of scarce water resources, an integrated operational model is developed for reservoir operation for irrigation of multiple crops. The model integrates the dynamics associated with the water released from a reservoir to the actual water utilized by the crops at farm level. It also takes into account the non-linear relationship of root growth, soil heterogeneity, soil moisture dynamics for multiple crops and yield response to water deficit at various growth stages of the crops. Two types of objective functions are evaluated for the model by applying to a case study of Malaprabha reservoir project. It is found that both the cropping area and economic benefits from the crops need to be accounted for in the objective function. In this connection, a multi-objective frame work is developed and solved using the MODE algorithm to derive simultaneous policies for irrigation cropping pattern and reservoir operation. It is found that the proposed frame work can provide effective and flexible policies for decision maker aiming at maximization of overall benefits from the irrigation system. For efficient management of water resources projects, there is always a great necessity to accurately forecast the hydrologic variables. To handle uncertain behavior of hydrologic variables, soft computing based artificial neural networks (ANNs) and fuzzy inference system (FIS) models are proposed for reservoir inflow forecasting. The forecast models are developed using large scale climate inputs like indices of El-Nino Southern Oscialltion (ENSO), past information on rainfall in the catchment area and inflows into the reservoir. In this purpose, back propagation neural network (BPNN), hybrid particle swarm optimization trained neural network (PSONN) and adaptive network fuzzy inference system (ANFIS) models have been developed. The developed models are applied for forecasting inflows into the Malaprabha reservoir. The performances of these models are evaluated using standard performance measures and it is found that the hybrid PSONN model is performing better than BPNN and ANFIS models. Finally by adopting PSONN model for inflow forecasting and EMPSO technique for solving the reservoir operation model, the practical utility of the different models developed in the thesis are demonstrated through application to a real time reservoir operation problem. The developed methodologies can certainly help in better planning and operation of the scarce water resources.

ANP / Este trabalho propõe o uso de Mapas Cognitivos Fuzzy Dinâmicos (DFCM, do inglês Dynamic Fuzzy Cognitive Maps), uma evolução dos Mapas Cognitivos Fuzzy (FCM), para o desenvolvimento de sistemas autônomos para tomada de decisões. O FCM representa o conhecimento de forma simbólica, através de conceitos e relações causais dispostas em um grafo. Na sua versão clássica, os FCMs são usados no desenvolvimento de modelos estáticos, sendo inapropriados para o desenvolvimento de modelos temporais ou dinâmicos devido à ocorrência simultânea de todas as causalidades em uma estrutura fixa dos grafos, i.e., os conceitos e suas relações causais são invariantes no tempo. O DFCM utiliza o mesmo formalismo matemático do FCM através de grafos, acrescentando funcionalidades, como por exemplo, a capacidade de auto adaptação através de algoritmos de aprendizagem de máquina e a possibilidade de inclusão de novos tipos de conceitos e relações causais ao modelo FCM clássico. A partir dessas inclusões, é possível construir modelos DFCM para tomada de decisões dinâmicas, as quais são necessárias no desenvolvimento de ferramentas inteligentes em áreas de conhecimento correlatas à engenharia, de modo especifico a construção de modelos aplicados em Robótica Autônoma. Em especial, para as áreas de Robótica de Enxame e Vida artificial, como abordados nesta pesquisa. O sistema autônomo desenvolvido neste trabalho aborda problemas com diferentes objetivos (como desviar de obstáculos, coletar alvos ou alimentos, explorar o ambiente), hierarquizando as ações necessárias para atingi-los, através do uso de uma arquitetura para o planejamento, inspirada no modelo clássico de Subsunção de Brooks, e uma máquina de estados para o gerenciamento das ações. Conceitos de aprendizagem de máquina, em especial Aprendizagem por Reforço, são empregadas no DFCM para a adaptação dinâmica das relações de casualidade, possibilitando o controlador a lidar com eventos não modelados a priori. A validação do controlador DFCM proposto é realizada por meio de experimentos simulados através de aplicações nas áreas supracitadas. / This dissertation proposes the use of Dynamic Fuzzy Cognitive Maps (DFCM), an evolution of Fuzzy Cognitive Maps (FCM), for the development of autonomous system to decision-taking. The FCM represents knowledge in a symbolic way, through concepts and causal relationships disposed in a graph. In its standard form, the FCMs are limited to the development of static models, in other words, classical FCMs are inappropriate for development of temporal or dynamic models due to the simultaneous occurrence of all causalities in a permanent structure, i.e., the concepts and the causal relationships are time-invariant. The DFCM uses the same mathematical formalism of the FCM, adding features to its predecessor, such as self-adaptation by means of machine learning algorithms and the possibility of inclusion of new types of concepts and causal relationships into the classical FCM model. From these inclusions, it is possible to develop DFCM models for dynamic decision-making problems, which are needed to the development of intelligent tools in engineering and other correlated areas, specifically, the construction of autonomous systems applied in Autonomous Robotic. In particular, to the areas of Swarm Robotics and Artificial Life, as approached in this research. The developed autonomous system deals with multi-objective problems (such as deviate from obstacle, collect target or feed, explore the environment), hierarchizing the actions needed to reach them, through the use of an architecture for planning, inspired by the Brook’s classical Subsumption model, and a state machine for the management of the actions. Learning machine algorithms, in particular Reinforcement Learning, are implemented in the DFCM to dynamically tune the causalities, enabling the controller to handle not modelled event a priori. The proposed DFCM model is validated by means of simulated experiments applied in the aforementioned areas.

ANP / Este trabalho propõe o uso de Mapas Cognitivos Fuzzy Dinâmicos (DFCM, do inglês Dynamic Fuzzy Cognitive Maps), uma evolução dos Mapas Cognitivos Fuzzy (FCM), para o desenvolvimento de sistemas autônomos para tomada de decisões. O FCM representa o conhecimento de forma simbólica, através de conceitos e relações causais dispostas em um grafo. Na sua versão clássica, os FCMs são usados no desenvolvimento de modelos estáticos, sendo inapropriados para o desenvolvimento de modelos temporais ou dinâmicos devido à ocorrência simultânea de todas as causalidades em uma estrutura fixa dos grafos, i.e., os conceitos e suas relações causais são invariantes no tempo. O DFCM utiliza o mesmo formalismo matemático do FCM através de grafos, acrescentando funcionalidades, como por exemplo, a capacidade de auto adaptação através de algoritmos de aprendizagem de máquina e a possibilidade de inclusão de novos tipos de conceitos e relações causais ao modelo FCM clássico. A partir dessas inclusões, é possível construir modelos DFCM para tomada de decisões dinâmicas, as quais são necessárias no desenvolvimento de ferramentas inteligentes em áreas de conhecimento correlatas à engenharia, de modo especifico a construção de modelos aplicados em Robótica Autônoma. Em especial, para as áreas de Robótica de Enxame e Vida artificial, como abordados nesta pesquisa. O sistema autônomo desenvolvido neste trabalho aborda problemas com diferentes objetivos (como desviar de obstáculos, coletar alvos ou alimentos, explorar o ambiente), hierarquizando as ações necessárias para atingi-los, através do uso de uma arquitetura para o planejamento, inspirada no modelo clássico de Subsunção de Brooks, e uma máquina de estados para o gerenciamento das ações. Conceitos de aprendizagem de máquina, em especial Aprendizagem por Reforço, são empregadas no DFCM para a adaptação dinâmica das relações de casualidade, possibilitando o controlador a lidar com eventos não modelados a priori. A validação do controlador DFCM proposto é realizada por meio de experimentos simulados através de aplicações nas áreas supracitadas. / This dissertation proposes the use of Dynamic Fuzzy Cognitive Maps (DFCM), an evolution of Fuzzy Cognitive Maps (FCM), for the development of autonomous system to decision-taking. The FCM represents knowledge in a symbolic way, through concepts and causal relationships disposed in a graph. In its standard form, the FCMs are limited to the development of static models, in other words, classical FCMs are inappropriate for development of temporal or dynamic models due to the simultaneous occurrence of all causalities in a permanent structure, i.e., the concepts and the causal relationships are time-invariant. The DFCM uses the same mathematical formalism of the FCM, adding features to its predecessor, such as self-adaptation by means of machine learning algorithms and the possibility of inclusion of new types of concepts and causal relationships into the classical FCM model. From these inclusions, it is possible to develop DFCM models for dynamic decision-making problems, which are needed to the development of intelligent tools in engineering and other correlated areas, specifically, the construction of autonomous systems applied in Autonomous Robotic. In particular, to the areas of Swarm Robotics and Artificial Life, as approached in this research. The developed autonomous system deals with multi-objective problems (such as deviate from obstacle, collect target or feed, explore the environment), hierarchizing the actions needed to reach them, through the use of an architecture for planning, inspired by the Brook’s classical Subsumption model, and a state machine for the management of the actions. Learning machine algorithms, in particular Reinforcement Learning, are implemented in the DFCM to dynamically tune the causalities, enabling the controller to handle not modelled event a priori. The proposed DFCM model is validated by means of simulated experiments applied in the aforementioned areas.

Made available in DSpace on 2016-08-17T14:53:21Z (GMT). No. of bitstreams: 1 Sergio Augusto.pdf: 2350058 bytes, checksum: 7c3c67925b0b27a77105c3cb0799c4e6 (MD5) Previous issue date: 2012-05-04 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / This work provides a framework to obtain the optimal bidding strategy for a GENCO in long-term electricity auction. The tool is based on intelligent techniques for optimizing the proposed Utility Function. The goal is to find the optimal strategy that maximizes the expected payoff of GENCO and simultaneously minimize the risks. The risks are modeled by two classical metrics: the Variance (Portfolio Theory) and Value at Risk (VaR). The proposed methodology is applied to auctions for long-term forward contracts, such that used in the Brazilian power system for buying and selling energy in the regulated market. The Bidding Strategy is formed through a Supply Curve which relates the optimal amount of energy to different offer prices. Thus, it allows the GENCO define the best bid (offer) for a given offer price. The proposed approach is validated for three test cases: First, concerning the variation of generation and price of energy scenarios for evaluation of the bidding strategy and the GENCOS risk perception; The second, consider a cascade hydro-term system for evaluation of MRE; and The third, considers the northeastern Brazilian subsystem where the supply curve is formed for the CHESF company's power plants portfolio. The results show how the offer may be changed according the variation of the spot prices and physical generation and demonstrate the efficacy of meta-heuristics proposed to optimize the supply model. / Este trabalho apresenta uma ferramenta de auxílio e suporte à tomada de decisões na formação de estratégias de oferta para agentes geradores (GENCOS) participantes de leilões de eletricidade de longo-prazo. A ferramenta é baseada em técnicas inteligentes para a otimização da Função de Utilidade proposta média-risco . O objetivo é encontrar a Estratégia Ótima que maximize o retorno esperado da GENCO e, simultaneamente, minimize os riscos relacionados às incertezas no montante de energia produzida e no preço spot, modelados por duas métricas clássicas de risco: a Variância (teoria dos portfólios) e o Valor em Risco (VaR). A abordagem proposta é aplicada ao mercado brasileiro de eletricidade, especificamente, ao ambiente de Leilões de Energia Existente na categoria Quantidade de Energia, tais quais os leilões aplicados pelo órgão regulador brasileiro para compra e venda de energia no mercado regulado. Sugere-se aqui a formação de uma Curva de Oferta que relacione a quantidade de energia ótima para diferentes preços de oferta. E, deste modo, permita a GENCO definir qual o melhor lance (oferta) para dado preço de oferta durante o processo do leilão. Para a avaliação da abordagem foram utilizados três casos testes: O primeiro considera cenários de geração física e preço de energia a fim de avaliar a estratégia de oferta e a percepção ao risco de contratação da GENCO quanto à variação de tais cenários; o segundo, considera um sistema em cascata onde é possível observar o efeito do Mecanismo de Realocação de Energia (MRE) sobre a oferta das GENCOS; e o terceiro considera o subsistema nordeste brasileiro onde a curva de oferta é formada para o portfólio de usinas pertencentes à empresa CHESF. Os resultados demonstram como a oferta de energia pode ser alterada de acordo com cenários de oferta gerados e comprovam a eficiência da meta-heurística proposta para otimização do modelo de oferta.

This research presents a Hybrid Particle Swarm Optimization with Bat Algorithm (HPSOBA) based approach to solve Optimal Reactive Power Dispatch (ORPD) problem. The primary objective of this project is minimization of the active power transmission losses by optimally setting the control variables within their limits and at the same time making sure that the equality and inequality constraints are not violated. Particle Swarm Optimization (PSO) and Bat Algorithm (BA) algorithms which are nature-inspired algorithms have become potential options to solving very difficult optimization problems like ORPD. Although PSO requires high computational time, it converges quickly; while BA requires less computational time and has the ability of switching automatically from exploration to exploitation when the optimality is imminent. This research integrated the respective advantages of PSO and BA algorithms to form a hybrid tool denoted as HPSOBA algorithm. HPSOBA combines the fast convergence ability of PSO with the less computation time ability of BA algorithm to get a better optimal solution by incorporating the BA’s frequency into the PSO velocity equation in order to control the pace. The HPSOBA, PSO and BA algorithms were implemented using MATLAB programming language and tested on three (3) benchmark test functions (Griewank, Rastrigin and Schwefel) and on IEEE 30- and 118-bus test systems to solve for ORPD without DG unit. A modified IEEE 30-bus test system was further used to validate the proposed hybrid algorithm to solve for optimal placement of DG unit for active power transmission line loss minimization. By comparison, HPSOBA algorithm results proved to be superior to those of the PSO and BA methods. In order to check if there will be a further improvement on the performance of the HPSOBA, the HPSOBA was further modified by embedding three new modifications to form a modified Hybrid approach denoted as MHPSOBA. This MHPSOBA was validated using IEEE 30-bus test system to solve ORPD problem and the results show that the HPSOBA algorithm outperforms the modified version (MHPSOBA). / Electrical and Mining Engineering / M. Tech. (Electrical Engineering)