×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

遺伝的アルゴリズムで巡回セールスマン問題を解く    

巡回セールスマン問題を遺伝的アルゴリズムで解くプログラムです。
Wikipediaから引用。
遺伝的アルゴリズム(いでんてき-、英語:genetic algorithm、略称:GA)とは、1975年にミシガン大学のジョン・H・ホランド(John Henry Holland)によって提案された近似解を探索するメタヒューリスティックアルゴリズムである。人工生命同様、偶然の要素でコンピューターの制御を左右する。4つの主要な進化的アルゴリズムの一つであり、その中でも最も一般的に使用されている。

詳細な説明は、Wikipedaiを読んでいただくとして、ここで採用したアルゴリズムの簡単にの流れを説明します。
  1. N固体を用意し、現世代のリストに入れる。
  2. 評価関数を適用し、上位X個を次世代のリストへ入れる。(淘汰)
  3. 交叉によりY個の子孫を作り、次世代リストに入れる (交叉は後述)
  4. 突然変異により子孫をつくり、次世代リストに入れる
    このとき、次世代の固体がN個になるように調節する。
  5. 次世代の固体を、現世代のリストに移し変え、2-4をG世代繰り返す。
  6. もっとも評価の良い個体を「解」とする。

これだけを読めばそれほど複雑なことをやっているわけではないことがわかると思います。
問題は、交叉や突然変異をどのように実装するのかということです。
これらを効率よく行うには、巡回する都市の経路データの表現形式が課題となってきます。

例えば、それぞれの都市をA,B,C,D,Eという5つの都市があったとします。
それぞれの都市の位置は、(x,y)という座標で表せますが、それをそのまま配列等に格納したのでは、いろいろと厄介なコードを書かなくてはなりません。
そこで、基準となるルートを設定し、未訪問都市の何番目にあたるかを整数のリストで表すこととします。
このパス表現を順序表現といいます。一方、元のABCDEとう経路表現をここではパス表現といいます。

※ 参照資料:http://aidiary.hatenablog.com/entry/20110109/1294581648

例えば、基準経路 ABCDEに対して、経路 ACEDBを、順序表現で表すと [01210]となります。
最初の 0 ですが、最初訪問する都市が未訪問都市リストの0番目(A)にあたることを表しています。
次に訪れるのは、(このとき、未訪問都市リストからAは除去されている)1番目の都市 C です。
そして、次に訪れるのは、未訪問都市リストの2番目の都市の E となります。
4番目に訪れる都市は、1番目の D。最後は、未訪問都市リストの0番目の都市の B となります

このような表現をとることで、遺伝的アルゴリズムの交叉が簡単に行えるようになります。
交叉とは、2つの固体(経路)から新しい子孫(経路)を残す方法のひとつです。ある点を選び、その後ろの経路を入れ替えるという操作でこれを実現します。
例えば、固体X [01010],固体Y [01210] で考えると3番目以降(0から開始)を入れ替えると [01010], [01210] という固体ができます。
これを元の経路に直してみると、ACBED, ACEDB という経路となります。
こうしてできた経路は、必ず正しい経路となります。同じ都市が重複するようなことは起こりえません。

ここでは、一点交叉の例を示しましたが、このプログラムでは、2点交叉と一様交叉といった交叉を採用しています。

突然変異については、いったんパス表現に戻してから、2つの都市の入れ替えなどを行っています。

■実行途中


■実行終了


■Newボタンを押して別の問いを解く


作成したプログラムは、もう少しチューニングが必要なようで、(都市の数が多いと)最適解が得られないこともあります。
僕はこの手の専門家ではないし、十分な検証時間をとることもできないので、どこをどう改良したらよいのかまでは、検討できていません。

この手のアルゴリズムは、最善手を求めるのではなく、ある時間内に、できるだけ良い手を探し出すのが目的ですから、これでも目的は達成できてると考えることもできますが...

興味のある人は、ぜひこのプログラムを改良してみてください。

WindowsFormsに依存しないようにクラス分割をしていますので、WPFなど他のプラットフォームにも移植するのはそれほど難しくないと思います。

以下、C#のソースコードを掲載します。

■Gene.cs
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;

namespace GeneticAlgorithm {
    // Gene(遺伝子) 一つの遺伝子で一種類の巡回ルートを表す
    public class Gene {
        private Random rnd = new Random();
        private static List<Point> _origin;
        private int[] _codes;
        private int _size;

        // コンストラクタ
        public Gene(List<Point> route) {
            _size = route.Count;
            _codes = Encode(route);
        }

        // コンストラクタ
        public Gene(int[] codes) {
            _size = codes.Length;
            _codes = (int[])codes.Clone();
        }

