「tsp遗传java」tsp问题遗传算法python

今天给各位分享tsp遗传java的知识，其中也会对tsp问题遗传算法python进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、用java解决tsp问题用什么算法最简单
• 2、血型遗传规律用JAVA怎么写
• 3、遗传算法解决TSP问题
• 4、TSP中用蚁群算法和遗传算法有区别么?
• 5、在遗传算法解决Tsp问题中如何保持种群的数量不变啊？
• 6、遗传算法解决旅行商问题(TSP)一:初始化和适应值

用java解决tsp问题用什么算法最简单

package noah;

import java.io.BufferedReader;

import java.io.FileInputStream;

import java.io.IOException;

import java.io.InputStreamReader;

public class TxTsp {

private int cityNum; // 城市数量

private int[][] distance; // 距离矩阵

private int[] colable;//代表列，也表示是否走过，走过置0

private int[] row;//代表行，选过置0

public TxTsp(int n) {

cityNum = n;

}

private void init(String filename) throws IOException {

// 读取数据

int[] x;

int[] y;

String strbuff;

BufferedReader data = new BufferedReader(new InputStreamReader(

new FileInputStream(filename)));

distance = new int[cityNum][cityNum];

x = new int[cityNum];

y = new int[cityNum];

for (int i = 0; i cityNum; i++) {

// 读取一行数据，数据格式1 6734 1453

strbuff = data.readLine();

// 字符分割

String[] strcol = strbuff.split(" ");

x[i] = Integer.valueOf(strcol[1]);// x坐标

y[i] = Integer.valueOf(strcol[2]);// y坐标

}

data.close();

// 计算距离矩阵

// ，针对具体问题，距离计算方法也不一样，此处用的是att48作为案例，它有48个城市，距离计算方法为伪欧氏距离，最优值为10628

for (int i = 0; i cityNum - 1; i++) {

distance[i][i] = 0; // 对角线为0

for (int j = i + 1; j cityNum; j++) {

double rij = Math

.sqrt(((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j])

* (y[i] - y[j])) / 10.0);

// 四舍五入，取整

int tij = (int) Math.round(rij);

if (tij rij) {

distance[i][j] = tij + 1;

distance[j][i] = distance[i][j];

} else {

distance[i][j] = tij;

distance[j][i] = distance[i][j];

}

}

}

distance[cityNum - 1][cityNum - 1] = 0;

colable = new int[cityNum];

colable[0] = 0;

for (int i = 1; i cityNum; i++) {

colable[i] = 1;

}

row = new int[cityNum];

for (int i = 0; i cityNum; i++) {

row[i] = 1;

}

}

public void solve(){

int[] temp = new int[cityNum];

String path="0";

int s=0;//计算距离

int i=0;//当前节点

int j=0;//下一个节点

//默认从0开始

while(row[i]==1){

//复制一行

for (int k = 0; k cityNum; k++) {

temp[k] = distance[i][k];

//System.out.print(temp[k]+" ");

}

//System.out.println();

//选择下一个节点，要求不是已经走过，并且与i不同

j = selectmin(temp);

//找出下一节点

row[i] = 0;//行置0，表示已经选过

colable[j] = 0;//列0，表示已经走过

path+="--" + j;

//System.out.println(i + "--" + j);

//System.out.println(distance[i][j]);

s = s + distance[i][j];

i = j;//当前节点指向下一节点

}

System.out.println("路径:" + path);

System.out.println("总距离为:" + s);

}

public int selectmin(int[] p){

int j = 0, m = p[0], k = 0;

//寻找第一个可用节点，注意最后一次寻找，没有可用节点

while (colable[j] == 0) {

j++;

//System.out.print(j+" ");

if(j=cityNum){

//没有可用节点，说明已结束，最后一次为 *--0

m = p[0];

break;

//或者直接return 0;

}

else{

m = p[j];

}

}

//从可用节点J开始往后扫描，找出距离最小节点

for (; j cityNum; j++) {

if (colable[j] == 1) {

if (m = p[j]) {

m = p[j];

k = j;

}

}

}

return k;

}

public void printinit() {

System.out.println("print begin....");

for (int i = 0; i cityNum; i++) {

for (int j = 0; j cityNum; j++) {

System.out.print(distance[i][j] + " ");

}

System.out.println();

}

System.out.println("print end....");

}

public static void main(String[] args) throws IOException {

System.out.println("Start....");

TxTsp ts = new TxTsp(48);

ts.init("c://data.txt");

//ts.printinit();

ts.solve();

}

}

血型遗传规律用JAVA怎么写

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; //是否被选择

}

遗传算法解决TSP问题

遗传算法在很多领域都得到应用；从神经网络研究的角度上考虑，最关心的是遗传算法在神经网络的应用。在遗传算法应用中，应先明确其特点和关键问题，才能对这种算法深入了解，灵活应用，以及进一步研究开发。

一、遗传算法的特点

1．遗传算法从问题解的中集开始嫂索，而不是从单个解开始。

这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。

2．遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。

由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。

3．遗传算法有极强的容错能力

遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。

4．遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。

