geneticalgorithm.cs

genetic algorithm source code, C# environment, and good, for beginners learning

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Drawing;
namespace GATest
{
    /// <summary>
    /// 简单的遗传算法实例
    /// 段旭良
    /// [e-mail]
    /// 2007-12
    /// </summary>
    class GeneticAlgorithm
    {
        private const double PI = 3.1415926535897932384;
        private double m_minValue;
        private double m_maxValue;
        private double m_length;
        private int m_codingLength;
        private int m_populationNumber;//种群大小
        private string[][] m_populations;//种群
        private double[] m_doublePopulation;
        private double[] m_fitness;
        private double m_crossRate;
        private double m_varRate;
        private double m_winFitness;
        private PointF[] m_DrawPoints;

        public PointF[] DrawPoints
        {
            get { return m_DrawPoints; }
            set { m_DrawPoints = value; }
        }
        public double WinFitness
        {
            get { return m_winFitness; }
            set { m_winFitness = value; }
        }
        private string[] m_winCoding;
        public string[] WinCoding
        {
            get { return m_winCoding; }
            set { m_winCoding = value; }
        }
        private double m_winValue;
        public double WinValue
        {
            get { return m_winValue; }
            set { m_winValue = value; }
        }
        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="min">变量取值范围-最小值</param>
        /// <param name="max">变量取值范围-最大</param>
        /// <param name="crossRate">交叉概率</param>
        /// <param name="varRate">变异概率</param>
        /// <param name="precision">精度，6表示小数点后6位</param>
        /// <param name="populationNumber">种群大小</param>
        /// <param name="picWidth">绘图的宽度</param>
        /// <param name="picHeight">绘图高度</param>
        public GeneticAlgorithm(double min, double max, double crossRate, double varRate, int precision, int populationNumber,int picWidth,int picHeight)
        {
            m_maxValue = max;
            m_minValue = min;
            m_crossRate = crossRate;
            m_varRate = varRate;
            m_populationNumber = populationNumber;
            m_length = max - min;
            m_populations = new string[m_populationNumber][];
            m_doublePopulation = new double[m_populationNumber];
            m_fitness = new double[m_populationNumber];
            m_codingLength = GetCodingLength(min, max, precision);//取得编码长度
            InitDrawPoints(picWidth, picHeight);
            InitPopulation();
        }
        /// <summary>
        /// 画点
        /// </summary>
        /// <param name="width">画板宽度</param>
        /// <param name="height">画板高度</param>
        private void InitDrawPoints(int width, int height)
        {
            int pointNumber = width;
            double length = (m_maxValue - m_minValue) / (double)pointNumber;
            double x = m_minValue;
            double y = 0.0d;
            m_DrawPoints = new PointF[pointNumber];
            for (int i = 0; i < pointNumber; i++)
            {
                m_DrawPoints[i].X = (float)i;
                y = x * Math.Sin(10.0 * PI * x) + 2.0;
                m_DrawPoints[i].Y = (float)height - (float)68.0 * (float)y;
                x += length;
            }
        }
        /// <summary>
        /// 进行遗传操作
        /// </summary>
        public void DoEvaluation()
        {
            ConvertIndivadual2Double();
            ComputeFitness();
            ComputeWins();
            Selection();
            Crossing();
            Mutation();
        }
        /// <summary>
        /// 根据适应度计算获胜
        /// </summary>
        private void ComputeWins()
        {
            int[] indexs = new int[m_populationNumber];
            for (int i = 0; i < m_populationNumber; i++)
            {
                indexs[i] = i;
            }
            int winIndex = GetMaxIndex(indexs);
            m_winCoding = m_populations[winIndex];
            m_winValue = m_doublePopulation[winIndex];
            m_winFitness = m_fitness[winIndex];
        }
        public int IndivadualNumber()
        {
            Hashtable tmpHash = new Hashtable();
            foreach (double i in m_fitness)
            {
                if (!tmpHash.Contains(i)) tmpHash.Add(i, i);
            }
            return tmpHash.Count;
        }
        /// <summary>
        /// 计算适应度
        /// </summary>
        private void ComputeFitness()
        {
            for (int i = 0; i < m_populationNumber; i++)
            {
                double x = m_doublePopulation[i];
                m_fitness[i] = x * Math.Sin(10.0 * PI * x) + 2.0;
            }
        }
        /// <summary>
        /// 选择
        /// </summary>
        private void Selection()
        {
            int size = 3;//竞争规模
            string[][] tmpPopulation = new string[m_populationNumber][];
            for (int i = 0; i < m_populationNumber; i++)
            {
                int[] inSelection = GetRandomIntArray(0, m_populationNumber - 1, size, i);
                int winIndex = GetMaxIndex(inSelection);
                string[] tmpStr = new string[m_codingLength];
                for (int j = 0; j < m_codingLength; j++)
                {
                    tmpStr[j] = m_populations[winIndex][j];
                }
                tmpPopulation[i] = tmpStr;
            }
            m_populations = tmpPopulation;
        }
        /// <summary>
        /// 交叉
        /// </summary>
        private void Crossing()
        {
            int[] crossRate = GetRandomIntArray(0, 1000, m_populationNumber, 3);
            for (int i = 0; i < m_populationNumber; i++)
            {
                if (crossRate[i] <= m_crossRate * 1000)
                {
                    int[] twoCrossIndex = GetRandomIntArray(0, m_populationNumber - 1, 2, 2);
                    Random rnd = new Random();
                    int crossPlace = rnd.Next(m_codingLength);
                    string[] tmpStr = new string[m_codingLength];
                    for (int j = 0; j < crossPlace; j++)
                    {
                        tmpStr[j] = m_populations[i][j];
                    }
                    for (int j = crossPlace; j < m_codingLength; j++)
                    {
                        tmpStr[j] = m_populations[twoCrossIndex[0]][j];
                    }
                    m_populations[i] = tmpStr;
                }
            }
        }
        /// <summary>
        /// 变异
        /// </summary>
        private void Mutation()
        {
            int[] varRate = GetRandomIntArray(0, 1000, m_populationNumber, 3);
            for (int i = 0; i < m_populationNumber; i++)
            {
                Random rand = new Random(i * i);
                int varPlace = rand.Next(m_codingLength);
                if (varRate[i] <= m_varRate * 1000)
                {
                    if (m_populations[i][varPlace] == "0")
                    {
                        m_populations[i][varPlace] = "1";
                    }
                    else
                    {
                        m_populations[i][varPlace] = "0";
                    }
                }
            }
        }
        private int GetMaxIndex(int[] tmp)
        {
            int index = -1;
            double tmpDou = double.MinValue;
            for (int i = 0; i < tmp.Length; i++)
            {
                if (m_fitness[tmp[i]] > tmpDou)
                {
                    tmpDou = m_fitness[tmp[i]];
                    index = tmp[i];
                }
            }
            return index;
        }
        private void ConvertIndivadual2Double()
        {
            for (int i = 0; i < m_populationNumber; i++)
            {
                m_doublePopulation[i] = Coding2Double(m_populations[i]);
            }
        }
        /// <summary>
        /// 初始化种群
        /// </summary>
        private void InitPopulation()
        {
            for (int i = 0; i < m_populationNumber; i++)
            {
                m_populations[i] = GetRandomBinaryArray(m_codingLength, i);
            }
        }
        /// <summary>
        /// 取得需要的编码长度
        /// </summary>
        /// <param name="min">区间下限</param>
        /// <param name="max">区间上限</param>
        /// <param name="precision">精度</param>
        /// <returns>返回编码长度</returns>
        private int GetCodingLength(double min, double max, int precision)
        {
            int tmpInt = Convert.ToInt32(m_length * Math.Pow(10, precision));
            return Convert.ToString(tmpInt, 2).Length;
        }
        /// <summary>
        /// 编码转换为计算区间之内的实数值
        /// </summary>
        /// <param name="coding">编码</param>
        /// <returns>实数</returns>
        private double Coding2Double(string[] coding)
        {
            double tmp = 0.0d;
            tmp = m_minValue + (double)Coding2Int(coding) * m_length / (Math.Pow(2, m_codingLength) - 1);
            return tmp;
        }
        /// <summary>
        /// 将编码转换为整数
        /// </summary>
        /// <param name="coding">编码</param>
        /// <returns>整数</returns>
        private int Coding2Int(string[] coding)
        {
            int tmp = 0;
            for (int i = 0; i < coding.Length; i++)
            {
                tmp += int.Parse(coding[i]) * Convert.ToInt32(Math.Pow(2, i));
            }
            return tmp;
        }
        /// <summary>
        /// 返回随机的01数组
        /// </summary>
        /// <param name="count"></param>
        /// <param name="ii"></param>
        /// <returns></returns>
        public static string[] GetRandomBinaryArray(int count, int ii)
        {
            Random rnd = new Random(DateTime.Now.Millisecond + ii);
            byte[] keys = new byte[count];
            rnd.NextBytes(keys);
            string[] items = new string[count];
            for (int i = 0; i < count; i++)
            {
                if (keys[i] > 127)
                {
                    items[i] = "1";
                }
                else
                {
                    items[i] = "0";
                }
            }
            return items;
        }
        /// <summary>
        /// 取得一个随机数数组，参考网络上代码
        /// 和常规思路不同，不是采取先获取一个随机数再查找有无重复之后加入结果集，
        /// 而是先利用Random.NextBytes 方法得到一个随机数字节数组，然后利用 Array.Sort 
        /// 的重载方法用这个随机数字节数组将顺序源数组排序为乱序，最后 Copy 出结果集。
        /// 由于只用了一个循环来为顺序源数组赋初值，只使用了简单数组类型而没有用集合或
        /// 泛型集合类，利用Random.NextBytes 方法一次获得一组随机数而不是在循环中多次
        /// 调用，利用Array.Copy 方法复制结果集。因而性能得到优化。
        /// </summary>
        /// <param name="minValue">最小值</param>
        /// <param name="maxValue">最大值</param>
        /// <param name="count">随机数数目</param>
        /// <returns>随机数数组</returns>
        public static int[] GetRandomIntArray(int minValue, int maxValue, int count, int ii)
        {
            Random rnd = new Random(DateTime.Now.Millisecond + ii);
            int length = maxValue - minValue + 1;
            byte[] keys = new byte[length];
            rnd.NextBytes(keys);
            int[] items = new int[length];
            for (int i = 0; i < length; i++)
            {
                items[i] = i + minValue;
            }
            Array.Sort(keys, items);
            int[] result = new int[count];
            Array.Copy(items, result, count);
            return result;
        }
    }
}