高次元用改良Simplex法とその波形分離による評価

宮前雄一,張崇良,成澤芳男*

   
Return

1.はじめに

 Spendleyら 1)によって提唱されたSimplex法(SM)は、n変数関数
    F(x1, x2, x3,%%%%, xn)
を極小にするxを探す最適化法のひとつである。その後NelderとMead 2)によって改良され、改良Simplex法(MSM)が発表された。Simplexとはn次元空間でn+1個の点によって形成される図形のことで、n=2では三角形、n=3では四面体である。3)
 SMおよびMSMの化学への応用例は数多く、中でもその改良 4), 5)や、実験条件の最適化への応用 6), 7)が多い。しかし、波形分離への応用例は少ない。8), 9) その理由は、標準スペクトル等を利用した波形分離9)の場合は別として、1つのピークを表すためのパラメータは最低でも3つは必要で、それがいくつか重なり合った波形となるとパラメータの数は10を越え、このような多くのパラメータを同時に最適化するのは、従来の方法では困難なためである。また、重なり度の高い波形になると、他の最適化法にくらべ発散が起こりにくいとされるSimplex法といえども、十分な波形分離は不可能になる。
 そこで、波形分離を行う際に問題になってくる従来のSimplex法(MSM)の弱点を改良し、波形分離に適用し、その効果を精度とスピードの両面について従来法と比較検討した。

 2.アルゴリズム

 

2.1.高次元の最適化におけるModified Simplex Methodの弱点

 MSMは、精度と収束速度が最適化を開始するときのSimplexサイズに大きく依存するSMの弱点を克服するために、Simplexの変形ルールを取り入れている。すなわち、 Fig. 1に2次元の例を示すが、Simplexのうちの最悪の点を捨て、残りの点の重心に対して最悪点と対称な位置に新しい点を取るというSMの基本ルールに則って点の移動を行った際、移動先のA点の関数値が非常に良い場合にはSimplexを一定の比率で伸ばし、また悪い場合には縮めるというものである。これは5次元程度までの低次元の最適化では非常に有効で、最初のSimplexサイズがあまり適当な大きさでなくても、最適化の初期段階では加速しながら最適値に向かってゆき、最適値に近付いてからはSimplexサイズを縮めて減速しながら精度良く最適値に達する。
 しかし、波形分離のような高次元の最適化になると、この変形ルールがうまく働かなくなってくる。高次元の最適化では、A点の関数値があまり良くならない場合が多くなるので、最適値から離れたところでSimplexが縮小し過ぎ、それ以上最適化が進まないということが起こる。またA点の関数値が1番の点より良い場合にも、Simplexを大きく伸ばすとA点より関数値が悪くなったり、Simplexの形がゆがんで後の最適化に支障を来すことがある。これらの理由から、MSMをそのまま波形分離に応用しても、途中まで順調に進んだ最適化が急に進まなくなるなど、安定した十分な精度までの最適化を行うことができない。
 
      Fig.1  SMの基本移動ルール

2.2.Simplex法の改良


a.Simplexの全点同時移動
 Simplexのサイズが小さすぎると最適化は遅くなるが、MSMのルールでSimplexを大きく伸ばすと、そのときは関数値のより良い点がつかまっても、後の最適化に悪影響があるのは先に述べた通りである。そこで、SMのルールによる移動先の点が非常に良い場合には、Simplexすべての点を同時に離れた場所に移動するルールを採用した。その方法を Fig. 2 に示す。 SMのルールで新しく取るA点の関数値が、元のSimplexの中で最もよい1番の点の関数値よりも良い場合には、3番の点からA点を通る延長上に更に関数値が良くなる点のある可能性がある。また最適値は3番の点から、1番と2番の重心の方向よりも1番の点に寄った非重心方向にある可能性も高い。ここでまず、その2つの方向でA点よりも関数値が良くなる点を捜し、見つかったら3番の点をそこに移動し、残りの1番と2番の点も同方向、同距離で平行移動する。この移動方法により、高次元の最適化では数十回の計算ループ回数を節約することができ、しかもSimplexの形やサイズは変わらないので、後の最適化にも支障がない。
 
        Fig.2   Simplexの全点同時移動

 ただし、この方法で移動すると新しいSimplexすべての点の関数値を計算する必要があり、通常の計算ループより計算時間がかかるため、A点とあまり関数値が変わらないような所へ全点を移動すると、かえって計算時間が無駄になる。この点は、関数値が一定の比率以上良くなる場合のみ全点同時移動を行うように制限をし、効果の低い全点同時移動を回避した。
b.Simplexの変形
 2次元平面上での最適化では、Simplexを形成する点の数は3点なので、MSMのようにSimplexの最悪点に対して対称な点(以下鏡像点とする)の関数値によって4種類の伸縮・方向転換の方法があれば十分である。しかし、点の数は次元数nに対してn+1個なので、高次元の最適化においては変形方法が4段階では区切り方が荒すぎると考えられる。
 そこで本改良では、鏡像点の関数値が既存の最良点より優れている場合には先の全点同時移動を行うが、そうでない場合には次元数が変わっても対応できるよう、次元数nに対しn+1種類の変形パターンを取るようにした。これは次元数が低いときはMSMのルールとほぼ同じであるが、次元数の高いときはより細かく伸縮係数を決定する方法である。
c.Simplexの作り直し
 高次元の最適化では応答表面はかなり複雑で、関数値が良くならない最適化ループを繰り返しているうちに、最適値に十分近づかないままSimplexが小さくなったり、Simplexの 形が歪んでSimplexの全ての点がほぼ同じ関数値をもつ位置に並んでしまうことがある。このような状態になると、その後の有効な最適化は困難になるので、本法ではSimplex中の最良点と最悪点の関数値の差が一定値より小さくなったときに、Simplexを新しく作り直すようにした。この方法の2次元での例を Fig. 3に示す。Fig. 3 (a)の数値は関数値の良 い順番を表す番号であるとして、1番の点のみを残し他の点は捨て、サイズや形が適当なFig. 3 (b)のようなSimplexに作り直す。これにより、多くの場合は最適化が進みにくくなった状態から脱出することができる。

    Fig.3   Simplexの作り直し

d.最適化空間の低次元化  波形分離の場合、波形の中で重なり度の高い部分と低い部分があると、重なり度の低い部分については他の部分より先に最適化が進むことがある。このとき、その部分のピークを表すパラメータを固定することで、計算プログラムをほとんど変更することなく、擬似的に最適化を行う空間の次元数を下げることができる。これにより、重なり度の高い部分の最適化がスムーズになり、また最適化計算ループ1回に要する計算時間も短くなる。

3.方法


3.1.装置とプログラム言語


 コンピュータはNECのPC-9821 Ap2を使用し、プログラム言語はMS-DOS 5.0A-H上でUBASIC86 Ver. 8.7c 10)を使用した。グラフィック表示を行うため、MS-DOS付属のグラフィックドライバを組み込んで使用した。

3.2.プログラムの概要


 本波形分離プログラムは、解析しようとする重なり波形と関数を合成した波形の差の2乗の和、すなわち残差2乗和(SSR) 11)が小さくなっていくように最適化のループ計算を繰り返す。最適化のアルゴリズムには、前項2.2.で述べた改良を加えたSimplex法を用いている。プログラムの流れは以下の通りである。
(1) 解析を行うデータ波形を読み込み、ピークを検索する。
(2) そのパラメータをもとに残りの点を作り、出発Simplexとする。
(3) 関数値(残差2乗和)が一定の設定値以下になるまで、最適化ループ計算を繰り返す。

4.合成波形の波形分離


4.1.目的と方法


 Simplex法の本改良の効果をテストするため、ガウス関数を重ね合わせて作った合成波形の波形分離を行った。比較のため、MSMによる波形分離も行った。
 合成波形であれば、成分ピークについての正確な情報があらかじめ分かっているので、最適化がどの程度うまくいっているかを検討するのに都合がよい。また、ガウス関数を重ねた波形を再びガウス関数で分離する場合、アルゴリズムが良ければ完全に元のピークに分離できるはずであり、Simplexがどこまで最適値を絞り込めるかも調べることができる。
 各ピークをガウス関数で表しているので、1つのピークについてのパラメータは位置、高さ、半値幅の3つで、ピーク数をPとすると、パラメータは全部で3P個になる。

