الگوریتم‌های فراابتکاری (meta-heuristic)

 

 

روش‌ها و الگوریتم‌های بهینه‌سازی به دو دسته الگوریتمهای دقیق (exact) و الگوریتم‌های تقریبی (approximate algortithms) تقسیم‌بندی می‌شوند.

الگوریتم‌های دقیق قادر به یافتن جواب بهینه به صورت دقیق هستند اما در مورد مسائل بهینه سازی سخت کارایی ندارند و زمان حل آنها در این مسائل به صورت نمایی افزایش می‌یابد. الگوریتم‌های تقریبی قادر به یافتن جواب‌های خوب (نزدیک به بهینه) در زمان حل کوتاه برای مسائل بهینه‌سازی سخت هستند. الگوریتم‌های تقریبی نیز به سه دسته الگوریتم‌های ابتکاری (heuristic) و فراابتکاری (meta-heuristic) و فوق ابتکاری (hyper heuristic) بخش بندی می شوند. دو مشکل اصلی الگوریتم‌های ابتکاری، قرار گرفتن آنها در بهینه‌های محلی، و ناتوانی آنها برای کاربرد در مسائل گوناگون است. الگوریتم‌های فراابتکاری برای حل این مشکلات الگوریتم‌های ابتکاری ارائه شده‌اند. در واقع الگوریتم‌های فراابتکاری، یکی از انواع الگوریتم‌های بهینه‌سازی تقریبی هستند که دارای راهکارهای برونرفت از بهینه محلی می‌باشند و قابل کاربرد در طیف گسترده ای از مسائل هستند.  رده های گوناگونی از این نوع الگوریتم در ده های اخیر توسعه یافته است.

دسته‌بندی الگوریتم‌های فراابتکاری

 

معیارهای مختلفی می‌تواند برای طبقه‌بندی الگوریتم‌های فراابتکاری استفاده شود:

مبتنی بر یک جواب و مبتنی بر جمعیت : الگوریتم‌های مبتنی بر یک جواب در حین فرایند جستجو یک جواب را تغییر می‌دهند، در حالی که در الگوریتم‌های مبتنی بر جمعیت در حین جستجو، یک جمعیت از جواب‌ها در نظر گرفته می‌شوند.

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

با حافظه و بدون حافظه: برخی از الگوریتم‌های فراابتکاری فاقد حافظه می‌باشند، به این معنا که، این نوع الگوریتم‌ها از اطلاعات بدست آمده در حین جستجو استفاده نمی‌کنند (به طور مثال تبرید شبیه‌سازی شده). این در حالی است که در برخی از الگوریتم‌های فراابتکاری نظیر جستجوی ممنوعه از حافظه استفاده می‌کنند. این حافظه اطلاعات بدست آمده در حین جستجو را در خود ذخیره می‌کند.

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

الگوریتم ژنتیک (Genetic Algorithm)

 

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

 این الگوریتم همانطور که از نام آن پیداست از توارث صفات والدین به فرزندان به وسیله ترکیب کروموزوم های والدین ایده می گیرد. بدین طریق که تعدادی کروموزوم تولید، بعد آن ها را ترکیب کرده و کروموزوم جدیدی ایجاد می کنند و از آنجا که والدین قوی (به طور کلی) به احتمال بیشتری فرزندان قوی تولید می کنند از ترکیب کروموزوم های قوی ، می توان به کروموزوم های قوی تر دست پیدا کرد، برای شروع کار یک جمعیت از فضای جسجورا انتخاب کرده و با توجه به تابع هدف شروع به جستجو می نمایند، جواب مساله به شکل کروموزوم  که خود شامل یک رشته از عددها و نمادها می باشد، نمایش داده می شود. دو عامل تقاطع (Crossover) و جهش (Mutation) در جهت رسیدن به جواب بهینه در مساله مداخله می کنند این دو عامل (تقاطع و جهش) با توجه به ارزش گذاری کروموزوم ها، بهترین ها را نسل به نسل انتقال می دهند تا جواب بهینه بدست آید.

مقایسه الگوریتم ژنتیک :

1. الگوریتم ژ نتیک همزمان با یک مجموعه از نقاط جستجو می کند نه با یک نقطه تنها.

2. الگوریتم ژنتیک از قوانین احتمالی پیروی می کند نه قوانین طبیعی

