進化戦略
このときもし f(x) < f(x′) であるなら、x = x′ として上記の処理を繰り返す。
ここで問題になるのはσがどれくらいの数値なら適正であるか である、もしσが小さな数値なら x' は非常に x に近い位置のベクトルになり、上記の操作は最も近い極大値を見つけることができる可能性が高い。しかしこの極大値が最大値である保証はなく、もし違うなら最大値ではない極大値に捕まって探索が失敗したことになる(局所解)。逆にσが大きな数値なら局所解の問題は回避できる可能性が高いが探索した結果がその空間付近の極大値である可能性は極めて低い、もしかしたら求めた解は最大値のほんの少し手前であるかもしれない。
(1+1)-ES は上記の探索を行いながらσの値を更新する探索手法である。更新方法には決まった方法の定義は無いが提案者の Schwefel は次のような更新規則と更新方法を推奨している。
r_{ij}=-r_{ji}=-\sin \alpha _{ij}\right.} r k k = 1 ( k = 1 , ... , n and k ≠ i , k ≠ j ) {\displaystyle r_{kk}=1(k=1,\dots ,n{\mbox{ and }}k\neq i,k\neq j)} それ以外の要素は 0 とする。
この二つの要素を以下の式で掛け合わせてベクトル ζ = ( ζ 1 , ζ 2 , ... , ζ n ) {\displaystyle \zeta =(\zeta _{1},\zeta _{2},\dots ,\zeta _{n})} を生成する。
ζ = ∏ i = 1 n − 1 ∏ j = i + 1 n R ( α i j ) η {\displaystyle \zeta =\prod _{i=1}^{n-1}\prod _{j=i+1}^{n}R(\alpha _{ij})\eta }
このベクトルとx の和をx' とする。
x ′ = x + ζ {\displaystyle \left.x'=x+\zeta \right.}
これが突然変異操作となる。
ここでは、(1+1)-ES アルゴリズムについて述べる。このアルゴリズムは次のような単純な局所探索の枠組みから始まる。
まず n 次元空間の上の目的関数 f(x) の最大値を求める問題を考えてみる。 このとき引数ベクトル x は x = ( x 1 , x 2 , ... , x n ) {\displaystyle x=(x_{1},x_{2},\dots ,x_{n})} の成分を持つとする。このとき
x i ′ = x i + N ( 0 , σ 2 ) ( i = 1 , 2 , ... , n ) {\displaystyle x'_{i}=x_{i}+N(0,\sigma ^{2})(i=1,2,\dots ,n)}
となるベクトル x ′ = ( x 1 ′ , x 2 ′ , ... , x n ′ ) {\displaystyle x'=(x'_{1},x'_{2},\dots ,x'_{n})} を考える、ここで N(0, σ) は平均 0、分散 σ(すなわち標準偏差 σ)の正規乱数(乱数列参照)であり、各成分ごとに独立である(同じ数値を全成分に加算するわけではない)。