Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem

Leopoldo Noel Gaxiola Sanchez, Juan Jose Tapia Armenta, Victor Hugo Diaz Ramirez
Instituto Politecnico Nacional, CITEDI, Ave. del Parque 1310, Mesa de Otay, Tijuana, B.C., 22510, Mexico
DIFU100 ci@, Vol. 8, No. 2, 2014

   title={Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem},

   author={S{‘a}nchez, Leopoldo Noel Gaxiola},

   journal={Revista en Ingenier{‘i}a y Tecnolog{‘i}a, UAZ},





Download Download (PDF)   View View   Source Source   



The implementation of parallel genetic algorithms on a graphic processor GPU to solve the Travelling Salesman Problem instances is presented. Two versions of parallel genetic algorithms are implemented, a Parallel Genetic Algorithm with Islands Model and a Parallel Genetic Algorithm with Elite Island; the two versions were executed on a GPU. In both cases, each individual is represented by a thread, and each island is represented by a block of threads. The main feature of the Parallel Genetic Algorithm with Elite Island in this work is that there is not migration between islands, instead, an Elite Island is created with the best individuals from each of the islands to share the best individuals. The individual with minimal fitness function is the sought solution. The results show that the Elite Island model is better than the island model with migration of individuals.
VN:F [1.9.22_1171]
Rating: 4.5/5 (2 votes cast)
Parallel Genetic Algorithms on a GPU to Solve the Travelling Salesman Problem, 4.5 out of 5 based on 2 ratings

* * *

* * *

TwitterAPIExchange Object
    [oauth_access_token:TwitterAPIExchange:private] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
    [oauth_access_token_secret:TwitterAPIExchange:private] => o29ji3VLVmB6jASMqY8G7QZDCrdFmoTvCDNNUlb7s
    [consumer_key:TwitterAPIExchange:private] => TdQb63pho0ak9VevwMWpEgXAE
    [consumer_secret:TwitterAPIExchange:private] => Uq4rWz7nUnH1y6ab6uQ9xMk0KLcDrmckneEMdlq6G5E0jlQCFx
    [postfields:TwitterAPIExchange:private] => 
    [getfield:TwitterAPIExchange:private] => ?cursor=-1&screen_name=hgpu&skip_status=true&include_user_entities=false
    [oauth:protected] => Array
            [oauth_consumer_key] => TdQb63pho0ak9VevwMWpEgXAE
            [oauth_nonce] => 1477628609
            [oauth_signature_method] => HMAC-SHA1
            [oauth_token] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
            [oauth_timestamp] => 1477628609
            [oauth_version] => 1.0
            [cursor] => -1
            [screen_name] => hgpu
            [skip_status] => true
            [include_user_entities] => false
            [oauth_signature] => WTUwegA21SazIwvzkl/lk2SOGgQ=

    [url] => https://api.twitter.com/1.1/users/show.json
Follow us on Facebook
Follow us on Twitter

HGPU group

2037 peoples are following HGPU @twitter

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: