using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GA
{
    class Program
    {

        #region 全局变量
        /// <summary>
        /// 染色体信息
        /// </summary>
        private class Chromosome
        {
            /// <summary>
            /// 用6bit对染色体进行编码，第1个元素表示正负，2-5以此存储二进制的的信息，最大表示31
            /// </summary>
            public int[] bits = new int[6];

            /// <summary>
            /// 适应值
            /// </summary>
            public int fitValue;

            /// <summary>
            /// 选择概率
            /// </summary>
            public double fitValuePercent;

            /// <summary>
            /// 累积概率
            /// </summary>
            public double totalProbability;

            public Chromosome Clone()//染色体赋值，复制
            {
                Chromosome c = new Chromosome();
                for (int i = 0; i < bits.Length; i++)//逐个染色体赋值
                {
                    c.bits[i] = bits[i];
                }
                c.fitValue = fitValue;
                c.fitValuePercent = fitValuePercent;
                c.totalProbability = totalProbability;
                return c;
            }
        }

        /// <summary>
        /// 变异几率
        /// </summary>
        public  static  double varProbability = 0.02;

        /// <summary>
        /// 染色体组;
        /// </summary>
        private static List<Chromosome> chromosomes = new List<Chromosome>();           //父代

        private static List<Chromosome> chromosomesChild = new List<Chromosome>();      //子代

        private static Random random = new Random();

        /// <summary>
        /// 选择类型
        /// </summary>
        private enum ChooseType
        {
            Bubble,//冒泡;
            Roulette,//轮盘赌;
        }

        private static ChooseType chooseType = ChooseType.Roulette;     //选择赌轮盘的方法
        #endregion

        /// <summary>
        /// Main入口函数;
        /// </summary>
        /// <param name="args"></param>
        private static void Main(string[] args)
        {
            Console.WriteLine("遗传算法");
            Console.WriteLine("求函数最大值函数为y = x*x-31x的最大值，-31<=x<=31");

            int totalTime = 30;                    // 迭代次数，根据结果调整
            Console.WriteLine("迭代次数为: " + totalTime);
            Console.WriteLine("初始化: ");          //初始化;

            Init();          // 输出初始化数据;          
            Print();

            for (int i = 0; i < totalTime; i++)
            {
                Console.WriteLine("当前迭代次数: " + i);

                //重新计算fit值;;
                UpdateFitValue();

                // 挑选染色体;
                Console.WriteLine("挑选:");

                switch (chooseType)
                {
                    case ChooseType.Bubble:
                        // 排序;
                        Console.WriteLine("排序:");
                        ChooseChromosome();
                        break;
                    default:
                        //轮盘赌;
                        Console.WriteLine("轮盘赌:");
                        UpdateNext();
                        break;
                }
                Print(true);

                //交叉得到新个体
                Console.WriteLine("交叉:");
                CrossOperate();
                Print();

                //变异
                Console.WriteLine("变异:");
                VariationOperate();
                Print();
            }

            //挑选出最大适应值
            int maxFit = chromosomes[0].fitValue;
            for (int i = 1; i < chromosomes.Count; i++)
            {
                if (chromosomes[i].fitValue > maxFit)
                {
                    maxFit = chromosomes[i].fitValue;
                }
            }
            Console.WriteLine("最大值为: " + maxFit);
            Console.ReadKey();
        }

        #region 打印输出
        /// <summary>
        /// 打印;
        /// </summary>
        private static void Print(bool bLoadPercent = false)
        {
            Console.WriteLine("=========================");
            for (int i = 0; i < chromosomes.Count; i++)
            {
                Console.Write("第" + i + "条" + " 基因: ");
                for (int j = 0; j < chromosomes[i].bits.Length; j++)
                {
                    Console.Write(" " + chromosomes[i].bits[j]);
                }
                int x = DeCode(chromosomes[i].bits);
                Console.Write(" x: " + x);
                Console.Write(" y: " + chromosomes[i].fitValue);
                if (bLoadPercent)
                {
                    Console.Write(" 选择概率: " + chromosomes[i].fitValuePercent);
                }
                Console.WriteLine();
            }
            Console.WriteLine("=========================");
        }
        #endregion

        #region 初始化
        /// <summary>
        /// 初始化
        /// </summary>
        private static void Init()
        {
            chromosomes.Clear();
            int length = 30;        // 染色体数量
            int totalFit = 0;

            for (int i = 0; i < length; i++)
            {
                Chromosome chromosome = new Chromosome();
                for (int j = 0; j < chromosome.bits.Length; j++)
                {
                    // 随机出0或者1;
                    int bitValue = random.Next(0, 2);
                    chromosome.bits[j] = bitValue;
                }
                //获得十进制的值;
                int x = DeCode(chromosome.bits);
                int y = GetFitValue(x);
                chromosome.fitValue = y;
                chromosomes.Add(chromosome);
                //算出total fit;
                if (chromosome.fitValue <= 0)
                {
                    totalFit += 0;
                }
                else
                {
                    totalFit += chromosome.fitValue;
                }
            }
        }
        #endregion

        #region 解码，二进制装换
        /// <summary>
        /// 解码,二进制装换;
        /// </summary>
        /// <param name="bits"></param>
        /// <returns></returns>
        private static int DeCode(int[] bits)
        {
            int result = bits[1] * 16 + bits[2] * 8 + bits[3] * 4 + bits[4] * 2 + bits[5] * 1;//第一个元素判断正负，后5个元素二进制转换十进制，所能表达的最大十进制数值为31
            //通过第一个元素判断正负;
            if (bits[0] == 0)
            {
                return result;
            }
            else
            {
                return -result;
            }
        }
        #endregion

        #region 获取fitValue（适应度）
        /// <summary>
        /// 获取fitValue，返回值越大说明适应度越高
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        private static int GetFitValue(int x)
        {
            return x * x - 31 * x;//目标函数 y= x*x -31*x
        }
        #endregion

        #region 选择
        /// <summary>
        /// 更新下一代;
        /// 基于轮盘赌选择方法，进行基因型的选择;
        /// </summary>
        private static void UpdateNext()
        {
            // 获取总的fit;
            double totalFitValue = 0;
            for (int i = 0; i < chromosomes.Count; i++)
            {
                //适应度为负数的取0（前提知道函数的最大值一定大于0）
                if (chromosomes[i].fitValue <= 0)
                {
                    totalFitValue += 0;
                }
                else
                {
                    totalFitValue += chromosomes[i].fitValue;
                }
            }
            Console.WriteLine("累计适应度（totalFitValue） ：" + totalFitValue);

            //算出每个的fit percent;
            for (int i = 0; i < chromosomes.Count; i++)
            {
                if (chromosomes[i].fitValue <= 0)   //杀掉适应度为负的基因
                {
                    chromosomes[i].fitValuePercent = 0;
                }
                else
                {
                    chromosomes[i].fitValuePercent = chromosomes[i].fitValue / totalFitValue;//计算第i个基因的适应值（第i个基于的适应值/累计适应值）
                }
                Console.WriteLine("第" + i + " 个体选择概率（fitValuePercent）：" + chromosomes[i].fitValuePercent);
            }

            ////计算累积概率
            //// 第一个的累计概率就是自己的概率，循环完后，便可得到累计概率的值，便于后续的赌轮盘算法
            chromosomes[0].totalProbability = chromosomes[0].fitValuePercent;
            double probability = chromosomes[0].totalProbability;
            for (int i = 1; i < chromosomes.Count; i++)
            {
                if (chromosomes[i].fitValuePercent != 0)        //只对出现概率概率不为0的染色体进行操作
                {
                    chromosomes[i].totalProbability = chromosomes[i].fitValuePercent + probability;
                    probability = chromosomes[i].totalProbability;
                }
            }

            chromosomesChild.Clear();
            //轮盘赌选择方法,用于选出前两个;
            for (int i = 0; i < chromosomes.Count; i++)
            {
                double chooseNum = random.NextDouble();     //生成0.0-1.0之间的随机数，用于选择
                Console.WriteLine("挑选的数值：" + chooseNum);
                //判断挑选的数值落在区间位置，从而确定选择的染色体
                if (chooseNum < chromosomes[0].totalProbability)
                {
                    chromosomesChild.Add(chromosomes[0].Clone());
                }
                else
                {
                    for (int j = 0; j < chromosomes.Count - 1; j++) //-1是因为去除了第1个染色体
                    {
                        if (chromosomes[j].totalProbability <= chooseNum && chooseNum <= chromosomes[j + 1].totalProbability)   //判断区间
                        {
                            chromosomesChild.Add(chromosomes[j + 1].Clone());   //j是从0开始的，
                        }
                    }
                }
            }
            for (int i = 0; i < chromosomes.Count; i++)
            {
                chromosomes[i] = chromosomesChild[i];   //子代变父代，便于进入下一次循环
            }
        }

        /// <summary>
        /// 选择染色体;
        /// </summary>
        private static void ChooseChromosome()
        {
            // 从大到小排序;
            chromosomes.Sort((a, b) => { return b.fitValue.CompareTo(a.fitValue); });
        }
        #endregion

        #region 交叉
        /// <summary>
        /// 交叉操作
        /// </summary>
        private static void CrossOperate()
        {
            //选择交叉位置
            int bitNum = chromosomes[0].bits.Length;    //获取染色体位数
            int a = random.Next(0, bitNum );            //生成0-染色体位数-1之间的随机数，
            int b = random.Next(0, bitNum );
            if (a > b)      //交换，排序
            {
                int temp = a;
                a = b;
                b = temp;
            }
            Console.WriteLine("交叉范围：" + a + "— " + b);

            //交叉位置处进行交叉操作（第1条和第2条进行交叉，两两一对，以此类推，染色体个数优先选择偶数个）
            for (int j = 0; j < chromosomes.Count; j = j + 2)
            {
                for (int i = a; i <= b; i++)        //从第一个随机数开始交叉 到第二个随机数结束
                {
                    int temp = chromosomes[j].bits[i];
                    chromosomes[j].bits[i] = chromosomes[j + 1].bits[i];
                    chromosomes[j + 1].bits[i] = temp;
                }

                //对交叉后生成的两条新染色体（二进制转码十进制）重新计算适应值
                chromosomes[j].fitValue = GetFitValue(DeCode(chromosomes[j].bits)); 
                chromosomes[j + 1].fitValue = GetFitValue(DeCode(chromosomes[j + 1].bits));
            }
        }
        #endregion

        #region 变异
        /// <summary>
        /// 变异操作
        /// </summary>
        private static void VariationOperate()
        {
            int chromoNum = chromosomes.Count;                      //染色体数量
            int geneNum = chromosomes[0].bits.Length - 1;           //单个染色体基因数-1,去除用于判断正负的一个基因
            int varSite = random.Next(1, chromoNum * geneNum + 1);  //在所有的基因数范围中选择一个随机数
            if (varSite <= chromoNum *geneNum *varProbability)       //通过判断随机数是否小于等于 基因总数*变异概率 ,判断是否发生突变     //每条染色体有5个决定基因(排除第一个决定正负的基因)
            {
                Console.WriteLine("开始变异");

                int row = random.Next(0, chromoNum );         //确定要突变的染色体编号
                int col = random.Next(0, geneNum );           //确定要突变的基因
                Console.WriteLine("变异的位置 :第" + row + "条染色体的第" + col + "个基因");
                //0变1,1变0
                if (chromosomes[row].bits[col] == 0)
                {
                    chromosomes[row].bits[col] = 1;
                }
                else
                {
                    chromosomes[row].bits[col] = 0;
                }
                chromosomes[row].fitValue = GetFitValue(DeCode(chromosomes[row].bits));
            }
        }
        #endregion

        #region 重新计算fit值
        /// <summary>
        /// 重新计算fit值;
        /// </summary>
        private static void UpdateFitValue()
        {
            for (int i = 0; i < chromosomes.Count; i++)
            {
                chromosomes[i].fitValue = GetFitValue(DeCode(chromosomes[i].bits));
            }
        }
        #endregion
    }
}