Browse
Submit Data
Databases
API
Help

Dataset Information

14 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

The Traveling Salesman Problem (TSP): A Spatial Navigation Task for Rats.

ABSTRACT: The Traveling Salesman Problem (TSP) is a behavioral test used to measure the efficiency of spatial navigation. It is an optimization problem, in which a number of baited targets are placed in an arena, and as the subject travels between the targets, the route is recorded and compared to chance and optimal routes. The TSP is appealing for the study of learning, memory, and executive function in nonhuman animals because the memory requirements can easily be modified with minor adjustments to task parameters. In the standard version of the task, rats are initially pre-trained to forage for bait in the arena. Once the animals consistently retrieve the bait, they are tested with a set of novel target configurations, and their behavior is recorded. The videos are then scored to produce several measures of performance.

SUBMITTER: Blaser RE

PROVIDER: S-EPMC8276063 | biostudies-literature |

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Similar Datasets

Genetic codes optimized as a traveling salesman problem.

Project description:The Standard Genetic Code (SGC) is robust to mutational errors such that frequently occurring mutations minimally alter the physio-chemistry of amino acids. The apparent correlation between the evolutionary distances among codons and the physio-chemical distances among their cognate amino acids suggests an early co-diversification between the codons and amino acids. Here we formulated the co-minimization of evolutionary distances between codons and physio-chemical distances between amino acids as a Traveling Salesman Problem (TSP) and solved it with a Hopfield neural network. In this unsupervised learning algorithm, macromolecules (e.g., tRNAs and aminoacyl-tRNA synthetases) associating codons with amino acids were considered biological analogs of Hopfield neurons associating "tour cities" with "tour positions". The Hopfield network efficiently yielded an abundance of genetic codes that were more error-minimizing than SGC and could thus be used to design artificial genetic codes. We further argue that as a self-optimization algorithm, the Hopfield neural network provides a model of origin of SGC and other adaptive molecular systems through evolutionary learning.

| S-EPMC6816573 | biostudies-other

A Discrete Fruit Fly Optimization Algorithm for the Traveling Salesman Problem.

Project description:The fruit fly optimization algorithm (FOA) is a newly developed bio-inspired algorithm. The continuous variant version of FOA has been proven to be a powerful evolutionary approach to determining the optima of a numerical function on a continuous definition domain. In this study, a discrete FOA (DFOA) is developed and applied to the traveling salesman problem (TSP), a common combinatorial problem. In the DFOA, the TSP tour is represented by an ordering of city indices, and the bio-inspired meta-heuristic search processes are executed with two elaborately designed main procedures: the smelling and tasting processes. In the smelling process, an effective crossover operator is used by the fruit fly group to search for the neighbors of the best-known swarm location. During the tasting process, an edge intersection elimination (EXE) operator is designed to improve the neighbors of the non-optimum food location in order to enhance the exploration performance of the DFOA. In addition, benchmark instances from the TSPLIB are classified in order to test the searching ability of the proposed algorithm. Furthermore, the effectiveness of the proposed DFOA is compared to that of other meta-heuristic algorithms. The results indicate that the proposed DFOA can be effectively used to solve TSPs, especially large-scale problems.

| S-EPMC5094794 | biostudies-literature

Finding long chains in kidney exchange using the traveling salesman problem.

Project description:As of May 2014 there were more than 100,000 patients on the waiting list for a kidney transplant from a deceased donor. Although the preferred treatment is a kidney transplant, every year there are fewer donors than new patients, so the wait for a transplant continues to grow. To address this shortage, kidney paired donation (KPD) programs allow patients with living but biologically incompatible donors to exchange donors through cycles or chains initiated by altruistic (nondirected) donors, thereby increasing the supply of kidneys in the system. In many KPD programs a centralized algorithm determines which exchanges will take place to maximize the total number of transplants performed. This optimization problem has proven challenging both in theory, because it is NP-hard, and in practice, because the algorithms previously used were unable to optimally search over all long chains. We give two new algorithms that use integer programming to optimally solve this problem, one of which is inspired by the techniques used to solve the traveling salesman problem. These algorithms provide the tools needed to find optimal solutions in practice.

| S-EPMC4311855 | biostudies-other

Hybrid pointer networks for traveling salesman problems optimization.

Project description:In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer's encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GPN). For the sack of fairness, we used the same setting as proposed in GPN paper. The experimental results show that our network significantly outperforms the original graph pointer network for small and large-scale problems. For example, it reduced the cost for travelling salesman problems with 50 cities/nodes (TSP50) from 5.959 to 5.706 without utilizing 2opt. Moreover, we solved benchmark instances of variable sizes using HPN and GPN. The cost of the solutions and the testing times are compared using Linear mixed effect models. We found that our model yields statistically significant better solutions in terms of the total trip cost. We make our data, models, and code publicly available https://github.com/AhmedStohy/Hybrid-Pointer-Networks.

| S-EPMC8670669 | biostudies-literature

People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours.

Project description:Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: (1) only a small portion of instances of such problems are actually hard, and (2) successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesman Problem (TSP). Participants were provided feedback on the cost of their solutions and were allowed unlimited solution attempts (trials). We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings. More importantly, we found that participants modified their current better solutions in such a way that edges belonging to the optimal solution ("good" edges) were significantly more likely to stay than other edges ("bad" edges), a hallmark of structural exploitation. We found, however, that more trials harmed the participants' ability to tell good from bad edges, suggesting that after too many trials the participants "ran out of ideas." In sum, we provide the first demonstration of significant performance improvement on the TSP under repetition and feedback and evidence that human problem-solving may exploit the structure of hard problems paralleling behavior of state-of-the-art heuristics.

