Control de Algoritmo Evolutivo

Vista previa del material en texto

LABORATORIO NACIONAL DE INFORMÁTICA AVANZADA
CENTRO DE ENSEÑANZA LANIA
Control de Parámetros del Algoritmo Evolución
Diferencial con Variantes Combinadas para la
Solución de Problemas de Optimización en
Mecatrónica
T E S I S
Que presenta:
I.S.C. Maury Faney Zapata Zapata
Para obtener el grado de:
Maestro en Computación Aplicada
Dirigida por:
Dr. Efrén Mezura Montes
Dr. Edgar Alfredo Portilla Flores
Dra. Cora Breatriz Excelente Toledo
Xalapa, Veracruz, México Agosto 2017
Agradecimientos
Realizar esta tesis fue una tarea que requirió de mucho esfuerzo y dedicación,
marcando una etapa importante en mi vida y siendo uno de los logros más satis-
factorios que he tenido en mi preparación profesional. Sin embargo, alcanzar esta
meta no hubiera sido posible sin el apoyo de aquellas personas que creyeron en mı́
y me impulsaron a lograrlo a través de su ayuda, est́ımulo y confianza. Es por ello
que quiero agradecerles de manera muy especial el haberme acompañado en este
trayecto.
Agradezco a mi familia, por el cariño y apoyo que me han brindado en todo este
tiempo, principalmente por esa motivación que siempre me han transmitido para
salir adelante.
A mis amigos, compañeros de la MCA y demás personas queridas que le dieron un
toque divertido, lleno de buenos momentos y sobre todo grato, a esta experiencia.
También a mis asesores, el Dr. Efrén, el Dr. Edgar y la Dra. Cora, quienes siem-
pre me orientaron, me compartieron su conocimiento y estuvieron al pendiente
de mi avance en todo momento. Sin ellos no habŕıa sido posible realizar un buen
trabajo.
Agradezco al Consejo Nacional de Ciencia y Tecnoloǵıa (CONACyT) por la beca
otorgada para realizar estudios de posgrado, bajo el marco del Programa Nacional
de Posgrados de Calidad con número de becario 581786.
Finalmente, quiero agradecer al personal de LANIA, por las facilidades y enseñan-
zas que me brindaron durante la maestŕıa.
iii
Resumen
En este trabajo de investigación se realiza un estudio de control de parámetros
sobre un algoritmo bioinspirado basado en Evolución Diferencial, con el fin de
mejorar su desempeño en la solución de tres problemas mecatrónicos de optimi-
zación; el primer problema, consiste en optimizar la trayectoria y el movimiento
de un mecanismo de cuatro barras en tres casos de estudio; en el segundo se op-
timiza el agarre esférico de dos casos de estudio de un efector final de tres dedos;
y finalmente, en el tercero, se optimiza el despacho económico de enerǵıa en una
microrred aislada comúnmente conocida como Smart Grid. El algoritmo base em-
pleado es conocido como DECV (Differential Evolution with Combined Variants)
El diseño experimental de este estudio se divide en dos fases: 1) experimentos
preliminares y 2) experimentos finales. Durante los experimentos preliminares se
prueban diversos mecanismos de control de parámetros en DECV y se selecciona
aquel con mejor desempeño al compararse contra la versión original de dicho algo-
ritmo. La técnica de control seleccionada consiste en añadir una memoria histórica
de parámetros para configurar de manera automática el Factor de Escala (F ) y la
Probabilidad de Cruzamiento (CR), además de una función lineal para reducir de
manera dinámica la Población de Individuos (NP ). A esta versión de DECV se
le otorga el nombre de LSHADE-CV. En los experimentos finales, el desempeño
de LSHADE-CV se compara contra los algoritmos DE/rand/1/bin y C-LSHADE,
una versión del algoritmo L-SHADE propuesta en este trabajo.
Los resultados finales sugieren que tanto LSHADE-CV como C-LSHADE son
capaces de encontrar mejores o iguales soluciones que DE/rand/1/bin empleando
menos recursos computacionales. Estas dos propuestas liberan al usuario final de
los inconvenientes que implica la tarea de calibrar manualmente los parámetros
de la Evolución Diferencial.
iv
Índice general
Agradecimientos III
Resumen IV
Índice de figuras VIII
Índice de tablas IX
Índice de algoritmos XII
1. Introducción 1
1.1. Planteamiento del Problema . . . . . . . . . . . . . . . . . . . . . 2
1.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1. Objetivo General . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2. Objetivos Expećıficos . . . . . . . . . . . . . . . . . . . . . 4
1.3. Hipótesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4. Justificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5. Organización del Documento . . . . . . . . . . . . . . . . . . . . . 6
1.6. Publicaciones Derivadas de esta Tesis . . . . . . . . . . . . . . . . 6
1.7. Conclusiones del Caṕıtulo . . . . . . . . . . . . . . . . . . . . . . 7
2. Optimización 8
2.1. Concepto de Optimización . . . . . . . . . . . . . . . . . . . . . . 8
2.2. Variables de Diseño . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3. Restricciones de Diseño . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4. Función Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5. Optimos Locales y Globales . . . . . . . . . . . . . . . . . . . . . 11
2.6. Clasificación de Problemas de Optimización . . . . . . . . . . . . 13
2.7. Algoritmos de Optimización . . . . . . . . . . . . . . . . . . . . . 14
2.8. Conclusiones del Caṕıtulo . . . . . . . . . . . . . . . . . . . . . . 15
3. Computación Evolutiva 16
3.1. Introducción a la Computación Evolutiva . . . . . . . . . . . . . . 16
3.2. Algoritmos Evolutivos . . . . . . . . . . . . . . . . . . . . . . . . 17
v
ÍNDICE GENERAL vi
3.3. Evolución Diferencial . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.1. Inicialización . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.3.2. Mutación . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.3. Recombinación . . . . . . . . . . . . . . . . . . . . . . . . 19
3.3.4. Selección . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3.5. Algoritmo DE clásico . . . . . . . . . . . . . . . . . . . . . 21
3.3.6. Variantes de DE . . . . . . . . . . . . . . . . . . . . . . . 22
3.4. Algoritmo DECV . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.5. Conclusiones del Caṕıtulo . . . . . . . . . . . . . . . . . . . . . . 24
4. Formulación de Problemas Mecatrónicos 26
4.1. Diseño de un Mecanismo de Cuatro Barras . . . . . . . . . . . . . 26
4.1.1. Cinemática del Mecanismo de Cuatro Barras . . . . . . . . 27
4.1.2. Declaración de Problemas de Optimización para Casos de
Estudio del Mecanismo . . . . . . . . . . . . . . . . . . . . 29
4.2. Diseño de un Efector Final de Tres Dedos . . . . . . . . . . . . . 34
4.2.1. Cinemática del Efector Final de Tres Dedos . . . . . . . . 35
4.2.2. Declaración de Problemas de Optimización para Casos de
Estudio del Efector . . . . . . . . . . . . . . . . . . . . . . 41
4.3. Despacho Económico de Enerǵıa en una Microrred Aislada - SCE1 45
4.3.1. Microrred Remota no Interconectable . . . . . . . . . . . . 46
4.3.2. Declaración del Problema de Optimización . . . . . . . . . 47
4.4. Conclusiones del Caṕıtulo . . . . . . . . . . . . . . . . . . . . . . 50
5. Configuración de Parámetros 51
5.1. Calibración de Parámetros . . . . . . . . . . . . . . . . . . . . . . 52
5.2. Control de Parámetros . . . . . . . . . . . . . . . . . . . . . . . . 52
5.3. Propuesta de Control de Parámetros . . . . . . . . . . . . . . . . 53
5.3.1. Algoritmo L-SHADE . . . . . . . . . . . . . . . . . . . . . 53
5.3.2. Enfoque Propuesto: LSHADE-CV . . . . . . . . . . . . . . 56
5.3.3. Enfoque Propuesto: C-LSHADE . . . . . . . . . . . . . . . 56
5.4. Conclusiones del Caṕıtulo . . . . . . . . . . . . . . . . . . . . . . 59
6. Experimentos y Resultados 60
6.1. Diseño Experimental . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.2. Estad́ıstica no Paramétrica . . . . . . . . . . . . . . . . . . . . . . 61
6.3. Experimentos Preliminares . . . . . . . . . . . . . . . . . . . . . . 63
6.3.1. Experimento A: DECVSenoidal vs DECV . . . . . . . . . 63
6.3.2. Experimento B: DECV con Memoria de Parámetros vs DECV
Senoidal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.4. Experimentos Finales . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.4.1. Experimento C: LSHADE-CV vs DE/rand/1/bin . . . . . 72
6.4.2. Experimento D: C-LSHADE vs DE/rand/1/bin . . . . . . 77
ÍNDICE GENERAL vii
6.4.3. Experimento E: C-LSHADE vs LSHADE-CV . . . . . . . 81
6.5. Visualización de Resultados . . . . . . . . . . . . . . . . . . . . . 84
6.5.1. Mecanismo de Cuatro Barras . . . . . . . . . . . . . . . . 85
6.5.2. Efector Final de Tres Dedos . . . . . . . . . . . . . . . . . 86
6.5.3. Microrred Aislada . . . . . . . . . . . . . . . . . . . . . . . 88
6.6. Conclusiones del Caṕıtulo . . . . . . . . . . . . . . . . . . . . . . 89
7. Conclusiones y Trabajo Futuro 90
7.1. Observaciones Finales . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.2. Objetivos Cumplidos . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.3. Contribuciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.4. Trabajo Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Apéndices 93
Apéndice A. Implementación de C-LSHADE en Matlab 94
A.1. Función C-LSHADE . . . . . . . . . . . . . . . . . . . . . . . . . 94
A.2. Codificación de C-LSHADE . . . . . . . . . . . . . . . . . . . . . 96
Bibliograf́ıa 102
Índice de figuras
1.1. Mecanismo plano de cuatro barras. Adaptada de [6]. . . . . . . . 3
2.1. Representación de puntos óptimos. Gráfica creada con información
de [16]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.1. Mecanismo de cuatro barras. Adaptada de [23]. . . . . . . . . . . 27
4.2. Mecanismo de seis barras para el diseño de un dedo. Adaptada de
[18]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.3. Mecanismo manivela-biela-corredera. Adaptada de [18]. . . . . . . 35
4.4. Mecanismo MBC para el caso r4 > 0. Adaptada de [18]. . . . . . . 36
4.5. Mecanismo MBC para el caso r4 < 0. Adaptada de [18]. . . . . . . 37
4.6. Mecanismo MBC para el caso r4 = 0. Adaptada de [18]. . . . . . . 38
4.7. Mecanismo de cuatro barras de un dedo. Adaptada de [18]. . . . . 39
4.8. Acoplador del mecanismo de cuatro barras. Adaptada de [18]. . . 41
5.1. Taxonomı́a global de configuración de parámetros en Algoritmos
Evolutivos. Adaptada de [7]. . . . . . . . . . . . . . . . . . . . . . 51
6.1. Gráficas de convergencia de LSHADE-CV y DE/rand/1/bin en los
seis problemas de optimización. . . . . . . . . . . . . . . . . . . . 76
6.2. Gráficas de convergencia de C-LSHADE y DE/rand/1/bin en los
seis problemas de optimización. . . . . . . . . . . . . . . . . . . . 80
6.3. Gráficas de convergencia de C-LSHADE y LSHADE-CV en los seis
problemas de optimización. . . . . . . . . . . . . . . . . . . . . . . 83
6.4. Mejores soluciones encontradas por el algoritmo C-LSHADE en las
tres instancias de mecanismos de cuatro barras. . . . . . . . . . . 86
6.5. Mejores soluciones encontradas por el algoritmo C-LSHADE en las
dos instancias del dedo del efector final siguiendo una trayectoria
esférica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
6.6. Visualización del suministro de enerǵıa durante las 24 horas del
d́ıa para el funcionamiento de la microrred aislada, obtenido por el
algoritmo LSHADE-CV. . . . . . . . . . . . . . . . . . . . . . . . 89
viii
Índice de tablas
3.1. Metáfora básica de la computación evolutiva que relaciona la evo-
lución natural con la resolución de problemas. . . . . . . . . . . . 17
4.1. Signo del radical según el tipo de mecanismo. . . . . . . . . . . . 29
4.2. Pares de puntos de precisión - CE3 . . . . . . . . . . . . . . . . . 34
4.3. Parámetros del ESS. . . . . . . . . . . . . . . . . . . . . . . . . . 49
5.1. Memoria Histórica MCR, MF . Adaptada de [36]. . . . . . . . . . . 54
6.1. Nombre abreviado de los seis problemas mecatrónicos resueltos. . 61
6.2. Número máximo de generaciones para cada problema de optimiza-
ción en DECV y DECV Senoidal. . . . . . . . . . . . . . . . . . . 64
6.3. Comparación de DECV y DECV Senoidal en los seis problemas de
optimización mecatrónica. Los śımbolos +, − y ≈ señalan que el
algoritmo indicado obtuvo un desempeño significativamente mejor
(+), significativamente peor (−) o no significativamente diferente
(≈) comparado contra DECV usando la prueba de suma de rangos
de Wilcoxon con un 95 % de confianza. . . . . . . . . . . . . . . . 65
6.4. Resultados de DECV-Sen1 y DECV en los seis problemas de opti-
mización mecatrónica. Cada columna muestra el mejor resultado,
el peor, la mediana, el promedio y la desviación estándar de los
valores de la función objetivo encontrados en 31 ejecuciones. . . . 66
6.5. Configuración de parámetros en SHADE-CV, LSHADE-CV e iLSHADE-
CV. D corresponde a la dimensión del problema de optimización. 69
6.6. Número máximo de evaluaciones de la función objetivo para cada
problema de optimización en LSHADE-CV e iLSHADE-CV. . . . 70
6.7. Comparación de DECV con memoria de parámetros y DECV-Sen1
en los seis problemas de optimización mecatrónica. Los śımbolos
+, − y ≈ señalan que el algoritmo indicado obtuvo un desem-
peño significativamente mejor (+), significativamente peor (−) o
no significativamente diferente (≈) comparado contra DECV-Sen1
usando la prueba de suma de rangos de Wilcoxon con un 95 % de
confianza. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
ix
ÍNDICE DE TABLAS x
6.8. Resultados de LSHADE-CV y DECV-Sen1 en los seis problemas
de optimización mecatrónica. Cada columna muestra el mejor re-
sultado, el peor, la mediana, el promedio y la desviación estándar
de los valores de la función objetivo encontrados en 31 ejecuciones. 71
6.9. Calibración de parámetros del algoritmo DE/rand/1/bin basada en
el enfoque de [38]. . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
6.10. Comparación de LSHADE-CV y DE/rand/1/bin en los seis proble-
mas de optimización mecatrónica. Los śımbolos +, − y ≈ señalan
que LSHADE-CV obtuvo un desempeño significativamente mejor
(+), significativamente peor (−) o no significativamente diferente
(≈) comparado contra DE/rand/1/bin usando la prueba de suma
de rangos de Wilcoxon con un 95 % de confianza. . . . . . . . . . 73
6.11. Resultados estad́ısticos obtenidos por LSHADE-CV y DE/rand/1/bin
en los seis problemas de optimización mecatrónica. Se marcan en
negritas los mejores valores de cada medida. . . . . . . . . . . . . 75
6.12. Configuración de parámetros de C-LSHADE basada en [36]. D co-
rresponde a la dimensión del problema de optimización. . . . . . . 77
6.13. Comparación de C-LSHADE y DE/rand/1/bin en los seis proble-
mas de optimización mecatrónica. Los śımbolos +, − y ≈ señalan
que C-LSHADE obtuvo un desempeño significativamente mejor
(+), significativamente peor (−) o no significativamente diferente
(≈) comparado contra DE/rand/1/bin usando la prueba de suma
de rangos de Wilcoxon con un 95 % de confianza. . . . . . . . . . 78
6.14. Resultados estad́ısticos obtenidos por C-LSHADE y DE/rand/1/bin
en los seis problemas de optimización mecatrónica. Se marcan en
negritas los mejores valores de cada medida. . . . . . . . . . . . . 79
6.15. Comparación de C-LSHADE y LSHADE-CV en los seis problemas
de optimización mecatrónica. Los śımbolos +, − y ≈ señalan que
C-LSHADE obtuvo un desempeño significativamente mejor (+),
significativamente peor (−) o no significativamente diferente (≈)
comparado contra LSHADE-CV usando la prueba de suma de ran-
gos de Wilcoxon con un 95 % de confianza. . . . . . . . . . . . . 81
6.16. Resultados estad́ısticos obtenidos por C-LSHADE y LSHADE-CV
en los seis problemas de optimización mecatrónica. Se marcan en
negritas los mejores valores de cada medida. . . . . . . . . . . . . 82
6.17. Valores encontrados por C-LSHADE para las variables de diseño
en los trescasos de estudio del mecanismo de cuatro barras, corres-
pondientes al mejor valor de la función objetivo. . . . . . . . . . . 85
6.18. Valores encontrados por C-LSHADE para las variables de diseño
en los dos casos de estudio del efector final de tres dedos, corres-
pondientes al mejor valor de la función objetivo. . . . . . . . . . . 87
ÍNDICE DE TABLAS xi
6.19. Valores encontrados por LSHADE-CV para las variables de diseño
de la microrred aislada en las 24 horas del d́ıa, correspondientes al
mejor valor de la función objetivo. . . . . . . . . . . . . . . . . . . 88
Índice de algoritmos
3.1. Algoritmo Evolutivo . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2. DE/rand/1/bin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3. DECV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.4. Actualización de memoria en L-SHADE . . . . . . . . . . . . . . . 55
5.5. LSHADE-CV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.6. C-LSHADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
6.7. Restricción de parámetros CR y F en iL-SHADE . . . . . . . . . 69
xii
CAPÍTULO 1
Introducción
La optimización es una tarea que se puede entender como un procedimiento me-
diante el cual se ajustarán ciertos valores o parámetros, para evaluar un número
finito de soluciones que cumplan con las caracteŕısticas que un contexto deter-
minado requiere, con el fin de hallar el resultado que implique menor costo para
resolver el problema. Con el fin de solucionar problemas de optimización se ha re-
currido al cómputo inteligente, incorporando a través de los últimos años técnicas
no tradicionales llamadas metaheuŕısticas, las cuales son un conjunto de concep-
tos que sirven para realizar procesos de búsqueda y debido a su diseño genérico,
pueden ser aplicadas a este tipo de problemas [1].
Un conjunto de técnicas metaheuŕısticas que se basan en metáforas biológicas
son los algoritmos bioinspirados. Dentro de éstos, espećıficamente en el grupo de
aquellos que pertenecen a los algoritmos evolutivos, se encuentra la Evolución Di-
ferencial (DE por sus siglas en inglés). Este algoritmo emula la evolución natural
al trabajar con un conjunto de individuos, también llamados vectores, que repre-
sentan soluciones potenciales para el problema de optimización [2].
En la actualidad, la mecatrónica es ampliamente aceptada como la metodoloǵıa
de diseño y optimización de nuevos productos, equipos y procesos, que integrados
simultáneamente combinan las técnicas de ingenieŕıa mecánica, ingenieŕıa eléctri-
ca, electrónica, automatización, microinformática y análisis de sistemas. Es un
campo interdisciplinario de ingenieŕıa en el que los nuevos productos diseñados
se caracterizan por tener un mejor desempeño comparado con el que ofrecen las
soluciones tradicionales [3].
1
CAPÍTULO 1. INTRODUCCIÓN 2
En este trabajo de investigación se formularon tres problemas de optimización
mecatrónica; el primero, consiste en optimizar la trayectoria y movimiento de un
mecanismo de cuatro barras; en el segundo, se optimiza el agarre esférico de un
efector final 1 de tres dedos con un grado de libertad (GDL)2; y finalmente, en el
tercero, se optimiza el despacho económico de enerǵıa en una microrred aislada
comúnmente conocida como Smart Grid. Los tres problemas fueron abordados a
través de un estudio del control de parámetros del algoritmo DECV (Differential
Evolution with Combined Variants) [4], el cual es una variante del algoritmo DE.
Esta investigación tuvo como fin ampliar el dominio de aplicación del algorit-
mo DECV en problemas de optimización mecatrónica, además de proponer una
técnica de control de parámetros que permitiera convertirlo en un algoritmo más
robusto, eficiente y menos dependiente del usuario.
1.1. Planteamiento del Problema
Actualmente en el Centro de Innovación y Desarrollo Tecnológico en Cómputo
(CIDETEC) del Instituto Politécnico Nacional (IPN), se encuentran solucionan-
do problemas de diseño de sistemas basados en mecanismos planos y de despacho
económico de enerǵıa. El diseño de sistemas se basa en mecanismos planos de
cuatro barras como el que se muestra en la Figura 1.1, en donde se pretende opti-
mizar el seguimiento de una trayectoria espećıfica. Por otra parte, se encuentra el
despacho económico de enerǵıa que consiste en suministrar la enerǵıa demandada
por una red eléctrica, de tal manera que se logren beneficios importantes, tales
como la disminución de costos, el ahorro energético y el aumento de la vida útil
de la infraestructura [5].
1En mecatrónica, se conoce como efector final o gripper al dispositivo que se encuentra en el
extremo de un brazo robótico, con el cual se manipulan los objetos.
2Los GDL determinan el número de parámetros necesarios para definir la posición de los
miembros de un mecanismo en cada instante.
CAPÍTULO 1. INTRODUCCIÓN 3
Figura 1.1: Mecanismo plano de cuatro barras. Adaptada de [6].
La nomenclatura de la Figura 1.1 es la siguiente [6]:
1. El eslabón 1, MN , de longitud a1, se conoce como bastidor o eslabón fijo.
2. El eslabón 2, MA, de longitud a2, se conoce como manivela o eslabón de
entrada.
3. El eslabón 3, AB, de longitud a3, se conoce como eslabón acoplador.
4. El eslabón 4, NB, de longitud a4, se conoce como seguidor o eslabón de
salida.
5. θi (i = 1, 2, 3, 4) denota los ángulos de las cuatro barras con respecto al eje
de referencia X.
En CIDETEC, tanto los problemas de optimización de trayectoria como los de
despacho económico de enerǵıa, se resuelven a través de algoritmos inspirados en
la naturaleza, los cuales permiten encontrar soluciones más competitivas a las que
encuentran los métodos clásicos. Sin embargo, a pesar de la eficacia que proveen
los algoritmos bioinspirados, existe la dificultad de hallar una combinación ade-
cuada de los parámetros que intervienen en ellos; es decir, aquella combinación
que permitirá hallar una solución altamente competitiva en el menor tiempo.
De acuerdo a [7], la clasificación de técnicas de configuración de parámetros se
divide en:
Calibración de parámetros: Se da en la etapa previa a la ejecución del
algoritmo, mediante diferentes métodos se identifica aquella combinación
que brinda mejores resultados. Al ejecutar el algoritmo se mantienen estos
valores constantes.
CAPÍTULO 1. INTRODUCCIÓN 4
Control de parámetros: Este método se presenta durante la ejecución,
utilizando diversas técnicas que permitirán ajustar los parámetros a partir
de la retroalimentación de la búsqueda, o del simple paso de los ciclos del
algoritmo.
En el CIDETEC se emplea la calibración de parámetros para obtener una com-
binación de valores que produzca una solución aceptable, sin embargo, se deben
realizar múltiples ejecuciones previas a la ejecución final del algoritmo. Conside-
rando que cada una de ellas podŕıa demorar desde varios minutos hasta varias
horas, la calibración requiere de mucho tiempo y en la mayoŕıa de las veces el
número de evaluaciones empleadas en el algoritmo pudiera resultar excesivo.
Con base en el rendimiento que presenta el algoritmo DECV, y en que se ha
demostrado que las técnicas de control de parámetros son más eficientes que la
calibración al encontrar la solución al problema [8] [9] [10], se propuso incorporar
un mecanismo de control a dicho algoritmo que permitiera configurar automáti-
camente los parámetros relacionados con la Evolución Diferencial, con el fin de
mejorar el proceso de búsqueda de la solución en problemas de optimización me-
catrónica.
1.2. Objetivos
1.2.1. Objetivo General
Aplicar el algoritmo DECV en la solución de problemas de optimización me-
catrónica, empleando una técnica de control en los parámetros relacionados con
la Evolución Diferencial que permita disminuir los recursos computacionales que
se consumen, medidos por el número de evaluacionesde soluciones.
1.2.2. Objetivos Expećıficos
Aplicar el algoritmo DECV a los problemas de optimización.
Comparar los resultados obtenidos con DECV contra los resultados de los
algoritmos empleados por CIDETEC.
Establecer una técnica de control de parámetros que mejore el rendimiento
del algoritmo, ya sea disminuyendo las evaluaciones requeridas o mejorando
el resultado final obtenido.
CAPÍTULO 1. INTRODUCCIÓN 5
1.3. Hipótesis
Es posible aplicar una técnica de control de parámetros al algoritmo DECV, que
permita mejorar los resultados finales obtenidos y/o disminuir los recursos compu-
tacionales empleados actualmente, medidos por el número de evaluaciones de so-
luciones, al resolver los problemas de optimización mecatrónica planteados.
1.4. Justificación
El desempeño de un algoritmo de búsqueda depende de varios aspectos propios del
problema a solucionar. Dentro de estos aspectos se pueden mencionar las variables
y restricciones que intervienen, pero uno de los factores que suele determinar la
calidad de la búsqueda es la configuración de los parámetros del algoritmo [11].
Como ya se mencionó, optar por la calibración implica realizar un gran número
de pruebas con diferentes valores, pruebas que requieren un tiempo considerable.
Por otra parte, el control de parámetros involucra técnicas que se encargan de
ajustar los valores durante la ejecución del algoritmo, lo cual permite explorar y
explotar a mayor escala el espacio de búsqueda además de que pueden promover
la obtención de la solución en un tiempo menor.
En el art́ıculo [11], Caspitrán y Mezura mencionan lo siguiente:
En los últimos años se han realizado trabajos de investigación para
desarrollar métodos que contribuyan a la configuración de parámetros,
sin embargo ninguna de esas técnicas ha sido posicionada como domi-
nante en la literatura especializada. . . los métodos desarrollados para
la optimización de parámetros, se fundamentan en el hecho de que los
algoritmos bioinspirados son muy sensibles a los valores paramétricos
y en la influencia correlativa entre cada uno de éstos. Tales métodos
de ajuste suelen mejorar el desempeño del algoritmo y aproximan la
búsqueda a mejores resultados.
Partiendo de lo anterior, realizar un trabajo de investigación proponiendo una
técnica de control que ajustara automáticamente los parámetros en DECV, me-
joraŕıa el desempeño del algoritmo y contribuiŕıa a entender la relevancia de los
cambios que sufren dichos parámetros en las iteraciones del proceso. Además, sig-
nificaŕıa aportar un mecanismo que permita abordar problemas de optimización
similares con un algoritmo basado en Evolución Diferencial, sin la dificultad y los
recursos computacionales que implica configurarlos a través de la calibración.
CAPÍTULO 1. INTRODUCCIÓN 6
1.5. Organización del Documento
A continuación se describe el resto de las secciones que conforman este documento:
Caṕıtulo 2. Optimización. En este caṕıtulo se introduce el concepto de
optimización, se describen los componentes principales de un problema de
optimización, su clasificación y algunos tipos de técnicas utilizadas para
resolverlos.
Caṕıtulo 3. Computación Evolutiva. En este apartado se realiza una
breve introducción a la computación evolutiva, haciendo énfasis en el algo-
ritmo Evolución Diferencial del cual se detallan sus parámetros, el proceso
de selección y algunas de sus variantes, especialmente el funcionamiento de
la variante DECV.
Caṕıtulo 4. Formulación de Problemas Mecatrónicos. En este caṕıtu-
lo se plantea la formulación de los problemas del mecanismo de cuatro ba-
rras, el efector final de tres dedos y el despacho económico de enerǵıa en una
microrred aislada.
Caṕıtulo 5. Configuración de Parámetros. En este caṕıtulo se introdu-
ce brevemente el concepto de configuración de parámetros y se presenta el
mecanismo añadido para controlar los parámetros evolutivos en el algoritmo
DECV.
Caṕıtulo 6. Experimentos y Resultados. Este caṕıtulo muestra cómo
se llevó a cabo la experimentación y cuáles fueron los resultados obtenidos
al incorporar un mecanismo de control. También, se comparan dichos resul-
tados con los del algoritmo DE/rand/1/bin y la versión original de DECV.
Caṕıtulo 7. Conclusiones y Trabajo Futuro. Finalmente, en este caṕıtu-
lo se presentan las conclusiones derivadas de los resultados obtenidos aśı
como los futuros trabajos a realizar.
1.6. Publicaciones Derivadas de esta Tesis
Zapata-Zapata Maury-Faney, Mezura-Montes Efrén y Portilla-Flores Edgar-
Alfredo; Evolución diferencial con memoria de parámetros para la optimiza-
ción de mecanismos de cuatro barras, En: Congreso Mexicano de Inteligencia
Artificial (COMIA 2017). Research in Computer Science (2017) (En impre-
sión).
CAPÍTULO 1. INTRODUCCIÓN 7
1.7. Conclusiones del Caṕıtulo
El objetivo principal del caṕıtulo de introducción fue mostrar la importancia de
realizar el estudio presentado, la cual radica en incorporar una técnica de control
de parámetros a un algoritmo basado en Evolución Diferencial, que permita a la
comunidad mecatrónica resolver problemas de optimización evitando los inconve-
nientes que implica calibrar el algoritmo manualmente.
CAPÍTULO 2
Optimización
2.1. Concepto de Optimización
La optimización es una herramienta importante para la toma de decisiones y el
análisis de sistemas f́ısicos. Para hacer uso de esta herramienta, inicialmente se de-
be identificar algún objetivo, el cual es una medida cuantitativa del desempeño del
sistema bajo estudio. Este objetivo podŕıa ser ganancia, tiempo, enerǵıa potencial,
o cualquier cantidad o combinación de cantidades que pueda ser representada por
un sólo número. El objetivo depende de ciertas caracteŕısticas del sistema, llama-
das variables. La finalidad, es encontrar los valores de las variables que optimicen
el objetivo. A menudo las variables son restringidas de alguna manera, por ejem-
plo, la tasa de interés en algún prestamo no puede ser negativa [12].
Otra definición propuesta por Baquela y Redchuk [13], desde el punto de vista de
la Investigación de Operaciones (IO), establece que:
Las técnicas de optimización se enfocan en determinar la poĺıtica a
seguir para maximizar o minimizar la respuesta del sistema. Dicha
respuesta, en general, es un indicador del tipo ‘Costo’, ‘Producción’,
‘Ganancia’, etc., la cual es una función de la poĺıtica seleccionada.
Dicha respuesta se denomina objetivo, y la función asociada se llama
función objetivo.
En donde poĺıtica se refiere a las variables independientes de la función de res-
puesta.
8
CAPÍTULO 2. OPTIMIZACIÓN 9
Matemáticamente hablando, para el caso de la optimización numérica, pues existe
también la optimización combinatoria que no es tema de esta tesis, la optimización
es el proceso de [14]:
(i) la formulación y
(ii) la solución de un problema de optimización restringido de la forma ma-
temática general:
min f(x), x = [x1, x2, ..., xn]T ε Rn (2.1)
sujeto a las restricciones:
gj(x) ≤ 0, j = 1, 2, ...,m
hk(x) = 0, k = 1, 2, ..., r (2.2)
En donde f(x), gj(x) y hk(x) son funciones escalares del vector columna real x.
Los componentes continuos xi de x = [x1, x2, ..., xn]T son llamados variables
de diseño, f(x) es la función objetivo, gj(x) denota las respectivas funciones de
restricciones de desigualdad y hk(x) las funciones de restricciones de igualdad.
La Optimización Matemática también es conocida como Optimización Numéri-
ca, Programación No Lineal o Programación Matemática. En términos más ge-
nerales, la Optimización Matemática puede ser descrita como la ciencia para de-
terminar las mejores soluciones a los problemas matemáticamente definidos, que
pueden ser modelos de realidad f́ısica o de sistemas de fabricación y gestión [14].
2.2. Variables de Diseño
Cualquier sistema o componente de ingenieŕıa está definido por un conjunto de
cantidades, algunasde las cuales son vistas como variables durante el proceso de
diseño. Estas cantidades que se tratan como variables, son llamadas variables de
decisión o de diseño. Las variables de diseño se representan como un vector de
diseño x = [x1, x2, ..., xn]. Si se considera un espacio cartesiano de n dimensiones,
en donde cada eje de coordenadas representa una variable de diseño xi (i =
1, 2, .., n), el espacio recibe el nombre de espacio variable de diseño o simplemente
espacio de diseño. Cada punto en el espacio de diseño n-dimensional se denomina
punto de diseño y representa una solución posible o imposible al problema [15].
Para formular un problema de optimización, el primer paso es identificar sus
variables de diseño [1].
CAPÍTULO 2. OPTIMIZACIÓN 10
2.3. Restricciones de Diseño
En muchos problemas prácticos, las variables de diseño no se pueden elegir arbi-
trariamente, sino que tienen que satisfacer ciertos requisitos funcionales especifi-
cados. Las restricciones que deben cumplirse para producir un diseño aceptable
comúnmente se denominan restricciones de diseño. Las restricciones que represen-
tan limitaciones en el comportamiento o rendimiento del sistema se denominan
restricciones de comportamiento o funcionales. Las restricciones que representan
limitaciones f́ısicas en variables de diseño, tales como disponibilidad, factibilidad
de producción y transportabilidad, se conocen como restricciones geométricas [15].
Después de haber determinado cuáles serán las variables de diseño, la siguien-
te tarea es identificar las restricciones asociadas con el problema de optimización.
Sin embargo, no existe una forma única para formular una restricción en todos
los problemas. La naturaleza y el número de restricciones que serán incluidas en
la formulación dependen del usuario [1].
Generalmente hay dos tipos de restricciones que surgen de la mayoŕıa de las
consideraciones; restricciones de desigualdad y de igualdad. Las restricciones de
desigualdad establecen que las relaciones funcionales entre las variables de diseño
sean mayores que (>) o menores que (<) un valor de recurso. Mientras que las
restricciones de igualdad establecen que las relaciones funcionales deben coincidir
exactamente con el valor de recurso, es decir, iguales a (=). Debido a que las
restricciones de igualdad son más dif́ıciles de manejar, deben ser evitadas tanto
como sea posible [1].
2.4. Función Objetivo
La tercera tarea en el proceso de formulación, es encontrar la función objetivo en
términos de las variables de diseño y demás parámetros del problema [1]. Esta
función nos permitirá hallar los valores de las variables de diseño, que optimicen
el objetivo cuantitativo del caso de estudio.
Cuando se busca el valor mı́nimo en el objetivo se dice que la función objeti-
vo es una función de costo, en el caso espećıfico en donde el mı́nimo que se está
buscando es cero, algunas veces es conocida como función de error. En contraste,
aquellas funciones que describen propiedades a ser maximizadas, comúnmente se
conocen como funciones de aptitud. Sin embargo, dado que el cambio de signo en
la función convierte sus máximos en mı́nimos, no se pierde generalidad refiriendose
a la discusión únicamente como minimización de la función [2].
CAPÍTULO 2. OPTIMIZACIÓN 11
La función objetivo posee varios atributos que pueden afectar el rendimiento de
un optimizador. A continuación se mencionan dichos atributos [2].
Cuantificación de parámetros: que se refiere a qué tipo de variables se mane-
jan en la función objetivo (continuas, discretas o si pertenecen a un conjunto
finito), y cuántas de ellas son de cada tipo.
Dependencia de parámetros: especifica si los parámetros pueden ser optimi-
zados de forma independiente o el valor de uno o más parámetros depende
de otros.
Dimensionalidad: el número de variables que definen la función objetivo.
Modalidad: indica si la función objetivo tiene sólo un valor mı́nimo local o
más de uno, es decir, si es uni-modal o multi-modal.
Dependencia de tiempo: señala si la ubicación del valor óptimo es dinámica
o estática.
Ruido: si cada vez que se evalúa el mismo vector se obtiene un valor diferente,
entonces existe el ruido.
Restricciones: indica si la función objetivo se encuentra sujeta a restricciones
de igualdad y/o desigualdad o no cuenta con restricciones
Diferenciabilidad: cuando se puede diferenciar la función objetivo en todos
sus puntos de interés.
2.5. Optimos Locales y Globales
Como se mencionó en la Sección 2.2, el espacio de diseño dependerá del número
de variables de decisión que existan en el problema de optimización. Si existen n
variables, entonces el espacio de diseño será de n dimensiones. Una vez que se ha
formulado el problema de optimización, se procede con la búsqueda de la mejor
solución dentro del espacio de diseño.
En un problema de optimización restringido, las restricciones:
Reducen la cantidad de alternativas posibles, definiendo un espacio
acotado de soluciones factibles (y complicando, de paso, la resolución
del problema)...en optimización, cualquier vector con componentes
apareadas a las variables independientes que satisfaga las restriccio-
nes, es una solución factible, es decir, una poĺıtica que es posible de
implementar en el sistema. [13].
CAPÍTULO 2. OPTIMIZACIÓN 12
En un problema sin restricciones todas las soluciones son factibles. La sección
del espacio de diseño en la que se encuentran las soluciones factibles, es conocida
como región o espacio factible.
Dentro del espacio factible se pueden encontrar diferentes tipos de puntos
(soluciones) óptimos, es decir, soluciones que además de cumplir las restricciones
minimizan o maximizan, según sea el caso, el objetivo. Estos puntos son [1]:
Punto óptimo local: un punto o solución x∗ es llamado punto local óptimo,
si no existe un punto en el vecindario de x∗ que sea mejor que x∗. En el caso
de problemas de minimización, un punto x∗ es un punto mı́nimo local si no
hay algún punto en el vecindario que tenga un valor de función menor que
f(x∗).
Punto óptimo global: un punto o solución x∗∗ es llamado punto global ópti-
mo, si no existe un punto en todo el espacio de búsqueda que sea mejor que
el punto x∗∗. De forma similar, un punto x∗∗ es un punto mı́nimo global si
no hay algún punto en todo el espacio de búsqueda que tenga un valor de
función menor que f(x∗∗).
En la Figura 2.1 se aprecian de forma más clara los conceptos anteriores.
Figura 2.1: Representación de puntos óptimos. Gráfica creada con información de
[16].
CAPÍTULO 2. OPTIMIZACIÓN 13
2.6. Clasificación de Problemas de Optimización
Los problemas de optimización pueden ser clasificados de acuerdo a las siguientes
caracteŕısticas [15]:
Existencia de restricciones: el problema puede ser clasificado como restrin-
gido o no restringido, dependiendo de si existen o no restricciones.
Número de funciones objetivo: de acuerdo al número de funciones objeti-
vo que serán minimizadas, un problema puede ser mono-objetivo o multi-
objetivo.
Naturaleza de las variables de diseño: con base en esta caracteŕıstica, los
problemas de optimización puede ser clasificados en dos grandes categoŕıas;
En la primera categoŕıa, el problema es encontrar valores a un conjunto de
parámetros de diseño que hacen que una determinada función sea mı́nima,
sujeto a ciertas restricciones. Estos problemas son llamados problemas de
optimización estática o de parámetros.; En la segunda categoŕıa, el objetivo
es encontrar un conjunto de parámetros de diseño, los cuales son funciones
continuas de algún otro parámetro que minimice una función objetivo sujeta
a un conjunto de restricciones. Este tipo de problema, es conocido como
problema de optimización dinámica o de trayectoria.
Estructura f́ısica del problema: de acuerdo a este criterio, el problema puede
ser un problema de control óptimo (OC por las siglas de OptimalControl)
o de control no óptimo. Un problema de control óptimo es un problema de
programación matemática que implica varias etapas, en donde cada etapa
evoluciona desde la etapa anterior de una manera prescrita. Generalmen-
te se describe por dos tipos de variables: las variables de control (diseño)
y las de estado. Las variables de control definen el sistema y rigen la evo-
lución del mismo a la siguiente etapa y las variables de estado describen
el comportamiento o estado del sistema en cualquier etapa. Por definición,
aquellos problemas que no manejan ambas variables son llamados problemas
de control no óptimo.
Naturaleza de las ecuaciones implicadas: otra clasificación importante de los
problemas de optimización se basa en la naturaleza de las expresiones para
la función objetivo y las restricciones. De acuerdo con esta clasificación, los
problemas de optimización pueden ser lineales, no lineales, geométricos o
cuadráticos.
Valores permitidos de las variables de diseño: según esta caracteŕıstica los
problemas de optimización pueden ser enteros o reales.
CAPÍTULO 2. OPTIMIZACIÓN 14
Naturaleza determinista de las variables: los problemas pueden ser proble-
mas de programación determinista o estocástica. Un problema de progra-
mación estocástica es aquél en donde algunos o todos los parámetros son
probabiĺısticos.
Separabilidad de las funciones: en donde un problema puede ser separable
o no separable según la separabilidad de la función objetivo y las funciones
de restricción.
2.7. Algoritmos de Optimización
La formulación de problemas de diseño en ingenieŕıa vaŕıa de acuerdo al problema.
Ciertos problemas involucran términos lineales para las restricciones y la función
objetivo, pero otros incluyen términos no lineales. Desafortunadamente, no existe
un algoritmo de optimización que resuelva todo tipo de problemas con el mismo
nivel de eficiencia. Algunos algoritmos pueden funcionar bien en algunos problemas
pero mal en otros. Es por eso que la literatura de optimización contiene un gran
número de algoritmos, cada uno adecuado para resolver un tipo particular de
problema. Los algoritmos de optimización pueden ser clasificados en los siguientes
grupos [1]:
Algoritmos de optimización uni-variable: proporcionan una buena compren-
sión de las propiedades de los puntos mı́nimos y máximos en una función, y
de cómo los algoritmos de optimización trabajan iterativamente para encon-
trar el punto óptimo en un problema. Se dividen en dos grandes categoŕıas:
métodos directos y métodos basados en gradiente. Los métodos directos no
utilizan información derivada de la función objetivo; Sólo utilizan valores
de la función objetivo para guiar el proceso de búsqueda. Sin embargo, los
métodos basados en gradiente utilizan información derivada de primer y/o
segundo orden para guiar dicho proceso.
Algoritmos de optimización multi-variable: demuestran cómo progresa la
búsqueda del punto óptimo en múltiples dimensiones. Dependiendo de si
la información del gradiente se utiliza o no, estos algoritmos también se
clasifican en técnicas directas y basadas en gradiente.
Algoritmos de optimización restringidos: estos algoritmos utilizan los al-
goritmos de optimización uni-variable y multi-variable de forma repetida y
simultánea, conservando el esfuerzo de búsqueda dentro de la región factible.
CAPÍTULO 2. OPTIMIZACIÓN 15
Algoritmos de optimización especializados: existe una serie de algoritmos
estructurados que son ideales sólo para una cierta clase de problemas de op-
timización. Dos de estos algoritmos son la programación entera y la progra-
mación geométrica, los cuales se utilizan a menudo en problemas de diseño
en ingenieŕıa.
Algoritmos de optimización no tradicionales [15]: en años recientes, se han
desarrollado algunos métodos de optimización que difieren de las técnicas
tradicionales de programación matemática. La mayoŕıa de estos métodos se
basan en ciertas caracteŕısticas y comportamiento de los sistemas biológi-
cos, moleculares, de insectos y neurobiológicos. Dentro de estos algoritmos
podemos encontrar los siguientes:
- Algoritmos Evolutivos
- Recocido simulado
- Optimización de cúmulo de part́ıculas
- Optimización de colonia de hormigas
- Optimización difusa
- Métodos basados en redes neuronales
2.8. Conclusiones del Caṕıtulo
En este caṕıtulo se definieron los conceptos principales de la optimización, que es
una herramienta importante para el análisis de sistemas f́ısicos como lo son los
sistemas mecatrónicos. El uso de esta herramienta involucra seguir los siguientes
pasos en la formulación del problema: 1) definir el objetivo que desea optimizar-
se; 2) identificar las variables de diseño que definen al sistema; 3) identificar las
restricciones de diseño que deben cumplir las variables para producir un diseño
aceptable; y 4) encontrar la función objetivo que permitirá medir qué tan buena es
la solución encontrada. Una vez que se ha formulado el problema de optimización,
éste puede resolverse a través de distintas técnicas, entre las cuales se encuentran
los Algoritmos Evolutivos.
CAPÍTULO 3
Computación Evolutiva
3.1. Introducción a la Computación Evolutiva
La computación evolutiva es un área de investigación dentro de las Ciencias de la
Computación. Como su nombre sugiere, es una caracteŕıstica especial de la compu-
tación que se inspira en el proceso de la evolución natural. No es sorprendente que
algunos cient́ıficos en computación hayan elegido la evolución natural como fuente
de inspiración: el poder de la evolución en la naturaleza es evidente en la variedad
de especies que conforman el mundo, cada una adaptada para sobrevivir en su
propio entorno. La metáfora fundamental de la computación evolutiva relaciona
esta evolución natural con un estilo particular de resolución de problemas: el de
prueba y error [17].
Para comprender la metáfora anterior, se debe considerar la evolución natural
de la siguiente forma: existe un entorno lleno de una población de individuos que
luchan por la supervivencia y la reproducción. La aptitud de dichos individuos está
determinada por el medio ambiente, y se relaciona con la forma en que tienen éxito
en el logro de sus objetivos. Es decir, representa la posibilidad que tienen para
sobrevivir y reproducirse. Mientras tanto, en el contexto de un proceso estocástico
de prueba y error, se tiene una colección de soluciones candidatas. Su calidad (qué
tan bien resuelven el problema) determina la posibilidad de que se mantengan y se
utilicen como base para construir nuevas soluciones candidatas [17]. La analoǵıa
entre ambos escenarios se puede observar en la Tabla 3.1, adaptada de [17].
16
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 17
Evolución Resolución de problema
Entorno ↔ Problema
Individuo ↔ Solución candidata
Aptitud ↔ Calidad
Tabla 3.1: Metáfora básica de la computación evolutiva que relaciona la evolución
natural con la resolución de problemas.
3.2. Algoritmos Evolutivos
Con el paso de los años han surgido diversas variantes de los algoritmos evoluti-
vos para resolver problemas de optimización. Sin embargo, la idea detrás de todos
ellos es la misma: dada una población de individuos dentro de un entorno con re-
cursos limitados, la competencia por dichos recursos provoca la selección natural
(supervivencia del más apto). Esto a su vez provoca un aumento en la aptitud de
la población [17].
Dada una función de calidad para ser minimizada, el proceso que sigue un algo-
ritmo evolutivo es el siguiente [17]:
1. Crear aleatoriamente un conjunto de soluciones candidatas, es decir, ele-
mentos del dominio de la función.
2. Posteriormente se debe aplicar la función de calidad a las soluciones como
una medida de aptitud abstracta (cuanto más alta mejor).
3. A continuación, tomando como base los valores de aptitud, algunos de los
mejores candidatos son elegidos para crear la poblaciónde la siguiente gene-
ración. Esto se hace aplicando recombinación y/o mutación a ellos. Recom-
binación es un operador que se aplica a dos o más candidatos seleccionados
(los llamados padres), produciendo de uno o más candidatos nuevos (los hi-
jos). La mutación se aplica a un candidato y da lugar a un nuevo miembro.
Por lo tanto, la ejecución de las operaciones de recombinación y mutación
en los padres conduce a la creación de un conjunto de nuevos candidatos (la
descendencia). Éstos tienen su aptitud evaluada y después compiten con los
viejos para ganar un lugar en la generación siguiente.
Este proceso puede ser iterado hasta que se encuentre un candidato con suficiente
calidad (una solución) o hasta que se haya alcanzada un ĺımite computacional
establecido previamente [17]. En el Algoritmo 3.1 se puede apreciar el esquema
general de un algoritmo evolutivo en seudocódigo.
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 18
Algoritmo 3.1 Algoritmo Evolutivo
1: Inicio
2: INICIALIZAR la población con soluciones candidatas aleatorias;
3: EVALUAR cada candidato;
4: while no se cumpla la condición de paro do
5: SELECCIONAR padres;
6: RECOMBINAR parejas de padres;
7: MUTAR la descendencia resultante;
8: SELECCIONAR individuos para la siguiente generación
9: end while
10: Fin
3.3. Evolución Diferencial
El algoritmo Evolución Diferencial (DE por sus siglas en inglés) fue desarrollado
por Price y Storn en 1995 para ser un optimizador de funciones confiable, versátil
y fácil de usar. Desde entonces, DE ha sido probado en competencias como el
ICEO (International Contest on Evolutionary Optimization) de la IEEE y en el
mundo real en una amplia variedad de aplicaciones [2].
DE es un algoritmo aproximado de optimización basado en población, que
ataca el problema mediante el muestreo de la función objetivo en múltiples pun-
tos seleccionados al azar. Los ĺımites preestablecidos de los parámetros definen el
dominio del cual se eligen los NP vectores de la población inicial. Cada vector
se indiza con un número de 1 a NP , y representa una solución candidata. Por
cada vector en la población, DE genera nuevos vectores que son perturbaciones
(mutaciones) de vectores existentes, esos vectores son producidos a partir de una
diferencia escalada de dos vectores de la población seleccionados aleatoriamente.
Posteriormente el vector diferencia obtenido se suma a un tercer vector aleatorio
seleccionado, obteniendo aśı el vector mutante (v) que será el que se recombi-
ne con el vector padre para dar origen al vector trial (u), que a su vez será el
que compita con el vector padre. Aquel que posea el menor valor de la función
objetivo (asumiendo minimización) será marcado como miembro de la siguiente
generación. El proceso se repite hasta que todos los NP vectores de la población
hayan competido con un vector trial generado mediante el proceso antes descrito.
Cuando se ha probado el último vector trial, aquellos vectores que hayan ganado
serán los nuevos padres de la siguiente generación en el ciclo evolutivo [2].
3.3.1. Inicialización
El algoritmo DE parte de una población Px conformada por NP vectores xi,g,
D-dimensionales:
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 19
Px,g = {xi,g}, i = 1, 2, ..., NP, g = 1, 2, ..., gmax
xi,g = {xj,i,g}, j = 1, 2, ..., D
(3.1)
El ı́ndice g = 1, 2, ..., gmax, indica la generación a la cual pertenece un vector.
Asimismo, cada vector tiene asignado un ı́ndice de población i, el cual va desde
1 hasta NP . Los parámetros o variables que conforman el vector tienen asignado
un ı́ndice j, que va desde 1 hasta D [2].
Antes de que la población pueda ser inicializada, tanto el ĺımite inferior (I)
como el superior (S) de cada parámetro j, deben ser especificados. Teniendo los
ĺımites de los parámetros, los vectores xi,g pueden ser creados con valores dentro
del intervalo [Ij, Sj], es decir, Ij ≤ xj,i,g ≤ Sj.
3.3.2. Mutación
La Evolución Diferencial muta y recombina a los individuos de la población para
producir una población de NP vectores trial. En particular, la mutación dife-
rencial añade una diferencia escalada de vectores, obtenidos al azar, a un tercer
vector. La Ecuación 3.2 muestra cómo se combinan tres vectores diferentes elegidos
aleatoriamente para crear un vector mutante vi,g:
vi,g = xr0,g + F (xr1,g − xr2,g) (3.2)
El factor de escala, F ∈ (0, 1+), es un número real positivo que escala el vector
diferencia que determina la dirección de búsqueda. Aunque no exista ĺımite supe-
rior de F, los valores efectivos rara vez son mayores a 1.0 [2].
El ı́ndice del vector base (r0) puede ser determinado de distintas formas. Sin
embargo, en la versión clásica del algoritmo DE se obtiene de forma aleatoria al
igual que los ı́ndices del vector diferencia, r1 y r2. Tanto el ı́ndice r0 como r1 y
r2 deben ser diferentes entre śı y además diferentes al ı́ndice del vector target, i.
Es decir:
vi,g = xr0,g + F (xr1,g − xr2,g), r0 6= r1 6= r2 6= i (3.3)
3.3.3. Recombinación
La recombinación intercambia o fusiona aleatoriamente los valores de dos o más
vectores para crear vectores trial. La recombinación discreta, también conocida co-
mo cruza, es una operación en la que los elementos del vector trial se conforman
de los elementos del vector padre y del vector mutante seleccionados aleatoria-
mente. Por el contrario, la recombinación continua o aritmética expresa vectores
trial como combinaciones lineales de vectores. Tanto la recombinación discreta
como la continua tienen varias formas de implementación [2]:
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 20
Cruza
• Un punto
• N-puntos
• Exponencial
• Uniforme (binomial)
Recombinación Continua
• Lineal
• Intermedia
• Intermedia extendida
Para fines de este trabajo de investigación, a continuación se explica la cruza
uniforme (binomial), ya que es el tipo de recombinación que se emplea en el
algoritmo DECV. Para información adicional sobre los tipos de recombinación
restantes, se puede consultar [2].
Cruza Uniforme (Binomial)
La cruza es uniforme en el sentido de que cada elemento, independientemente de
su ubicación en el vector trial, tiene la misma probabilidad (pCr) de heredar su
valor de un vector dado [2]. En palabras más detalladas, Capistrán menciona en
[18] lo siguiente:
La recombinación binomial consiste en intercambiar información entre
el vector padre (target) y el vector mutado, por medio de una pro-
babilidad de recombinación CR ∈ [0, 1) y un valor entero aleatorio
jrand ∈ [1...NP ]. CR vaŕıa el número de elementos del vector padre
y del vector mutante que serán incluidos en el vector hijo. Con jrand
aseguramos que el vector hijo (trial) sea diferente del vector target al
incluir en él, por lo menos uno de los parámetros del vector mutado.
La Ecuación 3.4 muestra el comportamiento descrito anteriormente.
uj,i,g =
{
vj,i,g si (randj[0, 1)) < CR o j = jrand
xj,i,g en caso contrario
(3.4)
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 21
3.3.4. Selección
Si el vector trial, ui,g, tiene un valor de función objetivo igual o inferior (asumiendo
minimización) al de su vector target, xi,g, sustituye al vector target en la siguiente
generación; de lo contrario, el target conservará su lugar en la población al menos
durante una generación más (Ecuación 3.5). Una vez creada la nueva población, se
repite el proceso de mutación, recombinación y selección hasta que se satisfaga un
criterio de terminación preestablecido, por ejemplo, que el número de generaciones
alcance un valor máximo gmax especificado previamente [2].
xi,g+1 =
{
ui,g si f(ui,g) ≤ f(xi,g)
xi,g en caso contrario
(3.5)
3.3.5. Algoritmo DE clásico
En el Algoritmo 3.2 se puede observar la versión clásica de Evolución Diferencial
[2], también conocida como variante DE/rand/1/bin, y la forma en la que se
integran los procesos descritos en las secciones anteriores de este caṕıtulo.
Algoritmo 3.2 DE/rand/1/bin
1: Inicio
2: Crear aleatoriamente la población inicialxi,0, donde i = 1, ..., NP
3: Evaluar la población f(xi,0), donde i = 1, ..., NP
4: for g = 1 hasta gmax do
5: for i = 1 hasta NP do
6: Seleccionar de forma aleatoria r0 6= r1 6= r2 6= i
7: jrand = randint[1, D]
8: for j = 1 hasta D do
9: if (randj[0, 1) < CR o j = jrand then
10: uj,i,g = xj,r0,g + F (xj,r1,g − xj,r2,g)
11: else
12: uj,i,g = xj,i,g
13: end if
14: end for
15: if f(ui,g) ≤ f(xi,g) then
16: xi,g+1 = ui,g
17: end if
18: end for
19: end for
20: Fin
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 22
3.3.6. Variantes de DE
Existe un esquema de nomenclatura desarrollado para hacer referencia a las va-
riantes del algoritmo DE. Dicho esquema utiliza la siguiente notación: DE/x/y/z,
en donde “DE” se refiere al algoritmo Evolución Diferencial (Differential Evolu-
tion),“x” especifica la forma en la que el vector base (r0) es seleccionado, puede
ser de forma aleatoria (rand), el mejor individuo hasta el momento (best), o algún
otro tipo de selección. La letra “y” indica el número de diferencias de vectores
que contribuyen al diferencial. Finalmente el operador “z” representa el tipo de
recombinación que se utiliza, en las versiones más comunes del algoritmo DE se
utiliza recombinación binomial (bin) o exponencial (exp) [19] [2] [20].
Como se mencionó anteriormente, la variante DE/rand/1/bin es la versión
clásica del algoritmo DE, sin embargo, desde el surgimiento del algoritmo muchas
otras variantes han sido propuestas, las más populares se mencionan a continua-
ción [18] [2] [20]:
DE/rand/1/bin
uj,i,g =
{
vj,i,g = xj,r0,g + F (xj,r1,g − xj,r2,g) si (randj [0, 1)) < CR o j = jrand
xi,i,g en caso contrario
DE/rand/1/exp
uj,i,g =
{
vj,i,g = xj,r0,g + F (xj,r1,g − xj,r2,g) mientras (randj [0, 1)) < CR o j = jrand
xi,i,g en caso contrario
DE/best/1/bin
uj,i,g =
{
vj,i,g = xj,best + F (xj,r1,g − xj,r2,g) si (randj [0, 1)) < CR o j = jrand
xi,i,g en caso contrario
DE/best/1/exp
uj,i,g ={
vj,i,g = xj,best + F (xj,r1,g − xj,r2,g) mientras (randj [0, 1)) < CR o j = jrand
xi,i,g en caso contrario
DE/current-to-rand/1
uj,i,g = vj,i,g = xj,i,g + F (xj,r0,g − xj,i,g) + F (xj,r1,g − xj,r2,g)
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 23
DE/current-to-best/1
uj,i,g = vj,i,g = xj,i,g + F (xj,best − xj,i,g) + F (xj,r1,g − xj,r2,g)
DE/current-to-rand/1/bin
uj,i,g ={
vj,i,g = xj,i,g + F (xj,r0,g − xj,i,g) + F (xj,r1,g − xj,r2,g) si (randj [0, 1)) < CR o j = jrand
xi,i,g en caso contrario
DE/current-to-best/1/bin
uj,i,g ={
vj,i,g = xj,i,g + F (xj,best − xj,i,g) + F (xj,r1,g − xj,r2,g) si (randj [0, 1)) < CR o j = jrand
xi,i,g en caso contrario
Existen aún más variantes del algoritmo DE [19] [2], pero este trabajo de in-
vestigación se centra en el algoritmo DECV, el cual hace uso de las variantes
DE/rand/1/bin y DE/best/1/bin y se explica en la siguiente sección.
3.4. Algoritmo DECV
El algoritmo DECV (Evolución Diferencial con Variantes Combinadas) fue pre-
sentado en [4], en donde se realizó una comparación del comportamiento de al-
gunas variantes del algoritmo Evolución Diferencial en problemas de prueba que
incorporaban restricciones. Después de observar que la variante DE/rand/1/bin
teńıa la habilidad de generar un conjunto diverso de direcciones de búsqueda a
partir de diferentes vectores base usando pequeñas poblaciones, y que la varian-
te DE/best/1/bin requeŕıa poblaciones más grandes debido a que las direcciones
de búsqueda se enfocan en la mejor solución, los autores decidieron combinarlas,
usando en primera instancia DE/rand/1/bin para llegar a la zona factible del
problema y posteriormente la variante DE/best/1/bin para buscar en dirección de
la mejor solución conocida. A este enfoque se le otorgó el nombre de Evolución
Diferencial con Variantes Combinadas y mostró un desempeño competitivo en el
estudio realizado.
DECV mantiene la simplicidad de la versión clásica de Evolución Diferen-
cial mostrada en el Algoritmo 3.2, la diferencia radica en la incorporación de un
mecanismo para cambiar de la variante DE/rand/1/bin a DE/best/1/bin. Este
mecanismo consiste en calcular el porcentaje de soluciones factibles (pf) en ca-
da generación (g), cuando tal porcentaje es mayor o igual (≥) al Porcentaje de
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 24
Cambio de Variante (PCV ) establecido por el usuario, se realiza el cambio en la
variante del algoritmo DE.
Adicionalmente, el algoritmo DECV incorpora un método de manejo de res-
tricciones, propuesto por Deb en [21], que consiste en tres criterios; 1) cualquier
solución factible es preferible sobre cualquier solución no factible; 2) entre dos
soluciones factibles, se prefiere aquella que tenga el mejor valor de la función ob-
jetivo; 3) entre dos soluciones no factibles, se prefiere aquella que tenga la menor
cantidad de violación de restricciones.
DECV es un algoritmo versátil y fácil de implementar, el orden en el que se
aplican las variantes puede ser modificado según las necesidades del usuario [4],
y además podŕıan utilizarse combinaciones de variantes diferentes a la propuesta.
A continuación, en el Algoritmo 3.3, se muestra el seudocódigo correspondiente a
DECV.
3.5. Conclusiones del Caṕıtulo
Durante el desarrollo de este caṕıtulo se habló de los algoritmos evolutivos, técni-
cas que se basan en la evolución natural de las especies en donde se parte de
una población de individuos que representan las soluciones al problema, estos
individuos pasan por ciertos procesos que los hacen mejorar con el paso de las
generaciones hasta finalizar el ciclo evolutivo. De de manera general los algorit-
mos evolutivos incluyen cuatro etapas; 1) inicialización, 2) mutación, 3) cruza o
recombinación y 4) selección. La integración e iteración de dichos procesos per-
mite hallar una solución competitiva al problema que se está resolviendo en un
tiempo determinado. Evolución Diferencial es un algoritmo evolutivo que ha sido
empleado para resolver distintos problemas de optimización. Desde el surgimiento
de esta técnica han sido propuestas muchas variantes, una de ellas es el algoritmo
DECV, en el cual se enfoca este trabajo de investigación.
CAPÍTULO 3. COMPUTACIÓN EVOLUTIVA 25
Algoritmo 3.3 DECV
1: Inicio
2: Crear aleatoriamente la población inicial xi,0, donde i = 1, ..., NP
3: Evaluar la población f(xi,0), donde i = 1, ..., NP
4: xbest = x1,0
5: for i = 2 hasta NP (Se obtiene el mejor individuo de la población inicial) do
6: if f(xi,0) es mejor que f(xbest) (basado en criterios de Deb) then
7: xbest = xi,0
8: end if
9: end for
10: for g = 1 hasta gmax do
11: Se calcula el pf (porcentaje de soluciones factibles)
12: for i = 1 hasta NP do
13: if pf ≥ PCV then
14: Seleccionar aleatoriamente r1 6= r2 6= i
15: else
16: Seleccionar aleatoriamente r0 6= r1 6= r2 6= i
17: end if
18: jrand = randint[1, D]
19: for j = 1 hasta D do
20: if (randj[0, 1) < CR o j = jrand then
21: if pf ≥ PCV then
22: uj,i,g = xj,best + F (xj,r1,g − xj,r2,g)
23: else
24: uj,i,g = xj,r0,g + F (xj,r1,g − xj,r2,g)
25: end if
26: else
27: uj,i,g = xj,i,g
28: end if
29: end for
30: if f(ui,g) es mejor que f(xi,g) (basado en criterios de Deb) then
31: xi,g+1 = ui,g
32: end if
33: if f(xi,g+1) es mejor que f(xbest) (basado en criterios de Deb) then
34: xbest = xi,g+1
35: end if
36: end for
37: end for
38: Fin
CAPÍTULO 4
Formulación de Problemas Mecatrónicos
En este trabajo de tesis se formularon tres problemas de optimización mecatrónica
para evaluar el desempeño del algoritmo DECV, incorporando estrategias de con-
trol en los parámetros relacionados con Evolución Diferencial; el primer problema
consistió en optimizar la trayectoria y movimiento de un mecanismo de cuatro ba-
rras en tres casos de estudio diferentes; en el segundo, se optimizó el movimiento
esférico de un efector final de tres dedos en dos casos de estudio; y finalmente,
en el tercero, se optimizó el despacho de económico de energia en una microrred
aislada. En el resto de este caṕıtulo se describe de forma detallada cadauno de
los problemas mencionados.
4.1. Diseño de un Mecanismo de Cuatro Barras
En el contexto de ingenieŕıa mecánica, un mecanismo es un dispositivo que tie-
ne como fin transferir movimiento de una fuente de entrada a una de salida. Su
estructura está conformada por barras, también llamadas eslabones, que se en-
cuentran conectadas por pasadores formando cadenas abiertas o cerradas. Sólo se
considera como mecanismo, si en tales cadenas existe al menos un eslabón fijo y
otros dos que retengan movilidad [22].
La cinemática se encarga de estudiar el movimiento de los mecanismos y los
métodos para construirlos. Para el estudio de movimiento se lleva a cabo el análisis
cinématico, en donde se especifican las dimensiones del mecanismo, sus interco-
nexiones y el movimiento de entrada. Con respecto al estudio de los métodos, se
utiliza la śıntesis cinemática, que se encarga de diseñar un mecanismo que realice
un movimiento espećıfico. Cuando se busca crear un mecanismo para cumplir con
un rendimiento dado se le llama śıntesis de tipo, y cuando se tiene un tipo de me-
canismo y un rendimiento predefinidos pero se busca determinar las dimensiones
y la posición inicial del mecanismo, se conoce como sintesis dimensional [22].
26
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 27
De acuerdo con [22] existen varios tipos de śıntesis dimensional, sin embargo,
en este problema se realiza la śıntesis dimensional de generación de trayectoria, en
donde el punto de un eslabonamiento (unión de dos barras) flotante debe seguir
una trayectoria previamente definida.
4.1.1. Cinemática del Mecanismo de Cuatro Barras
En la Figura 4.1 se muestra un mecanismo de cuatro barras conformado por:
barra de referencia (r̄1), barra de entrada (r̄2), acoplador (r̄3) y barra de salida o
balanćın (r̄4). Para efectos del análisis, se utilizan dos sistemas de coordenadas; el
primero, se encuentra fijo al mundo real (OXY ) y el segundo es para referencia
(O2XrYr). En donde (x0, y0), es la distancia entre los puntos de origen de ambos
sistemas, θ0 es el ángulo de rotación del segundo sistema con respecto del primero,
θi (i = 1, 2, 3, 4) denota los ángulos de las cuatro barras, y el par de coordenadas
(rcx, rcy) definen la posición del acoplador C [23].
Figura 4.1: Mecanismo de cuatro barras. Adaptada de [23].
Para el análisis del mecanismo se inicia con la ecuación de lazo cerrado, la cual se
define como:
~r1 + ~r4 = ~r2 + ~r3 (4.1)
Empleando notación polar para cada término en la Ecuación 4.1 se obtiene:
r1e
jθ1 + r4e
jθ1 = r2e
jθ2 + r3e
jθ3 (4.2)
Aplicando la ecuación de Euler en la Ecuación 4.2 y separando término reales e
imaginarios:
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 28
r1cosθ1 + r4cosθ4 = r2cosθ2 + r3cosθ3
r1senθ1 + r4senθ4 = r2senθ2 + r3senθ3
(4.3)
Se expresa el sistema de ecuaciones 4.3 en términos de θ4:
r4cosθ4 = r2cosθ2 + r3cosθ3 − r1cosθ1
r4senθ4 = r2senθ2 + r3senθ3 − r1senθ1
(4.4)
Se obtiene la ecuación compacta de Freudenstein elevando al cuadrado los términos
del sistema de ecuaciones 4.4 y sumando sus terminos:
A1cosθ3 +B1senθ3 + C1 = 0 (4.5)
en donde:
A1 = 2r3(r2cosθ2 − r1cosθ1) (4.6)
B1 = 2r3(r2senθ2 − r1senθ1) (4.7)
C1 = r2
1 + r2
2 + r2
3 − r2
4 − 2r1r2cos(θ1 − θ2) (4.8)
El ángulo θ3 se puede obtener como función de A1, B1, C1 y θ2, si senθ3 y cosθ3
se expresan en términos de tan( θ3
2
):
senθ3 =
2tan( θ3
2
)
1 + tan2( θ3
2
)
, cosθ3 =
1− tan2( θ3
2
)
1 + tan2( θ3
2
)
(4.9)
Una ecuación lineal de segundo orden se obtiene al sustituir en la Ecuación 4.5:
[C1 − A1] = tan2
(
θ3
2
)
+ [2B1]tan
(
θ3
2
)
+ A1 + C1 = 0 (4.10)
A partir de la Ecuación 4.10, el ángulo θ3 está dado por:
θ2 = 2arctan
[
−B1 ±
√
B2
1 + A2
1 − C2
1
C1 − A1
]
(4.11)
Para calcular el ángulo θ4 se sigue un proceso similar; el signo del radical para los
ángulos θ3 y θ4 se seleccionan de acuerdo a la configuración del mecanismo según
la Tabla 4.1. Como el punto de interés del acoplador es C, para determinar su
posición en el sistema O2XrYr se establece que:
Cxr = r2cosθ2 + rcxcosθ3 − rcysenθ3
Cyr = r2senθ2 + rcxsenθ3 + rcycosθ3
(4.12)
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 29
En el sistema global de coordenadas, este punto puede expresarse como:[
Cx
Cy
]
=
[
cosθ0 −senθ0
senθ0 cosθ0
] [
Cxr
Cyr
]
+
[
x0
y0
]
(4.13)
Como puede notarse, las Ecuaciones 4.12 y 4.13, además de las expresiones de la
cinemática del mecanismo, son todo lo que se necesita para calcular la posición
de C a través de una trayectoria.
Tabla 4.1: Signo del radical según el tipo de mecanismo.
Configuración θ3 θ4
abierta +
√ −√
cerrada −√ +
√
4.1.2. Declaración de Problemas de Optimización para Ca-
sos de Estudio del Mecanismo
Después de realizar la cinemática del mecanismo, el siguiente paso es definir el
problema de diseño como un caso de optimización numérica, por lo tanto, es nece-
sario especificar los parámetros y las operaciones matemáticas para la evaluación
del sistema.
Restricciones de diseño
Al trabajar con mecanismos de cuatro barras se deben tener en cuenta las restric-
ciones que se imponen a su funcionamiento, las cuales están relacionadas con la
movilidad y el dimensionamiento.
Ley de Grashof: establece el criterio para lograr que al menos una barra
del mecanismo se pueda mover completamente. La Ley de Grashof dice que
para un eslabonamiento plano de cuatro barras, la suma de las longitudes
más corta y más larga de los eslabones no puede ser mayor que la suma
de las longitudes de los dos eslabones restantes, si se desea que exista una
rotación relativa continua entre dos elementos [24]. Si la longitud del eslabón
más corto es o, la del más largo es l y las longitudes de las barras restantes
son m y n, entonces:
l + o < m+ n (4.14)
Para el caso del mecanismo de cuatro barras, la ley de Grashof está dada
por:
r1 + r2 < r3 + r4 (4.15)
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 30
Adicionalmente, para asegurar que el mecanismo cumpla con la ley de Gras-
hof, se añaden las siguientes restricciones:
r2 < r3, r3 < r4, r4 < r1 (4.16)
Secuencia de ángulos de entrada: Cuando el problema de śıntesis es de gene-
ración de trayectoria sin sincronización prescrita, los valores que toman los
ángulos de la manivela deben estar ordenados secuencialmente. Si el ángulo
del punto de precisión i se denota como θi2, se debe cumplir que:
θ1
2 < θ2
2 < ... < θN2 (4.17)
en donde N se refiere al número de puntos de precisión
Función Objetivo
La śıntesis dimensional del mecanismo de cuatro barras se lleva a cabo para calcu-
lar la longitud de sus barras, el ángulo de rotación con respecto al sistema OXY ,
la distancia entre los dos sistemas de coordenadas y el conjunto de ángulos para
la barra de entrada que permitirán generar la trayectoria deseada. En el sistema
global de coordenadas el punto de precisión i está dado por:
Ci
d = [Ci
xd, C
i
yd] (4.18)
El conjunto de N puntos de precisión se describe como:
Ω = {Ci
d|i ∈ N} (4.19)
Además, dado un conjunto de valores de las barras del mecanismo y sus parámetros
x0, y0, θ0, cada punto del acoplador puede ser expresado como una función de la
posición de la barra de entrada:
Ci = [Cx(θ
i
2), Cy(θ
i
2)] (4.20)
Entonces, se desea minimizar la distancia de los puntos de precisión Ci
d y los
puntos calculados Ci. La función propuesta para dicho cálculo es:
f(θi2) =
N∑
i=1
[(Ci
xd − Ci
x)
2 − (Ci
yd − Ci
y)
2] (4.21)
Tanto el análisis del mecanismo, como las restricciones de diseño y la función ob-
jetivo fueron tomadas de [23].
Para este problema se obtuvo la śıntesis dimensional de tres casos de estudio
distintos, en donde el punto C del mecanismo debe seguir una trayectoria de
puntos cartesianos previamente definidos. A continuación, se describe cada caso
de estudio.
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 31
Caso de estudio 1: seguimiento de una trayectoria linealvertical, sin
sincronización previa - MCE1
En el primer caso de estudio, tomado de [25], el acoplador debe pasar por los
seis puntos de precisión indicados en la Ecuación 4.22, los cuales se encuentran
alineados verticalmente.
Ω = {(20, 20), (20, 25), (20, 30), (20, 35), (20, 40), (20, 45)} (4.22)
El vector de variables de diseño es:
~p = [p1, p2, p3, ..., p15]T (4.23)
= [r1, r2, r3, r4, rcx, rcy, θ0, x0, y0, θ
1
2, θ
2
2, θ
3
2, θ
4
2, θ
5
2, θ
6
2]T (4.24)
en donde las primeras cuatro variables corresponden a las barras del mecanismo,
las dos siguientes definen la posición del acoplador, θ0, x0 y y0 indican la orienta-
ción del sistema O2XrYr con respecto al sistema OXY , y las variables restantes
corresponden a la secuencia de ángulos de la barra de entrada (r̄2).
Los ĺımites superior e inferior de las variables de diseño se encuentran definidos
por:
r1, r2, r3, r4 ∈ [0, 60] (4.25)
rcx, rcy, x0, y0 ∈ [−60, 60] (4.26)
θ0, θ
1
2, θ
2
2, θ
3
2, θ
4
2, θ
5
2, θ
6
2 ∈ [0, 2π] (4.27)
Se considera el problema de optimización mono-objetivo descrito de la Ecuación
4.28 a la 4.37.
min f(~p) =
N∑
i=1
[(Ci
xd − Ci
x)
2 − (Ci
yd − Ci
y)
2] ~p ∈ R15 (4.28)
Sujeto a:
g1(~p) = r1 + r2 − r3 − r4 ≤ 0 (4.29)
g2(~p) = r2 − r3 ≤ 0 (4.30)
g3(~p) = r3 − r4 ≤ 0 (4.31)
g4(~p) = r4 − r1 ≤ 0 (4.32)
g5(~p) = θ1
2 − θ2
2 ≤ 0 (4.33)
g6(~p) = θ2
2 − θ3
2 ≤ 0 (4.34)
g7(~p) = θ3
2 − θ4
2 ≤ 0 (4.35)
g8(~p) = θ4
2 − θ5
2 ≤ 0 (4.36)
g9(~p) = θ5
2 − θ6
2 ≤ 0 (4.37)
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 32
Caso de estudio 2: seguimiento de una trayectoria no alineada, con
sincronización previa - MCE2
En este caso de estudio se realiza una sincronización prescrita y la trayectoria es
no alineada, la cual consta de los siguientes puntos:
Ω = {(3, 3), (2.759, 3.363), (2.372, 3.663), (1.890, 3.862), (1, 355, 3.943)} (4.38)
El vector de variables de diseño es:
~p = [p1, p2, p3, p4, p5, p6]T (4.39)
= [r1, r2, r3, r4, rcx, rcy]
T (4.40)
Las variables x0, y0, θ0 = 0, y la sincronización prescrita está dada por la siguiente
secuencia de ángulos:
θi2 =
{
2π
12
,
3π
12
,
4π
12
,
5π
12
,
6π
12
}
(4.41)
Los ĺımites superior e inferior de las variables de diseño se encuentran definidos
por:
r1, r2, r3, r4 ∈ [0, 50] (4.42)
rcx, rcy ∈ [−50, 50] (4.43)
En este caso, el problema de optimización mono-objetivo se describe de la Ecua-
ción 4.44 a la 4.48.
min f(~p) =
N∑
i=1
[(Ci
xd − Ci
x)
2 − (Ci
yd − Ci
y)
2] ~p ∈ R6 (4.44)
Sujeto a:
g1(~p) = r1 + r2 − r3 − r4 ≤ 0 (4.45)
g2(~p) = r2 − r3 ≤ 0 (4.46)
g3(~p) = r3 − r4 ≤ 0 (4.47)
g4(~p) = r4 − r1 ≤ 0 (4.48)
Caso de estudio 3: generación de movimiento delimitado por un con-
junto de pares de puntos - MCE3
Finalmente se tiene el tercer caso de estudio, tomado de [23], en donde se consi-
deran diez pares de puntos de precisión (K = 10), dados por las coordenadas de
la Tabla 4.2. El vector de variables de diseño es:
~p = [p1, p2, p3, ..., p18, p19]T (4.49)
= [r1, r2, r3, r4, rcx, rcy, θ0, x0, y0, θ
1
2, ..., θ
10
2 ]T (4.50)
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 33
con los ĺımites superior e inferior definidos como:
r1, r2, r3, r4 ∈ [0, 60] (4.51)
rcx, rcy, x0, y0 ∈ [−60, 60] (4.52)
θ0, θ
1
2, ..., θ
10
2 ∈ [0, 2π] (4.53)
La función de este caso es diferente a la de los problemas anteriores, ya que
considera la distancia del acoplador a los dos puntos de cada par de coordenadas.
El problema de optimización mono-objetivo se describe de la Ecuación 4.54 a la
4.67
min f(~p) =
K∑
i=1
[(Ci
1xd − Ci
x)
2 − (Ci
1yd − Ci
y)
2] +
K∑
i=1
[(Ci
2xd − Ci
x)
2 − (Ci
2yd − Ci
y)
2]
~p ∈ R19
(4.54)
Sujeto a:
g1(~p) = r1 + r2 − r3 − r4 ≤ 0 (4.55)
g2(~p) = r2 − r3 ≤ 0 (4.56)
g3(~p) = r3 − r4 ≤ 0 (4.57)
g4(~p) = r4 − r1 ≤ 0 (4.58)
g5(~p) = θ1
2 − θ2
2 ≤ 0 (4.59)
g6(~p) = θ2
2 − θ3
2 ≤ 0 (4.60)
g7(~p) = θ3
2 − θ4
2 ≤ 0 (4.61)
g8(~p) = θ4
2 − θ5
2 ≤ 0 (4.62)
g9(~p) = θ5
2 − θ6
2 ≤ 0 (4.63)
g10(~p) = θ6
2 − θ7
2 ≤ 0 (4.64)
g11(~p) = θ7
2 − θ8
2 ≤ 0 (4.65)
g12(~p) = θ8
2 − θ9
2 ≤ 0 (4.66)
g13(~p) = θ9
2 − θ10
2 ≤ 0 (4.67)
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 34
Tabla 4.2: Pares de puntos de precisión - CE3
Par C1d C2d
1 (1.768, 2.3311) (1.9592, 2.44973)
2 (1.947, 2.6271) (2.168, 2.675)
3 (1.595, 2.7951) (1.821, 2.804)
4 (1.019, 2.7241) (1.244, 2.720)
5 (0.479, 2.4281) (0.705, 2.437)
6 (0.126, 2.0521) (0.346, 2.104)
7 (-0.001, 1.720) (0.195, 1.833)
8 (0.103, 1.514) (0.356, 1.680)
9 (0.442, 1.549) (0.558, 1.742)
10 (1.055, 1.905) (1.186, 2.088)
4.2. Diseño de un Efector Final de Tres Dedos
Al igual que en el problema del mecanismo de cuatro barras, en este problema
se deb́ıa obtener la śıntesis dimensional de generación de trayectoria pero ahora
de un efector final, también llamado gripper, compuesto de tres dedos. Cada dedo
está diseñado con un mecanismo de seis barras (Figura 4.2) cuya configuración
permite un agarre esférico. Debido a la simetŕıa de los dedos, basta realizar el
análisis de uno de ellos para lograr construir el efector final.
Figura 4.2: Mecanismo de seis barras para el diseño de un dedo. Adaptada de [18].
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 35
Como se puede observar en la Figura 4.2, el diseño de un dedo está conformado
por dos sub-sistemas que simulan sus falanges. El primer sub-sistema corresponde
a un mecanismo manivela-biela-corredera (MBC) que se usa en la entrada (r2, r3,
r4), y el segundo es un mecanismo de cuatro barras en la salida (r0, r′2, r5, r6).
Ambos mecanismos conforman el sistema completo, en donde el impulsor es la
corredera y el punto E en el acoplador es la salida. El análisis de este problema
fue tomado del trabajo realizado por Capistrán en [18] y se presenta en la siguiente
sección.
4.2.1. Cinemática del Efector Final de Tres Dedos
Para plantear de forma eficaz el problema, se deb́ıa realizar el análisis de los dos
sub-sitemas por separado y posteriormente unirlos en un problema de optimiza-
ción. Primeramente se analizó el mecanismo MBC (Figura 4.3) respecto al eje x
según la posición de la corredera r4, en donde existen tres casos: r4 > 0, r4 < 0 y
r4 = 0, en todos ellos la variable de interés que describe al sub-sistema es θ3. A
continuación se presenta el modelo de cada caso [18]:
Figura 4.3: Mecanismo manivela-biela-corredera. Adaptada de [18].
a) Si r4 > 0, entonces:
Se calcula el valor del ángulo θ3 que es la suma de los ángulos θ2, ϕ y π (igual
a 180◦). En la Figura 4.4 se muestran los ángulos requeridos para efectuar los
cálculos necesarios en este caso.
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 36
Figura 4.4: Mecanismo MBC para el caso r4 > 0. Adaptada de [18].
Con base en el análisis del sistema, para calcular θ2 se tiene que:
θ2 = β + γ (4.68)
Para obtener γ se debe calcular l mediante el teorema de pitágoras:
l =
√
r2
1 + r2
4 (4.69)
Utilizando ley de cosenos y despejando γ se obtiene la Ecuación 4.70.
γ = cos−1
[
r2
2 + l2 − r2
3
2r2l
]
(4.70)
Para el ángulo β se tiene:
β = tan−1
(
|r4|
r1
)
(4.71)
Sustituyendo las Ecuaciones 4.70 y 4.71 en la Ecuación 4.68:
θ2 = tan−1
(
|r4|
r1
)
+ cos−1
[
r2
2 + l2 − r2
3
2r2l
]
(4.72)
Para calcular ϕ se aplica ley de cosenos y se despeja:
ϕ = cos−1
[
r2
2 + r2
3 − l2
2r2r3
]
(4.73)
CAPÍTULO 4. FORMULACIÓN DE PROBLEMAS MECATRÓNICOS 37
Finalmente, se puede calcular θ3 con la Ecuación 4.74.
θ3 = θ2 + ϕ+ π (4.74)
b) Si r4 < 0, entonces:
Figura 4.5: Mecanismo MBC para el caso r4 < 0. Adaptada de [18].
Este caso se ilustra en la Figura 4.5 y su análisis matemático es similar al del caso
anterior, se debe calcular el valor del ángulo θ3 con la distinción de que ahora el
angulo θ2 corresponde a la diferencia entre los ángulos γ y β (Ecuación 4.75).
θ2 = γ − β (4.75)
Sustituyendo las Ecuaciones 4.70 y 4.71 en la Ecuación 4.75, se tiene que:
θ2 = cos−1
[
r2
2 + l2 − r2
3
2r2l
]
− tan−1
(
|r4|
r1
)
(4.76)
Ya