GA遗传算法入门

        好吧，这几天突然对算法有点想法，准备整理一个专题来学习算法，虽然目前博主只掌握了一个算法-GA遗传算法，但几个月前，博主在学会这个算法的当天几乎失眠，幻想自己可以用这个算法去作很多事情，不过第二天清早还是继续了原来的生活轨迹，呵呵。

        在这篇简短的入门文章中，博主会用最简单的方式告诉你遗传算法是什么，以及怎么作一个C#的DEMO，这应该是网上最简单的遗传算法入门教程了，花几个小时看完这篇文章，你将收益匪浅。当初学者看到复杂的公式，总觉得算法是高高在上的。但其实算法离我们很近，比如我们带入一个生活中的实际问题：我们去中国9大城市旅游，想知道每个城市走一遍，总路程最短的出行顺序是哪一条？

OK，题目已经明确，我们来看看遗传算法是怎么来帮我们找出来这个最优解的。如果你觉得，看文字太麻烦，博主也准备了一份B站的同步视频：【遗传算法入门-哔哩哔哩】 遗传算法入门_哔哩哔哩_bilibili

在下图中，是我们用遗传算法解决这个问题的一些关键元素，这些元素来自真实世界生物物种的遗传机制，使用这些关键元素，就是模拟了生物物种的遗传更替。在现实世界中一个生物物种的不断进化，需要很漫长的时间，但在计算机的世界里，抽象的数据可以在极短的时间中大量迭代，最终出现一个最优结果。

图上的5个关键元素，就是遗传算法的关键元素，基于这些元素，我们设计详细的算法步骤：

第一步，我们自己定义计算规模，也叫种群大小（为什么叫这个，因为遗传算法是真正模拟生物遗传的元素），我们定义了100，就是假设100条线路，这些线路里面的数字数据，是初始化时让程序随机生成的，当然我们也可以定义30，就是假设30条线路，然后把数据初始上去，这些都是自己定的。

第二步，我们让电脑开始计算，100组线路中，每一组的路程有多长。这样的情况下，比如第一组从1到2到3到4到5到6到7到8到9，的总距离是7000KM。第二组从9到8到7到6到5到4到3到2到1的总距离是6000KM......第100组的总距离是8888KM。

第三步，我们对100组的总距离排序（升序），距离越小就在前面，距离越大就越在后面。然后我们规定，90个进入下一轮，淘汰掉最后距离最大的10个，因为我们想要距离最短的。我们还要再随机生成10个组数据，和90个一起进入下一轮，保证我们每次计算都有100个。我们还要模拟大自然中的变异，在90个优剩组中，每组的数字顺序让它随机变一点。比如第一组7000KM进入了下一轮，我们随机改变它一点，从1，2，3，4，5，6，7，8，9改变为2，1，3，4，5，6，7，8，9。

第四步，我们一直重复上面的过程，我们可以定义循环计算1000次，也可以定义不管运行多少次一直要运算10分钟。我记得SAP APO的算法参数就是定义的运算10分钟。

        上图截至道友的程序计算，非常类似的问题，可以看到统计每次迭代计算后，我们找到的最短距离越来越小，最后就不再变小了，这样我们就认为，我们找到了最优解，虽然它可能还不是最优的最短距离，但是应该已经很靠谱了。

         博主用C# WINFORM写了一个最简单的DEMO，用遗传算法来计算一次旅游中国9个真实城市经纬坐标的最短距离。经过GA算法计算，很快就得到了最优解和最短距离是3129公里.那么遗传算法解决问题的本质是什么呢？是在现实场景中，计算总量大到我们无法通过全量的计算得到结果，比如我们要计算的城市不是9个，而是300个或者3000个，如果去逐一模拟每一条线路，然后对比这些数字，得到最短的数字，这个方式的计算量就太大了；那我们就需要另一种方法去找到最终的解，用模拟遗传的方式来得到结果是一个好的办法，它不需要全量的计算，在有限的时间中可以找到最优解或最近似的最优解。

遗传算法是AI中一种重要的优化方法，其仿生机制和通用性使其在解决复杂问题时具有独特优势。尽管它不直接模仿人类智能，但作为“自然智能”的模拟，仍属于人工智能的范畴。

最后是C#写的全部代码：

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Security.Policy;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
using System.Windows.Forms;
 
 
 
namespace MyGA
{
    public partial class Form1 : Form
    {
        public static CityPoint cityPoint1 = new CityPoint() { Latitude = 106.45000, Longitude = 29.56667 }; //重庆
        public static CityPoint cityPoint2 = new CityPoint() { Latitude = 104.06667, Longitude = 30.66667 }; //成都
        public static CityPoint cityPoint3 = new CityPoint() { Latitude = 103.73333, Longitude = 36.03333 }; //兰州
        public static CityPoint cityPoint4 = new CityPoint() { Latitude = 108.95000, Longitude = 34.26667 }; //西安
        public static CityPoint cityPoint5 = new CityPoint() { Latitude = 118.78333, Longitude = 32.05000 }; //南京
        public static CityPoint cityPoint6 = new CityPoint() { Latitude = 121.43333, Longitude = 34.50000 }; //上海
        public static CityPoint cityPoint7 = new CityPoint() { Latitude = 116.41667, Longitude = 39.91667 }; //北京
        public static CityPoint cityPoint8 = new CityPoint() { Latitude = 113.23333, Longitude = 23.16667 }; //广州
        public static CityPoint cityPoint9 = new CityPoint() { Latitude = 114.06667, Longitude = 22.61667 }; //深圳
        public static List<CityPoint> city9 = new List<CityPoint>();
        public static List<NUM9> list100 = new List<NUM9>();
        public static NUM9 mini = new NUM9();
 
