A Distributed Constraint Satisfaction Problem (DisCSP) is a CSP which is divided into several inter-related complex local problems, each assigned to a different agent. Thus, each agent has knowledge of the variables and corresponding domains of its local problem together with the constraints relating its own variables (intra-agent constraints) and the constraints linking its local problem to other local problems (inter-agent constraints). DisCSPs have a variety of practical applications including, for example, meeting scheduling and sensor networks. Existing approaches to Distributed Constraint Satisfaction can be mainly classified into two families of algorithms: systematic search and local search. Systematic search algorithms are complete but may take exponential time. Local search algorithms often converge quicker to a solution for large problems but are incomplete. Problem solving could be improved through using hybrid algorithms combining the completeness of systematic search with the speed of local search. This thesis explores hybrid (systematic + local search) algorithms which cooperate to solve DisCSPs. Three new hybrid approaches which combine both systematic and local search for Distributed Constraint Satisfaction are presented: (i) DisHyb; (ii) Multi-Hyb and; (iii) Multi-HDCS. These approaches use distributed local search to gather information about difficult variables and best values in the problem. Distributed systematic search is run with a variable and value ordering determined by the knowledge learnt through local search. Two implementations of each of the three approaches are presented: (i) using penalties as the distributed local search strategy and; (ii) using breakout as the distributed local search strategy. The three approaches are evaluated on several problem classes. The empirical evaluation shows these distributed hybrid approaches to significantly outperform both systematic and local search DisCSP algorithms. DisHyb, Multi-Hyb and Multi-HDCS are shown to substantially speed-up distributed problem solving with distributed systematic search taking less time to run by using the information learnt by distributed local search. As a consequence, larger problems can now be solved in a more practical timeframe.

No description available.

The main topic of this PhD thesis is metaheuristic algorithm in wider scope. The first chapters are dedicated to a description of broader context of metaheuristics, i.e. various optimization classes, determination of their omplexity and different approaches to their solutions. The consequent discussion about metaheuristics and their typical characteristics is followed by several selected examples of metaheuristics concepts. The observed characteristics serve as a base for building general metaheuristics model which is suitable for developing brand new or hybrid algorithms. The thesis is concluded by illustration of author’s publications with discussion about their adaptation to the proposed model. On the attached CD, there is also available a program implementation of the created model.

De maneira geral, a necessidade de aumentar o desempenho e diminuir o tamanho dos sistemas mecatrônicos tem levado a indústria moderna a idealizar e desenvolver sistemas de posicionamento com boas características de aceleração e precisão de posicionamento. Por outro lado, a crescente demanda de componentes com melhores características metrológicas e de acabamento, tais corno lentes para raio X e infra vermelho, tem exigido o desenvolvimento de variados tipos de sistemas de microposicionamento capazes de movimentar elementos de máquinas em distâncias muito pequenas com alto grau de exatidão, dentre os quais podem-se destacar os acionados por meio de atuadores piezoelétricos. Este trabalho propõe a utilização de um novo tipo de atuador baseado na propriedade de estricção eletromagnética de certas ligas metálicas (atuadores magnetoestritivos) associado a um sistema de controle digital que utiliza um algoritmo de controle baseado em lógica difusa e redes neurais artificiais para o controle de microposicionamento. Metodologias e princípios de projeto para engenharia de precisão são abordados de forma a auxiliar no desenvolvimento de dois protótipos de posicionadores para uso em usinagem de ultraprecisão. Resultados obtidos em testes experimentais apontam para urna melhoria no comportamento dinâmico dos microposicionadores acionados por atuadores magnetoestritivos. Isto permite sua utilização como alternativa válida no posicionamento submicrométrico. / In general, actual requirements such as high performance and small sizes of mechatronic systems, has led modern industry to design positioning systems with good characteristics of acceleration and positioning accuracy. The increasing demand of components with better metrological and finish characteristics, as X-ray and infra-red lens, has allowed the development of a number of types of micropositioning systems that are able to move machine elements to very small distances with high levels of accuracy. In this work it is proposed the use of a new type of actuator that applies the properties of electromagnetic strain of certain metallic alloys (magnetostrictive actuators). lt is also proposed the application of a digital control system that uses a control algorithm which is based on fuzzy logic and artificial neural networks for the micropositioning control. Design principles and methodologies related to precision engineering are discussed with the purpose of aiding the development of two prototypes of positioners for ultraprecision rnachining, experimental results show that micropositioner driven by magnetostrictive actuators have better dynamics behaviours. This allows the use of such actuators as an valid alternative for positioning in submicrometer range.

