Solving NP-Complete Problems Using Genetic Algorithms

被引：10
作者：
Arabi, Bander Hassan [1 ]
机构：
[1] King Abdulaziz Univ, Dept Res & Dev, Distance Learning, POB 80254, Jeddah, Saudi Arabia
来源：
2016 UKSIM-AMSS 18TH INTERNATIONAL CONFERENCE ON COMPUTER MODELLING AND SIMULATION (UKSIM) | 2016年
关键词：
component; NP-Complet Problem; Genetic Algorithm; Traveling Salesman Problem;
D O I：
10.1109/UKSim.2016.65
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
Genetic Algorithms are designed to find the accuracy of approximated solutions in order to perform as effectively as possible. This paper present a new way for genetic algorithm to solve NP-Complete problem. We study genetic algorithm to find an optimal solution for instances of the Traveling Salesman Problem. To overcome this solution, we have to see what is the shortest path that satisfies all of these conditions? We review the paradigms of design of genetic algorithm and demonstrate how they can be applied for the Traveling Salesman Problem. The experiments are presented in which the performance of genetic algorithm is compared to that of Exhaustive Searches.
引用
收藏
页码：43 / 48
页数：6
相关论文
共 50 条
  • [41] Solving Multicommodity Capacitated Network Design Problems Using Multiobjective Evolutionary Algorithms
    Kleeman, Mark P.
    Seibert, Benjamin A.
    Lamont, Gary B.
    Hopkinson, Kenneth M.
    Graham, Scott R.
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2012, 16 (04) : 449 - 471
  • [42] On Designing Genetic Algorithms for Solving Small- and Medium-Scale Traveling Salesman Problems
    Liu, Chun
    Kroll, Andreas
    SWARM AND EVOLUTIONARY COMPUTATION, 2012, 7269 : 283 - 291
  • [43] A Comparison of Algorithms for Solving Multicomponent Optimization Problems
    Vieira, D. K. S.
    Mendes, M. H. S.
    IEEE LATIN AMERICA TRANSACTIONS, 2017, 15 (08) : 1474 - 1479
  • [44] Intelligent Algorithms for solving multiobjective optimization problems
    Yi Hong-Xia
    Xiao Liu
    Liu Pu-Kun
    2008 4TH INTERNATIONAL CONFERENCE ON WIRELESS COMMUNICATIONS, NETWORKING AND MOBILE COMPUTING, VOLS 1-31, 2008, : 13101 - 13105
  • [45] Algorithms for solving assembly sequence planning problems
    Su, Yingying
    Mao, Haixu
    Tang, Xianzhao
    NEURAL COMPUTING & APPLICATIONS, 2021, 33 (02) : 525 - 534
  • [46] Heterogeneous selection genetic algorithms for traveling salesman problems
    Tsai, HK
    Yang, JM
    Tsai, YF
    Kao, CY
    ENGINEERING OPTIMIZATION, 2003, 35 (03) : 297 - 311
  • [47] Solving traveling salesman problems using generalized chromosome genetic algorithm
    Yang, Jinhui
    Wu, Chunguo
    Lee, Heow Pueh
    Liang, Yanchun
    PROGRESS IN NATURAL SCIENCE-MATERIALS INTERNATIONAL, 2008, 18 (07) : 887 - 892
  • [48] Solving traveling salesman problems using generalized chromosome genetic algorithm
    Heow Pueh Lee
    ProgressinNaturalScience, 2008, (07) : 887 - 892
  • [49] Using a repair genetic algorithm for solving constrained nonlinear optimization problems
    Bidabadi, Narges
    JOURNAL OF INFORMATION & OPTIMIZATION SCIENCES, 2018, 39 (08) : 1647 - 1663
  • [50] Solving the economic lot scheduling problem with deteriorating items using genetic algorithms
    Yao, MJ
    Huang, JX
    JOURNAL OF FOOD ENGINEERING, 2005, 70 (03) : 309 - 322
12345