Beispiel für Partikelschwarmoptimierung in Java

Thomas Darimont

Erfahrenes Mitglied
Hallo,

hier mal ein kleines Beispiel zur Implementierung eines Partikelschwarmoptimierers in Java.
Siehe auch: http://en.wikipedia.org/wiki/Particle_swarm_optimization

Die @Getter / @Setter / @Data Annotations kommen von http://projectlombok.org/

Java:
package de.tutorials.algorithms.ai.swarm;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Random;
import java.util.Set;

import lombok.Data;
import lombok.Getter;
import lombok.Setter;

public class ParticleSwarmExample {
	public static void main(String[] args) {
		IProblemSolver solver = new SwarmOptimizer();

		Problem problem = new Problem("Foxholes", 2) {
			// http://www.iwi.uni-hannover.de/cms/files/doko06/vortrag_brodersen.pdf
			// Page 19

			@Override
			public Constraints getPositionConstraints() {
				return new Constraints(new Constraint(-65536, 65536), new Constraint(-65536, 65536));
			}

			@Override
			public Constraints getVelocityConstraints() {
				return new Constraints(new Constraint(0.00001, 1000), new Constraint(0.00001, 1000));
			}

			double[][] a = {
					{ -32, -16, 0, 16, 32, -32, -16, 0, 16, 32, -32, -16, 0, 16, 32, -32, -16, 0, 16, 32, -32, -16, 0, 16, 32 },
					{ -32, -32, -32, -32, -32, -16, -16, -16, -16, -16, 0, 0, 0, 0, 0, 16, 16, 16, 16, 16, 32, 32, 32, 32, 32 } };

			public double evaluate(Particle current) {

				double f = 0.002;

				for (int j = 0; j < 25; j++) {
					double fj = j;
					for (int i = 0; i < 2; i++) {
						fj += Math.pow(current.getPosition()[i] - a[i][j], 6);
					}
					f += 1.0 / fj;
				}

				return f;
			}
		};

		Solution solution = solver.solve(problem);
		System.out.println(solution);
	}

	static interface IProblemSolver {
		Solution solve(Problem problem);
	}

	public static interface ISwarmOptimizer extends IProblemSolver {
		Particle optimize(Swarm swarm);
	}

	public static interface IParticleEvaluator {
		double evaluate(Particle current);
	}

	public static interface IParticleVelocityAdjuster {
		void adjustVelocity(Particle particle, Swarm swarm,	Constraints velocityConstraints);
	}

	public static interface IRestrictionHandler {
		void restrict(Particle particle, int dimension, Constraint constraint);
	}

	@Data
	public static class DefaultVelocityAdjuster implements IParticleVelocityAdjuster {
		protected double inertia = 0.995;
		protected double cognitiveBehavior = 0.95;
		protected double socialBehavior = 0.9;

		public void adjustVelocity(Particle particle, Swarm swarm, Constraints velocityConstraints) {
			Particle bestNeighbour = getBestNeighbour(particle, swarm);

			double[] vel = particle.getVelocity();
			double[] pos = particle.getPosition();
			double[] persBestPos = particle.getPersonalBestPosition();
			double[] bestNeighPos = bestNeighbour.getPosition();

			for (int i = 0, dims = particle.getDimensions(); i < dims; i++) {
				double dvCurrent = vel[i] * inertia;
				double dvCognitive = cognitiveBehavior * (persBestPos[i] - pos[i]);
				double dvSocial = socialBehavior * (bestNeighPos[i] - pos[i]);
				double newVelocity = dvCurrent + dvCognitive + dvSocial;
				vel[i] = velocityConstraints.get(i).restrict(newVelocity);
			}
		}

		protected Particle getBestNeighbour(Particle particle, Swarm swarm) {
			Particle bestNeighbour = particle;
			for (Particle n : swarm.getNeighbours(particle)) {
				if (n.getScore() > bestNeighbour.getScore()) {
					bestNeighbour = n;
				}
			}
			return bestNeighbour;
		}
	}

	public static class BouncingRestrictionHandler implements IRestrictionHandler {
		public void restrict(Particle particle, int dimension, Constraint constraint) {
			double[] position = particle.getPosition();
			int result = constraint.fulfilled(position[dimension]);
			if (result != 0) {
				position[dimension] = result == -1 ? constraint.getMin() : constraint.getMax();
				particle.invertDirection(dimension);
			}
		}
	}

