A study of chemical reaction optimization

A study of chemical reaction optimization

徐进(Jin Xu)

香港大學/Doctor of Philosophy/Electrical and Electronic Engineering/博士(2012年)

並列摘要

Complex optimization problems are prevalent in various fields of science and

engineering. However, many of them belong to a category of problems called NP-

hard (nondeterministic polynomial-time hard). On the other hand, due to the

powerful capability in solving a myriad of complex optimization problems, metaheuristic

approaches have attracted great attention in recent decades. Chemical

Reaction Optimization (CRO) is a recently developed metaheuristic mimicking

the interactions of molecules in a chemical reaction. With the flexible structure

and excellent characteristics, CRO can explore the solution space efficiently to

identify the optimal or near optimal solution(s) within an acceptable time. Our

research not only designs different versions of CRO and applies them to tackle

various NP-hard optimization problems, but also investigates theoretical aspects

of CRO in terms of convergence and finite time behavior.

We first focus on the problem of task scheduling in grid computing, which

involves seeking the most efficient strategy for allocating tasks to resources. In

addition to Makespan and Flowtime, we also take reliability of resource into

account, and task scheduling is formulated as an optimization problem with three

objective functions. Then, four different kinds of CRO are designed to solve this

problem. Simulation results show that the CRO methods generally perform better

than existing methods and performance improvement is especially significant in

large-scale applications.

Secondly, we study stock portfolio selection, which pertains to deciding how to

allocate investments to a number of stocks. Here we adopt the classical Markowitz

mean-variance model and consider an additional cardinality constraint. Thus,

the stock portfolio optimization becomes a mixed-integer quadratic programming

problem. To solve it, we propose a new version of CRO named Super Molecule-based

CRO (S-CRO). Computational experiments suggest that S-CRO is superior

to canonical CRO in solving this problem.

Thirdly, we apply CRO to the short adjacent repeats identification problem

(SARIP), which involves detecting the short adjacent repeats shared by multiple

DNA sequences. After proving that SARIP is NP-hard, we test CRO with both

synthetic and real data, and compare its performance with BASARD, which is

the previous best algorithm for this problem. Simulation results show that CRO

performs much better than BASARD in terms of computational time and finding

the optimal solution.

We also propose a parallel version of CRO (named PCRO) with a synchronous

communication scheme. To test its efficiency, we employ PCRO to solve the

Quadratic Assignment Problem (QAP), which is a classical combinatorial optimization

problem. Simulation results show that compared with canonical sequential

CRO, PCRO can reduce the computational time as well as improve the

quality of the solution for instances of QAP with large sizes.

Finally, we perform theoretical analysis on the convergence and finite time

behavior of CRO for combinatorial optimization problems. We explore CRO

convergence from two aspects, namely, the elementary reactions and the total

system energy. Furthermore, we also investigate the finite time behavior of CRO

in respect of convergence rate and first hitting time.

並列關鍵字

Chemical reactions - Mathematical models.