Introducción:
La Optimización actualmente recibe mucho interés pues aparece en gran cantidad de problemas científicos e industriales. A veces abordar  estos problemas de manera  tradicional es algo impracticable, dada la complejidad computacional del proceso de optimización. Los procedimientos meta heurísticos constituyen una posible variante de solucione en estos casos, brindándonos soluciones aproximadas con una calidad relativamente buena.
Las meta heurísticas poblacionales son de las empleadas en la actualidad, pues en general permiten una mejor exploración del espacio de búsqueda, al tener más de un agente involucrado en el proceso de búsqueda heurística; entre las conocidas están los algoritmos genéticos, la optimización basada en colonias de hormigas y la optimización basada enjambre de partículas (Burkle and Kendall, 2005). Sin embargo, un problema presente en la búsqueda realizada por las meta heurísticas poblacionales, es que la población puede converger de forma tal que el proceso de búsqueda pueda verse limitado a una zona muy específica del espacio de soluciones, con lo cual disminuye la capacidad de exploración del método.
Este trabajo tiene como objetivo el estudio del efecto que provoca la incorporación de un operador encargado de  realizar una operación de limpieza (clearing), en el proceso de búsqueda de la meta heurística Optimización Basada en Enjambre de Partículas (PSO) (Kennedy and Eberhart, 1995) como mecanismo para aumentar  la diversidad en la población y por ende un incremento de la exploración del espacio de soluciones.

• Meta heurísticas poblacionales.

Las meta heurísticas basadas en población, o meta heurísticas poblacionales constituyen herramientas de gran potencia si se quiere resolver un problema de optimización, estas son aquellas que emplean un conjunto de soluciones (población) en cada iteración. Las mismas proporcionan de forma intrínseca un mecanismo de exploración paralelo del espacio de soluciones, y su eficacia depende en gran medida de cómo se manipule dicha población. Dentro de esta clasificación se destacan los Algoritmos Evolutivos (AEs) y los algoritmos basados en Inteligencia Colectiva.
Ambos tienen en común el haber sido inspirados en algún proceso natural, en el primero de los casos en la teoría de la evolución de Darwin (Darwin, 1859). Este científico  planteó que la evolución de las especies se produce por tres conceptos: replicación, variación y selección natural. Por otro lado algoritmos basados en Inteligencia Colectiva toman su inspiración en ejemplos biológicos de comportamiento colectivo (enjambres) como es el caso de las colonias de insectos, las bandadas de aves y los cardúmenes de peces.
 Los Algoritmos Evolutivos son métodos de optimización y búsqueda de soluciones basados en los postulados de la evolución biológica. En ellos se mantiene un conjunto de entidades que representan posibles soluciones, las cuales se mezclan, y compiten entre sí, de tal manera que las más aptas son capaces de prevalecer a lo largo del tiempo, evolucionando hacia mejores soluciones cada vez.
Numerosos han sido los modelos de AEs propuestos. Algunos de los más destacados son: los algoritmos genéticos (AGs) (Goldberg, 1998), búsqueda dispersa (Laguna and Martí, 2003),  evolución diferencial (Storn and Price, 1997), algoritmos basados en estimación de distribuciones (Larrañaga and Lozano, 2002), optimización basada en colonia de hormigas (Dorigo and Caro, 1999),  sistemas de partículas (Particle Swarm Optimization, PSO) (Kennedy and Eberhart, 1995), etc.

• Diversidad Poblacional.

 En los modelos evolutivos, es de vital importancia el hecho de que se realice de una manera correcta  la exploración del espacio de soluciones, para lo cual es necesario mantener en la población individuos con características diferentes, que representen la mayor parte del espacio de búsqueda. Este factor se conoce como diversidad de la población.
Numerosas  han sido las variantes propuestas de mecanismos para introducir la diversidad. A continuación se presentan algunas variantes:
En (Muhlenbein et al., 1991) se presentan los primeros esfuerzos por introducir diversidad, proponiéndose un mecanismo que mantiene en paralelo varias sub-poblaciones, procesadas cada una por un algoritmo genético.
En (Merz, 2004, Merz and Katayama, 2004) se presentan Algoritmos Meméticos que abordan de forma muy eficiente problemas clásicos de optimización discreta (Viajante de Comercio, Asignación Cuadrática, entre otros). Sus buenos resultados son un modelo a seguir, y se apoyan en:

• El uso de operadores de cruce y mutación específicos del problema.
• Adaptar el esquema del EA empleado al problema considerado, incorporando mecanismos de reinicio en caso de estancamiento (perturbar la población).

Seront y Bersini (Seront and Bersini, 2000) presentan un EA con un método de agrupamiento que puede reducir el costo total de la búsqueda local, evitando redescubrir varias veces los mismos óptimos locales.
Mecanismo de prevención de incesto, introducido en el algoritmo generacional con selección elitista y recombinación heterogénea  (CHC) (Eshelman, 1991), donde se cruzan solo aquellos individuos que presenten una determinada diversidad.

• Optimización con PSO

El PSO básicamente consiste en un modelo iterativo basado en una población de partículas en la que cada una de estas sobrevuela el espacio de decisión en busca de soluciones óptimas. Es decir, que asumiendo que contamos con una población de k partículas, donde cada partícula se representa como ) siendo una solución potencial en el espacio D-dimensional sobrevolando dicho espacio en busca de nuevas posiciones , con vector de velocidad . El movimiento del enjambre por el espacio de búsqueda está altamente relacionado con el esquema de PSO que se emplee. En nuestro caso podemos definir el mismo mediante los siguientes pasos:

• Generar la población inicial de k partículas con sus posiciones  y velocidades aleatorias .
• Para cada partícula calcular su valor (evaluación de la función objetivo) y asignar la mejor posición visitada por la misma (  ), así como la mejor posición alcanzada por todo el enjambre ( ).
• Actualizar para cada partícula su vector velocidad  de la siguiente forma:

Siendo un peso de inercia (Engelbrecht, 2006),  un parámetro cognitivo que indica la influencia de la mejor experiencia individual de la partícula en su nueva velocidad y  el parámetro social que indica la influencia de la información social en el nuevo valor de la velocidad de la partícula, en otras palabras la constantes  ,  van a determinar  en qué  medida la partícula es influenciada por el desplazamiento de su propia memoria () y por la cooperación social ().
Por otro parte ,  constituyen números aleatorios con distribución uniforme , los cuales van a proporcionar el comportamiento estocástico del modelo.

• Actualizar la posición de la partícula -esima y forzar que esta se mantenga dentro del de los límites del espacio de soluciones:
• Obtener el valor de la función objetivo evaluada en la partícula   y actualizar en caso de ser necesario   y/o .
• Volver al paso tres y realizar una nueva iteración hasta que se cumpla cierta condición de parada, siendo el  existente en ese momento la solución aportada por el algoritmo.

Otra idea del cálculo de velocidad en PSO es la inclusión de un factor de estrechamiento o coeficiente de restricciones (Parsopoulos and Vrahatis., 2004) el cual controla la velocidad de la partícula y reduce la influencia de la dirección de búsqueda previamente recorrida por la partícula. Esta variante de cálculo de velocidad solo es mencionada pues no forma parte del estudio realizado.
Numerosas han sido las modificaciones realizadas a los esquemas de PSO antes mencionados , podemos citar por ejemplo: el empleo de un operador de turbulencia y la utilización del valor de la función objetivo junto con las restricciones para determinar la calidad de una solución descrito en (Toscano-Pulido and Coello-Coello, 2004) con el cual se logra un aumento de la diversidad poblacional. Por otro lado Liang y Sugathan (Liang and Suganthan, 2006) utilizan un esquema de PSO multicúmulos, cada subcúmulo se encarga de una restricción que es asignada dinámicamente, Li, Tian y Kong (Li et al., 2005) proponen un algoritmo de PSO que utiliza mutación como una alteración del vuelo de la partícula. Además pueden citarse los trabajos realizados en  (Coello-Coello et al., 2006) y (Chen and Lu., 2006).

• Operación de limpieza o clearing