        // 最初の位置を記憶しておく。Encode、Decodeするのに必要。
        public static void SetOrigin(List<Point> origin) {
            _origin = origin.ToList();
        }

        // 複製する
        public Gene Clone() {
            return new Gene(this.Encode());
        }

        // 順序表現に変換する (交叉による致死個体の生成を防ぐため)
        private int[] Encode(List<Point> route) {
            List<int> codes = new List<int>();
            List<Point> temp = _origin.ToList();
            for (int i = 0; i < _size; i++) {
                int n = temp.FindIndex(x => x == route[i]);
                temp.RemoveAt(n);
                codes.Add(n);
            }
            return codes.ToArray();
        }

        // 順序表現に変換する (既に求めてある)
        public int[] Encode() {
            return _codes;
        }

        // 順序表現をPointのリストに戻す
        public List<Point> Decode() {
            List<Point> route = new List<Point>();
            List<Point> temp = _origin.ToList();
            foreach (var code in _codes) {
                route.Add(temp[code]);
                temp.RemoveAt(code);
            }
            return route;
        }

        // 評価
        public double Score {
            get {
                double score = 0;
                List<Point> route = Decode();
                for (int i = 0; i < route.Count; i++) {
                    Point a = route[i];
                    Point b = (i == route.Count - 1)
                                ? route[0]
                                : route[i + 1];
                    score += a.GetDistance(b);
                    //score += Math.Abs(a.X - b.X);
                }
                return score;
            }
        }

        #region 突然変異
        // 変異 ここでは2つのPointを入れ替える
        // 一つの個体から3つの子孫を作る
        // 改善されなければ、返さない
        public IEnumerable<Gene> MutateChange() {
            double val = this.Score;
            for (int i = 0; i < 3; i++) {
                Gene newGene = new Gene(Swap(this.Decode()));
                if (val > newGene.Score)
                    yield return newGene;
            }
        }

        // 変異 都市1を都市2の位置に移動する。
        // 一つの個体から3つの子孫を作る
        // 改善されなければ、返さない
        public IEnumerable<Gene> MutateSlide() {
            double val = this.Score;
            for (int i = 0; i < 3; i++) {
                Gene newGene = new Gene(Slide(this.Decode()));
                if (val > newGene.Score)
                    yield return newGene;
            }
        }

        // 変異 都市1から都市2への経路を反転する。
        // 一つの個体から3つの子孫を作る
        // 改善されなければ、返さない
        public IEnumerable<Gene> MutateReverse() {
            double val = this.Score;
            for (int i = 0; i < 3; i++) {
                int ix1 = rnd.Next(1, _size);
                int ix2 = rnd.Next(ix1 + 1, _size);
                var list = this.Decode().ToList();
                list.Reverse(ix1, Math.Abs(ix2 - ix1));
                Gene newGene = new Gene(list);
                if (val > newGene.Score)
                    yield return newGene;
            }
        }

        // ランダムに選んだ値の位置を変更する。
        public List<Point> Slide(List<Point> list) {
            int ix1 = rnd.Next(1, _size);
            int ix2 = rnd.Next(1, _size - 1);
            List<Point> temp = list.ToList();
            Point pt = temp[ix1];
            temp.RemoveAt(ix1);
            temp.Insert(ix2, pt);
            return temp;
        }

        // 変異 ここでは2つのPointを入れ替える
        public List<Point> Swap(List<Point> list) {
            List<Point> child = list.ToList();
            double val = this.Score;
            int ix1 = rnd.Next(1, _size);
            int ix2 = rnd.Next(1, _size);
            Point temp = child[ix1];
            child[ix1] = child[ix2];
            child[ix2] = temp;
            return child;
        }

        #endregion

        #region 交叉
        // 交叉
        public IEnumerable<Gene> Crossover(Gene spouse) {
            double score = Math.Min(this.Score, spouse.Score);
            // 2点交叉
            int[] temp1 = this.Encode();
            int[] temp2 = spouse.Encode();
            int i = rnd.Next(1, _size - 1);
            int j = rnd.Next(1, _size - 1);
            for (int n = i; n <= j; n++) {
                int temp = temp1[n];
                temp1[n] = temp2[n];
                temp2[n] = temp;
            }
            Gene child = new Gene(temp1);
            if (child.Score < score)
                yield return child;
            child = new Gene(temp2);
            if (child.Score < score)
                yield return child;
        }

        public IEnumerable<Gene> Crossover2(Gene spouse) {
            double score = Math.Min(this.Score, spouse.Score);
            // 一様交叉
            int[] temp1 = this.Encode();
            int[] temp2 = spouse.Encode();
            for (int i = 1; i < _size - 1; i++) {
                if (rnd.Next(0, 2) == 0) {
                    int temp = temp1[i];
                    temp1[i] = temp2[i];
                    temp2[i] = temp;
                }
            }
            Gene child = new Gene(temp1);
            if (child.Score < score)
                yield return child;
            child = new Gene(temp2);
            if (child.Score < score)
                yield return child;
        }
        #endregion

