Abstract-This paper presenterar en rekursiv, dimension-sweep algoritm för beräkning av hypervolym indikator av kvaliteten på en uppsättning n icke-dominerade punkter i d > 2 dimensioner. Den förbättrar den befintliga HSO-algoritmen (Hypervolym med skivmål) genom att beskära rekursionsträdet för att undvika upprepade dominanskontroller och omräkning av partiella hypervolymer. Dessutom innehåller den ett nytt resultat för det tredimensionella specialfallet. Den föreslagna algoritmen uppnår O (n d 2 log n) tid och linjär rymd komplexitet i värsta fall, men experimentella resultat visar att de beskärning tekniker som används kan minska tiden komplexitet exponenten ännu mer.
Den snabbaste algoritmen baserad på dimensionssvettning är FPL-algoritmen av Fonseca et al. REF som har en asymptotisk komplexitet av O(n d‐2 log n) medan endast linjärt utrymme används.
An Improved Dimension-Sweep Algorithm for the Hypervolume Indicator
{'venue': '2006 IEEE International Conference on Evolutionary Computation', 'journal': '2006 IEEE International Conference on Evolutionary Computation', 'mag_field_of_study': ['Mathematics', 'Computer Science']}