T abajo de Fin de G ado
Cu so 2023–2024
Gene alización de algo i mos de búsqueda
es ocás ica local po medio de mé odos de
ep esen ación conjun a de soluciones
Gene aliza ion o s ochas ic local sea ch algo i hms ia
me hods o common ep esen a ion o solu ions
Au o a
Sa a Vicen e A oyo
Di ec o es
Ismael Rod íguez Laguna
Fe nando Rubio Diez
Doble G ado en Ingenie ía In o má ica y Ma emá icas
Depa amen o de Sis emas In o má icos y Compu ación
Facul ad de In o má ica
Uni e sidad Complu ense de Mad id
Mad id, 13 de sep iemb e de 2024
A mis pad es, po aguan a mis llan os
du an e diez pe iodos de exámenes
consecu i os, y a mis compañe os, po hace los
mucho más lle ade os
iii
Ag adecimien os
Al D . Dama Wicaksono y al P o . D . Michael Hech , po su iempo y sus acla-
aciones sob e el undamen o eó ico y los de alles de implemen ación de la lib e ía
Min e py. Las con e saciones man enidas con ellos median e co eo elec ónico y
ideocon e encia han esul ado undamen ales a la ho a de encauza es e T abajo
de Fin de G ado.
A mis di ec o es, Ismael y Fe nando, po odo lo que he ap endido de ellos.

Resumen
Gene alización de algo i mos de búsqueda es ocás-
ica local po medio de mé odos de ep esen ación
conjun a de soluciones
Du an e las úl imas décadas, se ha p oducido un alu ión de con ibuciones al
campo de la compu ación e olu i a. Se han desa ollado algo i mos inspi ados en
odo ipo de especies na u ales, además de híb idos en e a ios de ellos. No obs-
an e, el compo amien o in ínseco de muchos es esencialmen e el mismo. Es o ha
pe mi ido di idi los en es g andes g upos: los que se pa ecen a los algo i mos ge-
né icos (GA), a los de enjamb e de pa ículas (PSO) y a los de colonia de ho migas
(ACO), espec i amen e. En es e abajo se da un paso más y se diseña un algo i mo
gene alizado al que pueden educi se odos. Además, se p opone una pa icula iza-
ción del mismo (AEMP) que cen a su a ención únicamen e en la dis ibución de
p obabilidad de las soluciones conside adas en cada momen o. Es e nue o algo i -
mo pe mi e c ea a ian es e híb idos en e ellas de o ma comple amen e di ec a,
sin necesidad de oma inspi ación en la na u aleza. Los expe imen os ealizados
en es e abajo mues an, además, que no exis en di e encias signi ica i as en e los
esul ados ob enidos po cie as a ian es de AEMP y mé odos clásicos como PSO
al en en a se a p oblemas de op imización NP-di íciles.
Palab as cla e
Compu ación e olu i a, algo i mos gené icos, algo i mos de enjamb e de pa ículas,
algo i mos de colonia de ho migas, op imización combina o ia, gene alización, dis-
ibuciones de p obabilidad, in e polación numé ica, p oblemas NP-di íciles, p uebas
no pa amé icas.
ii
Abs ac
Gene aliza ion o s ochas ic local sea ch algo i hms
ia me hods o common ep esen a ion o solu ions
O e he las decades, he e has been a lood o con ibu ions o he ield o
e olu iona y compu a ion. Algo i hms inspi ed in all kinds o na u al species ha e
been de eloped, as well as hyb ids be ween se e al o hem. Howe e , he in insic
beha io o many is essen ially he same. This has allowed au ho s o so hem
in o h ee la ge g oups: hose simila o gene ic algo i hms (GA), o pa icle swa m
op imiza ion (PSO) algo i hms and o an colony op imiza ion (ACO) algo i hms,
espec i ely. In his wo k, we go one s ep o wa d and design an algo i hm ha
gene alizes all o hem. Mo eo e , we p opose a pa icula iza ion o i (AEMP)
ha only ocuses on he p obabili y dis ibu ion o he solu ions conside ed a any
momen . This no el algo i hm allows us o c ea e a ian s and hyb ids be ween
hem in a way ha is comple ely di ec , wi hou he need o na u al inspi a ion.
Expe imen s conduc ed in his wo k also show ha no signi ican di e ence exis s
be ween esul s ob ained by ce ain AEMP a ian s and classical me hods such as
PSO when acing NP-ha d op imiza ion p oblems.
Keywo ds
E olu iona y compu a ion, gene ic algo i hms, pa icle swa m op imiza ion algo-
i hms, an colony op imiza ion algo i hms, combina o ial op imiza ion, gene al-
iza ion, p obabili y dis ibu ions, nume ical in e pola ion, NP-ha d p oblems, non-
pa ame ic es s.
ix

Capí ulo 1
In oducción
Du an e las úl imas décadas, cien os de algo i mos e olu i os han in adido la
li e a u a, inspi ados en odo ipo de especies, poblaciones o enómenos na u ales
(o no an na u ales). Ga os [6], del ines [49, 24], galaxias [37], bac e ias [36, 7, 32],
abejas [2, 22, 54], umo es [53], u bolis as [43, 44, 1] o incluso zombis [39] son an
solo algunas de las uen es de inspi ación o me á o as seleccionadas pa a ala ga
la lis a de in eg an es de es e pa adigma. Además, o os au o es han desa ollado
algo i mos híb idos, que consis en simplemen e en la aplicación consecu i a de los
ope ado es de unos y o os [23, 56].
En los úl imos años han su gido oces c í icas con la mencionada explosión de
con ibuciones al campo de la compu ación e olu i a. En 2015, Sö ensen [52] ins a
a analiza la dinámica subyacen e de odos es os algo i mos, sin dis ae se con las
pa icula idades de mé odos supues amen e inno ado es. Po su pa e, Molina e al.
[33] p oponen en 2020 una axonomía que clasi ica más de escien os de ellos en
únicamen e es g andes g upos, según su compo amien o eal (mo imien o de ec-
o di e encial,combinación de soluciones yes igme gia). A gumen an, además, que
dicho compo amien o es más ele an e que el enómeno biológico, social o na u al
en el que se inspi an.
El obje i o de es e abajo es da un paso más y de ini un algo i mo e olu i o
gene alizado al que puedan educi se odos ellos. De es a o ma, c ea lige as a ian-
es e incluso híb idos en e dis in as pa icula izaciones se á i ial y no eque i á
del desa ollo de odo un escena io me a ó ico nue o pa a cada pequeño cambio
en su mecánica subyacen e. Asimismo, se p e ende diseña e implemen a nue as
pa icula izaciones de dicho algo i mo capaces de en en a se a p oblemas de op i-
mización en los que esul e comple amen e p ohibi i o el uso de una simple búsqueda
exhaus i a. Más conc e amen e, p oblemas NP-di íciles de dimensión supe io a 30.
En base a los obje i os an edichos, se ha seguido el plan de abajo expues o a
con inuación, que cons a de una pa e eó ica y o a p ác ica.
En p ime luga , se ha es udiado en p o undidad la li e a u a ela i a a es
algo i mos bioinspi ados clásicos: los gené icos [21], los de enjamb e de pa ículas
[26] y los de colonia de ho migas [10]. Se a a de los ep esen an es indiscu ibles
de cada uno de los g upos en los que Molina e al. [33] clasi ican los algo i mos
1
2Capí ulo 1. In oducción
e olu i os. En el Capí ulo 3 se in oduce b e emen e al lec o a su uncionamien o.
A con inuación, se han explo ado abajos p e ios de gene alización o, al menos,
de alejamien o de me á o as y o as pa icula idades. Los algo i mos de es imación
de la dis ibución (EDA, po sus siglas en inglés) [28] cons uyen en cada i e ación
un modelo p obabilís ico que, como sugie e su nomb e, es ima la dis ibución de las
mejo es soluciones del p oblema de op imización co espondien e y pe mi e ob e-
ne nue as mues as según dicha dis ibución. Po o o lado, el algo i mo CMA-ES
(es a egia de e olución po adap ación de la ma iz de co a ianza) [19] ambién
u iliza el mues eo alea o io pa a di igi la búsqueda hacia las mejo es soluciones.
Asume que es as siguen una dis ibución no mal, cuyos pa áme os (media y ma iz
de co a ianza) se an ac ualizando i e a i amen e. En el Capí ulo 4 se apo a una
in oducción más de allada a los EDA y al algo i mo CMA-ES.
Al comienzo del Capí ulo 5 se p opone, po in, un algo i mo p opio capaz de
gene aliza odos los algo i mos e olu i os. Se basa en la exis encia de una a iable
alea o ia subyacen e que p i ilegia unas soluciones en e a o as (es deci , les asigna
una mayo o meno p obabilidad) y que se ac ualiza as cada i e ación.
La pa e p ác ica de es e abajo ha consis ido, en p ime luga , en la in es-
igación de dis in as écnicas de in e polación y mues eo pa a su uso en nue as
pa icula izaciones del algo i mo gene alizado, al y como se jus i ica en la Sección
5.2 del Capí ulo 5. Pa a ello, se ha con ac ado con expe os del ámbi o de la op i-
mización numé ica del Helmhol z-Zen um D esden-Rossendo (HZDR) en D esde,
Alemania, cuyos consejos han esul ado undamen ales pa a encauza las ideas de
diseño hacia algo i mos e dade amen e implemen ables.
Finalmen e, se ha desa ollado una pa icula ización del algo i mo gene alizado,
el algo i mo e olu i o po medias ponde adas (AEMP), que pone el oco en la dis-
ibución subyacen e de cada conjun o de soluciones conside adas. Se han diseñado
e implemen ado cua o a ian es del mismo de o ma comple amen e di ec a, sin
necesidad de de ini ope ado es o escena ios me a ó icos. Los esul ados ob enidos
as en en a dichas a ian es, así como los algo i mos clásicos, a p oblemas de
op imización NP-di íciles se p esen an y se discu en en el Capí ulo 6.
Capí ulo 2
P elimina es
En es e capí ulo se in oducen de iniciones que se án de u ilidad en los capí ulos
pos e io es, así como la no ación u ilizada.
2.1. Teo ía de la p obabilidad
De inición 2.1.1. Una a iable alea o ia sob e un espacio de p obabilidad Ωes
una unción X: Ω →Rnmedible.
2.2. Op imización
De inición 2.2.1. Dados un conjun o Θ⊂Rny una unción :Rn→R, de inimos
el p oblema de minimización como
minimiza (x)
suje o a x∈Θ
Decimos que Θes la egión ac ible, el espacio de búsqueda o el espacio de
soluciones del p oblema, y que es la unción obje i o.
De inición 2.2.2. Dados un conjun o Θ⊂Rny una unción :Rn→R, decimos
que x∈Rnes solución ac ible del p oblema de minimización si x∈Θ.
De inición 2.2.3. Dados un conjun o Θ⊂Rny una unción :Rn→R, decimos
que x∗∈Rnes solución óp ima del p oblema de minimización si es solución
ac ible y
(x∗)≤ (x)∀x∈Θ
Obse ación 2.2.4. El p oblema de maximización se de ine de o ma análoga.
De inición 2.2.5. Un p oblema de op imización combina o ia es un p oblema
de op imización (es deci , de minimización o de maximización) cuya egión ac ible
Θes un conjun o ini o.
3
Capí ulo 3
Algo i mos e olu i os clásicos
En es e capí ulo se esumen las ideas undamen ales sob e es de los algo i mos
e olu i os inspi ados en la na u aleza más impo an es de la li e a u a, como son
los algo i mos gené icos ( éase la Sección 3.1), los de enjamb e de pa ículas ( éase
la Sección 3.2) y los de colonia de ho migas ( éase la Sección 3.3). Se han elegido
es os es po se , de alguna mane a, los ep esen an es canónicos de cada una de
las ca ego ías en las que Molina e al. [33] di iden los algo i mos e olu i os: com-
binación de soluciones,mo imien o de ec o di e encial yes igme gia,
espec i amen e.
3.1. Algo i mos gené icos
Los algo i mos gené icos (gene ic algo i hms, GA) [21] oman su inspi ación en
la eo ía clásica de la e olución y la selección na u al [8]. Se emplean p incipalmen e
pa a esol e de o ma ap oximada un p oblema de op imización en Θ⊂Rn
op imiza (x)
suje o a x∈Θ
donde el espacio de soluciones o población Θpuede se con inuo o disc e o. Cada
solución ac ible x∈Θes un indi iduo y la unción obje i o :Rn→Ro unción
de i ness desc ibe cuán adap ado al medio se encuen a cada uno de ellos. Si el
p oblema es de maximización, los indi iduos xcon un al o alo de i ness (x)
se án las mejo es soluciones. Po el con a io, si el p oblema es de minimización,
busca emos indi iduos con ni eles bajos de i ness. Obse amos que x= (x1, . . . , xn)
es un ec o de ncomponen es. A menudo es e se in e p e a como un c omosoma
donde cada componen e es un gen.
El esquema gene al de un algo i mo gené ico cons a de es ases que se epi en
en cada i e ación. Dada una gene ación de indi iduos, es deci , un subconjun o
de Θ, se seleccionan aquellos mejo adap ados pa a da luga a la siguien e. Los
indi iduos seleccionados se c uzan dos a dos y así se o igina su descendencia, que
hab á he edado ca ac e ís icas de ambos. Finalmen e, al igual que en la na u aleza,
5

