Spelling suggestions: "subject:"greedy andsearch"" "subject:"greedy 3research""
1 |
Resilient dynamic state estimation in the presence of false information injection attacksLu, Jingyang 01 January 2016 (has links)
The impact of false information injection is investigated for linear dynamic systems with multiple sensors. First, it is assumed that the system is unaware of the existence of false information and the adversary is trying to maximize the negative effect of the false information on Kalman filter's estimation performance under a power constraint. The false information attack under different conditions is mathematically characterized. For the adversary, many closed-form results for the optimal attack strategies that maximize the Kalman filter's estimation error are theoretically derived. It is shown that by choosing the optimal correlation coefficients among the false information and allocating power optimally among sensors, the adversary could significantly increase the Kalman filter's estimation errors.
In order to detect the false information injected by an adversary, we investigate the strategies for the Bayesian estimator to detect the false information and defend itself from such attacks. We assume that the adversary attacks the system with certain probability, and that he/she adopts the worst possible strategy that maximizes the mean squared error (MSE) if the attack is undetected. An optimal Bayesian detector is designed which minimizes the average system estimation error instead of minimizing the probability of detection error, as a conventional Bayesian detector typically does.
The case that the adversary attacks the system continuously is also studied. In this case, sparse attack strategies in multi-sensor dynamic systems are investigated from the adversary's point of view. It is assumed that the defender can perfectly detect and remove the sensors once they are corrupted by false information injected by an adversary. The adversary's goal is to maximize the covariance matrix of the system state estimate by the end of attack period under the constraint that the adversary can only attack the system a few times over the sensor and over the time, which leads to an integer programming problem. In order to overcome the prohibitive complexity of the exhaustive search, polynomial-time algorithms, such as greedy search and dynamic programming, are proposed to find the suboptimal attack strategies. As for greedy search, it starts with an empty set, and one sensor is added at each iteration, whose elimination will lead to the maximum system estimation error. The process terminates when the cardinality of the active set reaches to the sparsity constraint. Greedy search based approaches such as sequential forward selection (SFS), sequential backward selection (SBS), and simplex improved sequential forward selection (SFS-SS) are discussed and corresponding attack strategies are provided. Dynamic programming is also used in obtaining the sub-optimal attack strategy. The validity of dynamic programming lies on a straightforward but important nature of dynamic state estimation systems: the credibility of the state estimate at current step is in accordance with that at previous step.
The problem of false information attack on and the Kalman filter's defense of state estimation in dynamic multi-sensor systems is also investigated from a game theoretic perspective. The relationship between the Kalman filter and the adversary can be regarded as a two-person zero-sum game. The condition under which both sides of the game will reach a Nash equilibrium is investigated.
|
2 |
Automatic Diagnosis of Parkinson’s Disease Using Machine Learning : A Comparative Study of Different Feature Selection Algorithms, Classifiers and Sampling Methods / Automatisk igenkänning av Parkinsons sjukdom med hjälp av maskininlärning : En jämförande studie av olika urvalsalgoritm, klassificerare och provtagningsmetodHe, Jeannie January 2021 (has links)
Over the past few years, several studies have been published to propose algorithms for the automated diagnosis of Parkinson’s Disease using simple exams such as drawing and voice exams. However, at the same time as all classifiers appear to have been outperformed by another classifier in at least one study, there appear to lack a study on how well different classifiers work with a certain feature selection algorithm and sampling method. More importantly, there appear to lack a study that compares the proposed feature selection algorithm and/or sampling method with a baseline that does not involve any feature selection or oversampling. This leaves us with the question of which combination of feature selection algorithm, sampling method and classifier is the best as well as what impact feature selection and oversampling may have on the performance. Given the importance of providing a quick and accurate diagnosis of Parkinson’s disease, a comparison is made between different systems of classifier, feature selection and sampling method with a focus on the predictive performance. A system was chosen as the best system for the diagnosis of Parkinson’s disease based on its comparative predictive performance on two sets of data - one from drawing exams and one from voice exams. / Som en av världens mest vanligaste sjukdom med en tendens att leda till funktionshinder har Parkinsons sjukdom länge varit i centrum av forskning. För att se till att så många som möjligt får en behandling innan det blir för sent har flera studier publicerats för att föreslå algoritmer för automatisk diagnos av Parkinsons sjukdom. Samtidigt som alla klassificerare verkar ha överträffats av en annan klassificerare i minst en studie, verkar det saknas en studie om hur väl olika klassificerare fungerar med en viss kombination av urvalsalgoritm (feature selection algorithm på engelska) och provtagningsmetod. Därutöver verkar det saknas en studie där resultatet från den föreslagna urvalsalgoritmen och/eller samplingsmetoden jämförs med resultatet av att applicera klassificeraren direkt på datan utan någon urvalsalgoritm eller resampling. Detta lämnar oss en fråga om vilket system av klassificerare, urvalsalgoritm och samplingsmetod man bör välja och ifall det är värt att använda en urvalsalgoritm och överprovtagningsmetod. Med tanke på vikten av att snabbt och noggrant upptäcka Parkinsons sjukdom har en jämförelse gjorts för att hitta den bästa kombinationen av klassificerare, urvalsalgoritm och provtagningsalgoritm för den automatiska diagnosen av Parkinsons sjukdom.
|
3 |
Optimization of the car relocation operations in one-way carsharing systems / Optimisation des opérations du redéploiement de véhicules dans un système d'autopartage à sens uniqueZakaria, Rabih 14 December 2015 (has links)
L'autopartage est un service de mobilité qui offre les mêmes avantages que les voitures particulières mais sansnotion de propriété. Les clients du système peuvent accéder aux véhicules sans ou avec réservation préalable. Laflotte de voitures est distribuée entre les stations et les clients peuvent prendre une voiture d'une station et ladéposer dans n'importe quelle autre station (one-way), chaque station disposant d'un nombre maximum de placesde stationnement. La demande pour la prise ou le retour des voitures dans chaque station est souvent asymétriqueentre les stations et varie au cours de la journée. Par conséquent, certaines stations accumulent des voitures etatteignent leur capacité maximale prévenant alors de nouvelles voitures de trouver une place de stationnement.Dans le même temps, des stations se vident et conduisent au rejet de la demande de retrait de clients. Notre travailporte sur l'optimisation des opérations de redéploiement de voitures afin de redistribuer efficacement les voitures surles stations suivant la demande qui varie en fonction du temps et de l'espace. Dans les systèmes d'autopartage àsens unique, le problème du redéploiement de voitures sur les stations est techniquement plus difficile que leproblème de la redistribution des vélos dans les systèmes de vélopartage. Dans ce dernier, on peut utiliser uncamion pour déplacer plusieurs vélos en même temps, alors que nous ne pouvons pas le faire dans le systèmeautopartage en raison de la taille des voitures et de la difficulté de chargement et de déchargement. Ces opérationsaugmentent le coût de fonctionnement du système d'autopartage sur l'opérateur. De ce fait, l'optimisation de cesopérations est essentielle afin de réduire leur coût. Dans cette thèse, nous développons un modèle deprogrammation linéaire en nombre entier pour ce problème. Ensuite, nous présentons trois politiques différentes deredéploiement de voitures que nous mettons en oeuvre dans des algorithmes de recherche gloutonne et nousmontrons que les opérations de redéploiement qui ne considèrent pas les futures demandes ne sont pas efficacesdans la réduction du nombre de demandes rejetées. Les solutions fournies par notre algorithme glouton sontperformantes en temps d'exécution (moins d'une seconde) et en qualité en comparaison avec les solutions fourniespar CPLEX. L'évaluation de la robustesse des deux approches présentées par l'ajout d'un bruit stochastique sur lesdonnées d'entrée montre qu'elles sont très dépendantes des données même avec l'adoption de valeur de seuil deredéploiement. En parallèle à ce travail algorithmique, l'analyse de variance (ANOVA) et des méthodes derégression multilinéaires ont été appliqués sur l'ensemble de données utilisées pour construire un modèle global afind'estimer le nombre de demandes rejetées. Enfin, nous avons développé et comparé deux algorithmesévolutionnaires multicritères pour prendre en compte l'indécision sur les objectifs de l'optimisation, NSGA-II et unalgorithme mémétique qui a montré une bonne performance pour résoudre ce problème. / To buy it. Users can have access to vehicles on the go with or without reservation. Each station has a maximumnumber of parking places. In one-way carsharing system, users can pick up a car from a station and drop it in anyother station. The number of available cars in each station will vary based on the departure and the arrival of cars oneach station at each time of the day. The demand for taking or returning cars in each station is often asymmetric andis fluctuating during the day. Therefore, some stations will accumulate cars and will reach their maximum capacitypreventing new arriving cars from finding a parking place, while other stations will become empty which lead to therejection of new users demand to take a car. Users expect that cars are always available in stations when they needit, and they expect to find a free parking place at the destination station when they want to return the rented car aswell. However, maintaining this level of service is not an easy task. For this sake, carsharing operators recruitemployees to relocate cars between the stations in order to satisfy the users' demands.Our work concerns the optimization of the car relocation operations in order to efficiently redistribute the cars overthe stations with regard to user demands, which are time and space dependent. In one-way carsharing systems, therelocation problem is technically more difficult than the relocation problem in bikesharing systems. In the latter, wecan use trucks to move several bikes at the same time, while we cannot do this in carsharing system because of thesize of cars and the difficulty of loading and unloading cars. These operations increase the cost of operating thecarsharing system.As a result, optimizing these operations is crucial in order to reduce the cost of the operator. In this thesis, we modelthis problem as an Integer Linear Programming model. Then we present three different car relocation policies thatwe implement in a greedy search algorithm. The comparison between the three policies shows that car relocationoperations that do not consider future demands are not effective in reducing the number of rejected demands.Results prove that solutions provided by our greedy algorithm when using a good policy, are competitive withCPLEX solutions. Furthermore, adding stochastic modification on the input data proves that the robustness of thetwo presented approaches to solve the relocation problem is highly dependent on the input demand even afteradding threshold values constraints. After that, the analysis of variance (ANOVA) and the multi-linear regressionmethods were applied on the used dataset in order to build a global model to estimate the number of rejecteddemands. Finally, we developed and compared two multi-objectives evolutionary algorithms to deal with thedecisional aspect of the car relocation problem using NSGA-II and memetic algorithms.
|
4 |
Exploitation d’informations riches pour guider la traduction automatique statistique / Complex Feature Guidance for Statistical Machine TranslationMarie, Benjamin 25 March 2016 (has links)
S'il est indéniable que de nos jours la traduction automatique (TA) facilite la communication entre langues, et plus encore depuis les récents progrès des systèmes de TA statistiques, ses résultats sont encore loin du niveau de qualité des traductions obtenues avec des traducteurs humains.Ce constat résulte en partie du mode de fonctionnement d'un système de TA statistique, très contraint sur la nature des modèles qu'il peut utiliser pour construire et évaluer de nombreuses hypothèses de traduction partielles avant de parvenir à une hypothèse de traduction complète. Il existe cependant des types de modèles, que nous qualifions de « complexes », qui sont appris à partir d'informations riches. Si un enjeu pour les développeurs de systèmes de TA consiste à les intégrer lors de la construction initiale des hypothèses de traduction, cela n'est pas toujours possible, car elles peuvent notamment nécessiter des hypothèses complètes ou impliquer un coût de calcul très important. En conséquence, de tels modèles complexes sont typiquement uniquement utilisés en TA pour effectuer le reclassement de listes de meilleures hypothèses complètes. Bien que ceci permette dans les faits de tirer profit d'une meilleure modélisation de certains aspects des traductions, cette approche reste par nature limitée : en effet, les listes d'hypothèses reclassées ne représentent qu'une infime partie de l'espace de recherche du décodeur, contiennent des hypothèses peu diversifiées, et ont été obtenues à l'aide de modèles dont la nature peut être très différente des modèles complexes utilisés en reclassement.Nous formulons donc l'hypothèse que de telles listes d'hypothèses de traduction sont mal adaptées afin de faire s'exprimer au mieux les modèles complexes utilisés. Les travaux que nous présentons dans cette thèse ont pour objectif de permettre une meilleure exploitation d'informations riches pour l'amélioration des traductions obtenues à l'aide de systèmes de TA statistique.Notre première contribution s'articule autour d'un système de réécriture guidé par des informations riches. Des réécritures successives, appliquées aux meilleures hypothèses de traduction obtenues avec un système de reclassement ayant accès aux mêmes informations riches, permettent à notre système d'améliorer la qualité de la traduction.L'originalité de notre seconde contribution consiste à faire une construction de listes d'hypothèses par passes multiples qui exploitent des informations dérivées de l'évaluation des hypothèses de traduction produites antérieurement à l'aide de notre ensemble d'informations riches. Notre système produit ainsi des listes d'hypothèses plus diversifiées et de meilleure qualité, qui s'avèrent donc plus intéressantes pour un reclassement fondé sur des informations riches. De surcroît, notre système de réécriture précédent permet d'améliorer les hypothèses produites par cette deuxième approche à passes multiples.Notre troisième contribution repose sur la simulation d'un type d'information idéalisé parfait qui permet de déterminer quelles parties d'une hypothèse de traduction sont correctes. Cette idéalisation nous permet d'apporter une indication de la meilleure performance atteignable avec les approches introduites précédemment si les informations riches disponibles décrivaient parfaitement ce qui constitue une bonne traduction. Cette approche est en outre présentée sous la forme d'une traduction interactive, baptisée « pré-post-édition », qui serait réduite à sa forme la plus simple : un système de TA statistique produit sa meilleure hypothèse de traduction, puis un humain apporte la connaissance des parties qui sont correctes, et cette information est exploitée au cours d'une nouvelle recherche pour identifier une meilleure traduction. / Although communication between languages has without question been made easier thanks to Machine Translation (MT), especially given the recent advances in statistical MT systems, the quality of the translations produced by MT systems is still well below the translation quality that can be obtained through human translation. This gap is partly due to the way in which statistical MT systems operate; the types of models that can be used are limited because of the need to construct and evaluate a great number of partial hypotheses to produce a complete translation hypothesis. While more “complex” models learnt from richer information do exist, in practice, their integration into the system is not always possible, would necessitate a complete hypothesis to be computed or would be too computationally expensive. Such features are therefore typically used in a reranking step applied to the list of the best complete hypotheses produced by the MT system.Using these features in a reranking framework does often provide a better modelization of certain aspects of the translation. However, this approach is inherently limited: reranked hypothesis lists represent only a small portion of the decoder's search space, tend to contain hypotheses that vary little between each other and which were obtained with features that may be very different from the complex features to be used during reranking.In this work, we put forward the hypothesis that such translation hypothesis lists are poorly adapted for exploiting the full potential of complex features. The aim of this thesis is to establish new and better methods of exploiting such features to improve translations produced by statistical MT systems.Our first contribution is a rewriting system guided by complex features. Sequences of rewriting operations, applied to hypotheses obtained by a reranking framework that uses the same features, allow us to obtain a substantial improvement in translation quality.The originality of our second contribution lies in the construction of hypothesis lists with a multi-pass decoding that exploits information derived from the evaluation of previously translated hypotheses, using a set of complex features. Our system is therefore capable of producing more diverse hypothesis lists, which are globally of a better quality and which are better adapted to a reranking step with complex features. What is more, our forementioned rewriting system enables us to further improve the hypotheses produced with our multi-pass decoding approach.Our third contribution is based on the simulation of an ideal information type, designed to perfectly identify the correct fragments of a translation hypothesis. This perfect information gives us an indication of the best attainable performance with the systems described in our first two contributions, in the case where the complex features are able to modelize the translation perfectly. Through this approach, we also introduce a novel form of interactive translation, coined "pre-post-editing", under a very simplified form: a statistical MT system produces its best translation hypothesis, then a human indicates which fragments of the hypothesis are correct, and this new information is then used during a new decoding pass to find a new best translation.
|
5 |
[en] ON MIMO COMMUNICATIONS SYSTEMS WITH 1-BIT QUANTIZATION AND COMPARATOR NETWORKS AT THE RECEIVER / [pt] SISTEMAS DE COMUNICAÇÃO MIMO COM QUANTIZAÇÃO DE 1-BIT E REDES COMPARADORAS NO RECEPTORANA BEATRIZ LOUREIRO B FERNANDES 09 August 2021 (has links)
[pt] Os sistemas de múltiplas entradas e múltiplas saídas (MIMO) empregam
um número crescente de antenas, o que leva a relevantes consumo de energia
e custo de hardware dos front-ends correspondentes. Nesse contexto,
o uso de conversores analógico-digitais (ADCs) de baixa resolução é promovido
como uma solução promissora para este problema. Neste estudo
consideramos um receptor MIMO de baixa resolução que implica que os
sinais recebidos são processados simultaneamente pelos 1-bit ADCs e pela
rede comparadora. Os sinais de entrada da rede comparadora podem vir
de antenas diferentes, de modo que a extensão da rede comparadora pode
ser interpretada como canais virtuais com saídas binárias. Com base nesses
receptores MIMO de baixa resolução, desenvolvemos um estimador de canal
e detector lineares de baixa resolução baseados no critério de mínimo erro
médio quadrático (LRA-LMMSE) de acordo com o teorema de Bussgang.
Duas redes de comparação são propostas, nomeadas, redes total e parcialmente
conectadas. Também desenvolvemos uma rede parcialmente conectada
baseada em busca gananciosa que usa muito menos comparadores para
obter um desempenho bem próximo ao da rede totalmente conectada. Os
resultados numéricos mostram que adicionar canais virtuais pode ser melhor
do que adicionar canais físicos extras que correspondem a antenas de
recepção adicionais em termos de taxa de erro de bit (BER). Além disso,
ao empregar o estimador de canal proposto e seu erro de estimativa correspondente,
construímos um limite inferior na taxa de soma ergódica para o
receptor LRA-MMSE. Os resultados de simulação mostram que os sistemas
com a proposta sistemas MIMO auxiliados por rede com quantização de
1-bit no receptor superam o convencional sistema MIMO de 1-bit em termos
de desempenho de BER e erro quadrático médio (MSE). Além disso,
as simulações numéricas confirmam uma vantagem significativa em termos
de taxa de soma para o sistema proposto. / [en] Multiple-input multiple-output (MIMO) systems employs an increasing
number of antennas, which leads to relevant energy consumption and hardware
cost of the corresponding front ends. In this context, the use of lowresolution
analog to digital converters (ADCs) is promoted as a promising
solution to this problem. In this study we consider a low-resolution MIMO
receiver which implies that the received signals simultaneously are processed
by the 1-bit ADCs and the comparator network. The input signals for the
comparator network can come from different antennas, such that the comparator
network extension can be interpreted as virtual channels with binary
outputs. Based on such low-resolution MIMO receivers, we develop
low-resolution aware linear minimum mean-squared error (LRA-LMMSE)
channel estimator and detector according to the Bussgang theorem. Two
comparator networks are proposed, namely, fully and partially connected
networks. We also devise a greedy search-based partially connected network
that can use much less comparators to approach the performance of the
fully connected network. Numerical results shows that adding virtual channels
can be better than adding extra physical channels which corresponds
to additional receive antennas in terms of bit error rate (BER). Furthermore,
by employing the proposed channel estimator and its corresponding
estimation error, we build up a lower bound on the ergodic sum rate for
the LRA-LMMSE receiver. Simulation results show that the systems with
the proposed network-aided MIMO systems with 1-bit quantization at the
receiver outperforms the conventional 1-bit MIMO system in terms of BER
and mean-square error (MSE) performances. Moreover, numerical simulations
confirm a significant advantage in terms of sum rate for the proposed
system.
|
6 |
Simulation and optimization models for scheduling and balancing the public bicycle-sharing systems / Modéles de simulation et d'optimisation pour l'ordonnancement et l'équilibrage des systèmes de vélos en libre-serviceKadri, Ahmed Abdelmoumene 11 December 2015 (has links)
Les enjeux du développement durable, le réchauffement climatique, la pollution dans les grandes villes, la congestion et les nuisances sonores, l'augmentation des prix de carburants, sont parmi des nombreux facteurs qui incitent les pays développés à l'innovation dans les transports publics. Dans ce contexte, l'introduction des systèmes de vélos en libre-service, au cours de ces dernières années, est une des solutions adoptées par de nombreuses grandes villes. Malgré leur succès fulgurant dans le monde entier, il existe peu d'études fondamentales sur ce type transport urbain. Pourtant, leur exploitation et leur management par des opérateurs soulèvent de nombreuses questions notamment d'ordre opérationnel. Dans ce contexte, cette thèse s'adresse aux problèmes d'ordonnancement et de rééquilibrage des stations de vélos en libre-service. Ce sont des problèmes cruciaux pour la qualité de service et la viabilité économique de tels systèmes. Le rééquilibrage consiste à redistribuer le nombre de vélos entre les différentes stations afin de satisfaire au mieux les demandes des usagers. Cette régulation se fait souvent par le biais de véhicules spécifiques qui font des tournées autour des différentes stations. Ainsi, deux problèmes d'optimisation difficiles se posent : la recherche de la meilleure tournée du véhicule de régulation (ordonnancement de la tournée) et la détermination des nombres de véhicules à utiliser (rééquilibrage des stations). Dans cette optique, les travaux de cette thèse constituent une contribution à la modélisation et à l'optimisation de performances des systèmes de vélos en libre-service en vue de leur rééquilibrage et leur ordonnancement. Plusieurs méthodes d'optimisation et ont été développées et testées. De telles méthodes incorporent différentes approches de simulation ou d'optimisation comme les réseaux de Petri, les algorithmes génétiques, les algorithmes gloutons, les algorithmes de recherche par voisinage, la méthode arborescente de branch-and-bound, l'élaboration des bornes supérieures et inférieures, etc. Différentes facettes du problème ont été étudiées : le cas statique, le cas dynamique, l'ordonnancement et le rééquilibrage avec un seul (ou multiple) véhicule(s). Afin de montrer la pertinence de nos approches, la thèse comporte également plusieurs applications réelles et expérimentations / In our days, developed countries have to face many public transport problems, including traffic congestion, air pollution, global oil prices and global warming. In this context, Public Bike sharing systems are one of the solutions that have been recently implemented in many big cities around the world. Despite their apparent success, the exploitation and management of such transportation systems imply crucial operational challenges that confronting the operators while few scientific works are available to support such complex dynamical systems. In this context, this thesis addresses the scheduling and balancing in public bicycle-sharing systems. These problems are the most crucial questions for their operational efficiency and economic viability. Bike sharing systems are balanced by distributing bicycles from one station to another. This procedure is generally ensured by using specific redistribution vehicles. Therefore, two hard optimization problems can be considered: finding a best tour for the redistribution vehicles (scheduling) and the determination of the numbers of bicycles to be assigned and of the vehicles to be used (balancing of the stations). In this context, this thesis constitutes a contribution to modelling and optimizing the bicycle sharing systems' performances in order to ensure a coherent scheduling and balancing strategies. Several optimization methods have been proposed and tested. Such methods incorporate different approaches of simulation or optimization like the Petri nets, the genetic algorithms, the greedy search algorithms, the local search algorithms, the arborescent branch-and-bound algorithms, the elaboration of upper and lower bounds, ... Different variants of the problem have been studied: the static mode, the dynamic mode, the scheduling and the balancing by using a single or multiple vehicle(s). In order to demonstrate the coherence and the suitability of our approaches, the thesis contains several real applications and experimentations
|
7 |
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.
|
Page generated in 0.1916 seconds