Este trabalho apresenta um estudo do efeito de incertezas na otimização estrutural. Tal efeito pode ser quantificado em termos de probabilidades de falha bem como do risco, ou custo esperado de falha. O estudo se baseia na comparação dos resultados obtidos através de três distintas formulações do problema de otimização estrutural: otimização determinística, otimização baseada em confiabilidade e otimização de risco estrutural. Para efeitos de comparação, informações sobre risco de falha estrutural (produto da probabilidade de falha pelo custo de falha) são incorporadas nas três formulações. A otimização determinística (DDO - Deterministic Design Optimization) permite encontrar uma configuração estrutural que é ótima em termos mecânicos, mas não considera explicitamente a incerteza dos parâmetros e seus efeitos na segurança estrutural. Em conseqüência, a segurança da estrutura ótima pode ser comprometida, em comparação à segurança da estrutura original. A otimização baseada em confiabilidade (RBDO - Reliability-Based Design Optimization) garante que a estrutura ótima mantenha um nível mínimo (e mensurável) de segurança. Entretanto, os resultados são dependentes da probabilidade de falha usada como restrição na análise. A otimização de risco estrutural (RBRO - Reliability-Based Risk Optimization) aumenta o escopo do problema, buscando um balanço entre economia e segurança, objetivos estes que de uma forma geral competem entre si. Isto é possível através da quantificação de custos associados à construção, operação e manutenção da estrutura, bem como das consequências monetárias de falha. A experiência mostra que problemas de otimização estudados, são utilizados neste trabalho dois métodos de otimização heurísticos: algoritmos genéticos e método do enxame de partículas. Tendo a eficiência como objetivo, dois métodos com fundamentação matemática também são estudados: os métodos de Powell e de Polak-Ribiere. Finalmente, buscando uma relação de compromisso entre confiabilidade (capacidade de encontrar o mínimo global em todos os problemas) e eficiência, quatro algoritmos híbridos são construídos, combinando os quatro métodos citados anteriormente. Efeitos de incertezas na otimização estrutural são estudados através da comparação de soluções obtidas via diferentes formulações do problema de otimização. São apresentados alguns estudos de caso, enfatizando as diferenças entre os projetos ótimos obtidos por cada formulação. O estudo mostra que, em geral, a estrutura ótima só é encontrada pela formulação mais abrangente: a otimização de risco ou RBRO. O estudo mostra que, para que a formulação DDO encontre a mesma configuração ótima da formulação RBRO, é necessário especificar um coeficiente de segurança ótimo para cada modo de falha. De maneira semelhante, o estudo mostra que quando os custos associados a diferentes modos de falha são distintos, a formulação RBDO somente resulta na estrutura ótima quando uma probabilidade de falha ótima é especificada como restrição para cada modo falha da estrutura. / In this study the effects of uncertainty on optimum structural design are investigated, by comparing three distinct formulations of a structural optimization problem. Such effects can be quantified in terms of failure probabilities and risk, or expected costs of failure. Deterministic Design Optimization (DDO) allows one the find the shape or configuration of a structure that is optimum in terms of mechanics, but the formulation do not consider explicitly parameter uncertainty and its effects on structural safety. As a consequence, safety of the optimum structure can be compromised, in comparison to safety of the original structure. Reliability-based Design Optimization (RBDO) has emerged as an alternative to properly model the safety-under-uncertainty part of the problem. With RBDO, one can ensure that a minimum (and measurable) level of safety is achieved by the optimum structure. However, results are dependent on the failure probability used as constraint in the analysis. Risk optimization increases the scope of the problem, by addressing the compromising goals of economy and safety, and allowing one to find a proper point of balance between these goals. This is accomplished by quantifying the costs associated to construction, operation and maintenance of the structure, as well as the monetary consequences of failure. Experience shows that structural optimization problems can have multiple local minima. With the objective of finding the global minimum in all studied problems, two heuristic optimization methods are used in this study: genetic algorithms and particle swarm optimization. Aiming at efficiency, two methods with mathematical foundations are also considered: the methods of Powel and Polak-Ribiere. Finally, looking for a compromise between reliability (capacity to find the global minimum) and efficiency, four hybrid algorithms are constructed, combining the four methods just cited. The study investigates the effects of uncertainty on optimum structural design by comparing solutions obtained via the different formulations of the optimization problem. The paper presents some case studies, highlighting the differences in the optimum designs obtained with each formulation. The study leads to a better understanding of the limitations of each formulation in the solution of structural optimization problems. The investigation shows that, in general, the optimum structure can only be found by the most comprehensive formulation: risk optimization or RBRO. The study shows that DDO only leads to the optimum structure if an optimum safety coefficient is used as constraint for each individual failure mode. In a similar way, the investigation shows that when the costs associated to distinct failure modes are different, the RBDO formulation only leads to the optimum structural design if an optimum failure probability is specified as constraint for each failure mode of the structure.

