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

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

基本信息

批准号：
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年6月在熊本举行的日本人工智能学会2023年全国会议（第37届）上公布。此外，我们将我们开发的基于成功概率的安全强化学习方法 EQ 与基于深度强化 DQN 的使用可变自动编码器（VAE）估计持续成功概率的方法 DEQN 相结合。学习方法扩展。这些结果于2022年6月在京都举行的日本人工智能学会2022年全国会议（第36届）上公布。