A Heuristic Design Information Sharing Framework for Hard Discrete Optimization Problems
Abstract
This project studied and developed simultaneous generalized hill climbing (SGHC) algorithms as an algorithmic framework for information sharing in discrete optimization problems. This framework has been used to gain new insights into neighborhood structure designs that allow different neighborhood functions to share information when using the same heuristic applied to the same problem. The results reported from this project introduce the SGHC algorithm framework for information sharing across sets of related discrete optimization problems, provide guidelines on how to use and to design neighborhood functions that results in effective performance of local search algorithms, and describe how tabu search can be effectively used to improve the performance of generalized hill climbing algorithms. Extensive computationally results are reported on a large variety of test bed, large-scale, real-world discrete optimization problems. The primary application for this research were a military combat search and rescue problems, where several possible search and rescue strategies must be considered to determine the optimal strategy, and a homeland security aviation security baggage screening problems, where several different baggage screening strategies at a set of airports must be considered to determine the optimal strategy for the entire system. Both these problems are intractable due, in part, to the exponentially large number of possible solutions that exist and must be evaluated to identify those that are optimal.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 2007
- Accession Number
- ADA467897
Entities
People
- Sheldon H. Jacobson
Organizations
- University of Illinois Urbana–Champaign