بهینه سازی ( Optimization) در مهندسی شیمی

[حــامد]

بهينه‌سازي يك فعاليت مهم و تعيين‌كننده در طراحي ساختاري است. طراحان زماني قادر خواهند بود طرح‌هاي بهتري توليد كنند كه بتوانند با روش‌هاي بهينه‌سازي در صرف زمان و هزينه طراحي صرفه‌جويي نمايند.بسياري از مسائل بهينه‌سازي در مهندسي شیمی، طبيعتاً پيچيده‌تر و مشكل‌تر از آن هستند كه با روش‌هاي مرسوم بهينه‌سازي نظير روش برنامه‌ريزي رياضي و نظاير آن قابل حل باشند. بهينه‌سازي تركيبي (Combinational Optimization)، جستجو براي يافتن نقطه بهينه توابع با متغيرهاي گسسته (Discrete Variables) مي‌باشد. امروزه بسياري از مسائل بهينه‌سازي تركيبي كه اغلب از جمله مسائل با درجه غير چندجمله‌اي (NP-Hard) هستند،به صورت تقريبي با كامپيوترهاي موجود قابل حل مي‌باشند. از جمله راه‌حل‌هاي موجود در برخورد با اين گونه مسائل، استفاده از الگوريتم‌هاي تقريبي يا ابتكاري است. اين الگوريتم‌ها تضميني نمي‌دهند كه جواب به دست آمده بهينه باشد و تنها با صرف زمان بسيار مي‌توان جواب نسبتاً دقيقي به دست آورد و در حقيقت بسته به زمان صرف شده، دقت جواب تغيير مي‌كند.

 

[حــامد]

هدف از بهينه‌سازي يافتن بهترين جواب قابل قبول، با توجه به محدوديت‌ها و نيازهاي مسأله است. براي يك مسأله، ممكن است جواب‌هاي مختلفي موجود باشد كه براي مقايسه آنها و انتخاب جواب بهينه، تابعي به نام تابع هدف تعريف مي‌شود. انتخاب اين تابع به طبيعت مسأله وابسته است. به عنوان مثال،بهينه‌سازي راکتورها یا برج های تقطیر واحدهای شیمیایی. به هر حال، انتخاب تابع هدف مناسب يكي از مهمترين گام‌هاي بهينه‌سازي است. گاهي در بهينه‌سازي چند هدف به طور همزمان مد نظر قرار مي‌گيرد؛ اين گونه مسائل بهينه‌سازي را كه دربرگيرنده چند تابع هدف هستند، مسائل چند هدفي مي‌نامند. ساده‌ترين راه در برخورد با اين گونه مسائل، تشكيل يك تابع هدف جديد به صورت تركيب خطي توابع هدف اصلي است كه در اين تركيب ميزان اثرگذاري هر تابع با وزن اختصاص يافته به آن مشخص مي‌شود. هر مسأله بهينه‌سازي داراي تعدادي متغير مستقل است كه آنها را متغيرهاي طراحي می‌نامند كه با بردار n بعدي x نشان داده مي‌شوند.
هدف از بهينه‌سازي تعيين متغيرهاي طراحي است، به گونه‌اي كه تابع هدف كمينه يا بيشينه شود.

 

[حــامد]

در نزم افزار MATLAB جعبه ابزاری بنام Optimization Toolbox قرار داده شده است که با دستور optimtool در خط اصلی نرم افزار MATLAB قابل دسترسی است :
که الگوریتم ژنتیک نیز که یکی از روشهای بهینه سازیست در این قسمت در قمست solver قرار داده شده است

​

 

[حــامد]

به نظر من بهترین مرجع برای یادگیری toolbox های MATLAB خود Usermanual هایی هست که شرکت Mathwork سازنده این نرم افزار ارائه کرده است در اینجا من یوزر منوال جعبه ابزار بهینه سازی رو قرار میدهم امیدوارم بتوانید استفاده لازم رو ببرید

 

[حــامد]

مسائل مختلف بهينه‌سازي به دو دسته زير تقسيم مي‌شود:
الف) مسائل بهينه‌سازي بي‌محدوديت: در اين مسائل هدف، بيشينه يا كمينه كردن تابع هدف بدون هر گونه محدوديتي بر روي متغيرهاي طراحي مي‌باشد.
ب) مسائل بهينه‌سازي با محدوديت: بهينه‌سازي در اغلب مسائل كاربردي، با توجه به محدوديت‌هايي صورت مي‌گيرد؛ محدوديت‌هايي كه در زمينه رفتار و عملكرد يك سيستم مي‌باشد و محدوديت‌هاي رفتاري و محدوديت‌هايي كه در فيزيك و هندسه مسأله وجود دارد، محدوديت‌هاي هندسي يا جانبي ناميده مي‌شوند.
معادلات معرف محدوديت‌ها ممكن است به صورت مساوي يا نامساوي باشند كه در هر مورد، روش بهينه‌سازي متفاوت مي‌باشد. به هر حال محدوديت‌ها، ناحيه قابل قبول در طراحي را معين مي‌كنند.

 

[hamidrezachemeng]

Multi-Objective Optimization

Multi-Objective Optimization

lممنون از مطالب خوبتون. فایلی هست در مورد مقدمه ای بر Multi-Objective optimization در مهندسی شیمی که فکر میکنم فصل اول یک کتاب باشه.اینجا قرار میدم امیدوارم مفید باشه

 

[حــامد]