6Capí ulo 3. Algo i mos e olu i os clásicos
pueden p oduci se mu aciones, es deci , pequeños cambios en el genoma de los
nue os indi iduos.
Los ope ado es de selección, c uce y mu ación se de ini án de o ma dis in a
según el p oblema pa icula al que nos en en emos, y su aplicación se epe i á de
o ma i e a i a has a que se cumpla una cie a condición de pa ada. También se á
p eciso de ini la mane a en la que se elegi á la gene ación inicial de indi iduos,
habi ualmen e po mues eo alea o io.
3.1.1. Ope ado es
A lo la go de los años se han desa ollado mul i ud de ope ado es de selección,
c uce y mu ación dis in os. En es a sección se enume an los más ele an es, aunque
no se p o undiza en ellos. Sus espec i as de iniciones se pueden consul a en g an
can idad de uen es [p. ej. 13, Capí ulos 4-5].
Selección
Un conjun o de indi iduos es seleccionado pa a ansmi i sus genes a la siguien-
e gene ación, y los demás son desca ados. Po no ma gene al, es e ope ado se
de ine de o ma que asigne una meno , pe o no nula, p obabilidad de se escogidos a
aquellos con peo i ness. Algunos mé odos as amen e u ilizados son la denominada
selección po o neo, la selección po ule a y la basada en anking.
C uce
Los c omosomas seleccionados se conside an aho a p ogeni o es, y se apa ean
dos a dos. Cada pa eja da luga a dos nue os c omosomas hijos, de inidos como
una combinación de ambos. Los ope ado es de c uce más conocidos son los llamados
c uce de un pun o y c uce de dos pun os. No obs an e, ambién cabe des aca el
c uce uni o me [51], que da luga a una mayo a iabilidad gené ica.
Mu ación
Po úl imo, cada c omosoma es suscep ible de su i un pequeño cambio según
una p obabilidad de mu ación elegida. De es a o ma, nos asegu amos pode
explo a egiones del espacio de soluciones inaccesibles median e aplicaciones de los
o os dos ope ado es a la gene ación inicial de indi iduos. Mu aciones ípicas son el
cambio en el alo o en la posición de un gen, o la pe mu ación de dos.
3.1.2. Va ian es
La de inición de algo i mo gené ico y la de sus componen es se pueden adap a
a o os p oblemas de op imización, en los que el espacio de búsqueda no es á com-
pues o po ec o es numé icos sino po eco idos sob e g a os o pe mu aciones de
elemen os [16]. También exis en a ian es que eliminan la in uición de ep oducción
sexual. En ellas los nue os indi iduos no se gene an a pa i de dos p ogeni o es,
3.2. Algo i mos de enjamb e de pa ículas 7
sino po encialmen e a pa i de odo el ma e ial gené ico p esen e en la gene ación
p e ia [35].
3.2. Algo i mos de enjamb e de pa ículas
Los algo i mos de enjamb e de pa ículas (pa icle swa m op imiza ion, PSO)
[26] ienen un pun o en común undamen al con los algo i mos gené icos: en cada
i e ación de inen explíci amen e un conjun o de soluciones ac ibles del p oblema
op imiza (x)
suje o a x∈Θ
Se alejan, sin emba go, de ellos en la o ma de ob ene un nue o conjun o de solucio-
nes a pa i del an e io . Cada solución se isualiza en es e caso como una pa ícula
en mo imien o a a és del espacio de búsqueda, cuya posición se modi ica según su
p opia elocidad eine cia. Además, las pa ículas o man pa e de un enjamb e y
eciben in o mación sob e las mejo es soluciones halladas po las demás, de o ma
que es el enjamb e en su conjun o el que esuel e el p oblema de op imización. Es-
os algo i mos se inspi an en la na u aleza coope a i a obse ada en poblaciones de
de e minadas especies del eino animal, como enjamb es de abejas, bancos de peces
o bandadas de a es.
La no ación u ilizada a lo la go de es a sección es una adap ación de la empleada
po Do igo e al. [11].
De inición 3.2.1. Una pa ícula es un pa (x, )con x, ∈Rn. Llamamos a x
posición y a elocidad de la pa ícula p= (x, ).
De inición 3.2.2. Llamamos enjamb e a una upla o denada de pa ículas
(p1= (x1, 1), . . . , pm= (xm, m))
y denominamos opología del enjamb e a cualquie g a o G= (V={1, . . . , m}, E).
De inición 3.2.3. Dado un enjamb e de pa ículas con opología G, llamamos en-
o no o ecinda io de la pa ícula pi,N(i), al conjun o de é ices adyacen es de
ien G.
Obse ación 3.2.4. Las de iniciones de opología y de ecinda io dependen exclu-
si amen e de la posición que ocupa cada pa ícula en la upla. In ui i amen e, es o
nos pe mi i á segui la pis a de cada pa ícula indi idual a lo la go de su ayec o ia,
aunque sus coo denadas cambien.
Nos encon amos en posición de o maliza el algo i mo básico de enjamb e de
pa ículas [25]. En la i e ación conside amos un enjamb e
P = (p
1= (x
1,
1), . . . , p
m= (x
m,
m)) = (p
i= (x
i,
i))m
i=1
8Capí ulo 3. Algo i mos e olu i os clásicos
donde cada posición xies una solución ac ible del p oblema, y una cie a opología
Gsob e P . Conside amos ambién la upla
M = (b
1, . . . , b
m)
de las mejo es posiciones pa a cada pa ícula has a el momen o, es deci , M e i ica
que pa a odo i∈ {1, . . . , m}exis e ∗∈ {0, . . . , } al que
b
i=x ∗
iy (x ∗
i)≤ (xs
i)∀s∈ {0, . . . , }
si el p oblema es de minimización. Finalmen e, conside amos una e ce a upla
V = (l
1, . . . , l
m)
de las mejo es posiciones de los ecinos de cada pa ícula. Es o es, pa a un p oblema
de minimización, V e i ica que pa a odo i∈ {1, . . . , m}exis e j∈ N (i) al que
l
i=b
jy (l
i)≤ (b
k)∀k∈ N(i)
En la i e ación + 1 ac ualizamos el enjamb e de la siguien e mane a
P +1 = (p +1
i= (x +1
i, +1
i))m
i=1
donde
 +1
