A Unifying Survey of Reinforced, Sensitive and Stigmergic Agent-Based Approaches for E-GTSP
---
paper_title: A Random-Key Genetic Algorithm for the Generalized Traveling Salesman Problem

paper_content:

The generalized traveling salesman problem is a variation of the well-known traveling salesman problem in which the set of nodes is divided into clusters; the objective is to find a minimum-cost tour passing through one node from each cluster. We present an effective heuristic for this problem. The method combines a genetic algorithm (GA) with a local tour improvement heuristic. Solutions are encoded using random keys, which circumvent the feasibility problems encountered when using traditional GA encodings. On a set of 41 standard test problems with symmetric distances and up to 442 nodes, the heuristic found solutions that were optimal in most cases and were within 1% of optimality in all but the largest problems, with computation times generally within 10 seconds. The heuristic is competitive with other heuristics published to date in both solution quality and computation time.
---
paper_title: Sensitive Ants in Solving the Generalized Vehicle Routing Problem

paper_content:

The idea of sensitivity in ant colony systems has been exploited in hybrid ant-based models with promising results for many combinatorial optimization problems. Heterogeneity is induced in the ant population by endowing individual ants with a certain level of sensitivity to the pheromone trail. The variable pheromone sensitivity within the same population of ants can potentially intensify the search while in the same time inducing diversity for the exploration of the environment. The performance of sensitive ant models is investigated for solving the generalized vehicle routing problem. Numerical results and comparisons are discussed and analysed with a focus on emphasizing any particular aspects and potential benefits related to hybrid ant-based models.
---
paper_title: A Memetic Algorithm for the Generalized Traveling Salesman Problem

paper_content:

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.
---
paper_title: Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem

paper_content:

The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems. In this paper, we discuss possible adaptations of TSP heuristics for the generalized traveling salesman problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search.
---
paper_title: An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem

paper_content:

The Generalized Traveling Salesman Problem (GTSP) is an extension of the well-known Traveling Salesman Problem (TSP), where the node set is partitioned into clusters, and the objective is to find the shortest cycle visiting each cluster exactly once. In this paper, we present a new hybrid Ant Colony System (ACS) algorithm for the symmetric GTSP. The proposed algorithm is a modification of a simple ACS for the TSP improved by an efficient GTSP-specific local search procedure. Our extensive computational experiments show that the use of the local search procedure dramatically improves the performance of the ACS algorithm, making it one of the most successful GTSP metaheuristics to date.
---
paper_title: Solving the Generalized Vehicle Routing Problem with an ACS‐based Algorithm

paper_content:

Ant colony system is a metaheuristic algorithm inspired by the behavior of real ants and was proposed by Dorigo et al. as a method for solving hard combinatorial optimization problems. In this paper we show its successful application to solving a network design problem: Generalized Vehicle Routing Problem. The Generalized Vehicle Routing Problem (GVRP) is the problem of designing optimal delivery or collection routes, subject to capacity restrictions, from a given depot to a number of predefined, mutually exclusive and exhaustive clusters. Computational results for several benchmark problems are reported.
---
paper_title: The Generalized Traveling Salesman and Orienteering Problems

paper_content:

Routing and Scheduling problems often require the determination of optimal sequences subject to a given set of constraints. The best known problem of this type is the classical Traveling Salesman Problem (TSP), calling for a minimum cost Hamiltonian cycle on a given graph.
---
paper_title: An efficient composite heuristic for the symmetric generalized traveling salesman problem

paper_content:

The main purpose of this paper is to introduce a new composite heuristic for solving the generalized traveling salesman problem. The proposed heuristic is composed of three phases: the construction of an initial partial solution, the insertion of a node from each non-visited node-subset, and a solution improvement phase. We show that the heuristic performs very well on 36 TSPLIB problems which have been solved to optimality by other researchers. We also propose some simple heuristics that can be used as basic blocks to construct more efficient composite heuristics.
---
paper_title: Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies

paper_content:

This book represents the results of cross-fertilization between OR/MS and CS/AI. It is this interface of OR/CS that makes possible advances that could not have been achieved in isolation. Taken collectively, these articles are indicative of the state-of-the-art in the interface between OR/MS and CS/AI and of the high caliber of research being conducted by members of the INFORMS Computing Society.
---
paper_title: Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem

