Academic literature on the topic 'Algorithmes online'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Algorithmes online.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Algorithmes online"
1
Tornede, Alexander, Viktor Bengs, and Eyke Hüllermeier. "Machine Learning for Online Algorithm Selection under Censored Feedback." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 9 (2022): 10370–80. http://dx.doi.org/10.1609/aaai.v36i9.21279.
Full textAbstract:
In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. As the latter is known to exhibit a heavy-tail distribution, an algorithm is normally stopped when exceeding a predefined upper time limit. As a consequence, machine learning methods used to optimize an algorithm selection strategy in a data-driven manner need to deal with right-censored samples, a problem that has received little attention in the literature so far. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. Moreover, we adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon. In an extensive experimental evaluation on an adapted version of the ASlib benchmark, we demonstrate that theoretically well-founded methods based on Thompson sampling perform specifically strong and improve in comparison to existing methods.
2
Lange, Tomer, Joseph (Seffi) Naor, and Gala Yadgar. "Offline and Online Algorithms for SSD Management." ACM SIGMETRICS Performance Evaluation Review 50, no. 1 (2022): 89–90. http://dx.doi.org/10.1145/3547353.3522630.
Full textAbstract:
The abundance of system-level optimizations for reducing SSD write amplification, which are usually based on experimental evaluation, stands in contrast to the lack of theoretical algorithmic results in this problem domain. To bridge this gap, we explore the problem of reducing write amplification from an algorithmic perspective, considering it in both offline and online settings. In the offline setting, we present a near-optimal algorithm. In the online setting, we first consider algorithms that have no prior knowledge about the input. We present a worst case lower bound and show that the greedy algorithm is optimal in this setting. Then we design an online algorithm that uses predictions about the input. We show that when predictions are pretty accurate, our algorithm circumvents the above lower bound. We complement our theoretical findings with an empirical evaluation of our algorithms, comparing them with the state-of-the-art scheme. The results confirm that our algorithms exhibit an improved performance for a wide range of input traces.
3
Xu, Chenyang, and Benjamin Moseley. "Learning-Augmented Algorithms for Online Steiner Tree." Proceedings of the AAAI Conference on Artificial Intelligence 36, no. 8 (2022): 8744–52. http://dx.doi.org/10.1609/aaai.v36i8.20854.
Full textAbstract:
This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the online Steiner tree problem in this model for both directed and undirected graphs. Steiner tree is known to have strong lower bounds in the online setting and any algorithm’s worst-case guarantee is far from desirable. This paper considers algorithms that predict which terminal arrives online. The predictions may be incorrect and the algorithms’ performance is parameterized by the number of incorrectly predicted terminals. These guarantees ensure that algorithms break through the online lower bounds with good predictions and the competitive ratio gracefully degrades as the prediction error grows. We then observe that the theory is predictive of what will occur empirically. We show on graphs where terminals are drawn from a distribution, the new online algorithms have strong performance even with modestly correct predictions.
4
Smale, Steve, and Yuan Yao. "Online Learning Algorithms." Foundations of Computational Mathematics 6, no. 2 (2005): 145–70. http://dx.doi.org/10.1007/s10208-004-0160-z.
Full text
5
BARBAKH, WESAM, and COLIN FYFE. "ONLINE CLUSTERING ALGORITHMS." International Journal of Neural Systems 18, no. 03 (2008): 185–94. http://dx.doi.org/10.1142/s0129065708001518.
Full textAbstract:
We introduce a set of clustering algorithms whose performance function is such that the algorithms overcome one of the weaknesses of K-means, its sensitivity to initial conditions which leads it to converge to a local optimum rather than the global optimum. We derive online learning algorithms and illustrate their convergence to optimal solutions which K-means fails to find. We then extend the algorithm by underpinning it with a latent space which enables a topology preserving mapping to be found. We show visualisation results on some standard data sets.
6
Sharma, Vishal, Kirsten E. Bray, Neha Kumar, and Rebecca E. Grinter. "Romancing the Algorithm." Proceedings of the ACM on Human-Computer Interaction 6, CSCW2 (2022): 1–29. http://dx.doi.org/10.1145/3555651.
Full textAbstract:
Many romance novelists have shifted to self-publishing mediated through online technologies, such as online retailer platforms for selling novels and social media for marketing. However, engagement with such complex algorithmic systems has posed challenges, including understanding continually changing algorithms, frequently changing silently, impacting novelists' successful professionalization and monetization. We conducted surveys and interviews with romance novelists to examine how they experience, interpret, and navigate algorithms. Our findings detail interviewees' efforts to comprehend algorithms, both individually and collectively, and leverage that comprehension to navigate and manipulate algorithms. We discuss how our interviewees constructed literacy of precarious algorithms on their work platforms, suggesting implications for designing algorithmic systems supporting digital work.
7
K, Kousalya, and Balasubramanie P. "Online Grid Scheduling Using Ant Algorithm." International Journal of Engineering and Technology 1, no. 1 (2009): 21–26. http://dx.doi.org/10.7763/ijet.2009.v1.4.
Full text
8
Möhlmann, Mareike, Lior Zalmanson, Ola Henfridsson, and Robert Wayne Gregory. "Algorithmic Management of Work on Online Labor Platforms: When Matching Meets Control." MIS Quarterly 45, no. 4 (2021): 1999–2022. http://dx.doi.org/10.25300/misq/2021/15333.
Full textAbstract:
Online labor platforms (OLPs) can use algorithms along two dimensions: matching and control. While previous research has paid considerable attention to how OLPs optimize matching and accommodate market needs, OLPs can also employ algorithms to monitor and tightly control platform work. In this paper, we examine the nature of platform work on OLPs, and the role of algorithmic management in organizing how such work is conducted. Using a qualitative study of Uber drivers’ perceptions, supplemented by interviews with Uber executives and engineers, we present a grounded theory that captures the algorithmic management of work on OLPs. In the context of both algorithmic matching and algorithmic control, platform workers experience tensions relating to work execution, compensation, and belonging. We show that these tensions trigger market-like and organization-like response behaviors by platform workers. Our research contributes to the emerging literature on OLPs.
9
Lange, Tomer, Joseph (Seffi) Naor, and Gala Yadgar. "Offline and Online Algorithms for SSD Management." Communications of the ACM 66, no. 7 (2023): 129–37. http://dx.doi.org/10.1145/3596205.
Full textAbstract:
Flash-based solid-state drives (SSDs) are a key component in most computer systems, thanks to their ability to support parallel I/O at sub-millisecond latency and consistently high throughput. At the same time, due to the limitations of the flash media, they perform writes out-of-place, often incurring a high internal overhead which is referred to as write amplification. Minimizing this overhead has been the focus of numerous studies by the systems research community for more than two decades. The abundance of system-level optimizations for reducing SSD write amplification, which is typically based on experimental evaluation, stands in stark contrast to the lack of theoretical algorithmic results in this problem domain. To bridge this gap, we explore the problem of reducing write amplification from an algorithmic perspective, considering it in both offline and online settings. In the offline setting, we present a near-optimal algorithm. In the online setting, we first consider algorithms that have no prior knowledge about the input and show that in this case, the greedy algorithm is optimal. Then, we design an online algorithm that uses predictions about the input. We show that when predictions are relatively accurate, our algorithm significantly improves over the greedy algorithm. We complement our theoretical findings with an empirical evaluation of our algorithms, comparing them with the state-of-the-art scheme. The results confirm that our algorithms exhibit an improved performance for a wide range of input traces.
10
R, Velvizhi, and Jayapriya D. "Decoupling Online Algorithms from Symmetric Encryption in Hierarchical Databases." Journal of Advanced Research in Dynamical and Control Systems 11, no. 0009-SPECIAL ISSUE (2019): 1004–9. http://dx.doi.org/10.5373/jardcs/v11/20192664.
Full textDissertations / Theses on the topic "Algorithmes online"
1
Liu, Ming. "Design and Evaluation of Algorithms for Online Machine Scheduling Problems." Phd thesis, Ecole Centrale Paris, 2009. http://tel.archives-ouvertes.fr/tel-00453316.
Full textAbstract:
Dans cette thèse, nous proposons et évaluons des algorithmes pour résoudre des problèmes d'ordonnancement en ligne. Pendant des décennies, les études en ordonnancement considèrent des modèles déterministes où toutes les informations nécessaires pour la définition du problème sont supposées connues à l'avance. Cette hypothèse n'est généralement pas réaliste. Ceci a motivé les études sur l'ordonnancement en ligne. Dans un problème d'ordonnancement en ligne, un algorithme doit prendre des décisions sans connaissance du futur. L'analyse compétitive est généralement la méthode utilisée pour évaluer les performances de tels algorithmes. Dans cette analyse, la performance d'un algorithme en ligne est mesurée par le ratio compétitif qui est le ratio dans le pire cas entre la performance de la solution obtenue et celle d'une solution optimale hors ligne. Nous considérons principalement deux paradigmes en ligne: celui où les tâches se présentent dans la liste et celui où les tâches arrivent au fur et à mesure. Sur la base de ces deux paradigmes, nous considérons différents modèles : une seule machine, deux machines identiques parallèles, deux machines uniformes parallèles, batch machines et open shop. Pour chacun des problèmes, nous démontrons une borne inférieure de ratios compétitifs et proposons des algorithmes en ligne. Ensuite, nous évaluons la performance de ces algorithmes à l'aide de l'analyse compétitive. Pour certains problèmes, nous montrons que les algorithmes proposés sont optimaux dans le sens où le ratio compétitif est égal à la borne inférieure.
2
Jin, Shendan. "Online computation beyond standard models." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS152.
Full textAbstract:
Dans le cadre standard du calcul en ligne, l’entrée de l’algorithme n’est pas entièrement connue à l’avance, mais elle est révélée progressivement sous forme d’une séquence de requêtes. Chaque fois qu'une requête arrive, l'algorithme en ligne doit prendre des décisions irrévocables pour servir la demande, sans connaissance des requêtes futures. Dans le domaine des algorithmes en ligne, le cadre standard utilisé pour évaluer les performances des algorithmes en ligne est l’analyse compétitive. De manière informelle, le concept d’analyse compétitive consiste à comparer les performances d’un algorithme en ligne dans le pire des cas à une solution optimale hors ligne qui aurait pu être calculée si toutes les données étaient connues d’avance. Dans cette thèse, nous étudierons de nouvelles façons d'approcher les problèmes en ligne. Dans un premier temps, nous étudions le calcul en ligne dans le modèle avec ré-optimisation, dans lequel l'irrévocabilité des décisions en ligne est relâchée. Autrement dit, l'algorithme en ligne est autorisé à revenir en arrière et changer les décisions précédemment prises. Plus précisément, nous montrons comment identifier le compromis entre le nombre de ré-optimisation et les performances des algorithmes en ligne pour le problème de couplage maximale en ligne. De plus, nous étudions des mesures autres que l'analyse compétitive pour évaluer les performances des algorithmes en ligne. Nous observons que parfois, l'analyse compétitive ne peut pas distinguer les performances de différents algorithmes en raison de la nature la plus défavorable du ratio de compétitivité. Nous démontrons qu'une situation similaire se pose dans le problème de la recherche linéaire. Plus précisément, nous revisitons le problème de la recherche linéaire et introduisons une mesure, qui peut être appliquée comme un raffinement du ratio de compétitivité. Enfin, nous étudions le calcul en ligne dans le modèle avec des conseils, dans lequel l'algorithme reçoit en entrée non seulement une séquence de requêtes, mais aussi quelques conseils sur la séquence de requêtes. Plus précisément, nous étudions un modèle récent avec des conseils non fiables, dans lequel les conseils peuvent être fiables ou non. Supposons que dans ce dernier cas, les conseils peuvent être générés à partir d'une source malveillante. Nous montrons comment identifier une stratégie optimale de Pareto pour le problème online bidding dans le modèle de conseil non fiable<br>In the standard setting of online computation, the input is not entirely available from the beginning, but is revealed incrementally, piece by piece, as a sequence of requests. Whenever a request arrives, the online algorithm has to make immediately irrevocable decisions to serve the request, without knowledge on the future requests. Usually, the standard framework to evaluate the performance of online algorithms is competitive analysis, which compares the worst-case performance of an online algorithm to an offline optimal solution. In this thesis, we will study some new ways of looking at online problems. First, we study the online computation in the recourse model, in which the irrevocability on online decisions is relaxed. In other words, the online algorithm is allowed to go back and change previously made decisions. More precisely, we show how to identify the trade-off between the number of re-optimization and the performance of online algorithms for the online maximum matching problem. Moreover, we study measures other than competitive analysis for evaluating the performance of online algorithms. We observe that sometimes, competitive analysis cannot distinguish the performance of different algorithms due to the worst-case nature of the competitive ratio. We demonstrate that a similar situation arises in the linear search problem. More precisely, we revisit the linear search problem and introduce a measure, which can be applied as a refinement of the competitive ratio. Last, we study the online computation in the advice model, in which the algorithm receives as input not only a sequence of requests, but also some advice on the request sequence. Specifically, we study a recent model with untrusted advice, in which the advice can be either trusted or untrusted. Assume that in the latter case, the advice can be generated from a malicious source. We show how to identify a Pareto optimal strategy for the online bidding problem in the untrusted advice model
3
Liu, Ming Chu Chengbin. "Design and Evaluation of Algorithms for Online Machine Scheduling Problems." S. l. : S. n, 2009. http://theses.abes.fr/2009ECAP0028.
Full text
4
Nouinou, Hajar. "Ordonnancement semi-online sur machine unitaire pour l’industrie du futur." Thesis, Troyes, 2021. http://www.theses.fr/2021TROY0028.
Full textAbstract:
Nous étudions la valeur de l’information dans des problèmes d’ordonnancement semi-online sur machine unitaire. Nous proposons ainsi des algorithmes semi-online pour résoudre ces problèmes et nous évaluons leurs performances. Contrairement aux problèmes d’ordonnancement classiques offline où le décideur connaît toutes les caractéristiques de l’instance à ordonnancer, dans les problèmes d’ordonnancement online ou semi-online la prise de décision est effectuée sans aucune information ou uniquement avec des informations partielles sur l’instance. Notre travail consiste à distinguer les informations qui peuvent améliorer la prise de décision dans un contexte d’ordonnancement semi-online des informations qui, même disponibles, n’apportent aucune amélioration. Nous traitons principalement les problèmes semi-online dont la fonction objective est la minimisation de la somme des dates de fin des tâches sur machine unitaire. Nous commençons par étudier plusieurs modèles semi-online avec des informations partielles sur les temps de traitement des tâches. Ensuite, nous considérons le problème avec une information sur les dates d’arrivée et finalement la combinaison de l’information sur les temps de traitements et les dates d’arrivée des tâches. Pour chaque problème étudié où l’information partielle est identifiée comme utile, nous proposons un algorithme semi-online intégrant l’information dans la prise de décision. Ensuite, nous évaluons sa performance à l’aide d’une analyse de compétitivité ou par étude expérimentale comparative<br>We study the value of information in semi-online single machine scheduling problems. We propose semi-online algorithms to solve these problems and evaluate their performances. Unlike the classical offline scheduling problems where the decision maker knows all characteristics of the instance to be scheduled, in online scheduling problems the decision-making is performed without previous information or only with partial information about the instance. Our work consists in distinguishing information that can improve the decision-making in a semi-online scheduling context from information that, even if available, does not bring any improvement. We mainly deal with semi-online problems for minimising the total completion time on a single machine. We start by studying several semi-online models with partial information on processing times of jobs. Then, we consider the problem with information on jobs release dates and finally the combination of information on processing times and jobs release dates. For each studied problem where partial information is identified as useful, we propose a semi-online algorithm integrating the information into the decision-making. We then evaluate its performance using a competitive analysis or a comparative experimental study
5
Renault, Marc Paul. "Lower and upper bounds for online algorithms with advice." Paris 7, 2014. http://www.theses.fr/2014PA077196.
Full textAbstract:
Les algorithmes en ligne fonctionnent dans un contexte où l'entrée est révélé au fur et à mesure du temps; chaque morceau révélé est appelé une demande. Après réception de chaque demahde, les algorithmes en ligne doivent prendre une action avant que la prochaine demande soit révélée, c'est-à-dire que les algorithmes en ligne doivent prendre une décision irrévocable basée sur les demandes déjà révélées sans aucune connaissance des demandes à venir. Le but est d'optimiser une fonction de coût dépendante de l'entrée. L'analyse compétitive est la méthode standard utilisée pour analyser la qualité des algorithmes en ligne. Le ratio compétitif est un ratio de pire cas, parmi toutes les séquences de demande finis, entre la performance de l'algorithme en ligne contre un algorithme optimal hors ligne pour la même séquence. Le ratio compétitif compare la performance d'un algorithme sans aucune connaissance de l'avenir contre un algorithme en pleine connaissance de l'avenir. Car l'absence totale de connaissance de l'avenir n'est souvent pas une hypothèse raisonnable, des modèles ont été proposés, appelés algorithmes en ligne avec conseil, qui donne les algorithmes en ligne l'accès à une quantité quantifiée des connaissances de l'avenir. L'intérêt de ce modèle est d'examiner comment le ratio compétitif change en fonction de la quantité de conseil. Dans cette thèse, il est présenté des bornes supérieures et inférieures dans ce modèle pour des problèmes en ligne classiques, tels que le problème de la k-serveur, de bin packing, de dual bin packing (sac à dos multiple), d'ordonnancement sur m machines identiques, du tampon de réordonnancement et de la mise à jour de la liste<br>Online algorithms operate in a setting where the input is revealed piece by piece; the pieces are called requests. After receiving each request, online algorithms must take an action before the next request is revealed, i. E. Online algorithms must make irrevocable decisions based on the input revealed so far without any knowledge of the future input. The goal is to optimize some cost function over the input. Competitive analysis is the standard method used to analyse the quality of online algorithms. The competitive ratio is the worst case ratio, over all valid finite request sequences, of the online algorithm's performance against an optimal offline algorithm for the same request sequence. The competitive ratio compares the performance of an algorithm with no knowledge about the future against an algorithm with full knowledge about the future. Since the complete absence of future knowledge is often not a reasonable assumption, models, termed online algorithms with advice, which give the online algorithms access to a quantified amount of future knowledge, have been proposed. The interest in this model is in examining how the competitive ratio changes as a function of the amount of advice. In this thesis, we present upper and lower bounds in the advice model for classical online problems such as the k-server problem, the bin packing problem, the dual bin packing (multiple knapsack) problem, scheduling problem on m identical machines, the reordering buffer management problem and the list update problem
6
Teiller, Alexandre. "Aspects algorithmiques de l'optimisation « multistage »." Electronic Thesis or Diss., Sorbonne université, 2020. http://www.theses.fr/2020SORUS471.
Full textAbstract:
En optimisation combinatoire classique, étant donné une instance d’un problème, il est demandé de trouver une bonne solution réalisable. Cependant, dans de nombreux cas, les données peuvent évoluer au cours du temps et il est demandé de résoudre une séquence d’instances. Gupta et al. (2014) et Eisenstat et al. (2014) ont proposé un modèle multistage où étant donné un horizon de temps, l’entrée est une séquence d’instances (une pour chaque pas de temps), et l’objectif est de trouver une séquence de solutions (une pour chaque pas de temps) qui atteindrait un compromis entre la qualité des solutions à chaque pas de temps et la stabilité/similarité des solutions pour des pas de temps consécutifs. Dans le Chapitre 1, nous présenterons un aperçu des problèmes d’optimisation prenant en compte des données évolutives. Dans le Chapitre 2, le problème du sac-à-dos est traité dans un contexte offline. La contribution principale est un schéma d’approximation polynomiale (PTAS). Dans le Chapitre 3, le cadre multistage est étudié pour des problèmes multistage dans un contexte online. La contribution principale est l’introduction d’une structure pour ces problèmes avec des bornes presque serrées supérieures et inférieures sur les meilleurs ratios compétitifs de ces modèles. Enfin, dans le Chapitre 4 est présenté une application directe du cadre multistage dans un contexte musical, i.e l’orchestration assistée par ordinateur avec son cible. Nous avons présenté une analyse théorique du problème, en montrant sa NP-difficulté, des résultats d’approximation ainsi que des expérimentations<br>N a classical combinatorial optimization setting, given an instance of a problem one needs to find a good feasible solution. However, in many situations, the data may evolve over time and one has to solve a sequence of instances. Gupta et al. (2014) and Eisenstat et al. (2014) proposed a multistage model where given a time horizon the input is a sequence of instances (one for each time step), and the goal is to find a sequence of solutions (one for each time step) reaching a trade-off between the quality of the solutions in each time step and the stability/similarity of the solutions in consecutive time steps. In Chapter 1 of the thesis, we will present an overview of optimization problems tackling evolving data. Then, in Chapter 2, the multistage knapsack problem is addressed in the offline setting. The main contribution is a polynomial time approximation scheme (PTAS) for the problem in the offline setting. In Chapter 3, the multistage framework is studied for multistage problems in the online setting. The main contribution of this chapter was the introduction of a structure for these problems and almost tight upper and lower bounds on the best-possible competitive ratio for these models. Finally in chapter 4 is presented a direct application of the multistage framework in a musical context i.e. the target-based computed-assisted orchestration problem. Is presented a theoretical analysis of the problem, with NP-hardness and approximation results as well as some experimentations
7
Vallée, Sven. "Algorithmes d’optimisation pour un service de transport partagé à la demande." Thesis, Université de Lorraine, 2019. http://www.theses.fr/2019LORR0063.
Full textAbstract:
L'objectif de cette thèse est de proposer des algorithmes d'optimisation efficaces pour un système de tranport en commun à la demande proposé par Padam Mobility, une start-up Parisienne. Après avoir modélisé le problème comme un DARP dynamique, trois modules d'optimisation sont présentés : un module online destiné à répondre aux requêtes en temps réel, un module de réinsertion pour insérer les requêtes rejetées par le module online et enfin un module offline basé sur une métaheuristique permettant d'optimiser en continue les itinéraires<br>The purpose of this thesis is to propose efficient optimization algorithms for an on-demand common transportation system operated by Padam Mobility, a Parisian company. Formalised as a dynamic DARP, we propose three optimisation modules to tackle the underlying problem : an online module to answer real-time requests, a reinsertion module to re-insert rejected requests and a metaheuristic-based offline module to continuously optimize the rides. The proposed methods are directly implemented in the company system and extensively tested on real instances
8
Jankovic, Anja. "Towards Online Landscape-Aware Algorithm Selection in Numerical Black-Box Optimization." Electronic Thesis or Diss., Sorbonne université, 2021. http://www.theses.fr/2021SORUS302.
Full textAbstract:
Les algorithmes d'optimisation de boîte noire (BBOA) sont conçus pour des scénarios où les formulations exactes de problèmes sont inexistantes, inaccessibles, ou trop complexes pour la résolution analytique. Les BBOA sont le seul moyen de trouver une bonne solution à un tel problème. En raison de leur applicabilité générale, les BBOA présentent des comportements différents lors de l'optimisation de différents types de problèmes. Cela donne un problème de méta-optimisation consistant à choisir l'algorithme le mieux adapté à un problème particulier, appelé problème de sélection d'algorithmes (AS). La vision d'automatiser cette sélection a vite gagné du terrain dans la communauté. Un moyen important de le faire est l'AS tenant compte du paysage, où le choix de l'algorithme est basé sur la prédiction de ses performances via des représentations numériques d'instances de problèmes appelées caractéristiques. Un défi clé auquel l'AS tenant compte du paysage est confrontée est le coût de calcul de l'extraction des caractéristiques, une étape qui précède l'optimisation. Dans cette thèse, nous proposons une approche d'AS tenant compte du paysage basée sur la trajectoire de recherche qui intègre cette étape d'extraction dans celle d'optimisation. Nous montrons que les caractéristiques calculées à l'aide de la trajectoire conduisent à des prédictions robustes et fiables des performances des algorithmes, et à de puissants modèles d'AS construits dessus. Nous présentons aussi plusieurs analyses préparatoires, y compris une perspective de combinaison de 2 stratégies de régression complémentaires qui surpasse des modèles classiques de régression simple et amplifie la qualité du sélecteur<br>Black-box optimization algorithms (BBOAs) are conceived for settings in which exact problem formulations are non-existent, inaccessible, or too complex for an analytical solution. BBOAs are essentially the only means of finding a good solution to such problems. Due to their general applicability, BBOAs can exhibit different behaviors when optimizing different types of problems. This yields a meta-optimization problem of choosing the best suited algorithm for a particular problem, called the algorithm selection (AS) problem. By reason of inherent human bias and limited expert knowledge, the vision of automating the selection process has quickly gained traction in the community. One prominent way of doing so is via so-called landscape-aware AS, where the choice of the algorithm is based on predicting its performance by means of numerical problem instance representations called features. A key challenge that landscape-aware AS faces is the computational overhead of extracting the features, a step typically designed to precede the actual optimization. In this thesis, we propose a novel trajectory-based landscape-aware AS approach which incorporates the feature extraction step within the optimization process. We show that the features computed using the search trajectory samples lead to robust and reliable predictions of algorithm performance, and to powerful algorithm selection models built atop. We also present several preparatory analyses, including a novel perspective of combining two complementary regression strategies that outperforms any of the classical, single regression models, to amplify the quality of the final selector
9
Fersula, Jérémy. "Swarm Robotics : distributed Online Learning in the realm of Active Matter." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS494.
Full textAbstract:
Avec la miniaturisation des composants électroniques et l’augmentation des performances des CPU / GPU modernes, il devient techniquement possible de développer de petits robots capables de travailler en essaims de centaines ou de milliers d’unités. Lorsque l’on considère des systèmes composés d’un grand nombre de robots indépendants en interaction, l’individualité s’efface devant le collectif, et le comportement global de l’ensemble doit émerger de règles locales. Comprendre la dynamique d’un grand nombre d’unités en interaction devient une connaissance clé pour concevoir des essaims robotiques contrôlables et efficaces. Ce sujet est au cœur du domaine de la matière active, dans lequel les systèmes d’intérêt présentent des effets collectifs émergeant d’interactions physiques sans calcul. Cette thèse vise à utiliser des éléments de la matière active pour concevoir et comprendre des collectifs robotiques, interagissant à la fois au niveau physique et au niveau logiciel par le biais d’algorithmes d’apprentissage distribués. Nous commençons par étudier expérimentalement la dynamique d’agrégation d’un essaim de petits robots vibrants effectuant la phototaxie (c’est-à-dire la recherche de lumière). Les expériences sont déclinées dans différentes configurations, soit ad-hoc, soit mettant en œuvre un algorithme d’apprentissage distribué en ligne. Cette série d’expériences sert de référence pour l’algorithme, en montrant ses capacités et ses limites dans une situation réelle. Ces expériences sont approfondies en changeant la forme extérieure des robots, ce qui modifie les interactions physiques en ajoutant une réponse en orientation aux forces extérieures. Cet effet supplémentaire modifie la dynamique globale de l’essaim, montrant que le computation morphologique est en jeu. La nouvelle dynamique est comprise grâce à un modèle physique d’auto-alignement, ce qui permet d’étendre le travail expérimental in sillico et de suggérer de nouveaux effet à grande échelle dans les essaims de robots qui se réorientent. Enfin, nous présentons un modèle d’apprentissage distribué par le biais d’équations différentielles stochastiques. Ce modèle est basé sur l’échange de degrés de liberté internes qui s’associent à la dynamique des particules, qui sont les équivalents dans le contexte de l’apprentissage à un ensemble de paramètres et à un contrôleur. Le modèle donne des résultats similaires en simulation à ceux des expériences réelles et ouvre la voie à une analyse théorique à grande échelle de la dynamique produite par l’apprentissage distribué en ligne<br>CPUs / GPUs, it becomes technically possible to develop small robots able to work in swarms of hundreds or thousands of units. When considering systems comprised of a large number of in- dependent robots in interaction, the individuality vanishes before the collective, and the global behavior of the ensemble has to emerge from local rules. Understanding the dynamics of large number of interacting units becomes a knowledge key to design controllable and efficient robotic swarms. This topic happens to be at the core of the field of active matter, in which the sys- tems of interest display collective effects emerging from physical interactions without computation. This thesis aims at using elements of active matter to design and understand robotic collectives, interacting both at the physical level and the software level through distributed learning algorithms. We start by studying experimentally the aggregation dynamics of a swarm of small vibrating robots performing phototaxis (i.e. search of light). The experiments are declined in different confi- gurations, either ad-hoc or implementing a distributed and online learning algorithm. This series of experiments act as a benchmark for the algorithm, showing its capabilities and limits in a real world situation. These experiments are further expanded by changing the outer shape of the robots, modifying the physical interactions by adding a force re-orientation response. This additional effect changes the global dynamics of the swarm, showing Morphological Computation at play. The new dynamics is understood through a physical model of self-alignment, allowing to extend the experimental work in sillico and hint for unseen global effects in swarms of re-orienting robots. Finally, we introduce a model of distributed learning through stochastic ODEs. This model is based on the exchange of internal degrees of freedom that couples to the dynamics of the particles, equivalents in the context of learning as a set of parameters and a controller. It shows similar results in simulation as the real-world experiments and opens up a way to a large-scale analysis of distributed and online learning dynamics
10
Alinia, Bahram. "Optimal resource allocation strategies for electric vehicles in smart grids." Thesis, Evry, Institut national des télécommunications, 2018. http://www.theses.fr/2018TELE0012/document.
Full textAbstract:
Avec les préoccupations environnementales croissantes liées aux émissions de carbone et la chute rapide des prix des batteries, la part de marché des véhicules électriques (EV) augmente rapidement. Le nombre croissant de EV ainsi que les progrès sans précédent dans la capacité de la batterie et de la technologie entraîne une augmentation drastique de la demande totale d'énergie destinée aux véhicules électriques. Cette forte demande de charge rend complexe le problème de planification de la charge. Même en prenant avantage de la propriété reportable des demandes de charge et d'une planification adéquate, la demande globale pourrait dépasser le taux de charge tolérable des stations, étant donné les contraintes physiques des dispositifs de charge et des transformateurs. Le principal défi est la nécessité de concevoir des solutions en ligne puisque, dans la pratique, l'ordonnanceur ne dispose d'aucune information sur les arrivées futures d'EV. Cette thèse étudie le problème d'ordonnancement des EV en ligne et fournit trois contributions principales. Premièrement, nous démontrons que le problème classique de la programmation en ligne des tâches sensibles aux échéances avec des valeurs partielles est similaire au problème d'ordonnancement EV et étudions l'extension de la programmation des charges EV en prenant en compte de la limite de traitement des travaux. Le problème réside dans la catégorie des problèmes d'ordonnancement en ligne couplés dans le temps sans disponibilité d'informations futures. Le premier algorithme proposé est déterministe, tandis que le second est randomisé et bénéficie d'une complexité de calcul plus faible. Deuxièmement, nous formulons un problème de maximisation du bien-être social pour la planification de la charge des EV avec une contrainte de capacité de charge. Nous avons conçu des algorithmes d'ordonnancement de charge qui non seulement fonctionnent dans un scénario en ligne, mais aussi qui répondent aux deux principaux défis suivants : (i) fournir un engagement à l'arrivée ; (ii) garantir la résistance aux stratégies (de groupe). Des simulations approfondies utilisant des traces réelles démontrent l'efficacité de nos algorithmes d'ordonnancement en ligne par rapport à la solution hors-ligne optimale non-engagée. La troisième contribution concerne la planification en ligne des véhicules électriques dans un réseau de recharge adaptatif (ACN) avec des contraintes de pics locaux et globaux. Nous avons conçu un algorithme d'ordonnancement primal-dual de faible complexité qui atteint un rapport d'approximation borné. Des résultats expérimentaux détaillés basés sur des traces montrent que les performances des algorithmes en ligne proposés sont proches de l'optimum hors ligne et surpassent les solutions existantes<br>With the increased environmental concerns related to carbon emission, and rapid drop in battery prices (e.g., 35% drop in 2017), the market share of Electric Vehicles (EVs) is rapidly growing. The growing number of EVs along with the unprecedented advances in battery capacity and technology results in drastic increase in the total energy demand of EVs. This large charging demand makes the EV charging scheduling problem challenging. The critical challenge is the need for online solution design since in practical scenario the scheduler has no information of future arrivals of EVs in a time-coupled underlying problem. This thesis studies online EV scheduling problem and provides three main contributions. First, we demonstrate that the classical problem of online scheduling of deadlinesensitive jobs with partial values is similar to the EV scheduling problem and study the extension to EV charging scheduling by taking into account the processing rate limit of jobs as an additional constraint to the original problem. The problem lies in the category of time-coupled online scheduling problems without availability of future information. Using competitive ratio, as a well-established performance metric, two online algorithms, both of which are shown to be (2 − 1/U)-competitive are proposed, where U is the maximum scarcity level, a parameter that indicates demand-to-supply ratio. Second, we formulate a social welfare maximization problem for EV charging scheduling with charging capacity constraint. We devise charging scheduling algorithms that not only work in online scenario, but also they address the following two key challenges: (i) to provide on-arrival commitment; respecting the capacity constraint may hinder fulfilling charging requirement of deadline-constrained EVs entirely. Therefore, committing a guaranteed charging amount upon arrival of each EV is highly required; (ii) to guarantee (group)-strategy-proofness as a salient feature to promote EVs to reveal their true type and do not collude with other EVs. Third, we tackle online scheduling of EVs in an adaptive charging network (ACN) with local and global peak constraints. Two alternatives in resource-limited scenarios are to maximize the social welfare by partially charging the EVs (fractional model) or selecting a subset of EVs and fully charge them (integral model). For the fractional model, both offline and online algorithms are devised. We prove that the offline algorithm is optimal. We prove the online algorithm achieves a competitive ratio of 2. The integral model, however, is more challenging since the underlying problem is NP-hard due to 0/1 selection criteria of EVs. Hence, efficient solution design is challenging even in offline setting. We devise a low-complexity primal-dual scheduling algorithm that achieves a bounded approximation ratio. Built upon the offline approximate algorithm, we propose an online algorithm and analyze its competitive ratio in special cases
Books on the topic "Algorithmes online"
1
Evripidis, Bampis, Jansen Klaus, and Kenyon Claire, eds. Efficient approximation and online algorithms: Recent progress on classical combinatorical optimization problems and new applications. Springer, 2006.
Find full text
2
Evripidis, Bampis, Jansen Klaus, and Kenyon Claire, eds. Efficient approximation and online algorithms: Recent progress on classical combinatorical optimization problems and new applications. Springer, 2006.
Find full text
3
Giuseppe, Persiano, and Solis-Oba Roberto, eds. Approximation and online algorithms: Second International Workshop, WAOA 2004, Bergen, Norway, September 14-16, 2004 : revised selected papers. Springer, 2005.
Find full text
4
Fiat, Amos, and Gerhard J. Woeginger, eds. Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029561.
Full text
5
Kaklamanis, Christos, and Asaf Levin, eds. Approximation and Online Algorithms. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-80879-2.
Full text
6
Koenemann, Jochen, and Britta Peis, eds. Approximation and Online Algorithms. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-92702-8.
Full text
7
Chalermsook, Parinya, and Bundit Laekhanukit, eds. Approximation and Online Algorithms. Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-18367-6.
Full text
8
Bampis, Evripidis, and Ola Svensson, eds. Approximation and Online Algorithms. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-18263-6.
Full text
9
Sanità, Laura, and Martin Skutella, eds. Approximation and Online Algorithms. Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-28684-6.
Full text
10
Erlebach, Thomas, and Giuseppe Persiano, eds. Approximation and Online Algorithms. Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-38016-7.
Full textBook chapters on the topic "Algorithmes online"
1
Fiat, Amos, and Gerhard J. Woeginger. "Competitive analysis of algorithms." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029562.
Full text
2
Albers, Susanne, and Jeffery Westbrook. "Self-organizing data structures." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029563.
Full text
3
Irani, Sandy. "Competitive analysis of paging." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029564.
Full text
4
Chrobak, Marek, and Lawrence L. Larmore. "Metrical task systems, the server problem and the work function algorithm." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029565.
Full text
5
Bartal, Yair. "Distributed paging." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029566.
Full text
6
Aspnes, James. "Competitive analysis of distributed algorithms." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029567.
Full text
7
Csirik, János, and Gerhard J. Woeginger. "On-line packing and covering problems." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029568.
Full text
8
Azar, Yossi. "On-line load balancing." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029569.
Full text
9
Sgall, JiŘí. "On-line scheduling." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029570.
Full text
10
Berman, Piotr. "On-line searching and navigation." In Online Algorithms. Springer Berlin Heidelberg, 1998. http://dx.doi.org/10.1007/bfb0029571.
Full textConference papers on the topic "Algorithmes online"
1
Degroote, Hans. "Online Algorithm Selection." In Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/746.
Full textAbstract:
Algorithm selection approaches have achieved impressive performance improvements in many areas of AI. Most of the literature considers the offline algorithm selection problem, where the initial selection model is never updated after training. However, new data from running algorithms on instances becomes available while an algorithm selection method is in use. In this extended abstract, the online algorithm selection problem is considered. In online algorithm selection, additional data can be processed, and the selection model can change over time. This abstract details the online algorithm setting, shows that it is a contextual multi-armed bandit, proposes a solution methodology, and empirically validates it.
2
Soma, Tasuku, and Yuichi Yoshida. "Online Risk-Averse Submodular Maximization." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/411.
Full textAbstract:
We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given T i.i.d. samples from an underlying distribution arriving online, our algorithm produces a sequence of solutions that converges to a (1−1/e)-approximate solution with a convergence rate of O(T −1/4 ) for monotone continuous DR-submodular functions. Compared with previous offline algorithms, which require Ω(T) space, our online algorithm only requires O( √ T) space. We extend our on- line algorithm to portfolio optimization for mono- tone submodular set functions under a matroid constraint. Experiments conducted on real-world datasets demonstrate that our algorithm can rapidly achieve CVaRs that are comparable to those obtained by existing offline algorithms.
3
Sardarmehni, Tohid, and Ali Heydari. "Approximate Solution for Optimal Control of Continuous-Time Switched Systems." In ASME 2016 Dynamic Systems and Control Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/dscc2016-9745.
Full textAbstract:
Two approximate solutions for optimal control of switched systems with autonomous subsystems and continuous-time dynamics are developed. The proposed solutions consist of online training algorithms with recursive least squares training laws. The first solution is the classic policy iteration algorithm which imposes heavy computational burden (full back-up). In order to relax the computational burden in the policy iteration algorithm, the second algorithm is presented. The convergence of the proposed algorithms to the optimal solution in online training is investigated. Simulation results are presented to illustrate the effectiveness of the discussed algorithms.
4
Banerjee, Siddhartha, Vasilis Gkatzelis, Safwan Hossain, Billy Jin, Evi Micha, and Nisarg Shah. "Proportionally Fair Online Allocation of Public Goods with Predictions." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/3.
Full textAbstract:
We design online algorithms for fair allocation of public goods to a set of N agents over a sequence of T rounds and focus on improving their performance using predictions. In the basic model, a public good arrives in each round, and every agent reveals their value for it upon arrival. The algorithm must irrevocably decide the investment in this good without exceeding a total budget of B across all rounds. The algorithm can utilize (potentially noisy) predictions of each agent’s total value for all remaining goods. The algorithm's performance is measured using a proportional fairness objective, which informally demands that every group of agents be rewarded proportional to its size and the cohesiveness of its preferences. We show that no algorithm can achieve better than Θ(T/B) proportional fairness without predictions. With reasonably accurate predictions, the situation improves significantly, and Θ(log(T/B)) proportional fairness is achieved. We also extend our results to a general setting wherein a batch of L public goods arrive in each round and O(log(min(N,L)T/B)) proportional fairness is achieved. Our exact bounds are parameterized as a function of the prediction error, with performance degrading gracefully with increasing errors.
5
Hao, Shuji, Peilin Zhao, Yong Liu, Steven C. H. Hoi, and Chunyan Miao. "Online Multitask Relative Similarity Learning." In Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2017. http://dx.doi.org/10.24963/ijcai.2017/253.
Full textAbstract:
Relative similarity learning~(RSL) aims to learn similarity functions from data with relative constraints. Most previous algorithms developed for RSL are batch-based learning approaches which suffer from poor scalability when dealing with real-world data arriving sequentially. These methods are often designed to learn a single similarity function for a specific task. Therefore, they may be sub-optimal to solve multiple task learning problems. To overcome these limitations, we propose a scalable RSL framework named OMTRSL (Online Multi-Task Relative Similarity Learning). Specifically, we first develop a simple yet effective online learning algorithm for multi-task relative similarity learning. Then, we also propose an active learning algorithm to save the labeling cost. The proposed algorithms not only enjoy theoretical guarantee, but also show high efficacy and efficiency in extensive experiments on real-world datasets.
6
Yang, Peng, Peilin Zhao, and Xin Gao. "Bandit Online Learning on Graphs via Adaptive Optimization." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/415.
Full textAbstract:
Traditional online learning on graphs adapts graph Laplacian into ridge regression, which may not guarantee reasonable accuracy when the data are adversarially generated. To solve this issue, we exploit an adaptive optimization framework for online classification on graphs. The derived model can achieve a min-max regret under an adversarial mechanism of data generation. To take advantage of the informative labels, we propose an adaptive large-margin update rule, which enjoys a lower regret than the algorithms using error-driven update rules. However, this algorithm assumes that the full information label is provided for each node, which is violated in many practical applications where labeling is expensive and the oracle may only tell whether the prediction is correct or not. To address this issue, we propose a bandit online algorithm on graphs. It derives per-instance confidence region of the prediction, from which the model can be learned adaptively to minimize the online regret. Experiments on benchmark graph datasets show that the proposed bandit algorithm outperforms state-of-the-art competitors, even sometimes beats the algorithms using full information label feedback.
7
Lintzmayer, Carla Negri, Flávio Keidi Miyazawa, and Eduardo Candido Xavier. "Online Circle and Sphere Packing∗." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3158.
Full textAbstract:
In the Online Circle Packing in Squares, circles arrive one at a time and we need to pack them into the minimum number of unit square bins. We improve the previous best-known competitive ratio for the bounded space version from 2.439 to 2.3536 and we also give an unbounded space algorithm. Our algorithms also apply to the Online Circle Packing in Isosceles Right Triangles and Online Sphere Packing in Cubes, for which no previous results were known.
8
Banas, Ryan, Andrew McDonald, and Tegwyn Perkins. "NOVEL METHODOLOGY FOR AUTOMATION OF BAD WELL LOG DATA IDENTIFICATION AND REPAIR." In 2021 SPWLA 62nd Annual Logging Symposium Online. Society of Petrophysicists and Well Log Analysts, 2021. http://dx.doi.org/10.30632/spwla-2021-0070.
Full textAbstract:
Subsurface analysis-driven field development requires quality data as input into analysis, modelling, and planning. In the case of many conventional reservoirs, pay intervals are often well consolidated and maintain integrity under drilling and geological stresses providing an ideal logging environment. Consequently, editing well logs is often overlooked or dismissed entirely. Petrophysical analysis however is not always constrained to conventional pay intervals. When developing an unconventional reservoir, pay sections may be comprised of shales. The requirement for edited and quality checked logs becomes crucial to accurately assess storage volumes in place. Edited curves can also serve as inputs to engineering studies, geological and geophysical models, reservoir evaluation, and many machine learning models employed today. As an example, hydraulic fracturing model inputs may span over adjacent shale beds around a target reservoir, which are frequently washed out. These washed out sections may seriously impact logging measurements of interest, such as bulk density and acoustic compressional slowness, which are used to generate elastic properties and compute geomechanical curves. Two classifications of machine learning algorithms for identifying outliers and poor-quality data due to bad hole conditions are discussed: supervised and unsupervised learning. The first allows the expert to train a model from existing and categorized data, whereas unsupervised learning algorithms learn from a collection of unlabeled data. Each classification type has distinct advantages and disadvantages. Identifying outliers and conditioning well logs prior to a petrophysical analysis or machine learning model can be a time-consuming and laborious process, especially when large multi-well datasets are considered. In this study, a new supervised learning algorithm is presented that utilizes multiple-linear regression analysis to repair well log data in an iterative and automated routine. This technique allows outliers to be identified and repaired whilst improving the efficiency of the log data editing process without compromising accuracy. The algorithm uses sophisticated logic and curve predictions derived via multiple linear regression in order to systematically repair various well logs. A clear improvement in efficiency is observed when the algorithm is compared to other currently used methods. These include manual processing by a petrophysicist and unsupervised outlier detection methods. The algorithm can also be leveraged over multiple wells to produce more generalized predictions. Through a platform created to quickly identify and repair invalid log data, the results are controlled through input and supervision by the user. This methodology is not a direct replacement of an expert interpreter, but complementary by allowing the petrophysicist to leverage computing power, improve consistency, reduce error and improve turnaround time.
9
Sviridov, Mikhail, Anton Mosin, Sergey Lebedev, and Ron Thompson. "VENDOR-NEUTRAL STOCHASTIC INVERSION OF LWD DEEP AZIMUTHAL RESISTIVITY DATA AS A STEP TOWARD EFFICIENCY STANDARDIZATION OF GEOSTEERING SERVICES." In 2021 SPWLA 62nd Annual Logging Symposium Online. Society of Petrophysicists and Well Log Analysts, 2021. http://dx.doi.org/10.30632/spwla-2021-0103.
Full textAbstract:
While proactive geosteering, special inversion algorithms are used to process the readings of logging-while-drilling resistivity tools in real-time and provide oil field operators with formation models to make informed steering decisions. Currently, there is no industry standard for inversion deliverables and corresponding quality indicators because major tool vendors develop their own device-specific algorithms and use them internally. This paper presents the first implementation of vendor-neutral inversion approach applicable for any induction resistivity tool and enabling operators to standardize the efficiency of various geosteering services. The necessity of such universal inversion approach was inspired by the activity of LWD Deep Azimuthal Resistivity Services Standardization Workgroup initiated by SPWLA Resistivity Special Interest Group in 2016. Proposed inversion algorithm utilizes a 1D layer-cake formation model and is performed interval-by-interval. The following model parameters can be determined: horizontal and vertical resistivities of each layer, positions of layer boundaries, and formation dip. The inversion can support arbitrary deep azimuthal induction resistivity tool with coaxial, tilted, or orthogonal transmitting and receiving antennas. The inversion is purely data-driven; it works in automatic mode and provides fully unbiased results obtained from tool readings only. The algorithm is based on statistical reversible-jump Markov chain Monte Carlo method that does not require any predefined assumptions about the formation structure and enables searching of models explaining the data even if the number of layers in the model is unknown. To globalize search, the algorithm runs several Markov chains capable of exchanging their states between one another to move from the vicinity of local minimum to more perspective domain of model parameter space. While execution, the inversion keeps all models it is dealing with to estimate the resolution accuracy of formation parameters and generate several quality indicators. Eventually, these indicators are delivered together with recovered resistivity models to help operators with the evaluation of inversion results reliability. To ensure high performance of the inversion, a fast and accurate semi-analytical forward solver is employed to compute required responses of a tool with specific geometry and their derivatives with respect to any parameter of multi-layered model. Moreover, the reliance on the simultaneous evolution of multiple Markov chains makes the algorithm suitable for parallel execution that significantly decreases the computational time. Application of the proposed inversion is shown on a series of synthetic examples and field case studies such as navigating the well along the reservoir roof or near the oil-water-contact in oil sands. Inversion results for all scenarios confirm that the proposed algorithm can successfully evaluate formation model complexity, recover model parameters, and quantify their uncertainty within a reasonable computational time. Presented vendor-neutral stochastic approach to data processing leads to the standardization of the inversion output including the resistivity model and its quality indicators that helps operators to better understand capabilities of tools from different vendors and eventually make more confident geosteering decisions.
10
ElSayed, A., E. Kongar, S. M. Gupta, and T. Sobh. "An Online Genetic Algorithm for Automated Disassembly Sequence Generation." In ASME 2011 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. ASMEDC, 2011. http://dx.doi.org/10.1115/detc2011-48635.
Full textAbstract:
In this study, we propose an intelligent automated disassembly cell for online (real time) selective disassembly. The cell is composed of an industrial robotic manipulator, a camera, range-sensing and component segmentation visual algorithms. The cell prototype allows for robotic sensory-driven disassembly under uncertainty. An online genetic algorithm model for selective disassembly is also proposed for optimal and near/optimal disassembly sequencing.
Reports on the topic "Algorithmes online"
1
Ur, Shmuel. Analysis of Online Algorithms for Organ Allocation. Defense Technical Information Center, 1990. http://dx.doi.org/10.21236/ada249361.
Full text
2
Santesson, S., and P. Hallam-Baker. Online Certificate Status Protocol Algorithm Agility. RFC Editor, 2011. http://dx.doi.org/10.17487/rfc6277.
Full text
3
Labrindis, Alexandros, and Nick Roussopoulos. A Performance Evaluation of Online Warehouse Update Algorithms. Defense Technical Information Center, 1998. http://dx.doi.org/10.21236/ada441038.
Full text
4
Streeter, Matthew, and Daniel Golovin. An Online Algorithm for Maximizing Submodular Functions. Defense Technical Information Center, 2007. http://dx.doi.org/10.21236/ada476748.
Full text
5
Balman, Mehmet, and Tevfik Kosar. An Online Scheduling Algorithm with Advance Reservation for Large-Scale Data Transfers. Office of Scientific and Technical Information (OSTI), 2010. http://dx.doi.org/10.2172/1050437.
Full text
6
Mathew, Jijo K., Christopher M. Day, Howell Li, and Darcy M. Bullock. Curating Automatic Vehicle Location Data to Compare the Performance of Outlier Filtering Methods. Purdue University, 2021. http://dx.doi.org/10.5703/1288284317435.
Full textAbstract:
Agencies use a variety of technologies and data providers to obtain travel time information. The best quality data can be obtained from second-by-second tracking of vehicles, but that data presents many challenges in terms of privacy, storage requirements and analysis. More frequently agencies collect or purchase segment travel time based upon some type of matching of vehicles between two spatially distributed points. Typical methods for that data collection involve license plate re-identification, Bluetooth, Wi-Fi, or some type of rolling DSRC identifier. One of the challenges in each of these sampling techniques is to employ filtering techniques to remove outliers associated with trip chaining, but not remove important features in the data associated with incidents or traffic congestion. This paper describes a curated data set that was developed from high-fidelity GPS trajectory data. The curated data contained 31,621 vehicle observations spanning 42 days; 2550 observations had travel times greater than 3 minutes more than normal. From this baseline data set, outliers were determined using GPS waypoints to determine if the vehicle left the route. Two performance measures were identified for evaluating three outlier-filtering algorithms by the proportion of true samples rejected and proportion of outliers correctly identified. The effectiveness of the three methods over 10-minute sampling windows was also evaluated. The curated data set has been archived in a digital repository and is available online for others to test outlier-filtering algorithms.
7
Arhin, Stephen, Babin Manandhar, Hamdiat Baba Adam, and Adam Gatiba. Predicting Bus Travel Times in Washington, DC Using Artificial Neural Networks (ANNs). Mineta Transportation Institute, 2021. http://dx.doi.org/10.31979/mti.2021.1943.
Full textAbstract:
Washington, DC is ranked second among cities in terms of highest public transit commuters in the United States, with approximately 9% of the working population using the Washington Metropolitan Area Transit Authority (WMATA) Metrobuses to commute. Deducing accurate travel times of these metrobuses is an important task for transit authorities to provide reliable service to its patrons. This study, using Artificial Neural Networks (ANN), developed prediction models for transit buses to assist decision-makers to improve service quality and patronage. For this study, we used six months of Automatic Vehicle Location (AVL) and Automatic Passenger Counting (APC) data for six Washington Metropolitan Area Transit Authority (WMATA) bus routes operating in Washington, DC. We developed regression models and Artificial Neural Network (ANN) models for predicting travel times of buses for different peak periods (AM, Mid-Day and PM). Our analysis included variables such as number of served bus stops, length of route between bus stops, average number of passengers in the bus, average dwell time of buses, and number of intersections between bus stops. We obtained ANN models for travel times by using approximation technique incorporating two separate algorithms: Quasi-Newton and Levenberg-Marquardt. The training strategy for neural network models involved feed forward and errorback processes that minimized the generated errors. We also evaluated the models with a Comparison of the Normalized Squared Errors (NSE). From the results, we observed that the travel times of buses and the dwell times at bus stops generally increased over time of the day. We gathered travel time equations for buses for the AM, Mid-Day and PM Peaks. The lowest NSE for the AM, Mid-Day and PM Peak periods corresponded to training processes using Quasi-Newton algorithm, which had 3, 2 and 5 perceptron layers, respectively. These prediction models could be adapted by transit agencies to provide the patrons with accurate travel time information at bus stops or online.
8
Danylchuk, Hanna B., and Serhiy O. Semerikov. Advances in machine learning for the innovation economy: in the shadow of war. Криворізький державний педагогічний університет, 2023. http://dx.doi.org/10.31812/123456789/7732.
Full textAbstract:
This preface introduces the selected and revised papers presented at the 10th International Conference on Monitoring, Modeling & Management of Emergent Economy (M3E2 2022), held online in Ukraine, on November 17-18, 2022. The conference aimed to bring together researchers, practitioners, and students from various fields to exchange ideas, share experiences, and discuss challenges and opportunities in applying computational intelligence and data science for the innovation economy. The innovation economy is a term that describes the emerging paradigm of economic development that is driven by knowledge, creativity, and innovation. It requires new approaches and methods for solving complex problems, discovering new opportunities, and creating value in various domains of science, business,and society. Computational intelligence and data science are two key disciplines that can provide such approaches and methods by exploiting the power of data, algorithms, models, and systems to enable intelligent decision making, learning, adaptation, optimization, and discovery. The papers in this proceedings cover a wide range of topics related to computational intelligence and data science for the innovation economy. They include theoretical foundations, novel techniques, and innovative applications. The papers were selected and revised based on the feedback from the program committe members and reviewers who ensured their high quality. We would like to thank all the authors who submitted their papers to M3E2 2022. We also appreciate the keynote speakers who shared their insights and visions on the current trends and future directions of computational intelligence and data science for the innovation economy. We acknowledge the support of our sponsors, partners, and organizers who made this conference possible despite the challenging circumstances caused by the ongoing war in Ukraine. Finally, we thank all the participants who attended the conference online and contributed to its success.