Algoritmo de otimização por enxame de partículas para o problema de atribuição axial 3D

Vista previa del material en texto

INSTITUTO TECNOLÓGICO DE LA PAZ 
DIVISIÓN DE ESTUDIOS DE POSGRADO E INVESTIGACIÓN 
MAESTRÍA EN SISTEMAS COMPUTACIONALES 
 
 
UN ALGORITMO BASADO EN LA OPTIMIZACIÓN POR ENJAMBRE DE 
PARTÍCULAS PARA EL PROBLEMA DE ASIGNACIÓN AXIAL 3-DIMENSIONAL 
 
 
T E S I S 
 
QUE PARA OBTENER EL GRADO DE 
MAESTRO EN SISTEMAS COMPUTACIONALES 
 
 
PRESENTA: 
ING. JOSÉ ALBERTO FRANCO GÓMEZ 
 
 
DIRECTOR DE TESIS: 
DR. MARCO ANTONIO CASTRO LIERA 
 
 
MIEMBROS DEL JURADO: 
PRESIDENTE: DR. SAÚL MARTÍNEZ DÍAZ 
SECRETARIO: M. EN S.C. JAVIER ALBERTO CARMONA TROYO 
VOCAL: M. EN C. JESÚS ANTONIO CASTRO 
VOCAL SUPLENTE: M.A.T.I. LUIS ARMANDO CÁRDENAS FLORIDO 
 
 
 
LA PAZ, BAJA CALIFORNIA SUR, MÉXICO; SEPTIEMBRE DEL 2011. 
 
 
i 
 
RESUMEN de la tesis de José Alberto Franco Gómez, presentada como requisito 
parcial para obtener el Grado de MAESTRO en SISTEMAS COMPUTACIONALES CON 
LINEA DE TRABAJO MODELACIÓN INTELIGENTE DE SISTEMAS. La Paz, Baja 
California Sur; septiembre del 2011. 
 
Un Algoritmo Basado en Optimización por Enjambre de Partículas para el 
Problema de Asignación Axial 3-Dimensional 
 
La optimización por enjambre de partículas (PSO) es un algoritmo inspirado en el 
comportamiento social de individuos dentro de enjambres en la naturaleza. Este método 
emplea una búsqueda basada en poblaciones; en la cual los individuos, para desplazarse en el 
espacio de búsqueda, usan su propia experiencia y el conocimiento de sus vecinos con 
distintos grados de confianza. PSO fue originalmente desarrollado para problemas continuos, 
pero varias adaptaciones del método a problemas discretos han sido propuestas recientemente. 
Con el fin de resolver el problema de asignación axial 3-dimensional (3AP), el cual es un 
problema discreto de tipo NP-duro, los operadores clásicos de PSO fueron redefinidos y un 
algoritmo en paralelo fue implementado. El algoritmo propuesto se aplicó a un conjunto de 
problemas de referencia y los resultados fueron comparados con los existentes de otros 
algoritmos que solucionan 3AP. La evaluación muestra que el algoritmo propuesto es 
competitivo. 
 
Palabras claves: Adaptación de continuo a discreto, problemas discretos, método 
evolutivo, algoritmo paralelo, optimización por enjambre de partículas, problema de 
asignación axial 3-dimensional. 
 
 
 
 
ii 
 
ABSTRACT of the thesis presented by JOSÉ ALBERTO FRANCO GÓMEZ as a partial 
requirement to obtain the MASTER degree in COMPUTER SYSTEMS in INTELLIGENT 
SYSTEMS MODELING. La Paz, Baja California Sur, México; September 2011. 
 
An Algorithm Based on Particle Swarm Optimization for Three Dimensional Axial 
Assignment Problem 
 
Particle Swarm Optimization (PSO) is an algorithm inspired by natural social behavior of 
individuals in swarms. This method employs a collaborative population based search, which 
features individuals that base their movements across the search space on self experience and 
neighborhood information. PSO was originally developed for continuous problems, but 
several adaptations of the method to discrete problems have been recently proposed. In order 
to solve the three dimensional axial assignment problem (3AP), which is a NP-hard discrete 
problem, the classical operators of PSO were redefined and a parallel algorithm was 
implemented. The proposed algorithm was applied to a set of benchmark problems and results 
were compared with existing from other algorithms for solving 3AP. The evaluation shows 
that the proposed algorithm is competitive. 
 
Keywords: Adaptation continues to discrete, discrete problems, evolutionary method, 
parallel algorithm, particle swarm optimization, three dimensional axial assignment problem. 
 
 
 
 
 
iii 
 
 
 
 
 
 
 
 
 
A mis padres 
A mis hermanos y sobrinitos 
A María de Jesús Martínez González 
 
 
 
 
iv 
 
Agradecimientos 
 
Agradezco a todas las personas que, directa o indirectamente, contribuyeron para que esta 
etapa académica de mi vida llegara a buen término. 
Al Dr. Marco Antonio Castro Liera por su enseñanza, guía, paciencia y disposición. 
Al Dr. Saúl Martínez Díaz a quien considero como una de las personas más importantes 
en mi formación académica. 
A todos los profesores que fueron parte de este proceso y de quienes aprendí mucho: a la 
Lic. María del Carmen Rodríguez Aguilar, M. en C. Jesús Antonio Castro, M. en S.C. Javier 
Alberto Carmona Troyo, M.A.T.I. Luis Armando Cárdenas Florido, M. en C. Bernabé Ortiz y 
Hebert y al Dr. Mario Cortés Larrinaga. 
Al M. en C. Manuel E. Casillas Brook por su amabilidad y por darme todas las facilidades 
en las instalaciones de posgrado para la realización de los experimentos. 
Al Dr. Matthew J. Saltzman por facilitarme los problemas de referencia. 
Al Ing. Jesús Belizario Ruíz Murillo por la oportunidad de trabajo que me ofreció y que 
significó tener los recursos para poder estudiar este posgrado. 
Al Ing. Jonathan Dezi Verduzco Cota por el gran apoyo bibliográfico. 
A todos mis compañeros de la maestría. 
 
 
 
 
 
 
v 
 
Tabla de Contenido 
Sección Página 
 
Resumen i 
Abstract ii 
Dedicatorias iii 
Agradecimientos iv 
Tabla de contenido v 
Lista de figuras vii 
Lista de tablas viii 
I. Introducción 1 
1.1 Definición del problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . 2 
1.2 Justificación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 
1.3 Objetivos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 
1.3.1 Objetivo general. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 
1.3.2 Objetivos específicos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 
1.4 Organización de la tesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 
II. El problema de la asignación axial tres dimensional 6 
2.1 La optimización. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 
2.2 Problemas de optimización combinatorios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 
2.3 Dificultad de un problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 
2.4 Problemas de asignación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 
2.4.1 Asignación generalizada o bidimensional. . . . . . . . . . . . . . . . . . . . . . . . 10 
2.4.2 Problemas multidimensionales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 
III. Optimización por enjambre de partículas 16 
3.1Inteligencia Artificial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 
3.1.1 Escalador de colinas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 
3.1.2 Recocido simulado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 
3.1.3 Búsqueda Tabú. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 
3.1.4 Algoritmos Genéticos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 
3.1.5 Inteligencia colectiva. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 
3.2 Optimización por enjambre de partículas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 
3.3 PSO aplicado en problemas discretos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 
3.4 Implementación de PSO para algunos problemas discretos. . . . . . . . . . . . . . . . . . . 26 
3.5 Métodos heurísticos implementados para la solución de 3AP. . . . . . . . . . . . . . . . . . 29 
IV Implementación, experimentos y resultados 32 
4.1 Redefinición de los operadores de PSO al espaciodiscreto. . . . . . . . . . . . . . . . . . . 33 
4.1.1 Espacio de búsqueda. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 
4.1.2 Representación de la solución. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 
4.1.3 Función de aptitud. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 
4.1.4 Relación de orden. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 
 
 
vi 
 
Tabla de Contenido (Continuación) 
Sección Página 
 
4.1.5 Distancia entre dos partículas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 
4.1.6 Velocidad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 
4.1.7 Suma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 
4.2 Implementación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 
4.2.1 Números aleatorios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 
4.2.2 Inicialización de las partículas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 
4.2.3 Aptitud de las partículas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 
4.2.4 Informantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 
4.2.5 Método principal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 
4.3 Implementación Distribuida. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 
4.3.1 Proceso maestro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 
4.3.2 El proceso esclavo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 
4.4 Resultados experimentales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 
4.4.1 Resultados usando el conjunto de Balaz y Saltzman. . . . . . . . . . . . . . . . 51 
4.4.2 Resultados usando el conjunto se Crama y Spieksma. . . . . . . . . . . . . . . 58 
V. Conclusiones y trabajo futuro 66 
5.1 Conclusiones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 
5.2 Trabajo futuro. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 
Referencias 68 
Apéndice A Configuración básica de PVM en Fedora 14 71 
 
 
 
 
 
 
 
 
 
vii 
 
Lista de Figuras 
Figura 
 
Página 
 
1 Ejemplo de maximización donde se muestra que los óptimos locales no 
garantizan una buena solución. 7 
2 Grafo bipartito para la asignación bidimensional. 11 
3 Selección de n triángulos. 13 
4 Estados del espacio de búsqueda que atrapan al agente escalador de colinas 17 
5 Modificación de la posición de la partícula i . 23 
6 Componentes del análisis de forma. 32 
7 Analogía de un movimiento lineal donde se muestra cómo se pueden dejar 
fuera posiciones prometedoras. 38 
8 Analogía de un movimiento errante, el cual, tiene más probabilidades de 
encontrar mejores posiciones en su trayecto 38 
9 Analogía de un movimiento aplicando el operador  . 40 
 
 
 
 
 
 
viii 
 
