旅行商问题的近似最优解（局部搜索、模拟退火、遗传算法）

private double fitness; // 适应度
private double selectedRate; // 被选中的概率，归一化处理
@Override
public int compareTo(Species o) {
    if (getRouteLength() < o.getRouteLength()) {
        return -1;
    } else if (getRouteLength() == o.getRouteLength()) {
        return 0;
    } else {
        return 1;
    }
}

/**
 * 获得适应度
 * @return 适应度
*/
public double getFitness() {
    updateFiness(); // 返回之前必须先更新（如果需要）
    return fitness;
}
/**
 * 计算并设置适应度
*/
private void calculateAndSetFitness() {
    updateLength(); // 计算适应度之前必须更新长度
    this.fitness = 1.0 / getRouteLength();
}

/**
 * 设置被选中的概率，归一化处理
 * @param selectedRate 被选择的概率，归一化处理
*/
public void setSelectedRate(double selectedRate) {
    this.selectedRate = selectedRate;
}

/**
 * 逆转给定区间
 * @param left 左端点（包含）
 * @param right 右端点（包含）
*/
public void reverse(int left, int right) {
    // 逆转
    while (left < right) {
        City c = routeList.get(left);
        routeList.set(left, routeList.get(right));
        routeList.set(right, c);
        ++left;
        --right;
    } 

// 直接把这一段父亲的基因复制到孩子对应的部分
for (int i = beginIndex; i < endIndex; ++i)
    list.set(i, father.get(i));

// 孩子缺少的基因从母亲那里拿
int i = 0;
// 从头开始遍历母亲的基因
for (int j = 0; j < size; ++j) {
    if (i == beginIndex)
        i = endIndex; // 跳过父亲那一段
    City c = mother.get(j); // 获取母亲的基因
    // 如果母亲的基因已经在孩子身上，就跳过，否则加入
    if (!list.contains(c)) { 
        list.set(i, c);
        i++;
    }
}

// 随机选择一段基因，逆序
int left = (int) (Math.random() * sp.size());
int right = (int) (Math.random() * sp.size());
if (left > right) {
    int tmp = left;
    left = right;
    right = tmp;
}
sp.reverse(left, right);

// 直接把个体丢掉优先级队列中，由于个体实现了Comparable接口，所以距离短的方案表现好，优先级高
PriorityQueue<Species> pq = new PriorityQueue<Species>();
pq.addAll(group);
// 清空种群，然后按照个体的表现从好到差放到种群中
group.clear();
while (!pq.isEmpty()) { // 要么放完
    group.add(pq.poll());
    if (group.size() == capacity) // 要么超过了最大容量就不放了
        break;

double rate = Math.random() / 100.0;
Species oldPoint = origin.get(i);
while (oldPoint != null && !oldPoint.equals(best))
{
 if (rate <= oldPoint.getSelectedRate()) {
  group.add(oldPoint);
   break;
 } else {
  rate = rate - oldPoint.getSelectedRate();
 }
}

for (int i = 1; i <= talentNum; i++) {
 group.add(best);// 复制物种至新表
if (oldPoint == null || oldPoint.equals(best)) 
 group.add(origin.getLast());

/**
 * MetroPolis准则
 * 
 * @param bestRoute
 *            最优解
 * @param currentRoute
 *            当前解
 * @param currentTemperature
 *            当前温度
 * @return MetroPolis准则的评估值
 */
private static double metropolis(Route bestRoute, Route currentRoute, double currentTemperature) {
    double ret = Math.exp(-(currentRoute.getRouteLength() - bestRoute.getRouteLength()) / currentTemperature);
    return ret;
}

/**
 * 能够接受劣解的概率
 * 
 * @param currentTemperature
 *            当前温度
 * @return 能够接受劣解的概率
*/
private static double getProbabilityToAcceptWorseRoute(double currentTemperature) {
    return (currentTemperature - ConstantValue.CHILLING_TEMPERATURE)
        / (ConstantValue.INITIAL_TEMPERATURE - ConstantValue.CHILLING_TEMPERATURE);
}

// 用shuffle随机一条路径作为初始解，并复制一份作为初始最优解

while (ConstantValue.CHILLING_TEMPERATURE < currentTemperature) {
    double p = getProbabilityToAcceptWorseRoute(currentTemperature);
    for (int i = 0; i < ConstantValue.SIMULATE_ANNEA_ITERATION_TIMES; i++) 
        // 产生邻域
        if (neighbourRoute.getRouteLength() <= bestRoute.getRouteLength()) {
            // 如果新解比当前解优，接受
        } else if (metropolis(bestRoute, neighbourRoute, currentTemperature) > p) {
            // 否则按照Metropolis准则确定接受的概率
        }
    }
    // 按照给定的速率降温
}

while (successfullyChanged != 0 && changed != 0) {
 Route neighbour = route.generateNeighbour();
 if (neighbour.getRouteLength() <= route.getRouteLength()) {
  route = neighbour;
  successfullyChanged--;
 }
 changed--;
}

遗传算法：
City [index=2, x=2, y=0] -> City [index=4, x=2, y=1] -> City [index=3, x=1, y=1] -> City [index=1, x=1, y=0] -> 
RouteLength = 4.0
局部搜索：
City [index=3, x=1, y=1] -> City [index=1, x=1, y=0] -> City [index=2, x=2, y=0] -> City [index=4, x=2, y=1] -> 
RouteLength = 4.0
模拟退火算法：
City [index=4, x=2, y=1] -> City [index=2, x=2, y=0] -> City [index=1, x=1, y=0] -> City [index=3, x=1, y=1] -> 
RouteLength = 4.0

10
1 0 0
2 12 32
3 5 25
4 8 45
5 33 17
6 25 7
7 15 15
8 15 25
9 25 15
10 41 12