The goal of this thesis is to analyze and to find solutions of optimization problems derived from automation of functional verification of hardware using artificial neural networks. Verification of any integrated circuit (so called Design Under Verification, DUV) using technique called coverage-driven verification and universal verification methodology (UVM) is carried out by sending stimuli inputs into DUV. The verification environment continuously monitors percentual coverage of DUV functionality given by the specification. In current context, coverage stands for measurable property of DUV, like count of verified arithemtic operations or count of executed lines of code. Based on the final coverage, it is possible to determine whether the coverage of DUV is high enough to declare DUV as verified. Otherwise, the input stimuli set needs to change in order to achieve higher coverage. Current trend is to generate this set by technique called constrained-random stimulus generation. We will practice this technique by using pseudorandom program generator (PNG). In this paper, we propose multiple solutions for following two optimization problems. First problem is ongoing modification of PNG constraints in such a way that the DUV can be verified by generated stimuli as quickly as possible. Second one is the problem of seeking the smallest set of stimuli such that this set verifies DUV. The qualities of the proposed solutions are verified on 32-bit application-specific instruction set processors (ASIPs) called Codasip uRISC and Codix Cobalt.

Cette thèse s’intéresse à différents problèmes de contrôle et d’optimisation dont il n’existe à ce jour que des solutions approchées. D’une part nous nous intéressons à des techniques visant à réduire ou supprimer les approximations pour obtenir des solutions plus précises voire exactes. D’autre part nous développons de nouvelles méthodes d’approximation pour traiter plus rapidement des problèmes à plus grande échelle. Nous étudions des méthodes numériques de simulation d’équation différentielle stochastique et d’amélioration de calculs d’espérance. Nous mettons en œuvre des techniques de type quantification pour la construction de variables de contrôle ainsi que la méthode de gradient stochastique pour la résolution de problèmes de contrôle stochastique. Nous nous intéressons aussi aux méthodes de clustering liées à la quantification, ainsi qu’à la compression d’information par réseaux neuronaux. Les problèmes étudiés sont issus non seulement de motivations financières, comme le contrôle stochastique pour la couverture d’option en marché incomplet mais aussi du traitement des grandes bases de données de médias communément appelé Big data dans le chapitre 5. Théoriquement, nous proposons différentes majorations de la convergence des méthodes numériques d’une part pour la recherche d’une stratégie optimale de couverture en marché incomplet dans le chapitre 3, d’autre part pour l’extension la technique de Beskos-Roberts de simulation d’équation différentielle dans le chapitre 4. Nous présentons une utilisation originale de la décomposition de Karhunen-Loève pour une réduction de variance de l’estimateur d’espérance dans le chapitre 2. / This thesis proposes different problems of stochastic control and optimization that can be solved only thanks approximation. On one hand, we develop methodology aiming to reduce or suppress approximations to obtain more accurate solutions or something exact ones. On another hand we develop new approximation methodology in order to solve quicker larger scale problems. We study numerical methodology to simulated differential equations and enhancement of computation of expectations. We develop quantization methodology to build control variate and gradient stochastic methods to solve stochastic control problems. We are also interested in clustering methods linked to quantization, and principal composant analysis or compression of data thanks neural networks. We study problems motivated by mathematical finance, like stochastic control for the hedging of derivatives in incomplete market but also to manage huge databases of media commonly known as big Data in chapter 5. Theoretically we propose some upper bound for convergence of the numerical method used. This is the case of optimal hedging in incomplete market in chapter 3 but also an extension of Beskos-Roberts methods of exact simulation of stochastic differential equations in chapter 4. We present an original application of karhunen-Loève decomposition for a control variate of computation of expectation in chapter 2.

