量子コンピューター（IBMQ）を用いてQAOAアルゴリズムを実行する
量子コンピューターを用いた最適化アルゴリズムの一つに、Quantum Approximation Optimization Algorithm (QAOA) があります。このアルゴリズムは主にゲート型の量子コンピューターで動作するアルゴリズムであり、実行するには量子回路のシミュレーターもしくは本物
数理最適化
記事数
12
【論文メモ】Optimistic Tree Searches for Combinatorial Black-Box Optimization (NeurIPS 2022)
openreview概要Huawei所属のCedric Malherbeらの研究グループによる論文木探索アルゴリズムに基づく0-1組合せ最適化問題に対するblack-box solverを提案ベイズ最適化に基づく手法と比較して計算コストが低く、進化計算アルゴリズムに基
深層学習モデルに対する敵対的攻撃(Adversarial Attack)を説明しようと試みる
日本語の記事が少ないので書いてみました。敵対的攻撃の中でも、画像分類モデルに対する非線形最適化手法をベースにした攻撃手法について紹介します。深層学習モデルの脆弱性深層学習モデルは、Adversarial Exampleと呼ばれる入力に対して脆弱性を持っています。この事実は、Szeg
【サーベイ編】深層強化学習を使ってTSPを解く
深層強化学習を用いたTSP・VRPの解法について調査する機会があったのでまとめます。TSP(巡回セールスマン問題)やVRP(配送経路問題)がどういう問題か、ということは知っている前提で話を進めます。対象とする手法・問題対象の問題今回対象となる問題は、2次元のユークリッドTS
【pythonで最適化】いろんな方法でTSPを解いてみた！
NP困難な最適化問題として知られる巡回セールスマン問題を、複数の近似解法と厳密解法を使って解いてみました。使用した解法は以下の４個です。整数計画問題(MTZ制約を使用、厳密解法)遺伝的アルゴリズム(近似解法)焼きなまし法(近似解法)2-opt(山登り法として実装、近似解法)実装はp
強化学習の基礎 マルコフ決定過程とQ-Learningについて
この記事では、強化学習を理解するための基本的な知識であるマルコフ決定過程によるモデル化とQ-Learningアルゴリズムについての解説を行います。マルコフ決定過程(Markov Decision Process, MDP)確率論におけるマルコフ性とは、「現在の状態が直前の状態にのみ
焼きなまし法（simulated annealing）の理論について
概要この記事では、焼きなまし法を支える理論について数学的な側面から解説することを目指します。焼きなまし法をマルコフ過程としてモデリングすることにより、アルゴリズムが大域的最適解に収束するための条件について調べよう、と言うのが全体的な流れです。連続と離散のギャップにより、ここで紹介する最適解
Simulated Annealingの簡単なまとめ
キーワード：最適化・近似解法・マルコフ過程Simulated Annealingってなに？日本語では擬似焼きなまし法とも呼ばれる、最適化問題に対する近似解法の一つで物性物理学における焼きなましからのアナロジーによって設計されています。温度パラメーターによって状態遷移を管理し
Yenのアルゴリズム
KSPについて少し勉強したので、理解を深めるために実装してみました。この記事ではアルゴリズムのイメージをつかむことを目的とし、アルゴリズム流れの説明実装例の紹介 を行います。厳密な解説を目的としたものではないのでご注意ください。KSP（K-shortest path pro
EppsteinのK-shortest pathを求めるアルゴリズムを実装したので解説します。
本記事の目的は、Eppsteinのアルゴリズムをふんわりと理解することです。詳細に理解したい方は元論文も合わせてご覧ください。K-shortest path problem とはk-shortest path problemとは、k番目に短い経路を求める問題で、いくつかのバリエーシ