蚁群算法-JAVA实现_DongLUOWAN的博客-程序员宝宝_java蚁群算法

技术标签: 算法  java  人工智能  eclipse  

蚁群算法

基本思想

蚂蚁靠什么找出最短路径?
• 信息素:信息素是一种由蚂蚁自身释放的易挥发的
物质,能够实现蚁群内的间接通信。蚂蚁在寻找食
物时,在其经过的路径上会释放信息素,信息素可
以被其他的蚂蚁感知,并且信息素的浓度越高,对
应的路径越短
• 正反馈:蚂蚁会以较大概率选择信息素浓度较高的
路径,并释放一定量的信息素,从而使距离较短的
信息素浓度被加强形成正反馈*

蚁群算法解决TSP问题步骤以及预备知识

预备知识


在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述


在这里插入图片描述

算法步骤

①初始化城市距离矩阵,贪心算法获得第一个路径,第一次更新信息素矩阵
②为每一只蚂蚁随机选择初始城市
③计算前往下一个城市的概率,更新禁忌表
④轮盘赌选择下一个城市
⑤更新信息素矩阵
循环执行,找出解空间的最优解
部分代码展示(用到了四个java文件)

蚂蚁类

package antGroupAlgrithm;
//蚂蚁类
public class Ants {
    
	// 禁忌表, 记录走过的城市
	public boolean table[];
	// 路径
	public int path[];
	//每一个的概率以及累积概率用于轮盘赌
	public double pro[];
	public double accumulatePro[];
	//记录当前路径花费的距离
	public double distance;
	Ants(int number) {
    
		this.table = new boolean[number];
		this.path = new int[number+1];
		
		for (int i = 0; i < number; i++) {
    
			this.table[i] = false;
			this.path[i]=-1;
		}
		this.path[number]=-1;
		this.distance=0;
	}
	
	public boolean notOver() {
    
		for(int i=0;i<this.table.length;i++)
			if(this.table[i]==false)
				return true;
		return false;
	}
}

城市类

package antGroupAlgrithm;
//城市类
public class City {
    
	//记录城市的坐标
	public int x,y;
	//记录城市的标志
	public int ID;
	City(int lx,int ly,int sign){
    
		this.x=lx;
		this.y=ly;
		this.ID=sign;
	}
}

解空间类

package antGroupAlgrithm;
//解空间的每一个元素,路径和距离的一个结构体
public class DistancePath {
    
	public int path[];
	public double distance;
	DistancePath(int num){
    
		this.path=new int[num+1];
		this.distance=0;
	}
}

主算法类
变量部分

public class AntAlgrithm {
    

	public int cityNum;
	public City city[];
	public Ants ants[];
	// 记录已经被选择的出发点
	public boolean start[];
	// 距离矩阵与信息素矩阵
	public double distanceMatrix[][];
	public double pheromones[][];
	
	//记录全局解结果
	public DistancePath dp[][];
	
	public static final double alpha = 1;
	public static final double beta = 2;
	public static final double p = 0.5;
	public static final int antnumber = 18;
	public static final int MAX = 100000;
	public static final int times = 500;
	
