Dataset Information

Faster sorting algorithms discovered using deep reinforcement learning.

ABSTRACT: Fundamental algorithms such as sorting or hashing are used trillions of times on any given day¹. As demand for computation grows, it has become critical for these algorithms to be as performant as possible. Whereas remarkable progress has been achieved in the past², making further improvements on the efficiency of these routines has proved challenging for both human scientists and computational approaches. Here we show how artificial intelligence can go beyond the current state of the art by discovering hitherto unknown routines. To realize this, we formulated the task of finding a better sorting routine as a single-player game. We then trained a new deep reinforcement learning agent, AlphaDev, to play this game. AlphaDev discovered small sorting algorithms from scratch that outperformed previously known human benchmarks. These algorithms have been integrated into the LLVM standard C++ sort library³. This change to this part of the sort library represents the replacement of a component with an algorithm that has been automatically discovered using reinforcement learning. We also present results in extra domains, showcasing the generality of the approach.

SUBMITTER: Mankowitz DJ

PROVIDER: S-EPMC10247365 | biostudies-literature | 2023 Jun

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Faster sorting algorithms discovered using deep reinforcement learning.

Mankowitz Daniel J DJ Michi Andrea A Zhernov Anton A Gelmi Marco M Selvi Marco M Paduraru Cosmin C Leurent Edouard E Iqbal Shariq S Lespiau Jean-Baptiste JB Ahern Alex A Köppe Thomas T Millikin Kevin K Gaffney Stephen S Elster Sophie S Broshear Jackson J Gamble Chris C Milan Kieran K Tung Robert R Hwang Minjae M Cemgil Taylan T Barekatain Mohammadamin M Li Yujia Y Mandhane Amol A Hubert Thomas T Schrittwieser Julian J Hassabis Demis D Kohli Pushmeet P Riedmiller Martin M Vinyals Oriol O Silver David D

Nature 20230607 7964

Fundamental algorithms such as sorting or hashing are used trillions of times on any given day<sup>1</sup>. As demand for computation grows, it has become critical for these algorithms to be as performant as possible. Whereas remarkable progress has been achieved in the past<sup>2</sup>, making further improvements on the efficiency of these routines has proved challenging for both human scientists and computational approaches. Here we show how artificial intelligence can go beyond the current s ...[more]

PMID: 37286649

Similar Datasets

Project description:Modern technologies, particularly artificial intelligence, play a crucial role in improving medical waste management by developing intelligent systems that optimize the shortest routes for waste transport, from its generation to final disposal. Algorithms such as Q-learning and Deep Q Network enhance the efficiency of transport and disposal while reducing environmental pollution risks. In this study, artificial intelligence algorithms were trained using Homogeneous agent systems with a capacity of 3 tons to optimize routes between hospitals within the Closed Capacitated Vehicle Routing Problem framework. Integrating AI with pathfinding techniques, especially the hybrid A*-Deep Q Network approach, led to advanced results despite initial challenges. K-means clustering was used to divide hospitals into zones, allowing agents to navigate the shortest paths using the Deep Q Network. Analysis revealed that the agents' capacity was not fully utilized. This led to the application of Fractional Knapsack dynamic programming with Deep Q Network to maximize capacity utilization while achieving optimal routes. Since the criteria used to compare the algorithms' effectiveness are the number of vehicles and the utilization of the total vehicle capacity, it was found that the Fractional Knapsack with DQN stands out by requiring the fewest number of vehicles (4), achieving 0% loss in this metric as it matches the optimal value. Compared to other algorithms that require 5 or 7 vehicles, it reduces the fleet size by 20 and 42.86%, respectively. Additionally, it maximizes vehicle capacity utilization at 100%, unlike other methods, which utilize only 33 to 66% of vehicle capacity. However, this improvement comes at the cost of a 9% increase in distance, reflecting the longer routes needed to serve more hospitals per trip. Despite this trade-off, the algorithm's ability to minimize fleet size while fully utilizing vehicle capacity makes it the optimal choice in scenarios where these factors are critical. This approach not only improved performance but also enhanced environmental sustainability, making it the most effective and challenging solution among all the algorithms used in the study.

Project description:Evaluating and tracking wound size is a fundamental metric for the wound assessment process. Good location and size estimates can enable proper diagnosis and effective treatment. Traditionally, laboratory wound healing studies include a collection of images at uniform time intervals exhibiting the wounded area and the healing process in the test animal, often a mouse. These images are then manually observed to determine key metrics -such as wound size progress- relevant to the study. However, this task is a time-consuming and laborious process. In addition, defining the wound edge could be subjective and can vary from one individual to another even among experts. Furthermore, as our understanding of the healing process grows, so does our need to efficiently and accurately track these key factors for high throughput (e.g., over large-scale and long-term experiments). Thus, in this study, we develop a deep learning-based image analysis pipeline that aims to intake non-uniform wound images and extract relevant information such as the location of interest, wound only image crops, and wound periphery size over-time metrics. In particular, our work focuses on images of wounded laboratory mice that are used widely for translationally relevant wound studies and leverages a commonly used ring-shaped splint present in most images to predict wound size. We apply the method to a dataset that was never meant to be quantified and, thus, presents many visual challenges. Additionally, the data set was not meant for training deep learning models and so is relatively small in size with only 256 images. We compare results to that of expert measurements and demonstrate preservation of information relevant to predicting wound closure despite variability from machine-to-expert and even expert-to-expert. The proposed system resulted in high fidelity results on unseen data with minimal human intervention. Furthermore, the pipeline estimates acceptable wound sizes when less than 50% of the images are missing reference objects.

Dataset Information

Faster sorting algorithms discovered using deep reinforcement learning.

Publications

Faster sorting algorithms discovered using deep reinforcement learning.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets