经验教训：遗传算法入门

using System;

namespace L2L_I2GA
{
    // Class that represents the Specimen
    public class Specimen
    {
        // The genes
        public double[] Genes;

        // Affinity to the solution
        public double Affinity;

        // Constructor that creates the Specimen
        // instance with initial genes
        public Specimen()
        {
            // Assume one double value as the genes
            Genes = new double[1];

            // Set up initial value to the genes
            Genes[0] = 10;
        }

        // Calculates affinity of this instance to the solution
        // Contains the equation formula
        public void CalculateAffinity()
        {
            double s1 = Math.Pow(Genes[0], 5) * 19.39281272;
            double s2 = Math.Pow(Genes[0], 4) *  7.82018991;
            double s3 = Math.Pow(Genes[0], 3) * 35.12849546;
            double s4 = Math.Pow(Genes[0], 2) * 28.09127103;
            double s5 = Genes[0] * 3.30129489;

            double f = s1 + s2 + s3 - s4 + s5;

            // Need positive value to evaluate proximity
            // 0 is the best value
            Affinity = Math.Abs(f - 20351.07006276);
        }
    }
}

// Class that represents the Specimen
public class Specimen
{
    // The genes
    public double[] Genes;

    // Affinity to the solution
    public double Affinity;

    // Constructor that creates the Specimen
    // instance with initial genes
    public Specimen()
    {
        // Assume one double value as the genes
        Genes = new double[1];

        // Set up initial value to the genes
        Genes[0] = 10;
    }

    // Calculates affinity of this instance to the solution
    // Contains the equation formula
    public void CalculateAffinity()
    {
        double s1 = Math.pow(Genes[0], 5) * 19.39281272;
        double s2 = Math.pow(Genes[0], 4) *  7.82018991;
        double s3 = Math.pow(Genes[0], 3) * 35.12849546;
        double s4 = Math.pow(Genes[0], 2) * 28.09127103;
        double s5 = Genes[0] * 3.30129489;

        double f = s1 + s2 + s3 - s4 + s5;

        // Need positive value to evaluate proximity
        // 0 is the best value
        Affinity = Math.abs(f - 20351.07006276);
    }
}

#ifndef H_SPECIMEN
#define H_SPECIMEN

// Class that represents the Specimen
class Specimen
{
public:
    // The genes
    double* Genes;

    // Affinity to the solution
    double Affinity;

    // Constructor that creates the Specimen
    // instance with initial genes
    Specimen();

    // Destructor. Frees memory for the Genes
    ~Specimen();

    // Clone the Specimen for simple memory management
    Specimen* Clone();

    // Calculates affinity of this instance to the solution
    // Contains the equation formula
    void CalculateAffinity();
};

#include "Specimen.h"
#include <math.h>
#include <cmath>

// Constructor that creates the Specimen
// instance with initial genes
Specimen::Specimen()
{
    // Assume one double value as the genes
    Genes = new double[1];

    // Set up initial value to the genes
    Genes[0] = 10;
}

// Destructor. Frees memory for the Genes
Specimen::~Specimen()
{
    delete[] Genes;
}

// Clone the Specimen for simple memory management
Specimen* Specimen::Clone()
{
    Specimen* s = new Specimen();
    s->Genes[0] = Genes[0];
    s->Affinity = Affinity;

    return s;
}

// Calculates affinity of this instance to the solution
// Contains the equation formula
void Specimen::CalculateAffinity()
{
    double s1 = pow(Genes[0], 5) * 19.39281272;
    double s2 = pow(Genes[0], 4) *  7.82018991;
    double s3 = pow(Genes[0], 3) * 35.12849546;
    double s4 = pow(Genes[0], 2) * 28.09127103;
    double s5 = Genes[0] * 3.30129489;

    double f = s1 + s2 + s3 - s4 + s5;

    // Need positive value to evaluate proximity
    // 0 is the best value
    Affinity = std::abs(f - 20351.07006276);
}

using System;

namespace L2L_I2GA
{
    // Class that performs main actions with the specimens and the population
    public static class SpecimenWorkshop
    {
        // Random generator
        static Random rnd = new Random();

        // Number of specimens in the population
        public static int PopulationSize;

        // Number of specimens in the selection 
        public static int SelectionSize;

