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

یکی از دوستان سوالی در مورد نحوه برخورد با قید ها (Constraints) در الگوریتم رقابت استعماری مطرح کرده بودند. به علت طولانی بودن پاسخ این سوال، در یک فایل صوتی برخی از روشهای عمومی مدیریت قیدها در الگوریتم رقابت استعماری بیان شده است. البته همانگونه که در فایل صوتی تهیه شده ملاحظه خواهید کرد، اغلب روشهای مدیریت قیود وابسته به الگوریتم خاصی نمی باشند. بنابراین اگر مثلاً روشی هست که الگوریتم ژنتیک را برای حل مسائل مقید مناسب می کند، با اندکی تغییرات به سادگی می تواند به روش بهینه سازی دیگری مثل الگوریتم رقابت استعماری اعمال شود.

 

• دانلود فایل صوتی – بخش 1: سرور1، لینک های کمکی: سرور2، سرور3 ، سرور4
• دانلود فایل صوتی – بخش 2: سرور1، لینک های کمکی: سرور2، سرور3 ، سرور4
• دانلود فایل صوتی – بخش 3: سرور1، لینک های کمکی: سرور2، سرور3 ، سرور4

نکته: در صورت استفاده از سرور شماره چهار جهت دانلود، باید از طریق اکانت گوگل (یا همان جیمیل) خود پس از کلیک بر روی لینک ها وارد شوید.

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

با سلام
در مورد مدیریت قیدها در الگوریتم های تکاملی از جمله الگوریتیم ژنتیک، الگوریتم پرندگان، زنبور عسل و الگوریتم رقابت استعماری و کلاً مسأله ای که مطرح است این است که روش هایی که موجود هستند و ما از آن ها استفاده می کنیم مستقل از نوع الگوریتم هستند. یعنی این، این طور نیستند که بگوییم روش هندل کردن قید در فلان جا. معمولاً روشی مدیریت قیود (Constraint Handling) که برای یک الگوریتم استفاده می شود برای یک الگوریتم دیگر هم قابل استفاده است. ما خود را محدود به هیچ الگوریتمی نمی کنیم و کلاً بازی کردن با قیدها مبحث جداگانه و تخصص جداگانه ای از کارکردن با خود فقط الگوریتم است.

ساده ترین روشی که برای مدیریت قیود استفاده می شود این است که در روش های تکاملی ما یک تابع هزینه ای داریم که این تابع هزینه ها را با یک برنامه جداگانه می خواهیم مینیمم یا ماکس آن را پیدا کنیم. که آن برنامه جداگانه می تواند برنامه الگوریتم ژنتیک، پرندگان باشد و غیره.
اولاً باید برنامه ها را از همان ابتدا برای این که بتوانیم جواب خوب بگیریم ماژولار بنویسیم. (یعنی تابع هزینه را از خود برنامه جدا کنیم). بعضی وقت ها دیده می شود که توی بعضی برنامه ها، افراد کل مسأله خود را در یک برنامه می نویسند.

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

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

حالا برویم سراغ های پیشگیری. روش های پیشگیری می گویند که اگر آن چیزی که اسمش را می گذاریم مجرم، در جامعه سعی کنیم نگذاریم متولد بشود. اگر مجرم متولد شد پانیش (تنبیه) کنیم. مثلاً یک قانون می تواند این باشد که هر کسی که پایش را فراتر از حدودی که تعیین شده گذاشت، اعدامش کنیم. این ساده ترین و کم پیچیده ترین قانونی است که می شود تصویب کرد. چه کار می کنیم؟ در الگوریتم ژنتیک می آییم پنالتی می گذاریم. مثلاً ما می دانیم که هزینه هایمان چه هستند.

به عبارت دیگر، خوب ما می خوایم مسأله مینیمم سازی حل کنیم یعنی هر چه کمتر باشد بهتر است ما می دانیم که هزینه هایمان بین منفی 10 تا 100 است یهو می آییم به آن جواب هایی که خیلی از قیود ما بیرون رفتند چه کار می کنیم؟ یهو یه پنالتی می دیم. مثلاً صد میلیون. یعنی چی؟ یعنی این می رود تو ته لیست جمعیت قرار می گیرد. خوب اعدام می شود یعنی می رود ته جمعیت ته لیست جمعیت و از جمعیت بیرون انداخته می شود. یعنی ما کافیه که در تابع هزینه مون که گفتیم به صورت جداگانه ما این رو نوشتیم یک تابع هزینه داریم f(x). داخل اون می نویسم f،x ؟؟ مثلاً اگر gx که هزینه ما هست کوچکتر از صفر شد همیشه می شود الگویش را می شود به این صورت نوشت. حالا بزرگ تر شد هر چی شد یعنی اگر عدول کرد، هزینه اش را بالا می گذاریم. مثلاً صد میلیارد. خوب این هم پس، آن یکی روش. روش اول که پیشگیری بود. روش درمان اولیه و سطحی که به ذهن می رسد همین است. این هم اگر جواب داد، ساده ترین کاری است که می شود انجام داد یعنی ما اگر بتوانیم با این روش کار را جلو ببریم می توانیم تا حدی خودمان را از پیچیدگی روشهای دیگر که در ادامه می گوییم رها کنیم. خوب ادامه را در بخش دوم ببینید.