Nowadays, assembly robots are increasingly used in the manufacturing industry to replace or collaborate with human labors. This is the goal of the dual arm assembly robot developed by ABB. With the rapid upgrading in consumer electronics products, the lifetime of an assembly line could be only a few months. However, even for experienced programmers, to manually construct a good enough assembly sequence is time consuming, and the quality of the generated assembly sequence is not guaranteed. Moreover, a good robot assembly sequence is important to the throughput of an assembly line. For dual arm robots, it is also important to obtain a balance between the two arms, as well as handling scheduling conflicts and avoiding collisions in a crowded environment. In this master thesis, a program is produced to automatically generate the optimal assembly sequence for a class of real-world assembly cases. The solution also takes the layout of the assembly cell into account, thus constructing the best combination of cell layout, workload balancing, task sequence and task scheduling. The program is implemented using Google OR-Tools – an open-source support library for combinatorial optimization. A customized search strategy is proposed and a comparison between this strategy and the built-in search strategy of Google OR-Tools is done. The result shows that the used approach is effective for the problem study case. It takes about 4 minutes to find the optimal solution and 32 minutes to prove its optimality. In addition, the result also shows that the customized search strategy works consistently with good performance for different problem cases. Moreover, the customized strategy is more efficient than built-in search strategy in many cases. / Numera används monteringsrobotar alltmer inom tillverkningsindustrin för att ersätta eller samarbeta med människor. Detta är måluppgiften för den tvåarmiga monteringsroboten, YuMi, som utvecklats av ABB. Med den korta produktlivslängden för hemelektronikprodukter kan livslängden för en monteringslinje vara ett fåtal månader. Även för erfarna robotprogrammerare är det svårt och tidsödande att manuellt konstruera en tillräckligt bra monteringsordning, och dessutom kan resultatets kvalitet inte garanteras. En bra monteringsordning är nödvändig för genomströmningen i en monteringslinje. För tvåarmiga robotar, är det också viktigt att få en balans mellan de två armarna, samt hantering av schemakrockar och undvika kollisioner i en trång miljö. I detta examensarbete har ett program skrivits, som automatiskt genererar optimala lösningar för en klass av verkliga monteringsfall. Lösningen tar hänsyn till utformningen av monteringscellen och arrangerar cellen på bästa sätt, balanserar arbetsbelastningen, ordnar och tidsbestämmer uppgifter. Programmet använder sig av Google OR-Tools – ett öppet kodbibliotek för kombinatorisk optimering. Dessutom föreslås en skräddarsydd sökstrategi, som jämförs med Google OR-Tools inbyggda sökstrategi. Resultatet visar att den använda metoden är effektiv för problemtypen. Det tar ungefär 4 minuter att hitta den optimala lösningen och 32 minuter för att bevisa optimalitet. Dessutom visar resultatet att den anpassade sökstrategin konsekvent har en bra prestanda för olika problemfall. Dessutom är den anpassade strategin effektivare än den inbyggda sökstrategin i många fall.

Since the term ESG was coined in 2005, the growth of sustainable investments has outpaced the overall asset management industry. A lot of research has been done with regards to the link between sustainability and financial performance, despite the fact that there is a lack of transparency in sustainability of listed companies. This thesis breaks down the word sustainability into two di↵erent categories, and in turn eleven di↵erent parameters. The result is the term Q score which represents a company’s sustainability. The purpose is to increase transparency in the fund selection process for asset managers. Further, a multiobjective optimization problem is solved to analyze the relationships between return, risk and sustainability. The main subject is that accommodating sustainability as a third parameter in addition to return and risk modifies the fund selection process. The result indicates that the relationships between sustainability, return and risk follow the ecient market hypothesis, implying that an investor would have to sacrifice risk and return in order to achieve higher sustainability. With that said, the results indicated that the sacrifice is relatively small, and that there are a number of sustainable portfolios that perform well. Moving on, the reporting of ESG company data is still lacking. For this reason, this master thesis acts as a precursor for any future development within the field. / Sedan termen ESG utvecklades år 2005, har tillväxten av hållbara investeringar vuxit snabbare än den generella förvaltningsindustrin. Mycket forskning har gjorts kring hållbarhet kopplat till finansiell avkastning, men trots detta saknas det fortfarande en transparens rådande hållbarhet av noterade bolag. Detta examensarbete bryter ned termen hållbarhet till två kategorier, vilket i sin tur bryts ner till elva kvantifierbara parametrar. Resultatet blir ett så kallat Q score, som är ett värde på ett företags hållbarhet. Syftet med arbetet är att öka transparensen av fonders hållbarhetsarbete. Vidare löses ett optimeringsproblem med tre parametrar för att undersöka förållandena mellan avkastning, risk och hållbarhet. Resultatet indikerar att dessa förhållanden följer hypotesen om effektiva marknader, vilket innebär att en investerare måste offra avkastning och risk för att uppnå en mer hållbar portfölj. Med det sagt, indikererar resultatet att en investerare inte behöver offra mycket inom avkastning för att uppnå en hållbar portfölj. Vidare kvarstår det mycket arbete inom rapporteringen av ESG data på företagsnivå. Av detta skäl anses detta examensarbete vara en föregångare innan datan utvecklas vidare.

