多目的最適化問題と再配置操作つきPareto Simulated Annealing
久保谷 寛行 (9951038)
多目的組み合わせ最適化問題として定式化される問題は，現実世界に多く存在する．
そのような問題を取り扱う場合に問題となるのは，意思決定者の多様な要求にいかに応じるかという事である．
従来多目的組み合わせ最適化問題は，最初に意思決定者の嗜好を定量化した上で，対象とする問題に対し特別な知識を持った専門家による発見的手法を適用することで，近似的に解かれてきた．
しかしながら，意思決定者の立場に立つと，多様な最適解を眺めてその中から最終的な最適解を選出するという過程の方が，スムーズに嗜好を引き出すことが出来る場合が多い．
従来の厳密解法でも，パラメータを変えて繰り返し問題を解いていくことで，多様な解を生成することはできる．
しかしながら，組み合わせ最適化問題は，その規模が大きくなると単目的の場合ですら組み合わせ爆発が起こる．
それ故，実用的な時間内に良質な解を得ることができる方法として，多目的シミュレーテッドアニーリング（多目的SA）を用いる方法がある．
しかしながら，多目的SAはあくまで近似解法なので，真の最適解にいかに接近した解を得られるかが重要となる．
以上から，多目的最適化問題を解く上で多目的SAに要求されるのは，「解品質の向上」と「解の広がりの向上」であると言える．
ここで，解の広がりの向上とは，一回の多目的SAの探索でより多様な最適解を得ることである．
本研究でも，以上の二つを目標とし研究を行った．
(1)最初に，解品質の向上を実現するために，受理確率関数に注目した．
多目的SAに適用可能な受理確率関数は，すでに幾つか提案されている．
しかしながら，従来の受理確率関数は，SAの探索能力に与える影響に関する十分な議論が行われていなかった．
そこで本研究では，パラメータ付き受理確率関数を新たに導入し，受理確率関数の関数形がSAにより得られる解の品質にどのような影響を与えるかを調べ，より良質の解を得られる受理確率関数を明らかにした．
(2)次に，解の広がりを実現するために，多目的SAの拡張の一例であるPareto Simulated Annealing (PSA)に注目した．
PSAは，従来一つの探索点により行われていたSAの探索を，複数の探索点を利用する多点探索とし，さらにそれらの探索点に対し，互いに離れていくような重み変更操作を加えたアルゴリズムである．
これにより，PSAは従来の多目的SAに比べて，より広範囲に渡る解を見つけることができる．
しかしながら，本発表で指摘する様に，PSAでは，多目的SAに要求される上記の二条件が両立されないという問題がある．
そこで，本研究では，このトレードオフの解決法として，PSAの探索の途上で探索点の再配置を行う再配置操作付きPSAを提案する．
これにより，解品質を高く維持した上で，広範囲に渡る最適解の探索を可能とした．
本発表では，(1)については簡単に考察のみを示し，主に(2)に重点をおいて説明を行う．