Discrete optimization via gradient-based adaptive stochastic search methods

Xi Chen, Enlu Zhou and Jiaqiao Hu

IISE Transactions, 2018, vol. 50, issue 9, 789-805

Abstract: Gradient-based Adaptive Stochastic Search (GASS) is a new stochastic search optimization algorithm that has recently been proposed. It iteratively searches promising candidate solutions through a population of samples generated from a parameterized probabilistic model on the solution space, and updates the parameter of the probabilistic model based on a direct gradient method. Under the framework of GASS, we propose two discrete optimization algorithms: discrete Gradient-based Adaptive Stochastic Search (discrete-GASS) and annealing Gradient-based Adaptive Stochastic Search (annealing-GASS). In discrete-GASS, we transform the discrete optimization problem into a continuous optimization problem on the parameter space of a family of independent discrete distributions, and apply a gradient-based method to find the optimal parameter, such that the corresponding distribution has the best capability to generate optimal solution(s) to the original discrete problem. In annealing-GASS, we use a Boltzmann distribution as the parameterized probabilistic model, and propose a gradient-based temperature schedule that changes adaptively with respect to the current performance of the algorithm. We show convergence of both discrete-GASS and annealing-GASS under appropriate conditions. Numerical results on several benchmark optimization problems and the traveling salesman problem indicate that both algorithms perform competitively against a number of other algorithms, including model reference adaptive search, the cross-entropy method, and multi-start simulated annealing with different temperature schedules.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2018.1448489 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:50:y:2018:i:9:p:789-805

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2018.1448489

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().