本論文は,様々なネットワーク最適化問題の数学的構造について様々な観点から調べたものである.主たる結果はネットワーク最適化問題の代表例である最大流問題に,関するいくつかの結果と,Min-Plus代数に値をもつ行列の固有値と固有ベクトルに関する特徴づけに関する結果からなっている. / 博士(理学) / Doctor of Philosophy in Science / 同志社大学 / Doshisha University

No description available.

L’ingénierie dirigée par les modèles (EDM) est un paradigme de développement logiciel qui promeut l’utilisation de modèles en tant qu’artefacts de première plan et de processus automatisés pour en dériver d’autres artefacts tels que le code, la documentation et les cas de test. La transformation de modèle est un élément important de l’EDM puisqu’elle permet de manipuler les représentations abstraites que sont les modèles. Les transformations de modèles, comme d’autres programmes, sont sujettes à la fois à des erreurs syntaxiques et sémantiques. La correction de ces erreurs est difficile et chronophage, car les transformations dépendent du langage de transformation comme ATL et des langages de modélisation dans lesquels sont exprimés les modèles en entrée et en sortie. Les travaux existants sur la réparation des transformations ciblent les erreurs syntaxiques ou sémantiques, une erreur à la fois, et définissent manuellement des patrons de correctifs. L’objectif principal de notre recherche est de proposer un cadre générique pour corriger automatiquement de multiples erreurs syntaxiques et sémantiques. Afin d’atteindre cet objectif, nous reformulons la réparation des transformations de modèles comme un problème d’optimisation multiobjectif et le résolvons au moyen d’algorithmes évolutionnaires. Pour adapter le cadre aux deux catégories d’erreurs, nous utilisons différents types d’objectifs et des stratégies sophistiquées pour guider l’exploration de l’espace des solutions. / Model-driven engineering (MDE) is a software development paradigm that promotes the use of models as first-class artifacts and automated processes to derive other artefacts from them such as code, documentation and test cases. Model transformation is an important element of MDE since it allows to manipulate the abstract representations that are models. Model transformations, as other programs are subjects to both syntactic and semantic errors. Fixing those errors is difficult and time consuming as the transformations depend on the transformation language such as ATL, and modeling languages in which input and output models are expressed. Existing work on transformation repair targets either syntactic or semantic errors, one error at a time, and define patch templates manually. The main goal of our research is to propose a generic framework to fix multiple syntactic and semantic errors automatically. In order to achieve this goal, we reformulate the repair of model transformations as a multi-objective optimization problem and solve it by means of evolutionary algorithms. To adapt the framework to the two categories of errors, we use different types of objectives and sophisticated strategies to guide the search.

The thesis deals the issue of solution of continuous systems by evolutionary computational techniques. Evolutionary computing techniques fall into the field of softcomputing, an advanced metaheuristics optimization that is becoming more and more a method of solving complicated optimization problems with the gradual increase in computing performance of computers. The solution of continuous systems, or the synthesis of continuous control circuits, is one of the areas where these advanced algorithms find their application. When dealing with continuous systems we will focus on regulatory issues. Evolutionary computing can then become a tool not only for optimization of controller parameters but also to design its structure. Various algorithms (genetic algorithm, differential evolution, etc.) can be used to optimize the parameters of the controller, for the design of the controller structurewe usually encounter so called grammatical evolution. However, the use of grammatical evolution is not necessary if appropriate coding is used, as suggested in the presented thesis. The thesis presents a method of designing the structure and parameters of a general linear controller using the genetic algorithm. A general linear regulator is known also as so called polynomial controller, if we encounter the polynomial theory of control. The method of encoding the description of the general linear controller into the genetic chain is crucial, it determines a set of algorithms that are usable for optimization and influence the efficiency of the calculations. Described coding, effective EVT implementation, including multi-criteria optimization, is a key benefit of this work.

Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées. / Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics.

Training a Support Vector Machine (SVM) requires the solution of a very large quadratic programming (QP) optimization problem. Sequential Minimal Optimization (SMO) is a decomposition-based algorithm which breaks this large QP problem into a series of smallest possible QP problems. However, it still costs O(n2) computation time. In our SVM implementation, we can do training with huge data sets in a distributed manner (by breaking the dataset into chunks, then using Message Passing Interface (MPI) to distribute each chunk to a different machine and processing SVM training within each chunk). In addition, we moved the kernel calculation part in SVM classification to a graphics processing unit (GPU) which has zero scheduling overhead to create concurrent threads. In this thesis, we will take advantage of this GPU architecture to improve the classification performance of SVM.