Como se menciona en el anteriormente, la diversidad en los métodos poblacionales es un elemento importante para realizar una buena exploración del espacio de búsqueda, y se presentaron algunas alternativas para fomentar un aumento de la misma. Otra de las variantes realizadas con este objetivo, es el método clearing propuesto en (Petrowski, 1996).
Básicamente el método utiliza el concepto de nicho (subregiones del espacio de búsqueda), y plantea que dos individuos van a pertenecer a un mismo  nicho si la distancia entre ellos es menor que una cuota establecida. El autor recomienda el uso de la distancias hamiltoniana para problemas binarios y la distancia euclidiana para problemas continuos. Entonces, la idea propuesta en este modelo es limitar un poco la competencia dentro de las subregiones o nichos perturbando algunos de los individuos que pertenecen al mismo nicho, para ello emplea una población auxiliar denominada  la cual es formada a partir de la ordenación teniendo en cuenta la calidad de los individuos de la población inicial y sobre la cual se realizan las operaciones. En la figura 2 se muestra un pseudocódigo de dicho método.
Basándonos en esa idea, se propone una variante de operador clearing al modelo PSO, pues este en su diseño original no cuenta con un mecanismo de fomentación de la diversidad. Se define nuestra propuesta de la siguiente forma:

• Se ordenan todas las partículas de la población inicial en función de su calidad.
• De forma secuencial, se compara cada partícula del enjambre  con sus sucesores, y aquello que se encuentren a una distancia menor que la cuota establecida como parámetro son perturbados (reposicionándolos en el enjambre).

Con este mecanismo se logra que haya una mayor separabilidad entre las partículas que integran el enjambre y por ende que una mayor parte del espacio de soluciones sea explorada.
La obtención de nuevas coordenadas para las partículas que según el operador están muy cercanas a otra con mejor calidad se puede realizar de dos formas:

• Reseteando de manera aleatoria la posición actual de la partícula, manteniendo la mejor posición por la que ha transitado (pbest).
• Reseteando de manera aleatoria la mejor posición por la que ha transitado la partícula (usada en la experimentación).

Seguidamente se muestran las variantes de aplicación  del operador clearing al modelo PSO:

• Aplicación del operador al transcurrir una iteración completa del modelo PSO.
• Aplicación del operador al transcurrir cierto número constante de iteraciones del modelo PSO.
• Aplicar el operador usando una matriz de similaritud: Dicha matriz va a contener los conjunto de similaritud asociados a cada partícula del enjambre:

3.1 Decimos que la partícula     si
 Siendo  la cota establecida por el operador clearing.
3.2 Luego aplicamos el operador cuando se detecte la convergencia a través del aumento del porcentaje de partículas relacionas entre sí. La cota para este porcentaje es establecida como parámetro.

• Resultados obtenidos.

A la hora de comparar algoritmos con múltiples conjuntos de datos no existe un procedimiento ya establecido, esto se debe en gran medida a que estos mantienen un comportamiento no determinístico, por lo que la diferencia detectada entre los resultados de dos algoritmos podría deberse a factores aleatorios, y no a una mejora real.
Numerosas son las posibles técnicas a aplicar para determinar si un algoritmo difiere de forma significativa respecto a otro. Principalmente existen dos grupos:

• Los tests paramétricos (Luengo et al., 2009).
• Los tests no-paramétricos (Sheskin, 2006).

En el análisis de los resultados se hace uso del segundo de estos grupos pues los resultados obtenidos por las meta heurísticas no cumplen con las condiciones necesarias para aplicar las pruebas paramétricas.
A continuación describimos el proceso para determinar diferencias significativas entre los modelos diseñados. Se trabajará con un margen de error de un 5% o lo que es lo mismo 0.05:

1. Se aplica la prueba de Iman-Davenport (Iman and Davenport, 1980), para establecer una comparación entre los rankings de los modelos en competencia y detectar diferencias entre el conjunto de algoritmos.
2. Si no se detectan deferencias se puede concluir que los algoritmos involucrados obtienen resultados que no difieren significativamente entre sí.
3. En otro caso, se pueden utilizar las pruebas de comparaciones múltiples (post-hoc). En este trabajo se aplica específicamente el test de Holm (Holm, 1979) para comparar una muestra de control (menor valor de ranking) con el conjunto restante de algoritmos (más de dos).
4. En caso de que sea necesario establecer una comparación entre dos algoritmos, se realiza una prueba de Wilcoxon (Wilcoxon, 1945).

