Download Práctica 4b - Universidad de Oviedo

Práctica 4b
Algoritmos Genéticos
En esta práctica vamos a ver un algoritmo genético implementado en MATLAB.
Veremos cómo es capaz de resolver el problema de las n-Reinas.
1 Genético para resolver las n-Reinas
Puede descargarse en: http://www.aic.uniovi.es/ssii/P4b/N-Reinas.zip
function [ FitnessMedio mejorFitness mejorIndividuo ] = GAnReinas2( nReinas ,...
NIND, MAXGEN, porcNewInd,pMutacion)
%GAnReinas2 Resulve el problema de las n-reinas con un genético
% Necesita:
%
nReinas: número de reinas
%
NIND: número de individuos de cada generación
%
MAXGEN: número máximo de generaciones
%
porcNewInd: porcentaje de nuevos individuos en la siguiente generación
%
porcMutacion: porcentaje de mutación
% Produce:
%
FitnessMedio: vector con el fitness medio de cada generación
%
mejorFitness: vector con el mejor fitness de cada generación
%
mejorIndividuo: matriz que contiene la representación del mejor
%
individuo de cada generación
% Representación:
%
Se utiliza un vector con tantas posiciones como columnas tiene el
%
tablero. Cada valor del vector indica la fila en la que se encuentra
%
la reina en esa columna.
%
% Implementado en 2005 para la asignatura Sistemas Inteligentes de Telecomunicaciones
% de E.P.S.I. de Gijon (universidad de Oviedo)
ValorObjetivo = sum(1:nReinas-1);
fprintf('ValorObjetivo: %d\n',ValorObjetivo);
% poblacion inicial
Poblacion = GeneraPoblacionInicial(NIND,nReinas,'GeneraPosicion2');
ObjV = EvaluaPoblacion(Poblacion,'EvaluaPosicion2');
% para el gráfico
close;
grid;
hold on;
axis([1 MAXGEN ValorObjetivo/2 ValorObjetivo]);
% inicializaciones
FinessMedio = zeros(MAXGEN,1);
mejorFitness = zeros(1,1);
mejorIndividuo = zeros(MAXGEN,nReinas);
gen = 0;
while ((gen < MAXGEN) & (max(mejorFitness) ~= ValorObjetivo)),
Poblacion = FormaNuevaPoblacion(Poblacion,ObjV,porcNewInd,'Ruleta',...
'CruzaPosicion2', 'MutaPosicion2',pMutacion);
ObjV = EvaluaPoblacion(Poblacion,'EvaluaPosicion2');
%Almacenar media del fitness y mejor individuo
mejor = find(ObjV==max(ObjV));
mejorFitness(gen+1) = ObjV(mejor(1));
mejorIndividuo(gen+1,:) = Poblacion(mejor(1),:);
FitnessMedio(gen+1) = mean(ObjV);
%incrementar el numero de generaciones
gen = gen + 1;
%actualizar gráfico
plot(mejorFitness,'-b');
plot(FitnessMedio,'-r');
if gen == 1
legend('Mejor Fitness', 'Media de la Poblacion');
end
drawnow;
end
hold off
val = PintaTablero( mejorIndividuo(gen,:),'EvaluaPosicion2')
En la página anterior se muestra la función principal del algoritmo genético:
1. se crea la población inicial
2. se evalúa dicha población
3. se genera una nueva población a partir de la anterior
4. se evalúa la nueva población
5. se repiten los pasos 3 y 4 hasta que se alcanza el número máximo de
generaciones o hasta que se alcanza el objetivo
Las funciones que tienen en el nombre “Poblacion” son funciones genéricas que
podrían utilizarse para resolver otro problema. El resto de funciones son específicas
para el problema de las n-Reinas.
Como todas las funciones tienen un comportamiento similar comentaremos únicamente
una de ellas:
Poblacion = GeneraPoblacionInicial(NIND,nReinas,'GeneraPosicion2');
Esta función se encarga de generar la población inicial. Para ello utiliza una función
específica del problema de las n-Reinas “GeneraPosicion2”, que se le pasa como
parámetro. Podemos implementar otra función para generar una posición y utilizarla:
Poblacion = GeneraPoblacionInicial(NIND,nReinas,'miPropiaFuncion');
Hay implementados dos métodos de selección:
1. Ruleta
2. Torneo
En la llamada a la función FormaNuevaPoblacion se debe indicar uno de los dos
métodos (si quieres puedes implementar más métodos☺).
Para ejecutarlo:
[ FitnessMedio mejorFitness mejorIndividuo ] = GAnReinas2( 10 , 50, 250, 0.97,0.1);
Siendo los parámetros en orden: número de reinas, número de individuos de cada
generación, número máximo de generaciones, porcentaje de nuevos individuos en la
siguiente generación y porcentaje de mutación.
Produce:
FitnessMedio: vector con el fitness medio de cada generación
mejorFitness: vector con el mejor fitness de cada generación
mejorIndividuo: matriz que contiene la representación del mejor individuo de cada
generación
Representación:
Se utiliza un vector con tantas posiciones como columnas tiene el tablero. Cada valor
del vector indica la fila en la que se encuentra la reina en esa columna.
También genera un gráfico que muestra la evolución de las sucesivas generaciones
(Figura 1).
Figura 1.- Ejemplo de gráfico de salida
[Trabajo] Jugar con los parámetros del algoritmo y con los métodos de selección para
estudiar la convergencia del algoritmo hacia la solución
2 Mejorando la solución
Piensa una manera de mejorar la convergencia del algoritmo cambiando la
representación de los individuos. Actualmente tenemos la siguiente representación:
[8
3 7 4 2 5 1 5]
Estamos permitiendo que dos reinas estén en la misma fila. Podríamos pensar en no
permitir eso, ya que los individuos (tableros) que están en esa situación son individuos
con ataques.
[Trabajo] Trata de modificar el genético para que se adapte a la nueva representación.
Crea las funciones que consideres necesarias
Si no eres capaz de adaptarlo, en http://www.aic.uniovi.es/ssii/P4b/N-Reinas-Mejor.zip
puedes descargarte las funciones necesarias para adaptarse a esta nueva representación.
Descomprímelas en directorio en que estás trabajando.