        // Power of mutations
        // 0 - no mutations
        // 100 - mutations up to whole gene value
        // 200 - mutations up to twice gene value
        public static double MaxMutationPercent;

        // Likelihood of mutation
        // 0 - no mutations, 100 - mutations for all cases
        public static int MutationLikelyhoodPercent;

        // Maximal affinity that is considered 
        // for the solution found
        public static double Epsilon;

        // Generate initial population
        public static Specimen[] GeneratePopulation()
        {
            // Creates array representing the population
            Specimen[] p = new Specimen[PopulationSize];

            // Creates specimens
            // Mutation of all specimens in initial population
            // increases variance that increases chance to
            // get better instance.
            for (int i = 0; i < PopulationSize; i++)
            {
                p[i] = new Specimen();
                Mutate(p[i]);

                // Calculate Affinity for new specimens
                p[i].CalculateAffinity();
            }

            return p;
        }

        // Generate population by reproduction of selection
        public static Specimen[] GeneratePopulation(Specimen[] selection)
        {
            // Creates array representing the population
            Specimen[] p = new Specimen[PopulationSize];

            // Copy instances from the selection to keep them
            // in new generation of population
            for (int i = 0; i < SelectionSize; i++)
            {
                p[i] = selection[i];
            }

            // Creates new specimens by reproducing two parents
            // Parents are selected randomly from the selection.
            int chield_index = SelectionSize;
            int parent1_index;
            int parent2_index;

            while(chield_index < PopulationSize)
            {
                // Select two parents randomly in way
                // they are different instances
                do
                {
                    parent1_index = rnd.Next(selection.Length);
                    parent2_index = rnd.Next(selection.Length);
                } while (parent1_index == parent2_index);

                // Creates new specimen
                p[chield_index] = ReproduceNew(
                          selection[parent1_index], 
                          selection[parent2_index]);

                chield_index++;
            }

            return p;
        }

        // Reproduce new specimen on base of two parents
        public static Specimen ReproduceNew(Specimen a, Specimen b)
        {
            Specimen s= new Specimen();

            // Inherit genes as the average oh the parents' genes
            s.Genes[0] = (a.Genes[0] + b.Genes[0]) / 2;

            // Mutate if likelihood allows
            int ml = rnd.Next(101);
            if (ml <= MutationLikelyhoodPercent)
            {
                Mutate(s);
            }

            // Calculate Affinity for new specimen
            s.CalculateAffinity();

            return s;
        }

        // Select the best specimens from the population
        public static Specimen[] Select(Specimen[] population)
        {
            // Sort population by increasing the affinity
            // The best specimens are moving to start of the array
            Sort(population);

            // Create set of selected specimens
            Specimen[] selected = new Specimen[SelectionSize];

            // Copy best specimens into the selection
            for (int i = 0; i < SelectionSize; i++)
            {
                selected[i] = population[i];
            }

            return selected;
        }

        // Sort the population
        public static void Sort(Specimen[] population)
        {
            // Use standard procedure
            Array.Sort<specimen>(population, CompareSpecimens);
        }

        // Comparison function for the standard Sort procedure
        public static int CompareSpecimens(Specimen a, Specimen b)
        {
            if(a.Affinity < b.Affinity)
            {
                return -1;
            } else
            if (a.Affinity > b.Affinity)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }

        // Mutate the specimen
        public static void Mutate(Specimen sp)
        {
            // Calculate Mutation Factor that is random value between 0 and MaxMutationPercent
            // calculates as ratio between 0 and 1
            double MutationFactor = (MaxMutationPercent / 100.0) * (rnd.Next(1001) / 1000.0);

            // Set mutation to negative with 50% likelihood
            if (rnd.Next(10) < 5)
            {
                MutationFactor = -MutationFactor;
            }

            // Calculate new gene
            sp.Genes[0] = sp.Genes[0] * (1 + MutationFactor);
        }
    }
}

import java.util.Random;

// Class that performs main actions with the specimens and the population
public class SpecimenWorkshop
{
    // Random generator
    static Random rnd = new Random();

    // Number of specimens in the population
    public static int PopulationSize;

    // Number of specimens in the selection 
    public static int SelectionSize;

    // Power of mutations
    // 0 - no mutations
    // 100 - mutations up to whole gene value
    // 200 - mutations up to twice gene value
    public static double MaxMutationPercent;

