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();
}
}
B. 什么是遗传算法
遗传算法是模拟自然界中按“优胜劣汰”法则进行进化过程而设计的算法。Bagley和Rosengerg于1967年在他们的博士论文中首先提出了遗传算法的概念。1975年Holland出版的专着奠定了遗传算法的理论基础。如今遗传算法不但给出了清晰的算法描述，而且也建立了一些定量分析的结果，在众多领域得到了广泛的应用，如用于控制(煤气管道的控制)、规划(生产任务规划)、设计(通信网络设计)、组合优化(TSP问题、背包问题)以及图像处理和信号处理等。
C. 用遗传算法求解TSP问题能获得最优解么
遗传算法属于启发式算法的一种，启发式算法与精确算法的区别之一就是不能得到最优解，但是可以得到次优解。
D. 遗传算法在求解TSP问题中是如何编码解码的 二进制如何编码 如何求解
路径表示是按照城市的访问顺序排列的一种编码方式，是最自然、简单和符合逻辑的表示方法。然而，除非初始基因是固定的，否则这种编码方式不具备唯一性。例如，旅程（5-1-7-8-9-4-6-2-3）与（1-7-8-9-4-6-2-3-5）表示的是同一条旅程，因为路径表示法是遍历了每一个节点，所以不会产生子回路。
考虑到此次研究对象的初始基因是固定的，不会出现漏选，所以运用这种编码方法。
初始种群可以随机产生，也可以通过某种算法生成，但需要保证群体的多样性。在种群初始化时，需要可虑以下几个方面的因素：
1、根据问题固有的知识，设法把握最优解所占的空间在整个问题空间中的分布范围，然后，在次分布范围内设定初始群体。
2、随机生成一定数目的个体，然后从中挑选出最好的个体加入群体。这一过程不断进行迭代，直到初始种群中个体数达到了预先确定的规模。
亲和度设置为1/f f为总路径长度
此后根据城市序号在进行选择，交叉，变异即可
E. tSp Concorder算法原理
tsp问题遗传算法将多目标按照线性加权的方式转化为单目标，然后应用传统遗传算法求解
其中w_i表示第i个目标的权重，f_k表示归一化之后的第i个目标值。我们很容易知道，这类方法的关键是怎么设计权重。比如，Random Weight Genetic Algorithm (RWGA) 采用随机权重的方式，每次计算适应度都对所有个体随机地产生不同目标的权重，然后进行选择操作。Vector-Evaluated Genetic Algorithm (VEGA) 也是基于线性加权的多目标遗传算法。如果有K个目标，VEGA 会随机地将种群分为K个同等大小子种群，在不同的子种群按照不同的目标函数设定目标值，然后再进行选择操作。VEGA 实质上是基于线性加权的多目标遗传算法。VEGA 是第一个多目标遗传算法，开启了十几年的研究潮流。
1.TSP问题是指假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。本文使用遗传算法解决att30问题，即30个城市的旅行商问题。旅行商问题是一个经典的组合优化问题。一个经典的旅行商问题可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。TSP问题可以分为对称和不对称。在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图，而不对称TSP则形成有向图。对称性TSP问题可以将解的数量减少了一半。所以本次实验的TSP问题使用att48数据，可在tsplib中下载数据包。演化算法是一类模拟自然界遗传进化规律的仿生学算法，它不是一个具体的算法，而是一个算法簇。遗传算法是演化算法的一个分支，由于遗传算法的整体搜索策略和优化计算是不依赖梯度信息，所以它的应用比较广泛。我们本次实验同样用到了遗传算法（用MATLAB编写）来解决TSP问题。
F. 遗传算法解决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．遗传算法在网络分析中的应用
遗传算法可用于分析神经网络。神经网络由于有分布存储等特点，一般难以从其拓扑结构直接理解其功能。遗传算法可对神经网络进行功能分析，性质分析，状态分析。
遗传算法虽然可以在多种领域都有实际应用，并且也展示了它潜力和宽广前景；但是，遗传算法还有大量的问题需要研究，目前也还有各种不足。首先，在变量多，取值范围大或无给定范围时，收敛速度下降；其次，可找到最优解附近，但无法精确确定最扰解位置；最后，遗传算法的参数选择尚未有定量方法。对遗传算法，还需要进一步研究其数学基础理论；还需要在理论上证明它与其它优化技术的优劣及原因；还需研究硬件化的遗传算法；以及遗传算法的通用编程和形式等。
G. java中错误：没有为类型 Tsp 定义方法 printBestRoute（），如何改，是在遗传算法实现中出现的问题
那就再定义下这个方法就好了吧
H. 在遗传算法解决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 fmin<fmax
f=1-(froad-fmin)/(fmax-fmin);
elseif fmin==fmax
f=1;
else
'error'
end
I. 遗传算法tsp问题
我有c++的，但基本和c差不多。