lممنون از مطالب خوبتون. فایلی هست در مورد مقدمه ای بر Multi-Objective optimization در مهندسی شیمی که فکر میکنم فصل اول یک کتاب باشه.اینجا قرار میدم امیدوارم مفید باشه

حمیدرضا جان خیلی ممنون در قسمت solver یک قسمت هست به اسم Multi-Objective optimization که در زمانیکه انتظار داریم تابع هدف ما از چند جهت بهینه بشه مثلا در برج تقطیر ما میخواهبم light naphtha و heavy naphtha ی بیشتری بکشیم و در پی این هستیم که ته مانده کمتری تولید کنیم از بهینه سازی چند هدفه استفاده میکنیم

 

[حــامد]

به طور كلي مسائل بهينه‌سازي با محدوديت را مي‌توان به صورت زير نشان داد:

[FONT=Arial][FONT=Arial]Minimize or Maximize : F(X) [/FONT][/FONT]
[FONT=Arial][FONT=Arial][FONT=Arial]Subject to : gi(x)<=0[/FONT][/FONT][/FONT]
[FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial]I = 1,2,3,…,p[/FONT][/FONT][/FONT][/FONT]
[FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial]hj(x)=0[/FONT][/FONT][/FONT][/FONT]
[FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial]j = 1,2,3,…,q[/FONT][/FONT][/FONT][/FONT][/FONT]
[FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial]Xkmin<Xk<Xkmax[/FONT][/FONT][/FONT][/FONT][/FONT]
[FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial][FONT=Arial]k = 1,2,3,…,n [/FONT][/FONT][/FONT][/FONT][/FONT][/FONT]

​

 

[حــامد]

بررسي روش‌هاي جستجو و بهينه‌سازي
پيشرفت كامپيوتر در طي پنجاه سال گذشته باعث توسعه روش‌هاي بهينه‌سازي شده، به طوري كه دستورهاي متعددي در طي اين دوره تدوين شده است. در اين بخش، مروري بر روش‌هاي مختلف بهينه‌سازي ارائه مي‌شود.

 

[حــامد]

بررسي روش‌هاي جستجو و بهينه‌سازي :
پيشرفت كامپيوتر در طي پنجاه سال گذشته باعث توسعه روش‌هاي بهينه‌سازي شده، به طوري كه دستورهاي متعددي در طي اين دوره تدوين شده است. در اين تاپیک، مروري بر روش‌هاي مختلف بهينه‌سازي ارائه مي‌شود.

 

[حــامد]

روش‌هاي شمارشي

در روش‌هاي شمارشي (Enumerative Method)، در هر تكرار فقط يك نقطه متعلق به فضاي دامنه تابع هدف بررسي مي‌شود. اين روش‌ها براي پياده‌سازي، ساده‌تر از روش‌هاي ديگر مي‌باشند؛ اما به محاسبات قابل توجهي نياز دارند. در اين روش‌ها سازوکاری براي كاستن دامنه جستجو وجود ندارد و دامنه فضاي جستجو شده با اين روش خيلي بزرگ است. برنامه‌ريزي پويا(Dynamic Programming) مثال خوبي از روش‌هاي شمارشي مي‌باشد. اين روش كاملاً غيرهوشمند است و به همين دليل امروزه بندرت به تنهايي مورد استفاده قرار مي‌گيرد​

 

[حــامد]

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

 

[hamidrezachemeng]

حمیدرضا جان خیلی ممنون در قسمت solver یک قسمت هست به اسم Multi-Objective optimization که در زمانیکه انتظار داریم تابع هدف ما از چند جهت بهینه بشه مثلا در برج تقطیر ما میخواهبم light naphtha و heavy naphtha ی بیشتری بکشیم و در پی این هستیم که ته مانده کمتری تولید کنیم از بهینه سازی چند هدفه استفاده میکنیم

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

 

[حــامد]

روش‌هاي ابتكاري و فرا ابتکاری(جستجوي تصادفي)
يك روش ناشيانه براي حل مسائل بهينه‌سازي تركيبي اين است كه تمامي جواب‌هاي امكان‌پذير در نظر گرفته شود و توابع هدف مربوط به آن محاسبه شود و در نهايت، بهترين جواب انتخاب گردد. روشن است كه شيوه شمارش كامل، نهايتاً به جواب دقيق مسأله منتهي مي‌شود؛ اما در عمل به دليل زياد بودن تعداد جواب‌هاي امكان‌پذير، استفاده از آن غيرممكن است. با توجه به مشكلات مربوط به روش شمارش كامل، همواره بر ايجاد روش‌هاي مؤثرتر و كاراتر تأكيد شده است. در اين زمينه، الگوريتم‌هاي مختلفي به وجود آمده است كه مشهورترين نمونه آنها، روش سيمپلكس براي حل برنامه‌هاي خطي و روش شاخه و كرانه براي حل برنامه‌هاي خطي با متغيرهاي صحيح است. براي مسائلی با ابعاد بزرگ، روش سيمپلكس از كارايي بسيار خوبي برخوردار است، ولي روش شاخه و كرانه كارايي خود را از دست مي‌دهد و عملكرد بهتری از شمارش كامل نخواهد داشت. به دلايل فوق، اخيراً تمركز بيشتري بر روش‌هاي ابتكاري (Heuristic) يا فرا ابتکاری (Metaheuristic) يا جستجوی تصادفی (Random Method) صورت گرفته است. روش‌هاي جستجوي ابتكاري، روش‌هايي هستند كه مي‌توانند جوابي خوب (نزديك به بهينه) در زماني محدود براي يك مسأله ارائه كنند. روش‌هاي جستجوي ابتكاري عمدتاً بر مبناي روش‌هاي شمارشي مي‌باشند، با اين تفاوت كه از اطلاعات اضافي براي هدايت جستجو استفاده مي‌كنند. اين روش‌ها از نظر حوزه كاربرد، كاملاً عمومي هستند و مي‌توانند مسائل خيلي پيچيده را حل كنند. عمده اين روش‌ها، تصادفي بوده و از طبيعت الهام گرفته شده‌اند.

 

