This report explores if Monte-Carlo Tree Search (MCTS) can perform well in Fox Game, a classic Scandinavian strategy game. MCTS is implemented using a cutoff in the simulation phase. The game state is then evaluated using a heuristic function that is formulated using theoretical arguments from its chess counterpart. MCTS is shown to perform on the same level as highly experienced human players using limited computational resources. The method is used to explore how the imbalance in Fox Game (favoring sheep) can be mended by reducing the number of sheep pieces from 20 to 18. / I denna rapport undersöks om Monte-Carlo trädsökning (MCTS) kan prestera väl i rävspel, ett klassiskt skandinaviskt strategispel. MCTS implementeras med en cutoff i simuleringsfasen. Speltillståndet utvärderas där med hjälp av en heuristisk funktion som formuleras med hjälp av teoretiska argument från dess motsvarighet i schack. MCTS med endast begränsade beräkningsresurser visas kunna prestera på samma nivå som mycket erfarna människor. Metoden används för att utforska hur obalansen i rävspel (som gynnar får) kan förbättras genom att minska antalet fårpjäser från 20 till 18. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm

The idea of using artificial intelligence to evaluatemilitary strategies is relevant for a large number of governmentstoday. With programs like AlphaZero beating world championsin games of ever-increasing complexity, military adaptations areprobably not far away, if they are not in use already. Partof these programs’ recent success is due to a heuristic searchalgorithm called Monte Carlo Tree Search. In this project,we explored the possibility of using this algorithm to build aprogram capable of playing the strategy board game of Riskat a high level. The complexity and stochastic dynamic ofthe game demanded the use of chance nodes and aggressivegameplay limitations, known as action-pruning. By changing theconditions and game environment of the algorithm, we observedperformance differences, mainly simulation length considerablyimproved convergence. We suggest that the created program,optimized with correct algorithm parameters, has the potentialof playing Risk at a high level. / Tanken att använda artificiell intelligensför att evaluera militära strategierär relevant för ett stortantal regeringar idag. När program så som AlphaZero slårvärldsmästare i allt mer komplexa spel bör militära tillämpningarinte ligga långt borta, om de inte redanär implementerade. Endel av programmens framgång kan härledas till dess användningav en heuristisk sökalgoritm, kallad Monte Carlo-Trädsökning. Idet här projektet, utforskade vi möjligheten att använda dennaalgoritm för att konstruera ett program, kapabel att spela detstrategiska brädspelet Risk på en hög nivå. Spelets komplexitetoch stokastiska natur krävde användning av så kallade ”chance-nodes” och en aggressiv användning av spelbegränsningar kändasom ”action-pruning”. Genom attändra villkoren och spelmiljönför algoritmen observerades prestandaförändringar, där konver-gensen i huvudsakökade vid begränsningar av möjliga val. Viföreslår att det skapade programmet, optimerat med korrektaalgoritmparametrar, har potentialen att spela Risk på en högnivå. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

The strategy game Risk is a very popular boardgame, requiring little effort to learn but lots of skill to master.The aim of this project is to explore the fortification phase of thegame, where the player’s troops are moved between territories.Our method is based on adapting Monte Carlo tree search(MCTS) to Risk. To improve the troop movements, we proposetwo techniques, hierarchical search and progressive bias. Thesemethods, combined with other extensions of MCTS are thencompared against a baseline player of the game. Our results showthat hierarchical search improved the MCTS agent’s playingpower and the progressive bias have potential to improve theagent but needs further investigation. / Strategispelet Risk är ett väldigt populärt brädspel som är lätt att lära sig men svårt att bemästra. Syftet med detta projekt är att utforska spelets befästningsfas, där spelarens trupper flyttas mellan territorier. Vår metod är baserad på en anpassning av Monte Carlo trädsökning (MCTS) till Risk. För att förbättra trupprörelserna föreslår vi två tekniker, ”hierarchical search” och ”progressive bias”. Dessa metoder, i kombination med andra tillägg av MCTS, jämförs sedan mot en standard agent i spelet. Våra resultat visar att hierarchical search förbättrade MCTS agentens spelstyrka och att progressivce bias har möjlighet att förbättra agenten men kräver fortsatt utforskning. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm

[EN] Nowadays, several communication standards are emerging and evolving, searching higher transmission rates, reliability and coverage. This expansion is primarily driven by the continued increase in consumption of mobile multimedia services due to the emergence of new handheld devices such as smartphones and tablets. One of the most significant techniques employed to meet these demands is the use of multiple transmit and receive antennas, known as MIMO systems. The use of this technology allows to increase the transmission rate and the quality of the transmission through the use of multiple antennas at the transmitter and receiver sides. MIMO technologies have become an essential key in several wireless standards such as WLAN, WiMAX and LTE. These technologies will be incorporated also in future standards, therefore is expected in the coming years a great deal of research in this field. Clearly, the study of MIMO systems is critical in the current investigation, however the problems that arise from this technology are very complex. High Performance Computing (HPC) systems, and specifically, modern hardware architectures as multi-core and many-cores (e.g Graphics Processing Units (GPU)) are playing a key role in the development of efficient and low-complexity algorithms for MIMO transmissions. Proof of this is that the number of scientific contributions and research projects related to its use has increased in the last years. Also, some high performance libraries have been implemented as tools for researchers involved in the development of future communication standards. Two of the most popular libraries are: IT++ that is a library based on the use of some optimized libraries for multi-core processors and the Communications System Toolbox designed for use with MATLAB, which uses GPU computing. However, there is not a library able to run on a heterogeneous platform using all the available resources. In view of the high computational requirements in MIMO application research and the shortage of tools able to satisfy them, we have made a special effort to develop a library to ease the development of adaptable parallel applications in accordance with the different architectures of the executing platform. The library, called MIMOPack, aims to implement efficiently using parallel computing, a set of functions to perform some of the critical stages of MIMO communication systems simulation. The main contribution of the thesis is the implementation of efficient Hard and Soft output detectors, since the detection stage is considered the most complex part of the communication process. These detectors are highly configurable and many of them include preprocessing techniques that reduce the computational cost and increase the performance. The proposed library shows three important features: portability, efficiency and easy of use. Current realease allows GPUs and multi-core computation, or even simultaneously, since it is designed to use on heterogeneous machines. The interface of the functions are common to all environments in order to simplify the use of the library. Moreover, some of the functions are callable from MATLAB increasing the portability of developed codes between different computing environments. According to the library design and the performance assessment, we consider that MIMOPack may facilitate industrial and academic researchers the implementation of scientific codes without having to know different programming languages and machine architectures. This will allow to include more complex algorithms in their simulations and obtain their results faster. This is particularly important in the industry, since the manufacturers work to analyze and to propose their own technologies with the aim that it will be approved as a standard. Thus allowing to enforce their intellectual property rights over their competitors, who should obtain the corresponding licenses to include these technologies into their products. / [ES] En la actualidad varios estándares de comunicación están surgiendo buscando velocidades de transmisión más altas y mayor fiabilidad. Esta expansión está impulsada por el aumento en el consumo de servicios multimedia debido a la aparición de nuevos dispositivos como los smartphones y las tabletas. Una de las técnicas empleadas más importantes es el uso de múltiples antenas de transmisión y recepción, conocida como sistemas MIMO, que permite aumentar la velocidad y la calidad de la transmisión. Las tecnologías MIMO se han convertido en una parte esencial en diferentes estándares tales como WLAN, WiMAX y LTE. Estas tecnologías se incorporarán también en futuros estándares, por lo tanto, se espera en los próximos años una gran cantidad de investigación en este campo. Está claro que el estudio de los sistemas MIMO es crítico en la investigación actual, sin embargo los problemas que surgen de esta tecnología son muy complejos. La sistemas de computación de alto rendimiento, y en concreto, las arquitecturas hardware actuales como multi-core y many-core (p. ej. GPUs) están jugando un papel clave en el desarrollo de algoritmos eficientes y de baja complejidad en las transmisiones MIMO. Prueba de ello es que el número de contribuciones científicas y proyectos de investigación relacionados con su uso se han incrementado en el últimos años. Algunas librerías de alto rendimiento se están utilizando como herramientas por investigadores en el desarrollo de futuros estándares. Dos de las librerías más destacadas son: IT++ que se basa en el uso de distintas librerías optimizadas para procesadores multi-core y el paquete Communications System Toolbox diseñada para su uso con MATLAB, que utiliza computación con GPU. Sin embargo, no hay una biblioteca capaz de ejecutarse en una plataforma heterogénea. En vista de los altos requisitos computacionales en la investigación MIMO y la escasez de herramientas capaces de satisfacerlos, hemos implementado una librería que facilita el desarrollo de aplicaciones paralelas adaptables de acuerdo con las diferentes arquitecturas de la plataforma de ejecución. La librería, llamada MIMOPack, implementa de manera eficiente un conjunto de funciones para llevar a cabo algunas de las etapas críticas en la simulación de un sistema de comunicación MIMO. La principal aportación de la tesis es la implementación de detectores eficientes de salida Hard y Soft, ya que la etapa de detección es considerada la parte más compleja en el proceso de comunicación. Estos detectores son altamente configurables y muchos de ellos incluyen técnicas de preprocesamiento que reducen el coste computacional y aumentan el rendimiento. La librería propuesta tiene tres características importantes: la portabilidad, la eficiencia y facilidad de uso. La versión actual permite computación en GPU y multi-core, incluso simultáneamente, ya que está diseñada para ser utilizada sobre plataformas heterogéneas que explotan toda la capacidad computacional. Para facilitar el uso de la biblioteca, las interfaces de las funciones son comunes para todas las arquitecturas. Algunas de las funciones se pueden llamar desde MATLAB aumentando la portabilidad de códigos desarrollados entre los diferentes entornos. De acuerdo con el diseño de la biblioteca y la evaluación del rendimiento, consideramos que MIMOPack puede facilitar la implementación de códigos sin tener que saber programar con diferentes lenguajes y arquitecturas. MIMOPack permitirá incluir algoritmos más complejos en las simulaciones y obtener los resultados más rápidamente. Esto es particularmente importante en la industria, ya que los fabricantes trabajan para proponer sus propias tecnologías lo antes posible con el objetivo de que sean aprobadas como un estándar. De este modo, los fabricantes pueden hacer valer sus derechos de propiedad intelectual frente a sus competidores, quienes luego deben obtener las correspon / [CA] En l'actualitat diversos estàndards de comunicació estan sorgint i evolucionant cercant velocitats de transmissió més altes i major fiabilitat. Aquesta expansió, està impulsada pel continu augment en el consum de serveis multimèdia a causa de l'aparició de nous dispositius portàtils com els smartphones i les tablets. Una de les tècniques més importants és l'ús de múltiples antenes de transmissió i recepció (MIMO) que permet augmentar la velocitat de transmissió i la qualitat de transmissió. Les tecnologies MIMO s'han convertit en una part essencial en diferents estàndards inalàmbrics, tals com WLAN, WiMAX i LTE. Aquestes tecnologies s'incorporaran també en futurs estàndards, per tant, s'espera en els pròxims anys una gran quantitat d'investigació en aquest camp. L'estudi dels sistemes MIMO és crític en la recerca actual, no obstant açó, els problemes que sorgeixen d'aquesta tecnologia són molt complexos. Els sistemes de computació d'alt rendiment com els multi-core i many-core (p. ej. GPUs)), estan jugant un paper clau en el desenvolupament d'algoritmes eficients i de baixa complexitat en les transmissions MIMO. Prova d'açò és que el nombre de contribucions científiques i projectes d'investigació relacionats amb el seu ús s'han incrementat en els últims anys. Algunes llibreries d'alt rendiment estan utilitzant-se com a eines per investigadors involucrats en el desenvolupament de futurs estàndards. Dos de les llibreries més destacades són: IT++ que és una llibreria basada en lús de diferents llibreries optimitzades per a processadors multi-core i el paquet Communications System Toolbox dissenyat per al seu ús amb MATLAB, que utilitza computació amb GPU. No obstant açò, no hi ha una biblioteca capaç d'executar-se en una plataforma heterogènia. Degut als alts requisits computacionals en la investigació MIMO i l'escacès d'eines capaces de satisfer-los, hem implementat una llibreria que facilita el desenvolupament d'aplicacions paral·leles adaptables d'acord amb les diferentes arquitectures de la plataforma d'ejecució. La llibreria, anomenada MIMOPack, implementa de manera eficient, un conjunt de funcions per dur a terme algunes de les etapes crítiques en la simulació d'un sistema de comunicació MIMO. La principal aportació de la tesi és la implementació de detectors eficients d'exida Hard i Soft, ja que l'etapa de detecció és considerada la part més complexa en el procés de comunicació. Estos detectors són altament configurables i molts d'ells inclouen tècniques de preprocessament que redueixen el cost computacional i augmenten el rendiment. La llibreria proposta té tres característiques importants: la portabilitat, l'eficiència i la facilitat d'ús. La versió actual permet computació en GPU i multi-core, fins i tot simultàniament, ja que està dissenyada per a ser utilitzada sobre plataformes heterogènies que exploten tota la capacitat computacional. Amb el fi de simplificar l'ús de la biblioteca, les interfaces de les funcions són comunes per a totes les arquitectures. Algunes de les funcions poden ser utilitzades des de MATLAB augmentant la portabilitat de còdics desenvolupats entre els diferentes entorns. D'acord amb el disseny de la biblioteca i l'evaluació del rendiment, considerem que MIMOPack pot facilitar la implementació de còdics a investigadors sense haver de saber programar amb diferents llenguatges i arquitectures. MIMOPack permetrà incloure algoritmes més complexos en les seues simulacions i obtindre els seus resultats més ràpid. Açò és particularment important en la industria, ja que els fabricants treballen per a proposar les seues pròpies tecnologies el més prompte possible amb l'objectiu que siguen aprovades com un estàndard. D'aquesta menera, els fabricants podran fer valdre els seus drets de propietat intel·lectual enfront dels seus competidors, els qui després han d'obtenir les corresponents llicències si vole / Ramiro Sánchez, C. (2015). MIMOPack: A High Performance Computing Library for MIMO Communication Systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/53930 / Premios Extraordinarios de tesis doctorales

