18888

۱۸۸۸۸

ارائه يك روش تنظيم پارامتر براي الگوريتم اصلاح شده ي شاخه زني محلي

كارشناسي ارشد

حمل و نقل ريلي

اسفند ماه ۱۳۹۶

دكتر مسعود يقيني

راه آهن

هر الگوريتم بهينه سازي داراي پارامترهايي است كه مقادير آن ها تاثير قابل توجهي در عملكرد الگوريتم و يافتن جواب هاي خوب در حل مسائل بهينه سازي سخت، خصوصا در دنياي واقعي نظير مسائل بهينه سازي در صنعت حمل و نقل ريلي دارد. با توجه به اهميت اين پارامترها و تاثير آن ها در جستجوي فضاي جواب به منظور يافتن يك جواب خوب در زمان قابل قبول، ما همواره با چالش تعيين مقادير پارامترهاي الگوريتم هاي بهينه سازي مواجه هستيم. در اين پايان نامه با استفاده از رويكرد كنترل پارامترها و منطق بهره برداري و اكتشاف در فضا، پس از بررسي دقيق روند الگوريتم اصلاح شده شاخه زني محلي و شناسايي پارامترهاي آن، يك ساختار انطباقي با ايجاد تعادل بين بهره برداري و اكتشاف در فضاي جواب براي الگوريتم مذكور ارائه نموده ايم. بدين ترتيب كه ساختار پيشنهادي با توجه به مشخصات هر مسئله خاص، بزرگي و يا كوچكي ابعاد آن، در اطراف نقاطي كه بهبود جواب مشاهده مي¬گردد، فضاي جستجو را به منظور بهره برداري و يافتن نقاط بهتر كوچك نموده و در مقابل، در شرايطي كه نقاط موجود در فضاي جستجوي مورد نظر بهبودي در جواب ايجاد نمي¬كند، فضاي جستجوي بزرگتري را در مدت زمان بيشتر براي كشف نقاط بهتر جستجو خواهد كرد. براي بررسي ساختار پيشنهادي، تعدادي نمونه مسئله آزمايشي از مجموعه مسائل طراحي شبكه چند كالايي براي حل و مقايسه نتايج در نظر گرفته شده كه نتايج بدست آمده نشان مي¬دهد، الگوريتم با ساختار انطباقي پيشنهادي عملكرد بسيار خوبي در يافتن جواب هاي بهينه وكاهش زمان حل، نسبت به نسخه اوليه الگوريتم و نرم افزار سيپلكس داشته است.

1397/02/22

5/12/2018 12:00:00 AM

In every optimization algorithm, there are some important parameters which affect the performance of the algorithm and enhance the search within the space. Due to the significant importance of these parameters which cause to improve their performance for finding the best solution during a suitable time, in this thesis, we tried to find the best parameter values for local branching extension algorithm. First of all we surveyed the trend of this algorithm in searching the space and recognized its parameters, afterwards we introduced an adaptive parameter control by equilibrium approach between exploitation and exploration, which is done by increasing or decreasing the search space during the run. In order to evaluate the effectiveness and efficiency of proposed adaptive configuration, several Multi-Commodity Network Design (MCND) problems are considered. The experimental results confirm the high performance of algorithm with proposed adaptive configuration compared to its basic version and CPLEX solver.