PROBLEMA

UN PROBLEMA EN REALIDAD ES UN CONJUNTO DE INFORMACIÓN QUE EL AGENTE UTILIZA PARA DECIDIR LO QUE VA A HACER.

PROBLEMA DE UN SOLO ESTADO

Supóngase que los sensores de un agente le proporcionen información suficiente como para determinar con exactitud el estado en el que se encuentre (es decir el mundo es accesible); supóngase que se conoce con exactitud el resultado producido por cada una de sus acciones                                                                                                                              

Ejemplo. Si su estado inicial es 5 será capaz de calcular que la secuencia de acciones le permitirá a alcanzar el estado meta. El anterior es el caso más sencillo, al que se denomina problemas de estado

Supóngase que el agente sabe cuál es el resultado de cada una de las acciones pero que su acceso al estado del mundo es limitado. En este caso solo se sabe que su estado inicial es uno de los del conjunto {1, 2, 3, 4, 5, 6, 7,8}. Aunque pudiera parecer que el agente no tiene ayuda en realidad puede arreglársela bastante bien. Gracias a que sabe cuál es el efecto de sus acciones puede, por ejemplo calcular que la acción de la derecha de la derecha le conducirá a uno de sus estados {2, 4, 6,8}. De hecho el agente pueda descubrir que la secuencia de acciones [Derecha, Aspirar, Izquierda, Aspirar] le garantiza alcanzar un estado meta, independientemente de cual sea el estado inicial.

PROBLEMA DE ESTADO MÚLTIPLE

Si el mundo no es totalmente accesible, el agente deberá razonar en términos de los conjuntos de estados a los que puede llegar, en vez de pensar en función de estados únicos. A lo anterior se acostumbra denominar problema de estado múltiple

Aunque pudiera parecer diferente, el caso de cuando se ignoran los efectos de las acciones puede ser manejado de manera similar. Por ejemplo, que el ambiente al parecer no es determinista puesto que sigue la Ley de Murphy: la acción denominada Aspirar, a veces deja mugre en la alfombra, pero solamente si en esta no había mugre anteriormente. Por ejemplo, si el agente sabe que está en estado 4, sabrá que si aspira llegar a uno de los estados {2, 4}. A cada estado inicial conocido le corresponde una secuencia de acciones que garantiza el logro de un estado meta

Si el agente está en un mundo de la Ley de Murphy, cuenta con un sensor de ubicación y un sensor local para la mugre, pero no tiene un sensor que le permita detectar mugre en otros cuadrantes. Además los sensores le dicen que está en uno de los estados {1, 3}. El agente podría formular la secuencia de acciones [Aspirar, Derecha, Aspirar]. El aspirar modificaría el estado al de {5, 7} y el desplazarse a ala derecha modificaría el estado a uno de {6, 8}. Si en realidad está en el estado 6, la secuencia de acciones tendrá éxito, pero si se trata del estado 8, el plan fracasara.  Si el agente podría hacer la secuencia de acción sencilla Aspirar tendría éxito a veces, pero no siempre. Resulta que no hay una secuencia fija de acciones que garantice la solución de este problema.

PROBLEMA DE CONTINGENCIA

El agente si tiene una forma de resolver el problema empezando del {1,3}: primero aspirar, luego desplazarse a la derecha, luego aspirar solo si allí está sucio es decir para utilizar este problema es necesario utilizar el sensor durante la fase de ejecución, nótese que ahora el agente debe calcular todo un árbol de acciones, en vez de una sola secuencia de ellas, Por lo general cada una de las ramas del árbol se refiere a una posible contingencia que pudiera surgir. Al anterior se le denomina problema de contingencia. Muchos de los problemas del mundo real, físico, son problemas de contingencia puesto que es imposible hacer predicciones exactas. Esta es la razón por la que la mayoría de las personas presten bastante atención cuando van caminando o al conducir. En los problemas de contingencia, es necesario emplear algoritmos más complejos. En vez de considerar por anticipado toda posible contingencia que pueda surgir durante la ejecución, muchas veces es mejor proceder a la ejecución y ver contingencias van surgiendo. Con base a la información adicional, el agente puede seguir resolviendo el problema.

PROBLEMAS DE EXPLORACIÓN

Considérese el predicamento de un agente que no cuenta con información sobre los efectos de las acciones. El agente tendrá que experimentar, descubrir poco a poco que tipo de búsqueda, pero en el mundo real, no en un modelo. Ejecutar un proceso en el mundo real, en vez de hacerlo en un modelo, entraña grandes peligros para un agente ignorante. Si logra sobrevivir, el agente aprenderá un “mapa” del ambiente, mapa que pude utilizar para resolver otros problemas que se le presenten.

EL MODELO DE UN AGENTE INTELIGENTE

Como debe proceder un agente: 

EL PROCESO DE RAZONAMIENTO SEGÚN LA LÓGICA

EL RAZONAMIENTO SE COMPONE DE DIVERSOS COMPONENTES:

“Leyes de la lógica de predicados o proposiciones”

Una lógica también debe definir la semántica del lenguaje. Si lo relacionamos con el lenguaje hablado, la semántica trata el «significado» de las sentencias. En lógica. Esta VALOR DE VERDAD definición es bastante más precisa. La semántica del lenguaje define el valor de verdad MUNDO POSIBLE de cada sentencia respecto a cada mundo posible.

La lógica de predicados, llamada también lógica cuantificacional, comienza distinguiendo dos clases de términos: los que representan individuos (gramaticalmente “sujetos”) y los que representan propiedades (gramaticalmente “predicados”). Lógicamente los llamaremos argumentos y predicados respectivamente

El ejemplo anterior no sólo nos muestra el concepto de implicación, sino. También cómo el concepto de implicación se puede aplicar para derivar conclusiones. Es decir: INFERENCIA LOGICA llevas a cabo la inferencia lógica. El algoritmo de inferencia que se denomina comprobación de modelos porque enumera todos los modelos COMPROBACION DE MODELOS posibles y comprueba si a es verdadera en todos los modelos en los que la BC es verdadera. Se dice que un algoritmo de inferencia que se deriva sólo sentencias implicadas es sólido o que mantiene la verdad. También es muy deseable la propiedad de completitud: un algoritmo de inferencia

Es completo si puede derivar cualquier sentencia que está implicada.

La sintaxis de la lógica proposicional nos define las sentencias que se pueden construir. Las sentencias atómicas (es decir. los elementos sintácticos indivisibles) se componen de un único símbolo proposicional. . Cada uno de estos símbolos representa una proposición Que puede ser verdadera o falsa. Utilizaremos letras mayúsculas para estos símbolos: P, Q, K; y siguientes.

