9-1. 遺伝的アルゴリズム（vcopt）で巡回セールスマン問題を解く（２人のセールスマン編）

#適当な道順を作成
para = np.array([3, 5, 2, 0, 4, 1, 2, 7, 9, 6, 8])
print(para)

#0のインデックス
print(np.where(para==0)[0][0])

#0番目の町を境界に、2つの列に分割（どちらも0はじまり）
para_1 = para[:np.where(para==0)[0][0] + 1][::-1]
para_2 = para[np.where(para==0)[0][0]:]
print(para_1)
print(para_2)

import numpy as np
import numpy.random as nr
import matplotlib.pyplot as plt
from vcopt import vcopt

#巡回セールスマン問題の作成
def create_tsp(town_num):
    
    #町のx座標とy座標の配列を作成
    town_x = nr.rand(town_num)
    town_y = nr.rand(town_num)
    
    #0番目の町を中心に置く
    town_x[0] = 0.5
    town_y[0] = 0.5
    
    return town_x, town_y

#巡回セールスマン問題の評価関数
def tsp_score(para):
    
    #0番目の町を境界に、2つの列に分解（どちらも0はじまり）    
    para_1 = para[:np.where(para==0)[0][0] + 1][::-1]
    para_2 = para[np.where(para==0)[0][0]:]

    #スコアの計算
    score_1 = np.sum(((town_x[para_1][:-1] - town_x[para_1][1:])**2 + (town_y[para_1][:-1] - town_y[para_1][1:])**2)**0.5)
    score_2 = np.sum(((town_x[para_2][:-1] - town_x[para_2][1:])**2 + (town_y[para_2][:-1] - town_y[para_2][1:])**2)**0.5)

    return max(score_1, score_2)

#paraの可視化
def tsp_show_para(para, **info):
    
    #2-opt処理中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    step_num = info['step_num']
    score = info['score']
    
    #プロット（および保存）
    plt.figure(figsize=(6, 6))
    plt.plot(town_x[para], town_y[para], 'ok-')
    #スタート地点を赤丸（中が白）で上書き
    plt.plot(town_x[0], town_y[0], 'or', markerfacecolor='w')
    plt.xlabel('x'); plt.ylabel('y')
    plt.xlim([0, 1]); plt.ylim([0, 1])
    plt.title('step={}, score={}'.format(step_num, score))
    #plt.savefig('save/{}.png'.format(step_num))
    plt.show()
    print()

#poolの可視化
def tsp_show_pool(pool, **info):
    
    #GA中の諸情報はinfoという辞書に格納されて渡されます
    #これらを受け取って使用することができます
    gen = info['gen']
    best_index = info['best_index']
    best_score = info['best_score']
    mean_score = info['mean_score']
    mean_gap = info['mean_gap']
    time = info['time']
    
    #プロット
    plt.figure(figsize=(6, 6))
    #pool_fullを100個まで薄い黒でプロット
    for para in pool[:100]:
        plt.plot(town_x[para], town_y[para], 'ok-', alpha=(2.0/len(pool[:100])))
    #エリートは赤でプロット     
    plt.plot(town_x[pool[best_index]], town_y[pool[best_index]], 'or-')
    #スタート地点を赤丸（中が白）で上書き
    plt.plot(town_x[0], town_y[0], 'or', markerfacecolor='w')
    #タイトルをつけて表示
    plt.xlabel('x'); plt.ylabel('y')
    plt.xlim([0, 1]); plt.ylim([0, 1])
    plt.title('gen={}, best={} mean={} time={}'.format(gen, best_score, mean_score, time))
    #plt.savefig('save/{}.png'.format(gen_num))
    plt.show()
    print()

#巡回セールスマン問題の作成
nr.seed(1)
town_num = 40
town_x, town_y = create_tsp(town_num)

#適当に道順を作成
para = np.arange(town_num)

#2-opt法で最適化
para, score = vcopt().opt2(para,                          #para
                           tsp_score,                     #score_func
                           0.0,                           #aim
                           show_para_func=tsp_show_para,  #show_para_func=None
                           seed=1)                        #seed=None

#結果の表示
print(para)
print(score)

#巡回セールスマン問題の作成
nr.seed(1)
town_num = 40
town_x, town_y = create_tsp(town_num)

#パラメータ範囲
para_range = np.arange(town_num)

#GAで最適化
para, score = vcopt().tspGA(para_range,                    #para_range
                            tsp_score,                     #score_func
                            0.0,                           #aim
                            show_pool_func=tsp_show_pool,  #show_pool_func=None
                            seed=1)                        #seed=None

#結果の表示
print(para)
print(score)