خوب حالا ببینیم که اگر آن روش، بدیش چیه؟ آن روش بدیش اینه که اگر، شما جامعه ای را در نظر بگیرید که ما افراد به خاطر عبور از خط قرمز، به خاطر کشتن آدم، به خاطر توهین به فلانی به خاطر اعتراض به هر دلیلی یه مجازات اعدام بگذاریم جلویش یهو می بینیم که نصف آن جامعه مجرم هستند؛ یعنی حتی بیشتر از نصف یعنی وقتی ما با قیود پیچیده مواجه هستیم این روش جواب نمی دهد چون با عث می شود که اگر اعضای جمعیت ما مثلاً اگر صدتایی است با آن تعریفی که ما از جرم انجام داده ایم یهو می بینیم که 90 درصد از جامعه ما مجرم هستند و باید پانیش (نتبیه) بشوند و باید بروند ته لیست. در حقیقت، آن موقع ته لیستی اصلاً نیست که جمعیت برود ته لیست. ته لیست موقعی معنی دارد که ما صدتا عوض جمعیت داریم و پنج تاشون، دوتاشون، قیود را زیر پا می گذارند و ما آنها را می فرستیم ته لیست تا تنبیه بشوند. منتها وقتی که از صدتا جمعیت ما، در قیود پیچیده واقعاً مسائل همین گونه هستند یعنی آن قدر فضای در دسترس (Feasible Space) یعنی ناحیه ای که فیزبل (در دسترس) هست، جواب ها باید توش باشند؛ آن قدر نسبت به فضای کل جستجو کوچک هست، آن قدر قیود ما برای در حقیقت تعریف جرم بسته هست که کل جامعه خیلی وقت ها، خیلی وقت ها می شود بله، صد رصد حتی مجرم هستند . خوب ما می آییم فرض کنید روش در حقیقت مجازات که همشون را کاست (هزینه) صد میلیارد بدهیم در نظر می گیرم. خوب ما در نظر بگیرید جمعیتی را که صد تا عنصر توی جمعیتش وجود دارد ما به همشون کاست صد میلیارد دادیم؛ خوب یه لیستی داره یک سری افرادی در آن هستند همه اعدام. هیچ فرقی بین جرم پایین و کوچک و بالا وجود ندارد. مجازات، کل فلسفه اش اینه که ما بخواهیم جمعیت را اصلاح کنیم. ما که اینجا نمی خواهیم از جمعیت انتقام بگیریم؟!! هدف اینه که می خواهیم برسیم به یک جواب خوب. برسیم به یک جمعیت بهبود یافته. برسیم به جواب مسألمون. جواب هایی که افرادی که هستند که در قیود ما صدق می کنند. پس خلاصه بخواهیم بگوییم در مواردی که قیود، فضایی را ایجاد می کنند که فیزبل سولوشن (ناحیه در دسترس) ما خیلی کوچکتر است از آن فضایی که ما جستجو را از آن شروع کردیم و هیچ سنسی (احساسی) از فضای اصلی نداریم، در چنین مواردی با احتمال کمی پاپیولیشن ها می افتند داخل آن قیود.

خوب در مواردی که ناحیه در دسترس ما خیلی نسبت به فضای جستجوی اصلی که ما جستجو را باهاش شروع کردیم، کوچک هست، روش تنبیه مساوی و بزرگ برای کل جمعیت روش مناسبی نیست. خوب این را می توانیم خیلی ساده تست کنیم. می آییم چه کار می کنیم؟ می آییم پاپیولیشن (جمعیت) مثلاً هزارتایی را در نظر می گیرم. بعد این ها را به صورت تصادفی تولید می کنیم در آن فضای اولیه حدس. خوب این ها را پخش می کنیم بعد قیود را در نظر می گیریم اگر دیدیم مثلاً از این هزارتا فقط20 تا 50 تا فوقش 100 تا یعنی ده درصد قیود را رد کردند و بقیه در فضای اصلی هستند، همون تنبیه ساده کافیه. منتها یهو دیدیم از آن هزارتایی که ما تولید کردیم دو تا فقط هست یا حتی یک دانه و یا حتی اصلاً نیست در قیود ما صدق کند این روش دیگه جواب نمی دهد می پره این ور و آن ور.

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

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