A la lógica proposicional también se le denominan Lógica Booleana, por el Matemático George Boole (1815-1864).

validación de un conjunto de sentencias mediante tablas de verdad

Una inferencia es una evaluación que realiza la mente entre expresiones bien formadas de un lenguaje (EBF) que, al ser relacionadas intelectualmente como abstracción, permiten trazar una línea lógica de condición o implicación lógica entre las diferentes EBF. De esta forma, partiendo de la verdad o falsedad posible (como hipótesis) o conocida (como argumento) de alguna o algunas de ellas, puede deducirse la verdad o falsedad de alguna o algunas de las otras EBF. En un sistema inferencial llamamos inferencias a los procesos mediante los cuales obtenemos una conclusión a partir de unas premisas de forma que el razonamiento sea válido. Una inferencia que siga las reglas será una inferencia correcta, mientras que si no las sigue será una inferencia incorrecta. En varios tratados lógicos podemos encontrar que a la conclusión de se le da el nombre de consecuencia lógica de las premisas.

Formalmente podemos decir que C es una conclusión o consecuencia lógica de las premisas P1, P2, P3, ..., Pn si y sólo si para cualquier interpretación I para la que P1ᶺ P2 ᶺP3ᶺ..ᶺPn es verdadera, C también es verdadera. Se puede demostrar que C es una conclusión o consecuencia lógica de las premisas P1, P2, P3, ..., Pn si y sólo si la sentencia P1ᶺP2ᶺP3ᶺ...ᶺPn-C es una tautología. O bien, si y sólo si la sentencia P1ᶺP2ᶺP3ᶺ...ᶺPnᶺ¬C es una contradicción.

REGLAS DE INFERENCIA MODUS PONENDO PONENS (PP) p → q “Si llueve, entonces las calles se mojan” (premisa) p “Llueve” (premisa)__________ q “Luego, las calles se mojan” (conclusión)

El condicional o implicación es aquella operación que establece entre dos enunciados una relación de causa-efecto. La regla ‘ponendo ponens’ significa, “afirmando afirmo” y en un condicional establece, que si el antecedente (primer término, en este caso p) se afirma, necesariamente se afirma el consecuente (segundo término, en este caso q). 

MODUS TOLLENDO TOLLENS (TT) ‘Tollendo tollens’ significa “negando, niego”, y se refiere a una propiedad inversa de los condicionales, a los que nos referíamos en primer lugar.

 p → q “Si llueve, entonces las calles se mojan” ¬q “Las calles no se mojan” _________ ¬p 

“Luego, no llueve” Si de un condicional, aparece como premisa el consecuente negado (el efecto), eso nos conduce a negar el antecedente (la causa), puesto que si un efecto no se da, su causa no ha podido darse.

Esto nos permite formular una regla combinada de las ambas anteriores, consecuencia ambas de una misma propiedad de la implicación; la regla ponendo ponens sólo nos permite afirmar si está afirmado el antecedente (el primer término de la implicación), y la regla tollendo tollens sólo nos permite negar a partir del consecuente (segundo término de la implicación); ambas consecuencias se derivan de que la implicación es una flecha que apunta en un único sentido, lo que hace que sólo se pueda afirmar a partir del antecedente y negar sólo a partir del consecuente. 

MODUS PONENDO PONENS (PP)

 p → q “Si llueve, entonces las calles se mojan” (premisa) p “Llueve” (premisa) _________________ q “Luego, las calles se mojan” (conclusión)

El condicional o implicación es aquella operación que establece entre dos enunciados una relación de causa-efecto. La regla ‘ponendo ponens’ significa, “afirmando afirmo” y en un condicional establece, que si el antecedente (primer término, en este caso p) se afirma, necesariamente se afirma el consecuente (segundo término, en este caso q).

 DOBLE NEGACIÓN (DN) MODUS PONENDO PONENS (PP)

 p → q “Si llueve, entonces las calles se mojan” (premisa) p “Llueve” (premisa) __________ q “Luego, las calles se mojan” (conclusión)

El condicional o implicación es aquella operación que establece entre dos enunciados una relación de causa-efecto. La regla ‘ponendo ponens’ significa, “afirmando afirmo” y en un condicional establece, que si el antecedente (primer término, en este caso p) se afirma, necesariamente se afirma el consecuente (segundo término, en este caso q).

 ¬¬p ↔ p El esquema representa, “p doblemente negada equivale a p”. Siguiendo el esquema de una inferencia por pasos, la representaríamos así:

 ¬¬p “No ocurre que aurora no es una repostera” ___________________ p “Aurora es una repostera ” La regla ‘doble negación’, simplemente establece que si un enunciado está doblemente negado, equivaldría al enunciado afirmado.

ADJUNCIÓN Y SIMPLIFICACIÓN

Adjunción (A): Si disponemos de dos enunciados afirmados como dos premisas separadas, mediante la adjunción, podemos unirlos en una sola premisa utilizando el operador Λ (conjunción). p “EDUARDO ES MECÁNICO” q “DANIEL ES ESTUDIANTE” ____________ p Λ q 

“EDUARDO ES MECÁNICO Y DANIEL ES ESTUDIANTE” Simplificación (S): obviamente, es la operación inversa. Si disponemos de un enunciado formado por dos miembros unidos por una conjunción, podemos hacer de los dos miembros dos enunciados afirmados por separado.

p Λ q “Tengo una manzana y tengo una pera” _______________ p “Tengo una manzana” q “Tengo una pera”

 MODUS TOLLENDO PONENS (TP) 

La disyunción, que se simboliza con el operador V, representa una elección entre dos enunciados. Ahora bien, en esa elección, forma parte de las posibilidades escoger ambos enunciados, es decir, la verdad de ambos enunciados no es incompatible, si bien, ambos no pueden ser falsos.

A partir de lo anterior, se deduce la siguiente regla, denominada tollendo ponens (negando afirmo): si uno de los miembros de una disyunción es negado, el otro miembro queda automáticamente afirmado, ya que uno de los términos de la elección ha sido descartado. 

p V q “He ido al cine o me he ido a la escuela”

¬q “No he ido a la escuela” _________ p “Por tanto, he ido al cine”

LEY DE LA ADICIÓN (LA) Dado un enunciado cualquiera, es posible expresarlo como una elección (disyunción) acompañado por cualquier otro enunciado. a “He comprado manzanas” b "He comprado mangos" _______ a V b “He comprado manzanas o he comprado mangos”

SILOGISMO HIPOTÉTICO (SH) Dados dos implicaciones, de las cuales, el antecedente de la una sea el consecuente de la otra (el mismo enunciado), podemos construir una nueva implicación cuyo antecedente sea el de aquella implicación cuya consecuencia sea el antecedente de la otra implicación, y cuyo consecuente sea el de ésta última, cuyo antecedente era consecuencia del primero. Expresado de otro modo, si una causa se sigue una consecuencia, y ésta consecuencia es a su vez causa de una segunda consecuencia, se puede decir que esa primera causa es causa de esa segunda consecuencia, del mismo modo que, si una bola de billar roja golpea a otra bola blanca que a su vez golpea a una bola negra, la bola roja es causa del movimiento de la bola negra. Expresado en forma de inferencia lógica: p → q “Si la bola roja golpea a la bola blanca, la bola blanca se mueve”

q → r “Si la bola blanca golpea a la bola negra, la bola negra se mueve” _________ p → r “Si la bola roja golpea a la bola blanca, la bola negra se mueve”

SILOGISMO DISYUNTIVO (DS) Dadas tres premisas, dos de ellas implicaciones, y la tercera una disyunción cuyos miembros sean los antecedentes de los condicionales, podemos concluir en una nueva premisa en forma de disyunción, cuyos miembros serían los consecuentes de las dos implicaciones. Lógicamente, si planteamos una elección entre dos causas, podemos plantear una elección igualmente entre sus dos posibles efectos, que es el sentido de esta regla.

p → q “Si llueve, entonces las calles se mojan” r → s “Si la tierra tiembla, los edificios se caen” p V r “Llueve o la tierra tiembla” _________ q V s “Las calles se mojan o los edificios se caen”

SIMPLIFICACIÓN DISYUNTIVA (SD) Si disponemos de dos premisas que corresponden a dos implicaciones con el mismo consecuente, y sus antecedentes se corresponden con los dos miembros de una disyunción, podemos concluir con el consecuente de ambas implicaciones.

 p V q “Helado de fresa o helado de vainilla”

p → r “Si tomas helado de fresa, entonces repites” q → r “Si tomas helado de vainilla, entonces repites” __________ r Luego, repites

LEY CONMUTATIVA

 Esta ley, no es válida para la implicación, pero sí para conjunción y para la disyunción. Una conjunción es afirmar que se dan dos cosas a la vez, de modo que el orden de sus elementos no cambia este hecho. Igualmente, una disyunción es presentar una elección entre dos cosas, sin importar en qué orden se presente esta elección. Así pues,

p Λ q ↔ q Λ p “«p y q» equivale a «q y p»” p V q ↔ q V p “«p ó q» equivale a «q ó p»

LEYES DE MORGAN (DM)

 Esta ley permite transformar una disyunción en una conjunción, y viceversa, es decir, una conjunción en una disyunción. Cuando se pasa de una a otra, se cambian los valores de afirmación y negación de los términos de la disyunción/conjunción así como de la propia operación en conjunto, como podemos observar aquí:

p Λ q                    p V q

 ___________    ____________ 

¬(¬p V ¬q)            ¬(¬p Λ ¬q)

LA DEMOSTRACIÓN Y SUS MÉTODOS

La demostración consiste básicamente en, a partir de preposiciones dadas llamadas premisas, obtener la proposición llamada conclusión, mediante la aplicación de reglas lógicas.

Los métodos de demostración son modelos o esquemas generales que se encuentran en los procesos deductivos, estos modelos están fundamentados lógicamente en teoremas o reglas de inferencia ya establecidas, se pueden distinguir cuatro métodos de demostración:

 MÉTODO DIRECTO O DE HIPÓTESIS AUXILIAR.

 Este método se utiliza para la demostración de implicaciones, y dice así: Sean R y S fórmulas. Si el suponer que R es verdadera, se puede hacer una demostración de que S es verdadera, entonces la implicación R Þ S es una fórmula verdadera.

Justificación: La tabla de verdad del condicional muestra que con antecedente verdadero, hay implicación, sólo en el caso en el que el consecuente es verdadero.

Esquema Operativo General: Para demostrar que una fórmula del tipo
R ÞS es teorema, se procederá así:

Se supone que el antecedente R es verdadero. A R se le llama hipótesis auxiliar.

A partir de la hipótesis, se construye un argumento lógico en el cual se pueden utilizar los axiomas y los teoremas ya probados, mediante la aplicación de las reglas de validez, para llegar a la fórmula S como conclusión o tesis.

En este punto concluye la prueba y queda establecida la verdad de R ÞS.

Esquema operativo general:

Para demostrar que una proposición específica de la forma  es teorema se procede así:

1. Suponemos como verdadero el antecedente P. Esta la denominamos hipótesis auxiliar.
2. A partir de la hipótesis construimos una argumentación lógica en la cual podemos utilizar los axiomas y teoremas demostrados para obtener mediante la aplicación de las reglas de validez y de inferencia, la validez de Q.
3. En este punto concluye la prueba y queda establecida la validez de .

A modo de síntesis, una demostración de la proposición P-Q por el método directo, tendría este desarrollo esquemático:

Ejemplo

Demuestre que: si a y b son números pares, entonces a + b es número par.
Solución:

Suponga que a y b son números pares, (Hipótesis auxiliar) luego, a = 2n y b = 2m con n, m Î Z .

 Entonces, a + b = 2n+ 2m =2(n + m); (n + m) ÎZ(enteros). Por tanto, si n + m = k; a + b = 2k, es decir, a + b es un número par.

Dadas P, Q y R fórmulas, pruebe que:
(P ÞQ) Þ ((Q Þ R) Þ (P Þ R)) es un teorema.

Solución:

P Þ Q (hipótesis auxiliar)

Q Þ R (hipótesis auxiliar)

P (Hipótesis auxiliar)

Q (RV1 en 1 y 3)

R (RV1 en 2 y 4)

P Þ R (método directo en 3 y 5)

(Q Þ R) Þ (P ÞR) (método directo en 2 y 6)

(P Þ Q) Þ ((Q Þ R) Þ (P Þ R)) (método directo en 1 y 7)

La anterior solución, muestra el esquema de la demostración, donde se hace una aplicación reiterada del método directo ya que lo que se debe probar es una cadena de implicaciones.
A medida que se toman las hipótesis auxiliares, se va desplazando la demostración hacia la derecha, para mostrar que las siguientes afirmaciones están subordinadas a las hipótesis anteriores. Cuando se comienza a establecer conclusiones se vuelve a desplazar la demostración hacia la izquierda, hasta establecer la conclusión definitiva en la teoría original, es decir, aquella donde no hay hipótesis auxiliares.

MÉTODO DEL CONTRARRECÍPROCO.

Se llama contrarrecíproco a una ley lógica, formalizada en los silogismos por Aristóteles, que consiste en la implicación de la negación de un consecuente con la negación de su antecedente.

El teorema del contrarrecíproco  da lugar a una variante del método directo, que se utiliza mucho en matemáticas y es conocido como método del contrarrecíproco. Este método puede resumirse así: Supongamos que se quiere demostrar que una proposición específica  es teorema y al intentar su demostración por el método directo no logramos obtener la conclusión deseada. Se procede entonces a demostrar por el método directo su contrarrecíproca , si se consigue este objetivo entonces queda establecida la validez de  al hacer sustitución por equivalencia.

Esquema operativo general

Para demostrar que una proposición específica de la forma  es un teorema se procede así:

1. Suponemos como hipótesis auxiliar no Q.
2. Utilizando el método directo construimos una argumentación lógica hasta concluir no P.
3. Concluimos por el método directo que  es teorema.
4. La regla de validez 3 nos permite concluir que  es válida mediante la equivalencia del contrarrecíproco.

A modo de síntesis una demostración de la proposición  por este método tendría este desarrollo esquemático:

Demostración por contrarreciproco

Si tenemos que demostrar que una proposición p implica una proposición q (es decir, si se da p, se tiene que dar q), a veces es más sencillo demostrar que si no se da q, entonces no puede cumplirse p. Esto se conoce como demostración por contrarrecíproco o contraposición. Nótese que "p implica q" y "no q implica no p" son proposiciones equivalentes.

Ejemplo

Un ejemplo sencillo: "Demuéstrese que todos los números primos mayores que 2 son impares". Aquí, la proposición p es "n es un número primo mayor que 2" y la proposición q es "n es un número impar". Demostrar que todo número primo mayor que 2 es impar (p -> q) es lo mismo que demostrar que no existe un número par que sea número primo mayor que 2, o equivalentemente, que el único número primo par es 2 (no q -> no p).

Esto es más fácil de demostrar, ya que todo número par se puede escribir como n = 2 × k, donde k es mayor o igual que 1 (la idea de número primo tiene sentido sólo en los números naturales). Si k es igual a 1, tenemos n = 2, número primo. Si, por el contrario, k es mayor que 1, entonces n es mayor que 2, pero no es primo ya que tiene algún factor que no es ni 1 ni él mismo. Así que 2 es el único número primo par, por lo que se ha demostrado que todos los números primos mayores que 2 son impares.

MÉTODO DE DEMOSTRACIÓN POR REDUCCIÓN AL ABSURDO.

Contradicción: Designamos en esta forma, toda proposición correspondiente a la conjunción entre una proposición y su negación.

Teoría contradictoria o inconsistente: Se dice que una teoría es contradictoria o inconsistente, cuando en dicha teoría es posible demostrar una contradicción. En una teoría contradictoria podemos concluir que una proposición es verdadera y falsa a la vez.

Esquema operativo general

Supongamos que se quiere demostrar que una proposición específica P es teorema. Por este método procedemos así:

1. Suponemos la negación de la tesis (no P) como hipótesis auxiliar.
2. A partir de las premisas de la teoría y de la hipótesis auxiliar se razona por el método directo, hasta obtener como conclusión una contradicción por ejemplo, Q y no Q.
3. Por el método directo concluimos 
4. El teorema anterior nos permite concluir del paso 3) la validez de P.

Nota: En la práctica, cuando se usa este método, al obtener una contradicción, inmediatamente se valida la negación de la hipótesis supuesta dando por terminada la prueba.

A modo de síntesis una demostración de una proposición P por este método tendría este desarrollo esquemático.

 Una de las condiciones que debe verificar el conjunto de axiomas, dado para la teoría, es la consistencia. Es decir, a partir de ellos no pueden derivarse, por aplicación de las reglas lógicas, contradicciones, o sea, fórmulas de la forma R Ù Ø R. Esto constituye la fundamentación del método de demostración por reducción al absurdo, el cual puede enunciarse así:

"Si al suponer que la proposición Ø P es un teorema, se puede establecer como teorema una proposición contradictoria, entonces el supuesto Ø P es falso, es decir, la proposición P es un teorema". 
Justificación: 

1. Ø P Þ R Ù Ø R método dir.

2. Ø P Þ Ø (Ø R Ú Ø Ø R) def. de Ù en 1.

3. Ø R Ú Ø Ø R Þ P contrar. en 2.

4. P RV1 en 3.

Procedimiento para la Aplicación del Método. Suponga que se va a demostrar que P es teorema por aplicación del método de reducción al absurdo, entonces, se siguen los siguientes pasos:

• Suponga que Ø P es verdadero.
• A partir de esta hipótesis se razona lógicamente hasta obtener como conclusión la conjunción de una fórmula con su negación.
• Por el método de reducción al absurdo, se concluye que P es teorema.

Ejemplo: Utilizando el método de reducción al absurdo, demostrar que el número real es irracional.

Solución:

Suponga que no es irracional, luego es racional y por tanto  = p/q, q ¹ 0, p, q Î Z y p, q primos relativos.

2 = p²/q², 2q² = p², de donde p² es número par y por lo tanto lo es p, esto es p = 2k, k Î Z, entonces p² = 4k². Se concluye, entonces, que 2q² = 4k²; q² = 2k², q² es número par, luego q es un número par.

Luego p y q tienen factor común 2. ¡Absurdo! puesto que p y q son primos relativos. Por tanto, es número irracional.

 MÉTODO DE CASOS. (SILOGISMO DISYUNTIVO).

La regla de inferencia de ese nombre da lugar a este método de demostración, casi de forzosa utilizacióncuando la hipótesis o una de las hipótesis es una disyunción de dos o más proposiciones, en cuyo caso procedemos así:

1. Suponemos la hipótesis dada correspondiente a una disyunción.
2. A partir de cada una de las proposiciones que integran la disyunción se obtiene una conclusión parcial por el método directo.
3. Se concluye finalmente la disyunción de las conclusiones parciales.

Esquema operativo general

Supongamos que se fuera a demostrar que un esquema de la forma  es teorema. Bajo este método procedemos esquemáticamente así:

Ejemplo:

Demostrar el siguiente teorema: Para a, b números reales, si a = 0 ó b = 0 entonces a.b = 0

1. Supongamos a = 0 ó b = 0 Hipótesis auxiliar 1

2. Supongamos: a = 0 Hipótesis auxiliar 2

3. a.b = 0.b Ley uniforme del producto en 2

4. 0.b = 0 Teorema en el conjunto de números reales

5. a.b = 0 Transitividad en la igualdad de 3. y 4.

6. Método directo 2....5.

7. Supongamos: b = 0 Hipótesis auxiliar 2

