11910

GACO: A GPU-based High Performance Parallel Multi-ant Colony Optimization Algorithm

Fan Li, Ming-lu Jin
Faculty of Electronic Information and Electrical Engineering, Dalian University of Technology, Dalian 116024, China
Journal of Information & Computational Science 11:6, 1775-1784, 2014
@article{li2014gaco,

   title={GACO: A GPU-based High Performance Parallel Multi-ant Colony Optimization Algorithm},

   author={Li, Fan and Jin, Ming-lu},

   year={2014}

}

Download Download (PDF)   View View   Source Source   

575

views

As a population-based algorithm, Ant Colony Optimization (ACO) is intrinsically massively parallel, and therefore it is expected to be well-suited for implementation on GPUs (Graphics Processing Units). In this paper, we present a novel ant colony optimization algorithm (called GACO), which based on Compute Unified Device Architecture (CUDA) enabled GPU. In GACO algorithm, we utilize some novel optimizations, such as hybrid pheromone matrix update, dynamic nearest neighbor path construction, and multiple ant colony distribution, which result in a higher speedup and a better quality solutions compared to other peer of algorithms. GACO is tested by the Traveling Salesman Problem (TSP) benchmark, and the experimental results show a total speedup up to 40.1x and 35.7x over implementation of Ant Colony System (ACS) and Max-min Ant System (MMAS), respectively.
VN:F [1.9.22_1171]
Rating: 0.0/5 (0 votes cast)

* * *

* * *

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] => 1480791446
            [oauth_signature_method] => HMAC-SHA1
            [oauth_token] => 301967669-yDz6MrfyJFFsH1DVvrw5Xb9phx2d0DSOFuLehBGh
            [oauth_timestamp] => 1480791446
            [oauth_version] => 1.0
            [cursor] => -1
            [screen_name] => hgpu
            [skip_status] => true
            [include_user_entities] => false
            [oauth_signature] => 7HcZbljinfC30CKY5PoI5Zk80aM=
        )

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

HGPU group

2079 peoples are following HGPU @twitter

HGPU group © 2010-2016 hgpu.org

All rights belong to the respective authors

Contact us: