pyevolveによる遺伝的アルゴリズム(3)

pyevolveによる遺伝的アルゴリズム(1)
pyevolveによる遺伝的アルゴリズム(2)

今回はGAで「巡回セールスマン問題」を解いてみます。
「matplotlib」のインタラクティブモードを使い、巡回経路がリアルタイムで変化するようにしました、経路がウネウネと最適化されていく姿を見てるだけでも面白いです。

実行には「numpy」「pyevolve」「matplotlib」の３つのライブラリが必要です、以下のサイトからダウンロードしてください。

http://numpy.scipy.org/
http://pyevolve.sourceforge.net/
http://matplotlib.sourceforge.net/

拠点数、世代数、標本数、突然変異確率をいじると、答えの導き方が変わってくるので、いろいろいじるのも楽しいです。

色々な経路を解いていると解ってくるのですが、拠点数が多くなってくると最適解まで届かない場合が多いです。遺伝子の袋小路に入ってしまうため、突然変異によるブレイクスルー待ちの状態になってしまうのですね。
ああ、ここを直せばいいのにぃ・・・とヤキモキしたりして、子供を見守る親の気持ちになったりします。

GAが最適解に向かわない問題の解決策としては、評価関数をもっと頭よくする必要があります。
状態によって評価関数を差し替えるの手段も有効です。
この巡回問題ならば「経路が交差している場合はペナルティ」などの処理を入れると、もっと精度が上がりそうな気がします。

#coding:utf-8
from pyevolve import GAllele
from pyevolve import G1DList
from pyevolve import Mutators
from pyevolve import Crossovers
from pyevolve import GSimpleGA
from pyevolve import Consts
from pylab import *
from math import sqrt
import random

#設定値
N               = 30    #拠点数
GENERATIONS     = 1000   #世代数
POPULATION_SIZE = 100    #標本数   
CROSSOVER_RATE  = 1.0    #交叉確率(0.0〜1.0)
MUTATION_RATE   = 0.08   #突然変異確率(0.0〜1.0)

#グローバル変数
city_x     = randn(N)    #拠点X座標
city_y     = randn(N)    #拠点Y座標
city_dists = []          #距離表
plot_line  = None        #Plot-line
best_chromosome = None   #最高結果

def create_distmatrix():
    """距離表の作成"""
    global city_dists
    for i in range(N):
        city_dists.append([])
        for j in range(N):
            dx = city_x[i]-city_x[j]
            dy = city_y[i]-city_y[j]
            city_dists[i].append(sqrt(dx**2 + dy**2))

def evolve_callback(ga_engine):
    """1ステップごとのコールバック"""
    global best_chromosome
    cur = list(ga_engine.bestIndividual())
    if best_chromosome != cur:
        best_chromosome = cur
        line_plot.set_xdata([city_x[t] for t in best_chromosome])
        line_plot.set_ydata([city_y[t] for t in best_chromosome])
        draw()

def eval_func(chromosome):
    """評価関数"""
    total=0
    num_cities = len(chromosome)
    for i in range(num_cities):
        j=(i+1)%num_cities
        city_i=chromosome[i]
        city_j=chromosome[j]
        total+=city_dists[city_i][city_j]
    return total

def G1DListTSPInitializator(genome, **args):
    """ 初期化関数 """
    genome.clearList()
    lst = [i for i in xrange(genome.listSize)]
    
    for i in xrange(genome.listSize):
        choice = random.choice(lst)
        lst.remove(choice)
        genome.append(choice)

if __name__ == "__main__":

    create_distmatrix()
    
    #グラフの設定
    ion()       # matplotlib - set intarctive mode
    line_plot, = plot(city_x,city_y,'r', lw=3,zorder=1)
    scatter(city_x,city_y,marker='+', c='r',zorder=2) 
    draw()

    #対立遺伝子(Allele)の設定
    setOfAlleles = GAllele.GAlleles(homogeneous=True)
    a = GAllele.GAlleleList([ i for i in xrange(N) ])
    setOfAlleles.add(a)

    #GAの設定
    genome = G1DList.G1DList(N)
    genome.setParams(allele=setOfAlleles)
    genome.evaluator.set(eval_func)
    genome.mutator.set(Mutators.G1DListMutatorSwap)
    genome.crossover.set(Crossovers.G1DListCrossoverOX)
    genome.initializator.set(G1DListTSPInitializator)
    ga = GSimpleGA.GSimpleGA(genome)
    ga.setGenerations(GENERATIONS)
    ga.setPopulationSize(POPULATION_SIZE)
    ga.setCrossoverRate(CROSSOVER_RATE)
    ga.setMutationRate(MUTATION_RATE)
    ga.stepCallback.set(evolve_callback)
    ga.setMinimax(Consts.minimaxType["minimize"])

    #GA実行
    ga.evolve(freq_stats=100)
    
    #グラフ描画
    evolve_callback(ga)
    show()