De maneira geral, a necessidade de aumentar o desempenho e diminuir o tamanho dos sistemas mecatrônicos tem levado a indústria moderna a idealizar e desenvolver sistemas de posicionamento com boas características de aceleração e precisão de posicionamento. Por outro lado, a crescente demanda de componentes com melhores características metrológicas e de acabamento, tais corno lentes para raio X e infra vermelho, tem exigido o desenvolvimento de variados tipos de sistemas de microposicionamento capazes de movimentar elementos de máquinas em distâncias muito pequenas com alto grau de exatidão, dentre os quais podem-se destacar os acionados por meio de atuadores piezoelétricos. Este trabalho propõe a utilização de um novo tipo de atuador baseado na propriedade de estricção eletromagnética de certas ligas metálicas (atuadores magnetoestritivos) associado a um sistema de controle digital que utiliza um algoritmo de controle baseado em lógica difusa e redes neurais artificiais para o controle de microposicionamento. Metodologias e princípios de projeto para engenharia de precisão são abordados de forma a auxiliar no desenvolvimento de dois protótipos de posicionadores para uso em usinagem de ultraprecisão. Resultados obtidos em testes experimentais apontam para urna melhoria no comportamento dinâmico dos microposicionadores acionados por atuadores magnetoestritivos. Isto permite sua utilização como alternativa válida no posicionamento submicrométrico. / In general, actual requirements such as high performance and small sizes of mechatronic systems, has led modern industry to design positioning systems with good characteristics of acceleration and positioning accuracy. The increasing demand of components with better metrological and finish characteristics, as X-ray and infra-red lens, has allowed the development of a number of types of micropositioning systems that are able to move machine elements to very small distances with high levels of accuracy. In this work it is proposed the use of a new type of actuator that applies the properties of electromagnetic strain of certain metallic alloys (magnetostrictive actuators). lt is also proposed the application of a digital control system that uses a control algorithm which is based on fuzzy logic and artificial neural networks for the micropositioning control. Design principles and methodologies related to precision engineering are discussed with the purpose of aiding the development of two prototypes of positioners for ultraprecision rnachining, experimental results show that micropositioner driven by magnetostrictive actuators have better dynamics behaviours. This allows the use of such actuators as an valid alternative for positioning in submicrometer range.

