-
Notifications
You must be signed in to change notification settings - Fork 1
/
main.tex
4315 lines (2950 loc) · 259 KB
/
main.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% The Legrand Orange Book
% LaTeX Template
% Version 2.4 (26/09/2018)
%
% This template was downloaded from:
% http://www.LaTeXTemplates.com
%
% Original author:
% Mathias Legrand (legrand.mathias@gmail.com) with modifications by:
% Vel (vel@latextemplates.com)
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
% Compiling this template:
% This template uses biber for its bibliography and makeindex for its index.
% When you first open the template, compile it from the command line with the
% commands below to make sure your LaTeX distribution is configured correctly:
%
% 1) pdflatex main
% 2) makeindex main.idx -s StyleInd.ist
% 3) biber main
% 4) pdflatex main x 2
%
% After this, when you wish to update the bibliography/index use the appropriate
% command above and make sure to compile with pdflatex several times
% afterwards to propagate your changes to the document.
%
% This template also uses a number of packages which may need to be
% updated to the newest versions for the template to compile. It is strongly
% recommended you update your LaTeX distribution if you have any
% compilation errors.
%
% Important note:
% Chapter heading images should have a 2:1 width:height ratio,
% e.g. 920px width and 460px height.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% arara: pdflatex: { shell: yes }
% arara: biber
% arara: pdflatex: { shell: yes }
% arara: htlatex
% arara: clean: { files: [ main.aux, main.log] }
%----------------------------------------------------------------------------------------
% PACKAGES AND OTHER DOCUMENT CONFIGURATIONS
%----------------------------------------------------------------------------------------
\documentclass[11pt,fleqn]{book} % Default font size and left-justified equations
\input{structure.tex} % Insert the commands.tex file which contains the majority of the structure behind the template
%\hypersetup{pdftitle={Title},pdfauthor={Author}} % Uncomment and fill out to include PDF metadata for the author and title of the book
%----------------------------------------------------------------------------------------
\usepackage[ruled,longend,noend]{algorithm2e}
\newcommand\mycommfont[1]{\footnotesize\ttfamily\textcolor{blue}{#1}}
\SetCommentSty{mycommfont}
\begin{document}
%----------------------------------------------------------------------------------------
% TITLE PAGE
%----------------------------------------------------------------------------------------
\begingroup
\thispagestyle{empty} % Suppress headers and footers on the title page
\begin{tikzpicture}[remember picture,overlay]
\node[inner sep=0pt] (background) at (current page.center) {\includegraphics[width=\paperwidth]{background.pdf}};
\draw (current page.center) node [fill=ocre!30!white,fill opacity=0.6,text opacity=1,inner sep=1cm]{\Huge\centering\bfseries\sffamily\parbox[c][][t]{\paperwidth}{\centering El libro Azul de Inteligencia Artificial\\[15pt] % Book title
{\Large 1era Edición}\\[20pt] % Subtitle
{\huge Alejandro Medina Reyes}}}; % Author name
\end{tikzpicture}
\vfill
\endgroup
%----------------------------------------------------------------------------------------
% COPYRIGHT PAGE
%----------------------------------------------------------------------------------------
\newpage
~\vfill
\thispagestyle{empty}
\noindent Copyright \copyright\ 2020 Alejandro Medina Reyes\\ % Copyright notice
\noindent \textsc{}\\ % Publisher
\noindent \textsc{}\\ % URL
\noindent Licensed under the Creative Commons Attribution-NonCommercial 3.0 Unported License (the ``License''). You may not use this file except in compliance with the License. You may obtain a copy of the License at \url{http://creativecommons.org/licenses/by-nc/3.0}. Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \textsc{``as is'' basis, without warranties or conditions of any kind}, either express or implied. See the License for the specific language governing permissions and limitations under the License.\\ % License information, replace this with your own license (if any)
\noindent \textit{} % Printing/edition date
%----------------------------------------------------------------------------------------
% TABLE OF CONTENTS
%----------------------------------------------------------------------------------------
%\usechapterimagefalse % If you don't want to include a chapter image, use this to toggle images off - it can be enabled later with \usechapterimagetrue
\chapterimage{chapter_head.pdf} % Table of contents heading image
\pagestyle{empty} % Disable headers and footers for the following pages
\tableofcontents % Print the table of contents itself
\pagestyle{fancy} % Enable headers and footers again
%----------------------------------------------------------------------------------------
% PART
%----------------------------------------------------------------------------------------
\part{Parte uno}
%----------------------------------------------------------------------------------------
% Prólogo y agradecimientos
%----------------------------------------------------------------------------------------
\chapterimage{chapter_head.pdf} % Chapter heading image
\chapter{Prólogo y agradecimientos}
\section{Prólogo}\index{Prólogo}
He decidido escribir este libro debido a que considero que es una rama de la computación muy interesante, además estos últimos años se ha incrementado el interés por la inteligencia artificial, debido principalmente a dos factores, la gran cantidad de información disponible que combinada con técnicas de deep learning nos permite hacer predicciones o generalizaciones muy exactas y el avance que hemos tenido tecnológicamente, siendo más preciso el desarrollo de potentes unidades de procesamiento gráfico, esto último es relevante ya que son capaces de trabajar eficazmente con operaciones de matrices que son ampliamente utilizadas por las redes neuronales.
A pesar de ser un campo con muchos años de investigación pienso que no hay mejor momento para descubrir todo el potencial que ésta área nos ofrece y explorar cómo puede repercutir en el mundo que nos rodea.
Este libro busca explorar diversos temas del campo de la inteligencia artificial con el fin de introducir diferentes paradigmas con los cuales se trabaja, revisando la parte conceptual y matemática, así como los usos de las diferentes técnicas.
%------------------------------------------------
\section{Agradecimientos}\index{Agradecimientos}
Primero quiero agradecer a mis padres ya que me han apoyado en todo mi desarrollo personal y académico, mis logros son un reflejo del gran ejemplo que me han dado y de lo mucho que han hecho por mi. Igualmente es importante reconocer el apoyo de mi hermana en las distintas actividades que he desempeñado y en los proyectos que me he propuesto.
También quiero agradecer a mis maestros que me han enseñado mucho a lo largo de mi carrera profesional, agradezco principalmente a aquellos que me han motivado a crecer y a perseguir mis sueños además de brindarme los conocimientos y herramientas del curso correspondiente. Entre mis maestros quiero darle las gracias especialmente a tres de ellos: José Jesús Sánchez Farías, José Guillermo Fierro Mendoza y Patricia Galvan Morales ya que sin su apoyo no creo que me hubiera decidido a hacer este libro.
Finalmente quiero darle gracias a mi amada esposa que me ha motivado a desarrollarme como persona y que siempre ha estado a mi lado dándome el impulso necesario para llevar a cabo este tipo de proyectos.
%----------------------------------------------------------------------------------------
% PART
%----------------------------------------------------------------------------------------
\part{Parte dos: Fundamentos}
%----------------------------------------------------------------------------------------
% CHAPTER 3
%----------------------------------------------------------------------------------------
\chapterimage{chapter_head.pdf} % Chapter heading image
\chapter{Historia de la inteligencia artificial}
\section{Introducción}\index{Introducción - Historia de la IA}
Considero interesante revisar primero un poco de la historia de la Inteligencia Artificial, ya que nos permite ponernos en contexto acerca del estado actual de esta ciencia y cómo llegamos a este punto. También siendo una ciencia con muchas vertientes podemos analizar cuales fueron los aciertos y fallas del pasado para considerarlos en los desarrollos actuales.
\section{Ideas sobre inteligencia artificial}\index{Ideas sobre inteligencia artificial}
El deseo del ser humano por entender la inteligencia y ser capaces de replicarla se remonta a la antigüedad, un ejemplo es la existencia de Talos en la mitología griega, un gigante de bronce que protegía a la Creta minoica de posibles invasores, la versión más dominante de su origen dice que Talos era un autómata creado por Hefesto (Dios del fuego y la forja).
Existen otros ejemplos de autómatas antropomorfos como el robot de Leonardo da Vinci con la apariencia externa de una armadura, capaz de mover piernas y brazos o el autómata creado por Pierre Jacques-Droz en 1774, su creación podía escribir una carta compuesta por 50 caracteres determinados por el usuario.
%------------------------------------------------
\section{Orígenes de la inteligencia artificial}\index{Orígenes de la inteligencia artificial}
Si bien muchos consideran que el trabajo de Alan Turing “Computing Machinery and Intelligence” \cite{turing_compmach} dio inicio al campo de la inteligencia artificial creo relevante mencionar primero el trabajo realizado por Warren McCulloch and Walter Pitts en 1943, ese año publicaron "A logical calculus of the ideas immanent in nervous activity", aquí describieron un modelo de neurona que sentó las bases de lo que serían en un futuro las redes neuronales (Técnicas ampliamente usadas en la actualidad).
Posteriormente en 1950 Turing publico el trabajo mencionado anteriormente donde habló acerca del Test que lleva su nombre, mediante el cual en lugar de determinar si una máquina está “pensando”, tratamos de averiguar si es capaz de ganar en “el juego de la imitación” (Haciendo pensar a un ser humano que está hablando con otro humano), este trabajo fue de gran relevancia para el campo de la IA. Además del Test de Turing se cuestiono acerca de si una máquina puede realmente pensar y escribió algunas ideas sobre el desarrollo de máquinas capaces de aprender, este articulo es una lectura que yo personalmente considero de suma importancia para aquellos interesados en esta área.
\section{Nacimiento de la inteligencia artificial como ciencia}\index{Nacimiento de la inteligencia artificial como ciencia}
La conferencia de Dartmouth (“Dartmouth Summer Research Project on Artificial Intelligence”), realizada en 1956 y que duró 2 meses, es considerada como el evento que dio como resultado el nacimiento de la Inteligencia artificial como ciencia.
En 1955 fue John McCarthy quien decidió organizar un grupo para estudiar la siguiente conjetura: cada aspecto del aprendizaje o característica de la inteligencia puede en principio ser descrito de manera tan precisa que una máquina pueda simularlo. A continuación muestro la propuesta de la conferencia \cite{DARTHMOUTH}:
“We propose that a 2-month, 10-man study of artificial intelligence be carried out during the summer of 1956 at Dartmouth College in Hanover, New Hampshire. The study is to proceed on the basis of the conjecture that every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it. An attempt will be made to find how to make machines use language, form abstractions and concepts, solve kinds of problems now reserved for humans, and improve themselves. We think that a significant advance can be made in one or more of these problems if a carefully selected group of scientists work on it together for a summer.”
Es aquí donde de forma oficial se introduce el término Inteligencia Artificial. (Si bien es un término que ya se había utilizado fue aquí donde se popularizó y se convirtió en el término dominante). Entre aquellos que asistieron se encuentran el Dr. Marvin Minsky, Herbert A. Simon, Allen Newell, Ray Solomonoff, John Henry Holland, entre otros. En este evento se discutieron diferentes acercamientos para crear soluciones de Inteligencia Artificial, los asistentes mencionados terminaron teniendo un alto impacto en esta ciencia.
\section{La edad de oro 1956-1974} \index{La edad de oro 1956-1974}
A la conferencia de Dartmouth le siguió un gran entusiasmo en el campo de la inteligencia artificial, incluso se estimaba que en 20 años se tendrían máquinas completamente inteligentes, a pesar de que era demasiado optimista si hubo avances durante este periodo de tiempo.
Entre los trabajos más relevantes se encuentran algoritmos que usan el paradigma “Reasoning as search”, en los cuales se aproximaba a la solución de problemas paso a paso como si de un laberinto se tratará, retrocediendo al llegar callejón sin salida, Allen Newell y Herbert A. Simon trataron de capturar una versión general de este algoritmo. También se dieron avances en el reconocimiento del lenguaje general, ELIZA desarrollado en el MIT permitía conversar mediante frases preprogramadas. A finales de 1960 Marvin Minsky y Seymour Papert propusieron que el estudio de la inteligencia artificial debía dirigirse a solucionar problemas en situaciones simples un enfoque denominado como micro-mundos, Minsky y Papert desarrollaron un robot que era capaz de apilar cubos. También se desarrolló el Perceptrón un tipo de red neuronal artificial que veremos más adelante en este libro.
\section{El primer invierno de la inteligencia artificial 1974-1980} \index{El primer invierno de la inteligencia artificial 1974-1980}
Debido a las altas expectativas desarrolladas previamente hubo una gran decepción al ver que las promesas de la Inteligencia Artificial no se cumplían. Hubo un gran recorte en los presupuestos de investigación y el campo de las redes neuronales fue mayormente ignorado debido a las fuertes críticas de Minsky sobre las limitaciones del perceptrón.
\section{El boom de la inteligencia artificial 1980–1987} \index{El boom de la inteligencia artificial 1980–1987}
La llegada de sistemas expertos (capaces de tomar decisiones como si fuese un experto humano mediante el uso de reglas lógicas) permitieron un nuevo boom en la Inteligencia Artificial gracias a su utilidad en las empresas.
Otro punto importante es el resurgimiento de las redes neuronales, gracias a las redes de Hopfield y el desarrollo del algoritmo de retropropagación.
\section{El segundo invierno de la inteligencia artificial 1987-1993} \index{El segundo invierno de la inteligencia artificial 1987-1993}
Durante este tiempo se dio otra reducción en las inversiones hacia el campo de la IA, sin embargo hubo avances principalmente en el campo de la robótica. Personalmente considero que una de las razones por las cuales tuvo lugar este segundo invierno de la IA son las desventajas o limitaciones de los sistemas expertos:
\begin{itemize}
\item Existen tareas demasiado complejas, la necesidad de diseñar estas reglas de manera manual es una limitante.
\item Existe conocimiento en constante cambio, muchos sistemas expertos requieren que las reglas sean actualizadas manualmente lo cual puede llegar a ser un problema.
\item Estos sistemas suelen contener conocimiento de un área específica pero carecen de sentido común.
\end{itemize}
\section{Siglo XXI} \index{Siglo XXI}
Como mencione en el prólogo gracias a el aumento de potencia computacional y el acceso a grandes cantidades de información la Inteligencia Artificial ha visto grandes avances, entre los avances más notorios se encuentran las investigaciones y algoritmos de machine learning y deep learning.
\chapterimage{chapter_head.pdf} % Chapter heading image
\chapter{Fundamentos de la IA}
\section{Definición} \index{Definición}
Existen diferentes definiciones del término inteligencia artificial, de acuerdo a las ciencias de la computación la inteligencia artificial es el estudio de agentes inteligentes \cite{logical_approach}.
Un agente inteligente es capaz de percibir su entorno y actuar sobre él tratando de optimizar algún objetivo, un agente es inteligente debido a que presenta características como el razonamiento o el aprendizaje.
\begin{figure}[ht]
\centering\includegraphics[width=7.5cm]{ia/Agente.png}
\caption{Representación de un agente}
\label{fig:agente}
\end{figure}
Otra definición determina que la inteligencia artificial es el desarrollo de sistemas capaces de interpretar correctamente información externa, aprender de esta información para cumplir con ciertos objetivos o tareas adaptándose de manera flexible \cite{KAPLAN201915}.
Dependiendo de la definición diversos tipos de desarrollos pueden considerarse inteligentes o no, por ello yo prefiero una definición más abierta como la siguiente: la inteligencia artificial es la simulación de comportamientos inteligentes por parte de un sistema informático.
\section{Ciencias relacionadas con la IA} \index{Ciencias relacionadas con la IA}
La inteligencia artificial se relaciona con diversas ciencias que sirven de base para el desarrollo de esta ciencia, algunos ejemplos son los siguientes:
\begin{itemize}
\item Filosofía
\item Lógica/matemática
\item Ciencias computacionales
\item Psicología
\item Biología
\item Neurociencia
\end{itemize}
Es evidente como estas ciencias han ayudado al desarrollo de la inteligencia artificial, gracias a la teoría de la evolución se lograron generar algoritmos evolutivos, el estudio del cerebro nos dio ideas sobre la manera de tratar problemas como el reconocimiento de imágenes, la lógica nos permitió modelar la manera en la cual razonamos y gracias a la matemática somos capaces de formalizar los modelos para poder implementarlos en los sistemas desarrollados.
\section{Paradigmas de la inteligencia artificial} \index{Paradigmas de la inteligencia artificial}
De acuerdo a Palma y Marín \cite{marin2008inteligencia} existen 4 paradigmas principales:
\begin{enumerate}
\item Simbólico o representacional: El conocimiento se representa por medio de descripciones declarativas y en lenguaje natural, éstos son los hechos, otro conjunto de conocimientos son las reglas de inferencia que describen las relaciones sobre los hechos, al aplicar dichas reglas sobre un conjunto de conceptos de entrada se razona y se obtiene una inferencia.
Un ejemplo de este tipo de desarrollos son los sistemas expertos, este paradigma fue dominante desde 1956 a 1986.
\item Situado o reactivo: Toda conducta es resultado de una percepción, por lo cual éstas se tienen una conexión directa, condicionada o secuencial.
\item Conexionista: Describe que los problemas pueden ser resueltos por unidades pequeñas interconectadas entre sí. Las unidades pueden ser neuronas, genes, agentes inteligentes, etc. Este paradigma corresponde a las redes neuronales artificiales (RNA) se definen modelos con entradas y salidas en los cuales se ajustan parámetros de la red mediante diferentes algoritmos de aprendizaje. Dentro de este paradigma también entran los algoritmos evolutivos y sistemas multiagentes.
\item Híbrido: Para resolver diversos problemas existe la necesidad de integrar soluciones que corresponden a distintos paradigmas, por ello los sistemas híbridos son de gran utilidad para problemas reales.
\end{enumerate}
Una ventaja del paradigma simbólico es que es fácil interpretar lo que sucede dentro del sistema, en cambio en sistemas conexionistas suele ser complicado determinar las razones detrás de una decisión, sin embargo, actualmente se han desarrollado técnicas como Grad-CAM \cite{gradcam} que permiten reducir esta incertidumbre en el campo de clasificación de imágenes.
En la siguiente figura se muestran distintas categorías de técnicas de inteligencia artificial.
\begin{figure}[ht]
\centering\includegraphics[width=13cm]{ia/ai_taxonomy.png}
\caption{Clasificación de técnicas de inteligencia artificial}
\label{fig:ai_taxonomy}
\end{figure}
\part{Parte tres: Técnicas clásicas}
%----------------------------------------------------------------------------------------
% CHAPTER 3
%----------------------------------------------------------------------------------------
\chapterimage{chapter_head.pdf} % Chapter heading image
\chapter{Búsquedas inteligentes}
\section{Introducción al capítulo}\index{Introducción al capítulo}
Antes de empezar a hablar directamente sobre estos temas relacionados principalmente con los grafos quiero hacer mención de un fenómeno descrito por John McCarthy “As soon as it works, no one calls it AI any more”; ésta frase me parece particularmente interesante debido a que la delimitación de los temas que comprenden la inteligencia artificial como ciencia no están perfectamente definidos, habrá autores que consideren estos temas como una rama de las estructuras de datos y no como parte de esta ciencia.
En los inicios de la inteligencia artificial era sorprendente cuando una máquina lograba algo remotamente inteligente y el asombro llevaba a generar altas expectativas del alcance de esta ciencia. Hoy en día quizá no se vea como algo tan sorprendente pero debido a que algunos de estos algoritmos nacieron siendo parte de la inteligencia artificial he decidido dedicarle una pequeña sección.
En este capítulo no profundizaré en las diversas técnicas de búsquedas inteligentes, en cambio revisaremos un ejemplo fuertemente ligado a la historia de la inteligencia artificial; sin embargo a continuación proporcionaré un enlace a el libro inteligencia artificial: introducción y tareas de búsqueda de Roberto J. de la Fuente López. (\url{http://www.aconute.es/iartificial/documentos/ia_intro_busqueda.pdf }) para aquellos que deseen abordar de una manera más amplia el tema.
\section{¿Qué es una búsqueda inteligente?} \index{¿Qué es una búsqueda inteligente?}
Una búsqueda inteligente es aquel algoritmo que nos permita recorrer una estructura de datos de manera eficiente para obtener una solución potencialmente óptima.
\section{La IA que venció al campeón del mundo} \index{La IA que venció al campeón del mundo}
Son famosos los juegos entre Garry Kasparov y Deep blue, antes de ver el funcionamiento de esta computadora veremos un poco de la historia de estos encuentros.
Es poco mencionado el hecho de que Kasparov ganó la primera partida en 1996, se dieron seis juegos de los cuales 3 fueron ganados por Kasparov y uno por Deep Blue, los otros terminaron en empate. (Link de la victoria de Kasparov sobre Deep Blue: \url{http://hemeroteca.abc.es/nav/Navigate.exe/hemeroteca/madrid/abc/1996/02/19/084.html })
En la partida de 1997 Deep Blue derrotó a Kasparov, este último ganó un solo juego y Deep Blue ganó 2, los otros 3 quedaron en empate. Algo interesante es el hecho de que Kasparov acusó de hacer trampa a IBM \cite{hsu2004behind} después del segundo juego ya que mostraba signos de inteligencia o creatividad, IBM negó esto y dijo que solo se había dado intervención humana entre los juegos (lo cual estaba permitido en las reglas acordadas).
\section{¿Cómo funcionaba Deep Blue?} \index{¿Cómo funcionaba Deep Blue?}
El algoritmo detrás de Deep Blue no es tan inteligente como hace parecer, incluso uno de sus programadores (Joe Hoane) menciona en una entrevista que no es un proyecto de inteligencia artificial cuando se le preguntó cuánto de su trabajo era dedicado específicamente a la inteligencia artificial en emular el pensamiento humano \cite{DBFORBES}.
Las principales características de Deep Blue eran las siguientes
\cite{CAMPBELL200257}:
\begin{itemize}
\item Libro de jugadas iniciales: Esto le permitía a la computadora realizar buenos movimientos iniciales
\item Hardware especializado: Deep Blue contaba con chips especializados que permitían evaluar tableros de ajedrez con una gran rapidez, la función de evaluación contaba con más de 8000 características y cada chip tenía una velocidad de búsqueda de 2 a 2.5 posiciones por segundo.
\item Paralelización de búsqueda: Deep Blue era un sistema con alta paralelización contando con más de 500 procesadores disponibles para realizar el árbol de búsqueda.
\end{itemize}
El algoritmo de búsqueda que utilizó Deep Blue está basado en el algoritmo alpha-beta que se detallará más adelante en este capítulo.
Si se quiere profundizar a detalle en el funcionamiento del sistema de esta computadora recomiendo leer el siguiente articulo (\url{https://doi.org/10.1016/S0004-3702(01)00129-1}).
\section{El algoritmo Minimax} \index{El algoritmo Minimax}
El algoritmo de minimax nos permite elegir el mejor movimiento en un juego con adversario considerando que éste último siempre escogerá el peor movimiento para nosotros (el mejor para él).
En el juego existen dos jugadores:
\begin{enumerate}
\item Maximizador (MAX): trata de obtener la puntuación más alta.
\item Minimizador (MIN): trata de obtener la puntuación más baja.
\end{enumerate}
Algoritmo de minimax con movimientos alternativos:
\begin{enumerate}
\item Generación del árbol de juego. Se generarán todos los nodos hasta llegar a un estado terminal (o a alguna condición determinada).
\item Uso de función de evaluación sobre los nodos terminales.
\item Calcular el valor de los nodos superiores a partir del valor de los inferiores, dependiendo de si el nivel corresponde a MAX o MIN se escogerá el valor más alto o más bajo.
\item Elegir la jugada valorando los valores que han llegado al nivel superior.
Para ilustrar el funcionamiento de este algoritmo a continuación mostraré en imágenes los diferentes pasos con el ejemplo del juego de gato (Si X gana el estado vale 1, Si O pierde el estado vale -1, Si se empata el valor es 0):
\end{enumerate}
\begin{figure}[ht!]
\centering\includegraphics[width=9.5cm]{ia/generación_edos.png}
\caption{Generación de estados}
\label{fig:gen_edos_minimax}
\end{figure}
\begin{figure}[ht!]
\centering\includegraphics[width=11.5cm]{ia/evaluacion_edos_finales.png}
\caption{Evaluación de estados finales}
\label{fig:ev_edos_minimax}
\end{figure}
\begin{figure}[ht!]
\centering\includegraphics[width=11.5cm]{ia/propagación_edos.png}
\caption{Cálculo de los valores en los nodos superiores}
\label{fig:prop_edos_minimax}
\end{figure}
\begin{figure}[ht!]
\centering\includegraphics[width=13.5cm]{ia/eleccion_edo.png}
\caption{Elección de estado o jugada}
\label{fig:elec_edos_minimax}
\end{figure}
\clearpage
El algoritmo MINIMAX es un procedimiento recursivo, a continuación se presenta el pseudocódigo correspondiente, se recomienda al lector analizar como el siguiente pseudocódigo hace lo mismo que se describió con anterioridad.
\begin{algorithm}
\DontPrintSemicolon
\SetKwFunction{FMain}{MINIMAX}
\SetKwProg{Fn}{Función}{:}{}
\Fn{\FMain{nodo, turnoMax}}{
\eIf{esTerminal(nodo)}{
funciónEvaluación(nodo)\;
\KwRet nodo\;
}{
posiblesEstados = funciónSucesor(nodo)\;
\ForEach{estado \textbf{in} posiblesEstados}{
estado = MINIMAX(estado, not (turnoMax) )\;
}
\eIf{turnoMax}{
\KwRet max(posiblesEstados)\;
}{
\KwRet min(posiblesEstados)\;
}
}
}
\;
\caption{Algoritmo MINIMAX}
\end{algorithm}
Es importante notar que dependiendo del “juego” sobre el cuál se esté aplicando este algoritmo varía la función de evaluación y la función sucesor, encargada de generar los nuevos estados.
En el pseudocódigo descrito con anterioridad se generan todos los estados finales posibles, en el juego de gato esto no es un gran problema ya que el número de estados posibles es relativamente pequeño (alrededor de 362,800), sin embargo en otros juegos como el ajedrez este número es mucho más alto por lo cual se puede verificar a qué nivel de profundidad pertenece el nodo y si se ha llegado a ese límite establecido previamente evaluar el nodo aunque no sea un estado final, esto implica además el tener que generar funciones de evaluación más complejas ya que en ese punto no se puede saber con certeza si el jugador ganará o perderá.
Otra nota importante es que en este pseudocódigo es en los nodos donde se almacena el resultado de la evaluación, esto también podría hacerse implementando una tupla (nodo, valor) y devolviendo esta estructura en la función MINIMAX.
\begin{center}
\line(1,0){420}
\end{center}
\textbf{Ejercicio de programación:}
Yo recomiendo realizar el siguiente ejercicio para fortalecer los conocimientos adquiridos:
En cualquier lenguaje de programación programar una inteligencia artificial capaz de jugar gato utilizando el algoritmo Minimax. A continuación se presenta un enlace, se debe hacer una copia del notebook y seguir las instrucciones.
(Ejercicio para completar: \url{https://colab.research.google.com/drive/1xX4vcx6G0Dj_9XW5cml_lOnZnLIPb65T?usp=sharing})
(Ejemplo minimax web: \url{https://github.com/amr205/TicTacToe-AI---Minimax})
\includegraphics[width=5cm]{Pictures/github/minimax.png}
\clearpage
\section{El algoritmo Alpha-beta pruning} \index{El algoritmo Alpha-beta pruning}
El algoritmo Alpha-beta pruning tiene el objetivo de realizar la misma tarea que el algoritmo Minimax sin embargo poda las ramas que no necesitan ser revisadas, sigue regresando el mismo resultado que el algoritmo minimax pero reduce el nivel de nodos que visita.
En este caso incluiré primero el pseudocódigo y posteriormente procederé a explicar el funcionamiento de este algoritmo.
\begin{algorithm}
\DontPrintSemicolon
\SetKwFunction{FMain}{AlphaBeta}
\SetKwProg{Fn}{Función}{:}{}
\Fn{\FMain{nodo, turnoMax, alpha, beta}}{
\eIf{esTerminal(nodo)}{
funciónEvaluación(nodo)\;
\KwRet nodo\;
}{
posiblesEstados = funciónSucesor(nodo)\;
\eIf{turnoMax}{
nodoMayor = nuevo Nodo\;
nodoMayor.valor = - infinito\;
\ForEach{estado \textbf{in} posiblesEstados}{
estado = AlphaBeta(estado, not(turnoMax), alpha, beta)\;
alpha = max(alpha, estado.valor)\;
nodoMayor = max(nodoMayor, estado)\;
\If{beta <= alpha}{
break
}
}
\KwRet nodoMayor\;
}{
nodoMenor = nuevo Nodo\;
nodoMenor.valor = infinito\;
\ForEach{estado \textbf{in} posiblesEstados}{
estado = AlphaBeta(estado, not(turnoMax), alpha, beta)\;
beta = min(beta, estado.valor)\;
nodoMenor = min(nodoMenor, estado)\;
\If{beta <= alpha}{
break
}
}
\KwRet nodoMenor\;
}
}
}
\;
\caption{Algoritmo Alpha-Beta Pruning}
\end{algorithm}
Se puede observar que el funcionamiento es muy similar al algoritmo Minimax pero se utilizan dos variables, alpha y beta. Se puede observar que alpha guardaría el mejor estado posible que el maximizador tiene, y beta el mejor estado posible para el minimizador, por la manera en la que se visitan los nodos cuando beta es menor o igual no tiene mucho sentido continuar revisando la rama ya que el jugador contrario ya tiene una mejor opción en un nivel superior.
Un ejemplo de cómo funciona puede ser muy útil para entender el funcionamiento de este algoritmo, en lo personal considero que el siguiente video de Sebastian Lague muestra un ejemplo muy completo y descrito paso por paso (\url{https://youtu.be/l-hh51ncgDI?t=546}).
\begin{center}
\line(1,0){420}
\end{center}
\textbf{Ejercicio de programación:}
Yo recomiendo realizar el siguiente ejercicio para fortalecer los conocimientos adquiridos:
En cualquier lenguaje de programación programar una inteligencia artificial capaz de jugar ajedrez utilizando el algoritmo Alpha-beta pruning.
(Ejemplo: \url{https://github.com/amr205/Chess-AI-using-Alpha-Beta-pruning})
\includegraphics[width=5cm]{Pictures/github/alphabeta.png}
\chapterimage{chapter_head.pdf} % Chapter heading image
\chapter{Algoritmos evolutivos}
\section{Introducción al capítulo}\index{Introducción al capítulo}
Estos algoritmos inspirados en la evolución natural son útiles debido a que nos permiten tratar problemas que con técnicas de búsqueda no informada requerirían de un tiempo de proceso demasiado grande y con técnicas de búsqueda informada corren el riesgo de llegar a un óptimo local.
Una ventaja de los algoritmos evolutivos es que se requiere solo una pequeña cantidad de conocimiento específico sobre el problema que se está tratando, en concreto la función de evaluación (Fitness function) que debe ser optimizada en el proceso \cite{streichert2002introduction}, más adelante en este capítulo serán más evidentes las razones que llevan a esta afirmación.
\section{Orígenes} \index{Orígenes}
Desde la década de los 50s los científicos han estudiado este tipo de algoritmos, en 1954 Nils Barricelli creó el primer algoritmo genético que imitaba la reproducción y mutación natural, su objetivo no era resolver problemas de optimización, sino crear vida artificial. Durante los siguientes años científicos como Alexander Fraser usaron su trabajo, Fraser quería simular la evolución debido a que observarla de manera directa en nuestro mundo requeriría de millones de años.
John Holland es considerado una de las personas más importantes en el campo de los algoritmos genéticos, ya que él introdujo el uso de una población para evaluarla y posteriormente usar procesos como el crossover, recombination, etc. En 1975 publicó su libro que sería la base teórica de muchos trabajos posteriores.
En 1988 John Koza, patentó su idea de usar algoritmos evolutivos para la generación de programas, continuó su trabajo con múltiples publicaciones relacionadas con la programación genética, por lo cual su trabajo es de mucha importancia en esta área de los algoritmos evolutivos.
En 1986 Holland sentó las bases de los sistemas clasificadores (LCS), estos algoritmos tenían el objetivo de solucionar la tarea de clasificación y utilizan elementos de aprendizaje y algoritmos genéticos, Stewart Wilson continuó el desarrollo de nuevos sistemas clasificadores como el “Zeroth-level” usando métodos más modernos de aprendizaje reforzado.
\section{Definición} \index{Definición}
Los algoritmos evolutivos tienen su base en la selección natural, una definición que yo considero apropiada es la siguiente: Los algoritmos evolutivos mediante la heurística son capaces de resolver tareas de optimización imitando aspectos de la evolución natural, suelen trabajar en poblaciones completas de posibles soluciones para una determinada tarea (Streichert, 2002).
\textbf{NOTA: Diferencia entre un algoritmo evolutivo y un algoritmo genético}
Un algoritmo genético es una subclase de los algoritmos evolutivos.
Todo algoritmo evolutivo está basado en las leyes de la evolución natural, un algoritmo genético tiene sus bases en el uso de poblaciones, cruzamiento o recombinación (crossover) y mutación. En cambio otros tipos de algoritmos evolutivos se basan principalmente en la mutación.
\section{Clasificación} \index{Clasificación}
Existen distintos tipos de algoritmos evolutivos, en este capítulo se revisarán aquellos más populares, sin embargo también hay sistemas y algoritmos que presentan un comportamiento híbrido, estos algoritmos no serán cubiertos hasta que se hayan visto los temas necesarios para poder abordarlos de manera completa, un ejemplo de esto último es el algoritmo NEAT (NeuroEvolution of Augmenting Topologies) que combina los algoritmos genéticos con el paradigma conexionista.
A continuación se presentan los tipos de algoritmos evolutivos más comunes:
\begin{figure}[ht]
\centering\includegraphics[width=14cm]{ia/AE clasificación.png}
\caption{Clasificación de los algoritmos evolutivos más comunes}
\label{fig:classification-ae}
\end{figure}
\section{Algoritmos genéticos} \index{Algoritmos genéticos} \label{section:Algoritmos-geneticos}
Los componentes principales de los algoritmos genéticos son los siguientes:
\begin{itemize}
\item Una función de evaluación a optimizar (fitness function)
\item Una población de cromosomas
\item Un operador de selección
\item Un operador de cruzamiento
\item Un operador de mutación
\end{itemize}
Antes de describir éstas partes, veamos el funcionamiento básico del algoritmo.
\begin{enumerate}
\item Se genera una población inicial
\item Se evalúa la población (si algún elemento supera algún nivel barrera se da por terminado el algoritmo)
\item Se seleccionan los mejores individuos de la población y se guardan en un grupo(en inglés a este grupo se le llama mating pool)
\item Se seleccionan pares del grupo generado y se aplica el operador de cruzamiento, también se aplica el operador de mutación de acuerdo a una tasa de mutación determinada por el desarrollador, al terminar la generación de la población se vuelve al paso 2.
\end{enumerate}
\begin{figure}[ht]
\centering\includegraphics[width=5.5cm]{ia/GA.png}
\caption{Diagrama de flujo de un algoritmo genético}
\label{fig:df-ga}
\end{figure}
A continuación se presenta un pseudocódigo de la implementación de un algoritmo genético simple, se recomienda leerlo y regresar a esta figura cuando se realice el ejercicio de programación propuesto.
\begin{figure}[ht]
\centering\includegraphics[width=13cm]{ia/pse-ga.png}
\caption{Pseudocódigo del Algoritmo Genético Simple, Figura tomada de Algoritmos Genéticos. 3 de Febrero 2020, de Universidad del País Vasco Sitio web: http://www.sc.ehu.es/ccwbayes/docencia/mmcc/docs/temageneticos.pdf}
\label{fig:pse-ga}
\end{figure}
\subsection{Población}\index{Población}
Estos algoritmos trabajan sobre una población de cromosomas, el término cromosoma hace referencia a un valor o conjunto de valores que representan a una posible solución o individuo. A cada uno de estos valores dentro del cromosoma se les llama gen.
\begin{figure}[ht]
\centering\includegraphics[width=13cm]{ia/GA población, cromosoma, gen.png}
\caption{Población, cromosoma y gen}
\label{fig:pob-crom-gen}
\end{figure}
chromosome = [p1,p2,...,pNpar]
\textbf{NOTA: Diferencia entre genotipo y fenotipo}
Al momento de hablar sobre la representación de los individuos de la población se suelen utilizar los términos genotipo y fenotipo, estos términos fueron creados por Wilhelm Johannsen en 1911, el genotipo es la información hereditaria completa de un organismo y el fenotipo son las propiedades observadas. En el campo de los algoritmos genéticos, el genotipo es una representación de bajo nivel (con menos abstracción) que el fenotipo.
\begin{figure}[ht]
\centering\includegraphics[width=13cm]{ia/ga - genotipo vs fenotipo.png}
\caption{Diferencia entre genotipo y fenotipo}
\label{fig:dif-gen-fen}
\end{figure}
Es importante hacer notar que los genes no tienen que ser de tipo binario; un carácter o un elemento de alguna estructura (como un árbol) puede ser un gen por sí mismo.
Generalmente la población inicial es creada con valores al azar, un parámetro importante que el desarrollador debe determinar es el tamaño de la población ya que si el número es muy reducido no se tendrá suficiente variación y es posible que los individuos nunca sobrepasen un óptimo local, también se debe evitar poblaciones muy grandes para evitar la redundancia y para reducir el tiempo necesario para llegar a una solución adecuada.
\subsection{Evaluación}\index{Evaluación}
Para realizar la evaluación de los individuos se requiere tener conocimiento detallado sobre el problema que se está abordando, en algunas ocasiones se requiere realizar una simulación para encontrar el valor de aptitud (Fitness value), es común mantener el máximo valor en 1 y el menor en 0, para favorecer a los individuos con mejor aptitud se puede elevar a alguna potencia.
No siempre se trata de satisfacer un solo objetivo por lo cual a veces se tendrán distintas funciones enfocadas a evaluar los diferentes objetivos y estos deberán ser integrados en un solo valor.
Otra situación importante son los problemas con restricciones, para esto voy a proponer un ejemplo. Si quisiéramos diseñar un algoritmo genético capaz de resolver un sudoku, es probable que definiéramos el problema de la siguiente manera:
\begin{figure}[ht]
\centering\includegraphics[width=11cm]{ia/sudoku ga - genotipo vs fenotipo.png}
\caption{Genotipo y fenotipo en un problema de resolución de sudoku}
\label{fig:sudoku-gen-fen}
\end{figure}
Como se puede observar en la imagen anterior cada gen es un número del 1 al 9 que representa el valor que tendría en la casilla de la cuadrícula. Sin embargo se presentan ciertas restricciones:
\begin{enumerate}
\item No se pueden repetir números en un mismo renglón.
\item No se pueden repetir números en una misma columna.
\item No se pueden repetir números dentro de la misma subcuadrícula.
\item Se deben respetar los valores asignados a las casillas dados al momento
de plantear el problema.
\end{enumerate}
Para solucionar problemas con restricciones se pueden tomar diferentes medidas, las más comunes son reparación y penalización, la reparación evita que las restricciones sean violadas y la penalización disminuye el valor de aptitud de un individuo, más adelante se revisará la medida de reparación; en este subtema de evaluación se describe el proceso de penalización.
En este problema específico se podría tener una función como la siguiente:
$F(I) = \frac{(243-x-y-z)}{243}$
Siendo x el número de casillas repetidas en los renglones, y el número de casillas repetidas en las columnas y z el número de casillas repetidas en las subcuadrículas. En este problema la función depende altamente de las restricciones, pero supongamos que hacemos un algoritmo genético cuya función sea conducir en el menor tiempo posible con la restricción de no chocar ningún obstáculo, entonces podríamos definir una función que considerará el tiempo pero disminuyera la aptitud según el número de obstáculos golpeados.
$F(I) = \frac{(300-T-40*O)}{100}$
Siendo T el tiempo que se tardó el individuo en recorrer la pista y O el número de obstáculos golpeados.
\subsection{Selección}\index{Selección}\label{selection:pse-ga}
El proceso para la generación de una nueva población involucra el seleccionar padres para realizar el cruzamiento y la mutación, existen diversos métodos utilizados para realizar la selección de los padres, en este libro se explorarán las siguientes opciones \cite{SELECTION}:
\begin{enumerate}
\item Selección por ruleta (Roulette Wheel Selection)
\item Muestreo universal estocástico (Stochastic Universal Sampling)
\item Selección por rango lineal (Linear Rank Selection)
\item Selección por rango exponencial(Exponential Rank Selection)
\item Selección por torneo (Tournament Selection)
\item Selección por truncamiento (Truncation Selection)
\end{enumerate}
\underline{Selección por ruleta}
En este método la probabilidad de un individuo para ser elegido como padre es directamente proporcional a su valor de aptitud.
$p(i)=\frac{f(i)}{\sum_{j=1}^{n} f(j)}$
Donde n es el tamaño de la población y f(i) es la aptitud del individuo i
Una manera de implementar este método es el siguiente:
\begin{itemize}
\item Calcular el valor de $S$ ($S = \sum_{j=1}^{n} f(j)$)
\item Inicializar en 0 las variables: $p_{acumulada}$ y $j$
\item Generar un número al azar $\alpha$ entre los valores 0 y $S$
\item Mientras $p_{acumulada}<\alpha$ y $j<n$:
\begin{itemize}
\item $p_{acumulada} = p_{acumulada} + f(j)$
\item $j = j+1$
\end{itemize}
\item Fin del ciclo
\item Seleccionar individuo j
\end{itemize}
Una desventaja de este método es el riesgo que existe donde el algoritmo genético termina de manera prematura en un óptimo local, esto debido a la presencia de un individuo con una aptitud considerablemente superior a la del resto de la población.
\underline{Muestreo universal estocástico}
Este método, desarrollado por Baker en 1987, es una variación del anterior y pretende eliminar el riesgo de convergencia prematura en un óptimo local.
Consiste en generar un número aleatorio $\alpha$ entre 0 y P (siendo P el promedio de la aptitud de los individuos) y posteriormente elegir a n individuos espaciados de manera uniforme (el valor de espaciado $\beta$ suele ser el promedio de la aptitud pero no es una regla).
\begin{figure}[ht]
\centering\includegraphics[width=13cm]{ia/GA SUS.png}
\caption{Elección de 5 individuos mediante muestreo universal estocástico}
\label{fig:ga-sel-mue}
\end{figure}
\clearpage
Existen diferentes implementaciones de este algoritmo, yo recomiendo utilizar el siguiente proceso para seleccionar m individuos.
\begin{itemize}
\item Calcular el valor de $P$ ($P = \frac{1}{n} \sum_{i=1}^{n} f(i)$)
\item Inicializar en 0 las variables: $p_{acumulada}$, $j$ y $s$
\item Generar un número al azar $\alpha$ entre los valores 0 y $P$
\item Mientras $s<m$ y $j<n$:
\begin{itemize}
\item $p_{acumulada} = p_{acumulada} + f(j)$
\item $j = j+1$
\item Si $p_{acumulada} < \alpha+s*\beta$
\begin{itemize}
\item Añadir elemento $j$ al conjunto $C$
\item $s = s+1$
\end{itemize}
\end{itemize}
\item Fin del ciclo
\item Devolver conjunto $C$
\end{itemize}
\underline{Selección por rango lineal}
Este método pretende evitar la convergencia del algoritmo genético en un óptimo local, es importante hacer notar que una desventaja es que disminuye la diferencia que hay entre los mejores y peores individuos por lo que puede aumentar el tiempo de convergencia, además de aumentar el tiempo de proceso necesario durante la generación de los rangos.
De manera intuitiva se puede decir que se le da un rango de 1 al peor individuo y al mejor un rango n, siendo n el tamaño de la población.
\begin{figure}[ht]
\centering\includegraphics[width=14cm]{ia/seleclineal.png}
\caption{Ejemplo del cambio de probabilidad mediante el uso de selección por rango lineal (Derecha)}
\label{fig:ga-sel-lineal}
\end{figure}
La fórmula que se usa para determinar la nueva aptitud en este método es de tipo lineal, un ejemplo sería el siguiente:
$f(pos) = \alpha + \frac{pos}{n}$
Mientras mayor sea el valor de $\alpha$ menor será la diferencia entre las probabilidades de los individuos, en la Figura \ref{fig:ga-sel-lineal} se usó 0 como valor de $\alpha$.
Otra fórmula que suele utilizarse es la siguiente:
$f(pos)=2-SP+\left ( 2*(SP-1)*\frac{pos-1}{n-1} \right )$
SP corresponde al término en inglés Selective Pressure (presión selectiva) y $2 \geq SP \geq 1$. A mayor presión selectiva más probabilidad de ser elegidos tienen los mejores individuos.
Para implementar este método se sugieren los siguientes pasos:
\begin{enumerate}
\item Ordenar los individuos de acuerdo a su aptitud
\item Calcular la nueva aptitud de acuerdo a una fórmula lineal
\item Implementar selección por ruleta
\end{enumerate}
\underline{Selección por rango exponencial}
Este método pretende aumentar la presión selectiva, se proponen diversas fórmulas, en este libro se sugiere la siguiente:
$f(pos)=exp(\frac{pos}{c})$
$c= \frac{n*2*(n-1)}{6*(n-1)+n} $
Existen distintos tipos de fórmulas que se pueden aplicar, es importante tratar de evitar fórmulas muy complejas que impacten altamente el tiempo de procesamiento, en la siguiente figura se observa una comparación que utiliza la fórmula propuesta aquí con anterioridad.
\begin{figure}[ht]
\centering\includegraphics[width=14.5cm]{ia/sel-exp.png}
\caption{Comparación de probabilidad de selección entre tres métodos distintos}
\label{fig:comp_metodos}
\end{figure}
Para implementar este método se sugieren los siguientes pasos:
\begin{enumerate}
\item Ordenar los individuos de acuerdo a su aptitud
\item Calcular la nueva aptitud de acuerdo a una fórmula exponencial
\item Implementar selección por ruleta
\end{enumerate}
\underline{Selección por torneo}
Este método consiste en obtener $k$ individuos y posteriormente seleccionar el individuo con mayor aptitud, este proceso se repite $n$ veces para obtener todos los padres.
La forma más fácil de implementar esta técnica es con $k=2$ se generan dos números aleatorios $\alpha$ y $\beta$ de 0 al tamaño de la población y se selecciona el elemento $\alpha$ o $\beta$ con mayor aptitud.
\underline{Selección por truncamiento}
Este método es bastante simple y no es muy utilizado en la práctica, su mayor caso de aplicación es en poblaciones de gran tamaño.
Consiste en ordenar los individuos de acuerdo a su aptitud y seleccionar una porción de los mismos para realizar la reproducción o cruzamiento entre ellos.
En el siguiente estudio Khalid Jeba \cite{SELECTION} analiza los métodos aquí descritos para estudiar el número de generaciones necesarias para llegar a la convergencia, así como el óptimo obtenido, también se propone un nuevo método que busca obtener un mejor óptimo sin sacrificar mucho tiempo para llegar a la convergencia. (\url{https://www.researchgate.net/publication/259009318_Parent_Selection_Operators_for_Genetic_Algorithms})
Otros métodos que me gustaría mencionar es la selección uniforme determinista que selecciona todos los elementos de la población para el cruzamiento, y la selección uniforme estocástica que selecciona elementos al azar de la población.
\subsection{Cruzamiento}\index{Cruzamiento}
Los operadores de cruce nos ayudan a generar la siguiente población a evaluar, consisten en generar 1 o más hijos a partir de dos individuos padre, el uso de algoritmos de cruzamiento lleva a un mejor desempeño en comparación a solo utilizar mutación, esto es más evidente cuando se tienen poblaciones grandes \cite{CROSSOVER_Spears}. Existen diversas maneras de realizar el cruzamiento, en este libro solo se revisarán algunos de los más comunes, más específicamente se revisarán los siguientes \cite{CROSSOVER_REVIEW}: Cruce de 1 punto, Cruce de k puntos, Cruce uniforme y Cruce por promedio.
\underline{Cruce de 1 punto}
Este es uno de los operadores de cruce más simples, dados dos individuos padres se elige un punto de cruce pi al azar, posteriormente se crean dos descendientes combinando los dos padres por el punto de cruce.
\begin{figure}[ht]
\centering\includegraphics[width=15.5cm]{ia/GEC-1 punto.png}
\caption{Ejemplo de cruce de 1 punto, en este caso el punto de cruce se encuentra entre el sexto y el séptimo gen}
\label{fig:gec-1-punto}
\end{figure}
\underline{Cruzamiento de k puntos}
Este operador es muy similar al anterior, la diferencia consiste en el número de puntos de cruce, se eligen k puntos de cruce para generar los descendientes.
\begin{figure}[ht]
\centering\includegraphics[width=15.5cm]{ia/GEC-k puntos.png}
\caption{Ejemplo de cruce de k-puntos, en este caso se usan 3 puntos de cruce}
\label{fig:gec-k-punto}
\end{figure}
\underline{Cruce uniforme}
Este método consiste en combinar los genes de ambos padres, para cada gen se genera un número aleatorio que determina si el primer descendiente tomará el valor del gen del primer padre o del segundo.
El pseudocódigo es similar al siguiente, dados dos padres a, b y dos descendientes x, y:
\begin{itemize}
\item Para cada gen
\begin{itemize}
\item Sea h un número aleatorio entre 0 y 1
\item Si h > 0.5
\begin{itemize}
\item El valor del gen para x es igual al valor del gen en a
\item El valor del gen para y es igual al valor del gen en b
\end{itemize}
\item Sino
\begin{itemize}
\item El valor del gen para x es igual al valor del gen en b
\item El valor del gen para y es igual al valor del gen en a
\end{itemize}
\end{itemize}
\end{itemize}
\underline{Cruce por promedio}
Este operador se utiliza cuando se tienen genes de tipo entero o real, dados dos padres se genera un solo descendiente, el valor de cada gen es el promedio del valor de los genes de los padres.
\begin{figure}[ht]
\centering\includegraphics[width=14cm]{ia/GEC-promedio.png}
\caption{Ejemplo del uso del cruce por promedio}
\label{fig:GEC-promedio}
\end{figure}
En el siguiente enlace pueden encontrar más técnicas de cruzamiento, algunas técnicas como el cruzamiento promediado se ajustan muy bien a cierto tipo de problemas por lo cuál puede valer la pena leer el siguiente artículo para observar si existe algún algoritmo de cruzamiento que se adapte a nuestro problema
(\url{http://ictactjournals.in/paper/IJSC_V6_I1_paper_4_pp_1083_1092.pdf}).
\subsection{Mutación} \index{Mutación}
La mutación permite que la población mantenga diversidad y mediante la generación de nuevos individuos no presentes en la población actual evita que el algoritmo converja en un valor prematuro.
Este operador se aplica sobre un cromosoma, dada una tasa de mutación (En inglés mutation rate) $p_{m}$ se genera un número aleatorio y si el número es menor a $p_{m}$ se realiza una o más modificaciones en los genes del individuo. En los algoritmos genéticos tradicionales (también llamados canónicos) el valor de $p_{m}$ es fijo, y solo se aplica un operador, sin embargo existen investigaciones que demuestran que es posible utilizar varios operadores con una tasa de mutación dinámica para cada operador, esto permite descubrir cuáles operadores son más útiles sin tener que realizar múltiples pruebas \cite{DYNAMIC_MUTATION}
\clearpage
\underline{Bit Flip Mutation}
Este operador se aplica para genes con valor binario, se selecciona uno o más genes y se invierte su valor.
\begin{figure}[ht]
\centering\includegraphics[width=15cm]{ia/Mutation-bitflip.png}
\caption{Aplicación del operador de mutación “Bit Flip”}
\label{fig:Mutation-bitflip}
\end{figure}
\underline{Random Resetting}
Se selecciona uno o más genes y se le asigna al azar uno de los valores permitidos para el gen.
\begin{figure}[ht]
\centering\includegraphics[width=15cm]{ia/Mutation-RANDOM RESET.png}
\caption{Aplicación del operador de mutación “Random Resetting”}
\label{fig:Mutation-RANDOMRESET}
\end{figure}
\underline{Swap Mutation}
Consiste en seleccionar uno o más pares de genes e intercambiar su valor.
\begin{figure}[ht]
\centering\includegraphics[width=15cm]{ia/Mutation-SWAP.png}
\caption{Aplicación del operador de mutación “Swap mutation”}
\label{fig:Mutation-SWAP}
\end{figure}
\underline{Scramble Mutation}
Consiste en subconjunto de genes y ordenarlos de manera aleatoria para insertarlos nuevamente.
\begin{figure}[ht!]
\centering\includegraphics[width=15cm]{ia/Mutation-SCRABBLE.png}
\caption{Aplicación del operador de mutación “Scramble mutation”}
\label{fig:Mutation-SCRABBLE}
\end{figure}
\underline{Inverse Mutation}
Consiste en subconjunto de genes e invertir su orden para insertarlos nuevamente.
\begin{figure}[ht!]
\centering\includegraphics[width=15cm]{ia/Mutation-Inverse.png}
\caption{Aplicación del operador de mutación “Inverse mutation”}
\label{fig:Mutation-Inverse}
\end{figure}
\subsection{Resolver problemas con restricciones} \index{Resolver problemas con restricciones}
Anteriormente en la sección correspondiente a la evaluación en los algoritmos genéticos se exploró el problema del sudoku como una situación donde existen restricciones, las tres maneras más comunes de implementar algoritmos con este tipo de problemas son las siguientes:
\begin{enumerate}
\item Uso de Funciones de penalización que reducen severamente el valor de aptitud de los individuos que no satisfacen las restricciones.
\item Uso de Funciones de reparación que toman una solución y la modifican para que cumpla con todas las restricciones.
\item No permitir que se genere ningún individuo que no cumpla con las restricciones.
\end{enumerate}
\subsection{Elitismo en algoritmos genéticos} \index{Elitismo en algoritmos genéticos}
El elitismo en los algoritmos genéticos consiste en asegurar que un porcentaje de los mejores individuos pasen a la siguiente generación de la población, se recomienda mantener este porcentaje por debajo del 10\% para asegurar la diversidad de la población. Usualmente estos individuos pasan a la siguiente generación sin ninguna mutación, posteriormente se realiza el proceso de crossover y mutación de manera habitual para completar la nueva población.
\textbf{¿Porqué utilizar elitismo?}
Usar elitismo puede tener un alto impacto en el rendimiento de nuestro algoritmo (Aumentando la velocidad de convergencia) \cite{rani2019effectiveness} debido a que no se tienen que re-descubrir soluciones que ya han probado tener una alta aptitud. De esta manera se asegura también que la aptitud del mejor individuo nunca va a reducirse a través del paso de las generaciones de la población.
\textbf{¿Porqué NO utilizar elitismo?}
Usar elitismo puede hacer al algoritmo converger en un óptimo local de manera prematura, esto depende también del porcentaje de la población que se use para aplicar el elitismo, mientras mayor sea el porcentaje mayor riesgo se corre de limitar el espacio de búsqueda de nuestro algoritmo.
\textbf{Implementación}
La manera más simple de implementar elitismo es ordenando los elementos de la población de acuerdo a su aptitud para posteriormente copiar el porcentaje de cromosomas determinados con anterioridad por el desarrollador, es importante no sobrescribir los valores de estos elementos por lo que solo se deben generar la cantidad de individuos restantes de la población.
\subsection{Aplicaciones de los algoritmos genéticos} \index{Aplicaciones de los algoritmos genéticos}
Los algoritmos genéticos resultan extremadamente para resolver problemas de parametrización, en problemas con múltiples óptimos locales las soluciones basadas en gradientes no suelen resolver el problema por lo cual los algoritmos genéticos son una buena alternativa.
\begin{itemize}
\item Machine learning: Se pueden utilizar los algoritmos genéticos para crear sistemas que aprendan reglas de producción o sistemas clasificadores (Wang, Bayer)
\item Multimodal optimization: Los algoritmos genéticos nos pueden ayudar a encontrar múltiples soluciones en contraste a solo una.
\item Problemas de ingeniería: Si se posee el conocimiento suficiente para crear una buena función de evaluación se pueden resolver problemas de diversas áreas de la ingeniería.
\end{itemize}
\subsection{Construcción de un algoritmo genético} \index{Construcción de un algoritmo genético}
A continuación se presenta una tabla que resume los puntos que el desarrollador debe determinar o tomar en cuenta cuando construye un algoritmo genético.
\begin{table}[ht!]
\centering
\caption{Parámetros y consideraciones en la construcción de un algoritmo genético}
\begin{tabular}{|p{5cm}|p{9cm}|}
\hline
Parámetros de la población & Tamaño de la población\\
\hline
Representación de la población & Método de selección y parámetros del método seleccionado. Ej. Si se selecciona Selección por rango lineal se debe determinar el valor de Selective Pressure \\
\hline
Cruzamiento & Método de cruzamiento\\
\hline
Mutación & Implementación de la mutación sobre nuestra población y tasa de mutación\\
\hline
Elitismo & Determinar si se usará o no y el porcentaje de la población que pasaría a la siguiente generación mediante elitismo.\\
\hline
Terminación & Determinar la condición de finalización\\
\hline
\end{tabular}
\end{table}
\FloatBarrier
\begin{center}
\line(1,0){420}
\end{center}
\textbf{Ejercicio de programación:}
Ejercicio para fortalecer los conocimientos adquiridos:
En cualquier lenguaje de programación hacer un programa capaz de realizar alguna de las siguientes tareas:
\begin{itemize}
\item Resolver un tablero de sudoku con algunas celdas llenadas previamente.
\item Resolver el problema del viajero.
(\url{https://es.wikipedia.org/wiki/Problema_del_viajante})
\item Adaptar la posición y rotación de líneas en un espacio tridimensional para representar una imagen. (\url{https://youtu.be/iV-hah6xs2A})
\end{itemize}
A continuación se presenta un repositorio donde aplicó un algoritmo genético para solucionar tableros de sudoku:
\includegraphics[width=5cm]{Pictures/github/genetic.png}
\url{https://github.com/amr205/SudokuSolver---Genethic-Algorithm}
\section{Programación genética} \index{Programación genética}
En este libro se revisarán las bases de la programación genética para culminar con un proyecto que demuestre que se entienden estos conceptos y se poseen las habilidades de programación necesarias para poner en práctica lo aprendido. Si tú como lector quieres explorar más a profundidad este tema recomiendo leer el siguiente libro:
(\url{http://www.lulu.com/shop/riccardo-poli-and-william-b-langdon-and-nicholas-freitag-mcphee/a-field-guide-to-genetic-programming/ebook/product-17447670.html}).
\clearpage
\textbf{¿Qué es la programación genética?}
La programación genética es un tipo de algoritmo evolutivo en el cual se determina “que debe hacerse” y se generan programas computacionales para resolver dicho problema.
El funcionamiento general de la programación genética es muy similar a los algoritmos genéticos ya que también tiene su base en la selección natural de la teoría de la evolución de Darwin. De hecho son tan similares que la Figura \ref{fig:df-ga} presentada para los algoritmos genéticos describe igualmente el flujo de un programa que implementa programación genética.
\textbf{Diferencia entre un algoritmos genéticos y la programación genética}
La respuesta más simple a esta pregunta son los individuos de la población, en la programación genética cada individuo es un programa computacional.