A metaheuristic optimization framework
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
Problems
Acceptance.pas
Arrays.pas
Ascension.dpr
Ascension.lpi
BitMath.pas
Common.pas
Config.ini
Crossovers.pas
DummyGA.inc
DummyLS.inc
DummySA.inc
DummyTS.inc
ExtraMath.pas
Formatting.pas
GeneticAlg.pas
HashFunctions.pas
HashTables.pas
IniConfigs.pas
Interface.inc
InvSys.pas
LICENSE
Lexer.pas
LocalSearchAlg.pas
Messages.pas
README.md
RandVars.pas
SimAnnealAlg.pas
SolutionLists.pas
Sorting.pas
SpecFuncs.pas
Statistics.pas
StringLists.pas
StringUtils.pas
TabuSearchAlg.pas
icon.res

README.md

Ascension

A metaheuristic optimization framework. See the project homepage for an overview and notable results (please note that many of the described features had to be omitted from the 2.0 release).

How to use the framework

Copy a project definition module (PDM) into the project folder, rename it to problem.pas, then compile and run Ascension. A couple of example PDMs are located in the problems folder. Algorithm parameters are specified in the Config.ini file. Several files are created during the optimization process:

File Description
XX_Status Status file containing the data about the optimization process (XX is the abbreviated algorithm name)
XX_Best The best solution found during the optimization.
Runs Information about the results of multiple optimization runs
Runs_Best The best solution found during multiple optimization runs

How to create a PDM

You can specify your own problem by creating a problem.pas file that supplies the types and routines required by each metaheuristic (full list can be found in interface.inc). See Problem_NQ.pas from the problems folder for an example of a complete PDM. If you don't need a certain algorithm, the corresponding definitions can be effectively omitted by placing a {$I DummyXX.inc} line at the end of the file.

Config parameters

Global Parameters

Parameter Description
Algorithm Optimization algorithm
⇢"SA" Simulated Annealing
⇢"GA" Genetic Algorithm
⇢"LS" Local Search
⇢"TS" Tabu Search
NRuns Number of independent algorithm runs
ScoreToReach The desired value of the score function, can be used by stopping criteria

Local Search

Parameter Description
Mode Local search mode.
⇢"First" Pick the first improving move from a move list
⇢"Best" Pick the best move from a move list
⇢"Chain" Sort all moves by score, then try to sequentially apply all improving moves in order from best to worst
StatusIters Interval between saving the data about optimization process to a status file, nothing is saved if set to zero

Tabu Search

Parameter Description
Iterations Total number of iterations
StatusIters Interval between saving the data about optimization process to a status file, nothing is saved if set to zero

Simulated Annealing

Parameter Description
Iterations Total number of iterations
T0 Initial temperature, used if T0Mode is "Manual"
Tfin Final temperature, used if TfinEBased is No
dEmax Maximal change of energy, used if T0Mode is "EBased"
dEmin Minimal change of energy, used if TfinEBased is Yes
T0Mode Initial temperature selection
⇢"Manual" Determined by T0
⇢"EBased" Calculated based on dEmax
⇢"AutoLow" Automatic selection, lower temperature mode
⇢"AutoHigh" Automatic selection, higher temperature mode
TfinEBased Final temperature selection
⇢No Determined by Tfin
⇢Yes Calculated based on dEmin
Acceptance Acceptance function
⇢"Exp" Exp(-xp)
⇢"Power" 1 / (1 + xp)
⇢"Tsallis" (1 - (1 - p) x)1 / (1 - p)
⇢"Threshold" (1 - Sign(x - 1)) / 2
⇢"Barker" 1 / (1 + Exp(x))
AcceptanceP Acceptance function parameter
Schedule Cooling schedule type
⇢"Zero" T = 0
⇢"Log" T ~ 1 / (C + Ln(1 + t / L))
⇢"Power" T ~ (1 + t / L)p
⇢"Exp" T ~ Exp(-(t / L)p)
ScheduleP Cooling schedule parameter
NReheat Number of reheating stages, no reheating if set to 1
FastReheat Determines the duration of reheating stages
⇢No Each reheating stage takes the same number of iterations
⇢Yes Later reheating stages take less iterations
Smoothing The amount of smoothing applied when calculating statistics for the status file
StatusIters Interval between saving the data about optimization process to a status file, nothing is saved if set to zero.

Genetic Algorithm

Parameter Description
PopulationSize Number of individuals in the population
Selection Method of selecting individuals for reproduction
⇢"RankProp" Selection probability is proportional to (1 - R)p if p > 0 or R-p if p < 0, where R is the individual's rank normalized to [0 .. 1] and p = SelectionP
⇢"Dist" SelectionP individuals are picked at random, then the pair with the largest (smallest) intersolution distance is selected if SelectionP > 0 (< 0)
⇢"DistToBest" SelectionP individuals are picked at random, then two individuals with the largest (smallest) distance to the best individual in the population are selected if SelectionP > 0 (< 0)
SelectionP Selection parameter
Replacement Method of selecting which individual to replace
⇢"Worst" Worst individual in the population
⇢"InvRank" Selection probability is proportional to Rp if p > 0 or (1 - R)-p if p < 0, where R is the individual's rank normalized to [0 .. 1] and p = ReplacementP
⇢"WorstParent" Worst parent
⇢"RandParent" Random parent
⇢"SimilarParent" Most similar parent
⇢"Influx" Worst parent. When the child is better than both parents, also replace the other parent with a new solution
ReplacementP Replacement parameter
Acceptance Criterion for determining whether the solution picked by Replacement method actually gets replaced
⇢"Elitist" Replace only if the child is better
⇢"Unconditional" Replace unconditionally
StopCriterion Criterion for stopping the algorithm
⇢"MaxGens" Maximal number of generations is reached
⇢"MaxNFE" Maximal number of function evaluations is reached
⇢"Score" ScoreToReach is reached
StatusGens Interval in generations between saving the data about optimization process to a status file, nothing is saved if set to zero
SaveGens Interval in generations between saving the population, nothing is saved if set to zero