ハイブリッド型遺伝的アルゴリズムに関する研究

混合遗传算法研究

基本信息

批准号：
07243213
负责人：
田村坦之
金额：
$ 0.58万
依托单位：
Osaka University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
1995
资助国家：
日本
起止时间：
1995 至无数据
项目状态：
已结题

项目摘要

組合せ的,離散的な制約条件のもとで最適化を扱う組合せ最適化は,昨今の数理計画法における中心的課題であり,実にさまざまな問題が組合せ最適化問題として扱われている.工場の長期的な生産計画や各工程のスケジューリング,VLSIのレイアウト設計,各種の配置最適化などは,その一例である.これらの問題を解くのに,離散的な数値の可能な組合せをすべて調べようとすると,組合せ的爆発を起こすため、最適解を得るのは事実上不可能である.しかし,現実の場面では,計算機資源や人的・時間的資源を考慮すると,最適解よりもむしろ近似的な解で十分な場合がほとんどである.したがって,実用的には,近似解を求める手法が有効となるが,近似解も,精度のよい解はたやすく得ることができないため,効率的な近似解法の解決が待たれている.効率的に近似解を求めるためには,いかにして無駄な探索を減らし,膨大な組合せの中から精度のよい近似解に絞り込んでいくかが,重要な課題となる.本研究では,以下に示す2種類の遺伝的アルゴリズムとラグランジュ緩和法を併用して組合せ最適化問題の近似解を求めるハイブリッド手法を提案し,ジョブショップスケジューリング問題への適用を行った.探索木の動的構成による解法ビーム探索における探索木の枝をGAによって動的に再構成しながら探索を行なう.処理順序関係の分割による解法解空間をジョブの処理順序関係で分割し,良い解を含む空間をGAで探索する.最終的な解は,列挙あるいはビーム探索で求める.以上の手法は,数値例により,従来手法に較べ性能の改善が見られることを示した.今後の課題としては,探索の過程を細かく分析することにより,GAの果たす役割を定性的に明らかにすることおよび大規模な問題へ本研究の手法を適用することにより性能評価を行うことがあげられる.

在组合和离散约束下处理优化的组合优化是当今数学编程中的一个核心问题，并且各种各样的问题被视为组合优化问题。示例是工厂的长期生产计划，每个过程的计划，VLSI的布局设计以及各种安排的布局优化。为了解决这些问题，如果您尝试研究离散数字的所有可能组合，则将发生组合爆炸，依此类推，几乎不可能获得适当的解决方案。但是，在实际情况下，在考虑计算机资源以及人类和时间资源时，近似解决方案通常就足够而不是最佳解决方案。因此，实际上，找到近似解决方案的方法是有效的，但是对于近似解决方案而言，获得准确的解决方案并不容易，因此正在等待有效的近似解决方案。为了有效地找到一个近似解决方案，如何减少不必要的搜索并创建大量未解决的连接。重要的问题是是否要以高精度缩小近似解决方案。在这项研究中，我们提出了一种混合方法，通过使用以下两种类型的遗传算法和拉格朗日放松方法来获得组合优化问题的近似解决方案，并将其应用于车间调度问题。使用搜索树动态构造的解决方案方法搜索树的分支在Beam搜索中由GA动态重建。该过程由过程序列关系划分。解决方案解决方案空间除以作业的过程顺序，并使用GA搜索包含良好解决方案的空间。最终解决方案是通过枚举或梁搜索确定的。以上方法表明，通过数值示例，与常规方法相比，可以看到性能的改进。未来的挑战包括通过详细分析搜索过程来对GA的作用进行定性澄清，并通过将本研究的方法应用于大规模问题来进行绩效评估。