使用JMetal解决分配优化问题

遗传算法是一种基于自然选择和遗传学原理的优化算法，也很适合解决任务分配问题, 比如达到任务总耗时最短, 比如再兼顾每个工人工作量相对均衡.
下面代码中 TaskAssignmentProblem(单目标优化) 和 BalancedTaskAssignmentProblem(多目标优化) .

package com.example;

import java.util.ArrayList;
import java.util.List;

import org.uma.jmetal.algorithm.Algorithm;
import org.uma.jmetal.algorithm.examples.AlgorithmRunner;
import org.uma.jmetal.algorithm.multiobjective.nsgaii.NSGAIIBuilder;
import org.uma.jmetal.operator.crossover.impl.IntegerSBXCrossover;
import org.uma.jmetal.operator.mutation.impl.IntegerPolynomialMutation;
import org.uma.jmetal.operator.selection.SelectionOperator;
import org.uma.jmetal.operator.selection.impl.BinaryTournamentSelection;
import org.uma.jmetal.problem.Problem;
import org.uma.jmetal.problem.integerproblem.impl.AbstractIntegerProblem;
import org.uma.jmetal.solution.integersolution.IntegerSolution;
import org.uma.jmetal.util.AbstractAlgorithmRunner;
import org.uma.jmetal.util.JMetalLogger;
import org.uma.jmetal.util.fileoutput.SolutionListOutput;
import org.uma.jmetal.util.fileoutput.impl.DefaultFileOutputContext;

public class App {

	public static void main(String[] args) {
		// 1. 定义问题
		Problem<IntegerSolution> problem = null;
		//problem = new TaskAssignmentProblem();
		problem = new  BalancedTaskAssignmentProblem();

		// 2. 设置交叉和变异算子 和 设置选择算子

		// 定义交叉操作: SBX交叉
		double crossoverProbability = 0.9;
		double crossoverDistributionIndex = 20.0;
		var crossover = new IntegerSBXCrossover(crossoverProbability, crossoverDistributionIndex);

		// 定义变异操作: 多项式变异
		double mutationProbability = 1.0 / problem.numberOfVariables();
		double mutationDistributionIndex = 20.0;
		var mutation = new IntegerPolynomialMutation(mutationProbability, mutationDistributionIndex);

		// 定义选择操作: 二元竞标赛选择
		SelectionOperator<List<IntegerSolution>, IntegerSolution> selection = new BinaryTournamentSelection<IntegerSolution>();

		// 3. 迭代次数和种群大小
		int populationSize = 100;

		// 4. 定义算法（NSGA-II）	
		Algorithm<List<IntegerSolution>> algorithm = new NSGAIIBuilder<IntegerSolution>(problem, crossover, mutation,
				populationSize)
				.setSelectionOperator(selection)
				.setMaxEvaluations(25000)
				.build();

		// 5. 运行算法
		AlgorithmRunner algorithmRunner = new AlgorithmRunner.Executor(algorithm).execute();
		List<IntegerSolution> solutionSet = algorithm.result();

		long computingTime = algorithmRunner.getComputingTime();
		JMetalLogger.logger.info("Total execution time: " + computingTime + "ms");

		// 6. 打印非支配排序结果,每个solution包含决策变量取值和目标函数取值.
		for (IntegerSolution solution : solutionSet) {
			JMetalLogger.logger.info("Solution: " + solution);
		}
		JMetalLogger.logger.info("Solution Count: " + solutionSet.size());

		// 7. save to tsv files
		new SolutionListOutput(solutionSet).setVarFileOutputContext(new DefaultFileOutputContext("VAR.csv", ","))
				.setFunFileOutputContext(new DefaultFileOutputContext("FUN.csv", ",")).print();
		AbstractAlgorithmRunner.printFinalSolutionSet(solutionSet);
	}

}

/*
 * 有4个任务需要3个工人完成, 需要找出最节省时间的任务分配方式.
 * 目标函数一个, 即所有任务总计耗时
 * 每个任务由哪个worker完成, 即决策变量, 所以共有4个变量,  变量的取值为 workerId, 范围从0~3 
 * 
 *  任务和工人的时间Cost矩阵如下: 
 * 
 * 任务 工人A 工人B 工人C
 * 任务A 2 3 1
 * 任务B 4 2 3
 * 任务C 3 4 2
 * 任务D 1 2 4
 */
