Search

The 2-opt, 3-opt or k–opt heuristics are classical local search algorithms for traveling salesman problems (TSP) in combinatorial optimization area, while sequential k–opt complete neighborhood examination takes polynomial time complexity which is timeconsuming to approach large scale TSP instances. This paper introduces a reasonable methodology called "multiple k–opt evaluation, multiple k–opt moves" that allows to simultaneously execute, without interference, massive k −opt moves that are globally found on the same TSP tour, as well as keep high performance GPU (Graphics Processing Unit) parallel 2-/3-opt evaluation with characteristic of "data parallelism, decentralized control and O(1) local memory for each GPU thread". The methodology is reasonable since intervention of a sequential O(N) time complexity tour reversal operation is unavoidable for each k −opt move when using array of ordered coordinates as TSP tour data structure for high performance GPU k −opt local search that considers coalesced memory access and usage of limited on-chip shared memory. Innovation work includes two parts, a sequential non-interacted k-opt moves' set partition algorithm that takes linear time complexity; a new TSP tour representation, array of ordered coordinates-index, that unveils how to combine the advantages of using doubly linked list and array of ordered coordinates data structures for iterative parallel k −opt local search based on GPU CUDA. We test this methodology on 22 national TSP instances with up to 71009 cities and with brute initial tour solution. Average maximum 997 non-interacted 2-opt moves are found and executed on the same tour of ch71009.tsp instance after one iteration of complete N ∗ (N − 1) 2 2-opt checks working in parallel on GPU. And the proposed iterative GPU parallel 2-opt methodology executes average 306631 2-opt moves while only iterates 786 tour reversal operations, in comparison with methods that have to execute tour reversal operation after each 2-opt move. Experimental comparisons show that our proposed methodology gets huge acceleration over both classical sequential and a current state-of-the-art GPU parallel 2-opt implementation. [ABSTRACT FROM AUTHOR]

We propose parallel implementation on GPU (graphics processing unit) system for some generic algorithms applied to superpixel image segmentation problem. The aim is to provide standard algorithms based on generic decentralized data structures that could be easily improved and customized on many optimization problems on parallel platforms. Note that superpixel segmentation are clustering algorithms applied to image processing. Two types of algorithms are presented and implemented on GPU based on common parallel data structures. Firstly, we present a parallel implementation of the well-known k -means algorithm with application to 3D data. It is based on a cellular grid subdivision of space that allows closest point findings in constant optimal time for bounded distributions. Secondly, we present an application of the parallel Boruvka minimum spanning forest algorithm to compute watershed segmentation. Both techniques are fully executed on GPU and share the same data structures that embed disjoint-set-trees and distributed-link-lists. We evaluate our k -means approach with regards to state-of-the-art methods, that are, the well known SLIC algorithm, and the adaptive segmentation approach SPASM. We argue that our implementation has the shortest execution time among the tested methods, with a near real time performance and quasi linear acceleration factor, while it provides more regular shape superpixel segmentation based on hexagonal tessellation. Watershed minimum spanning forest method is presented and evaluated accordingly to the same experimental framework. • We propose a generic decentralized parallel data structures and optimization algorithms on graphics processing unit (GPU) applied to image segmentation problem. • Two types of algorithms are presented and implemented on GPU based on common parallel data structures. The first algorithm include a parallel implementation of the well-known k -means algorithm with application to 3D data. • The second parallel algorithm include an application of the parallel Boruvka minimum spanning forest algorithm to compute watershed segmentation. • Our proposed implementations have the shortest execution time campared to the tested methods, with near real time performance, and quasi linear acceleration factor, while it results a more regular shape superpixel segmentation. [ABSTRACT FROM AUTHOR]

Abstract: We study the hybridization of the self-organizing map (SOM) in an evolutionary algorithm to solve the Euclidean traveling salesman problem (TSP). The evolutionary dynamics consist of interleaving the SOM execution with a mapping operator, a fitness evaluation and a selection operator. SOM and mapping operators have a similar structure based on closest point findings and simple moves performed in the plane. We evaluate the approach on standard TSP test problems and show that it performs better, with respect to solution quality and/or computation time, than other neural network approaches given previously in the literature. Experiments are conducted on 91 publicly available TSP instances with up to 85900 cities. [Copyright &y& Elsevier]

We propose an intelligent tool for terrestrial transportation design based on the underlying concept of adaptive meshing. Vehicle routes are deformable visual patterns which cover the geographic area adapting shapes to distributed demands or specific places. In this way the system allows dynamic interaction and continuous visual feedback for the designer constructing and evaluating a transportation bus network. To assist the designer, an optimization framework merging neural networks and evolutionary algorithms permits one to position services and create routes among them automatically. The transport system optimizer built on a geographic information system is illustrated by application to a real life case of clustering and routing for the transportation of the 780 employees of an enterprise. [ABSTRACT FROM AUTHOR]

