GA遗传算法和ALNS算法的区别(我的APS项目七)

2024-03-28 16:20

本文主要是介绍GA遗传算法和ALNS算法的区别(我的APS项目七),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

博主用最简单的方式告诉你遗传算法是什么,估计这是网上最简单的遗传算法入门教程了。首先我们先带入一个问题,我们要去9大城市旅游,想知道每个城市走一遍,总路程最短的出行顺序是什么?

OK,题目我们已经明确,我们来看看遗传算法是怎么来帮我们找出来这个最优解的。

如果你觉得,看文字太麻烦,博主也准备了一份B站的同步视频:【遗传算法入门-哔哩哔哩】 遗传算法入门_哔哩哔哩_bilibili

第一步,我们自己定义计算规模,也叫种群大小(为什么叫这个,因为遗传算法是真正模拟生物遗传的元素),我们定义了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分钟。

图片截至网友的程序计算,可以看到统计每次计算后,我们找到的最短距离越来越小,最后就不再变小了,这样我们就认为,我们找到了最优解,虽然它可能还不是最优的最短距离,但是应该已经很靠谱了。

图片截至网友的CSDN博客,说的内容是GA遗传算法同ALNS算法是很类似的,我理解是ALNS算法在进化和淘汰机制上作了优化控制,而遗传算法是随机的。

//-----------2024.3.24增加C#程序DEMO代码内容---------------

话说光说不练假把式,今天周末,用C# WINFORM写了一个最简单的DEMO,用遗传算法来计算一次旅游中国9个真实城市经纬坐标的最短距离。经过GA算法计算,很快就得到了最优解和最短距离是3129公里.

谁说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);}}}
}

这篇关于GA遗传算法和ALNS算法的区别(我的APS项目七)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/856095

相关文章

Android kotlin中 Channel 和 Flow 的区别和选择使用场景分析

《Androidkotlin中Channel和Flow的区别和选择使用场景分析》Kotlin协程中,Flow是冷数据流,按需触发,适合响应式数据处理;Channel是热数据流,持续发送,支持... 目录一、基本概念界定FlowChannel二、核心特性对比数据生产触发条件生产与消费的关系背压处理机制生命周期

Javaee多线程之进程和线程之间的区别和联系(最新整理)

《Javaee多线程之进程和线程之间的区别和联系(最新整理)》进程是资源分配单位,线程是调度执行单位,共享资源更高效,创建线程五种方式:继承Thread、Runnable接口、匿名类、lambda,r... 目录进程和线程进程线程进程和线程的区别创建线程的五种写法继承Thread,重写run实现Runnab

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,:本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v

Go语言中make和new的区别及说明

《Go语言中make和new的区别及说明》:本文主要介绍Go语言中make和new的区别及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 概述2 new 函数2.1 功能2.2 语法2.3 初始化案例3 make 函数3.1 功能3.2 语法3.3 初始化

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

深度解析Spring Boot拦截器Interceptor与过滤器Filter的区别与实战指南

《深度解析SpringBoot拦截器Interceptor与过滤器Filter的区别与实战指南》本文深度解析SpringBoot中拦截器与过滤器的区别,涵盖执行顺序、依赖关系、异常处理等核心差异,并... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)深度解析:区别、实现

如何在Spring Boot项目中集成MQTT协议

《如何在SpringBoot项目中集成MQTT协议》本文介绍在SpringBoot中集成MQTT的步骤,包括安装Broker、添加EclipsePaho依赖、配置连接参数、实现消息发布订阅、测试接口... 目录1. 准备工作2. 引入依赖3. 配置MQTT连接4. 创建MQTT配置类5. 实现消息发布与订阅

springboot项目打jar制作成镜像并指定配置文件位置方式

《springboot项目打jar制作成镜像并指定配置文件位置方式》:本文主要介绍springboot项目打jar制作成镜像并指定配置文件位置方式,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录一、上传jar到服务器二、编写dockerfile三、新建对应配置文件所存放的数据卷目录四、将配置文