前言

这个课设就是给用户一个框，然后鼠标移动的时候显示鼠标的点所在的位置。
选取任意个点然后发送给服务器，计算一条从选择的第一个到最后一个的距离。
使用遗传算法，使用D3可视化库。

前端部分

使用CSS样式将需要点击的区域和body区域设置不同的样式。然后所有的内容都是用JavaScript完成，对于JavaScript的基本知识不做过多介绍，这也是一门面向对象的语言。

首先使用D3可视化库的对象在body后面追加(append)一个SVG对象，点击区域使用SVG对象，然后在SVG对象上设置属性(attr)，设置宽为1000，长为500，将其样式设置为box的样式。

然后创建两个对象，一个对象用来画圆，另外一个对象用来显示该点坐标，画圆的属性设置为半径为5，属性设置为不显示（为了在下面的事件中显示），另外一个对象用来显示文本，属性设置红色，字体大小为11px，字体设置为sans-serif，属性同样是不显示。代码写法如下，var yuan = svg.append(“circle”).attr(“r”, 5).attr(‘class’,’move1’);使用svg对象的append方法追加一个circle标签的圆，然后设置圆的属性。

使用SVG对象绑定一个鼠标移动的事件，svg.on(‘click’,function(event))，在function(event)后面使用花括号写JavaScript的函数。在SVG对象的区域内如果有鼠标移动即可触发该事件，该事件的作用是将画圆和显示坐标的对象display的属性变成block状态，这样会跟随鼠标的移动而显示，便于用户实时查看所选点的坐标。然后对鼠标位置进行判断。如果超过了950则进行显示的移动，因为默认的显示是在点的右侧,所以这样的情况下将显示的坐标会在区域外，所以进行判断将显示的text文本放在左侧。

然后进行SVG对象的click操作绑定，当在SVG对象中进行点击操作的时候调用显示的点击反馈，使用的是一个mo的js动画图形库来进行反馈。然后在反馈后使用D3图形库的追加方式画出点击位置的圆和该点的坐标显示。然后调用ajax()的JavaScript函数。这个函数在布局内容结束后讲到。点击之后结果展示如图：

在显示布局结构上还有几个进行点击的按钮，使用遗传算法进行计算最短路径，使用基本的贪心算法来计算最短路径和一个进行重置的按钮。
在ajax.js文件中还定义了数据反馈的打印。在服务器进行数据的计算后返回的点的坐标。调用JavaScript的print()函数进行连线的打印。代码情况如下：

//接受数据后的画线和输出信息代码
function print(){
	//追加画线的功能
	var x1="",y1="",x2="",y2="",pos1="",pos2="";
	for(var i=1;i<=len-4;i++){
		pos1='a'+i;
		pos2='a'+(i+1);
	    svg.append("line")
	       .attr("x1",a[pos1].x)
	       .attr("y1",a[pos1].y)
	       .attr("x2",a[pos2].x)
	       .attr("y2",a[pos2].y)
	       .attr("stroke","black")
	       .attr("stroke-width","5");
	}
	//追加输出的信息文本
	d3.select("body").append("p");//相对按钮标签换行
	var text= d3.select("body")
		.append("text")
		.text(function(d){
			return "计算使用时间："+a.time+
				"ms  路径距离："+a.distance;
		});
}

接口部分

使用的ajax技术，具体的话可以看我之前写的一篇博客—>java使用tomcat&原生ajax

后台部分

首先说遗传算法吧，这个算法是一种启发式算法，主要就是模拟生物进化的理论来不断优化答案，当进化次数够多的时候可以找到最优的路径。在下面主要使用了一种类似交叉运算的方法进行交配，然后使用突变为进化造成可能的小惊喜。基本使用的都是随机数，Math.random()返回一个大于等于0.0小于1.0取值范围的值，注意这里取不到1.0这个数。下面写遗传算法的思想在代码中的体现。

City类：

在City类中定义的就是每个点的坐标，在遗传算法中表示的是一个基因，然后重载了一个取得String类型的函数，然后定义了一个计算两个City之间距离的函数。

Tour类：

City表示的是每个点，然后多个点按照顺序排的顺序，表示的就是一条路径，在遗传算法中对应的就是一个个体。这个Tour类的实现方法使用的是一个ArrayList类型的数组来进行数据的储存。然后为这个写了初始化方法，将destinationCities对象中的路径依次加入到ArrayList的数组中。

getDistance()方法：作用是得到这条路径的距离。从前往后依次调用City类的distanceTo()方法来计算。最后返回距离之和即可。还有getCity()方法和重载的toString()方法。

Population类：

Population类表示很多个Tour(路径)的集合。在遗传算法中的意义就是一个种群，种群内部的个体之间互相交配子代变异来得到新的种群。Population类的实现方式是通过一个Tour类型的数组。

在其中值得一提是一个getFittest()方法，用来得到该种群中最优的个体也就是我们需要最优解。通过一个fitness值来进行判断，这个值的就是distance取倒数后得到的一个评估数。如果并没有赋值的话那么就调用getdistance()方法计算distance得到fitness的值。在写代码的过程中发现自己自己对于对象的属性length和getSize()方法之间的区分并不是很清楚，然后发现一个是对象，另一个是方法之后也就敏锐的察觉了问题。

GA类：