Lista de Tablas 
Tabla Página 
I Características de los equipos de cómputo utilizados en las pruebas. 50 
II Descripción de las pruebas implementadas. 51 
III Resultados de la prueba 1. 51 
IV Comparación de los resultados de la prueba 1. 52 
V Comparación de los resultados de la prueba 1 usando /resultado óptimo 52 
VI Resultados de la prueba 2. 53 
VII Comparación de los resultados de la prueba 2. 53 
VIII Comparación de los resultados de la prueba 2 usando /resultado óptimo . 54 
IX Resultados de la prueba 3. 54 
X Comparación de los resultados de la prueba3. 55 
XI Comparación de los resultados de la prueba 3 usando /resultado óptimo . 55 
XII Resultados de la prueba 4. 56 
XIII Comparación de los resultados de la prueba 4. 56 
XIV Comparación de los resultados de la prueba 4 usando /resultado óptimo . 57 
XV Resultados de la prueba 5. 58 
XVI Comparación de los resultados de la prueba 5. 58 
XVII Comparación de los resultados de la prueba 5 usando /resultado óptimo . 59 
XVIII Resultados de la prueba 6. 60 
 
 
ix 
 
 Lista de Tablas (Continuación) 
Tabla Página 
XIX Comparación de los resultados de la prueba 6. 60 
XX Comparación de los resultados de la prueba 6 usando /resultado óptimo . 61 
XXI Resultado de la prueba 7. 62 
XXII Comparación de los resultados de la prueba7. 62 
XXIII Comparación de los resultados de la prueba 7 usando /resultado óptimo . 63 
XIV Resultados de la prueba 8. 64 
XXV Comparación de los resultados de la prueba 8. 64 
XXVI Comparación de los resultados de la prueba 8 usando /resultado óptimo . 65 
1 
 
 
 
Capítulo I 
Introducción 
 
Los problemas de optimización tienen gran relevancia práctica en muchas áreas. El 
problema acerca del plegamiento de proteínas, la optimización de recursos industriales, 
encontrar los parámetros indicados para algún proceso, entre otros, son ejemplos comunes 
donde se requiere de un método que garantice un resultado casi inmejorable. 
La optimización se presenta en dos clases. La primera es la continua y la segunda es la 
combinatoria o discreta. Los problemas combinatorios se caracterizan por tener un número 
muy grande de posibles soluciones y, en general, la mayoría de este tipo de problemas 
encontrados en la vida real están considerados como muy difíciles de resolver. En principio, es 
posible hacer una enumeración de todas las combinaciones que integran al espacio de 
búsqueda para encontrar la solución que cumpla con las restricciones del problema. Sin 
embargo, el número de posibles combinaciones, aunque finito, es muy grande. 
Dada su importancia, la optimización ha sido objeto de estudio desde diferentes tipos de 
enfoques. Muchos problemas pueden resolverse con búsquedas exhaustivas o a través de 
métodos matemáticos exactos como la programación lineal y el cálculo. Sin embargo, existe 
una cantidad considerable de problemas tanto continuos como discretos que presentan 
espacios multimodales. Estos por su dificultad son intratables con técnicas tradicionales. Para 
este conjunto de problemas se han venido empleando otro tipo de métodos enmarcados dentro 
del ámbito de la inteligencia artificial, los cuales, buscan explorar de manera más eficiente el 
espacio de búsqueda. 
Un ejemplo es la optimización por enjambre de partículas (PSO por sus siglas en inglés). 
Esta es una técnica evolutiva basada en poblaciones que fue desarrollada por Kennedy y 
Eberhart en 1995. Este método se basa en el paradigma de inteligencia colectiva y trata de 
2 
 
 
 
emular el comportamiento de los bancos de peces (o parvadas de pájaros) con el objetivo de 
solucionar problemas de optimización continuos y no lineales. 
Los elementos en los que se basa este método son las partículas, las cuales, son soluciones 
potenciales que tienen una posición y velocidad asociada. Estos elementos “vuelan” a través 
de un espacio multidimensional ayudándose de su propia experiencia, del conocimiento del 
enjambre y de operadores estocásticos. De esta manera, se espera que las partículas tiendan a 
concentrarse en áreas potencialmente buenas. 
PSO comparte algunas similitudes con otras técnicas evolutivas como la generación 
aleatoria de la población y el uso de una función de evaluación. Pero a diferencia de otros 
métodos, el número de parámetros que se deben ajustar es pequeño (Eberhart y Shi, 2001). 
Esto hace que la implementación, comparada con otras técnicas evolutivas, sea más sencilla. 
1.1 Definición del problema. 
La optimización por enjambre de partículas ha sido utilizada con gran éxito para solucionar 
problemasde tipo continuo. Algunos ejemplos donde se ha demostrado su efectividad son: 
a. Entrenamiento de redes neuronales (Eberhart y Shi, 2001). Prácticamente, el método 
puede ser aplicado a cualquier tipo de red neuronal. 
 
b. Funciones continuas no lineales (Ching-Jong, et al. 2007). 
En términos generales PSO puede ser utilizado para resolver la mayoría de los problemas 
de optimización. Sin embargo, la definición clásica del método no funciona para problemas 
combinatorios. 
Ahora bien, el problema de asignación axial 3-dimensional es un problema de optimización 
combinatorio que pertenece a la clase NP duro . Esto implica que es un problema no tratable 
con métodos tradicionales. Aun así, se han desarrollado métodos heurísticos y exactos para 
intentar solucionarlo. 
3 
 
 
 
El método de optimización por enjambre de partículas no ha sido adaptado para solucionar 
el problema de asignación axial 3-dimensional y, por lo tanto, no se tienen datos de cuál sería 
el comportamiento de esta técnica para este problema discreto en particular. 
1.2 Justificación. 
La optimización de problemas de tipo discreto sigue siendo un tema abierto de 
investigación. La razón es que muchos problemas tanto teóricos como prácticos caen en esta 
categoría y, normalmente, su espacio de solución es muy complejo. Un enfoque que se ha 
venido aplicando, con el objetivo de encontrar mejores soluciones, es adaptar técnicas que han 
tenido éxito en cierto ámbito a otro completamente diferente. 
Uno de estos casos es la optimización por enjambre de partículas. PSO, como ya se 
mencionó, fue desarrollado inicialmente para resolver problemas continuos; pero algunos 
expertos y académicos empezaron a pensar cómo solucionar otro tipo de problemas de 
optimización con este método (Lu Qiang, et al. 2009). 
Kennedy y Eberhart (1997) fueron los primeros en proponer un método para solucionar 
problemas discretos con PSO utilizando un esquema de código binario (Wei-Neng, et al. 
2009). Desde entonces muchos métodos, basados en esta heurística, se han definido para 
solucionar problemas combinatorios, pero hasta hoy no se ha encontrado un método genérico 
que pueda ser aplicado a la mayoría de los problemas. En general, los algoritmos propuestos 
son específicos al problema a solucionar. Por ejemplo, el método con esquema de código 
binario es muy prometedor para ciertos problemas, pero muchos espacios discretos no caen 
dentro de su ámbito de operación. 
Por lo tanto, la idea de adaptar el método clásico de optimización por enjambre de 
partículas, para solucionar el problema de asignación axial 3-dimensional (3AP), se 
fundamenta en una corriente de investigación vigente e interesada en encontrar métodos 
particulares (o bien genéricos) basados en PSO para solucionar problemas discretos. 
Por otra parte, el problema de asignación axial 3-dimensional surge de un bastante 
número de situaciones prácticas. Por ejemplo, en la inversión de capital, en el lanzamiento de 
4 
 
 
 
satélites, en el montaje de circuitos impresos, manufacturas, teoría de grafos, economía, etc. 
Estos casos de aplicación, junto con otros más, hacen que el estudio de este problema sea aun 
de interés. 
1.3 Objetivos 
1.3.1 Objetivo general 
Implementar un algoritmo basado en la optimización por enjambre de partículas aplicado al 
problema de asignación axial 3-dimensional para determinar su eficiencia y la calidad de sus 
soluciones generadas. 
 1.3.2 Objetivos específicos 
a. Contar con un análisis detallado de las características del problema 3AP y de los 
avances que existen en la optimización por enjambre de partículas para problemas de tipo 
discreto que sirvan de base para proponer un algoritmo que resuelva el problema 3AP. 
b. Diseñar casos de prueba para hacer los ajustes del algoritmo y realizar experimentos del 
algoritmo propuesto con un conjunto de problemas de referencia. 
c. Analizar los resultados para determinar la eficiencia y calidad de las soluciones del 
algoritmo propuesto. 
1.4. Organización de la tesis. 
El resto de este documento está organizado de la siguiente manera: 
Los capítulos II y III contienen las bases teóricas para entender el problema que se está 
tratando. 
En el capítulo II se define de manera formal el concepto de optimización. También, se 
especifican los criterios de este trabajo para definir la dificultad de un problema. Por otra 
parte, se define lo que son los problemas combinatorios. Se hace una descripción general de 
5 
 
 
 
los problemas de asignación haciendo énfasis en el problema de asignación axial 3-
dimensional. 
El capítulo III contiene una descripción de la optimización por enjambre de partículas. En 
primer lugar, se ubica el método en el contexto de la inteligencia artificial y de la inteligencia 
colectiva. Después, se hace una descripción de algunas técnicas heurísticas. Se describe la 
optimización por enjambre de partículas para el caso discreto y se mencionan ejemplos donde 
se ha aplicado. Al final del capítulo, se hace un recuento de algunos métodos que se han 
empleado para solucionar el problema 3AP 
En el capítulo IV se presenta la metodología utilizada para la resolución del problema, se 
hace una descripción del algoritmo implementado, se describen los experimentos realizados y 
se muestran los resultados obtenidos. 
En el capítulo V se presentan las conclusiones así como el trabajo futuro a realizar. 
 
 
6 
 
 
 
Capítulo II 
El Problema de la Asignación Axial 3-Dimensional 
 
2.1 La optimización. 
El objetivo más importante de la optimización es mejorar (Goldberg, 2006), por tal motivo, 
las técnicas de optimización buscan obtener el óptimo global de un problema. Este es un valor 
(o un conjunto de valores) dentro de un espacio de búsqueda que cumple con ciertas 
restricciones y que hace que el costo global del problema sea un máximo o un mínimo. El 
problema de la minimización se puede expresar como sigue: 
min ( )f x , sujeto a: 
( ) 0, 1,...,ig x i p   
( ) 0, 1,...,jh x j n   
 Donde x es el vector solución, ( )f x es la función objetivo, ( )ig x son las p 
restricciones de desigualdad y ( )ih x es el conjunto de restricciones de igualdad. 
(1) 
 En otras palabras, se debe determinar el vector de parámetros x que haga que la función 
objetivo regrese el mejor valor mínimo posible, pero siempre cumpliendo con las restricciones 
de g y h . 
2.2 Problemas de optimización combinatorios. 
Los problemas de optimización se clasifican en dos categorías. La primera involucra 
variables de tipo continuo y la solución del problema es un conjunto de números reales. En la 
otra categoría, se trabaja con variables discretas y, de un conjunto finito, se busca determinar 
algún valor entero, un conjunto, una permutación o un grafo. 
7 
 
 
 
Una instancia de un problema de optimización es un par ( , )F c , donde F es cualquier 
conjunto (el dominio de puntos factibles) y c es la función de costo. 
:c F R (2) 
Entonces el problema consiste en encontrar f F para el cual 
( ) ( )c f c y , para toda y F (3) 
 Como se verá más adelante, no siempre es posible determinar el mejor valor (óptimo 
global) para determinados problemas debido a su dificultad. No obstante, es frecuente que se 
pueda acceder a una solución que comparada con un vecindario sea la mejor. A esta solución 
alternativa se le llama óptimo local, pero no siempre garantizan una buena calidad (fig. 1). De 
manera formal se puede expresar de la siguiente forma: 
Dada una instancia de un problema optimización y un vecindario N , una solución factible 
f F es llamada óptimo local con respecto a N si: 
( ) ( )c f c g Para toda ( )g N f (4) 
Los óptimos locales son una solución alternativa cuando no es posible encontrar el óptimo 
global, siempre y cuando el umbral de error aceptable no sea muy estricto. Pero para algunos 
métodos representan un obstáculo en su camino a encontrarla mejor solución posible. 
 
Figura 1. Ejemplo de maximización donde se muestra que los óptimos locales no 
garantizan una buena solución. 
 
8 
 
 
 
2.3 Dificultad de un problema. 
Dentro del conjunto de problemas de optimización muchos son clasificados como más 
difíciles que otros. En la teoría de la computación se define de manera formal lo que hace a un 
problema computacionalmente difícil. La evaluación del algoritmo, que soluciona el 
problema, es comparado de manera asintótica con funciones conocidas. 
Si un problema, en el peor de sus casos, está acotado por una función polinómica; se dice 
que pertenece a los problemas denominados de clase P (polinómicamente acotado). Los 
problemas pertenecientes a esta categoría pueden ser solucionados en un tiempo polinomial, 
por ejemplo, usando búsquedas exhaustivas. En general, pueden ser resueltos en un tiempo 
( )kO n para alguna constante k , donde nes el tamaño de la entrada del problema (Cormen, et 
al. 2001). 
Por otra parte, están los problemas de la clase NP (no determinista), los cuales, pueden ser 
resueltos por una máquina de Turing no determinística. Es decir, existe un algoritmo no 
determinista polinómicamente acotado (Baase, 2002). Se considera que P NP , a la fecha 
no se ha demostrado que P sea un subconjunto propio de NP . 
Los problemas NP completos son más difíciles que los NP . Si existiera un algoritmo 
polinómicamente acotado para un problema NP completo , también habría un algoritmo 
polinómicamente acotado para todos los problemas NP . 
Existen una gran variedad de problemas que a simple inspección se consideran sencillos, 
pero que en realidad son más complejos de lo esperado. Por lo tanto, es importante poder 
determinar a qué clase pertenece el problema a solucionar. Esta acción, posteriormente, 
permite decidir que técnica (una heurística o un método exacto de solución) es más apropiada 
para ser implementada. 
 El concepto de dificultad también puede ser tratado desde otros puntos de vista. Por 
ejemplo, si solo se considera la solución práctica de un problema (aun cuando pertenezca a la 
clase P ), se puede afirmar que su dificultad está directamente relacionada con el grado del 
9 
 
 
 
conocimiento que tengamos del mismo y con la eficiencia de los algoritmos implementados 
para su solución. Si el algoritmo tarda mucho en encontrar una solución, simplemente se 
puede decir que el problema está clasificado como difícil. Por ejemplo, si un problema de la 
clase P tiene un orden de 100( )O n , se puede considerar intratable. Esto muestra que no todo 
problema en P es sencillo ya que no siempre se cuenta con un algoritmo con una eficiencia 
aceptable. 
El conocimiento que se tenga del problema a resolver es importante. Algunos problemas 
NP Completos pueden ser tratados aplicando restricciones adicionales en sus entradas. Esta 
acción, usualmente, no garantiza que el problema deje de ser NP Completo ; pero, algunas 
veces, es probable que un criterio alterno produzca un problema de clase P (Baase, 2002). 
Por otra parte, la dificultad de un problema de optimización, en un espacio dado de 
búsqueda, es la probabilidad de no encontrar una solución al escoger una posición aleatoria en 
una distribución uniforme (Clerc, 2006). Si la probabilidad de encontrar la solución de un 
problema, sin hacer ningún trabajo especial y al primer intento, es grande; se trata de un 
problema sencillo. 
La definición anterior nos da la posibilidad de contar con un criterio para poder estimar la 
dificultad de los problemas, y así, tener una herramienta de evaluación de los algoritmos 
propuestos. Para ello, la dificultad se especifica por la siguiente fórmula: 
ln(1 _ _ )Dificultad probabilidad de error   (5) 
Lo cual implica que: 
ln( _ _ )Dificultad probabilidad de éxito  (6) 
Resulta obvio que las restricciones pueden jugar un papel importante para reducir la 
complejidad de un problema. Por ejemplo, si alguna restricción ε es ajustada, es probable que 
algunos óptimos locales aceptables puedan ser alcanzables. 
10 
 
 
 
Otra forma de reducir la dificultad de un problema es a través de la modificación del 
espacio de búsqueda. Solo se debe hacer si existe un grado de flexibilidad en la calidad de los 
resultados que se esperan encontrar. 
Las modificaciones a las restricciones (o del espacio de búsqueda) no garantizan la 
disminución de la dificultad. Puede suceder que la complejidad del problema aumente. Por 
otro lado, no siempre es posible hacer modificaciones al espacio de búsqueda porque 
normalmente se necesita un conocimiento del problema que en la mayoría de las ocasiones no 
se tiene. 
2.4 Problemas de asignación. 
2.4.1 Asignación generalizada o bidimensional 
Los problemas de asignación abordan el problema de cómo asignar nelementos a otros n 
distintos (Sahu, Tapadar, 2007). Una manera de ver este problema es como un mapeo 
biyectivo  entre dos conjuntos finitos U y V de n elementos. Al identificar los conjuntos U 
y V se puede representar la asignación por medio de una permutación. 
1 2 … 3 
φ (1) φ(2) … φ(n) 
(7) 
De esta manera cada elemento de V es mapeado por ( )x , donde x U . 
La permutación φ corresponde a la una matriz de permutación ( )ijX X  , donde: 
1
0ij
x 

 
(8) 
Cada renglón y columna tienen una sumatoria que resulta igual a uno. A esto se le llaman 
restricciones de asignación y se pueden representar como sigue: 
1, si ( )j i 
11 
 
 
 
1
1, 1, 2,...,
n
ij
j
x i n

  
(9) 
1
1, 1, 2,...,
n
ij
i
x j n

  
 
0,1
, 1,2,...
ijx
i j n

 
 
 
Otra manera de representar el problema es por medio de un grafo bipartito (fig. 2). Este es 
un grafo G donde sus vértices quedan definidos en dos subconjuntos disjuntos con idéntica 
cardinalidad. Cada arista asocia a dos elementos de cada subconjunto de manera biyectiva. 
( , )G V A (10) 
Donde: 
V Son los vértices de G . Además, 1 2V v v  y 1 2v v Nulo  
A Son las aristas de G siempre de la forma ,a b A 1a v y 2b v 
 
Figura 2. Grafo bipartita para la asignación bidimensional 
Sea nS el conjunto de todas las permutaciones tales que φ ∈ nS . Si, a su vez, se tiene 
asociada una matriz de costos nxn definida como ( )ijC c , donde ijc define el costo de 
asignar i con j , entonces el problema consiste en encontrar en nS la permutación φ que 
12 
 
 
 
minimice el costo total (Sahu, Tapadar, 2007). Este es un problema de optimización 
combinatoria y está formulado como: 
( )
1
min
n
n
i iS i
C 

 
(11) 
El espacio de búsqueda para encontrar  es de !n elementos. Esto implica que existe un 
número muy grande de asignaciones para valores de n incluso pequeños. Sin embargo, este 
problema se ha solucionado con métodos exactos como el método húngaro. 
2.4.2 Problemas multidimensionales. 
Los problemas de asignación multidimensionales fueron introducidos por primera vez por 
Pierskalla en 1967 como una extensión del clásico problema de asignación bidimensional (M. 
Aiex, et al 2005). Para el caso de la asignación 3-dimensional dos modelos han sido 
investigados: el problema de la asignación axial 3-dimensional y el problema de la asignación 
3-dimensional planar. 
El problema de asignación axial 3-dimensional se puede representar de varias formas. Por 
ejemplo, como un problema bilineal entero. 
, 1 1 1
min
n
n n n
ijk ij ikY Z X i j k
c y z

  
   