paper_content:

The Generalized Traveling Salesman Problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. While the GTSP is a very important combinatorial optimization problem and is well studied in many aspects, the local search algorithms used in the literature are mostly basic adaptations of simple TSP heuristics. Hence, a thorough and deep research of the neighborhoods and local search algorithms specific to the GTSP is required. We formalize the procedure of adaptation of a TSP neighborhood for the GTSP and classify all other existing and some new GTSP neighborhoods. For every neighborhood, we provide efficient exploration algorithms that are often significantly faster than the ones known from the literature. Finally, we compare different local search implementations empirically.
---
paper_title: A Multistart Heuristic for the Equality Generalized Traveling Salesman Problem

paper_content:

We study the equality generalized traveling salesman problem (E-GTSP), which is a variant of the well-known traveling salesman problem. We are given an undirected graph G = (V, E), with set of vertices V and set of edges E, each with an associated cost. The set of vertices is partitioned into clusters. E-GTSP is to find an elementary cycle visiting exactly one vertex for each cluster and minimizing the sum of the costs of the traveled edges. We propose a multistart heuristic, which iteratively starts with a randomly chosen set of vertices and applies a decomposition approach combined with improvement procedures. The decomposition approach considers a first phase to determine the visiting order of the clusters and a second phase to find the corresponding minimum cost cycle. We show the effectiveness of the proposed approach on benchmark instances from the literature. On small instances, the heuristic always identifies the optimal solution rapidly and outperforms all known heuristics; on larger instances, the heuristic always improves, in comparable computing times, the best known solution values obtained by the genetic algorithm recently proposed by Silberholz and Golden.
---
paper_title: Generalized Travelling Salesman Problem Through n Sets Of Nodes: An Integer Programming Approach

paper_content:

AbstractThis paper deals with a generalized version of the Travelling Salesman Problem, which consists of finding the shortest Hamiltonian cycle through n sets of nodes. The problem is formulated as an integer linear program including degree constraints, subtour elimination constraints, and integrality constraints. A branch and bound algorithm is used for the solution of the problem; the main feature of the algorithm lies in the relaxation of the subtour elimination constraints. Computational results for Euclidean and non-Euclidean problems are reported.
---
paper_title: MAX-MIN Ant System and local search for the traveling salesman problem

paper_content:

Ant System is a general purpose algorithm inspired by the study of the behavior of ant colonies. It is based on a cooperative search paradigm that is applicable to the solution of combinatorial optimization problems. We introduce MAX-MIN Ant System, an improved version of basic Ant System, and report our results for its application to symmetric and asymmetric instances of the well known traveling salesman problem. We show how MAX-MIN Ant System can be significantly improved, extending it with local search heuristics. Our results clearly show that MAX-MIN Ant System has the property of effectively guiding the local search heuristics towards promising regions of the search space by generating good initial tours.
---
paper_title: The complexity of agent design problems: Determinism and history dependence

paper_content:

The agent design problem is as follows: given a specification of an environment, together with a specification of a task, is it possible to construct an agent that can be guaranteed to successfully accomplish the task in the environment? In this article, we study the computational complexity of the agent design problem for tasks that are of the form "achieve this state of affairs" or "maintain this state of affairs." We consider three general formulations of these problems (in both non-deterministic and deterministic environments) that differ in the nature of what is viewed as an "acceptable" solution: in the least restrictive formulation, no limit is placed on the number of actions an agent is allowed to perform in attempting to meet the requirements of its specified task. We show that the resulting decision problems are intractable, in the sense that these are non-recursive (but recursively enumerable) for achievement tasks, and non-recursively enumerable for maintenance tasks. In the second formulation, the decision problem addresses the existence of agents that have satisfied their specified task within some given number of actions. Even in this more restrictive setting the resulting decision problems are either pspace-complete or np-complete. Our final formulation requires the environment to be history independent and bounded. In these cases polynomial time algorithms exist: for deterministic environments the decision problems are nl-complete; in non-deterministic environments, p-complete.
---
paper_title: A Sensitive Metaheuristic for Solving a Large Optimization Problem

paper_content:

A metaheuristic for solving complex problems is proposed. The introduced Sensitive Robot Metaheuristic (SRM) is based on the Ant Colony System optimization technique. The new model relies on the reaction of virtual sensitive robots to different stigmergic variables. Each robot is endowed with a particular stigmergic sensitivity level ensuring a good balance between search diversification and intensification. Comparative tests are performed on large-scale NP-hard robotic travel problems. These tests illustrate the effectiveness and robustness of the proposed metaheuristic.
---
paper_title: New Integer Programming Formulations of the Generalized Travelling Salesman Problem

paper_content:

The Generalized Travelling Salesman Problem, denoted by GTSP, is a variant of the classical travelling salesman problem (TSP), in which the nodes of an undirected graph are partitioned into node sets (clusters) and the salesman has to visit exactly one node from every cluster. In this paper we described six distinct formulations of the GTSP as an integer programming. Apart from the standard formulations all the new formulations that we describe are 'compact' in the sense that the number of constraints and variables is a polynomial function of the number of nodes in the problem. In order to provide compact formulations for the GTSP we used two approaches using auxiliary flow variables beyond the natural binary edge and node variables and the second one by distinguishing between global and local variables. Comparisons of the polytopes corresponding to their linear relaxations are established.
---
paper_title: Efficient Local Search Algorithms for Known and New Neighborhoods for the Generalized Traveling Salesman Problem

paper_content:

The Generalized Traveling Salesman Problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. While the GTSP is a very important combinatorial optimization problem and is well studied in many aspects, the local search algorithms used in the literature are mostly basic adaptations of simple TSP heuristics. Hence, a thorough and deep research of the neighborhoods and local search algorithms specific to the GTSP is required. We formalize the procedure of adaptation of a TSP neighborhood for the GTSP and classify all other existing and some new GTSP neighborhoods. For every neighborhood, we provide efficient exploration algorithms that are often significantly faster than the ones known from the literature. Finally, we compare different local search implementations empirically.
---
paper_title: Improving ant systems using a local updating rule

paper_content:

An algorithm based on ant colony system for solving traveling salesman problem is proposed. The new algorithm, introduces in ant colony system an inner loop aiming to update the pheromone trails. The update increases the pheromone in the trail followed by the ants and therefore generates improved tours.
---
paper_title: MAX-MIN Ant System and local search for the traveling salesman problem

paper_content:

Ant System is a general purpose algorithm inspired by the study of the behavior of ant colonies. It is based on a cooperative search paradigm that is applicable to the solution of combinatorial optimization problems. We introduce MAX-MIN Ant System, an improved version of basic Ant System, and report our results for its application to symmetric and asymmetric instances of the well known traveling salesman problem. We show how MAX-MIN Ant System can be significantly improved, extending it with local search heuristics. Our results clearly show that MAX-MIN Ant System has the property of effectively guiding the local search heuristics towards promising regions of the search space by generating good initial tours.
---
paper_title: Heterogeneous sensitive ant model for combinatorial optimization

paper_content:

A new metaheuristic called Sensitive Ant Model (SAM) for solving combinatorial optimization problems is proposed. SAM improves and extends the Ant Colony System approach by enhancing each agent of the model with properties that induce heterogeneity. SAM agents are endowed with different pheromone sensitivity levels. Highly-sensitive agents are essentially influenced in the decision making process by stigmergic information and thus likely to select strong pheromone-marked moves. Search intensification can be therefore sustained. Agents with low sensitivity are biased towards random search inducing diversity for exploration of the environment. A heterogeneous agent model has the potential to cope with complex and/or dynamic search spaces. Sensitive agents (or ants) allow many types of reactions to a changing environment facilitating an efficient balance between exploration and exploitation.
---
paper_title: A Sensitive Metaheuristic for Solving a Large Optimization Problem

paper_content:

A metaheuristic for solving complex problems is proposed. The introduced Sensitive Robot Metaheuristic (SRM) is based on the Ant Colony System optimization technique. The new model relies on the reaction of virtual sensitive robots to different stigmergic variables. Each robot is endowed with a particular stigmergic sensitivity level ensuring a good balance between search diversification and intensification. Comparative tests are performed on large-scale NP-hard robotic travel problems. These tests illustrate the effectiveness and robustness of the proposed metaheuristic.
---
paper_title: A Brief History of Stigmergy

