A genetic algorithm for TSP with backhauls based on conventional heuristics

Download

index.pdf

Date

2007

Author

Önder, İlter

Metadata

Show full item record

Item Usage Stats

245
views

62
downloads

A genetic algorithm using conventional heuristics as operators is considered in this study for the traveling salesman problem with backhauls (TSPB). Properties of a crossover operator (Nearest Neighbor Crossover, NNX) based on the nearest neighbor heuristic and the idea of using more than two parents are investigated in a series of experiments. Different parent selection and replacement strategies and generation of multiple children are tried as well. Conventional improvement heuristics are also used as mutation operators. It has been observed that 2-edge exchange and node insertion heuristics work well with NNX using only two parents. The best settings among different alternatives experimented are applied on traveling salesman problem with backhauls (TSPB). TSPB is a problem in which there are two groups of customers. The aim is to minimize the distance traveled visiting all the cities, where the second group can be visited only after all cities in the first group are already visited. The approach we propose shows very good performance on randomly generated TSPB instances.

Subject Keywords

Information Technology .

URI

http://etd.lib.metu.edu.tr/upload/12608726/index.pdf
https://hdl.handle.net/11511/17008

Collections

Graduate School of Informatics, Thesis

Suggestions

OpenMETU
Core

A genetic-based intelligent intrusion detection system Özbey, Halil; Şen, Tayyar; Department of Industrial Engineering (2005) In this study we address the problem of detecting new types of intrusions to computer systems which cannot be handled by widely implemented knowledge-based mechanisms. The solutions offered by behavior-based prototypes either suffer low accuracy and low completeness or require use data eplaining abnormal behavior which actually is not available. Our aim is to develop an algorithm which can produce a satisfactory model of the target system̕s behavior in the absence of negative data. First, we design and deve...
A Modified Parallel Learning Vector Quantization Algorithm for Real-Time Hardware Applications Alkim, Erdem; AKLEYLEK, SEDAT; KILIÇ, ERDAL (2017-10-01) In this study a modified learning vector quantization (LVQ) algorithm is proposed. For this purpose, relevance LVQ (RLVQ) algorithm is effciently combined with a reinforcement mechanism. In this mechanism, it is shown that the proposed algorithm is not affected constantly by both relevance-irrelevance input dimensions and the winning of the same neuron. Hardware design of the proposed scheme is also given to illustrate the performance of the algorithm. The proposed algorithm is compared to the corresponding...
An information theoretic approach to select alternate subsets of predictors for data-driven hydrological models TAORMİNA, RİCCARDO; GALELLİ, STEFANO; Karakaya, Gülşah; Ahipasaoglu, S. D. (Elsevier BV, 2016-11-01) This work investigates the uncertainty associated to the presence of multiple subsets of predictors yielding data-driven models with the same, or similar, predictive accuracy. To handle this uncertainty effectively, we introduce a novel input variable selection algorithm, called Wrapper for Quasi Equally Informative Subset Selection (W-QEISS), specifically conceived to identify all alternate subsets of predictors in a given dataset. The search process is based on a four-objective optimization problem that m...
A Meta-Heuristic Paradigm for solving the Forward Kinematics of 6-6 General Parallel Manipulator Chandra, Rohitash; Frean, Marcus; Rolland, Luc (2009-12-18) The forward kinematics of the general Gough platform, namely the 6-6 parallel manipulator is solved using hybrid meta-heuristic techniques in which the simulated annealing algorithm replaces the mutation operator in a genetic algorithm. The results are compared with the standard simulated annealing and genetic algorithm. It shows that the standard simulated annealing algorithm outperforms standard genetic algorithm in terms of computation time and overall accuracy of the solution on this problem. However, t...
A GENERALIZED CORRELATED RANDOM WALK APPROXIMATION TO FRACTIONAL BROWNIAN MOTION Vardar Acar, Ceren (null; 2018-04-30) In this study, we mainly propose an algorithm to generate correlated random walk converging to fractional Brownian motion, with Hurst parameter, H∈ [1/2,1]. The increments of this random walk are simulated from Bernoulli distribution with proportion p, whose density is constructed using the link between correlation of multivariate Gaussian random variables and correlation of their dichotomized binary variables. We prove that the normalized sum of trajectories of this proposed random walk yields a Gaussian p...

Citation Formats

İ. Önder, “A genetic algorithm for TSP with backhauls based on conventional heuristics,” M.S. - Master of Science, Middle East Technical University, 2007.