(12) 
Donde:C es la matriz de costos, ,Y Z son las matrices de permutaciones y nX es el conjunto 
de todas las matrices de n n . 
Este problema también se puede definir como sigue: dado un grafo tripartito completo 
, , ( , ( ) ( ) ( ))n n nK I J K I J I K J K        , donde , ,I J K son conjuntos disjuntos de 
tamaño n , y una matriz de costos ijkC para cada triángulo ( , , )i j k I J K   . El problema de 
asignación axial 3-dimensionalconsiste en encontrar un subconjunto A de n triángulos (fig. 
13 
 
 
 
3), A I J K   de tal manera que cada elemento de I J K  ocurra en exactamente un 
triángulo de A , y el costo ( )C A de los triángulos seleccionados sea un mínimo (Crama y 
Spieksma, 1992). 
 
Figura 3. Selección de n triángulos 
El problema también puede ser descrito como un problema lineal entero (Spieksma, 2000). 
Dados 3 conjuntos de tamaño n ( 1A , 2A y 3A ) para cada par de tripleta en 1 2 3A A A  un 
número es conocido ya sea un costo o una ganancia. El problema consiste en encontrar n 
tripletas tales que cada elemento en 1 2 3A A A  sea exactamente una tripleta. Por lo tanto, las 
n tripletas requeridas maximizan o minimizan el costo total. 
Para el caso de la minimización se tiene que las restricciones de asignación son las 
siguientes: 
1 1 1
m in
n n n
ijk i jk
i j k
C X
  
   
(13) 
Sujeto a: 
1 1
1
n n
ijk
i j
X
 
 , para 1,...,k n 
 
14 
 
 
 
1 1
1
n n
ijk
i k
X
 
 , para 1,...,j n 
1 1
1
n n
ijk
j k
X
 
 , para 1,...,i n 
0,1ijkX  , para , , 1,...,i j k n 
 Si se alinean las n tripletas seleccionadas, se obtienen tres permutaciones de 1,2,...,n 
(Huang y Lim, 2006). Sin embargo, ya que el orden de las permutaciones no es relevante, la 
primera se puede dejar fija sustituyéndola por un índice i. 
De esta manera el problema se puede redefinir de la siguiente forma (Burkard, et al. 2009): 
Sean 3n coeficientes de costo dados de ( , , 1, 2,..., )ijkC i j k n . El problema ahora consiste en 
encontrar dos permutaciones  y  tales que: 
( ) ( ), 1
min
n
n
i i iS i
C   

 
(14) 
Donde: nS es el conjunto de todas las permutaciones de los enteros 1,2,.., n. 
Dado que las permutaciones a ser seleccionadas pueden ser escogidas de manera arbitraría, 
el problema de asignación axial 3-dimensional tiene 2( !)n soluciones factibles. El problema es 
NP-duro (Karp, 1972). No existe un algoritmo que pueda resolver el problema en un tiempo 
polinomial a menos que P = NP. Incluso cuando ijkC solo puede tomar dos valores, el 
problema permanece NP-duro. 
El problema de asignación axial 3-dimensional presenta algunos casos especiales (Crama, 
Spieksma, 1992). El primero es  donde la distancia (verificando las desigualdades del 
triángulo) se define como un conjunto de puntos, y el costo del triángulo es la suma de las 
longitudes de sus lados, pero si la suma de las longitudes son sus lados más cortos, entonces se 
trata del problema S . 
15 
 
 
 
Yves Crama y Frits C.R. Spieksma (1992) demostraron que incluso estos dos casos 
especiales siguen siendo NP-duros. 
 
16 
 
 
 
Capítulo III 
Optimización por enjambre de partículas 
 
3.1 Inteligencia Artificial 
La inteligencia artificial (IA) tiene sus orígenes en muchas disciplinas. Algunas de las más 
importantes son la filosofía, las matemáticas, la psicología, neurociencias y, por supuesto, las 
ciencias computacionales. Junto con otras, cada una de estas han hecho importantes 
aportaciones (Russell y Norving, 2006). 
La filosofía ha intentado dar explicaciones a muchas interrogantes acerca del pensamiento 
humano y el razonamiento desde épocas muy remotas. Para ello, ha desarrollado modelos que 
buscan esclarecer los fenómenos mentales como el conocimiento. La IA toma estos modelos y 
los formaliza a través de las matemáticas con la intención de aplicarlo en problemas 
específicos. Las matemáticas han aportado a la inteligencia artificial formalidad a través de su 
notación. Además, la mayoría de las técnicas de la IA utilizan muchos conceptos de la lógica, 
la probabilidad, la estadística y otros campos de las matemáticas. 
Los problemas que trata la inteligencia artificial abarcan un espectro muy amplio, y están 
clasificados en tareas de la vida diaria, tareas formales y tareas de los expertos (Rich y Knight, 
1994). En general, la IA aborda problemas poco estructurados donde no se conoce el mejor 
método para resolverlos. Algunos ejemplos son la visión, el habla, el sentido común, juegos, 
demostración de teoremas, optimización, diagnósticos y los sistemas de control. 
Dentro de las ramas de la inteligencia artificial se encuentra la denominada soft-computing, 
la cual, es una colección de técnicas y herramientas computacionales que comparten 
disciplinas muy relacionadas (Konar, 1999). En concreto, es un conjunto de metodologías que 
tienen como objetivo explotar la tolerancia a la imprecisión y la incertidumbre para lograr 
soluciones manejables, más robustas, y con un costo bajo (Azvine, et al, 2000). En esta 
17 
 
 
 
categoría de técnicas se encuentran la lógica difusa, el razonamiento probabilístico, los 
modelos conexionistas y los algoritmos evolutivos. 
El paradigma principal en la IA, para la resolución de problemas de optimización, es la 
búsqueda heurística. Este es un método muy general que se puede aplicar a muchos tipos de 
problemas difíciles con el fin de encontrar una solución en un tiempo prudente, pero sin 
garantizar que esta sea la solución óptima (global). Su objetivo es que casi siempre se 
encuentre una buena solución. 
Existen muchos algoritmos de búsqueda heurísticos (incluyendo a PSO). Estos han sido 
implementados para resolver una diversidad grande de problemas de optimización continuos y 
discretos. A continuación se presenta una breve descripción de algunas técnicas heurísticas 
ampliamente utilizadas. 
3.1.1. Escalador de colinas. 
El agente, a partir de su estado actual en un espacio de búsqueda, examina su vecindario y 
determina la dirección a tomar. Este paso lo repite N veces o hasta que ya no puede encontrar 
mejoría. El algoritmo utiliza una función de evaluación para determinar si una posición es 
mejor que otra. 
Su desventaja se debe a que el agente puede quedar atrapado en estados que no son el 
objetivo. Los lugares que limitan su movimiento son los máximos locales y mesetas (fig. 4). 
Una forma de solucionar este problema es reiniciar el ascenso desde puntos aleatorios varias 
veces, pero conservando el mejor valor encontrado hasta cierto instante. 
 
Figura 4. Estados del espacio de búsqueda que atrapan al agente escalador de colinas 
18 
 
 
 
3.1.2 Recocido simulado. 
Es una variante del escalador de colinas, pero el movimiento del agente es muy intenso 
(contiene mucha energía) en las primeras etapas de la búsqueda con el objetivo de evitar caer 
en algún óptimo local. Conforme avanza la ejecución del algoritmo, se reduce la energía hasta 
alcanzar un estado final de mínima energía. 
La idea principal es que un resultado parcial malo no sea ignorado del todo. Puede 
convertirse en el estado actual con una probabilidad 'p . 
' /E Tp e   , donde T es la temperatura, E es la energía del sistema y  es la 
diferencia entre el estado actual y el nuevo valor calculado. 
(15) 
La velocidad con la que se enfría el sistema a lo largo del proceso se denomina programa 
de enfriamiento (Rich y Knight, 1994) y afecta notablemente la calidad de las soluciones 
encontradas. 
3.1.3 Búsqueda Tabú. 
Se basa en la utilización de estructuras de memoria flexibles (para explorar un conjunto de 
estados factible) junto con criterios de aspiración y restricciones estratégicas (Ríos Insua, et al. 
2009). Este método admite movimientos potencialmente malos y utiliza una lista donde 
guarda temporalmente movimientos realizados marcados como prohibidos. El objetivo de la 
lista es no caer en espacios repetidos. Sin embargo, si algún elemento de la lista supera los 
criterios de aspiración, es aceptado. Esto permite que movimientos potencialmente buenos (de 
la lista) no queden bloqueados del todo. El algoritmo termina cuando un número de iteraciones 
se cumple o cuando un umbral específico es alcanzado. 
3.1.4 Los algoritmos genéticos. 
Los algoritmos genéticos son métodos de búsqueda basados en la mecánica de laselección 
natural y la transferencia de material genético (Goldberg, 2006). Estos algoritmos operan 
sobre poblaciones donde en cada generación nuevos individuos (cromosomas) son generados a 
19 
 
 
 