3. الگوریتم ژنتیک بر روی یک مجموعه از خواص کد شده عمل می کند و نه بر روی مقادیر اصلی آن ها( به جزء در مواردی که از نمایش حقیقی در رشته ها استفاده شود)

4. الگوریتم ژنتیک به مشتق گیری یا هر گونه اطلاعات کمکی نیاز ندارد و تنها تابع هدف و شیوه تعیین برازش از اطلاعات خام ، جهت جستجو را مشخص می کنند.

      دانلود : الگوریتم ژنتیک  - Genetic Algorithm

      برچسب :الگوریتم ژنتیک چیست؟ - عملگرهای یک الگوریتم ژنتیک - فلو چارت این الگوریتم

حل مسائل بهینه سازی خطی با Excel

 مسائل بهینه سازی و مسائلی از جمله برنامه ریزی خطی که در مهندسی با آن سروکار داریم را می توان براحتی با Excel حل نمود ، بدین معنی که با استفاده از امکانات جانبی نرم افزار Excel وبا فعال سازی  Solver که یک Add-In می‌باشد مسائل بهینه سازی خطی را براحتی می توان انجام داد.

   دانلود : فایل پاورپوینت  - Excel Solver

   برچسب : نمونه مسائل برنامه ریزی خطی

بهینه سازی توده ذرات (Particle Swarm Optimization )

الگوریتم توده ذرات که به نام انگلیسی Particle Swarm Optimization معروف است یا به اختصار به آن PSO هم می گویند برگرفته از تجمع انبوهی از ذرات است، به این معنی از حرکت دسته جمعی پرندگانٰ، ماهی ها و … الهام گرفته است. در حرکت جمعی هر جز خود هوشمندی ندارد ولی رفتار گروه یک هوشمندی رو دنبال دارد.

یکی از روش های مطرح در زمینه بهینه سازی، الگوریتم ازدحام ذرات می باشد. این روش در سال 1995 برای اولین بار توسط کندی و ابرهارت ارائه گردید. این الگوریتم از رفتارهای اجتماعی یک دسته از پرندگان و گروهی از ماهی ها در یافتن غذا الهام گرفته شده است(کندی و ابرهارت، 1995). اساس این الگوریتم بر تکرار جستجو در محیط مسئله توسط جمعیت تصادفی می باشد که در هر تکرار ،تابع شایستگی مورد ارزیابی قرار می گیرد و سپس بهترین موقعیت هر پرنده و بهترین موقعیت تمام پرندگان در آن نسل در دو حافظه(بهترین موقعیت محلی ، بهترین موقعیت کلی ) قرار می گیرند،سپس در نسل بعد جمعیت جدیدی جایگزین جمعیت قبلی می شود و در این نسل نیز بهترین موقعیت محلی و بهترین موقعیت کلی با آنچه در نسل قبلی بدست آمد مورد مقایسه قرار می گیرد. در واقع حرکت پرندگان در این الگوریتم به دو عامل حرکت فردی و حرکت جمعی وابسته است.

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

بهینه سازی تکاملی سازه ها(Evolutionary Structural Optimization)

زی و استیون در سال 1993 در مقاله خود تحت عنوان  « یک روش تکاملی ساده برای بهینه سازی سازه ای » مقدمات روش ESO را پایه ریزی کردند ودر سال 1995 هینتون و سینز توانستند در ادامه کار زی و استیون روش دیگری برای حذف المان با کاهش مدول الاستیسیته آن ارایه دهند ودر نهایت کوارن در سال 1997 در رساله دکتری خود روش ESO  را مطرح نمود .

ویژگی مهم روش ESO آن است  در عین حال که نتایج قابل اعتماد ارایه می دهد به آسانی قابل درک و یادگیری می باشد،آن چه که حائز توجه است  این که تمام جنبه های رفتاری سازه می تواند درمفهوم  ESO گنجانده شود، البته در این روش قید ها می توانند بر مبنای تنش ، سختی ، جابجایی ، فرکانس و غیره ... .باشند.

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

کاربردهای ESO

از جمله کاربردهای روشESO  در زمینه های مختلف بهینه سازی توپولوژیکی، می توان به مواردی از قبیل مسائل کمانش ، مسائل فرکانس طبیعی و مسائل با قید جابجایی اشاره کرد،این روش توانایی خود را در بهینه سازی توپولوژیکی مسائل حرارتی نیز بخوبی اثبات کرده است . ازمهمترین موارد قابل ذکر

می توان به ارائه روش بهینه سازی تکاملی افزاینده در سازه ها موسوم به AESO و بهینه سازی تکاملی دو سویه در سازه ها که موسوم به روش BESO  می باشد اشاره نمود.          

  دانلود :پاورپوینت ESO 

 

الگوریتم تکاملی تفاضلی (Differential evolution algorithm)

الگوریتم تکاملی تفاضلی (DE) نخستین بار در سال 1995 توسط استورن و پرایس معرفی شد.این دو نشان دادند که این الگوریتم توانایی خوبی در بهینه سازی توابع غیرخطی مشتق ناپذیر دارد که به عنوان روشی قدرتمند و سریع برای مسائل بهینه سازی در فضاهای پیوسته معرفی شده است.

الگوریتم (DE) جهت غلبه بر عیب اصلی الگوریتم ژنتیک، یعنی فقدان جستجوی محلی دراین الگوریتم ارائه شده است، تفاوت اصلی بین الگوریتم های ژنتیکی و الگوریتم (DE)در عملگر انتخاب selection operators می باشد.

در اپراتور انتخاب GA ،شانس انتخاب یک جواب به عنوان یکی از والدین وابسته به مقدار شایستگی آن می باشد،اما در الگوریتم DE  همه جواب ها دارای شانس مساوی جهت انتخاب شدن می باشند. یعنی شانس انتخاب شدن آنها وابسته به مقدار شایستگی آنها نمی باشد، پس از این که یک جواب جدید با استفاده از یک اپراتور جهش خود-تنظیم و اپراتور crossover  تولید شد،جواب جدید با مقدار قبلی مقایسه می شود و در صورت بهتر بودن جایگزین می گردد.

 در این الگوریتم  بر خلاف دیگر الگورتیم ها که اول عملگر crossover و سپس عملگر mutation انجام می شود به گونه ای که ابتدا عملگرجهش اعمال شده و سپس عملگر تقاطع اعمال می شود تا بدین وسیله نسل جدید ایجاد گردد.

 برای اعمال عملگر mutation از توزیع خاصی استفاده نمی شود بلکه طول گام جهش برابر با مقدار از فاصله میان اعضای فعلی تعیین می شود.

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

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

بعد از انجام جهش ، کراس اور انجام می شود، بدین صورت که عددی تصادفی بین صفر و یک تولید شده و اگر عدد تولید شده کمتر از میزان نرخ کراس اور باشد عنصر مورد نظر در آن عضو از جمعیت،از قسمت جهش برداشته می شود در غیر اینصورت عنصر مورد نظر از مقدار اولیه عضو برداشته می شود اینقدر این کار تکرار می شود تا تمامی اعضای یک عضو یا از قسمت جهش خورده یا از مقادیر اولیه خود انتخاب گردند. سپس ماتریسی جدیدی که تولید شده با ماتریس اولیه مقایسه می شود و اگر ماتریس جدید دارای هزینه کمتری باشد جایگزین ماتریس اولیه می شود. این کار برای تمامی اعضای جمعیت انجام می شود.

        

پاورپوینت :الگوریتم تکاملی تفاضلی (DE) - کد متلب الگوریتم

برچسب :تکامل تفاضلی - www.icasite.info

رمز تمامی فایل های داخل وبلاگ ((password:30viloptimization))

مفهوم کلی بهینه سازی

امر بهینه سازی درابتدا با توجه به تنوع الگوریتم های بهینه سازی در رشته عمران کمی گنگ به نظر می رسد اما توصیه اینجانب برای دانشجویان این رشته این است که ابتدا یک دید کلی ازمفهوم بهینه سازی رو در گرایش های مختلف داشته باشند بعد روی الگوریتم خود وتابع هدفی که می خواهند آن رو بهینه نمایند کار کنند باتوجه به اینکه خودم نیز در اوایل دید کلی نسبت به بهینه سازی نداشتم واین علم نیز کمی برایم ناشناخته بود لذا فرصت رو غنیمت شمرده و فایلی آماده کرده ام تا انشالله برای دوستانم مفید واقع شود.

                                                                                                                        با تشکر مدیر سایت

دانلود فایل : مطالعه علم بهینه سازی درگرایش های عمران - درباره بهینه سازی سازه ها