i=w
i+α1U
1(b
i−x
i) + α2U
2(l
i−x
i)
x +1
i=x
i+ +1
i
y la opología Gqueda ija.
El pa áme o w∈Rse denomina ine cia y los pa áme os α1yα2,coe icien es
de acele ación. Las ma ices U
1yU
2son diagonales y sus elemen os de la diagonal
se gene an alea o iamen e en cada i e ación según una dis ibución uni o me.
Podemos obse a que el desplazamien o de una pa ícula depende en esencia de
es ac o es. El é mino w
ies á elacionado con la ine cia o el momen o lineal, la
endencia de la pa ícula a con inua desplazándose en la misma di ección y sen ido.
El é mino α1U
1(b
i−x
i)es la componen e cogni i a omemo ís ica, que lle a a
la pa ícula de uel a hacia las mejo es posiciones que ha isi ado. Po úl imo, la
componen e α2U
2(l
i−x
i)es la social, que guía a la pa ícula hacia las mejo es
soluciones halladas po su en o no.
3.2.1. Va ian es
El p ime p oblema que sal a a la is a con el algo i mo clásico es la al a de
ga an ía de pe manece en la egión ac ible al a anza una i e ación. Po ello, exis en
a ian es en las que se adap a la elocidad de las pa ículas en pos de man ene la
ac ibilidad de las soluciones [14].
3.3. Algo i mos de colonia de ho migas 9
3.3. Algo i mos de colonia de ho migas
Los algo i mos de colonia de ho migas (an colony op imiza ion, ACO) [10] se
inspi an en el compo amien o colabo a i o, y a la ez dis ibuido, de es os insec os
en su búsqueda de alimen o. Cada una de ellas deja un as o de sus ancias químicas
denominadas e omonas po el camino seguido has a la uen e de sus en o y de uel a
al nido, que pos e io men e se i á de guía pa a o as ho migas de su colonia. Es a
o ma de coope ación y comunicación indi ec a a a és de modi icaciones en el
medio ísico se conoce como es igme gia. En es e pa adigma, a di e encia de los dos
an e io es, cada agen e u ho miga a i icial no ep esen a una solución de o ma
explíci a, sino que la cons uye i e a i amen e al eco e una cie a es uc u a de
da os.
En es e caso nos educimos a p oblemas de op imización combina o ia, es deci ,
op imiza (x)
suje o a x∈Θ
donde Θes un conjun o ini o. Más conc e amen e, si x= (x1, . . . , xn)∈Θ, cada a-
iable de decisión xipod á oma alo es en un conjun o ini o Vi={ i
1, i
2, . . . , i
Ni}.
Obse ación 3.3.1. El ecíp oco no es cie o. Es deci , un ec o x∈ V1× · · ·× Vn
no iene po qué se ac ible, puede habe es icciones adicionales. Un ejemplo son
los p oblemas de pe mu aciones, donde V1=· · · =Vn={ 1, 2, . . . , n}y no se
puede da xi=xjpa a i=j.
Las siguien es de iniciones pueden esul a poco in ui i as, sob e odo si se co-
noce p e iamen e el concep o de algo i mo de colonia de ho migas como mé odo de
op imización en g a os. Se incluyen po que son las que se u ilizan ípicamen e en
la li e a u a pa a in oduci es os algo i mos [12], pa a do a los de aplicabilidad en
la esolución de cualquie p oblema de op imización combina o ia. Al inal de es a
sección, no obs an e, se da una in e p e ación g á ica de es as de iniciones y se p o-
pone una al e na i a más na u al pa a p oblemas de g a os, que ue on la e dade a
mo i ación de es os algo i mos.
De inición 3.3.2. Dado un p oblema de op imización combina o ia, denominamos
componen e a una ins ancia de una a iable de decisión, xi= i
j.
De inición 3.3.3. Un g a o de cons ucción GC= (C, E)es un g a o comple o
al que Ces el conjun o de odas las componen es del p oblema. A los elemen os de
Elos llamamos conexiones.
De inición 3.3.4. Un es ado es una secuencia ini a de componen es. Además,
decimos que es un es ado ac ible si se puede comple a a una solución ac ible.
De inición 3.3.5. Si aes una conexión y s= (c0, c1, . . . , ck)es un es ado, decimos
que a o ma pa e de s, y lo deno amos po a⊑s, si a= (ci, ci+1)pa a algún
i∈ {0, . . . , k −1}.
De inición 3.3.6. Un as o de e omonas es una unción τ:E→R+.
16 Capí ulo 4. Algunos in en os de gene alización
x1x2x3x4x5x6 (x)
1 1 1 1 1 1 1 6
2 1 0 1 0 1 1 4
3 1 1 1 1 1 0 5
4 0 1 0 1 1 1 4
5 1 1 1 1 0 1 5
6 1 0 0 1 1 1 4
7 0 1 0 1 1 0 3
8 1 1 1 0 1 0 4
9 1 1 1 0 0 1 4
10 1 0 0 1 1 1 4
11 1 1 0 0 1 1 4
12 1 0 1 1 1 0 4
13 0 1 1 0 1 1 4
14 0 1 1 1 1 0 4
15 0 1 1 1 1 1 5
16 0 1 1 0 1 1 4
17 1 1 1 1 1 0 5
18 0 1 0 0 1 0 2
19 0 0 1 1 0 1 3
20 1 1 0 1 1 1 5
Tabla 4.3: Ejemplo de conjun o A1 omado de [28, Tabla 3.3].
desa ollado algo i mos de es imación de la dis ibución más complejos, capaces de
cap u a elaciones de dependencia en e pa es de a iables alea o ias. Des acan en
el ámbi o de la op imización disc e a los EDA que emplean edes bayesianas, es-
o es, g a os di igidos acíclicos, pa a cons ui un modelo p obabilís ico que es ime
p(x|B)y ob ene nue as mues as a pa i de él. Un ep esen an e impo an e de es-
e pa adigma es el BOA (Bayesian Op imiza ion Algo i hm) [42]. Pa a op imización
con inua, po su pa e, des acan algo i mos como el EGNA (Es ima ion o Gaussian
Ne wo ks Algo i hm) [29], que u ilizan edes gaussianas pa a cap u a y modela la
dis ibución de las soluciones seleccionadas. Una uen e ú il pa a p o undiza en el
uncionamien o de las edes bayesianas y gaussianas es [27].
4.2. Adap ación de la ma iz de co a ianza
El algo i mo CMA-ES (Co a iance Ma ix Adap a ion - E olu ion S a egy), p e-
sen ado po Hansen y Os e meie [19] en 2001, se encuad a den o del conjun o de
mé odos denominados es a egias de e olución.
Las es a egias de e olución su gen en la década de 1960 con el abajo de Re-
chenbe g [45], con el obje i o de se u ilizadas en p oblemas de op imización con-
inua. Se ca ac e izan po la aplicación i e a i a de ope ado es de selección, c uce
y mu ación, como en el caso de los algo i mos gené icos. La mane a especí ica y
concep ualmen e di e en e de de ini y aplica dichos ope ado es, sin emba go, ha