paper_content:

Stigmergy is a class of mechanisms that mediate animal-animal interactions. Its introduction in 1959 by Pierre-Paul Grasse made it possible to explain what had been until then considered paradoxical observations: In an insect society individuals work as if they were alone while their collective activities appear to be coordinated. In this article we describe the history of stigmergy in the context of social insects and discuss the general properties of two distinct stigmergic mechanisms: quantitative stigmergy and qualitative stigmergy.
---
paper_title: Self-Organization in Biological Systems

paper_content:

From the Publisher: ::: "Broad in scope, thorough yet accessible, this book is a self-contained introduction to self-organization and complexity in biology - a field of study at the forefront of life sciences research."--BOOK JACKET.
---
paper_title: Intelligent Complex Evolutionary Agent‐Based Systems

paper_content:

In this paper, we investigate the possibility to develop intelligent agent‐based complex systems that use evolutionary learning techniques in order to adapt for the efficient solving of the problems by reorganizing their structure. For this investigation is proposed a complex multiagent system called EAMS (Evolutionary Adaptive Multiagent System), which using an evolutionary learning technique can learn different patterns of reorganization. The realized study proves that evolutionary techniques successfully can be used to create complex multiagent systems capable to intelligently reorganize their structure during their life cycle. The practical establishment of the intelligence of a computational system in generally, an agent‐based system in particularly consists in how efficiently and flexibly the system can solve difficult problems.
---
paper_title: The complexity of agent design problems: Determinism and history dependence

paper_content:

The agent design problem is as follows: given a specification of an environment, together with a specification of a task, is it possible to construct an agent that can be guaranteed to successfully accomplish the task in the environment? In this article, we study the computational complexity of the agent design problem for tasks that are of the form "achieve this state of affairs" or "maintain this state of affairs." We consider three general formulations of these problems (in both non-deterministic and deterministic environments) that differ in the nature of what is viewed as an "acceptable" solution: in the least restrictive formulation, no limit is placed on the number of actions an agent is allowed to perform in attempting to meet the requirements of its specified task. We show that the resulting decision problems are intractable, in the sense that these are non-recursive (but recursively enumerable) for achievement tasks, and non-recursively enumerable for maintenance tasks. In the second formulation, the decision problem addresses the existence of agents that have satisfied their specified task within some given number of actions. Even in this more restrictive setting the resulting decision problems are either pspace-complete or np-complete. Our final formulation requires the environment to be history independent and bounded. In these cases polynomial time algorithms exist: for deterministic environments the decision problems are nl-complete; in non-deterministic environments, p-complete.
---
paper_title: A Memetic Algorithm for the Generalized Traveling Salesman Problem

paper_content:

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.
---
paper_title: An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem

paper_content:

The Generalized Traveling Salesman Problem (GTSP) is an extension of the well-known Traveling Salesman Problem (TSP), where the node set is partitioned into clusters, and the objective is to find the shortest cycle visiting each cluster exactly once. In this paper, we present a new hybrid Ant Colony System (ACS) algorithm for the symmetric GTSP. The proposed algorithm is a modification of a simple ACS for the TSP improved by an efficient GTSP-specific local search procedure. Our extensive computational experiments show that the use of the local search procedure dramatically improves the performance of the ACS algorithm, making it one of the most successful GTSP metaheuristics to date.
---
paper_title: Data Mining with an Ant Colony Optimization Algorithm

paper_content:

The paper proposes an algorithm for data mining called Ant-Miner (ant-colony-based data miner). The goal of Ant-Miner is to extract classification rules from data. The algorithm is inspired by both research on the behavior of real ant colonies and some data mining concepts as well as principles. We compare the performance of Ant-Miner with CN2, a well-known data mining algorithm for classification, in six public domain data sets. The results provide evidence that: 1) Ant-Miner is competitive with CN2 with respect to predictive accuracy, and 2) the rule lists discovered by Ant-Miner are considerably simpler (smaller) than those discovered by CN2.
---
paper_title: Lin-Kernighan Heuristic Adaptations for the Generalized Traveling Salesman Problem

paper_content:

