Método iterativo para la reducción de espacio de soluciones en algoritmos heurísticos de optimización. Aplicación a la adaptación de redes de alcantarillado en escenarios de cambio climático

Abstract

[ES] El espacio de búsqueda de soluciones (SS) en los algoritmos de optimización heurísticos es extenso, esto genera dificultades en la exploración completa de este. El impedimento de la exploración del SS en toda su extensión ocasiona que existan soluciones que se estancan o detienen en mínimos locales dificultando al algoritmo la obtención de buenas soluciones. Este trabajo toma como punto de partida el método presentado por Ngamalieu, 2019 para la reducción del SS, el cual se basa en el desarrollo de dos mecanismos asociados entre sí: el primero, la reducción de las variables de decisión (DV) a través de la prelocalización de tanques de tormenta (ST) y la posterior preselección de conductos, el segundo, la reducción del rango de variación de cada una de las DV. Para la reducción de la variación de las DV considera la discretización del área (N) que podrán ocupar los ST más pequeña y los diámetros candidatos (ND) de los conductos a sustituir pertenecen a una gama reducida de estos. Previo a establecer una metodología de reducción del SS es necesario establecer el tamaño de grupo de simulaciones, de forma que, las soluciones a las que converge el algoritmo de optimización en cada una de las simulaciones sean representativas del SS, por lo tanto, el desarrollo de un análisis estadístico aplicado a un problema de optimización permite determinar el número de simulaciones adecuado que deben constituir el tamaño de grupo. Expuestos estos antecedentes, se implementa un método iterativo que considera los mecanismos de reducción del SS presentado por Ngamalieu, 2019, adicionando a la prelocalización de ST aquellos nudos que presentan un volumen de inundación en el sistema. Siendo estos nudos los principales candidatos para la prelocalización de los ST, los nudos inundados son sometidos a criterios de clasificación que dan origen a diferentes casos de reducción del SS. El desarrollo de los casos reducción del SS permite reducir las DV en cada iteración del método, suprimiendo aquellos nudos y/o conductos que dejan de ser candidatos de una iteración a la siguiente. Como resultado del desarrollo del método se obtiene el caso de reducción de SS más eficiente, la eficiencia de cada uno de los casos se valora a través del porcentaje de buenas soluciones a las que converge el algoritmo de optimización. Entendiendo por buena solución que el valor obtenido por el algoritmo no supere un porcentaje determinado al valor mínimo del caso de estudio utilizado en el análisis. El desarrollo de las distintas instancias de este trabajo corresponde a diferentes tamaños de problema de optimización, es así que: el análisis estadístico se analiza con una red considerado como pequeño problema, mientras que, el análisis de cada uno de los casos de reducción del SS se analiza sobre un problema intermedio, para finalizar con la aplicación del caso de reducción de SS más eficiente sobre una red que bordea de un problema grande.

[EN] The solutions of search space (SS) in heuristic optimization algorithms is wide and it is difficult to explore it entirely. The impossibility of performing a complete exploration of SS promote the existence of solutions that stagnate or stop at local minima making the algorithm not to obtain good solutions. The starting point of this work is the method of Ngamalieu-Nengoue et al., (2019) for the reduction of SS, which is based on the development of two mechanisms associated with each other. The first mechanism is related with the reduction of the decision variables (DV) by the pre-location of storm tanks (ST) and the subsequent pre-selection of pipes. The second mechanism is about the reduction of the variation range of the DV. The reduction of the variation of the DVs consider the discretization of the area (N) that the smallest STs can occupy and the candidate diameters (ND) of the ducts to be replaced which belong to a reduced spectrum of variables. The establishment of a methodology for the reduction of the SS requires the definition of a size of the simulation group to achieve representative solutions from the optimization algorithm of each of the simulations, Therefore, the development of an error analysis applied to an optimization problem determine a suitable number of simulations that must constitute the group size of simulations. According to this background is necessary some improvement proposals as the incorporation of an iterative process that considers the reduction mechanisms of SS published by Ngamalieu-Nengoue et al., (2019). Besides, a ST is added to a pre-location of ST of those nodes that have a flood volume in the system. Finally, some criteria are implemented for the selection of the DV for the pipeline preselection process. Besides, this work is a proposal for an iterative simultaneous method for the reduction of SS. This method is based on the application of the criteria selection of DV. The development of the method allows the reduction of the SS that cause the reduction of the DVs in each iteration of the method, avoiding those nodes and pipes that are not candidates for the next iterations. As result of the methodology use in this work, the most efficient SS reduction was obtained, the efficiency of each case is evaluated by means of the percentage of good solutions that converges by the optimization algorithm. A good solution is defined as the value obtained by the algorithm that do not exceed a certain percentage to the minimum value of the case study. Also, some criteria for the comparison of the proposed methods are implemented. The development of the different instances of this work corresponds to diverse sizes of optimization problem. So, the error analysis is performed with a network considered as a small problem, while the analysis of each of the reduction methods of the SS is performed about an intermediate and large size problem.

[CA] L'espai de cerca de solucions (SS) en els algorismes d'optimització heurístics és extens, això genera dificultats en l'exploració completa d'aquest. L'impediment de l'exploració del SS en tota la seua extensió ocasiona que existisquen solucions que s'estancen o detenen en mínims locals dificultant a l'algorisme l'obtenció de bones solucions. Aquest treball pren com a punt de partida el mètode presentat per *Ngamalieu- *Nengoue et al., (2019) per a la reducció del SS, el qual es basa en el desenvolupament de dos mecanismes associats entre si: el primer, la reducció de les variables de decisió (*DV) a través de la *pre-localització de tancs de tempesta (*ST) i la posterior preselecció de conductes, el segon, la reducció del rang de variació de cadascuna de les *DV. Per a la reducció de la variació de les *DV considera la *discretización de l'àrea (N) que podran ocupar els *ST més xicoteta i els diàmetres candidats (*ND) dels conductes a substituir, pertanyen a una gamma reduïda d'aquests. Previ a establir una metodologia de reducció del SS és necessari definir la grandària de grup de simulacions, de manera que, les solucions a les quals convergeix l'algorisme d'optimització en cadascuna de les simulacions siguen representatives del SS, per tant, el desenvolupament d'una anàlisi d'errors aplicat a un problema d'optimització permet determinar el nombre de simulacions adequat que han de constituir la grandària de grup. Exposats aquests antecedents, s'implementa propostes de millores, incorporant un procés iteratiu que considera els mecanismes de reducció del SS presentat per *Ngamalieu-*Nengoue et al., (2019). A més, s'addiciona a la *pre-localització de *ST aquells nusos que presenten un volum d'inundació en el sistema. Finalment, S'implementa criteris de selecció de les *DV en el procés de preselecció de conductes. D'altra banda, aquest treball presenta una proposta de mètode simultani iteratiu per a la reducció del SS. El mètode es basa en l'aplicació de criteris de selecció de les *DV. El desenvolupament del mètode permet la reducció del SS alhora que ocasiona la reducció de les *DV en cada iteració del mètode, suprimint aquells nusos i conductes que deixen de ser candidats d'una iteració a la següent. Com a resultat del desenvolupament de la metodologia d'aquest treball, s'obté el cas de reducció de SS més eficient, l'eficiència de cadascun dels casos es valora a través del percentatge de bones solucions a les quals convergeix l'algorisme d'optimització. Entenent per bona solució, que el valor obtingut per l'algorisme no supere un percentatge determinat al valor mínim del cas d'estudi. A més, s'implementa criteris per a la comparació dels mètodes proposats. El desenvolupament de les diferents instàncies d'aquest treball correspon a diferents grandàries de problema d'optimització, és així com: l'anàlisi d'errors es realitza amb una xarxa considerat com a problema xicotet, mentre que, l'anàlisi de cadascun dels mètodes de reducció del SS es realitza sobre un problema grandària intermèdia i gran.