[حــامد]

- مسائل بهينه‌سازي تركيبي (Optimization ProblemsCombinational)
در طول دو دهه گذشته، كاربرد بهينه‌سازي در زمينه‌هاي مختلفي چون مهندسي شیمی گسترش يافته است.
بهينه‌سازي خطي و غيرخطي (جستجو جهت يافتن مقدار بهينه تابعي از متغيرهاي پيوسته)، در دهه پنجاه و شصت از اصلي‌ترين جنبه‌هاي توجه به بهينه‌سازي بود.
بهينه‌سازي تركيبي عبارت است از جستجو براي يافتن نقطه توابع با متغيرهاي گسسته و در دهه 70 نتايج مهمي در اين زمينه به دست آمد. امروزه بسياري از مسائل بهينه‌سازي تركيبي (مانند مسأله فروشنده دوره‌گرد) كه اغلب از جمله مسائل NP-hard هستند، به صورت تقريبي (نه به طور دقيق) در كامپيوترهاي موجود قابل حل مي‌باشند.
مسأله بهينه‌سازي تركيبي را مي‌توان به صورت زوج مرتب R,C نمايش داد كه R مجموعه متناهي از جواب‌هاي ممكن (فضاي حل) و C تابع هدفي است كه به ازاي هر جواب مقدار خاصي دارد

 

[حــامد]

روش حل مسائل بهينه‌سازي تركيبي
روشن است كه شيوه شمارش كامل، نهايتاً به جواب دقيق مسأله منجر مي‌شود؛ اما در عمل به دليل زياد بودن تعداد جواب‌هاي امكان‌پذير، استفاده از آن بي‌نتيجه است. براي آنكه مطلب روشن شود، مسأله مشهور فروشنده دوره‌گرد (TSP) را در نظر مي‌گيريم.
اين مسأله يكي از مشهورترين مسائل در حيطه بهينه‌سازي تركيبي است که بدين شرح می‌باشد:
تعيين مسير حركت يك فروشنده بين N شهر به گونه‌اي كه از هر شهر تنها يكبار بگذرد و طول كل مسير به حداقل برسد، بسيار مطلوب است. تعداد كل جواب‌ها برابر است با!(n-1)2/1 . فرض كنيد كامپيوتري موجود است كه مي‌تواند تمام جواب‌هاي مسأله با بيست شهر را در يك ساعت بررسي كند. بر اساس آنچه آورده شد، براي حل مسأله با 21 شهر، 20 ساعت زمان لازم است و به همين ترتيب، زمان لازم براي مسأله 22 شهر، 5/17 روز و براي مسأله 25 شهر، 6 قرن ا ست!
به دليل همين رشد نمايي زمان محاسبه، شمارش كامل روشي كاملاً نامناسب است.
همان طور که گفته شد، با توجه به مشكلات مربوط به روش شمارش كامل، همواره بر ايجاد روش‌هاي مؤثرتر و كاراتر تأكيد شده است. در اين زمينه، الگوريتم‌هاي مختلفي به وجود آمده كه مشهورترين آنها، الگوريتم سيمپلكس براي حل برنامه‌هاي خطي و روش شاخه و كران براي حل برنامه‌هاي خطي با اعداد صحيح است.
بنابراين در سال‌هاي اخير توجه بيشتري بر روش‌هاي ابتكاري برگرفته از طبيعت كه شباهت‌هايي با سيستم‌هاي اجتماعي يا طبيعي دارد، صورت گرفته است و نتايج بسيار خوبي در حل مسائل بهينه‌سازي تركيبي NP-hardبه دنبال داشته است. در اين الگوريتم‌ها هيچ ضمانتي براي آنكه جواب به دست آمده بهينه باشد، وجود ندارد و تنها با صرف زمان بسيار مي‌توان جواب نسبتاً دقيقي به دست آورد؛ در حقيقت با توجه به زمان صرف شده، دقت جواب تغيير مي‌كند.
براي روش‌هاي ابتكاري نمي‌توان تعريفي جامع ارائه كرد. با وجود اين، در اينجا كوشش مي‌شود تعريفي تا حد امكان مناسب براي آن عنوان شود:
روش جستجوي ابتكاري، روشي است كه مي‌تواند جوابي خوب (نزديك به بهينه) در زماني محدود براي يك مسأله ارائه كند. هيچ تضميني براي بهينه بودن جواب وجود ندارد و متأسفانه نمي‌توان ميزان نزديكي جواب به دست آمده به جواب بهينه را تعيين كرد.

 

[حــامد]

در اينجا مفاهيم برخي از روش‌هاي اصلي ابتكاري بدون وارد شدن به جزييات معرفي مي‌شود.

