Search

The Dynamic Orienteering Problem (DOP) is studied where nodes change their value over time. An improvement heuristic that is based on Variable Neighborhood Search is proposed for the DOP. The new heuristic is experimentally compared with two heuristics that are based on state-of-the-art algorithms for the static Orienteering Problem. For the experiments several benchmark instances are used as well as instances that are generated from existing road networks. The results show that the new heuristic outperforms the other heuristics with respect to several evaluation criteria and different measures for run time. An additional experiment shows that the new heuristic can be easily adapted to become a standalone algorithm that does not need given initial solutions. The standalone version obtains better results than two state-of-the-art algorithms.

A thorough understanding of discrete optimization problem instances is the foundation for the development of successful solving strategies. For this, the analysis of search spaces is a valuable tool. In particular, networks of solutions—referred to as search landscapes—are used in research. Because of the large number of solutions, topological analysis methods are typically restricted to much smaller problem instances than instances that occur in practical applications. In this paper we present a coarse-grained abstraction of search landscapes—the meta landscape—that is accessible for a complete analysis, can be computed easily and preserves relevant properties of the original search landscapes. Thus, detailed topological analysis and visualization become available for problem instances of realistic sizes. We demonstrate the use of our method for search spaces of more than 1050 solutions.

This paper considers a special case of two-machine flow shop scheduling problems with buffers, namely, the case where all processing times on one of the two machines are equal. This case is interesting because it occurs in various applications, e.g., when one machine is a packing machine. For the buffers we consider two types of buffers that have been studied in the literature for flow shops. It is shown that all considered buffered flow shop problems remain NP-hard for the makespan criterion and permutation schedules even with the restriction to equal processing times on one machine. Two specific heuristics for solving the problems are proposed: (i) a modification of the commonly used NEH heuristic (mNEH) and (ii) an Iterated Local Search heuristic (2BF-ILS) that uses the mNEH heuristic for computing its initial solution. It is shown experimentally that the proposed 2BF-ILS heuristic obtains better results than two state-of-the-art algorithms for buffered flow shop problems from the literature and an Ant Colony Optimization algorithm. In addition, it is shown experimentally that 2BF-ILS can obtain the same solution quality as the standard NEH heuristic with a smaller number of function evaluations.

Discrete combinatorial optimization problems such as the Traveling Salesman Problem have various applications in science and in everyday life. The complexity of the problem and the effectiveness of search algorithms depend not only on the problem itself but also on the search operator in use. Therefore, investigating search operators and the search landscapes they give rise to is an important field of research. However, a full topological analysis of the landscapes is impossible due to their exponentially growing size. We propose a visualization system that gives a visual intuition about topological properties of the search landscape. We obtain representative samples of the search landscape and its optima by random sampling and by computing the related optima using local search. The distribution and the correlation of this data within the search landscape is visualized with a combination of one and two dimensional visualizations. Using the TSP as an example we illustrate how the visualization supports the understanding and comparison of search landscapes and their complexity.

A population based ant optimization algorithm (PACO) for reconstructing electrocardiogram (ECG) signals is proposed in this paper. In particular, the PACO algorithm is used to find a subset of nonzero positions of a sparse wavelet domain ECG signal vector which is used for the reconstruction of a signal. The proposed PACO algorithm uses a time window for fixing certain decisions of the ants during the run of the algorithm. The optimization behaviour of the PACO is compared with two random search heuristics and several algorithms from the literature for ECG signal reconstruction. Experimental results are presented for ECG signals from the MIT-BIT Arrhythmia database. The results show that the proposed PACO reconstructs ECG signals very successfully.

A method is proposed to generate multi-objective optimization problem instances from a corresponding single-objective instance. The user of the method can specify the correlations between the generated the objectives. Different from existing instance generation methods the new method allows to keep certain properties of the original single-objective instance. In particular, we consider optimization problems where the objective is defined by a matrix, e.g., a distance matrix for the Traveling Salesperson problem (TSP) or a flow matrix for the Quadratic Assignment problem. It is shown that the method creates new distance matrices with specific correlations between each other and also have the same average distance and variance of distances as the distance matrix of the original instance. This property is important, e.g., when the influence of correlations between the objectives on the behavior of metaheuristics for the multi-objective TSP are investigated. Some properties of the new method are shown theoretically. In an empirical analysis the new method is compared with instance generation methods from the literature.

The formation of groups in heterogeneous swarms is important whenever there is benefit from cooperation between the members of a group. Here we investigate decentralized group formation strategies for a set of moving agents that have to collect resources. The agents are reconfigurable and can adapt themselves to the needs of their group. It is assumed that the agents are simple and communication between groups is limited to sensing each other. Members of one group are able to share information about their capabilities and movement decision. Also the decision strategies for integrating a new agent into a group and for the moving direction of a group are simple. Several versions of the system are compared experimentally for a dynamic situation where the number of available resource types changes. It is shown that the costs for reconfiguration influences the optimal strategy for the integration of new agents into a group. The system can adapt the average group size to the number of available resource types.

In this paper we propose some changes and extensions of the visualization approach that is used in the visualization tool dPSO-Vis. It is shown also how corresponding visualizations can help for the analysis of fitness landscapes of combinatorial optimization problems and for understanding and comparing the optimization behaviour of heuristics. As an example we use a small instance of the Travelling Salesperson Problem (TSP) and the three heuristics Greedy, Random greedy, and Simulated Annealing.