partir de una serie de operadores estocásticos (operadores genéticos). Los individuos 
representan a las soluciones potenciales del problema a resolver y pueden codificarse como 
cadenas de bits, números reales o vectores de números enteros. 
Los algoritmos genéticos consisten básicamente de cuatro etapas (Tim Jones, 2005). El 
primer paso es la inicialización de los individuos de manera aleatoria. Después, se obtiene la 
aptitud de cada uno de ellos con base en la función de evaluación. Posteriormente, se 
selecciona un conjunto de individuos a ser recombinados. La selección, entre otras formas, 
puede realizarse por el método de la ruleta (basado en la proporción de la aptitud con respecto 
a la de los demás) o por torneo (eliminación directa entre dos candidatos). Por último, el 
algoritmo, a partir de la recombinación de los individuos seleccionados, genera nuevos 
cromosomas utilizando los operadores de cruce y mutación. 
El operador de cruce toma dos cromosomas y selecciona en ellos un punto de manera 
aleatoria y, a partir de ese lugar, intercambia las partes de los individuos. Por otra parte, la 
mutación se utiliza para generar material genético nuevo con el objetivo de evitar que el 
algoritmo se estanque en algún óptimo local. Este proceso, regularmente, se efectúa con una 
probabilidad pequeña. El proceso consiste en seleccionar un punto aleatorio dentro del 
cromosoma y cambiar su valor. 
El algoritmo termina después de cierto número de iteraciones o por algún otro criterio de 
parada relacionado con la aptitud. 
3.1.5 Inteligencia colectiva. 
Algunas técnicas heurísticas están basadas en la inteligencia colectiva. Este paradigma se 
fundamenta en el comportamiento colectivo de sistemas descentralizados y auto-organizados. 
Normalmente, consisten de una población de agentes que interactúan entre sí en un espacio de 
búsqueda. 
Comúnmente, la interacción no es dictada por un control centralizado, sino que cada 
individuo de la población sigue reglas simples. Este modo de actuar, combinado con un 
20 
 
 
 
número de iteraciones, genera en la población un comportamiento más complejo. Aun cuando 
el trabajo es colectivo, cada elemento de la población es considerado una solución potencial. 
Un ejemplo de estas técnicas es la optimización por colonia de hormigas (ACO). Esta 
heurística está inspirada en el comportamiento que siguen las hormigas cuando buscan 
alimento a partir de su hormiguero. Las hormigas dejan un rastro temporal de feromonas en su 
camino. Entre más hormigas sigan el rastro, la intensidad de este aumenta y, entre más intenso 
sea, tiene más probabilidades de que otras hormigas lo sigan. Debido a la volatilidad de la 
feromona, los caminos cortos tienen a estabilizarse mientras que los largos se vuelven débiles 
y tienden a desaparecer. Así, la solución es la ruta más corta encontrada al final del algoritmo. 
3.2 Optimización por enjambre de partículas (PSO). 
Dentro de las heurísticas de la inteligencia colectiva se encuentra la optimización por 
enjambre de partículas. Esta es en una técnica evolutiva que fue propuesta por Kennedy y 
Eberhard (1995). Este método fue descubierto a través de un modelo social simplificado y 
está inspirado en el comportamiento social de organismos como los bancos de peces o 
bandadas de aves. 
Se ha demostrado que PSO es una técnica muy eficiente para resolver problemas de 
optimización de tipo continuo. Particularmente, PSO es un método que genera mejores 
resultados para problemas catalogados como difíciles. Sin embargo, se ha observado que su 
desempeño en problemas lineales no es muy bueno. 
Una aplicación de PSO, que ha tenido gran éxito, es el entrenamiento de redes neuronales. 
Prácticamente cualquier modelo conexionista puede ser entrenado por un algoritmo basado en 
PSO. Una ventaja que esta técnica tiene con respecto a otras se debe a su nula necesidad de 
requerir el gradiente de la función de activación. 
Una solución potencial es representada en PSO por un vector llamado partícula, individuo, 
elemento, agente o simplemente solución. Cada una de estas partículas i tiene la misma 
dimensión n y se representan de la siguiente manera: 
21 
 
 
 
( ,1 ) ( , 2 ) ( , )( ) ( , , . . . , )i i i nX i x x x 
(16) 
Las partículas, sobre el espacio de búsqueda n-dimensional, “vuelan” tratando de encontrar 
una solución óptima. Para hacer esto, cada individuo ajusta su posición de acuerdo a una 
combinación lineal de su inercia, su propia experiencia y del conocimiento del enjambre. 
Cada agente almacena en una memoria la mejor posición encontrada (visitada) hasta el 
instante actual t . La experiencia de la partícula se denota como: 
( ,1 ) ( , 2 ) ( , )( ) ( , , . . . , )i i i nP i p p p 
(17) 
El conocimiento del enjambre es el conjunto de memorias de cada partícula. A diferencia 
de los algoritmos genéticos, en PSO no existe la competencia entre individuos. Por lo tanto, la 
interacción entre las partículas, para obtener un beneficio, es la norma. Para hacer esto, cada 
partícula pone a disposición de los demás su memoria de conocimiento. 
La asignación de informantes (vecindario) es una forma de compartir la experiencia. Cada 
partícula recibe información de k agentes seleccionados de forma aleatoria en cada iteración 
del algoritmo. Después, la partícula determina entre sus informantes aquel que tenga la mejor 
aptitud previa. Posteriormente, lo selecciona para que sea parte del proceso de actualización de 
su posición. Normalmente, el valor de k es pequeño (método lbest), sin embargo, puede ser 
tan grande como el tamaño del enjambre (método gbest). Este último criterio hace que las 
partículas tiendan hacia la mejor partícula encontrada hasta algún instante t . Las 
características del problema a solucionar determinan cual de los dos métodos es más adecuado 
para su implementación. 
 La mejor partícula del vecindario se representa por: 
( ,1 ) ( , 2 ) ( , )( ) ( , , . . . , )i i i nG i g g g 
(18) 
Al igual que en otros algoritmo de tipo evolutivo, PSO necesita de una función de 
evaluación (también llamada función de aptitud). Esta permite determinar la calidad de las 
22 
 
 
 
soluciones. Su importancia radica en que es la única forma de poder evaluar la posición de 
cada elemento. 
Cada coordenada (elemento) de X de cada partícula tiene una velocidad o razón de cambio 
V , 1, 2,...,d n . 
( ,1 ) ( , 2 ) ( , )( ) ( , , . . . , )i i i nV i v v v 
(19) 
Para realizar un desplazamiento, la partícula determina la velocidad considerando su propia 
inercia W (busca evitar la convergencia prematura), su memoria de conocimiento y su 
confianza en el enjambre, para después, sumarla a la posición actual. 
El grado de confianza lo determinan los operadores aleatorios 1r y 2r (en el rango 0-1) 
junto con los coeficientes de confianza 1c y 2c . Estos últimos, también llamados constantes de 
aceleración, son los términos que tiran a cada partícula hacia las posiciones P y G (Eberhart y 
Shi, 2001). 
En otras palabras, las partículas hacen un movimiento hacia un punto intermedio tomando 
en cuenta la mejor posición previa, el mejor informante y un punto accesible desde la posición 
actual (fig. 5). El ajuste de la posición de las partículas es conceptualmente similar a la 
operación de cruce usado por los algoritmos genéticos (Kennedy, 1996). 
Las ecuaciones siguientes ajustan la velocidad y posición de cada partícula: 
1
1 1 2 2( ) ( )
t t t t t t t
i i i i i iV w V c r P X c r G X
      (20) 
1 1t t t
i i iX X V
   (21) 
Donde: 
1t
iV
 , Velocidad ajustada 
tW , Inercia del propio movimiento 
1c Coeficiente de confianza en la experiencia 
23 
 
 
 
2c Coeficiente de confianzaen la experiencia del grupo 
iP Mejor posición previa de i 
t
iX Posición actual de i 
iG Mejor posición previa encontrada por el grupo 
1
tr y 2
tr Operadores aleatorios entre 0 y 1. 
1t
iX
 Posición de la partícula i después del ajuste. 
 
 
Figura 5. Modificación de la posición de la partícula i . 
Debido a que en el proceso de actualización de la velocidad están inmiscuidos operadores 
aleatorios, el método de modificación de la posición de las partículas se puede considerar a fin 
de cuentas un paso estocástico, pero heurístico. 
 En términos generales, PSO se puede describir en tres pasos. El primero es evaluar cada 
elemento para determinar la calidad de la posición actual. Esto permite que se puedan 
encontrar la mejor y las mejores partículas. Después, se deben realizar los ajustes necesarios 
de las mejores posiciones previas. Por último, se determinan los nuevos desplazamientos para 
cada partícula con la información ajustada. Por analogía, estos movimientos no son más que 
una forma de tratar de imitar a otros individuos. 
24 
 
 
 
Para detener el proceso se necesita que un criterio de parada se cumpla. Este puede ser 
determinado por un número fijo de ciclos, opcionalmente, combinado con un umbral de error 
aceptable. Al terminar la ejecución del algoritmo, la solución que reporta el método es la 
mejor posición previa encontrada por alguna partícula l. 
De manera más detallada, el método de PSO se describe como sigue: 
a. Inicializar la población. La posición de cada una de las partículas es determinada de 
manera aleatoria. 
b. La mejor posición previa es igualada a la posición actual. 
c. Cada posición es evaluada en la función de aptitud para determinar la calidad de la 
solución. 
d. Se compara la aptitud de la posición actual con la mejor previa. 
e. Asignar informantes (vecindario) de tamaño k a la partícula. 
f. Determinar la mejor partícula del vecindario. 
g. Ajustar la velocidad. 
h. Ajustar la posición. 
i. Verificar si se cumple el criterio de parada. 
j. Si no se cumple, regresar al paso e. 
La versión original de PSO presentaba algunas desventajas. Si la mejor solución está 
estancada en algún óptimo local, todas las partículas tenderán rápidamente a concentrarse en 
ese punto (Afsahi, 2011). Otra importante desventaja era su poco control para tener un balance 
entre la exploración y la explotación. Para contrarrestar estos problemas, se utiliza el 
coeficiente de inercia W (Abdel-Kader, 2011). 
3.3 PSO aplicado en problemas discretos. 
Si se considera la definición clásica de PSO, se pueden apreciar características de este 
método que lo hacen una técnica poco apropiada para resolver problemas discretos. Los 
conceptos que la integran están pensados para espacios continuos donde la velocidad de la 
partícula queda determinada por una combinación lineal. 
25 
 
 
 