1-آزاد‌سازي
آزادسازي (Relaxation)، يكي از روش‌هاي ابتكاري در بهينه‌سازي است كه ريشه در روش‌هاي قطعي بهينه‌سازي دارد.در اين روش، ابتدا مسأله به شكل يك مسأله برنامه‌ريزي خطي عدد صحيحLIP) = Linear Litegar Programmingا مختلطMIP) = Mixed Integer Programming )(و گاهي اوقات كمي غير خطي)، فرموله مي‌شود. سپس با برداشتن محدوديت‌هاي عدد صحيح بودن، يك مسأله آزاد شده به دست آمده و حل مي‌شود. يك جواب خوب (و نه لزوماً بهينه) براي مسأله اصليمي‌تواند از روند كردن جواب مسأله آزاد شده (براي رسيدن به يك جواب موجه نزديك به جواب مسأله آزاد شده)، به دست آيد؛ اگر چه روند كردن جواب براي رسيدن به يك جواب لزوماً كار آساني نيست، اما در مورد بسياري از مدل‌هاي معمول، به آساني قابل انجام است.

 

[حــامد]

2- تجزيه
بسياري اوقات آنچه كه حل يك مسأله را از روش‌هاي قطعي بسيار مشكل مي‌كند، اين است كه بيش از يك مورد تصميم‌گيري وجود دارد، مانند موقعيت ماشين‌آلات و تخصيص كار، تخصيص بار به وسائل نقليه و مسيريابي. هر يك از اين موارد تصميم‌گيري ممكن است به تنهايي پيچيده نباشند، اما در نظر گرفتن همه آنها در يك مدل به طور همزمان، چندان آسان نيست. روش ابتكاري تجزيه (Decomposition) مي‌تواند در چنين مسائلي مفيد واقع شود. در اين روش، جواب به دو يا چند بخش (كه فرض مي‌شود از هم مستقل هستند) تجزيه شده و هر يك جداگانه حل مي‌شوند؛ سپس يك روش براي هماهنگ كردن و تركيب اين جواب‌هاي جزيي و به دست آوردن يك جواب خوب ابتكاري، به كار گرفته مي‌شود.

2-1-تكرار
يكي از روش‌هاي تجزيه، تكرار (Iteration) است. در اين روش، مسأله به زيرمسأله‌هاي جداگانه‌اي تبديل مي‌شود و در هر زمان يكي از زيرمسأله‌ها با ثابت در نظر گرفتن متغيرهاي تصميم موجود در ساير زيرمسأله‌ها در بهترين مقدار شناخته شده‌شان، بهينه مي‌شود؛ سپس يكي ديگر از زيرمسأله‌ها در نظر گرفته مي‌شود و اين عمل به طور متناوب تا رسيدن به يك جواب رضايت‌بخش، ادامه مي‌يابد.


2-2- روش توليد ستون(Column Generation)
اين نيز يكي از روش‌هاي تجزيه است كه عموماً براي مسائلي كه داراي عناصر زيادي هستند (مانند مسأله كاهش ضايعات برش با تعداد الگوهاي زياد) كاربرد دارد. در اين روش، حل مسأله به دو بخش تقسيم مي‌شود:
1- يافتن ستون‌ها (يا عناصر) جواب (مثلاً در مسأله كاهش ضايعات برش و يافتن الگوهاي برش).
2- يافتن تركيب بهينه اين عناصر، با توجه به محدوديت‌ها (در مسأله كاهش ضايعات برش و يافتن تركيب مناسب الگوها). يكي از روش‌هاي معمول براي يافتن ستون‌ها، مقدار متغيرهاي دوگانه مسأله اصلي است، اما هر روش ديگري نيز مي‌تواند مورد استفاده قرار گيرد.

 

[حــامد]

3- جستجوي سازنده(Constructive Search)
در اين روش، با شروع از يك جواب تهي، تصميم‌ها مرحله به مرحله گرفته مي‌شود تا يك جواب كامل به دست آيد. هر تصميم، يك تصميم آزمند است؛ يعني قصد دارد با استفاده از اطلاعات به دست آمده از آنچه كه تا كنون انجام شده است، بهترين تصميم را بگيرد.
آنچه كه يك الگوريتم سازنده و يك الگوريتم آزمند را از هم متمايز مي‌كند، نحوه ساختن جواب‌ها مي‌باشد. يك الگوريتم سازنده، جواب را به هر طريق ممكن توليد مي‌كند، اما در يك الگوريتم آزمند، جواب مرحله به مرحله و با توجه به يافته‌ها، ساخته مي‌شود (در هر مرحله، بخشي از جواب ساخته مي‌شود). جستجوي سازنده در مسائلي مانند زمانبندي ماشين و بودجه‌بندي سرمايه كاربرد داشته است. در اينجا مثال مسيريابي كاميون مطرح مي‌شود. در اين مسأله كالا بايد به نقاط مشخصي (هر يك با ميزان مشخصي از تقاضا براي كالا) حمل شود؛ مسأله، سازماندهي اين نقاط در مسيرهاي مشخص با توجه به محدوديت ظرفيت كاميون است.

 

[حــامد]

4- جستجوي بهبود يافته (Improving Search)
بر خلاف روش جستجوي سازنده، اين روش با جواب‌هاي كامل كار مي‌كند. جستجو با يك يا چند جواب (مجموعه‌اي از مقادير متغيرهاي تصميم) شروع مي‌شود و در هر مرحله، حركت‌ها يا تغييرات مشخصي در مجموعه فعلي در نظر گرفته مي‌شود و حركت‌هايي كه بيشترين بهبود را ايجاد مي‌كنند، انجام مي‌شود و عمل جستجو ادامه مي‌يابد. يك مسأله در طراحي اين روش، انتخاب جواب اوليه است. گاهي اوقات جواب اوليه يك جواب تصادفي است و گاهي نيز برای ساختن يک جواب اوليه، از روش‌هايي نظير جستجوي سازنده استفاده مي‌شود. مسأله ديگر، تعيين حركت‌ها يا به عبارتي، تعريف همسايگي (مجموعه جواب‌هايي كه با يك حركت از جواب فعلي قابل دسترسي هستند) در مسأله است.

