差分进化算法(Differential Evolution) JAVA代码样例

柔情只为你懂 2022-10-01 00:47 168阅读 0赞

差分进化算法（Differential Evolution）是一个经典的智能优化算法。虽然其很难得到最优解，但是差分进化算法可以在有限的资源与时间能寻得次优解。将差分进化算法应用到参数寻优上往往可以获得意想不到的结果。

差分进化的百度百科： http://baike.baidu.com/item/%E5%B7%AE%E5%88%86%E8%BF%9B%E5%8C%96/10072496?fr=aladdin

差分进化的维基百科（含有伪代码）： https://en.wikipedia.org/wiki/Differential\_evolution

差分进化算法实现简单，主要分为：“突变”、“交叉”、以及“选择”三个步骤，下面给出简单的JAVA代码，以供参考。

import java.util.*;
    
    /**
     * There steps in differential evolution:
     * 		1. mutation
     * 		2. cross
     * 		3. selection
     * 
     * @author JunH (email: junh_cs@126.com)
     *
     */
    public class DifferentialEvolution4SeachParam {
    	private int population_size;
    	private int iter_num;
    	private int param_num;
    	private double param_bottom_bound;
    	private double param_upper_bound;
    	private double F = 0.5; 		// mutation factor [0, 1], range from 0 to 1
    	private double CR = 0.5; 		// cross rate (0, 1)
    	
    	// tmp
    	private double[][] population;
    	private double[] scores;
    	private Random rand;
    	
    	// output
    	private double[] final_individual;
    	
    	public static void main(String[] args) {
    		DifferentialEvolution4SeachParam de = new DifferentialEvolution4SeachParam(10, 500, 5, -1, 1);
    		double[] params = de.getTheFinalParams();
    		
    		System.out.println();
    		for (int j = 0; j < params.length-1; j++)
    			System.out.print(params[j]+", ");
    		System.out.println(params[params.length-1]+")");
    		System.out.println("HAVE A GOOD DAY!");
    	}
    	
    	public DifferentialEvolution4SeachParam(int population_size, int iter_num, 
    			int param_num, double param_bottom_bound, double param_upper_bound){
    		this.population_size = population_size;
    		this.iter_num = iter_num;
    		this.param_num = param_num;
    		this.param_bottom_bound = param_bottom_bound;
    		this.param_upper_bound = param_upper_bound;
    		
    		final_individual = run();
    	}
    	
    	public double[] getTheFinalParams(){
    		return final_individual;
    	}
    	
    	private double[] run(){
    		this.init();
    		
    		double[] final_best_individual = null;
    		for (int iter = 0; iter < iter_num; iter++){
    			double[][] mutated_population = this.mutate();
    			double[][] crossed_population = this.cross(mutated_population);
    			this.select(crossed_population);
    		
    			int[] index = insertDescendSortIndex(scores, 1);
    			
    			StringBuffer sb = new StringBuffer();
    			sb.append("The "+(iter+1)+"-th iter's score is "+scores[index[0]]+" (");
    			for (int j = 0; j < param_num-1; j++)
    				sb.append(this.population[index[0]][j]+", ");
    			sb.append(this.population[index[0]][param_num-1]+")");
    			
    			System.out.println(sb.toString());
    			
    			final_best_individual = this.population[index[0]];
    		}
    		
    		return final_best_individual;
    	}
    	
    	private int[] insertDescendSortIndex(final double[] arr, int sortTopN){
    		int[] indexes = new int[arr.length];
    		for (int i = 0; i < indexes.length; i++)
    			indexes[i] = i;
    		
    		for (int i = 1; i < indexes.length; i++){
    			for (int j = 0; j < i && j < sortTopN; j++){
    				if (arr[indexes[i]] > arr[indexes[j]]){
    					int tmp = indexes[i];
    					indexes[i] = indexes[j];
    					indexes[j] = tmp;
    				}
    			}
    		}
    		
    		if (indexes.length > sortTopN){
    			int[] ans = new int[sortTopN];
    			for (int i = 0; i < sortTopN; i++){
    				ans[i] = indexes[i];
    			}
    			
    			return ans;
    		}
    		
    		return indexes;
    	}
    	
    	private void init(){
    		rand = new Random(new Date().getTime());
    		
    		population = new double[population_size][param_num];
    		scores = new double[population_size];
    		for (int i = 0; i < population_size; i++){
    			for (int j = 0; j < param_num; j++){
    				population[i][j] = param_bottom_bound + rand.nextDouble() * (param_upper_bound - param_bottom_bound);
    			}
    			
    			scores[i] = scorefunc(population[i]);
    		}
    	}
    	
    	private double[][] mutate(){
    		double[][] mutated_population = new double[population_size][param_num];
    		for (int i = 0; i < population_size; i++){
    			int ind1 = rand.nextInt(population_size);
    			int ind2 = rand.nextInt(population_size);
    			int ind3 = rand.nextInt(population_size);
    			while (ind1 == i || ind2 == i || ind3 == i 
    					|| ind1 == ind2 || ind1 == ind3 || ind2 == ind3){
    				ind1 = rand.nextInt(population_size);
    				ind2 = rand.nextInt(population_size);
    				ind3 = rand.nextInt(population_size);
    			}
    					
    			for (int j = 0; j < param_num; j++){
    				mutated_population[i][j] = population[ind1][j] + F * (population[ind2][j] - population[ind3][j]); 
    			}
    		}
    		
    		return mutated_population;
    	}
    	
    	private double[][] cross(double[][] mutated_population){
    		double[][] crossed_population = new double[population_size][param_num];
    		for (int i = 0; i < population_size; i++){
    			int Jrand = rand.nextInt(param_num);
    			for (int j = 0; j < param_num; j++){
    				if (j == Jrand || rand.nextDouble() < CR)
    					crossed_population[i][j] = mutated_population[i][j];
    				else crossed_population[i][j] = population[i][j];
    				
    				if (crossed_population[i][j] > this.param_upper_bound 
    						|| crossed_population[i][j] < this.param_bottom_bound){
    					crossed_population[i][j] = param_bottom_bound + rand.nextDouble() * (param_upper_bound - param_bottom_bound);
    				}
    			}
    		}
    		
    		return crossed_population;
    	}
    	
    	private void select(double[][] crossed_population){
    		for (int i = 0; i < population_size; i++){
    			double new_sco = scorefunc(crossed_population[i]);
    			if (new_sco > scores[i]){
    				population[i] = crossed_population[i];
    				scores[i] = new_sco;
    			}
    		}
    	}
    	
    	private double scorefunc(double[] individual){	// TODO the higher, the better.
    		double sco = 0.0;
    		for (int i = 0; i < param_num; i++)
    			sco += individual[i];
    		
    		return sco;
    	}
    }