4.2. Adap ación de la ma iz de co a ianza 17
p o ocado que adicionalmen e se los conside e clases dis in as de algo i mos e olu-
i os. Una g an di e encia en e ellos es la impo ancia que le o o gan a la mu ación.
En un algo i mo gené ico clásico es habi ual que es e ope ado p o oque pequeños
cambios en algunos indi iduos, con el obje i o de alcanza egiones inexplo adas del
espacio de soluciones. En una es a egia de e olución, po el con a io, la mu ación
di ige comple amen e el camino de los indi iduos hacia el óp imo. De hecho, en las
e siones más an iguas, ni siquie a exis e ope ado de c uce (algo impensable en un
algo i mo gené ico), y los hijos se ob ienen únicamen e aplicando mu aciones a los
p ogeni o es.
El ope ado de mu ación canónico de es a clase de algo i mos consis e en suma
a cada indi iduo (x1, . . . , xn)∈Rnun ec o ob enido como mues a de una dis-
ibución no mal mul i a ian e con media ce o. Veamos un p ime ejemplo sencillo,
en el que además de inimos el ope ado de c uce de la mane a más habi ual: co-
mo la media a i mé ica de los p ogeni o es. N(µ, σ2)deno a la dis ibución no mal
uni a iable de media µy des iación ípica σ.
Ejemplo 4.2.1. Seleccionamos los p ogeni o es p1= (x1
1, x1
2, x1
3),p2= (x2
1, x2
2, x2
3),
p3= (x3
1, x3
2, x3
3)∈R3. T as aplica el ope ado de c uce, ob enemos el hijo
h=1
3
3
X
j=1
pj,
donde la suma ec o ial se ealiza componen e a componen e. A con inuación, ob-
enemos una mues a {y= (y1, y2, y3)} ∼ X= (X1, X2, X3), con Xi∼ N(0, σ2)
pa a odo i∈ {1,2,3}, dado un cie o σ > 0. Finalmen e, añadimos a la nue a
gene ación de indi iduos el hijo mu ado, es o es, h+y.
El Ejemplo 4.2.1 nos in i a a o mula nos algunas p egun as. ¿Cómo se elige el
pa áme o σ? ¿Se man iene cons an e? ¿Tiene sen ido u iliza el mismo pa a odas
las componen es? Una ca ac e ís ica impo an e de la mayo ía de es a egias de
e olución es, p ecisamen e, la au oadap ación dinámica de los pa áme os que igen
la mu ación, pa a acili a la con e gencia. Podemos sus i ui la exp esión h+y
po h+sy, donde s > 0es el paso, que aumen a á cuando el algo i mo se es é
di igiendo de mane a consis en e hacia mejo es soluciones, y ice e sa. Po o o
lado, e ec i amen e, la na u aleza de nume osos p oblemas de op imización equie e
a a de o ma dis in a cada dimensión. Algunas es a egias de e olución de inen
Xi∼ N(0, σ2
i), con una des iación ípica σi>0dis in a pa a cada i∈ {1, . . . , n}.
No obs an e, podemos da un paso más y conside a ambién las dependencias
en e a iables. Pa a ello, ob enemos mues as de X∼ N(0,C), que aho a deno a
la dis ibución no mal mul i a ian e de media el o igen y ma iz de co a ianza
C, que cap u a dichas dependencias. Reco demos que la posición (C)i,j de la ma iz
ep esen a la co a ianza de las a iables XiyXj, que es siemp e nula cuando es as
son independien es, pe o no lo se á en gene al.
En el Algo i mo 2 se mues a el esquema gene al de la es a egia CMA-ES. El
lec o in e esado en conoce odos los de alles ma emá icos puede consul a [18].
18 Capí ulo 4. Algunos in en os de gene alización
Algo i mo 2 CMA-ES. Es necesa io de ini la condición de pa ada.
Ob ene una mues a A={y1, . . . , ym}∼N(0,I).
mien as no se cumpla la condición de pa ada hace
µ←1
mPm
j=1 yj
Calcula el nue o paso s.
Calcula la nue a ma iz de co a ianza C.
Ob ene una mues a A={y1, . . . , ym} ∼ s· N (µ, C)∼ N(µ, s2C).
in mien as
Capí ulo 5
Algo i mo gene alizado
La idea cen al de es e abajo su je de obse a que el compo amien o de odos
los algo i mos e olu i os se puede desc ibi de la mane a siguien e: Al comienzo
de cada i e ación, es á de inido un cie o conjun o A⊂Θ( ini o o in ini o) de
soluciones al p oblema de op imización conside ado. En el caso de GA o PSO, A
es el p opio conjun o de indi iduos seleccionados o de pa ículas gene adas. En
ACO, po el con a io, Aes el conjun o de odos los posibles eco idos sob e el
g a o de cons ucción con p obabilidad posi i a de se escogidos po las ho migas.
A con inuación, se ac ualiza el conjun o Ay comienza la siguien e i e ación.
Es e esquema nos lle a a imagina una a iable alea o ia subyacen e en cada i e-
ación, que p i ilegia unas soluciones en e a o as (es deci , les asigna una mayo
p obabilidad de o ma pa e del nue o conjun o A). El Algo i mo 3 es una abs ac-
ción de odos los algo i mos e olu i os en es os é minos. Xdeno a el conjun o de
odas las a iables alea o ias sob e Θ, y Pes el conjun o po encia o pa es de.
Algo i mo 3 Algo i mo e olu i o gene alizado. Es necesa io de ini la egión
ac ible Θ, la a iable alea o ia inicial X0: Θ →R, la unción de ac ualización
ac :X × P (Θ) → X y la condición de pa ada.
X←X0
Ob ene una mues a A⊂Θsegún la dis ibución inducida po X.
mien as no se cumpla la condición de pa ada hace
X←ac (X, A)
Ob ene una mues a A⊂Θsegún la dis ibución inducida po X.
in mien as
Has a aho a no ha apa ecido la unción a op imiza , que a menudo llama emos
unción de i ness po in luencia de GA. Es o se debe a que, en p incipio, el Algo i mo
3no iene po qué conduci nos a las mejo es soluciones. Es o es impo an e.
En su exp esión más gene al, es e solo busca cap u a las ac ualizaciones sucesi as
de su a iable alea o ia in ínseca a pa i de sí misma, que pueden i , a p io i,
en cualquie sen ido. Unas pa icula izaciones del algo i mo unciona án mejo que
o as, e in ui i amen e es as se án p ecisamen e las que u ilicen la unción en la
de inición de ac .
19
20 Capí ulo 5. Algo i mo gene alizado
5.1. Los algo i mos clásicos como pa icula izacio-
nes del gene alizado
En cada i e ación de GA, ac (X, A)de uel e una nue a a iable alea o ia que
asigna p obabilidad posi i a e igual a odos los elemen os del conjun o Bde los
hijos de A, gene ado as aplica en es e úl imo los co espondien es ope ado es de
selección, c uce y mu ación, y nula al es o de elemen os de Θ. De mane a comple a-
men e análoga, en cada i e ación de PSO la unción ac (X, A)de uel e la a iable
alea o ia que asigna p obabilidad posi i a e igual a odos los elemen os del conjun o
de nue as pa ículas alcanzadas a pa i de las de Asegún las eglas de ac ualización
p opias del algo i mo, y ce o al es o.
El caso de ACO es lige amen e dis in o. Reco demos que en una cie a i e ación
de dicho algo i mo, A ep esen a el conjun o de odos los posibles eco idos sob e
el g a o de cons ucción con p obabilidad posi i a, dada po la dis ibución de la
a iable X, de se escogidos po las ho migas. Po an o, ac (X, A)de uel e la
a iable alea o ia que asigna p obabilidad posi i a (y posiblemen e dis in a) a cada
eco ido sob e el g a o de cons ucción as habe ac ualizado consecuen emen e el
as o de e omonas.
5.2. De inición de o as pa icula izaciones
A la ho a de c ea dis in as pa icula izaciones del Algo i mo 3, pa ece azonable
de ini las co espondien es unciones de ac ualización de o ma que nue as a ia-
bles alea o ias asignen p obabilidades mayo es a elemen os con mayo i ness. Una
mane a de log a es o es median e el uso de unciones de in e polación.
Imaginemos que en una de e minada i e ación los elemen os del conjun o A=
{y1, . . . , ym}alcanzan los alo es de i ness { (y1), . . . , (ym)}. Nos p oponemos
de ini la nue a a iable alea o ia o, más conc e amen e, su unción de p obabilidad
(de densidad en el caso con inuo o de masa en el caso disc e o) asociada pnue a.
Decimos que una unción gin e pola a en Asi
g(yi) = (yi)∀i∈ {1, . . . , m}.
Es e iden e que si pnue a es p opo cional a alguna unción gque in e pola a en A,
end emos lo que pe seguimos: que los elemen os de Acon mayo i ness cuen en con
una mayo p obabilidad de se seleccionados pa a la siguien e i e ación y ice e sa.
Además, si exigimos un cie o g ado de con inuidad ag, los pun os p óximos a cada
uno de ellos se án escogidos ambién con p obabilidad simila . Es o se á ú il bajo
la p emisa de que, has a cie o pun o, el i ness de indi iduos pa ecidos es pa ecido,
en la que se undamen an odos los algo i mos e olu i os.
En la Sección 5.2.1 se analizan las unciones de in e polación ideadas du an e el
desa ollo del abajo, la mo i ación de ás de cada una y sus en ajas e incon e-
nien es. La Sección 5.2.2 es á dedicada al o o pun o undamen al del Algo i mo 3:
p ecisamos ob ene mues as según una dis ibución conc e a a bi a ia, con algún
5.2. De inición de o as pa icula izaciones 21
mé odo implemen able en la p ác ica. Se p esen an y se analizan ambién dis in as
o mas de log a lo.
5.2.1. Funciones de in e polación
La in e polación polinómica es, sin duda, la más es udiada en el campo del
análisis numé ico. También ue la p ime a conside ada du an e el desa ollo de es e
abajo. En el caso unidimensional es ampliamen e conocido el polinomio in e pola-
do de New on o de Lag ange [46, Capí ulo 6]. Hech e al. [20] han desa ollado odo
un ma co eó ico pa a ex ende el obje o mencionado a dimensión a bi a ia. Ade-
más, la lib e ía Min e py [3] implemen a en lenguaje Py hon odos los algo i mos
diseñados en el a ículo ci ado y las es uc u as de da os necesa ias.
T a a con unciones de in e polación gpolinómicas supone g andes en ajas
debido a su egula idad. En pa icula , al se ácilmen e in eg ables analí icamen e,
enemos ga an izado que la unción de densidad p opo cional
p(x) = g(x)
RΘg(x)dx
puede se calculada. Es a p opiedad ambién ha pe mi ido diseña un mé odo de
mues eo especí ico que se de alla en la Sección 5.2.2.
Lamen ablemen e, as cha la con los desa ollado es de Min e py, comp endi-
mos que dicha lib e ía no se ajus a adecuadamen e a nues o p opósi o. En p ime
luga , no pe mi e ob ene un polinomio gque in e pola a en un conjun o ijado de
pun os A. Po el con a io, el p opio algo i mo selecciona los nodos de in e polación
de en e odos los pun os del espacio mul idimensional, pues es os deben cumpli la
llamada p opiedad de unisol encia [20, Sección 2].
¿Es po an o comple amen e imposible u iliza Min e py pa a ob ene un poli-
nomio que pase po un conjun o a bi a io de pun os? Lo cie o es que no, siemp e y
cuando se admi a un de e minado e o de ap oximación. La lib e ía ambién o ece
una uncionalidad in e esan e: la eg esión polinómica. En es e caso, a pa i de un
conjun o A={y1, . . . , ym}de pun os, el algo i mo calcula los nodos unisol en es de
o ma que la unción de eg esión gob enida (que se á un polinomio de in e polación
en dichos nodos) ap oxima en A. Es deci , ya no se cumple necesa iamen e que
g(yi) = (yi)∀i∈ {1, . . . , m},
pe o es o no nos supone un incon enien e. Po la na u aleza de nues o p oblema,
únicamen e necesi amos dis ingui las egiones de mayo y meno i ness, sin p eo-
cupa nos po la exac i ud.
A pesa de odo, las p ime as p uebas hicie on pa en e la necesidad de espacio
en disco del o den de pe aby es al conside a pun os en un espacio 30-dimensional,
incluso es ingiéndonos a polinomios de g ado meno o igual que es. De nue o, los
desa ollado es de la lib e ía a oja on algo de luz sob e lo que ocu ía. La es uc u a
de da os in e na en la que se undamen an p ác icamen e odos los algo i mos in-
cluidos en Min e py, los conjun os de mul iíndices (clase Mul iIndexSe ), aumen a

22 Capí ulo 5. Algo i mo gene alizado
su amaño exponencialmen e con la dimensión del espacio. Po ello, la lib e ía queda
inalmen e desca ada pa a dimensión mayo que cinco.
En ealidad, an o Min e py como o as lib e ías de in e polación numé ica pe -
siguen un obje i o conc e o: ob ene una unción que ap oxime o a desconocida
(como pod ía se la de i ness) con el mayo g ado de p ecisión posible en odo
pun o de su dominio. Es a a ea se e a ec ada po el enómeno denominado
maldición de la dimensión, desc i o po p ime a ez po Bellman [5] en 1957. La
can idad de pun os necesa ios pa a ap oxima adecuadamen e una unción c ece ex-
ponencialmen e con la dimensión del espacio. No obs an e, eco demos que nues o
obje i o dis a de conoce los alo es de i ness asociados a odo pun o de la egión
ac ible Θ. Po el con a io, p e endemos i desplazándonos hacia mejo es soluciones
i e a i amen e, según el espí i u de cualquie algo i mo e olu i o.
Podemos aleja nos comple amen e de la idea de la in e polación polinómica y
emplea o a écnica, mucho más sencilla a p io i, pe o que ha esul ado se pode osa
y e sá il: la in e polación po medias ponde adas. Imaginemos el siguien e
ejemplo en R2, ilus ado en la Figu a 5.1.
Ejemplo 5.2.1. Sean los pun os y1= (0,1), y2= (2,0), y3= (0,3), con i ness
(y1)=1, (y2) = 4, (y3) = 10.
y1
y2
y3
y
Figu a 5.1: Rep esen ación g á ica del Ejemplo 5.2.1.
Si de inimos g(yi) = (yi)pa a odo i∈ {1,2,3}, ¿qué alo de gasignamos, po
ejemplo, al pun o y= (0,0)? Una o ma de consegui que dicho alo sea pa ecido
al de los pun os ce canos es emplea simplemen e la media de { (y1), (y2), (y3)}
ponde ada po el in e so de la dis ancia de ya cada uno de ellos. Es deci , si d
deno a la mé ica euclídea (o Manha an, que en es e caso coinciden),
g(y) =
1
d(y,y1) (y1) + 1
d(y,y2) (y2) + 1
d(y,y3) (y3)
1
d(y,y1)+1
d(y,y2)+1
d(y,y3)
=
1
1·1 + 1
2·4 + 1
3·10
1
1+1
2+1
3
=38
11.
El ejemplo an e io nos conduce de mane a na u al a la de inición de la ó mula
gene al de unción de in e polación po medias ponde adas.
5.2. De inición de o as pa icula izaciones 23
De inición 5.2.2. Sean el subconjun o A={y1, . . . , ym}de Rn, con alo es de
i ness { (y1), . . . , (ym)}, y una dis ancia d, la unción de in e polación po
medias ponde adas gMP :Rn→Rse de ine como
gMP(y) = 