	public static class StickRestrictionHandler implements IRestrictionHandler {

		public void restrict(Particle particle, int dimension, Constraint constraint) {
			double[] position = particle.getPosition();
			int result = constraint.fulfilled(position[dimension]);
			if (result != 0) {
				position[dimension] = result > 0 ? constraint.getMax() : constraint.getMin();
			}
		}
	}

	public static class WrapRestrictionHandler implements IRestrictionHandler {

		public void restrict(Particle particle, int dimension, Constraint constraint) {
			double[] position = particle.getPosition();
			int result = constraint.fulfilled(position[dimension]);
			if (result != 0) {
				position[dimension] = result > 0 ? constraint.getMin()
						+ (position[dimension] - constraint.getMax())
						: constraint.getMax() - (constraint.getMin() - position[dimension]);
			}
		}
	}

	@Getter
	@Setter
	public static class SwarmOptimizer implements ISwarmOptimizer {
		protected Random rnd = new Random();

		protected int maxNeighbourCount = 75;
		protected int populationSize = 800;
		protected int maxIterations = 500;
		protected int maxIterationsWithNoImprovement = 200;

		protected int dimensions;
		protected Constraints positionConstraints;
		protected Constraints velocityConstraints;

		protected IParticleEvaluator particleEvaluator;
		protected IParticleVelocityAdjuster velocityAdjuster;
		protected IRestrictionHandler restrictionHandler;

		public Solution solve(Problem problem) {
			init(problem);
			Swarm swarm = newSwarm();
			Particle solution = optimize(swarm);
			return problem.solved(solution);
		}

		protected Swarm newSwarm() {
			return new Swarm(maxNeighbourCount);
		}

		public Particle optimize(Swarm swarm) {
			populate(swarm);

			int itersWithoutImprovement = 0;
			for (int iter = 0; iter < maxIterations; iter++) {

				double improvement = updateBest(swarm);
				if (Double.compare(0.0, improvement) == 0) {
					itersWithoutImprovement = 0;
				} else {
					itersWithoutImprovement++;
				}

				if (itersWithoutImprovement >= maxIterationsWithNoImprovement) {
					System.out.println("Aborting optimization. No improvements for " + itersWithoutImprovement + " iterations");
					break;
				}

				move(swarm);

				System.out.println("Current best: " + swarm.getBest() + " improvement: " + improvement);

			}
			Particle best = swarm.getBest();
			return best;
		}

		protected void move(Swarm swarm) {
			updateVelocities(swarm);
			updatePositions(swarm);
		}

		protected void init(Problem problem) {
			this.dimensions = problem.getDimensions();

			if (this.particleEvaluator == null) {
				this.particleEvaluator = problem;
			}

			if (positionConstraints == null) {
				this.positionConstraints = problem.getPositionConstraints();
			}

			if (velocityConstraints == null) {
				this.velocityConstraints = problem.getVelocityConstraints();
			}

			if (velocityAdjuster == null) {
				this.velocityAdjuster = new DefaultVelocityAdjuster();
			}

			if (restrictionHandler == null) {
				// this.restrictionHandler = new BouncingRestrictionHandler();
				this.restrictionHandler = new StickRestrictionHandler();
				// this.restrictionHandler = new WrapRestrictionHandler();
			}
		}

		protected void updateVelocities(Swarm swarm) {
			for (Particle particle : swarm) {
				velocityAdjuster.adjustVelocity(particle, swarm, velocityConstraints);
			}
		}

		protected void updatePositions(Swarm swarm) {
			for (Particle particle : swarm) {
				particle.move();
				restrict(particle);
			}
		}

		protected void restrict(Particle particle) {
			for (int dimension = 0, dims = particle.getDimensions(); dimension < dims; dimension++) {
				Constraint constraint = positionConstraints.get(dimension);
				restrictionHandler.restrict(particle, dimension, constraint);
			}
		}

		protected double updateBest(Swarm swarm) {
			double improvment = 0.0;
			Particle best = swarm.getBest();
			for (Particle current : swarm) {
				double score = computeScore(current);
				if (score >= best.getScore()) {
					improvment = current.getScore() - best.getScore();
					swarm.setBest(current.clone());
				}
			}
			return improvment;
		}