A continuación se muestran los resultados obtenidos para las variantes de aplicación del operador clearing usando para la experimentación una población de 40 partículas, y como funciones de pruebas 20 funciones multimodales propuestas en el CEC 2005 . En esta investigación se empleó un enfoque de minimización en todas las pruebas realizadas. Además en la experimentación se empleó un peso de inercia fijo w=0.8 pues un valor de w grande facilita la exploración global y la selección de un valor pequeño explotación local. También  se establecieron valores para las constantes cognitivas y social c1=c2=1.94, pues la selección de valores grandes harían a las partículas experimentar saltos muy bruscos mientras que valores pequeños permiten explorar regiones diversas antes de dirigirse al objetivo (Eberhart and Shi, 1998).
Se realizaron dos grupos  de comparación: en uno se agruparon todas las variantes de incorporación del operador clearing al PSO al transcurrir cierto número fijo de iteraciones y otro en el cual se aplica dicho operador teniendo en cuenta el porcentaje de partículas relacionadas entre sí (matriz de similaritud). Por último las alternativas de mejor comportamiento de estos grupos se compararon con el modelo PSO puro, realizando en todos los casos las comparaciones teniendo en cuenta la calidad.
Basándose en este criterio de comparación, se compararon los rankings (promedio de la calidad de las funciones para cada uno de los grupos) para detectar la posible variante de mejor comportamiento en cada uno de estos.
En el primero, se comporta como la variante de mejor ranking aquella que aplica el procedimiento de clearing transcurridas 10 iteraciones del modelo PSO (grafico 1), mientras que en el segundo de estos se destaca el comportamiento de la variante que aplica el operador clearing cuando más del 20 % de las partículas están relacionadas entre sí.
Las dos variantes seleccionadas se compararon con el modelo PSO puro, resultando ambas con mejor ranking que este y destacándose la que aplica la operación clearing transcurridas 10 iteraciones del modelo PSO (grafico 3).
Hasta ahora contamos con dos variantes de PSO-Clearing que poseen mejor ranking que el modelo PSO-Puro, para detectar la existencia de diferencias significativas se comparó cada uno por separado con la variante PSO-Puro.
En la primera comparación (PSO-Puro con PSO-Clearing cada 10 iteraciones) se aprecia que sí son estadísticamente significativas las diferencias, viéndose notablemente favorecida la variante que incorpora el clearing. Esto puede apreciarse en los resultados de la prueba de Wilcoxon de la tabla 1.
Tabla  1. Resultados de la prueba de Wilcoxon.

PSO+Clearing(cada 10 iteraciones)	PSO-Puro	Sig. Asintótica	Hipótesis
210.00	0.00	-3.920	Rechazada

En la segunda comparación (PSO-Puro con PSO-Clearing más del 20% de las partículas relacionadas),  aunque en  menor grado, nuevamente las diferencias son estadísticamente significativas, viéndose favorecida en este caso la variante PSO-Clearing más del 20% de las partículas relacionadas (tabla2).
Tabla  2. Resultados de la prueba de Wilcoxon.

PSO+Clearing(más del 20% de las partículas relacionadas)	PSO-Puro	Sig. Asintótica	Hipótesis
117.50	92.50	-0.467	Rechazada

Conclusiones.
A partir de los resultados experimentales alcanzados, se puede plantear que, la incorporación del método de clearing propuesto al modelo PSO analizado, garantiza una mejora tangible en la calidad de las soluciones obtenidas por este, sin la incorporación del operador,  pues los resultados alcanzados son significativamente superiores a los  alcanzados por dicha meta heurística sin el operador clearing.

