import java.util.*;
public class Tsp {
private String cityName[]={"北京","上海","天津","重庆","哈尔滨","长春","沈阳","呼和浩特","石家庄","太原","济南","郑州","西安","兰州","银川","西宁","乌鲁木齐","合肥","南京","杭州","长沙","南昌","武汉","成都","贵州","福建","台北","广州","海口","南宁","昆明","拉萨","香港","澳门"};
//private String cityEnd[]=new String[34];
private int cityNum=cityName.length; //城市个数
private int popSize = 50; //种群数量
private int maxgens = 20000; //迭代次数
private double pxover = 0.8; //交叉概率
private double pmultation = 0.05; //变异概率
private long[][] distance = new long[cityNum][cityNum];
private int range = 2000; //用于判断何时停止的数组区间
private class genotype {
int city[] = new int[cityNum]; //单个基因的城市序列
long fitness; //该基因的适应度
double selectP; //选择概率
double exceptp; //期望概率
int isSelected; //是否被选择
}
private genotype[] citys = new genotype[popSize];
/**
* 构造函数,初始化种群
*/
public Tsp() {
for (int i = 0; i < popSize; i++) {
citys[i] = new genotype();
int[] num = new int[cityNum];
for (int j = 0; j < cityNum; j++)
num[j] = j;
int temp = cityNum;
for (int j = 0; j < cityNum; j++) {
int r = (int) (Math.random() * temp);
citys[i].city[j] = num[r];
num[r] = num[temp - 1];
temp--;
}
citys[i].fitness = 0;
citys[i].selectP = 0;
citys[i].exceptp = 0;
citys[i].isSelected = 0;
}
initDistance();
}
/**
* 计算每个种群每个基因个体的适应度,选择概率,期望概率,和是否被选择。
*/
public void CalAll(){
for( int i = 0; i< popSize; i++){
citys[i].fitness = 0;
citys[i].selectP = 0;
citys[i].exceptp = 0;
citys[i].isSelected = 0;
}
CalFitness();
CalSelectP();
CalExceptP();
CalIsSelected();
}
/**
* 填充,将多选的填充到未选的个体当中
*/
public void pad(){
int best = 0;
int bad = 0;
while(true){
while(citys[best].isSelected <= 1 && best<popSize-1)
best ++;
while(citys[bad].isSelected != 0 && bad<popSize-1)
bad ++;
for(int i = 0; i< cityNum; i++)
citys[bad].city[i] = citys[best].city[i];
citys[best].isSelected --;
citys[bad].isSelected ++;
bad ++;
if(best == popSize ||bad == popSize)
break;
}
}
/**
* 交叉主体函数
*/
public void crossover() {
int x;
int y;
int pop = (int)(popSize* pxover /2);
while(pop>0){
x = (int)(Math.random()*popSize);
y = (int)(Math.random()*popSize);
executeCrossover(x,y);//x y 两个体执行交叉
pop--;
}
}
/**
* 执行交叉函数
* @param 个体x
* @param 个体y
* 对个体x和个体y执行佳点集的交叉,从而产生下一代城市序列
*/
private void executeCrossover(int x,int y){
int dimension = 0;
for( int i = 0 ;i < cityNum; i++)
if(citys[x].city[i] != citys[y].city[i]){
dimension ++;
}
int diffItem = 0;
double[] diff = new double[dimension];
for( int i = 0 ;i < cityNum; i++){
if(citys[x].city[i] != citys[y].city[i]){
diff[diffItem] = citys[x].city[i];
citys[x].city[i] = -1;
citys[y].city[i] = -1;
diffItem ++;
}
}
Arrays.sort(diff);
double[] temp = new double[dimension];
temp = gp(x, dimension);
for( int k = 0; k< dimension;k++)
for( int j = 0; j< dimension; j++)
if(temp[j] == k){
double item = temp[k];
temp[k] = temp[j];
temp[j] = item;
item = diff[k];
diff[k] = diff[j];
diff[j] = item;
}
int tempDimension = dimension;
int tempi = 0;
while(tempDimension> 0 ){
if(citys[x].city[tempi] == -1){
citys[x].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi ++;
}
Arrays.sort(diff);
temp = gp(y, dimension);
for( int k = 0; k< dimension;k++)
for( int j = 0; j< dimension; j++)
if(temp[j] == k){
double item = temp[k];
temp[k] = temp[j];
temp[j] = item;
item = diff[k];
diff[k] = diff[j];
diff[j] = item;
}
tempDimension = dimension;
tempi = 0;
while(tempDimension> 0 ){
if(citys[y].city[tempi] == -1){
citys[y].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi ++;
}
}
/**
* @param individual 个体
* @param dimension 维数
* @return 佳点集 (用于交叉函数的交叉点) 在executeCrossover()函数中使用
*/
private double[] gp(int individual, int dimension){
double[] temp = new double[dimension];
double[] temp1 = new double[dimension];
int p = 2 * dimension + 3;
while(!isSushu(p))
p++;
for( int i = 0; i< dimension; i++){
temp[i] = 2*Math.cos(2*Math.PI*(i+1)/p) * (individual+1);
temp[i] = temp[i] - (int)temp[i];
if( temp [i]< 0)
temp[i] = 1+temp[i];
}
for( int i = 0; i< dimension; i++)
temp1[i] = temp[i];
Arrays.sort(temp1);
//排序
for( int i = 0; i< dimension; i++)
for( int j = 0; j< dimension; j++)
if(temp[j]==temp1[i])
temp[j] = i;
return temp;
}
/**
* 变异
*/
public void mutate(){
double random;
int temp;
int temp1;
int temp2;
for( int i = 0 ; i< popSize; i++){
random = Math.random();
if(random<=pmultation){
temp1 = (int)(Math.random() * (cityNum));
temp2 = (int)(Math.random() * (cityNum));
temp = citys[i].city[temp1];
citys[i].city[temp1] = citys[i].city[temp2];
citys[i].city[temp2] = temp;
}
}
}
/**
* 打印当前代数的所有城市序列,以及其相关的参数
*/
public void print(){
/**
* 初始化各城市之间的距离
*/
private void initDistance(){
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++){
distance[i][j] = Math.abs(i-j);
}
}
}
/**
* 计算所有城市序列的适应度
*/
private void CalFitness() {
for (int i = 0; i < popSize; i++) {
for (int j = 0; j < cityNum - 1; j++)
citys[i].fitness += distance[citys[i].city[j]][citys[i].city[j + 1]];
citys[i].fitness += distance[citys[i].city[0]][citys[i].city[cityNum - 1]];
}
}
/**
* 计算选择概率
*/
private void CalSelectP(){
long sum = 0;
for( int i = 0; i< popSize; i++)
sum += citys[i].fitness;
for( int i = 0; i< popSize; i++)
citys[i].selectP = (double)citys[i].fitness/sum;
}
/**
* 计算期望概率
*/
private void CalExceptP(){
for( int i = 0; i< popSize; i++)
citys[i].exceptp = (double)citys[i].selectP * popSize;
}
/**
* 计算该城市序列是否较优,较优则被选择,进入下一代
*/
private void CalIsSelected(){
int needSelecte = popSize;
for( int i = 0; i< popSize; i++)
if( citys[i].exceptp<1){
citys[i].isSelected++;
needSelecte --;
}
double[] temp = new double[popSize];
for (int i = 0; i < popSize; i++) {
// temp[i] = citys[i].exceptp - (int) citys[i].exceptp;
// temp[i] *= 10;
temp[i] = citys[i].exceptp*10;
}
int j = 0;
while (needSelecte != 0) {
for (int i = 0; i < popSize; i++) {
if ((int) temp[i] == j) {
citys[i].isSelected++;
needSelecte--;
if (needSelecte == 0)
break;
}
}
j++;
}
}
/**
* @param x
* @return 判断一个数是否是素数的函数
*/
private boolean isSushu( int x){
if(x<2) return false;
for(int i=2;i<=x/2;i++)
if(x%i==0&&x!=2) return false;
return true;
}
/**
* @param x 数组
* @return x数组的值是否全部相等,相等则表示x.length代的最优结果相同,则算法结束
*/
private boolean isSame(long[] x){
for( int i = 0; i< x.length -1; i++)
if(x[i] !=x[i+1])
return false;
return true;
}
/**
* 打印任意代最优的路径序列
*/
private void printBestRoute(){
CalAll();
long temp = citys[0].fitness;
int index = 0;
for (int i = 1; i < popSize; i++) {
if(citys[i].fitness<temp){
temp = citys[i].fitness;
index = i;
}
}
System.out.println();
System.out.println("最佳路径的序列:");
for (int j = 0; j < cityNum; j++)
{
String cityEnd[]={cityName[citys[index].city[j]]};
for(int m=0;m<cityEnd.length;m++)
{
System.out.print(cityEnd[m] + " ");
}
}
//System.out.print(citys[index].city[j] + cityName[citys[index].city[j]] + " ");
//System.out.print(cityName[citys[index].city[j]]);
System.out.println();
}
/**
* 算法执行
*/
public void run(){
long[] result = new long[range];
//result初始化为所有的数字都不相等
for( int i = 0; i< range; i++)
result[i] = i;
int index = 0; //数组中的位置
int num = 1; //第num代
while(maxgens>0){
System.out.println("----------------- 第 "+num+" 代 -------------------------");
CalAll();
print();
pad();
crossover();
mutate();
maxgens --;
long temp = citys[0].fitness;
for ( int i = 1; i< popSize; i++)
if(citys[i].fitness<temp){
temp = citys[i].fitness;
}
System.out.println("最优的解:"+temp);
result[index] = temp;
if(isSame(result))
break;
index++;
if(index==range)
index = 0;
num++;
}
printBestRoute();
}
/**
* @param a 开始时间
* @param b 结束时间
*/
public void CalTime(Calendar a,Calendar b){
long x = b.getTimeInMillis() - a.getTimeInMillis();
long y = x/1000;
x = x - 1000*y;
System.out.println("算法执行时间:"+y+"."+x+" 秒");
}
/**
* 程序入口
*/
public static void main(String[] args) {
Calendar a = Calendar.getInstance(); //开始时间
Tsp tsp = new Tsp();
tsp.run();
Calendar b = Calendar.getInstance(); //结束时间
tsp.CalTime(a, b);
}
}
分享到:
相关推荐
Java遗传算法排课系统是一种利用遗传算法解决复杂优化问题的软件应用。在教育领域,排课是一个典型的组合优化问题,需要考虑多方面的约束条件,如教师时间冲突、教室容量限制、课程时间安排等。遗传算法作为一种启发...
### Java遗传算法寻找最优路径 #### 一、遗传算法概览 遗传算法(Genetic Algorithm, GA)是一种基于自然选择和遗传学原理的全局优化技术。它通过模拟自然界中的生物进化过程来解决优化问题,包括搜索空间较大的...
《JAVA遗传算法编程》这本书是面向对遗传算法有兴趣并希望通过Java语言进行实现的读者的一本专业指南。遗传算法(Genetic Algorithm,简称GA)是一种基于生物进化论中的自然选择和遗传原理的优化方法,它在解决复杂...
Java遗传算法是一种应用了生物学进化原理的全局优化技术,它被广泛用于解决复杂问题的最优化,例如在本例中,寻找函数的最小值或最大值。遗传算法模仿自然界中的物种进化过程,通过选择、交叉和变异等操作,逐步改进...
**JAVA遗传算法开发包**是一种基于Java编程语言的遗传算法实现,主要面向具有一定遗传算法基础和Java编程经验的开发者。遗传算法(Genetic Algorithm,GA)是一种模拟自然选择和遗传机制的优化方法,广泛应用于解决...
Java遗传算法是一种应用了生物进化原理的优化技术,它通过模拟自然选择和遗传的过程来解决复杂问题。在Java中实现遗传算法,主要涉及到以下几个核心概念和技术: 1. **编码方式**:遗传算法中的个体通常被编码为二...
本书是学习如何利用遗传算法来解决问题的入门指南,书中包含了Java语言编写的、能运行的项目和解决方案。本书引导读者一步一步地实现各种遗传算法及一些常见应用场景,帮助读者在实践中加深理解,从而能够解决自己...
Java遗传算法求最值是一种利用生物进化原理解决优化问题的计算方法,它是人工智能领域中的一种模拟自然选择和遗传机制的搜索算法。在这个Java实现中,我们主要关注的是如何通过编程来模拟生物进化的过程,以寻找特定...
一本基于java遗传算法编程技术的讲解书书籍,全书讲解很全面,适合对遗传算法感兴趣的读者。本书共分为6章,每章都会有实例。
Java遗传算法是编程领域中解决复杂优化问题的一种高级技术,主要应用于解决旅行商问题(TSP)等组合优化难题。免疫遗传算法则是结合了生物免疫系统机制与遗传算法的优化方法,旨在提高算法的搜索效率和全局最优解的...
基于Java遗传算法实现集群调度策略模拟源代码(课程设计).zip基于Java遗传算法实现集群调度策略模拟源代码(课程设计).zip基于Java遗传算法实现集群调度策略模拟源代码(课程设计).zip基于Java遗传算法实现集群...
Java遗传算法编程是一种利用生物学中的进化原理来解决复杂优化问题的方法。在实际应用中,遗传算法因其并行性、全局搜索能力和对问题的抽象性,被广泛用于解决各种工程、科学和商业问题。本篇文章将深入探讨Java实现...
Java遗传算法智能组卷系统是一种利用遗传算法优化技术来实现自动组卷的程序。这个项目是用Java编程语言实现的,特别适合于教育领域,它能够根据预设的规则和需求,从大量的试题库中自动选择合适的题目,形成一套完整...
java 遗传算法 TSP 遗传算法大体上是可以先随机生成一组大量的解空间,作为一个初始的种群,然后按照一定的策略让种群自由交叉(也就是传说中的交配),变异。按照一定的策略淘汰种群中不符合预期目的的个体。
"JAVA遗传算法_TSP"这部分表明了遗传算法也被应用来解决旅行商问题。遗传算法是一种模拟自然选择和遗传的全局优化方法。在这个实现中,可能包括以下步骤: 1. 初始化种群:随机生成一组解决方案(路径),每个解决...
Java遗传算法(Genetic Algorithm, GA)是一种模拟生物进化过程的优化算法,广泛应用于解决复杂的搜索和优化问题。本项目"java-ga-devel-alpha-0.1.tar.gz"提供了Java语言实现的遗传算法的源代码,特别关注了算法的...
《深入理解Java遗传算法》 遗传算法(Genetic Algorithm,简称GA)是一种模拟自然选择和遗传机制的优化方法,广泛应用于解决复杂问题的求解。在这个名为“GA(Java).zip”的压缩包中,我们可以看到一系列与Java实现...
Java遗传算法用于解决旅行商问题(TSP)是一种在计算科学和优化领域广泛应用的方法。旅行商问题是一个经典的组合优化问题,目标是找到访问一系列城市并返回起点的最短路径,每个城市只访问一次。在这个Java界面版的...
《JAVA实现遗传算法详解》 遗传算法是一种模拟自然选择和遗传机制的优化方法,它在计算机科学领域,尤其是在人工智能和机器学习中具有广泛的应用。本文将深入探讨如何使用Java编程语言来实现遗传算法,并以此为基础...
求解大规模具有能力约束的车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)求解大规模具有能力约束的车辆路径问题(Capacitated Vehicle Routing Problem, CVRP)求解大规模具有能力约束的车辆路径问题...