(y)si y∈A,
Pm
i=1 w(y, yi) (yi)si y /∈A,
donde
w(y, z) =
1
d(y,z)
Pm
i=1
1
d(y,yi)
.
Una en aja impo an e de gMP es que su de inición se puede modi ica ácilmen-
e pa a ob ene a ian es que no emplean odos los pun os de A, sino únicamen e
los más in e esan es en cada momen o (los de mayo i ness, los más ce canos a y,
e cé e a). Es o, como e emos en el Capí ulo 6, se i á pa a da luga a pa icula-
izaciones más simila es a unos o a o os algo i mos e olu i os clásicos.
5.2.2. Técnicas de mues eo
Una ez hemos de inido una unción de p obabilidad pnue a : Θ →[0,1], nos
p egun amos cómo ob ene mues as según su dis ibución inducida, que es a p io i
a bi a ia y desconocida. Un algo i mo ampliamen e u ilizado po su e sa ilidad
es el llamado mé odo de acep ación- echazo [47, Sección 2.3], que es aplicable
siemp e y cuando Θes é aco ado. Es e ap o echa que es sencillo en la p ác ica
ob ene mues as siguiendo una dis ibución uni o me cualquie a.
En p ime luga , lo p esen amos pa a el caso uni a iable en el Algo i mo 4.
Conside amos, po an o, que Θ⊂(a, b)⊂R. Además, deno amos po U(a, b)la
dis ibución uni o me en el in e alo (a, b).
Algo i mo 4 Mé odo de acep ación- echazo uni a iable. Es p eciso de ini la egión
ac ible Θ, la unción de p obabilidad py el amaño mues al deseado k∈N. El
alo ysup >0es una co a supe io del alo máximo de pen Θ.
S← ∅
mien as |S|< k hace
Ob ene una mues a {x} ∼ U(a, b).
Ob ene una mues a {y} ∼ U(0, ysup).
si p(x)> y en onces
S←S∪ {x}
in si
in mien as
Si ca ecemos de más in o mación, siemp e podemos de ini ysup = 1, aunque
es imaciones más inas da án mejo es esul ados en é minos de núme o necesa io
de i e aciones. La Figu a 5.2 mues a una in e p e ación isual de la co ección del
algo i mo. Los pun os (x, y)se dis ibuyen uni o memen e en el ec ángulo (a, b)×
24 Capí ulo 5. Algo i mo gene alizado
(0, ysup). Únicamen e aquellos que quedan debajo de la g á ica de p, es deci , e i ican
p(x)> y son acep ados y añadidos a S. In ui i amen e, en las egiones de Θcon
mayo alo de pse concen a án más pun os acep ados y al con a io.
ab
0
ysup p(x)
ysup
Figu a 5.2: Pun os cuya coo denada xes acep ada (cí culos azules) y echazada
(c uces ojas).
La ex ensión del mé odo de acep ación- echazo a dimensión a bi a ia esul a
muy na u al, y se mues a en el Algo i mo 5. Conside amos en es e caso que Θ⊂
(a1, b1)×· · ·×(an, bn)⊂Rn. Sabemos que si X= (X1, . . . , Xn)es un ec o alea o io
de inido en el ec ángulo R= (a1, b1)× · · · × (an, bn)yX∼U(R), en onces Xi∼
U(ai, bi)pa a odo i∈ {1, . . . , n}y son independien es. Po an o, podemos ob ene
mues as x= (x1, . . . , xn)componen e a componen e.
Algo i mo 5 Mé odo de acep ación- echazo mul i a iable. Es p eciso de ini la
egión ac ible Θ, la unción de p obabilidad py el amaño mues al deseado k∈N.
El alo ysup >0es una co a supe io del alo máximo de pen Θ.
S← ∅
mien as |S|< k hace
pa a i∈ {1, . . . , n}hace
Ob ene una mues a {xi} ∼ U(ai, bi).
in pa a
Ob ene una mues a {y} ∼ U(0, ysup).
si p(x1, . . . , xn)> y en onces
S←S∪ {(x1, . . . , xn)}
in si
in mien as
El mé odo de acep ación- echazo es muy sencillo de implemen a en la p ác ica,
y se puede emplea con cualquie unción de p obabilidad y en dimensión a bi a ia.
Además, man iene sus p opiedades al sus i ui ppo o a unción p opo cional, po
lo que no es necesa io que pnue a es é no malizada en [0,1] (siemp e y cuando seamos
capaces de es ima una co a supe io , que ya no end ía po qué se 1). Es o se á
5.2. De inición de o as pa icula izaciones 25
especialmen e ú il al a a con unciones de in e polación con in eg al desconocida
o compu acionalmen e p ohibi i a.
Po supues o, no odo son en ajas. El p incipal incon enien e de es e algo i mo
apa ece cuando la unción de in e polación conside ada asigna alo es muy p óximos
a ce o a una egión demasiado g ande de su dominio. En es e caso, el núme o de
i e aciones del bucle ex e no c ece conside ablemen e, debido a la al a can idad de
echazos. En las si uaciones más ex emas el mé odo de acep ación- echazo es, po
an o, indis inguible de una búsqueda exhaus i a.
En el caso conc e o en que pnue a es una unción polinómica, p oponemos un
algo i mo de mues eo o almen e dis in o que no e inc emen ado su cos e en iempo
en p esencia de g andes egiones de ce os. Desc ibimos su uncionamien o po medio
de un ejemplo en dimensión n= 2.
Ejemplo 5.2.3. Sean Θ = [0,100] ×[0,100] y
pnue a(x, y) = g(x, y)
RΘg(x, y)d(x, y),
donde g(x, y) = x3+ 2x2y+xy + 5xy2+ 2xy3+y4. Nos p oponemos ob e ne una
mues a según la dis ibución de p obabilidad que iene a pnue a po unción de
densidad. En p ime luga obse amos que el denominado es ácilmen e calculable:
ZΘ
g(x, y)d(x, y) = Z100
0Z100
0
[x3+ 2x2y+xy + 5xy2+ 2xy3+y4]dydx
=Z100
0
[x3y+x2y2+1
2xy2+5
3xy3+1
2xy4+1
5y5]
100
y=0
dx
=Z100
0
[100x3+ 104x2+ 5 ·103x+5·106
3x+ 5 ·107x+ 2 ·109]dx
= [25x4+104
3x3+155015 ·103
6x2+ 2 ·109x]
100
x=0
=1392575000000
3.
Si lo analizamos in ui i amen e, únicamen e hemos empleado ope aciones sencillas
con los exponen es y hemos eco ido en dos ocasiones odos los monomios. Llame-
mos D= 1392575000000/3.
Como ya hemos mencionado, es ac ible en la p ác ica gene a núme os según
una dis ibución uni o me. Conside amos { , s} ∼ U(0,1), y supongamos po un
momen o que conocemos el alo x0∈[0,100] al que
1
DZx0
0Z100
0
g(x, y)dxdy= ,
es o es, eu ilizando los cálculos an e io es, aquel al que
25x4
0+104
3x3
0+155015 ·103
6x2
0+ 2 ·109x0= D.
32 Capí ulo 6. Implemen ación p ác ica
Algo i mo 6 AEMP gene alizado. Es necesa io de ini la egión ac ible Θ, el nú-
me o de i e aciones k, el amaño de las mues as m, la dis ancia dy la unción
de i ness no malizada en [0,1]. También se debe elegi el ope ado de selección
sel(B, , m), que de uel e msoluciones de Ben unción de su alo de i ness.
A← {s1, . . . , sm} ∼ U(Θ)
pa a ki e aciones hace
S← ∅
mien as |S|< m hace
Ob ene una mues a {x} ∼ U(Θ).
Ob ene una mues a {y} ∼ U(0,1).
Elegi el subconjun o Bx⊂Ade soluciones p i ilegiadas.
si gBx(x)> y en onces
S←S∪ {x}
in si
in mien as
A←sel(A∪S, , m)
in pa a
donde
wB(y, z) =
1
d(y,z)
Pb∈B
1
d(y,b)
.
Nó ese que la media ponde ada de los alo es de i ness aho a se ealiza únicamen-
e sob e los elemen os de un subconjun o de Aque depende de x. Es o es una
di e encia undamen al con los EDA, donde eco demos que en cada i e ación selec-
cionábamos un cie o B⊂Ade soluciones p i ilegiadas. Es e de e minaba ambién
la p obabilidad p(x|B)de ob ene cada nue o pun o xpo mues eo, pe o e a el
mismo pa a odos ellos.
Si Bxes á o mado po los dos pun os más p óximos a x, en onces ob enemos
una e sión del AEMP más pa ecida a GA. Si, po el con a io, dicho subconjun o
con iene el elemen o de Amás ce cano a xy el óp imo (el de mayo i ness), ob-
enemos o a e sión más pa ecida a PSO. Lo ilus amos en la Figu a 6.3 y en la
Figu a 6.4 espec i amen e.
Figu a 6.3: Conjun o A( ojo) y pun o x(azul). Los dos elemen os de Amás p óximos
ax o man Bx.