4-1- روش جستجوي همسايه ( NS= Neighbourhood Search)
استفاده از الگوريتم مبتني بر تكرار مستلزم وجود يك سازوکار توليد جواب است. سازوکار توليد جواب، براي هر جواب i يك همسايه به وجود مي‌آورد كه مي‌توان از i به آن منتقل شد. الگوريتم‌هاي تكراري به عنوان جستجوي همسايه (NS) يا جستجوي محلي نيز شناخته مي‌شوند. الگوريتم بدين صورت بيان مي‌شود كه از يك نقطه (جواب) شروع مي‌شود و در هر تكرار، از نقطه جاري به يك نقطه همسايه جابه‌جايي صورت مي‌گيرد. اگر جواب همسايه مقدار كمتري داشته باشد، جايگزين جواب جاري مي‌شود (در مسأله حداقل‌سازي) و در غير اينصورت، نقطه همسايه ديگري انتخاب مي‌شود. هنگامي كه مقدار جواب از جواب تمام نقاط همسايه آن كمتر باشد، الگوريتم پايان مي‌يابد.
مفهوم روش جستجوي همسايه از حدود چهل سال پيش مطرح شده است. از جمله اولين موارد آن، كارهاي كرز مي‌باشد كه براي حل مسأله فروشنده دوره‌گرد از مفهوم جستجوی همسايه استفاده کرده است. در كارهاي اخير ريوز نيز جنبه‌هايي از اين شيوه يافت مي‌شود.

اشكالات الگوريتم فوق بدين شرح است:
1- ممكن است الگوريتم در يك بهينه محلي متوقف شود، اما مشخص نباشد كه آيا جواب به دست آمده يك بهينه محلي است يا يك بهينه سراسري.
2- بهينه محلي به دست آمده به جواب اوليه وابسته است و در مورد چگونگي انتخاب جواب اوليه هيچ راه حلي در دسترسي نيست.
3- به طور معمول نمي‌توان يك حد بالا براي زمان اجرا تعيين كرد.
البته الگوريتم‌هاي مبتني بر تكرار مزايايي نيز دارند؛ از جمله اينكه يافتن جواب اوليه، تعيين مقدار تابع و سازوکار توليد جواب همسايه به طور معمول ساده است.
با وجود آنكه تعيين حد بالاي زمان اجرا امكان‌پذير نيست، ولي با اطمينان مي‌توان گفت كه يك تكرار از الگوريتم در زمان مشخص قابل اجراست.

 

[حــامد]

روش‌هاي فرا ابتكاري(Metaheuristic) برگرفته از طبيعت

در سال‌هاي اخير يكي از مهمترين و اميدبخش‌ترين تحقيقات،«روش‌هاي ابتكاري برگرفته از طبيعت» بوده است؛ اين روش‌ها شباهت‌هايي با سيستم‌هاي اجتماعي و يا طبيعي دارند. كاربرد ‌آنها برگرفته از روش‌هاي ابتكاري پيوسته می‌باشد كه در حل مسائل مشكل تركيبي (NP-Hard) نتايج بسيار خوبی داشته است.
در ابتدا با تعريفي از طبيعت و طبيعي بودن روش‌ها شروع مي‌كنيم؛ روش‌ها برگرفته از فيزيك، زيست‌شناسي و جامعه‌شناسي هستند و به شكل زير تشكيل شده‌اند:
- استفاده از تعداد مشخصي از سعي‌ها و كوشش‌هاي تكراري
- استفاده از يك يا چند عامل (نرون،خرده‌ريز، كروموزوم، مورچه و غيره)
- عمليات (در حالت چند عاملي) با يك سازوکار همكاري ـ رقابت
- ايجاد روش‌هاي خود تغييري و خود تبديلي
طبيعت داراي دو تدبير بزرگ مي‌باشد:
1- انتخاب پاداش براي خصوصيات فردي قوي و جزا براي فرد ضعيف‌تر؛
2- جهش كه معرفي اعضای تصادفي و امکان تولد فرد جديد را ميسر می‌سازد.
به طور كلي دو وضعيت وجود دارد كه در روش‌هاي ابتكاري برگرفته از طبيعت ديده مي‌شود، يكي انتخاب و ديگري جهش. انتخاب ايده‌اي مبنا براي بهينه‌سازي و جهش ايده‌اي مبنا براي جستجوي پيوسته مي‌باشد.
از خصوصيات روش‌هاي ابتكاري برگرفته از طبيعت، مي‌توان به موارد زير اشاره كرد:
1- پديده‌اي حقيقي در طبيعت را مدل‌سازي مي‌كنند.
2- بدون قطع مي‌باشند.
3- اغلب بدون شرط تركيبي همانند (عامل‌هاي متعدد) را معرفي مي‌نمايند.
4- تطبيق‌پذير هستند.
خصوصيات بالا باعث رفتاري معقول در جهت تأمين هوشمندي مي‌شود. تعريف هوشمندي نيز عبارت است از قدرت حل مسائل مشكل؛ بنابراين هوشمندي به حل مناسب مسائل بهينه‌سازي تركيبي منجر می‌شود

 

[حــامد]