The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems. In this paper, we discuss possible adaptations of TSP heuristics for the generalized traveling salesman problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search.
---
paper_title: An Efficient Hybrid Ant Colony System for the Generalized Traveling Salesman Problem

paper_content:

The Generalized Traveling Salesman Problem (GTSP) is an extension of the well-known Traveling Salesman Problem (TSP), where the node set is partitioned into clusters, and the objective is to find the shortest cycle visiting each cluster exactly once. In this paper, we present a new hybrid Ant Colony System (ACS) algorithm for the symmetric GTSP. The proposed algorithm is a modification of a simple ACS for the TSP improved by an efficient GTSP-specific local search procedure. Our extensive computational experiments show that the use of the local search procedure dramatically improves the performance of the ACS algorithm, making it one of the most successful GTSP metaheuristics to date.
---
paper_title: A decision-theoretic framework for comparing heuristics

paper_content:

Abstract In this paper we describe a decision-theoretic framework for comparing a number of heuristics in terms of accuracy for a given combinatorial optimization problem. The procedure takes both expected accuracy and downside risk into account and is quite easy to implement.
---
paper_title: Support vector machine learning with an evolutionary engine

paper_content:

The paper presents a novel evolutionary technique constructed as an alternative of the standard support vector machines architecture. The approach adopts the learning strategy of the latter but aims to simplify and generalize its training, by offering a transparent substitute to the initial black-box. Contrary to the canonical technique, the evolutionary approach can at all times explicitly acquire the coefficients of the decision function, without any further constraints. Moreover, in order to converge, the evolutionary method does not require the positive (semi-)definition properties for kernels within nonlinear learning. Several potential structures, enhancements and additions are proposed, tested and confirmed using available benchmarking test problems. Computational results show the validity of the new approach in terms of runtime, prediction accuracy and flexibility.
---

Title: A Unifying Survey of Reinforced, Sensitive and Stigmergic Agent-Based Approaches for E-GTSP

Section 1: Introduction
Description 1: Introduce the significance and complexity of the Generalized Traveling Salesman Problem (GTSP) and its variant E-GTSP.

Section 2: The GTSP description
Description 2: Provide a comprehensive description of the Generalized Traveling Salesman Problem including definitions and its applications.

Section 3: A mathematical model of GTSP
Description 3: Present the mathematical model for GTSP and discuss its complex nature and time complexity.

Section 4: Agent-based approaches for solving GTSP
Description 4: Describe the various agent-based techniques proposed for solving GTSP, including Ant Colony System, Reinforcing Ant Colony System, Sensitive Ant Colony System, Sensitive Robot Metaheuristic, and Sensitive Stigmergic Agent System.

Section 5: Ant Colony System for GTSP
Description 5: Explain the Ant Colony System specifically adapted for GTSP, including algorithms and key operations.

Section 6: Reinforcing Ant Colony System for GTSP
Description 6: Detail the Reinforcing Ant Colony System and describe its modifications from the standard Ant Colony System.

Section 7: Sensitive Ant Colony System for GTSP
Description 7: Illustrate the functioning of the Sensitive Ant Colony System and how it uses pheromone sensitivity levels for improved problem-solving.

Section 8: SRM for solving GTSP
Description 8: Explain the Sensitive Robot Metaheuristic approach and its use of virtual autonomous robots with stigmergic sensitivity levels.

Section 9: Sensitive Stigmergic Agent System for GTSP
Description 9: Describe the Sensitive Stigmergic Agent System integrating concepts from Sensitive Ant Colony System and Stigmergic Agent System.

Section 10: Evaluations of Agent-Based Algorithms for E-GTSP
Description 10: Present the numerical experiments comparing the performance of different agent-based approaches for solving E-GTSP.

Section 11: Computational Analysis
Description 11: Provide a detailed computational analysis of the results obtained from various agent-based algorithms and compare their efficiency.

Section 12: Statistical analysis: advantages and disadvantages
Description 12: Summarize the statistical analysis highlighting the advantages and disadvantages of the techniques used.

Section 13: Conclusion
Description 13: Conclude with a summary of the findings, advantages of the methods described, and potential directions for future research.

Section 14: Acknowledgement
Description 14: Acknowledge contributions and assistance received in the course of the research.