On Solving the Maximum Betweenness Problem Using Genetic Algorithms

Savić, Aleksandar

Serdica Journal of Computing (2009)

  • Volume: 3, Issue: 3, page 299-308
  • ISSN: 1312-6555

Abstract

top
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.

How to cite

top

Savić, Aleksandar. "On Solving the Maximum Betweenness Problem Using Genetic Algorithms." Serdica Journal of Computing 3.3 (2009): 299-308. <http://eudml.org/doc/11363>.

@article{Savić2009,
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.},
author = {Savić, Aleksandar},
journal = {Serdica Journal of Computing},
keywords = {Evolutionary Approach; Genetic Algorithms; Betweenness Problem; numerical examples; genetic algorithms; betweenness problem},
language = {eng},
number = {3},
pages = {299-308},
publisher = {Institute of Mathematics and Informatics Bulgarian Academy of Sciences},
title = {On Solving the Maximum Betweenness Problem Using Genetic Algorithms},
url = {http://eudml.org/doc/11363},
volume = {3},
year = {2009},
}

TY - JOUR
AU - Savić, Aleksandar
TI - On Solving the Maximum Betweenness Problem Using Genetic Algorithms
JO - Serdica Journal of Computing
PY - 2009
PB - Institute of Mathematics and Informatics Bulgarian Academy of Sciences
VL - 3
IS - 3
SP - 299
EP - 308
AB - 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.
LA - eng
KW - Evolutionary Approach; Genetic Algorithms; Betweenness Problem; numerical examples; genetic algorithms; betweenness problem
UR - http://eudml.org/doc/11363
ER -

NotesEmbed ?

top

You must be logged in to post comments.