L’optimisation des structures est un processus essentiel dans la conception des systèmes mécaniques et électroniques. Cette thèse s’intéresse à la résolution des problèmes mono-objectifs et multi-objectifs des structures mécaniques et mécatroniques. En effet, les industriels ne sont pas seulement préoccupés à améliorer les performances mécaniques des pièces qu’ils conçoivent, mais ils cherchent aussi à optimiser leurs poids, leurs tailles, ainsi que leurs coûts de production. Pour résoudre ce type de problème, nous avons fait appel à des métaheuristiques robustes qui nous permettent de minimiser le coût de production de la structure mécanique et de maximiser le cycle de vie de la structure. Alors que des méthodes inappropriées de l’évolution sont plus difficiles à appliquer à des modèles mécaniques complexes en raison de temps calcul exponentiel. Il est connu que les algorithmes génétiques sont très efficaces pour les problèmes NP-difficiles, mais ils sont très lourds et trop gourmands quant au temps de calcul, d’où l’idée d’hybridation de notre algorithme génétique par l’algorithme d’optimisation par essaim de particules (PSO) qui est plus rapide par rapport à l’algorithme génétique (GA). Dans notre expérimentation, nous avons obtenu une amélioration de la fonction objectif et aussi une grande amélioration de la minimisation de temps de calcul. Cependant, notre hybridation est une idée originale, car elle est différente des travaux existants. Concernant l’avantage de l’hybridation, il s’agit généralement de trois méthodes : l’hybridation en série, l’hybridation en parallèle et l’hybridation par insertion. Nous avons opté pour l’hybridation par insertion par ce qu’elle est nouvelle et efficace. En effet, les algorithmes génétiques se composent de trois étapes principales : la sélection, le croisement et la mutation. Dans notre cas, nous remplaçons les opérateurs de mutation par l’optimisation par essaim de particules. Le but de cette hybridation est de réduire le temps de calcul ainsi que l’amélioration la solution optimale. / This thesis focuses on solving single objective problems and multiobjective of mechanical and mechatronic structures. The optimization of structures is an essential process in the design of mechanical and electronic systems. Industry are not only concerned to improve the mechanical performance of the parts they design, but they also seek to optimize their weight, size and cost of production. In order to solve this problem we have used Meta heuristic algorithms robust, allowing us to minimize the cost of production of the mechanical structure and maximize the life cycle of the structure. While inappropriate methods of evolution are more difficult to apply to complex mechanical models because of exponential calculation time. It is known that genetic algorithms are very effective for NP-hard problems, but their disadvantage is the time consumption. As they are very heavy and too greedy in the sense of time, hence the idea of hybridization of our genetic algorithm optimization by particle swarm algorithm (PSO), which is faster compared to the genetic algorithm (GA). In our experience, it was noted that we have obtained an improvement of the objective function and also a great improvement for minimizing computation time. However, our hybridization is an original idea, because it is a different and new way of existing work, we explain the advantage of hybridization and are generally three methods : hybridization in series, parallel hybridization or hybridization by insertion. We opted for the insertion hybridization it is new and effective. Indeed, genetic algorithms are three main parts : the selection, crossover and mutation. In our case,we replace the operators of these mutations by particle swarm optimization. The purpose of this hybridization is to reduce the computation time and improve the optimum solution.

