diff options
Diffstat (limited to 'nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps')
4 files changed, 425 insertions, 0 deletions
diff --git a/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/DEPSAgent.java b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/DEPSAgent.java new file mode 100644 index 000000000..3a08df39f --- /dev/null +++ b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/DEPSAgent.java @@ -0,0 +1,128 @@ +package net.adaptivebox.deps; + +/** + * Description: The description of agent with hybrid differential evolution and particle swarm. + * + * @ Author Create/Modi Note + * Xiaofeng Xie Jun 10, 2004 + * Xiaofeng Xie Jul 01, 2008 + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * Please acknowledge the author(s) if you use this code in any way. + * + * @version 1.0 + * @Since MAOS1.0 + * + * @References: + * [1] Zhang W J, Xie X F. DEPSO: hybrid particle swarm with differential + * evolution operator. IEEE International Conference on Systems, Man & Cybernetics, + * Washington D C, USA, 2003: 3816-3821 + * [2] X F Xie, W J Zhang. SWAF: swarm algorithm framework for numerical + * optimization. Genetic and Evolutionary Computation Conference (GECCO), + * Seattle, WA, USA, 2004: 238-250 + * -> an agent perspective + */ + +import net.adaptivebox.deps.behavior.AbsGTBehavior; +import net.adaptivebox.deps.behavior.DEGTBehavior; +import net.adaptivebox.deps.behavior.PSGTBehavior; +import net.adaptivebox.global.RandomGenerator; +import net.adaptivebox.goodness.IGoodnessCompareEngine; +import net.adaptivebox.knowledge.ILibEngine; +import net.adaptivebox.knowledge.Library; +import net.adaptivebox.knowledge.SearchPoint; +import net.adaptivebox.problem.ProblemEncoder; +import net.adaptivebox.space.BasicPoint; + +public class DEPSAgent { + + // Describes the problem to be solved + private ProblemEncoder problemEncoder; + + // Forms the goodness landscape + private IGoodnessCompareEngine qualityComparator; + + // store the point that generated in current learning cycle + private SearchPoint trailPoint; + + // temp variable + private AbsGTBehavior selectGTBehavior; + + // the own memory: store the point that generated in old learning cycle + private BasicPoint pold_t; + + // the own memory: store the point that generated in last learning cycle + private BasicPoint pcurrent_t; + + // the own memory: store the personal best point + private SearchPoint pbest_t; + + // Generate-and-test behaviors. + private DEGTBehavior deGTBehavior; + private PSGTBehavior psGTBehavior; + + private double switchP = 0.5; + + public DEPSAgent(ProblemEncoder encoder, DEGTBehavior deGTBehavior, PSGTBehavior psGTBehavior, + double switchP, IGoodnessCompareEngine comparer, SearchPoint pbest) { + this.switchP = switchP; + + problemEncoder = encoder; + + qualityComparator = comparer; + + trailPoint = problemEncoder.getFreshSearchPoint(); + pold_t = problemEncoder.getFreshSearchPoint(); + pcurrent_t = problemEncoder.getFreshSearchPoint(); + pbest_t = pbest; + + this.deGTBehavior = deGTBehavior; + this.deGTBehavior.setMemPoints(pbest_t, pcurrent_t, pold_t); + + this.psGTBehavior = psGTBehavior; + this.psGTBehavior.setMemPoints(pbest_t, pcurrent_t, pold_t); + } + + public void setSpecComparator(IGoodnessCompareEngine comparer) { + qualityComparator = comparer; + } + + private AbsGTBehavior getGTBehavior() { + if (RandomGenerator.doubleZeroOneRandom() < switchP) { + return deGTBehavior; + } else { + return psGTBehavior; + } + } + + public void setGTBehavior(AbsGTBehavior gtBehavior) { + gtBehavior.setMemPoints(pbest_t, pcurrent_t, pold_t); + } + + public void generatePoint() { + // generates a new point in the search space (S) based on + // its memory and the library + selectGTBehavior = getGTBehavior(); + selectGTBehavior.generateBehavior(trailPoint, problemEncoder); + + // evaluate into goodness information + problemEncoder.evaluate(trailPoint); + } + + public void learn() { + selectGTBehavior.testBehavior(trailPoint, qualityComparator); + } + + public SearchPoint getMGState() { + return trailPoint; + } +} diff --git a/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/AbsGTBehavior.java b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/AbsGTBehavior.java new file mode 100644 index 000000000..2701c9dee --- /dev/null +++ b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/AbsGTBehavior.java @@ -0,0 +1,43 @@ +/** + * Description: The description of generate-and-test behavior. + * + * + * Author Create/Modi Note + * Xiaofeng Xie May 17, 2004 + * Xiaofeng Xie Jul 01, 2008 + * + * @version 1.0 + * @Since MAOS1.0 + * + * @References: + * [1] X F Xie, W J Zhang. SWAF: swarm algorithm framework for numerical + * optimization. Genetic and Evolutionary Computation Conference (GECCO), + * Seattle, WA, USA, 2004: 238-250 + * -> a generate-and-test behavior + */ +package net.adaptivebox.deps.behavior; + +import net.adaptivebox.goodness.IGoodnessCompareEngine; +import net.adaptivebox.knowledge.ILibEngine; +import net.adaptivebox.knowledge.Library; +import net.adaptivebox.knowledge.SearchPoint; +import net.adaptivebox.problem.ProblemEncoder; +import net.adaptivebox.space.BasicPoint; + +abstract public class AbsGTBehavior implements ILibEngine { + // The referred social library + protected Library socialLib; + + // the own memory: store the personal best point + protected SearchPoint pbest_t; + + public void setLibrary(Library lib) { + socialLib = lib; + } + + abstract public void setMemPoints(SearchPoint pbest, BasicPoint pcurrent, BasicPoint pold); + + abstract public void generateBehavior(SearchPoint trailPoint, ProblemEncoder problemEncoder); + + abstract public void testBehavior(SearchPoint trailPoint, IGoodnessCompareEngine qualityComparator); +} diff --git a/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/DEGTBehavior.java b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/DEGTBehavior.java new file mode 100644 index 000000000..c9ca0ef82 --- /dev/null +++ b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/DEGTBehavior.java @@ -0,0 +1,122 @@ +/** + * Description: The description of differential evolution Generate-and-Test Behavior. + + #Supported parameters: + NAME VALUE_type Range DefaultV Description + FACTOR real (0, 1.2] 0.5 DEAgent: scale constant + CR real [0, 1] 0.9 DEAgent: crossover constant + //Other choices for FACTOR and CR: (0.5, 0.1) + + * + * Author Create/Modi Note + * Xiaofeng Xie May 11, 2004 + * Xiaofeng Xie Jul 01, 2008 + * + * @version 1.0 + * @Since MAOS1.0 + * + * @References: + * [1] Storn R, Price K. Differential evolution - a simple and efficient + * heuristic for global optimization over continuous spaces. Journal of + * Global Optimization, 1997, 11: 341-359 + * The original differential evolution idea + * [2] X F Xie, W J Zhang. SWAF: swarm algorithm framework for numerical + * optimization. Genetic and Evolutionary Computation Conference (GECCO), + * Seattle, WA, USA, 2004: 238-250 + * -> a generate-and-test behavior + */ + +package net.adaptivebox.deps.behavior; + +import net.adaptivebox.global.RandomGenerator; +import net.adaptivebox.goodness.IGoodnessCompareEngine; +import net.adaptivebox.knowledge.Library; +import net.adaptivebox.knowledge.SearchPoint; +import net.adaptivebox.problem.ProblemEncoder; +import net.adaptivebox.space.BasicPoint; + +public class DEGTBehavior extends AbsGTBehavior { + //Number of differential vectors, normally be 1 or 2 + private static final int DVNum = 2; + + //scale constant: (0, 1.2], normally be 0.5 + public double MIN_FACTOR = 0.5; + + //scale constant: (0, 1.2], normally be 0.5 + public double MAX_FACTOR = 0.5; + + //crossover constant: [0, 1], normally be 0.1 or 0.9 + public double CR = 0.9; + + @Override + public void setMemPoints(SearchPoint pbest, BasicPoint pcurrent, BasicPoint pold) { + pbest_t = pbest; + } + + /** + * Crossover and mutation for a single vector element done in a single step. + * + * @param index Index of the trial vector element to be changed. + * @param trialVector Trial vector reference. + * @param globalVector Global best found vector reference. + * @param differenceVectors List of vectors used for difference delta + * calculation. + */ + private void crossoverAndMutation(int index, double trialVector[], double globalVector[], + BasicPoint differenceVectors[]) { + double delta = 0D; + + for (int i = 0; i < differenceVectors.length; i++) { + delta += (i % 2 == 0 ? +1D : -1D) * differenceVectors[i].getLocation()[index]; + } + + trialVector[index] = globalVector[index] + RandomGenerator.doubleRangeRandom(MIN_FACTOR, MAX_FACTOR) * delta; + } + + @Override + public void generateBehavior(SearchPoint trailPoint, ProblemEncoder problemEncoder) { + BasicPoint[] referPoints = getReferPoints(); + int DIMENSION = problemEncoder.getDesignSpace().getDimension(); + int guaranteeIndex = RandomGenerator.intRangeRandom(0, DIMENSION - 1); + + double[] trailVector = trailPoint.getLocation(); + double[] locaclVector = pbest_t.getLocation(); + double[] globalVector = socialLib.getGbest().getLocation(); + + /* Handle first part of the trial vector. */ + for (int index = 0; index < guaranteeIndex; index++) { + if (CR <= RandomGenerator.doubleZeroOneRandom()) { + trailVector[index] = locaclVector[index]; + continue; + } + + crossoverAndMutation(index, trailVector, globalVector, referPoints); + } + + /* Guarantee for at least one change in the trial vector. */ + crossoverAndMutation(guaranteeIndex, trailVector, globalVector, referPoints); + + /* Handle second part of the trial vector. */ + for (int index = guaranteeIndex + 1; index < DIMENSION; index++) { + if (CR <= RandomGenerator.doubleZeroOneRandom()) { + trailVector[index] = locaclVector[index]; + continue; + } + + crossoverAndMutation(index, trailVector, globalVector, referPoints); + } + } + + @Override + public void testBehavior(SearchPoint trailPoint, IGoodnessCompareEngine qualityComparator) { + Library.replace(qualityComparator, trailPoint, pbest_t); + } + + private SearchPoint[] getReferPoints() { + SearchPoint[] referPoints = new SearchPoint[DVNum * 2]; + for (int i = 0; i < referPoints.length; i++) { + referPoints[i] = socialLib.getRandomPoint(); + } + return referPoints; + } +} diff --git a/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/PSGTBehavior.java b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/PSGTBehavior.java new file mode 100644 index 000000000..68bf5a10e --- /dev/null +++ b/nlpsolver/ThirdParty/EvolutionarySolver/src/net/adaptivebox/deps/behavior/PSGTBehavior.java @@ -0,0 +1,132 @@ +/** + * Description: The description of particle swarm (PS) Generate-and-test Behavior. + * + #Supported parameters: + NAME VALUE_type Range DefaultV Description + c1 real [0, 2] 1.494 PSAgent: learning factor for pbest + c2 real [0, 2] 1.494 PSAgent: learning factor for gbest + w real [0, 1] 0.729 PSAgent: inertia weight + CL real [0, 0.1] 0 PSAgent: chaos factor + //Other choices for c1, c2, w, and CL: (2, 2, 0.4, 0.001) + + * Author Create/Modi Note + * Xiaofeng Xie May 11, 2004 + * Xiaofeng Xie Jul 01, 2008 + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * Please acknowledge the author(s) if you use this code in any way. + * + * @version 1.0 + * @Since MAOS1.0 + * + * References: + * [1] Kennedy J, Eberhart R C. Particle swarm optimization. IEEE Int. Conf. on + * Neural Networks, Perth, Australia, 1995: 1942-1948 + * For original particle swarm idea + * [2] Shi Y H, Eberhart R C. A Modified Particle Swarm Optimizer. IEEE Inter. Conf. + * on Evolutionary Computation, Anchorage, Alaska, 1998: 69-73 + * For the inertia weight: adjust the trade-off between exploitation & exploration + * [3] Clerc M, Kennedy J. The particle swarm - explosion, stability, and + * convergence in a multidimensional complex space. IEEE Trans. on Evolutionary + * Computation. 2002, 6 (1): 58-73 + * Constriction factor: ensures the convergence + * [4] Xie X F, Zhang W J, Yang Z L. A dissipative particle swarm optimization. + * Congress on Evolutionary Computation, Hawaii, USA, 2002: 1456-1461 + * The CL parameter + * [5] Xie X F, Zhang W J, Bi D C. Optimizing semiconductor devices by self- + * organizing particle swarm. Congress on Evolutionary Computation, Oregon, USA, + * 2004: 2017-2022 + * Further experimental analysis on the convergence of PSO + * [6] X F Xie, W J Zhang. SWAF: swarm algorithm framework for numerical + * optimization. Genetic and Evolutionary Computation Conference (GECCO), + * Seattle, WA, USA, 2004: 238-250 + * -> a generate-and-test behavior + * + */ + +package net.adaptivebox.deps.behavior; + +import net.adaptivebox.global.RandomGenerator; +import net.adaptivebox.goodness.IGoodnessCompareEngine; +import net.adaptivebox.knowledge.Library; +import net.adaptivebox.knowledge.SearchPoint; +import net.adaptivebox.problem.ProblemEncoder; +import net.adaptivebox.space.BasicPoint; +import net.adaptivebox.space.DesignSpace; + +public class PSGTBehavior extends AbsGTBehavior { + // Two normally choices for (c1, c2, weight), i.e., (2, 2, 0.4), or (1.494, + // 1.494, 0.729) The first is used in dissipative PSO (cf. [4]) as CL>0, and + // the second is achieved by using constriction factors (cf. [3]) + public double c1 = 2; + public double c2 = 2; + + //inertia weight + public double weight = 0.4; + + //See ref[4], normally be 0.001~0.005 + public double CL = 0; + + // the own memory: store the point that generated in old learning cycle + private BasicPoint pold_t; + + // the own memory: store the point that generated in last learning cycle + private BasicPoint pcurrent_t; + + @Override + public void setMemPoints(SearchPoint pbest, BasicPoint pcurrent, BasicPoint pold) { + pcurrent_t = pcurrent; + pbest_t = pbest; + pold_t = pold; + } + + @Override + public void generateBehavior(SearchPoint trailPoint, ProblemEncoder problemEncoder) { + DesignSpace designSpace = problemEncoder.getDesignSpace(); + + double[] pold_t_location = pold_t.getLocation(); + double[] pbest_t_location = pbest_t.getLocation(); + double[] pcurrent_t_location = pcurrent_t.getLocation(); + double[] gbest_t_location = socialLib.getGbest().getLocation(); + double[] trailPointLocation = trailPoint.getLocation(); + + int DIMENSION = designSpace.getDimension(); + for (int b = 0; b < DIMENSION; b++) { + if (RandomGenerator.doubleZeroOneRandom() < CL) { + designSpace.mutationAt(trailPointLocation, b); + continue; + } + + double deltaxb = weight * (pcurrent_t_location[b] - pold_t_location[b]) + + c1 * RandomGenerator.doubleZeroOneRandom() * (pbest_t_location[b] - pcurrent_t_location[b]) + + c2 * RandomGenerator.doubleZeroOneRandom() * (gbest_t_location[b] - pcurrent_t_location[b]); + + // limitation for delta_x + double deltaxbm = 0.5 * designSpace.getMagnitudeIn(b); + + if (deltaxb < -deltaxbm) { + deltaxb = -deltaxbm; + } else if (deltaxb > deltaxbm) { + deltaxb = deltaxbm; + } + + trailPointLocation[b] = pcurrent_t_location[b] + deltaxb; + } + } + + @Override + public void testBehavior(SearchPoint trailPoint, IGoodnessCompareEngine qualityComparator) { + Library.replace(qualityComparator, trailPoint, pbest_t); + pold_t.importLocation(pcurrent_t); + pcurrent_t.importLocation(trailPoint); + } +} |