NeuroGenetic approach for combinatorial optimization: an exploratory analysis

Given the NP-Hard nature of many optimization problems, it is often impractical to obtain optimal solutions to large-scale problems in reasonable computing time. For this reason, heuristic and metaheuristic search approaches are used to obtain good solutions fast. However, these techniques often str...

Full description

Saved in:
Bibliographic Details
Published in:Annals of operations research 2010-02, Vol.174 (1), p.185-199
Main Authors: Agarwal, Anurag, Colak, Selcuk, Deane, Jason
Format: Article
Language:English
Subjects:
Algorithms
Analysis
Business and Management
Chromosomes
Combinatorics
Electromagnetism
Genetic algorithms
Methods
Neighborhoods
Neural networks
Operations management
Operations research
Operations Research/Decision Theory
Optimization
Scheduling
Studies
Theory of Computation
Traveling salesman problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given the NP-Hard nature of many optimization problems, it is often impractical to obtain optimal solutions to large-scale problems in reasonable computing time. For this reason, heuristic and metaheuristic search approaches are used to obtain good solutions fast. However, these techniques often struggle to develop a good balance between local and global search. In this paper we propose a hybrid metaheuristic approach which we call the NeuroGenetic approach to search for good solutions for these large scale optimization problems by at least partially overcoming this challenge. The proposed NeuroGenetic approach combines the Augmented Neural Network (AugNN) and the Genetic Algorithm (GA) search approaches by interleaving the two. We chose these two approaches to hybridize, as they offer complementary advantages and disadvantages; GAs are very good at searching globally, while AugNNs are more proficient at searching locally. The proposed hybrid strategy capitalizes on the strong points of each approach while avoiding their shortcomings. In the paper we discuss the issues associated with the feasibility of hybridizing these two approaches and propose an interleaving algorithm. We also provide empirical evidence demonstrating the effectiveness of the proposed approach.
ISSN:0254-5330
1572-9338
DOI:10.1007/s10479-009-0562-z