        // 無条件に子孫を残す ここではSlideを採用
        public Gene Bean() {
            return new Gene(this.Slide(this.Decode()));
        }

        // デバッグ用
        public override string ToString() {
            string s = string.Join(",", _codes.Select(n => n.ToString()).ToArray());
            string s2 = string.Join(",", Decode().Select(n => n.X.ToString()).ToArray());

            return s + " - " + s2 + " - " + this.Score.ToString();
        }
    }

    // Geneの比較クラス 
    class GeneComparer : IEqualityComparer<Gene> {
        public bool Equals(Gene x, Gene y) {
            var obj1 = x.Encode();
            var obj2 = y.Encode();
            return obj1.SequenceEqual(obj2);
        }

        public int GetHashCode(Gene obj) {
            return (int)(obj.Score * 100);
        }
    }


}



■TravelingSalesmanProblem.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Drawing;
using System.Threading;

namespace GeneticAlgorithm {
    public class GaEventArgs : EventArgs {
        public Gene Gene { get; set; }
    }

    // 遺伝的アルゴリズムで巡回セールスマン問題を解く
    public class TravelingSalesmanProblem {
        // 現世代 個体群
        private List<Gene> Population1 = new List<Gene>();
        private List<Gene> Population2 = new List<Gene>();
        // 個体数
        private const int NumOfPopulation = 100;
        private const int NumOfSurvival = 40;
        private const int NumOfCróssing = 30;
        private const int NumOfMutation = NumOfPopulation - NumOfSurvival - NumOfCróssing;
        private const int LimitOfNoEvolution = 500;
        private int MutateRate = 1;

        // 初期化 
        public void Initialize(List<Point> origin) {
            // origin が仮の巡回ルートとする
            Population1.Add(new Gene(origin));
            // 適当にシャッフルして他の巡回ルートも作成する
            for (int i = 1; i < NumOfPopulation; i++) {
                Population1.Add(new Gene(origin.Shuffle()));
            }
        }

        public event EventHandler<GaEventArgs> OnChanged;

        public Gene Solve() {
            // 次世代の 個体群を用意
            double min = double.MaxValue;
            Gene best = null;
            Gene better = null;
            int count = 0;
            while (count < 1000) {
                // 良い順に並び替える
                Population1 = Evaluate();
                // 現世代で最も良い遺伝子を記憶する
                better = Population1.First();
                // その評価関数を呼び出し、scoreに入れる
                double score = better.Score;
                if (score < min) {
                    // 現世代でスコアが良くなっていれば下記の処理をする
                    // 世代が上がっても進化しないこともあり得る。
                    count = 0;
                    min = score;
                    best = better.Clone();
                    if (OnChanged != null) {
                        OnChanged(this, new GaEventArgs { Gene = best });
                    }
                    Thread.Sleep(200);
                } else {
                    count++;
                }

                Population2.Clear();
                // 選択・淘汰
                Population2.AddRange(Population1.Take(NumOfSurvival));

                if (count % 10 == 9) {
                    // なかなか進化しない場合は、新しい種を入れる必要がある。
                    // 変異率を変えることで対応
                    MutateRate++;
                }
                // 交叉(自分よりも良い子孫だけが登録される)
                Population2.AddRange(BearByCrossover().Take(NumOfCróssing));
                // 突然変異 (自分よりも良い子孫だけが登録される)
                Population2.AddRange(BearByMutate().Take(NumOfMutation));

                // 不足分を補う 
                // ここでは、無条件に変異させたものを登録することで、良い子孫ができることを期待
                int shortage = NumOfPopulation - Population2.Count;
                var topGene = Population2.First();
                for (int i = 0; i < shortage; i++) {
                    Population2.Add(topGene.Bean());
                }
                Population1 = Population2;
            }
            return best;
        }

        // 評価をし、良い順に並び替える。
        private List<Gene> Evaluate() {
            var sorted = Population1.OrderBy(g => g.Score)
                        .Distinct(new GeneComparer())
                        .ToList();
            return sorted;
        }

        private Random rnd = new Random();

        // 子孫を残す (交叉)
        private IEnumerable<Gene> BearByCrossover() {
            int count = Population1.Count;
            for (int loop = 0; loop < 5; loop++) {
                for (int i = 0; i < NumOfPopulation; i++) {
                    int index1 = rnd.Next(0, 5);  // できるだけ良い遺伝子と交叉させるため
                    int index2 = rnd.Next(0, count);
                    while (index1 == index2) {
                        index2 = rnd.Next(0, count);
                    }
                    Gene g1 = Population1[index1];
                    Gene g2 = Population1[index2];
                    if (rnd.Next(2) == 0) {
                        foreach (var x in g1.Crossover(g2))
                            yield return x;
                    } else {
                        foreach (var x in g1.Crossover2(g2))
                            yield return x;
                    }
                }
            }
        }