Bibliografía
BURKLE, E. & KENDALL, G. Search methodologies, Springer, 2005.
COELLO-COELLO, C., CAGNINA, C. A. & ESQUIVEL, L. C. A particle swarm optimizer for constrained numerical. Lecture Notes in Computer Science, 2006. Vol. 4193, p. 910–919.
CHEN, W. & LU., Q. Dynamic-objective particle swarm optimization for constrained optimization problems. Journal of combinatorial optimization, 2006. Vol.12, p.409–419.
DARWIN, C. On the Origin of Species. London: John Murray, 1859.126.
DORIGO, M. & CARO, G. D. The Ant Colony Optimization meta-heuristic en New Ideas in Optimization, D. Corne, M. Dorigo, and F. Glover, Editors, McGraw-Hill: London  UK, 1999.  p. 11-32.
EBERHART, R. C. & SHI, Y. Parameter Selection in Particle Swarm Optimization. Evolutionary Programming VII Springer, Lecture Notes in Computer Science, 1998. 1447, p.591-600.
ENGELBRECHT, A. P. Fundamentals of Computational Swarm Intelligence, 2006. John Wiley & Sons.
ESHELMAN, L. The CHC Adaptive Search Algorithm. How to Have Safe Search When Engaging in Nontraditional Genetic Recombination. Foundations of Genetic Algorithms, 1991. p.265-283.
GOLDBERG, D. E. (Ed.) Genetic Algorithms in Search. Optimization and Machine Learning. 1998. Addison-Wesley Publishing Company: University of Alabama.
HOLM, S. A simple sequentially rejective multiple test procedure. Scand Journal Stat,1979. Vol.6,  p.65-70.
IMAN, R. L. & DAVENPORT, J. M. Approximations of the critical region of the Friedman statistic. Commun Stat, 1980. Vol.18: p. 571-595.
KENNEDY, J. & EBERHART, R. C. Particle swarm optimization. en IEEE International Conference on Neural Networks. Piscataway, New York, USA, 1995.Vol. 4: p. 1942-1948.
LAGUNA, M. & MARTÍ, R. Scatter Search. Methodology and Implementation in C. Kluwer Academic Publishers. 1ra ed. 2003.
LI, X., TIAN, M. & KONG , P. Novel particle swarm optimization for constrained optimization problems, Lecture Notes in Computer Science, , 2005. Vol. 3809, p. 1305–1310.
LIANG, J. J. & SUGANTHAN, P. N. Dynamic multi-swarm particle swarm optimizer with a novel constraint-handling mechanism. Proceedings  of  the  IEEE Congress  on  Evolutionary Computation (CEC  2006), Vancouver, Canada, 2006. p. 316-323,
LARRAÑAGA, P. &. LOZANO J.A, Estimation of Distribution Algorithms. A New Tool for Evolutionaty Computation, Kluwer Academic Publichers: Boston/Dordrecht/London, 2002.
LUENGO, J., GARCÍA, S. & HERRERA, F. A Study on the Use of Statistical Tests for Experimentation with Neural Networks: Analysis of Parametric Test Conditions and Non-Parametric Tests. Expert Systems with Applications, 2009. 36: p. 7798-7808.
MERZ, P.NK-Fitness Landscaes and Memetic Algorithms with Greedy Operators and k-opt Local Search. Recent Advances in Memetic Algorithms, 2004. 166, p. 209-228.
MERZ, P. & KATAYAMA, K.. Memetic Algorithms for the Unconstrained Binary Quadratic Programming Problem. Bio System, 2004. 78, p. 99-18.
MUHLENBEIN, H., SCHOMISCH, M. & BORN, J. The parallel genetic algorithm as function optimizer. Fourth International Conference on Genetic Algorithms. San Mateo, California, Morgan Kaufmann, 1991.
PARSOPOULOS, K. E. & VRAHATIS., M. N. (2004) Upso: A unified particle swarm optimization scheme. Proc. Int. Conf. Computational Methods in Sciences and Engineering (ICCMSE2004), VSP International Science Publishers, 2004. Vol. 1, p. 868--873.
PETROWSKI, A. A clearing procedure as a niching method for genetic algorithms. In Proc. IEEE International conference on evolutionary computation. Japan, 1996. p. 798-803.
SERONT, G. & BERSINI, H. A new ga-local search hybrid for continous optimization based on multi level single linkaga clustering. en of the Genetic and Evolutionary Computation Conference 2000. 2000, p. 90-95.
SHESKIN, D. Handbook of parametric and nonparametric statistical procedures.CRC Editor., Chapman & Hall: London/West Palm Beach, 2006.
STORN, R. & PRICE, K. Diferential Evolution. A Simple and Effcient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization,1997. Vol. 11, p. 341-359.
TOSCANO-PULIDO, G. & COELLO-COELLO, C. A. A constrained-handling mechanism for particle swarm optimization. Proceedings of the Congress on Evolutionary Computation (CEC 2004), Portland, Oregon, USA, IEEE Service Center, 2004. p. 1396--1403,
WILCOXON, F. Ajusted p-values for simultaneous inference, Biometrics, 1945. 48, p. 1005-1013.