-1-مسأله فروشنده دوره‌گرد (Travelling Salesman Problem = TSP)
در ابتدا به مسأله فروشنده دوره‌گرد (TSP) توجه مي‌كنيم؛ در اين مسأله مأموري به صورت تصادفي در فضاي جستجو (گرافn بعدي) حركت مي‌كند. تنها موقعيت اجباري اين است كه مأمور بايد فهرست شهرهايي را كه رفته به جهت اجتناب از تكرار به خاطر بسپارد. در اين روش بعد از n حركت، مأمور به شهر شروع باز مي‌گردد و راه‌حلي به دست مي‌آيد. روش جستجوي تصادفي ممكن است تكراري بوده و يا از شهرهاي مختلف شروع شود كه شامل الگوريتم چند شروعه (Multistart) مي‌شود.
روش‌هاي فرا ابتكاري مي‌توانند مطابق موارد زير به دست آيند:
1- استفاده از شيوه‌اي مبتني بر علاقه‌مندي براي انتخاب هر حركت مأمور؛
2- استفاده از روش جستجوي محلي (معاوضه موقعيت گره‌ها) براي بهبودي راه‌حل؛
3- استفاده از روش جستجوي محلي تصادفي و تنها پذيرش تغييرات بهبود يافته؛
4- استفاده از m مأمور كه از شهرهاي مختلف شروع مي‌كنند.
5- استفاده از تعدادي مأمور با استخدام غير قطعي؛
6- استفاده از روش‌هاي گروهي براي قسمت‌بندي فضا و يا مأموران؛
7- استفاده از قانون پذيرش بدون قطع براي تغييرات اصلاح نشده؛
8- استفاده از اطلاعات آخرين حركات براي اجراي يك سيستم حافظه‌اي.

 

[حــامد]

1 - الگوريتم ژنتيك
الگوريتم ژنتيك (Genetic Algorithm) روشي عمومي از روش‌هاي فرا ابتكاري براي بهينه‌سازي گسسته مي‌باشد كه مسائل جدول زمانبندي را حل مي‌نمايد. روش شبيه‌سازي كه در ادامه مورد بحث قرار می‌گيرد، راهبرد تكاملي نام دارد. اين روش در سال 1975 به وسيله هولند(Holland) و در سال 1989 توسط گولدبرگ (Goldberg) ابداع شده است.
اين روش نوعي روش جستجوي همسايه است كه عملكردي مشابه ژن دارد. در طبيعت، فرايند تكامل هنگامي ايجاد مي‌شود كه چهار شرط زير برقرار باشد:
الف) يك موجود توانايي تكثير داشته باشد(قابليت توليد مثل).
ب) جمعيتي از اين موجودات قابل تكثير وجود داشته باشد.
پ) چنين وضعيتي داراي تنوع باشد.
ت) اين موجودات به وسيله قابليت‌هايي در زندگي از هم جدا شوند.
در طبيعت، گونه‌هاي متفاوتي از يك موجود وجود دارند كه اين تفاوت‌ها در كروموزوم‌هاي اين موجودات ظاهر مي‌شود و باعث تنوع در ساختار و رفتار اين موجودات مي‌شود.
اين تنوع ساختار و رفتار به نوبه خود بر زاد و ولد تأثير مي‌گذارد. موجوداتي كه قابليت‌ها و توانايي بيشتري براي انجام فعاليت‌ها در محيط دارند(موجودات متكامل‌تر)، داراي نرخ زاد و ولد بالاتري خواهند بود و طبعاً موجوداتي كه سازگاري كمتري با محيط دارند، از نرخ زاد و ولد پايين‌تري برخوردار خواهند بود. بعد از چند دوره زماني و گذشت چند نسل، جمعيت تمايل دارد كه موجوداتي را بيشتر در خود داشته باشد كه كروموزوم‌هايشان با محيط اطراف سازگاري بيشتري دارد.

در طي زمان،ساختار افراد جامعه به علت انتخاب طبيعي تغيير مي‌كند و اين نشانه تكامل جمعيت است.​

 

[حــامد]

در optimization toolbox متلب بهینه سازی از طریق الگوریتم ژنتیک قرار داده شده است که معمولا دوستانی که در پی بهینه سازی فرایند های شیمیایی هستند به نظر بهترین انتخاب الگوریتم ژنتیک هست که بعلت اهمیت موضوع usermanual این الگوریتم را اینجا قرار میدهم

 

[حــامد]

و اینم هم نرم افزاری جهت تحلیل مساله فروشنده دوره گردTSP بوسیله الگوریتم ژنتیک

 

[حــامد]