这个类的作用用来进行种群的进化换代。首先在进化的过程中首先交配创造下一代种群。进行两个个体的交配，调用crosscover()方法进行交配。

crosscover()传入两个Tour类型的路径，然后使用随机数得到两个数，通过这两个数确定一个区间，孩子路径集成父代1该区间的内容，然后按照父代2的顺序依次扫描子代的部分，如果没有的话将该City插入到孩子中，保证孩子路径中各个City的唯一性。

在交配完之后，进行概率性的变异，设置的变异率是1.5%，如果随机数得到的结果小于设置的变异率，那么就对该对象进行变异操作，随机选择两个点进行交换位置完成变异。

TSP_GA类：

这个类的作用是用来调用GA或者是Normal中的方法，用来进行城市的加入和中间字符串的转化。在其中进行种群的进化操作和清除操作。因为在计算完一个之后需要清除其中的数据避免对下一次的计算造成影响。

Normal类：

这个类是使用普通贪心来计算路线的一个类，这个的使用在之前需要判断在路径中的基因的个数，因为如果只有一个点的话会产生访问一个不存在的对象的情况，而是程序运行的过程中产生抛出异常的情况。在计算的过程中用nowCity对象来标记当前所指向的City的位置，通过pos的值调用getCity()的方法来找到下一个点的位置，维护一个min的路径最小值。然后遍历更新，当加入一个点到ans中去时便将这个点从原有路径中删除。

Routing类：

这个类的继承于HttpServlet，写public的doGet和doPost方法便可以来进行流程控制。负责加入数据或处理请求等。

调试中遇到的问题：

问题1

前端初版本使用的document.onlick来进行鼠标事件的操作。但使用这个的结果是无法方便地对该输入区域进行JavaScript函数调用的设置，而使键入和按钮之间的功能正确区分。
解决方法：使用D3可视化库插入SVG对象，对SVG对象进行事件的绑定，同时给SVG对象进行CSS样式参数的设置来改变该区域的颜色。

问题2

在进行接口的客户端和服务器传递解析数据，这部分耗费了大量的时间和精力，在网上很难找到原生的JavaScript详细使用ajax的例子，但是从来没接触过这方面的知识，短时间内难以掌握jq等js库的传值方法，而且根本不知道json的数据格式和传值的方法，然后寻找格式调试很久才让两边的通信正常。（等稍微有空去整理博客供后来者学习）
在期间使用了chrome浏览器的开发者选项，更加直观得对js的内容有了更加深入的了解，对http的报文结构方式等也有了一定的认识。

问题3

严重: Servlet.service() for servlet [Routing] in context with path [/java_big] threw exception和一个报错java.lang.NumberFormatException: null经过百度查找才知道是因为传过去的值为null，在使用hang1=Integer.parseInt(req.getParameter(“event.clientY”));在使用这句的时候因为int型不能再进行转换所以出错。
在解决JavaScript后台解析问题的时候传值中一直出现问题。然后使用chrome的开发者选项排查错误。

经过一番调试，发现在js中的数据值已经正常，但是服务器后台一直接收不到，如果使用form的表单数据却可以正确传输。一直找不到传不过去的原因。后来看了几十篇博客，才发现是一个context首部值没有进行设置。
在这个过程中花费了很多的时间，从使用jsp转到使用两个html网页，使用iframe框架结构来进行板块的划分，然后发现数据处理和信号之间有着逻辑性的错误，而且对于网页和JavaScript等技术并不熟悉，最终才处理成了现在这个样子。

问题4

普通贪心算法的问题：这个问题使用每次的贪心算法看似比较正确，其实不然，脑子比较笨，最初没有想到这个问题，还是稀里糊涂地在做网页的数据传输。现在给出这个算法问题的反例。左上角是起点，右上角是终点（右上角和左下角的两个点是等价的关系）

如左边使用贪心算法，每次找最短的路径，该路径的长度之和为200√2，而遗传算法计算所得的结果是100*（1+√2）。所以得出普通贪心并不能得到正确的结果。
这个原因是什么怎么回事呢，我也思考了许久。最初认为这个的原因是因为最后的一个终点是不能先加入到路径中，所以可能在最后几个点的时候往另一个方向跑，而使距离变远，但是这个想法也只是想对了一半。这个应该是一个局部贪心和全局贪心的问题。
虽然每次选择离自己最近的一个点，但是在全局上面来看并不是这样的。这里举一个动态规划的例子。如果我们有面值为10元、6元和1元的纸币若干枚，如何用最少的纸币找零13元？贪心策略：10元一张，1元三张，共四张。最优策略：6元两张，1元一张，共三张。如果使用普通贪心的方法，那么需要4张才能找零。这个问题的错误和我们的普通贪心的错误在一定程度是一样的。
可以使用数据结构中的迪杰斯特拉算法等算法来进行计算。时间有限，没有再写第三种方法了。

后记

这个遗传算法用的比较浅显，但是结构层次非常清晰，在一个大佬的代码改来的，大佬遗传算法最短路github地址
如果对具体的实例想自己操作一下，我的内容放在github上面，第一次做写的有点烂–>master分支链接
使用D3可视化库看的教程在这里咯—>D3可视化库教程整理
最后再次感谢一下大佬巭孬嫑莪(叫SYSTEM，要我写这个名字～)的帮助，ajax调试了好久。