-
آرشیو :
نسخه زمستان 1398
-
نوع مقاله :
پژوهشی
-
کد پذیرش :
1349
-
موضوع :
سایر شاخه های علوم رایانه
-
نویسنده/گان :
سجاد اسفندیاری، وحید رافع، محمود فرخیان
-
چکیده :
مسائل برنامه ریزی هوش مصنوعی، مسائلی هستند که برای رسیدن به هدفشان راه های بسیار زیادی پیش رو دارند و برای دستیابی به هدف خود که رسیدن سریع تر به جواب میباشد، غالبا برهوش هیجانی تکیه میکنند. برای حل اینگونه مسائل بعضا می توان از وارسی مدل استفاده کرد. وارسی مدل فرآیندی است که تمامی حالت های ممکن یک سیستم را در قالب یک گراف نمایش می دهد و به کمک آن درستی یابی را انجام می دهد درستی یابی یک محصول بیشترین زمان را در طراحی نرم افزار (و سخت افزار) صرف می کند. از آنجا که ابزارهای وارسی مدل در واقع به دنبال یافتن یک حالت خاص در یک فضای حالت بسیار بزرگ و جامع هستند، ما در این پژوهش سعی می کنیم چند مسئله معروف برنامه ریزی را با ابزار قدرتمند وارسی مدل، مدلسازی و حل کنیم تا کارایی و قابلیت های مختلف ابزارها در این مسائل مقایسه شود. به منظور ارزیابی ابزارهای نامبرده مسائل را بدون هیچگونه هوشمندی خاصی مدل می کنیم و هوشمندی جستجو را بر عهده ابزار می گذاریم. درنهایت با آزمایشات مختلف و افزایش سطوح مسائل، کارایی دو ابزار در این حوزه را مورد ارزیابی قرار می دهیم و خواهیم دید که ابزار Uppaal یک ابزار مناسب در مسائل برنامه ریزی هوش مصنوعی است. گرید محاسباتی مجموعهای از سیستمهای ناهمگون در مقیاس بزرگ میباشد. زمانبندی کارها یکی از مسائل مهم در سیستم گرید توزیع شده میباشد. الگوریتم ژنتیک به عنوان الگوریتم تکاملی پایه، راهی عادلانه برای پاسخگویی به مسائل دشواری است که با روشهای متداول سنتی برای رسیدن به نتایج مطلوب، با شکست برخوردند. این الگوریتم توانسته است به نتایج قابل قبولی برای مسئله زمان بندی کارها در سیستم گرید دست یابد. در این پژوهش زمان بندی کارها در سیستم گرید با روشی پیشنهادی مورد بررسی قرار میگیرد. روش پیشنهادی به ایجاد الگوریتمهای تکاملی جدید که حاصل ترکیب الگوریتم ژنتیک با الگوریتم بهینه سازی انبوه ذرات (PSO-GA)، الگوریتم ژنتیک با الگوریتم رقابت استعماری (GA-ICA)، الگوریتم ژنتیک با الگوریتم شبیه سازی تبرید (GA-SA)، الگوریتم ژنتیک با بهینه سازی کلونی مورچگان (GA-ACO) به منظور زمانبندی بهینه کارهای توزیع شده در سیستم گرید میپردازد. هدف اصلی الگوریتم ترکیبی این است که بتوان روند جستجوی محلی الگوریتم ژنتیک (GA) را با ترکیب نمودن با الگوریتمهای تکاملی ICA و PSO و SA و ACO بهبود بخشد و از همگرایی زودرس و توقف در مینیممهای محلی جلوگیری کرده و بهینگی سراسری را تضمین نمود. با در نظرگرفتن روند زمانی جریان کارها و زمان اتمام اجرای کارها به عنوان معیارهای مقایسه، در نهایت الگوریتم پیشنهادی ترکیبی توانست نتایج مطلوبی برای مسئله زمانبندی کارها در سیستم گرید توزیع شده دست یابد.
-
کلید واژه :
واژههای کلیدی: الگوریتم ترکیبی، بهینهسازی، زمانبندیکارها، زمان اتمام اجرای کارها.
-
Abstract :
A computational grid is a set of large-scale heterogeneous systems. Job scheduling is one of the most important issues in a distributed grid system. Genetic Algorithm As a basic evolutionary algorithm, it is a fair way to answer difficult problems that have failed with traditional conventional methods to achieve the desired results. This algorithm has been able to achieve acceptable results for the task scheduling problem in the grid system. In this research, the scheduling of tasks in the grid system is examined in a proposed way. Proposed method to create new evolutionary algorithms resulting from combining genetic algorithm with particle mass optimization algorithm (PSO-GA), genetic algorithm with colonial competition algorithm (GA-ICA), genetic algorithm with refrigeration simulation algorithm, SA-refrigeration algorithm (GA) Genetics deals with ant colony optimization (GA-ACO) to schedule distributed optimizations in the grid system. The main purpose of the hybrid algorithm is to improve the local search process of the genetic algorithm (GA) by combining it with the evolutionary algorithms ICA, PSO, SA and ACO, preventing premature convergence and stopping at the local minimums and ensuring global optimization. Considering the time process of workflow and completion time of works as comparison criteria, finally the proposed hybrid algorithm was able to achieve the desired results for the task scheduling problem in the distributed grid system.
-
مراجع :
1. Dordaie, N. and N.J. Navimipour, A hybrid particle swarm optimization and hill climbing algorithm for task scheduling in the cloud environments. ICT Express, 2018. 4(4): p. 199-202.
2. Dai, Y., Y. Lou, and X. Lu. A Task Scheduling Algorithm Based on Genetic Algorithm and Ant Colony Optimization Algorithm with Multi-QoS Constraints in Cloud Computing. in 2015 7th International Conference on Intelligent Human-Machine Systems and Cybernetics. 2015.
3. Molaiy, S. and M. Effatparvar, Scheduling in Grid Systems using Ant Colony Algorithm. International Journal of Computer Network and Information Security, 2014. 6: p. 16-22.
4. Zhang, L., et al., A Task Scheduling Algorithm Based on PSO for Grid Computing. International Journal of Computational Intelligence Research, 2008. 4: p. 37-43.
5. Chen, T., et al., Task Scheduling in Grid Based on Particle Swarm Optimization. 2006. 238-245.
- صفحات : 1-10
-
دانلود فایل
( 801.23 KB )