شبیه سازی پروژه با weka وکا
ژوئن 14, 2019
مروری بر فیلتر کردن ، سیستم های خطی و تبدیلات
ژوئن 14, 2019
Show all

شبیه سازی الگوریتم های بهینه سازی


چکیده

الگوریتم تبرید شبیه‌سازی‌شده
از ویکی‌پدیا، دانشنامهٔ آزاد


پرش به ناوبریپرش به جستجوالگوریتم تبرید شبیه‌سازی‌شده (Simulated Annealing) (SA)، یک الگوریتم بهینه‌سازی فراابتکاری ساده و اثربخش در حل مسائل بهینه‌سازی در فضاهای جستجوی بزرگ است. این الگوریتم بیشتر زمانی استفاده می‌شود که فضای جستجو گسسته باشد (مثلاً همه گشت‌هایی که از یک مجموعه از شهرها میگذرند). برای مسائلی که پیدا کردن یک پاسخ تقریبی برای بهینه کلی مهمتر از پیدا کردن یک پاسخ دقیق برای بهینه محلی در زمان محدود و مشخصی است، تبرید شبیه‌سازی شده ممکن است نسبت به باقی روش‌ها مانند گرادیان کاهشی دارای ارجحییت باشد.
تکنیک تبرید تدریجی، به وسیلهٔ متالورژیست‌ها برای رسیدن به حالتی که در آن ماده جامد، به خوبی مرتب و انرژی آن کمینه شده باشد، استفاده می‌شود. هدف از این کار این است که سایز کریستال‌ها در حالت جامد ماده در حال تبرید به بزرگترین حالت برسد. این تکنیک شامل قرار دادن ماده در دمای بالا و سپس کم کردن تدریجی این دماست. شبیه سازی تبرید رویکردی است که مسئله کمینه سازی یک تابع با تعداد بسیار زیادی متغیر است را به یک مسئله مکانیک آماری کاهش می‌دهد. بنیان گذاران این الگوریتم برای حل مسائل سخت بهینه‌سازی، روشی مبتنی بر تکنیک تبرید تدریجی و آرام پیشنهاد نمودند. این محققین برای مدلسازی تبرید یک سیستم به منظور پیدا کردن پاسخ کمینه کلی، از شبیه سازی کامپیوتری استفاده کردند.[۱][۲]
می‌توان تبرید تدریجی و آرام در این الگوریتم را به عنوان کاهش تدریجی احتمال انتخاب پاسخ‌های بدتر حین جستجو در فضای پاسخ‌ها دانست (انتخاب پاسخ‌های بدتر یک ویژگی اساسی الگوریتم‌های فراابتگاری است و پیدا کردن بهترین پاسخ را ممکن می‌سازد). شبیه سازی را می‌توان به دو صورت حل روابط کینتیکی برای توابع چگالی (مانند کار خاچاتوریان، سمونوفسکایا و وینشتاین در سال ۱۹۷۹ و ۱۹۸۱) یا استفاده از نمونه‌گیری تصادفی، انجام داد. نمونه گیری تصادفی در سال ۱۹۸۳ توسط کریک‌پاتریک، گلت و کلی معرفی شد[۲]،‌ کرنی در سال ۱۹۸۵ و خاچاتوریان، سمونوفسکایا و وینشتاین در سال ۱۹۸۵ به‌طور مستقل این ایده را مطرح کردند. این روش یک اقتباس از الگوریتم متروپولیس-هستینگز است، یک روش مونت کارلو که نمونه حالت‌هایی را از یک سیستم ترمودینامیک تولید می‌کند.
  این مقاله به مکان­یابی بانکها تحت شرایط رقابتی با سطوح جذابیت متفاوت پرداخته است. مساله مکان­یابی بانکها به فاکتورهای زیادی نیاز داشته و جزء مسایل NP-HARD طبقه­بندی می­شود. استفاده از روشهای فراابتکاری برای حل مسایل NP-HARD علیرغم تقریبی بودن، مناسب­ترین راه حل به نظر می­رسد. در این تحقیق از روشهای بهینه­سازی ژنتیک، شبیه­سازی تبرید و الگوریتم بهینه­سازی فاخته­ها در حل مساله مکان­یابی رقابتی بانکها استفاده شده است.  روشها به طوری آماده شدند که قابلیت پیدا نمودن مکان بانک جدید با وجود بانکهای رقیب را دارند و مکان بانک جدید از بانکهای هم نوع خودش تا حد ممکن دورتر باید باشد (هدف بازاریابی). همچنین در مجموع کل مشتریان این نوع بانک نبایستی از یک حدی کمتر شده و میزان جذب مشتری شعبه جدید التاسیس بانک از یک تعدادی کمتر نشود (محدودیت­ها). بدین منظور قسمتی از شهر تبریز جهت پیاده­سازی انتخاب شد. در نهایت به منظور ارزیابی کیفیت و دقت الگوریتم­ها از تست تکرارپذیری و مقایسه اعداد همگرایی برای نتایج حاصل از اجرای هر الگوریتم روی داده­ها استفاده شد. نتایج حاصل از این آزمون­ها عملکرد دقیقتر و همچنین سرعت همگرایی بیشتر، الگوریتم فاخته­ها نسبت به روشهای بهینه­سازی ژنتیک و شبیه­سازی تبرید در بهینه­سازی مکان­یابی رقابتی بانکها را نشان می­دهد. 
کلیدواژه‌ها
مکان یابی رقابتی؛ الگوریتم بهینه سازی فاخته ها؛ الگوریتم ژنتیک و الگوریتم شبیه سازی تبرید؛ بانکها
عنوان مقاله [English]
The Assessment and Comparison of a Genetic Algorithm, Simulated Annealing and Cuckoo Optimization Algorithm for Optimization of the Facility Location under Competitive Conditions (Case Study: Banks)
نویسندگان [English]
Farshad Hakim pour1؛ Siamak Talat Ahary2؛ Abolfazl Ranjbar2
چکیده [English]
This paper determines the location of bank branches under competitive conditions with different attractive conditions. Finding an optimum location of branches depends on many factors and these problems are known as NP-hard problems. Despite being approximate methods, meta-heuristic algorithms seem suitable tools for solving NP-hard problems. In this paper, Genetic Algorithm (GA), Simulated Annealing (SA) and Cuckoo Optimization Algorithm (COA) are applied for finding the best location of bank branches. From marketing point of view, the aim is to attract more customers while the number of attracted persons to a new branch should be acceptable. The new methods have capability to find the optimum location of new branches under competitive conditions. The location of a new branch should be as far away as possible from branches of the same bank. The other condition is that the total number of customers for the new branch should not be less than a specified number, while the new branch should not attract customers of old branches of the same bank more than a threshold. To fulfill this propose a part of the Tabriz city was selected for implementation. Finally, to evaluate quality and accuracy of the algorithms, several iterations with different seeds are performed. The results of statistical and final tests indicate that the accuracy and convergence speed of Cuckoo Optimization Algorithm are more than the Simulated Annealing and Genetic Algorithms in finding optimal location of bank branches under competitive conditions.
کلیدواژه‌ها [English]
Facility Location under Competitive, Genetic Algorithm(GA), Simulated Annealing (SA) and Cuckoo Optimization Algorithm(COA), Banks
مراجع

فرم ثبت سفارش

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *