بهینه سازی به روش کلونی مورچگان (Ant colony optimization )

 الگوریتم کلونی مورچه برای اولین بار توسط دوریگو(Dorigo) و همکارانش به عنوان یک راه حل چند عامله (Multi Agent) برای مسائل مشکل بهینه سازی مثل فروشنده دوره گرد     (TSP :Traveling Sales Person) ارائه شد این الگوریتم الهام گرفته شده از مطالعات و مشاهدات روی کلونی مورچه هاست.

مورچه ها هنگام راه رفتن از خود ردی از ماده شیمیایی فرومون(Pheromone) بجای می گذارندکه این ماده بزودی تبخیر می شود ولی در کوتاه مدت بعنوان رد مورچه بر سطح زمین باقی می ماند.

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

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

  

فایل پاورپوینت تهیه شده : الگوریتم کلونی مورچه

لینک بهینه سازی کلونی :http://www.icasite.info/2010/06/ant-colony-optimization-aco.html

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

 

 

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

 

الگوریتم (css) جستجوی ذرات باردار

 

CSS ازجدیدترین الگوریتم های فراکاوشی است که با استفاده از قوانین حاکم بر فیزیک الکتریسته اقدام به جستجوی فضای مسئله می کند، این روش در سال 2010 توسط پروفسور علی کاوه ودکتر طلعت اهری ابداع وبه اسم خودشان ثبت گردید.این روش از جمله جدیدترین الگوریتم های فراکاوشی است که قوانین مورد استفاده در این الگوریتم عبارتند از: قوانین کولمب و گوس از فیزیک وقوانین نیوتن از مکانیک کلاسیک .

 

معرفی الگوریتم  CSS

 

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

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

مانند بسیاری از روشهای فرا کاوشی، روش سیستم ذرات باردار یک روش چند عاملی است که به هر یک ازعوامل ، ذرات بارداریا CP گفته می شود که دارای بار الکتریکی برابر با qi است . بنابراین این ذرات یک میدان الکتریکی متناسب با qi  ایجاد خواهند کرد.مقدار qi  باید طوری تعریف شود که ذرات با جوابهای خوب دارای میدان الکتریکی بزرگتر و در نتیجه نیروی بیشتری باشند. نکته مهم اینکه موقعیت اولیه ذره به صورت تصادفی انتخاب می شود وسرعت اولیه تمام ذرات باردار صفرv_(i,j)^((0))=0  در نظر گرفته میشود.  

  لینک 1  :  Optimization of structures  - دانلود مقالات   <<< بروزرسانی جدید

  لینک 2  : رساله دکتری سیامک طلعت اهری در دانشگاه تبریز

 

الگوریتم‌های فراابتکاری (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))

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

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

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

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