File Download
Supplementary
-
Citations:
- Appears in Collections:
postgraduate thesis: A study of chemical reaction optimization
Title | A study of chemical reaction optimization |
---|---|
Authors | |
Issue Date | 2012 |
Publisher | The University of Hong Kong (Pokfulam, Hong Kong) |
Citation | Xu, J. [徐进]. (2012). A study of chemical reaction optimization. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4819924 |
Abstract | 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. |
Degree | Doctor of Philosophy |
Subject | Chemical reactions - Mathematical models. |
Dept/Program | Electrical and Electronic Engineering |
Persistent Identifier | http://hdl.handle.net/10722/188725 |
HKU Library Item ID | b4819924 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Xu, Jin | - |
dc.contributor.author | 徐进 | - |
dc.date.accessioned | 2013-09-05T07:53:05Z | - |
dc.date.available | 2013-09-05T07:53:05Z | - |
dc.date.issued | 2012 | - |
dc.identifier.citation | Xu, J. [徐进]. (2012). A study of chemical reaction optimization. (Thesis). University of Hong Kong, Pokfulam, Hong Kong SAR. Retrieved from http://dx.doi.org/10.5353/th_b4819924 | - |
dc.identifier.uri | http://hdl.handle.net/10722/188725 | - |
dc.description.abstract | 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. | - |
dc.language | eng | - |
dc.publisher | The University of Hong Kong (Pokfulam, Hong Kong) | - |
dc.relation.ispartof | HKU Theses Online (HKUTO) | - |
dc.rights | The author retains all proprietary rights, (such as patent rights) and the right to use in future works. | - |
dc.rights | This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License. | - |
dc.source.uri | http://hub.hku.hk/bib/B48199242 | - |
dc.subject.lcsh | Chemical reactions - Mathematical models. | - |
dc.title | A study of chemical reaction optimization | - |
dc.type | PG_Thesis | - |
dc.identifier.hkul | b4819924 | - |
dc.description.thesisname | Doctor of Philosophy | - |
dc.description.thesislevel | Doctoral | - |
dc.description.thesisdiscipline | Electrical and Electronic Engineering | - |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.5353/th_b4819924 | - |
dc.date.hkucongregation | 2012 | - |
dc.identifier.mmsid | 991033760769703414 | - |