組合せ最適化問題に対するアルゴリズム開発と数値実験

组合优化问题的算法开发和数值实验

基本信息

批准号：
06740145
负责人：
久保幹雄
金额：
$ 0.58万
依托单位：
東京商船大学
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

项目摘要

本年度の研究実績は,大きく二つに分けられる.一つは,個々の組合せ最適化問題に対する解法の比較であり,もう一つは,種々の解法を総括して一段高い見地から見た一般的な枠組みを提案することである.まず標準的な比較対象として用いられているグラフ分割問題を取り上げ,代表的なメタヒューリスティックであるTabu SearchとSimulated Anncaling法を比較対象した.比較を行うためにTabu Searchをもとにした実験的解析ツールであるLife Span Method(寿命法)およびSimulated Annealing法の改良であるRe-annealing法を設計した.その後,系統的な実験的解析によりLife Span MethodのRe-annealing法に対する有効性を示した.それに伴い,アルゴリズムに内在する種々のパラメータの適正値に対する知見を示した.同様の検討をグラフ上の重要な組合せ最適化問題であるグラフ彩色問題および最大クリーク問題に対して行い,Life Span Methodの有効性を示した.また,スケジューリング問題の中でも最も困難であると言われているジョブショップスケジューリング問題に対してもLife Span Methodを適用し,従来法に対する有効性を実験的解析によって示した.これらの成果を踏まえて,種々のメタヒューリスティックスを一段高い見地から総括した解法(Generic Local Scarch)を構築した.これらの成果は,Life Span Methodとともに「離散構造とアルゴリズムIV」(近代科学社)の中の一章(メタヒューリスティックス)および計測自動制御学会論文誌の特集論文にまとめられている.また,メタヒューリスティックスの代表的な方法であるニューラルネット法,遺伝的アルゴリズムの研究者とともに,メタヒューリステックの有効性を論じるためのシンポジウムおよびセミナーを開催した.題目および講演者は以下の通りである.日本オペレーションズリサーチ学会シンポジウム「モダンヒューリスティックスの新展開Genetic Algorithm,Simulated Annealing,Tabu Search,Neural Net法は本当に有効か?-」(講演者:茨木(京大),武藤(慶大),玉置(京大),久保),日本オペレーションズリサーチ学会セミナー「モダンヒューリスティックス-Neural Network,Genetic Algorithm,Simulated Annealing,Tabu Searchの基礎から最新動向まで-」(講演者:甘利(東大),田中(茨城大),久保)

今年的研究成果大致可以分为两部分，一是对个别组合优化问题的求解方法的比较，二是对各种求解方法进行概括分析，从更高的角度来看待。提出图划分问题作为标准比较目标，并比较具有代表性的元启发法禁忌搜索和模拟安娜卡林方法。我们设计了寿命法（Life Span Method），这是一种基于搜索的实验分析工具，以及重新退火法（Re-annealing method），它是模拟退火法的改进。除此之外，我们还展示了退火法的有效性。关于算法中固有的各种参数的适当值的知识。对图着色问题和最大团问题进行了类似的研究，这是针对寿命跨度执行的重要组合优化问题。我们还将生命周期方法应用于车间调度问题，这被认为是所有调度问题中最困难的，并通过实验分析证明了其相对于传统方法的有效性。基于这些结果，我们构建了一种解决方法（Generic）。 Local Scarch）从更高的角度总结了各种元启发法。它与方法一起在“离散结构和算法 IV”（近代科学社）的一章（元启发式）中进行了总结，并在仪器与控制工程师学会杂志上的一篇专题文章中进行了总结。它也是一种代表性方法我们举办了一场研讨会和研讨会，与神经网络方法和遗传算法的研究人员一起讨论元启发法的有效性。主题和演讲者如下：日本运筹学会研讨会“新现代启发式部署遗传”算法、模拟退火、禁忌搜索和神经网络方法真的有效吗？（演讲者：Ibaraki（京都大学）、Muto（庆应义塾大学）、Tamaki（京都大学）、Kubo），日本运筹学会研讨会“现代启发式-”神经网络、遗传算法、模拟退火、禁忌从搜索基础知识到最新趋势——”（演讲者：Amari（东京大学）、Tanaka（茨城大学）、Kubo）