51 |
Methods and tools for the integration of formal verification in domain-specific languages / Méthodes et outils pour l’intégration de la vérification formelle pour les langages dédiésZalila, Faiez 09 December 2014 (has links)
Les langages dédiés de modélisation (DSMLs) sont de plus en plus utilisés dans les phases amont du développement des systèmes complexes, en particulier pour les systèmes critiques embarqués. L’objectif est de pouvoir raisonner très tôt dans le développement sur ces modèles et, notamment, de conduire des activités de vérification et validation (V and V). Une technique très utilisée est la vérification des modèles comportementaux par exploration exhaustive (model-checking) en utilisant une sémantique de traduction pour construire un modèle formel à partir des modèles métiers pour réutiliser les outils performants disponibles pour les modèles formels. Définir cette sémantique de traduction, exprimer les propriétés formelles à vérifier et analyser les résultats nécessite une expertise dans les méthodes formelles qui freine leur adoption et peut rebuter les concepteurs. Il est donc nécessaire de construire pour chaque DSML, une chaîne d’outils qui masque les aspects formels aux utilisateurs. L’objectif de cette thèse est de faciliter le développement de telles chaînes de vérification. Notre contribution inclut 1) l’expression des propriétés comportementales au niveau métier en s’appuyant sur TOCL (Temporal Object Constraint Language), une extension temporelle du langage OCL; 2) la transformation automatique de ces propriétés en propriétés formelles en réutilisant les éléments clés de la sémantique de traduction; 3) la remontée des résultats de vérification grâce à une transformation d’ordre supérieur et un langage de description de correspondance entre le domaine métier et le domaine formel et 4) le processus associé de mise en oeuvre. Notre approche a été validée par l’expérimentation sur un sous-ensemble du langage de modélisation de processus de développement SPEM, et sur le langage de commande d’automates programmables Ladder Diagram, ainsi que par l’intégration d’un langage formel intermédiaire (FIACRE) dans la chaîne outillée de vérification. Ce dernier point permet de réduire l’écart sémantique entre les DSMLs et les domaines formels. / Domain specific Modeling Languages (DSMLs) are increasingly used at the early phases in the development of complex systems, in particular, for safety critical systems. The goal is to be able to reason early in the development on these models and, in particular, to fulfill verification and validation activities (V and V). A widely used technique is the exhaustive behavioral model verification using model-checking by providing a translational semantics to build a formal model from DSML conforming models in order to reuse powerful tools available for this formal domain. Defining a translational semantics, expressing formal properties to be assessed and analysing such verification results require such an expertise in formal methods that it restricts their adoption and may discourage the designers. It is thus necessary to build for each DSML, a toolchain which hides formal aspects for DSML end-users. The goal of this thesis consists in easing the development of such verification toolchains. Our contribution includes 1) expressing behavioral properties in the DSML level by relying on TOCL (Temporal Object Constraint Language), a temporal extension of OCL; 2) An automated transformation of these properties on formal properties while reusing the key elements of the translational semantics; 3) the feedback of verification results thanks to a higher-order transformation and a language which defines mappings between DSML and formal levels; 4) the associated process implementation. Our approach was validated by the experimentation on a subset of the development process modeling language SPEM, and on Ladder Diagram language used to specify programmable logic controllers (PLCs), and by the integration of a formal intermediate language (FIACRE) in the verification toolchain. This last point allows to reduce the semantic gap between DSMLs and formal domains.
|
52 |
Registrace ultrazvukových sekvencí s využitím evolučních algoritmů / Image registration of ultrasound sequences using evolutionary algorithmsHnízdilová, Bohdana January 2021 (has links)
This master´s thesis deals with the registration of ultrasound sequences using evolutionary algorithms. The theoretical part of the thesis describes the process of image registration and its optimalization using genetic and metaheuristic algorithms. The thesis also presents problems that may occur during the registration of ultrasonographic images and various approaches to their registration. In the practical part of the work, several optimization methods for the registration of a number of sequences were implemented and compared.
|
53 |
Evoluční algoritmy při řešení problému obchodního cestujícího / Evolutionary Algorithms for the Solution of Travelling Salesman ProblemJurčík, Lukáš January 2014 (has links)
This diploma thesis deals with evolutionary algorithms used for travelling salesman problem (TSP). In the first section, there are theoretical foundations of a graph theory and computational complexity theory. Next section contains a description of chosen optimization algorithms. The aim of the diploma thesis is to implement an application that solve TSP using evolutionary algorithms.
|
54 |
Restabelecimento de energia em sistemas de distribuição considerando aspectos práticos / Distribution systems service restoration with the consideration of practical aspectsMarques, Leandro Tolomeu 13 June 2018 (has links)
No contexto da operação de sistemas de distribuição, um dos problemas com os quais os operadores lidam frequentemente é o de restabelecimento de energia. Este problema surge na ocorrência de uma falta permanente e pode ser tratado por meio de manobras em chaves presentes na rede primária. Uma vez que tais redes operam com topologia radial, a ocorrência de uma falta pode resultar no desligamento de consumidores saudáveis. Desta maneira, o problema consiste em definir, num curto intervalo de tempo, um número mínimo de chaves que devem ser operadas a fim de isolar a falta e restaurar o máximo de consumidores saudáveis desligados. Os esforços para a obtenção de ferramentas computacionais para fornecimento de soluções para o problema de restabelecimento têm sido intensificados nos últimos anos. Isto ocorre, em especial, devido aos enormes prejuízos causados pela falta de energia às companhias de eletricidade e a toda a sociedade. Neste sentido, o objetivo deste trabalho é a obtenção de um método para auxiliar o trabalho dos operadores através do fornecimento de planos adequados de restabelecimento em curtos intervalos de tempo. Os diferenciais deste método proposto são a sua capacidade de: lidar, em especial, com redes reais de grande porte com reduzido esforço computacional; considerar a existência de vários níveis de prioridade de atendimento entre os consumidores (note, por exemplo, que um hospital ou um centro de segurança pública devem ter maior prioridade de atendimento que um grande supermercado ou unidades residenciais) e priorizar o atendimento deles de acordo a sua prioridade; fornecer uma sequência por meio da qual as chaves possam ser operadas a fim de isolar os setores em falta e reconectar o maior número de consumidores saudáveis desligados executando-se o mínimo de manobras em chaves e priorizando os consumidores com maior prioridade; ser capaz de selecionar cargas menos prioritárias para permaneceram desligadas nas situações em que não é possível obter uma solução que restaure todas as cargas saudáveis fora de serviço; e, adicionalmente, priorizar a operação de chaves controladas remotamente, que, diferentemente das chaves controladas manualmente, podem ser operadas com menores custos e de maneira mais rápida. O método proposto consiste, de maneira sintética, na união de uma busca exaustiva aplicada localmente a um novo algoritmo evolutivo multi-objetivo em tabelas de subpopulação que faz uso de uma estrutura de dados eficiente denominada Representação Nó-Profundidade. Para avaliar a performance relativa do método proposto, simulações foram realizadas num sistema de distribuição de pequeno porte e os resultados foram comparados com os obtidos por um método de Programação Matemática. Na sequência, novos experimentos foram realizadas em diversos casos de falta na rede de distribuição da cidade de Londrina-PR e cidades adjacentes. As soluções fornecidas mostraram-se adequadas ao tratamento dos casos de falta, assim como as sequências de chaveamento associadas a elas, as quais foram capazes de priorizar o restabelecimento dos consumidores prioritários seguindo seus níveis de prioridade. Adicionalmente, estudos avaliaram a variação do tempo de processamento computacional do método proposto com a dimensão das redes de distribuições e também com o número de gerações realizadas pelo algoritmo evolutivo multi-objetivo proposto e os resultados mostraram-se satisfatórios às necessidades do problema Portanto, pode-se comprovar que o método proposto atingiu os objetivos especificados, em especial, o tratamento de aspectos práticos do problema. Além do próprio método proposto, algumas contribuições desta pesquisa são a proposição um novo algoritmo evolutivo multiobjetivo em tabelas de subpopulação e de um novo operador para manipulação de florestas de grafo armazenadas pela Representação Nó-Profundidade e voltado ao problema de restabelecimento. / In the context of distribution systems operation, service restoration is one of the problems with which operators constantly deal. It arises when a permanent fault occurs and is treated trough operations in switches at primary grid. Since distribution systems are usually radial, fault occurrence turns-off healthy customers. Thereby, the service restoration problem consists in defining, in a short processing time, the minimum amount of switches that must be operated for the isolation of the fault and reconnection of the maximum amount of healthy out-of-service customers. The efforts of developing computational tools for getting solution to this problems has increased in the last years. It is, in special, due to enormous losses caused to the utilities and to the whole society. In this sense, the main objective of this research is getting a method able to help the distribution system operator\'s work through providing service restoration plans quickly. The differentials of this research are its ability to: deal, in special, with large scale grids whit a reduced computational effort; consider costumers of several priority levels (note, for instance, a hospital has a higher supply priority in relation to a big supermarket) and prioritize the higher priority customers; provide a switching sequence able to isolate and reconnect the maximum amount of healthy out-of-service customer by the minimum amount of switching actions; select lower priority customers to keep out-of-service in order to reconnect higher priority customers when a it is not possible to restore all customers; and, additionally, prioritize switching operation in remotely controlled switches, whose operation is faster and cheapest than the operation of manually controlled switches. The proposed method mixes a local exhaustive search and a new multi-objective evolutionary algorithm in subpopulation tables that uses a data structure named Node-Depth Encoding. For evaluating the relative performance of proposed method, simulations were performed in small distribution systems and the performance was compared with the performance a Mathematical Programing method from literature. New experiments were performed a Mathematical Programing method from literature. New experiments were performed in several fault situations in the real and large-scale distribution system of Londrina-PR and adjacent cities. The solutions provided were appropriated to the treatment of such contingency situations. The same occurs with the switching sequences provided, which were able to prioritize the restoration of higher priority customers. Additional studies evaluated the variation of the running time with the size of grids and with the values adopted for the maximum number of generations of the evolutionary algorithm (which is an input parameter). The results expressed the running time of the proposed method is suitable to the problem needs. Therefore, it could be proved the proposed method achieved the specified objectives, in special, the treatment of practical aspects of the problem. Besides the proposed method, some contributions of this research are proposition of a new multi-objective evolutionary algorithm in subpopulation tables and a new reproduction operator to manipulate graph forests computationally represented by Node-Depth Encoding.
|
55 |
Restabelecimento de energia em sistemas de distribuição considerando aspectos práticos / Distribution systems service restoration with the consideration of practical aspectsLeandro Tolomeu Marques 13 June 2018 (has links)
No contexto da operação de sistemas de distribuição, um dos problemas com os quais os operadores lidam frequentemente é o de restabelecimento de energia. Este problema surge na ocorrência de uma falta permanente e pode ser tratado por meio de manobras em chaves presentes na rede primária. Uma vez que tais redes operam com topologia radial, a ocorrência de uma falta pode resultar no desligamento de consumidores saudáveis. Desta maneira, o problema consiste em definir, num curto intervalo de tempo, um número mínimo de chaves que devem ser operadas a fim de isolar a falta e restaurar o máximo de consumidores saudáveis desligados. Os esforços para a obtenção de ferramentas computacionais para fornecimento de soluções para o problema de restabelecimento têm sido intensificados nos últimos anos. Isto ocorre, em especial, devido aos enormes prejuízos causados pela falta de energia às companhias de eletricidade e a toda a sociedade. Neste sentido, o objetivo deste trabalho é a obtenção de um método para auxiliar o trabalho dos operadores através do fornecimento de planos adequados de restabelecimento em curtos intervalos de tempo. Os diferenciais deste método proposto são a sua capacidade de: lidar, em especial, com redes reais de grande porte com reduzido esforço computacional; considerar a existência de vários níveis de prioridade de atendimento entre os consumidores (note, por exemplo, que um hospital ou um centro de segurança pública devem ter maior prioridade de atendimento que um grande supermercado ou unidades residenciais) e priorizar o atendimento deles de acordo a sua prioridade; fornecer uma sequência por meio da qual as chaves possam ser operadas a fim de isolar os setores em falta e reconectar o maior número de consumidores saudáveis desligados executando-se o mínimo de manobras em chaves e priorizando os consumidores com maior prioridade; ser capaz de selecionar cargas menos prioritárias para permaneceram desligadas nas situações em que não é possível obter uma solução que restaure todas as cargas saudáveis fora de serviço; e, adicionalmente, priorizar a operação de chaves controladas remotamente, que, diferentemente das chaves controladas manualmente, podem ser operadas com menores custos e de maneira mais rápida. O método proposto consiste, de maneira sintética, na união de uma busca exaustiva aplicada localmente a um novo algoritmo evolutivo multi-objetivo em tabelas de subpopulação que faz uso de uma estrutura de dados eficiente denominada Representação Nó-Profundidade. Para avaliar a performance relativa do método proposto, simulações foram realizadas num sistema de distribuição de pequeno porte e os resultados foram comparados com os obtidos por um método de Programação Matemática. Na sequência, novos experimentos foram realizadas em diversos casos de falta na rede de distribuição da cidade de Londrina-PR e cidades adjacentes. As soluções fornecidas mostraram-se adequadas ao tratamento dos casos de falta, assim como as sequências de chaveamento associadas a elas, as quais foram capazes de priorizar o restabelecimento dos consumidores prioritários seguindo seus níveis de prioridade. Adicionalmente, estudos avaliaram a variação do tempo de processamento computacional do método proposto com a dimensão das redes de distribuições e também com o número de gerações realizadas pelo algoritmo evolutivo multi-objetivo proposto e os resultados mostraram-se satisfatórios às necessidades do problema Portanto, pode-se comprovar que o método proposto atingiu os objetivos especificados, em especial, o tratamento de aspectos práticos do problema. Além do próprio método proposto, algumas contribuições desta pesquisa são a proposição um novo algoritmo evolutivo multiobjetivo em tabelas de subpopulação e de um novo operador para manipulação de florestas de grafo armazenadas pela Representação Nó-Profundidade e voltado ao problema de restabelecimento. / In the context of distribution systems operation, service restoration is one of the problems with which operators constantly deal. It arises when a permanent fault occurs and is treated trough operations in switches at primary grid. Since distribution systems are usually radial, fault occurrence turns-off healthy customers. Thereby, the service restoration problem consists in defining, in a short processing time, the minimum amount of switches that must be operated for the isolation of the fault and reconnection of the maximum amount of healthy out-of-service customers. The efforts of developing computational tools for getting solution to this problems has increased in the last years. It is, in special, due to enormous losses caused to the utilities and to the whole society. In this sense, the main objective of this research is getting a method able to help the distribution system operator\'s work through providing service restoration plans quickly. The differentials of this research are its ability to: deal, in special, with large scale grids whit a reduced computational effort; consider costumers of several priority levels (note, for instance, a hospital has a higher supply priority in relation to a big supermarket) and prioritize the higher priority customers; provide a switching sequence able to isolate and reconnect the maximum amount of healthy out-of-service customer by the minimum amount of switching actions; select lower priority customers to keep out-of-service in order to reconnect higher priority customers when a it is not possible to restore all customers; and, additionally, prioritize switching operation in remotely controlled switches, whose operation is faster and cheapest than the operation of manually controlled switches. The proposed method mixes a local exhaustive search and a new multi-objective evolutionary algorithm in subpopulation tables that uses a data structure named Node-Depth Encoding. For evaluating the relative performance of proposed method, simulations were performed in small distribution systems and the performance was compared with the performance a Mathematical Programing method from literature. New experiments were performed a Mathematical Programing method from literature. New experiments were performed in several fault situations in the real and large-scale distribution system of Londrina-PR and adjacent cities. The solutions provided were appropriated to the treatment of such contingency situations. The same occurs with the switching sequences provided, which were able to prioritize the restoration of higher priority customers. Additional studies evaluated the variation of the running time with the size of grids and with the values adopted for the maximum number of generations of the evolutionary algorithm (which is an input parameter). The results expressed the running time of the proposed method is suitable to the problem needs. Therefore, it could be proved the proposed method achieved the specified objectives, in special, the treatment of practical aspects of the problem. Besides the proposed method, some contributions of this research are proposition of a new multi-objective evolutionary algorithm in subpopulation tables and a new reproduction operator to manipulate graph forests computationally represented by Node-Depth Encoding.
|
Page generated in 0.0457 seconds