آنيلينگ شبيه‌سازي شده
اين روش توسط متروپوليس(Metropolis) و همكاران در سال 1953 پيشنهاد شده و جهت بهينه‌سازي به وسيله وچی (Vecchi)، گلات (Gelatt) و کرک‌پاتريک(kirkpatrick) در سال 1983 مورد بازبيني قرار گرفته است. اين روش در مسائل تاكسي تلفنيكاربرد دارد.
الگوريتم آنيلينگ شبيه‌سازي شده (Simulated Annealing) در شکل عمومي، بر اساس شباهت ميان سرد شدن جامدات مذاب و حل مسائل بهينه‌سازي تركيبي به وجود آمده است. در فيزيك مواد فشرده، گرم و سرد كردن فرايندي است فيزيكي كه طي آن يك ماده جامد در ظرفي حرارت داده مي‌شود تا مايع شود؛ سپس حرارت آن بتدريج كاهش مي‌يابد. بدين ترتيب تمام ذرات فرصت مي‌يابند تا خود را در پايين‌ترين سطح انرژي منظم كنند. چنين وضعي در شرايطي ايجاد مي‌شود كه گرمادهي كافي بوده و سرد كردن نيز به آهستگي صورت گيرد. جواب حاصل از الگوريتم گرم و سرد كردن شبيه‌سازي شده، به جواب اوليه وابسته نيست و مي‌توان توسط آن جوابي نزديك به جواب بهينه به دست آورد. حد بالايي زمان اجراي الگوريتم نيز قابل تعيين است. بنابراين الگوريتم گرم و سرد كردن شبيه‌سازي شده، الگوريتمي است تكراري كه اشكالات روش‌هاي عمومي مبتني بر تكرار را ندارد.
در روش آنيلينگ شبيه‌سازي شده، به صورت پي در پي از جواب جاري به يكي از همسايه‌هاي آن انتقال صورت مي‌گيرد. اين سازوکار توسط زنجيره ماركوف به صورت رياضي قابل توصيف است. در اين روش، يك مجموعه آزمون انجام مي‌گيرد؛ اين آزمون‌ها به نحوي است كه نتيجه هر يك به نتيجه آزمون قبل وابسته است. در روش آنيلينگ شبيه‌سازي شده، منظور از يك آزمون، انتقال به نقطه جديد است و روشن است كه نتيجه انتقال به نقطه جديد تنها وابسته به مشخصات جواب جاري است.
روش جستجوي همسايه و روش آنيلينگ شبيه‌سازي شده، هر دو روش‌هاي تكراري هستند. در الگوريتم آنيلينگ شبيه‌سازي شده، هر بار كه شاخص كنترل‌كننده به مقدار نهايي خود مي‌رسد، در حقيقت يك عمليات تكراري انجام شده است. در الگوريتم جستجوي همسايه، هنگاميكه تعداد تكرارها به سمت بي‌نهايت ميل مي‌كند، روش به جواب بهينه نزديك مي‌شود. اما عملكرد الگوريتم آنيلينگ شبيه‌سازي شده سريع‌تر است.

 

[حــامد]

MATLAB function: reverse.m​

function reverse(ncity,n)
% reverse(ncity,n)
global iorder;
nn=(1+mod((n(2)-n(1)+ncity),ncity))/2;
for j=1:nn
k=1 + mod((n(1)+j-2),ncity);
l=1 + mod((n(2)-j+ncity),ncity);
itmp=iorder(k);
iorder(k)=iorder(l);
iorder(l)=itmp;
end

-----------------------------------​

MATLAB function: revcst.m​

function de = revcst(x,y,ncity,n)
% de = revcst(x,y,ncity,n)
global iorder;
% find n(3), the city just before n(1)
n(3)=1 + mod((n(1)+ncity-2),ncity);
% find n(4), the city just after n(2)
n(4)=1 + mod(n(2),ncity);
for j=1:4
ii=iorder(n(j));
xx(j)=x(ii);
yy(j)=y(ii);
end
de = -alen(xx(1),xx(3),yy(1),yy(3));
de = de-alen(xx(2),xx(4),yy(2),yy(4));
de = de+alen(xx(1),xx(4),yy(1),yy(4));
de = de+alen(xx(2),xx(3),yy(2),yy(3));

---------------------------------------​

MATLAB function: alen.m​

function length = alen(x1,x2,y1,y2)
% length = alen(x1,x2,y1,y2)
length = sqrt((x2-x1)ˆ2+(y2-y1)ˆ2);

MATLAB function: metrop.m​

function boolean = metrop(de,t)
% boolean = metrop(de,t)
boolean = de < 0 || rand(1) < exp(-de/t);

---------------------------------​

MATLAB function: anneal reverse.m​

function anneal_reverse(x,y,ncity)
%
% anneal_reverse(x,y,ncity)
%
%
global iorder;
tfactor=0.9;
nover=100*ncity;
nlimit=10*ncity;
path=0;
t=0.5;
for i=1:ncity-1
i1=iorder(i);
i2=iorder(i+1);
path = path + alen(x(i1),x(i2),y(i1),y(i2));
end
i1=iorder(ncity);
i2=iorder(1);
path = path + alen(x(i1),x(i2),y(i1),y(i2));
for j=1:100
nsucc=0;
for k=1:nover
nn=0;
while nn<3
n(1)=1+floor(ncity*rand(1));
n(2)=1+floor((ncity-1)*rand(1));
if n(2) >= n(1)
n(2)=n(2)+1;
end
nn=1+mod((n(1)-n(2)+ncity-1),ncity);
end
de=revcst(x,y,ncity,n);
ans=metrop(de,t);
if ans
nsucc=nsucc + 1;
path = path + de;
reverse(ncity,n);
end
if nsucc >= nlimit
break;
end
end
fprintf(1,’T = %10.6f, Path Length = %12.6f \n’,t,path);
fprintf(1,’Successful Moves: %6d\n’,nsucc);
iorder % display current iorder
t=t*tfactor;
if nsucc == 0
return;
end
end

--------------------------------​

MATLAB program: an example run of anneal reverse​

Input:​

global iorder
x=[0,0,0,1,1,1]
y=[0,1,2,0,1,2]
iorder=[1, 6, 3, 5, 2, 4]
ncity=length(iorder)
anneal_reverse(x,y,ncity)

 

[حــامد]

