制約充足確率に基づく強化学習による組合せ最適化問題の解法に関する基礎的研究

基于约束满足概率的强化学习求解组合优化问题的基础研究

• 批准号: 22K12158
• 负责人: 松井 藤五郎
• 金额: $ 2.66万
• 依托单位: Chubu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2022
• 资助国家: 日本
• 起止时间: 2022-04-01 至 2025-03-31
• 项目状态: 未结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-22K12158/
• 关键词: 強化学習; 安全な強化学習; 組合せ最適化; 配送計画問題

2022年度は、深層強化学習を実際の物流業務における配送時間制約付き配車計画問題に適用するための準備として、巡回セールスマン問題 (TSP) を深層強化学習を用いて解く手法おける報酬の改善方法について検討した。また、制約充足確率に拡張する予定である成功確率に基づく安全な強化学習の手法を深層強化学習に拡張する方法について検討した。実際の物流業務においては、複数の配送先が非常に近い位置にあることがある。配送先が離れている場合には経路を変更すると経路長が大きく変わるが、配送先が非常に近い位置にある場合には経路を変更しても経路長がほとんど変わらない。先行研究において提案された最短経路長を新しく作成した経路長の差分（改善分）を報酬とする手法においては、このような問題に対しては報酬が非常に小さくなり、学習が進まなくなってしまう。そこで本研究では、平方根を用いた報酬関数を導入することによって、1より小さい報酬を増加させるとともに1より大きい報酬を減少させる方法を開発した。この手法を実際の運送会社の配送経路探索問題に適用し、配送先が非常に近い位置に密集している問題において有効であることを確認した。この成果については、2023年6月に熊本で開催される2023年度人工知能学会全国大会（第37回）において発表する予定である。また、我々がこれまでに開発した成功確率に基づく安全な強化学習の手法 EQ を深層強化学習の手法である DQN をベースとして Variable Autoencoder (VAE) を用いて成功し続ける確率を推定する手法 DEQN に拡張した。この成果については、2022年度6月に京都で開催された2022年度人工知能学会全国大会（第36回）において発表した。

在2022财年，我们讨论了通过解决旅行推销员问题（TSP）提高奖励的方法，以准备在实际物流操作中将深入的强化学习应用于交付时间有限的乘车骑车计划问题。我们还研究了如何基于成功概率扩展安全加强学习方法，该方法计划扩展到约束履行概率，深入强化学习。在实际的物流操作中，多个交付目的地可能非常接近。如果交货目的地距离相距较远，则路线的长度将发生巨大变化，但是如果交货目的地非常接近，即使更改了交货目的地，路线的长度也几乎不会改变。在使用以前研究中提出的最短路径长度新创建的最短路径长度的方法中，使用路径长度的差异（改进）奖励，此类问题的奖励很小，并且学习不会进展。因此，在这项研究中，我们开发了一种通过使用平方根引入奖励函数来增加奖励少于1的方法，并降低了大于1的奖励。该方法应用于实际运输公司的交付路线搜索问题，并确认它在集中在非常近距离的地方的问题中有效。这些结果将在2023年全国人工智能学会（第37届）全国会议上介绍。2023年6月，我们还扩展了EQ，我们已经扩展了EQ，这是一种基于成功概率的安全加强学习方法，到目前为止，我们已经开发了一种deqn，deqn，该方法估算了使用可变自动化方法的成功率（vae deqn），该方法估算了AutoeCododer（vae deqn）的成功率。这些结果在2022年6月在京都举行的2022年全国人工智能学会（36日）上介绍。

项目成果

DQNに基づく連続観測空間における安全な強化学習

基于DQN的连续观察空间安全强化学习

• 发表时间: 2022
• 作者: 大橋 宥斗;松井 藤五郎;武藤 敦子;森山 甲一;犬塚 信博
• 通讯作者: 犬塚 信博

組合せ最適化におけるジャンピングとアテンションを用いたグラフニューラルネットワーク

在组合优化中使用跳跃和注意力的图神经网络

• 发表时间: 2022
• 作者: グェンフウ バオロン;松井 藤五郎;原 謙介
• 通讯作者: 原 謙介