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/
Ausgabe:
Gruß Tom
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