差分進化

進化的計算における差分進化（さぶんしんか、、略称: DE）とは、与えられた評価尺度に関するを反復的に改良していき、問題を最適化する手法である。このような手法は、最適化の対象となる問題に関する仮定を一切置かないか、あるいはわずかしか置かないメタヒューリスティクスであり、広範な解の候補の空間を探索できる。ただし、DEのようなメタヒューリスティクスは真の最適解を見つけられる保証はない。DEは多次元空間での実数値関数に対して用いることができるが、最適化対象である関数（目的関数）の勾配は使用しない。つまり、最急降下法や準ニュートン法のような古典的な最適化手法が要求する次の条件 「最適化問題が微分可能」 をDEは必要としない。それゆえ、DEは関数が連続でない場合やノイズの多い場合、時間変化する場合の最適化問題に対しても用いることができる。DEは単純な式に従って候補解集団を更新し、最適化問題に対して最良のスコアまたは最良の当てはまりを示した候補解を保持しておく。これにより、最適化すべき目的関数は解の候補に評価尺度を与える単なるブラックボックスと見なせて、その勾配の値を必要としない。
DEは元々はStomおよびPriceの着想である。並列計算、多目的最適化、制約付き最適化の分野に於いて、DEの使用に関する理論的見地、実用的見地および応用領域からの調査に基づく書籍が出版されている。DEの多面的研究は論文に投稿されている。
アルゴリズム.
DEアルゴリズムは候補解集団（エージェントとよばれる）を保持して動作する。エージェントは、単純な数式に従ってその集団内の位置を組み合わせながら、探索すべき空間内を動き回り、その位置を更新する。エージェントを更新した位置が評価尺度の上で改良を示したならば、それは棄却されずに解の候補集団の一部となる。そうでなければ、その位置は棄却される。この過程が繰り返されて、（真の最適解である保証はないが）解に到達する。形式的には、formula_1 を最小化すべき目的関数または最大化すべき適合度（フィットネス）関数とする。この関数は引数として実数値ベクトルで表された候補解を受け取り、その候補解の適合度を示す実数を出力する。その際に formula_2 の勾配は不明である。行いたいことは、探索空間におけるすべての点 formula_3 に対して formula_4 であるような解 formula_5、つまり大域的な最小点を見つけ出すことである。もしも最小化ではなくて最大化を行いたい場合には、formula_6 を考えればよい。formula_7 を集団における候補解（エージェント）とする。formula_8 を交叉率 ("crossover rate") とする。formula_9 をスケール因子 ("scaling factor" )とする。formula_10 を集団サイズとする。これらのパラメータは、formula_11 のもとで、計算を行なう者が決める（以下を参照）。DEアルゴリズムの基本的な流れは以下のとおりである。
パラメータ選択.
DEアルゴリズムのパラメータである formula_33 および formula_10 は最適化性能に大きな影響を与えうる。良い性能を引き出すようにDEパラメータを選ぶことが、多くの研究活動における主題となる。パラメータ選択として、正確ではないが大雑把な方法がStornら、LiuおよびLampienによって考案された。パラメータ選択に関する収束判定はZaharieによって行われている。DEパラメータのメタ最適化はPedersenおよびZhangらによって行われている。
亜種.
最適化パフォーマンスを改良すべく、DEアルゴリズムの多くの亜種が開発されている。上記で与えた基本アルゴリズムにおける交叉およびエージェントの変異方法を変更しても良い。
サンプルコード.
以下は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