8. a.b = a.0 Ley uniforme del producto en 7

9. a.0 = 0 Teorema en el conjunto de los números reales

10. a.b = 0 Transitividad en la igualdad 8.y 9.

11.  Método directo 7....10.

12. a.b = 0 Método de casos de 1., 6. y 11.(Regla de inferencia )

13. Método directo

Tecnicas Heuristicas

Se puede definir Heurística como un arte, técnica o procedimiento práctico o informal, para resolver problemas. Alternativamente, se puede definir como un conjunto de reglas metodológicas no necesariamente formalizadas, positivas y negativas, que sugieren o establecen cómo proceder y problemas a evitar a la hora de generar soluciones y elaborar hipótesis.

Es generalmente considerado que la capacidad heurística es un rasgo característico de los humanos desde cuyo punto de vista puede describirse como el arte y la ciencia del descubrimiento y de la invención o de resolver problemas mediante la creatividad y el pensamiento lateral o pensamiento divergente. Según el matemático George Pólya la base de la heurística está en la experiencia de resolver problemas y en ver cómo otros lo hacen. Consecuentemente se dice que hay búsquedas ciegas, búsquedas heurísticas (basadas en la experiencia) y búsquedas racionales.

La palabra heurística procede del término griego εὑρίσκειν, que significa «hallar, inventar» (etimología que comparte con Eureka). La palabra «heurística» aparece en más de una categoría gramatical. Cuando se usa como sustantivo, identifica el arte o la ciencia del descubrimiento, una disciplina susceptible de ser investigada formalmente. Cuando aparece como adjetivo, se refiere a cosas más concretas, como estrategias heurísticas, reglas heurísticas o silogismos y conclusiones heurísticas. Claro está que estos dos usos están íntimamente relacionados ya que la heurística usualmente propone estrategias heurísticas que guían el descubrimiento.

La robótica trata de cubrir todos los temas necesarios para programar un robot con inteligencia artificial en aplicaciones de sensado y planificación de rutas para dar solución a un problema. A través del tiempo, el campo de la robótica se ha transformado, al pasar de máquinas rústicas hasta la construcción de humanoides, que permiten resolver tareas sencillas o complicadas.

Algunos de estos robots, se han construido basándose en el comportamiento de seres vivos dándole un toque sutil del raciocinio. No sólo la parte física y de comportamiento se ha basado en la vida, sino también los algoritmos que controlan dichos robots, los cuales nos dan una mayor posibilidad de encontrar soluciones a problemas difíciles de resolver para el ser humano.

Algunas de las técnicas que involucran procedimientos de búsqueda en el espacio de soluciones factibles.

Búsqueda local.

Los algoritmos de búsqueda local parten de una solución inicial  y aplicándole operadores de variación, la van alterando; si la solución alterada es mejor que la original, se acepta, si no lo es, se vuelve a la inicial. El procedimiento se repite hasta que no se consigue mejora en la solución. Los procedimientos de búsqueda local más usados son los basados en el gradiente: en este caso, el operador de variación selecciona una nueva solución teniendo en cuenta la derivada de la función que se quiere optimizar en el punto, tratando de ascender o descender usando el gradiente hasta llegar a un punto de inflexión donde no se puede obtener ninguna mejora adicional.

Métodos que usan soluciones parciales.

Estos métodos van construyendo soluciones variables a variable, no obteniendo una solución completa al problema hasta que todas las variables han sido asignadas. Uno de los métodos más conocidos son los algoritmos voraces o greedy, que funcionan de la forma siguiente: para cada variable, se asigna aquél valor que maximice alguna función de utilidad.

En el caso del TSP, un algoritmo voraz comenzaría con una ciudad elegida aleatoriamente, y elegiría la ciudad más cercana a ésta. Para esta segunda ciudad, elegiría la más cercana, y así sucesivamente.

En este caso, el problema estaría simplemente parametrizado con la ciudad inicial elegida. Los algoritmos voraces sustituyen un criterio de optimalidad global por un criterio en cada paso; no siempre los dos se corresponden, y por tanto, no tienen porqué hallar el máximo global del problema.

Otros métodos consisten en dividir el problema general en problemas más simples, y hallar la solución a estos problemas más simples; el método se denomina divide y vencerás; en algunos casos, la solución a un problema de orden n puede venir resolver a otro problema de orden n-1, tal como sucede, por ejemplo en el conocido problema de las torres de Hanói. Ejemplo branch and bound. Algunos métodos consisten en ir descartando partes del espacio de búsqueda, con el objeto de acotar cada vez más la solución al problema.

El branch and bound. Este método imagina el espacio de búsqueda como un árbol de decisión; en cada paso del algoritmo, se toma la decisión de podar las ramas del árbol que parezcan menos prometedoras.

Este método procede de la forma siguiente: se establece una cota inferior a la posible solución (o superior, si se trata de minimizar). Se va siguiendo una rama del árbol, hasta que se encuentra que la solución parcial es menor que esa cuota; en ese caso, se descarta la rama completa.

En el caso del recorrido del viajante, supongamos que hemos establecido que la cota superior es 200 Km. Se establece un árbol de la forma siguiente: tomando una ruta entre dos ciudades, pongamos AB, se establecen dos ramas para una posible solución con y sin esa ruta; a partir de ahí, se hace lo mismo con el resto de las rutas.

Se van recorriendo las ramas, y si se encuentra que la suma parcial de las rutas supera los 200 Km, se elimina esa rama y ya no se sigue recorriendo. Si se ha organizado el espacio de búsqueda en forma de árbol, puede resultar importante la ordenación de las ramas, porque si se consigue colocar las ramas "mejores" antes, el algoritmo será capaz de encontrar la solución con más rapidez. Algoritmos como él A* toman este tipo de enfoque. En este algoritmo, se usa un método mejor-primero para recorrer las ramas, y un método heurístico para estimar el coste de las ramas que quedan por recorrer. La principal diferencia con el método anterior es que se usan heurísticas para estimar valores de las ramas restantes, en vez de valores exactos.

Estos métodos se pueden extender también a problemas de optimización numérica, en cuyo caso

darían cotas entre las cuales se moverían las soluciones. Pero si el espacio de búsqueda no se puede enumerar bien, o si existe un número de variables excesivo, este tipo de algoritmos no suelen funcionar bien.

Hillclimbing

Estos procedimientos se suelen llamar de hillclimbing, o de escalado de colinas; el mayor truco en ellos consiste en escoger correctamente el tamaño de paso para ascender y el punto de inicio. Pero se trata de algoritmos de búsqueda locales, y, como tales, sólo van a encontrar el máximo local más cercano al punto de inicio.  Esto se puede resolver usando una estrategia de multicomienzo, pero, en todo caso, no te garantizan que se encuentre, o incluso de acerque uno, al máximo global. En todo caso, tiene la ventaja de que, en cada iteración del algoritmo, se tiene una solución válida, aunque no tiene porqué ser la mejor. En el caso del TSP, un procedimiento de búsqueda local se denomina 2-opt. Consiste en escoger una permutación inicial aleatoria, e ir probando con todas las posibles soluciones en la vecindad de esta, entendiendo como vecindad el conjunto de todos los recorridos que pueden ser alcanzados intercambiando dos caminos no adyacentes en el recorrido original. Un recorrido reemplaza al original si es mejor; una vez que no se puede mejorar un recorrido, se considera óptimo y se da como solución.

El mejor algoritmo de búsqueda local conocido para el recorrido del viajante es el llamado Lin-Kernighan. Es una variación del anterior, permitiendo el número de caminos a intercambiar en cada iteración variar; además, en vez de tomar cualquier mejora, prueba varias y se queda con la mejora de más valor.

Recocido Simulado

El recocido simulado o algoritmo de los Dioses (es un escalador estocástico). Se basa en el proceso de recocido, en la cual los metales se funden y se forjan a la par que se enfrían, hasta conseguir una estructura cristalina, dura y resistente.

Éste método realiza una búsqueda global que requiere de una “temperatura” inicial, una final y una función de variación de la temperatura. Consiste en un ascenso de gradiente comenzando en un punto aleatorio; dependiendo de la temperatura es como se mueve por el espacio de búsqueda. La probabilidad de escoger una solución peor que la actual, desciende con el tiempo; la solución (se aproxima a la solución óptima) se escoge de manera determinista evitando los mínimos locales.

Iteración básica

En cada iteración, el método de recocido simulado evalúa algunos vecinos del estado actual s y probabilísticamente decide entre efectuar una transición a un nuevo estado s' o quedarse en el estados. En el ejemplo de recocido de metales descrito arriba, el estado s se podría definir en función de la posición de todos los átomos del material en el momento actual; el desplazamiento de un átomo se consideraría como un estado vecino del primero en este ejemplo. Típicamente la comparación entre estados vecinos se repite hasta que se encuentre un estado óptimo que minimice la energía del sistema o hasta que se cumpla cierto tiempo computacional u otras condiciones.

Vecindario de un estado

El vecindario de un estados está compuesto por todos los estados a los que se pueda llegar a partir de s mediante un cambio en la conformación del sistema. Los estados vecinos son generados mediante métodos de Montecarlo.

El método de evaluación de estados vecinos es fundamental para encontrar una solución óptima global al problema dado. Los algoritmos heurísticos, basados en buscar siempre un estado vecino mejor (con energía más baja) que el actual se detienen en el momento que encuentran un mínimo local de energía. El problema con este método es que no puede asegurar que la solución encontrada sea un óptimo global, pues el espacio de búsqueda explorado no abarca todas las posibles variaciones del sistema.

Búsqueda Tabú

La búsqueda tabú fue propuesta por Glover, Taillard y de Werra. El método es utilizado para resolver problemas complejos de optimización. Esta técnica, en realidad es una meta-heurística,

que guiará a otras técnicas para que no se quede en óptimos locales. También ayuda a la resolución de problemas combinatorios.

La búsqueda Tabú, explora el espacio de búsqueda de todas las soluciones por medio de movimientos que se harán sólo si la solución siguiente es mejor que la anterior. Para que esta técnica no quede atrapada en un óptimo local o se generen movimientos cíclicos la búsqueda tabú utiliza una “memoria” (lista taboo) en donde se almacenan las soluciones examinadas recientemente, volviéndose prohibidas para el siguiente movimiento que se realizará. También, registra los atributos más comunes de un conjunto de soluciones para buscar en la zona que le corresponde y a largo plazo se extiende sobre regiones no exploradas.

Conceptos Básicos de Búsqueda Tabú

Los orígenes de la búsqueda tabú se ubican a fines de los 60s y principios de los 70s, y se atribuye a Fred Glover, quien desarrolló esta heurística para tratar de resolver problemas de cubierta no lineal (nonlinear covering), aunque varios de sus principios también fueron delineados independientemente por P. Hansen. La búsqueda tabú surgió como un dispositivo que permitiría implementar una estrategia para resolver problemas de programación entera con restricciones sustitutas (surro-gate constraints),  y aunque su planteamiento original ha sufrido varios cambios a través de los años, la idea básica propuesta por Glover ha permanecido intacta desde sus orígenes.

La búsqueda tabú puede verse como una meta-heurística que se superpone a una técnica de búsqueda y que se encarga de evitar que dicha técnica caiga en óptimos locales prohibiendo (o, en un sentido más general, penalizando) ciertos movimientos. El propósito de clasificar ciertos movimientos como prohibidos (o "tabú") es para evitar que se caiga en ciclos durante la búsqueda. 

Debido a esto, Glover sugiere como nombre alternativo para su método el de búsqueda con "inhibición débil", ya que los movimientos que se consideran prohibidos constituyen generalmente una pequeña fracción del total de movimientos disponibles, y un movimiento pierde su status de prohibido después de un período de tiempo relativamente corto, volviéndose después nuevamente accesible. A este respecto, este método puede contrastarse con la técnica de ramificación y límites (branch and bound) que también prohíbe ciertos movimientos para evitar ciclos, pero lo hace de una manera

La búsqueda tabú se encuentra fundamentada en 3 cosas principales:

1. El uso de estructuras flexibles de memoria basadas en atributos, diseñadas para permitir una mejor explotación de los criterios de evaluación y la información histórica de la búsqueda que lo que se conseguiría con estructuras rígidas de memoria (como las que se usan en la búsqueda de ramificación y límites y el algoritmo A*) o con sistemas carentes de memoria (como la técnica de "enfriamiento simulado" simulated annealing y otras técnicas aleatorias similares).

2. Un mecanismo asociado de control (para emplear las estructuras de memoria) basado en la interacción entre las condiciones que limitan y hacen más flexible el proceso de búsqueda. Este mecanismo se encuentra inmerso en la técnica en la forma de restricciones y criterios de aspiración (un criterio de aspiración es aquél que permite que un movimiento pierda su status de "tabú" debido a que proporciona una mejor solución que la actual).

