差分進化のソースを表示

{{翻訳直後|1=[[:en:Differential_evolution]] 06:58, 30 March 2017|date=2017年5月}}

[[進化的計算]]における'''差分進化'''（さぶんしんか、{{lang-en-short|Differential evolution}}、略称: '''DE'''）とは、与えられた評価尺度に関する{{仮リンク|候補解|en|Feasible_region#Candidate_solution}}を[[反復法 (数値計算)|反復的]]に改良していき、問題を最適化する手法である。このような手法は、最適化の対象となる問題に関する仮定を一切置かないか、あるいはわずかしか置かない[[メタヒューリスティクス]]であり、広範な解の候補の空間を探索できる。ただし、DEのようなメタヒューリスティクスは真の最適解を見つけられる保証はない。DEは多次元空間での実数値関数に対して用いることができるが、最適化対象である関数（目的関数）の[[勾配 (ベクトル解析)|勾配]]は使用しない。つまり、[[最急降下法]]や[[準ニュートン法]]のような古典的な最適化手法が要求する次の条件 「最適化問題が[[微分可能関数|微分可能]]」 をDEは必要としない。それゆえ、DEは関数が連続でない場合やノイズの多い場合、時間変化する場合の最適化問題に対しても用いることができる<ref name=elediadereview>
{{Cite journal
|last1=Rocca
|first1=P.
|last2=Oliveri
|first2=G.
|last3=Massa
|first3=A.
|title=Differential Evolution as Applied to Electromagnetics
|journal=IEEE Antennas and Propagation Magazine
|year=2011
|volume=53
|issue=1
|pages=38&ndash;49
|doi=10.1109/MAP.2011.5773566 
}}
</ref>。DEは単純な式に従って候補解集団を更新し、最適化問題に対して最良のスコアまたは最良の当てはまりを示した候補解を保持しておく。これにより、最適化すべき目的関数は解の候補に評価尺度を与える単なるブラックボックスと見なせて、その勾配の値を必要としない。
DEは元々はStomおよびPriceの着想である<ref name=storn97differential>
{{cite journal
|last=Storn
|first=R.
|author2=Price, K.
|title=Differential evolution - a simple and efficient heuristic for global optimization over continuous spaces
|journal=Journal of Global Optimization
|year=1997
|volume=11
|pages=341&ndash;359
|doi=10.1023/A:1008202821328
}}</ref><ref name=storn96usage>
{{cite conference
|last=Storn
|first=R.
|title=On the usage of differential evolution for function optimization
|book-title=Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS)
|year=1996
|pages=519&ndash;523
}}
</ref>。[[並列計算]]、[[多目的最適化]]、[[制約付き最適化]]の分野に於いて、DEの使用に関する理論的見地、実用的見地および応用領域からの調査に基づく書籍が出版されている<ref name=price05differential>
{{cite book
|title=Differential Evolution: A Practical Approach to Global Optimization
|url=http://www.springer.com/computer/theoretical+computer+science/foundations+of+computations/book/978-3-540-20950-8
|last1=Price
|first1=K.
|last2=Storn
|first2=R.M.
|last3=Lampinen
|first3=J.A.
|year=2005
|publisher=Springer
|isbn=978-3-540-20950-8
}}
</ref><ref name=feoktistov06differential>
{{cite book
|title=Differential Evolution: In Search of Solutions
|url=http://www.springer.com/mathematics/book/978-0-387-36895-5
|last=Feoktistov
|first=V.
|year=2006
|publisher=Springer
|isbn=978-0-387-36895-5
}}
</ref><ref>G. C. Onwubolu and  B V Babu, {{cite web|url=http://www.springer.com/in/book/9783540201670|title=New Optimization Techniques in Engineering|publisher=|accessdate=17 September 2016}}</ref><ref name=chakraborty08advances>
{{citation
|title=Advances in Differential Evolution
|url=http://www.springer.com/engineering/book/978-3-540-68827-3
|editor-last=Chakraborty
|editor-first=U.K.
|year=2008
|publisher=Springer
|isbn=978-3-540-68827-3
}}
</ref>。DEの多面的研究は論文に投稿されている<ref>{{cite journal|author=Das, S.; Suganthan, P. N. |title=Differential Evolution: A Survey of the State-of-the-art|journal=IEEE Trans. on Evolutionary Computation|volume= 15|issue=1|pages=4-31|year= 2011|doi= 10.1109/TEVC.2010.2059031}}</ref><ref>{{cite journal|author=Das, S.; Mullick, S. S.; Suganthan, P. N. |title=Recent Advances in Differential Evolution - An Updated Survey|journal=Swarm and Evolutionary Computation|doi=10.1016/j.swevo.2016.01.004|year= 2016|volume=27|pages=1-30}}</ref>。

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

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

== パラメータ選択 ==
{{Expand section|date=May 2017}}

[[Image:DE Meta-Fitness Landscape (Sphere and Rosenbrock).JPG|thumb|Performance landscape showing how the basic DE performs in aggregate on the Sphere and Rosenbrock benchmark problems when varying the two DE parameters <math>\text{NP}</math> and <math>\text{F}</math>, and keeping fixed <math>\text{CR}</math>=0.9.]]

DEアルゴリズムのパラメータである <math>F, \text{CR}</math> および <math>\text{NP}</math> は最適化性能に大きな影響を与えうる。良い性能を引き出すようにDEパラメータを選ぶことが、多くの研究活動における主題となる。パラメータ選択として、正確ではないが大雑把な方法がStornら<ref name=storn96usage/><ref name=price05differential/>、LiuおよびLampien<ref name=liu02setting>
{{cite conference
|title=On setting the control parameter of the differential evolution method
|book-title=Proceedings of the 8th International Conference on Soft Computing (MENDEL)
|last=Liu
|first=J.
|last2=Lampinen
|first2=J.
|year=2002
|pages=11&ndash;18
|location=Brno, Czech Republic
}}
</ref>によって考案された。パラメータ選択に関する収束判定はZaharieによって行われている<ref name=zaharie02critical>
{{cite conference
|title=Critical values for the control parameters of differential evolution algorithms
|book-title=Proceedings of the 8th International Conference on Soft Computing (MENDEL)
|last=Zaharie
|first=D.
|year=2002
|pages=62&ndash;67
|location=Brno, Czech Republic
}}
</ref>。DEパラメータの[[メタ最適化]]はPedersen<ref name=pedersen08thesis>
{{cite book
|type=PhD thesis
|title=Tuning & Simplifying Heuristical Optimization
|url=http://www.hvass-labs.org/people/magnus/thesis/pedersen08thesis.pdf
|last=Pedersen
|first=M.E.H.
|year=2010
|publisher=University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group
}}
</ref><ref name=pedersen10good-de>
{{Cite journal
|last=Pedersen
|first=M.E.H.
|url=http://www.hvass-labs.org/people/magnus/publications/pedersen10good-de.pdf
|title=Good parameters for differential evolution
|journal=Technical Report HL1002
|publisher=Hvass Laboratories
|year=2010
}}
</ref>およびZhangら<ref name=zhang11fitting>
{{cite conference
|last1=Zhang
|first1=X.
|last2=Jiang
|first2=X.
|last3=Scott
|first3=P.J.
|title=A Minimax Fitting Algorithm for Ultra-Precision Aspheric Surfaces
|book-title=The 13th International Conference on Metrology and Properties of Engineering Surfaces
|year=2011
}}
</ref>によって行われている。

== 亜種 ==
{{Expand section|date=May 2017}}

<!-- 適切な文献(カンファレンスペーパー、ジャーナル、技術レポート、修士または博士論文)を記載すること。代表的な研究のみを記載すること。何百もの DE の亜種があるが、wikipedia はそれらすべてを記載する場所としては適切ではない。 -->
最適化パフォーマンスを改良すべく、DEアルゴリズムの多くの亜種が開発されている。上記で与えた基本アルゴリズムにおける交叉およびエージェントの変異方法を変更しても良い<ref name=storn96usage/>。

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

<!-- javascript syntax color works well for pseudocode -->
<syntaxhighlight lang="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
	}
}
</syntaxhighlight>

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 関連項目 ==
<!-- DE に関連した最適化手法のみを加えること -->
* [[人工蜂コロニーアルゴリズム]]
* [[CMA-ES]]
* [[Differential search algorithm]]<ref name=civici>
{{cite journal
|last=Civicioglu
|first=P.
|title=Transforming geocentric cartesian coordinates to geodetic coordinates by using differential search algorithm
|journal=Computers & Geosciences
|year=2012
|volume=46
|pages=229&ndash;247
|doi=10.1016/j.cageo.2011.12.011
}}
</ref>
* [[進化戦略]]
* [[遺伝的アルゴリズム]]

== 外部リンク ==
* [http://www.icsi.berkeley.edu/~storn/code.html Storn's Homepage on DE] featuring source-code for several programming languages.
* [http://www.sciencedirect.com/science/article/pii/S0957417410010493 Fast DE Algorithm] A Fast Differential Evolution Algorithm using k-Nearest Neighbour Predictor.
* [http://www.sciencedirect.com/science/article/pii/S0957417413000857 MODE Application] Parameter Estimation of a Pressure Swing Adsorption Model for Air Separation Using Multi-objective Optimisation and Support Vector Regression Model.
* [http://www.sciencedirect.com/science/article/pii/S1568494615002756 The runner-root algorithm (RRA)]

{{DEFAULTSORT:さふんしんか}}

[[Category:進化的アルゴリズム]]