    // Likelihood of mutation
    // 0 - no mutations, 100 - mutations for all cases
    public static int MutationLikelyhoodPercent;

    // Maximal affinity that is considered 
    // for the solution found
    public static double Epsilon;

    // Generate initial population
    public static Specimen[] GeneratePopulation()
    {
        // Creates array representing the population
        Specimen[] p = new Specimen[PopulationSize];

        // Creates specimens
        // Mutation of all specimens in initial population
        // increases variance that increases chance to
        // get better instance.
        for (int i = 0; i < PopulationSize; i++)
        {
            p[i] = new Specimen();
            Mutate(p[i]);

            // Calculate Affinity for new specimens
            p[i].CalculateAffinity();
        }

        return p;
    }

    // Generate population by reproduction of selection
    public static Specimen[] GeneratePopulation(Specimen[] selection)
    {
        // Creates array representing the population
        Specimen[] p = new Specimen[PopulationSize];

        // Copy instances from the selection to keep them
        // in new generation of population
        for (int i = 0; i < SelectionSize; i++)
        {
            p[i] = selection[i];
        }

        // Creates new specimens by reproducing two parents
        // Parents are selected randomly from the selection.
        int chield_index = SelectionSize;
        int parent1_index;
        int parent2_index;

        while(chield_index < PopulationSize)
        {
            // Select two parents randomly in way
            // they are different instances
            do
            {
                parent1_index = rnd.nextInt(selection.length);
                parent2_index = rnd.nextInt(selection.length);
            } while (parent1_index == parent2_index);

            // Creates new specimen
            p[chield_index] = ReproduceNew(selection[parent1_index], selection[parent2_index]);

            chield_index++;
        }

        return p;
    }

    // Reproduce new specimen on base of two parents
    public static Specimen ReproduceNew(Specimen a, Specimen b)
    {
        Specimen s= new Specimen();

        // Inherit genes as the average oh the parents' genes
        s.Genes[0] = (a.Genes[0] + b.Genes[0]) / 2;

        // Mutate if likelihood allows
        int ml = rnd.nextInt(101);
        if (ml <= MutationLikelyhoodPercent)
        {
            Mutate(s);
        }

        // Calculate Affinity for new specimen
        s.CalculateAffinity();

        return s;
    }

    // Select the best specimens from the population
    public static Specimen[] Select(Specimen[] population)
    {
        // Sort population by increasing the affinity
        // The best specimens are moving to start of the array
        Sort(population);

        // Create set of selected specimens
        Specimen[] selected = new Specimen[SelectionSize];

        // Copy best specimens into the selection
        for (int i = 0; i < SelectionSize; i++)
        {
            selected[i] = population[i];
        }

        return selected;
    }

    // Sort the population
    public static void Sort(Specimen[] population)
    {
        Specimen temp;

        for (int i = 0; i < PopulationSize; i++)
        {
        	for (int j = 0; j < PopulationSize; j++)
        	{
        		if (population[i].Affinity < population[j].Affinity)
        		{
        			temp = population[i];
        			population[i] = population[j];
        			population[j] = temp;
        		}
        	}
        }        	
    }

    // Mutate the specimen
    public static void Mutate(Specimen sp)
    {
        // Calculate Mutation Factor that is random value between 0 and MaxMutationPercent
        // calculates as ratio between 0 and 1
        double MutationFactor = (MaxMutationPercent / 100.0) * (rnd.nextInt(1001) / 1000.0);

        // Set mutation to negative with 50% likelihood
        if (rnd.nextInt(10) < 5)
        {
            MutationFactor = -MutationFactor;
        }

        // Calculate new gene
        sp.Genes[0] = sp.Genes[0] * (1 + MutationFactor);
    }
}

#ifndef H_SPECIMENWORKSHOP
#define H_SPECIMENWORKSHOP

#include "Specimen.h"

// Class that performs main actions with the specimens and the population
class SpecimenWorkshop
{
public:

	// Number of specimens in the population
	static int PopulationSize;

	// Number of specimens in the selection 
	static int SelectionSize;

	// Power of mutations
	// 0 - no mutations
	// 100 - mutations up to whole gene value
	// 200 - mutations up to twice gene value
	static double MaxMutationPercent;

