اُپتی‌کد، مرجع کدهای الگوریتم فرا ابتکاری مسائل ریاضی

اُپتی‌کد، مرجع کدهای الگوریتم فرا ابتکاری مسائل ریاضی

سعی ما در اُپتی‌کد بر این است که کدهای فرا ابتکاری مسائل سخت و مشهور ریاضی را به صورت کاملاً سفارشی‌سازی و کامنت‌گذاری شده، در کوتاه‌ترین زمان و با کمترین هزینه، در اختیار دانشجویان و علاقه‌مندان قرار دهیم.

محل لوگو

آمار بازدید

  • بازدید امروز : 2
  • بازدید دیروز : 80
  • بازدید کل : 15602

آشنایی با الگوریتم‌های ابتکاری



 

 

الگوریتم‌های ابتکاری

الگوریتم‌های ابتکاری جزو دسته روش‌های حل تقریبی می‌باشند و در طول فرآیند حل، از اطلاعات منحصربفرد مسئله استفاده می‌کنند. با پیاده‌سازی این الگوریتم‌ها می‌توان به پاسخ‌های نزدیک به بهینه دست یافت بطوریکه این روش‌ها تضمین می‌کنند که پاسخ بدست آمده در بازه درصد مشخصی از پاسخ بهینه قرار بگیرد. گیر افتادن در نقاط بهینه محلی و همگرایی زودرس و پیش از بلوغ پاسخ‌ها به این محل‌ها (Premature convergence) دو مشکل اصلی این روش‌ها به حساب می‌آیند. اگرچه الگوریتم‌های ابتکاری غالباً تضمینی در یافتن جواب بهینه نمی‌دهند، با این حال با سرعت بالایی جواب‌هایی که نزدیک به پاسخ بهینه هستند، تولید می‌کنند. این الگوریتم‌ها به دو دسته تقسیم می‌شوند.

1- الگوریتم‌های سازنده: دسته‌ای از انواع الگوريتم‌هاي ابتكاري هستند كه در آن يك جواب از مسئله به تدريج و مرحله بهمرحله با توجه به داده‌هاي مسئله ساخته مي‌شوند. برای مثال الگوريتم نزديك‌ترين همسايگي براي حل مسئلهفروشنده دوره‌گرد يك الگوريتم سازنده محسوب می‌شود كه در طول فرآیند حل، اولين شهر را به صورت تصادفي انتخاب كرده وسپس با توجه به ماتريس فاصله در هر تكرار نزديك ترين شهر به مجموعه شهرهاي عضو تور، انتخاب شدهو به تور اضافه مي‌شود. بازیکن بازی شطرنج را در نظر بگیرید که در طول بازی طبیعتا نمی‌تواند مسیر بهینه را برای برد طی کند، با این حال از قواعد و خط مشی‌هایی در هر حرکت طوری تبعیت می‌کند که بهترین نتیجه را از آن گام بگیرد. الگوريتم‌هاي سازنده بسيار سريع هستند، اما معمولاً فاصله جواب توليد شده باجواب بهينه زياد است.

2- الگوریتم‌های بهبوددهنده: از اين الگوريتم‌ها تحت عنوان الگوريتم‌هاي جستجوي محلي نيز ياد مي‌شود. بهبوددهنده‌ها نوع ديگري از الگوريتم‌‌هاي ابتكاري هستند كه در آن‌ها معمولاً جستجو از يك جواب اوليه شروع مي شود. اين جواب اوليه ممكن است از طریق يك الگوريتم سازنده قبلاً حاصل شده باشد و یا اینکه به صورت تصادفي توليد شده باشد. در گام بعد با جستجوي موضعي در همسايه‌هاي اين جواب، سعي در بهبود جواب دارند و اين كار را به صورت بازگشتي در هر تكرار از الگوريتم‌ها انجام مي‌دهند. ساختار و چگونگی ایجاد پاسخ همسايگي اين نوع از الگوريتم‌ها بسيار مهم است. مثلاً در الگوريتم‌هاي گراديان كاهشي (براي مسائل مينيمم سازي) و تپه‌نوردي (براي مسائل ماكزيمم سازي) از ايده جستجوي محلي براي يافتن جواب‌هاي بهتر در همسايگي جواب فعلي استفاده مي‌كنند. اما مشكل اصلي اين نوع از الگوريتم‌ها آن است كه اغلب در دام بهينه محلي كه نسبت به بهينه سراسري بسيار بدتر است، گرفتار مي‌شوند.

 


 

 

بعنوان مثال از الگوریتم‌های ابتکاری سازنده برای مسئله TSP می‌توان به روش‌های زیر اشاره کرد:

