差分進化

進化的計算における差分進化（さぶんしんか、英: Differential evolution、略称: DE）とは、与えられた評価尺度に関する候補解（英語版）を反復的に改良していき、問題を最適化する手法である。このような手法は、最適化の対象となる問題に関する仮定を一切置かないか、あるいはわずかしか置かないメタヒューリスティクスであり、広範な解の候補の空間を探索できる。ただし、DEのようなメタヒューリスティクスは真の最適解を見つけられる保証はない。DEは多次元空間での実数値関数に対して用いることができるが、最適化対象である関数（目的関数）の勾配は使用しない。つまり、最急降下法や準ニュートン法のような古典的な最適化手法が要求する次の条件「最適化問題が微分可能」をDEは必要としない。それゆえ、DEは関数が連続でない場合やノイズの多い場合、時間変化する場合の最適化問題に対しても用いることができる^[1]。DEは単純な式に従って候補解集団を更新し、最適化問題に対して最良のスコアまたは最良の当てはまりを示した候補解を保持しておく。これにより、最適化すべき目的関数は解の候補に評価尺度を与える単なるブラックボックスと見なせて、その勾配の値を必要としない。 DEは元々はStomおよびPriceの着想である^[2]^[3]。並列計算、多目的最適化、制約付き最適化の分野に於いて、DEの使用に関する理論的見地、実用的見地および応用領域からの調査に基づく書籍が出版されている^[4]^[5]^[6]^[7]。DEの多面的研究は論文に投稿されている^[8]^[9]。

アルゴリズム

DEアルゴリズムは候補解集団（エージェントとよばれる）を保持して動作する。エージェントは、単純な数式に従ってその集団内の位置を組み合わせながら、探索すべき空間内を動き回り、その位置を更新する。エージェントを更新した位置が評価尺度の上で改良を示したならば、それは棄却されずに解の候補集団の一部となる。そうでなければ、その位置は棄却される。この過程が繰り返されて、（真の最適解である保証はないが）解に到達する。形式的には、 $f:\mathbb {R} ^{n}\to \mathbb {R}$ を最小化すべき目的関数または最大化すべき適合度（フィットネス）関数とする。この関数は引数として実数値ベクトルで表された候補解を受け取り、その候補解の適合度を示す実数を出力する。その際に $f$ の勾配は不明である。行いたいことは、探索空間におけるすべての点 $p$ に対して $f(m)\leq f(p)$ であるような解 $m$ 、つまり大域的な最小点を見つけ出すことである。もしも最小化ではなくて最大化を行いたい場合には、 $h:=-f$ を考えればよい。 $\mathbf {x} \in \mathbb {R} ^{n}$ を集団における候補解（エージェント）とする。 ${\text{CR}}\in [0,1]$ を交叉率 (crossover rate) とする。 $F\in [0,2]$ をスケール因子 (scaling factor )とする。 ${\text{NP}}$ を集団サイズとする。これらのパラメータは、 ${\text{NP}}\geq 4$ のもとで、計算を行なう者が決める（以下を参照）。DEアルゴリズムの基本的な流れは以下のとおりである。

