algoritmos culturales

Algoritmos Culturales para resolucin de
o
problemas complejos de Asignacin Horaria
o

Carlos R. Soza Canales
Tesis desarrollada como requisito parcial
para la obtencin del ttulo y grado de
o

Ingeniero Civil en Informtica
a
Magister en Ciencias de la Ingeniera Informtica

a

Departamento de Informtica
a
Universidad Tcnica Federico Santa Mara
e

Valparaso, Chile.
c
 Carlos R. Soza Canales, Octubre 2005.

Universidad Tcnica Federico Santa Mara
e

Departmento de Informtica
a
Valparaso - Chile


TITULO DE LA TESIS:


ALGORITMOS CULTURALES PARA RESOLUCION DE

PROBLEMAS COMPLEJOS DE ASIGNACION HORARIA
AUTOR

CARLOS R. SOZA CANALES
TRABAJO DE GRADO, presentado en cumplimienoto parcial de
los requisitos para el ttulo deIngeniero Civil en Informtica y el

a
grado de Magister en Ciencias de la Ingeniera Informtica de

a
la Universidad Tcnica Federico Santa Mara.
e

Dra. Mara Cristina Ri


Profesor Gua


Dra. Mara Cristina Ri


Correferente

Sr. Ricardo Landa Becerra

Correferente Externo

Valparaso - Chile.

Octubre 2005.

3
ABSTRACT
Many applications consecrate the useof asymmetric distributions to t real data,
and practical situations often require robust parametric inference. This thesis presents
the derivation of M-estimators with asymmetric in
uence functions, motivated by the
q 0 distribution. This law, based on the multiplicative model for speckled imagery, can
be highly skewed and maximum likelihood estimation can be severely hampered by
smallpercentages of outliers. These outliers appear mainly because the hypothesis of
independence and equal distribution of observations are seldom satised in practice;
for instance, in the process of ltering, some pixels within a window frequently come
from regions with dierent underlying distributions. Traditional robust estimation
methods, based on symmetric robustifying functions, assume thatthe distribution
is symmetric, but when the data distribution is asymmetric these methods yield
biased estimators. Empirical in
uence functions for maximum likelihood estimators
are computed, and based on this information this thesis propose the Asymmetric Mestimator (AM-estimator), an M-estimator with asymmetric redescending functions.
A

RESUMEN
Muchas aplicaciones utilizan distribucionesasimtricas para ajustar datos reales,
e
y frecuentemente las situaciones prcticas requieren tcnicas de inferencia paramtria
e
e
ca robusta. Esta tesis presenta la derivacin de los M-estimadores con funciones de
o
in
uencia asimtricas, motivados en la distribucin q 0 . Esta ley, basada en el modee
o
lo multiplicativo para imgenes contaminadas con ruido speckle, puede ser altamentea
sesgada, y la estimacin por mxima verosimilitud puede ser severamente obstaculizao
a
da por peque~os porcentajes de outliers. Los outliers aparecen principalmente debido
n
a que las hiptesis de independencia e igual distribucin de las observaciones rara vez
o
o
son satisfechas en la prctica; por ejemplo, en el proceso de ltraje, algunos pixeles
a
dentro de una ventana a menudoprovienen de regiones con diferentes distribuciones
subyacentes. Los mtodos tradicionales de estimacin robusta, basados en funciones
e
o
de robustez simtricas, asumen que la distribucin es simtrica, pero cuando la dise
o
e
tribucin de los datos es asimtrica tales mtodos producen estimadores sesgados.
o
e
e
Las funciones de in
uencia emprica son calculadas, y basada en estainformacin,

o
esta tesis propone el Asymmetric M-estimator (AM-estimator), un M-estimador con
funciones redescendentes asimtricas.
e
A

ndice general
I
Resumen

3

ndice de guras
I

6

ndice de tablas
I

7

ndice de algoritmos
I

8

Agradecimientos

9

1. Estado del Arte

1

1.1. Computacin Evolutiva . . . . . . . . . . . . . . . . . . . . . . . . . ....