Ma ke ing Compu acional: Diseño
Au omá ico de P oduc os
____________
MEMORIA DEL PROYECTO
S ephania C is ina Hinos oza Hualpa
Bo ja Salaza Rey
Di igido po Ismael Rod íguez Laguna
T abajo de Fin de G ado en Ingenie ía In o má ica
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
Sep iemb e 2016
Uni e sidad Complu ense de Mad id
Depa amen o de Sis emas In o má icos y Compu ación
Mad id, España
Ma ke ing Compu acional: Diseño
Au omá ico de P oduc os
Memo ia pa a op a al G ado de Ingenie ía In o má ica
P esen ada po
S ephania C is ina Hinos oza Hualpa
Bo ja Salaza Rey
Di ec o :
Ismael Rod íguez Laguna
I
Au o ización de di usión y u ilización
T abajo de Fin de G ado
Ma ke ing Compu acional: Diseño Au omá ico de P oduc os
Cu so 2015/2016
Los abajo i man es, alumnos y u o del T abajo Fin de G ado (TFG) en el G ado
en Ingenie ía In o má ica de la Facul ad de In o má ica, au o izan a la Uni e sidad
Complu ense de Mad id (UCM) a di undi y u iliza con ines académicos, no
come ciales y mencionando exp esamen e a su au o el T abajo Fin de G ado (TFG)
cuyos da os se de allan a con inuación. Así mismo au o izan a la Uni e sidad
Complu ense de Mad id a que sea deposi ado en acceso abie o en el eposi o io
ins i ucional con el obje o de inc emen a la di usión, uso e impac o del TFG en
In e ne y ga an iza su p ese ación y acceso a la go plazo.
Di igido po Ismael Rod íguez Laguna que pe enece al depa amen o de
Sis emas In o má icos y Compu ación.
S ephania C is ina Hinos oza Hualpa Bo ja Salaza Rey
Ismael Rod íguez Laguna

II
III
Ag adecimien os
P incipalmen e nos gus a ía ag adece a nues o di ec o de p oyec o Ismael
Rod íguez Laguna, po la con ianza que ha deposi ado en noso os y po los
conocimien os que nos ha ansmi ido a lo la go del desa ollo del p oyec o. También
que emos menciona al p o eso Pablo Rabanal po ayuda nos a esol e las dudas que
hemos enido en cie o momen o. Po úl imo, ag adece a la emp esa Feebbo po
pe mi i publica nues as encues as y pode u iliza a sus clien es como encues ados.
Du an e es os meses hemos ap endido cómo lle a el p oyec o pese a que
hemos enido buenos y malos momen os, sin emba go, nues o di ec o siemp e ha
es ado ahí pa a da nos ideas y posibles soluciones que nos ayudado a esol e los
p oblemas noso os mismos. Po eso ag adecemos su implicación con noso os y el
sabe deci nos las cosas en cada momen o.
En es e apa ado de ag adecimien os que emos menciona a los pila es más
impo an es de nues as idas y po el cual noso os es amos aquí, nues a amilia, que
siemp e nos han apoyado du an e es os años de ca e a, an o en los buenos como en
los malos momen os que hemos pasado. Así que es o a po y pa a oso os, g acias
po odo.
Me gus a ía menciona a pe sonas que han es ado apoyándome siemp e y
sob e odo es e úl imo año. Una pe sona undamen al en mi ida y que ha es ado día y
noche a mi lado cuando lo he necesi ado: Oma . A mis amigos de oda la ida que no
hace al a menciona los po que ellos saben quiénes son. A mis amigos de la
uni e sidad: Lau a, Samuel, Manu, Eddy, Jo ge y Ma iano, aquellos con los que he
compa ido día a día, y que saben en p ime a pe sona como han sido es os años de la
ca e a. Amigos que me han ayudado de alguna o ma es e úl imo año a base de
buenos consejos y de c í icas cons uc i as: Rica do y Ósca . G acias a odos oso os
po se como sois, po o ma pa e de mi ida y po es a cuando se os necesi a.
– S ephania –
Me gus a ía hace mención especial a cie as pe sonas que du an e es os dos
años de mi andadu a en Mad id han es ado ce ca de mí, escuchándome,
aguan ándome, y dándome consejos. Las pe sonas más impo an es du an e es a
e apa, que me ha dado la ue za cuando lo necesi ada y donde siemp e he encon ado
un apoyo, Susana. Y aunque ya se ha mencionado a la amilia, quisie a ema ca a mi
he mana Sa a, quien siemp e es un espaldo y que es e año ha conseguido ambién un
g an log o académico. Y a mis amigos de con ianza que siemp e es án ahí llue a o
nie e.
– Bo ja –
IV
V
Resumen
El obje i o de es e p oyec o es desa olla una aplicación mul ipla a o ma que,
dadas las p e e encias de los clien es po las posibles ca ac e ís icas que se pueden da
a un p oduc o, y dados los p oduc os que ende la compe encia, decida las
ca ac e ís icas del p oduc o a ende pa a que és e ob enga el mayo núme o de
clien es, bien de mane a inmedia a, o bien a la go plazo. La solución óp ima de es e
ipo de p oblemas es in a able, ya que no se pueden esol e en iempo polinómico,
po lo que noso os u ilizamos soluciones heu ís icas, conc e amen e: algo i mos
gené icos, algo i mos minimax, algo i mos de ap endizaje au omá ico y algo i mos de
in e polación.
Además, ealizamos un caso de es udio con da os eales ob enidos a a és de
una se ie de encues as u ilizando una pla a o ma web, conc e amen e de la emp esa
Feebbo, que nos pe mi ió ob ene esul ados sob e las p e e encias de más de 500
encues ados. Las p egun as de las encues as se cen a on en un ipo de p oduc o en
pa icula , en nues o caso elé onos mó iles.
Palab as cla e: algo i mos gené icos, algo i mos minimax, ma ke ing
compu acional, Ja a, In e polación, Weka, clus e s, Feebbo, PSO, SA.
XII
Índice de Figu as
Figu a 1 Diag ama Algo i mo Gené ico .......................................................................... 26
Figu a 2 Pseudocódigo del Algo i mo Gené ico ............................................................. 27
Figu a 3 Ejemplos de mejo solución global (Gbes ) y local (Lbes ) ............................... 29
Figu a 4 Esquema gene al de un algo i mo PSO ............................................................ 30
Figu a 5 Ejemplo de Algo i mo Minimax ........................................................................ 32
Figu a 6 Diag ama Algo i mo K-MEANS ......................................................................... 35
Figu a 7 He amien a WEKA ........................................................................................... 36
Figu a 8 He amien a WEKA – Algo i mo SimpleKMeans .............................................. 36
Figu a 9 Diag ama de Clases Abs acción ....................................................................... 50
Figu a 10 Diag ama de Clases Gene ales ....................................................................... 51
Figu a 11 Ejemplo de ejecución Algo i mo Gené ico ..................................................... 52
Figu a 12 Ejemplo de lis a de a ibu os gene ados ........................................................ 53
Figu a 13 Modi icación de da os de en ada.................................................................. 53
Figu a 14 Ejemplo de clus e ización ............................................................................... 54
Figu a 15 Ejemplo de ejecución Algo i mo Gené ico en And oid .................................. 54
Figu a 16 Ejemplo de con igu ación de a ian es en And oid ....................................... 55
Figu a 17 Modi icación de da os de en ada en And oid ............................................... 55
Figu a 18 Ejemplo de iche o Sin axis ............................................................................ 60
Figu a 19 Ejemplo de iche o Da os ............................................................................... 60
Figu a 20 Ejemplo de pe iles en o ma o x ................................................................. 61
Figu a 21 Ejecuciones Alea o ias Algo i mo Gené ico ................................................... 65
Figu a 22 Ejecuciones Alea o ias Algo i mo po Enjamb e de Pa ículas ...................... 66
Figu a 23 Ejecuciones Alea o ias Algo i mo de En iamien o Simulado ........................ 67
Figu a 24 Ejecuciones Alea o ias Algo i mo Minimax .................................................... 68
Figu a 25 Ejecuciones Da os Feebbo .............................................................................. 69
Figu a 26 Ejecución del Algo i mo Gené ico con a ios p oduc os ............................... 70
Figu a 27 Ejecución del Algo i mo po Enjamb e de Pa ículas con a ios p oduc os .. 71
Figu a 28 Ejecución del Algo i mo de En iamien o Simulado con a ios p oduc os. ... 72
Figu a 29 Ejecución de los cua o algo i mos, en la a ian e de maximiza bene icios. 73
Figu a 30 Ejecución de dos algo i mos u ilizando clus e ización ................................... 74
Figu a 31 Ejecución del algo i mo minimax con dis in as p o undidades ..................... 75
Figu a 32 Me odología Sc um ........................................................................................ 82

13
1. In oducción
En es e p ime apa ado de in oducción desc ibi emos b e emen e cómo
es a á es uc u ada la memo ia. Además, explica emos los obje i os que enemos
plan eados pa a ealiza el p oyec o de Ma ke ing Compu acional: Diseño Au omá ico
de P oduc os.
1.1 O ganización de la Memo ia
La memo ia es á es uc u ada de la siguien e o ma:
 En el p ime capí ulo, se exponen los obje i os del p oyec o.
 En el segundo capí ulo desc ibi emos los p oblemas que abo da á la aplicación.
 En el e ce capí ulo abo da emos el es ado del a e. Menciona emos las
ac i idades desa olladas po di e sas emp esas exis en es en la ac ualidad,
elacionadas con es udios de me cado.
 En el cua o capí ulo p esen a emos cómo hemos lle ado a cabo el diseño de
nues a aplicación.
 En el quin o capí ulo desc ibi emos las uncionalidades que iene nues a
aplicación an o pa a esc i o io como pa a And oid.
 En el sex o capí ulo menciona emos qué he amien as hemos elegido pa a
ealiza la implemen ación y los esul ados que o ecen.
 En el sép imo capí ulo se comen a á la implemen ación de la aplicación
mul ipla a o ma.
 En el oc a o capí ulo desc ibi emos las encues as que hemos ealizado en la
pla a o ma Feebbo, así como el ipo de p egun as ealizadas y los esul ados
ob enidos.
 En el no eno capí ulo p esen a emos los esul ados ob enidos en nues o caso
de es udio de la aplicación.
 En el décimo capí ulo da emos las conclusiones inales al desa olla es e
p oyec o. También discu i emos las posibles ex ensiones y mejo as que se
pueden da a es e p oyec o.
 En el undécimo capí ulo comen a emos el apa ado de abajo u u o,
desc ibiendo las di e sas ampliaciones que se pueden hace al p oyec o.
 El duodécimo capí ulo p esen a emos la o ganización del desa ollo del
p oyec o y la con ibución que cada uno hemos hecho cada miemb o del
g upo.
 En el decimo e ce capí ulo se á la bibliog a ía u ilizada.
14
 En el decimocua o capí ulo se ha á un esumen de los obje i os, conclusiones
y abajo u u o en inglés.
1.2 Obje i os
Los obje i os p incipales del p oyec o son:
1. Desa olla una aplicación que, a pa i de las p e e encias de los clien es sob e
las ca ac e ís icas de un p oduc o especí ico, y eniendo en cuen a los
p oduc os o ecidos po la compe encia, ob enga el p oduc o ideal de o ma
inmedia a o a la go plazo, es deci :
a) Diseña un p oduc o o almen e desde ce o, pa a maximiza el núme o
de clien es o pa a llega a un núme o de e minado de clien es; o bien
b) Diseña una es a egia que indique cómo i emos modi icando nues o
p oduc o a medida que la compe encia aya modi icando los suyos, de
o ma que ob engamos un núme o de clien es en un plazo de e minado
independien emen e de los cambios que hayan ealizado los
compe ido es.
Se conside a ambién una e sión al e na i a del p oblema an e io en
la que se es inge la echa lími e: el núme o de u nos no puede se
mayo que el núme o de a ibu os de p oduc os.
Nues a aplicación esol e á a ias a ian es de dichos p oblemas, y lo ha á
pe mi iendo aplica di e sos algo i mos di e en es. Además, o ece á an o una
e sión de esc i o io pa a Windows como una e sión de mó il pa a And oid.
2. Vamos a demos a la u ilidad de la aplicación lle ando a cabo un caso de
es udio ealis a comple o.
3. Finalmen e compa a emos los di e sos algo i mos en la esolución de di e sas
a ian es de los p oblemas plan eados.
Pa a log a es os p opósi os, se equie e lle a a cabo las siguien es
ac i idades:
 P o undiza en nues os conocimien os sob e algo i mos gené icos, algo i mos
de op imización po enjamb e de pa ículas, algo i mos de en iamien o
simulado, algo i mos minimax y algo i mos de in e polación pa a aplica los en
el desa ollo de nues a aplicación y de nues o caso de es udio.
 Diseña y lle a a cabo un conjun o de p egun as pa a las encues as que
pe mi an, a a és de la página web de Feebbo [1], ob ene esul ados eales
de las p e e encias de los encues ados sob e un p oduc o en conc e o, en
nues o caso elé onos mó iles.
15
 Ap ende dis in os algo i mos de clus e ización, pa a clasi ica a los
encues ados en clus e s o ganizados po simili ud.
 Diseña nues a aplicación, indaga qué he amien a podemos u iliza pa a que
sea mul ipla a o ma, y po úl imo las uncionalidades que que emos aba ca .
 Desa olla e implemen a la aplicación que nos si a pa a diseña el mejo
p oduc o.
 Mejo a la habilidad de p og amación en el lenguaje Ja a y ap ende a usa
unciones con enidas en sus lib e ías.
 E alua los esul ados de la aplicación y analiza los en unción de los p oduc os
ob enidos.
 Elabo a una documen ación que ecoja odo lo que hemos ealizado y que
pe mi a en un u u o amplia el p oyec o.
16
2. De inición del P oblema
(a) El p oblema P oduc Design Op imiza ion (PDO) consis e en lo siguien e.
Supongamos que nos dan un conjun o de a ibu os de p oduc os (po
ejemplo: colo , o ma, e c.), los subconjun os de alo es de a ibu os
disponibles pa a cada compe ido , los p oduc os que ende cada p oduc o
y las alo aciones de los alo es de cada a ibu o pun uadas po los clien es
de cada pe il (po ejemplo: cie o pe il lo alo a 3 sob e 5 que sea ojo). El
obje i o es selecciona los alo es de los a ibu os de nues o p oduc o (po
ejemplo: e de, cuad ado, e c.) de al mane a que se maximice el núme o
de clien es o se consiga un núme o de e minado de clien es.
(b) El p oblema Succeed in he P oduc Design Game (SPDG) consis e en lo
siguien e. Supongamos un juego en el que cada p oduc o modi ica po
u nos algunas ca ac e ís icas de su p oduc o, y en onces odos los clien es
uel en a escoge sus p oduc os p e e idos. Nos dan como pa áme os de
en ada pa a el juego: el núme o de a ibu os que cada p oduc o puede
modi ica de su p oduc o en cada u no, el núme o de u nos del juego y el
núme o de u nos p e ios en e los que se calcula á la media de clien es
ob enidos po cada p oduc o . La con igu ación de cada juego de ine en el
u no ac ual el p oduc o endido po cada p oduc o , y el núme o de
clien es conseguidos po cada p oduc o en cada uno de los úl imos u nos
del juego. El obje i o es encon a una es a egia que ga an ice que cie o
p oduc o alcanza á cie o núme o de e minado de clien es p omedio
du an e un cie o pe íodo de iempo independien emen e de las es a egias
de sus compe ido es.
(c) El p oblema Linea ly-Bounded SPDG (lSPDG) es idén ico al SPDG, aunque el
núme o de pasos del juego es á limi ado po el núme o de a ibu os.
En el a ículo [2], el di ec o del p esen e abajo y sus dos coau o es
demues an que es os p oblemas son NP-comple o, EXPTIME-comple o, y PSPACE-
comple o, espec i amen e, lo que demues a que encon a su solución óp ima es
in a able (es deci , que no pueden se esuel os en iempo polinómico) bajo
suposiciones es ánda .
Aunque la esolución de es os p oblemas de mane a óp ima pa a casos muy
pequeños puede se ac ible, es cla amen e in iable pa a la mayo ía de los casos con
amaños mayo es.
17
Es a di icul ad obliga al uso de soluciones heu ís icas pa a esol e es os
p oblemas. Po desg acia, ni siquie a el p oblema más simple (a), puede se bien
ap oximado en iempo polinómico en gene al, ya que además de se NP-comple o,
ambién es Poli-APX-comple o, cómo ambién se demues a en [2]. Es o implica que
no puede exis i un algo i mo polinómico que dé soluciones ap oximadas cuya a io
con las soluciones óp imas alcancen siemp e cie a cons an e.
La de inición y la di icul ad de dichos p oblemas se en a ec adas po el modelo
que ep esen a la p e e encia de los pe iles de los clien es sob e los p oduc os.
Conside amos que, pa a cada pe il de clien e, los clien es de dicho pe il asocian una
alo ación (un en e o posi i o) a cada alo de a ibu o. Los clien es eligen el p oduc o
cuya suma de alo aciones de los alo es de odos sus a ibu os sea la más al a (pa a
algunos clien es eales, algunas ca ac e ís icas pod ían se nega i as en luga de
posi i as, aunque un modelo que pe mi e alo aciones nega i as se puede con e i
i ialmen e en un modelo equi alen e que use solo alo aciones posi i as).
Al e na i amen e, supongamos que las p e e encias del clien e se de inen po
medio de las unciones más gene ales que, dados los alo es de los a ibu os de odos
los p oduc os disponibles, de uel e el p oduc o p e e ido. Supongamos que las únicas
condiciones impues as sob e es as unciones sean es as:
(i) Las p e e encias son ansi i as (es deci , si se p e ie e A sob e B y B en
C, en onces p e e imos A sob e C).
(ii) Las unciones que de uel en el p oduc o seleccionado se pueden
calcula en un iempo polinómico.
En nues o caso, las nue as e siones de los p oblemas se ían gene alizaciones
i iales de nues os p oblemas o iginales, po lo que man end ían su NP y Poli-APX-
du eza, EXPTIME- du eza, y PSPACE- du eza, espec i amen e.

18
3. Es ado del A e
A con inuación, comen amos di e en es emp esas que ealizan una
in es igación sob e es udios de me cado, a a és de las p e e encias de sus clien es
sob e un amplio núme o de p oduc os. Casi siemp e es e ipo de emp esas ealiza
es os es udios pa a ende las a compañías más g andes que es án in e esadas en los
esul ados que han ob enido, y o ecen una boni icación a los suje os encues ados
pa a hace su es udio.
 Consumolab [3]: es un cen o dedicado a la in es igación y es udios de las
p e e encias de consumo. Emplea écnicas de análisis y ma ke ing senso ial
pa a comp ende las p e e encias de los consumido es sob e un p oduc o y
qué se puede hace pa a di igi su éxi o en el me cado.
Además, o ece di e en es ipos de es udio:
1. Ma ke ing: es udio de compe ido es, ca ac e ización del p oduc o
ideal, selección del mejo p o o ipo en e a ios, in es igación de la
segmen ación de las p e e encias (clus e s), e c.
2. I+D: desa ollo e inno ación de p oduc os, e c.
3. Calidad: iempo de ida ú il del p oduc o, e c.
 PanelSillike [4]: Es una compañía in e nacional que o ece se icios pa a la
mejo a de la calidad y segu idad alimen a ia. Lle an a cabo es udios de
me cado pa a conoce la opinión de los consumido es ace ca de una mul i ud
de p oduc os. Es os es udios se ealizan a a és de se icios de análisis y
análisis senso ial.
El p opósi o de es os es udios es que las alo aciones de los consumido es
ayuden a los ab ican es a mejo a sus p oduc os.
 MySu ey [5]: es un panel de consumido es o mado po pe sonas que se
o ecen olun a iamen e pa a pa icipa en es udios de in es igación de
me cado.
 Su eyMonkey [6]: Emp esa que pe mi e c ea a los usua ios encues as en línea
y analiza los da os. Pe mi en el análisis de ex o, in eg ación SPSS y gene a
in o mes p o esionales.
 Feebbo [1]: Es una emp esa in e nacional que pe mi e c ea es udios de
me cados y selecciona un núme o pe sonas pa a que pa icipen en las
encues as. Se pueden e los esul ados en iempo eal y en di e en es
o ma os: Excel, SPSS, e c. Pos e io men e, es a emp esa se menciona á más
en de alle, debido a nues a colabo ación con ellos.
19
La mayo ía de es as emp esas u iliza la he amien a Fizz pa a ealiza sus
encues as, ya que les pe mi e ob ene de o ma e icien e el análisis senso ial de los
alimen os. Es e análisis iene como inalidad e alua a ibu os de p oduc os a a és de
los di e en es sen idos.
La en aja de u iliza es a he amien a es que apa e acele a y au oma iza los
análisis, educe de modo conside able el iempo de análisis de la in o mación
suminis ada po los consumido es y apo a nue os mecanismos pa a oma mejo es
decisiones.
Es os análisis de da os se basan en ealiza p o ocolos de p uebas, cap u a
espues as de los consumido es de mane a au omá ica, ealiza es adís icas y g á icos.
Las emp esas mencionadas ex aen las p e e encias de los usua ios sob e
di e sos aspec os, pe o no u ilizan dicha in o mación pa a a a de compone
au omá icamen e el p oduc o que ob end ía más clien es. Es en dicho segundo paso
en el que se cen a á nues a aplicación.
20
4. Diseño de la Aplicación
En es e apa ado explica emos la a qui ec u a de nues a aplicación, así como
las decisiones de diseño que hemos omado.
Desa olla nues a aplicación implica hace en e a dos p oblemas
concep ualmen e di e en es (ya que SPDG y lSPDG sólo se di e encian en el núme o de
u nos). En PDO, se c ea un p oduc o desde ce o que maximice el núme o de clien es.
Nues a aplicación esol e á es e p oblema median e el uso de un algo i mo gené ico,
un ipo de algo i mo que se puede aplica a una g an a iedad de p oblemas de
op imización NP-du os.
Además, se implemen an o os algo i mos de op imización que son al e na i os
al algo i mo gené ico: op imización po enjamb e de pa ículas y en iamien o
simulado. Ambos esol e án ambién el p oblema PDO. La inalidad de inclui es os
algo i mos es obse a los esul ados que o ece cada uno y compa a los.
En SPDG, se p e ende maximiza el núme o de clien es medios a la go plazo
den o de un sis ema de u nos (con su a ian e lSPDG, que es inge el núme o
máximo de u nos). Es e p oblema se esol e á median e un algo i mo minimax con
poda al a-be a, que es un mé odo comúnmen e u ilizado pa a esol e p oblemas de
juego EXPTIME-du os y PSPACE-du os.
Tomando como e e encia inicial las e siones básicas de ambos algo i mos que
ealizó el p o eso Pablo Rabanal pa a lle a a cabo los expe imen os expues os en [2],
es uc u amos el código de nues a implemen ación de la siguien e mane a:
 El p oyec o P oduc Design es á o ganizado en dis in os paque es:
a) Paque e Gene al: almacena las clases comunes pa a odos los
algo i mos y una in e az que implemen a á cada algo i mo.
b) Paque e Gene ic: ep esen a la implemen ación del algo i mo gené ico.
Con iene una clase abs ac a del algo i mo gené ico, y o a clase que la
implemen a.
c) Paque e Minimax: ep esen a la implemen ación del algo i mo
minimax. Con iene una clase abs ac a del algo i mo minimax, y o a
clase que la implemen a.
d) Paque e PSO: ep esen a la implemen ación del algo i mo de
op imización po enjamb e de pa ículas. Con iene una clase abs ac a
del algo i mo PSO, y o a clase que la implemen a.
21
e) Paque e SA: ep esen a la implemen ación del algo i mo de
en iamien o simulado. Con iene una clase abs ac a del algo i mo SA,
y o a clase que la implemen a.
) Paque e Inpu : pa a las clases que pe mi en lee los da os de en ada.
g) Paque e Ou pu : con iene clases que almacenan los esul ados.
h) Paque e GUI: que almacena la clase que implemen a la in e az pa a
esc i o io.
i) Paque e Main: ep esen a la clase p incipal del p oyec o de Ja a.
 El paque e Gene al engloba las siguien es clases:
a) A ibu e: ep esen a las ca ac e ís icas que se pueden asigna a un
p oduc o.
b) Cus ome P o ile: ep esen a la es uc u a de un pe il de clien e.
Con iene una lis a de a ibu os y cada pe il iene una lis a de
subpe iles.
c) P oduce : ep esen a a cada uno de los compe ido es. Un p oduc o
iene una lis a de a ibu os disponibles y un p oduc o.
d) P oduc : ep esen a a cada indi iduo de la población. Cada p oduc o
iene una lis a de a ibu os y su alo asignado.
e) In e pola ion: con iene los mé odos que pe mi en es ima el p ecio de
un p oduc o.
) LinkedA ibu e: ep esen a la implemen ación de una a ian e de
nues os p oblemas en la que cie as combinaciones de alo es de
a ibu os suponen una modi icación posi i a o nega i a de la alo ación
o al del p oduc o si an jun os. Es o pe mi e ep esen a si uaciones
donde las p e e encias de los clien es puedan se supe -adi i as o in a-
adi i as, lo que no es aba con emplado en los p oblemas o iginales.
g) P oblem: es a clase con iene la implemen ación de los mé odos que
son comunes pa a cada uno de los algo i mos. La inalidad de c ea es a
clase es abs ae los mé odos pa a acili a la ag egación de un
algo i mo nue o si así se equie e en un u u o, además de a o ece la
eu ilización de código y op imiza la implemen ación de la aplicación.
 Los paque es que hacen e e encia a cada algo i mo con ienen las
clases que los implemen an.
 El paque e Inpu ep esen a las clases que pe mi en gene a los da os
de en ada a a és de la in e az g á ica, lec u a de un a chi o x o
xml, o gene ando los da os alea o iamen e.
 El paque e Ou pu ep esen a las clases que mues an los esul ados
en la in e az g á ica y ambién se almacenan en un a chi o.
28
6.3 Algo i mo de Op imización po Enjamb e de
Pa ículas
El algo i mo de Op imización po Enjamb e de Pa ículas (en inglés Pa icle
Swa m Op imiza ion, de aho a en adelan e u iliza emos sus siglas PSO) es una écnica
de op imización en el campo del ap endizaje au omá ico.
Hace e e encia a una me aheu ís ica inspi ada en el compo amien o social de
las bandadas de a es al ola , así como a los mo imien os de los bancos de peces. Una
población de en idades se mue e po el espacio de búsqueda du an e la ejecución del
algo i mo. Es as en idades son muy simples y ealizan in e acciones locales. El
esul ado de la combinación de compo amien os simples es la apa ición de
compo amien os complejos y la posibilidad de ob ene buenos esul ados en equipo.
Se pa e del supues o de que la bandada busca comida en un á ea (el obje i o
del p oblema). Una buena es a egia pa a encon a la comida es segui al a e que más
es é comiendo en su posición, lo que indica que en dicha posición hay más comida
(mejo alo obje i o). PSO emula es e compo amien o pa a esol e p oblemas de
op imización. Cada solución o pa ícula es un a e en el espacio de búsqueda que es á
siemp e en mo imien o y nunca mue e. De hecho, se puede conside a que el
enjamb e es un sis ema mul iagen e donde las pa ículas son simples agen es que se
mue en a a és del espacio de búsqueda y memo izan la mejo solución encon ada
has a el momen o.
Cada elemen o del enjamb e iene un alo de i ness, una posición y un ec o
de elocidad que di ige su uelo.
Las siguien es ecuaciones ajus an la elocidad y la posición de cada pa ícula:
𝑉𝑖󰇗𝑡+1 =𝑤𝑡𝑉𝑖𝑡+𝑐1𝑟1
𝑡(𝑃𝑖−𝑋𝑖𝑡)+𝑐2𝑟2
𝑡(𝐺𝑖−𝑋𝑖𝑡)
𝑋𝑖𝑡+1 =𝑋𝑖𝑡+𝑉𝑖𝑡+1
Donde:
𝑉𝑖󰇗𝑡+1 es la elocidad ajus ada
𝑤𝑡 es la ine cia del p opio mo imien o
𝑐1 es el coe icien e de con ianza en la expe iencia
𝑐2 es el coe icien e de con ianza en la expe iencia del g upo
𝑃𝑖 es la mejo posición p e ia de 𝑖󰇗

