PDF de programación - Algoritmos Basados en Inteligencia Colectiva para la Resolución de Problemas de Bioinformática y Telecomunicaciones

Algoritmos Basados en Inteligencia Colectiva

para la Resolución de Problemas de
Bioinformática y Telecomunicaciones

Trabajo de Investigación Tutelado

Programa de Máster en Ingeniería del

Software e Inteligencia Artificial

Periodo 2006/2007

Alumno: José Manuel García Nieto

Tutor: Enrique Alba Torres

Universidad de Málaga, Septiembre de 2007

Resumen

En este trabajo se estudia la resolución de problemas procedentes del dominio
de la Bioinformática y las Telecomunicaciones mediante algoritmos bioinspira-
dos. En concreto, nos centramos en una subclase de éstos basada en procesos
de inteligencia colectiva (Swarm Intelligence). Actualmente, existe un crecien-
te interés en los problemas relacionados con el descubrimiento de propiedades
en el campo de la genética, siendo especialmente sensible en los estudios sobre
análisis de cánceres. Un foco diferente de interés en la investigación científica,
aunque en cierto sentido relacionado con el anterior, reside en el campo de las
telecomunicaciones, debido a la gran demanda de servicios de comunicación por
parte de la sociedad. Muchos de estos problemas pueden plantearse como pro-
blemas de optimización que no pueden resolverse de forma exacta o exhaustiva
debido al gran tamaño de su espacio de soluciones. En tales casos, las técnicas
metaheurísticas se convierten en una buena opción para encontrar alguna solu-
ción. Estas técnicas no aseguran una solución óptima pero en la mayoría de los
casos pueden obtener una solución aceptablemente buena en un tiempo razona-
ble. Dentro de las metaheurísticas se encuentran los algoritmos bioinspirados,
que se inspiran en algunos procesos naturales emulando el “modus operandi” de
ciertos animales cuando se enfrentan a problemas de supervivencia. Tras una
breve revisión sobre problemas de bioinformática y telecomunicaciones, se reali-
za una visión global de los algoritmos de inteligencia colectiva. A continuación,
el trabajo aborda la resolución del problema de la selección y clasificación de
genes en Microarrays de ADN (como parte bioinformática) y el problema de la
gestión de la localización de terminales móviles en redes GSM (como parte de
telecomunicaciones).

Índice general

1. Introducción

2. Problemas de Bioinformática y Telecomunicaciones

2.1. Selección y Clasificación de Genes en Microarrays de ADN . . . .
2.2. Gestión de la Localización en Redes GSM . . . . . . . . . . . . .

5

7
7
9

3. Algoritmos Basados en Inteligencia Colectiva

3.1. Swarm Intelligence: Una Visión General

13
13
. . . . . . . . . . . . . .
15
3.1.1. Algoritmos de Colonias de Hormigas . . . . . . . . . . . .
16
3.1.2. Algoritmos de Cúmulos de Partículas
. . . . . . . . . . .
3.1.3. Algoritmos Basados en la Polinización de Abejas Artificiales 18
18

3.2. Algoritmo de Cúmulos Basado en Espacios Geométricos . . . . .

21
22
23
23
24

29
31
31
32
33

35

37

4. Selección y Clasificación de Genes en Microarrays de ADN

4.1. Función de Fitness . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Microarrays Utilizados . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . .
4.3. Algoritmos y Parámetros
4.4. Experimentos y Resultados
. . . . . . . . . . . . . . . . . . . . .

5. Gestión de la Localización de Terminales Móviles

5.1. Experimentos y Resultados

. . . . . . . . . . . . . . . . . . . . .
5.1.1. Efecto Segmentación de la Red . . . . . . . . . . . . . . .
5.1.2. Análisis de la Robustez
. . . . . . . . . . . . . . . . . . .
5.1.3. Comparación Entre GPSO y HNN+BD . . . . . . . . . .

6. Conclusiones

Bibliografía

3

4

Capítulo 1

Introducción

Uno de los principales frentes de trabajo en el ámbito de la Informática ha
sido tradicionalmente el diseño de algoritmos cada vez más eficientes para la
solución de problemas tanto de optimización como de búsqueda. En este domi-
nio, el objetivo consiste en obtener algoritmos nuevos que necesiten un esfuerzo
computacional más pequeño que los algoritmos existentes con la intención de
abordar los problemas de forma más eficiente y también para poder abordar
tareas que estaban vedadas debido al coste de otras técnicas clásicas.

La investigación en algoritmos tanto exactos como heurísticos para resol-
ver problemas de optimización combinatoria tiene una vigencia inusualmente
importante en estos días, ya que nos enfrentamos a nuevos problemas de inge-
niería al mismo tiempo que contamos con nuevos recursos computaciones tales
como máquinas más potentes, redes y entornos como Internet.

