AI人工知能？組み合せ最適化問題、量子アニーリング、焼きなまし

Jun Makino @jun_makino

ちなみに、これくらいならSA使うまでもなく求められる、というのは誰か専門家が書いてるであろう。

Umepon @shunji_umetani

とりあえず手元のPCでどの程度の大きさの巡回セールスマン問題が解けるのか知りたい人はConcordeを試して欲しい．ちなみに最新版は2003年です． math.uwaterloo.ca/tsp/concorde/i…

笑い猫 @bokudentw

@jun_makino math.uwaterloo.ca/tsp/concorde/b…　厳密法アルゴリズムによるベンチマークはここで数百都市から１０００都市以上まで解かれています。解は当然厳密解です。この手の話題が出るたびに何度でもいわないといけませんが、やさしい問題＝インスタンスはベンチマークとして使えません。３２都市では小さすぎ

ｈｒｋ先生 @Prof_hrk

@jun_makino SA実行時の収束条件はどの値を使いましたか？デジタルアニーラ評価では99％としているみたい。

Jun Makino @jun_makino

@Prof_hrk そこまで真面目にやってません。 それっぽい解がでました程度。

Jun Makino @jun_makino

@bokudentw はい、その通りです。

Umepon @shunji_umetani

math.uwaterloo.ca/tsp/index.html に巡回セールスマン問題に関する情報が良くまとまっています．1954年には49都市，2004年には24978都市，これまでに85900都市の問題例が解かれた記録があります．

Umepon @shunji_umetani

一方で，ヒューリスティクスに関して言えば，最適値からの誤差が1%以内で良ければ100万都市でも達成することはそれほど難しくはありません．

Umepon @shunji_umetani

ただし，巡回セールスマン問題は比較的扱い易い問題なのか？と言うと，多分そうではなく，数十年に渡る多くの研究の積み重ねの成果だろうと言うのが個人的な感想です．一般に，解が順列で記述されるタイプの問題は扱いが難しいと言う印象です．

Hideyuki Tanaka @tanakh

@Hishinuma_t (´･_･`)どうもAIエンジニアです。

Umepon @shunji_umetani

もう少し，巡回セールスマン問題と一口に言っても，ここまでの話題は主にユークリッド巡回セールスマン問題と呼ばれる特殊形に関する結果です．これまでに多種多様な巡回セールスマン問題のバリエーションが研究されてきたので，それらの成果については注意深く確認する必要があります．

Umepon @shunji_umetani

最後に，巡回セールスマン問題に興味を持たれた方には，山本芳嗣，久保幹雄「巡回セールスマン問題への招待」と，ウィリアム・J・クック「驚きの数学 巡回セールスマン問題」をおすすめします．

Nobutaka Shimizu @knewknowl

@shunji_umetani ここでいう「解かれた」とは、厳密解が得られたという意味ですか？ (だとすると、なぜ厳密解が得られたと確認できたのかが少し気になりました)

Jun Makino @jun_makino

ちなみに日立も富士通も量子とはいってない。そこは線がひけるかも。

ダンボルギーニ斎藤ጿኈ ቼ ዽ ጿ @ritzberry

内閣府：「量子コンピューター」と呼ばず　異論相次ぎ - 毎日新聞 mainichi.jp/articles/20180…

Umepon @shunji_umetani

@knewknowl 多くの厳密解法では，最適な巡回路長に対して上界（の最小化）と下界（の最大化）を並列に計算します．上界と下界が一致した時点でそれが最適な巡回路長であることが示されます．ちなみに，組合せ最適化問題では緩和問題を使って下界を求めることが多いです．

Nobutaka Shimizu @knewknowl

@shunji_umetani やはりそんな感じでしたか. 主双対っぽいですね. 勉強になります.

Hirotaka Ono (小野 廣隆) @hirotaka_ono

TSPに限らず、組合せ最適化問題はNP困難であってもそれぞれのインスタンスにおいては最適解がきちんと得られることがそれなりにあるということがあまり知られていないのだなあ。。

chunjp @chunjp

最適解だけでなく近似保証のある解まで含めると解けるクラスの問題はかなり多いんですよねぇ

Umepon @shunji_umetani

@knewknowl まさにその通りです．主双対法では主問題の求解と双対問題の求解が連携しますが，上界と下界が一致すれば最適性は示せるので特に連携する必要はありません．

MIZUNO Yoshiyuki　水野義之 @y_mizuno

3月25日（日）の午後に、人工知能・ロボットの「情報倫理」に関するシンポジウムを、京都女子大学で開催します。 ご都合がつけば、ぜひご参加ください。詳細：janl.net/sympo2018.html

Umepon @shunji_umetani

@knewknowl 巡回セールスマン問題で最も有名な下界はHeld-Karp lower boundで1-treeと呼ばれる緩和問題を使います．辺を重み付けしたラグランジュ緩和問題を定義し，ラグランジュ双対問題を解いて下界を最大化します．