这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。

5．遗传算法具有隐含的并行性

遗传算法的基础理论是图式定理。它的有关内容如下：

(1)图式(Schema)概念

一个基因串用符号集{0，1，*}表示，则称为一个因式；其中*可以是0或1。例如：H=1x x 0 x x是一个图式。

(2)图式的阶和长度

图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用δ(H)表示。对于图式H＝1x x0x x，有0(H)＝2，δ(H)＝4。

(3)Holland图式定理

低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。

遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。

二、遗传算法的应用关键

遗传算法在应用中最关键的问题有如下3个

1．串的编码方式

这本质是问题编码。一般把问题的各种参数用二进制编码，构成子串；然后把子串拼接构成“染色体”串。串长度及编码形式对算法收敛影响极大。

2．适应函数的确定

适应函数(fitness function)也称对象函数(object function)，这是问题求解品质的测量函数；往往也称为问题的“环境”。一般可以把问题的模型函数作为对象函数；但有时需要另行构造。

3．遗传算法自身参数设定

遗传算法自身参数有3个，即群体大小n、交叉概率Pc和变异概率Pm。

群体大小n太小时难以求出最优解，太大则增长收敛时间。一般n＝30-160。交叉概率Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。一般取Pc=0.25-0.75。变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。一般取Pm＝0．01—0．2。

三、遗传算法在神经网络中的应用

遗传算法在神经网络中的应用主要反映在3个方面：网络的学习，网络的结构设计，网络的分析。

1．遗传算法在网络学习中的应用

在神经网络中，遗传算法可用于网络的学习。这时，它在两个方面起作用

(1)学习规则的优化

用遗传算法对神经网络学习规则实现自动优化，从而提高学习速率。

(2)网络权系数的优化

用遗传算法的全局优化及隐含并行性的特点提高权系数优化速度。

2．遗传算法在网络设计中的应用

用遗传算法设计一个优秀的神经网络结构，首先是要解决网络结构的编码问题；然后才能以选择、交叉、变异操作得出最优结构。编码方法主要有下列3种：

(1)直接编码法

这是把神经网络结构直接用二进制串表示，在遗传算法中，“染色体”实质上和神经网络是一种映射关系。通过对“染色体”的优化就实现了对网络的优化。

(2)参数化编码法

参数化编码采用的编码较为抽象，编码包括网络层数、每层神经元数、各层互连方式等信息。一般对进化后的优化“染色体”进行分析，然后产生网络的结构。

(3)繁衍生长法

这种方法不是在“染色体”中直接编码神经网络的结构，而是把一些简单的生长语法规则编码入“染色体”中；然后，由遗传算法对这些生长语法规则不断进行改变，最后生成适合所解的问题的神经网络。这种方法与自然界生物地生长进化相一致。

3．遗传算法在网络分析中的应用

遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。

遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。

TSP中用蚁群算法和遗传算法有区别么?

TSP,只是一个普通但很经典的NP-C问题。具有大的难以想象的解空间。一般的branch-and-bound算法是很难搞定的。于是,人们尝试智能算法,包括遗传算法,蚁群算法,粒子群算法等。遗传算法和蚁群算法都是基于种群的。但是这两个算法有着本质区别。遗传算法的进化机制是基于个体竞争,而蚁群算法的搜索机制则是蚂蚁之间的信息素传导机制下的群体合作。因此,蚁群算法,粒子群算法,人工鱼群算法等,被归纳为群智能算法,成为了一个有别于遗传算法的另一个进化计算领域的分支。由于搜索机制的不同,这两种算法对于不同的问题,具有不同的效率。就拿标准遗传算法和标准蚁群算法来说,应该是蚁群算法更适合求解TSP。然而,无论是遗传算法还是蚁群算法,都有大量的变种算法或者称为改进算法,所以很难简单的说谁更适合TSP。

记得采纳啊

在遗传算法解决Tsp问题中如何保持种群的数量不变啊？

function f=fitness(fmin,fmax,froad)

%this function to computer the fitness this road

%this the f is 0 or 1 froad more less the f more posible 1

if fminfmax

f=1-(froad-fmin)/(fmax-fmin);

elseif fmin==fmax

f=1;

else

'error'

end

遗传算法解决旅行商问题(TSP)一:初始化和适应值

旅行商问题（Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。

设有n个城市，城市i和城市j之间的距离是 。设

那么TSP问题使下面的目标最小：

首先，设置一下参数：

这里假设有10个城市，其坐标定义于pos变量，第一行是各个城市的x坐标，第二行是各个城市的y坐标，比如第一个城市的坐标为(1,1)，第三个城市的坐标为(2,2)。之后计算处各个城市之间的距离。

种群中每个个体，都表示着一个访问城市的路径，这意味着每个个体都要覆盖所有城市，但是只能经过一个城市一次。

根据种群中每个个体中城市的顺序，可以求出这个个体所代表的距离，距离越大，适应度越小，因此用距离的倒数作为个体的适应度值。

tsp遗传java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于tsp问题遗传算法python、tsp遗传java的信息别忘了在本站进行查找喔。