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 条
  • [1] Combining Approximation Algorithm with Genetic Algorithm at the Initial Population for NP-complete Problem
    Razip, Hajar
    Zakaria, M. Nordin
    PROCEEDINGS OF THE 2017 IEEE 15TH STUDENT CONFERENCE ON RESEARCH AND DEVELOPMENT (SCORED), 2017, : 98 - 103
  • [2] An application of P-system: A new algorithm for NP-complete optimization problems
    Nishida, TY
    8TH WORLD MULTI-CONFERENCE ON SYSTEMICS, CYBERNETICS AND INFORMATICS, VOL V, PROCEEDINGS: COMPUTER SCIENCE AND ENGINEERING, 2004, : 109 - 112
  • [3] Analysis of the suitability of using blind crossover operators in genetic algorithms for solving routing problems
    Osaba, Eneko
    Carballedo, Roberto
    Diaz, Fernando
    Perallos, Asier
    2013 IEEE 8TH INTERNATIONAL SYMPOSIUM ON APPLIED COMPUTATIONAL INTELLIGENCE AND INFORMATICS (SACI 2013), 2013, : 17 - 22
  • [4] A new approach for solving linear bilevel problems using genetic algorithms
    Calvete, Herminia I.
    Gale, Carmen
    Mateo, Pedro M.
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 188 (01) : 14 - 28
  • [5] Solving transportation problems with concave cost functions using genetic algorithms
    Pasa, Tatiana
    COMPUTER SCIENCE JOURNAL OF MOLDOVA, 2020, 28 (02) : 140 - 151
  • [6] Solving traveling salesman problems by genetic algorithms
    LEE Heow Pueh
    LIM Siak Piang
    LEE Kwok Hong
    Progress in Natural Science, 2003, (02) : 57 - 63
  • [7] Solving traveling salesman problems by genetic algorithms
    Liang, YC
    Ge, HW
    Zhou, CG
    Lee, HP
    Lin, WZ
    Lim, SP
    Lee, KH
    PROGRESS IN NATURAL SCIENCE-MATERIALS INTERNATIONAL, 2003, 13 (02) : 135 - 141
  • [8] The Complete Subtour Order Crossover in Genetic Algorithms for Traveling Salesman Problem Solving
    Toathom, Thanan
    Champrasert, Paskorn
    2022 37TH INTERNATIONAL TECHNICAL CONFERENCE ON CIRCUITS/SYSTEMS, COMPUTERS AND COMMUNICATIONS (ITC-CSCC 2022), 2022, : 904 - 907
  • [9] On the influence of using initialization functions on genetic algorithms solving combinatorial optimization problems: a first study on the TSP
    Osaba, E.
    Carballedo, R.
    Diaz, F.
    Onieva, E.
    Lopez, P.
    Perallos, A.
    2014 IEEE CONFERENCE ON EVOLVING AND ADAPTIVE INTELLIGENT SYSTEMS (EAIS), 2014,
  • [10] Solving constrained traveling salesman problems by genetic algorithms
    WU Chunguo 1
    Key Laboratory for Symbol Computation and Knowledge Engineering
    2. Institute of High Performance Computing
    Progress in Natural Science, 2004, (07) : 79 - 85
12345