		protected double computeScore(Particle current) {
			double score = particleEvaluator.evaluate(current);
			current.setScore(score);
			return score;
		}

		protected void populate(Swarm swarm) {
			for (int i = 0; i < populationSize; i++) {
				Particle particle = new Particle(generateRandomPosition(), generateRandomVelocity());
				swarm.add(particle);
			}
			swarm.setBest(new Particle(new double[dimensions], new double[dimensions]));
		}

		protected double[] generateRandomPosition() {
			return generateRandomValues(positionConstraints);
		}

		protected double[] generateRandomValues(Constraints constraints) {
			double[] value = new double[dimensions];
			for (int i = 0; i < dimensions; i++) {
				Constraint constraint = constraints.get(i);
				value[i] = constraint.getMin()
						+ (constraint.getMax() - constraint.getMin())
						* rnd.nextDouble();
			}
			return value;
		}

		protected double[] generateRandomVelocity() {
			return generateRandomValues(velocityConstraints);
		}
	}

	@Getter
	@Setter
	public static class Swarm implements Iterable<Particle> {
		protected Particle best;
		protected int maxNeighbourCount;
		protected IdentityHashMap<Particle, Set<Particle>> neighbours;

		protected List<Particle> members = new ArrayList<Particle>();

		public Swarm(int maxNeighbourCount) {
			this.maxNeighbourCount = maxNeighbourCount;
		}

		public void add(Particle particle) {
			members.add(particle);
		}

		public Iterable<Particle> getNeighbours(Particle particle) {
			if (neighbours == null) {
				computeNeighbours();
			}
			return neighbours.get(particle);
		}

		private void computeNeighbours() {
			Random rnd = new Random();
			neighbours = new IdentityHashMap<Particle, Set<Particle>>();
			for (Particle p : members) {
				Set<Particle> neighbourParticles = new HashSet<Particle>();
				int count = rnd.nextInt(maxNeighbourCount);
				for (int i = 0; i < count; i++) {
					int idx = rnd.nextInt(members.size());
					neighbourParticles.add(members.get(idx));
				}
				neighbours.put(p, neighbourParticles);
			}
		}

		public Iterator<Particle> iterator() {
			return members.iterator();
		}
	}

	@Getter
	@Setter
	public static class Particle implements Cloneable {
		protected final double[] velocity;
		protected final double[] position;
		protected double[] personalBestPosition;
		protected double score = Double.NEGATIVE_INFINITY;

		public Particle(double[] position, double[] velocity) {
			this.position = position;
			this.velocity = velocity;
		}

		public int getDimensions() {
			return position.length;
		}

		public void setScore(double score) {
			if (score >= this.score) {
				this.personalBestPosition = position.clone();
			}
			this.score = score;
		}

		public void setPosition(int dimension, double posi) {
			this.position[dimension] = posi;
		}

		public void invertDirection(int dimension) {
			this.velocity[dimension] *= -1.0;
		}

		public void move() {
			for (int dimension = 0; dimension < position.length; dimension++) {
				position[dimension] += velocity[dimension];
			}
		}

		public Particle clone() {
			Particle clone = new Particle(position.clone(), velocity.clone());
			clone.setScore(score);
			return clone;
		}

		@Override
		public String toString() {
			return toText(true);
		}

		protected String toText(boolean includeVelocities) {
			StringBuilder sb = new StringBuilder();

			DecimalFormat dfPos = new DecimalFormat("0.0000");
			DecimalFormat dfVel = new DecimalFormat("0.0000");
			DecimalFormat dfScore = new DecimalFormat("0.0000E0");

			sb.append("{");
			for (int i = 0; i < position.length; i++) {
				sb.append(i).append(": ").append(dfPos.format(position[i]));
				if (includeVelocities) {
					sb.append("(Velocity: ").append(dfVel.format(velocity[i])).append(") ");
				}
			}
			sb.append("} Score=").append(dfScore.format(score));

			return sb.toString();
		}
	}

	@Data
	public abstract static class Problem implements IParticleEvaluator {
		protected final int dimensions;
		protected double epsilon = 0.000001;
		protected Constraints positionConstraints;
		protected Constraints velocityConstraints;
		protected Solution solution;
		protected String title;