6.2. Algo i mos empleados 33
Figu a 6.4: Conjun o A(elemen o de mayo i ness en e de, es o en ojo) y pun o
x(azul). El subconjun o Bxes á o mado po y el pun o de Amás p óximo a x.
La in uición de ás de es a a i mación es sencilla. Al aplica un algo i mo ge-
né ico, la p obabilidad de conside a una cie a solución en la i e ación i+ 1 es á
ue emen e elacionada con la de habe seleccionado dos posibles p ogeni o es (es
deci , soluciones p óximas a ella) en la i e ación i. Po o o lado, en la i e ación i+1
de PSO es muy p obable que las pa ículas conside adas sean ce canas a las de la
i e ación iy que, además, se ap oximen a la solución óp ima del enjamb e.
Denominamos ambas e siones AEMP-GA y AEMP-PSO espec i amen e. Es
impo an e no a que no es amos a ando de imi a a la pe ección los algo i mos
clásicos, sino de de ini y p oba dis in as a iaciones de AEMP que cap u en la
esencia de cómo dichos algo i mos p i ilegian unas soluciones u o as, de mane a
ácil y di ec a. Además, hib ida los aho a esul a i ial. Bas a con, po ejemplo,
de ini Bxcomo el conjun o que con iene los dos elemen os de Amás p óximos a x
y aquel con mayo alo de i ness. Llamamos a es a e ce a a ian e AEMP-HIB en
lo que es a de capí ulo.
De ini una pa icula ización de AEMP simila a ACO ha supues o un g an e o
du an e el desa ollo de es e abajo. El p opio Ma co Do igo, pad e de los algo i mos
de colonia de ho migas, p esen a la que es, según su c i e io, la mejo o ma de
gene aliza los mismos en [50]. Su obje i o es pode aplica ACO a p oblemas de
op imización con inua, y apo a dos ideas undamen ales que podemos u iliza .
En p ime luga , Socha y Do igo [50] p oponen desca a comple amen e el g a o
de cons ucción y simplemen e lle a un a chi o, es deci , una abla con las mejo es
soluciones y su alo de i ness. Es o es exac amen e lo que se hace en AEMP, donde
el conjun o A oma el papel de a chi o. Se basan en que, cuando una ho miga
decide qué nue a componen e añadi a su es ado (solución pa cial), simplemen e es á
omando una mues a a pa i de una a iable alea o ia disc e a (que asigna dis in as
p obabilidades posi i as a cada a is a), y es a a iable pod ía sus i ui se po o a
o almen e a bi a ia. Lo único e dade amen e impo an e según los au o es es que
cada solución se cons uya componen e a componen e, al y como se hace en AEMP.
La segunda modi icación undamen al se cen a en la ac ualización de e omo-
nas. Como ya no exis e el g a o de cons ucción, los au o es p oponen simplemen e
34 Capí ulo 6. Implemen ación p ác ica
ol ida (es deci , elimina del a chi o) las Mpeo es soluciones as habe gene ado
Mnue as. Po an o, pa a ob ene una e sión de AEMP más pa ecida a ACO,
podemos de ini el subconjun o Bx=Apa a odo pun o x. Llamamos a es a úl ima
pa icula ización AEMP-ACO.
6.3. Resul ados ob enidos
En la Sección 6.3.1 y la Sección 6.3.2 se mues an y analizan los esul ados
ob enidos as aplica los seis algo i mos a di e sas ins ancias del p oblema de la
cobe u a de é ices y de la mochila espec i amen e. En odos los casos se ha
empleado la dis ancia más na u al en espacios bina ios, la de Hamming, de inida a
con inuación. Nó ese que dHamming(x, y)simplemen e mide el núme o de componen es
de xque hab ía que in e i (cambia 1po 0o ice e sa) pa a llega ay.
De inición 6.3.1. Dados x, y ∈ {0,1}n, la dis ancia de Hamming dHamming en e
xeyse de ine como
dHamming(x, y) =
n
X
i=1
|xi−yi|.
Además, el ope ado de selección u ilizado es el de uncamien o, es deci , en
cada i e ación se eligen las msoluciones con mayo i ness y se desca an las demás.
6.3.1. P oblema de la cobe u a de é ices
Se han p obado odos los algo i mos con dis in as ins ancias del p oblema VERTEX
COVER omadas de [48]. En conc e o, se han empleado las mos adas en la Tabla 6.1,
po con a con un amaño (núme o de é ices) ajus ado a los obje i os de es e
abajo. Algunas han sido p ep ocesadas pa a que odas ep esen en un g a o no
di igido y no alo ado con é ices nume ados de 1an.
Ins ancia n
ENZYMES-G102 42
a es-spa ow-social-2010 40
a es-spa owlyon- lock-season2 46
ca -mixed-species-b ain-1 65
Tabla 6.1: Las cua o ins ancias empleadas y su núme o de é ices n.
Los esul ados ob enidos en 20 ejecuciones independien es, con 1000 i e aciones
y poblaciones de 300 indi iduos pa a los seis algo i mos conside ados y la ins ancia
ENZYMES-G102 se mues an en la Tabla 6.2. Cabe des aca que, aunque g an pa e de
las ejecuciones a ojan los mismos alo es de i ness máximo, las soluciones en las que
es e se alcanza son en gene al dis in as. Es o esal a la na u aleza no de e minis a
de los algo i mos empleados. El alo de i ness máximo encon ado ha sido 17, y
en la Figu a 6.5 se mues a un ejemplo de solución con dicho alo , que al y como
hemos mencionado no es única.
6.3. Resul ados ob enidos 35
1
2
3
4
5
6
7
8
9
10
1112
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 30 31 32 33 34 35 36
37
38
39
40
41
42
Figu a 6.5: Cobe u a de 42 −17 = 25 é ices pa a la ins ancia ENZYMES-G102.
36 Capí ulo 6. Implemen ación p ác ica
GA PSO AEMP-GA AEMP-PSO AEMP-HIB AEMP-ACO
1 17 16 16 16 16 16
2 17 16 16 16 16 17
3 17 16 16 16 16 16
4 17 16 16 16 16 16
5 17 16 16 16 16 16
6 17 16 16 16 16 16
7 17 16 15 16 16 16
8 17 16 16 17 16 16
9 17 16 16 16 16 17
10 17 16 16 16 16 16
11 17 16 16 16 16 16
12 17 17 16 15 16 16
13 17 16 16 16 16 16
14 17 16 17 16 16 16
15 17 17 16 16 16 16
16 17 17 16 16 16 16
17 17 16 16 16 16 16
18 17 16 16 16 16 16
19 17 17 16 16 16 16
20 17 17 15 16 16 16
Tabla 6.2: Resul ados pa a ENZYMES-G102.
Como se puede obse a , los esul ados son po lo menos acep ables. No o ma
pa e de los obje i os de es e abajo diseña algo i mos que supe en en endimien o
a las implemen aciones op imizadas de los algo i mos adicionales. No obs an e, es
buena p ác ica emplea p uebas es adís icas pa a compa a de o ma jus i icada los
esul ados. Tomamos como hipó esis nula H0que no exis en di e encias signi ica i-
as en e los seis algo i mos, es deci , que los 20 esul ados de cada uno pod ían se
mues as de la misma a iable alea o ia subyacen e, y ealizamos un con as e es a-
dís ico. Debemos u iliza las llamadas p uebas no pa amé icas, pues o que es as no
asumen p opiedades como no malidad, independencia u homogeneidad de a ianzas.
El lec o in e esado en p o undiza en es a clase de p uebas y cómo aplica las puede
encon a oda la in o mación en [9].
T as emplea el es de Quade, una a iación del más comúnmen e conocido es
de F iedman que ajus a los pesos a la ho a de ealiza la clasi icación en unción de
la di icul ad del p oblema, ob enemos que H0puede se echada. Es deci , sí exis en
di e encias signi ica i as en e los seis algo i mos. Sin emba go, as aplica lo que se
conoce como un mé odo pos -hoc pa a compa a los mismos dos a dos (en conc e o,
el de Holm, de los ecomendados en [9]), esul a que únicamen e exis en di e encias
signi ica i as en e los esul ados de GA y AEMP-GA, y no en e los o os 14 pa es,
con un ni el de signi icación α= 0,05.
En la Tabla 6.3 y en la Tabla 6.4 se mues an los esul ados ob enidos pa a las
ins ancias a es-spa ow-social-2010 ya es-spa owlyon- lock-season2 es-
6.3. Resul ados ob enidos 37
pec i amen e. Resul a llama i o que absolu amen e odas han alcanzado el mismo
alo de i ness máximo, 10 en el caso de la p ime a ins ancia y 13 en el de la segun-
da. Quizá incluso demasiado llama i o. No obs an e, de nue o, dichos alo es se han
alcanzado en soluciones di e en es. Es deci , sí se ha p oducido una adecuada ex-
plo ación del espacio de búsqueda. E iden emen e, podemos a i ma que no exis en
di e encias signi ica i as en e los seis algo i mos sin necesidad de emplea p uebas
no pa amé icas.
GA PSO AEMP-GA AEMP-PSO AEMP-HIB AEMP-ACO
1 10 10 10 10 10 10
2 10 10 10 10 10 10
3 10 10 10 10 10 10
4 10 10 10 10 10 10
5 10 10 10 10 10 10
6 10 10 10 10 10 10
7 10 10 10 10 10 10
8 10 10 10 10 10 10
9 10 10 10 10 10 10
10 10 10 10 10 10 10
11 10 10 10 10 10 10
12 10 10 10 10 10 10
13 10 10 10 10 10 10
14 10 10 10 10 10 10
15 10 10 10 10 10 10
16 10 10 10 10 10 10
17 10 10 10 10 10 10
18 10 10 10 10 10 10
19 10 10 10 10 10 10
20 10 10 10 10 10 10
Tabla 6.3: Resul ados pa a a es-spa ow-social-2010.
Finalmen e, en la Tabla 6.5 se p esen an los esul ados ob enidos pa a la ins ancia
ca -mixed-species-b ain-1. Si aplicamos de nue o el es de Quade y el mé odo
pos -hoc de Holm, ob enemos que únicamen e exis en di e encias signi ica i as en e
GA y AEMP-ACO, en e GA y AEMP-HIB y en e GA y AEMP-GA, con un ni el
de signi icación 0,05. Resul a eseñable que las p uebas es adís icas no encuen an
di e encias signi ica i as en e GA y AEMP-PSO, ni en e PSO y ninguna de las
a ian es de AEMP.
6.3.2. P oblema de la mochila
Se han empleado cua o ins ancias de KNAPSACK de dimensión 50 omadas de [40].
Conc e amen e, las cua o p ime as del di ec o io 00Unco ela ed/n00050/R01000.
Las nomb amos kn0,kn1,kn2 ykn3 po simplicidad. En es a ocasión, se han necesi-
ado 5000 i e aciones po ejecución pa a alcanza la con e gencia de los algo i mos.

