Analyzing Influence of Relationship between Characteristic of Solutions and Their Evaluation Time in Asynchronous Evolutionary Algorithm

• Harada Tomohiro

  Depertment of Human and Computer Intelligence, College of Information Science and Engineering, Ritsumeikan University

Bibliographic Information

Other Title

• 非同期進化的アルゴリズムにおける解の性質と評価時間の関係性による影響の分析

Abstract

This paper presents an analysis of an optimization process in asynchronous evolutionary algorithms from the viewpoint of influence of the relationship between characteristic of solutions and their evaluation time. An asynchronous evolutionary algorithm continuously evolves solutions without waiting for evaluations of other solutions, and consequently an asynchronous evolutionary algorithm is effective in the situation where the evaluation times of solutions differ from each other. This paper focuses on optimization problems in which the evaluation time of solutions depends on their characteristics. In particular, this paper considers two relationships; (a) the evaluation time relates to the evaluation value of solutions; and (b) the evaluation time relates to design variables of solutions. In each relationship, four correlation settings are defined; (1) uniform evaluation time setting where all solutions have the same evaluation time; (2) no-correlation setting where the evaluation time is not uniform but does not depend on characteristic of solutions; (3) positive correlation setting where the evaluation time increases by getting close to the optimal solution; and (4) negative correlation setting where the evaluation time increases by getting far awary from the optimmal solution. Experiments on the defined correlation settings are conducted on three conventional asynchronous evolutionary algorithms and four benchmark problems. The analytical results reveal the following implications; (1) in the case where the evaluation time relates to the evaluation value of solutions, when a lot of local optima exists in the search space such as multi-modal problems, a number of evaluations to escape from local optima is needed and the evaluation time of solutions close to local optima influences the computational time of search process. On the other hand, when it is hard to converge to the optimal solution, the evaluation time of solutions close to the optimal solution influences the computation time of search process; and (2) in the case where the evaluation time relates to the design variable of solutions, when the evaluation time of solutions decreases by getting close to the optimal solution, the computation time decreases because the search direction is biased toward the optimal solution.

Journal

• Transaction of the Japanese Society for Evolutionary Computation

  Transaction of the Japanese Society for Evolutionary Computation 7 (2), 46-55, 2016

  The Japanese Society for Evolutionary Computation

Keywords

• asynchronous evolutionary algorithm
• expensive fitness evaluation
• behavioral analyses

Details

• CRID: 1390001205365833728
• NII Article ID: 130005277274
• DOI: 10.11394/tjpnsec.7.46
• ISSN: 21857385
• Text Lang: ja
• Data Source:
  • JaLC
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed