デスクトップグリッド環境におけるタスクスケジューリングアルゴリズムRR理論の実証と進化戦略の同期待ち時間削減について

摘要

This paper empirically investigates the effect of Desktop Grid Environment on the computational cost of Evolution Strategies (ES). Especially, for task scheduling, List Scheduling with Round-robin order Replication (RR) is adopted to reduce waiting time due to synchronization in ES. Computer simulations are conducted which compare with the loss energy of theoretical maximum value and an actual maximum measurement on Desktop Grid Environment for ES. Results on RR prove that the loss energy of an actual maximum measurement is less than that of theoretical maximum value. Moreover, RR can reduce the synchronous waiting time and improve parallel efficiency in comparison with Work Queue algorithm.%自然進化のメカニズムをモデル化した進化戦略（ES）rn［1,2,11］は，多くの工学的最適化問題に対して広く適用rnされ，その有用性が認識されている．とくに，このESrnは進化計算分野において，1964年の古い初期の時代かrnら実関数最適化に着目して数々の研究がなされている．rnそのため，グリッド計算における進化システムの展開にrnあたっても，豊富な数理的論証や基礎実験データが今後rnの展開に役立つと期待できる．しかし，進化システムrnの複雑さや規模が増すにつれ（たとえば，自律移動ロrnボットの制御機構としてEvolutionary Artificial NeuralrnNetworks（EANN）［13］を用いる場合［9］など），その計rn算量は莫大なものとなり，計算時間の短縮が望まれる．