Los algoritmos basados en inteligencia colectiva o Swarm Intelligence (SI), es
un novedoso paradigma de inteligencia distribuida para la resolución de proble-
mas de optimización, que toma su inspiración en ejemplos biológicos de compor-
tamiento colectivo (swarming) como el fenómeno de las bandadas y las manadas
en los vertebrados. Los algoritmos de cúmulos de partículas o Particle Swarm
Optimization (PSO) [26] incorporan comportamientos colectivos observados en
las bandadas de aves, los bancos de peces, las colmenas de abejas e incluso en el
comportamiento social de los humanos. Los algoritmos de colonias de hormigas,
conocidos como Ant Colony Optimization (ACO) [13], trabajan con sistemas
artificiales que se inspiran en el comportamiento de búsqueda de las hormigas
reales, siendo utilizados para resolver problemas de optimización discreta.

Este tipo de técnicas metaheurísticas bioinspiradas vienen siendo aplicadas
con éxito durante esta última década y actualmente en multitud de problemas
de optimización, ya sea en problemas de naturaleza discreta, continua e incluso
con representación de árboles y grafos. La idea de reutilizar mecanismos que
siempre han existido en la naturaleza para su aplicación en problemas reales,
introduce un componente de interés público en otras disciplinas de la ciencia
cómo la biología, psicología e incluso la reciente nanotecnología. Supone un
campo totalmente abierto a la investigación, por lo que suscita un gran interés
por parte de la comunidad científica.

5

Dentro de los dominios de conocimiento que pueden beneficiarse de estos
eficientes algoritmos de optimización, la investigación microbiológica a nivel
molecular está viviendo un cambio espectacular en los últimos años. En apenas
una década se ha pasado de trabajos basados en el estudio de uno o unos pocos
genes al análisis de los genomas en su totalidad. La técnica de Microarrays de
ADN (MAs) [4] está atrayendo un gran interés, ya que permite monitorizar la
actividad de un genoma completo mediante un simple experimento. Además,
cada uno de estos experimentos con MAs puede suponer el manejo desde cien-
tos hasta decenas de miles de genes, normalmente con decenas de muestras por
gen. Por este motivo, son necesarias técnicas de reducción que permitan agru-
par genes con patrones de expresión relacionados e informativos, desechando
la información irrelevante. Algunos ejemplos son las técnicas de clustering [9],
reconocimiento de patrones o reglas [23], selección y clasificación de genes en
MAs [15].

Por otra parte, las telecomunicaciones son un símbolo importante de nuestra
actual sociedad de la información. Con un rápido crecimiento de servicios para el
usuario, la telecomunicación es un campo en el que hay muchas líneas de inves-
tigación abiertas que están desafiando a la comunidad investigadora. Muchos de
los problemas que podemos encontrar en esta área pueden ser formulados como
problemas de optimización. Algunos ejemplos son: la signación frecuencias en
enlaces de radio [33], la gestión de localización de terminales móviles en redes
GSM [48] y diseñar la red de telecomunicaciones [7].

En la práctica, la mayoría de estos problemas de optimización son inabor-
dables con técnicas exactas. Por eso, es adecuado el uso de enfoques heurísticos
tales como los algoritmos evolutivos y bioinspirados. No obstante, la gran com-
plejidad de las instancias reales de esos problemas requieren la potencia de cálcu-
lo de varias máquinas trabajando juntas para encontrar soluciones aceptables.
Esto da lugar a la aplicación de algoritmos paralelos para abordar eficientemente
esos problemas.

El presente trabajo se ha estructurado de la siguiente manera. En primer lu-
gar se realiza un estudio de diferentes problemas del dominio de la Bioinformáti-
ca y las Telecomunicaciones en el Capítulo 2. De entre ellos se ha escogido dos
con aplicación real directa para resolverlos con algoritmos de inteligencia colec-
tiva: la selección y clasificación de genes en Microarrays de ADN, como ejemplo
de bioinformática y la gestión de la localización óptima de terminales móviles
en redes GSM, como exponente de las telecomunicaciones. Posteriormente, en el
Capítulo 3 se hace una visión global de de los algoritmos de Swarm Intellegence,
describiéndose de forma general y centrándose especialmente en los algoritmos
usados en la tercera parte del trabajo. En ésta (Capítulos 4 y 5), se detallan
los problemas abordados y se presentan los experimentos y los resultados ob-
tenidos. Por último, se concluye en el Capítulo 6 con las principales reflexiones
obtenidas de este trabajo por parte del alumno.

6

Capítulo 2

Problemas de
Bioinformática y
Telecomunicaciones

Este capítulo desarrolla una descripción de los problemas abordados en este
trabajo pertenecientes al campo de la bioinformática y las telecomunicaciones.
Como se ha mencionado anteriormente, se han elegido los problemas de “Se-
lección y Clasificación de Genes en Microarrays de ADN” y la “Gestión de la
Localización Óptima de Terminales Móviles en Redes GSM”, ambos de comple-
jidad NP-difícil. En primer lugar se realiza un breve repaso por los artículos más
relacionados del estado del arte, para pasar a la motivación y definición teórica
de cada problema.

2.1. Selección y Clasificación de Genes