雑記

日々の記録になります.

【最適化】SCE-UA法

SCE-UA法について

SCE-UA法(Shuffled Complex Evolution Method developed at the University of Arizona)は,シンプレックス法,ランダム探索,遺伝的アルゴリズムに類似した競争進化,集団混合の概念を組み合わせたパラメータの大域的探索手法である(Duan et al., 1992).以下にSCE-UA法のアルゴリズムを示す(杉原ら, 2011).

f:id:okome29taberu:20200809221811p:plain
SCE-UA法のアルゴリズム(杉原ら, 2011)
f:id:okome29taberu:20200809221814p:plain
SCE-UA法内のCCE法のアルゴリズム(杉原ら, 2011)

数値実験

SCE-UA法でのパラメータ探索において設定の必要な値は,探索するパラメータの数n,集団の個数p,各集団における個体(点)の数m,親個体の数q,反復回数α,βである.本稿では,nとpについては藤井(2011)と同様にn=10,p=10とした.ほかの値についてDuan et al. (1992) は,m=2n+1,q=n+1,α=1,β=2n+1を推奨している.この推奨値に準じて,m=21,q=11,α=1,β=21に設定した.

数値実験に用いるテスト関数として,藤井(2011)と同様に次の8関数を選択した.下表にこれらの最適解とその時のパラメータ値および定義域を示す.

f:id:okome29taberu:20200809221702p:plain
数値実験に用いるテスト関数とその最適解,パラメータ値,定義域

収束判定基準は最良個体の関数値が10-8を下回った場合に,パラメータは最適解に近づいたとして,探索成功とみなした.一方で,目的関数により評価した回数(評価回数)が840,000回を超えた場合は探索失敗とみなした(藤井, 2011).各テスト関数での試行回数は100回とした.

実験結果

以下に探索成功回数と平均評価回数をテスト関数ごとに示す.参考に同様の条件で数値実験を行った藤井(2011)の結果も併記した.どのテスト関数についても100試行すべてで探索に成功した.また本稿で作成したプログラムと藤井(2011)の間で結果に大差はなく,再現できたといえる.

No テスト関数 探索成功回数 平均評価回数
本稿 藤井(2011) 本稿 藤井(2011)
1 Sphere 100 100 8077 7745
2 Ridge 100 100 10870 9966
3 Rosenbrock 100 100 18232 14662
4 Bohachevsky 100 100 10773 9325
5 Rastrigin 100 100 40891 37099
6 Schwefel 100 100 393456 423574
7 Griewank 100 100 14561 13071
8 Griewank-d 100 100 14813 13344

実装したプログラムはこちら(GitHub - Okome-chan/SCEUA

引用文献
  1. Duan, Q., Soroshin, S. and Gupta, V. K. (1992) Effective and Efficient Global Optimization for Conceptual Rainfall-Runoff Models, Water Resources Research, 28(4), pp.1015-1031.
  2. 杉原成満, 福田慎哉, 倉本和正, 荒木義則, 朝位孝二, 古川浩平 (2011) SCE-UA法を用いたタンクモデルの構築とそれを用いた土砂災害発生危険基準線の設定, 土木学会論文集F6 (安全問題), 67(1), pp.1-13.
  3. 藤井厚紀 (2011) 関数最適化アルゴリズム SCE-UA法の性能評価と改良, 福岡工業大学研究論集, 44(1), pp.45-52.