权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

混合遗传算法研究

基本信息

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

项目摘要

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

Combinatorial, discrete constraints and optimization are central problems in mathematical programming. The long-term production plan of the factory and the design of various projects, the design of VLSI, and the optimization of various configurations are just one example. It is impossible to solve this problem by combining discrete numbers and possible combinations of discrete numbers. In the present situation, computer resources, human resources and time resources are considered, and the optimal solution is approximated. The approximate solution of the solution is to be solved by the method of solving the problem. The approximate solution of the probability is obtained. It is an important subject to explore the approximate solution of the probability. In this study, the following two kinds of genetic algorithms are presented and applied to the optimization problem by using the combination optimization algorithm. Explore the composition of wood motion, explore the solution, explore the branches of wood motion, and reconstitute the exploration. Processing order relation partition solution space partition solution space GA. The ultimate solution is to explore and explore. For example, the improvement of the performance of the above methods is shown in the table below. The future of the project is to explore the process of detailed analysis,GA results, qualitative analysis, and large-scale research methods.