3. La incorporación de memorias de diferente duración (de corto a largo plazo), para implementar estrategias que intensifiquen y diversifiquen la búsqueda. Las estrategias de intensificación refuerzan las propiedades de las combinaciones de movimientos que han demostrado (históricamente) ser buenas, mientras que las estrategias de diversificación dirigen la búsqueda hacia nuevas regiones del espacio de soluciones factibles. Note que estos dos mecanismos son muy similares a la cruza y la mutación en los algoritmos genéticos, ya que la primera nos permite delimitar una cierta región del espacio de búsqueda, mientras que la segunda nos permite saltar a nuevas regiones del mismo, evitando que quedemos atrapados en un óptimo local.

La parte medular de la búsqueda tabú se localiza en el proceso de memoria de corto plazo, y muchas de las consideraciones estratégicas en que se fundamenta este proceso reaparecen, amplifica-das pero sin mayores modificaciones, en los procesos de memoria de largo plazo.

Ejemplo de Uso

Para ilustrar el funcionamiento de esta técnica, utilizaremos un ejemplo clásico de estructuras de datos e Inteligencia Artificial: el problema de las N reinas. La idea básica es colocar N reinas en un tablero de ajedrez de N×N casillas, de tal manera que ninguna de ellas pueda capturar a otra.

Este problema puede verse como uno de optimización en el que el objetivo es minimizar el número de colisiones (una colisión se presenta cuando una reina puede capturar a otra). Si asumimos que cada reina se colocará siempre en una fila determinada de acuerdo a un cierto orden pre-establecido, podemos representar cualquier estado del tablero usando una permutación de la forma (p1, p2,..., pn), donde el valor de p1 representa la columna donde se colocará a  la reina que está en la fila 1, y así sucesivamente.

Una de las operaciones básicas que el algoritmo utilizará es el intercambio de 2 elementos cualquiera de una permutación en la que haya colisiones. A fin de evitar la repetición de intercambios realizados recientemente, consideraremos tabú cualquier intercambio de este tipo. Debido a condiciones de simetría (intercambiar las reinas 1 y 4 es lo mismo que intercambiar las reinas 4 y 1), una estructura puede usarse para almacenar el número de iteraciones que faltan para permitir que 2 reinas intercambien posiciones nuevamente.

La restricción de los intercambios de 2 reinas puede ser ignorada si un cierto movimiento (prohibido) conduce a una mejor solución (este es el criterio de aspiración).

Escalando la colina

Esta técnica se basa en optimización local, sigue la dirección de ascenso o descenso a partir de su posición y requiere muy poco costo computacional. Su comportamiento es irrevocable porque no permite regresarnos a otra alterativa.

La técnica de escalando la colina, evalúa la función en varios puntos, pasando de un punto a otro donde el valor de la evaluación es mayor. La búsqueda termina cuando se ha encontrado el punto con un valor máximo, por lo que no se obtendría la mejor solución.

Algoritmos Bio-inspirados

Son propuestas inspiradas en modelos biológicos, tales como Algoritmos de Optimización basada en Colonias de Hormigas, Algoritmos basados en Enjambres (de abejas, termitas) y Computación Evolutiva. Basan su operación en los principios de la teoría Neo-Darwiniana de la evolución natural. Los problemas combinatoriales pueden ser divididos en dos grandes grupos considerando la existencia de algoritmos polinomiales para resolver cada tipo de problema. El primero es el problema tipo P (polinomial) para el cual existen algoritmos con esfuerzos computacionales de tipo polinomial para encontrar la solución óptima; y el segundo es el problema tipo NP (no polinomial) para el cual no se conocen algoritmos con esfuerzos computacionales de tipo polinomial para encontrar la solución óptima. Las técnicas heurísticas son algoritmos que encuentran soluciones de buena calidad para problemas combinatoriales complejos; o sea, para problemas tipo NP. Los algoritmos heurísticos son más fáciles de implementar y encuentran buenas soluciones con esfuerzos computacionales relativamente pequeños;  sin embargo, renuncian (desde el punto de vista teórico) a encontrar la solución óptima global de un problema.

En problemas de gran tamaño rara vez un algoritmo heurístico encuentra la solución óptima global. Los algoritmos heurísticos se clasifican en algoritmos constructivos (golosos), algoritmos de descomposición y división, algoritmos de reducción, algoritmos de manipulación del modelo y algoritmos de búsqueda usando vecindad. En esta última categoría pueden ser agrupados los Algoritmos Genéticos (AG),

 Simulated Annealing (SA),

Búsqueda Tabú (TS), Colonia de

Hormigas (ACO) y GRASP, [4, 5].

Algoritmos Genéticos (AG)

Son herramientas matemáticas que imitan a la naturaleza e intentan resolver problemas complejos empleando el concepto de la evolución. El algoritmo ejecuta una búsqueda simultánea en diferentes regiones del espacio factible, realiza una intensificación sobre algunas de ellas y explora otros subespacios a través de un intercambio de información entre configuraciones. Emplea tres mecanismos básicos que son: La selección, el crossover y la mutación, [4, 5]:

Algoritmos Genéticos:

En forma aleatoria se conformó una población inicial, en la que cada cromosoma representa una posible ruta a seguir y cada gen indica el número de la ciudad.

Los datos utilizados por el algoritmo son:

Población inicial: 14 cromosomas (aleatoria)

Número de genes por cromosoma: 8

Proceso de selección: Esquema de la ruleta

Tipo de crossover: Punto simple

Tasa de crossover: ρc = 0.9

Tasa de mutación: ρm = 0.02

Máximo número de generaciones: 400

Criterio de parada: 20 generaciones consecutivas sin que mejore la función objetivo o máximo número de generaciones.

Los resultados encontrados por el algoritmo de AG son:

Ruta óptima: 1 4 8 7 6 5 3 2

Función objetivo: 1490

Total de generaciones: 125

Crossover

Consiste en el intercambio de material genético entre dos cromosomas (a veces más, como el operador orgía propuesto por Eiben et al.). El crossover es el principal operador genético, hasta el punto que se puede decir que no es un algoritmo genético si no tiene crossover, y, sin embargo, puede serlo perfectamente sin mutación, según descubrió Holland. El teorema de los esquemas confía en él para hallar la mejor solución a un problema, combinando soluciones parciales.

Para aplicar el crossover, entrecruzamiento o recombinación, se escogen aleatoriamente dos miembros de la población. No pasa nada si se emparejan dos descendientes de los mismos padres; ello garantiza la perpetuación de un individuo con buena puntuación (y, además, algo parecido ocurre en la realidad; es una práctica utilizada, por ejemplo, en la cría de ganado, llamada inbreeding, y destinada a potenciar ciertas características frente a otras). Sin embargo, si esto sucede demasiado a menudo, puede crear problemas: toda la población puede aparecer dominada por los descendientes de algún gen, que, además, puede tener caracteres no deseados. Esto se suele denominar en otros métodos de optimización atranque en un mínimo local, y es uno de los principales problemas con los que se enfrentan los que aplican algoritmos genéticos.