1- نزدیک‌ترین همسایه (Nearest neighbor heuristic): این روش، ابتدا یک شهر را به تصادف بعنوان شهر آغازین انتخاب کرده و سپس در هر تکرار، از آخرین شهر اضافه شده به تور، به نزدیک‌ترین همسایه آن شهر حرکت می‌کند.

2- افزودن نزدیک‌ترین گره (Nearest insertion heuristic): طی این روش، ابتدا یک تور بین دو شهر دلخواه ایجاد می‌شود و در هر تکرار، ابتدا نزدیکترین شهر را به مجموعه شهرهای موجود در تور یافته و سپس این شهر جدید را طوری به تور اضافه می‌کنیم که افزایش طول تور کمینه باشد.

3- افزودن ارزانترین گره (Cheapest insertion heuristic): این روش، مشابه روش افزودن نزدیکترین گره است، با این تفاوت که شهر جدید را طوری انتخاب می‌کند که میزان افزایش در هزینه یا طول تور، با افزودن این گره به تور کمینه باشد.

4- افزودن دورترین گره (Furthest insertion heuristic): ابتدا دو گره که دورترین فاصله را از هم دارند داخل تور قرار می‌دهیم. سپس در هر تکرار، گرهی که با قرار گرفتن در بهترین چینش تور، بیشترین مسافت را ایجاد می‌کند، به تور اضافه می‌شود. هدف این روش، اینست که ابتدا شهرهای دور در داخل تور قرار گیرند.

5- الگوریتم کریستوفیدز (Christofides heuristic): علی‌رغم گذشت بیش از 30 سال از ارائه این روش، همچنان روش کریستوفیدز بهترین الگوریتم ابتکاری حل مسئله TSP بشمار می‌رود و پاسخ‌های بدست آمده از این روش، از 1.5 برابر پاسخ بهینه بدتر نخواهند بود. این الگوریتم از مفاهیم نظریه گراف، بسط دادن درخت پوششی کمینه، جدا کردن رأس‌های با درجه فرد، یافتن بهترین تطابق میان این رأس‌ها، تشکیل تور اویلری میان این رأس‌ها و حذف میانبرها (shortcuts) که درنهایت منجر به تشکیل یک تور TSP می‌شود. تشکیل یافته است.

 

همچنین برخی از الگوریتم‌های بهبوددهنده ارائه شده برای مسئله TSP به شرح زیر است:

1- الگوریتم دو-گزینشی (Two-opt heuristic): این الگوریتم، یک تور کامل را در نظر می‌گیرد و در هر تکرار، دو یال نامجاور را در نظر می‌گیرد و آن‌ها را حذف می‌کند. سپس دو زیرتور ایجاد شده را طوری به هم وصل می‌کند که طول تور نهایی، کمینه شود. بعبارتی، سعی در حذف برخورد مابین یال‌ها دارد و اگر فواصل مسئله TSP ماهیت اقلیدسی داشته باشند، هیچ برخوردی در نهایت مابین یالهای تور نخواهد ماند.

 

 

2- الگوریتم چند-گزینشی (k-opt heuristic): این الگوریتم حالت کلی و جامع الگوریتم قبلی است و در هر تکرار k یال نامجاور را حذف کرده و زیرتورهای ایجاد شده را به بهترین شکل مجدداً به هم متصل می‌کند. پاسخ بهینه بدست آمده از روش چند-گزینشی را k-optimum می‌نامند. این الگوریتم نیازمند حجم عملیات زیادی است و اغلب به ازای k=2,3 کاربرد دارد.

3- الگوریتم لین-کرنیگان (Lin-Kernighan heuristic): این الگوریتم نسخه دیگری از چند-گزینشی است که در آن مقدار k در تکرارهای مختلف تغییر می‌کند.

 

بطور خلاصه، الگوریتم‌های ابتکاری سعی بر این دارند که با در نظر گرفتن ساختار مسئله، با سرعت بالایی به یک پاسخ نزدیک بهینه دست یابند. جهت مطالعه بیشتر در این زمینه، کتاب زیر را پیشنهاد می‌کنیم.

 

“Design of Modern Heuristics – Principles and Applications” by Franz Rothlauf

 

 


 

 

  انتشار : ۲۱ مرداد ۱۳۹۹               تعداد بازدید : 204

دیدگاه های کاربران (0)

کتاب بانکداری داخلی 1(بهمند - بهمنی)

کتاب بانکداری داخلی 1(بهمند - بهمنی)

عنوان : کتاب بانکداری 1 (بهمند - بهمنی) حوزه کاربرد: حسابداری، بانکداری، اقتصاد تعداد صفحات: 194 صفحه کتاب بانکداری داخلی 1 (تجهیز منابع داخلی) نوشته آقایان (بهمند - بهمنی) به صورت PDF و در 194 صفحه خدمت دانشجویان و علاقه مندان عزیز تقدیم می گردد. فایل های ارائه شده برای این مجموعه با ...

