Novel opposition-based sampling methods for efficiently solving challenging optimization problems
Date
2011-04-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In solving noise-free and noisy optimization problems, candidate initialization and sampling
play a key role, but are not deeply investigated. It is of interest to know if the entire
search space has the same quality for candidate-solutions during solving different type of
optimization problems. In this thesis, a comprehensive investigation is conducted in order
to clear those doubts, and to examine the effects of variant sampling methods on solving
challenging optimization problems, such as large-scale, noisy, and multi-modal problems.
As a result, the search space is segmented by using seven segmentation schemes, namely:
Center-Point, Center-Based, Modula-Opposite, Quasi-Opposite, Quasi-Reflection, Supper-
Opposite, and Opposite-Random. The introduced schemes are studied using Monte-Carlo
simulation, on various types of noise-free optimization problems, and ultimately ranked
based on their performance in terms of probability of closeness, average distance to unknown
solution, number of solutions found, and diversity. Based on the results of the
experiments, high-ranked schemes are selected and utilized on well-known metaheuristic
algorithms, as case studies. Two categories of case studies are targeted; one for a singlesolution-
based metaheuristic (S-metaheuristic) and another one for a population based
metaheuristic (P-metaheuristic). A high-ranked single-solution-based scheme is utilized
to accelerate Simulated Annealing (SA) algorithm, as a noise-free S-metaheuristic case
study. Similarly, for noise-free P-metaheuristic case study, an effective population-based
algorithm, Differential Evolution (DE), has been utilized. The experiments confirm that
the new algorithms outperform the parent algorithm (DE) on large-scale problems. In the
same direction, with regards to solving noisy problems more efficiently, a Shaking-based
sampling method is introduced, in which the original noise is tackled by adding an additional
noise into the search process. As a case study, the Shaking-based sampling is
utilized on the DE algorithm, from which two variant algorithms have been developed and
showed impressive performance in comparison to the classical DE, in tackling noisy largescale
problems. This thesis has created an opportunity for a comprehensive investigation
on search space segmentation schemes and proposed new sampling methods. The current
study has provided a guide to use appropriate sampling schemes for a given types of
problems such as noisy, large-scale and multi-modal optimization problems. Furthermore,
this thesis questions the effectiveness of uniform-random sampling method, which is widely
used in of S-Metaheuristic and P-Metaheuristic algorithms.
Description
Keywords
Opposition-based learning, Large-scale, Noisy, Sampling methods, Evolutionary algorithm