オオバ カズヒサ   OBA, Kazuhisa
  大場 和久
健康科学部 福祉工学科
教授
発表年月日 2012/11
発表テーマ Solving Quadratic Assignment Problems by Differential Evolution
発表学会名 IEEE Japan Society for Fuzzy Theory and intelligent informatics
主催者 Japan Society for Fuzzy Theory and intelligent informatics (SOFT)
学会区分 国際学会
単独共同区分 共同
発表者・共同発表者 Jun-ichi Kushida, Kazuhisa Oba, Akira Hara and Tetsuyuki Takahama
概要 Differential evolution (DE) was introduced by Stone and Price in 1995 as a population-based stochastic search tech- nique for solving optimization problems in a continuous space. DE has been successfully applied to various real world numerical optimization problems. In recent years not only continuous real- valued function, the applications of DE on combinatorial opti- mization problems with discrete decision variables are reported. However, genetic operator in the standard DE can not directly applied to discrete space. In this paper, we propose a method to solve quadratic assignment problems (QAP) by DE. The QAP is a well-known combinatorial optimization problem with a wide variety of practical applications. It is NP-hard and is considered to be one of the most difficult problems. In the QAP, a candidate solution can represented a permutation of integer. The proposed method employs permutation representation for individuals in DE. Therefore, a individual vector is encoded directly as a permutation. In discrete space, to realize effcient solution search like standard DE which have continuous nature, we modify differential operator to handle permutation encoding. Additionally, in order to maintain diversity of population, re- start strategy and tabu list are introduced to proposed method instead of crossover operator. Finally, we show the experimental results using instances of QAPLIB and the efficacy of proposed method.
journal:SCIS-ISIS 2012