Задание:
Написать программу на языке высокого уровня, который реализует работу А. Обеспечить возможность задания входных параметров и отражения результата.
Краткие теоретические сведения:
Генетические алгоритмы - популярные методы решения задач оптимизации. Они используют эволюционные принципы для поиска оптимального решения. Параметры задачи являются генетическим материалом. Совокупность генов складывает хромосому.
Текст программы:
1. Text.cs
using System;
using btl.generic;
public class Test
{
// optimal solution for this is (0.5,0.5)
public static double theActualFunction(double[] values)
{
if (values.GetLength(0) != 2)
throw new ArgumentOutOfRangeException("should only have 2 args");
double x = values[0];
double y = values[1];
double n = 9; // should be an int, but I don't want to waste time casting.
double f1 = Math.Sin(n*Math.PI*x)*Math.Sin(2*n*Math.PI*y);
return f1;
}
public static void Main()
{
// Crossover = 80%
// Mutation = 5%
// Population size = 100
// Generations = 2000
// Genome size = 2
GA ga = new GA(0.8,0.05,2,5,2);
ga.FitnessFunction = new GAFunction(theActualFunction);
//ga.FitnessFile = @"H:\fitness.csv";
ga.Elitism = true;
ga.Go();
double[] values;
double fitness;
ga.GetBest(out values, out fitness);
System.Console.WriteLine("Best ({0}):", fitness);
for (int i = 0 ; i < values.Length ; i++)
System.Console.WriteLine("{0} ", values[i]);
ga.GetWorst(out values, out fitness);
System.Console.WriteLine("\nWorst ({0}):", fitness);
for (int i = 0 ; i < values.Length ; i++)
System.Console.WriteLine("{0} ", values[i]);
}
}
2. GA.cs
using System;
using System.Collections;
using System.IO;
namespace btl.generic
{
public delegate double GAFunction(double[] values);
/// <summary>
/// Genetic Algorithm class
/// </summary>
public class GA
{
/// <summary>
/// Default constructor sets mutation rate to 5%, crossover to 80%, population to 100,
/// and generations to 2000.
/// </summary>
public GA()
{
InitialValues();
m_mutationRate = 0.05;
m_crossoverRate = 0.80;
m_populationSize = 100;
m_generationSize = 2000;
m_strFitness = "";
}
public GA(double crossoverRate, double mutationRate, int populationSize, int generationSize, int genomeSize)
{
InitialValues();
m_mutationRate = mutationRate;
m_crossoverRate = crossoverRate;
m_populationSize = populationSize;
m_generationSize = generationSize;
m_genomeSize = genomeSize;
m_strFitness = "";
}
public GA(int genomeSize)
{
InitialValues();
m_genomeSize = genomeSize;
}
public void InitialValues()
{
m_elitism = false;
}
/// <summary>
/// Method which starts the GA executing.
/// </summary>
public void Go()
{
if (getFitness == null)
throw new ArgumentNullException("Need to supply fitness function");
if (m_genomeSize == 0)
throw new IndexOutOfRangeException("Genome size not set");
// Create the fitness table.
m_fitnessTable = new ArrayList();
m_thisGeneration = new ArrayList(m_generationSize);
m_nextGeneration = new ArrayList(m_generationSize);
Genome.MutationRate = m_mutationRate;
CreateGenomes();
RankPopulation();
StreamWriter outputFitness = null;
bool write = false;
if (m_strFitness != "")
{
write = true;
outputFitness = new StreamWriter(m_strFitness);
}
for (int i = 0; i < m_generationSize; i++)
{
CreateNextGeneration();
RankPopulation();
if (write)
{
if (outputFitness != null)
{
double d = (double)((Genome)m_thisGeneration[m_populationSize-1]).Fitness;
outputFitness.WriteLine("{0},{1}",i,d);
}
}
}
if (outputFitness != null)
outputFitness.Close();
}
/// <summary>
/// After ranking all the genomes by fitness, use a 'roulette wheel' selection
/// method. This allocates a large probability of selection to those with the
/// highest fitness.
/// </summary>
/// <returns>Random individual biased towards highest fitness</returns>
private int RouletteSelection()
{
double randomFitness = m_random.NextDouble() * m_totalFitness;
int idx = -1;
int mid;
int first = 0;
int last = m_populationSize -1;
mid = (last - first)/2;
// ArrayList's BinarySearch is for exact values only
// so do this by hand.
while (idx == -1 && first <= last)
{
if (randomFitness < (double)m_fitnessTable[mid])
{
last = mid;
}
else if (randomFitness > (double)m_fitnessTable[mid])
{
first = mid;
}
mid = (first + last)/2;
// lies between i and i+1
if ((last - first) == 1)
idx = last;
}
return idx;
}
/// <summary>
/// Rank population and sort in order of fitness.
/// </summary>
private void RankPopulation()
{
m_totalFitness = 0;
for (int i = 0; i < m_populationSize; i++)
{
Genome g = ((Genome) m_thisGeneration[i]);
g.Fitness = FitnessFunction(g.Genes());
m_totalFitness += g.Fitness;
}
m_thisGeneration.Sort(new GenomeComparer());
// now sorted in order of fitness.
double fitness = 0.0;
m_fitnessTable.Clear();
for (int i = 0; i < m_populationSize; i++)
{
fitness += ((Genome)m_thisGeneration[i]).Fitness;
m_fitnessTable.Add((double)fitness);
}
}
/// <summary>
/// Create the *initial* genomes by repeated calling the supplied fitness function
/// </summary>
private void CreateGenomes()
{
for (int i = 0; i < m_populationSize ; i++)
{
Genome g = new Genome(m_genomeSize);
m_thisGeneration.Add(g);
}
}
private void CreateNextGeneration()
{
m_nextGeneration.Clear();
Genome g = null;
if (m_elitism)
g = (Genome)m_thisGeneration[m_populationSize - 1];
for (int i = 0 ; i < m_populationSize ; i+=2)
{
int pidx1 = RouletteSelection();
int pidx2 = RouletteSelection();
Genome parent1, parent2, child1, child2;
parent1 = ((Genome) m_thisGeneration[pidx1]);
parent2 = ((Genome) m_thisGeneration[pidx2]);
if (m_random.NextDouble() < m_crossoverRate)
{
parent1.Crossover(ref parent2, out child1, out child2);
}
else
{
child1 = parent1;
child2 = parent2;
}
child1.Mutate();
child2.Mutate();
m_nextGeneration.Add(child1);
m_nextGeneration.Add(child2);
}
if (m_elitism && g != null)
m_nextGeneration[0] = g;
m_thisGeneration.Clear();
for (int i = 0 ; i < m_populationSize; i++)
m_thisGeneration.Add(m_nextGeneration[i]);
}
private double m_mutationRate;
private double m_crossoverRate;
private int m_populationSize;
private int m_generationSize;
private int m_genomeSize;
private double m_totalFitness;
private string m_strFitness;
private bool m_elitism;
private ArrayList m_thisGeneration;
private ArrayList m_nextGeneration;
private ArrayList m_fitnessTable;
static Random m_random = new Random();
static private GAFunction getFitness;
public GAFunction FitnessFunction
{
get
{
return getFitness;
}
set
{
getFitness = value;
}
}
// Properties
public int PopulationSize
{
get
{
return m_populationSize;
}
set
{
m_populationSize = value;
}
}
public int Generations
{
get
{
return m_generationSize;
}
set
{
m_generationSize = value;
}
}
public int GenomeSize
{
get
{
return m_genomeSize;
}
set
{
m_genomeSize = value;
}
}
public double CrossoverRate
{
get
{
return m_crossoverRate;
}
set
{
m_crossoverRate = value;
}
}
public double MutationRate
{
get
{
return m_mutationRate;
}
set
{
m_mutationRate = value;
}
}
public string FitnessFile
{
get
{
return m_strFitness;
}
set
{
m_strFitness = value;
}
}
/// <summary>
/// Keep previous generation's fittest individual in place of worst in current
/// </summary>
public bool Elitism
{
get
{
return m_elitism;
}
set
{
m_elitism = value;
}
}
public void GetBest(out double[] values, out double fitness)
{
Genome g = ((Genome)m_thisGeneration[m_populationSize-1]);
values = new double[g.Length];
g.GetValues(ref values);
fitness = (double)g.Fitness;
}
public void GetWorst(out double[] values, out double fitness)
{
GetNthGenome(0, out values, out fitness);
}
public void GetNthGenome(int n, out double[] values, out double fitness)
{
if (n < 0 || n > m_populationSize-1)
throw new ArgumentOutOfRangeException("n too large, or too small");
Genome g = ((Genome)m_thisGeneration[n]);
values = new double[g.Length];
g.GetValues(ref values);
fitness = (double)g.Fitness;
}
}
}