4.2.結果と考察


 波形分離を行った3種類の重なり波形、a(2ピーク),b(4ピーク),c(7ピーク)を Fig. 4Fig. 6に示す。各図とも、ガウス関数で表される単独ピークとそれらを重ねたものの両方を示してある。  各波形について、本改良法とMSMでそれぞれ波形分離を行ったときの計算ループ回数、計算時間、平均ピーク面積誤差を Table 1Table 3に示す。平均ピーク面積誤差とは、ピーク面積の真値と波形分離の計算値との誤差が真値に対し何%であるかをピークごとに求め、その値を全てのピークで平均したものである。設定誤差は1.0×10^{-2}〜1.0×10^{-10}の5段階を用いた。なお表中の ------- は、10000ループの計算でその設定誤差に達しなかったことを示す。

        Fig.4    波形 a

         Fig.5 波形 b

         Fig.6    波形 c

 まず波形aについては、ピーク同士の重なり度は非常に高いにもかかわらず、本改良法、MSMのいずれの方法でも十分な精度で波形分離を行うことができた。これは、ピークが2つだけなので最適化を行う空間の次元数は6次元であり、この程度の次元数なら通常のMSMも問題なく使えることを示している。計算スピードについては、本改良法の方がやや優れている結果が出た。
 ピーク数4の波形bでは、設定誤差1.0×10^{-4}まではMSMも問題なく最適化を行えるが、その次の1.0×10^{-6}の設定では、10000ループの計算でも設定誤差に到達できなかった。これは関数値が10^{-4}を下回ったあたりで最適化がうまく進まなくなり、Simplexが縮小してそれ以上最適値に近づけなくなったためである。しかし、1.0×10^{-4}の誤差設定でも平均ピーク面積誤差0.232%までの最適化はできており、実際の波形分離に何とか利用できる程度といえよう。また伸縮係数の調整により、もう少し最適化を進めることは可能と思われる。
 これに対し、本改良法を用いた場合は関数値が10^{-10}に達するまでスムーズに最適化が進んでおり、全く問題がなかった。
 最後に7ピークの波形cについてであるが、この波形は重なり度が低く、分離する必要などほとんどないような波形である。しかし、一見非常に分離が簡単そうなこの波形でも、MSMによる波形分離では約1%の平均ピーク面積誤差を残しており、満足な解析ができているとは言い難い。これは波形bの場合と同様に、21次元という高次元の最適化において、Simplexを縮小する傾向の強いMSMでは、一度最適化が減速すると再び加速することができず、そこで収束してしまうためである。
 本改良法による波形分離では、計算時間はかなり要しているものの、設定誤差1.0×10^{-1}での解析にも成功している。この点で、高次元の解析を精度良く行うという本改良の第一目的は達せられたといえる。
 実測データへの応用例として、N-Acetyl-L-proline N-methylamide (APM)の赤外吸収スペクトルの解析結果を Fig. 7に示す。この解析ではピークによってガウス関数とローレンツ関数を使い分け、4つのピークで波形分離を行っている。この図では、実測スペクトル、波形分離した各ピークおよびそれらのピークを合成した波形を重ねて表示しているが、合成波形と実測スペクトルの差が分からないほど十分な最適化が行えた。条件を変えて測定したスペクトルの解析など、APMのIRスペクトルの総合的な考察は別報にて行いたい。
   
        Fig.7   APM の IR スペクトル

 本論文では合成波形の解析を中心に取り上げたが、ピークを表す適当な関数さえあればいかなる実測波形にも応用が可能で、今後の幅広い応用が期待できる。

Table 1   各設定誤差で波形 a の分離に要した計算時間の比較


Table 2  各設定誤差で波形 b の分離に要した計算時間の比較


Table 3  各設定誤差で波形 c の分離に要した計算時間の比較

謝辞


APMの赤外吸収スペクトルを提供して頂いた、立教大学理学部化学科の大谷俊明氏、秋山稔氏に感謝を申し上げます。

 参考文献

1. W. Spendley, G. B. Hext, and F. R. Himsworth, Technometrics, 4, 441 (1962).
2. J. A. Nelder and R. Mead, Comput. J., 7, 308 (1965). 
3. 渡部力%名取亮%小国力監修, Fortran77による数値計算ソフトウェア, 丸善 (1989).
4. M.-H. Shao, Anal. Chim. Acta, 248, 31 (1991).
5. P. Hedlund and A. Gustavsson, Anal. Chim. Acta, 259, 243 (1992).
6. R. Koncki, S. Glab, and A. Hulanicki, Anal. Chim. Acta, 273, 477 (1993)
7. Y. Guillaume and C. Guinchard, J. Liq. Chromatogr., 16, 3457 (1993)
8. H. Miyata, S. Tokuda, and T. Yoshida, Appl. Spectrosc., 43, 522 (1989).
9. M. Blanco, V. Cerd , J. Coello, J. Gen , H. Iturriaga, and S. Maspoch, Anal. Lett., 25, 543 (1992).
10. 木田祐司, UBASIC|86 第8.7版ユーザーズマニュアル, 日本評論社(1994).
11. J. C. Miller and J. N. Miller, Statistics for Analytical Chemistry, 3rd ed. , Ellis Horwood (1993).

Return