From the TSP to the Dynamic VRP: an Application of Neural Networks in Population based Metaheuristic
20130101
9783642306648
9783642306648

1
2
3
Metaheuristics for Dynamic Optimization
Studies in Computational Intelligence
From the TSP to the Dynamic VRP: an Application of Neural Networks in Population based Metaheuristic
433
Dynamic Vehicle Routing Problem for medical emergency management
20110101
9789533075464
9789533075464

1
2
3
4
Self Organizing Maps  Applications and Novel Algorithm Design, New Achievements
13
Selforganizing maps in population based metaheuristic to the dynamic vehicle routing problem
20121101
13826905
13826905

1
2
3
4
Journal of Combinatorial Optimization
24
4
437
458
SelfOrganizing Maps in Evolutionary Approach for the Traveling Salesman Problem and Vehicle Routing Problem with Time Windows
20080101

1
2
3
Journal of Information and Optimization Sciences
29
3
485
512
Interactive Meshing for the Design and Optimization of Bus Transportation Networks
20070901

1
2
Journal of Transportation Engineering, ASCE Publications
133
9
529
538
Transport Clustering and Routing as a Visual Meshing Process
20070701

1
2
Journal of Information and Optimization Sciences
28
4
573
601
SelfOrganizing Maps in Evolutionary Approach for the Vehicle Routing Problem with Time Windows
20070101

1
2
3
International Journal of Computer Science and Network Security
7
1
103
110
Un framework organisationnel et multiagent pour la conception de métaheuristiques
20100922

1
2
3
Revue d'Intelligence Artificielle RSTIRIA
24
6
787
816
Coalitionbased metaheuristic: a selfadaptive metaheuristic using reinforcement learning and mimetism
20101201

1
2
3
Journal of Heuristics
16
6
859
879
A Memetic Neural Network for the Euclidean Traveling Salesman Problem
20090923

1
2
Neurocomputing
72
1250
1264
MultiAgent Environment for Modelling and Solving Dynamic Transport Problems
20090923

1
2
3
4
Computing and Informatics
28
3
277
298
The Memetic SelfOrganizing Map Approach to the Vehicle Routing Problem
20080923

1
2
Soft Computing  A Fusion of Foundations
12
11
1125
1141
SelfOrganization in Evolution for the Solving of Distributed Terrestrial Transportation Problems
20080423

1
2
Soft Computing applications in industry
Studies in Fuzziness and SoftComputing
226
SelfOrganization and Evolution combined to address the Vehicle Routing Problem
20080923

1
2
Lecture Notes in Computer Science (AE’2007)
4926
100
111
A Cooperative and Selfadaptive Metaheuristic for the Facility Location Problem
20090708

1
2
3
Montreal, Canada
11th Annual conference on Genetic and Evolutionary Computation (GECCO’09)
A CoalitionBased Metaheuristic for the Vehicle Routing Problem
20080601

1
2
3
Hong Kong
IEEE Congress on Evolutionary Computation
Approach for optimized and dynamic medical emergency management
20080923