| S-EPMC2912227 | biostudies-literature

Multiple probabilistic traveling salesman problem in the coordination of drug transportation-In the context of sustainability goals and Industry 4.0.

Project description:Improving the effectiveness of route planning, especially in road transport deliveries is a challenge we need to face in the context of advancing climate change and the sustainable development goals. The main aim of the paper is to demonstrate the above average and utilitarian significance of the multiple probabilistic traveling salesman problem (MPTSP) in the coordination and modeling of sustainable product transportation, which is a novelty at the theoretical, conceptual, methodological and empirical level. We propose a new, hybrid algorithm of solving MPTSP instances (it connects harmony search, k-means and 2-opt), which can be successfully used in economic practice for coordination and modeling of Industry 4.0. The effectiveness of proposed approach is tested using a case study of drugs distribution services and datasets obtained from the transportation enterprise located in Poland. The study focuses on the issue of planning routes, with particular emphasis on the changing demand of customers. It should be stressed that this work may be of interest to researchers but also to management practitioners. The value added of this research lies in the innovative modeling the coordination of sustainable drug transportation as an instance of MPTSP and proposing an effective method to solve it. The main research results confirm that proposed method contributes to overall sustainability of studied supply chain.

| S-EPMC7993843 | biostudies-literature

High-Throughput Task to Study Memory Recall During Spatial Navigation in Rodents.

Project description:Spatial navigation is one of the most frequently used behavioral paradigms to study memory formation in rodents. Commonly used tasks to study memory are labor-intensive, preventing the simultaneous testing of multiple animals with the tendency to yield a low number of trials, curtailing the statistical power. Moreover, they are not tailored to be combined with neurophysiology recordings because they are not based on overt stereotyped behavioral responses that can be precisely timed. Here we present a novel task to study long-term memory formation and recall during spatial navigation. The task consists of learning sessions during which mice need to find the rewarding port that changes from day to day. Hours after learning, there is a recall session during which mice search for the location of the memorized rewarding port. During the recall sessions, the animals repeatedly poke the remembered port over many trials (up to ?20) without receiving a reward (i.e., no positive feedback) as a readout of memory. In this task, mice show memory of port locations learned on up to three previous days. This eight-port maze task requires minimal human intervention, allowing for simultaneous and unsupervised testing of several mice in parallel, yielding a high number of recall trials per session over many days, and compatible with recordings of neural activity.

| S-EPMC7243682 | biostudies-literature

Traveling Companions Add Complexity and Hinder Performance in the Spatial Behavior of Rats.

Project description:We sought to uncover the impact of the social environment on the spatial behavior of rats. Food-deprived rats were trained in a spatial task of collecting food items from 16 equispaced objects. Following training, they were tested, first alone and then with a similarly-trained cage-mate. It was found that the presence of another rat substantially altered the rats' spatial behavior. Lone rats collected the food items faster while traveling a shorter distance, reflecting a higher efficiency of task completion. When accompanied by a partner, however, the rats traveled together, visiting the same set of objects in each trip with one of them leading. Whether alone or with a partner, rats continued to revisit the same objects; however, more such revisits occurred with a partner. We argue that revisiting objects is not necessarily an error, since returning to past places is an important aspect of rats' natural behavior. Revisiting an object following food depletion implies that searching for food was not the main driving force in the rats' spatial behavior. Specifically, despite food deprivation, rats were more attentive to one another than to the food. This could be adaptive, since foraging and feeding in groups is a way of poison avoidance in wild rats. Finally, the addition of a social component added complexity to the environment since the rats organized their spatial behavior in reference to one another in addition to their organization in the physical surrounding. Consequently, when tested with a partner, spatial behavior was less structured, less predictable and more chaotic.

| S-EPMC4701008 | biostudies-literature

Volumetric spatial behaviour in rats reveals the anisotropic organisation of navigation.

Project description:We investigated how access to the vertical dimension influences the natural exploratory and foraging behaviour of rats. Using high-accuracy three-dimensional tracking of position in two- and three-dimensional environments, we sought to determine (i) how rats navigated through the environments with respect to gravity, (ii) where rats chose to form their home bases in volumetric space, and (iii) how they navigated to and from these home bases. To evaluate how horizontal biases may affect these behaviours, we compared a 3D maze where animals preferred to move horizontally to a different 3D configuration where all axes were equally energetically costly to traverse. Additionally, we compared home base formation in two-dimensional arenas with and without walls to the three-dimensional climbing mazes. We report that many behaviours exhibited by rats in horizontal spaces naturally extend to fully volumetric ones, such as home base formation and foraging excursions. We also provide further evidence for the strong differentiation of the horizontal and vertical axes: rats showed a horizontal movement bias, they formed home bases mainly in the bottom layers of both mazes and they generally solved the vertical component of return trajectories before and faster than the horizontal component. We explain the bias towards horizontal movements in terms of energy conservation, while the locations of home bases are explained from an information gathering view as a method for correcting self-localisation.

| S-EPMC7829245 | biostudies-literature