Geodesic
On Solving the Maximum Betweenness Problem Using Genetic Algorithms
Serdica Journal of Computing, Tome 3 (2009) no. 3, pp. 299-308

Voir la notice de l'article provenant de la source Bulgarian Digital Mathematics Library

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.
Keywords: Evolutionary Approach, Genetic Algorithms, Betweenness Problem 
@article{SJC_2009_3_3_a5,
     author = {Savi\'c, Aleksandar},
     title = {On {Solving} the {Maximum} {Betweenness} {Problem} {Using} {Genetic} {Algorithms}},
     journal = {Serdica Journal of Computing},
     pages = {299--308},
     publisher = {mathdoc},
     volume = {3},
     number = {3},
     year = {2009},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJC_2009_3_3_a5/}
}
TY  - JOUR
AU  - Savić, Aleksandar
TI  - On Solving the Maximum Betweenness Problem Using Genetic Algorithms
JO  - Serdica Journal of Computing
PY  - 2009
SP  - 299
EP  - 308
VL  - 3
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJC_2009_3_3_a5/
LA  - en
ID  - SJC_2009_3_3_a5
ER  - 
%0 Journal Article
%A Savić, Aleksandar
%T On Solving the Maximum Betweenness Problem Using Genetic Algorithms
%J Serdica Journal of Computing
%D 2009
%P 299-308
%V 3
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJC_2009_3_3_a5/
%G en
%F SJC_2009_3_3_a5
Savić, Aleksandar. On Solving the Maximum Betweenness Problem Using Genetic Algorithms. Serdica Journal of Computing, Tome 3 (2009) no. 3, pp. 299-308. http://geodesic.mathdoc.fr/item/SJC_2009_3_3_a5/