tsp_heuristics::TwoOpt Class Reference
TwoOpt Heuristic for the Knapsack Problem. Tries to insert each item in the knapsack while there is room for more items. More...
#include <TwoOpt.h>
Inheritance diagram for tsp_heuristics::TwoOpt:
Public Member Functions | |
| TwoOpt (const bool randomInit=true) | |
| void | run () override |
| The TwoOpt heuristic gradually constructs a tour by repeatedly selecting the shortest edge and adding it to the tour as long as it doesn’t create a cycle with less than N edges, or increases the degree of any node to more than 2. We must not add the same edge twice of course. | |
| string | getName () const |
| Returns the name of the algorithm, this is used in the to_json method. Must be implemented in the subclasses. More... | |
| string | getID () const |
| Returns the identificator of the algorithm, this is used in the to_json method. Must be implemented in the subclasses. It should return the acronym of useful id for a particular configuration. More... | |
| void | setProblem (shared_ptr< TSP > prob) |
| void | setProblem (TSP *prob) |
| Front< IntFloatSolution > | getResults () const override |
| Returns a Front object with all the solutions of the evolutionary process. This method must be implemented in the subclasses. More... | |
 Public Member Functions inherited from Heuristic< IntFloatSolution > | |
| virtual json | to_json () const |
| Returns the JSON representation of the Heuristic. More... | |
| Public Member Functions inherited from AbstractEA< S > | |
| AbstractEA () | |
| Construct a new Abstract EA object with default parameter values. More... | |
| AbstractEA (const int &maxEvals, const int &popsize) | |
| AbstractEA constructor which initialises the parameters maxEvalautions and populationSize. More... | |
| AbstractEA (unique_ptr< PopulationEvaluator< S >>, const int &maxEvals, const int &popsize) | |
| AbstractEA constructor which initialises the parameters maxEvalautions, the populationSize and the evaluator approach. More... | |
| int | getPopulationSize () const |
| Get the population size. More... | |
| void | setPopulationSize (int pSize) |
| Setter to update the population size. More... | |
| double | getElapsedTime () const |
| Get the elapsed time of the evolutionary process. More... | |
| const vector< S > & | getPopulation () const |
| Gets a reference of the population. More... | |
| int | getMaxEvaluations () const |
| Get the maximum number of evaluations to perform. More... | |
| void | setMaxEvaluations (int maxEval) |
| Set a new maximum number of evaluations to perform. More... | |
| const Problem< S > * | getProblem () const |
| Gets a pointer to the problem which is being solved. More... | |
| virtual void | setProblem (shared_ptr< Problem< S >> prob) |
| Set the new problem to solve. Uses a shared_ptr pointer which updates the reference counter. Does no take the ownership. More... | |
| virtual void | setProblem (Problem< S > *prob) |
| Set the new problem to solve. Uses a raw pointer and takes the ownership of the object. More... | |
| PopulationEvaluator< S > * | getEvaluator () const |
| Gets a pointer to the population evaluator system. More... | |
| void | setEvaluator (unique_ptr< PopulationEvaluator< S >> eval) |
| Updates the population evaluator system with the unique_ptr. The method takes the ownership of the object behind. More... | |
| int | getPerformedEvaluations () const |
| Get the performed evaluations. More... | |
| void | setPerformedEvaluations (int pEvals) |
| Set the Performed Evaluations. Useful for the updateProgress method. More... | |
| void | setPopulation (const vector< S > &pop) |
| Set the Population. More... | |
| virtual Evolution< S > | getEvolution () const |
| Get the Evolution data. More... | |
| int | getPrintingInterval () const |
| Get the interval of checkpoints. More... | |
Additional Inherited Members | |
| Static Public Attributes inherited from AbstractEA< S > | |
| static const int | DEFAULT_POPULATION_SIZE = 100 |
| Default population size equal to 100 individuals. More... | |
| static const int | DEFAULT_EVALUATIONS_LIMIT = 100000 |
| Default evaluation limit equal to 100000 evaluations. More... | |
| static const std::string | NAME = "Algorithm" |
| static const std::string | MAX_EVALUATIONS = "Max Evaluations" |
| static const std::string | POP_SIZE = "Population Size" |
| static const std::string | ELAPSED_TIME = "Elapsed Time" |
| static const std::string | EVALUATOR = "Evaluator" |
| static const int | EVOLUTION_SIZE = 10 |
| Protected Member Functions inherited from Heuristic< IntFloatSolution > | |
| virtual void | initProgress () |
| Not implemented. Nothing really to do here. | |
| virtual void | updateProgress () |
| Not implemented. Nothing really to do here. | |
| void | finishProgress () override |
| Finishes the progress of the Heuristic by computing the elapsed time. More... | |
| bool | isStoppingConditionReached () override |
| Always returns false. TODO: Refactor to inherit from Algorithm. More... | |
| virtual void | createInitialPopulation () |
| Not implemented. Nothing really to do here. | |
| virtual void | evaluatePopulation (vector< IntFloatSolution > &) |
| Not implemented. Nothing really to do here. | |
| virtual void | updateEvolution (vector< IntFloatSolution > &) |
| Not implemented. Nothing really to do here. | |
| virtual void | updateEvolution (const int &checkpoint, vector< IntFloatSolution > &) |
| Not implemented. Nothing really to do here. | |
| Protected Member Functions inherited from AbstractEA< S > | |
| virtual void | evaluatePopulation (vector< S > &pop)=0 |
| Evaluates the entire population of solutions. This is a virtual method that must be implemented in the subclasses to adapt special cases. | |
| virtual void | updateEvolution (vector< S > &pop) |
| virtual void | updateEvolution (const int &checkpoint, vector< S > &) |
| Protected Attributes inherited from AbstractEA< S > | |
| int | maxEvaluations |
| int | performedEvaluations |
| int | populationSize |
| vector< S > | population |
| shared_ptr< Problem< S > > | problem |
| unique_ptr< PopulationEvaluator< S > > | evaluator |
| Evolution< S > | evolution |
| AvgEvolution< S > | avgEvolution |
| std::chrono::system_clock::time_point | startTime |
| std::chrono::system_clock::time_point | endTime |
| double | elapsedTime |
| int | nextCheckpoint |
| int | evolutionInterval |
Detailed Description
TwoOpt Heuristic for the Knapsack Problem. Tries to insert each item in the knapsack while there is room for more items.
Member Function Documentation
◆ getID()
|
inlinevirtual |
Returns the identificator of the algorithm, this is used in the to_json method. Must be implemented in the subclasses. It should return the acronym of useful id for a particular configuration.
- Returns
- string
Implements Heuristic< IntFloatSolution >.
◆ getName()
|
inlinevirtual |
Returns the name of the algorithm, this is used in the to_json method. Must be implemented in the subclasses.
- Returns
- string
Implements Heuristic< IntFloatSolution >.
◆ getResults()
|
overridevirtual |
Returns a Front object with all the solutions of the evolutionary process. This method must be implemented in the subclasses.
- Returns
- Front
Implements Heuristic< IntFloatSolution >.
The documentation for this class was generated from the following files:
- include/dignea/algorithms/tsp_heuristics/TwoOpt.h
- src/dignea/algorithms/tsp_heuristics/TwoOpt.cpp