		public Problem(String title, int dimensions) {
			this.title = title;
			this.dimensions = dimensions;
			this.velocityConstraints = new Constraints(new Constraint(epsilon,2.0), dimensions);
		}

		public Solution solved(Particle best) {
			return new Solution(this, best) {
				@Override
				public String toString() {
					return problem.title + " " + particle.toText(false);
				}
			};
		}
	}

	@Data
	public static abstract class Solution {
		protected final Particle particle;
		protected final Problem problem;

		public Solution(Problem problem, Particle particle) {
			this.problem = problem;
			this.particle = particle;
		}
	}

	@Data
	public static class Constraint {
		final double min;
		final double max;

		public int fulfilled(double value) {
			int result;

			if (value >= min) {
				if (value <= max) {
					result = 0; // yes
				} else {
					result = 1; // no, too high
				}
			} else {
				result = -1; // no, too low
			}

			return result;
		}

		public double restrict(double newVelocity) {
			double v = Math.abs(newVelocity);
			v = Math.max(min, v);
			v = Math.min(max, v);
			return Math.signum(newVelocity) * v;
		}
	}

	@Data
	public static class Constraints {
		final Constraint[] constraints;

		public Constraints(Constraint... constraints) {
			this.constraints = constraints;
		}

		public Constraints(Constraint constraint, int dimensions) {
			this.constraints = new Constraint[dimensions];
			Arrays.fill(this.constraints, constraint);
		}

		public Constraint get(int index) {
			return constraints[index];
		}
	}
}

Ausgabe:
Code:
Current best: {0: -30300,3397(Velocity: 310,8899) 1: 21221,7693(Velocity: 801,7998) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -29991,0042(Velocity: 309,3355) 1: 22019,5602(Velocity: 797,7908) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -29683,2154(Velocity: 307,7888) 1: 22813,3621(Velocity: 793,8019) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -29376,9656(Velocity: 306,2499) 1: 23603,1950(Velocity: 789,8329) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -29072,2470(Velocity: 304,7186) 1: 24389,0787(Velocity: 785,8837) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -28769,0519(Velocity: 303,1950) 1: 25171,0330(Velocity: 781,9543) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -28467,3729(Velocity: 301,6790) 1: 25949,0775(Velocity: 778,0445) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -28167,2023(Velocity: 300,1706) 1: 26723,2318(Velocity: 774,1543) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -27868,5325(Velocity: 298,6698) 1: 27493,5153(Velocity: 770,2835) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -27571,3560(Velocity: 297,1764) 1: 28259,9475(Velocity: 766,4321) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -27275,6655(Velocity: 295,6906) 1: 29022,5474(Velocity: 762,6000) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -26981,4534(Velocity: 294,2121) 1: 29781,3344(Velocity: 758,7870) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -26688,7123(Velocity: 292,7410) 1: 30536,3274(Velocity: 754,9930) } Score=2,0000E-3 improvement: 0.0
Current best: {0: -26397,4350(Velocity: 291,2773) 1: 31287,5455(Velocity: 751,2181) } Score=2,0000E-3 improvement: 0.0
....
Current best: {0: -32,0000(Velocity: 0,0000) 1: -32,0000(Velocity: 0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: -0,0000) 1: -32,0000(Velocity: -0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: -0,0000) 1: -32,0000(Velocity: -0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: 0,0000) 1: -32,0000(Velocity: 0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: 0,0000) 1: -32,0000(Velocity: 0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: -0,0000) 1: -32,0000(Velocity: -0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: -0,0000) 1: -32,0000(Velocity: -0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: 0,0000) 1: -32,0000(Velocity: 0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: 0,0000) 1: -32,0000(Velocity: 0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: -0,0000) 1: -32,0000(Velocity: -0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: -0,0000) 1: -32,0000(Velocity: -0,0000) } Score=1,8233E48 improvement: 0.0
Current best: {0: -32,0000(Velocity: 0,0000) 1: -32,0000(Velocity: 0,0000) } Score=1,8233E48 improvement: 0.0
Foxholes {0: -32,00001: -32,0000} Score=1,8233E48

Gruß Tom
 
Zurück