| Journal: | Computación y sistemas |
| Database: | |
| System number: | 000560141 |
| ISSN: | 1405-5546 |
| Authors: | Singh, Dharm Raj1 Singh, Manoj Kumar1 Singh, Tarkeshwar2 Prasad, Rajkishore3 |
| Institutions: | 1Banaras Hindu University, Centre for Interdisciplinary Mathematical Sciences, Uttar Pradesh. India 2Birla Institute Of Technology And Science, Department of Mathematics, Rajasthan. India 3Bihar National College Patna, Patna, Bihar. India |
| Year: | 2018 |
| Season: | Abr-Jun |
| Volumen: | 22 |
| Number: | 2 |
| Pages: | 491-503 |
| Country: | México |
| Language: | Inglés |
| Document type: | Artículo |
| English abstract | 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. |
| Disciplines: | Ciencias de la computación |
| Keyword: | Inteligencia artificial, Inteligencia artificial |
| Keyword: | Genetic algorithm, Multiple traveling salesman problem, Group theory, Crossover operator, 2-opt mutation, Artificial intelligence |
| Full text: | Texto completo (Ver HTML) Texto completo (Ver PDF) |