روش سوم این است که ما بیاییم متناسب با عدول از قیود، پانیشمنت در نظر بگیریم. این به چه صورت است؟ می آییم می گویم مثلاً اگر قرار بود که x2 +x1 کوچکتر از 10 باشد و حالا، بزرگتر از 10 شده، نیائیم هر کروموزمی که x1+x2 برای آن؛ بزرگتر از 10 هست، پانیش کنیم. بیاییم چه کار کنیم؟ بیائیم میزان تنبیه رو برابر با میزان عدول در نظر بگیریم.

مثلاً به چه میزان از x1+x2 که باید 10 می شد بزرگتر است. اگه 11 هست یک واحد پانیش کنیم اگر 15 هست 5 واحد پانیش کنیم اگه 20 هست 10 واحد پانیش کنیم . این یعنی به اصطلاح متناسب با آن میزان عدول از قیود آن ها را پانیش کنیم. این یکی از روشهاست. پس میزان پانیش منت مساوی است با فاصله ای که از قیود می گیرند. مثلاً می توانیم، مثلاً اگر 5 تا قید داریم می گوییم مجموع فواصل از قیود را کمینه کنید.

یک روش هم این است که در کنار این که این ها را در نظر بگیریم تعداد عدول از قیود را هم در نظر می گیریم. معمولاً بعضی روش ها مثلاً اگه 7 یا 8 تا قید داریم می گوییم نه تنها میزان عدولشان بلکه تعداد عدولشان را هم در نظر بگیر. این چیزهایی که گفته می شود این جا، این جا روش استاندارد و کلاسیکی وجود ندارد گفته بشود بله ، این روش کار ماست. نه! این ها آن قدر باید باهاشون بازی بشود تا مناسب ترین روش اصلاح برای آن مسأله به دست بیاید. یعنی این طور نیست که ما قانونی را برای یک کشور تصویب کنیم و همان قانون برای کشور همسایه بتواند آن کشور را اصلاح کند. منتها خوب می شود قانون هایی را بهشون رسید که در میانگین، بهتر از قوانین دیگر جواب می دهند. منتها باید توجه کرد که این یک اکسیر یا کیور آل (cure-all) برای تمام مسائل نیست.

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

فقط یک مسأله را در نظر داشته باشید که باید خیلی حرفه ای با این مسأله برخورد شود. بعضی وقت ها، مثلاً پنالتی ها به گونه ای هستند که اول کار، خوب جواب می دهند، وسط ها مثلاً یهو می بینی که مسأله، بهینه سازی می شود؛ منتها در نهایت جواب می دهد که باز خارج از قیود ما هست. ریشه کار به چی بر می گردد؟ ریشه کار به این برمی گردد که شما اگر با موبایل داخل ماشین نشسته و صحبت کنید، جریمه اش مثلاً 10 هزار تومان است. منتها خیلی از افراد یک معامله مثلاً یک میلیونی را با همان مکالمه 5 دقیقه ای که اگه بگیرنش 10 هزار تومان جریمه اش باشد؛ انجام می دهند. یعنی پاپیولیشن ها (اعضای جمعیت) ما هم بعضی وقت ها می روند، قیدها را زیر پا می گذارند. منتها از این طرف، توی تابع هزینه یه جاهایی را پیدا می کنند که هزینه آن قدر کم می شود که شما اگر هزینه تمام قیود را جمع کنید و در نهایت باز جبران آن عدول از قیود نمی شود. یعنی در حقیقت می شود گفت پانیش منت (تنبیه) ما خیلی شُل هست. یعنی جامعه را خیلی شُل گرفتیم. این به این معنی نیست که بیاییم پانیش منت را بگیریم هر چی شد تابع به اضافه صد برابر عدول از قیود. نه! پانیش منت را باید در طی مسأله باید کم کنیم، زیاد کنیم، این ها چیزهایی که باید باهاشون مدتی بازی بشود که دستتون کاملاً بیاد.

کلاً paper های کانسرنت هندلنگ (مدیریت قیود) خیلی زیاد هستند. در مورد این ها می توانیم مجزا مطالعه کنیم. منتها این روش هایی که گفتم، روش های عام این قضیه هستند و می توانیم با مقداری بازی کردن باهاشون، کار کنید.

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

در ضمن نگاهی به مقالات منتشر شده در مورد الگوریتم رقابت استعماری در بخش مقالات و پایان نامه ها در سایت داشته باشید. مقالات خوبی در زمینه مدیریت قیود را خواهید دید.