差分進化

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

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

Performance landscape showing how the basic DE performs in aggregate on the Sphere and Rosenbrock benchmark problems when varying the two DE parameters ${\displaystyle {\text{NP}}}$ and ${\displaystyle {\text{F}}}$, and keeping fixed ${\displaystyle {\text{CR}}}$=0.9.

DEアルゴリズムのパラメータである ${\displaystyle F,{\text{CR}}}$ および ${\displaystyle {\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
	}
}

• 人工蜂コロニーアルゴリズム
• CMA-ES
• Differential search algorithm[1]
• 進化戦略
• 遺伝的アルゴリズム

• 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)

1. 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.