	// Likelihood of mutation
	// 0 - no mutations, 100 - mutations for all cases
	static int MutationLikelyhoodPercent;

	// Maximal affinity that is considered 
	// for the solution found
	static double Epsilon;

	// Generate initial population
	static Specimen** GeneratePopulation();

	// Generate population by reproduction of selection
	static Specimen** GeneratePopulation(Specimen** selection);

	// Reproduce new specimen on base of two parents
	static Specimen* ReproduceNew(Specimen* a, Specimen* b);

	// Select the best specimens from the population
	static Specimen** SpecimenWorkshop::Select(Specimen** population);

	// Sort the population
	static void SpecimenWorkshop::Sort(Specimen** population);

	// Mutate the specimen
	static void SpecimenWorkshop::Mutate(Specimen* sp);
};

#endif

#include "SpecimenWorkshop.h"
#include <stdlib.h>

// Number of specimens in the population
int SpecimenWorkshop::PopulationSize;

// Number of specimens in the selection 
int SpecimenWorkshop::SelectionSize;

// Power of mutations
// 0 - no mutations
// 100 - mutations up to whole gene value
// 200 - mutations up to twice gene value
double SpecimenWorkshop::MaxMutationPercent;

// Likelihood of mutation
// 0 - no mutations, 100 - mutations for all cases
int SpecimenWorkshop::MutationLikelyhoodPercent;

// Maximal affinity that is considered 
// for the solution found
double SpecimenWorkshop::Epsilon;

// Generate initial population
Specimen** SpecimenWorkshop::GeneratePopulation()
{
	// Creates array representing the population
	Specimen** p = new Specimen*[PopulationSize];

	// Creates specimens
	// Mutation of all specimens in initial population
	// increases variance that increases chance to
	// get better instance.
	for (int i = 0; i < PopulationSize; i++)
	{
		p[i] = new Specimen();
		Mutate(p[i]);

		// Calculate Affinity for new specimens
		p[i]->CalculateAffinity();
	}

	return p;
}

// Generate population by reproduction of selection
Specimen** SpecimenWorkshop::GeneratePopulation(Specimen** selection)
{
	// Creates array representing the population
	Specimen** p = new Specimen*[PopulationSize];

	// Copy instances from the selection to keep them
	// in new generation of population
	for (int i = 0; i < SelectionSize; i++)
	{
		p[i] = selection[i]->Clone();
	}

	// Creates new specimens by reproducing two parents
	// Parents are selected randomly from the selection.
	int chield_index = SelectionSize;
	int parent1_index;
	int parent2_index;

	while (chield_index < PopulationSize)
	{
		// Select two parents randomly in way
		// they are different instances
		do
		{
			parent1_index = rand() % SelectionSize;
			parent2_index = rand() % SelectionSize;
		} while (parent1_index == parent2_index);

		// Creates new specimen
		p[chield_index] = ReproduceNew(selection[parent1_index], selection[parent2_index]);

		chield_index++;
	}

	return p;
}

// Reproduce new specimen on base of two parents
Specimen* SpecimenWorkshop::ReproduceNew(Specimen* a, Specimen* b)
{
	Specimen* s = new Specimen();

	// Inherit genes as the average oh the parents' genes
	s->Genes[0] = (a->Genes[0] + b->Genes[0]) / 2;

	// Mutate if likelihood allows
	int ml = rand() % 101;
	if (ml <= MutationLikelyhoodPercent)
	{
		Mutate(s);
	}

	// Calculate Affinity for new specimen
	s->CalculateAffinity();

	return s;
}

// Select the best specimens from the population
Specimen** SpecimenWorkshop::Select(Specimen** population)
{
	// Sort population by increasing the affinity
	// The best specimens are moving to start of the array
	Sort(population);

	// Create set of selected specimens
	Specimen** selected = new Specimen*[SelectionSize];

	// Copy best specimens into the selection
	for (int i = 0; i < SelectionSize; i++)
	{
		selected[i] = population[i]->Clone();
	}

	return selected;
}

// Sort the population
void SpecimenWorkshop::Sort(Specimen** population)
{
	Specimen* temp;

	for (int i = 0; i < PopulationSize; i++)
	{
		for (int j = 0; j < PopulationSize; j++)
		{
			if (population[i]->Affinity < population[j]->Affinity)
			{
				temp = population[i];
				population[i] = population[j];
				population[j] = temp;
			}
		}
	}
}

