diff options
author | Tomaž Vajngerl <tomaz.vajngerl@collabora.co.uk> | 2017-11-06 00:54:25 +0100 |
---|---|---|
committer | Tomaž Vajngerl <quikee@gmail.com> | 2017-11-18 01:16:20 +0100 |
commit | 08404bbb90a8978b70698ef057a4a46ad4fceae3 (patch) | |
tree | 035b124578957f69e31966263002e1751b1d45f0 /sccomp/source | |
parent | Update Tabbed Notebookbar remove placeholder img (diff) | |
download | core-08404bbb90a8978b70698ef057a4a46ad4fceae3.tar.gz core-08404bbb90a8978b70698ef057a4a46ad4fceae3.zip |
Swarm based (uses PSO or DE) experimental non-linear solver
This is a new, simple non-linear solver that uses a swarm
(population) to do global optimization. It uses two algoritms -
Particle Swarm Optimization (PSO) or Differential Evolution (DE)
to find a (non-optimal) solution.
It is experimental as not all functions are implemented and it
needs a lot more testing so that it performs well.
Change-Id: If55dad7eda17394851a9d178ad892de771eca7c9
Reviewed-on: https://gerrit.libreoffice.org/44382
Tested-by: Jenkins <ci@libreoffice.org>
Reviewed-by: Tomaž Vajngerl <quikee@gmail.com>
Diffstat (limited to 'sccomp/source')
-rw-r--r-- | sccomp/source/solver/DifferentialEvolution.hxx | 164 | ||||
-rw-r--r-- | sccomp/source/solver/ParticelSwarmOptimization.hxx | 178 | ||||
-rw-r--r-- | sccomp/source/solver/SwarmSolver.cxx | 591 | ||||
-rw-r--r-- | sccomp/source/solver/swarmsolver.component | 15 |
4 files changed, 948 insertions, 0 deletions
diff --git a/sccomp/source/solver/DifferentialEvolution.hxx b/sccomp/source/solver/DifferentialEvolution.hxx new file mode 100644 index 000000000000..7d37ef82b9f8 --- /dev/null +++ b/sccomp/source/solver/DifferentialEvolution.hxx @@ -0,0 +1,164 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + */ + +#ifndef INCLUDED_SCCOMP_SOURCE_DIFFERENTIALEVOLUTION_HXX +#define INCLUDED_SCCOMP_SOURCE_DIFFERENTIALEVOLUTION_HXX + +#include <vector> +#include <random> +#include <limits> + +struct Individual +{ + std::vector<double> mVariables; +}; + +template <typename DataProvider> class DifferentialEvolutionAlgorithm +{ + static constexpr double mnDifferentialWeight = 0.5; // [0, 2] + static constexpr double mnCrossoverProbability = 0.9; // [0, 1] + + static constexpr double constAcceptedPrecision = 0.000000001; + + DataProvider& mrDataProvider; + + size_t mnPopulationSize; + std::vector<Individual> maPopulation; + + std::random_device maRandomDevice; + std::mt19937 maGenerator; + size_t mnDimensionality; + + std::uniform_int_distribution<> maRandomPopulation; + std::uniform_int_distribution<> maRandomDimensionality; + std::uniform_real_distribution<> maRandom01; + + Individual maBestCandidate; + double mfBestFitness; + int mnGeneration; + int mnLastChange; + +public: + DifferentialEvolutionAlgorithm(DataProvider& rDataProvider, size_t nPopulationSize) + : mrDataProvider(rDataProvider) + , mnPopulationSize(nPopulationSize) + , maGenerator(maRandomDevice()) + , mnDimensionality(mrDataProvider.getDimensionality()) + , maRandomPopulation(0, mnPopulationSize - 1) + , maRandomDimensionality(0, mnDimensionality - 1) + , maRandom01(0.0, 1.0) + , mfBestFitness(std::numeric_limits<double>::lowest()) + , mnGeneration(0) + , mnLastChange(0) + { + } + + std::vector<double> const& getResult() { return maBestCandidate.mVariables; } + + int getGeneration() { return mnGeneration; } + + int getLastChange() { return mnLastChange; } + + void initialize() + { + mnGeneration = 0; + mnLastChange = 0; + maPopulation.clear(); + maBestCandidate.mVariables.clear(); + + // Initialize population with individuals that have been initialized with uniform random + // noise + // uniform noise means random value inside your search space + for (size_t i = 0; i < mnPopulationSize; ++i) + { + maPopulation.emplace_back(); + Individual& rIndividual = maPopulation.back(); + mrDataProvider.initializeVariables(rIndividual.mVariables, maGenerator); + } + } + + // Calculate one generation + bool next() + { + bool bBestChanged = false; + + for (size_t agentIndex = 0; agentIndex < mnPopulationSize; ++agentIndex) + { + // calculate new candidate solution + + // pick random point from population + size_t x = agentIndex; // randomPopulation(generator); + size_t a, b, c; + + // create a copy of choosen random agent in population + Individual& rOriginal = maPopulation[x]; + Individual aCandidate(rOriginal); + + // pick three different random points from population + do + { + a = maRandomPopulation(maGenerator); + } while (a == x); + + do + { + b = maRandomPopulation(maGenerator); + } while (b == x || b == a); + + do + { + c = maRandomPopulation(maGenerator); + + } while (c == x || c == a || c == b); + + size_t randomIndex = maRandomDimensionality(maGenerator); + + for (size_t index = 0; index < mnDimensionality; ++index) + { + double randomCrossoverProbability = maRandom01(maGenerator); + if (index == randomIndex || randomCrossoverProbability < mnCrossoverProbability) + { + double fVarA = maPopulation[a].mVariables[index]; + double fVarB = maPopulation[b].mVariables[index]; + double fVarC = maPopulation[c].mVariables[index]; + + double fNewValue = fVarA + mnDifferentialWeight * (fVarB - fVarC); + fNewValue = mrDataProvider.boundVariable(index, fNewValue); + aCandidate.mVariables[index] = fNewValue; + } + } + + double fCandidateFitness = mrDataProvider.calculateFitness(aCandidate.mVariables); + + // see if is better than original, if so replace + if (fCandidateFitness > mrDataProvider.calculateFitness(rOriginal.mVariables)) + { + maPopulation[x] = aCandidate; + + if (fCandidateFitness > mfBestFitness) + { + if (std::abs(fCandidateFitness - mfBestFitness) > constAcceptedPrecision) + { + bBestChanged = true; + mnLastChange = mnGeneration; + } + mfBestFitness = fCandidateFitness; + maBestCandidate = maPopulation[x]; + } + } + } + mnGeneration++; + return bBestChanged; + } +}; + +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/ParticelSwarmOptimization.hxx b/sccomp/source/solver/ParticelSwarmOptimization.hxx new file mode 100644 index 000000000000..6c820ab7978c --- /dev/null +++ b/sccomp/source/solver/ParticelSwarmOptimization.hxx @@ -0,0 +1,178 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + */ + +#ifndef INCLUDED_SCCOMP_SOURCE_PARTICLESWARM_HXX +#define INCLUDED_SCCOMP_SOURCE_PARTICLESWARM_HXX + +#include <vector> +#include <random> +#include <limits> + +struct Particle +{ + Particle(size_t nDimensionality) + : mVelocity(nDimensionality) + , mPosition(nDimensionality) + , mCurrentFitness(std::numeric_limits<float>::lowest()) + , mBestPosition(nDimensionality) + , mBestFitness(std::numeric_limits<float>::lowest()) + { + } + + std::vector<double> mVelocity; + + std::vector<double> mPosition; + double mCurrentFitness; + + std::vector<double> mBestPosition; + double mBestFitness; +}; + +template <typename DataProvider> class ParticleSwarmOptimizationAlgorithm +{ +private: + // inertia + static constexpr double constWeight = 0.729; + // cognitive coefficient + static constexpr double c1 = 1.49445; + // social coefficient + static constexpr double c2 = 1.49445; + + static constexpr double constAcceptedPrecision = 0.000000001; + + DataProvider& mrDataProvider; + + size_t mnNumOfParticles; + + std::vector<Particle> maSwarm; + + std::random_device maRandomDevice; + std::mt19937 maGenerator; + size_t mnDimensionality; + + std::uniform_real_distribution<> maRandom01; + + std::vector<double> maBestPosition; + double mfBestFitness; + int mnGeneration; + int mnLastChange; + +public: + ParticleSwarmOptimizationAlgorithm(DataProvider& rDataProvider, size_t nNumOfParticles) + : mrDataProvider(rDataProvider) + , mnNumOfParticles(nNumOfParticles) + , maGenerator(maRandomDevice()) + , mnDimensionality(mrDataProvider.getDimensionality()) + , maRandom01(0.0, 1.0) + , maBestPosition(mnDimensionality) + , mfBestFitness(std::numeric_limits<float>::lowest()) + , mnGeneration(0) + , mnLastChange(0) + { + } + + std::vector<double> const& getResult() { return maBestPosition; } + + int getGeneration() { return mnGeneration; } + + int getLastChange() { return mnLastChange; } + + void initialize() + { + mnGeneration = 0; + mnLastChange = 0; + maSwarm.clear(); + + mfBestFitness = std::numeric_limits<float>::lowest(); + + for (size_t i = 0; i < mnNumOfParticles; i++) + { + maSwarm.emplace_back(mnDimensionality); + Particle& rParticle = maSwarm.back(); + + mrDataProvider.initializeVariables(rParticle.mPosition, maGenerator); + mrDataProvider.initializeVariables(rParticle.mVelocity, maGenerator); + + for (size_t k = 0; k < mnDimensionality; k++) + { + rParticle.mPosition[k] = mrDataProvider.clampVariable(k, rParticle.mPosition[k]); + } + + rParticle.mCurrentFitness = mrDataProvider.calculateFitness(rParticle.mPosition); + + for (size_t k = 0; k < mnDimensionality; k++) + { + rParticle.mPosition[k] = mrDataProvider.clampVariable(k, rParticle.mPosition[k]); + } + + std::copy(rParticle.mPosition.begin(), rParticle.mPosition.end(), + rParticle.mBestPosition.begin()); + rParticle.mBestFitness = rParticle.mCurrentFitness; + + if (rParticle.mCurrentFitness > mfBestFitness) + { + mfBestFitness = rParticle.mCurrentFitness; + std::copy(rParticle.mPosition.begin(), rParticle.mPosition.end(), + maBestPosition.begin()); + } + } + } + + bool next() + { + bool bBestChanged = false; + + for (Particle& rParticle : maSwarm) + { + double fRandom1 = maRandom01(maGenerator); + double fRandom2 = maRandom01(maGenerator); + + for (size_t k = 0; k < mnDimensionality; k++) + { + rParticle.mVelocity[k] + = (constWeight * rParticle.mVelocity[k]) + + (c1 * fRandom1 * (rParticle.mBestPosition[k] - rParticle.mPosition[k])) + + (c2 * fRandom2 * (maBestPosition[k] - rParticle.mPosition[k])); + + mrDataProvider.clampVariable(k, rParticle.mVelocity[k]); + + rParticle.mPosition[k] += rParticle.mVelocity[k]; + rParticle.mPosition[k] = mrDataProvider.clampVariable(k, rParticle.mPosition[k]); + } + + rParticle.mCurrentFitness = mrDataProvider.calculateFitness(rParticle.mPosition); + + if (rParticle.mCurrentFitness > rParticle.mBestFitness) + { + rParticle.mBestFitness = rParticle.mCurrentFitness; + std::copy(rParticle.mPosition.begin(), rParticle.mPosition.end(), + rParticle.mBestPosition.begin()); + } + + if (rParticle.mCurrentFitness > mfBestFitness) + { + if (std::abs(rParticle.mCurrentFitness - mfBestFitness) > constAcceptedPrecision) + { + bBestChanged = true; + mnLastChange = mnGeneration; + } + std::copy(rParticle.mPosition.begin(), rParticle.mPosition.end(), + maBestPosition.begin()); + mfBestFitness = rParticle.mCurrentFitness; + } + } + mnGeneration++; + return bBestChanged; + } +}; + +#endif + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/SwarmSolver.cxx b/sccomp/source/solver/SwarmSolver.cxx new file mode 100644 index 000000000000..809ebb4fde96 --- /dev/null +++ b/sccomp/source/solver/SwarmSolver.cxx @@ -0,0 +1,591 @@ +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */ +/* + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + */ + +#include <sal/config.h> +#include <config_lgpl.h> + +#include <com/sun/star/frame/XModel.hpp> +#include <com/sun/star/uno/XComponentContext.hpp> +#include <com/sun/star/container/XIndexAccess.hpp> +#include <com/sun/star/sheet/XSpreadsheetDocument.hpp> +#include <com/sun/star/sheet/XSpreadsheet.hpp> +#include <com/sun/star/sheet/XSolver.hpp> +#include <com/sun/star/sheet/XSolverDescription.hpp> +#include <com/sun/star/table/CellAddress.hpp> +#include <com/sun/star/table/CellContentType.hpp> +#include <com/sun/star/table/XCell.hpp> +#include <com/sun/star/lang/XServiceInfo.hpp> + +#include <rtl/math.hxx> +#include <cppuhelper/implbase.hxx> +#include <cppuhelper/supportsservice.hxx> + +#include <comphelper/broadcasthelper.hxx> +#include <comphelper/propertycontainer.hxx> +#include <comphelper/proparrhlp.hxx> + +#include <vector> +#include <limits> +#include <chrono> +#include <random> +#include <o3tl/make_unique.hxx> + +#include <unotools/resmgr.hxx> + +#include "DifferentialEvolution.hxx" +#include "ParticelSwarmOptimization.hxx" + +#include <strings.hrc> + +using namespace css; + +namespace +{ + +struct Bound +{ + double lower; + double upper; + + Bound() + // float bounds should be low/high enough for all practical uses + // otherwise we are too far away from the solution + : lower(std::numeric_limits<float>::lowest()) + , upper(std::numeric_limits<float>::max()) + { + } + + void updateBound(sheet::SolverConstraintOperator eOp, double fValue) + { + if (eOp == sheet::SolverConstraintOperator_LESS_EQUAL) + { + // if we set the bound multiple times use the one which includes both values + // for example bound values 100, 120, 150 -> use 100 -> the lowest one + if (fValue < upper) + upper = fValue; + } + else if (eOp == sheet::SolverConstraintOperator_GREATER_EQUAL) + { + if (fValue > lower) + lower = fValue; + } + else if (eOp == sheet::SolverConstraintOperator_EQUAL) + { + lower = fValue; + upper = fValue; + } + } +}; + +enum +{ + PROP_NONNEGATIVE, + PROP_INTEGER, + PROP_TIMEOUT, + PROP_ALGORITHM, +}; + +} // end anonymous namespace + +typedef cppu::WeakImplHelper<sheet::XSolver, sheet::XSolverDescription, lang::XServiceInfo> + SwarmSolver_Base; + +class SwarmSolver : public comphelper::OMutexAndBroadcastHelper, + public comphelper::OPropertyContainer, + public comphelper::OPropertyArrayUsageHelper<SwarmSolver>, + public SwarmSolver_Base +{ +private: + uno::Reference<sheet::XSpreadsheetDocument> mxDocument; + table::CellAddress maObjective; + uno::Sequence<table::CellAddress> maVariables; + uno::Sequence<sheet::SolverConstraint> maConstraints; + bool mbMaximize; + + // set via XPropertySet + bool mbNonNegative; + bool mbInteger; + sal_Int32 mnTimeout; + sal_Int32 mnAlgorithm; + + // results + bool mbSuccess; + double mfResultValue; + + uno::Sequence<double> maSolution; + OUString maStatus; + + std::vector<Bound> maBounds; + std::vector<sheet::SolverConstraint> maNonBoundedConstraints; + +private: + static OUString getResourceString(const char* pId); + + uno::Reference<table::XCell> getCell(const table::CellAddress& rPosition); + void setValue(const table::CellAddress& rPosition, double fValue); + double getValue(const table::CellAddress& rPosition); + +public: + SwarmSolver() + : OPropertyContainer(GetBroadcastHelper()) + , mbMaximize(true) + , mbNonNegative(false) + , mbInteger(false) + , mnTimeout(60000) + , mnAlgorithm(0) + , mbSuccess(false) + , mfResultValue(0.0) + { + registerProperty("NonNegative", PROP_NONNEGATIVE, 0, &mbNonNegative, + cppu::UnoType<decltype(mbNonNegative)>::get()); + registerProperty("Integer", PROP_INTEGER, 0, &mbInteger, + cppu::UnoType<decltype(mbInteger)>::get()); + registerProperty("Timeout", PROP_TIMEOUT, 0, &mnTimeout, + cppu::UnoType<decltype(mnTimeout)>::get()); + registerProperty("Algorithm", PROP_ALGORITHM, 0, &mnAlgorithm, + cppu::UnoType<decltype(mnAlgorithm)>::get()); + } + + DECLARE_XINTERFACE() + DECLARE_XTYPEPROVIDER() + + virtual uno::Reference<beans::XPropertySetInfo> SAL_CALL getPropertySetInfo() override + { + return createPropertySetInfo(getInfoHelper()); + } + // OPropertySetHelper + virtual cppu::IPropertyArrayHelper& SAL_CALL getInfoHelper() override + { + return *getArrayHelper(); + } + // OPropertyArrayUsageHelper + virtual cppu::IPropertyArrayHelper* createArrayHelper() const override + { + uno::Sequence<beans::Property> aProperties; + describeProperties(aProperties); + return new cppu::OPropertyArrayHelper(aProperties); + } + + // XSolver + virtual uno::Reference<sheet::XSpreadsheetDocument> SAL_CALL getDocument() override + { + return mxDocument; + } + virtual void SAL_CALL + setDocument(const uno::Reference<sheet::XSpreadsheetDocument>& rDocument) override + { + mxDocument = rDocument; + } + + virtual table::CellAddress SAL_CALL getObjective() override { return maObjective; } + virtual void SAL_CALL setObjective(const table::CellAddress& rObjective) override + { + maObjective = rObjective; + } + + virtual uno::Sequence<table::CellAddress> SAL_CALL getVariables() override + { + return maVariables; + } + virtual void SAL_CALL setVariables(const uno::Sequence<table::CellAddress>& rVariables) override + { + maVariables = rVariables; + } + + virtual uno::Sequence<sheet::SolverConstraint> SAL_CALL getConstraints() override + { + return maConstraints; + } + virtual void SAL_CALL + setConstraints(const uno::Sequence<sheet::SolverConstraint>& rConstraints) override + { + maConstraints = rConstraints; + } + + virtual sal_Bool SAL_CALL getMaximize() override { return mbMaximize; } + virtual void SAL_CALL setMaximize(sal_Bool bMaximize) override { mbMaximize = bMaximize; } + + virtual sal_Bool SAL_CALL getSuccess() override { return mbSuccess; } + virtual double SAL_CALL getResultValue() override { return mfResultValue; } + + virtual uno::Sequence<double> SAL_CALL getSolution() override { return maSolution; } + + virtual void SAL_CALL solve() override; + + // XSolverDescription + virtual OUString SAL_CALL getComponentDescription() override + { + return SwarmSolver::getResourceString(RID_SWARM_SOLVER_COMPONENT); + } + + virtual OUString SAL_CALL getStatusDescription() override { return maStatus; } + + virtual OUString SAL_CALL getPropertyDescription(const OUString& rPropertyName) override + { + const char* pResId = nullptr; + switch (getInfoHelper().getHandleByName(rPropertyName)) + { + case PROP_NONNEGATIVE: + pResId = RID_PROPERTY_NONNEGATIVE; + break; + case PROP_INTEGER: + pResId = RID_PROPERTY_INTEGER; + break; + case PROP_TIMEOUT: + pResId = RID_PROPERTY_TIMEOUT; + break; + case PROP_ALGORITHM: + pResId = RID_PROPERTY_ALGORITHM; + break; + default: + break; + } + return SwarmSolver::getResourceString(pResId); + } + + // XServiceInfo + virtual OUString SAL_CALL getImplementationName() override + { + return OUString("com.sun.star.comp.Calc.SwarmSolver"); + } + + sal_Bool SAL_CALL supportsService(const OUString& rServiceName) override + { + return cppu::supportsService(this, rServiceName); + } + + uno::Sequence<OUString> SAL_CALL getSupportedServiceNames() override + { + uno::Sequence<OUString> aServiceNames{ "com.sun.star.sheet.Solver" }; + return aServiceNames; + } + +private: + void applyVariables(std::vector<double> const& rVariables); + bool doesViolateConstraints(); + +public: + double calculateFitness(std::vector<double> const& rVariables); + size_t getDimensionality(); + void initializeVariables(std::vector<double>& rVariables, std::mt19937& rGenerator); + double clampVariable(size_t nVarIndex, double fValue); + double boundVariable(size_t nVarIndex, double fValue); +}; + +OUString SwarmSolver::getResourceString(const char* pId) +{ + OUString sString; + if (!pId) + return sString; + + static std::locale aLocale = Translate::Create("scc"); + return Translate::get(pId, aLocale); +} + +uno::Reference<table::XCell> SwarmSolver::getCell(const table::CellAddress& rPosition) +{ + uno::Reference<container::XIndexAccess> xSheets(mxDocument->getSheets(), uno::UNO_QUERY); + uno::Reference<sheet::XSpreadsheet> xSheet(xSheets->getByIndex(rPosition.Sheet), + uno::UNO_QUERY); + return xSheet->getCellByPosition(rPosition.Column, rPosition.Row); +} + +void SwarmSolver::setValue(const table::CellAddress& rPosition, double fValue) +{ + getCell(rPosition)->setValue(fValue); +} + +double SwarmSolver::getValue(const table::CellAddress& rPosition) +{ + return getCell(rPosition)->getValue(); +} + +IMPLEMENT_FORWARD_XINTERFACE2(SwarmSolver, SwarmSolver_Base, OPropertyContainer) +IMPLEMENT_FORWARD_XTYPEPROVIDER2(SwarmSolver, SwarmSolver_Base, OPropertyContainer) + +void SwarmSolver::applyVariables(std::vector<double> const& rVariables) +{ + for (sal_Int32 i = 0; i < maVariables.getLength(); ++i) + { + setValue(maVariables[i], rVariables[i]); + } +} + +double SwarmSolver::calculateFitness(std::vector<double> const& rVariables) +{ + applyVariables(rVariables); + + if (doesViolateConstraints()) + return std::numeric_limits<float>::lowest(); + + double x = getValue(maObjective); + + if (mbMaximize) + return x; + else + return -x; +} + +void SwarmSolver::initializeVariables(std::vector<double>& rVariables, std::mt19937& rGenerator) +{ + int nTry = 1; + bool bConstraintsOK = false; + + while (!bConstraintsOK && nTry < 10) + { + size_t noVariables(maVariables.getLength()); + + rVariables.resize(noVariables); + + for (size_t i = 0; i < noVariables; ++i) + { + Bound const& rBound = maBounds[i]; + if (mbInteger) + { + sal_Int64 intLower(rBound.lower); + sal_Int64 intUpper(rBound.upper); + std::uniform_int_distribution<sal_Int64> random(intLower, intUpper); + rVariables[i] = double(random(rGenerator)); + } + else + { + std::uniform_real_distribution<double> random(rBound.lower, rBound.upper); + rVariables[i] = random(rGenerator); + } + } + + applyVariables(rVariables); + + bConstraintsOK = !doesViolateConstraints(); + nTry++; + } +} + +double SwarmSolver::clampVariable(size_t nVarIndex, double fValue) +{ + Bound const& rBound = maBounds[nVarIndex]; + double fResult = std::max(std::min(fValue, rBound.upper), rBound.lower); + + if (mbInteger) + return sal_Int64(fResult); + + return fResult; +} + +double SwarmSolver::boundVariable(size_t nVarIndex, double fValue) +{ + Bound const& rBound = maBounds[nVarIndex]; + // double fResult = std::max(std::min(fValue, rBound.upper), rBound.lower); + double fResult = fValue; + while (fResult < rBound.lower || fResult > rBound.upper) + { + if (fResult < rBound.lower) + fResult = rBound.upper - (rBound.lower - fResult); + if (fResult > rBound.upper) + fResult = (fResult - rBound.upper) + rBound.lower; + } + + if (mbInteger) + return sal_Int64(fResult); + + return fResult; +} + +size_t SwarmSolver::getDimensionality() { return maVariables.getLength(); } + +bool SwarmSolver::doesViolateConstraints() +{ + for (sheet::SolverConstraint& rConstraint : maNonBoundedConstraints) + { + double fLeftValue = getValue(rConstraint.Left); + double fRightValue = 0.0; + + table::CellAddress aCellAddress; + + if (rConstraint.Right >>= aCellAddress) + { + fRightValue = getValue(aCellAddress); + } + else if (rConstraint.Right >>= fRightValue) + { + // empty + } + else + { + return false; + } + + sheet::SolverConstraintOperator eOp = rConstraint.Operator; + switch (eOp) + { + case sheet::SolverConstraintOperator_LESS_EQUAL: + { + if (fLeftValue > fRightValue) + return true; + } + break; + case sheet::SolverConstraintOperator_GREATER_EQUAL: + { + if (fLeftValue < fRightValue) + return true; + } + break; + case sheet::SolverConstraintOperator_EQUAL: + { + if (!rtl::math::approxEqual(fLeftValue, fRightValue)) + return true; + } + break; + default: + break; + } + } + return false; +} + +template <typename SwarmAlgorithm> class SwarmRunner +{ +private: + SwarmAlgorithm& mrAlgorithm; + double mfTimeout; + + static constexpr size_t mnPopulationSize = 40; + static constexpr int constNumberOfGenerationsWithoutChange = 50; + + std::chrono::high_resolution_clock::time_point maStart; + std::chrono::high_resolution_clock::time_point maEnd; + +public: + SwarmRunner(SwarmAlgorithm& rAlgorithm) + : mrAlgorithm(rAlgorithm) + , mfTimeout(5000) + { + } + + void setTimeout(double fTimeout) + { + mfTimeout = fTimeout; + } + + std::vector<double> const& solve() + { + using std::chrono::duration_cast; + using std::chrono::milliseconds; + using std::chrono::high_resolution_clock; + + mrAlgorithm.initialize(); + + maEnd = maStart = high_resolution_clock::now(); + + int nLastChange = 0; + + while ((mrAlgorithm.getGeneration() - nLastChange) < constNumberOfGenerationsWithoutChange + && duration_cast<milliseconds>(maEnd - maStart).count() < mfTimeout) + { + bool bChange = mrAlgorithm.next(); + + if (bChange) + nLastChange = mrAlgorithm.getGeneration(); + + maEnd = high_resolution_clock::now(); + } + return mrAlgorithm.getResult(); + } +}; + +void SAL_CALL SwarmSolver::solve() +{ + uno::Reference<frame::XModel> xModel(mxDocument, uno::UNO_QUERY_THROW); + + maStatus.clear(); + mbSuccess = false; + + maBounds.resize(maVariables.getLength()); + + xModel->lockControllers(); + + if (mbNonNegative) + { + for (Bound& rBound : maBounds) + rBound.lower = 0; + } + + // Determine variable bounds + for (sheet::SolverConstraint const& rConstraint : maConstraints) + { + table::CellAddress aLeftCellAddress = rConstraint.Left; + sheet::SolverConstraintOperator eOp = rConstraint.Operator; + + size_t index = 0; + bool bFoundVariable = false; + for (table::CellAddress& rVariableCell : maVariables) + { + if (aLeftCellAddress == rVariableCell) + { + bFoundVariable = true; + table::CellAddress aCellAddress; + double fValue; + + if (rConstraint.Right >>= aCellAddress) + { + uno::Reference<table::XCell> xCell = getCell(aCellAddress); + if (xCell->getType() == table::CellContentType_VALUE) + { + maBounds[index].updateBound(eOp, xCell->getValue()); + } + else + { + maNonBoundedConstraints.push_back(rConstraint); + } + } + else if (rConstraint.Right >>= fValue) + { + maBounds[index].updateBound(eOp, fValue); + } + } + index++; + } + if (!bFoundVariable) + maNonBoundedConstraints.push_back(rConstraint); + } + + std::vector<double> aSolution; + + if (mnAlgorithm == 0) + { + DifferentialEvolutionAlgorithm<SwarmSolver> aDE(*this, 50); + SwarmRunner<DifferentialEvolutionAlgorithm<SwarmSolver>> aEvolution(aDE); + aEvolution.setTimeout(mnTimeout); + aSolution = aEvolution.solve(); + } + else + { + ParticleSwarmOptimizationAlgorithm<SwarmSolver> aPSO(*this, 100); + SwarmRunner<ParticleSwarmOptimizationAlgorithm<SwarmSolver>> aSwarmSolver(aPSO); + aSwarmSolver.setTimeout(mnTimeout); + aSolution = aSwarmSolver.solve(); + } + + xModel->unlockControllers(); + + mbSuccess = true; + + maSolution.realloc(aSolution.size()); + std::copy(aSolution.begin(), aSolution.end(), maSolution.begin()); +} + +extern "C" SAL_DLLPUBLIC_EXPORT uno::XInterface* SAL_CALL +com_sun_star_comp_Calc_SwarmSolver_get_implementation(uno::XComponentContext*, + uno::Sequence<uno::Any> const&) +{ + return cppu::acquire(new SwarmSolver()); +} + +/* vim:set shiftwidth=4 softtabstop=4 expandtab: */ diff --git a/sccomp/source/solver/swarmsolver.component b/sccomp/source/solver/swarmsolver.component new file mode 100644 index 000000000000..0cdd925ee9fd --- /dev/null +++ b/sccomp/source/solver/swarmsolver.component @@ -0,0 +1,15 @@ +<?xml version="1.0" encoding="UTF-8"?> +<!-- + * This file is part of the LibreOffice project. + * + * This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. + --> + +<component loader="com.sun.star.loader.SharedLibrary" environment="@CPPU_ENV@" + xmlns="http://openoffice.org/2010/uno-components"> + <implementation name="com.sun.star.comp.Calc.SwarmSolver" constructor="com_sun_star_comp_Calc_SwarmSolver_get_implementation"> + <service name="com.sun.star.sheet.Solver"/> + </implementation> +</component> |