samchon::example::tsp Namespace Reference

Traveling Salesman Problem Solver. More...

Classes
struct	GAParameters
	Parameters for Genetic-Algorithm. More...
class	GeometryPoint
	A geometry coordinates (point) More...
class	Scheduler
	A scheduler. More...
class	Travel
	Represent a travel containning Point(s) More...

Detailed Description

Traveling Salesman Problem Solver.

Module tsp deducts an optimal traveling scheduel by genetic algorithm.

The tsp module is built for providing guidance of using entity and genetic algorithm module.

Example Sources

Scheduler.hpp

#pragma once
#include <samchon/protocol/Entity.hpp>
#include <samchon/example/tsp/Travel.hpp>

#include <samchon/library/GeneticAlgorithm.hpp>

#include <iostream>
#include <Windows.h>

namespace samchon
{
namespace example
{
namespace tsp
{
    using namespace std;

    using namespace library;
    using namespace protocol;

    struct GAParameters
    {
        double mutationRate;
        size_t tournament;

        size_t population;
        size_t generation;
    };

    class Scheduler
        : public Entity
    {
    private:
        typedef Entity super;

    protected:
        shared_ptr<Travel> travel;

        struct GAParameters gaParameters;

    public:
        /* -----------------------------------------------------------
            CONSTRUCTORS
        ----------------------------------------------------------- */
        Scheduler()
            : super()
        {
            this->travel = make_shared<Travel>();
            this->gaParameters = {.03, 50, 100, 300};
        };

        Scheduler(shared_ptr<Travel> travel, const struct GAParameters &gaParameteres)
            : super()
        {
            this->travel = travel;
            this->gaParameters = gaParameteres;
        };

        virtual ~Scheduler() = default;

        virtual void construct(shared_ptr<XML> xml) override
        {
            super::construct(xml);
            gaParameters.mutationRate = xml->getProperty<double>("mutationRate");
            gaParameters.tournament = xml->getProperty<size_t>("tournament");
            gaParameters.population = xml->getProperty<size_t>("population");
            gaParameters.generation = xml->getProperty<size_t>("generation");

            travel->construct(xml->get(travel->TAG())->at(0));
        };

        /* -----------------------------------------------------------
            CALCULATORS
        ----------------------------------------------------------- */
        auto optimize() -> shared_ptr<Travel>
        {
            GeneticAlgorithm<Travel> geneticAlgorithm
                (
                    true,
                    gaParameters.mutationRate,
                    gaParameters.tournament
                );

            travel = 
                geneticAlgorithm.evolveGeneArray
                (
                    travel, 
                    gaParameters.population, 
                    gaParameters.generation
                );

            return travel;
        };

        auto calcDistance() const -> double
        {
            return travel->calcDistance();
        };

        /* -----------------------------------------------------------
            EXPORTER
        ----------------------------------------------------------- */
        virtual auto TAG() const -> string override
        {
            return "scheduler";
        };

        virtual auto toXML() const -> shared_ptr<XML> override
        {
            shared_ptr<XML> &xml = super::toXML();
            xml->setProperty("mutationRate", gaParameters.mutationRate);
            xml->setProperty("tournament", gaParameters.tournament);
            xml->setProperty("population", gaParameters.population);
            xml->setProperty("generation", gaParameters.generation);

            xml->push_back(travel->toXML());
            return xml;
        };

        auto toString() const -> string
        {
            return travel->toString();
        };

        /* -----------------------------------------------------------
            MAIN
        ----------------------------------------------------------- */
        static void main()
        {
            shared_ptr<Travel> travel = make_shared<Travel>();
            for(int i = 0; i < 30; i++)
                travel->emplace_back(new GeometryPoint(i + 1));

            // OPTIMIZING
            struct GAParameters gaParameters = {.03, 30, 400, 400};

            Scheduler scheduler(travel, gaParameters);
            travel = scheduler.optimize();

            // PRINTING
            string &str = travel->toString();

            toClipboard(str);
            cout << str << endl;
        };

    private:
        static void toClipboard(const string &str)
        {
        #if defined(_WINDOWS) || defined(_WIN32) || defined(_WIN64)
            OpenClipboard(0);
            EmptyClipboard();
            HGLOBAL hg = GlobalAlloc(GMEM_MOVEABLE, str.size());

            if (!hg)
            {
                CloseClipboard();
                return;
            }
            memcpy(GlobalLock(hg), str.c_str(), str.size());

            GlobalUnlock(hg);
            SetClipboardData(CF_TEXT, hg);
            CloseClipboard();
            GlobalFree(hg);
        #endif
        };
    };          
};
};
};

Travel.hpp

#pragma once
#include <samchon/protocol/SharedEntityArray.hpp>
#include <samchon/example/tsp/GeometryPoint.hpp>

namespace samchon
{
namespace example
{
namespace tsp
{
    using namespace std;

    using namespace library;
    using namespace protocol;

