Beispiel für Partikelschwarmoptimierung in Java @ tutorials.de: Tutorials, Forum & Hilfe

**Thomas Darimont** · 14.02.11 23:33

Hallo,

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

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

Code 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) {
            // [url]http://www.iwi.uni-hannover.de/cms/files/doko06/vortrag_brodersen.pdf[/url]
            // 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

tut orials.de	tut verbinden	tut dir helfen	tut kooperieren
©2000-2012 tutorials.de Alle Rechte vorbehalten	tut informieren » Impressum » Nutzungsregeln » Netiquette » Team » Redaktion	» Tutorials » Videotutorials » Showroom » Events & Contests » Chat » RSS-Feed » Blogs	» der-webdesigner.net » DesignerInAction » Design Nation » Directorforum » Flashhilfe » PHP-Resource » PHPwelt » PSD-Tutorials

Themen-Optionen

Anzeige

Ähnliche Themen

Kleines Beispiel zur Verwendung der Derby DB in Java 6

Kleines Beispiel zum Thema Java 3D

Beispiel Java NIO

Consumer Producer Beispiel mit Java 5.0

Side für Beispiel-Java-Applikationen?

E-Mail:

Abonnieren Abbestellen