29
𝑋𝑖𝑡 es la posición ac ual de 𝑖󰇗
𝐺𝑖 es la mejo posición p e ia encon ada po el g upo
𝑟1
𝑡 y 𝑟2
𝑡 son los ope ado es alea o ios en e 0 y 1
𝑋𝑖𝑡+1 es la posición de la pa ícula 𝑖󰇗 después del ajus e
El mo imien o de las pa ículas es guiado en pa e po la mejo solución
encon ada po odas las pa ículas. Conc e amen e, una pa ícula es á compues a de
cua o ec o es:
1. Un ec o que almacena la posición ac ual (localización) de la pa ícula
en el espacio de búsqueda.
2. Un ec o que almacena el ec o de elocidad de acue do al cual la
pa ícula se mue e.
3. Un ec o que almacena la localización de la mejo solución encon ada
po la pa ícula has a el momen o.
4. Un ec o que almacena la localización de la mejo solución encon ada
po el enjamb e y es común pa a odas.
Figu a 3 Ejemplos de mejo solución global (Gbes ) y local (Lbes )
3
También hay es alo es de i ness:
1. El p ime alo almacena el i ness de la solución ac ual.
2. El segundo alo almacena el i ness de la mejo solución local.
3. El e ce alo almacena el i ness de la mejo solución global.
3
h p://www.yo ku.ca/sychen/ esea ch/ heses/2011_Yenny_MSc.pd
30
El mo imien o de cada pa ícula depende de la mejo solución que ha
encon ado desde que se inició el algo i mo y de la mejo solución encon ada po
odas las pa ículas en oda la nube de pa ículas. Es e ipo de ecindad de las
pa ículas, donde odas las pa ículas en el enjamb e son a aídas po la mejo
solución, p opo ciona una ápida con e gencia del algo i mo. De acue do con es a
opología, la elocidad se cambia en cada i e ación del algo i mo pa a ace ca la a
posiciones donde es á la mejo solución local/global encon ada.
Figu a 4 Esquema gene al de un algo i mo PSO
4
6.4 Algo i mo de En iamien o Simulado
El algo i mo de en iamien o simulado (en inglés Simula ed Annealing, de aho a
en adelan e u iliza emos sus siglas SA) es un mé odo pa a encon a una solución
buena (no necesa iamen e pe ec a) a un p oblema de op imización.
En es e algo i mo se man iene una a iable de empe a u a pa a simula el
p oceso de en iamien o. Mien as la a iable de empe a u a es al a, se pe mi e al
algo i mo, con mayo ecuencia, acep a las soluciones que son peo es que la solución
4
h p://blade1.uniquindio.edu.co/uniquindio/ e is ain es igaciones/adjun os/pd /2bc6_46-53.pd
31
ac ual. Es o le da al algo i mo la capacidad de sal a desde cualesquie a óp imos
locales que se en en a al comienzo de la ejecución. A medida que se educe la
empe a u a, ambién se educe la posibilidad de acep a soluciones peo es, po lo
que el algo i mo se concen a g adualmen e en la zona del espacio de búsqueda se
espe an encon a soluciones ce canas a la solución óp ima.
Es e p oceso g adual de ‘en iamien o’ es lo que hace el algo i mo de
en iamien o simulado sea no ablemen e e icaz en la búsqueda de una solución
ce cana a la óp ima cuando se a a de p oblemas que con ienen nume osos óp imos
locales. En compa ación a o os algo i mos como el de Hill Climbing, nos pe mi e e i a
el p oblema de queda nos a ascados en óp imos locales, y es mucho mejo en
p omedio en su ap oximación al óp imo local.
Pa a que el algo i mo decida qué nue as soluciones acep a pa a e i a los
óp imos locales, comp ueba si la solución ecina conside ada en cada momen o es
mejo que la que iene ac ualmen e. Si es así, se acep a incondicionalmen e. Sin
emba go, si esa solución no es mejo , se ienen en cuen a más ac o es: cuán o peo es
la solución ecina; y la empe a u a ac ual. A al as empe a u as es más p obable que
acep e soluciones que son peo es.
La ecuación pa a calcula la p obabilidad de acep ación es la siguien e:
𝑎 =ⅇ𝛥𝐸∕𝑇
Donde 𝑎 es la p obabilidad de acep ación, 𝐸 es la ene gía del sis ema y 𝛥 es la
di e encia en e el es ado ac ual y el nue o alo calculado, 𝑇 es la empe a u a y ⅇ es
2.71828.
Básicamen e, cuan o meno sea la di e encia de cos es y más al a la
empe a u a, más p obable es que el algo i mo acep e la nue a solución.
6.5 Algo i mo Minimax
El Algo i mo Minimax [10] consis e en u iliza una unción de e aluación
heu ís ica exhaus i amen e pa a cie o núme o de con igu aciones u u as posibles de
un juego. Es un algo i mo de decisión que ayuda a minimiza la máxima pé dida
espe ada en un juego de ad e sa ios.
El algo i mo a a de selecciona el mejo mo imien o suponiendo que nues o
con incan e elegi á después el peo pa a noso os. Es o se ealiza de o ma ecu si a
has a que se cumpla alguna de las siguien es condiciones:
32
 Que gane algún jugado .
 Que ya se hayan explo ado N ni eles, siendo el N el núme o máximo de
ni eles ( u nos u u os) a explo a .
 Que se haya e minado el iempo de explo ación.
 Que se haya llegado a un ni el donde no se puede ealiza ningún
cambio.
Figu a 5 Ejemplo de Algo i mo Minimax
5
La aplicación a nues o p oblema se explica á en más de alle pos e io men e,
en la sección de implemen ación.
6.6 Algo i mo de In e polación
Pa a de ini las ins ancias a abo da en nues o caso de es udio, necesi amos
es ima el p ecio de cada posible elé ono mó il en unción de sus ca ac e ís icas, pues
po cada ca ac e ís ica añadida, el p ecio del mó il aumen a, pe o si iene menos
ca ac e ís icas (o más ba a as), el p ecio disminuye. Pa a calcula la es imación del
p ecio u ilizamos mé odos de in e polación.
El p oblema de la in e polación [11] consis e en, pa iendo de una unción de la
que sólo conocemos una se ie de pun os, halla el alo de nue os pun os de esa
unción, o incluso ob ene una ap oximación de la exp esión que de ine la p opia
unción.
5
Wikipedia - Ejemplo de Algo i mo Minimax: h ps://es.wikipedia.o g/wiki/Minimax
33
En nues o caso, necesi amos ealiza una in e polación mul i a iable [12], ya
que enemos que ene en cuen a más de una ca ac e ís ica de un elé ono mó il.
In es igando en el campo, encon amos algunas he amien as que a p io i
pod ían se álidas: A cGIS [13] y Ma Lab [14].
A cGIS consis e en un conjun o de he amien as que ienen di e en es
uncionalidades, en e ellas, modelado y análisis espacial en in o mación ás e . Lo que
más nos in e esaba de odas sus he amien as e a la de In e polación [15], pe o
p on o nos dimos cuen a que los alo es de en ada que u ilizaba A cGIS e an
necesa iamen e imágenes. Po lo an o, u imos que desca a es a he amien a.
Ma Lab nos p opo cionaba di e en es unciones pa a in e pola da os con los
dis in os algo i mos exis en es [16], pe o ambién decidimos no u iliza lo po que
necesi ábamos p oba in e polación con más de 50 a iables, opción que no
p opo cionaba di ec amen e Ma Lab.
Así que decidimos implemen a nues o p opio mé odo de in e polación.
Teníamos dos o mas de hace lo:
1. Es ima una unción lineal que enga an os pa áme os de en ada como
ca ac e ís icas enga el mó il y nos de uel a el p ecio. Se puede in e pola a
pa i de los p ecios de mó iles eales que u iliza emos pa a modeliza la
compe encia, de o ma que cada uno de es os mó iles (jun o con su p ecio
conocido) es un pun o de dicha unción. Es e modelo lineal no iene en cuen a
que el p ecio de una ca ac e ís ica puede depende de que cie as
ca ac e ís icas ayan jun as o no. Pa a es ima heu ís icamen e los pesos de
cada pa áme o en la unción lineal, podemos u iliza un algo i mo gené ico:
cada indi iduo (c omosoma) es una combinación conc e a de pesos, y la
unción de i ness de uel e la suma de las dis ancias en e el p ecio eal de
cada mó il que se conoce y el p ecio que es ima ía esa unción (o el cuad ado
de esas dis ancias, pa a que aleja se po mucho penalice más).
2. El alo de un pun o X de una unción se calcula como la media ponde ada del
alo obse ado de dicha unción en odos los pun os (X1, X2, ..., Xn) de la
mues a conocida, donde el peso de cada Xi es in e samen e p opo cional a su
dis ancia a X.
De es as dos opciones decidimos hace la implemen ación de la media ponde ada,
u ilizando la siguien e ó mula:
𝑝𝑟ⅇ𝑐𝑖𝑜(𝑥)= ∑ (𝑝𝑟ⅇ𝑐𝑖𝑜(𝑥𝑖)∗𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑖𝑎(𝑥,𝑥𝑖)
∑𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑖𝑎(𝑥,𝑥𝑗)
𝑗 ∈ 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜 )
𝑖 ∈ 𝑝𝑟𝑜𝑑𝑢𝑐𝑡𝑜

34
donde asumimos que 𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑖𝑎(𝑎,𝑏) es la dis ancia que hay desde el
p oduc o a has a el p oduc o b, de inidos po los alo es de sus a ibu os (𝑎1,…,𝑎𝑛 y
𝑏1,…,𝑏𝑛 espec i amen e).
𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑖𝑎(𝑎,𝑏)=√|𝑎1−𝑏1|2+|𝑎2−𝑏2|2+ |𝑎3−𝑏3|2+ ⋯+ |𝑎𝑛−𝑏𝑛|2
6.7 Algo i mo de Ag upamien o
Hemos añadido el es udio de es e ipo de algo i mos al desa ollo de nues o
p oyec o, debido a que e a el más idóneo pa a la colabo ación con la emp esa Feebbo,
ya que necesi aban un p og ama que les pe mi a clasi ica a sus clien es en g upos
o ganizados po simili ud. El a o que hicimos con Feebbo ue in o mación po
in o mación, es deci , ayuda les con clus e ización a cambio de usa su pla a o ma
pa a pode ealiza nues a encues a.
Además, nos pa eció in e esan e inco po a lo en nues a aplicación pa a
clasi ica los usua ios de mó iles. Conc e amen e, podemos c ea la población inicial
del algo i mo gené ico, PSO, e c., de o ma que, pa a cada clús e de pe iles de
clien es, uno de los indi iduos iniciales sea un p oduc o diseñado ( o azmen e) pa a
esul a a ac i o a los pe iles ag upados en dicho clús e .
Un algo i mo de ag upamien o [17] [18] (llamado ambién clus e ing) es un
p ocedimien o de ag upación que consis e en di idi las ins ancias de un conjun o de
da os po g upos de ins ancias simila es. Pa a medi la simili ud en e obje os se
suelen u iliza di e en es o mas de dis ancia: dis ancia Euclídea, de Manha an, e c.
Los mé odos de ag upamien o se di iden en es g upos undamen ales:
je á quicos, pa icionales y basados en densidad. En es e caso, hemos decidido u iliza
un algo i mo que pe enece al g upo de los pa icionales, es deci , que son aquellos
que ealizan una di isión inicial de los da os en g upos y luego mue en los obje os de
un g upo a o o según se op imice alguna unción obje i o.
Es os algo i mos asumen un conocimien o a p io i del núme o de clus e s en
que debe se di idido el conjun o de da os, y p opo cionan una di isión en clases que
op imiza un c i e io p ede inido o unción obje i o. El algo i mo que amos a emplea
es K-means.
35
6.7.1 K-MEANS
K-means es uno de los mé odos de ag upamien o más conocidos y más
u ilizados en aplicaciones cien í icas e indus iales [17].
La idea p incipal es escoge k cen oides al aza que ep esen a án el cen o del
g upo que p e ende ep esen a , luego oma cada pun o del conjun o de da os y
si ua lo en la clase de su cen oide más ce cano. El siguien e paso es ecalcula el
cen oide de cada g upo y ol e a dis ibui odos los obje os según el cen oide más
ce cano. Es e p oceso es i e a i o, ya que se epi e has a alcanza el c i e io de pa ada,
po ejemplo, que no haya ningún cambio en los g upos de un paso al siguien e.
A di e encia de o os algo i mos, k-medias necesi a la p e ia especi icación del
núme o de clus e s que se desean ob ene .
Figu a 6 Diag ama Algo i mo K-MEANS
6
Realizamos una in es igación pa a e si exis ía alguna he amien a de
ap endizaje au omá ico que nos pe mi a u iliza es e ipo de algo i mo y si nos se ía
ú il, o po el con a io end íamos que ealiza noso os la implemen ación. Finalmen e
encon amos la he amien a Weka, que nos ue ácil de usa siguiendo un u o ial
básico [19] [20], así como el api [21] de es a he amien a.
La implemen ación del algo i mo explicado en es e apa ado es ambién la que
iene Weka.
6.7.2 WEKA
Weka [22] es una pla a o ma de so wa e que con iene una colección de
algo i mos de ap endizaje au omá ico pa a a eas de mine ía de da os, esc i o en Ja a
y desa ollado en la Uni e sidad de Waika o. Es un so wa e de código abie o con una
licencia GNU-GPL [23].
6
Algo i mo K-Means: h ps://es.wikipedia.o g/wiki/K-means
36
Los algo i mos se pueden aplica a un conjun o de da os po medio de su
in e az o bien pueden se llamados di ec amen e desde su p opio código Ja a [24].
Weka con iene di e sas he amien as de da os: p e-p ocesamien o,
clasi icación, eg esión, clus e ing, eglas de asociación, y la isualización.
Además, es a he amien a cuen a con un eposi o io de ejemplos [25], con un
ipo de o ma o especí ico que podemos u iliza pa a ealiza dis in as p uebas y e
cómo unciona.
Figu a 7 He amien a WEKA
En nues o caso, u ilizamos la opción clus e ing, y aplicamos el algo i mo
SimpleKMeans. Tenemos la opción de elegi el ipo de dis ancia. Noso os
seleccionamos dis ancia Euclidean. Además, podemos decidi el núme o de clus e s
que que emos que ob ene .
Figu a 8 He amien a WEKA – Algo i mo SimpleKMeans
37
En la colabo ación con la emp esa Feebbo pa a clasi ica sus clien es en clus e s
po simili ud, decidimos u iliza la he amien a Weka, pues o que nos pe mi ía
isualiza los esul ados y ob ene los de o ma au omá ica.
Po o o lado, ambién añadimos a nues a implemen ación de Ja a la lib e ía
de Weka, pa a in eg a lo en nues a aplicación como nue a uncionalidad y pode
clasi ica a los usua ios ep esen ados en cualquie ins ancia con la que deba abaja
nues a aplicación.
44
Los mé odos abs ac os a implemen a po el p oblema son los siguien es:
 Un mé odo pa a ob ene el Fi ness.
 Mé odos pa a ob ene el espacio de mo imien os de juego sob e el que
abajamos pa a pode ealiza los cambios en el obje o en cada u no de
juego.
 Un mé odo (se Solu ion) pa a pode ealiza el mo imien o escogido po el
jugado .
El mé odo inicial de es a clase i e a, pa a cada uno de los jugado es, odos los
u nos has a e mina el juego.
En cada uno de es os u nos se ejecu an dos mé odos. El p ime o se enca ga de
cambia el obje o a mejo a . Pa a ello, comienza a c ea el á bol de soluciones, que
median e una unción ecu si a comienza a busca el cambio óp imo.
Una ez hecho el cambio, se ac ualizan los esul ados ob enidos po ese
jugado , y se ealiza el cambio median e la unción se Solu ion. A con inuación,
hacemos lo mismo con el o o jugado , y luego el u no uel e a comenza .
Al e mina el p oceso, el obje o ideal debe queda almacenado pa a cada
jugado median e la unción se Solu ion que se ejecu a al inal de cada u no.
7.2.3.2 S AB
La clase S AB ep esen a la es uc u a de al a-be a, la cual se usa pa a gua da
los cambios ob enidos po las amas del minimax, y pode compa a los al inal del
algo i mo.
7.2.4 Paque e PSO
En es e paque e se encuen a la clase que ep esen a la implemen ación del
algo i mo de op imización po enjamb e de pa ículas.
7.2.4.1 PSO Algo i hm
La clase PSOAlgo i hm ep esen a la implemen ación del algo i mo PSO,
independien e del p oblema al que quie a se aplicado.
En es a clase de inimos:

