Download Document

Sistema Inmune Artificial: Un Nuevo Paradigma De
Inteligencia Computacional
por: Nareli Cruz Cortés
1
Sistemas bio-inspirados
Algunos de ellos son:
• El sistema nervioso central (redes neuronales)
• Sistemas evolutivos (algoritmos evolutivos)
• Colonia de hormigas
• El sistema inmune biológico (sistema inmune artificial).
2
¿por qué el sistema inmune?
• Sistema de procesamiento de información
• Adaptativo, distribuido y paralelo
• Usa aprendizaje y memoria
• Reconoce patrones que se han presentado en el pasado, aún a
partir de información incompleta.
• Su comportamiento global es una propiedad emergente de
muchas interacciones locales.
3
El sistema inmune natural tiene dos lı́neas básicas de defensa:
• La respuesta innata
• La respuesta adaptativa o aprendida
4
Figure 1: Linfocitos o células T y B
5
Sistema inmune artificial
Son sistemas adaptativos inspirados por la teorı́a inmunológica y
funciones, principios y modelos inmunes observados, los cuales son
aplicados a la solución de problemas.
6
Caracterı́sticas del sistema inmune
• Aprendizaje
• Memoria
• Descentralizado
• Reconocimiento de patrones
• Paralelo
• Diversidad
• Autoregulatorio
• Detección distribuida
7
Figure 2: Las células B aprenden!
8
Esquema para un algoritmo con inspiración biológica:
1. Representación de los componenetes del sistema
2. Un conjunto de mecanismos para evaluar la interacción de los
individuos con el ambiente y/o entre ellos.
3. Un procedimiento de adaptación que conduzca la dinámica del
sistema.
9
Principales modelos del sistema inmune
• Modelos de médula ósea (librerı́as)
• Modelos de timo
– Algoritmo selección negativa
• Algoritmos de selección clonal
• Teorı́a de red inmune
10
Celulas propias
Linfocitos inmaduros
Detectores que sobreviven
Figure 3: Algoritmo de selección negativa
11
Epitope
Receptor
(paratope)
Antigens
High affinity
Lynphocyte
Antigens
Low affinity
Figure 4: Lymphocyte binding
12
Antigen
antibody
low affinity
antibody
high affinity
proliferation(cloning)
hypermutation
memory cells
effector cells
Figure 5: Principio de seleción clonal
13
p2
Ab
Foreign stimulus
Ag
(epitope)
i2
p1
Internal image
Ab
i1
p3
Ab
i3
i1
Ab
px
Figure 6: Teorı́a de Red Inmune
14
Principales aplicaciones del sistema inmune artificial
Las emulaciones del sistema inmune se han aplicado principalmente
a los siguientes problemas:
• Seguridad de redes y sistemas de cómputo.
• Detección de anomalı́as
• Reconocimiento de patrones
• Sistemas clasificadores
• Planeamiento de robots
• Diseño de circuitos electrónicos
• Optimización
15
Sistema inmune artificial para problemas de optimización:
• Hajela and Yoo (1999). Handling constraints in GA.
• Cruz, Trejo y Coello (2005) Handling constraints.
• Kelsey and Timmis (2003). Multimodal optimization.
• Coello Coello and Cruz-Cortés (2004). Multiobjective
optimization.
• Balicki’s proposal (2004). Multiobjective optimization.
• Luh and Chueh (2004). Multiobjective optimization.
16
AG
optimiza la funcion
objetivo f(x)
AG interno
sistema inmune artificial
(manejo de restricciones)
Evoluciona la poblacion de
anticuerpos hacia la poblacion de
antigenos
Figure 7: Sistema inmune artificial para manejo de restricciones en
AG’s, Hajela and Yoo (1999).
17
CLONALG algorithm Basado en el Principio de Selección
clonal:
1. Generate j antibodies randomly.
2. Repeat a predetermined number of times:
(a) Determine the affinity of each antibody (Ab).
(b) Select the n highest affinity antibodies.
(c) The n antibodies are cloned proportionally to their
affinities, generating a repertory C of clones.
(d) The clones from C are subject to a hyper-mutation process
inversely proportional to their antigenic affinity.
(e) Determine the affinity of the mutated clones C.
(f) From sets C and Ab, select the j highest affinity individuals
to compose the new antibodies’ population.
(g) Replace the d lowest affinity antibodies by random new
individuals.
18
Finite field exponentiation
Let P a big prime defined in the finite field F over the integers Zp .
Let α be an arbitrary element of a finite field F , e an arbitrary
positive integer. Then, field exponentiation is defined as the
problem of finding an element β ∈ F such that the equation
β = αe modP holds.
19
Let α ∈ F and e = 415. Find β = αe
Naive method: β = α × α × α × . . . × α × α × α
|
{z
}
415 times
Binary method:
α2 = α × α
α4 = α2 × α2
α8 = α4 × α4
α16 = α8 × α8
α32 = α16 × α16
α64 = α32 × α32
α128 = α64 × α64
α256 = α128 × α128
α384 = α256 × α128
α400 = α384 × α16
α408 = α400 × α8
α412 = α408 × α4
α414 = α412 × α2
α415 = α414 × α
Optimal method:
α2 = α × α
α3 = α2 × α
α5 = α2 × α3
α10 = α5 × α5
α20 = α10 × α10
α40 = α20 × α20
α80 = α40 × α40
α83 = α3 × α80
α166 = α83 × α83
α332 = α166 × α166
α415 = α332 × α83
20
Addition chain
An addition chain U for a positive integer e of length l is a
sequence of positive integers U = {u0 , u1 , · · · , ul }, and an
associated sequence of r pairs V = {v1 , v2 · · · , vl } with
vi = (i1 , i2 ), 0 ≤ i2 ≤ i1 < i, such that:
• u0 = 1 and ul = e;
• for each ui , 1 ≤ i ≤ l, ui = ui1 + ui2 .
21
Example of an addition chain
Consider the case e = 415 = (110011111)2 Then, the binary
addition chain with length l = 14 for that e is,
U
:=
1 → 2 → 4 → 8 → 16 → 32 → 64 → 128 →
256 → 384 → 400 → 408 → 412 → 414 → 415
With the associated sequence governed by the rule,
ui = ui−1 + ui−1 = 2ui−1 for 1 ≤ i ≤ 8 and, u9 = u8 + u7 , and
u10+m = u9+m + u4−m , for m = 0, 1, . . . , 4.
22
Optimal addition chains for m = 32k (1/2)
m
m−1
Artificial immune system (AIS)
AIS
Takagi
ITMIA
binary method
32
31
1-2-3-6-7-14-28-31
7
7
8
64
63
1-2-3-6-7-14-28-56-63
8
8
10
96
95
1-2-3-5-10-20-40-80-90-95
9
9
11
128
127
1-2-3-6-12-24-48-96-120-126-127
10
10
12
160
159
1-2-3-6-12-24-48-96-144-156-159
10
10
12
192
191
1-2-4-8-16-17-34-68-136-170-187-191
11
11
13
224
223
1-2-3-6-12-13-26-52-104-208-221-223
11
11
13
256
255
1-2-3-5-10-20-40-80-85-170-255
10
10
14
288
287
1-2-3-5-7-14-28-56-112-224-280-287
11
11
13
320
319
1-2-3-6-12-18-36-72-144-288-306-318-319
12
12
14
352
351
1-2-3-6-12-24-27-54-108-216-324-351
11
11
14
384
383
1-2-3-5-10-20-40-80-160-320-360-380-383
12*
13
15
416
415
1-2-3-5-10-20-40-80-83-166-332-415
11*
12
14
448
447
1-2-3-6-12-18-36-72-144-288-432-444-447
12
12
15
23
Optimal addition chains for m = 32k (2/2)
m
m−1
Artificial immune system (AIS)
AIS
Takagi
ITMIA
binary method
480
479
1-2-3-6-7-14-28-56-112-224-448-476-479
12*
13
15
512
511
1-2-3-5-10-15-30-60-120-240-480-510-511
12
12
16
576
575
1-2-3-5-10-20-23-46-92-184-368-552-575
12*
13
15
608
607
1-2-3-6-12-18-36-72-144-288-576-594-606-607
13
13
15
640
639
1-2-3-6-12-24-26-52-104-208-416-624-636-639
13
13
16
704
703
1-2-3-5-10-20-40-80-160-320-640-680-700-703
13
13
16
736
735
1-2-3-5-10-15-30-60-120-240-480-720-735
12
12
16
768
767
1-2-3-5-10-20-40-80-83-166-332-664-747-767
13*
14
17
800
799
1-2-3-6-12-24-48-96-192-384-768-792-798-799
13
13
15
832
831
1-2-3-6-12-24-48-96-192-384-768-816-828-831
13
13
16
864
863
1-2-3-5-10-20-40-43-86-172-344-688-860-863
13*
15
16
896
895
1-2-3-5-10-20-40-80-160-163-326-652-815-895
13*
14
17
24
Optimal addition chains for e = p − 1, p a prime.
p
p−1
AIS
AIS
ITMIA Binary method
163
162
1-2-4-8-16-32-64-80-81-162
9
9
167
166
1-2-3-5-10-20-40-80-83-166
9*
10
173
172
1-2-3-5-10-20-40-43-86-172
9*
10
191
190
1-2-3-5-10-20-40-80-160-180-190
10*
12
193
192
1-2-3-6-12-24-48-96-192
8
8
197
196
1-2-4-8-16-32-48-49-98-196
9
9
223
222
1-2-3-6-12-24-48-96-192-216-222
10*
12
2 233
232
1-2-4-8-16-24-28-29-58-116-232
10
10
269
268
1-2-4-8-16-32-64-66-67-134-268
10
10
271
270
1-2-3-5-10-20-40-80-90-180-270
10*
11
293
292
1-2-4-8-16-32-64-72-73-146-292
10
10
331
330
1-2-3-5-10-20-40-80-160-320-330
10*
11
379
378
1-2-4-8-16-18-36-72-144-288-360-378
11*
13
383
382
1-2-3-5-10-20-40-80-160-320-360-380-382
12*
14
389
388
1-2-4-8-16-32-64-96-97-194-388
10
10
443
442
1-2-3-6-12-13-26-52-104-208-416-442
11*
13
463
462
1-2-4-8-16-32-33-66-132-264-396-462
11*
13
491
490
1-2-3-5-10-20-40-80-160-320-480-490
11*
13
509
508
1-2-3-6-12-14-28-30-60-120-240-480-508
12*
14
521
520
1-2-4-8-16-32-64-65-130-260-520
10
10
25
Congresos:
• International Conference on Artificial Immune Systems,
ICARIS desde 2002.
• Sesiones especiales de Sistema Inmune Artificial en los
principales congresos internacionales de Computación
Evolutiva como GECCO, CIS, PPSN.
26
Libros especializados:
• Artificial immune systems, editado por Dasgupta en 1999.
• Artificial Immune Systems: A New Computational Intelligence
Approach Por Leandro Nunes de Castro, Jonathan Timmis
(2002)
• Design Principles for the Immune System and Other
Distributed Autonomous Systems Por Irun R Cohen, Lee A
Segel
• Immunity-based Systems: A Design Perspective Por Yoshiteru
Ishida (2003)
27
28