        public Form1()
        {
            InitializeComponent();
 
            //------线程-------------         
            Control.CheckForIllegalCrossThreadCalls = false;
            Thread thread = new Thread(new ThreadStart(gogogo));
            thread.IsBackground = true;
            thread.Start();
 
        }
 
 
        void gogogo()
        {
      
            mini.distance = 9999999;
 
            //---------------------------  
            for (int i = 1; i <= 9; i++)
            { city9.Add(cityPoint1); city9.Add(cityPoint2); city9.Add(cityPoint3); city9.Add(cityPoint4); city9.Add(cityPoint5); city9.Add(cityPoint6); city9.Add(cityPoint7); city9.Add(cityPoint8); city9.Add(cityPoint9); }
 
            //-----计算距离--------------------  
            for (int i = 1; i <= 100; i++)
            {
                NUM9 tmp = new NUM9();
                tmp.CalCal();
                list100.Add(tmp);
            }
 
            list100.Sort(new NUM9Comparer());
 
            //------显示---------------------------
            foreach (var one in list100)
            {
                listBox1.Items.Add(one.numbers[0] + " " + one.numbers[1] + " " + one.numbers[2] + " " + one.numbers[3] + " " + one.numbers[4] + " " + one.numbers[5] + " " + one.numbers[6] + " " + one.numbers[7] + " " + one.numbers[8] + "  " + one.distance);
            }
 
 
            for (int d = 1; d <= 10000; d++)
            {
                Thread.Sleep(50);
                toolStripStatusLabel1.Text = "计算次数:" + d.ToString();
                //------淘汰掉最后10个-------------
                list100.RemoveRange(90, 10);
 
                //---------变异前面90个---------------
                foreach (var l in list100)
                {
                    l.change();
                }
 
 
                //------补上10个----------
                for (int i = 1; i <= 10; i++)
                {
                    NUM9 tmp = new NUM9();
                    tmp.CalCal();
                    list100.Add(tmp);
                }
 
                //------排序----------
                list100.Sort(new NUM9Comparer());
 
                //----取最短距离--------------
 
                if (mini.distance > list100[0].distance)
                {
                    mini.distance = list100[0].distance;
                    mini.numbers = list100[0].numbers;
                    listBox2.Items.Add(mini.numbers[0] + " " + mini.numbers[1] + " " + mini.numbers[2] + " " + mini.numbers[3] + " " + mini.numbers[4] + " " + mini.numbers[5] + " " + mini.numbers[6] + " " + mini.numbers[7] + " " + mini.numbers[8] + "  " + mini.distance);
 
                }
 
            }
 
           }
 
 
 
        public static double CalculateDistance(CityPoint c1, CityPoint c2)
        {
            double lat1 = c1.Latitude;
            double lon1 = c1.Longitude;
            double lat2 = c2.Latitude;
            double lon2 = c2.Longitude;
            double radiusOfEarth = 6371; // 地球平均半径，单位为千米
 
            double lat1Rad = Math.PI * lat1 / 180;
            double lat2Rad = Math.PI * lat2 / 180;
            double lon1Rad = Math.PI * lon1 / 180;
            double lon2Rad = Math.PI * lon2 / 180;
            double deltaLat = lat2Rad - lat1Rad;
            double deltaLon = lon2Rad - lon1Rad;
            double a = Math.Sin(deltaLat / 2) * Math.Sin(deltaLat / 2) + Math.Cos(lat1Rad) * Math.Cos(lat2Rad) * Math.Sin(deltaLon / 2) * Math.Sin(deltaLon / 2);
            double c = 2 * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1 - a));
            return radiusOfEarth * c;
        }
        public class CityPoint
        {
            public double Latitude { get; set; } // 纬度
            public double Longitude { get; set; } // 经度
 
        }
 
 
        public class NUM9
        {
            public static  Random random = new Random();
            public int[] numbers = Enumerable.Range(1, 9).OrderBy(x => random.Next()).ToArray();
            public int distance = 0;
            //------评价函数---------
            public void CalCal()
            {
                distance = 0;
                for (int i = 0; i < 8; i++)
                {
                    distance = distance + ((int)CalculateDistance(city9[numbers[i]], city9[numbers[i + 1]]));
                }
            }
            //-----变异----------
            public void change()
            {
                for (int i = 0; i <= 3; i++) //只变3个
                {
                    int index = random.Next(1, 9);
                    int temp = numbers[index];
                    numbers[index] = numbers[0];
                    numbers[0] = temp;
                }
                CalCal();
            }
        }
        public class NUM9Comparer : IComparer <NUM9>
        {
            public int Compare(NUM9 x, NUM9 y)
            {
                return x.distance.CompareTo(y.distance);
            }
        }
 
    }
}