経験的知識を利用した適応型問題解決に関する研究

利用经验知识自适应解决问题的研究

基本信息

批准号：
01J09616
负责人：
小野智司
金额：
$ 1.28万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

事例形式で知識を獲得・再利用する適応型問題解決パラダイムを提案した.悪定義な現実問題として日本語点字翻訳問題を,悪構造な現実問題として室内レイアウト変更計画問題を,それぞれ対象問題とし,提案するパラダイムを適用した.ここで,室内レイアウト変更計画問題とは,変更前後の機器配置レイアウト,変更作業者数,作業時間の上限が与えられたときに,各機器の移動経路の集合からなるプラン,および,機器移動作業への作業者および作業時間の割当てからなるスケジュールを求める問題である.本年度は,室内レイアウト変更計画問題において,事例知識を再利用する方式の開発・評価を行った.本問題は,プランニングとスケジューリングの双方を同時に行わなければならない複雑な問題である.このため,本問題を制約充足問題として定式化することによって,汎用的な解探索ソルバを用いてプランとスケジュールを同時作成できるようにした.また,対象とする問題インスタンスに最も類似した過去の事例から,ヒューリスティクスを選択的に作成することにより,探索の効率化を実現した.実験により,事例を用いることによって,事例検索・適合のオーバーヘッドを加味しても,40問題のうち31問題において,探索性能を改善できることを確認した.現段階では,過去の事例を対象問題インスタンスに適合させる処理において,再利用していないパラメータが多く存在する.これらのパラメータについても再利用することにより,さらなる探索性能の改善を図ることができると考える.

我们提出了一种自适应解决问题的范式，该范式以案例式格式获取和重用知识。我们使用拟议的范式将日本盲文翻译问题用作明确定义的实际问题，而室内布局变更计划问题是结构性不佳的实际问题，并应用了拟议的范式。在这里，室内布局变更计划问题是一个问题，它需要一个计划，该计划由每种设备的一系列移动路径组成，以及包括分配工人和工作时间用于设备运动工作的时间表。今年，我们开发并评估了一种在室内布局变更计划问题中重复使用案例知识的方法。此问题涉及同时计划和计划。因此，通过将此问题提出为约束满意度问题，可以使用通用解决方案搜索求解器同时创建计划和时间表。此外，通过从与目标问题实例最相似的过去案例中有选择地创建启发式方法，实现了搜索效率。通过实验，我们确认在40个问题中有31个可以改善搜索性能，即使考虑到使用案例的案例搜索和拟合的开销，我们已经确认，在此阶段的40个问题中，可以改善搜索性能。在此阶段，在调整过去案件以针对问题实例的过程中，有许多参数尚未重复使用。通过重复这些参数，我们认为可以进一步改善搜索性能。