探索空間における全エージェント $\mathbf {x}$ をランダムな位置に初期化する。
終了条件が満たされるまで（たとえば、繰り返し回数やフィットネス値の閾値を越えた、など）、以下を繰り返す。
- 集団の各エージェント $\mathbf {x}$ $\mathbf {x}$ について、以下を行う。
  - ランダムに 3 つのエージェント $\mathbf {a} ,\mathbf {b} ,\mathbf {c}$ を選ぶ。ここで、 $\mathbf {x}$ , $\mathbf {a}$ , $\mathbf {b}$ , $\mathbf {c}$ は互いに異なるエージェントであるようにする。
  - ランダムにインデックス $R\in \{1,\ldots ,n\}$ を選ぶ( $n$ は最適化問題の次元数である)。
  - エージェントの更新位置 $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ $\mathbf {y} =[y_{1},\ldots ,y_{n}]$ を次のように計算する。
    - 各 $i\in \{1,\ldots ,n\}$ ごとに、一様分布に従う乱数 $r_{i}\equiv U(0,1)$ を選ぶ。
    - もし、 $r_{i}<CR$ または $i=R$ であれば $y_{i}=a_{i}+F\times (b_{i}-c_{i})$ とし、そうでなければ $y_{i}=x_{i}$ とする。
    - (本質的には、更新位置は中間エージェント $\mathbf {z} =\mathbf {a} +F\times (\mathbf {b} -\mathbf {c} )$ とエージェント $\mathbf {x}$ のバイナリクロスオーバー(binary crossover) の出力である。
  - もし、 $f(\mathbf {y} )<f(\mathbf {x} )$ であればその位置のエージェントを更新された解に置換、すなわち $\mathbf {x}$ と $\mathbf {y}$ を入れ替える。
最も大きい適合度または最も小さい目的関数値を持つエージェントを集団から選び、それを最適解として返す。

パラメータ選択

DEアルゴリズムのパラメータである $F,{\text{CR}}$ および ${\text{NP}}$ は最適化性能に大きな影響を与えうる。良い性能を引き出すようにDEパラメータを選ぶことが、多くの研究活動における主題となる。パラメータ選択として、正確ではないが大雑把な方法がStornら^[3]^[4]、LiuおよびLampien^[10]によって考案された。パラメータ選択に関する収束判定はZaharieによって行われている^[11]。DEパラメータのメタ最適化はPedersen^[12]^[13]およびZhangら^[14]によって行われている。

亜種

最適化パフォーマンスを改良すべく、DEアルゴリズムの多くの亜種が開発されている。上記で与えた基本アルゴリズムにおける交叉およびエージェントの変異方法を変更しても良い^[3]。

サンプルコード

以下はDEアルゴリズムの実装を擬似コードで示した例である（Java言語に類似の形式により記述されている）。より一般的な擬似コードについては、アルゴリズムセクションを参照すること。

//definition of one individual in population
public class Individual {
	//normally DifferentialEvolution uses floating point variables
	float data1, data2
	//but using integers is possible too  
	int data3
}

public class DifferentialEvolution {
	//Variables
	//linked list that has our population inside
	LinkedList<Individual> population=new LinkedList<Individual>()
	//New instance of Random number generator
	Random random=new Random()
	int PopulationSize=20

	//differential weight [0,2]
	float F=1
	//crossover probability [0,1]
	float CR=0.5
	//dimensionality of problem, means how many variables problem has. this case 3 (data1,data2,data3)
	int N=3;

	//This function tells how well given individual performs at given problem.
	public float fitnessFunction(Individual in) {
		...
		return	fitness	
	}

	//this is main function of program
	public void Main() {
		//Initialize population with individuals that have been initialized with uniform random noise
		//uniform noise means random value inside your search space
		int i=0
		while(i<populationSize) {
			Individual individual= new Individual()
			individual.data1=random.UniformNoise()
			individual.data2=random.UniformNoise()
			//integers cant take floating point values and they need to be either rounded
			individual.data3=Math.Floor( random.UniformNoise())
			population.add(individual)
			i++
		}
		
		i=0
		int j
		//main loop of evolution.
		while (!StoppingCriteria) {
			i++
			j=0
			while (j<populationSize) {
				//calculate new candidate solution
			
				//pick random point from population
				int x=Math.floor(random.UniformNoise()%(population.size()-1))
				int a,b,c

				//pick three different random points from population
				do{
					a=Math.floor(random.UniformNoise()%(population.size()-1))
				}while(a==x);
				do{
					b=Math.floor(random.UniformNoise()%(population.size()-1))
				}while(b==x| b==a);
				do{
					c=Math.floor(random.UniformNoise()%(population.size()-1))
				}while(c==x | c==a | c==b);
				
				// Pick a random index [0-Dimensionality]
				int R=rand.nextInt()%N;
				
				//Compute the agent's new position
				Individual original=population.get(x)
				Individual candidate=original.clone()
				
				Individual individual1=population.get(a)
				Individual individual2=population.get(b)
				Individual individual3=population.get(c)
				
				//if(i==R | i<CR)
					//candidate=a+f*(b-c)
				//else
					//candidate=x
				if( 0==R | random.UniformNoise()%1<CR){	
					candidate.data1=individual1.data1+F*(individual2.data1-individual3.data1)
				}// else isn't needed because we cloned original to candidate
				if( 1==R | random.UniformNoise()%1<CR){	
					candidate.data2=individual1.data2+F*(individual2.data2-individual3.data2)
				}
				//integer work same as floating points but they need to be rounded
				if( 2==R | random.UniformNoise()%1<CR){	
					candidate.data3=Math.floor(individual1.data3+F*(individual2.data3-individual3.data3))
				}
				
				//see if is better than original, if so replace
				if(fitnessFunction(original)<fitnessFunction(candidate)){
					population.remove(original)
					population.add(candidate)
				}
				j++
			}
		}
		
		//find best candidate solution
		i=0
		Individual bestFitness=new Individual()
		while (i<populationSize) {
			Individual individual=population.get(i)
			if(fitnessFunction(bestFitness)<fitnessFunction(individual)){
				bestFitness=individual
			}
			i++
		}
		
		//your solution
		return bestFitness
	}
}

脚注

[脚注の使い方]

^ Rocca, P.; Oliveri, G.; Massa, A. (2011). “Differential Evolution as Applied to Electromagnetics”. IEEE Antennas and Propagation Magazine 53 (1): 38–49. doi:10.1109/MAP.2011.5773566.
^ Storn, R.; Price, K. (1997). “Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces”. Journal of Global Optimization 11: 341–359. doi:10.1023/A:1008202821328.
^ ^a ^b ^c Storn, R. (1996). "On the usage of differential evolution for function optimization". Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523.
^ ^a ^b Price, K.; Storn, R.M.; Lampinen, J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer. ISBN 978-3-540-20950-8
^ Feoktistov, V. (2006). Differential Evolution: In Search of Solutions. Springer. ISBN 978-0-387-36895-5
^ G. C. Onwubolu and B V Babu, “New Optimization Techniques in Engineering”. 17 September 2016閲覧。
^ Chakraborty, U.K., ed. (2008), Advances in Differential Evolution, Springer, ISBN 978-3-540-68827-3
^ Das, S.; Suganthan, P. N. (2011). “Differential Evolution: A Survey of the State-of-the-art”. IEEE Trans. on Evolutionary Computation 15 (1): 4-31. doi:10.1109/TEVC.2010.2059031.
^ Das, S.; Mullick, S. S.; Suganthan, P. N. (2016). “Recent Advances in Differential Evolution - An Updated Survey”. Swarm and Evolutionary Computation 27: 1-30. doi:10.1016/j.swevo.2016.01.004.
^ Liu, J.; Lampinen, J. (2002). "On setting the control parameter of the differential evolution method". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 11–18.
^ Zaharie, D. (2002). "Critical values for the control parameters of differential evolution algorithms". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 62–67.
^ Pedersen, M.E.H. (2010). Tuning & Simplifying Heuristical Optimization (PhD thesis). University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group
^ Pedersen, M.E.H. (2010). “Good parameters for differential evolution”. Technical Report HL1002 (Hvass Laboratories).
^ Zhang, X.; Jiang, X.; Scott, P.J. (2011). "A Minimax Fitting Algorithm for Ultra-Precision Aspheric Surfaces". The 13th International Conference on Metrology and Properties of Engineering Surfaces.

外部リンク

Storn's Homepage on DE featuring source-code for several programming languages.
Fast DE Algorithm A Fast Differential Evolution Algorithm using k-Nearest Neighbour Predictor.
MODE Application Parameter Estimation of a Pressure Swing Adsorption Model for Air Separation Using Multi-objective Optimisation and Support Vector Regression Model.
The runner-root algorithm (RRA)

^ Civicioglu, P. (2012). “Transforming geocentric cartesian coordinates to geodetic coordinates by using differential search algorithm”. Computers & Geosciences 46: 229–247. doi:10.1016/j.cageo.2011.12.011.

[elediadereview-1] Rocca, P.; Oliveri, G.; Massa, A. (2011). “Differential Evolution as Applied to Electromagnetics”. IEEE Antennas and Propagation Magazine 53 (1): 38–49. doi:10.1109/MAP.2011.5773566.

[storn97differential-2] Storn, R.; Price, K. (1997). “Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces”. Journal of Global Optimization 11: 341–359. doi:10.1023/A:1008202821328.

[storn96usage-3] Storn, R. (1996). "On the usage of differential evolution for function optimization". Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523.

[price05differential-4] Price, K.; Storn, R.M.; Lampinen, J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization. Springer. ISBN 978-3-540-20950-8

[feoktistov06differential-5] Feoktistov, V. (2006). Differential Evolution: In Search of Solutions. Springer. ISBN 978-0-387-36895-5

[6] G. C. Onwubolu and B V Babu, “New Optimization Techniques in Engineering”. 17 September 2016閲覧。

[chakraborty08advances-7] Chakraborty, U.K., ed. (2008), Advances in Differential Evolution, Springer, ISBN 978-3-540-68827-3

[8] Das, S.; Suganthan, P. N. (2011). “Differential Evolution: A Survey of the State-of-the-art”. IEEE Trans. on Evolutionary Computation 15 (1): 4-31. doi:10.1109/TEVC.2010.2059031.

[9] Das, S.; Mullick, S. S.; Suganthan, P. N. (2016). “Recent Advances in Differential Evolution - An Updated Survey”. Swarm and Evolutionary Computation 27: 1-30. doi:10.1016/j.swevo.2016.01.004.

[liu02setting-10] Liu, J.; Lampinen, J. (2002). "On setting the control parameter of the differential evolution method". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 11–18.

[zaharie02critical-11] Zaharie, D. (2002). "Critical values for the control parameters of differential evolution algorithms". Proceedings of the 8th International Conference on Soft Computing (MENDEL). Brno, Czech Republic. pp. 62–67.

[pedersen08thesis-12] Pedersen, M.E.H. (2010). Tuning & Simplifying Heuristical Optimization (PhD thesis). University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group

[pedersen10good-de-13] Pedersen, M.E.H. (2010). “Good parameters for differential evolution”. Technical Report HL1002 (Hvass Laboratories).

[zhang11fitting-14] Zhang, X.; Jiang, X.; Scott, P.J. (2011). "A Minimax Fitting Algorithm for Ultra-Precision Aspheric Surfaces". The 13th International Conference on Metrology and Properties of Engineering Surfaces.

[civici-15] Civicioglu, P. (2012). “Transforming geocentric cartesian coordinates to geodetic coordinates by using differential search algorithm”. Computers & Geosciences 46: 229–247. doi:10.1016/j.cageo.2011.12.011.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[1]

アルゴリズム

パラメータ選択

亜種

サンプルコード

脚注

関連項目

外部リンク