On the convergence of chemical reaction optimization for combinatorial optimization

Yun Sang Albert LAM, Victor O.K. Li, Jin Xu

Research output: Contribution to journalArticlepeer-review

31 Citations (Scopus)

Abstract

A novel general-purpose optimization method, chemical reaction optimization (CRO), is a population-based metaheuristic inspired by the phenomenon of interactions between molecules in a chemical reaction process. CRO has demonstrated its competitive edge over existing methods in solving many real-world problems. However, all studies concerning CRO have been empirical in nature and no theoretical analysis has been conducted to study its convergence properties. In this paper, we present some convergence results for several generic versions of CRO, each of which adopts different combinations of elementary reactions. We investigate the limiting behavior of CRO. By modeling CRO as a finite absorbing Markov chain, we show that CRO converges to a global optimum solution with a probability arbitrarily close to one when time tends to infinity. Our results also show that the convergence of CRO is determined by both the elementary reactions and the total energy of the system. Moreover, we also study and discuss the finite time behavior of CRO.

Original languageEnglish
Article number6355648
Pages (from-to)605-620
Number of pages16
JournalIEEE Transactions on Evolutionary Computation
Volume17
Issue number5
DOIs
Publication statusPublished - 2013

Scopus Subject Areas

  • Software
  • Theoretical Computer Science
  • Computational Theory and Mathematics

User-Defined Keywords

  • Chemical reaction optimization (CRO)
  • Convergence
  • Convergence rate
  • Finite absorbing Markov chain
  • First hitting time

Fingerprint

Dive into the research topics of 'On the convergence of chemical reaction optimization for combinatorial optimization'. Together they form a unique fingerprint.

Cite this