38 Capí ulo 6. Implemen ación p ác ica
GA PSO AEMP-GA AEMP-PSO AEMP-HIB AEMP-ACO
1 13 13 13 13 13 13
2 13 13 13 13 13 13
3 13 13 13 13 13 13
4 13 13 13 13 13 13
5 13 13 13 13 13 13
6 13 13 13 13 13 13
7 13 13 13 13 13 13
8 13 13 13 13 13 13
9 13 13 13 13 13 13
10 13 13 13 13 13 13
11 13 13 13 13 13 13
12 13 13 13 13 13 13
13 13 13 13 13 13 13
14 13 13 13 13 13 13
15 13 13 13 13 13 13
16 13 13 13 13 13 13
17 13 13 13 13 13 13
18 13 13 13 13 13 13
19 13 13 13 13 13 13
20 13 13 13 13 13 13
Tabla 6.4: Resul ados pa a a es-spa owlyon- lock-season2.
En la Tabla 6.6 se mues an los esul ados ob enidos pa a la ins ancia kn0. El es
de Quade y el mé odo pos -hoc de Holm únicamen e hallan di e encias signi ica i as
en e GA y AEMP-GA, en e GA y AEMP-ACO y en e GA y AEMP-PSO, con un
ni el de signi icación α= 0,05. Es deci , en es e caso conc e o AEMP-HIB supe a
en endimien o a los dos algo i mos que hib ida y esul a indis inguible del mejo ,
que de nue o es GA.
En la Tabla 6.7 se p esen an los esul ados ob enidos pa a la ins ancia kn1. En
es a ocasión sí hay di e encias signi ica i as (con α= 0,05) en e GA y odas las
a ian es de AEMP, aunque nue amen e AEMP-HIB es la que mejo ac úa de las
cua o.
Los esul ados pa a la ins ancia kn2 se mues an en la Tabla 6.8. T as aplica el
es de Quade y el mé odo de Holm, podemos obse a algo cu ioso. A di e encia de
los dos an e io es, en es e caso no hay di e encias signi ica i as en e AEMP-GA y
GA (como sí las hay en e GA y las demás a ian es de AEMP). Es deci , con un
ni el de signi icación α= 0,05, el algo i mo gené ico clásico y la e sión de AEMP
más pa ecida a él ac úan igual. Lo mismo se puede a i ma de AEMP-PSO y PSO.
Po úl imo, los esul ados ob enidos pa a la ins ancia kn3 se p esen an en la
Tabla 6.9. En es a ocasión únicamen e hay di e encias signi ica i as (con α= 0,05)
en e dos de los 15 pa es de algo i mos: en e GA y AEMP-ACO y en e GA y
AEMP-GA.
6.3. Resul ados ob enidos 39
GA PSO AEMP-GA AEMP-PSO AEMP-HIB AEMP-ACO
1 12 11 11 11 11 11
2 12 11 11 11 11 10
3 12 11 10 11 10 11
4 12 11 10 11 11 11
5 12 11 10 10 11 10
6 12 11 10 10 10 11
7 12 10 10 10 11 10
8 12 11 10 11 10 10
9 12 11 10 11 11 10
10 12 12 10 11 11 10
11 12 11 11 10 11 10
12 12 11 11 11 10 10
13 12 10 10 11 10 11
14 12 10 11 11 10 10
15 12 11 11 10 10 10
16 12 10 11 11 10 10
17 12 11 10 11 10 11
18 12 10 11 11 10 10
19 12 10 11 11 10 10
20 12 11 10 10 10 10
Tabla 6.5: Resul ados pa a ca -mixed-species-b ain-1.
GA PSO AEMP-GA AEMP-PSO AEMP-HIB AEMP-ACO
1 20783 19213 18931 19176 19076 18703
2 20716 19250 19042 19121 18888 19218
3 20776 19318 19204 18976 19003 19550
4 20806 19185 19110 19601 19220 18974
5 20877 19711 19098 19535 18993 19007
6 20741 19602 19025 19418 19693 18779
7 20936 19418 19277 19320 18798 19433
8 20817 19865 18819 19308 19239 18836
9 20884 19678 19079 18929 19213 19133
10 20842 19824 18846 19097 18923 18930
11 20768 19396 19490 18848 18896 19144
12 20723 19290 19106 19168 19291 18743
13 20612 19148 19107 18955 19113 19274
14 20653 20403 18927 18988 19147 19146
15 20984 19365 19186 18679 19202 19040
16 20864 19479 19609 18937 19001 19118
17 20583 19427 18762 18978 18897 19093
18 20842 20056 18884 19487 19485 19426
19 20831 19483 19085 19167 19262 18877
20 20723 19609 19452 19060 19018 18987
Tabla 6.6: Resul ados pa a kn0.
40 Capí ulo 6. Implemen ación p ác ica
GA PSO AEMP-GA AEMP-PSO AEMP-HIB AEMP-ACO
1 19459 18062 17460 17020 17490 17154
2 19441 17951 17046 17219 17738 18273
3 19471 17556 17274 17449 17557 17444
4 19599 17682 17612 17039 17201 17494
5 19604 17862 17270 16860 17349 17718
6 19411 17850 17613 17169 17852 17328
7 19537 17991 16990 17226 16996 16897
8 19836 17604 17368 17114 17206 16914
9 19511 18464 17386 17257 17417 17273
10 19676 17537 17145 17490 17134 17250
11 19496 18098 17486 17197 17427 17395
12 19432 17940 17392 17543 17089 17278
13 19422 17637 17248 17596 17150 17197
14 19836 17508 17112 17387 17320 17914
15 19548 17613 17353 17535 17305 17340
16 19809 17703 17524 17361 18573 17329
17 19836 17555 17149 17840 17185 16953
18 19334 17769 17172 18293 17396 17311
19 19666 18041 17244 18387 17519 17282
20 19376 17717 17274 17295 17274 17796
Tabla 6.7: Resul ados pa a kn1.
GA PSO AEMP-GA AEMP-PSO AEMP-HIB AEMP-ACO
1 20370 19402 18960 18457 18555 18732
2 20339 19139 18640 18558 18611 18221
3 20360 19562 18959 18506 18814 18779
4 20243 19282 18821 18986 18795 18740
5 20382 19246 18553 18681 18608 18509
6 20127 18992 18720 18549 18483 18563
7 20285 19227 19003 18641 18549 18414
8 20390 19122 18780 18469 18621 18823
9 20471 19483 18599 18845 18496 18595
10 20419 19188 18743 18743 18937 18739
11 20371 19057 18637 18390 18822 18587
12 20436 18848 18980 18584 18778 19034
13 20410 18862 18503 18800 18755 18782
14 20361 19165 19001 18452 18819 18834
15 20553 19158 18903 18688 18448 18539
16 20317 18847 18816 18597 18505 18721
17 20373 19293 19093 18774 18563 18695
18 20401 18945 18842 18612 18778 18754
19 20507 18735 18586 18672 18603 18520
20 20507 19128 18781 19265 18672 19125
Tabla 6.8: Resul ados pa a kn2.
6.3. Resul ados ob enidos 41
GA PSO AEMP-GA AEMP-PSO AEMP-HIB AEMP-ACO
1 19450 18208 17751 18568 18190 17589
2 19547 18108 17839 17764 18595 17794
3 19651 18366 17957 17846 18039 17902
4 19691 18224 17847 18375 17925 17738
5 19513 17866 17626 17973 17828 17868
6 19609 18359 17707 17972 18088 17855
7 19640 18077 18171 17949 18247 17653
8 19691 17775 17900 18517 17565 17814
9 19605 18351 17891 18079 17991 17783
10 19684 18174 18013 18090 18674 17840
11 19736 18570 17881 17727 18261 17671
12 19596 18454 18021 17905 18065 18045
13 19571 18298 17987 18167 18127 17866
14 19530 18798 18057 17794 17869 17806
15 19574 17787 17896 17695 18009 17676
16 19487 17894 17808 18283 17624 17980
17 19523 18281 17455 17674 17904 17584
18 19677 18441 17795 18353 17763 17886
19 19581 17964 17779 17884 17937 18080
20 19709 18327 17700 17831 17799 17972
Tabla 6.9: Resul ados pa a kn3.
48 Capí ulo 7. Conclusiones y abajo u u o
p oposed o handle polynomials and use i o sol e con inuous op imiza ion p oblems
in dimension i e o lowe . The e a e highly in e es ing p oblems in low-dimensional
spaces, such as hose in he ield o so-called black-box op imiza ion [41]. In hese
cases, i is a p io i y o minimize he numbe o e alua ions o he i ness unc ion,
as hese e alua ions a e compu a ionally expensi e o he unc ion i sel is unknown.