    class Travel
        : public SharedEntityArray<GeometryPoint>
    {
    private:
        typedef SharedEntityArray<GeometryPoint> super;

    protected:
        double distance;

    public:
        /* -----------------------------------------------------------
            CONSTRUCTORS
        ----------------------------------------------------------- */
        Travel()
            : super()
        {
            distance = INT_MIN;
        };

        Travel(const Travel &travel)
            : super(travel)
        {
            distance = INT_MIN;
        };

        Travel(Travel &&travel)
            : super(move(travel))
        {
            distance = travel.distance;
        };

        virtual ~Travel() = default;

        virtual void construct(shared_ptr<XML> xml) override
        {
            super::construct(xml);

            if (xml->hasProperty("distance") == true)
                distance = xml->getProperty<double>("distance");
            else
                distance = INT_MIN;
        };

    protected:
        virtual auto createChild(shared_ptr<XML>) -> GeometryPoint*
        {
            return new GeometryPoint();
        };

        /* -----------------------------------------------------------
            CALCULATORS
        ----------------------------------------------------------- */
    public:
        auto calcDistance() const -> double
        {
            if(this->distance != INT_MIN)
                return this->distance;

            double distance = 0.0;
            for(size_t i = 1; i < size(); i++)
                distance += at(i-1)->calcDistance(*at(i));

            ((Travel*)this)->distance = distance;
            return distance;
        };

    public:
        auto operator<(const Travel &travel) const -> bool
        {
            return this->calcDistance() < travel.calcDistance();
        };

        /* -----------------------------------------------------------
            EXPORTER
        ----------------------------------------------------------- */
        virtual auto TAG() const -> string override
        {
            return "travel";
        };
        virtual auto CHILD_TAG() const -> string override
        {
            return "point";
        };

        virtual auto toXML() const -> shared_ptr<XML> override
        {
            shared_ptr<XML> &xml = super::toXML();
            if (distance != INT_MIN)
                xml->setProperty("distance", distance);

            return xml;
        };

        auto toString() const -> string
        {
            string str =
                "Distance: " + StringUtil::numberFormat(calcDistance()) + " km\n" + 
                "uid    longitude   latitude\n";

            for(size_t i = 0; i < size(); i++)
                str += at(i)->toString() + "\n";

            return str;
        };
    };          
};
};
};

GeometryPoint.hpp

#pragma once
#include <samchon/protocol/Entity.hpp>

#include <random>
#include <cmath>
#include <samchon/library/Math.hpp>
#include <samchon/library/StringUtil.hpp>
#include <samchon/library/XML.hpp>

namespace samchon
{
namespace example
{
namespace tsp
{
    using namespace std;

    using namespace library;
    using namespace protocol;

    class GeometryPoint
        : public Entity
    {
    private:
        typedef Entity super;

    protected:
        int uid;

        double longitude;

        double latitude;

    public:
        /* -----------------------------------------------------------
            CONSTRUCTORS
        ----------------------------------------------------------- */
        GeometryPoint()
            : super()
        {
        };

        GeometryPoint(int uid)
            : super()
        {
            this->uid = uid;

            this->longitude = Math::random() * 180.0;
            this->latitude = Math::random() * 180 - 90.0;
        };

        GeometryPoint(int uid, double longitude, double latitude)
            : super()
        {
            this->uid = uid;
            this->longitude = longitude;
            this->latitude = latitude;
        };

        virtual ~GeometryPoint() = default;

        virtual void construct(shared_ptr<XML> xml) override
        {
            uid = xml->getProperty<int>("uid");
            longitude = xml->getProperty<double>("longitude");
            latitude = xml->getProperty<double>("latitude");
        };

        /* -----------------------------------------------------------
            GETTERS
        ----------------------------------------------------------- */
        virtual auto key() const -> string override
        {
            return to_string(uid);
        };

        auto calcDistance(const GeometryPoint &point) const -> double
        {
            if (longitude == point.longitude && latitude == point.latitude)
                return 0.0;

            double latitude_radian1 = Math::degree_to_radian(this->latitude);
            double latitude_radian2 = Math::degree_to_radian(point.latitude);
            double theta = this->longitude - point.longitude;

            double val =
                sin(latitude_radian1) * sin(latitude_radian2)
                + cos(latitude_radian1) * cos(latitude_radian2) * cos(Math::degree_to_radian(theta));

            val = acos(val);
            val = Math::radian_to_degree(val);
            val = val * 60 * 1.1515;
            val = val * 1.609344;

            return val;
        };

        /* -----------------------------------------------------------
            EXPORTER
        ----------------------------------------------------------- */
        virtual auto TAG() const -> string
        {
            return "point";
        };

        auto toXML() const -> shared_ptr<XML> override
        {
            shared_ptr<XML> &xml = super::toXML();
            xml->setProperty("uid", uid);
            xml->setProperty("longitude", longitude);
            xml->setProperty("latitude", latitude);

            return xml;
        };

        auto toString() const -> string
        {
            return StringUtil::substitute
                (
                    "{1}\t{2}\t{3}",
                    uid, longitude, latitude
                );
        };
    };          
};
};
};

Result of the example

See also

protocol::Entity

library::GeneticAlgorithm

Author

Jeongho Nam http://samchon.org