// Mutate the specimen
void SpecimenWorkshop::Mutate(Specimen* sp)
{
	// Calculate Mutation Factor that is random value between 0 and MaxMutationPercent
	// calculates as ratio between 0 and 1
	double MutationFactor = (MaxMutationPercent / 100.0) * (rand() % 1001 / 1000.0);

	// Set mutation to negative with 50% likelihood
	if ((rand() % 10) < 5)
	{
		MutationFactor = -MutationFactor;
	}

	// Calculate new gene
	sp->Genes[0] = sp->Genes[0] * (1 + MutationFactor);
}

</stdlib.h>

using System;

namespace L2L_I2GA
{
    // Class that implements the Genetic Algorithm
    // at the highest abstraction level
    public static class Solver
    {
        // Current Population
        static Specimen[] Current_Population;

        // Current Selection
        static Specimen[] Current_Selection;

        // Current Proximity
        static double Current_Proximity;

        // Current Iteration
        static int Current_Iteration;

        // Initialize the algorithm
        public static void Initialize()
        {
            // Set up options for the algorithm
            SpecimenWorkshop.PopulationSize = 10000;
            SpecimenWorkshop.SelectionSize = 1000;
            SpecimenWorkshop.MaxMutationPercent = 500;
            SpecimenWorkshop.MutationLikelyhoodPercent = 90;
            SpecimenWorkshop.Epsilon = 0.000000001;

            // Generate initial population
            Current_Population = SpecimenWorkshop.GeneratePopulation();
            Current_Iteration = 0;
        }

        // Run the algorithm
        public static void Run()
        {
            // Set Current_Proximity to the biggest value
            Current_Proximity = double.MaxValue;

            // Loop while Current_Proximity is not less than the Epsilon
            while (SpecimenWorkshop.Epsilon <= Current_Proximity)
            {
                // Select the best specimens
                Current_Selection = SpecimenWorkshop.Select(Current_Population);

                // Calculate proximity for the top-selected (the best) specimen
                Current_Proximity = Current_Selection[0].Affinity;

                // Report proximity and found solution for the current iteration
                Console.WriteLine(
                                         "{0}\t{1}\t{2}",
                                         Current_Iteration,
                                         Current_Proximity,
                                         Current_Selection[0].Genes[0]);

                // End the calculations if Current_Proximity is less than the Epsilon
                if (Current_Proximity < SpecimenWorkshop.Epsilon)
                {
                    break;
                }

                // Generate new population by reproducing specimens from the selection
                Current_Population =
                                     SpecimenWorkshop.GeneratePopulation(Current_Selection);

                Current_Iteration++;                
            }
        }
    }
}

// Class that implements the Genetic Algorithm
// at the highest abstraction level
public class Solver
{
    // Current Population
    static Specimen[] Current_Population;

    // Current Selection
    static Specimen[] Current_Selection;

    // Current Proximity
    static double Current_Proximity;

    // Current Iteration
    static int Current_Iteration;

    // Initialize the algorithm
    public static void Initialize()
    {
        // Set up options for the algorithm
        SpecimenWorkshop.PopulationSize = 10000;
        SpecimenWorkshop.SelectionSize = 1000;
        SpecimenWorkshop.MaxMutationPercent = 500;
        SpecimenWorkshop.MutationLikelyhoodPercent = 90;
        SpecimenWorkshop.Epsilon = 0.000000001;

        // Generate initial population
        Current_Population = SpecimenWorkshop.GeneratePopulation();
        Current_Iteration = 0;
    }

    // Run the algorithm
    public static void Run()
    {
        // Set Current_Proximity to the biggest value
        Current_Proximity = Double.MAX_VALUE;

        // Loop while Current_Proximity is not less than the Epsilon
        while (SpecimenWorkshop.Epsilon <= Current_Proximity)
        {
            // Select the best specimens
            Current_Selection = SpecimenWorkshop.Select(Current_Population);

            // Calculate proximity for the top-selected (the best) specimen
            Current_Proximity = Current_Selection[0].Affinity;

            // Report proximity and found solution for the current iteration
            System.out.println(
             		Current_Iteration + "\t" + 
                    Current_Proximity + "\t" + 
              		Current_Selection[0].Genes[0]);

            // End the calculations if Current_Proximity is less than the Epsilon
            if (Current_Proximity < SpecimenWorkshop.Epsilon)
            {
                break;
            }

            // Generate new population by reproducing specimens from the selection
            Current_Population = SpecimenWorkshop.GeneratePopulation(Current_Selection);

            Current_Iteration++;                
        }
    }
}

