Evolutionary Approach Genetic Algorithms Betweenness Problem
Issue Date:
2009
Publisher:
Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 3, No 3, (2009), 299p-308p
Abstract:
In this paper a genetic algorithm (GA) is applied on Maximum
Betweennes Problem (MBP). The maximum of the objective function is
obtained by finding a permutation which satisfies a maximal number of
betweenness constraints. Every permutation considered is genetically coded
with an integer representation. Standard operators are used in the GA.
Instances in the experimental results are randomly generated. For smaller
dimensions, optimal solutions of MBP are obtained by total enumeration.
For those instances, the GA reached all optimal solutions except one. The
GA also obtained results for larger instances of up to 50 elements and 1000
triples. The running time of execution and finding optimal results is quite
short.
