Story Transcript
Un algoritmo basado en la colonia arti cial de abejas con búsqueda local para resolver problemas de optimización con restricciones
TESIS DE MAESTRÍA Adán Enrique Aguilar Justo FACULTAD DE FÍSICA E INTELIGENCIA ARTIFICIAL DEPARTAMENTO DE INTELIGENCIA ARTIFICIAL "Maestría en Inteligencia Arti cial" Fecha: 07 de agosto de 2014
Documento maquetado con TEXiS v.1.0+.
Un algoritmo basado en la colonia arti cial de abejas con búsqueda local para resolver problemas de optimización con restricciones
Tesis para obtener el grado de Maestro en Inteligencia Arti cial
Maestría en Inteligencia Arti cial Dirigida por el Doctor
Efrén Mezura Montes
FACULTAD DE FÍSICA E INTELIGENCIA ARTIFICIAL DEPARTAMENTO DE INTELIGENCIA ARTIFICIAL "Maestría en Inteligencia Arti cial" Fecha: 07 de agosto de 2014
Agradecimientos Puedes censurar a un amigo en con anza, pero debes alabarlo delante de los demás. Leonardo Da Vinci
Agradezco a el CONACYT por el apoyo económico brindado durante la realización de este proyecto. Agradezco a la Universidad Veracruzana, esta institución de enorme calidad, que me brindó todo el apoyo durante mi estancia. Agradezco a mi asesor el Dr. Efrén Mezura Montes, todo su apoyo, conocimientos y compromiso con el proyecto que fueron parte fundamental para que éste trabajo llegara a su termino en tiempo y forma. Agradezco al Dr. Carlos Artemio Coello Coello, el haber compartido su conocimiento y sus aportes al trabajo. Agradezco a todos mis compañeros de la Maestría y del Doctorado en Inteligencia Arti cial quienes me aportaron comentarios y criticas valiosas que me ayudaron a mejorar mi trabajo. En especial agradezco a mis padres, que siguen siendo un soporte fundamental en mi vida, quienes me han dado las mejores enseñanzas de la vida.
v
Resumen El rendirse a la ignorancia y llamarla dios siempre ha sido prematuro y sigue siéndolo hoy día. Issac Asimov
El algoritmo de colonia arti cial de abejas (ABC por sus siglas en ingles
Arti cial Bee Colony ) originalmente fue planteado como un algoritmo para resolver problemas de optimización sin restricciones, con el paso del tiempo se le han incorporado mejoras y modi caciones para resolver problemas restringidos. En la presente tesis se describe una propuesta de algoritmo memético basado ABC para problemas de optimización con restricciones. El algoritmo propuesto es probado con dos métodos de búsqueda local, Hooke-Jeeves y Complex, estos son incorporados dentro del ciclo de evolutivo de ABC, particularmente después de la fase de abejas observadoras. Se ha utilizado una métrica basada en la aptitud de la población actual para determinar el momento de aplicar la búsqueda local. El algoritmo propuesto fue probado en los conjuntos de funciones de prueba del congreso de Computación Evolutiva (CEC) de la IEEE en sus versiones del CEC2006 y CEC2010. Los resultados fueron comparados con los obtenidos por dos algoritmos del estado del arte. Los resultados muestran que la propuesta es competitiva resolviendo este tipo de problemas respecto a los del estado del arte.
vii
Índice Agradecimientos
v
Resumen
vii
1. Introducción
1
1.1.
Antecedentes
1.2.
De nición del problema
1.3.
Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . . .
1
. . . . . . . . . . . . . . . . . . . . .
2
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.3.1.
Objetivo general
. . . . . . . . . . . . . . . . . . . . .
3
1.3.2.
Objetivos especí cos . . . . . . . . . . . . . . . . . . .
3
1.4.
Contribución
. . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.5.
Hipótesis
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.6.
Justi cación . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.7.
Organización del documento de tesis
4
. . . . . . . . . . . . . .
2. Inteligencia colectiva y Cómputo memético
5
2.1.
Inteligencia Colectiva (Swarm Intelligence) . . . . . . . . . . .
5
2.2.
Cómputo memético . . . . . . . . . . . . . . . . . . . . . . . .
7
2.3.
Algoritmos meméticos
. . . . . . . . . . . . . . . . . . . . . .
8
2.4.
Diseño de un algoritmo memético . . . . . . . . . . . . . . . .
8
2.4.1.
Algoritmo Lamarckniano . . . . . . . . . . . . . . . . .
9
2.4.2.
Algoritmo Baldwiniano
9
. . . . . . . . . . . . . . . . .
3. Algoritmo de Colonia Arti cial de Abejas
11
3.1.
Modelo Biológico . . . . . . . . . . . . . . . . . . . . . . . . .
11
3.2.
Algoritmo básico
12
3.3.
ABC para problemas con restricciones 3.3.1.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
Propuesta de Karaboga y Akay (2011) . . . . . . . . .
14
4. Algoritmo Propuesto CMABC 4.1.
Buscadores locales 4.1.1.
. . . . . . . . . . . . . . . . . . . . . . . .
Hooke-Jeeves
. . . . . . . . . . . . . . . . . . . . . . .
17 17 18
ix
x
Índice
4.1.2.
Complex . . . . . . . . . . . . . . . . . . . . . . . . . .
19
4.2.
Abeja empleada basada en Evolución Diferencial
. . . . . . .
21
4.3.
ε-constrained
. . . . . . . . . . . . . . . . . . . . . . . . . . .
21
4.4.
Convergencia basada en aptitud . . . . . . . . . . . . . . . . .
22
4.5.
Algoritmo Completo
23
. . . . . . . . . . . . . . . . . . . . . . .
5. Resultados y discusión 5.1.
25
Diseño del experimento . . . . . . . . . . . . . . . . . . . . . .
25
5.1.1.
26
Parámetros de los algoritmos
. . . . . . . . . . . . . .
5.2.
Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
5.3.
Discusión
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
5.3.1.
Resultados CEC2006 . . . . . . . . . . . . . . . . . . .
28
5.3.2.
Resultados CEC2010 . . . . . . . . . . . . . . . . . . .
29
6. Conclusiones y trabajo futuro 6.1.
Conclusiones
6.2.
Trabajo futuro
45
. . . . . . . . . . . . . . . . . . . . . . . . . . .
45
. . . . . . . . . . . . . . . . . . . . . . . . . .
46
I Apéndices
47
A. Apéndice
49
A.1. Pruebas de Wilcoxon . . . . . . . . . . . . . . . . . . . . . . .
B. Apéndice B.1. Grá cas de convergencia CEC2006
49
53 . . . . . . . . . . . . . . .
53
B.2. Grá cas de convergencia CEC2010 dimensión 10
. . . . . . .
66
B.3. Grá cas de convergencia CEC2010 dimensión 30
. . . . . . .
76
C. Apéndice
85
C.1. Detalle de las funciones del CEC2006 . . . . . . . . . . . . . .
85
C.2. Detalle de las funciones del CEC2010 . . . . . . . . . . . . . .
97
Referencias
105
Índice de guras 2.1.
Ejemplos de comportamiento social en la naturaleza
2.2.
Forma de trabajar del algoritmo Lamarckniano, se realiza una búsqueda local en el espacio del fenotipo a una mejora con
2.3.
F 10
G1, se encuentra G1 por G10 . .
esta mejora reemplaza a
6
10
Algoritmo Baldwiniano, realiza la búsqueda local en el espacio de fenotipo, pero
G1
solo toma la nueva aptitud sin ser
reemplazada por el genotipo correspondiente a 3.1.
. . . . .
F 10
. . . . . .
10
Modelo biológico del forrajeo de las abejas 1. Abejas empleadas asignadas a una fuente de alimento, 2. Comunicación de información de las fuentes de alimento por medio de una danza, 3. Abejas observadoras visitan las fuentes de alimento más prometedoras, 4. Las abejas exploradoras buscan nuevas fuentes. 12
3.2.
[19] Porcentaje de publicaciones basadas en enjambre de abejas: HBMO: Honey-bee mating optimization, BCO: Bee colony optimization, BA: BeeAdHoc, ABC: Arti cial Bee Colony
14
5.1.
Grá ca de convergencia de la función G01 . . . . . . . . . . .
30
5.2.
Grá ca de convergencia de la función G04 . . . . . . . . . . .
30
5.3.
Grá ca de convergencia de la función G23 . . . . . . . . . . .
31
5.4.
Grá ca de convergencia de la función C01 dimensión 30
. . .
31
5.5.
Grá ca de convergencia de la función C14 dimensión 30
. . .
32
5.6.
Grá ca de convergencia de la función C15 dimensión 30
. . .
33
B.1. Grá ca de convergencia de la función G01 . . . . . . . . . . .
53
B.2. Grá ca de convergencia de la función G02 . . . . . . . . . . .
54
B.3. Grá ca de convergencia de la función G03 . . . . . . . . . . .
55
B.4. Grá ca de convergencia de la función G04 . . . . . . . . . . .
55
B.5. Grá ca de convergencia de la función G05 . . . . . . . . . . .
56
B.6. Grá ca de convergencia de la función G06 . . . . . . . . . . .
56
B.7. Grá ca de convergencia de la función G07 . . . . . . . . . . .
57
B.8. Grá ca de convergencia de la función G08 . . . . . . . . . . .
57
xi
xii
Índice de figuras
B.9. Grá ca de convergencia de la función G09 . . . . . . . . . . .
58
B.10.Grá ca de convergencia de la función G11 . . . . . . . . . . .
58
B.11.Grá ca de convergencia de la función G02 . . . . . . . . . . .
59
B.12.Grá ca de convergencia de la función G12 . . . . . . . . . . .
59
B.13.Grá ca de convergencia de la función G13 . . . . . . . . . . .
60
B.14.Grá ca de convergencia de la función G14 . . . . . . . . . . .
60
B.15.Grá ca de convergencia de la función G15 . . . . . . . . . . .
61
B.16.Grá ca de convergencia de la función G16 . . . . . . . . . . .
61
B.17.Grá ca de convergencia de la función G17 . . . . . . . . . . .
62
B.18.Grá ca de convergencia de la función G18 . . . . . . . . . . .
63
B.19.Grá ca de convergencia de la función G19 . . . . . . . . . . .
64
B.20.Grá ca de convergencia de la función G23 . . . . . . . . . . .
64
B.21.Grá ca de convergencia de la función G24 . . . . . . . . . . .
65
B.22.Grá ca de convergencia de la función C01
. . . . . . . . . . .
66
B.23.Grá ca de convergencia de la función C02
. . . . . . . . . . .
67
B.24.Grá ca de convergencia de la función C03
. . . . . . . . . . .
67
B.25.Grá ca de convergencia de la función C04
. . . . . . . . . . .
68
B.26.Grá ca de convergencia de la función C05
. . . . . . . . . . .
68
B.27.Grá ca de convergencia de la función C06
. . . . . . . . . . .
69
B.28.Grá ca de convergencia de la función C07
. . . . . . . . . . .
69
B.29.Grá ca de convergencia de la función C08
. . . . . . . . . . .
70
B.30.Grá ca de convergencia de la función C09
. . . . . . . . . . .
70
B.31.Grá ca de convergencia de la función C10
. . . . . . . . . . .
71
B.32.Grá ca de convergencia de la función C11
. . . . . . . . . . .
71
B.33.Grá ca de convergencia de la función C12
. . . . . . . . . . .
72
B.34.Grá ca de convergencia de la función C13
. . . . . . . . . . .
72
B.35.Grá ca de convergencia de la función C14
. . . . . . . . . . .
73
B.36.Grá ca de convergencia de la función C15
. . . . . . . . . . .
73
B.37.Grá ca de convergencia de la función C16
. . . . . . . . . . .
74
B.38.Grá ca de convergencia de la función C17
. . . . . . . . . . .
74
B.39.Grá ca de convergencia de la función C18
. . . . . . . . . . .
75
B.40.Grá ca de convergencia de la función C01
. . . . . . . . . . .
76
B.41.Grá ca de convergencia de la función C02
. . . . . . . . . . .
77
B.42.Grá ca de convergencia de la función C03
. . . . . . . . . . .
77
B.43.Grá ca de convergencia de la función C07
. . . . . . . . . . .
78
B.44.Grá ca de convergencia de la función C08
. . . . . . . . . . .
78
B.45.Grá ca de convergencia de la función C09
. . . . . . . . . . .
79
B.46.Grá ca de convergencia de la función C10
. . . . . . . . . . .
79
B.47.Grá ca de convergencia de la función C12
. . . . . . . . . . .
80
B.48.Grá ca de convergencia de la función C13
. . . . . . . . . . .
80
B.49.Grá ca de convergencia de la función C14
. . . . . . . . . . .
81
Índice de figuras
xiii
B.50.Grá ca de convergencia de la función C15
. . . . . . . . . . .
81
B.51.Grá ca de convergencia de la función C16
. . . . . . . . . . .
82
B.52.Grá ca de convergencia de la función C17
. . . . . . . . . . .
82
B.53.Grá ca de convergencia de la función C18
. . . . . . . . . . .
83
Índice de Tablas 5.1.
Parámetros para los algoritmos: SN es el número de fuentes de alimento, MR el Modi cation Ratio, MCN el máximo de ciclos, LIMITE máximo de ciclos que una fuente puede permanecer sin mejora, ERROR I y ERROR F son la tolerancia inicial y nal para restricciones de igualdad.
D es la dimensión
del problema. . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.
Parámetros el algoritmo propuesto y los buscadores locales. Hooke-Jeeves: reducción,
∆
xión,
δ
vector de incrementos. Complex:
α
factor de re e-
SN Ratio, G
distancia mínima entre las soluciones. MC-ABC:
número de fuentes de alimento,
MR
Modi cation
ciclo para considerar convergencia no factible.
TC
α factor de ϕ diferencia
distancia mínima para terminar,
mínima entre la aptitud de las soluciones,
ciclo donde
ε
es mínimo,
CP
ε-constraint: , P
factor de reducción de
potencia para la suma de restricciones. . . . . . . . . . . . . .
5.3.
26
27
Características de las funciones del conjunto de prueba del CEC2006.
D
número de variables del problema,
ρ
porcentaje
LI y N I restricciones de deLE y N E son el número de lineales y no lineales. a es el número
aproximado de la zona factible,
sigualdad lineales y no lineales, restricciones de igualdad
de restricciones activas . . . . . . . . . . . . . . . . . . . . . .
5.4.
Límites y valor óptimo de las funciones del conjunto de prueba del CEC2006
5.5.
34
. . . . . . . . . . . . . . . . . . . . . . . . . . .
35
Características de las funciones del conjunto de prueba del CEC2010.
D
es el número de variables del problema, E es el
número de restricciones de igualdad, I el número de restricciones de desigualdad.
ρ = |F |/|S|
es el porcentaje estimado
entre la región factible y el espacio de búsqueda . . . . . . . .
36
xv
xvi
5.6.
Índice de tablas
Estadísticas del conjunto de pruebas CEC2006: funciones G01 a G08. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.7.
37
Estadísticas del conjunto de pruebas CEC2006: funciones G09 a G16. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.8.
38
Estadísticas del conjunto de pruebas CEC2006: funciones G17 a G24. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.9.
39
Estadísticas del conjunto de pruebas CEC2010 dimensión 10: funciones C01 a C09. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa.
. . . . . . . . . . . . . . . . . .
40
5.10. Estadísticas del conjunto de pruebas CEC2010 dimensión 10: funciones C10 a C18. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa.
. . . . . . . . . . . . . . . . . .
41
5.11. Estadísticas del conjunto de pruebas CEC2010 dimensión 30: funciones C01 a C09. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa.
. . . . . . . . . . . . . . . . . .
42
5.12. Estadisticas del conjunto de pruebas CEC2010 dimensión 30: funciones C10 a C18. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa.
. . . . . . . . . . . . . . . . . .
43
A.1. Prueba de Wilcoxon para el CEC2006. El número 1 indica que hay diferencia signi cativa, el 0 que no la hay y - es que no hubo soluciones factibles. A0 es MABC-SF, A1 es MABC, A2 es CMABC-HJ, A3 es CMABC-COM
. . . . . . . . . . . . .
50
Índice de tablas
xvii
A.2. Prueba de Wilcoxon para el CEC2010 dimensión 10. El número 1 indica que hay diferencia signi cativa, el 0 que no la hay y - es que no hubo soluciones factibles. A0 es MABC-SF, A1 es MABC, A2 es CMABC-HJ, A3 es CMABC-COM
. . . . .
51
A.3. Prueba de Wilcoxon para el CEC2010 dimensión 30. El número 1 indica que hay diferencia signi cativa, el 0 que no la hay y - es que no hubo soluciones factibles. A0 es MABC-SF, A1 es MABC, A2 es CMABC-HJ-T, A3 es CMABC C.1. C.2.
Data set for test problem g19 Data set for test problem g20
. . . . . . .
52
. . . . . . . . . . . . . . . . . . .
94
. . . . . . . . . . . . . . . . . . .
95
Capítulo 1
Introducción 1.1. Antecedentes Dentro de los algoritmos inspirados en el naturaleza para resolver problemas de optimización, podemos encontrar aquéllos basados en inteligencia colectiva (Swarm Intelligence ) que son aquellos que se enfocan en el comportamiento colectivo, en el control descentralizado y en la auto-organización [20]. Dentro de estos algoritmos podemos encontrar a la colonia de hormigas, bancos de peces, parvadas de pájaros y la colonia arti cial de abejas (ABC por sus siglas en inglés, Arti cial Bee Colony [18]), en el cual estará centrado este documento. ABC fue propuesto en 2005 por Karaboga [18] y está basado en el comportamiento de forrajeo de las abejas melíferas. Este algoritmo fue pensado para resolver problemas de optimización sin restricciones, sin embargo, también se ha adaptado para resolver problemas con restricciones y problemas de combinatoria. Karaboga y Akay (2011)[17],[2], proponen una de las primeras versiones de ABC para resolver problemas de optimización numérica con restricciones, cambiando la forma de trabajar del operador básico del ABC añadiendo una forma de cruza, mientras que para el manejo de restricciones proponen el usó las reglas de Deb [8]. Mezura-Montes et al. en [24], proponen un algoritmo basado en ABC, que promueve la exploración del espacio de búsqueda, además de utilizar el método de tolerancia dinámica de restricciones usada en las estrategias evolutivas y aplicar un buscador local, que es utilizado cada vez que se alcanza un porcentaje de evaluaciones predeterminado. Bravejic et al. [6],[7], no consideran cada ejecución del algoritmo de manera independiente, utilizando la mejor solución de la ejecución anterior en la población inicial de la siguiente, prueban su algoritmo en un conjunto de funciones de ingeniería. Mezura-Montes et al. [23] presentan un algoritmo que explora la vecindad 1
2
Capítulo 1. Introducción
de la mejor solución, además de utilizar el método de
-constraint
para el
manejo de restricciones. En cuanto a algoritmos que combinen diferentes técnicas de búsqueda junto con ABC podemos encontrar a Shi et al. [31] quienes proponen un algoritmo híbrido basado en ABC y optimización de partículas (PSO), el cual prueban en funciones de optimización numérica sin restricciones. Fei Kang et al. [16] combinan ABC y el método de Hooke-Jeeves como buscador local para resolver problemas de optimización numérica irrestricta. Fister et al. [11] desarrollaron un algoritmo basado en ABC que combinan con dos buscadores locales Nelder-Mead y caminata aleatoria con dirección de explotación. Este algoritmo fue aplicado al conjunto de funciones de optimización global continua de gran escala del congreso de Computación Evolutiva de la IEEE CEC2012. Se puede observar que la tendencia del uso de buscadores locales en ABC para optimización numérica con restricciones es escasa. Además no existen estudios sobre el efecto de este tipo de algoritmos.
1.2. De nición del problema Uno de los problemas que ha atraído un alto interés en las últimas décadas ha sido la optimización numérica, en este ámbito los algoritmos inspirados en la naturaleza han jugado un papel importante obteniendo resultados favorables. Dentro de estos problemas encontramos aquellos de optimización numérica con restricciones (Ecuación 1.1), el cual se de ne sin pérdida de generalidad, como encontrar un vector ~ x que minimice una función objetivo f (~x) sujeta a restricciones de igualdad (hj ) y/o desigualdad (gj ), donde li y ui son los límites inferior y superior para cada una de las variables respectivamente, m es el número total de restricciones, y q es el número de restricciones de desigualdad así m − q es el número de restricciones de igualdad. Este tipo de problemas serán los resueltos en este trabajo.
minimizar
f (~x), ~x = (x1 , . . . , xn ) ∈ Rn li ≤ xi ≤ ui ,
sujeto a :
i = 1, . . . , n
gj (~x) ≤ 0,
para
j = 1, . . . , q
hj (~x) = 0,
para
j = q + 1, . . . , m (1.1)
1.3. Objetivos
3
1.3. Objetivos 1.3.1. Objetivo general Desarrollar un algoritmo basado en MABC (Modi ed Arti cial Bee Colony [17]) e incorporarle un buscador local que logre competir en resultados con los algoritmos del estado del arte.
1.3.2. Objetivos especí cos Implementar el algoritmo MABC(Modi ed Arti cial Bee)[17]. Comparar el desempeño de los métodos Hooke-Jevees y Complex como buscadores locales. Implementar el algoritmo MABC incorporando los buscadores locales. Diseñar experimentos, probar y analizar resultados.
1.4. Contribución Un estudio comparativo de dos buscadores locales sobre MABC. Un algoritmo memético basado en MABC para resolver problemas de optimización con restricciones.
1.5. Hipótesis La combinación del algoritmo MABC como buscador global y algoritmos de búsqueda local logran obtener resultados competitivos con algoritmos del estado del arte.
1.6. Justi cación El problema de optimización numérica con restricciones ha sido atacado por diferentes algoritmos basados en la naturaleza, entre estos ABC que es un algoritmo joven y que ha demostrado ser competitivo contra algoritmos del estado del arte, sin embargo poco se ha explorado su hibridación con algoritmos de búsqueda local. Karaboga y Akay (2011)[17],[2], propusieron modi caciones al algoritmo original de ABC para contender con las restricciones, básicamente integran manejo de restricciones al algoritmo. Mezura-Montes et al. [23] propusieron modi caciones en la selección de fuentes de alimento para las abejas observadoras, aplicaron la técnica conocida como
ε-contrained para las restricciones
4
Capítulo 1. Introducción
y buscaron sesgar la generación de soluciones de las abejas exploradoras hacia la vecindad de la mejor solución encontrada. Mientras que Bravejic et al. [6],[7], utilizaron el algoritmo para resolver problemas de ingeniería y consideraron las ejecuciones del algoritmo dependientes, usando la mejor solución encontrada para la siguiente ejecución, además de buscar mayor diversidad al sustituir a las fuentes de alimento no factibles y las abandonadas factibles por soluciones generadas aleatoriamente. Como podemos ver, la revisión de la literatura especializada sugiere que los esfuerzos se han centrado en el manejo de restricciones y en los operadores de las abejas, mas no así en la incorporación de buscadores locales que coadyuven a la mejora de las soluciones que va generando el ABC.
1.7. Organización del documento de tesis El resto del documento está organizado de la siguiente manera: Capítulo 2. Inteligencia Colectiva y Cómputo Memético. En este capítulo se presentan los antecedentes históricos de los algoritmos de inteligencia colectiva así como la de nición del cómputo memético y algoritmos meméticos que son conceptos claves en la hibridación de buscadores globales con buscadores locales. Capítulo 3. Colonia Arti cial de Abejas (ABC). Aquí se presenta de manera extensa el funcionamiento del algoritmo ABC y MABC que son la base de este trabajo de tesis. Capítulo 4. Propuesta de algoritmo. En este capítulo se describe la propuesta de algoritmo memético utilizando MABC y el buscador local, además del funcionamiento de los algoritmos locales utilizados. Capítulo 5. Resultados y discusión. En este capítulo se muestran y discuten los resultados obtenidos por el algoritmo propuesto y se comparan con algoritmos del estado del arte. Capítulo 6. Conclusiones y trabajo futuro. En este capítulo se presentan las conclusiones a partir de los resultados obtenidos y el trabajo futuro que se deriva de esta tesis.
Capítulo 2
Inteligencia colectiva y Cómputo memético En este capítulo se hablará de dos términos que están relacionados con el trabajo que se presenta, por un lado tenemos la inteligencia colectiva de la cual forma parte el algoritmo ABC y Cómputo Memético un término relativamente nuevo, pero que explica muy bien el tipo de algoritmo que se propone en este trabajo.
2.1. Inteligencia Colectiva (Swarm Intelligence) En la naturaleza es muy común encontrar animales que mantienen grupos de individuos, en algunos casos éstos tienen un líder (conocido como el macho/hembra alfa), y el comportamiento de los individuos es estrictamente jerárquico. Aún más interesantes son aquéllos en los que no se logra determinar un líder del grupo. Estas especies tienen un comportamiento de auto-organización, como lo podemos ver en las parvadas, o en los cardúmenes (bancos de peces) como podemos ver en la Fig. 2.1. Aquí los individuos desconocen el estado del grupo general, sin embargo al transmitirse información logran agruparse [10]. La inteligencia colectiva también puede ser referida como Swarm Inte-
lligence . Formalmente Swarm se puede de nir como un grupo de agentes (comúnmente móviles) que se comunican con otros de manera directa o indirecta, para actuar sobre su entorno local [10]. La interacción entre los agentes da como resultado estrategias para resolver problemas de manera distribuida. El estudio de numerosos comportamientos de animales y sociedades ha dado como resultado el modelado de diferentes algoritmos de inteligencia colectiva. Entre estos comportamientos biológicos que han inspirado a los modelos computacionales encontramos, hormigas, termitas, abejas, arañas, cardúmenes, parvadas, entre otros. 5
6
Capítulo 2. Inteligencia colectiva y Cómputo memético
(a) Colonia de hormigas
(b) Parvada
(c) Cardumen
Figura 2.1: Ejemplos de comportamiento social en la naturaleza
El objetivo de los algoritmos de inteligencia colectiva es modelar los comportamientos de los agentes y sus interacciones con el ambiente y sus vecinos, con la nalidad de obtener un comportamiento más complejo que pueda usarse para resolver problemas [10]. Un algoritmo de inteligencia colectiva está conformado por agentes que interaccionan con su medio ambiente y de acuerdo a esta interacción comunican a los demás información que les puede ser de utilidad, cada agente decidirá su comportamiento con base en la información de sus compañeros y el conocimiento que tenga en ese momento. De acuerdo a esto podemos de nir la estructura general de un algoritmo de inteligencia colectiva como se muestra en el Algoritmo 1
Algoritmo 1 Algoritmo general de la inteligencia colectiva 1: Inicializar la población de agentes 2: 3:
loop
Generar una nueva población por medio de la interacción de cada agente con su medio, de acuerdo al comportamiento individual
4:
Compartir la información con el resto de los agentes o con aquéllos que sean seleccionados de acuerdo a un comportamiento de comunicación
5:
Generar una nueva población con la información que ha obtenido de los otros agentes y de la información de su medio ambiente.
6:
end loop
7: Retornar la información que contenga el mejor agente.
2.2. Cómputo memético
7
2.2. Cómputo memético Para hablar de cómputo memético primero debemos de nir la palabra meme, que fue acuñada por Dawkins en 1976 en su libro llamado The Sel sh Gene y lo de nió como la unidad básica de transmisión cultural o imitación. Dada esta de nición, algunos ejemplos de meme son: melodías, frases, tendencias, etc. Hoy en día la palabra meme es usada como análogo de la palabra gen que es más adecuada en la idea de la computación inteligente. Una de nición que podemos encontrar para el cómputo memético es la siguiente:
La computación memética es un paradigma que usa la noción de memes como unidades de información, codi cada en representaciones computacionales para resolver un problema [29] De acuerdo a la de nición anterior podemos decir que el cómputo memético busca combinar dos o más técnicas de solución de problemas, para así poder obtener mejores resultados. Un esquema básico de un algoritmo memético se muestra en el Algoritmo 2, la inicialización de la población es la responsable de producir el conjunto inicial de individuos, comúnmente en los algoritmos evolutivos tradicionales se inicializa con soluciones aleatorias, pero en los algoritmos meméticos es recomendable iniciar con buenas soluciones aplicando heurísticas a los individuos generados. Para generar una nueva población se emplea la cooperación y mejora de individuos, que son la parte central de estos algoritmos. Dentro de este proceso se puede emplear más de un operador de selección y recombinación. La competencia es un medio de reemplazo para construir la población del siguiente ciclo a partir de la población actual y la generada.
Algoritmo 2 Algoritmo Memético básico 1: Inicializar la población 2:
loop
3:
Generar nueva población por medio de la cooperación
4:
Generar nueva población por medio de la mejora
5:
Combinar las poblaciones anteriores por medio de una competencia
6: 7: 8: 9:
if
la población converge
then
Reiniciar la población
end if end loop
10: Regresar el mejor individuo
Algunas de las áreas de investigación donde se han aplicado algoritmos meméticos se enumeran a continuación [26]:
1. Problemas NP de optimización combinatoria
8
Capítulo 2. Inteligencia colectiva y Cómputo memético
2. Aprendizaje automático y robótica 3. Ingeniería y Electrónica 4. Optimización de problemas moleculares
2.3. Algoritmos meméticos Uno de los problemas que competen a la computación es resolver problemas de optimización. Dentro de esta área de estudio se han derivado múltiples estrategias, las cuales se denominan meta-heurísticas, entre ellas destacan los algoritmos evolutivos que se encuentran muy relacionados con los algoritmos meméticos. Los algoritmos meméticos son una rama de estudio que pertenece a la computación memética, y se de ne a continuación:
Un algoritmo memético es una meta-heurística basada en población compuesta por un marco evolutivo y un conjunto de algoritmos de búsqueda local que son utilizados dentro del ciclo de evolución [27] Aunque esta de nición puede llevarnos a la conclusión de que únicamente la combinación de un algoritmo evolutivo y un buscador local es un algoritmo memético, esto no es cierto, puesto que este tipo de combinaciones conforman sólo un subconjunto de los algoritmo meméticos. Dada esta ambigüedad, es complicado encontrar en la literatura algoritmos meméticos como tales, y es más común encontrarlos como algoritmos híbridos, algoritmos Lamarcknianos o algoritmos Baldwinianos.
2.4. Diseño de un algoritmo memético Incluir un buscador local a un algoritmo bio-inspirado no necesariamente implica que éste mejorará su rendimiento, el diseño de estos algoritmo puede guiarse respondiendo las siguientes preguntas [21]: ¾Qué método de búsqueda local debe ser usado? ¾Cómo es el paisaje de aptitud que se debe explorar? ¾Dónde y cuándo debe aplicarse el buscador local dentro del ciclo de evolución? ¾Qué modelo de mejora debe ser elegido Baldwiniano o Lamarckniano? ¾Cómo se puede mejorar la integración de los operadores del algoritmo evolutivo con el buscador local? ¾Qué individuos de la población deben ser mejorados por la búsqueda local y cómo se seleccionarán?
2.4. Diseño de un algoritmo memético
9
Para dar respuesta a estas preguntas se requiere que conozcamos algunos detalles del problema que estamos atacando, como su dimensión, el tipo de problema (optimización combinatoria o numérica), la forma del paisaje de aptitud, etc. Saber en qué momento dentro del ciclo evolutivo es conveniente aplicar el buscador local, dependerá del funcionamiento del algoritmo evolutivo elegido y del efecto que se espera del buscador local en la búsqueda global. Incluso se puede pensar en modi car los operadores del algoritmo evolutivo para que éstos incluyan la búsqueda local como parte de su proceso. A continuación se describen los algoritmos Lamarckniano y Baldwiniano.
2.4.1. Algoritmo Lamarckniano En la actualidad la teoría de evolución de Lamarck se encuentra rechazada. Esta teoría expone que las características (fenotípicas) que un individuo adquiere durante su tiempo de vida, son transmitidas a su codi cación genética (genotipo) y heredadas a los individuos de la siguiente generación. En el campo de la computación estas transformaciones de fenotipo a genotipo y viceversa son muy simples de realizar y crean una poderosa herramienta en el campo de la optimización. La evolución de Lamarck fue combinada con algoritmos genéticos por Hart y Belew en 1996 [12], comúnmente la función de Lamarck toma la forma de un buscador local y trabaja sobre el espacio de búsqueda fenotípico intentando mejorar la aptitud del individuo como se puede ver en la gura 2.2. Un algoritmo básico de Lamarck se muestra en el Algoritmo 3
Algoritmo 3 Algoritmo Lamarck 1: Inicializar la población 2:
loop
3:
Selección
4:
Reproducción
5:
Mutación
6:
Reemplazo
7: 8:
Evolución Lamarck (Buscador local)
end loop
2.4.2. Algoritmo Baldwiniano En 1896 en el artículo A new Factor in evolution de J. Mark Baldwin [4] propone su teoría de evolución, donde expone de manera general que los individuos pueden mejorar durante su tiempo de vida. Sin embargo estas características adquiridas no se transmiten a su genotipo. Un algoritmo que implementa una estrategia Baldwin, utiliza un buscador local para mejorar
10
Capítulo 2. Inteligencia colectiva y Cómputo memético
Figura 2.2: Forma de trabajar del algoritmo Lamarckniano, se realiza una búsqueda local en el espacio del fenotipo a
F 10
esta mejora reemplaza a
G1
por
G1,
se encuentra una mejora con
G10
su aptitud, los valores obtenidos en esos cambios no son transmitidos a su genotipo, pero su aptitud adquirida si se mantiene. Hinton y Nowlan (1987) [13] señalan que este algoritmo incrementa la búsqueda dentro de los óptimos locales, incrementando la posibilidad de encontrar el óptimo global. El esquema básico de un algoritmo Baldwin es similar al presentado en el algoritmo 3, cambiando la línea 7 por el buscador local Baldwin. De acuerdo a las pruebas realizadas en [34], la evolución Lamarckniana tiende a converger a óptimos locales mientras, la evolución Baldwin converge a óptimos globales sin embargo esta última es más lenta.
Figura 2.3: Algoritmo Baldwiniano, realiza la búsqueda local en el espacio de fenotipo, pero
G1
solo toma la nueva aptitud sin ser reemplazada por el
genotipo correspondiente a
F 10
Capítulo 3
Algoritmo de Colonia Arti cial de Abejas El algoritmo de colonia arti cial de abejas (ABC) fue propuesto por Dervis Karaboga en 2005 [18] está basado en el comportamiento de forrajeo de las abejas, y diseñado originalmente para problemas de optimización numérica sin restricciones, aunque puede ser utilizado para resolver problemas de combinatoria.
3.1. Modelo Biológico El proceso de búsqueda de néctar por parte de las abejas es un proceso de optimización, y el comportamiento de éstas se modeló como una heurística de optimización basada en el modelo biológico que consta de los siguientes elementos: 1. Fuentes de alimento: aunque el valor de una fuente de alimento depende de muchos factores, es resumido en un valor numérico que indica su potencial. 2. Abejas recolectoras empleadas: estas abejas explotan una fuente de alimento, también son las encargadas de comunicar su ubicación y rentabilidad a las abejas observadoras. 3. Abejas recolectoras desempleadas: este tipo de abejas se encuentran buscando fuentes de alimento para explotar. Se dividen en dos tipos las exploradoras que se encargan de buscar nuevas fuentes de alimento y las observadoras que esperan en la colmena para elegir alguna de las fuentes de alimento que se encuentran en un proceso de explotación por las abejas empleadas. Estos tres elementos básicos del comportamiento de forrajeo interaccionan de la siguiente forma: las abejas empleadas comunican la información de 11
12
Capítulo 3. Algoritmo de Colonia Arti cial de Abejas
la fuente de alimento que están explotando a las abejas observadoras por medio de una danza, donde el ángulo respecto al sol indica la dirección de la fuente y un zigzagueo indica la distancia, las danzas con mayor duración re eren a fuentes de alimento más rentables y más probables a ser elegidas por las abejas observadoras. [18] Una vez que las fuentes de alimento han sido agotadas (ya sea por las abejas empleadas u observadoras) son abandonadas y reemplazadas por nuevas fuentes encontradas por las abejas exploradoras. En la Figura 3.1 se muestra grá camente el comportamiento del forrajeo de las abejas.
Figura 3.1: Modelo biológico del forrajeo de las abejas 1. Abejas empleadas asignadas a una fuente de alimento, 2. Comunicación de información de las fuentes de alimento por medio de una danza, 3. Abejas observadoras visitan las fuentes de alimento más prometedoras, 4. Las abejas exploradoras buscan nuevas fuentes.
3.2. Algoritmo básico Las fuentes de alimento representan a cada solución como un vector Ddimensional, y las abejas a los operadores de variación ya que cuando ellas visitan las fuentes de alimento, calcularán una nueva solución do a la ecuación 3.1 donde
~xi,g
~vi,g
de acuer-
representa la fuente de alimento donde se
~xk,g es una fuente de alimento seleccio~xi,g , g es el ciclo actual y φ es un número
encuentra la abeja en ese momento, nada aleatoriamente y diferente de
[−1, 1], ~vi,g denota posición actual ~ xi,g .
real aleatorio entre respecto a la
la ubicación de la nueva solución con
~vi,g = ~xi,g + φ(~xi,g − ~xk,g )
(3.1)
3.2. Algoritmo básico
13
Las abejas observadoras seleccionan las fuentes de alimento de acuerdo a una probabilidad
pi
asociada a la fuente de alimento, la cual es calculada de la
siguiente manera (ver Ecuación 3.2):
f iti pi = PSN n=1 f itn donde
f iti
(3.2)
es el valor de aptitud de la solución, y este valor es proporcional
a la cantidad de néctar que tiene la solución
i.
Los parámetros del algoritmo son los siguientes:
1. SN : es el número de fuentes de alimento
2. MCN : el número total de iteraciones que ejecutará ABC
3. Límite (limit): número de ciclos que será conservada una solución sin mejora antes de ser reemplazada por una nueva solución generada por una abeja exploradora.
En el Algoritmo 4 se muestra el seudocódigo.
Algoritmo 4 ABC 1: Inicializar la población de soluciones
~xi,0 , i = 1, ..., SN
Evaluar la pobla-
ción 2: 3:
for g = 1 hasta M CN do Generar nuevas soluciones
~vi,g
para las abejas empleadas usando la
Ecuación 3.1 y evaluarlas
~xi,g
y
~vi,g
4:
Conservar la mejor solución entre
5:
Seleccionar las soluciones que serán visitadas por las abejas observadoras usando la Ecuación 3.2
6:
Generar nuevas soluciones
~vi,g
para las abejas observadoras usando la
Ecuación 3.1 y evaluarlas
~xi,g
y
~vi,g
7:
Conservar la mejor solución entre
8:
Veri car si existen fuentes abandonadas (si ya se alcanzó el Límite) y reemplazarlas por soluciones generadas aleatoriamente por las abejas exploradoras.
9: 10:
Conservar la mejor solución encontrada hasta el momento
end for
11: Retornar la mejor solución
En la siguiente sección se muestran algunas modi caciones del algoritmo general para la resolución de problemas con restricciones.
14
Capítulo 3. Algoritmo de Colonia Arti cial de Abejas
3.3. ABC para problemas con restricciones Desde que fue propuesto el algoritmo ABC en 2005, ha habido un crecimiento en el estudio su comportamiento en diferentes ámbitos, de acuerdo a la recopilación hecha por Karaboga en 2012 [19], el 54 % (Figura 3.2) de las publicaciones referentes a algoritmos basados en enjambres de abejas se re eren al algoritmo ABC entre éstos se encuentran aquellos que han sido utilizados para resolver problemas con restricciones.
Figura 3.2: [19] Porcentaje de publicaciones basadas en enjambre de abejas: HBMO: Honey-bee mating optimization, BCO: Bee colony optimization, BA: BeeAdHoc, ABC: Arti cial Bee Colony
3.3.1. Propuesta de Karaboga y Akay (2011) Karaboga y Akay (2011)[17][2], proponen una serie de modi caciones a su algoritmo original de ABC para manejar las restricciones, agregando dos parámetros: Modi cation Rate (MR) y el Scout Production Period (SPP). El parámetro MR actúa en el operador de las abejas, produciendo así una solución nueva
~vi
que contiene parte del vector original
~xi
y parte de la
solución generada por la Ecuación 3.1, el operador modi cado se muestra en la Ecuación 3.3.
(
vi,g =
~xi,g + φ(~xi,g − ~xk,g ) xi,g
si
randj [0; 1] < M R
en caso contrario
(3.3)
El SPP se aplica para controlar la frecuencia de la fase de las abejas exploradoras de esta manera la producción de soluciones nuevas mantiene la diversidad en la población. Tal proceso es detallado en el Algoritmo 5, donde
f allos
es un contador que tiene cada solución y cuanti ca las veces que no
3.3. ABC para problemas con restricciones
15
ha mejorado. Como técnica de manejo de restricciones utilizan las reglas de Deb [8] que se describen a continuación: 1. Dadas dos soluciones factibles, se escogerá aquella que tenga mejor valor de aptitud 2. Dadas dos soluciones una factible y otra no factible se seleccionará la solución factible 3. Dadas dos soluciones no factibles se mantendrá aquella que menos viole las restricciones
Algoritmo 5 Fase de las abejas exploradoras 1: if MCN mod SPP = 0 then 2: if max(fallos)>limite then 3: 4: 5:
Reemplazar
end if end if
~xi
con una nueva solución aleatoria.
La selección de fuentes de alimento por parte de las abejas observadoras se realiza por medio de una técnica de selección proporcional, popular en los algoritmos genéticos y conocida como ruleta el cálculo de la probabilidad de selección de cada fuente de alimento se muestra en el algoritmo 6
Algoritmo 6 Cálculo de probailidades de cada fuente de alimento 1: for i = 0 a SN do 2:
Calcular la probabilidad utilizando el valor de aptitud o la suma de violación de restricciones.
aptitudi 0.5 + ΣSN aptitud ∗ 0.5 j j=1 pi = violaci´ oni 1 − ΣSN violaci´on ∗ 0.5 j
j=1
Si la solución es factible Si la solución no es factible (3.4)
donde
violaci´ on
es la sumatoria de violación de restricciones de cada
fuente de alimento, y
aptitud
se determina con base en los valores de
la función objetivo a optimizar, como se detalla en la Ecuación 3.5
(
aptitudi = Donde
3:
end for
fi
1/(1 + fi ) sifi ≤ 0 1 + abs(fi ) sifi < 0
(3.5)
es el valor de la función objetivo de cada fuente de alimento.
Capítulo 4
Algoritmo Propuesto CMABC En este capítulo se describirá el algoritmo memético que se propuso e implementó al cual hemos llamado CMABC(Constraint Memetic Arti cial Bee Colony), usando como base el algoritmo de la propuesta de Karaboga y Akay [17][2]. Para el diseño del algoritmo se siguieron algunas de las preguntas guía descritas en la sección 2.4. Se seleccionaron dos buscadores locales tomados del área de programación matemática, Hooke-Jeeves y Complex, dado que el problema a resolver es la optimización numérica con restricciones, el funcionamiento de estos métodos se describe en la siguiente sección. La búsqueda local se aplica después de la fase de las abejas empleadas y se aplica a la mejor solución. Se implementó una métrica de convergencia basada en la aptitud [28][11] para determinar cuándo aplicar la búsqueda local y el reemplazo seleccionado fue de tipo Lamarckniano. El detalle del algoritmo se puede ver en el Algoritmo 11. Con la intención de mejorar el desempeño del algoritmo se cambió el operador de las abejas empleadas por uno basado en el comportamiento de la evolución diferencial , y se reemplazaron las reglas de Deb [8] por la técnica
-contrained
[33] para manejar las restricciones. De acuerdo a las pruebas
realizadas por Alizadegan en [3] variar la relación entre el número de abejas empleadas y observadoras puede ayudar a mejorar el comportamiento del algoritmo esta propuesta fue considera también dentro del algoritmo nal.
4.1. Buscadores locales En esta sección se describirán los métodos de búsqueda local que se utilizaron en el algoritmo. Estos métodos son parte de la optimización directa los cuales no necesitan conocer el gradiente de la función. El método de Hooke-Jeeves también conocido como búsqueda en patrón (Pattern search) fue desarrollado por Hooke y Jeeves [14] en 1961, mientras que el método de Complex fue desarrollado por M.J. Box [5] en 1965, basado en el método 17
18
Capítulo 4. Algoritmo Propuesto CMABC
Simplex pero considerando restricciones.
4.1.1. Hooke-Jeeves El método de Hooke-Jeeves consiste en una serie de movimientos de exploración, y si éstos han sido satisfactorios se realiza el paso de patrón [9]. El movimiento de exploración revisa la vecindad de la solución actual para encontrar una mejor. Con estas dos soluciones se realiza un movimiento de patrón para encontrar una dirección de búsqueda que prometa mejoras.
4.1.1.1. Movimiento de exploración ~xc , es modi cada en una de sus dimensiones por ∆ (cuyos valores van decrementando con el paso
Dada una solución inicial un vector de perturbación
del tiempo y el valor recomendado es de 0.5) tanto en su dirección positiva como negativa, siempre se recuerda la mejor solución encontrada. Se inicia
i=1
y
~x = ~xc .
1. Calcular las funciones
f = f (~x), f + = f (~xi + ∆i )
y
sumando y restando a la dimensión correspondiente 2. Se selecciona aquel que mejore el valor de la función.
~x
sera igual al que corresponda
f − = f (~xi − ∆i ), el valor de ∆i
fmin = min(f, f + , f − ).
fmin .
3. Si no se han recorrido todas las dimensiones, repetimos desde el paso 1, si ya se recorrieron ir al paso 4. 4. Si
~xc 6= ~x,
no ha
entonces el movimiento de exploración ha tenido
fallado.
éxito, si
4.1.1.2. Movimiento de patrón Una nueva solución es encontrada desde la solución actual a la mejor solución anterior
~x(k−1)
y la solución base
~x(k)
~xc , en dirección
como se muestra
en la Ecuación 4.1
~x(k+1) = ~x(k) + (~x(k) − ~x(k−1) )
(4.1)
El algoritmo completo se describe en Algoritmo 7. Este método no considera las restricciones, de ahí que para el algoritmo propuesto se selecciona la mejor solución con base en las reglas de Deb [8]. Por otro lado, para controlar que no haga evaluaciones excesivas hasta reducir
∆,
se agregó una contador de ciclos permitidos, cuyo limite original es 2,
mientras mejore después de esos dos ciclos se le permite al algoritmo realizar una ejecución más de la búsqueda.
4.1. Buscadores locales
19
Algoritmo 7 Hooke-Jeeves 1: Seleccionar un punto inicial
factor de reducción
2: 3: 4:
while
||∆|| >
do
α
~x0 ,
inicializar el vector de incrementos
y un valor de término
Realizar un movimiento de exploración
if
el movimiento de exploración es satisfactorio
~x(k+1)
then
6:
= ~x k =k+1
7:
Realizar un movimiento de patrón usando la Ecuación4.1
5:
8: 9: 10: 11:
∆,
else
Dividir el vector de incrementos entre el factor de reducción
end if end while
∆/α
4.1.2. Complex El método Complex [1] está basado en el método Simplex [9] sin embargo a diferencia de éste, Complex toma en cuenta las restricciones al momento de minimizar. Complex trabaja de la siguiente forma:
1. Primero generar el Complex inicial: A partir de una solución factible
~xf
se crearan
K
soluciones de acuerdo a la Ecuación 4.2
~xk = ~l + (~u − ~l) ∗ rand
(4.2)
Dónde ~ ly y
~u son los limites inferiores y superiores de la función objetivo rand es un número aleatorio entre 0 y 1. Cada vez que se genere una
nueva solución será evaluada y si no es factible, la solución se retrae hacia el centroide del Complex aplicando la Ecuación 4.3. Este proceso se repite hasta que
~xk
sea factible, entonces se agrega esta solución al
Complex y se continua generando soluciones hasta que se completen los
K
requeridos.
~xk = ~xk + (1/2) ∗ (x − ~xk ) P x = ( ki x~i )/K
(4.3)
2. A continuación se realiza el ciclo de mejora, el cual se detendrá cuando se ha alcanzado un límite de distancia
δ
entre las soluciones del
complex. También se debe inicializar un factor de re exión
α.
En cada iteración se selecciona la solución con el peor valor de aptitud del Complex
~xw ,
una vez seleccionada se crea un nuevo vector usando
la Ecuación 4.4
~xn = x + α ∗ (x − ~xw )
(4.4)
20
Capítulo 4. Algoritmo Propuesto CMABC
Si
~xn
es mejor que
~xw ,
entonces lo reemplaza en el Complex, si no
es mejorada se continua creando nuevas soluciones pero tomando como base al actual
~xn .
El algoritmo termina cuando la distancia en el
δ
Complex es menor o igual a
aptitud ha alcanzado un limite
Los valores recomendados para problema,
δ = 1e − 5, ϕ = 1e − 5
o cuando la diferencia en la función de
ϕ.
K
es
d+1
donde
d
es la dimensión del
y para el factor de re exión
α = 1.3
de
acuerdo a Box [5]. Este método asume que se inicia con un punto factible, y que la zona factible es cóncava, requerimientos que no se pueden asegurar al momento de agregar el método al algoritmo ABC. Para poder mejorar soluciones no factibles se le incluyeron las reglas de Deb, cuando se crea el Complex se le permite mejorar sólo durante 3 ciclos si el punto no es factible, mientras que en el ciclo de mejora, si la solución no ha mejorado y la distancia euclidiana entre la solución actual y el centroide es menor o igual a
ϕ,
entre los valores de aptitud es menor a
δ
o la diferencia
entonces se detiene la búsqueda y
en la siguiente iteración se seleccionará una solución aleatoriamente y no al peor. El seudocódigo completo del método se detalla en el Algoritmo 8.
Algoritmo 8 Complex 1: Inicializar el Complex 2:
while
qP
k ~i i (||x
− x||)2 > δ
qP
y
k i (f (xi )
− f )2 > ϕ
do
~xw
3:
Seleccionar al peor o una solución aleatoria del complex
4:
Crear una nueva solución ~ xn de acuerdo a la Ecuación 4.4 ~xw sea mejor que ~xn de acuerdo a reglas de Deb y ||~xn −x||
5: 6: 7: 8: 9: 10: 11: 12: 13: 14:
while do
>δ
~xn = (x + ~xn )/2
end while if ~xn es mejor que ~xw then Reemplazar
~xw
por
~xn
Continuar seleccionando a la peor solución del Complex
else
Seleccionar de manera aleatoria una solución en el siguiente ciclo
end if end while
15: Retornar la mejor solución del Complex
A continuación se describe el algoritmo memético basado en el propuesto por Karaboga y Akay [17]
4.2. Abeja empleada basada en Evolución Diferencial
21
4.2. Abeja empleada basada en Evolución Diferencial Con la nalidad de promover la mejora de las soluciones el operador de las abejas empleadas fue cambiado por el operador de la evolución diferencial rand/1/bin [32]. El operador original de las abejas empleadas lo podemos ver en la Ecuación 3.1 en la Ecuación 4.5 se muestra el operador de la evolución diferencial, donde
~xr0,g , ~xr1,g ,~xr2,g son tres vectores aleatorios de la población f es un número por lo general mayor a 1.
pero diferentes entre ellos, y
La nalidad de incluir el operador de evolución diferencial es promover la exploración por parte de las abejas empleadas sin embargo para no añadir la calibración del parámetro
f,
se mantiene la
φ
del operador original de las
abejas, dado que éste es un valor entre 0 y 1. En el Algoritmo 9 se muestra el proceso modi cado de las abejas empleadas.
~vi,g = ~xr0,g + f (~xr1,g − ~xr2,g )
Algoritmo 9
(4.5)
Proceso de las abejas empleadas usando el operador de evo-
lución diferencial
~xr0,g , ~xr1,g ,~xr2,g diferentes entre ellos jrand = rand(N ) // donde N es la dimensión del for i = 0 a i < N do if rand[0, 1] < M R o i = jrand then ~vi,g = ~xr0,g + φ(~xr1,g − ~xr2,g )
1: Seleccionar 2: 3: 4: 5:
else
6: 7: 8: 9:
problema
~vi,g = ~xi,g
end if end for
//~ xi,g la fuente de alimento actual
4.3. ε-constrained Para el manejo de restricciones se reemplazaron las reglas de Deb [8], por el método de
ε-contrained
[33], en el cual la sumatoria de violación de
restricciones se encuentra de nida por el máximo de todas las restricciones o por la suma de éstas, como se detalla en las Ecuaciones 4.6 y 4.7.
ϑ(x) = max{max{0, gj (x)}, max|hj (x)|} ϑ(x) =
X
||max{0, gj (x)}||P +
X
||hj (x)||P
(4.6)
(4.7)
gj (~x), j = 1, . . . , q son las restricciones de desigualdad, hj (~x), j = 1, . . . , m las de igualdad, y P un número entero positivo. donde
22
Capítulo 4. Algoritmo Propuesto CMABC
Las forma de selección se realiza por medio del nivel de par
(f (x), ϑ(x)),
ϑ
y se utiliza el
de acuerdo a la Ecuación 4.8.
(f1 , ϑ1 ) < (f2 , ϑ2 ) ⇔
f1 < f2 ,
if
f1 < f2 , ϑ G then Calcular
ψ
usando la Ecuación 4.10 sólo considerando las soluciones
no factibles
6: 7: 8: 9: 10:
end if end if if rand(0, 1) ≤ ψ then Aplicar buscador local
end if
4.5. Algoritmo Completo En las secciones anteriores se describieron algunas de las partes que comprenden el algoritmo memético propuesto en este trabajo de tesis. A continuación se muestra el algoritmo 11, donde se tiene el detalle completo cuya base es el algoritmo ABC propuesto por Karaboga y Akay [17]. Para decidir a que solución de la población aplicar el buscador local se usa el Algoritmo 12. En este algoritmo
xbg
y
xbg−1
son la mejor solución del ciclo actual y del
ciclo anterior,respectivamente. Dado que los buscadores locales que se proponen son deterministas, ésto es, para una solución dada siempre obtendrán la misma solución, y por esta razón se busca promover el uso del buscador local con una solución de la cual se desconozca su vecindad.
24
Capítulo 4. Algoritmo Propuesto CMABC
Algoritmo 11 Memético propuesto 1: Inicializar la población de soluciones
~xi,0 , i = 1, ..., SN
2: Calcular el limite para abandonar la fuente de alimento
SN )/(SN 2 ):
donde
F ES
3: Evaluar la población 4: 5:
while
no se alcance
limit = (F ES −
el número de evaluaciones permitidas
F ES
do
Aplicar el operador de la Ecuación 4.5 a cada una de las fuentes de alimento, manteniendo las mejores
6:
Calcular las probabilidades de selección de las fuentes de alimento de acuerdo al Algoritmo 6
7:
Calcular
cuantas
abejas
observadoras
deberán
ser
seleccionadas
onlookers = (SN/employedR) ∗ onlookerR: donde employedR y onlookerR son la relación entre el número de abejas empleadas y observadoras, comúnmente esta relación es de 1:1 8:
Seleccionar las soluciones que serán visitadas por las abejas observadoras mediante una ruleta
9:
Generar nuevas soluciones
~vi,g
para las abejas observadoras usando el
operador de la Ecuación 3.1 y evaluarlas
~xi,g
Conservar la mejor solución entre la actual
11:
Aplicar el buscador local de acuerdo a los Algoritmos 10 y 12
12: 13: 14: 15:
if
mejoró la solución
y
~vi,g
10:
then
Reemplazar la mejor con la solución dada por el buscador local
else
Reemplazar la peor solución de la población
16:
end if
17:
Veri car si existen fuentes abandonadas (si ya se alcanzó el
limit)
y
reemplazarlas por soluciones generadas de manera aleatoria por las abejas exploradoras. 18: 19:
Conservar la mejor solución encontrada hasta el momento
end while
Algoritmo 12 Selección de solución para aplicar el buscador local 1: if NO se ha aplicado el buscador local o ~ xbg 6= ~xbg−1 then 2: 3: 4:
b
Aplicar el buscador local a la mejor solución del ciclo actual (xg )
else
Aplicar el buscador local a una solución seleccionada de manera aleatoria
5:
end if
Capítulo 5
Resultados y discusión En este capítulo se presentan y discuten los resultados obtenidos por el algoritmo memético propuesto con los buscadores local Hooke-Jevees (CMABC-HJ) y Complex (CM-ABC-COM).
5.1. Diseño del experimento Para evaluar el desempeño y comportamiento del algoritmo memético propuesto, se utilizaron los conjuntos de prueba del congreso de Computación Evolutiva (CEC) de la IEEE en sus versiones del CEC2006 y CEC2010 que contienen diferentes tipos de funciones con restricciones tanto de igualdad como de desigualdad. En la Tabla 5.3 se resumen las características principales del conjunto de funciones de prueba del CEC2006 en esta tabla del problema,
LI
D
es el número de variables
es el número de restricciones lineales de desigualdad,
es el número de restricciones no-lineales de desigualdad, restricciones lineales de igualdad, de igualdad,
NE
LE
NI
es el número de
el número de restricciones no-lineales
a es el número de restricciones activas en ~x y ρ = |F |/|S| es una
medida para aproximar el tamaño de la región factible con respecto a todo el espacio de búsqueda, donde
|F |
es el número de soluciones factibles y
|S|
el total de soluciones generadas aleatoriamente. En [25] Michalewicz sugiere un total de 1,000,000 de soluciones para
|S|.
En la Tabla 5.4 se muestran los
límites para las variables y el valor de aptitud
f (~x)
óptimo de cada función.
El detalle de las funciones de este conjunto de pruebas puede verse en [15] y en apéndice C. La Tabla 5.5 muestra las características principales del conjunto de pruebas del CEC2010, en [30] y en el apéndice C se puede ver el detalle de las funciones cabe destacar que de este conjunto de funciones se desconoce su valor óptimo. El algoritmo CMABC se ejecutó de acuerdo a los requerimientos de los conjuntos de prueba. Para el CEC2006 se realizaron 25 ejecuciones por cada 25
26
Capítulo 5. Resultados y discusión
función y considerando un máximo de 500,000 evaluaciones. El conjunto de prueba del CEC2010 al ser problemas escalables, se ejecuta con dimensión 10 y 30 para cada función, en ambos casos se consideran 25 ejecuciones del algoritmo, y un máximo de 200,000 evaluaciones para la dimensión 10 y 600,000 para la dimensión 30. A los resultados se le aplicó la prueba estadística de Wilcoxon, que es una prueba no paramétrica que compara las medianas de dos muestras relacionas, para determinar si existen diferencias signi cativas entre ellas, se utiliza cuando no se puede suponer la normalidad en dichas muestras [35].
5.1.1. Parámetros de los algoritmos En las Tablas 5.1 y 5.2 se muestran los parámetros con los que se probaron los algoritmos. MABC-SF es el algoritmo MABC-SmartFlight propuesto por Cetina en [23]. MABC de Karaboga [17] descrito en el capítulo 3. CM-ABC-HJ y CM-ABC-COM con los buscadores locales Hooke-Jeeves y Complex, respectivamente.
Los parámetros para los algoritmos MABC y MABC-SF son los descritos en la literatura en la que se proponen. Para las versiones meméticas CM-ABC se calibraron con la herramienta IRACE [22], sin embargo los resultados de esta calibración fueron inferiores a los obtenidos por la calibración empírica, estos últimos son los que se presentan. Tabla 5.1: Parámetros para los algoritmos: SN es el número de fuentes de alimento, MR el Modi cation Ratio, MCN el máximo de ciclos, LIMITE máximo de ciclos que una fuente puede permanecer sin mejora, ERROR I y
ERROR F son la tolerancia inicial y nal para restricciones de igualdad. es la dimensión del problema.
MACBSF MABC
SN MR MCN LIMITE
ERROR I / ERROR F
50
0.8
1/1E-5
50
0.8
5800
45
D
0.5*SN*D
Los parámetros mostrados en la Tabla 5.2 son:
G
ciclo para considerar
la población no factible, TC ciclo en el que el valor de velocidad de decremento para
ε,
ε
sea igual a 0, CP
P exponente de penalización para la su-
matoria de violación de restricciones. Valores para el método Hooke-Jeves,
es la tolerancia de distancia entre las soluciones,
ción,
∆
plex son,
θ
α
es el factor de reduc-
es el vector de incrementos. Los parámetros para el método Com-
ϕ
diferencia mínima entre los valores de aptitud de las soluciones,
es el factor de contracción y
δ
la distancia mínima entre las soluciones.
5.2. Resultados
27
Employed/Onlooker
es la relación entre el número de abejas empleadas y
abejas observadoras. Tabla 5.2: Parámetros el algoritmo propuesto y los buscadores locales. Hooke-
distancia mínima para terminar, α factor de reducción, ∆ vector de incrementos. Complex: ϕ diferencia mínima entre la aptitud de las soluciones, α factor de re exión, δ distancia mínima entre las soluciones. MC-ABC: SN número de fuentes de alimento, M R Modi cation Ratio, G ciclo para considerar convergencia no factible. ε-constraint: T C ciclo donde ε es mínimo, CP factor de reducción de , P potencia para la suma de restricciones. Jeeves:
MC-ABC SN MR G 100
0.8
HOOKE JEEVES 500
ε-CONSTRAINT
TC CP 500
3
P
1
α
1.00E-005
∆ 2
COMPLEX
0.5
ϕ
α
δ
1.00E-005
1.3
1.00E-005
5.2. Resultados Las Tablas 5.6,5.7 y 5.8 muestran los resultados estadísticos obtenidos de cada algoritmo en las funciones del conjunto de prueba del CEC2006 y la prueba de Wilcoxon respecto a CMACB-HJ. Se puede observar para las funciones G01, G06, G08, G12, G16 y G24 todos los algoritmos encuentran el valor óptimo, y en las funciones G20, G21 y G22 ninguno logra realizar ejecuciones con resultados factibles. MABC de Karaboga encuentra el óptimo en la función G02, sin embargo en las funciones G14 y G23 es el único que no encuentra soluciones factibles. Y en las funciones G03, G04, G05, G07, G09, G13, G15, G17, G18 y G19 todos los algoritmos encuentran soluciones factibles, sin embargo no logran obtener el valor óptimo. Los algoritmos meméticos logran generar más ejecuciones factibles. Para el conjunto de pruebas del CEC2010 se desconocen los valores óptimos, sin embargo utilizamos los obtenidos por Takahama y Sakai [33]. En las tablas 5.9 y 5.10 se muestran los resultados para las funciones del CEC2010 con dimensión 10, y en la Tabla A.2 se presenta la prueba estadística de Wilcoxon para estos resultados. El algoritmo MABCSF únicamente en la función C11 no encuentra soluciones factibles, MABC en las funciones C03, C04, C05, C06, C09, C10, C11 y C16 no logra ninguna ejecución factible, y solamente el algoritmo CMABC-HJ en todas las funciones encuentra resultados factibles. En las funciones C01, C5, C06, C13 y C16 el algoritmo CMABC-HJ llega al óptimo obtenido por Takahama. En C18 CMABC-HJ encuentra un mejor resultado que el reportado por Takahama.
28
Capítulo 5. Resultados y discusión
Los resultados estadísticos para el conjunto de pruebas de CEC2010 en dimensión 30, son mostradas en las Tablas 5.11 y 5.12 y en la Tabla A.3 la prueba de Wilcoxon. En estos resultados podemos observar que ninguno de los algoritmos logra resultados factibles en todas las funciones. Sin embargo CMABC-HJ en las funciones C02, C03, C16 y C17 logra encontrar el óptimo reportado por Takahama, y en C13 y C18 encuentra un valor más bajo. En el apéndice A se muestra el detalle de las pruebas de Wilcoxon entre los algoritmos probados. Y en el B se muestran todas las grá cas de convergencia de cada una de las funciones.
5.3. Discusión 5.3.1. Resultados CEC2006 Es interesante observar que con respecto al conjunto de prueba del CEC2006, el algoritmo propuesto CMABC (en sus dos variantes con diferente buscador local), tienen mejor rendimiento (estadísticamente signi cativo) que MABCSF y MABC, en cuanto a la generación de soluciones factibles sólo en las funciones G15 y G23 obtuvieron menos de las 25 ejecuciones, lo cual nos dice que éstos son más estables. Ésto lo podemos veri car observando que existen diferencias signi cativas, entre los desempeños observados en tales algoritmos. De acuerdo a la prueba de Wilcoxon el algoritmo memético con el buscador local Hooke-Jeeves tiene mejor comportamiento en las funciones G02, G03, G06, G07, G10, G12, G13, G14, G18, G19 Y G24. Mientras que MCABCCOM sólo en la función G16. Ambos algoritmos tienen comportamiento similar y son mejores que MABC y MABC-SF en las funciones G01, G04, G05, G08, G09, G11, G15, G17 y G23. En Figura 5.1 se muestra la grá ca de convergencia para la función G01, en ésta observamos que el comportamiento de los algoritmos es muy similar, sin embargo se destaca que MABC-SF es el que converge mas rápido, y MABC es el que lo hace mas lento. La grá ca de convergencia para función G04 mostrada en 5.2 muestra la reducción en la velocidad de convergencia en los algoritmos meméticos propuestos. En la Figura 5.3 se aprecia mejor la velocidad de convergencia, en esta función MABC no encontró soluciones factibles. Podemos observar que la version CMABC-COM encuentra la zona factible más rápido que los otros, CMABC-HJ tarda más en entrar en la zona factible pero encuentra mejores resultados. Las funciones G20, G21 y G22 son difíciles de resolver pues, son las que tiene mayor numero de restricciones de igualdad no lineales. Se puede apreciar en las grá cas de convergencia que los algoritmos meméticos requieren
5.3. Discusión
29
un mayor número de evaluaciones por ciclo que MABC y MABC-SF. Los comportamientos aquí descritos se comparten en general para las funciones del CEC2006.
5.3.2. Resultados CEC2010 Las funciones del CEC2010 presentan un reto para los algoritmos basados en ABC, sin embargo para las funciones en dimensión 10 se observa que los algoritmos meméticos superan en desempeño a MABC y MABC-SF. El algoritmo memético que incorpora al método de Hooke-Jeeves obtiene mejores resultados y desempeño que su similar Complex, en las funciones C01, C03, C05, C07, C08, C09, C11, C13, C14, C16 y C18. Mientras que en las funciones C02 y C10 su comportamiento es similar. Es interesante observar que en las funciones C14 y C15 aunque se logra alcanzar la zona factible, los resultados están muy alejados de los reportados por Takahama, se observa que estas funciones no son separables y que sólo cuentan con restricciones de desigualdad, sin embargo aunque estas características las comparten con otras funciones, su espacio de búsqueda es grande. En estas funciones en la dimension 30, el rendimiento en general de los algoritmos decae, para las funciones C04, C05, C06 y C11 ambos algoritmos meméticos no logran alcanzar la zona factible. Se continua observando un mejor rendimiento por parte de CMABC-HJ respecto a los demás algoritmos, incluso en las funciones C17 y C18 encuentra mejores resultados que los reportados por Takahama. En la Figura 5.4 se muestra la grá ca de convergencia para la función C01 en dimensión 30, en ella el mejor valor encontrado fue por MABC. Podemos ver que el comportamiento de los algoritmos meméticos es muy similar, y requieren más evaluaciones por ciclo, sobre todo el que tiene el método Complex. Al parecer los buscadores locales no están ayudando en la mejora de las soluciones como se espera. Este comportamiento se re eja de igual manera en las funciones C14 y C15, de las cuales se muestran sus grá cas de convergencia en las Figuras 5.5 y 5.6.
30
Capítulo 5. Resultados y discusión
Figura 5.1: Grá ca de convergencia de la función G01
Figura 5.2: Grá ca de convergencia de la función G04
5.3. Discusión
Figura 5.3: Grá ca de convergencia de la función G23
Figura 5.4: Grá ca de convergencia de la función C01 dimensión 30
31
32
Capítulo 5. Resultados y discusión
Figura 5.5: Grá ca de convergencia de la función C14 dimensión 30
5.3. Discusión
Figura 5.6: Grá ca de convergencia de la función C15 dimensión 30
33
34
Capítulo 5. Resultados y discusión
Tabla 5.3: Características de las funciones del conjunto de prueba del CEC2006.
D
número de variables del problema,
de la zona factible, neales,
LI
y
NI
ρ
porcentaje aproximado
restricciones de desigualdad lineales y no li-
LE y N E son el número de restricciones a es el número de restricciones activas
de igualdad lineales y no
lineales. Prob.
D
Tipo de Función
g01
13
cuadrática
g02
20
no lineal
g03
10
g04
5
g05
4
g06
2
g07
10
g08
2
g09 g10
ρ
LI
NI
LE
NE
a
0.0111 %
9
0
0
0
6
99.9971 %
0
2
0
0
1
polinomial
0.0000 %
0
0
0
1
1
cuadrática
52.1230 %
0
6
0
0
2
cúbica
0.0000 %
2
0
0
3
3
cúbica
0.0066 %
0
2
0
0
2
cuadrática
0.0003 %
3
5
0
0
6
no lineal
0.8560 %
0
2
0
0
0
7
polinomial
0.5121 %
0
4
0
0
2
8
lineal
0.0010 %
3
3
0
0
6
g11
2
cuadrática
0.0000 %
0
0
0
1
1
g12
3
cuadrática
4.7713 %
0
1
0
0
0
g13
5
no lineal
0.0000 %
0
0
0
3
3
g14
10
no lineal
0.0000 %
0
0
3
0
3
g15
3
cuadrática
0.0000 %
0
0
1
1
2
g16
5
no lineal
0.0204 %
4
34
0
0
4
g17
6
no lineal
0.0000 %
0
0
0
4
4
g18
9
cuadrática
g19
15
no lineal
g20
24
g21
7
g22 g23 g24
0.0000 %
0
13
0
0
6
33.4761 %
0
5
0
0
0
lineal
0.0000 %
0
6
2
12
16
lineal
0.0000 %
0
1
0
5
6
22
lineal
0.0000 %
0
1
8
11
19
9
lineal
0.0000 %
0
2
3
1
6
2
lineal
79.6556 %
0
2
0
0
2
5.3. Discusión
35
Tabla 5.4: Límites y valor óptimo de las funciones del conjunto de prueba del CEC2006
Prob.
D
f (~x)
g01
13
-15
g02
20
-0.8036191042
g03
10
-1.0005001
g04
5
-30665.5386717834
g05
4
5126.4967140071
g06
2
-6961.8138755802
g07
10
24.3062090681
g08
2
-0.0958250415
g09
7
680.6300573745
g10
8
7049.2480205286
g11
2
0.7499
g12
3
-1
g13
5
0.053941514
g14
10
-47.7648884595
g15
3
961.7150222899
g16
5
-1.9051552586
g17
6
8853.5396748064
g18
9
-0.8660254038
g19
15
32.6555929502
g20
24
0.2049794002
g21
7
193.72451007
g22
22
236.430975504
g23
9
-400.0551
g24
2
-5.5080132716
Límites
0 ≤ ~xi ≤ 1(i = 1, . . . , 9), 0 ≤ ~xi ≤ 100(i = 10, 11, 12) y 0 ≤ ~x1 3 ≤ 1 0 < ~xi ≤ 10(i = 1, . . . , n) 0 ≤ ~xi ≤ 1(i = 1, . . . , n) 78 ≤ ~x1 ≤ 102, 33 ≤ ~x2 ≤ 45 y 27 ≤ ~xi ≤ 45(i = 3, 4, 5) 0 ≤ ~x1 ≤ 1200, 0 ≤ ~x2 ≤ 1200, −0.55 ≤ ~x3 ≤ 0.55 y −0.55 ≤ ~x4 ≤ 0.55 13 ≤ ~x1 ≤ 100 y 0 ≤ ~x2 ≤ 100 −10 ≤ ~xi ≤ 10(i = 1, . . . , 10) 0 ≤ ~x1 ≤ 10 y 0 ≤ ~x2 ≤ 10 −10 ≤ ~xi ≤ 10 para (i = 1, . . . , 7) 100 ≤ ~x1 ≤ 10000, 1000 ≤ ~xi ≤ 10000(i = 2, 3) y 10 ≤ ~xi ≤ 1000(i = 4, . . . , 8) −1 ≤ ~x1 ≤ 1 y −1 ≤ ~x2 ≤ 1 0 ≤ ~xi ≤ 10(i = 1, 2, 3) y p, q, r = 1, 2, . . . , 9 −2.3 ≤ ~xi ≤ 2.3(i = 1, 2) y −3.2 ≤ ~xi ≤ 3.2(i = 3, 4, 5) 0 < ~xi ≤ 10(i = 1, . . . , 10) 0 ≤ ~xi ≤ 10(i = 1, 2, 3) 704.4148 ≤ ~x1 ≤ 906.3855, 68.6 ≤ ~x2 ≤ 288.88, 0 ≤ ~x3 ≤ 134.75, 193 ≤ ~x4 ≤ 287.0966, 25 ≤ ~x5 ≤ 84.1988 0 ≤ ~x1 ≤ 400, 0 ≤ ~x2 ≤ 1000, 340 ≤ ~x3 ≤ 420, 340 ≤ ~x4 ≤ 420, −1000 ≤ ~x5 ≤ 1000 y 0 ≤ ~x6 ≤ 0.5236 −10 ≤ ~xi ≤ 10(i = 1, . . . , 8) y 0 ≤ ~x9 ≤ 20 0 ≤ ~xi ≤ 10(i = 1, . . . , 15) 0 ≤ ~xi ≤ 10(i = 1, . . . , 24) 0 ≤ ~x1 ≤ 1000, 0 ≤ ~x2 , ~x3 ≤ 40, 100 ≤ ~x4 ≤ 300, 6.3 ≤ ~x5 ≤ 6.7, 5.9 ≤ ~x6 ≤ 6.4 y 4.5 ≤ ~x7 ≤ 6.25 0 ≤ ~x1 ≤ 20000, 0 ≤ ~x2 , ~x3 , ~x4 ≤ 1 × 106 , 0 ≤ ~x5 , ~x6 , ~x7 ≤ 4 × 107 100 ≤ ~x8 ≤ 299.99, 100 ≤ ~x9 ≤ 399.99, 100.01 ≤ ~x10 ≤ 300, 100 ≤ ~x11 ≤ 400 100 ≤ ~x12 ≤ 600, 0 ≤ ~x13 , ~x14 , ~x15 ≤ 500, 0.01 ≤ ~x16 ≤ 300 0.01 ≤ ~x17 ≤ 400, −4.7 ≤ ~x18 , ~x19 , ~x20 , ~x21 , ~x22 ≤ 6.25 0 ≤ ~x1 , ~x2 , ~x6 ≤ 300, 0 ≤ ~x3 , ~x5 , ~x7 ≤ 100, 0 ≤ ~x4 , ~x8 ≤ 200 0.01 ≤ ~x9 ≤ 0.03 0 ≤ ~x1 ≤ 3 y 0 ≤ ~x2 ≤ 4
y
36
Capítulo 5. Resultados y discusión
Tabla 5.5: Características de las funciones del conjunto de prueba del CEC2010.
D
es el número de variables del problema, E es el número
de restricciones de igualdad, I el número de restricciones de desigualdad.
ρ = |F |/|S|
es el porcentaje estimado entre la región factible y el espacio de
búsqueda
Prob.
Rango
Tipo de objetivo
E
I
Región factible 10D
30D
C01
[0, 10]D
No separable
0
2
0.997689 %
1.000000 %
C02
[−5.12, 5.12]D [−1000, 1000]D [−50, 50]D [−600, 600]D [−600, 600]D [−140, 140]D [−140, 140]D [−500, 500]D [−500, 500]D [−100, 100]D [−1000, 1000]D [−500, 500]D [−1000, 1000]D [−1000, 1000]D [−10, 10]D [−10, 10]D [−50, 50]D
Separable
1
2
0.000000 %
0.000000 %
No separable
1
0
0.000000 %
0.000000 %
Separable
4
0
0.000000 %
0.000000 %
Separable
2
0
0.000000 %
0.000000 %
Separable
2
0
0.000000 %
0.000000 %
No separable
0
1
0.505123 %
0.503725 %
No separable
0
1
0.379512 %
0.375278 %
No separable
1
0
0.000000 %
0.000000 %
No separable
1
0
0.000000 %
0.000000 %
Rotado
1
0
0.000000 %
0.000000 %
Separable
1
1
0.000000 %
0.000000 %
Separable
0
3
0.000000 %
0.000000 %
No separable
0
3
0.003112 %
0.006123 %
No separable
0
3
0.003210 %
0.006023 %
No separable
2
2
0.000000 %
0.000000 %
No separable
1
2
0.000000 %
0.000000 %
No separable
1
1
0.000010 %
0.000000 %
C03 C04 C05 C06 C07 C08 C09 C10 C11 C12 C13 C14 C15 C16 C17 C18
5.3. Discusión
37
Tabla 5.6: Estadísticas del conjunto de pruebas CEC2006: funciones G01 a G08. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa.
G01 Factibles -1.50E+01 Mejor Mediana Media Desv. Std. Peor Wilcoxon G02 Factibles -8.04E-01 Mejor Mediana Media Desv. Std. Peor Wilcoxon G03 Factibles -1.00E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon G04 Factibles -3.07E+04 Mejor Mediana Media Desv. Std. Peor Wilcoxon G05 Factibles 5.13E+03 Mejor Mediana Media Desv. Std. Peor Wilcoxon G06 Factibles -6.96E+03 Mejor Mediana Media Desv. Std. Peor Wilcoxon G07 Factibles 2.43E+01 Mejor Mediana Media Desv. Std. Peor Wilcoxon G08 Factibles -9.58E-02 Mejor Mediana Media Desv. Std. Peor Wilcoxon
CM-ABC-HJ MABC-SF MABC
CM-ABC-COM
25
-1.50E+01
25
25
-1.50E+01 -1.50E+01 -1.50E+01
25
-1.50E+01
-1.50E+01
-1.50E+01
-1.50E+01
-1.50E+01
-1.46E+01
-1.50E+01
0.00E+00
-1.50E+01
7.07E-01
-1.50E+01
-1.24E+01
-1.50E+01
-1.50E+01
25
-8.04E-01
25 -6.94E-01
-8.04E-01
-7.93E-01
-5.09E-01
-8.04E-01
-7.90E-01
-4.92E-01
-8.03E-01
1.25E-02
1.05E-01
1.55E-03
4.22E-02
-7.64E-01
-2.35E-01
-7.97E-01
-6.30E-01
0.00E+00
+
= 25
+ 25
20
0.00E+00 =
25 -7.88E-01 -7.50E-01 -7.37E-01
25
+ 25
-1.00E+00
-1.00E+00
-1.00E+00
-1.00E+00
-2.62E-01
-1.00E+00
-1.00E+00
-8.82E-01
-2.88E-01
-1.00E+00
2.26E-01
1.34E-01
2.98E-04
-1.00E+00
-2.37E-01
-7.78E-02
-9.99E-01
25
-3.07E+04
25
-3.07E+04
1.83E-08
-5.85E-01
+
-1.00E+00
+
+
25
25
-3.06E+04
-3.07E+04 -3.07E+04
-3.06E+04
-3.07E+04
-3.07E+04
-3.07E+04
-3.05E+04
-3.07E+04
1.23E+02
4.64E-12
-3.07E+04
4.87E-12 -3.07E+04
-3.02E+04
-3.07E+04
-3.07E+04
25
10
11
5.13E+03
5.13E+03
5.13E+03
5.26E+03
5.13E+03
5.13E+03
5.13E+03
5.30E+03
5.17E+03
1.49E-12
1.98E+02
7.98E+01
1.41E-12
5.13E+03
5.76E+03
5.40E+03
5.13E+03
+
5.13E+03
5.13E+03
=
+ 25
5.20E-12 = 25
5.13E+03
+
=
-6.96E+03
25
25
25
-6.96E+03 -6.96E+03 -6.96E+03
-6.96E+03
-6.96E+03
-6.96E+03
-6.96E+03
-6.96E+03
-6.73E+03
-6.96E+03
3.71E-12
-6.96E+03
5.14E+02
-6.96E+03
-5.17E+03
-6.96E+03
-6.96E+03
25
2.43E+01
25 2.51E+01
2.44E+01
2.43E+01
2.43E+01
2.80E+01
2.44E+01
2.43E+01
2.43E+01
2.89E+01
2.44E+01
2.43E+01
3.69E+00
7.30E-02
1.44E-04
4.00E+01
2.47E+01
2.43E+01
3.71E-12
+
2.30E-06
2.43E+01
= 25
+ 25
25
+
+
25
25
-9.58E-02
-9.58E-02
-9.58E-02
-9.58E-02
-9.58E-02
-9.58E-02
-9.58E-02
-9.32E-02
-9.58E-02
-9.58E-02
+ 25
-9.58E-02 1.42E-17
3.85E-07
-9.58E-02
-9.58E-02
1.33E-02
1.42E-17
1.42E-17
-2.91E-02
-9.58E-02
-9.58E-02
+
=
=
38
Capítulo 5. Resultados y discusión
Tabla 5.7: Estadísticas del conjunto de pruebas CEC2006: funciones G09 a G16. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa.
G09 6.81E+02
Factibles Mejor Mediana Media Desv. Std. Peor Wilcoxon G10 Factibles 7.05E+03 Mejor Mediana Media Desv. Std. Peor Wilcoxon G11 Factibles 7.50E-01 Mejor Mediana Media Desv. Std. Peor Wilcoxon G12 Factibles -1.00E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon G13 Factibles 5.39E-02 Mejor Mediana Media Desv. Std. Peor Wilcoxon G14 Factibles -4.78E+01 Mejor Mediana Media Desv. Std. Peor Wilcoxon G15 Factibles 9.62E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon G16 Factibles -1.91E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon
CM-ABC-HJ MABC-SF MABC
CM-ABC-COM
25
25
25
6.81E+02
6.81E+02
6.81E+02
6.82E+02
6.81E+02
6.81E+02
6.81E+02
3.26E-13
6.83E+02
6.81E+02
6.81E+02
2.54E+00
3.07E-03
3.50E-13
6.81E+02
6.90E+02
6.81E+02
6.81E+02
25
24
25
25
6.81E+02
7.05E+03
6.81E+02
+
+
25
=
7.24E+03
7.06E+03
7.05E+03
7.05E+03
8.35E+03
7.11E+03
7.05E+03
7.05E+03
3.62E-06
9.50E+03
7.14E+03
7.05E+03
2.66E+03
7.74E+01
7.59E-02
7.05E+03
1.64E+04
7.35E+03
7.05E+03
25
16
25
25
7.50E-01
7.50E-01
7.52E-01
7.50E-01
7.50E-01
7.50E-01
7.59E-01
3.40E-16
2.15E-04
1.45E-02
3.30E-16
7.50E-01
7.51E-01
8.05E-01
7.50E-01
7.50E-01
+
7.50E-01
+
7.50E-01
+
+
7.50E-01 7.50E-01
+
=
25
25
25
25
-1.00E+00
-1.00E+00
-1.00E+00
-1.00E+00
-1.00E+00
-9.96E-01
-1.00E+00
-1.00E+00
0.00E+00
-1.00E+00
25
5.39E-02
-1.00E+00 -1.00E+00 -1.00E+00 -1.00E+00
9.83E-03
0.00E+00
3.71E-08
-9.51E-01
-1.00E+00
-1.00E+00
+
9
+
= 2
25
5.94E-02
9.97E-01
5.39E-02
5.39E-02
5.00E-01
1.00E+00
5.39E-02
5.39E-02
8.01E-18
5.69E-01
9.98E-01
5.40E-02
5.99E-01
2.06E-03
5.97E-06
5.39E-02
2.04E+00
1.00E+00
5.40E-02
25
7
0
25
-4.67E+01
-4.78E+01
-4.77E+01
-4.56E+01
-4.77E+01
-4.77E+01
-4.55E+01
-4.77E+01
1.18E+00
1.13E-01
-4.76E+01
-4.32E+01
13
16
24
9.62E+02
9.62E+02
9.62E+02
9.63E+02
9.65E+02
9.62E+02
9.62E+02
2.37E-13
9.63E+02
9.65E+02
9.62E+02
8.68E-01
2.18E+00
3.52E-13
9.62E+02
9.65E+02
9.69E+02
9.62E+02
25
25
25
25
-1.91E+00
-1.85E+00
-1.91E+00
-1.91E+00
-1.91E+00
-1.79E+00
-1.91E+00
1.25E-01
4.53E-16
-1.91E+00
6.84E-16 -1.91E+00
-1.50E+00
-1.91E+00
-1.91E+00
-4.78E+01
4.95E-02
9.62E+02
-1.91E+00
+
+
9.62E+02
+
+
+
+
+
-4.73E+01
+
17
=
-1.91E+00 -1.91E+00 -1.91E+00
+
-
5.80E-16 =
5.3. Discusión
39
Tabla 5.8: Estadísticas del conjunto de pruebas CEC2006: funciones G17 a G24. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CM-ABC-HJ, - en contra y = que no existe diferencia signi cativa.
G17 8.85E+03
Factibles Mejor Mediana Media Desv. Std. Peor Wilcoxon G18 Factibles -8.66E-01 Mejor Mediana Media Desv. Std. Peor Wilcoxon G19 Factibles 3.27E+01 Mejor Mediana Media Desv. Std. Peor Wilcoxon G20 Factibles 9.67E-02 Mejor Mediana Media Desv. Std. Peor Wilcoxon G21 Factibles 1.94E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon G22 Factibles 2.36E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon G23 Factibles -4.00E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon G24 Factibles -5.51E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon
CM-ABC-HJ MABC-SF MABC 25
CM-ABC-COM
8.85E+03
5
4
8.94E+03
8.93E+03
8.85E+03
8.93E+03
8.95E+03
8.94E+03
8.93E+03
8.91E+03
9.04E+03
8.94E+03
3.56E+01
1.36E+02
8.87E+00
3.47E+01
8.95E+03
9.23E+03
8.95E+03
8.95E+03
+ 25
25
25
8.91E+03
+
=
25
25
-6.75E-01
-8.66E-01
-8.66E-01
-8.66E-01
-8.66E-01
-5.06E-01
-7.04E-01
-7.90E-01
-6.09E-01
-7.51E-01
9.55E-02
1.51E-01
8.56E-02
9.68E-02
-6.75E-01
-4.36E-01
-6.71E-01
-6.75E-01
+
-8.66E-01
-7.59E-01
-
3.27E+01
25 4.94E+01
3.47E+01
3.27E+01
3.27E+01
8.74E+01
3.58E+01
3.27E+01
3.27E+01
9.26E+01
3.58E+01
3.27E+01
2.85E+01
4.52E-01
2.47E-02
1.54E+02
3.66E+01
3.28E+01
1.13E-02
3.27E+01
25
+
25
+
25
+
+
0
0
0
0
0
0
0
0
0
0
0
0
23
-3.89E+02
2
0
-1.44E+02
-2.80E+02
1.16E+02
-2.02E+02
-2.39E+02
-1.41E+01
-1.64E+02
1.84E+02
1.78E+02
2.49E+02
1.16E+02
3.39E+02
25
-5.51E+00
25
25
25
-5.51E+00 -5.51E+00 -5.51E+00
-5.51E+00
-5.51E+00
-5.51E+00
-5.51E+00
-5.51E+00
-5.51E+00
-5.51E+00
9.06E-16
-5.51E+00
1.98E-03 -5.50E+00
-5.51E+00
-5.51E+00
1.60E+02
+
=
9.06E-16
-5.51E+00
+
22
-3.88E+02
=
=
1.03E-13 +
40
Capítulo 5. Resultados y discusión
Tabla 5.9: Estadísticas del conjunto de pruebas CEC2010 dimensión 10: funciones C01 a C09. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CMABC-HJ, - en contra y = que no existe diferencia signi cativa.
C01 -7.473E-01
Factibles Mejor Mediana Media Desv. Std. Peor Wilcoxon C02 Factibles -2.278E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C03 Factibles 0.000E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C04 Factibles -9.992E-06 Mejor Mediana Media Desv. Std. Peor Wilcoxon C05 Factibles -4.836E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon C06 Factibles -5.787E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon C07 Factibles 0.000E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C08 Factibles 0.000E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C09 Factibles 0.000E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon
CM-ABC-HJ MABC-SF MABC
CM-ABC-COM
25
25
25
25
-7.47E-01
-7.12E-01
-7.47E-01
-7.47E-01
-5.42E-01
-7.47E-01
-6.94E-01
-7.44E-01
-5.55E-01
-7.47E-01
9.02E-02
1.01E-05
-6.81E-01
7.16E-03 -7.26E-01
-3.85E-01
-7.47E-01
-6.07E-01
25
-2.28E+00
13 -1.26E+00
1.70E+00
-2.28E+00
-2.24E+00
-2.40E-01
2.16E+00
-2.25E+00
-2.25E+00
-9.94E-02
1.93E+00
-2.25E+00
1.25E-02
7.41E-01
3.28E-01
1.24E-02
-2.24E+00
8.89E-01
2.16E+00
-2.24E+00
+
3.82E-02
2
+ 25
-7.43E-01
+ 24
+
=
3.22E-24
15
0
25
2.19E+01
1.49E-11
4.09E-07
9.48E+12
1.94E+00
3.40E+00
4.33E+13
7.08E+00
6.70E+13
1.26E+01
2.13E+14
7.80E+00
2.92E+01
+ 18
9
5.81E+01 +
+
0
0
4.78E-06
2.45E-03
6.38E-04
4.19E-02
1.72E-01
5.25E-02
3.35E-01
3.57E-02
1.01E+00
1.04E-01
+
+
+
8
-4.84E+02
4
0
10
1.43E+02
-2.61E+02
-2.47E+02
2.64E+02
-2.47E+02
-2.85E+02
2.67E+02
8.17E+01
1.23E+02
-2.47E+02
4.36E+02
+
-2.48E+02
4.39E+00 -2.47E+02 +
+
25
-5.79E+02
2
0
0
4.12E+02
-5.77E+02
4.54E+02
-5.68E+02
4.33E+02
4.71E+01
2.98E+01
-3.42E+02
4.54E+02
+ 25
25
+
25
+ 25
9.61E-20
8.45E-02
2.38E-02
7.58E-08
1.15E-13
1.00E+00
3.26E+00
1.39E+00 2.12E+00
4.78E-01
1.32E+00
3.92E+01
2.71E+00
8.83E+01
1.88E+00
2.77E+00
3.99E+00
3.57E+02
6.45E+00
1.28E+01
25
2.63E-22
25 3.52E-02
4.16E-03
1.54E+02
3.99E+00
8.40E+02
3.56E-01
2.10E+04
1.03E+01
6.31E+06
1.74E+00
2.24E+01
3.15E+07
3.11E+00
3.17E+05
1.15E+02
1.58E+08
1.08E+01
1.45E+06
+
+ 25
+ 25
+ 25
1.64E+05
+
+
6.69E-26
2
0
24
5.86E+12
2.69E-04
1.14E-01
7.59E+12
2.41E-01
3.54E-01
8.80E-01
6.72E+12
9.50E-01
1.23E+12
1.60E+00
4.41E+00
7.59E+12
+
4.44E+00 +
+
5.3. Discusión
41
Tabla 5.10: Estadísticas del conjunto de pruebas CEC2010 dimensión 10: funciones C10 a C18. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CMABC-HJ, - en contra y = que no existe diferencia signi cativa.
C10 0.000E+00
Factibles Mejor Mediana Media Desv. Std. Peor Wilcoxon C11 Factibles -1.523E-03 Mejor Mediana Media Desv. Std. Peor Wilcoxon C12 Factibles -5.701E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon C13 Factibles -6.843E+01 Mejor Mediana Media Desv. Std. Peor Wilcoxon C14 Factibles 0.000E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C15 Factibles 0.000E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C16 Factibles 0.000E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C17 Factibles 1.463E-17 Mejor Mediana Media Desv. Std. Peor Wilcoxon C18 Factibles 3.731E-20 Mejor Mediana Media Desv. Std. Peor Wilcoxon
CM-ABC-HJ MABC-SF MABC 25
5.24E-25
CM-ABC-COM
1
0
24
1.31E+12
6.43E-03
6.71E-01
1.31E+12
7.24E-01
1.15E+00
1.31E+12
1.41E+00
1.52E+00
1.51E+00
5.71E+00
1.31E+12
5.43E+00
8
-4.83E-04
0
-1.46E-04
-1.67E-04
=
2.39E-04
1.24E-04
+ 0
+ 7
10
= 0
+
20
+ 0
-5.68E+02
-3.06E+02
-1.92E-01
-1.73E+02
-3.25E-01
-1.11E-01
-2.86E+02
-3.18E+01
4.16E-02
9.63E+01
3.40E-01
1.93E+02 -1.73E+02
2.77E+00
1.01E+00
25
25
+
+
+
25
25
-6.84E+01
-6.22E+01
-6.84E+01
-6.84E+01
-5.96E+01
-6.83E+01
-5.77E+01
-6.79E+01
-5.86E+01
-6.80E+01
4.40E+00
7.09E-01
-5.69E+01
1.44E+00 -6.35E+01
-4.54E+01
-6.50E+01
-5.01E+01
25
24
4.52E+10
1.01E+06
25 1.09E+09
1.03E+12
1.14E+12
5.71E+13
1.38E+10
1.53E+13
1.43E+12
6.23E+13
1.80E+10
1.12E+12
5.13E+13
1.60E+10
9.44E+12
4.99E+12
2.09E+14
5.50E+10
3.77E+13
+
-6.10E+01
2.99E+00
-
-
+ 25
1.50E+13
-
25
10
25
+ 25
1.63E+12
5.70E+13
2.28E+12
4.71E+11
1.51E+13
1.57E+14
1.13E+13
3.11E+13
1.91E+13
1.52E+14
1.26E+13
1.37E+13
6.32E+13
9.15E+12
3.71E+13
5.29E+13
2.39E+14
4.44E+13
1.56E+14
+
3.87E+13
=
0.00E+00
6 6.66E-16
5.39E-10
0.00E+00
2.36E-01
1.37E-09
4.78E-02
0
-
12
15
1.49E-01
1.77E-01
2.28E-09
1.90E-01
2.14E-09
5.19E-01
4.93E-01
+ 1
8
8.76E-09 +
1
+ 0
7.19E-01
9.65E-13
3.91E+02
7.19E-01
3.19E+00
3.91E+02
3.91E+02
7.19E-01
1.78E+01
2.92E+01
7.19E-01
6.72E+01
3.91E+02
19
17
=
=
+
6
9 4.86E-06
1.34E-28
8.55E-23
2.15E+03
2.08E-21
1.94E-01
8.28E+03
1.50E-05
6.01E-19
2.51E-18
7.79E+01
7.00E+03
2.61E-05
1.86E+02
3.60E+03
2.54E-05
1.09E-17
7.42E+02
1.25E+04
7.90E-05
+
+
+
42
Capítulo 5. Resultados y discusión
Tabla 5.11: Estadísticas del conjunto de pruebas CEC2010 dimensión 30: funciones C01 a C09. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CMABC-HJ, - en contra y = que no existe diferencia signi cativa.
C01 -8.218E-01
Factibles Mejor Mediana Media Desv. Std. Peor Wilcoxon C02 Factibles -2.169E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C03 Factibles 2.867E+01 Mejor Mediana Media Desv. Std. Peor Wilcoxon C04 Factibles 4.698E-03 Mejor Mediana Media Desv. Std. Peor Wilcoxon C05 Factibles -4.531E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon C06 Factibles -5.286E+02 Mejor Mediana Media Desv. Std. Peor Wilcoxon C07 Factibles 1.147E-15 Mejor Mediana Media Desv. Std. Peor Wilcoxon C08 Factibles 2.519E-14 Mejor Mediana Media Desv. Std. Peor Wilcoxon C09 Factibles 2.771E-16 Mejor Mediana Media Desv. Std. Peor Wilcoxon
CM-ABC-HJ MABC-SF MABC
CM-ABC-COM
25
25
25
-6.45E-01
-8.22E-01
25
-8.20E-01 -7.93E-01
-4.06E-01
-8.20E-01
-7.02E-01
-7.94E-01
-4.20E-01
-8.19E-01
1.27E-01
1.94E-03
-6.91E-01
1.97E-02 -7.54E-01
-1.75E-01
-8.14E-01
-6.09E-01
22
-2.16E+00
0
-1.85E+00 -1.72E+00
4.58E+00
-1.82E+00
4.29E-01
3.57E-01
5.02E+00
-1.57E+00
+
3.29E-01
-9.74E-01
-7.56E-01
4.37E-02
-
+
10
2
3.72E+00
-2.08E+00
4.84E+00
-1.57E+00
+
+
2.87E+01
0
2.90E+01
2.87E+01
2.90E+01
2.87E+01
2.90E+01
2.87E+01
2.90E+01
0
0
0
0
2.19E-05
0
=
4
+
0
1
1
+
=
5.22E+02
0
0
5.22E+02
5.22E+02
5.22E+02
0
0
0
0
-
5.46E-05
25
25
25
25
1.34E-02
1.79E+01
1.50E+01
1.32E+01
1.71E+02
2.31E+01
8.25E+01
1.89E+01
2.45E+09
2.33E+01
2.10E+01
6.62E+09
2.12E+00
1.14E+02
7.73E+01
2.84E+10
2.79E+01
4.49E+02
+
1.16E+02
+ 25
+
25
3.93E+00
25 1.54E+02
2.31E+01
3.03E+07
1.28E+02
1.61E+08
2.41E+01
7.33E+07
4.38E+02
7.04E+09
2.44E+01
7.68E+02
1.48E+10
1.31E+00
5.60E+07
2.98E+03
5.82E+10
2.86E+01
2.71E+08
+
25
8.84E+07
+ 1
+
25
3.06E+00
1 4.35E+13
2.40E+13
8.28E+00
1.25E+02
4.35E+13
2.40E+13
5.82E+01
9.84E+02
4.35E+13
2.40E+13
1.36E+02
2.13E+03
1.72E+02
8.60E+03
4.35E+13 =
19
2.40E+13 =
6.43E+02 =
5.3. Discusión
43
Tabla 5.12: Estadisticas del conjunto de pruebas CEC2010 dimensión 30: funciones C10 a C18. En negrita se resaltan los mejores resultados. Para la prueba de Wilcoxon: + es que hay diferencia signi cativa a favor de CMABC-HJ, - en contra y = que no existe diferencia signi cativa.
C10 3.252E+01
Wilcoxon C11 -3.268E-04
Factibles Mejor Mediana Media Desv. Std. Peor
Factibles Mejor Mediana Media Desv. Std. Peor Wilcoxon C12 Factibles -1.991E-01 Mejor Mediana Media Desv. Std. Peor Wilcoxon C13 Factibles -6.642E+01 Mejor Mediana Media Desv. Std. Peor Wilcoxon C14 Factibles 5.016E-14 Mejor Mediana Media Desv. Std. Peor Wilcoxon C15 Factibles 2.160E+01 Mejor Mediana Media Desv. Std. Peor Wilcoxon C16 Factibles 0.000E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon C17 Factibles 2.166E-01 Mejor Mediana Media Desv. Std. Peor Wilcoxon C18 Factibles 1.226E+00 Mejor Mediana Media Desv. Std. Peor Wilcoxon
CM-ABC-HJ MABC-SF MABC
CM-ABC-COM
25
2
0
18
6.91E+01
3.77E+13
3.18E+01
3.40E+02
5.03E+13
9.37E+01
8.93E+02
4.40E+13
2.42E+03
8.94E+12
1.24E+04
5.03E+13
+
3.97E+02
8.70E+02 3.79E+03 +
-
0
0
0
0
17
0
18
7
-1.90E-01
-1.78E-01
6.82E-02
-1.29E-01
1.38E+00
3.29E+00
1.87E-01
8.21E-01
5.71E+00
5.63E+00 1.78E+01
2.87E+00
-1.93E-01
+ 25
24
6.93E+00 1.64E+01
= 25
= 25
-6.74E+01
-6.03E+01
-5.64E+01
-6.10E+01
-6.43E+01
-5.18E+01
-5.00E+01
-5.60E+01 -5.61E+01
-6.40E+01
1.63E+00
-4.99E+01
-5.06E+01
1.07E+01
3.13E+00
2.90E+00
-6.02E+01
-1.44E+01
-4.49E+01
-4.98E+01
25
25
3.06E+12
1.83E+11
25 5.18E+11
3.04E+13
1.08E+13
2.56E+14
1.78E+12
9.23E+13
1.23E+13
2.19E+14
1.75E+12
6.29E+12
1.32E+14
8.12E+11
3.98E+13
3.20E+13
4.20E+14
3.70E+12
1.77E+14
+
+
-
+ 25
9.55E+13
25
+
25
5.08E+13
19 8.46E+13
5.99E+13
6.95E+13
1.04E+14
3.65E+14
9.16E+13
2.21E+14
1.05E+14
3.49E+14
9.42E+13
2.02E+14
4.03E+13
1.28E+14
2.13E+14
6.32E+14
15
0.00E+00
1
0.00E+00 1.48E-17
6.02E-01
25
2.11E+13
7.35E+13
1.33E+14
3.45E+14
+
= 14
6.02E-01
1.16E+00
8.59E-12
6.02E-01
1.16E+00
2.95E-11
1.16E+00
9.50E-04 3.55E-03
3.91E-17
1.11E-16
6.02E-01
1.16E+00
= 5
+
1
1.33E-02
=
+
5.26E-02
2
3
1
3.29E+01
7.53E+02
1.74E-01
1.31E-01
1.87E+02
8.79E+02
1.74E-01
1.08E-01
4.60E-02
1.10E+02
1.16E+03
1.74E-01
1.09E+02
6.04E+02
1.55E-01
1.87E+02
1.86E+03
1.74E-01
=
+
1.81E-01
12 9.53E+00
2.44E+04
3.94E-01
1.74E+00
3.20E+02
3.60E+04
2.55E+00
2.58E+00
1.29E+03
3.62E+04
5.04E+00
2.88E+03
5.92E+03
8.99E+00
1.01E+04
4.63E+04
3.52E+01
2.73E+00
1.13E+01
16
=
17
+
14
+
=
Capítulo 6
Conclusiones y trabajo futuro A continuación se presentan las conclusiones a las que se llegaron aparir del experimento y resultados obtenidos, además de el trabajo futuro que se deriva de esta investigación.
6.1. Conclusiones De acuerdo a los resultados obtenidos por los algoritmos propuestos y expuestos en el capítulo anterior, podemos concluir que la hipótesis propuesta de este trabajo es validada, pues la combinación del algoritmo ABC con buscadores locales nos pueden proveer de resultados competitivos. Sin embargo incluir el buscador local implica un proceso de diseño, para que el resultado sea el deseado, si no, puede ser que se obtenga el efecto contrario. Aunque ambos buscadores locales se desempeñaron mejor que las versiones sin éstos, hay que destacar que el método de Hooke-Jeeves logro obtener mejores resultados sobre el método Complex. El rendimiento del algoritmo CMABC sobre las funciones del CEC2006, fue satisfactoria, solamente en las funciones G20, G21 y G22 no se obtuvieron resultados factibles. De acuerdo a las características de estas funciones, se puede concluir que la zona factible es muy pequeña y que las restricciones no lineales de igualdad presentan un problema tanto para el algoritmo ABC como para los buscadores locales. Respecto al conjunto de funciones del CEC2010, el algoritmo CMABC presentó mejor rendimiento que sus similares MABC y MABCSF. El algoritmo presenta di cultades en problemas donde la dimensionalidad es alta y los rangos de las variables son muy amplios (como en el benchmark del CEC'2010), ya que en dimensión 10 el rendimiento es mejor que en dimensión 30. Las funciones C14 y C15 son interesantes, ya que aunque su área factible es grande y rápida de alcanzar, los algoritmo no logran converger al optimo reportado por Takahama [33]. Podemos concluir que al ser no separables estas funciones, los buscadores locales (en que su funcionamiento 45
46
Capítulo 6. Conclusiones y trabajo futuro
exploran por dimensión) no logran el desempeño deseado. Las modi caciones respecto al operador de abejas empleadas y la relación entre el número de empleadas y observadoras, fueron realizadas para disminuir la rápida convergencia, ya que agregar el buscador local la aceleraría. Dadas las grá cas mostradas en las Figuras 5.1,5.2 y 5.3 podemos concluir que se logró disminuir la convergencia prematura.
6.2. Trabajo futuro Si algo destaca a la ciencia es que esta no se detiene, es por esto que derivada de esta investigación se observan el siguiente trabajo futuro. Probar otros algoritmos de búsqueda local (Powell, Hill-climbing) junto con el algoritmo ABC. Explorar otros diseños como lo puede ser el efecto Baldwin, la incorporación de la búsqueda local en los operadores de las abejas, entre otros. En el algoritmo propuesto se varió la relación entre el número de abejas empleadas con el número de abejas observadoras, buscando reducir la convergencia, se propone estudiar el comportamiento de este parámetro dentro del algoritmo memético.
Parte I
Apéndices
Apéndice A
Apéndice A.1. Pruebas de Wilcoxon
49
50
Apéndice A. Apéndice
Tabla A.1: Prueba de Wilcoxon para el CEC2006. El número 1 indica que hay diferencia signi cativa, el 0 que no la hay y - es que no hubo soluciones factibles. A0 es MABC-SF, A1 es MABC, A2 es CMABC-HJ, A3 es CMABCCOM
G01 A0 A1 A2 G02 A0 A1 A2 G03 A0 A1 A2 G04 A0 A1 A2 G05 A0 A1 A2 G06 A0 A1 A2 G07 A0 A1 A2 G08 A0 A1 A2
A1 A2 A3 G09 A1 1 1 1 A0 1 0 0 A1 0 A2 A1 A2 A3 G10 A1 1 1 1 A0 1 1 1 A1 1 A2 A1 A2 A3 G11 A1 1 1 1 A0 1 1 1 A1 1 A2 A1 A2 A3 G12 A1 1 1 1 A0 1 0 0 A1 0 A2 A1 A2 A3 G13 A1 1 1 1 A0 0 1 1 A1 0 A2 A1 A2 A3 G14 A1 1 1 1 A0 0 1 A1 1 A2 A1 A2 A3 G15 A1 1 1 1 A0 1 1 1 A1 1 A2 A1 A2 A3 G16 A1 1 1 1 A0 1 A1 0 0 0 A2
A2 A3 G17 1 1 A0 1 1 A1 0 A2 A2 A3 G18 1 1 A0 1 1 A1 1 A2 A2 A3 G19 1 1 A0 1 1 A1 0 A2 A2 A3 G20 1 0 A0 0 1 A1 1 A2 A2 A3 G21 1 1 A0 1 1 A1 1 A2 A2 A3 G22 1 1 A0 A1 1 A2 A2 A3 G23 1 1 A0 1 1 A1 0 A2 A2 A3 G24 1 1 A0 1 0 A1 0 A2
A1 A2 A3 0 1 1 1 1 0
A1 A2 A3 1 1 1 1 1 1 A1 A2 A3 1 1 1 1 1 1 A1 A2 A3 -
-
-
-
-
A1 A2 A3 -
-
-
-
-
A1 A2 A3 -
-
-
-
-
A1 A2 A3 -
0
0
-
0
A1 A2 A3 1 1 1 0 1 1
A.1. Pruebas de Wilcoxon
51
Tabla A.2: Prueba de Wilcoxon para el CEC2010 dimensión 10. El número 1 indica que hay diferencia signi cativa, el 0 que no la hay y - es que no hubo soluciones factibles. A0 es MABC-SF, A1 es MABC, A2 es CMABC-HJ, A3 es CMABC-COM
C01 A0 A1 A2 C02 A0 A1 A2 C03 A0 A1 A2 C04 A0 A1 A2 C05 A0 A1 A2 C06 A0 A1 A2
A1 A2 A3 1 1 1 1 1 1 A1 A2 A3 1 1 1 1 1 0
A1 A2 A3 1 1 -
-
1 A1 A2 A3 1 -
-
A1 A2 A3 1 1 -
-
1 A1 A2 A3 1 -
-
C07 A0 A1 A2 C08 A0 A1 A2 C09 A0 A1 A2 C10 A0 A1 A2 C11 A0 A1 A2 C12 A0 A1 A2
A1 A2 A3 C13 0 1 0 A0 1 1 A1 1 A2 A1 A2 A3 C14 1 1 1 A0 1 1 A1 1 A2 A1 A2 A3 C15 1 1 A0 A1 1 A2 A1 A2 A3 C16 0 0 A0 A1 0 A2 A1 A2 A3 C17 A0 A1 A2 A1 A2 A3 C18 1 1 A0 1 A1 A2
A1 A2 A3 1 1 1 1 1 1 A1 A2 A3 1 1 1 1 1 1 A1 A2 A3 1 1 1 0 1 1 A1 A2 A3 1 1 -
-
0
-
0
-
1 A1 A2 A3 0
-
A1 A2 A3 1 1 0 1 1 1
52
Apéndice A. Apéndice
Tabla A.3: Prueba de Wilcoxon para el CEC2010 dimensión 30. El número 1 indica que hay diferencia signi cativa, el 0 que no la hay y - es que no hubo soluciones factibles. A0 es MABC-SF, A1 es MABC, A2 es CMABC-HJ-T, A3 es CMABC
C01 A0 A1 A2 C02 A0 A1 A2 C03 A0 A1 A2 C04 A0 A1 A2 C05 A0 A1 A2 C06 A0 A1 A2
A1 A2 A3 1 1 1 1 1 1 A1 A2 A3 -
-
1
-
1 0
A1 A2 A3 -
-
-
-
0
A1 A2 A3 -
-
-
A1 A2 A3 -
-
-
-
-
A1 A2 A3 -
-
-
C07 A0 A1 A2 C08 A0 A1 A2 C09 A0 A1 A2 C10 A0 A1 A2 C11 A0 A1 A2 C12 A0 A1 A2
A1 A2 A3 C13 0 1 0 A0 1 1 A1 1 A2 A1 A2 A3 C14 1 1 0 A0 1 1 A1 1 A2 A1 A2 A3 C15 0 0 0 A0 0 0 A1 0 A2 A1 A2 A3 C16 1 1 A0 A1 1 A2 A1 A2 A3 C17 A0 A1 A2 A1 A2 A3 C18 A0 0 1 A1 0 A2
A1 A2 A3 0 1 1 1 1 1 A1 A2 A3 1 1 1 1 1 1 A1 A2 A3 1 1 1 0 1 1 A1 A2 A3 0
0
0
0
0
0
0
1 A1 A2 A3 0
1
0 0
A1 A2 A3 1 1 1 1 1 0
Apéndice B
Apéndice A continuación se presentan las grá cas de convergencia para cada una de las funciones. Estas grá cas corresponden a la ejecución con el valor de mediana en los resultados. Resumen:
B.1. Grá cas de convergencia CEC2006
Figura B.1: Grá ca de convergencia de la función G01
53
54
Apéndice B. Apéndice
Figura B.2: Grá ca de convergencia de la función G02
B.1. Grá cas de convergencia CEC2006
Figura B.3: Grá ca de convergencia de la función G03
Figura B.4: Grá ca de convergencia de la función G04
55
56
Apéndice B. Apéndice
Figura B.5: Grá ca de convergencia de la función G05
Figura B.6: Grá ca de convergencia de la función G06
B.1. Grá cas de convergencia CEC2006
Figura B.7: Grá ca de convergencia de la función G07
Figura B.8: Grá ca de convergencia de la función G08
57
58
Apéndice B. Apéndice
Figura B.9: Grá ca de convergencia de la función G09
Figura B.10: Grá ca de convergencia de la función G11
B.1. Grá cas de convergencia CEC2006
Figura B.11: Grá ca de convergencia de la función G02
Figura B.12: Grá ca de convergencia de la función G12
59
60
Apéndice B. Apéndice
Figura B.13: Grá ca de convergencia de la función G13
Figura B.14: Grá ca de convergencia de la función G14
B.1. Grá cas de convergencia CEC2006
Figura B.15: Grá ca de convergencia de la función G15
Figura B.16: Grá ca de convergencia de la función G16
61
62
Apéndice B. Apéndice
Figura B.17: Grá ca de convergencia de la función G17
B.1. Grá cas de convergencia CEC2006
Figura B.18: Grá ca de convergencia de la función G18
63
64
Apéndice B. Apéndice
Figura B.19: Grá ca de convergencia de la función G19
Figura B.20: Grá ca de convergencia de la función G23
B.1. Grá cas de convergencia CEC2006
Figura B.21: Grá ca de convergencia de la función G24
65
66
Apéndice B. Apéndice
B.2. Grá cas de convergencia CEC2010 dimensión 10
Figura B.22: Grá ca de convergencia de la función C01
B.2. Grá cas de convergencia CEC2010 dimensión 10
Figura B.23: Grá ca de convergencia de la función C02
Figura B.24: Grá ca de convergencia de la función C03
67
68
Apéndice B. Apéndice
Figura B.25: Grá ca de convergencia de la función C04
Figura B.26: Grá ca de convergencia de la función C05
B.2. Grá cas de convergencia CEC2010 dimensión 10
Figura B.27: Grá ca de convergencia de la función C06
Figura B.28: Grá ca de convergencia de la función C07
69
70
Apéndice B. Apéndice
Figura B.29: Grá ca de convergencia de la función C08
Figura B.30: Grá ca de convergencia de la función C09
B.2. Grá cas de convergencia CEC2010 dimensión 10
Figura B.31: Grá ca de convergencia de la función C10
Figura B.32: Grá ca de convergencia de la función C11
71
72
Apéndice B. Apéndice
Figura B.33: Grá ca de convergencia de la función C12
Figura B.34: Grá ca de convergencia de la función C13
B.2. Grá cas de convergencia CEC2010 dimensión 10
Figura B.35: Grá ca de convergencia de la función C14
Figura B.36: Grá ca de convergencia de la función C15
73
74
Apéndice B. Apéndice
Figura B.37: Grá ca de convergencia de la función C16
Figura B.38: Grá ca de convergencia de la función C17
B.2. Grá cas de convergencia CEC2010 dimensión 10
Figura B.39: Grá ca de convergencia de la función C18
75
76
Apéndice B. Apéndice
B.3. Grá cas de convergencia CEC2010 dimensión 30
Figura B.40: Grá ca de convergencia de la función C01
B.3. Grá cas de convergencia CEC2010 dimensión 30
Figura B.41: Grá ca de convergencia de la función C02
Figura B.42: Grá ca de convergencia de la función C03
77
78
Apéndice B. Apéndice
Figura B.43: Grá ca de convergencia de la función C07
Figura B.44: Grá ca de convergencia de la función C08
B.3. Grá cas de convergencia CEC2010 dimensión 30
Figura B.45: Grá ca de convergencia de la función C09
Figura B.46: Grá ca de convergencia de la función C10
79
80
Apéndice B. Apéndice
Figura B.47: Grá ca de convergencia de la función C12
Figura B.48: Grá ca de convergencia de la función C13
B.3. Grá cas de convergencia CEC2010 dimensión 30
Figura B.49: Grá ca de convergencia de la función C14
Figura B.50: Grá ca de convergencia de la función C15
81
82
Apéndice B. Apéndice
Figura B.51: Grá ca de convergencia de la función C16
Figura B.52: Grá ca de convergencia de la función C17
B.3. Grá cas de convergencia CEC2010 dimensión 30
Figura B.53: Grá ca de convergencia de la función C18
83
Apéndice C
Apéndice C.1. Detalle de las funciones del CEC2006 g01
The details of the
24 test problems utilized in this work are the following:
Minimize:
f (~ x) = 5
4 X i=1
xi − 5
4 X i=1
x2i −
13 X
xi
(C.1)
i=5
Subject to:
g1 (~ x) = 2x1 + 2x2 + x10 + x11 − 10 ≤ 0 g2 (~ x) = 2x1 + 2x3 + x10 + x12 − 10 ≤ 0 g3 (~ x) = 2x2 + 2x3 + x11 + x12 − 10 ≤ 0 g4 (~ x) = −8x1 + x10 ≤ 0 g5 (~ x) = −8x2 + x11 ≤ 0 g6 (~ x) = −8x3 + x12 ≤ 0 g7 (~ x) = −2x4 − x5 + x10 ≤ 0 g8 (~ x) = −2x6 − x7 + x11 ≤ 0 g9 (~ x) = −2x8 − x9 + x12 ≤ 0 0 ≤ xi ≤ 1 (i = 1, . . . , 9), 0 ≤ xi ≤ 100 (i = 10, 11, 12), and 0 ≤ x13 ≤ 1. The feasible x∗ = (1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1) where f (x∗ ) = -15. where g2 , g3 , g7 , g8 g9 are active constraints.
where
global optimum is located at
g1 ,
g02 Minimize:
P n cos4 (x ) − 2 Qn cos2 (x ) i i i=1 f (~ x) = − i=1 pPn 2 ixi i=1
(C.2)
Subject to:
Qn
g1 (~ x) = 0 .75 − x ≤0 i=1 i P n g2 (~ x) = x − 7.5n ≤ 0 i=1 i 85
86
Apéndice C. Apéndice
n = 20 and 0 ≤ xi ≤ 10 (i = 1, . . . , n). The best known solution is located at x? = (3.16246061572185, 3.12833142812967, 3.09479212988791, 3.06145059523469, 3.02792915885555, 2.99382606701730, 2.95866871765285, 2.92184227312450, 0.49482511456933, 0.48835711005490, 0.48231642711865, 0.47664475092742, 0.47129550835493, 0.46623099264167, 0.46142004984199, 0.45683664767217, 0.45245876903267, 0.44826762241853, 0.44424700958760, 0.44038285956317), with f (x∗ ) =?0.80361910412559. g1 is close to be active. where
g03 Minimize:
f (~ x) = −
√
n n Y
n
xi
(C.3)
i=1 Subject to:
h(~ x) =
n X
x2i − 1 = 0
i=1
√ n = 10 and 0 ≤ xi ≤ 1 (i = 1, . . . , n). The feasible global minimum is located at x∗i = 1/ n ∗ (i = 1, . . . , n) where f (x ) = -1.00050010001000.
where
g04 Minimize:
f (~ x) = 5.3578547x23 + 0.8356891x1 x5 + 37.293239x1 − 40792.141
(C.4)
Subject to:
g1 (~ x) g2 (~ x) g3 (~ x) g4 (~ x) g5 (~ x) g6 (~ x) where:
= 85.334407 + 0.0056858x2 x5 + 0.0006262x1 x4 − 0.0022053x3 x5 − 92 = −85.334407 − 0.0056858x2 x5 − 0.0006262x1 x4 + 0.0022053x3 x5 = 80.51249 + 0.0071317x2 x5 + 0.0029955x1 x2 + 0.0021813x23 − 110 = −80.51249 − 0.0071317x2 x5 − 0.0029955x1 x2 − 0.0021813x23 + 90 = 9.300961 + 0.0047026x3 x5 + 0.0012547x1 x3 + 0.0019085x3 x4 − 25 = −9.300961 − 0.0047026x3 x5 − 0.0012547x1 x3 − 0.0019085x3 x4 + 20
≤0 ≤0 ≤0 ≤0 ≤0 ≤0
78 ≤ x1 ≤ 102, 33 ≤ x2 ≤ 45, 27 ≤ xi ≤ 45 (i = 3, 4, 5). The feasible global optimum is x∗ = (78, 33, 29.9952560256815985, 45, 36.7758129057882073) where f (x∗ )=-30665.539. g6 are active constraints.
located at
g1
and
g05 Minimize:
f (~ x) = 3x1 + 0.000001x31 + 2x2 + (0.000002/3)x32
(C.5)
Subject to:
g1 (~ x) g2 (~ x) h3 (~ x) h4 (~ x) h5 (~ x)
= −x4 + x3 − 0.55 = −x3 + x4 − 0.55
≤0 ≤0
= 1000 sin(−x3 − 0.25) + 1000 sin(−x4 − 0.25) + 894.8 − x1 = 1000 sin(x3 − 0.25) + 1000 sin(x3 − x4 − 0.25) + 894.8 − x2 = 1000 sin(x4 − 0.25) + 1000 sin(x4 − x3 − 0.25) + 1294.8
=0 =0 =0
C.1. Detalle de las funciones del CEC2006
87
0 ≤ x1 ≤ 1200, 0 ≤ x2 ≤ 1200, −0.55 ≤ x3 ≤ 0.55, and −0.55 ≤ x4 ≤ 0.55. The best known x∗ =(679.945148297028709, 1026.06697600004691, 0.118876369094410433, −0.396233485215178266) where f (x∗ ) = 5126.4967140071.
where
solution is located at:
g06 Minimize:
f (~ x) = (x1 − 10)3 + (x2 − 20)3
(C.6)
Subject to:
g1 (~ x) g2 (~ x)
= −(x1 − 5)2 − (x2 − 5)2 + 100 = (x1 − 6)2 + (x2 − 5)2 − 82.81
≤0 ≤0
where 13 ≤ x1 ≤ 100 and 0 ≤ x2 ≤ 100. The feasible global optimum is located at: x∗ = (14.09500000000000064, 0.8429607892154795668) where f (x∗ ) = −6961.81387558015.
Both
constraints are active.
g07 Minimize:
f (~ x)
=
x21 + x22 + x1 x2 − 14x1 − 16x2 + (x3 − 10)2 + 4(x4 − 5)2 + (x5 − 3)2 + 2(x6 − 1)2 + 5x27 + 7(x8 − 11)2 + 2(x9 − 10)2 + (x10 − 7)2 + 45
(C.7)
Subject to:
g1 (~ x) g2 (~ x) g3 (~ x) g4 (~ x) g5 (~ x) g6 (~ x) g7 (~ x) g8 (~ x)
= −105 + 4x1 + 5x2 − 3x7 + 9x8 = 10x1 − 8x2 − 17x7 + 2x8 = −8x1 + 2x2 + 5x9 − 2x10 − 12 = 3(x1 − 2)2 + 4(x2 − 3)2 + 2x23 − 7x4 − 120 = 5x21 + 8x2 + (x3 − 6)2 − 2x4 − 40 = x21 + 2(x2 − 2)2 − 2x1 x2 + 14x5 − 6x6 = 0.5(x1 − 8)2 + 2(x2 − 4)2 + 3x25 − x6 − 30 = −3x1 + 6x2 + 12(x9 − 8)2 − 7x10
≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0
−10 ≤ xi ≤ 10 (i = 1, . . . , 10). The feasible global optimum is located at x∗ = (2.17199634142692, 2.3636830416034, 8.77392573913157, 5.09598443745173, 0.990654756560493, 1.43057392853463, 1.32164415364306, 9.82872576524495, 8.2800915887356, 8.3759266477347) where f (x∗ ) = 24.30620906818. g1 , g2 , g3 , g4 , g5 , and g6 are active constraints. where
g08 Minimize:
f (~ x) = −
sin3 (2πx1 ) sin(2πx2 ) x31 (x1 + x2 )
(C.8)
Subject to:
g1 (~ x) g2 (~ x)
= x21 − x2 + 1 = 1 − x1 + (x2 − 4)2
≤0 ≤0
where 0 ≤ x1 ≤ 10 and 0 ≤ x2 ≤ 10. The feasible global (1.22797135260752599, 4.24537336612274885) with f (x∗ ) = −0.0958250414180359.
optimum is located at:
x∗ =
88
Apéndice C. Apéndice
g09 Minimize:
f (~ x) = (x1 − 10)2 + 5(x2 − 12)2 + x43 + 3(x4 − 11)2 + 10x65 + 7x26 + x47 − 4x6 x7 − 10x6 − 8x7
(C.9)
Subject to:
g1 (~ x) g2 (~ x) g3 (~ x) g4 (~ x)
= −127 + 2x21 + 3x42 + x3 + 4x24 + 5x5 = −282 + 7x1 + 3x2 + 10x23 + x4 − x5 = −196 + 23x1 + x22 + 6x26 − 8x7 = 4x21 + x22 − 3x1 x2 + 2x23 + 5x6 − 11x7
≤0 ≤0 ≤0 ≤0
where −10 ≤ xi ≤ 10 (i = 1, . . . , 7). The feasible global optimum is located at:x∗ =(2.33049935147405174, 1.95137236847114592, −0.477541399510615805, 4.36572624923625874, −0.624486959100388983, 1.03813099410962173, 1.5942266780671519) with f (x∗ ) = 680.630057374402. g1 and g4 are active constraints.
g10 Minimize:
f (~ x) = x1 + x2 + x3
(C.10)
Subject to:
g1 (~ x) g2 (~ x) g3 (~ x) g4 (~ x) g5 (~ x) g6 (~ x)
= −1 + 0.0025(x4 + x6 ) = −1 + 0.0025(x5 + x7 − x4 ) = −1 + 0.01(x8 − x5 ) = −x1 x6 + 833.33252x4 + 100x1 − 83333.333 = −x2 x7 + 1250x5 + x2 x4 − 1250x4 = −x3 x8 + 1250000 + x3 x5 − 2500x5
≤0 ≤0 ≤0 ≤0 ≤0 ≤0
100 ≤ x1 ≤ 10000, 1000 ≤ xi ≤ 10000, (i = 2, 3), 10 ≤ xi ≤ 1000, (i = 4, . . . , 8). The feasix∗ = (579.306685017979589, 1359.97067807935605, 5109.97065743133317, 182.01769963061534, 295.601173702746792, 217.982300369384632, 286.41652592786852, 395.601173702746735) with f (x∗ ) = 7049.24802052867. g1 , g2 , and g3 are active constraints.
where
ble global optimum is located at
g11 Minimize:
f (~ x) = x21 + (x2 − 1)2
(C.11)
Subject to:
h(~ x) = x2 − x21 = 0 −1 ≤ x1 ≤ 1, −1 ≤ x2 ≤ 1. f (x∗ ) = 0.7499.
where: with
The feasible global optimum is located at:x∗
√ = (±1/ 2, 1/2)
g12 Minimize:
f (~ x) = − Subject to:
100 − (x1 − 5)2 − (x2 − 5)2 − (x3 − 5)2 100
(C.12)
C.1. Detalle de las funciones del CEC2006
89
g1 (~ x) = (x1 − p)2 + (x2 − q)2 + (x3 − r)2 − 0.0625 ≤ 0 0 ≤ xi ≤ 10 (i = 1, 2, 3) and p, q, r = 1, 2, . . . , 9. The feasible region consists on 93 disjoint (x1 , x2 , x3 ) is feasible if and only if there exist p, q, r such that the above inequaholds. The feasible global optimum is located at x∗ = (5, 5, 5) with f (x∗ ) = −1.
where
spheres. A point lity
90
Apéndice C. Apéndice
g13 Minimize:
f (~ x) = ex1 x2 x3 x4
(C.13)
Subject to:
h1 (~ x) h2 (~ x) h3 (~ x)
= x21 + x22 + x23 + x24 + x25 − 10 = x2 x3 − 5x4 x5 = x31 + x32 + 1
=0 =0 =0
−2.3 ≤ xi ≤ 2.3 (i = 1, 2) and −3.2 ≤ xi ≤ 3.2 (1 = 3, 4, 5). The feasible global optimum is x~∗ = (−1.71714224003, 1.59572124049468, 1.8272502406271, −0.763659881912867, −0.76365986736498) ~∗ ) = 0.053941514041898. with f (x where at
g14 Minimize:
f (~ x) =
10 X i=1
xi
ci + ln
!
xi
P10 j=1
(C.14)
xj
Subject to:
h1 (~ x) h2 (~ x) h3 (~ x)
= x1 + 2x2 + 2x3 + x6 + x10 − 2 = x4 + 2x5 + x6 + x7 − 1 = x3 + x7 + x8 + 2x9 + x10 − 1
=0 =0 =0
where 0 < xi ≤ 10 (i = 1, ..., 10), and c1 = -6.089, c2 = -17.164, c3 = -34.054, c4 = -5.914, c5 = -24.721, c6 = -14.986, c9 = -26.662, c10 = -22.179. The best known solution is at x∗ = (0.0406684113216282, 0.147721240492452, 0.783205732104114, 0.00141433931889084, 0.485293636780388, 0.000693183051556082, 0.0274052040687766, 0.0179509660214818, 0.0373268186859717, 0.0968844604336845) with f (x∗ ) = −47.7648884594915.
g15 Minimize:
f (~ x) = 1000 − x21 − 2x22 − x23 − x1 x2 − x1 x3
(C.15)
Subject to:
h1 (~ x) h2 (~ x)
= x21 + x22 + x23 − 25 = 8x1 + 14x2 + 7x3 − 56
=0 =0
0 ≤ xi ≤ 10 (i = 1, 2, 3). The best known solution is at x∗ = (3.51212812611795133, 0.216987510429556135, 3.55217854929179921) with f (x∗ ) = 961.715022289961. where
g16 Minimize:
f (~ x)
=
0.000117y14 + 0.1365 + 0.00002358y13 + 0.000001502y16 + 0.0321y12 + 0.004324y5 + 0.0001 cc15 16 + 37.48 cy2 − 0.0000005843y17 12
(C.16)
C.1. Detalle de las funciones del CEC2006
91
Subject to:
g1 (~ x) g2 (~ x) g3 (~ x) g4 (~ x) g5 (~ x) g6 (~ x) g7 (~ x) g8 (~ x) g9 (~ x) g10 (~ x) g11 (~ x) g12 (~ x) g13 (~ x) g14 (~ x) g15 (~ x) g16 (~ x) g17 (~ x) g18 (~ x) g19 (~ x) g20 (~ x) g21 (~ x) g22 (~ x) g23 (~ x) g24 (~ x) g25 (~ x) g26 (~ x)
g27 (~ x) g28 (~ x) g29 (~ x) g30 (~ x) g31 (~ x) g32 (~ x) g33 (~ x) g34 (~ x) g35 (~ x) g36 (~ x) g37 (~ x) g38 (~ x)
where
y − y4 = 00..28 72 5 = x3 − 1.5x2 = 3496 cy2 − 21 12 = 110.6 + y1 − 62212 c17 = 213.1 − y1 = y1 − 405.23 = 17.505 − y2 = y2 − 1053.6667 = 11.275 − y3 = y3 − 35.03 = 214.228 − y4 = y4 − 665.585 = 7.458 − y5 = y5 − 584.463 = 0.961 − y6 = y6 − 265.916 = 1.612 − y7 = y7 − 7.046 = 0.146 − y8 = y8 − 0.222 = 107.99 − y9 = y9 − 273.366 = 922.693 − y10 = y10 − 1286.105 = 926.832 − y11 = y11 − 1444.046
= 18.766 − y12 = y12 − 537.141 = 1072.163 − y13 = y13 − 3247.039 = 8961.448 − y14 = y14 − 26844.086 = 0.063 − y15 = y15 − 0.386 = 71084.33 − y16 = −140000 + y16 = 2802713 − y17 = y17 − 12146108
≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0
≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0
92
Apéndice C. Apéndice
y1 = x2 + x3 + 41.6 c1 = 0.024x4 − 4.62 .5 + 12 y2 = 12 c1 c2 = 0.0003535x21 + .5311x1 + 0.08705y2 x1 c3 = 0.052x1 + 78 + 0.002377y2 x1 y3 = cc2 3 y4 = 19y3 0.1956(x −y )2
1 3 c4 = 0.04782(x1 − y3 ) + + 0.6376y4 + 1.594y3 x2 c5 = 100x2 c 6 = x1 − y3 − y4 c7 = 0.950 − cc4 5 y5 = c6 c7 y6 = x1 − y5 − y4 − y3 c8 = (y5 + y4 )0.995 y7 = yc8 1 c 8 y8 = 3798 7 c9 = y7 − 0.0663y − 0.3153 y8 96.82 y9 = c + 0.321y1 9 y10 = 1.29y5 + 1.258y4 + 2.29y3 + 1.71y6 y11 = 1.71x1 − 0.452y4 + 0.580y3 12.3 c10 = 752 .3 c11 = (1.75y2 )(0.995x1 ) c12 = 0.995y10 + 1998 y12 = c10 x1 + cc11 12 y13 = c12 + 1.75y2 y14 = 3623 + 64.4x2 + 58.4x3 + 146312 y9 +x5 c13 = 0.995y10 + 60.8x2 + 48x4 − 0.1121y14 − 5095 y15 = yc13 13 y16 = 148000 − 331000y15 + 40y13 − 61y15 y13 c14 = 2324y10 − 28740000y2 y17 = 14130000 − 1328y10 − 531y11 + cc14 12 c15 = yy13 − 0y.13 52 15 c16 = 1.104 − 0.72y15 c17 = y9 + x5
704.4148 ≤ x1 ≤ 906.3855, 68.6 ≤ x2 ≤ 288.88, 0 ≤ x3 ≤ 134.75, 193 ≤ x4 ≤ 287.0966, 25 ≤ x5 ≤ 84.1988.
and where and
The best known solution is at: x∗ = (705.174537070090537, 68.5999999999999943, 102.899999999999991, 282.324931593660324, 37.5841164258054832) with f (x∗ ) = −1.90515525853479.
g17 Minimize:
f (~ x) = f (x1 ) + f (x2 )
(C.17)
C.1. Detalle de las funciones del CEC2006
93
where
f1 (x1 ) =
n
30x1 31x1
0 ≤ x1 < 300 300 ≤ x1 < 400
(
28x2 29x2 30x2
0 ≤ x2 < 100 100 ≤ x2 < 200 200 ≤ x2 < 1000
f2 (x2 ) =
Subject to:
h1 (~ x) = −x1 + 300 −
x3 x4 131.078
cos(1.48477 − x6 ) +
0.90798x2 3 131.078
cos(1.47588)
h2 (~ x) = −x2 −
x3 x4 131.078
cos(1.48477 + x6 ) +
0.90798x2 4 131.078
cos(1.47588)
h3 (~ x) = −x5 −
x3 x4 131.078
sin(1.48477 + x6 ) +
0.90798x2 4 131.078
sin(1.47588)
h4 (~ x) = 200 −
x3 x4 131.078
sin(1.48477 − x6 ) +
0.90798x2 4 131.078
sin(1.47588)
0 ≤ x1 ≤ 400, 0 ≤ x2 ≤ 1000, 340 ≤ x3 ≤ 420, 340 ≤ x4 ≤ 420, −1000 ≤ x5 ≤ 1000, 0 ≤ x6 ≤ 0.5236. The best known solution is at x∗ = (201.784467214523659, 99.9999999999999005, 383.071034852773266, 420, −10.9076584514292652, 0.0731482312084287128) with f (x∗ ) = 8853.53967480648.
and where and
g18 Minimize:
f (~ x) = −0.5(x1 x4 − x2 x3 + x3 x9 − x5 x9 + x5 x8 − x6 x7 )
(C.18)
Subject to:
g1 (~ x) g2 (~ x) g3 (~ x) g4 (~ x) g5 (~ x) g6 (~ x)
= x23 + x24 − 1 = x29 − 1 = x25 + x26 − 1 = x21 + (x2 − x9 )2 − 1 = (x1 − x5 )2 + (x2 − x6 )2 − 1 = (x1 − x7 )2 + (x2 − x8 )2 − 1
≤0 ≤0 ≤0 ≤0 ≤0 ≤0
g7 (~ x) g8 (~ x) g9 (~ x) g10 (~ x) g11 (~ x) g12 (~ x) g13 (~ x)
= (x3 − x5 )2 + (x4 − x6 )2 − 1 = (x3 − x7 )2 + (x4 − x8 )2 − 1 = x27 + (x8 − x9 )2 − 1 = x2 x3 − x1 x4 = −x3 x9 = x5 x9 = x6 x7 − x5 x8
≤0 ≤0 ≤0 ≤0 ≤0 ≤0 ≤0
where −10 ≤ xi ≤ 10 (i = 1, ..., 8) and 0 ≤ x9 ≤ 20. The best known solution is at: x∗ = (−0.657776192427943163, −0.153418773482438542, 0.323413871675240938, −0.946257611651304398, −0.657776194376798906, −0.753213434632691414, 0.323413874123576972, − 0.346462947962331735, 0.59979466285217542) with f (x∗ ) = −0.866025403784439.
g19 Minimize:
94
Apéndice C. Apéndice
f (~ x) =
5 5 X X
cij x(10+j) x(10+j) + 2
j=1 i=1
5 X
dj x3(10+j) −
10 X
bi xi
(C.19)
i=1
j=1
Subject to:
gj (~ x) = −2
P5
c x i=1 ij (10+i)
− ej +
P10 i=1
aij xi ≤ 0
j = 1, . . . , 5
~b = [-40, -2, -0.25, -4, -4, -1, -40, -60, 5, 1] and the remaining values are taken from Table 0 ≤ xi ≤ 10 (i = 1, . . . , 15). The best known solution is at x∗ = (1.66991341326291344e−17 , 3.95378229282456509e−16 , 3.94599045143233784, 1.06036597479721211e−16 , 3.2831773458454161, 9.99999999999999822, 1.12829414671605333e−17 , 1.2026194599794709e− 17, 2.50706276000769697e−15 , 2.24624122987970677e−15 , 0.370764847417013987, 0.278456024942955571, 0.523838487672241171, 0.388620152510322781, 0.298156764974678579) with f (x∗ ) = 32.6555929502463. where C.1,
j
1
2
3
4
5
ej c1j c2j c3j c4j c5j dj a1j a2j a3j a4j a5j a6j a7j a9j a10j
-15
-27
-36
-18
-12 -10
Tabla C.1:
30
-20
-10
32
-20
39
-6
-31
32
-10
-6
10
-6
-10
32
-31
-6
39
-20
-10
32
-10
-20
30
4
8
10
6
2
-16
2
0
1
0 2
0
-2
0
0.4
-3.5
0
2
0
0
0
-2
0
-4
-1
0
-9
-2
1
-2.8
2
0
-4
0
0
-1
-1
-1
-1
-1
1
2
3
4
5
1
1
1
1
1
Data set for test problem g19
g20 Minimize:
f (~ x) =
24 X i=1
Subject to:
ai xi
(C.20)
C.1. Detalle de las funciones del CEC2006
95
(xi +x(i+12) ) P ≤0 24
gi (~ x) =
j=1
(xi+3 +x(i+15) )
gi (~ x) =
P24 j=1
h1 (~ x) =
≤0
−
xj j=13 bj
P24
h13 (~ x) =
P24
h14 (~ x) =
P12
i=1
i = 4, 5, 6
xj +ei
x(i+12) bi+12
i = 1, 2, 3
xj +ei
40bi
ci xi P 12
xj j=1 bj
=0
i = 1, . . . , 12
xi − 1 = 0
x−i i=1 di
+k
P24
xi i=13 bi
− 1.671 = 0
i
ai
bi 4
ci
4di
ei
1
0.0693
44.094
123.7
31.244
0.1
2
0.0577
58.12
31.7
36.12
0.3
3
0.05
58.12
45.7
34.784
0.4
4
0.2
137.4
14.7
92.7
0.3
5
0.26
120.9
84.7
82.7
0.6
6
0.55
170.9
27.7
91.6
0.3
7
0.06
62.501
49.7
56.708 82.7
8
0.1
84.94
7.1
9
0.12
133.425
2.1
80.8
10
0.18
82.507
17.7
64.517
11
0.1
46.07
0.85
49.4
12
0.09
60.097
0.64
49.1
13
0.0693
44.094
14
0.5777
6
15
0.05
58.12
16
0.2
137.4
17
0.26
120.9
18
0.55
170.9
19
0.06
62.501
20
0.1
84.94
21
0.12
133.425
22
0.18
82.507
23
0.1
46.07
24
0.09
60.097
Tabla C.2:
58.12
Data set for test problem g20
where k = (0.7302)(530)(14.740) and the data set is detailed Table C.2. 0 ≤ xi ≤ 10 (i = 1, . . . , 24). The best known solution is at x∗ = (1.28582343498528086e−18 , 4.83460302526130664e−34 , 0, 0, 6.30459929660781851e−18 , 7.57192526201145068e−34 , 5.03350698372840437e−34 , 9.28268079616618064e−34 , 0, 1.76723384525547359e− 17, 3.55686101822965701e−34 , 2.99413850083471346e−34 , 0.158143376337580827, 2.29601774161699833e−19 , 1.06106938611042947e−18 , 1.31968344319506391e−18 , 0.530902525044209539, 0, 2.89148310257773535e−18 , 3.34892126180666159e−18 , 0, 0.310999974151577319, 5.41244666317833561e−05 , 4.84993165246959553e−16 ). This solution is slightly infeasible and no feasible solution has been reported so far.
g21 Minimize:
96
Apéndice C. Apéndice
f (~ x) = x1
(C.21)
Subject to:
g1 (~ x)
h1 (~ x) h2 (~ x)
= −x1 + 35x02.6 + 35x03.6
≤0
= −300x3 + 7500x5 − 7500x6 − 25x4 x5 + 25x4 x6 + x3 x4 = 100x2 + 155.365x4 + 2500x7 − x2 x4 − 24x4 x7 − 15536.5
h3 (~ x) h4 (~ x) h5 (~ x)
= −x5 + ln(−x4 + 900) = −x6 + ln(x4 + 300) = −x7 + ln(−2x4 + 700)
=0 =0
=0 =0 =0
where 0 ≤ x1 ≤ 1000, 0 ≤ x2 , x3 ≤ 40, 100 ≤ x4 ≤ 300, 6.3 ≤ x5 ≤ 6.7, 5.9 ≤ x6 ≤ 6.4, and 4.5 ≤ x7 ≤ 6.25. The best known solution is at: x∗ = (193.724510070034967, 5.56944131553368433e−27 , 17.3191887294084914, 100.047897801386839, 6.68445185362377892, 5.99168428444264833, 6.21451648886070451) with f (x∗ ) = 193.724510070035.
g22 Minimize:
f (~ x) = x1
(C.22)
Subject to:
g1 (~ x) h1 (~ x) h2 (~ x) h3 (~ x) h4 (~ x) h5 (~ x) h6 (~ x) h7 (~ x) h8 (~ x) h9 (~ x) h10 (~ x) h11 (~ x)
h12 (~ x) h13 (~ x) h14 (~ x) h15 (~ x) h16 (~ x) h17 (~ x) h18 (~ x) h19 (~ x)
= −x1 + x20.6 + x03.6 x04.6 = x5 − 100000x8 + 1 ∗ 107 = x6 − 100000x8 − 100000x9 = x7 − 100000x9 − 5 ∗ 107 = x5 − 100000x10 − 3.3 ∗ 107 = x6 − 100000x11 − 4.4 ∗ 107 = x7 − 100000x12 − 6.6 ∗ 107 = x5 − 120x2 x13 = x6 − 80x3 x14 = x7 − 40x4 x15 = x8 − x11 + x16 = x9 − x12 + x17
≤0 =0 =0 =0 =0 =0 =0 =0 =0 =0 =0 =0
= −x18 + ln(x10 − 100) = −x19 + ln(−x8 + 300) = −x20 + ln(x16 ) = −x21 + ln(−x9 + 400) = −x22 + ln(x17 ) = −x8 − x10 + x13 x18 − x13 x19 + 400 = x8 − x9 − x11 + x14 x20 − x14 x21 + 400 = x9 − x12 − 4.60517x15 + x15 x22 + 100
=0 =0 =0 =0 =0 =0 =0 =0
0 ≤ x1 ≤ 20000, 0 ≤ x2 , x3 , x4 ≤ 1 ∗ 106 , 0 ≤ x5 , x6 , x7 ≤ 4 ∗ 107 , 100 ≤ x8 ≤ 299.99, 100 ≤ x9 ≤ 399.99, 100.01 ≤ x10 ≤ 300, 100 ≤ x11 ≤ 400, 100 ≤ x12 ≤ 600, 0 ≤ x13 , x14 , x15 ≤ 500, 0.01 ≤ x16 ≤ 300, 0.01 ≤ x17 ≤ 400, −4.7 ≤ x18 , x19 , x20 , x21 , x22 ≤ 6.25. The best known solution is at: x∗ = (236.430975504001054, 135.82847151732463, 204.818152544824585, 6446.54654059436416, 3007540.83940215595, 4074188.65771341929, 32918270.5028952882, 130.075408394314167, 170.817294970528621, 299.924591605478554, 399.258113423595205, 330.817294971142758, 184.51831230897065, 248.64670239647424, 127.658546694545862, 269.182627528746707, where
C.2. Detalle de las funciones del CEC2010
97
160.000016724090955, 5.29788288102680571, 5.13529735903945728, 5.59531526444068827, 5.43444479314453499, 5.07517453535834395) with f (x∗ ) = 236.430975504001.
g23 Minimize:
f (~ x) = −9x5 − 15x8 + 6x1 + 16x2 + 10(x6 + x7 )
(C.23)
Subject to:
g1 (~ x) g2 (~ x) h1 (~ x) h2 (~ x) h3 (~ x) h4 (~ x)
= x9 x3 + 0.02x6 − 0.025x5 = x9 x4 + 0.02x7 − 0.015x8 = x1 + x2 − x3 − x4 = 0.03x1 + 0.01x2 − x9 (x3 + x4 ) = x3 + x6 − x5 = x4 + x7 − x8
≤0 ≤0 =0 =0 =0 =0
0 ≤ x1 , x2 , x6 ≤ 300, 0 ≤ x3 , x5 , x7 ≤ 100, 0 ≤ x4 , x8 ≤ 200, and 0.01 ≤ x9 ≤ 0.03. The best = (0.00510000000000259465, 99.9947000000000514, 9.01920162996045897e−18 , 99.9999000000000535, 0.000100000000027086086, 2.75700683389584542e−14 , 99.9999999999999574, 2000.0100000100000100008) with f (x∗ ) = −400.055099999999584.
where
known solution is at:x∗
g24 Minimize:
f (~ x) = −x1 − x2
(C.24)
Subject to:
g1 (~ x) g2 (~ x) where
0 ≤ x1 ≤ 3
17849307411774)
and with
= −2x41 + 8x31 − 8x21 + x2 − 2 = −4x41 + 32x31 − 88x21 + 96x1 + x − 2 − 36
0 ≤ x2 ≤ 4.
The feasible global minimum is at:x∗
f (x∗ ) = −5.50801327159536.
≤0 ≤0 = (2.329520197477623,
This problem has a feasible region consisting
on two disconnected sub-regions.
C.2. Detalle de las funciones del CEC2010 C01
The details of the
18 test problems utilized in this work are the following:
Minimize:
PD Q 2 (z ) i=1 cos4 (zi ) − 2 D cos i i=1 f (~ x) = − qP D izi2 i=1
Subject to:
g1 (~ x) = 0.75 −
PD
QD
z i=1 i
≤0
g2 (~ x) = −7.5D ≤ 0 i=1 x ∈ [0, 10]D
z =x−o
(C.25)
98
Apéndice C. Apéndice
C02 Minimize:
z = x − o, y = z − 0.5
f (~ x) = max(z)
(C.26)
Subject to:
PD 2 1 [z − 10 cos(2πzi ) + 10] ≤ 0 D i=1 i P D 1 2 − 10 cos(2πz ) + 10] − 15 ≤ 0 g2 (~ x) = D [z i PDi=1 2i 1 g1 (~ x) = 10 −
[y − 10 cos(2πyi ) + 10] − 20 = 0 h(~ x) = D i=1 i x ∈ [−5.12, 5.12]D
C03 Minimize:
D−1
f (~ x) =
X
(100(zi2 − zi+1 )2 )
z =x−o
(C.27)
i=1 Subject to:
PD−1
h(~ x) = (zi − zi+1 )2 = 0 i=1 x ∈ [−1000, 1000]D
C04 Minimize:
f (~ x) = max(z)
z =x−o
(C.28)
Subject to:
p PD (zi cos( |zi |)) = 0 i=1 PD/2−1 h2 (~ x) = (zi − zi+1 )2 = 0 Pi=1 D−1 h3 (~ x) = (zi2 − zi+1 )2 = 0 Pi=D/2+1 D h1 (~ x) =
1 D
h4 (~ x) = z=0 i=1 x ∈ [−50, 50]D
C05 Minimize:
f (~ x) = max(z)
z =x−o
Subject to:
h1 (~ x) =
1 D 1 D
p PD (−zi sin( |zi |)) = 0 p Pi=1 D
h2 (~ x) = (−zi cos(0.5 i=1 x ∈ [−600, 600]D
|zi |)) = 0
(C.29)
C.2. Detalle de las funciones del CEC2010
99
C06 Minimize:
f (~ x) = max(z)
(C.30)
z = x − o, y = (x + 4.83.6106156535 − o)M − 483.6106156535 Subject to:
1 D 1 D
h1 (~ x) =
p PD (−yi sin( |yi |)) = 0 i=1 p PD
(−yi cos(0.5 h2 (~ x) = i=1 x ∈ [−600, 600]D
|yi |)) = 0
C07 Minimize:
D−1
f (~ x) =
X
(100(zi2 − zi+1 )2 + (zi − 1)2 )
(C.31)
i=1
z = x + 1 − o, y = x − o Subject to:
q
g(~ x) = 0.5 − exp(−0.1
1 D
PD i=1
1 yi2 ) − 3exp( D
PD i=1
cos(0.1y)) + exp(1) ≤ 0
x ∈ [−140, 140]D
C08 Minimize:
D−1
f (~ x) =
X
(100(zi2 − zi+1 )2 + (zi − 1)2 )
i=1
z = x + 1 − o, y = (x − o)M Subject to:
q
g(~ x) = 0.5 − exp(−0.1 x ∈ [−140, 140]D
C09 Minimize:
1 D
PD i=1
1 yi2 ) − 3exp( D
PD i=1
cos(0.1y)) + exp(1) ≤ 0
(C.32)
100
Apéndice C. Apéndice
D−1
f (~ x) =
X
(100(zi2 − zi+1 )2 + (zi − 1)2 )
(C.33)
i=1
z = x + 1 − o, y = x − o Subject to:
PD
h(~ x) = (y sin( i=1 x ∈ [−500, 500]D
p
|yi |)) = 0
C10 Minimize:
D−1
f (~ x) =
X
(100(zi2 − zi+1 )2 + (zi − 1)2 )
(C.34)
i=1
z = x + 1 − o, y = (x − o)M Subject to:
h(x) =
PD i=1
p
(y sin(
|yi |) = 0
x ∈ [−500, 500]D
C11 Minimize:
f (~ x) =
1 D
D X
p
(−zi cos(2
|zi |))
(C.35)
i=1
z = (x − o)M, y = x + 1 − o Subject to:
h(x) =
PD−1 i=1
(100(yi2 − yi+1 )2 + (yi − 1)2 ) = 0
x ∈ [−100, 100]D
C12 Minimize:
f (~ x) =
D X
(zi sin(
i=1
z =x−o
p
|zi |))
(C.36)
C.2. Detalle de las funciones del CEC2010
101
Subject to:
h(~ x) =
PD−1
g(~ x) =
PD
i=1
i=1
(z 2 − zi+1 )2 = 0
(z − 100 cos(0.1z) + 10) ≤ 0
x ∈ [−1000, 1000]D
C13 Minimize:
f (~ x) =
1 D
D X
(−zi sin(
p
|zi |))
(C.37)
i=1
z =x−o Subject to:
g1 (~ x) = −50 + g2 (~ x) =
50 D
1 100D
PD i=1
PD i
zi2 ≤ 0
1 sin( 50 πz) ≤ 0 zi2 i=1 4000
PD
g3 (~ x) = 75 − 50( x∈
QD
−
i=1
zi cos( √ ) + 1) ≤ 0 i
[−500, 500]D
C14 Minimize:
D−1
f (~ x) =
X
(100(zi2 − zi+1 )2 + (zi − 1)2 )
(C.38)
i=1
z = x + 1 − o, y = x − o Subject to:
g1 (~ x) =
PD
g2 (~ x) =
PD
g3 (~ x) =
PD
i=1
i=1
i=1
p
(−yi cos( (yi cos( (yi sin(
p
p
|yi |)) − D ≤ 0
|yi |)) − D ≤ 0
|yi |)) − 10D ≤ 0
x ∈ [−1000, 1000]D
C15 Minimize:
D−1
f (~ x) =
X i=1
(100(zi2 − zi+1 )2 + (zi − 1)2 )
(C.39)
102
Apéndice C. Apéndice
z = x + 1 − o, y = (x − o)M Subject to:
g1 (~ x) =
PD
g2 (~ x) =
PD
g3 (~ x) =
PD
p
i=1
i=1
i=1
(−yi cos( (yi cos( (yi sin(
|yi |)) − D ≤ 0
p
|yi |)) − D ≤ 0
p
|yi |)) − 10D ≤ 0
x ∈ [−1000, 1000]D
C16 Minimize:
f (~ x) =
D X zi2
4000
−
D Y i=1
i=1
zi cos( √ ) + 1 i
(C.40)
z =x−o Subject to:
g1 (~ x) =
PD
g2 (~ x) =
QD
h1 (~ x) =
PD
h2 (~ x) =
PD
i=1
zi2 − 100 cos(πz) + 10 ≤ 0 ≤0
z i=1 i i=1
i=1
p
(zi sin(
(−zi sin(
|zi |)) = 0
p
|zi |)) = 0
x ∈ [−10, 10]D
C17 Minimize:
D−1
X
f (~ x) =
(zi − zi+1 )2
i=1
z =x−o Subject to:
g1 (~ x) =
QD
≤0
g1 (~ x) =
PD
≤0
h1 (~ x) =
PD
(zi sin(4
z i=1 i z i=1 i i=1
x ∈ [−10, 10]D
p
|zi |)) = 0
(C.41)
C.2. Detalle de las funciones del CEC2010
103
C18 Minimize:
D−1
f (~ x) =
X
(zi − zi+1 )2
i=1
z =x−o Subject to:
g(~ x) = h(~ x) =
1 D
PD
1 D
PD
i=1
(−zi sin(
i=1
x ∈ [−50, 50]D
(zi sin(
p
p
|zi |)) ≤ 0
|zi |)) = 0
(C.42)
Referencias La autoeducación es, estoy convencido, el único tipo de educación que existe Issac Asimov [1] G. V. R. A. Ravindran, K. M. Ragsdell.
tions, 2nd Edition.
Engineering Optimization: Methods and Applica-
Wiley, 2nd edition, may 2006.
[2] B. Akay and D. Karaboga.
Arti cial bee colony algorithm for large-scale problems and
engineering design optimization.
Journal of Intelligent Manufacturing,
23(4):10011014,
2012. [3] A. Alizadegan, B. Asady, and M. Ahmadpour. Two modi ed versions of arti cial bee colony algorithm.
Applied Mathematics and Computation, 225(0):601 609, 2013.
The University of Chicago Press for The American Society of Naturalists, 30(354):441451, June 1896.
[4] J. M. Baldwin. A new factor in evolution.
[5] M. J. Box. A new method of constrained optimization and a comparison with other methods.
The Computer Journal, 8(1):4252, 1965.
[6] I. Brajevic, M. Tuba, and M. Subotic. Improved arti cial bee colony algorithm for constrai-
Proceedings of the 11th WSEAS international conference on nural networks and 11th WSEAS international conference on evolutionary computing and 11th WSEAS international conference on Fuzzy systems, NN'10/EC'10/FS'10, pages 185190, Stevens Point,
ned problems. In
Wisconsin, USA, 2010. World Scienti c and Engineering Academy and Society (WSEAS). [7] I. Brajevic, M. Tuba, and M. Subotic. Performance of the improved arti cial bee colony algorithm on standard engineering constrained problems.
Int J Math Comput Simul, 5(2):135
143, 2011. [8] K. Deb. An e cient constraint handling method for genetic algorithms.
in Applied Mechanics and Engineering, 186(24):311338, 2000.
[9] K. DEB.
Computer Methods
Optimization for Engineering Design: Algorithms and Examples.
PHI Learning,
2012. [10] A. P. Engelbrecht.
Fundamentals of Computational Swarm Intelligence.
John Wiley & Sons,
2006. [11] I. Fister, I. J. Fister, and J. B. Zumer. Memetic arti cial bee colony algorithm for large-scale global optimization. In
Evolutionary Computation (CEC), 2012 IEEE Congress on,
pages
18, June 2012. [12] W. E. Hart and R. K. Belew. Adaptive individuals in evolving populations. chapter Optimization with Genetic Algorithm Hybrids That Use Local Searches, pages 483496. AddisonWesley Longman Publishing Co., Inc., Boston, MA, USA, 1996.
105
106
Referencias
[13] G. E. Hinton and S. J. Nowlan. Adaptive individuals in evolving populations. In R. K. Belew and M. Mitchell, editors,
Adaptive individuals in evolving populations, chapter How learning
can guide evolution, pages 447454. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1996. [14] R. Hooke and T. A. Jeeves. direct search solution of numerical and statistical problems.
J. ACM, 8(2):212229, Apr. 1961.
[15] E. M. M. M. C. P. S. C. C. C. K. D. J.J. Liang, T. Runarsson.
Problem de nitions and
evaluation criteria for the cec 2006 special session on constrained real-parameter optimization. Technical report, Nanyang Technological University, Singapore, December 2005. [16] F. Kang, J. Li, Z. Ma, and H. Li.
Arti cial bee colony algorithm with local search for
Journal of Software, 6(3), 2011.
numerical optimization.
[17] D. Karaboga and B. Akay. A modi ed arti cial bee colony (abc) algorithm for constrained optimization problems.
Applied Soft Computing, 11(3):3021 3031, 2011.
[18] D. Karaboga and B. Basturk. A powerful and e cient algorithm for numerical function optimization: arti cial bee colony (abc) algorithm.
Journal of Global Optimization, 39(3):459
471, 2007. [19] D. Karaboga, B. Gorkemli, C. Ozturk, and N. Karaboga. A comprehensive survey: arti cial bee colony (abc) algorithm and applications.
Arti cial Intelligence Review, pages 137, 2012.
[20] J. Kennedy and w. Y. S. Russell C. Eberhart.
Swarm Intelligence.
Morgan Kaufmann
publishers, 2001. [21] N. Krasnogor and J. Smith. A tutorial for competent memetic algorithms: model, taxonomy, and design issues.
IEEE Trans. Evolutionary Computation, 9(5):474488, 2005.
[22] M. López-Ibáñez, J. Dubois-Lacoste, T. Stützle, and M. Birattari. The irace package, iterated race for automatic algorithm con guration. Technical Report TR/IRIDIA/2011-004, IRIDIA, Université Libre de Bruxelles, Belgium, 2011. [23] E. Mezura-Montes and O. Cetina-Domínguez.
Empirical analysis of a modi ed arti cial
bee colony for constrained numerical optimization.
Applied Mathematics and Computation,
218(22):10943 10973, 2012. [24] E. Mezura-Montes and R. Velez-Koeppel. Elitist arti cial bee colony for constrained realparameter optimization.
In
Evolutionary Computation (CEC), 2010 IEEE Congress on,
pages 18, 2010. [25] Z. Michalewicz and M. Schoenauer. Evolutionary algorithms for constrained parameter optimization problems.
Evolutionary Computation, 4:132, 1996.
New Optimization TechniStudies in Fuzziness and Soft Computing, pages 5385.
[26] P. Moscato, C. Cotta, and A. Mendes. Memetic algorithms. In
ques in Engineering,
volume 141 of
Springer Berlin Heidelberg, 2004. [27] F. Neri and C. Cotta. Memetic algorithms and memetic computing optimization: A literature review.
Swarm and Evolutionary Computation, 2(0):1 14, 2012.
[28] F. Neri, J. Toivanen, G. L. Cascella, and Y.-S. Ong. for designing hiv multidrug therapies.
An adaptive multimeme algorithm
IEEE/ACM Trans. Comput. Biology Bioinform.,
4(2):264278, 2007. [29] Y.-S. Ong, M.-H. Lim, and X. Chen. Memetic computation past, present, future [research frontier].
Computational Intelligence Magazine, IEEE, 5(2):2431, 2010.
[30] P. N. S. R. Mallipeddi. Problem de nitions and evaluation criteria for the cec 2010 competition on constrained real-parameter optimization. Technical report, Nanyang Technological University, Singapore, April 2010.
107
Referencias
[31] X. Shi, Y. Li, H. Li, R. Guan, L. Wang, and Y. Liang. An integrated algorithm based on
Natural Computation (ICNC), 2010 Sixth International Conference on, volume 5, pages 25862590, 2010. arti cial bee colony and particle swarm optimization. In
[32] R. Storn and K. Price.
Dierential evolution - a simple and e cient adaptive scheme for
global optimization over continuous spaces, 1995. [33] T. Takahama and S. Sakai. Constrained optimization by the constrained dierential evolution with an archive and gradient-based mutation. In
IEEE Congress on, pages 19, 2010.
Evolutionary Computation (CEC), 2010
[34] D. Whitley, V. Gordon, and K. Mathias. Lamarckian evolution, the baldwin eect and fun-
Parallel Problem Lecture Notes in Computer Science, pages
ction optimization. In Y. Davidor, H.-P. Schwefel, and R. Manner, editors,
Solving from Nature PPSN III,
volume 866 of
515. Springer Berlin Heidelberg, 1994. [35] F. Wilcoxon. Individual comparisons by ranking methods. 1(6):8083, Dec 1945.
International Biometric Society,