Skip to content

inversed-ru/Ascension

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

35 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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(-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

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