45
 Una lis a que gua da el enjamb e con el que ealiza emos el algo i mo.
 Va iables de con igu ación, como la elocidad ope, el ac o de con ianza
en la expe iencia, o alo es pa a el cálculo de alo ación de la p opia
ine cia.
 La lis a de las elocidades de las pa ículas del enjamb e.
 Va iables pa a gua da el Fi ness ob enido de cada una de las pa ículas, así
como la mejo pa ícula ob enida has a la echa.
Los mé odos abs ac os a implemen a po el p oblema son los siguien es:
 Un mé odo pa a ob ene el Fi ness.
 Un mé odo pa a inicializa el enjamb e inicial.
 Un mé odo pa a ob ene la localización ac ual de una pa ícula.
 Y un úl imo mé odo pa a ac ualiza la posición de una pa ícula.
El mé odo inicial de es a clase (sol ePSOAlgo i hm) es el enca gado comenza
con el algo i mo.
En p ime a ins ancia, c eamos el enjamb e inicial, y ob enemos pa a cada una
de las pa ículas una elocidad alea o ia.
A con inuación, i e amos po un núme o de eces de e minado el enjamb e, el
cual se i á mo iendo sob e nues o espacio de soluciones pa a ob ene la pa ícula
óp ima. En cada una de es as i e aciones hab á a ios pasos.
El p ime paso es ac ualiza nues o enjamb e con las posibles mejo es
pa ículas que haya encon ado. Inmedia amen e después ac ualizamos el mejo
indi iduo que enemos, en el caso de habe lo mejo ado.
En el úl imo paso i e amos po cada pa ícula del enjamb e, y pa a cada una de
ellas, ob enemos una nue a elocidad, basada en su es ado p e io y en la posición de
la mejo pa ícula encon ada. Después de ene la nue a elocidad, ac ualizamos la
posición en base a ella.
Al e mina las i e aciones se ac ualizan los Fi ness.
Cuando el algo i mo concluye, es de uel a la mejo pa ícula hallada.
7.2.5 Paque e SA
En es e paque e se encuen a la clase que ep esen a la implemen ación del
algo i mo de en iamien o simulado.
46
7.2.5.1 SA Algo i hm
La clase Simmula edAnnealingAlgo i hm ep esen a la implemen ación del
algo i mo SA, independien e del p oblema al que quie a se aplicado.
En es a clase de inimos:
 La empe a u a inicial.
 La empe a u a ac ual.
 El a io de en iamien o.
Los mé odos abs ac os a implemen a po el p oblema son los siguien es:
 Un mé odo pa a ob ene el Fi ness.
 Un mé odo pa a pe mi i que el algo i mo pueda cambia el obje o con el
que es á abajando.
El mé odo inicial de es a clase (sol e_SA) es el enca gado comenza con el
algo i mo.
T abaja emos con dos obje os, el mejo obje o encon ado, y el ac ual.
Es e algo i mo comienza con la empe a u a en su máximo, e i e a has a que la
empe a u a llega al mínimo. Du an e la ejecución de cada i e ación c eamos un
obje o nue o, y luego ob enemos su Fi ness median e el mé odo abs ac o ge Fi ness,
compa amos los Fi ness de cada p oduc o y nos quedamos con el mejo o no,
dependiendo de una p obabilidad dependien e de la empe a u a.
Cuando el algo i mo e mina, el mé odo p incipal de uel e el obje o óp imo,
modelado a base de i e aciones.
7.2.6 Paque e Inpu
En es e paque e se almacenan las clases que desc iben las dis in as o mas de
lee los da os de en ada.
7.2.6.1 Inpu Random
La clase Inpu Random ep esen a los mé odos que pe mi en gene a los da os
de en ada alea o iamen e. Gene a a ibu os, p oduc o es, pe iles, subpe iles y
núme os de pe iles de clien es. Los subpe iles se gene a on pa a ene en cuen a
47
ambién los g upos mino i a ios y no desp ecia ninguna alo ación. La c eación de los
subpe iles se omi ió pa a el algo i mo Minimax, ya que es un algo i mo bas an e
cos oso, y mul iplica el núme o de pe iles con los que juega lo ha ía más cos oso
oda ía. También se pueden gene a alea o iamen e los a ibu os enlazados (es deci ,
combinaciones de ellos con boni icaciones o penalizaciones si an jun os).
Dispone de un cons uc o , mé odos ge e s y se e s comunes en las demás
clases.
7.2.6.2 Inpu GUI
La clase Inpu GUI ep esen a los mé odos que pe mi en lee los da os de
en ada in oducidos po la in e az g á ica pa a gene a a ibu os, p oduc o es,
pe iles y núme os de pe iles de clien es. También se pueden gene a los a ibu os
enlazados in oduciendo los da os co espondien es.
A su ez, los da os que se añaden a a és de la in e az g á ica pueden se
gua dados en un a chi o x o xml pa a u u as p uebas. Además, en es a clase se
encuen an ambién los mé odos que pe mi en ob ene los da os de en ada de un
a chi o x y xml.
Pa a ealiza la lec u a y esc i u a de un a chi o x , u ilizamos las clases de Ja a
Scanne y P in W i e espec i amen e. Pa a ealiza la lec u a y esc i u a de un
a chi o xml u ilizamos DOM (Documen Objec Model), que es un api de Ja a pa a el
p ocesamien o de XML.
Dispone de un cons uc o , mé odos ge e s y se e s comunes en las demás
clases.
7.2.6.3 Inpu Weka
La clase Inpu Weka ep esen a la implemen ación del algo i mo de
ag upamien o pa iendo de los pe iles de clien es gene ados como da os de en ada.
Los mé odos u ilizados en es a clase son impo ados de la lib e ía de Weka en Ja a.
C eamos y con igu amos el algo i mo SimpleKMeans pa a ealiza la
clus e ización.
Ca gamos los da os de en ada de un a chi o cs y ealizamos un il ado que
nos pe mi e cambia los a ibu os numé icos a nominales, con la inalidad no de
48
ob ene núme os eales en los cen oides, sino de que pueda selecciona alo es que
es án den o de un ango especí ico.
Cons uimos el algo i mo de clus e ización e iden i icamos el clus e de cada
ins ancia, y po úl imo calculamos los cen oides.
Dispone de un cons uc o , mé odos ge e s y se e s que nos pe mi en
ob ene el núme o de clus e s y modi ica lo.
7.2.7 Paque e Ou pu
En es e paque e se almacenan las clases en los que se almacena los da os de
salida.
7.2.7.1 Ou pu CSV
La clase Ou pu CSV iene un mé odo que gene a un a chi o cs a a és de los
pe iles de clien es gene ados, con la inalidad de que ese a chi o se pueda pasa
como da os de en ada en Weka.
7.2.7.2 Ou pu Resul s
La clase Ou pu Resul s iene un mé odo que gene a un a chi o x que
almacena los esul ados de las ejecuciones de cada uno de los algo i mos.
7.2.7.3 Show Resul s
La clase ShowResul s ep esen a los mé odos que mues an las lis as gene adas
po cada algo i mo: a ibu os, p oduc o es, pe iles y subpe iles.
7.2.8 Paque e GUI
En es e paque e se almacena la clase que ep esen a la implemen ación de la
in e az g á ica pa a esc i o io.
49
7.2.8.1 GUI
La clase GUI ep esen a la in e az g á ica del p og ama pa a isualiza los da os
ob enidos po cada uno de los algo i mos, así como la implemen ación de los e en os
con los que in e ac uamos.
Se ealizan in ocaciones a mé odos las clases que ep esen an cada algo i mo
pa a solici a su ejecución.
La in e az mues a los esul ados del algo i mo y el iempo que a da en
ejecu a se. Además, pe mi e ealiza modi icaciones de los da os de en ada y de
da os gene ales, y ambién de los esul ados que se ob ienen al ealiza la
clus e ización.
7.2.9 Paque e Main
7.2.9.1 Main
La clase Main ep esen a la clase p incipal del p og ama. En es a clase
llamamos a la clase GUI pa a ejecu a la aplicación.
7.3 Objec Aid UML Explo e
Objec Aid UML Explo e es una he amien a pa a o ganiza la c eación y
isualización de diag amas en UML en Eclipse.
En es os diag amas de clase UML se mues a los mé odos del código uen e de
Ja a. Cualquie cambio que se ealice en el código de la clase Ja a au omá icamen e se
e e lejado en el diag ama.
En es e caso, hemos elegido es a he amien a de isualización po que es muy
sencilla de u iliza , y nos pe mi e ins ala lo como un plugin de Eclipse.
7.3.1 Diag ama de Clases
En es e apa ado mos amos un diag ama de clases con las clases más
ele an es del p oyec o Ma ke ing Compu acional.

50
Figu a 9 Diag ama de Clases Abs acción
En la Figu a 9 se mues a el diag ama de clases que con iene la abs acción del
código. La clase P oblem con iene los mé odos implemen ados pa a nues o p oblema
en pa icula . Las demás clases ep esen an la implemen ación de los algo i mos y sus
mé odos co espondien es. Cada algo i mo iene una elación di ec a con la clase
P oblem.
51
Figu a 10 Diag ama de Clases Gene ales
En la Figu a 10 se mues an las clases comunes que ienen odos los algo i mos
que se han implemen ado en es e p oyec o y las elaciones di ec as que ienen en e
sí.
7.4 In e az G á ica
Pa a desa olla la aplicación pa a esc i o io, p ime o u ilizamos Ne Beans, que
es un en o no de desa ollo in eg ado lib e y g a ui o que nos pe mi e gene a una
in e az de usua io. No obs an e, nos dimos cuen a de que gene aba muchas líneas de
código y de que empeo aba el endimien o. Finalmen e, decidimos implemen a la
in e az desde ce o en Ja a.
Además, que íamos o ece al usua io la posibilidad de abaja con nues a
aplicación de la o ma que más cómoda le esul e. Po ello, decidimos hace nues a
aplicación mul ipla a o ma y, en pa icula , o ece la ambién pa a disposi i os
And oid.
52
U ilizamos And oid S udio, que es un en o no de desa ollo in eg ado pa a la
pla a o ma And oid. La implemen ación de es a in e az se ealiza en Ja a, y además
iene una licencia Apache 2.0 de uso g a ui o.
7.4.1 In e az pa a Esc i o io
Nues a in e az cons a de los siguien es paneles:
a) Un panel po cada algo i mo (gené ico, minimax, PSO y SA) que o ece los
esul ados as su ejecución.
b) Un panel que mues a las lis as de a ibu os, p oduc o es, pe iles y
subpe iles que se gene an al ealiza cada algo i mo.
c) Un panel pa a modi ica los da os de en ada comunes pa a cada algo i mo,
es deci , se pueden modi ica los a ibu os, p oduc o es y pe iles. Al lado
podemos e qué a ibu os se es án añadiendo con sus espec i as
ca ac e ís icas.
d) Un panel que pe mi e modi ica los da os gene ales, ales como núme o de
ejecuciones y po cen ajes de a ibu os conocidos, e c. También se pueden
modi ica las a iables p opias de cada algo i mo.
e) Po úl imo, un panel que mues a los esul ados de Weka al ealiza la
clus e ización. Podemos obse a las ins ancias que pe enecen a cada
clus e y cuáles son los cen oides.
Mos amos unas imágenes de ejemplo de la in e az g á ica pa a esc i o io:
Figu a 11 Ejemplo de ejecución Algo i mo Gené ico
53
Figu a 12 Ejemplo de lis a de a ibu os gene ados
Figu a 13 Modi icación de da os de en ada
60
8.3 Resul ados de las Encues as
Finalmen e, Feebbo nos p opo cionó los esul ados de la encues a (en es e caso
se pa iciona on en es encues as pa ciales) en a chi os cs . El p ime a chi o, de
sin axis, con enía las p egun as de la encues a y sus espues as (cada espues a enía
asignada un código). El segundo a chi o, de da os, con enía los da os del encues ado y
sus espec i as espues as de la encues a (especi icadas con códigos).
Figu a 18 Ejemplo de iche o Sin axis
Figu a 19 Ejemplo de iche o Da os
Pa a a a es os da os, u imos que adap a lo al o ma o que ya eníamos
p ede inido en un documen o de ex o, eniendo en cuen a las espues as que había