Bibliog a ía
[1] Ab. Rashid, M. Tiki- aka algo i hm: a no el me aheu is ic inspi ed by oo ball
playing s yle. Enginee ing Compu a ions, ol. 38(1), páginas 313–343, 2020.
[2] Abbass, H. MBO: ma iage in honey bees op imiza ion – a Haplome osis
polygynous swa ming app oach. En P oceedings o he 2001 Cong ess on E o-
lu iona y Compu a ion (IEEE Ca . No.01TH8546), ol. 1, páginas 207–214.
2001.
[3] Acos a, U. H.,Vee il, S. K. T.,Wicaksono, D.,Sch eibe , J.,Mi-
chel ei , J.,Ho man, N.,Schme le , S. yChand asheka , V. Re-
posi o io de la lib e ía Min e py (Mul i a ia e In e pola ion in Py hon). 2021.
Disponible en h ps://gi hub.com/casus/min e py (úl imo acceso, 2024).
[4] Baluja, S. Popula ion-Based Inc emen al Lea ning: A Me hod o In eg a-
ing Gene ic Sea ch Based Func ion Op imiza ion and Compe i i e Lea ning.
In o me Técnico CMU-CS-94-163, Compu e Science School, Ca negie Mellon
Uni e si y, 1994.
[5] Bellman, R. Dynamic p og amming. P ince on Uni e si y P ess, P ince on,
NJ, USA, 1957.
[6] Chu, S.-C.,Tsai, P.-w. yPan, J.-S. Ca Swa m Op imiza ion. En PRICAI
2006: T ends in A i icial In elligence (edi ado po Q. Yang y G. Webb), páginas
854–858. Sp inge Be lin Heidelbe g, 2006.
[7] Chu, Y.,Mi, H.,Liao, H.,Ji, Z. yWu, Q. H. A Fas Bac e ial Swa ming
Algo i hm o high-dimensional unc ion op imiza ion. En 2008 IEEE Con-
g ess on E olu iona y Compu a ion (IEEE Wo ld Cong ess on Compu a ional
In elligence), páginas 3135–3140. 2008.
[8] Da win, C. On he O igin o Species. John Mu ay, 1859.
[9] De ac, J.,Ga cía, S.,Molina, D. yHe e a, F. A p ac ical u o-
ial on he use o nonpa ame ic s a is ical es s as a me hodology o compa-
ing e olu iona y and swa m in elligence algo i hms. Swa m and E olu iona y
Compu a ion, ol. 1(1), páginas 3–18, 2011.
[10] Do igo, M.,Maniezzo, V. yColo ni, A. Posi i e Feedback as a Sea ch
S a egy. In o me Técnico 91-016, Dipa imen o di Ele onica, Poli ecnico di
Milano, I alia, 1999.
49
50 BIBLIOGRAFÍA
[11] Do igo, M.,Mon es de Oca, M. A. yEngelb ech , A. Pa icle swa m
op imiza ion. Schola pedia, ol. 3(11), página 1486, 2008. Disponible en h p:
//www.schola pedia.o g/a icle/Pa icle_swa m_op imiza ion (úl imo
acceso, 2024).
[12] Do igo, M. yS ü zle, T. An Colony Op imiza ion. B ad o d Company,
2004.
[13] Eiben, A. E. ySmi h, J. E. In oduc ion o E olu iona y Compu ing. Sp in-
ge , 2015.
[14] Engelb ech , A. P. Fundamen als o Compu a ional Swa m In elligence.
Wiley, 2005.
[15] Gad, A. F. Pygad: An in ui i e gene ic algo i hm py hon lib a y. Mul imedia
Tools and Applica ions, páginas 1–14, 2023.
[16] Goldbe g, D. E. yLingle, R. Alleles, loci, and he a eling salesman p o-
blem. En P oceedings o he i s in e na ional con e ence on gene ic algo i hms
and hei applica ions, páginas 154–159. Psychology P ess, 1985.
[17] Hagbe g, A. A.,Schul , D. A. ySwa , P. J. Explo ing ne wo k s uc u e,
dynamics, and unc ion using Ne wo kX. En P oceedings o he 7 h Py hon
in Science Con e ence (SciPy2008) (edi ado po G. Va oquaux, T. Vaugh y
J. Millman), páginas 11–15. 2008.
[18] Hansen, N. The CMA E olu ion S a egy: A Tu o ial. A Xi , 2016. Dispo-
nible en h ps://a xi .o g/pd /1604.00772 (úl imo acceso, 2024).
[19] Hansen, N. yOs e meie , A. Comple ely De andomized Sel -Adap a ion
in E olu ion S a egies. E olu iona y Compu a ion, ol. 9(2), páginas 159–195,
2001.
[20] Hech , M.,Goncia z, K.,Michel ei , J.,Si kin, V. ySbalza ini,
I. F. Mul i a ia e In e pola ion on Unisol en Nodes – Li ing he Cu se o
Dimensionali y. A Xi , 2020. Disponible en h ps://a xi .o g/pd /2010.
10824.pd (úl imo acceso, 2024).
[21] Holland, J. H. Hidden O de , How Adap a ion Builds Complexi y. Addison-
Wesley Publishing Company, 1995.
[22] Jung, S. H. Queen-bee e olu ion o gene ic algo i hms. Elec onics Le e s,
ol. 39, páginas 575–576(1), 2003.
[23] Kao, Y.-T. yZaha a, E. A hyb id gene ic algo i hm and pa icle swa m op-
imiza ion o mul imodal unc ions. Applied So Compu ing, ol. 8(2), páginas
849–857, 2008.
[24] Ka eh, A. yFa houdi, N. A new op imiza ion me hod: Dolphin echoloca-
ion. Ad ances in Enginee ing So wa e, ol. 59, páginas 53–70, 2013.
BIBLIOGRAFÍA 51
[25] Kennedy, J. Swa m In elligence. En Handbook o Na u e-Inspi ed and In-
no a i e Compu ing, In eg a ing Classical Models wi h Eme ging Technologies
(edi ado po A. Zomaya), páginas 187–219. 2006.
[26] Kennedy, J. yEbe ha , R. Pa icle swa m op imiza ion. En P oceedings
o ICNN’95 - In e na ional Con e ence on Neu al Ne wo ks, ol. 4, páginas
1942–1948. 1995.
[27] La añaga, P. An In oduc ion o P obabilis ic G aphical Models. En Es i-
ma ion o Dis ibu ion Algo i hms: A New Tool o E olu iona y Compu a ion
(edi ado po P. La añaga y J. A. Lozano), páginas 27–56. Sp inge US, Bos on,
MA, 2002.
[28] La añaga, P. A Re iew on Es ima ion o Dis ibu ion Algo i hms. En
Es ima ion o Dis ibu ion Algo i hms: A New Tool o E olu iona y Compu-
a ion (edi ado po P. La añaga y J. A. Lozano), páginas 57–100. Sp inge US,
Bos on, MA, 2002.
[29] La añaga, P.,E xebe ia, R.,Lozano, J. yPeña, J. Op imiza ion
in con inuous domains by lea ning and simula ion o Gaussian ne wo ks. En
P oceedings o he 2000 Gene ic and E olu iona y Compu a ion Con e ence
Wo kshop P og am, páginas 201–204. 2000.
[30] López-Ibáñez, M.,Dubois-Lacos e, J.,Pé ez Cáce es, L.,S ü zle,
T. yBi a a i, M. The i ace package: I e a ed Racing o Au oma ic Algo-
i hm Con igu a ion. Ope a ions Resea ch Pe spec i es, ol. 3, páginas 43–58,
2016.
[31] Mi anda, L. J. V. PySwa ms, a esea ch- oolki o Pa icle Swa m Op imi-
za ion in Py hon. Jou nal o Open Sou ce So wa e, ol. 3(21), 2018.
[32] Mo, H. yXu, L. Magne o ac ic bac e ia op imiza ion algo i hm o mul i-
modal op imiza ion. En 2013 IEEE Symposium on Swa m In elligence (SIS),
páginas 240–247. 2013.
[33] Molina, D.,Poya os, J.,Del Se , J.,Ga cía, S.,Hussain, A. yHe e-
a, F. Comp ehensi e Taxonomies o Na u e- and Bio-inspi ed Op imiza ion:
Inspi a ion e sus Algo i hmic Beha io , C i ical Analysis Recommenda ions.
Cogni i e Compu a ion, ol. 12, páginas 897––939, 2020.
[34] Mühlenbein, H. yPaaß, G. F om ecombina ion o genes o he es ima-
ion o dis ibu ions I. Bina y pa ame e s. En Pa allel P oblem Sol ing om
Na u e — PPSN IV (edi ado po H.-M. Voig , W. Ebeling, I. Rechenbe g y H.-
P. Schwe el), páginas 178–187. Sp inge Be lin Heidelbe g, Be lin, Heidelbe g,
1996.
[35] Mühlenbein, H. yVoig , H.-M. Gene Pool Recombina ion in Gene ic Algo-
i hms. En Me a-Heu is ics: Theo y and Applica ions (edi ado po I. H. Osman
y J. P. Kelly), páginas 53–62. Sp inge , 1996.
52 BIBLIOGRAFÍA
[36] Mulle , S.,Ma che o, J.,Ai aghi, S. yKou nou sakos, P. Op i-
miza ion based on bac e ial chemo axis. IEEE T ansac ions on E olu iona y
Compu a ion, ol. 6(1), páginas 16–29, 2002.
[37] Mu hiah-Naka ajan, V. yNoel, M. M. Galac ic Swa m Op imiza ion:
A new global op imiza ion me aheu is ic inspi ed by galac ic mo ion. Applied
So Compu ing, ol. 38, páginas 771–787, 2016.
[38] Mühlenbein, H. The equa ion o esponse o selec ion and i s use o p e-
dic ion. E olu iona y Compu a ion, ol. 5(3), páginas 303–346, 1997.
[39] Nguyen, H. T. yBhanu, B. Zombie Su i al Op imiza ion: A swa m in e-
lligence algo i hm inspi ed by zombie o aging. En P oceedings o he 21s In-
e na ional Con e ence on Pa e n Recogni ion (ICPR2012), páginas 987–990.
2012.
[40] Onoue, Y. Reposi o io de la lib e ía kplib. 2013. Disponible en h ps:
//gi hub.com/lik /kplib (úl imo acceso, 2024).
[41] Pa dalos, P. M.,Rasskazo a, V. yV aha is, M. N., edi o es. Black
Box Op imiza ion, Machine Lea ning, and No-F ee Lunch Theo ems. Sp inge ,
2021.
[42] Pelikan, M.,Goldbe g, D. E. yCan ú-Paz, E. BOA: he Bayesian op-
imiza ion algo i hm. En P oceedings o he 1s Annual Con e ence on Gene ic
and E olu iona y Compu a ion, GECCO’99, páginas 525—-532. Mo gan Kau -
mann Publishe s Inc., San F ancisco, CA, USA, 1999.
[43] Pu nomo, H. D. yWee, H.-M. Socce Game Op imiza ion: An Inno a i-
e In eg a ion o E olu iona y Algo i hm and Swa m In elligence Algo i hm.
En Me a-Heu is ics Op imiza ion Algo i hms in Enginee ing, Business, Econo-
mics, and Finance (edi ado po P. M. Vasan ), páginas 386–420. IGI Global,
2013.
[44] Razmjooy, N.,Khalilpou , M. yRamezani, M. A New Me a-Heu is ic
Op imiza ion Algo i hm Inspi ed by FIFA Wo ld Cup Compe i ions: Theo y
and I s Applica ion in PID Designing o AVR Sys em. Jou nal o Con ol,
Au oma ion and Elec ical Sys ems, ol. 27, página 419–440, 2016.
[45] Rechenbe g, I. Cybe ne ic Solu ion Pa h o an Expe imen al P oblem. RAE-
LT-1122. Royal Ai c a Es ablishmen , 1965.
[46] In an e del Río, J. A. yRey Cabezas, J. M. Mé odos numé icos: Teo ía,
p oblemas y p ác icas con MATLAB. Ciencia y Técnica. Ediciones Pi ámide,
sex a edición, 2022.
[47] Robe , C. P. yCasella, G. Mon e Ca lo S a is ical Me hods. Sp inge
Tex s in S a is ics. Sp inge -Ve lag, segunda edición, 2004.
BIBLIOGRAFÍA 53
[48] Rossi, R. A. yAhmed, N. K. The Ne wo k Da a Reposi o y wi h In e ac i e
G aph Analy ics and Visualiza ion. En P oceedings o he Twen y-Nin h AAAI
Con e ence on A i icial In elligence. 2015.
[49] Shiqin, Y.,Jianjun, J. yGuangxing, Y. A Dolphin Pa ne Op imiza ion.
En 2009 WRI Global Cong ess on In elligen Sys ems, ol. 1, páginas 124–128.
2009.
[50] Socha, K. yDo igo, M. An colony op imiza ion o con inuous domains.
Eu opean Jou nal o Ope a ional Resea ch, ol. 185(3), páginas 1155–1173,
2008.
[51] Sywe da, G. Uni o m C osso e in Gene ic Algo i hms. En P oceedings o
he Thi d In e na ional Con e ence on Gene ic Algo i hms (edi ado po J. D.
Scha e ), páginas 2–9. Mo gan Kau mann Publishe s Inc., 1989.
[52] Sö ensen, K. Me aheu is ics— he me apho exposed. In e na ional T ansac-
ions in Ope a ional Resea ch, ol. 22(1), páginas 3–18, 2015.
[53] Tang, D.,Dong, S.,Jiang, Y.,Li, H. yHuang, Y. ITGO: In asi e umo
g ow h op imiza ion algo i hm. Applied So Compu ing, ol. 36, páginas 670–
698, 2015.
[54] Teodo o ic, D.,Lucic, P.,Ma ko ic, G. yO co, M. D. Bee Colony
Op imiza ion: P inciples and Applica ions. En 2006 8 h Semina on Neu al
Ne wo k Applica ions in Elec ical Enginee ing, páginas 151–156. 2006.
[55] Vicen e A oyo, S. Reposi o io de es e abajo. 2024. Disponible en h ps:
//gi hub.com/sa icen e2109/TFG-In o (úl imo acceso, 2024).
[56] Zukh i, Z. yPapu ungan, I. A Hyb id Op imiza ion Algo i hm based on
Gene ic Algo i hm and An Colony Op imiza ion. In e na ional Jou nal o
A i icial In elligence Applica ions, ol. 4(5), páginas 63–75, 2013.