محاسبه وزن الکترود نسبت به سایز و ضخامت لوله

محاسبه وزن الکترود نسبت به سایز و ضخامت لوله

به نام خدا سلام این یک فایل اکسل میباشد که محاسبه وزن الکترود و وزن فیلر نسبت به سایز و ضخامت لوله را محاسبه میکند ، و بسیار دقیق میباشد و چندین بار امتحان شده ، روش کار بسیار ساده هستش سایز لوله رو انتخاب کرده و بعد ضخامت لوله و یا همون اسکیجول و جنس لوله که کربن هست ...

آموزش دفتر فنی پایپینگ (Piping Technical Office)

آموزش دفتر فنی پایپینگ (Piping Technical Office)

به نام خدا با سلام این مجموعه آموزشی وظایف مهم دفتر فنی پایپینگ رو معرفی و شرح داده است و شامل بخشهای : مدارک اصلی پایپینگ ، ایزومتریک ، سرجوش گذاری نقشه ها تهیه WORK FRONT ، برنامه دو هفتگی ، کنترل متریال ، MIV ،MRC ،MRV ، تست پکیج ، لاین چک ، پانچ لیست ، تست ، فلاشینگ و ...

روش ساخت شابلون برنج تی پیس و وای پیس (Stencil t and y

روش ساخت شابلون برنج تی پیس و وای پیس (Stencil t and y

به نام خدا با سلام این مجموعه روش ساخت برنج تی پیس و وای پیس را آموزش و شرح داده است. ...

آموزش گام به گام کنترل پروژه پریماورا (PRIMAVERA) به

آموزش گام به گام کنترل پروژه پریماورا (PRIMAVERA) به

آموزش متفاوت از نرم افزار پریماورا برای اولین بار با حل یک مثال واقعی از یک پروژه واقعی این نرم افزار را فرا بگیرید. امروزه مشکل اساسی علاقه مندان به کنترل پروژه این است که با توجه به منابع و کتابهای فراوانی که در بازار وجود دارد باز هم سردرگم یافتن آموزشی هستند که جنبه ...

مجموعه طرح های معرق و مشبک

مجموعه طرح های معرق و مشبک

مجموعه طرح های زیبا و حرفه ای معرق کاری و مشبک کاری این مجموعه شامل: بسم الله شجره طرح های مینیاتوری تصاویر نوشتار و ....................... ...

پروژه درس کنترل کیفیت آماری ویژه دانشجویان

پروژه درس کنترل کیفیت آماری ویژه دانشجویان

هدف از کنترل کیفیت هدف اصلي يك سيستم كنترل فرآيند ، اتخاذ تصميمات مقرون به صرفه جهت انجام اقدامـات تاثير گذار بر فرآيند مي باشد . كنترل فرآيند نشان ميدهد كه كجاي فرآيند نيازمند انجام كنتـــــــرل هاي دقيق تـــــــر ميباشد و كجاهاي فرآيند انجام كنترل كمتر مجاز است. ( ...

متن کامل انگلیسی _ استاندارد بین المللی ایزو 31000 -

متن کامل انگلیسی _ استاندارد بین المللی ایزو 31000 -

متن کامل انگلیسی _ استاندارد بین المللی ایزو 31000 - مدیریت ریسک خطوط راهنمای مدیریت ریسک ISO 31000 : 2018 Risk Management Guidelines ...

آموزش OPERCOM و ICAPS

آموزش OPERCOM و ICAPS

به نام خدا این مجموعه کاملی از آشنایی مفصل با مفاهیم و مزایای استفاده از متد OPERCOM و آموزش و آشنایی با نرم افزار ICAPS و همچنین شامل بخشهای : هدف از اجرای روش OPERCOM – معرفی و شرح اصلی ترین دستورالعمل های -- OPERCOMمزایای استفاده از روش OPERCOM به کمک نرم افزار ICAPS – مزایای تقسیم بندی ...

دریافت فایل : آموزش OPERCOM و ICAPS
نرم افزار انبارداری بدون محدودیت استفاده و سورس

نرم افزار انبارداری بدون محدودیت استفاده و سورس

نرم افزار بسیار کاربردی انبارداری اکسس با پیغامها و امکانات فارسی: امکانات : امکان تعریف کاربران با سطح دسترسی محدود کاربران امکان تعریف کالاهای با رده مختلف امکان تعریف مشتریان امکان تعریف پرسنل امکان تعریف تامین کنندگان اسناد خرید یا رسید اسناد ...

کد الگوریتم‌های فرا ابتکاری مسائل مشهور ریاضی را از ما بخواهید.

فید خبر خوان    نقشه سایت    تماس با ما