En cuanto al teorema de los esquemas, se basa en la noción de bloques de construcción. Una buena solución a un problema está constituido por unos buenos bloques, igual que una buena máquina está hecha por buenas piezas. El crossover es el encargado de mezclar bloques buenos que se encuentren en los diversos progenitores, y que serán los que den a los mismos una buena puntuación. La presión selectiva se encarga de que sólo los buenos bloques se perpetúen, y poco a poco vayan formando una buena solución. El teorema de los esquemas viene a decir que la cantidad de buenos bloques se va incrementando con el tiempo de ejecución de un algoritmo genético, y es el resultado teórico más importante en algoritmos genéticos.

El intercambio genético se puede llevar a cabo de muchas formas, pero hay dos grupos principales Crossover n-puntos: Los dos cromosomas se cortan por n puntos, y el material genético situado entre ellos se intercambia. Lo más habitual es un crossover de un punto o de dos puntos.

Crossover uniforme: Se genera un patrón aleatorio de 1s y 0s, y se intercambian los bits de los dos cromosomas que coincidan donde hay un 1 en el patrón. O bien se genera un número aleatorio para cada bit, y si supera una determinada probabilidad se intercambia ese bit entre los dos cromosomas.

Crossover especializados: En algunos problemas, aplicar aleatoriamente el crossover da lugar a cromosomas que codifican soluciones inválidas;  en este caso hay que aplicar el crossover de forma que genere siempre soluciones válidas. Un ejemplo de estos son los operadores de crossover usados en el problema del viajante.

Algoritmo genético simple.

John Holland desde pequeño, se preguntaba cómo logra la naturaleza, crear seres cada vez más perfectos (aunque, como se ha visto, esto no es totalmente cierto, o en todo caso depende de qué entienda uno por perfecto). Lo curioso era que todo se lleva a cabo a base de interacciones locales entre individuos, y entre estos y lo que les rodea. No sabía la respuesta, pero tenía una cierta idea de cómo hallarla: tratando de hacer pequeños modelos de la naturaleza, que tuvieran alguna de sus características, y ver cómo funcionaban, para luego extrapolar sus conclusiones a la totalidad. De hecho, ya de pequeño hacía simulaciones de batallas célebres con todos sus elementos: copiaba mapas y los cubría luego de pequeños ejércitos que se enfrentaban entre sí.

En los años 50 entró en contacto con los primeros ordenadores, donde pudo llevar a cabo algunas de sus ideas, aunque no se encontró con un ambiente intelectual fértil para propagarlas. Fue a principios de los 60, en la Universidad de Michigan en Ann Arbor, donde, dentro del grupo Logis of

Computes, sus ideas comenzaron a desarrollarse y a dar frutos. Y fue, además, leyendo un libro escrito por un biólogo evolucionista, R. A. Fisher, titulado La teoría genética de la selección natural, como comenzó a descubrir los medios de llevar a cabo sus propósitos de comprensión de la naturaleza. De ese libro aprendió que la evolución era una forma de adaptación más potente que el simple aprendizaje, y tomó la decisión de aplicar estas ideas para desarrollar programas bien adaptados para un fin determinado. En esa universidad, Holland impartía un curso titulado Teoría de sistemas adaptativos. Dentro de este curso, y con una participación activa por parte de sus estudiantes, fue donde se crearon las ideas que más tarde se convertirían en los algoritmos genéticos. Por tanto, cuando Holland se enfrentó a los algoritmos genéticos, los objetivos de su investigación fueron dos: imitar los procesos adaptativos de los sistemas naturales, diseñar sistemas artificiales (normalmente programas) que retengan los mecanismos importantes de los sistemas naturales.

Unos 15 años más adelante, David Goldberg, actual delfín de los algoritmos genéticos, conoció a Holland, y se convirtió en su estudiante. Golberg era un ingeniero industrial trabajando en diseño de pipelines, y fue uno de los primeros que trató de aplicar los algoritmos genéticos a problemas industriales. Aunque Holland trató de disuadirle, porque pensaba que el problema era excesivamente complicado como para aplicarle algoritmos genéticos, Goldberg consiguió lo que quería, escribiendo un algoritmo genético en un ordenador personal Apple II. Estas y otras aplicaciones creadas por estudiantes de Holland convirtieron a los algoritmos genéticos en un campo con base suficiente aceptado para celebrar la primera conferencia en 1985, ICGA´85. Tal conferencia se sigue celebrando bianualmente.

Anatomía de un algoritmo genético simple

Los algoritmos genéticos son métodos sistemáticos para la resolución de problemas de búsqueda y optimización que aplican a estos los mismos métodos de la evolución biológica: selección basada en la población, reproducción sexual y mutación.

Los algoritmos genéticos son métodos de optimización, que tratan de resolver el mismo conjunto de problemas que se ha contemplado anteriormente, es decir, hallar (xi,..., xn) tales que F (xi,..., xn) sea máximo. En un algoritmo genético, tras parametrizar el problema en una serie de variables, (xi,..., xn) se codifican en un cromosoma. Todas los operadores utilizados por un algoritmo genético se aplicarán sobre estos cromosomas, o sobre poblaciones de ellos. En el algoritmo genético va implícito el método para resolver el problema; son solo parámetros de tal método los que están codificados, a diferencia de otros algoritmos evolutivos como la programación genética. Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, por ser útil para cualquier problema, pero a la vez débil, pues no está especializado en ninguno.

Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor solución (aunque no necesariamente la mejor de todas las soluciones posibles). El ambiente, constituido por las otras camaradas soluciones, ejercerá una presión selectiva sobre la población, de forma que sólo los mejor adaptados (aquellos que resuelvan mejor el problema) sobrevivan o leguen su material genético a las siguientes generaciones, igual que en la evolución de las especies. La diversidad genética se introduce mediante mutaciones y reproducción sexual.

En la Naturaleza lo único que hay que optimizar es la supervivencia, y eso significa a su vez maximizar diversos factores y minimizar otros. Un algoritmo genético, sin embargo, se usará para optimizar habitualmente para optimizar sólo una función, no diversas funciones relacionadas entre sí simultáneamente. Este tipo de optimización, denominada optimización multimodal, también se suele abordar con un algoritmo genético especializado.

Por lo tanto, un algoritmo genético consiste en lo siguiente: hallar de qué parámetros depende el problema, codificarlos en un cromosoma, y se aplican los métodos de la evolución: selección y reproducción sexual con intercambio de información y alteraciones que generan diversidad. En las

siguientes secciones se verán cada uno de los aspectos de un algoritmo genético.