identificar máquinas, además de las restricciones anteriores,
también restringen la identificación a máquinas de estados
(son aquellas que no poseen estados equivalentes).
La identificación de MEF se ha llevado a cabo a través de
experimentos de naturaleza adaptativos, los cuales requieren
que el ingeniero (y/o identificador) haga uso de su
conocimiento de máquinas secuenciales y SED para
seleccionar la apropiada secuencia de entrada en cada etapa de
la identificación. La idea básica es aplicar una secuencia y
observar la respuesta de la máquina, de esa información se
formulan los diagramas de estado parciales. Luego se aplica
otra secuencia de entrada y se usa la respuesta para extender o
eliminar los previamente formados diagramas de estado
parciales, y así se continúa el proceso hasta que se obtenga al
menos un diagrama de estado completamente definido que
describa la máquina que se está investigando.
La selección de una secuencia de prueba en cualquier punto
del experimento depende del ingeniero (y/o identificador) y su
interpretación de los resultados previos. Sin embargo, muchas
veces se escoge una secuencia de longitud n igual al número
máximo posible de estados. También como se asumió que la
máquina no presenta estados equivalentes, para dos estados
cualesquiera q1 y q2 existen secuencias de entrada que
generan distintas secuencias de salida.
Los procedimientos de identificación anteriormente
mencionados son los que generalmente se llevan a cabo en el
momento de enfrentarse a problemas de identificación de
dinámicas discretas. En la literatura que aborda este tema se
hace referencia a diversas técnicas de identificación de
máquinas de estados finitos, pero en el fondo todas parten del
mismo planteamiento y presentan las mismas restricciones.
Finalmente, cuando la salida de la máquina es independiente
de la entrada, se trata de una máquina de Moore, de lo
contrario se asume que la máquina se comporta como el
modelo de Mealy.
C. Computación Evolutiva
Bajo el término de Computación Evolutiva se engloba a un
amplio conjunto de técnicas de resolución de problemas
complejos basados en la emulación de los procesos naturales
de evolución [1, 3, 9, 10]. Es decir, la Computación Evolutiva
abarca los modelos computacionales que usan como elemento
clave algún mecanismo de la teoría de la evolución para su
diseño e implementación.
El principal aporte de la Computación Evolutiva a la
metodología de resolución de problemas consiste en el uso de
mecanismos de selección de soluciones potenciales y de
construcción de nuevos candidatos por recombinación de
características de otros ya presentes, de modo parecido a como
ocurre en la evolución de los organismos naturales.
A modo más específico, la Computación Evolutiva es un
enfoque alternativo para abordar problemas complejos de
búsqueda y aprendizaje a través de modelos computacionales
de procesos evolutivos. Las implementaciones concretas de
tales modelos se conocen como algoritmos evolutivos. El
propósito de los algoritmos evolutivos es guiar una búsqueda
estocástica haciendo evolucionar un conjunto de estructuras y
seleccionando de modo iterativo las más aptas. Un algoritmo
evolutivo se ejecuta sobre una población de individuos, que
representan a un conjunto de candidatos a soluciones de un
problema, dichos individuos son sometidos a una serie de
transformaciones con las que se actualiza la búsqueda y
después a un proceso de selección que favorece a los mejores
individuos. Cada ciclo de transformación-selección constituye
una generación. Se espera del algoritmo evolutivo que tras
cierto número de generaciones (iteraciones) el mejor
individuo esté razonablemente próximo a la solución buscada.
Los operadores evolutivos son los que realizan los
cambios de la población durante la ejecución de un algoritmo
evolutivo. Clásicamente, existen dos operadores genéticos:
mutación (Es un operador unario que simula el proceso
evolutivo que ocurre en los individuos cuando cambian su
estructura genética.) y cruce (Es un operador normalmente
binario, que permite representar el procesos de apareamiento
natural usando operaciones sencillas. toman diversos
componentes de distintos individuos para generar con ellos
nuevos individuos, de tal manera que hereden características
de sus padres). Sin embargo, han sido propuestos otros
operadores que se acoplan a problemas particulares, por
ejemplo: dominación, segregación, traslocación, inversión,
entre otros.
Los pasos de un algoritmo evolutivo son los siguientes:
• Generación de una población inicial, generalmente en
forma aleatoria.
• Evaluación de los individuos
• Selección de algunos individuos de la población, a través
de algún mecanismo.
• Modificación de los genes de los progenitores
seleccionados usando los operadores genéticos.
• Generación de una nueva población mediante algún
mecanismo de reemplazo.
• Verificación del criterio de parada del algoritmo, y se
regresa al paso 3, si es el caso.
Las principales técnicas de la Computación Evolutiva son
[1]: los algoritmos genéticos propuestos por Holland, las
estrategias evolutivas propuestas por Rochenberg y
Schwefel, la programación genética propuesta por Koza, y la
programación evolutiva propuesta por Fogel.
1) Programación evolutiva (EP)
La programación evolutiva fue originalmente concebida
por Lawrence J. Fogel en 1960 [1, 9, 10, 11] y consiste en un
mecanismo que hace evolucionar un conjunto de máquinas de
estados finitos. Esta técnica desarrolla un conjunto de
soluciones las cuales muestran un comportamiento óptimo con
respecto a un ambiente y a una función deseada.
A continuación se hace una explicación exhaustiva de como
la programación evolutiva hace evolucionar las máquinas de
estado finito.
• Población inicial (P(t)): Se comienza con una población
de máquinas de estados finitos que representan soluciones
al problema en cuestión.
• Evaluación: Cada máquina es evaluada por medio de una
función específica, que calcula la capacidad del individuo
para resolver el problema.