class TaskAssignmentProblem extends AbstractIntegerProblem {
	private int evaluationCount;

	private static final int NUMBER_OF_TASK = 4;
	private static final int[][] COMPLETION_TIMES = {
			{ 2, 3, 1 },
			{ 4, 2, 3 },
			{ 3, 4, 2 },
			{ 1, 2, 4 },
	};

	public TaskAssignmentProblem() {
		numberOfObjectives(1);
		name("TaskAssignmentProblem");

		// 4 varabiles for 4 tasks
		var lowerList = new ArrayList<Integer>();
		lowerList.add(0); // workerId lower value
		lowerList.add(0); // workerId lower value
		lowerList.add(0); // workerId lower value
		lowerList.add(0); // workerId lower value
		var upperList = new ArrayList<Integer>();
		upperList.add(2); // workerId upper value
		upperList.add(2); // workerId upper value
		upperList.add(2); // workerId upper value
		upperList.add(2); // workerId upper value

		variableBounds(lowerList, upperList);
	}

	@Override
	public IntegerSolution evaluate(IntegerSolution solution) {
		int totalTime = 0;
		for (int i = 0; i < NUMBER_OF_TASK; i++) {
			var workerId = solution.variables().get(i);
			totalTime += COMPLETION_TIMES[i][workerId];
		}
		solution.objectives()[0] = totalTime;
		return solution;
	}
}




/*
 * 有4个任务需要3个工人完成, 需要找出最节省时间的任务分配方式, 同时要求每个人的工作量尽量平衡
 * 目标函数2个, (1)所有任务总计耗时最小, (2)每个人总耗时最小, 即最忙的那个人耗时最小
 * 每个任务由哪个worker完成, 即决策变量, 所以共有4个变量,  变量的取值为 workerId, 范围从0~3 
 * 
 *  任务和工人的时间Cost矩阵如下: 
 * 
 * 任务 工人A 工人B 工人C
 * 任务A 3 2 4
 * 任务B 5 4 3
 * 任务C 2 3 2
 * 任务D 1 4 2
 */
class BalancedTaskAssignmentProblem extends AbstractIntegerProblem {
	private int evaluationCount;

	private static final int NUMBER_OF_TASK = 4;
	private static final int NUMBER_OF_WORKER = 3;
	private static final int[][] COMPLETION_TIMES = {
			{ 3, 2, 4 },
			{ 5, 4, 3 },
			{ 2, 3, 2 },
			{ 1, 4, 2 },
	};

	public BalancedTaskAssignmentProblem() {
		numberOfObjectives(2);
		name("TaskAssignmentProblem");

		// 4 varabiles for 4 tasks
		var lowerList = new ArrayList<Integer>();
		lowerList.add(0); // workerId lower value
		lowerList.add(0); // workerId lower value
		lowerList.add(0); // workerId lower value
		lowerList.add(0); // workerId lower value
		var upperList = new ArrayList<Integer>();
		upperList.add(2); // workerId upper value
		upperList.add(2); // workerId upper value
		upperList.add(2); // workerId upper value
		upperList.add(2); // workerId upper value

		variableBounds(lowerList, upperList);
	}

	@Override
	public IntegerSolution evaluate(IntegerSolution solution) {
		int totalTime = 0;
		int[] workerTime= new int[NUMBER_OF_WORKER] ;

		//目标函数: 总耗时最小
		for (int i = 0; i < NUMBER_OF_TASK; i++) {
			var workerId = solution.variables().get(i);
			totalTime += COMPLETION_TIMES[i][workerId];
			workerTime[workerId]+=COMPLETION_TIMES[i][workerId];
		}
		solution.objectives()[0] = totalTime;

		//目标函数:每个人总耗时最小
		int maxTime=0 ;
		for (int time : workerTime) {
			if (maxTime<time){
				maxTime=time;
			}
		}
		solution.objectives()[1]=maxTime;
		return solution;
	}
}