#ifndef H_SOLVER
#define H_SOLVER

#include "Specimen.h"

// Class that implements the Genetic Algorithm
// at the highest abstraction level
class Solver
{
public:
	// Current Population
	static Specimen** Current_Population;

	// Current Selection
	static Specimen** Current_Selection;

	// Current Proximity
	static double Current_Proximity;

	// Current Iteration
	static int Current_Iteration;

	static void Solver::Initialize();
	
	static void Solver::Run();
};

#endif

#include "Solver.h"
#include "SpecimenWorkshop.h"
#include <iostream>

// Current Population
Specimen** Solver::Current_Population;

// Current Selection
Specimen** Solver::Current_Selection;

// Current Proximity
double Solver::Current_Proximity;

// Current Iteration
int Solver::Current_Iteration;

// Initialize the algorithm
void Solver::Initialize()
{
	// Set up options for the algorithm
	SpecimenWorkshop::PopulationSize = 10000;
	SpecimenWorkshop::SelectionSize = 1000;
	SpecimenWorkshop::MaxMutationPercent = 500;
	SpecimenWorkshop::MutationLikelyhoodPercent = 90;
	SpecimenWorkshop::Epsilon = 0.000000001;

	// Generate initial population
	Current_Population = SpecimenWorkshop::GeneratePopulation();

	// Set Current_Selection to zero for correct work delete[] operator
	Current_Selection = 0;

	Current_Iteration = 0;
}

// Run the algorithm
void Solver::Run()
{
	// Set Current_Proximity to the biggest value
	Current_Proximity = 1.7976931348623157E+308;

	// Loop while Current_Proximity is not less than the Epsilon
	while (SpecimenWorkshop::Epsilon <= Current_Proximity)
	{
		// Delete old selection
		if (Current_Selection != 0)
		{
			for (int i = 0; i < SpecimenWorkshop::SelectionSize; i++)
			{
				// Calculate Affinity for new specimens
				delete Current_Selection[i];
			}

			delete[] Current_Selection;
		}

		// Select the best specimens
		Current_Selection = SpecimenWorkshop::Select(Current_Population);

		// Calculate proximity for the top-selected (the best) specimen
		Current_Proximity = Current_Selection[0]->Affinity;

		// Report proximity and found solution for the current iteration
		std::cout << Current_Iteration << '\t';
		std::cout << Current_Proximity << '\t';
		std::cout << Current_Selection[0]->Genes[0] << '\t' << std::endl;;

		// End the calculations if Current_Proximity is less than the Epsilon
		if (Current_Proximity < SpecimenWorkshop::Epsilon)
		{
			break;
		}

		// Delete old population
		for (int i = 0; i < SpecimenWorkshop::PopulationSize; i++)
		{
			// Calculate Affinity for new specimens
			delete Current_Population[i];
		}

		delete[] Current_Population;

		// Generate new population by reproducing specimens from the selection
		Current_Population = SpecimenWorkshop::GeneratePopulation(Current_Selection);

		Current_Iteration++;
	}
}
</iostream>

using System;

namespace L2L_I2GA
{
    class Program
    {
        static void Main(string[] args)
        {
            Solver.Initialize();
            Solver.Run();

            Console.WriteLine("Press Enter to exit.");
            Console.ReadLine();
        }
    }
}

import java.io.IOException;

public class Program {

    public static void main(String[] args) throws IOException {
        Solver.Initialize();
        Solver.Run();

		System.out.println("Press Enter to exit.");
		System.in.read();
    }
}

#include <iostream>
#include "Solver.h"

int main()
{
	Solver::Initialize();
	Solver::Run();

	std::cout << "Press Enter to exit." << std::endl;
	std::cin.ignore(100000, '\n');
    return 0;
}
</iostream>