「差分進化」の版間の差分

削除された内容追加された内容

インライン

2017年5月5日 (金) 02:19時点における版

進化的計算における差分進化(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$ を見つけることである。つまり、 $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”. 2016年9月17日閲覧。
^ Chakraborty, U.K., ed. (2008), Advances in Differential Evolution, Springer, ISBN 978-3-540-68827-3
^ S. Das and P. N. Suganthan, "Differential Evolution: A Survey of the State-of-the-art", IEEE Trans. on Evolutionary Computation, Vol. 15, No. 1, pp. 4-31, Feb. 2011, DOI: 10.1109/TEVC.2010.2059031.
^ S. Das, S. S. Mullick, P. N. Suganthan, "Recent Advances in Differential Evolution - An Updated Survey," Swarm and Evolutionary Computation, doi:10.1016/j.swevo.2016.01.004, 2016.
^ 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.
^ 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.

外部リンク

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)

[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”. 2016年9月17日閲覧。

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

[8] S. Das and P. N. Suganthan, "Differential Evolution: A Survey of the State-of-the-art", IEEE Trans. on Evolutionary Computation, Vol. 15, No. 1, pp. 4-31, Feb. 2011, DOI: 10.1109/TEVC.2010.2059031.

[9] S. Das, S. S. Mullick, P. N. Suganthan, "Recent Advances in Differential Evolution - An Updated Survey," Swarm and Evolutionary Computation, doi:10.1016/j.swevo.2016.01.004, 2016.

[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]

[15]