Aun así, muchos investigadores (incluyendo a Kennedy y Eberhart) han desarrollado 
versiones de esta heurística con el objetivo de aplicarla a los problemas discretos. Sin 
embargo, no existe un algoritmo de optimización por enjambre de partículas que pueda ser 
aplicado a todos los problemas de tipo discreto. Los algoritmos propuestos contienen 
características muy particulares del problema a tratar o del ámbito a solucionar como muestran 
Langeveld y Engelbrecht (2011) en el algoritmo genérico de optimización por enjambre de 
partículas basado en conjuntos. 
En la búsqueda por encontrar un método más completo para aplicar PSO en cualquier 
problema combinatorio, los enfoques utilizados se pueden clasificar en cuatro (Wein-Neng, et 
al. 2010): 
a. Basados en operadores de intercambio. El algoritmo define la posición de la partícula 
como una permutación de números y la velocidad como un conjunto de intercambios. 
 
b. Transformación del espacio. La posición es definida como un vector real y una técnica 
de transformación del espacio es usada para convertir la posición en su correspondiente 
solución. 
 
c. Matrices difusas. Estos métodos definen a la posición y a la velocidad como matrices 
difusas. Se necesita un operador que, en el dominio discreto, decodifique la matriz 
difusa en una solución posible. 
 
d. Algoritmos híbridos. Se trata de cualquier enfoque que utilice una búsqueda local para 
buscar mejorar la solución. Esta estrategia, llamada hibridación del método, se aplica en 
alguna etapa del algoritmo principal y, en general, pretende mejorar la solución 
encontrada hasta algún instante t 
Se observa en la literatura que la mayoría de los esfuerzos hechos al emplear PSO en 
problemas no continuos están acompañados de búsquedas locales. 
26 
 
 
 
Los operadores aritméticos, usados en las ecuaciones de velocidad y posición (incluyendo 
la suma, resta y multiplicación), deben ser redefinidos (Jin Qin, et al. 2011) para poder 
solucionar problemas discretos complejos sobre espacios combinatorios. Esta redefinición 
debe tener como objetivo encontrarles un significado práctico en el ámbito del problema a 
solucionar. 
Los siguientes elementos son necesarios para implementar PSO en un problema discreto 
(Clerc, 2006): 
a) Un espacio de búsqueda H . 
b) Una forma de representar las posiciones x H . 
c) Una función f definida en el espacio de búsqueda H tal que ( ) ,f x c c C  . 
d) Una relación de orden  , 'c c . 
e) Una definición de distancia para  , 'x x . 
f) La velocidad de la partícula. 
g) Resta (posición, posición)velocidad. 
h) Multiplicación externa (número real, velocidad)velocidad. 
i) Suma (Velocidad, velocidad)Velocidad. 
j) Desplazamiento (posición, velocidad)posición. 
Esto se debe a que todos estos elementos están integrados en las ecuaciones de velocidad y 
movimiento. Su redefinición, generalmente, es lo que ocasiona una nueva interpretación de los 
conceptos de velocidad y movimiento. 
3.4 Implementación de PSO para algunos problemas discretos. 
El primer intento, para extender PSO para problemas discretos, es el algoritmo binario de 
PSO (Wei-Neg, et al. 2010) propuesto por Kennedy y Eberhart. Está basado en un esquema de 
código binario y muchas variantes surgieron tomándolo como referencia. Sin embargo, no se 
ha encontrado un algoritmo genérico y, normalmente, se considera un método útil solo para 
ciertos problemas que puedan representarse con las estructuras que maneja el método. 
27 
 
 
 
Otro ejemplo, del uso de PSO en problemas discretos, es el Algoritmo PSO híbrido multi-
criterio con comunicaciones para la optimización combinatoria (Lakshmi, 2010). Este 
algoritmo utiliza el concepto de múltiples enjambres; pero el tamaño de los cúmulos 
propuestos, a diferencia de otros algoritmos, es dinámico y opera con un tamaño pequeño. El 
objetivo principal de este algoritmo es la optimización de problemas multi-objetivos. Los 
autores señalan que este algoritmo, comparado con otros, es muy competitivo. 
Se ha aplicado PSO con redes bayesianas para la selección de atributos en la minería de 
datos (Correa, et al. 2007). Este algoritmo también utiliza variables discretas, pero las 
poblaciones que utiliza tienen partículas de tamaño variable. Esto hace que cada solución 
tenga un número constante de atributos a través de las iteraciones. Por otra parte, el concepto 
de velocidad es redefinido como una probabilidad. Es decir, hace que la velocidad sea como 
un vecindario proporcional para después estimar nuevas posiciones. La desventaja, que este 
algoritmo presenta, es que para que tenga un buen desempeño, el número de atributos debe ser 
pequeño. 
En un ámbito parecido, se ha implementado PSO en conjunto con operadores genéticos 
para la agrupación de documentos (Premalatha y Natarajan, 2009). Si las partículas tienden a 
estancarse en un óptimo local, se agrega la reproducción al procedimiento utilizando los 
operadores de cruce y mutación definidos en los algoritmos genéticos. Esto permite una 
convergencia más rápidahacia soluciones de mejor calidad. 
PSO también ha sido adaptado para solucionar el problema de planificación flexible 
trabajo-tienda (Jun-qing Li, et al. 2009). De nuevo fue necesario incorporar una técnica 
auxiliar para hacer el algoritmo híbrido. En este caso la técnica usada fue la búsqueda tabú. En 
general, se propone una representación de las partículas a través de cromosomas. Además, los 
operadores clásicos de PSO son adaptados para utilizar funciones de cruzamiento y mutación 
similares a los algoritmos genéticos. En cada generación o iteración, se le aplica la búsqueda 
tabú a la mejor solución encontrada hasta ese momento con el objetivo de mejorarla. El 
algoritmo es competitivo comparado con los algoritmos genéticos implementados para 
28 
 
 
 
resolver este mismo problema, sin embargo, el tiempo de ejecución es alto y el algoritmo es 
poco robusto. 
Un problema al que se recurre frecuentemente para solucionarlo con PSO es el problema 
del agente viajero (TSP). Uno de estos métodos implementados es el algoritmo de 
optimización por enjambre de partículas mejorado (Yang y Wang, 2007). Este algoritmo se 
centra en la utilización de un depresor para evitar la convergencia prematura. Para ello, se 
apoya en un medidor de diversidad que permite variar el valor del depresor. El algoritmo es 
competitivo, pero no es superior a otros métodos. 
Otro enfoque utilizado es el método basado en conjuntos (Wei-Neng, et al. 2010). Primero, 
este algoritmo busca caracterizar el espacio discreto a través de representaciones basadas en 
conjuntos. Segundo, Las soluciones candidatas son redefinidas como un conjunto y la 
velocidad queda representada por un conjunto de posibilidades. Todos los operadores de PSO 
clásico (como los aritméticos, las reglas de ajuste de la velocidad y posición) son remplazados 
por operadores de la teoría de conjuntos. Una desventaja que presenta este método es su poca 
generalización ya que está claramente definido para resolver ciertos problemas combinatorios. 
El algoritmo genérico de optimización por enjambre de partículas demuestra la viabilidad 
de usar PSO para resolver problemas basados en conjuntos (Langeveld y Engelbrecht, 2011). 
Un objetivo particular de este método es encontrar un conjunto de parámetros que, aplicado a 
los 33 problemas de prueba, generen buenas soluciones. Aunque no se encontró, el algoritmo 
es lo suficientemente robusto para ser aplicado a cualquier problema que se pueda especificar 
como un problema basado en conjuntos. 
 Finalmente, se sabe que la implementación en paralelo de algoritmos puede tener varias 
ventajas como la disminución del tiempo de ejecución. Además, el desarrollo de aplicaciones 
paralelas ya no está confinado a grandes y costosos equipos (Castro Liera, et al. 2011). Esto 
hace que exista una mayor tendencia a desarrollar e implementar algoritmos distribuidos de 
manera directa. 
 
29 
 
 
 
3.5. Métodos heurísticos implementados para la solución del 3AP. 
Muchas técnicas se han empleado para solucionar el problema 3AP. Existen algunas que 
utilizan la enumeración implícita, pero estas implementaciones, aún en paralelo, han sido 
incapaces de resolver problemas de tamaño real (Centeno, 2010). 
Como 3AP es un problema combinatorio, la mayoría de técnicas heurísticas usadas para su 
solución son aquellas que ya han demostrado ser muy eficientes en la resolución de problemas 
discretos como la búsqueda tabú, los algoritmos genéticos y la optimización por colonia de 
hormigas. 
El uso de algoritmos híbridos es muy común. Se observa en la literatura que los algoritmos 
implementados, para solucionar 3AP, necesitaron en algún punto utilizar algún proceso 
auxiliar para mejorar la calidad de sus soluciones. Por ejemplo, la utilización de un algoritmo 
genético con alguna técnica de búsqueda local. Algunas veces, el proceso auxiliar es utilizado 
como una inicialización para que, posteriormente, el método principal del algoritmo tome esos 
valores e inicie su proceso. 
Ese es el caso del algoritmo S-FANT, el cual, es un método basado en la optimización por 
colonia de hormigas (Jiang, et al. 2008). El algoritmo consiste en dos fases. En la primera, 
llamada fase de muestreo, se utiliza un esquema de múltiples reinicios para generar óptimos 
locales. En la segunda etapa, la feromona es inicializada de acuerdo a la frecuencia de las 
tripletas que aparecen en esos óptimos locales. Posteriormente, el método estándar de ACO es 
aplicado para mejorar esas soluciones potenciales. 
Los algoritmos genéticos también han sido empleados para resolver 3AP, sin embargo, se 
observa que utilizar solo el algoritmo genético no genera muy buenas soluciones. Se advierte 
que para implementar un algoritmo genético para 3AP se encuentra difícil implementar de 
manera conjunta el operador de mutación junto con el de cruzamiento (Gonzalez y Centeno, 
2001). Además, para obtener mejores resultados es necesario aumentar el tamaño de la 
población. González propuso en su algoritmo no utilizar el cruce, pero si la mutación. En este 
30 
 
 
 
