CUDA-Based Genetic Algorithm on Traveling Salesman Problem

被引：0
|
作者：
Chen, Su [1 ]
Davis, Spencer [1 ]
Jiang, Hai [1 ]
Novobilski, Andy [1 ]
机构：
[1] Arkansas State Univ, Dept Comp Sci, Jonesboro, AR 72467 USA
来源：
COMPUTER AND INFORMATION SCIENCE 2011 | 2011年 / 364卷
关键词：
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Genetic algorithm is a widely used tool for generating searching solutions in NP-hard problems. The genetic algorithm on a particular problem should be specifically designed for parallelization and its performance gain might vary according to the parallelism hidden within the algorithm. NVIDIA CPUs that support the CUDA programming paradigm provide many processing units and a shared address space to ease the parallelization process. A heuristic genetic algorithm on the traveling salesman problem is specially designed to run on CPU. Then a corresponding CUDA program is developed for performance comparison. The experimental results indicate that a sequential genetic algorithm with intensive interactions can be accelerated by being translated into CUDA code for CPU execution.
引用
收藏
页码：241 / 252
页数：12
相关论文
共 50 条
  • [41] An efficient genetic algorithm for the traveling salesman problem with precedence constraints
    Moon, C
    Kim, J
    Choi, G
    Seo, Y
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2002, 140 (03) : 606 - 617
  • [42] A Solution to Traveling Salesman Problem Using Hybrid Genetic Algorithm
    Wang, Jian-cheng
    Yang, Yan-jie
    Lu, Ya-ping
    Lu, Ya-ping
    2013 INTERNATIONAL CONFERENCE ON COMPUTER SCIENCE AND ARTIFICIAL INTELLIGENCE (ICCSAI 2013), 2013, : 235 - 240
  • [43] Randomized Bias Genetic Algorithm to Solve Traveling Salesman Problem
    Gupta, Indresh Kumar
    Choubey, Abha
    Choubey, Siddhartha
    2017 8TH INTERNATIONAL CONFERENCE ON COMPUTING, COMMUNICATION AND NETWORKING TECHNOLOGIES (ICCCNT), 2017,
  • [44] Acceleration of a CUDA-Based Hybrid Genetic Algorithm and its Application to a Flexible Flow Shop Scheduling Problem
    Luo, Jia
    El Baz, Didier
    Hu, Jinglu
    2018 19TH IEEE/ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCE, NETWORKING AND PARALLEL/DISTRIBUTED COMPUTING (SNPD), 2018, : 117 - 122
  • [45] A hybrid genetic algorithm for the traveling salesman problem with pickup and delivery
    Zhao F.-G.
    Sun J.-S.
    Li S.-J.
    Liu W.-M.
    International Journal of Automation and Computing, 2009, 6 (1) : 97 - 102
  • [46] A Hybrid Genetic Algorithm for the Traveling Salesman Problem with Pickup and Delivery
    Fang-Geng Zhao1
    International Journal of Automation & Computing, 2009, (01) : 97 - 102
  • [47] An improved immune-genetic algorithm for the traveling salesman problem
    Lu, Jingui
    Fang, Ning
    Shao, Dinghong
    Liu, Congyan
    ICNC 2007: THIRD INTERNATIONAL CONFERENCE ON NATURAL COMPUTATION, VOL 4, PROCEEDINGS, 2007, : 297 - +
  • [48] Greedy Permuting Method for Genetic Algorithm on Traveling Salesman Problem
    Liu, Junjun
    Li, Wenzheng
    2018 8TH INTERNATIONAL CONFERENCE ON ELECTRONICS INFORMATION AND EMERGENCY COMMUNICATION (ICEIEC), 2018, : 47 - 51
  • [49] Traveling Salesman Problem of Optimization based on Genetic Algorithms
    Ellili, Walid
    Samet, Mounir
    Kachouri, Abdennaceur
    2017 INTERNATIONAL CONFERENCE ON SMART, MONITORED AND CONTROLLED CITIES (SM2C), 2017, : 123 - 127
  • [50] An improved memetic genetic algorithm based on a complex network as a solution to the traveling salesman problem
    Mohammadi, Hadi
    Mirzaie, Kamal
    Mollakhalili Meybodi, Mohammad Reza
    TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES, 2020, 28 (05) : 2910 - 2925
12345