Published March 1, 2022
| Version v1
Publication
Open
Capping methods for the automatic configuration of optimization algorithms
- 1. Universidade do Estado de Santa Catarina
- 2. University of Manchester
- 3. Universidade Federal do Rio Grande do Sul
- 4. Universidad de Málaga
Description
Automatic configuration techniques are widely and successfully used to find good parameter settings for optimization algorithms. Configuration is costly, because it is necessary to evaluate many configurations on different instances. For decision problems, when the objective is to minimize the running time of the algorithm, many configurators implement capping methods to discard poor configurations early. Such methods are not directly applicable to optimization problems, when the objective is to optimize the cost of the best solution found, given a predefined running time limit. We propose new capping methods for the automatic configuration of optimization algorithms. They use the previous executions to determine a performance envelope, which is used to evaluate new executions and cap those that do not satisfy the envelope conditions. We integrate the capping methods into the irace configurator and evaluate them on different optimization scenarios. Our results show that the proposed methods can save from about 5% to 78% of the configuration effort, while finding configurations of the same quality. Based on the computational analysis, we identify two conservative and two aggressive methods, that save an average of about 20% and 45% of the configuration effort, respectively. We also provide evidence that capping can help to better use the available budget in scenarios with a configuration time limit.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
تُستخدم تقنيات التكوين التلقائي على نطاق واسع وبنجاح للعثور على إعدادات معلمة جيدة لخوارزميات التحسين. التكوين مكلف، لأنه من الضروري تقييم العديد من التكوينات في حالات مختلفة. بالنسبة لمشاكل القرار، عندما يكون الهدف هو تقليل وقت تشغيل الخوارزمية، يقوم العديد من أدوات التهيئة بتنفيذ طرق التغطية لتجاهل التكوينات السيئة في وقت مبكر. لا تنطبق هذه الطرق بشكل مباشر على مشاكل التحسين، عندما يكون الهدف هو تحسين تكلفة أفضل حل تم العثور عليه، نظرًا لحد زمني محدد مسبقًا للتشغيل. نقترح طرق تغطية جديدة للتكوين التلقائي لخوارزميات التحسين. يستخدمون عمليات التنفيذ السابقة لتحديد مظروف الأداء، والذي يستخدم لتقييم عمليات التنفيذ الجديدة وتغطية تلك التي لا تفي بشروط المظروف. ندمج طرق التغطية في مكوّن irace ونقيمها على سيناريوهات تحسين مختلفة. تظهر نتائجنا أن الطرق المقترحة يمكن أن توفر من حوالي 5 ٪ إلى 78 ٪ من جهد التكوين، مع العثور على تكوينات بنفس الجودة. استنادًا إلى التحليل الحسابي، نحدد طريقتين محافظتين وطريقتين عدوانيتين، توفران في المتوسط حوالي 20 ٪ و 45 ٪ من جهد التكوين، على التوالي. نقدم أيضًا دليلًا على أن الحد الأقصى يمكن أن يساعد في استخدام الميزانية المتاحة بشكل أفضل في السيناريوهات ذات الحد الزمني للتكوين.Translated Description (French)
Les techniques de configuration automatique sont largement et avec succès utilisées pour trouver de bons paramètres pour les algorithmes d'optimisation. La configuration est coûteuse, car il est nécessaire d'évaluer de nombreuses configurations sur différentes instances. Pour les problèmes de décision, lorsque l'objectif est de minimiser le temps d'exécution de l'algorithme, de nombreux configurateurs mettent en œuvre des méthodes de plafonnement pour éliminer rapidement les mauvaises configurations. De telles méthodes ne sont pas directement applicables aux problèmes d'optimisation, lorsque l'objectif est d'optimiser le coût de la meilleure solution trouvée, compte tenu d'une limite de temps d'exécution prédéfinie. Nous proposons de nouvelles méthodes de capping pour la configuration automatique des algorithmes d'optimisation. Ils utilisent les exécutions précédentes pour déterminer une enveloppe de performance, qui est utilisée pour évaluer les nouvelles exécutions et plafonner celles qui ne satisfont pas aux conditions de l'enveloppe. Nous intégrons les méthodes de plafonnement dans le configurateur irace et les évaluons sur différents scénarios d'optimisation. Nos résultats montrent que les méthodes proposées permettent d'économiser d'environ 5% à 78% de l'effort de configuration, tout en trouvant des configurations de même qualité. Sur la base de l'analyse computationnelle, nous identifions deux méthodes conservatrices et deux méthodes agressives, qui économisent en moyenne environ 20% et 45% de l'effort de configuration, respectivement. Nous fournissons également des preuves que le plafonnement peut aider à mieux utiliser le budget disponible dans des scénarios avec une limite de temps de configuration.Translated Description (Spanish)
Las técnicas de configuración automática se utilizan ampliamente y con éxito para encontrar una buena configuración de parámetros para los algoritmos de optimización. La configuración es costosa, porque es necesario evaluar muchas configuraciones en diferentes instancias. Para los problemas de decisión, cuando el objetivo es minimizar el tiempo de ejecución del algoritmo, muchos configuradores implementan métodos de limitación para descartar configuraciones deficientes antes de tiempo. Dichos métodos no son directamente aplicables a los problemas de optimización, cuando el objetivo es optimizar el costo de la mejor solución encontrada, dado un límite de tiempo de ejecución predefinido. Proponemos nuevos métodos de capping para la configuración automática de algoritmos de optimización. Utilizan las ejecuciones anteriores para determinar una envolvente de rendimiento, que se utiliza para evaluar nuevas ejecuciones y limitar aquellas que no satisfacen las condiciones de la envolvente. Integramos los métodos de limitación en el configurador de irace y los evaluamos en diferentes escenarios de optimización. Nuestros resultados muestran que los métodos propuestos pueden ahorrar de aproximadamente un 5% a un 78% del esfuerzo de configuración, al tiempo que encuentran configuraciones de la misma calidad. A partir del análisis computacional, identificamos dos métodos conservadores y dos agresivos, que ahorran una media de alrededor del 20% y 45% del esfuerzo de configuración, respectivamente. También proporcionamos evidencia de que la limitación puede ayudar a utilizar mejor el presupuesto disponible en escenarios con un límite de tiempo de configuración.Files
1-s2.0-S0305054821003300-main.pdf.pdf
Files
(8.2 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:8ec68a75852ddc25b7115f0bf042c195
|
8.2 MB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- طرق السد للتكوين التلقائي لخوارزميات التحسين
- Translated title (French)
- Méthodes de plafonnement pour la configuration automatique des algorithmes d'optimisation
- Translated title (Spanish)
- Métodos de tapado para la configuración automática de algoritmos de optimización
Identifiers
- Other
- https://openalex.org/W3208898742
- DOI
- 10.1016/j.cor.2021.105615
References
- https://openalex.org/W135055223
- https://openalex.org/W1491246725
- https://openalex.org/W1582334898
- https://openalex.org/W1615720819
- https://openalex.org/W170314049
- https://openalex.org/W1713435687
- https://openalex.org/W1926688248
- https://openalex.org/W1976358752
- https://openalex.org/W2014328192
- https://openalex.org/W2014538668
- https://openalex.org/W2017708378
- https://openalex.org/W2042986967
- https://openalex.org/W2049791651
- https://openalex.org/W2060747552
- https://openalex.org/W2061554433
- https://openalex.org/W2067612530
- https://openalex.org/W2074821977
- https://openalex.org/W2079454949
- https://openalex.org/W2081453109
- https://openalex.org/W2104008682
- https://openalex.org/W2110383956
- https://openalex.org/W2139059344
- https://openalex.org/W2141119792
- https://openalex.org/W2151459007
- https://openalex.org/W2158984240
- https://openalex.org/W2163316275
- https://openalex.org/W2181005956
- https://openalex.org/W2185085875
- https://openalex.org/W2342137734
- https://openalex.org/W2397790788
- https://openalex.org/W2486444208
- https://openalex.org/W2600077159
- https://openalex.org/W2753452838
- https://openalex.org/W2903754058
- https://openalex.org/W2909673565
- https://openalex.org/W2950680102
- https://openalex.org/W3004042307
- https://openalex.org/W3120004977
- https://openalex.org/W3123901663
- https://openalex.org/W3153881645
- https://openalex.org/W4232223209
- https://openalex.org/W4256137062