Este trabalho apresenta um estudo do efeito de incertezas na otimização estrutural. Tal efeito pode ser quantificado em termos de probabilidades de falha bem como do risco, ou custo esperado de falha. O estudo se baseia na comparação dos resultados obtidos através de três distintas formulações do problema de otimização estrutural: otimização determinística, otimização baseada em confiabilidade e otimização de risco estrutural. Para efeitos de comparação, informações sobre risco de falha estrutural (produto da probabilidade de falha pelo custo de falha) são incorporadas nas três formulações. A otimização determinística (DDO - Deterministic Design Optimization) permite encontrar uma configuração estrutural que é ótima em termos mecânicos, mas não considera explicitamente a incerteza dos parâmetros e seus efeitos na segurança estrutural. Em conseqüência, a segurança da estrutura ótima pode ser comprometida, em comparação à segurança da estrutura original. A otimização baseada em confiabilidade (RBDO - Reliability-Based Design Optimization) garante que a estrutura ótima mantenha um nível mínimo (e mensurável) de segurança. Entretanto, os resultados são dependentes da probabilidade de falha usada como restrição na análise. A otimização de risco estrutural (RBRO - Reliability-Based Risk Optimization) aumenta o escopo do problema, buscando um balanço entre economia e segurança, objetivos estes que de uma forma geral competem entre si. Isto é possível através da quantificação de custos associados à construção, operação e manutenção da estrutura, bem como das consequências monetárias de falha. A experiência mostra que problemas de otimização estudados, são utilizados neste trabalho dois métodos de otimização heurísticos: algoritmos genéticos e método do enxame de partículas. Tendo a eficiência como objetivo, dois métodos com fundamentação matemática também são estudados: os métodos de Powell e de Polak-Ribiere. Finalmente, buscando uma relação de compromisso entre confiabilidade (capacidade de encontrar o mínimo global em todos os problemas) e eficiência, quatro algoritmos híbridos são construídos, combinando os quatro métodos citados anteriormente. Efeitos de incertezas na otimização estrutural são estudados através da comparação de soluções obtidas via diferentes formulações do problema de otimização. São apresentados alguns estudos de caso, enfatizando as diferenças entre os projetos ótimos obtidos por cada formulação. O estudo mostra que, em geral, a estrutura ótima só é encontrada pela formulação mais abrangente: a otimização de risco ou RBRO. O estudo mostra que, para que a formulação DDO encontre a mesma configuração ótima da formulação RBRO, é necessário especificar um coeficiente de segurança ótimo para cada modo de falha. De maneira semelhante, o estudo mostra que quando os custos associados a diferentes modos de falha são distintos, a formulação RBDO somente resulta na estrutura ótima quando uma probabilidade de falha ótima é especificada como restrição para cada modo falha da estrutura. / In this study the effects of uncertainty on optimum structural design are investigated, by comparing three distinct formulations of a structural optimization problem. Such effects can be quantified in terms of failure probabilities and risk, or expected costs of failure. Deterministic Design Optimization (DDO) allows one the find the shape or configuration of a structure that is optimum in terms of mechanics, but the formulation do not consider explicitly parameter uncertainty and its effects on structural safety. As a consequence, safety of the optimum structure can be compromised, in comparison to safety of the original structure. Reliability-based Design Optimization (RBDO) has emerged as an alternative to properly model the safety-under-uncertainty part of the problem. With RBDO, one can ensure that a minimum (and measurable) level of safety is achieved by the optimum structure. However, results are dependent on the failure probability used as constraint in the analysis. Risk optimization increases the scope of the problem, by addressing the compromising goals of economy and safety, and allowing one to find a proper point of balance between these goals. This is accomplished by quantifying the costs associated to construction, operation and maintenance of the structure, as well as the monetary consequences of failure. Experience shows that structural optimization problems can have multiple local minima. With the objective of finding the global minimum in all studied problems, two heuristic optimization methods are used in this study: genetic algorithms and particle swarm optimization. Aiming at efficiency, two methods with mathematical foundations are also considered: the methods of Powel and Polak-Ribiere. Finally, looking for a compromise between reliability (capacity to find the global minimum) and efficiency, four hybrid algorithms are constructed, combining the four methods just cited. The study investigates the effects of uncertainty on optimum structural design by comparing solutions obtained via the different formulations of the optimization problem. The paper presents some case studies, highlighting the differences in the optimum designs obtained with each formulation. The study leads to a better understanding of the limitations of each formulation in the solution of structural optimization problems. The investigation shows that, in general, the optimum structure can only be found by the most comprehensive formulation: risk optimization or RBRO. The study shows that DDO only leads to the optimum structure if an optimum safety coefficient is used as constraint for each individual failure mode. In a similar way, the investigation shows that when the costs associated to distinct failure modes are different, the RBDO formulation only leads to the optimum structural design if an optimum failure probability is specified as constraint for each failure mode of the structure.

The main topic of this PhD thesis is metaheuristic algorithm in wider scope. The first chapters are dedicated to a description of broader context of metaheuristics, i.e. various optimization classes, determination of their omplexity and different approaches to their solutions. The consequent discussion about metaheuristics and their typical characteristics is followed by several selected examples of metaheuristics concepts. The observed characteristics serve as a base for building general metaheuristics model which is suitable for developing brand new or hybrid algorithms. The thesis is concluded by illustration of author’s publications with discussion about their adaptation to the proposed model. On the attached CD, there is also available a program implementation of the created model.

Υλοποιούμε οχτώ αλγορίθμους που επιλύουν on line προβλήματα ομαδοποίησης. Αναπτύσουμε τρεις νέες μορφές υβριδικών αλγορίθμων. Εφαρμόζουμε όλους τους παραπάνω αλγορίθμους σε τεχνητά δεδομένα και καταγράφουμε την αποτελεσματικότητά τους. Μεταβαίνουμε από την ομαδοποίηση στην ταξινόμηση. Επιλύουμε δύο προβλήματα ταξινόμησης του πραγματικού κόσμου και βλέπουμε πως κυμαίνονται τα ποσοστά επιτυχούς ταξινόμησης. Παραθέτουμε τα συγκριτικά γραφήματα των αποτελεσμάτων όλων των αλγορίθμων. / We implement eight algorithms that solve on line problems of clustering and we develope three new forms of hybrid algorithms. We apply these algorithms in artificial data and we record their effectiveness. Also we go from clustering to classification. Finally we solve two problems of classification from the real world and we appose the comparative graphs of the results of our algorithms.