جستجوي ممنوع
روشی عمومي است كه به وسيله گلوور(Glover) در سال 1989 پيشنهاد شده و در حل مسائل برنامه‌ريزي كاري ـ خريد کاربرد دارد.
روش جستجوي ممنوع (Tabu Search)، همانند روش آنيلينگ شبيه‌سازي شده بر اساس جستجوي همسايه بنا شده است. در اين روش عملكرد حافظه انسان شبيه‌سازي شده است. حافظه انسان با به كارگيري ساختماني مؤثر و در عين حال ساده از اطلاعات، آنچه را در قبل رؤيت شده، ذخيره مي‌كند. اين مركز همچنين فهرستی از حركات منع شده را تنظيم مي‌كند و اين فهرست همواره بر اساس آخرين جستجوها منظم مي‌شود. اين روش از انجام هر گونه عمليات مجدد و تكراري جلوگيري مي‌كند.
شكل نوين جستجوي ممنوع توسط گلوور مطرح شده است. روش جستجوي مبتني بر منع، با ايجاد تغييري كوچك در روش جستجوي همسايه به وجود مي‌آيد. هدف اين روش آن است كه بخش‌هايي از مجموعه جوابكه پيش از اين بررسي نشده است، مد نظر قرار گيرد. بدين منظور حركت به جواب‌هايي كه اخيراً جستجو شده، ممنوع خواهد بود.
ساختار كلي روش جستجوي ممنوع بدين صورت است كه ابتدا يك جواب اوليه امكان‌پذير انتخاب مي‌شود؛ سپس براي جواب مربوط،بر اساس يک معيار خاص مجموعه‌اي از جواب‌هاي همسايه امكان‌پذير در نظر گرفته مي‌شود.
در گام بعد، پس از ارزيابي جواب‌هاي همسايه تعيين شده، بهترين آنها انتخاب مي‌شود و جابه‌جايي از جواب جاري به جواب همسايه انتخابي صورت مي‌گيرد. اين فرايند به همين ترتيب تكرار مي‌شود تا زمانيكه شرط خاتمه تحقق يابد.
در روش جستجوي ممنوع، فهرستي وجود دارد كه جابه‌جايي‌هاي منع شده را نگهداري مي‌كند و به فهرست تابو معروف است و كاربرد اصلي آن، پرهيز از همگرا شدن به جواب‌هاي بهينه محلي است. به عبارت ديگر، به كمك فهرست تابو جابه‌جايي به جواب‌هايي كه اخيراً جستجو شده‌اند، ممنوع خواهد شد. فقط بخش‌هايي از مجموعه جواب كه پيش از اين مورد بررسي قرار نگرفته، مد نظر خواهند بود. در واقع جابه‌جايي از جواب جاري به جواب همسايه امكان‌پذير زماني انجام مي‌شود كه در فهرست تابو قرار نداشته باشد. در غير اينصورت، جواب همسايه ديگري كه در ارزيابي جواب‌هاي همسايه در رده بعدي قرار گرفته است، انتخاب شده و جابه‌جايي به آن صورت مي‌گيرد.
در روش جستجوي ممنوع بعد از هر جابه‌جايي،فهرست تابو بهنگام مي‌شود، به نحويكه جابه‌جايي جديد به آن فهرست اضافه شده و جابه‌جايي كه تا n تكرار مشخص در فهرست بوده است، از آن حذف مي‌شود. نحوه انتخاب مي‌تواند با توجه به شرايط و نوع مسأله متفاوت باشد.

 

[حــامد]

 

[حــامد]

کولونی مورچه ها (Ants Colony)
اين روش در سال 1991 توسط مانيه‌زو (Maniezzo) دوريگو (Dorigo) پيشنهاد شده است كه در حل مسأله فروشنده دوره‌گرد و مسائل تخصيص چندوجهي کاربرد دارد.
الگوريتم بهينه‌سازي كلوني مورچه‌ها از عامل‌هاي ساده‌اي كه مورچه ناميده مي‌شوند، استفاده مي‌كند تا به صورت تكراري جواب‌هايي توليد كند. مورچه‌ها می‌توانند كوتاه‌ترين مسير از يك منبع غذايي به لانه را با بهره‌گيري از اطلاعات فرموني پيدا کنند. مورچه‌ها در هنگام راه رفتن، روي زمين فرمون مي‌ريزند و با بو كشيدن فرمون ريخته شده بر روي زمين راه را دنبال مي‌كنند؛ چنانچه در طي مسير به سوي لانه به يك دوراهي برسند، از آن جايي كه هيچ اطلاعي درباره راه بهتر ندارند، راه را به تصادف برمي‌گزينند. انتظار مي‌رود به طور متوسط نيمي از مورچه‌ها مسير اول و نيمي ديگر مسير دوم را انتخاب كنند.
فرض مي‌شود كه تمام مورچه‌ها با سرعت يكسان مسير را طي كنند. از آنجا كه يك مسير كوتاه‌تر از مسير ديگر است، مورچه‌هاي بيشتري از آن مي‌گذرند و فرمون بيشتري بر روي آن انباشته مي‌شود. بعد از مدت كوتاهي مقدار فرمون روي دو مسير به اندازه‌اي مي رسد كه روي تصميم مورچه‌هاي جديد براي انتخاب مسير بهتر تأثير مي‌گذارد. از اين به بعد، مورچه‌هاي جديد با احتمال بيشتري ترجيح مي‌دهند از مسير كوتاه‌تر استفاده كنند، زيرا در نقطه تصميم‌گيري مقدار فرمون بيشتري در مسير كوتاه‌تر مشاهده مي‌كنند. بعد از مدت كوتاهي تمام مورچه‌ها اين مسير را انتخاب خواهند كرد.