        // 子孫を残す (変異)
        private IEnumerable<Gene> BearByMutate() {
            int count = Population1.Count;
            for (int loop = 0; loop < 5; loop++) {
                for (int i = 0; i < count; i++) {
                    if (rnd.Next(100) > MutateRate) {
                        if (rnd.Next(2) == 0)
                            foreach (var x in Population1[i].MutateChange())
                                yield return x;
                        else
                            foreach (var x in Population1[i].MutateSlide())
                                yield return x;
                    } else {
                        foreach (var x in Population1[i].MutateReverse())
                            yield return x;
                    }
                }
            }
        }
    }


}



■PathGenerator.cs
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;

namespace GeneticAlgorithm {
    public static class PathGenerator {
        public static List<Point> MakeInitialPath() {
            var path = new List<Point>();
            path.Add(new Point(80, 60));
            path.Add(new Point(105, 160));
            path.Add(new Point(110, 90));
            path.Add(new Point(210, 75));
            path.Add(new Point(90, 120));
            path.Add(new Point(65, 100));
            path.Add(new Point(140, 130));
            path.Add(new Point(70, 130));
            path.Add(new Point(130, 40));
            path.Add(new Point(180, 105));
            path.Add(new Point(220, 110));
            path.Add(new Point(240, 90));
            path.Add(new Point(220, 150));
            return path;
        }

        public static List<Point> MakeRandom() {
            var path = new List<Point>();
            Random rnd = new Random();
            int count = rnd.Next(10, 20);
            for (int i = 0; i < count; i++) {
                int x = rnd.Next(30, 220);
                int y = rnd.Next(30, 180);
                path.Add(new Point(x, y));
            }
            return path;
        }
    }
}



■Form1.cs
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;
using System.Threading;

namespace GeneticAlgorithm {
    public partial class Form1 : Form {
        public Form1() {
            InitializeComponent();
        }

        // 位置を保持したリスト
        private List<Point> _path = new List<Point>();

        // 初期の位置を設定する
        private void Form1_Load(object sender, EventArgs e) {
            _path = PathGenerator.MakeInitialPath();
        }

        // Solveボタンを押したときの処理 (スレッド起動)
        private void button1_Click(object sender, EventArgs e) {
            this.toolStripStatusLabel1.Text = "";
            this.toolStripStatusLabel2.Text = "";
            this.Cursor = Cursors.WaitCursor;
            Thread th = new Thread(Work);
            th.Start();
        }

        // 求めた答え
        private Gene ans = null;

        // Generationクラスを使って問題を解く
        private void Work() {
            Gene.SetOrigin(_path);
            var tsp = new TravelingSalesmanProblem();
            tsp.OnChanged += new EventHandler<GaEventArgs>(tsp_OnChanged);
            tsp.Initialize(_path);
            ans = tsp.Solve();
            this.Invoke((MethodInvoker)delegate {
                this.toolStripStatusLabel1.Text = " Finished";
                this.Cursor = Cursors.Arrow;
            });
            this.Invalidate(this.ClientRectangle);
        }

        // 世代が変わるごとに当イベントハンドラが呼び出される
        void tsp_OnChanged(object sender, GaEventArgs e) {
            ans = e.Gene;
            Gene Koho = e.Gene;
            this.Invalidate(this.ClientRectangle);
        }

        // フォームの描画 (初期状態の描画 と 途中の状態の描画)
        private void Form1_Paint(object sender, PaintEventArgs e) {
            if (ans != null) {
                var list = ans.Decode();
                foreach (var p in _path) {
                    e.Graphics.DrawEllipse(new Pen(Color.Blue, 2), p.X-1, p.Y-1, 3, 3);
                }
                e.Graphics.DrawPolygon(new Pen(Color.Blue, 1), list.ToArray());
                toolStripStatusLabel2.Text = string.Format("総距離={0:#.##}",ans.Score);
            } else {
                e.Graphics.Clear(Color.White);
                foreach (var p in _path) {
                    e.Graphics.DrawEllipse(new Pen(Color.Blue, 2), p.X-1, p.Y-1, 3, 3);
                }
            }
        }

        // 新しいPoint群を生成
        private void button2_Click(object sender, EventArgs e) {
            ans = null;
            _path = PathGenerator.MakeRandom();
            this.Invalidate(this.ClientRectangle);
        }
    }
}