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 problem definition module (PDM) from the problems into the project folder, rename it to problem.pas, then compile (I recommend using Lazarus IDE) and run Ascension. 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

Included PDMs

File | Problem --- | --- Problem_2DHP.pas | Hydrophobic-polar protein folding model Problem_3DNQ.pas | 3D N queens Problem_BinTexGen.pas | Binary texture generation Problem_Chess_Covering.pas | Queen (non)domination, knights covering Problem_NQ.pas | N queens Problem_No_Subsquares.pas | Maximal density subsquare-free arrangements Problem_Peaceable_Queens.pas | Peaceable queens Problem_Still_Life.pas | Maximal density still life

See the description section inside of each file for more details.

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 ⇢"CTS" | Cooperative 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 PopSize | Population size (cooperative variant only) 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(-x^p) ⇢"Power" | 1 / (1 + x^p) ⇢"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

See the algorithm page for a detailed description of selection, replacement and acceptance parameters.

Parameter | Description --- | --- PopulationSize | Number of individuals in the population Selection | Method of selecting individuals for reproduction SelectionP | Selection parameter Replacement | Method of selecting which individual to replace ReplacementP | Replacement parameter Acceptance | Criterion for determining whether the solution picked by Replacement method actually gets replaced 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

Acknowledgements

This project has been supported by the following patrons via Patreon:

• Brian Bucklew
• Anton Shepelev
• Adam Hill
• John Metcalf
• Tomoyuki Naito