	//构造函数
	AntAlgrithm(int x[], int y[]) {
    
		this.cityNum = x.length;
		this.city = new City[cityNum];
		this.ants = new Ants[antnumber];
		this.start = new boolean[cityNum];
		for (int i = 0; i < this.cityNum; i++) {
    
			this.city[i] = new City(x[i], y[i], i);
			this.start[i] = false;
		}
		// 初始化每一只蚂蚁
		for (int i = 0; i < antnumber; i++) {
    
			this.ants[i] = new Ants(this.cityNum);
			this.ants[i].pro = new double[this.cityNum - 1];
			this.ants[i].accumulatePro = new double[this.cityNum - 1];
		}
		//记录解空间的初始化
		this.dp=new DistancePath[times][antnumber];
		for(int i=0;i<this.dp.length;i++) {
    
			for(int j=0;j<this.dp[i].length;j++)
				this.dp[i][j]=new DistancePath(this.cityNum);
		}
	}
	//初始化函数
	public void Initial() {
    
		this.distanceMatrix = new double[this.cityNum][this.cityNum];
		this.pheromones = new double[this.cityNum][this.cityNum];

		for (int i = 0; i < this.cityNum; i++) {
    
			for (int j = i; j < this.cityNum; j++) {
    
				if (j == i)
					this.distanceMatrix[i][j] = MAX;
				else {
    
					this.distanceMatrix[i][j] = Math.hypot(this.city[i].x - this.city[j].x,
							this.city[i].y - this.city[j].y);
					this.distanceMatrix[j][i] = this.distanceMatrix[i][j];
				}
			}
		}
		// 利用贪心算法更新信息素矩阵
		double cn = this.greedy();
		double tao;
		tao = antnumber / cn;
		for (int i = 0; i < this.cityNum; i++) {
    
			for (int j = i + 1; j < this.cityNum; j++) {
    
				this.pheromones[i][j] = tao;
				this.pheromones[j][i] = tao;
			}
		}
	}

主函数部分

public static void main(String[] args) {
    
		//城市坐标
		int xCoordinate[] = {
     1304, 3639, 4177, 3712, 3488, 3326, 3238, 4196, 4312, 4386, 3007, 2562, 2788, 2381, 1332,
				3715, 3918, 4061, 3780, 3676, 4029, 4263, 3429, 3507, 3394, 3439, 2935, 3140, 2545, 2778, 2370 };
		int yCoordinate[] = {
     2312, 1315, 2244, 1399, 1535, 1556, 1229, 1004, 790, 570, 1970, 1756, 1491, 1676, 695,
				1678, 2179, 2370, 2212, 2578, 2838, 2931, 1908, 2367, 2643, 3201, 3240, 3550, 2357, 2826, 2975 };
		int flag = 0;
		//初始化
		AntAlgrithm ata = new AntAlgrithm(xCoordinate, yCoordinate);
		ata.Initial();
		//演变
		while (flag < times) {
    
			ata.tsp();
			ata.record(flag);
			ata.remake();
			flag += 1;
		}
		//选择最优解
		ata.chooseBest();
	}

需要注意的是,蚁群算法得到的解不是固定的,但是收敛于一个较小的值

代码运行截图
在这里插入图片描述
如果觉得有帮助的话就点个赞吧!

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/DongLUOWAN/article/details/121254876

智能推荐

计算机网络原理学习资源——相关书籍推荐_qq_43386985的博客-程序员宝宝

如果想对网络有个清晰、全面的认识,可以阅读三本书籍:第一本就是潘爱民翻译的Andrew S.Tanenbaum的《计算机网络》,此书讲明白了网络之道,即计算机网络通信的主要原理;第二本是W.Richard Stevens的《TCP/IP详解卷一:协议》,此书讲明白了网络之术,即TCP/IP协议簇的工作过程;第三本是Douglas E.Comer的《计算机网络与因特网》,此书尝试在更广泛意义...

每周小记(2)_weixin_45758376的博客-程序员宝宝

数组:arrarr.push():将一个或多个元素添加到数组的末尾arr.unshift():将一个或多个元素添加到数组的开头arr.pop():从数组中删除最后一个元素arr.shift():从数组中删除第一个元素arr.splice():从指定位置开始删除或修改指定个数的数组元素arr.reverse():将数组中元素的位置颠倒arr.concat():用于合并两个或多个数组arr.join():把数组里面的每一项内容链接起来,变成一个字符串arr.sort():对数组进行排序冒泡

【合集】用Raspberry Pi(树莓派)打造各种服务器_gaochaoweino的博客-程序员宝宝

【合集】用Raspberry Pi(树莓派)打造各种服务器Raspberry Pi(树莓派)有很多的应用,其中搭建服务器是大家应用比较多的,今天就整理一个合集用Raspberry Pi(树莓派)打造各种服务器。欢迎大家提出宝贵意见,更欢迎大家补充您用树莓派所做的好玩的应用![教程] 将树莓派变成网络打印机服务器(更新PC和手机端设置)!http://www.eeboard.

js02 -- JSON_Sky皓皓的博客-程序员宝宝_js2json

js02 -- JSONJSON1. 概述2. 定义3. json和js对象之间的转换JSON1. 概述JSON(JavaScript Object Notation, JS 对象简谱) 是一种轻量级的数据交换格式。本质就是一个字符串,用来规定了 服务器 和 浏览器之间的数据交互的格式JSON是一个轻量级的数据交换格式2. 定义格式一般为单引号包裹双引号,如 ' "name":"jack" ' ,或者也可以是双引号包裹单引号,如 " 'name':'jack' " ,但是不可以都是单

如何用jquery实现checkbox点选一个选中其他,取消一个取消其他_王奕然的博客-程序员宝宝

用jquery实现,选中一个特定的checkbox,则其他checkbox都选中,不选中这个特定的checkbox,则其他checkbox也不选中首先要导入jquery.js这是我碰到了 jquery没有反应,网页提示找不到对象,网上找了,这个很可能是导入的jquery路径写错!还有就是选中checkbox应该是$(:checkbox)一定注意加冒号!最开始我想看一下==可不可以用

随便推点

2021牛客暑期多校训练营1 I题_Spy_Savior的博客-程序员宝宝

I题: Increasing Subsequence题目链接:https://ac.nowcoder.com/acm/contest/11166/I题目大意Alice和Bob在一个大小为n(1≤n≤5000)n(1\le n\le 5000)n(1≤n≤5000)的排列PPP上玩游戏,双方轮流选择数字。每一轮中,当前玩家需要往后选择一个比曾经选择过的所有元素大的数,换句话说题解参考代码#include&lt;bits/stdc++.h&gt;#define ll long longusin

最全的HTTP响应状态码列表:除了404,HTTP状态码还有啥?_cky8792的博客-程序员宝宝

HTTP是一个应用层协议,虽然在2015年已推出HTTP/2版本,并被主要的web浏览器和web服务器支持。它的主要特点可概括如下:支持客户/服务器模式。简单快速:...

hdfs mysql sqoop 失败_Sqoop采集mysql数据到HDFS遇到的坑_无声如风的博客-程序员宝宝

1. 在sqoop进行数据迁移时,我写了几个简单的脚本,便于后续做定时任务① 要进行数据导出的数据库信息配置脚本(db_xxx.sh)#!/bin/sh# 数据库信息export username='root'export password='12345678'export database_url='jdbc:mysql://localhost:3306'# 数据库名字export base_d...

Windows Sever 2012 安装MongoDB数据库教程及问题解决_bienyou的博客-程序员宝宝

1、下载安装包地址:https://www.mongodb.com/download-center/community此次是在windows sever 2012 r2上安装数据库MongoDB2、安装过程(1)双机下载好的安装包进行安装(2)勾选同意安装,Next(3)选择自定义安装(4)选择安装路径(5)自定义安装路径(6)取消安装MongDB指南的选项备注:如...

ubuntu 下git安装及使用笔记_icefireym的博客-程序员宝宝

1.安装sudo apt-get install git-core openssh-server openssh-client$ sudo apt-get install git-core git-gui git-doc sudo apt-get install libcur14-gnutls-dev libexpat1-dev gettext libz-dev git-core

推荐文章

热门文章

相关标签