caso, se comprobó que un número elevado de mutaciones es conveniente para obtener mejores 
resultados. 
Un método que utiliza un algoritmo genético para solucionar 3AP se puede mejorar 
implementando una búsqueda local. Por ejemplo, es bien conocido que el Método húngaro 
puede resolver el problema de asignación 2-dimensional (2AP) de una forma eficiente. Este 
hecho es utilizado en el algoritmo genético híbrido (Huang y Lim 2006). La idea principal de 
este método es remplazar el operador de mutación por una búsqueda local utilizando el 
método húngaro. Para hacer esto, es necesario hacer una proyección de 3D a 2D. Es decir, la 
solución del problema 3AP consiste de dos permutaciones  y  mientras que 2AP consiste 
solamente de una; pero si una permutación (del caso 3AP) se fija, entonces la optimización de 
la segunda permutación se convierte en un problema 2AP. Esto es equivalente a construir un 
grafo bipartita a partir de uno tripartita. 
Dada una solución inicial para 3AP ( , ), entonces: 
Sea , ( ),ij i i jd C  entonces , 1, 2,..,i j n  se tiene que: 
( ) ( ) , ( ), 1 1
min min
n n
n n
i i i i iS Si i
C d     
 
  
(22) 
Usando la misma idea, se pueden definir otras dos formas de hacer la proyección: 
Sea , , , ( )i j i j id C  , , 1, 2,..,i j n  (23) 
 
Sea , , ( ), ( )i j j i id C   , , 1, 2,..,i j n  (24) 
El método anterior también utiliza una técnica de múltiples reinicios que encuentra buenos 
resultados en un tiempo muy corto. Sin Embargo, una vez que localiza un óptimo local ya no 
le es posible mejorarlo. Aún si se le da más tiempo al algoritmo, este no puede mejorar la 
solución. 
31 
 
 
 
Por otra parte, GRASP es una meta-heurística (heurística guiada por otra heurística) de 
múltiples reinicios para problemas combinatorios. Usualmente consiste de un procedimiento 
ávido de construcción y de una búsqueda local. GRASP con redefinición de vínculos fue 
implementado para solucionar el problema 3AP. La idea principal del método es explorar 
trayectorias que conectan soluciones de alta calidad. En general es una meta-heurística que 
genera buenos resultados, pero la eficiencia no es muy buena al ser comparada con otros 
métodos. Una ventaja de este algoritmo es que puede ser implementado en paralelo para 
reducir los tiempos de ejecución. 
También se ha recurrido a la implementación de algoritmos basados en la búsqueda tabú. 
Tal es el caso de la búsqueda de soluciones para el 3AP-Axial usando búsqueda por entornos 
(Centeno, 2010). Esta implementación se basa en los elementos básicos de la búsqueda Tabú 
más algunas características propias. El algoritmo utiliza una memoria a corto plazo que le 
permite tener en cuenta los atributos recién cambiados (pasado reciente). Con esta memoria, 
junto con otros atributos, se busca evitar revisitar soluciones.Además, cuenta con un criterio 
de aspiración que permite ciertos movimientos aun cuando tengan estatus tabú. Este algoritmo 
también está hibridizado a través de una heurística voraz que inicializa las soluciones al inicio 
del método. 
Pseudo-código del algoritmo de búsqueda tabú adaptado para solucionar 3AP: 
1. Leer archivo de costo. 
2. Leer dimensión de la vecindad. 
3. Generar la solución inicial x . 
4. Repetir 
a. Generar candidatas de la solución anterior 
b. Seleccionar 'x candidatas de x / ( ') ( *);f x f x 
c. *x candidatas ( ) ;x HM 
d. Actualizar HM 
5. Hasta regresar a la solución inicial 
6. Fin. 
32 
 
 
 
Capítulo IV 
Implementación, experimentos y resultados 
Para adaptar un algoritmo basado en PSO que solucione 3AP se necesita de un mecanismo 
que permita transformar los componentes de PSO continuo al dominio discreto. En el capítulo 
III están descritos los operadores para implementar un algoritmo de tipo discreto usando PSO. 
Sin embargo, no se ha tratado el método para llevar a cabo dicha implementación, lo cual, es 
uno de los principales problemas a resolver en el presente trabajo. La generalización de un 
proceso para implementar PSO en el dominio discreto no es sencilla. Comparado con otras 
técnicas está limitada y se acentúa más en los problemas combinatorios. 
Uno de muchos enfoques utilizados para hacer esta adaptación es el análisis de forma 
(forma analysis). Este planteamiento se define como sigue (Gong y Tuson, 2007): Dado un 
operador de plantilla, cualquier descripción adecuada del dominio de algún problema tratado 
da lugar a un operador concreto, cuyos comportamientos y rendimiento están relacionados a 
los supuestos que se hicieron para describir el espacio de búsqueda. Los componentes de esta 
definición puede observarse en la figura 6. 
 
 
 
 
 
 
 
Figura 6. Componentes del análisis de forma 
Base definida para el dominio 
Dominio 1 
Descripción 1 
Descripción 2 
Dominio 2 
Descripción 1 
Descripción 2 
Operador 
plantilla 
Operador 1 
Operador 2 
Operador 3 
Operador 4 
33 
 
 
 
En otras palabras, este enfoque, a partir del conocimiento que se tiene del problema y de 
relaciones de equivalencia, permite derivar los operadores que permitan implementar PSO al 
dominio del problema 3AP. 
4.1 Redefinición de los operadores de PSO al espacio discreto. 
4.1.1. Espacio de búsqueda. 
El espacio de búsqueda del problema 3AP está conformador por 2( !)n de posibles 
soluciones y a este conjunto se le denomina nS . Cada elemento de nS puede transformarse en 
otra solución dentro de nS aplicándole un operador un número determinado de veces. 
4.1.2. Representación de la solución. 
Cada partícula consta de dos conjuntos , nS   definidas de la siguiente manera: 
 (0), (1),..., ( 1)p p p n   y  (0), (1),..., ( 1)q q q n   (25) 
Donde el dominio de  y  es  0,.. 1n  y el rango son los valores comprendidos entre 1 
y n . Además, se define la siguiente restricción de la posición: 
( ), ( )p m p l   donde m l , ( ) ( )p m p l y 
( ), ( )q m q l   donde m l , ( ) ( )q m q l 
(26) 
Lo cual implica que ningún elemento de  o  puede ser colocado en dos lugares 
diferentes al mismo tiempo. Esta restricción limita a la partícula a pertenecer solo a nS y es 
equivalente a la restricción del método clásico donde si una partícula abandona el espacio de 
búsqueda, se le ajusta su posición para que permanezca dentro de los límites definidos. 
 
 
 
34 
 
 
 
4.1.3. Función de aptitud. 
La función de aptitud f es aquella que permite evaluar una solución. 3AP se puede 
representar de diferentes formas, pero el espacio de búsqueda, ya definido, permite trabajar 
con la representación de 3AP definida en (14). 
4.1.4. Relación de orden 
En el contexto de PSO, se entiende por relación de orden a todo operador que aplicado a un 
par de partículas l y m permita determinar cuál de las dos es mejor o si son equivalentes. 
La relación de orden de dos partículas l y m para 3AP se define de la siguiente manera: 
l es mejor que m si ( ) ( )l mf X f X 
m es mejor que l si ( ) ( )l mf X f X 
l es equivalente a m si ( ) ( )l mf X f X 
(27) 
Sin embargo, que ( ) ( )l mf X f X no implica que siempre l mX X , es decir, que su 
distancia sea cero. 
4.1.5. Distancia entre dos partículas. 
La redefinición de los operadores de PSO debe incluir la distancia en el espacio de 
búsqueda. Esta debe ser una buena medida de la diferencia de dos puntos en el espacio de 
búsqueda (Jin Qin, 2011). 
Redefinición (distancia). La distancia comprendida entre dos partículas, es el resultado de 
hacer una comparación de cada una de las componentes que integran a  y  para determinar 
el número de elementos que son diferentes. 
1( , )l mdist X X d para  (28) 
35 
 
 
 
2( , )l mdist X X d para  
Por ejemplo, dadas dos partículas l y m su distancia en la componente  es: 
 1, 2,3, 4,5lX  ,  5, 4,3,2,1mX  
( , ) 4l mdist X X  
(29) 
Esto es equivalente a decir que la distancia es el número de veces que se debe aplicar un 
operador a una de las dos partículas para que sean iguales. 
La distancia, entonces, no es la diferencia aritmética de los resultados arrojados por la 
función de aptitud al evaluar l y m . Sin embargo, es evidente que entre más cercanos estén l y 
m , la probabilidad de que los valores resultantes de la función de aptitud sean parecidos es 
más alta. 
En el caso del problema 3AP, se observa que las variaciones en los valores de  y  (por 
mínimas que estas sean) pueden provocar un resultado muy diferente con respecto al valor que 
tenía antes de la variación, incluso, si la distancia entre el vector inicial y el perturbado es uno. 
No obstante, en 3AP las tripletas que contienen un valor considerado como un óptimo local 
regularmente contienen información perteneciente a un óptimo global (He Jiang, et al. 2008). 
Por lo tanto, es conveniente informar a las partículas de aquellos casos donde existe un 
solución potencialmente buena. 
4.1.6. Velocidad 
La velocidad, en la definición clásica, representa la distancia que se debe recorrer por 
alguna partícula i desde su posición actual X hacia algún punto en nS (Wei-jun Xia y Zhi-
ming Wu, 2006). Este concepto no se puede aplicar a los problemas discretos. La redefinición 
de la distancia permite trabajar con otro enfoque en la velocidad: la velocidad es cualquier 
operador que aplicado a t nX S produce otra posición 
1tX  válida en nS . 
36 
 
 
 
