Over the past few decades great efforts were made to solve uncertain hybrid optimization problems. The n-Queen problem is one of such problems that many solutions have been proposed for. The traditional methods to solve this problem are exponential in terms of runtime a چکیده کامل
Over the past few decades great efforts were made to solve uncertain hybrid optimization problems. The n-Queen problem is one of such problems that many solutions have been proposed for. The traditional methods to solve this problem are exponential in terms of runtime and are not acceptable in terms of space and memory complexity. In this study, parallel genetic algorithms are proposed to solve the n-Queen problem. Parallelizing island genetic algorithm and Cellular genetic algorithm was implemented and run. The results show that these algorithms have the ability to find related solutions to this problem. The algorithms are not only faster but also they lead to better performance even without the use of parallel hardware and just running on one core processor. Good comparisons were made between the proposed method and serial genetic algorithms in order to measure the performance of the proposed method. The experimental results show that the algorithm has high efficiency for large-size problems in comparison with genetic algorithms, and in some cases it can achieve super linear speedup. The proposed method in the present study can be easily developed to solve other optimization problems.
پرونده مقاله
در طی دو دهه اخیر، بالارفتن فوق‌العاده سرعت شبکه‌های رایانه ای و همچنین افزایش نیاز به سیستم‌هایی با کارایی بالا سبب شده است که محققان به پردازش‌های موازی و توزیع‌شده علاقه‌مند شوند. رشد سریع سیستم‌های توزیع‌شده باعث شده که مسائل گوناگونی در این زمینه مطرح شود. یکی از م چکیده کامل
در طی دو دهه اخیر، بالارفتن فوق‌العاده سرعت شبکه‌های رایانه ای و همچنین افزایش نیاز به سیستم‌هایی با کارایی بالا سبب شده است که محققان به پردازش‌های موازی و توزیع‌شده علاقه‌مند شوند. رشد سریع سیستم‌های توزیع‌شده باعث شده که مسائل گوناگونی در این زمینه مطرح شود. یکی از مهم‌ترین مسائلی که موردتوجه محققان زیادی قرارگرفته، مسئله تخصیص وظایف در این‌گونه محیط‌ها است که به‌منظور به دست آوردن بهره‌وری مؤثر از سیستم انجام می‌شود. مسئله تخصیص وظایف به‌جز در معدود موارد خاص جز مسائل NP-کامل است؛ بنابراین از فرایندهای اکتشافی برای دستیابی به راه‌حل‌های زیربهینه در مدت‌زمان مطلوب استفاده می‌شود. اگرچه از روش‌های مختلف در تحقیقات استفاده‌شده، اما هنوز پیدا کردن روش مؤثر و کارا برای این مشکل موردنیاز و مطلوب است. در این پژوهش از الگوریتم ژنتیک موازی برای پیدا کردن راه‌حل بهینه برای تخصیص یک گراف از وظایف به پردازنده‌ها در سیستم توزیع‌شده استفاده‌شده است. نتایج نشان داد الگوریتم پیشنهادی می‌تواند تخصیص‌های بهینه یا نزدیک بهینه برای مسائل با اندازه‌های گوناگون ارائه دهد. همچنین روش پیشنهادی توانست در زمان بسیار سریع‌تر از الگوریتم ژنتیک سنتی و با تسریع فراخطی، مسائل با اندازه‌های بزرگ و متوسط را حل کند.
پرونده مقاله
در طول چند دهه گذشته تلاش‌های زیادی برای حل مسائل بهینه‌سازی ترکیبی غیرقطعی انجام شده است. مسئله n-وزیر یکی از همین مسائل است که تاکنون راه‌حل‌های زیادی برای حل این مسئله ارائه شده است. روش‌های سنتی حل این مسئله از نظر زمان اجرا، به صورت نمایی هستند و ازنظر پیچیدگی نمای چکیده کامل
در طول چند دهه گذشته تلاش‌های زیادی برای حل مسائل بهینه‌سازی ترکیبی غیرقطعی انجام شده است. مسئله n-وزیر یکی از همین مسائل است که تاکنون راه‌حل‌های زیادی برای حل این مسئله ارائه شده است. روش‌های سنتی حل این مسئله از نظر زمان اجرا، به صورت نمایی هستند و ازنظر پیچیدگی نمایی و فضایی قابل قبول نیستند. در مطالعه حاضر الگوریتم‌های ژنتیک موازی برای حل مسئله n-وزیر پیشنهاد شده است تا راه‌حل‌های این مسئله را پیدا کند. موازی‌سازی الگوریتم ژنتیک جزیره‌ای و الگوریتم ژنتیک سلولی با استفاده از جعبه‌ابزار محاسبات موازی متلب پیاده‌سازی و روی یک سیستم با پردازنده دو هسته‌ای اجرا شده است. نتایج نشان می‌دهد که این الگوریتم‌ها توانایی پیدا کردن راه‌حل‌های مربوط به این مسئله را دارند. این الگوریتم‌ها حتی بدون استفاده از سخت‌افزار موازی و با اجرا روی یک هستهٔ پردازنده، نه فقط به الگوریتم‌های سریع‌تر بلکه به عملکرد بهتر نیز منجر می‌شوند. مقایسه‌های خوبی بین روش پیشنهادی و نسخه‌های سریال الگوریتم ژنتیک برای سنجش عملکرد روش پیشنهادی انجام شده است. نتایج تجربی نشان می‌دهد این الگوریتم‌ها در مقایسه با الگوریتم ژنتیک سریال برای اندازه‌های بزرگ مسئله کارایی بالایی دارند و در برخی موارد می‌توانند به تسریع فوق‌خطی دست یابند. روش پیشنهادی این مقاله می‌تواند به آسانی برای حل دیگر مسائل بهینه‌سازی توسعه داده شود.
پرونده مقاله
سکوی نشر دانش
سند یا سکوی نشر دانش ،سامانه ای جهت مدیریت حوزه علمی و پژوهشی نشریات دانشگاه آزاد می باشد