61
elegido cada pe sona encues ada, y así ob ene los a ibu os, p oduc o es y pe iles de
clien es.
Pa a c ea los pe iles, decidimos ene en cuen a dos da os especí icos de cada
pe sona: la edad y el ni el de es udios.
Las edades de odas pe sonas que ealiza on la encues a pe enecían a un ango
de 14 a 74 años, de los cuales decidimos ag upa los en 3: p ime ango de 14 a 29
años, segundo ango de 30 a 49 años y el e ce ango 50 a 74 años.
Los ni eles de es udios de las pe sonas que han ealizado la encues a son:
doc o ado, mas e , educación secunda ia, educación p ima ia, g ado en la uni e sidad,
educación ocacional, mas e en la uni e sidad, educación supe io .
Ag upamos los pe iles po su edad y, den o de cada ango de edad, po cada
ni el de es udio, po ejemplo:
Pe il 1: Edad 14 -29 años y doc o ado.
Pe il 2: Edad 14 - 29 años y más e .
Pe il 3: Edad 14 – 29 años y educación p ima ia.
En cuan o a los alo es de las alo aciones dadas po cada pe il, se asignan
dependiendo del ipo de p egun a habiendo dos ipos posibles: p egun as sob e
ca ac e ís icas especí icas que no sean buenas ni malas en sí mismas (po ejemplo: iOs
o And oid), y p egun as que p egun en po algo in ínsecamen e posi i o,
conc e amen e sob e cómo de impo an e conside a el encues ado dicha
ca ac e ís ica ("poco impo an e", "algo impo an e", "impo an e", "bas an e
impo an e", "muy impo an e").
Figu a 20 Ejemplo de pe iles en o ma o x
62
El núme o de pe sonas que ealiza on las es encues as pa ciales ue on 535,
1500 y 1502 espec i amen e.
En el siguien e apa ado se desc ibi án los expe imen os en los que los da os de
en ada de nues os p oblemas ue on los gene ados a pa i de los esul ados de
dicha encues a.
8.4 Análisis de la Compe encia
Después de habe ealizado una in es igación sob e ele onía mó il, a
con inuación lis amos odos aquellos mó iles que hemos u ilizado pa a modeliza la
compe encia del p oduc o que hemos diseñado con la aplicación. También
menciona emos sus ca ac e ís icas, pa a pode obse a las di e encias que hay en e
cada uno de ellos. Toda es a in o mación la hemos ecopilado de la página Ube gizmo
[31].
Las ca ac e ís icas que u iliza emos de cada mó il son las que mismas sob e las
que se han p egun ado en las encues as. Los mó iles que hemos seleccionado son:
iPhone 6s, Samsung Galaxy s6, BQ Aqua is M5.5, One Plus 2, Huawei P8 Li e, Sony
Xpe ia Z4, Nexus 5X, Meizu M2 No e, LG G4 y Nokia Lumia 730.
Ejemplo de elé ono mó il conside ado, jun o con algunas de sus
especi icaciones écnicas conc e as:
Iphone 6s:
 Dimensión de pan alla: 4.7’’ mediana (4’’- 5’’) sob e g ande (más de 5’’) o
pequeña (menos de 4’’).
 Sis ema ope a i o iOS sob e And oid, Windows Phone o Symbian.
 Ba e ía no ex aíble sob e si ex aíble.
 Fo ma de pan alla ác il sob e eclado deslizan e, pan alla y eclado.
 Tipo de SIM: Nano SIM sob e SIM no mal, Mic o SIM.
 Bo ones de na egación ác iles sob e ísicos.
 Tac o de apa ase a liso sob e sua e o ugoso.
 Ma e ial del mó il: me al sob e c is al o plás ico.
Los demás mó iles con sus espec i as ca ac e ís icas se adjun an en un
documen o sepa ado jun o con la memo ia.
63
9 Resul ados de la Aplicación
En es e apa ado se desc ibe los esul ados inales de los expe imen os
ealizados an o pa a el caso de es udio eal sob e mó iles como pa a ins ancias
alea o ias, y las explicaciones co espondien es sob e dichos esul ados.
Después de implemen a odos los algo i mos mencionados y gene a un
documen o de ex o con los esul ados de las encues as p opo cionadas po Feebbo, el
cual p opo ciona los da os de las ins ancias de nues os p oblemas que que emos
esol e en elación a nues o caso de es udios sob e mó iles, mos amos los g á icos
que e lejan las ejecuciones de cada uno de los algo i mos y sus espec i os esul ados.
Las ins ancias alea o ias de ambos p oblemas a esol e en nues os
expe imen os se cons uye on de la siguien e o ma. Se conside an 63 a ibu os con 5
alo es posibles pa a la cons ucción de cada una de las ins ancias PDO, mien as que
10 a ibu os con 2 alo es posibles se u iliza on pa a SPDG. En ambos casos, los
pe iles de clien e se c ea on de es a mane a. La alo ación que cada pe il de clien e
da a cada alo del a ibu o es siemp e en e 0 y 5. Inicialmen e, cua o pe iles ue on
c eados al aza . A con inuación, pa a cada uno de ellos c eamos dos a ian es
adicionales.
Cada a ian e oma inicialmen e las mismas alo aciones que el pe il del que
p o iene, y a los siguien es 33% de las alo aciones se dan nue os alo es alea o ios.
Finalmen e, se añadie on cua o pe iles de clien es adicionales comple amen e al
aza . Es os 16 pe iles de clien es in en an simula la o ma de p e e encias en un
me cado iable: la mayo ía de los pe iles de los clien es se eúnen en pocos g upos de
p e e encia simila , y hay algunos de o os ipos de clien es aislados.
Además, 10 p oduc o es ue on conside ados en casos de PDO. Pa a el 90% de
los a ibu os, odos sus alo es de a ibu o es aban disponibles pa a se seleccionados
po cualquie p oduc o . Sin emba go, pa a el es o de a ibu os, sólo un alo de
a ibu o es aba disponible pa a odos los p oduc o es, mien as que el 33% de los
p oduc o es puede ene más de un alo de a ibu o disponible (con una p obabilidad
del 50% pa a cada alo posible del a ibu o). En cuan o al p oblema SPDG, sólo se
u iliza on 2 p oduc o es, y odos los alo es de odos los a ibu os disponibles pa a
ambos.
En PDO, los p oduc os p oducidos inicialmen e po cada uno de los 9
p oduc o es oponen es se c ean de acue do con el siguien e algo i mo o az. Pa a
cada p oduc o , se seleccionan al aza cua o pe iles de clien es. A con inuación, pa a
cada a ibu o y pa a cada uno de sus alo es de a ibu os, añadimos las alo aciones
de es e alo de a ibu o en es os cua o pe iles de clien es.
64
Iden i icamos el alo del a ibu o cuya adición e a el más al o, y es e alo de
a ibu o ue el alo asignado al a ibu o co espondien e del p oduc o .
A con inuación, el algo i mo gené ico, PSO y SA se lle a on a cabo pa a
encon a un p oduc o bueno pa a el p oduc o 1. Pa a cada a ibu o, la p obabilidad
de mu ación e a 0.01, y se aplicó un c uce uni o me. Una población inicial de 20
soluciones posibles (es deci , p oduc os pa a el p oduc o 1) se c eó u ilizando el
algo i mo o az p e io, y el algo i mo gené ico, PSO y SA ue ejecu ado cien eces.
Pa a el PDO, el p oduc o 1 iene la en aja de diseña p ime o su p oduc o.
Con el in de compa a de o ma equi a i a el endimien o del algo i mo gené ico, PSO
y SA con el endimien o de la es a egia o az pa a esol e el p oblema PDO, se
gua dan los esul ados iniciales ob enidos po el o az pa a hace una compa a i a
cuando e minen los di e en es algo i mos.
Pa a SPDG, los p oduc os p oducidos inicialmen e po los dos p oduc o es
ue on c eados al aza . Además, D = 1 (núme o de a ibu os modi icables), p = 5
(núme o del úl imo u no jugado), = 5 (núme o de u nos o ales del juego). La
es a egia es que pa a cada u no del juego donde se mue e, se ejecu a un algo i mo
minimax con poda al a y be a con cie a p o undidad d1 ∈ {4,6,8}. Pa a el p oduc o 2,
se u ilizó el mismo mé odo, aunque sus p o undidades son d2 ∈ {1,2}. Pa a ambos
p oduc o es, el alo heu ís ico omadas en las hojas del á bol explo ado po el
algo i mo minimax ue el núme o de clien es ecogidos du an e odas las uel as
eco idas en la ama del á bol donde es á la hoja.
Hemos gene ado la población inicial (sin u iliza clus e ización) de los
algo i mos GA y PSO de la siguien e mane a. Se calcula un p ime indi iduo que sea el
esul ado de un algo i mo o az de en e odos los pe iles gene ados, de al mane a
que el p oduc o es é en la media de odos ellos. A pa i de es e p oduc o gene amos
o os ce canos a él, y más adelan e indi iduos alea o ios pa a añadi los a la población.
De es a o ma pa imos de una base con cie o c i e io, que se basa en odos los
pe iles a la ez.
Al usa clus e ización pa a la gene ación de la población inicial, lo que hacemos
es di idi el núme o de pe iles gene ados en un p incipio en X g upos. Y una ez
enemos de inidos es os g upos, gene amos pa a cada uno de ellos un p oduc o que
sea el esul ado de un algo i mo o az aplicado únicamen e a ese g upo. Así en la
población inal end emos an os p oduc os como g upos nos hayamos hecho a aíz de
la clus e ización, y odos ellos se án p ome edo es pa a algún sec o de la población.
Además, a es a población pod emos añadi ambién el p oduc o o iginado del
algo i mo o az de odos los pe iles pa a ene una población oda ía más
p ome edo a. Al ene an os indi iduos di e en es, conseguidos a a és de dis in os
sec o es de los usua ios, end emos más opo unidad de saca un p oduc o óp imo.
65
En odos los g á icos que se mues an a con inuación el po cen aje inicial y inal
(ini Pe Cus y Pe Cus espec i amen e) se ep esen an de es a o ma: se mul iplica el
alo del po cen aje eal po diez, con la inalidad de que se adap e al in e alo que
hemos elegido pa a los g á icos y pueda isualiza se mejo .
 Pa a ejecuciones con da os gene ados alea o iamen e, se han ealizado las
siguien es p uebas:
Figu a 21 Ejecuciones Alea o ias Algo i mo Gené ico
En la Figu a 21 se mues an los esul ados del algo i mo gené ico en la
esolución de cinco ins ancias alea o ias. Pa a cada una de ellas, se mues an los
esul ados de la media de diez ejecuciones sob e la misma ins ancia. Se mues an el
po cen aje de clien es iniciales y inales ob enidos, los alo es de media inicial y inal
de núme o de clien es ob enidos, des iación ípica inicial y inal de dicho alo .
0100 200 300 400 500 600 700 800 900 1000
ini Mean
Mean
ini S dDe
S dDe
ini Pe Cus (*10)
Pe Cus (*10)
ini Mean Mean ini S dDe S dDe ini Pe Cus
(*10) Pe Cus (*10)
Ins ancia 1 511,345 698,95 433,806 390,483 307,09 420,03
Ins ancia 2 653,545 929,47 696,35 539,59 329,16 467,72
Ins ancia 3 586,965 787,27 497,594 453,253 325,2 436,36
Ins ancia 4 566,6 759,02 496,213 455,315 312,94 419,23
Ins ancia 5 415,48 685,6 484,354 393,388 255,93 422,86
GA Ins ancia Alea o ia
Ins ancia 1 Ins ancia 2 Ins ancia 3 Ins ancia 4 Ins ancia 5

66
Los esul ados mejo an conside ablemen e en e un 10–12 de pun os
po cen uales y en odas las ejecuciones se man iene el po cen aje de mejo a.
Figu a 22 Ejecuciones Alea o ias Algo i mo po Enjamb e de Pa ículas
En la Figu a 22 se mues an los esul ados de la ejecución de cinco ins ancias
del p oblema median e el algo i mo PSO. Se mues an los mismos da os conside ados
an es.
0200 400 600 800 1000 1200
ini Mean
Mean
s dDe
ini S dDe
ini Pe Cus (*10)
Pe Cus (*10)
ini Mean Mean s dDe ini S dDe ini Pe Cus
(*10) Pe Cus (*10)
Ins ancia 1 353,64 1047,2 52,89 699,216 190,14 564,49
Ins ancia 2 332,18 989,04 86,421 667,256 189,68 564,35
Ins ancia 3 301,16 905,8 53,195 607,66 182,46 552,47
Ins ancia 4 102,2 1023,5 25,5 792,516 131,48 584,63
Ins ancia 5 337,48 982,68 102,424 657,65 185,97 541,74
PSO Ins ancia Alea o ia
Ins ancia 1 Ins ancia 2 Ins ancia 3 Ins ancia 4 Ins ancia 5
67
El algo i mo se mues a es able en sus esul ados iniciales y inales pa a odas
las ins ancias, consiguiendo siemp e al ededo de 30 pun os po cen uales de mejo a.
Figu a 23 Ejecuciones Alea o ias Algo i mo de En iamien o Simulado
En la Figu a 23 se mues an los esul ados de la ejecución de cinco ins ancias
del p oblema median e el algo i mo de en iamien o simulado.
Sal o en la ins ancia 4, odos los esul ados son bas an e es ables y ob ienen
una mejo a de en e 15 - 20 pun os po cen uales.
0200 400 600 800 1000 1200
ini Mean
Mean
s dDe
ini S dDe
ini Pe Cus (*10)
Pe Cus (*10)
ini Mean Mean s dDe ini S dDe ini Pe Cus
(*10) Pe Cus (*10)
Ins ancia 1 537,333 958,8 59,594 449,747 259,28 422,03
Ins ancia 2 465,467 678,5 103,43 247,131 297,89 435,15
Ins ancia 3 473,8 745,6 120 310,528 295,47 464,17
Ins ancia 4 301,8 819,8 40,662 520,282 176,2 476,63
Ins ancia 5 496,1 741 149 297,335 312,45 465,31
SA Ins ancia Alea o ia
Ins ancia 1 Ins ancia 2 Ins ancia 3 Ins ancia 4 Ins ancia 5
68
Figu a 24 Ejecuciones Alea o ias Algo i mo Minimax
En la Figu a 24 se mues an los esul ados al ejecu a cinco ins ancias
dis in as del algo i mo minimax.
Pa a cada ins ancia hemos hecho diez ejecuciones y lo que mos amos en el
g á ico es la media de esas diez ejecuciones. El algo i mo se mues a bas an e
es able pa a odas las ins ancias consiguiendo pa a cada una un ma gen de mejo as
de en e 40 - 45 pun os po cen uales. Ya que pa a es e algo i mo no c eamos
ninguna población inicial, no hace al a c ea un p ime indi iduo median e un
algo i mo o az como en los o os casos.
01000 2000 3000 4000 5000 6000 7000 8000 9000 10000
ini Mean
Mean
ini S dDe
S dDe
ini Pe Cus (*10)
Pe Cus (*10)
ini Mean Mean ini S dDe S dDe ini Pe Cus
(*10) Pe Cus (*10)
Ins ancia 1 1684 8734,8 7061,35 358,309 106,03 550,15
Ins ancia 2 1557,05 8014,5 6474,749 465,223 107,33 552,52
Ins ancia 3 1689,35 8691,9 7016,781 441,408 105,66 543,28
Ins ancia 4 1542,85 7720,45 6208,134 384,8 133,31 547,36
Ins ancia 5 1723,85 8839,85 7127,418 387,449 106,49 545,89
Minimax Ins ancia Alea o ia
Ins ancia 1 Ins ancia 2 Ins ancia 3 Ins ancia 4 Ins ancia 5
69
Pa a nues o algo i mo usamos la poda al a-be a. La poda al a-be a oma
dicho nomb e de la u ilización de dos pa áme os que desc iben los lími es sob e los
alo es hacia a ás que apa ecen a lo la go de cada camino. Es a búsqueda al a-be a
a ac ualizando el alo de los pa áme os según se eco e el á bol. El mé odo
ealiza á la poda de las amas es an es cuando el alo ac ual que se es á
examinando sea peo que el alo ac ual de α o β pa a MAX o MIN,
espec i amen e.
 Pa a ejecuciones ealizadas sob e la ins ancia gene ada a pa i de los
esul ados de las encues as (es deci , nues o caso de es udio sob e mó iles),
se mues an los siguien es esul ados:
En cada uno de los algo i mos hemos ealizado cinco ejecuciones, y lo que se
mues a en es e g á ico es la media de odas ellas.
Figu a 25 Ejecuciones Da os Feebbo
05000 10000 15000 20000 25000
ini Mean
Mean
S dDe
ini S dDe
ini Pe Cus (*10)
Pe Cus (*10)
ini Mean Mean S dDe ini S dDe ini Pe Cus
(*10) Pe Cus (*10)
SA 3098,4 4138,8 67,922 1044,228 495,38 662,12
PSO 1377,76 3929,2 533,62 2628,288 328,06 935,52
Minimax 2795,1 21026,9 598,01 18244,742 66,56 500,64
Gené ico 1967,87 4063,2 310,008 2141,332 468,54 967,44
Ins ancia del caso de es udio
SA PSO Minimax Gené ico
76
10 Conclusiones
En es e p oyec o se han implemen ado algo i mos pa a esol e los p oblemas
PDO, SPDG y lSPDG, es p oblemas que a an de encapsula obje i os esenciales en
ma ke ing: la selección de un p oduc o que log e un núme o al o de clien es de o ma
inmedia a (en PDO), y la selección de una es a egia de diseño de p oduc o sos enible
que log e un núme o de e minado de clien es en un la go o co o plazo (en SPDG y
lSPDG espec i amen e). Pa a esol e es os p oblemas, hemos u ilizado mé odos
heu ís icos subóp imos, en luga de u iliza algo i mos óp imos que esul a ían
in a ables.
Desa ollamos expe imen os con da os alea o ios y con da os ob enidos de un
caso de es udio eal sob e mó iles.
Pa a lle a a cabo los obje i os que eníamos plan eados hemos diseñado una
in e az mul ipla a o ma pa a que los esul ados se puedan isualiza cla amen e y se
puedan in oduci los da os a a és de la aplicación. Además, en cuan o a la
implemen ación de la aplicación, el código ha sido abs aído y bien o ganizado de al
mane a que pueda se eu ilizable y se puedan añadi di e en es algo i mos con
p oblemas nue os.
Conside ando los es obje i os p opues os al p incipio del desa ollo del
p oyec o, hemos desa ollado un p og ama ú il y e icien e que nos pe mi e esol e
nues o obje i o p incipal: decidi las ca ac e ís icas del p oduc o a ende pa a
maximiza el núme o de clien es de o ma inmedia a o a la go plazo. Hemos lle ado a
cabo un caso de es udio eal pa a aplica lo a nues a he amien a.
Pa a comple a el e ce obje i o del p oyec o, a pa i de los esul ados
expe imen ales desc i os en la sección an e io , exponemos nues as conclusiones
sob e los dis in os algo i mos que hemos implemen ado.
Comenza emos po el p oblema PDO y el algo i mo gené ico. Es e algo i mo
iene unos esul ados iniciales bas an e es ables. Aunque en algún caso sí que
ob enemos algún esul ado que se aleja de la media, es en las meno es ocasiones, y
pa ece depende mucho de la ins ancia con la que ejecu emos el algo i mo. Los
esul ados inales alcanzan casi siemp e en e unos 40 y 45 pun os po cen uales, con
lo que ob enemos esul ados inales es ables, aunque son unos de los más bajos de
en e odos los algo i mos. Además el índice de mejo a sob e los esul ados de la
población inicial del algo i mo es ambién el más bajo de odos los algo i mos, an solo
mejo a una media de 12 pun os po cen uales po ejecución.

77
En el algo i mo PSO enemos da os cu iosos. Po ejemplo, el p oduc o inicial de
es e algo i mo comienza eniendo un 17 % de los clien es iniciales, una de las más
bajas si uaciones iniciales, algo ex año ya que an o el GA como el PSO ob ienen su
si uación inicial de la misma mane a y debe ían ene pun uaciones iniciales pa ecidas.
Es o nos hace pensa que pod ía habe un bug en el código el cual no ha sido
encon ado, ya que los dos algo i mos gene an la población de la misma mane a, y uno
comienza con un 17% del me cado, y o o con el 35%. Pensamos en la idea de un bug a
pesa de que, as es udia la ejecución del algo i mo paso a paso con ins ancias
pequeñas (lo su icien e pa a pode hace el seguimien o manualmen e), comp obamos
que el algo i mo unciona co ec amen e.
Po úl imo, amos a analiza los esul ados del algo i mo de en iamien o
simulado. Es e algo i mo ob iene esul ados no males, sin ningún ipo de ano malidad.
Los esul ados iniciales es án en la media de los esul ados ob enidos po odos los
demás algo i mos y lo mismo ocu e con sus esul ados inales. Como mues an los
esul ados, no es ni el que peo empieza, ni el que mejo acaba, pe o siemp e se queda
en e los 45 pun os po cen uales, así que podemos deci que es un algo i mo es able.
Pa a el p oblema SPDG y el algo i mo minimax, el an o po cien o de clien es
conseguido en la si uación inicial es bajo, en o no a 10 %, y sin emba go el algo i mo
minimax ob iene una g an op imización del p oduc o, consiguiendo alcanza ce ca de
55 % de los clien es del me cado. Hay que ene en cuen a que en es e p oblema
ambién se mejo a el p oduc o de la compe encia, así que ambién es el más ealis a,
dado que esul a di ícil c ee que un compe ido no aya a e oluciona su p oduc o
pa a ob ene más bene icios que su oponen e.
Es e algo i mo es muy es able, habiendo una di e encia mínima de un 0.9 pun os
po cen uales en e su mejo y su peo esul ado.
Dado que el Minimax po un lado, y los algo i mos GA, PSO y SA po o o,
esuel en p oblemas dis in os es inú il compa a sus esul ados. El Minimax a a de
esol e un p oblema SPDG, mien as que los demás esuel en el p oblema PDO.
Además es os algo i mos es án u ilizando ins ancias dis in as, po lo que
de ini i amen e no iene sen ido compa a los, ya que no apo a ía ninguna
in o mación ú il.
Aho a amos a analiza los esul ados de los mismos algo i mos, pe o habiendo
u ilizado los da os de nues o p opio caso de es udio. Reco demos que es a ins ancia
es cons uida a pa i de los esul ados de encues as que solici amos a la emp esa
Feebbo. Comen emos las g andes disc epancias con espec o a los casos de es udio de
ins ancias alea o ias.
78
Po ejemplo, una de las cosas que más nos llaman la a ención es que, excep o en
el minimax, odos los demás algo i mos mejo an conside ablemen e (en e los 15
pun os po cen uales) sus si uaciones iniciales y inales.
En el caso del Minimax es al e és, es e empeo a sus esul ados inales en
compa ación con el caso de es udio con ins ancias alea o ias, pe o lo cu ioso es que la
mejo a es la misma. En es e caso, empieza 4 pun os po cen uales po debajo y e mina
igual, con el esul ado inal 4 pun os po debajo del caso de es udio alea o io. Es o
hace que la mejo a sea la misma, e indica que el algo i mo es muy es able, y es a
bajada en los esul ados iniciales puede debe se simplemen e al cambio de ins ancia
u ilizada, ya que la can idad de da os que maneja es conside ablemen e di e en e.
En los esul ados del algo i mo SA ocu e lo mismo. Si bien hemos comen ado
que su esul ado inicial y inal aumen a, hay que ecalca que aumen a lo mismo que
en e las ins ancias alea o ias. Y el índice de mejo a en e el caso de es udio alea o io y
el caso de es udio eal es el mismo, 17 pun os po cen uales. Es o indica lo mismo que
en el minimax, que es un algo i mo es able y es a di e encia puede debe se al cambio
conside able de la ins ancia u ilizada.
Pa a el GA y PSO ocu e una anomalía. Ambos algo i mos dan esul ados
pa ecidos, cosa que no es de ex aña g acias a su g an pa ecido. Sin emba go, dichos
esul ados ienen algo inusual. Si bien los dos algo i mos comienzan con una si uación
inicial más al a que con el caso de es udio alea o io, consiguen una si uación inal
ex añamen e al a, ambos algo i mos supe an los 90 pun os po cen uales, en el caso
del GA llega has a los 96. No enemos muy cla o a qué se debe es e aumen o de la
e iciencia del algo i mo, pe o obse ando que se p oduce en los dos algo i mos que
son simila es podemos pensa que no se a a de un e o en la ejecución del
algo i mo, ya que end ía que habe se p oducido un e o en ambos algo i mos que
desemboquen en la misma epe cusión, y eso es complicado. De los dos algo i mos el
que mayo op imización ealiza uel e a se el PSO. Es a anomalía pod ía debe se a la
ins ancia u ilizada, puede que los esul ados ob enidos de las encues as de Feebbo, o
bien nues a mane a de con e i los da os de dichas encues as en da os de en ada
pa a el p oblema PDO no haya dado luga a una ins ancia que cap e ielmen e la
di icul ad de lidia con la compe encia o de combina ap opiadamen e los a ibu os de
los p oduc os, y que po ello, pa a la ins ancia ob enida, sea so p enden emen e ácil
cap a una can idad eno me del me cado (cues a c ee que, si ealmen e exis ie a al
eno me nicho de demanda insa is echo, las emp esas que ab ican elé onos mó iles
no se hubie an dado cuen a ya).
Después nos encon amos los esul ados de los di e en es algo i mos usando la
clus e ización. El p ime o en analiza es el GA. En ambos casos (usando o no la
clus e ización pa a gene a la población inicial) la mejo a que nos encon amos es que,
iendo los esul ados iniciales, en el caso de la clus e ización el an o po cien o de
79
clien es ob enidos es un 10% supe io , con lo cual el índice de clien es conseguidos al
inal del algo i mo es igualmen e supe io al algo i mo sin clus e ización.
Con el algo i mo PSO nos encon amos el mismo compo amien o que en GA, el
índice de mejo a es igual en ambos casos, y cuando usamos la clus e ización,
conseguimos comenza el algo i mo en una posición más en ajosa que sin él. Eso
in luye en que el esul ado inal ambién sea mejo .
Conside emos los esul ados pa a las a ian es que maximizan los bene icios en
con aposición a los clien es. En el caso de PDO, podemos obse a que el algo i mo
SA y PSO ob ienen un inc emen o de los ing esos pa ecido, en o no a 150 pun os
po cen uales de mejo a. Mien as que el GA llega has a más de los 250 pun os.
En es a e sión del p oblema el algo i mo que mejo es esul ados pa ece
ob ene es el Gené ico con una mejo a de 275 pun os po cen uales. No sabemos muy
bien po qué el PSO y el SA se dis ancian an o en es a a ian e del algo i mo si en las
ejecuciones pa a el PDO es ánda no se lle an an a di e encia.
Con espec o a los esul ados ob enidos en la esolución de la a ian e en la que
cada p oduc o puede ende simul áneamen e con a ios p oduc os, obse amos las
siguien es dis inciones en los es algo i mos donde se ha aplicado es a a ian e.
Si sumamos los pun os po cen uales ob enidos en e los es p oduc os, nos da
una si uación inicial aco de con los da os ob enidos en las ejecuciones es ánda .
Con espec o a la si uación inal ocu e lo mismo: los pun os po cen uales
ob enidos po los p oduc os son in e io es a la ejecución es ánda , pe o si les
sumamos los ob enidos po los es p oduc os endidos conjun amen e, ob enemos
incluso una mayo pun uación que en la e sión no mal. Es o se debe a que se aplica el
algo i mo gené ico a es p oduc os dis in os conjun amen e. Si somos capaces de
op imiza un solo p oduc o has a cie o pun o, y aplicamos esa misma écnica a o os
dos p oduc os más de mane a conjun a y coo dinada, ob end emos mejo es
esul ados, ob eniendo mejo es p oduc os, los cuáles se coo dinan pa a epa i se el
espacio de demanda.
En el úl imo expe imen o, que co esponde a la ejecución del Minimax con
dis in as p o undidades, se obse a cla amen e que cuando ejecu amos el p oblema
con una p o undidad 2 pa a el oponen e y 4 pa a noso os, ob enemos una pun uación
inal de 53 pun os po cen uales. Sin emba go, si ejecu amos el algo i mo con una
p o undidad supe io pa a noso os (2 pa a el oponen e, 8 pa a noso os), ob enemos
una pun uación inal mejo , de 57 pun os po cen uales. Así comp obamos que, si
amos educiendo la p o undidad nues a y ampliando la del oponen e, los esul ados
se án peo es pa a noso os y mejo es pa a el oponen e. Po an o, el esul ado
ob enido po el Minimax depende de la p o undidad a la que es emos dispues os a
80
llega , sin ol ida que el iempo de ejecución c ece exponencialmen e con la
p o undidad.
Finalmen e, llegados a es e pun o podemos conclui que hemos comple ado los
obje i os plan eados al p incipio de es e p oyec o. En e las a eas desa olladas,
des aca íamos po su pa icula complejidad el caso de es udio eal que hemos
ealizado a a és de Feebbo, y que nos ha se ido como expe iencia a lo la go del
desa ollo del p oyec o. Lle a la a cabo ha aído consigo algunos con a iempos.
Puede que el mayo de ellos haya sido la pa e de in es igación sob e cómo ealiza
encues as pa a miles de pe sonas con el obje i o de ob ene espues as que nos si an
pa a nues o caso de es udio y nues a aplicación. Además, a dichas encues as había
que añadi le p egun as de pe sonalidad que ambién u imos que in es iga . Más aún,
los esul ados de las encues as no e an inmedia as ya que que íamos alcanza un
núme o de encues ados bas an e al o.
Como da o inal, comen amos el p ecio y algunas ca ac e ís icas del mó il que
ob iene alguno de los algo i mos (en es e caso u ilizamos el Algo i mo Gené ico) de
nues a aplicación al ealiza la ejecución del caso de es udio eal. El p ecio del mó il
es de 154 eu os y iene las siguien es ca ac e ís icas: a je a Nano SIM, adio FM,
blue oo h, esis en e al agua, iene ecnología NFC, mó il con Dual SIM y diseño
ju enil.
Po úl imo, des aca el po encial de la aplicación pa a el mundo labo al ac ual, en
pa icula den o del á ea del ma ke ing.
81
11. Posible T abajo Fu u o
En es e apa ado explica emos odas las cosas en las que pod íamos abaja en
un u u o pa a mejo a y amplia es e p oyec o.
Como ya hemos comen ado además de la aplicación de esc i o io, enemos una
aplicación mó il de es e p og ama, si bien la app con alguna uncionalidad menos,
como es el caso de lec u a y esc i u a de iche o. Además, como es lógico los
algo i mos se ejecu an mucho más len amen e en la app.
En un u u o pod íamos hace un sis ema Clien e – Se ido en el que la app
hicie a de in e az pa a el usua io, pa a que elija los algo i mos que desee pa a ealiza
la ejecución, las a ian es, in oducción de da os manualmen e, e c. Después de ene
los da os necesa ios pa a la ejecución, se lanza ía la pe ición al se ido , que se
enca ga ía de ealiza el algo i mo, ya que además lo ha ía mucho más ápido. Cuando
la ejecución e minase, de ol e ía el esul ado a la app pa a mos á selo al usua io.
Como idea, se pod ían u iliza un sis ema de se icios REST, ya que las ansacciones
median e obje os Json acili a ían la comunicación con nues o p og ama desa ollado
en Ja a.
O a de las mejo as posibles pa a el p oyec o hace e e encia a la ob ención del
p ecio óp imo pa a nues o p oduc o. Aho a mismo u ilizamos una unción de media
ponde ada, pe o ambién alo amos o a opción que al inal no se desa olló. Es a
opción consis e en es ima una unción lineal que enga an os pa áme os de en ada
como ca ac e ís icas enga el mó il y nos de uel a el p ecio. Dicha unción se puede
in e pola a pa i de los p ecios de mó iles eales que u iliza emos pa a modeliza la
compe encia, de o ma que cada uno de es os mó iles (jun o con su p ecio conocido)
es un pun o de dicha unción. Pa a es ima heu ís icamen e los coe icien es de la
unción lineal, pod íamos u iliza un algo i mo gené ico: cada indi iduo (c omosoma)
es una combinación conc e a de pesos, y la unción de i ness de uel e la dis ancia
en e el p ecio eal y el p ecio es imado con los pesos de ese c omosoma, desca ando
aquellos que engan una dis ancia mayo , y quedándose con los que se ajus en más.
O a posible u u a mejo a es añadi más algo i mos al p og ama pa a op a a
una mayo a iedad. Po ejemplo, se pod ía implemen a el algo i mo Hill Climbing.
Aunque se p esupone peo que el Simula ed Annealing, ya que se queda a ascado en
máximos locales, o ece algunas a ian es in e esan es que pod íamos es udia .
Finalmen e, pod ían añadi se más a ian es de los p oblemas a nues o
p og ama. Como ejemplo, pod íamos desa olla una a ian e de la e sión con a ios
p oduc os po p oduc o en la que no engan que ene odos los p oduc o es el
mismo núme o de p oduc os, y se pueda da el caso de que un p oduc o juegue con
cua o p oduc os y o o solo con dos, o uno.

82
12. Plan de P oyec o
A con inuación, explica emos cómo nos hemos o ganizado y en qué medida
hemos con ibuido cada uno pa a el desa ollo del p oyec o.
12.1 O ganización del P oyec o
Hemos ealizado euniones cada dos o es semanas con el di ec o de nues o
p oyec o Ismael, ía Skype o p esencial. En cada una de las euniones le
comen ábamos lo que habíamos hecho du an e el anscu so de ese in e alo de
iempo. Además, le plan eábamos las dudas que nos habían su gido y nues a posible
solución a esos p oblemas.
Po o o lado, an es de acaba cada eunión comen ábamos con el di ec o del
p oyec o lo que íbamos a hace du an e ese iempo, de ca a a la siguien e eunión.
A lo la go del desa ollo de nues a aplicación, hemos u ilizado las hojas de
cálculo de Google D i e [32] pa a lis a las a eas que eníamos que hace y
consecuen emen e no i ica cuando és as es aban concluidas. Pa a que no haya
con usión, decidimos que e a mejo i poniendo las echas pa a cada a ea y po ende
su du ación. Hemos seguido la me odología Sc um [33]: ma camos en e de las a eas
que han sido ealizadas en el plazo que habíamos es ablecido, en ama illo las que se
e asaban y po úl imo en ojo aquellas que no se cumplían o que no se llegaban a
usa (po ejemplo, in es igaciones que se hicie on en su debido momen o pa a e si
podían se i nos en el p oyec o).
Figu a 32 Me odología Sc um
83
Además, hemos ano ado odas las e e encias a páginas que hemos u ilizado
pa a ealiza nues a in es igación.
En cuan o a la o ganización que hemos u ilizado al desa olla el código,
c eímos con enien e y cómodo usa el sis ema de con ol Gi con un eposi o io
público en Gi Hub [34]. Allí hemos c eado un eposi o io con nues o p oyec o .gi , que
enía una ama mas e y una ama pa a que cada uno pudié amos abaja en pa alelo,
y ealiza las p uebas co espondien es.
Cuando ambos e minábamos de hace las p uebas sa is ac o iamen e,
ac ualizábamos la ama mas e pa a que u ie a siemp e una e sión es able.
12.2 Con ibución al P oyec o
En es e apa ado ambos amos explica indi idualmen e nues a con ibución
al p oyec o Ma ke ing Compu acional.
12.2.1 S ephania C is ina Hinos oza Hualpa
En es e apa ado oy a desc ibi mi apo ación indi idual y menciona las
di icul ades que me han su gido a lo la go del desa ollo del p oyec o.
Pa a empeza con el p oyec o ealizamos un es udio del abajo inicial
p opo cionado po el p o eso pa a pode inco po a lo en el p oyec o. Se in es igó
sob e los di e en es algo i mos que u ilizaban, y decidi inalmen e si segui íamos con
el mismo lenguaje de p og amación o po lo con a io op imiza la implemen ación
con o o lenguaje.
Después de decidi el lenguaje de p og amación y la he amien a que
u iliza íamos pa a es e p oyec o: Ja a y Eclipse (And oid S udio pa a la app de mó il)
espec i amen e, u imos que documen a nos sob e la o ma de lle a a cabo la
implemen ación y op imización de los algo i mos. En p ime luga , me documen é
sob e las di e en es lib e ías que nos pe mi ían acili a el uso de esos algo i mos, po
ejemplo: lib e ía Poi pa a la lec u a de iche os Excel, JGAP (Ja a Gene ic Algo i hms
Package) que con enía la implemen ación del algo i mo gené ico, Ja a CSV pa a la
lec u a de iche os CSV, e c.
De odas las lib e ías que he in es igado, algunas se han u ilizado du an e el
p oyec o mien as que o as se han ido desca ando a lo la go del desa ollo. Po
ejemplo, la lib e ía Poi se desca ó po que nos p oducía p oblemas al lee el iche o
Excel del caso de es udio abo dado en [2] sob e la polí ica de España, y la lib e ía JGAP
84
se desca ó ambién po que decidimos implemen a el algo i mo gené ico,
basándonos en lo que nos habían p opo cionado.
En pa alelo a esa in es igación, ealicé o a sob e emp esas que hacían es udios
de me cado. Como pa ía de un b e e conocimien o de alguna de es as emp esas,
decidí p o undiza en el ema y pone me en con ac o con alguna de ellas pa a sabe si
pod ían ayuda nos de alguna mane a y de o ma desin e esada. Como nues a idea
e a hace un caso de es udio eal sob e un de e minado p oduc o, lo que que íamos
e a publica una encues a pa a que lo pueda ealiza mucha gen e, y con esos
esul ados pode gene a nues o caso de es udio. Me puse en con ac o con una
emp esa, pe o inalmen e no ob u imos espues a, decidí segui in en ando y con la
segunda emp esa con la que con ac amos, es a ez a a és del p o eso po co eo,
ecibimos una buena espues a po pa e de la emp esa Feebbo, ya que colabo aban
con di e en es uni e sidades a ni el in e nacional. Es a se dedica a ealiza es udios de
me cado a a és de encues as ealizadas po sus clien es, y a ende esos esul ados a
o as emp esas in e esadas en di e en es p oduc os. Tu imos di e sas euniones con
el di ec o de Feebbo, Goyo He nández, pa a aco da cómo nos ayuda ían y cuál se ía
nues a colabo ación con ellos, sin ene que paga po los esul ados de la encues a.
Finalmen e, el acue do ue que podíamos usa su pla a o ma pa a subi nues a
encues a y que podamos u iliza a sus clien es pa a que espondie an a las p egun as
de la encues a, a cambio de que les ayudásemos a clasi ica a sus encues ados po
pe iles de simili ud.
Pa a ealiza lo que nos pedía Feebbo, u e que documen a me sob e
algo i mos de ag upamien o y e i ica cuál nos pod ía se i con o me a lo que nos
pedían. Pa a u iliza es os algo i mos, decidí que la he amien a Weka me podía se i
pa a hace p uebas sob e clus e ización. Elegí es a he amien a po que ya la había
u ilizado en una asigna u a en la ca e a, e inmedia amen e eco dé que podía
clasi ica los pe iles en clus e s ag upados po simili ud, ap o echando los di e sos
algo i mos que me p opo cionaba Weka. Como no eco daba odas las uncionalidades
de Weka, me puse a in es iga más en p o undidad sob e la he amien a. El algo i mo
que elegí ue K-Means, ya que después de in es iga se adecuaba a lo que nos pedía
Goyo.
Además, es a he amien a iene una lib e ía Weka.ja que nos pe mi ía u iliza
el algo i mo en Ja a. Realicé una implemen ación en Ja a sob e el algo i mo K-Means
(c ea y con igu a el algo i mo, ca ga los da ase s, en ena el algo i mo de
clus e ización, e iden i ica los clus e s de cada ins ancia) y inalmen e mos a los
cen oides u ilizando la lib e ía de Weka. Después de que ealiza a la implemen ación
y las p uebas pe inen es an o en la he amien a Weka como en Ja a, u imos una
eunión con Goyo en el que le expliqué desde ce o sob e los algo i mos de
ag upamien o, sob e la he amien a Weka (uso, licencia, e c.), el algo i mo u ilizado, y
85
las p uebas básicas de las dos o mas. Se le p opo cionó oda la in o mación que
necesi aba, así como la implemen ación que hice en Ja a.
La implemen ación que ealicé del algo i mo de clus e ización ambién nos
si ió pa a añadi lo como a ian e en nues o p oyec o mencionado en apa ados
an e io es, es a a ian e nos pe mi e ene esul ados mejo es.
Fui la enca gada de ealiza la in e az pa a esc i o io desde ce o y de añadi le
odas las uncionalidades pos e io men e. U ilicé la he amien a Ne beans pa a ene
una idea concep ual de la in e az pa a esc i o io que pos e io men e implemen a ía
en Eclipse, desa ollé una pequeña implemen ación que ue mejo ando con o me
a anzaba el p oyec o.
Ademas de ene ya implemen ados esos algo i mos, había que es ima el
p ecio del p oduc o, y pa a ello u e que in es iga sob e algo i mos de in e polación y
he amien as que pod íamos u iliza . Así que du an e la in es igación encon é dos
he amien as que a p io i pa ecía que nos iba a se ú il: Ma Lab y A cGis, pe o después
de as ea un poco con es as he amien as y hace di e sas p uebas, decidí
desca a las po que no hacían ealmen e lo que que íamos. Finalmen e se op ó po
implemen a lo po nues a cuen a.
Se p opusie on dos nue os algo i mos: Algo i mo de Op imización po
Enjamb e de Pa ículas y Algo i mo de En iamien o Simulado. Pa a sabe un poco más
de es os algo i mos (ya que no lo habíamos is o en la ca e a) me puse a busca
in o mación ú il que nos si ie a an o pa a comp ende los algo i mos como pa a
sabe implemen a los. Encon é di e sos ejemplos básicos que me hicie an en ende
la uncionalidad y el compo amien o de es os algo i mos, así como esquemas
gene ales en pseudocódigo que nos si ie on de ayuda a la ho a de implemen a . Al
adap a dichos algo i mos en Eclipse, ambién iba ac ualizando y mejo ando la in e az
g á ica de esc i o io pa a isualiza los esul ados, así como solucionando los allos que
se p oducían.
En cuan o a las abs acciones de es os algo i mos, es aba enca gada de
o ganiza el código pa a pode op imiza lo. Implemen é una clase donde se
encon aban odos los mé odos y a iables comunes que hay en cada algo i mo, con la
inalidad de no duplica código, sino op imiza lo de la mejo o ma posible.
Las a ian es del p oyec o que se iban implemen ando ambién se adap aban
pa a la in e az de esc i o io (la a ian e de a ibu os enlazados u e que
implemen a lo pa a que se pudie an in oduci a a és de la in e az), ya que nos
pe mi ía in oduci los da os de en ada ( u e que ealiza la implemen ación pa a la
c eación de los a ibu os, p oduc o es y pe iles) y modi ica di e en es a iables
p opias de cada algo i mo y las a iables comunes en e dichos algo i mos pa a hace
las p uebas necesa ias. Es a in e az ambién pe mi ía lee de un iche o x y xml, pa a
92
[33]
K. S. Rubin, Essen ial Sc um: A P ac ical Guide o he Mos Popula Agile, Uppe Saddle
Ri e , NJ : Addison-Wesley, 2012.
[34]
«Gi Hub,» [En línea]. A ailable: h ps://gi hub.com/.
[35]
«The Apache POI P ojec ,» [En línea]. A ailable: h ps://poi.apache.o g/.
[36]
J. Bell, Machine Lea ning: Hands-On o De elope s and Technical P o essionals, Wiley.
[37]
L. d. S. Coelho, A quan um pa icle swa m op imize wi h chao ic mu a ion ope a o ,
ol. 37, Chaos Soli ons & F ac als, 2008, pp. 2-22.

93
14 Summa y in English
14.1 In oduc ion
In his i s in oduc o y sec ion we will desc ibe b ie ly how he epo will be
s uc u ed. In addi ion, we will explain he objec i es we ha e aised o he p ojec
Compu a ional Ma ke ing: Au oma ic P oduc Design.
14.2 P ojec O ganiza ion
The epo is s uc u ed as ollows:
 In he i s chap e , he p ojec goals a e exposed.
 The second chap e desc ibes he p oblems add essed he applica ion.
 The hi d chap e will discuss he s a e o a . We will men ion he ac i i ies
de eloped by se e al exis ing companies, ela ed o ma ke esea ch.
 The ou h chap e p esen s how we ca ied ou he design o ou applica ion.
 In he i h chap e , we desc ibe he unc ionali y o ou desk op and And oid
applica ions.
 In he six h chap e , we will men ion wha ools we chose o he
implemen a ion and why hey sui ou necessi ies.
 In he se en h chap e , he implemen a ion o he mul ipla o m applica ion
will be discussed.
 In he eigh h chap e we desc ibe he su eys we designed o be conduc ed in
he Feebbo pla o m, as well as he ype o ques ions asked and he esul s
ob ained.
 In he nin h chap e we will p esen he esul s achie ed in ou case s udy o
he applica ion.
 In he en h chap e we gi e he inal conclusions o his p ojec . We will also
discuss possible ex ensions and imp o emen s.
 In he ele en h chap e will discuss he u u e wo k, desc ibing he ex ensions
ha can be made o he p ojec .
 In he wel h chap e we will p esen he o ganiza ion o he p ojec
de elopmen , as well as and he con ibu ion o each membe o he g oup.
 The hi een h chap e is he bibliog aphy.
 The ou een h chap e p o ides a summa y o he objec i es, conclusions and
u u e wo k in English.

94
14.3 Goals
The main objec i es o he p ojec a e:
1. De elop an applica ion ha , based on he cus ome p e e ences abou he
cha ac e is ics o a speci ic p oduc , and aking in o accoun he p oduc s
o e ed by compe i o s, ob ains he ideal p oduc o be sold immedia ely o in
he long e m, ha is:
a) Design a p oduc comple ely om sc a ch o maximize he numbe o
cus ome s o o each a ce ain numbe o cus ome s; o
b) Design a s a egy indica ing how o modi y ou p oduc as he
compe i o s modi y hei own, so ha we each some a e age numbe
o cus ome s wi hin a speci ied pe iod ega dless o changes ha ha e
made he compe i o s.
I is also conside ed an al e na i e e sion o he abo e p oblem in
which he deadline is es ic ed: he numbe o u ns canno be g ea e
han he numbe o p oduc a ibu es.
Ou applica ion will sol e se e al a ian s o such p oblems, and i will allow o
apply di e en algo i hms. I will also o e bo h a desk op e sion o Windows as a
mobile e sion o And oid.
2. We will demons a e he use ulness o he applica ion ca ying ou a ealis ic
ull case s udy.
3. Finally, we will compa e a ious algo i hms in he esolu ion o a ious a ian s
o he p oblems.
In o de o achie e his pu pose, we need o de elop he ollowing ac i i ies:
 Deepen ou knowledge on gene ic algo i hms, algo i hms pa icle swa m
op imiza ion, simula ed annealing algo i hms, minimax algo i hms and
in e pola ion algo i hms, o apply hem in he de elopmen o ou applica ion
and ou case s udy.
 Design and ca y ou a se o ques ions o su eys allowing us o, ge opinions
o esponden s’ p e e ences on a pa icula p oduc (in ou case mobile
phones) h ough he websi e Feebbo [1].
 Lea n di e en clus e ing algo i hms o classi y esponden s in clus e s
o ganized by simila i y.
 Design ou applica ion, choose he ools o be used in o de o de elop a
mul ipla o m sys em.
 De elop and implemen he applica ion ha designs he bes p oduc .
95
 Imp o e he abili y o p og amming in he Ja a language and lea n o use
unc ions con ained in i s lib a ies.
 E alua e he esul s o he implemen a ion and analyze hem in e ms o he
ob ained p oduc s.
 Elabo a e documen a ion collec ing e e y hing we ha e done and enable he
u u e expansion o he p ojec .
14.4 Conclusions
In his p ojec we ha e implemen ed algo i hms o sol e p oblems PDO, SPDG
and lSPDG, h ee p oblems ying o encapsula e essen ial objec i es in ma ke ing:
selec ing a p oduc ha achie es a high numbe o clien s immedia ely (PDO), and
selec ion o a s a egy o sus ainable p oduc design ha achie es a ce ain numbe o
cus ome s in a long o sho e m (in SPDG and lSPDG espec i ely).
To sol e hese p oblems, we used sub-op imal heu is ic me hods, ins ead o using
op imal algo i hms ha would be in ac able.
We de eloped expe imen s wi h andom da a and da a om a eal case s udy
abou mobile phones.
Fo conduc ing he objec i es ha we aised we ha e designed a mul ipla o m
in e ace so ha he esul s can be displayed clea ly and he use can en e da a
h ough he applica ion. Fu he mo e, as o he implemen a ion o he applica ion, he
code has been abs ac ed and well o ganized so ha i can be eusable and can be
added di e en algo i hms wi h new p oblems.
Conside ing he h ee goals we p oposed a he beginning o he de elopmen
o his p ojec , we ha e de eloped a use ul and e icien p og am ha allows us o
sol e ou main objec i e: decide he cha ac e is ics o he p oduc o sell o maximize
he numbe o clien s immedia ely o long e m. We ha e conduc ed a eal case s udy
o apply ou ool.
In o de o comple e he hi d goal o he p ojec , nex we analyze he
expe imen al esul s desc ibed in he p e ious sec ion, and we p esen ou conclusions
abou he algo i hms we ha e implemen ed.
We begin wi h he PDO p oblem and gene ic algo i hm. This algo i hm has a
ai ly s able ini ial esul s. Al hough in some cases we ge a esul ha depa s om he
a e age, i is in he mino occasions, and i seems o depend a lo on he ins ance wi h
which we execu e he algo i hm. Final esul s usually each be ween 40 and 45
pe cen age poin s, hus ob ain s able end esul s, bu a e among he lowes o all
algo i hms. In addi ion, he a e o imp o emen on he esul s o he ini ial popula ion
96
o he algo i hm is also he lowes o all algo i hms, only an a e age imp o emen o
12 pe cen age poin s pe execu ion.
In he PSO algo i hm we ha e obse ed cu ious ac s. Fo example, he ini ial
p oduc o his algo i hm begins aking 17% o he ini ial cus ome s, one o he ini ial
lowes si ua ions, some hing s ange as bo h he GA and he PSO ge hei ini ial
si ua ion in he same way and should ha e ini ial sco es simila . This makes us hink
he e migh be a bug in he code which has no been ound, as he wo algo i hms
gene a e he popula ion in he same way, and one begins wi h a 17 % ma ke sha e,
and ano he wi h 35%. We canno disca d he idea o a bug e en in spi e o he ac
ha , a e s udying he implemen a ion o s ep wi h small algo i hm ins ances (enough
o keep ack manually), we ound ha he algo i hm wo ks co ec ly.
Finally, we analyze he esul s o simula ed annealing algo i hm. This esul s o
his algo i hm a e no mal, wi hou any abno mali y. Ini ial esul s ma ch he a e age
esul s ob ained by all o he algo i hms and so does hei inal esul s. As he esul s, I
is nei he he algo i hm wi h he wo s beginning no he algo i hm wi h he bes
ending, bu always s ays be ween 45 pe cen age poin s, so we can say ha i is a
s able algo i hm.
Fo he p oblem SPDG and minimax algo i hm, he pe cen age o cus ome s
achie ed in he ini ial si ua ion is low, a ound 10%, and ye he minimax algo i hm
ob ains a p oduc op imiza ion, achie ing each abou 55% o ma ke cus ome s. Keep
in mind ha in his p oblem he compe ing p oduc is also imp o ed, so i is also he
mos ealis ic, since i is di icul o belie e ha a compe i o will no make his p oduc
e ol e o ge mo e bene i s han you opponen .
This algo i hm is e y s able, ha ing a minimum di e ence o 0.9 pe cen age
poin s om i s bes and i s wo s esul .
Since he Minimax and GA, PSO and SA sol e a ious p oblems i is useless o
compa e hei esul s. The Minimax ying o sol e a p oblem SPDG, while o he s sol e
he p oblem PDO. Fu he mo e, hese algo i hms a e using di e en ins ances, so
de ini ely compa ing hem is poin less, as hey would no p o ide any use ul
in o ma ion.
Now le 's analyze he esul s o hese algo i hms wi h da a om ou own case
s udy. Le us emembe ha his ins ance is cons uc ed om he esul s o su eys
ha ask he company Feebbo. Discuss he majo disc epancies ega ding he case
s udies o andom ins ances.
Fo example, one o he hings ha d aws ou a en ion is ha , excep in he
minimax, all o he algo i hms imp o e conside ably (by 15 pe cen age poin s) hei
ini ial and inal si ua ions.
97
In he case o Minimax, i is he o he way a ound, i wo sens hei inal esul s
compa ed o he case s udy wi h andom ins ances, bu i is cu ious ha he
imp o emen is he same. In his case, i s a s 4 pe cen age poin s lowe and ends he
same, wi h he inal sco e 4 poin s below he andom case s udy. This means ha he
imp o emen is he same, indica ing ha he algo i hm is e y s able, and his d op in
he ini ial esul s may simply be due o he di e en ins ance, since he amoun o da a
handled is signi ican ly di e en (as well as he da a hemsel es).
The esul s o he algo i hm SA a e he same. While we ha e said ha hei
ini ial and inal esul inc eases, we mus s ess ha i inc eases he same as be ween
andom ins ances. And he a e o imp o emen be ween he case o andomized and
eal case s udy is he same, 17 pe cen age poin s. Simila ly, as in he case o he
Minimax, his indica es ha he algo i hm is s able and his di e ence may be due o
signi ican changes o he ins ance used.
Fo GA and PSO, some hing ema kable and unsual happens. Bo h algo i hms
gi e simila esul s, which is no su p ising because o hei esemblance. Howe e ,
hese esul s a e somewha unusual. While bo h algo i hms s a wi h a highe ini ial
si ua ion compa ed o he case o andom ins ances, bo h ge a s angely high inal
esul , as bo h algo i hms exceed 90 pe cen age poin s (in he case o GA, i goes up o
96). We do no ha e a ce ain explana ion o his inc ease o e iciency o he
algo i hm, bu gi en ha his inc ease a ec s bo h algo i hms almos in he same way
we can p obably disca d an e o in he execu ion o he algo i hm, since i is no likely
ha wo bugs, one a each algo i hm, a ec he esul s o bo h algo i hms in he same
way, and ha 's complica ed. Compa ing bo h algo i hms, once again he PSO
op imiza ion is highe . The abno mally high pe o mance o bo h algo i hms could be
due o he pa icula ins ance unde use, which in u n was buil om he eplies
collec ed om ou Feebbo su eys. In pa icula , ou way o con e da a om hese
su eys in o inpu da a o he PDO p oblem could ha e no gi en ise o an ins ance
ha ai h ully cap u es he di icul y o dealing wi h compe i o s, o o app op ia ely
combine he a ibu es o p oduc s. As a esul , o he ob ained ins ance, i is
su p isingly easy o g asp a huge amoun o ma ke (i is ha d o belie e ha , i he e
eally a huge unsa is ied demand, manu ac u ing mobile phones companies had no
ealized ye ).
Nex we analyze he esul s o di e en algo i hms using clus e ing. The i s
one we discuss is he GA. Compa ing bo h cases (i.e. using o no clus e ing o
gene a e he ini ial popula ion), he numbe o cus ome s eached by he bes
indi idual o he ini ial con igu a ion is 10% highe in he case o clus e ing. Rega ding
he cus ome s a e achie ed a he end o he algo i hm, he a e o he algo i hm wi h
clus e ing is also highe han he a e o he algo i hm wi hou clus e ing.