This work focuses on the dynamic Pickup and Delivery Problem with Time Windows (PDPTW). The transport requests should be performed using the available fleet of vehicles. The vehicles move between the nodes of a road network. The aim of this work is to propose a model which allows, during a transport plan creation, to take into account predictable events. Particularly, we consider the frequency of requests at any node in the road network and the construction of vehicle routes that will allow new requests to be inserted without any significant route modification. Therefore, we construct routes that pass near the nodes where transport requests are most frequently generated.

With the development of computer capabilities, memories and network abilities, we need more efficient and robust algorithms to manage databases and to store and retrieve the relevant information for the user. The aim of this work is to automate the construction of a neural network Information Retrieval System (IRS) adapted to a medical image database. The user builds queries and the system must retrieve the relevant documents or images. Queries are groups of keywords or items associated with relevant images. In our approach, the set of queries and the binary relevance judgments on the documents constitute complex learning data associations. There are two phases in the automatic construction of the IRS. The indexing phase builds the learning data base and then a specific learning algorithm builds the neural network. For the system to be able to immediately learn these complex data, we have developed a new specific algorithm. It allows a perfect learning of a binary logical table in a stepwise fashion without forgetting the previously learnt logical combinations. Furthermore, this algorithm works very quickly and leads to a parallel implementation for large databases. [ABSTRACT FROM AUTHOR]

Automatically finding correspondences between object features in images is of main interest for several applications, as object detection and tracking, identification, registration, and many derived tasks. In this paper, we address feature correspondence within the general framework of graph matching optimization and with the principal aim to contribute. We proposed two optimized algorithms: first-order and second-order for graph matching. On the one hand, a first-order normalized cross-correlation (NCC) based graph matching algorithm using entropy and response through Marr wavelets within the scale-interaction method is proposed. First, we proposed a new automatic feature detection processing by using Marr wavelets within the scale-interaction method. Second, feature extraction is executed under the mesh division strategy and entropy algorithm, accompanied by the assessment of the distribution criterion. Image matching is achieved by the nearest neighbor search with normalized cross-correlation similarity measurement to perform coarse matching on feature points set. As to the matching points filtering part, the Random Sample Consensus Algorithm (RANSAC) removes outliers correspondences. One the other hand, a second-order NCC based graph matching algorithm is presented. This algorithm is an integer quadratic programming (IQP) graph matching problem, which is implemented in Matlab. It allows developing and comparing many algorithms based on a common evaluation platform, sharing input data, and a customizable affinity matrix and matching list of candidate solution pairs as input data. Experimental results demonstrate the improvements of these algorithms concerning matching recall and accuracy compared with other algorithms. [ABSTRACT FROM AUTHOR]

This paper proposes a parallel computation model for the self-organizing map (SOM) neural network applied to Euclidean traveling salesman problems (TSP). This model is intended for implementation on the graphics processing unit (GPU) platform. The Euclidean plane is partitioned into an appropriate number of cellular units, called cells, and each cell is responsible of a certain part of the data and network. Compared to existing GPU implementations of optimization metaheuristics, which are often based on data duplication or mixed sequential/parallel solving, the advantage of the proposed model is that it is decentralized and based on data decomposition. Designed for handling large-scale problems in a massively parallel way, the required computing resources grow linearly along the problem size. Experiments are conducted on 52 publicly available Euclidean TSP instances with up to 85,900 cities for the largest TSPLIB instance and 71,009 cities for the largest National TSP instance. Experimental results show that our GPU implementations of the proposed model run significantly faster than the currently best-performing neural network approaches, to obtain results of similar quality. [ABSTRACT FROM AUTHOR]

Current accurate stereo matching algorithms employ some key techniques that are not suitable for parallel GPU architecture. It will be tricky and cumbersome to directly take these techniques into GPU applications. Trying to tackle this difficulty, we design two GPU-based stereo matching algorithms, one using a local fixed aggregation window whose size is configurable, and the other using an adaptive aggregation window which only includes necessary pixels. We use the winner-takes-all (WTA) principle for optimization and a plain voting refinement for post-processing; both do not need complex data structures. We aim to implement on GPU platforms fast stereo matching algorithms that produce results with same-level quality as other WTA local dense methods that use window-based cost aggregation. In our GPU-based implementation of the fixed window partially demosaiced CFA stereo matching application, accelerations up to 20 times are obtained for large size images. In our GPU-based implementation of the adaptive window color stereo matching application, experiment results show that it can handle four pairs of standard images from Middlebury database within roughly 100 ms. [ABSTRACT FROM AUTHOR]