بهینه سازی طراحی سیستم
طاهره مصطفویدر۱۴۰۳/۲/۱۸
بهینه سازی فرایند یافتن بهترین جایگزین از مجموعه ای از گزینه های قابل اجرا برای به حداکثر یا به حداقل رساندن یک تابع به نام تابع هدف است. متغیرهایی که کاربر می تواند به آنها دسترسی پیدا کند و مقدار تابع هدف با تغییر مقادیر آنها را تغییردهد، متغیرهای طراحی نامیده می شوند. کاربر می تواند ارزش متغیر طراحی را با انتخاب گزینه های مختلف از مجموعه ای از گزینه های موجود برای این متغیر طراحی، تغییر دهید. ترکیبی از متغیرهای طراحی که با انتخاب یک گزینه برای هر یک از متغیرهای طراحی از مجموعه خود تشکیل شده از گزینه های مناسب را طراحی می نامند. بهینه سازی طراحی هر سیستم می تواند به عنوان ترکیبی از طراحی و تجزیه و تحلیل سیستم در نظر گرفته شود . طراحی یک سیستم فرایند تولید یک طرح جدید است و تجزیه و تحلیل، فرایند تعیین اثر بخشی طرح است. در زمان طراحی یک سیستم ممکن است ما نیاز به ارضا مجموعه ای از شرایط به نام محدودیت داشته باشیم.
با توجه به تعداد توابع هدف و تعداد محدودیت ها، مسائل بهینه سازی را می توان به چهار نوع تقسیم کرد. اگر ما فقط یک تابع هدف و بدون محدودیت برای ارضا داشته باشیم پس آن را مسئله بهینه سازی تک-هدفه نامحدود می نامیم. اگر ما بیش از یک تابع هدف و بدون محدودیت داشته باشیم پس آن را مسئله بهینه سازی چند-هدفه نامحدود می نامیم. اگر ما محدودیت در مسئله داشته باشیم پس مسئله بهینه سازی تک یا چند-هدفه محدود خواهد بود.
با در نظر گرفتن تعداد متغیرهای طراحی و تعداد گزینه های در دسترس برای هر یک از آنها، تعداد طرح هایی که می توانند تولید شوند بسیار زیاد خواهد بود. اگر ما بخواهیم بهترین مجموعه از طرح ها را توسط ارزیابی توابع هدف از تمام این طرح ها داشته باشیم، این کار زمان بسیاری طول می کشد و کارآمد نیست. برای حل این مشکل ما به یک الگوریتم نیاز داریم که بتواند تعیین کند چه ترکیبی از متغیرهای طراحی ، مقدار تابع هدف بهتر و طرح هایی را تولید کند که در مقایسه با طرح های قبلی بهتر هستند.
اگر ما متغیرهای طراحی را در امتداد محورهای متعامد به یکدیگرنمایش دهیم بنابراین می توانیم فضایی که توسط این محور ها طراحی شده است را فضای طراحی بنامیم. هر نقطه ای که در فضای طراحی انتخاب شده است، یک نقطه طراحی نامیده می شود. ما هیچ ایده از فضای طراحی و اینکه طراحی های خوب کجا خواهند بود، نداریم. بدون وجود هیچ ایده اولیه ای از فضای طراحی، ما نمی توانیم انتظار یک الگوریتم برای پیدا کردن طرح های بهتر را داشته باشیم، مگر آنکه الگوریتم خود توانایی آموختن داشته باشد.
الگوریتم ژنتیک (GA ) توانایی یادگیری به تنهایی را دارد و بهترین گزینه برای این نوع مشکلات، که در آن متغیرهای طراحی گسسته هستند، می باشد. از این رو GA برای مشکل بهینه سازی ما انتخاب شده است.
الگوریتم های ژنتیکی
الگوریتم های ژنتیک بر پایه نظریه تکامل است. آنها روند تکامل در ایجاد طرح های جدید را شبیه سازی می کنند. الگوریتم های ژنتیکی یاد می گیرند که چگونه بر اساس نتایج بدست آمده از ارزیابی طراحی های قبلی به سمت طرح بهتر حرکت کنند. از این رو الگوریتم های ژنتیک به هیچ دانش قبلی از فرآیند بهینه سازی نیاز ندارد.
برای شبیه سازی فرآیند تکامل، الگوریتم ژنتیک از سه روش به نام ادغام، جهش و انتخاب استفاده
می کند. طرح های بهتر با ترکیب ویژگی های موفق از طرح های موجود بدست می آیند.
در اصطلاحات GA ، یک نقطه طراحی، که توسط ترکیبی از متغیرهای طراحی در فضای طراحی تشکیل شده است، راه حل کاندید نامیده می شود. مجموعه ای از راه حل های کاندید، که ما فرآیند بهینه سازی را با آنها شروع می کنیم، نشان دهنده نسل اول هستند. مجموعه ای از راه حل های کاندید که در هر نسل تولید شده، جمعیت و تعداد راه حل های کاندید در هر نسل، اندازه جمعیت نامیده می شود. تعداد
طرح های محفوظ مشخص می کند که چه تعداد از بهترین طرح های موجود را می خواهیم به نسل بعد منتقل کنیم.
نسل اول (والد) ،با انتخاب راه حل های کاندید به طور تصادفی در فضای طراحی تولید می شود. مقادیر تابع هدف برای کل جمعیت ارزیابی و به الگوریتم ژنتیک ارائه شده است. با یادگیری از این نتایج، GA با نگه داشتن برخی از بهترین طرح های به دست آمده از نسل قبلی، به نسل بعدی (فرزند) می رسد و طرح های باقی مانده با استفاده از ادغام و جهش در طرح به دست آمده از نسل قبلی ،به دست می آیند . مقادیر تابع هدف برای طراحی های هر دو نسل به دست آمده است. توانایی یک راه حل کاندید برای بقا و ظهورپیدا کردن در نسل بعدی، سازواری یا توانایی زیستی نامیده می شود. راه حل های کاندید با سازواری بالا برای نسل های بسیاری وجود دارد. در اینجا تابع سازواری ، تابع هدف است. در مورد یک مسئله بهینه سازی چند هدفه، سازواری یک راه حل کاندید با تمامی توابع هدف مرتبط است. هنگامی که مقادیر سازواری شناخته شده است ما هر دو جمعیت والد و فرزند را با توجه به مقادیر سازواری آنها مرتب می کنیم. ما می توانیم طرح های که برای نسل بعدی باقی می مانند را به دو روش پیدا کنیم. در روش اول ما بدترین طرح از جمعیت فرزندان را با بهترین طرح در جمعیت والد جایگزین می کنیم و این روش را انتخاب نخبه گرا نامیده می شود. در روش دیگر ما هر دوجمعیت والد و فرزند را ترکیب کرده و آنها را با توجه به ارزش های سازواریشان مرتب می کنیم. طرح ها با بهترین ارزش سازواری انتخاب می شوند و این روش، روش انتخاب متعدد نخبه گرا نامیده می شود.
با استفاده از روش نخبه گرا یا انتخاب متعدد نخبه گرا ما تعدادی از طرح ها را که برابر با تعداد طرح های محفوظ هستند، انتخاب می کنیم. بقیه جمعیت در نسل جدید با استفاده از فرآیندهای ادغام و جهش به دست می آیند که در مورد آنها بحث می کنیم. ما احتمال کاربرد هر دو روش ادغام و جهش را در آغاز فرآیند بهینه سازی فراهم می کنیم. کاربرد ادغام و یا جهش با مقایسه احتمال آنها با مقدار احتمال یک تولید تصادفی تعیین می شود. اگر احتمال ادغام یا جهش کمتر از ارزش احتمال تولید به طور تصادفی آن باشد، پس آن اپراتور (ادغام / جهش) به کار برده می شود. اجازه دهید ما فرآیندهای ادغام و جهش را ببینیم.
ادغام: فرض کنید که ما دو طرح با شش متغیر طراحی داریم. برای رسیدن به طراحی نسل بعدی با استفاده از این دو طرح با روش ادغام، ما دو طرح والد را تقسیم می کنیم. نقطه تقسیم به صورت تصادفی انتخاب شده است. اجازه بدهید بگوییم که ما آنها را به دو نیمه تقسیم می کنیم. نسل های جدید با ترکیب یک بخش از هر یک از این دو طرح تولید می شوند.
مثال: اجازه دهید طرحَA 4، 2، 3، 3، 2، 1 و طراح B 3، 4، 2، 2، 2، 1، باشد به طوریکه در آن، اعداد، گزینه انتخاب شده برای هر متغیر طراحی را بیان می کنند (با فرض اینکه گزینه های مختلفی برای هر متغیر طراحی در دست هستند).
با تقسیم هر یک از این طرح ها به دو نیمه ما 4، 2، 3 - 3، 2، 1 و 3، 4، 2 - 2، 2، 1 را خواهیم داشت. برای رسیدن به طرح های جدید با استفاده از ادغام ما بخش های مختلف از طرح های موجود را ترکیب می کنیم. بدین ترتیب ما طرح های جدید 4، 2، 3، 2، 2، 1 و 3، 4، 2، 3، 2، 1 را بدست می آوریم.
در این فرایند ما طرح های موجود را ترکیب می کنیم و این کار ما را به بخشی از فضای طراحی، که در آن والد حظور دارد، محدود می کند. از این رو اگر ما تنها از ادغام استفاده کنیم، بسیار سریع به نقطه همگرایی می رسیم که یک نقطه همگرایی محلی است. ما به این نقطه بدون جستجو در بخش های دیگر فضای طراحی رسیدیم. این کار ما را از پیدا کردن طرح های بهتر موجود در مناطق دیگر بازمی دارد و همچنین از رسیدن به نقطه همگرایی جهانی جلوگیری می کند. برای رفتن به مناطق مختلف در فضای طراحی ما باید مطمئن شویم که متغیرهای طراحی در بخش های مختلف فضای طراحی انتخاب شده اند.
جهش: از جهش برای معرفی طرح هایی در سایر بخش های فضای طراحی استفاده می شود. جهش پس از ادغام و با احتمال کمتر استفاده می شود. در جهش نقطه کاربرد به صورت تصادفی انتخاب می شود و در آن نقطه مقدار متغیر طراحی به طور تصادفی ازبین گزینه های موجود انتخاب شده است.
در ادغام ما طرح های جدید را با ترکیب بخش های مختلف از طرح های موجود تولید می کنیم. در این فرایند ما تنها طرح هایی را می توانیم تولید کنیم که توسط مقادیر متغیر طراحی در طرح های موجودشکل گرفته اند و در دسترس هستند. ما نمی توانیم هیچ طرحی را با داشتن برخی متغیرهای دیگر طراحی تولید کنیم. به عنوان مثال، در بحث ادغام ما دیدیم که 4، 2، 3، 3، 2، 1 و 3، 4، 2، 2، 2، 1 می تواند طرح های 4، 2، 3، 2، 2، 1 و 3، 4، 2، 3، 2،1 را تولید کند. اما ما نمی توانیم طرحی به صورت 4، 2، 3، 2، 5،1 تولید کنیم. ما می توانیم با استفاده از جهش به این طرح برسیم.
مثال: اجازه دهید طراحی اولیه 4، 2، 3، 2، 2،1 باشد. اگر نقطه تصادفی کاربردی جهش 5 باشد پس ما طراحی با مقدار متغیر پنجم را از گزینه های موجود انتخاب میکنیم. اگر گزینه های موجود 1،2،3،4،5،6 باشند و اگر ما 5 را به عنوان گزینه تصادفی انتخاب کنیم ، طراحی جدید 4، 2، 3، 2، 5،1 خواهد بود. بنابراین جهش به ما اجازه می دهد تا در میان فضای طراحی حرکت کنیم و در نتیجه مانع از همگرایی زودرس می شود.
بنابراین ما به نسل جدیدی از طرح ها با استفاده از الگوریتم ژنتیک می رسیم. این ما را به طرح هایی که به صورت یک مرز غالب است،می رساند. روند محاسبه ارزش سازواری برای طرح ها، انتخاب و تولید جمعیت جدید از طرح ها، تکرار می شود تا زمانی که GA بتواند مرز غالب را بهبود بخشد و یا تا زمانی که به تعداد اولیه ای از نسل ها برسد. نتیجه نهایی مجموعه ای از طرح های در سطح جهانی غالب خواهد بود.(سیارک)