98
Wi h he PSO algo i hm we obse e he same beha io as o he GA. The a e
o imp o emen is he same in bo h cases, and when we use clus e ing, we managed
o s a he algo i hm in a mo e ad an ageous posi ion han wi hou i . The inal
esul s a e also be e .
We conside he esul s o a ian s ha maximize he bene i s as opposed o
cus ome s. Fo PDO, we can see ha he PSO and SA algo i hm ob ain an inc ease o
income like o a ound 150 pe cen age imp o emen , whe eas he GA eaches mo e
han 250 poin s.
In his e sion o he p oblem, he algo i hm ha seems ge be e esul s is he
gene ic wi h an imp o emen o 275 pe cen age poin s. We do no eally know why
he PSO algo i hm ge s much wo se esul s in his a ian o he p oblem i execu ions
o s anda d PDO do no ake much di e ence.
Wi h espec o he esul s ob ained in he esolu ion o he a ian in which
each p oduce can sell simul aneously wi h se e al p oduc s, we obse e he ollowing
dis inc ions in he h ee algo i hms applied o his a ian .
I we add up he ob ained pe cen age poin s achie ed by he h ee p oduc s
sold by each p oduce , i gi es us an ini ial si ua ion acco ding o he da a ob ained in
s anda d execu ions.
Wi h espec he inal esul s, i happens he same. The ob ained pe cen age
poin s achie ed by p oduc s a e lowe han in he s anda d execu ion, bu i we add
hose ob ained by he h ee p oduc s sold oge he , we ge a highe sco e han he
no mal e sion. This is because he gene ic algo i hm is applied o h ee di e en
p oduc s join ly. I we a e able o op imize a single p oduc o some ex en , and apply
he same echnique o wo o he p oduc s in a coo dina ed way, we ge be e esul s,
as we will be ob aining be e p oduc s, which a e coo dina ed o e icien ly di ide he
demand space.
In he las expe imen , which co esponds o he execu ion o Minimax wi h
di e en dep hs, i is clea ly seen ha when we un he p oblem wi h a dep h 2 o he
opponen and 4 o us, we ge a inal sco e o 53 pe cen age poin s. Howe e , i we
execu e he algo i hm wi h supe io dep h o us (2 o he opponen , 8 o us), we
ob ain a be e inal sco e, 57 pe cen age poin s. So we see ha , i we educe ou
dep h and expand ha o ou opponen , he esul s will be wo se o us and be e o
he opponen . The e o e, he esul ob ained by he Minimax depends on he dep h o
which we a e willing o go. We should no o ge ha he unning ime g ows
exponen ially wi h he dep h.
Finally, a his poin we can conclude ha we ha e comple ed he goals se a
he beginning o his p ojec . Among he asks pe o med, we highligh he pa icula
99
complexi y o he eal case s udy we de eloped wi h he aid o Feebbo. I has se ed as
an expe ience h oughou he p ojec de elopmen . Ca ying i ou has b ough some
se backs. The g ea es o hem may ha e been he pa o esea ch on how o conduc
su eys o housands o people in o de o ge answe s ha help us o ou case s udy
and ou applica ion. Mo eo e , in hese su eys we had o add ques ions o
pe sonali y which we also had o in es iga e. In addi ion, he su ey esul s we e no
a ailable immedia ely, as we wan ed o each a ai ly high numbe o su eyed people.
As inal da a, we p esen he p ice and some o he ea u es o he mobile
phone ha ge s one o he algo i hms o ou applica ion o pe o m he execu ion o
eal case s udy (in his case we used he Gene ic Algo i hm). The p ice o he mobile
phone is 154 eu os and has he ollowing ea u es: Nano SIM ca d, FM adio,
Blue oo h, wa e p oo , ha e NFC echnology, mobile wi h Dual SIM, a young design.
Finally, we spo ligh he po en ial applica ion o oday's wo kplace, pa icula ly
in he a ea o ma ke ing.
14.5 Possible Fu u e Wo k
This sec ion we will explain all he asks we could ca y ou in he u u e o
imp o e and expand his p ojec .
As we ha e al eady men ioned, in addi ion o he desk op applica ion we ha e
also de eloped a mobile applica ion o his p og am, e en hough wi hou some
unc ionali ies, such as he eading case and w i ing o ile. Mo eo e , as i is expec ed
he algo i hms execu e much slowe in he mobile app.
In he u u e we could make a Clien – Se e sys em in which he app would be
jus he in e ace o he use o choose he algo i hms you wan o execu e, a ian s,
manual da a en y, e c. A e ha ing he necessa y da a o he execu ion, he eques
would be sen o he se e , which would hen ca y ou he algo i hm, as i would un
i much as e . When he execu ion would inish, i would e u n he esul o he app
o show i o he use . As an idea, you could use a REST sys em se ices as ansac ions
h ough Json objec s o acili a e he communica ion wi h ou de eloped p og am in
Ja a.
Ano he possible imp o emen o he p ojec e e s o ob aining he op imum
p ice o ou p oduc . Righ now we use a weigh ed a e age unc ion, bu we also
conside ed ano he op ion ha we inally did no de elop. This op ion is o es ima e a
linea unc ion ha ing as many inpu pa ame e s as ea u es has he mobile phone,
which would e u n us he p ice. This unc ion can be in e pola ed om he ac ual
100
p ices o he mobile phones we use o model he compe i ion, so ha each o hese
phones (along wi h i s known p ice) is a poin o ha unc ion. To heu is ically es ima e
he coe icien s o he linea unc ion, we could use a gene ic algo i hm: each
indi idual (ch omosome) is a speci ic combina ion o weigh s (coe icien s), and he
i ness unc ion e u ns he dis ance be ween he ac ual p ice and he es ima ed p ice
i we use he weigh s o ha c omosome. The GA would disca d hose ha ha e a
g ea e dis ance and would keep he ones which i mo e.
Ano he possible u u e imp o emen is o add mo e algo i hms. Fo example,
we could implemen he Hill Climbing. Al hough algo i hm i is assumed ha i is wo se
han Simula ed Annealing since i ge s s uck in local maximums, i o e s some
in e es ing a ia ions ha we could s udy.
Finally, mo e p oblem a ian s could be added o ou p og am. As an example,
we could de elop a a ian o he e sion wi h di e en p oduc s o each p oduce ,
whe e each p oduce may ha e a di e en numbe o p oduc s. Fo ins ance, a use
could play wi h ou di e en p oduc s whe eas ano he use wi h only wo. The
numbe o p oduc s would no ha e o be he same o all p oduce s.