蟻コロニー最適化

本ソフトウェアは蟻コロニー最適化 (ACO: Ant Colony Optimization)を用いて巡回セールスマン問題 (TSP: Traveling Salesman Problem)を解く過程を可視化するものです． 実行中に都市を動かすことでフェロモンの濃度が変化する様子を観察できるのが最大の特徴です． 本ソフトウェアの実行にはお使いのコンピュータにJREがインストールされている必要があります． なお，本ソフトウェアは個人の責任において使用してください．使用の結果生じたいかなる損害についても責任を負いかねますのでご了承ください．

使い方

下の図はMacでプログラムを実行した場合のスクリーンショットです。Windowsで実行した場合にはボタンの配置や色が若干変化します．

画面の説明

  • the number of cities
    都市数を入力します．
  • population size
    個体数，即ち1世代で用いるアリの数を入力します．
  • maximum generation
    最大で何世代学習を行うかを入力します．
  • evaporation rate
    フェロモンの蒸発率を0〜1.0の範囲で入力します．0以下の値が入力された場合は0，1以上の値が入力された場合は1として扱われます．大きいほどフェロモン情報が次世代に持ち越されます．
  • α
    フェロモン情報の優先度です．都市の選択確率はフェロモンの値のα乗に比例します．
  • β
    ヒューリスティック情報の優先度です．都市の選択確率はヒューリスティック（距離の逆数）の値のβ乗に比例します．
  • delay
    1世代当たりの遅延です．この値を小さくすると描画が高速になりますがCPU使用率が大きくなります．
  • runボタン
    このボタンをクリックすることでACOが起動します．
  • stopボタン
    このボタンをクリックすることでACOが一時停止します．停止中は一部のパラメータを変更できます．
  • resumeボタン
    一時停止中にクリックすることでACOが再開します．
  • resetボタン
    都市の配置はそのままでその他の情報をリセットします．runボタンをクリックすることでACOを再び起動することができます．
  • init citiesボタン
    全ての情報をリセットし，都市をランダムに配置し直します．
  • チェックボックス
    current best（現世代の最良個体），overall best（最良個体），pheromone（フェロモン）のうち，ここでチェックをいれたものだけが描画フィールドに描画されます．
  • generation
    現在の世代数を表示します．
  • best at current generation
    現在の世代の最良個体のルートと距離を表示します．
  • overall best
    最良個体のルートと距離を表示します．
  • 描画フィールド
    ここに番号付きの都市，current best（現世代の最良個体，黄色），overall best（最良個体，赤），pheromone（フェロモン，緑）が表示されます．特にフェロモンは濃度が高いと濃く，低いと薄く表示されます．都市はいつでもドラッグして移動することができます．