Redefinición (Velocidad). La velocidad es un operador  que perturba la distancia de una 
posición X con respecto a algún otro punto en nS . Es decir, los elementos de X deben ser 
modificados para que la distancia con respecto a algún punto accesible, iP o iG sea pequeña o 
nula. 
1( ( , )) ( , )t tdist Y X dist Y X   , donde 1, ,t t nX X Y S
  (30) 
La perturbación se logra utilizando el enfoque basado en operadores de intercambio 
descrito en el capítulo III. Para las permutaciones, el operador más utilizado es el cruce 
también usado en los algoritmos genéticos. Existen una amplia variedad de estos operadores, 
sin embargo, no existe evidencia de que alguno sea superior a otro (Huang y Lim, 2006) y, 
además, el problema que se requiere resolver determina cuál de ellos es más apropiado de 
utilizar. 
No es deseable que la partícula tienda hacia otro punto de una forma total. La justificación 
para esto es el gran tamaño de nS . Si la distancia obtenida después de la perturbación es igual 
a cero, se repite un punto en nS ya explorado por otra partícula. En lugar de eso, es preferible 
que la partícula quede en algún punto cercano que se pueda evaluar y desde donde se pueda 
iniciar otro movimiento. 
Para lograr un acercamiento parcial entre dos puntos es necesario limitar el número de 
intercambios a realizar. Pero no es conveniente establecerposiciones fijas en el vector como 
no intercambiables. Esto también provoca que ciertos puntos queden con pocas probabilidades 
de ser explorados aun cuando sean buenas soluciones potenciales. En vez de ello, el operador 
de intercambio 1( , , )X Y p limita el intercambio de dos elementos de la siguiente manera: 
Si 1 1( ) ( )X p Y p , 1 1( ) ( )X p Y p y 1 1( ( ( ))) ( )X pos Y p X p 
Siempre que 1 1( ( ))p pos Y p 
Donde: 1 1, ( ( )) xp pos Y p P , xP es el conjunto de todas las posiciones de X . 
(31) 
37 
 
 
 
Conforme el valor 1p tienda a 1n la probabilidad de intercambio va disminuyendo hasta 
ser cero cuando 1p lo iguala. Por lo tanto, la probabilidad de intercambio del elemento de X
está totalmente sujeta a la posición en X del elemento en Y . 
Por otra parte, un acercamiento directo (“lineal”) limita el espacio a ser explorado (fig.7). 
Es preferible realizar un acercamiento al nuevo punto de forma un poco errante (fig.8). Esto se 
puede obtener haciendo una perturbación de la distancia usando intercambios estocásticos. 
Esta operación, que trabaja en conjunto con la restricción de intercambio, tiene como objetivo 
tener varias posiciones de tipo ' nX S ya evaluadas al final del proceso. Es decir, no solo se 
evalúa la posición final 1tX  , sino toda una trayectoria válida. Esta es la principal ventaja que 
este operador tiene con respecto a otros operadores como el cruce parcial (PMX), el cual, no 
proporcionó la diversidad necesaria para que el algoritmo propuesto convergiera a soluciones 
buenas. La desventaja es que necesita de un número de intentos de intercambios mayor a n . 
Las pruebas realizadas muestran que 3n intentos son suficientes para hacer el cruce 
estocástico. 
La evaluación parcial de los puntos de la trayectoria no implica evaluar toda la función de 
aptitud. Esto incrementaría en demasía el tiempo de ejecución. Para solucionar este problema 
se evalúa de forma parcial f en  y  . 
, , , , , , , , , , , , , , , ,( , , , , , ) ( ( )) ( )parcial i j k l m n i m k l j n aptitud i j k l m n i m k l j nf X C c c c c X c c c c     
Donde: C es la matriz de costos, , , , ,,i j k l m nc c C son los costos antes del 
intercambio de j y m , , , , ,,i m k l j nc c C son los costos después del intercambio de las 
posiciones j y m 
(32) 
A continuación se describe el operador de velocidad incluyendo el proceso de intercambio 
de un elemento de X con el operador  previamente descrito: 
1( ( , )) ( , , )
kdist Y X X Y p   (33) 
38 
 
 
 
donde 1 ( )
kp aleatorio n en el intento k de intercambio y donde 1,2,.. 3k n  
 
Figura 7. Analogía de un movimiento lineal donde se muestra como se puede dejar 
fuera posiciones prometedoras 
 
 
Figura 8. Analogía de un movimiento errante, el cual, tiene más probabilidades de 
encontrar mejores posiciones en su trayecto. 
 
 
4.1.7. Suma 
Redefinición (Suma de velocidades). La definición clásica lo describe como una suma 
aritmética de dos números reales cuyo resultado es la velocidad. Esto permite una 
combinación lineal de un punto accesible, iP y iG . Debido a que no es posible realizar una 
combinación directa en el espacio discreto de los tres componentes que resulte en un número 
real, la suma se puede redefinir de dos formas. 
39 
 
 
 
El operador de suma de dos velocidades  es la probabilidad de seleccionar a iP y iG para 
perturbar a tX (usando  ) y así producir 1t nX S
  . Para ello los coeficientes de confianza 
2c y 3c se fijan con un valor de uno. Por lo tanto, la probabilidad de la selección de una de las 
dos componentes está fija en 1
2
. Un número real aleatorio  0,1a se genera para ser el 
selector. 
1 ( ( , ) ( ( , )t t ti i i i iX dist P X dist G X
    (34) 
Debido a que la partícula tiene ajustados sus coeficientes de confianza al mismo nivel, la 
partícula i “salta” en cada iteración hacia su mejor posición previa ó hacía el mejor 
informante encontrado en la iteración t . 
Por otra parte, el operador de suma de dos velocidades  es una secuencia de 
perturbaciones sobre tX (usando  ) de tal forma que el resultado final sea 1t nX S
  . El 
resultado de la primera perturbación es nY S , es decir, sigue siendo una posición valida en el 
espacio de búsqueda. La primera perturbación es hecha con respecto a iP , mientras que la 
segunda considera a iG . 
1 ( ( , ) ( ( , )t t ti i i i iX dist P X dist G X
    (35) 
Lo que es equivalente a realizar una composición del operador  de la siguiente forma: 
1 ( ( , ( ( , ))))t ti i iX dist G dist P X
    (36) 
Se observa que en cada iteración t , la partícula tiende a regresar a su mejor posición previa 
para luego alejarse hacia un informante. Este comportamiento resulta beneficioso para la 
partícula porque de manera implícita existe una búsqueda local. Cada vez que la partícula se 
aleja para después regresar, el vecindario de su mejor posición previa es explorado. En 
consecuencia, es factible que se mejore el valor de la posición previa en algún punto cercano 
al óptimo local (fig. 9). Este comportamiento también se observa con el operador  , pero de 
40 
 
 
 
forma menos directa y, además, se obtienen resultados más favorables con  . Sin embargo, el 
operador  implica más costo computacional debido a que siempre se realizan dos 
perturbaciones en cada iteración. 
En ambos operadores está implícito el operador Desplazamiento (posición, velocidad)
posición. Cada perturbación sobre tX implica un cambio en su posición. 
En ambas definiciones w es ignorado debido a que la velocidad es un operador sobre tX . 
La primera componente de la definición clásica de velocidad no contiene a la posición, 
entonces, y por analogía, el operador de velocidad no puede aplicarse en el caso discreto en 
ausencia de tX . Esto es equivalente a decir que la velocidad inicial es igual a cero. 
 
 
Figura 9. Analogía de un movimiento aplicando el operador  . 
 
 
41 
 
 
 
4.2 Implementación. 
4.2.1 Número aleatorios 
La heurística de optimización por enjambre de partículas depende ampliamente de procesos 
estocásticos. Algunos ejemplos donde se requieren son en la inicialización del enjambre y en 
los operadores 1r y 2r . El algoritmo propuesto necesita de la aleatoriedad en el operador en  , 
 y en otros más. 
Las librerías que comúnmente están incorporadas en los compiladores tanto libres como 
comerciales no son buenos generadores de números pseudo-aleatorios. Esto se refleja en un 
pobre rendimiento de los algoritmos que las utilizan. 
El generador de números pseudo-aleatorios KISS de Marsaglia cumple con todas las 
pruebas estadísticas estándar que se emplean para garantizar la calidad de los generadores 
(Marsaglia, 1999). Sin embargo, este presenta una desventaja: tiene un alto consumo de 
tiempo. Por lo tanto, es necesario implementar un mecanismo que ayude a reducir ese 
inconveniente cuando el algoritmo principal utilice con mucha frecuencia el generador de 
Marsaglia. La solución se obtiene con la generación de una matriz de números psudo-
aleatorios (usando KISS) de un tamaño suficiente para garantizar un comportamiento bueno 
del método implementado. Las pruebas hechas indican que un tamaño de 3200 ( 3)n  es 
suficiente. La matriz aleatoria se define como: 
, 3200 ( 3)( )i j nA a   
Donde: ,i ja es el i esimo número aleatorio en su posición j y  , 1, 2..,i ja n 
(37) 
Para los casos donde no es necesario o se imposibilita el uso de A se utiliza una función alea 
que utiliza directamente el generador KISS de Marsaglia. 
( ) (0,1) ( ))na alea ARGUMENTO KISS ARGUMENTO   , donde 
 1, 2..,na ARGUMENTO 
(38) 
42 
 
 
 
4.2.2 Inicialización de las partículas 
Frecuentemente la condición de la población inicial, hasta cierto punto, afecta la calidad de 
la solución o la velocidad de convergencia de la población (Jun-qing Li, et al. 2009).