1
2
3
the 5th International Conference Service Systems and Service Management  Exploring Service Dynamics with Science and Innovative Technology (ICSSSM'08)
An Organizational View of Metaheuristics
20080512

1
2
3
Estoril, Portugal
International Workshop on Optimisation in MultiAgent Systems. International Conference on Autonomous Agents and Multiagent Systems (AAMAS'08)
Dynamic Optimization for Medical Emergencies Management
20070923

1
2
3
4
Fez, Morocco
the IEEE First International Conference of EMedical Systems
SelfOrganizing Maps in Evolutionary Approach meant for Dimensioning Routes to the Demand
20070525

1
2
3
Vienna, Austria
the 21th International Conference on Computer, Electrical, and Systems Science, and Engineering (CESSE 2007)
Two Phases Parallel Hyperheuristic Approach to the Bus Driver Scheduling Problem
20110808

1
2
3
4
Phoenix, Arizona
the 5th Multidisciplinary International Scheduling Conference (MISTA 2011)
A hyperheuristic system for Bus driver scheduling problem
20100603

1
2
3
4
France
EU/MEeting 2010
Un framework organisationnel pour la conception et l'implantation multiagent de métaheuristiques
20080915

1
2
3
Brest, France
Journées Francophones sur les Systèmes MultiAgents (JFSMA 2008)
Optimisation de plan de mobilité
20071221

1
2
3
Journée industrielle "Optimisation des ressources dans les entreprises" (CNRS/ROADEF/UTBM)
Multiagent Approach to Dynamic Pickup and Delivery Problem with Uncertain Knowledge about Future Transport Demands
20061001
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 in road network. This aim of the work is to propose a model which allows predictable future events to take into consideration when a transport plan is created. Particularly, we consider the probability of the frequency of requests at any node in the road network and construction of such vehicle routes that will allow new requests to be inserted into the route without any significant route modification. Therefore, we try to construct routes that pass near the nodes where transport requests are most frequently generated.
1
2
3
4
Fundamenta Informaticae
71
1
27
36
Automatic Mesh Generation for Mobile Network Dimensioning using Evolutionary Approach
20051105

1
2
3
4
IEEE Transactions on Evolutionary Computation
9
1
Local search study of honeycomb clustering problem for cellular planning
20061105

1
2
Journal of Mobile Network Design and Innovation
1
2
Modeling and Optimization of City Traffic with the Agent Approach
20060517

1
2
3
12th IFAC Symposium on Information Control Problems in Manufacturing, INCOM'06, SaintEtienne, France, May 1719
A Neural Evolutionary Algorithm for Geometric Median Cycle Problem
20050212

1
2
3
European Simulation and Modeling Conference, ESM’2005, EUROSIS, Porto, Portugal, October 2426
Multiagent environment for dynamic transport planning and scheduling
20040606
3540221166
3540221166

1
2
3
4
Krakow, Poland
4th International Conference on Computational Science  ICCS 2004. Lecture Notes in Computer Science vol. 3038
A neural network model to index medical images
19990302
We present an application of neural network indexing techniques to information retrieval in large medical image databases.
1
2
Journal of Biological Systems
7
1
45
51
An information retrieval system using a new neural network model
19970212

1
2
CYBERNETICA
XL
2
127
139
Du comportement de groupe au comportement individuel : un modèle évolutionniste pour optimiser la consultation de sites web complexes
20030212

1
2
IEEE Conférence Internationale Sciences Electroniques, Technologies de l'Information et des Télécommunications, IEEE SETIT'03, Sousse, Tunisie, 1721 Mars
Apprentissage à distance : un modèle évolutionniste pour assister un public hétérogène
20030212

1
2
3
Second Colloque du Guéret autour des Communautés Virtuelles Educatives, Guéret, France, 46 juin
Grilles AutoOrganisatrices pour le Dimensionnement de Parcours de Véhicules adaptés à la Demande
20020212

1
2
3
Troisième Conférence Internationale en Recherche Opérationnelle, CIRO'02, Théorie et Application, Marrakech, Maroc, 46 Juin
Modélisation macroscopique du trafic sur un carrefour urbain: approches neuronales et estimation paramétrique
20010212

1
2
3
4
3e Conférence Francophone de Modélisation et Simulation, MOSIM'01, Université de Technologie de Troyes, France, 2527 avril
A Connexionnist Approach to the Hexagonal Mesh Generation
20000212

1
2
3
Lausanne, Switzerland
16th IMACS World Congress
A MultiAgent Approach to Adaptive Mesh Generation
20000212

1
2
3
4
AgentBased Simulation, SCSEurope, Passau, Germany, May 23
Evolutionary Meshing for Mobile Network Dimensioning
20000212

1
2
3
4
5
2ièmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, AlgoTel'2000, La Rochelle, France
Mobile Network Dimensioning: an Evolutionary Approach
19990212

1
2
3
4
Seventh International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS’99, cosponsored by ACM, IEEE
Environnement d’aide à la réutilisation d’algorithmes d’optimisation et applications
19990212

1
2
3
Troisième Séminaire Optimisation du CNET (Centre National d’Etude des Télécommunications), Sophia Antipolis, 2830 Avril
Un réseau de neurones pour améliorer la précision d’un système de recherche d’informations d’images médicales
19980212

1
2
15e congrès international de cybernétique de Namur, Belgique, Août
A Neural Network Model for Identification
19970212

1
15th IMACS World Congress, Artificial Intelligence and Computer Science, vol. 4
A neural network which increases in a suitable size
19970212

1
2
11th International Conference on Mathematical and Computer Modelling and Scientific Computing, Washington, March
A neural network model for the IRS
19970212

1
2
International Conference on Mathematical and Computer Modelling and Scientific Computing, special issue of the journal Mathematical and Computer Modelling and Scientific Computing, vol. 8
Sur un algorithme de synthèse de fonction booléenne par un réseau neuronal
19950212

1
2
3
14e congrès international de cybernétique de Namur, Belgique, Août
A Neural System to Detect Faulty Components on Complex Boards in Digital Switches
19950212

1
2
3
Int. Workshop on Applications of Neural Networks to Telecommunications 2
Système de détection de composants défectueux sur cartes numériques complexes
19940212

1
2
3
First International Conference on Neural Networks and their Applications, NEURAP'94
From simple heuristics to evolutionary approach for routing messages in a NoC
20100503

1
2
3
4
5
France
EU/MEeting 2010
Two Phases Distributed Hyperheuristic Approach to the Bus Driver Scheduling Problem
20120412

1
2
3
4
Angers
Congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision, ROADEF’12
An Evolutionary Approach To Pickup and Delivery Problem with Time Windows
20040606
ISBN 354022114X
ISBN 354022114X

1
2
3
4
Computational Science  ICCS 2004, 4th International Conference, Krakow, Poland.. Lecture Notes in Computer Science, vol. 3038
Evolutionary methods for the Antenna Parameter Setting Problem
20020415
0769515738
0769515738

1
2
3
4
RFlorida, USA
16th International Parallel and Distributed Processing Symposium (IPDPS 2002), Workshop on BiologicallyInspired Solutions to Parallel Processing Problems  BIOSP
SelfAdaptive NetworkonChip Interface
20131201
This paper presents an original approach of bandwidthoriented selfadaptivity in the domain of Networkon Chip, where reconfiguration is handled by network interfaces offering traffic with guarantee of service. Reconfiguration is first based on multiple FIFOs with variables bounds and implemented in a single dualport memory with a dedicated controller. Secondly, it relies on multiple and compliant TDMA tables based on a new heuristic for path computation. Combination of both techniques provide significant bandwidth improvement with a negligible resource overhead. The proposed solution is demonstrated with cycleaccurate VHDL simulation and FPGA implementation for synthetic and image processing applications.
1
2
3
IEEE Embedded Systems Letters
5
4
73
76
The MultiAgent Patrolling Problem  Theoretical Results about Cyclic Strategies
20140604
Patrolling an environment consists in visiting as frequently as possible its most relevant areas in order to supervise, control or protect it. This task is commonly performed by a team of agents that seek to optimize a performance criterion generally based on the notion of node idleness, that is the period during which a node remains unvisited. For some patrolling strategies, the performance criterion may be unbounded or the classical iterative evaluation algorithm may be ineffective to rapidly provide this performance criterion. The contribution of this paper is fourfold. Firstly we extend the formulation of the classical multiagent patrolling problem. Secondly we define a large class of multiagent patrolling strategies, the consistent cyclic patrolling strategies, where every agent may visit some nodes once before ultimately visiting the same set of nodes infinitely often. Idlenessbased performance criteria considered in this paper to evaluate such strategies are always bounded. Thirdly we provide theoretical results about the computation time required for evaluating efficiently and accurately any consistent cyclic strategy. Fourthly we propose an efficient and accurate evaluation algorithm of polynomial complexity based on these theoretical results.
1
2
3
Practical Applications of Agents and MultiAgent Systems (PAAMS)
Le problème de la patrouille multiagent  Etude de convergence de l'évaluation des stratégies cycliques
20141230
Le problème de la patrouille multiagent implique une équipe d'agents qui doivent visiter les lieux stratégiques d'un environnement le plus fréquemment possible. Ce problème d'optimisation consiste généralement à déterminer une stratégie de patrouille multiagent minimisant la pire oisiveté d'un graphe, c'està dire la plus grande durée pendant laquelle un noeud n'a pas été visité. Nous proposons dans cet article d'étudier de manière théorique l'évaluation des stratégies de patrouille cycliques. Une telle stratégie est constituée de n couples de précycles et de cycles, n étant le nombre d'agents patrouilleurs. Chaque cycle définit la liste des noeuds qu'un agent doit visiter indéfiniment, le premier noeud étant le même que le dernier noeud. Chaque pré cycle définit la liste des noeuds visités par un agent pour atteindre son cycle de patrouille. Nous présentons dans cet article les conditions de convergence permettant à un algorithme efficace d'évaluer en un nombre fini d'étapes la pire oisiveté de telles stratégies. Un algorithme d'évaluation basé sur ces résultats théoriques est également décrit.
1
2
3
Revue d'Intelligence Artificielle
A Massive Parallel Cellular GPU implementation of Neural Network to Large Scale Euclidean TSP
20131124
This paper proposes a parallel model of the self organizing map (SOM) neural network applied to the Euclidean traveling salesman problem (TSP) and intended for implementation on the graphics processing unit (GPU) platform. The plane is partitioned into an appropriate number of cellular units, that are each responsible of a certain part of the data and network. The advantage of the parallel algorithm is that it is decentralized and based on data decomposition, rather than based on data duplication, or mixed sequential/parallel solving, as often with GPU implementation of optimization metaheuristics. The processing units and the required memory are with linear increasing relationship to the problem size, which makes the model able to deal with very large scale problems in a massively parallel way. The approach is applied to Euclidean TSPLIB problems and National TSPs with up to 33708 cities on both GPU and CPU, and these two types of implementation are compared and discussed.
1
2
3
12th Mexican International Conference on Artificial Intelligence, MICAI 2013, Mexico City, Mexico, November 2430, 2013, Proceedings, Part II (Best Student Paper Award), Advances in Soft Computing and Its Applications, Lecture Notes in Computer Science, Volume 8266, pp.118129
A Near RealTime Color Stereo Matching Method for GPU
20131117
http://www.thinkmind.org/index.php?view=article&articleid=infocomp_2013_2_10_10094
This paper presents a near realtime stereo matching method with acceptable matching results. This method consists of three important steps: SADALD cost measure, cost aggregation in adaptive window in crossbased support regions and a refinement step. These three steps are well organized to be adopted by the GPU's parallel architecture. The parallelism brought by GPU and CUDA implementations provides significant acceleration in running time. This method is tested on six pairs of images from Middlebury dataset, each possibly declined within different sizes. For each pair of images it can generate acceptable matching results in roughly less than 100 milliseconds. The method is also compared with three GPUbased methods and one CPUbased method on increasing size image pairs.
1
2
3
4
5
Lisbon, Portugal
Third International Conference on Advanced Communications and Computation (INFOCOMP'2013)
Cellular GPU Model for Structured Mesh Generation and its Application to the StereoMatching Disparity Map
20131209
This paper presents a cellular GPU model for structured mesh generation according to an input stereomatching disparity map. Here, the disparity map stands for a density distribution that reflects the proximity of objects to the camera in 3D space. The meshing process consists in covering such data density distribution with a topological structured hexagonal grid that adapts itself and deforms according to the density values. The goal is to generate a compressed mesh where the nearest objects are provided with more details than objects which are far from the camera. The solution we propose is based on the Kohonen's SelfOrganizing Map learning algorithm for the benefit of its ability to generate a topological map according to a probability distribution and its ability to be a natural massive parallel algorithm. We propose a GPU parallel model and its implantation of the SOM standard algorithm, and present experiments on a set of standard stereo matching disparity map benchmarks.
1
2
3
4
5
Anaheim, California, USA
IEEE International Symposium on Multimedia (ISM'2013)
Partial demosaicing for stereo matching of CFA images on GPU and CPU
20131117
http://newtheme.hgpu.org/?p=11164
This paper presents a GPU implementation of a partial demosaicing scheme that is specially designed for stereo matching of CFA image. This method consists of three main techniques keys: the adapted matching cost for CFA image, the estimated Second color component based on Hamilton’s estimate method and a robust cost aggregation window. Experiments are carried out to explore the performance for this method on GPU both at matching quality and matching efficiency, with comparison with version on CPU. The experiments on different size image pairs from Middlebury dataset show that this method can be substantially accelerated on GPU when the image size is large and has still space for improvements in performance.
1
2
3
4
5
Lisbon, Portugal
International Conference on Advanced Communications and Copmutation (INFOCOMP'2013)
Heuristique de génération de colonnes pour l'habillage dans les systèmes de transport en commun
20130213
Heuristique de génération de colonnes pour l'habillage dans les systèmes de transport en commun
1
2
3
4
Congrès de la Société Française de Recherche Opérationnelle et d’Aide à la Décision ROADEF’13
A study of hyperheuristic combinations system for scheduling problem
20100325
A study of hyperheuristic combinations system for scheduling problem
1
2
3
4
10th anniversary of metaheuristics community, Lorient
Parallel Structured Mesh Generation with Disparity Maps by GPU Implementation
20150316
The goal of structured mesh is to generate a compressed representation of the 3D surface, where near objects are provided with more details than objects far from the camera, according to the disparity map. The solution is based on the Kohonens SelfOrganizing Map algorithm for the benefits of its ability to generate a topological map according to a probability distribution and its potential to be a natural massive parallel algorithm. The disparity map, which stands for a density distribution that reflects the proximity of objects to the camera, is partitioned into an appropriate number of cell units, in such a way that each cell is associated to a processing unit and responsible of a certain area of the plane. The advantage of the proposed model is that it is decentralized and based on data decomposition. The required processing units and memory are with linearly increasing relationship to the problem size. Experimental results show that our GPU implementation is able to provide near real time performance with small size disparity maps and the running time increases in a linear way with a very weak increasing coefficient. The proposed method is suitable to deal with large scale problems in a massively parallel way.
1
2
3
4
5
IEEE Transactions on Visualization and Computer Graphics
21
9
Parallel and Distributed Implementation Models for Bioinspired Optimization Algorithms
20141128
Bioinspired optimization algorithms have natural parallelism but practical implementations in parallel and distributed computational systems are nontrivial. Gains from different parallelism philosophies and implementation strategies may vary widely. In this paper, we contribute with a new taxonomy for various parallel and distributed implementation models of metaheuristic optimization. This taxonomy is based on three factors that every parallel and distributed metaheuristic implementation needs to consider: control, data, and memory. According to our taxonomy, we categorize different parallel and distributed bioinspired models as well as local search metaheuristic models. We also introduce a new designed GPU parallel model for the Kohonen’s selforganizing map, as a representative example which belongs to a significant category in our taxonomy.
1
2
International Conference on Swarm Intelligence Based Optimization, ICSIBO'2014, Mulhouse, France, May 1314, 2014, Swarm Intelligence Based Optimization, Lecture Notes in Computer Science Volume 8472, pp 6879, 28 Nov.
Massively parallel cellular matrix model for superpixel adaptive segmentation map
20151025
We propose the concept of superpixel adaptive segmentation map, to produce a perceptually meaningful representation of rigid pixel image, with higher resolution of more superpixels on interesting regions according to the density distribution of desired attributes. The solution is based on the selforganizing map (SOM) algorithm, for the benefits of SOM's ability to generate a topological map according to a probability distribution and its potential to be a natural massive parallel algorithm. We also propose the concept of parallel cellular matrix which partitions the Euclidean plane defined by input image into an appropriate number of uniform cell units. Each cell is responsible of a certain part of the data and the cluster center network, and carries out massively parallel spiral searches based on the cellular matrix topology. Experimental results from our GPU implementation show that the proposed algorithm can generate adaptive segmentation map where the distribution of superpixels reflects the gradient distribution or the disparity distribution of input image, with respect to scene topology. When the input size augments, the running time increases in a linear way with a very weak increasing coefficient.
1
2
3
4
14th Mexican International Conference on Artificial Intelligence (MICAI 2015), Cuernavaca, Morelos, Mexico, Oct. 2531, 2015, Advances in Artificial Intelligence and Its Applications, Lecture Notes in Computer Science, vol.9414, pp.325336
Massively parallel cellular matrix model for selforganizing map applications
20151206
We propose the concept of parallel cellular matrix which partitions the Euclidean plane defined by input data into an appropriate number of uniform cell units. Each cell is responsible of a certain part of the data and the network of the self organizing map (SOM), and carries out massive parallel spiral searches based on the cellular matrix topology. The advantage of the proposed model is that it is decentralized and based on data decomposition. The required processing units and memory are with linearly increasing relationship to the problem size. Based on the cellular matrix model, the parallel SOM is implemented to deal with various applications including the traveling salesman problem, structured mesh generation, and superpixel adaptive segmentation map. Experimental results of our GPU implementation show that the running time increases in a linear way with a very weak increasing coefficient according to the input size. The proposed cellular matrix model is suitable to deal with large scale problems in a massively parallel way.
1
2
3
2015 IEEE International Conference on Electronics, Circuits, and Systems (ICECS 2015), Cairo, Egypt, Dec. 0609
Massively parallel gpu computing for fast stereo correspondence algorithms
20160406
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 GPUbased 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 winnertakesall (WTA) principle for optimization and a plain voting refinement for postprocessing; both do not need complex data structures. We aim to implement on GPU platforms fast stereo matching algorithms that produce results with samelevel quality as other WTA local dense methods that use windowbased 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 milliseconds.
1
2
3
4
5
Journal of Systems Architecture
65
Dossier Intelligence Artificielle et Transport  L'équipe systèmes multiagents et optimisation de l'UTBM
20160408
http://afia.asso.fr/tikidownload_file.php?fileId=300

1
2
3
4
5
6
7
8
9
10
Bulletin AFIA
91
37
40
Distributed Local Search for Elastic Image Matching
20160613
We propose a distributed local search (DLS) algorithm, which is a parallel formulation of a local search procedure in an attempt to follow the spirit of standard local search metaheuristics. Applications of different operators for solution diversification are possible in a similar way to variable neighborhood search. We formulate a general energy function to be equivalent to elastic image matching problems. A specific example application is stereo matching. Experimental results show that the GPU implementation of DLS seems to be the only method that provides an increasing acceleration factor as the instance size augments, among eight tested energy minimization algorithms.
1
2
3
4
International Conference on Swarm Intelligence Based Optimization, ICSIBO'2016, Mulhouse, France, June 1314. Swarm Intelligence Based Optimization, ICSIBO 2016, Lecture Notes in Computer Science: Volume 10103, pp.6574, 25 Nov.
Stereo Matching by using Selfdistributed Segmentation and Massively Parallel GPU Computing
20160529
9783319393841 • 9783319393834
9783319393841 • 9783319393834
As an extension of using image segmentation to do stereo matching, firstly, by using selforganizing map (som) and Kmeans algorithms, this paper provides a selfdistributed segmentation method that allocates segments according to image's texture changement where in most cases depth discontinuities appear. Then, for stereo, under the fact that the segmentation of left image is not exactly same with the segmentation of right image, we provide a matching strategy that matches segments of left image to pixels of right image as well as taking advantage of border information from these segments. Also, to help detect occluded regions, an improved aggregation cost that considers neighbor valid segments and their matching characteristics is provided. For post processing, a gradient border based median filter that considers the closest adjacent valid disparity values instead of all pixels' disparity values within a rectangle window is provided. As we focus on realtime execution, these timeconsumming works for segmentation and stereo matching are executed on a massively parallel cellular matrix GPU computing model. Finaly, we provide our visual dense disparity maps before post processing and final evaluation of sparse results after postprocessing to allow comparison with several ranking methods top listed on Middlebury.
1
2
Zakopane, Pologne
International Conference on Artificial Intelligence and Soft Computing. Lecture Notes in Artificial Intelligence LNAI, Volume 9693, Springer International Publishing, 2016: 723733
A massively parallel neural network approach to largescale Euclidean traveling salesman problems
20170220
This paper proposes a parallel computation model for the selforganizing 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 largescale 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.
1
2
3
Neurocomputing
240
137
151
Local search methods for conflictfree routing in a multiprocessor system on chip
20120719
Are presented heuristics for cyclic Kshortest paths problems.
1
2
3
4
EURO 2012, 25th European conference on operational research, Vilnius, Lithuania
Parallel 2Opt Local Search on GPU
20171101
To accelerate the solution for large scale traveling salesman problems (TSP), a parallel 2opt local search algorithm with simple implementation based on Graphics Processing Unit (GPU) is presented and tested in this paper. The parallel scheme is based on technique of data decomposition by dynamically assigning multiple K processors on the integral tour to treat K edges' 2opt local optimization simultaneously on independent subtours, where K can be userdefined or have a function relationship with input size N. We implement this algorithm with doubly linked list on GPU. The implementation only requires O(N) memory. We compare this parallel 2opt local optimization against sequential exhaustive 2 opt search along integral tour on TSP instances from TSPLIB with more than 10000 cities.
1
2
World Academy of Science, Engineering and Technology, International Journal of Electrical, Computer, Energetic, Electronic and Communication Engineering, 2017, 11(3): 291295.
Massive Parallel Selforganizing Map and 2Opt on GPU to Large Scale TSP
20170615
9783319591520
9783319591520
This paper proposes a platform both for parallelism of selforganizing map (SOM) and the 2opt algorithm to large scale 2Dimensional Euclidean traveling salesman problems(TSP). Given a TSP tour with N input point, this platform makes these two algorithms working in a massively parallel way on graphical processing unit (GPU). Advantages of this platform include its flexibly topology preserving network, its fine parallel granularity and it allows maximum (N/3) 2opt optimization moves to be executed with O(N) time complexity within one tour orientation as well as keep the tour valid. The parallel technique follows data decomposition and decentralized control. We test this optimization method on large TSPLIB instances, experiments show that the acceleration factor we obtained makes the proposed method competitive, and allows for further increasing for very large TSP instances along with the quantity increase of physical cores in GPU systems.
1
2
Cádiz, Espagne
International WorkConference on Artificial Neural Networks. Lecture Notes in Computer Science LNCS, Volume 10305, Springer, Cham, 2017: 471482.
Cellular matrix model for parallel combinatorial optimization algorithms in Euclidean plane
20170815
We propose a parallel computation model, called cellular matrix model (CMM), to address largesize Euclidean graph matching problems in the plane. The parallel computation takes place by partitioning the plane into a regular grid of cells, each cell being affected to a single processor. Each processor operates on local data, starting from its cell location and extending its search to the neighborhood cells in a spiral search way. In order to deal with largesize problems, memory size and processor number are fixed as O(N), where N is the problem size. Then one key point is that closest point searching in the plane is performed in O(1) expected time for uniform or bounded distribution, for each processor independently. We define a generic loop that models the parallel projection between graphs and their matching, as executed by the many cells at a given level of computation granularity. To illustrate its efficacy and versatility, we apply the CMM, on GPU platforms, to two problems in image processing: superpixel segmentation and stereo matching energy minimization. Firstly, we propose an extended version of the wellknown SLIC superpixel segmentation algorithm, which we call SPASM algorithm, by using a parallel 2D selforganizing map instead of kmeans algorithm. Secondly, we investigate the idea of distributed variable neighborhood search, and propose a parallel search heuristic, called distributed local search (DLS), for global energy minimization of stereo matching problem. We evaluate the approach with regards to the stateoftheart graph cut and belief propagation algorithms. For each problem, we argue that the parallel GPU implementation provides new competitive quality/time tradeoffs, with substantial acceleration factors as the problem size increases.
1
2
3
Applied Soft Computing
Optimizing the Cyclic Kconflictfree Shortest Path Problem in a Networkonchip
20170915
We study a combinatorial optimization problem for conflictfree routing in a NetworkonChip. Based on time division multiplexing and cyclic emission, the problem consists in finding a set of K shortest paths, such that packets will never conflict through the network but can use shared communication links. in an efficient way.
1
2
3
4
International Journal of Computer & Software Engineering
1
2
Parallelisation of Optical Flow
20170906
1
2
3
4
FUTURMOB : préparer la transition vers la mobilité autonome, Montbéliard, France
An object tracking parallel algorithm based on multiframe difference and background subtraction
20170906
1
2
3
FUTURMOB : préparer la transition vers la mobilité autonome, Montbéliard, France
GPU based optical flow estimation using parallel local search algorithm
20180221
optical flow estimation problem of a pair of images using a distributed local search (DLS)
1
2
3
4
19ème congrès de la société Française de Recherche Opérationnelle et d'Aide à la Décision, ROADEF 2018
Massively Parallel Optical Flow using Distributed Local Search
20180222
9781612086125
9781612086125
The design of many tasks in computer vision field requires addressing difficult NPhard energy optimization problems. An example of application is the visual correspondence problem of optical flow, which can be formulated as an elastic pattern matching optimization problem. Pixels of a first image have to be matched to pixels in a second image while preserving elastic smoothness constraint on the first image deformation. In this paper, we present a parallel approach to address optical flow problem following the concept of distributed local search. Distributed local search consists in the parallel execution of many standard local search processes operating on a partition of the data. Each process performs local search on its own part of the data such that the overall energy is minimized. The approach is implemented on graphics processing unit (GPU) platform and evaluated on standard Middlebury benchmarks to gauge the substantial acceleration factors that can be achieved in the task of energy minimization.
1
2
3
4
The Tenth International Conference on Pervasive Patterns and Applications PATTERNS 2018. Barcelona, Spain. February 1822
Massive 2opt and 3opt Moves with High Performance GPU Local Search to Largescale Traveling Salesman Problem
20181216
2opt, 3opt or kopt heuristics are classical local search algorithms for traveling salesman problems (TSP) in combinatorial optimization area. This paper introduces a judicious decision making methodology of offloading which part of the kopt heuristic works in parallel on Graphics Processing Unit (GPU) while which part remains sequential, called ``multiple kopt evaluation, multiple kopt moves", in order to simultaneously execute, without interference, massive 2/3opt moves that are globally found on the same TSP tour or the same Euclidean space for many edges, as well as keep high performance for GPU massive kopt evaluation. We prove the methodology is judicious and valuable because of our originally proposed sequential non interacted 2/3exchange set partition algorithm taking linear time complexity and a new TSP tour representation, array of ordered coordinatesindex, in order unveil how to use GPU onchip shared memory to achieve the same goal as using doubly linked list and array of ordered coordinates for parallel kopt implementation. We test this methodology on 22 national TSP instances with up to 71009 cities and with brute initial tour solution. Average maximum 997 noninteracted 2opt moves are found and executed on the same tour of ch71009.tsp instance in one iteration of our proposed method. Experimental comparisons show that our proposed methodology gets huge acceleration over both classical sequential and a possible current fastest stateoftheart GPU parallel 2opt implementation.
1
2
Kalamata, Greece
International Learning and intelligent OptimizationN Conference
Spiral Search Method to GPU Parallel Euclidean Minimum Spanning Tree Problem
20180621
We present both sequential and data parallel approaches to build hierarchical minimum spanning forest (MSF) or tree (MST) in Euclidean space (EMSF/EMST) for applications whose input N points are uniformly or boundedly distributed in the Euclidean space. Each iteration of the sequential approach takes O(N) time complexity through combining Borůvka's algorithm with an improved componentbased neighborhood search algorithm, namely sliced spiral search, that is a newly proposed improvement of Bentley's spiral search for finding a component graph's closest outgoing point on 2D plane. We also propose a kd search technique to extend this kind of search into 3D space. The data parallel approach includes a newly proposed two direction breadthfirst search (BFS) implementation on graphics processing unit (GPU) platform, which is aimed for selecting a spanning tree's minimum outgoing weight. The GPU parallel approaches assign N threads with one thread associated to one input point, one thread occupies O(1) local memory and the whole algorithm occupies O(N) global memory. Experiments are conducted on point set in the plane of both uniformly distributed data sets and TSPLIB database. We evaluate computation time of the proposed approaches on more than 40 benchmarks with size N growing up to 10^5 points.
1
2
Kalamata, Greece
International Learning and intelligent OptimizationN Conference
Moving Object Detection and Tracking Based on Threeframe Difference and Background Subtraction with Laplace Filter
20180511
https://link.springer.com/chapter/10.1007/9783319912622_1#citeas
9783319912622
9783319912622
Moving object detection and tracking is an important research field. Currently, ones of the core algorithms used for tracking include frame difference method (FD), background subtraction method (BS), and optical flow method. Here, authors are looking at the first two approaches since very adequate for very fast realtime treatments whereas optical flow has higher computation cost since related to a dense estimation. Combination of FD and BS with filters and edge detectors is a way to achieve sparse detection fast. This paper presents a tracking algorithm based on a new combination of FD and BS, using Canny edge detector and Laplace filter. Laplace filter occupies a leading role to sharpen the outlines and details. Canny edge detector identifies and extracts edge information. Morphology processing is used to eliminate interfering items finally. Experimental results show that 3FDBDLC method has higher detection accuracy and better noise suppression than current combination methods on sequence images from standard datasets.
1
2
The 17th International Conference on Artificial Intelligence and Soft Computing ICAISC
Matlab GUI Application for Moving Object Detection and Tracking
20180626
https://www.dcaiconference.net/
In this paper a novel tool for moving object detection and tracking is presented. The main contribution of the proposed application is the achievement of a simple and intuitive graphic interface during the extraction the silhouette of targets by means of a new algorithm. This proposed algorithm which combined frame difference method, background subtraction method, Laplace filter and Canny edge detector together can realize a way to achieve sparse detection fast. Some modular architecture in this Graphical User Interface has been developed in order to enhance the user's experience. The experiment was tested by using sequence images from the MULTIVITION dataset, and experimental results showed that our proposed method has more validity and flexibility to get the desired result than conventional algorithm.
1
2
15th International Conference on Distributed Computing and Artificial Intelligence
GPU Implementation of Borůvka's Algorithm to Euclidean Minimum Spanning Tree based on Elias Method
20190301
We present both sequential and data parallel approaches to build hierarchical minimum spanning forest (MSF) or tree (MST) in Euclidean space (EMSF/EMST) for applications whose input N points are uniformly or boundedly distributed in Euclidean space. Each iteration of the sequential approach takes O(N) time complexity through combining Borůvka's algorithm with an improved componentbased neighborhood search algorithm, namely sliced spiral search, which is a newly proposed improvement to Bentley's spiral search for finding a component graph's closest outgoing point on the plane. It works based on the uniqueness property in Euclidean space, and allows O(1) time complexity for one search from a query point to find the component's closest outgoing point at different iterations of Borůvka's algorithm. The data parallel approach includes a newly proposed twodirection breadth first search (BFS) implementation on graphics processing unit (GPU) platform, which is specialized for selecting a spanning tree's shortest ougoing edge. This GPU twodirection parallel BFS enables a tree traversal operation to start from any one of its vertex acting as root. These GPU parallel implementations work by assigning N threads with one thread associated to one input point, one thread occupies O(1) local memory and the whole algorithm occupies O(N) global memory. Experiments are conducted on both uniformly distributed data sets and TSPLIB database. We evaluate computation time of the proposed approaches on more than 80 benchmarks with size N growing up to 10^6 points on personal laptop.
1
2
Applied Soft Computing
76
105
120
GPU Kdimensional nearest neighbor search for parallel Euclidean minimum spanning tree problem
20191207
We propose new data parallel approaches working on graphics processing unit (GPU) CUDA platform to build hierarchical minimum spanning forest (MSF) or tree (MST) for applications whose input only contains N points that are uniformly or boundedly distributed in Euclidean Kdimensional space (EMSF/EMST). Characteristic of these proposed algorithms follows ``data parallelism, decentralized control and constant local memory occupied by each GPU thread". Instead of using Kd tree search, we propose a nearest neighbor search algorithm, called Kd search, working based on dividing the Euclidean Kdimensional space into congruent and non overlapping cells where size of points in each cell is bounded. We further combine the uniqueness property in Euclidean space with this Kd search approach. This combination achieves sequential O(N) time complexity to find bichromatic closest pair between two color point sets, and O(N)/N time when working in concurrent read/write parallel model. The data parallel approach also exploits parallelism of each substep to build EMST in Borůvka's framework, for example CUDA kernels on a distributed dynamic linked list data structure for GPU parallel tree traversal operation, GPU parallel unionfind implementation. Experimental results are conducted on both 2D and 3D benchmarks with up to $10^7$ points on personal laptop, and show that our algorithm runs faster than current fastest dualtree Mlpack EMST library.
1
2
Submitted to journal
Massive 2opt and 3opt Moves with High Performance GPU Local Search to Largescale Traveling Salesman Problem
20191207
2opt, 3opt or kopt heuristics are classical local search algorithms for traveling salesman problems (TSP) in combinatorial optimization area. This paper introduces a judicious decision making methodology of offloading which part of the kopt heuristic works in parallel on Graphics Processing Unit (GPU) while which part remains sequential, called ``multiple kopt evaluation, multiple kopt moves", in order to simultaneously execute, without interference, massive 2/3opt moves that are globally found on the same TSP tour or the same Euclidean space for many edges, as well as keep high performance for GPU massive kopt evaluation. We prove the methodology is judicious and valuable because of our originally proposed sequential non interacted 2/3exchange set partition algorithm taking linear time complexity and a new TSP tour representation, array of ordered coordinatesindex, in order unveil how to use GPU onchip shared memory to achieve the same goal as using doubly linked list and array of ordered coordinates for parallel k opt implementation. We test this methodology on 22 national TSP instances with up to 71009 cities and with brute initial tour solution. Average maximum 997 noninteracted 2opt moves are found and executed on the same tour of ch71009.tsp instance in one iteration of our proposed method. Experimental comparisons show that our proposed methodology gets huge acceleration over both classical sequential and a possible current fastest stateoftheart GPU parallel 2opt implementation.
1
2
conference paper recommended to journal of Annals of Mathematics and Artificial Intelligence