Browsing by Author "Dharm Raj Singh"

Now showing 1 - 8 of 8

A genetic method using hybrid crossover for solving travelling salesman problem
(Blue Eyes Intelligence Engineering and Sciences Publication, 2019) Anubhav Kumar Prasad; Dharm Raj Singh; Pankaj
This paper proposes a Genetic approach using Hybrid Crossover for Solving the Travelling Salesman Problem. Proposed hybrid method generates an initial population using Nearest Neighbor (NN) approach which is modified using “Sub-Path Mutation” (SPM) process. Modified population undergoes Distance Preserving Crossover (DPX) [2] and 2-opt Optimal mutation (2-opt) [1] to check for possible refinement. SPM searches position for the minimum distant city within a given path. This work is motivated by the algorithm developed by [3] who performed DPX and 2-opt mutation on the initial population generated using NN. For performance comparison, standard TSPLIB data is taken. The proposed hybrid method performances better in terms of % best error. It performs better than methods reported in [3-11]. © BEIESP.
A hybrid algorithm with modified Inver-over operator and genetic algorithm search for traveling salesman problem
(Springer Verlag, 2016) Dharm Raj Singh; Manoj Kumar Singh; Tarkeshwar Singh
In this article, we develop a novel hybrid approach to solve the traveling salesman problem (TSP). In this approach, we first initialize suboptimal solution using Nearest Neighbor (NN) tour construction method, followed modified Inver-over operator and then proposed crossover with 2-opt mutation applied to improve for optimal solution. We use 14 TSP data sets from TSPLIB to evaluate the performance of proposed hybrid method. The proposed hybrid method gives better results in terms of best and average error. In experimental results of the tests we show that the proposed hybrid method is superior to available algorithm in literature. © Springer Science+Business Media Singapore 2016.
A hybrid heuristic algorithm for the Euclidean traveling salesman problem
(Institute of Electrical and Electronics Engineers Inc., 2015) Dharm Raj Singh; Manoj Kumar Singh; Tarkeshwar Singh
In this paper, we propose hybrid algorithm, 2-opt optimal (2-opt) heuristic mutation with nearest neighbor (NN) tour construction, for solving traveling salesman problem (TSP). In this method, we first initialize suboptimal solution with the help of NN tour construction then DPX crossover is being used and after that 2-opt heuristic method is applied to refine solution for global optimality. Standard benchmark data from TSPLIB is used to evaluate the performance of proposed algorithm. The proposed algorithm gives better performance in term of best and average error. The proposed algorithm decreases the best error values in comparison to other methods with the ratio in between 19.13% and 90.55% and average error values between 32.16% and 86.10%. © 2015 IEEE.
An Efficient Hybrid Algorithm with Novel Inver-over Operator and Ant Colony Optimization for Traveling Salesman Problem
(Springer Science and Business Media Deutschland GmbH, 2024) Dharm Raj Singh; Manoj Kumar Singh; Sachchida Nand Chaurasia
In this research paper, we present a hybrid algorithm that merges the principles of Genetic Algorithm (GA) and Ant Colony Optimization (ACO). Our algorithm consists of two distinct stages. In the first stage, we employ Ant Colony Optimization to establish an initial population, and we utilize the proposed Inver-over (IO) heuristic to obtain suboptimal solutions for the Euclidean Traveling Salesman Problem (TSP). The proposed Inver-over operator is used to refine the solution obtained through ACO. Subsequently, this refined solution is incorporated into the Genetic Algorithm (GA) for the second stage. In the second stage of our algorithm, we apply GA with our proposed crossover operator and a 2-optimal heuristic to further refine the solution with the goal of achieving global optimality. To assess the effectiveness of our proposed algorithm, we rely on standard benchmark data from TSPLIB. The experimental results indicate that our hybrid algorithm outperforms recent methods and exhibits greater efficiency when compared to other reported methods. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Genetic algorithm for solving multiple traveling salesmen problem using a new crossover and population generation
(Instituto Politecnico Nacional, 2018) Dharm Raj Singh; Manoj Kumar Singh; Tarkeshwar Singh; Rajkishore Prasad
In this paper, we proposed a new crossover operator and a population initialization method for solving multiple traveling salesmen (MTSP) problem in genetic algorithm (GA) framework. The group theory based technique of intital population generation ensures the uniqueness of members in population, hence no redundancy in the search space and also remove the random initialization effect. The new crossover is based on the intuitive idea that the city in sub optimal / optimal tours occurs at same position. In this crossover the Hamming distance is preserved and there is very less chance to generate child same as members in the population, so diversity of the population is not much affected. For efficient representation of search space, we exploited the multi-chromosome representation technique to encode the search space of MTSP. We evaluate and compare the proposed technique with the methods using crossover TCX, ORX +A, CYX +A and PMX +A reported in [35] for two standard objective functions of the MTSP, namely, minimising total travel cost of m tours of the m salesman and minimising the longest tour cast travel by any one salesman. Experimental results show that the GA with proposed population initialization and crossover gives better result compared to all four methods for second objective, however, in very few cases slightly degraded result for first objective. © 2018 Instituto Politecnico Nacional. All rights reserved.
Genetic Algorithm Incorporating Group Theory for Solving the General Travelling Salesman Problem
(Springer, 2024) Dharm Raj Singh; Manoj Kumar Singh; Sachchida Nand Chaurasia; Anshul Verma
This paper presents a novel Genetic Algorithm (GA) designed to tackle the Travelling Salesman Problem (TSP) with remarkable efficacy. It integrates group theory into population initialization, employs Partially Matched Crossover (PMX), and adopts a 2-optimal mutation strategy. The pioneering approach harnesses algebraic structures in constructing group tours, utilizing integer addition modulo n within Zn to generate varied initial solutions. The initial population enhances diversity by ensuring that each individual/tour shares an identical node order but begins from a distinct starting node. This distinctiveness in starting nodes facilitates thorough exploration of the entire search space. The Partially mapped Crossover operator, grounded in order principles, is a crucial mechanism for transferring sequence and value characteristics from parental to offspring tour. This operation effectively guides a strong local search. Subsequently, applying a 2-opt optimal mutation seeks to refine the solution further, targeting a more globally optimal outcome. The effectiveness of this methodology is evaluated through experiments with TSP instances sourced from the widely recognized TSPLIB. Furthermore, the superiority of our proposed approach is demonstrated through comparisons with state-of-the-art methods developed within hybrid frameworks. Statistical analyses underscore the significance and effectiveness of the proposed methodology. © The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. 2024.
Hybrid Heuristic for Solving the Euclidean Travelling Salesman Problem
(Springer, 2024) Dharm Raj Singh; Manoj Kumar Singh; Sachchida Nand Chaurasia; Pradeepika Verma
This study introduces a hybrid methodology that integrates the ant colony optimization (ACO) with genetic algorithm (GA) techniques. ACO is employed first to create an initial population and to derive a sub-optimal solution for the TSP using a newly designed inver-over (IO) operator. The Proposed IO operator is utilized to improve the solution derived from the ACO. This refined solution is then employed in the GA, where a genetic operator is applied alongside other randomly selected members from the initial population during the second phase. GA is used with the proposed crossover operator and the 2-opt heuristic in this phase to achieve optimal solution refinement towards a global optimum. Our evaluation of the algorithm’s efficacy uses benchmark datasets from TSPLIB. The proposed approach gives superior solution quality, both the average and the best solution metrics, demonstrating enhanced performance with a lower percentage of best error and percentage of average error. Experimental results indicate that the hybrid approach outperforms the efficiency of other state-of-the-art techniques. © The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. 2024.
Multiple traveling salesman problem using novel crossover and group theory
(Institute of Electrical and Electronics Engineers Inc., 2017) Dharm Raj Singh; Manoj Kumar Singh; Tarkeshwar Singh
This paper propose a new technique which uses novel crossover with multi chromosome representation using group theory for tour construction for solving the multiple traveling salesmen problem (MTSP) using a genetic algorithm (GA) for near-optimal solutions. In the proposed algorithm, we use group tour construction method to get population having rich diversity. In group tour construction method each individual/initial tour is distinct provided that population size is less than the total number of cities. We also use multi chromosome representation technique, which minimizes the search space. We evaluated and compare the proposed technique with four different crossover methods for two MTSP objective functions, namely, total travel of the cost of m tours of the m salesman and longest tour cost travel by any one salesman. In this MTSP, we minimize these objective functions. Computational results obtained from proposed crossover with group tour construction is better than T CX, ORX+A, CYX+A, PMX + A crossover based method. © 2017 IEEE.