Cette thèse traite de la révision automatique des connaissances contenues dans les systèmes fonctionnant par exploration informée d'arbres d'états. Ces systèmes, de par leur performance, sont employés dans de nombreux domaines applicatifs. En particulier, des travaux ont proposés d’utiliser cette approche dans le cadre de l'automatisation de la généralisation de données géographiques. La généralisation de données géographique s'intéresse à la dérivation, à partir de données géographiques détaillées, de données moins détaillées adaptées à un besoin particulier (e.g. changement d'échelle). Son automatisation, enjeu majeur pour les agences cartographiques telles que l'Institut Géographique National (IGN), est particulièrement complexe. Les performances des systèmes basés sur l’exploration informée d'arbres d'états sont directement dépendantes de la qualité de leurs connaissances (heuristiques). Or, la définition et la mise à jour de ces dernières s'avèrent généralement fastidieuses. Dans le cadre de cette thèse, nous proposons une approche de révision hors ligne des connaissances basée sur le traçage du système et sur l'analyse de ces traces. Ces traces sont ainsi utilisées par un module de révision qui est chargé d'explorer l'espace des connaissances possibles et d'en modifier en conséquence les connaissances du système. Des outils de diagnostic en ligne de la qualité des connaissances permettent de déterminer quand déclencher le processus de révision hors ligne des connaissances. Pour chaque méthode et approche que nous présentons, une mise en oeuvre est détaillée et expérimentée dans le cadre de l'automatisation de la généralisation de données géographiques / This work deals with automatic knowledge revision in systems based on an informed tree search strategy. Because of their efficiency, these systems are used in numerous fields. In particular, some literature work uses this approach for the automation of geographic data generalisation. Geographic data generalisation is the process that derives data adapted to specific needs (e.g. map scale) from too detailed geographic data. Its automation, which is a major issue for national mapping agencies like Institut Géographique National (IGN), is particularly complex. The performances of systems based on informed tree search are directly dependant on their knowledge (heuristics) quality. Unfortunately, most of the time, knowledge definition and update are fastidious. In this work, we propose an offline knowledge revision approach based on the system logging and on the analysis of these logs. Thus, the logs are used by a revision module which is in charge of the system knowledge revision by knowledge space exploration. Tools for online knowledge quality diagnosis allow to determine when the offline knowledge process should be activated. For each method and each approach presented, an implementation is proposed in the context of geographic data generalisation

La présente thèse porte sur l'étude de prise de décisions séquentielles multi-Objectif (MOSDM). La motivation de ce travail est double. D'un côté, la prise de décision, par exemple, dans les domaines de robotique et de planification, concerne l'optimisation séquentielle. De l'autre côté, nombreuses applications dans le monde réel sont plus naturellement formulés en termes d'optimisation multi-Objectif (MOO). La méthode proposée dans la thèse adapte le cadre bien connue de recherche Monte-Carlo arborescente (MCTS) à l'optimisation multi-Objectif, dans lequel multiple séquences de décision optimales sont développées dans un seul arbre de recherche. Le principal défi est de proposer une nouvelle récompense, capable de guider l'exploration de l'arbre bien que le problème de MOO n'applique pas un ordre total entre les solutions. La contribution principale de cette thèse est de proposer et d'étudier expérimentalement ces deux récompenses : l'indicateur de hypervolume et la récompense de dominance Pareto, qui sont inspirées de la littérature de MOO et basés sur une archive de solutions antérieures (archives Pareto). L'étude montre la complémentarité de ces deux récompenses. L'indicateur de hypervolume souffre de sa complexité algorithmique. Cependant, cet indicateur fournit des informations à grains fins de la qualité des solutions à l'égard de l'archive actuelle. Bien au contraire, la complexité de la récompense de dominance Pareto est linéaire, mais cette récompense fournit des informations de plus en plus rare au long de la recherche. Les preuves de principe de l'approche sont donnés sur les problèmes articiaux et les défis internationaux, et confirment la valeur de l'approche. En particulier, MOMCTS est capable de découvrir les politiques se trouvant dans les régions non-Convexes du front Pareto, qui contraste avec l'état de l'art: les algorithmes d'apprentissage par renforcement multi-Objectif existants sont basés sur scalarization linéaire et donc ne sont pas capables de explorer ces régions non-Convexes. Enfin, MOMCTS a fait honorablement la concurrence avec l'état de l'art sur la compétition internationale de MOPTSP 2013. / This thesis is concerned with multi-Objective sequential decision making (MOSDM). The motivation is twofold. On the one hand, many decision problems in the domains of e.g., robotics, scheduling or games, involve the optimization of sequences of decisions. On the other hand, many real-World applications are most naturally formulated in terms of multi-Objective optimization (MOO). The proposed approach extends the well-Known Monte-Carlo tree search (MCTS) framework to the MOO setting, with the goal of discovering several optimal sequences of decisions through growing a single search tree. The main challenge is to propose a new reward, able to guide the exploration of the tree although the MOO setting does not enforce a total order among solutions. The main contribution of the thesis is to propose and experimentally study two such rewards, inspired from the MOO literature and assessing a solution with respect to the archive of previous solutions (Pareto archive): the hypervolume indicator and the Pareto dominance reward. The study shows the complementarity of these two criteria. The hypervolume indicator suffers from its known computational complexity; however the proposed extension thereof provides fine-Grained information about the quality of solutions with respect to the current archive. Quite the contrary, the Pareto-Dominance reward is linear but it provides increasingly rare information. Proofs of principle of the approach are given on artificial problems and challenges, and confirm the merits of the approach. In particular, MOMCTS is able to discover policies lying in non-Convex regions of the Pareto front, contrasting with the state of the art: existing Multi-Objective Reinforcement Learning algorithms are based on linear scalarization and thus fail to sample such non-Convex regions. Finally MOMCTS honorably competes with the state of the art on the 2013 MOPTSP competition.

Efficient best-first search algorithms have been developed for deterministic two-player games with two-outcome.We present a formal framework to represent such best-first search algorithms.The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm.We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K.This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions.We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves.

My thesis is entitled "Contributions to Simulation-based High-dimensional Sequential Decision Making". The context of the thesis is about games, planning and Markov Decision Processes. An agent interacts with its environment by successively making decisions. The agent starts from an initial state until a final state in which the agent can not make decision anymore. At each timestep, the agent receives an observation of the state of the environment. From this observation and its knowledge, the agent makes a decision which modifies the state of the environment. Then, the agent receives a reward and a new observation. The goal is to maximize the sum of rewards obtained during a simulation from an initial state to a final state. The policy of the agent is the function which, from the history of observations, returns a decision. We work in a context where (i) the number of states is huge, (ii) reward carries little information, (iii) the probability to reach quickly a good final state is weak and (iv) prior knowledge is either nonexistent or hardly exploitable. Both applications described in this thesis present these constraints : the game of Go and a 3D simulator of the european project MASH (Massive Sets of Heuristics). In order to take a satisfying decision in this context, several solutions are brought : 1. Simulating with the compromise exploration/exploitation (MCTS) 2. Reducing the complexity by local solving (GoldenEye) 3. Building a policy which improves itself (RBGP) 4. Learning prior knowledge (CluVo+GMCTS) Monte-Carlo Tree Search (MCTS) is the state of the art for the game of Go. From a model of the environment, MCTS builds incrementally and asymetrically a tree of possible futures by performing Monte-Carlo simulations. The tree starts from the current observation of the agent. The agent switches between the exploration of the model and the exploitation of decisions which statistically give a good cumulative reward. We discuss 2 ways for improving MCTS : the parallelization and the addition of prior knowledge. The parallelization does not solve some weaknesses of MCTS; in particular some local problems remain challenges. We propose an algorithm (GoldenEye) which is composed of 2 parts : detection of a local problem and then its resolution. The algorithm of resolution reuses some concepts of MCTS and it solves difficult problems of a classical database. The addition of prior knowledge by hand is laborious and boring. We propose a method called Racing-based Genetic Programming (RBGP) in order to add automatically prior knowledge. The strong point is that RBGP rigorously validates the addition of a prior knowledge and RBGP can be used for building a policy (instead of only optimizing an algorithm). In some applications such as MASH, simulations are too expensive in time and there is no prior knowledge and no model of the environment; therefore Monte-Carlo Tree Search can not be used. So that MCTS becomes usable in this context, we propose a method for learning prior knowledge (CluVo). Then we use pieces of prior knowledge for improving the rapidity of learning of the agent and for building a model, too. We use from this model an adapted version of Monte-Carlo Tree Search (GMCTS). This method solves difficult problems of MASH and gives good results in an application to a word game.

Abstract The development of wireless telecommunication systems has been rapid during the last two decades and the data rates as well as the quality of service (QoS) requirements are continuously growing. Multiple-input multiple-output (MIMO) techniques in combination with orthogonal frequency-division multiplexing (MIMO–OFDM) have been identified as a promising approach for high spectral efficiency wideband systems. The optimal detection method for a coded MIMO–OFDM system with spatial multiplexing (SM) is the maximum a posteriori (MAP) detector, which is often too complex for systems with high order modulation. Suboptimal linear detectors, such as the linear minimum mean square error (LMMSE) criterion based detection, offer low complexity solutions, but have poor performance in correlated fading channels. A list sphere detector (LSD) is a tree search based soft output detector that can be used to approximate the MAP detector with a lower computational complexity. The benefits of the more advanced detectors can be realized especially in a low SNR environment by, e.g., increasing the cell coverage. In this thesis, we consider the linear minimum mean square error (LMMSE) criterion based detectors and more advanced LSDs for detection of SM transmission. The LSD algorithms are not as such feasible for hardware implementation. Therefore, we identify the design choices that relate to the performance and implementation complexity of the LSD algorithms. We give guidelines to the LSD algorithm design and propose the proper trade-off solutions for practical wireless systems. The more stringent requirements call for further research on architectures and implementation. In particular, it is important to address the parallelism and pipelining factors in the architecture design to enable an optimal trade-off between used resources and operating speed. We design pipelined systolic array architecture for LMMSE detector algorithms and efficient architectures with given algorithm properties for the LSD algorithms. We consider the VLSI implementation of the algorithms to study the true performance and complexity. The designed architectures are implemented on a field programmable gate array (FPGA) chip and CMOS application specific integrated circuit (ASIC) technology. Finally, we present some measurement results with a hardware testbed to verify the performance of the considered algorithms. / Tiivistelmä Langattoman tietoliikenteen kehitys on ollut nopeaa viimeisien vuosikymmenien aikana ja järjestelmiltä vaaditaan yhä suurempia datanopeuksia ja luotettavuutta. Multiple-input multiple-output (MIMO) tekniikka yhdistettynä monikantoaaltomodulointiin (MIMO-OFDM) on tunnistettu lupaavaksi järjestelmäksi, joka mahdollistaa tehokkaan taajuusalueen hyödyntämisen. Optimaalinen ilmaisumenetelmä tilakanavoituun (SM) ja koodattuun MIMO-OFDM järjestelmään on maximum a posteriori (MAP) ilmaisin, joka on tyypillisesti liian kompleksinen toteuttaa laajakaistajärjestelmissä, joissa käytetään korkean asteen modulointia. Alioptimaaliset lineaariset ilmaisimet, kuten pienimpään keskineliövirheeseen (LMMSE) perustuvat ilmaisimet, ovat suhteellisen yksinkertaisia toteuttaa nykyteknologialla, mutta niiden suorituskyky on varsin heikko korreloivassa radiokanavassa. Listapalloilmaisin (LSD) on puuhakualgoritmiin perustuva pehmeän ulostulon ilmaisin, joka pystyy jäljittelemään MAP ilmaisinta sitä pienemmällä kompleksisuudella. Kehittyneemmät ilmaisimet, kuten LSD, voivat parantaa langattoman verkon suorituskykyä erityisesti ympäristössä, jossa on matala signaalikohinasuhde, esimerkiksi mahdollistamalla suuremman toiminta-alueen. Tässä väitöskirjassa on tutkittu kahta LMMSE ilmaisinta ja kolmea LSD ilmaisinta SM lähetyksen ilmaisuun. Yleisesti LSD algoritmit eivät ole sellaisenaan toteutuskelpoisia kaupallisiin järjestelmiin. Väitöskirjassa on tämän vuoksi tutkittu LSD:n toteutukseen liittyviä haasteita ja toteutusmenetelmiä ja annetaan suosituksia LSD algorithmien suunnitteluun sekä ehdotetaan sopivia toteutuskompromisseja käytännön langattomiin järjestelmiin. Haastavammat suorituskyky- ja latenssivaatimukset edellyttävät lisätutkimuksia toteutusarkkitehtuureihin ja toteutuksiin. Erityisesti rinnakkaisten resurssien käyttö ja liukuhihnatekniikka toteutusarkkitehtuureissa mahdollistavat optimaalisen kompromissin löytämisen toteutuksessa käytettyjen resurssien ja laskentanopeuden väliltä. Väitöskirjassa suunnitellaan tehokkaat arkkitehtuurit tutkituille LMMSE ja LSD algoritmeille ottaen huomioon niiden ominaisuudet. Väitöskirjassa tutkitaan algoritmien toteutusta VLSI tekniikalla ja pyritään saamaan realistinen arvio algoritmien kompleksisuudesta ja suorituskyvystä. Algoritmeille suunnitellut arkkitehtuurit on toteutettu sekä FPGA piirille että erillisenä toteutuksena ASIC teknologialla. Väitöskirjassa esitetään myös testilaitteistolla tehtyjä mittaustuloksia ja varmistetaan toteutettujen algoritmien suorituskyky.

Nous nous intéressons dans cette thèse aux possibilités d’hybridation entre les méthodes exactes et les méthodes heuristiques afin de pouvoir tirer avantage de chacune des deux approches : optimalité de la résolution exacte, caractère moins déterministe et rapidité de la composante heuristique. Dans l’objectif de résoudre des problèmes NPdifficiles de taille relativement importante tels que les problèmes de transports, nous nous intéressons dans les deux dernières parties de ce mémoire à la conception de méthodes incomplètes basées sur ces hybridations. Dans la première partie, nous allons nous intéresser aux méthodes de résolution par recherche arborescente. Nous introduisons une nouvelle approche pour la gestion des décisions de branchement, que nous appelons Dynamic Learning Search (DLS). Cette méthode définit de manière dynamique des règles de priorité pour la sélection des variables à chaque noeud et l’ordre des valeurs sur lesquelles brancher. Ces règles sont conçues dans une optique de généricité, de manière à pouvoir utiliser la méthode indépendamment du problème traité. Le principe général est de tenir compte par une technique d’apprentissage de l’impact qu’ont eu les décisions de branchement dans les parties déjà explorées de l’arbre. Nous évaluons l’efficacité de la méthode proposée sur deux problèmes classiques : un problème d’optimisation combinatoire et un problème à satisfaction de contraintes. La deuxième partie de ce mémoire traite des recherches à grand voisinage. Nous présentons un nouvel opérateur de voisinage, qui détermine par un algorithme de programmation dynamique la sous-séquence optimale d’un chemin dans un graphe. Nous montrons que cet opérateur est tout particulièrement destiné à des problèmes de tournées pour lesquels tous les noeuds ne nécessitent pas d’être visités. Nous appelons cette classe de problème les Problèmes de Tournées avec Couverture Partielle et présentons quelques problèmes faisant partie de cette classe. Les chapitres 3 et 4 montrent, à travers des tests expérimentaux conséquents, l’efficacité de l’opérateur que nous proposons en appliquant cette recherche à voisinage large sur deux problèmes, respectivement le Problème de l’Acheteur Itinérant (TPP) et le Problème de Voyageur de Commerce Généralisé (GTSP). Nous montrons alors que cet opérateur peut être combiné de manière efficace avec des métaheuristiques classiques, telles que des algorithmes génétiques ou des algorithmes d’Optimisation par Colonies de Fourmis. Enfin, la troisième partie présente des méthodes heuristiques basées sur un algorithme de Génération de Colonnes. Ces méthodes sont appliquées sur un problème complexe : le problème de Tournées de Véhicules avec Contraintes de Chargement à Deux Dimensions (2L-VRP). Nous montrons une partie des possibilités qu’il existe afin de modifier une méthode a priori exacte en une méthode heuristique et nous évaluons ces possibilités à l’aide de tests expérimentaux / We are interested in this thesis in the possibilities of hybridization between the exact methods and the methods heuristics to be able to take advantage of each of both approaches: optimality of the exact resolution, the less determinist character and the speed of the constituent heuristics. In the objective to resolve problems NP-hard of relatively important size such as the transportation problems, we are interested in the last two parts of this report in the conception of incomplete methods based on these hybridizations. In the first part, we are going to be interested in the methods of resolution by tree search. We introduce a new approach for the management of the decisions of connection, which we call Dynamic Learning Search ( DLS). This method defines in a dynamic way rules of priority for the selection of variables in every knot and the order of the values on which to connect. These rules are conceived in an optics of genericity, so as to be able to use the method independently of the treated problem. The general principle is to take into account by a technique of learning of the impact which had the decisions of connection in the parts already investigated in the tree. We estimate the efficiency of the method proposed on two classic problems: a combinatorial optimization problem and a constraints satisfaction problem. The second part of this report handles large neighborhood search. We present a new operator of neighborhood, who determines by an algorithm of dynamic programming the optimal sub-sequence of a road in a graph. We show that this operator is quite particularly intended for problems of tours for which all the vertices do not require to be visited. We call this class of problem the Problems of Tours with Partial Cover and present some problems being a part of this class. Chapters 3 and 4 show, through consequent experimental tests, the efficiency of the operator which we propose by applying this search to wide neighborhood on two problems, respectively the Traveling Purchaser Problem (TPP) and Generalized Traveling Salesman Problem ( GTSP). We show while this operator can be combined in a effective way with classic metaheuristics, such as genetic algorithms or algorithms of Ant Colony Optimization