Browsing by Author "Arshad, Shakeel"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    ItemMetadata only
    A hybrid genetic algorithm and inver over approach for the travelling salesman problem.
    (IEEE, 2010) Arshad, Shakeel; Yang, Shengxiang
    This paper proposes a two-phase hybrid approach for the travelling salesman problem (TSP). The first phase is based on a sequence based genetic algorithm (SBGA) with an embedded local search scheme. Within the SBGA, a memory is introduced to store good sequences (sub-tours) extracted from previous good solutions and the stored sequences are used to guide the generation of offspring via local search during the evolution of the population. Additionally, we also apply some techniques to adapt the key parameters based on whether the best individual of the population improves or not and maintain the diversity. After SBGA finishes, the hybrid approach enters the second phase, where the inver over (IO) operator, which is a state-of-the-art algorithm for the TSP, is used to further improve the solution quality of the population. Experiments are carried out to investigate the performance of the proposed hybrid approach in comparison with several relevant algorithms on a set of benchmark TSP instances. The experimental results show that the proposed hybrid approach is efficient in finding good quality solutions for the test TSPs.
  • No Thumbnail Available
    ItemMetadata only
    A sequence based genetic algorithm with local search for the travelling salesman problem.
    (University of Nottingham, 2009) Arshad, Shakeel; Yang, Shengxiang; Li, Changhe
    The standard Genetic Algorithm often suffers from slow convergence for solving combinatorial optimization problems. In this study, we present a sequence based genetic algorithm (SBGA) for the symmetric travelling salesman problem (TSP). In our proposed method, a set of sequences are extracted from the best individuals, which are used to guide thesearch of SBGA. Additionally, some procedures are applied to maintain the diversity by breaking the selected sequences into sub tours if the best individual of the population does not improve. SBGA is compared with the inver-over operator, a state-of-the-art algorithm for theTSP, on a set of benchmark TSPs. Experimental results show that the convergence speed of SBGA is very promisingand much faster than that of the inver-over algorithm and that SBGA achieves a similar solution quality on all test TSPs.