A New Framework with a Stability Theory for Multipoint-Type and Stochastic Meta-Heuristic Optimization Algorithms

Yuji KOGUMA; Eitaro AIYOSHI

doi:10.1587/transfun.E98.A.700

A New Framework with a Stability Theory for Multipoint-Type and Stochastic Meta-Heuristic Optimization Algorithms

Yuji KOGUMA, Eitaro AIYOSHI

Full Text Views

0

Share
Cite this

Summary :

In Recent years, a paradigm of optimization algorithms referred to as “meta-heuristics” have been gaining attention as a means of obtaining approximate solutions to optimization problems quickly without any special prior knowledge of the problems. Meta-heuristics are characterized by flexibility in implementation. In practical applications, we can make use of not only existing algorithms but also revised algorithms that reflect the prior knowledge of the problems. Most meta-heuristic algorithms lack mathematical grounds, however, and therefore generally require a process of trial and error for the algorithm design and its parameter adjustment. For one of the resolution of the problem, we propose an approach to design algorithms with mathematical grounds. The approach consists of first constructing a “framework” of which dynamic characteristics can be derived theoretically and then designing concrete algorithms within the framework. In this paper, we propose such a framework that employs two following basic strategies commonly used in existing meta-heuristic algorithms, namely, (1) multipoint searching, and (2) stochastic searching with pseudo-random numbers. In the framework, the update-formula of search point positions is given by a linear combination of normally distributed random numbers and a fixed input term. We also present a stability theory of the search point distribution for the proposed framework, using the variance of the search point positions as the index of stability. This theory can be applied to any algorithm that is designed within the proposed framework, and the results can be used to obtain a control rule for the search point distribution of each algorithm. We also verify the stability theory and the optimization capability of an algorithm based on the proposed framework by numerical simulation.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.2 pp.700-709

Publication Date: 2015/02/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E98.A.700

Type of Manuscript: PAPER

Category: Numerical Analysis and Optimization

Authors

Yuji KOGUMA
Keio University
Eitaro AIYOSHI
Keio University

Keyword

meta-heuristics, global optimization, stochastic optimization, normal distribution

Cite this

Copy

Yuji KOGUMA, Eitaro AIYOSHI, "A New Framework with a Stability Theory for Multipoint-Type and Stochastic Meta-Heuristic Optimization Algorithms" in IEICE TRANSACTIONS on Fundamentals, vol. E98-A, no. 2, pp. 700-709, February 2015, doi: 10.1587/transfun.E98.A.700.
Abstract: In Recent years, a paradigm of optimization algorithms referred to as “meta-heuristics” have been gaining attention as a means of obtaining approximate solutions to optimization problems quickly without any special prior knowledge of the problems. Meta-heuristics are characterized by flexibility in implementation. In practical applications, we can make use of not only existing algorithms but also revised algorithms that reflect the prior knowledge of the problems. Most meta-heuristic algorithms lack mathematical grounds, however, and therefore generally require a process of trial and error for the algorithm design and its parameter adjustment. For one of the resolution of the problem, we propose an approach to design algorithms with mathematical grounds. The approach consists of first constructing a “framework” of which dynamic characteristics can be derived theoretically and then designing concrete algorithms within the framework. In this paper, we propose such a framework that employs two following basic strategies commonly used in existing meta-heuristic algorithms, namely, (1) multipoint searching, and (2) stochastic searching with pseudo-random numbers. In the framework, the update-formula of search point positions is given by a linear combination of normally distributed random numbers and a fixed input term. We also present a stability theory of the search point distribution for the proposed framework, using the variance of the search point positions as the index of stability. This theory can be applied to any algorithm that is designed within the proposed framework, and the results can be used to obtain a control rule for the search point distribution of each algorithm. We also verify the stability theory and the optimization capability of an algorithm based on the proposed framework by numerical simulation.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.700/_p

Copy

@ARTICLE{e98-a_2_700,
author={Yuji KOGUMA, Eitaro AIYOSHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Framework with a Stability Theory for Multipoint-Type and Stochastic Meta-Heuristic Optimization Algorithms},
year={2015},
volume={E98-A},
number={2},
pages={700-709},
abstract={In Recent years, a paradigm of optimization algorithms referred to as “meta-heuristics” have been gaining attention as a means of obtaining approximate solutions to optimization problems quickly without any special prior knowledge of the problems. Meta-heuristics are characterized by flexibility in implementation. In practical applications, we can make use of not only existing algorithms but also revised algorithms that reflect the prior knowledge of the problems. Most meta-heuristic algorithms lack mathematical grounds, however, and therefore generally require a process of trial and error for the algorithm design and its parameter adjustment. For one of the resolution of the problem, we propose an approach to design algorithms with mathematical grounds. The approach consists of first constructing a “framework” of which dynamic characteristics can be derived theoretically and then designing concrete algorithms within the framework. In this paper, we propose such a framework that employs two following basic strategies commonly used in existing meta-heuristic algorithms, namely, (1) multipoint searching, and (2) stochastic searching with pseudo-random numbers. In the framework, the update-formula of search point positions is given by a linear combination of normally distributed random numbers and a fixed input term. We also present a stability theory of the search point distribution for the proposed framework, using the variance of the search point positions as the index of stability. This theory can be applied to any algorithm that is designed within the proposed framework, and the results can be used to obtain a control rule for the search point distribution of each algorithm. We also verify the stability theory and the optimization capability of an algorithm based on the proposed framework by numerical simulation.},
keywords={},
doi={10.1587/transfun.E98.A.700},
ISSN={1745-1337},
month={February},}

Copy

TY - JOUR
TI - A New Framework with a Stability Theory for Multipoint-Type and Stochastic Meta-Heuristic Optimization Algorithms
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 700
EP - 709
AU - Yuji KOGUMA
AU - Eitaro AIYOSHI
PY - 2015
DO - 10.1587/transfun.E98.A.700
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2015
AB - In Recent years, a paradigm of optimization algorithms referred to as “meta-heuristics” have been gaining attention as a means of obtaining approximate solutions to optimization problems quickly without any special prior knowledge of the problems. Meta-heuristics are characterized by flexibility in implementation. In practical applications, we can make use of not only existing algorithms but also revised algorithms that reflect the prior knowledge of the problems. Most meta-heuristic algorithms lack mathematical grounds, however, and therefore generally require a process of trial and error for the algorithm design and its parameter adjustment. For one of the resolution of the problem, we propose an approach to design algorithms with mathematical grounds. The approach consists of first constructing a “framework” of which dynamic characteristics can be derived theoretically and then designing concrete algorithms within the framework. In this paper, we propose such a framework that employs two following basic strategies commonly used in existing meta-heuristic algorithms, namely, (1) multipoint searching, and (2) stochastic searching with pseudo-random numbers. In the framework, the update-formula of search point positions is given by a linear combination of normally distributed random numbers and a fixed input term. We also present a stability theory of the search point distribution for the proposed framework, using the variance of the search point positions as the index of stability. This theory can be applied to any algorithm that is designed within the proposed framework, and the results can be used to obtain a control rule for the search point distribution of each algorithm. We also verify the stability theory and the optimization capability of an algorithm based on the proposed framework by numerical simulation.
ER -