PDF de programación - UN ALGORITMO BASADO EN LA OPTIMIZACIÓN POR ENJAMBRE DE PARTÍCULAS PARA EL PROBLEMA DE ASIGNACIÓN AXIAL 3-DIMENSIONA

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

ING. JOSÉ ALBERTO FRANCO GÓMEZ

PRESENTA:

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.






























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.









i





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.











ii



























A mis padres

A mis hermanos y sobrinitos

A María de Jesús Martínez González



iii



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.











iv

Tabla de Contenido

Sección

Resumen
Abstract
Dedicatorias
Agradecimientos
Tabla de contenido
Lista de figuras
Lista de tablas
I. Introducción

1.1 Definición del problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . .
1.2 Justificación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Objetivos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.1 Objetivo general. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2 Objetivos específicos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Organización de la tesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

II. El problema de la asignación axial tres dimensional

2.1 La optimización. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Problemas de optimización combinatorios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Dificultad de un problema. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Problemas de asignación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1 Asignación generalizada o bidimensional. . . . . . . . . . . . . . . . . . . . . . . .
2.4.2 Problemas multidimensionales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

III. Optimización por enjambre de partículas

3.1Inteligencia Artificial. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Escalador de colinas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2 Recocido simulado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3 Búsqueda Tabú. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.4 Algoritmos Genéticos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.5 Inteligencia colectiva. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Optimización por enjambre de partículas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 PSO aplicado en problemas discretos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4 Implementación de PSO para algunos problemas discretos. . . . . . . . . . . . . . . . . . .
3.5 Métodos heurísticos implementados para la solución de 3AP. . . . . . . . . . . . . . . . . .

IV Implementación, experimentos y resultados

4.1 Redefinición de los operadores de PSO al espacio discreto. . . . . . . . . . . . . . . . . . .
4.1.1 Espacio de búsqueda. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.2 Representación de la solución. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3 Función de aptitud. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.4 Relación de orden. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

v



Página


i
ii
iii
iv
v
vii
viii
1
2
3
4
4
4
4
6
6
6
8
10
10
12
16
16
17
18
18
18
19
20
24
26
29
32
33
33
33
34
34





Tabla de Contenido (Continuación)

Sección


4.1.5 Distancia entre dos partículas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.6 Velocidad. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.7 Suma. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Implementación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Números aleatorios. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2 Inicialización de las partículas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.3 Aptitud de las partículas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.4 Informantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.5 Método principal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Implementación Distribuida. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Proceso maestro.