پایان نامه تغییر الگوریتم بهینه سازی فاخته جهت استفاده در محیط های پویا

پایان‌نامه برای دریافت درجه کارشناسی ارشد

رشته مهندسی کامپیوتر گرایش هوش مصنوعی.

چکیده

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

واژه‌های کلیدی: مسائل بهینه­ سازی پویا، الگوریتم­ های تکاملی و الگوریتم بهینه ­سازی فاخته

فصل اول: مقدمه

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

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

در پژوهش­های انجام شده تاکنون از سه روش اصلی در الگوریتم­های تکاملی برای حل مسائل
بهینه­سازی پویا استفاده شده است: (1) ایجاد تنوع، (2) به ­کارگیری حافظه و (3) رویکرد چند-جمعیتی. به دلیل امکان ایجاد تغییرات در فضایی که هیچ عضوی در آن حضور ندارد و یا امکان هم­گرایی اعضا در آن منطقه، از رویکرد ایجاد تنوع استفاده می­شود. جهت تحقق این امر در الگوریتم­هایی چون الگوریتم ژنتیک، از مهاجران تصادفی و گاهی از مکانیزم خود-تطبیقی در نرخ جابجایی مهاجران وارد شده به جمعیت بهره گرفته شده است. در الگوریتم­های کلونی مورچگان و کلونی زنبورهای مصنوعی از خودکار سلولی و در یک نمونه نیز از الگوریتم ایمنی مصنوعی بر پایه­ی خودکار یادگیرنده، استفاده شده است. همچنین محققان سعی کردند تا با به­ کارگیری حافظه و استفاده از بهترین اعضای جمعیت بتوانند الگوریتم ژنتیک را با محیط­هایی که در معرض تغییرات کم قرار می­گیرند تا حدی سازگار نمایند. در نمونه­های دیگر از الگوریتم­هایی چون الگوریتم بهینه­سازی تجمعی ذرات[1]، الگوریتم گروه ماهی­های مصنوعی[2] و الگوریتم کرم شب­تاب[3] از رویکرد چند-جمعیتی استفاده شده که در آن­ها از چندین جمعیت در فضای جستجو برای ایجاد تعادل بین اکتشاف[4] و استخراج[5] نقطه­ی (نقاط) بهینه و ردیابی هر چه بهتر آن(ها) بهره گرفته شده است.

در این پایان­نامه یکی از جدیدترین الگوریتم­ های تکاملی، الگوریتم بهینه­سازی فاخته[6]، برای حل مسائل بهینه­سازی پویا ارائه می­گردد. این الگوریتم همان طور که از نامش پیداست از نحوه­ی زندگی پرنده­ای موسوم به فاخته الهام گرفته شده است. مسئله­ای که در این جا وجود دارد اینست که الگوریتم فاخته برای حل مسائل بهینه­سازی ایستا به ­کار رفته و نتایج خوبی را گزارش داده است. حال آن­که برای استفاده از این الگوریتم در حل مسائل بهینه­سازی پویا یکسری مکانیزم­هایی جهت ردیابی بهینه در زمان تغییرات و نیز برقراری نوعی تعادل در عملیات اکتشاف و استخراج، افزوده می­شوند.

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

فصل دوم: شرح مسئله

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

2-1 محیط­های پویا و مسائل بهینه­سازی پویا

محیط­های پویا، که به نام مسائل پویا[7] یا مسائل وابسته به زمان[8] شناخته می­شوند، محیط­هایی هستند که در طول زمان می­توانند شاهد تغییرات پیوسته یا گسسته در خود باشند. این تغییرات می­تواند در حوزه­ی وسیعی اتفاق بیافتد. از جمله این­که تعداد، ابعاد، دامنه­ی پارامترهای محیطی و یا دیگر ویژگی­ها­ می­تواند تغییر کند. از دیگر مواردی که ممکن است اتفاق بیافتد، تغییر مقدار پارامترها با توجه به زمان است. در نهایت در کلیه­ی تغییرات ایجاد شده، محیط با تغییر نقطه یا نقاط بهینه­ی سراسری و محلی روبرو می­گردد. مسایلی که در این حوزه تعریف می­شوند هم در بخش آزمایشگاهی و هم در دنیای واقعی به این محیط­ها عینیت می­بخشند. از جمله­ی آن­ها، مسائل بهینه­سازی پویا[9] بوده که در آن­ها مقدار تابع برازندگی مرتب تغییر می­کند. به طور دقیق­تر در تعریف ریاضی این گونه مسائل خواهیم داشت [1] :

(2‑1)

که در آن  فضای جستجو،  زمان،  تابع شایستگی که مقادیر عددی  را به هر راه­حل ممکن ( ) در زمان  نسبت می­دهد و  مجموع راه­حل­های شدنی  در زمان  می­باشد.

2-2 تغییرات پیوسته و ناپیوسته

از حیث تغییرات ایجاد شده در نقطه­ی (نقاط) بهینه­ی تابع هدف، محیط می­تواند شاهد دو نوع تغییر پیوسته یا ناپیوسته باشد [2]. اگر  تابع هدف ایستا در نظر گرفته شود، آن­گاه با اعمال تغییرات خواهیم داشت:  که در آن بردار جابجایی  مسیر حرکت بهینه[10] را کنترل
می­کند. بنابراین در صورتی که  بهینه­ی تابع  باشد، در آن ­صورت  بهینه­ی  در زمان  خواهد بود. حال  می­تواند به طرق مختلف تعریف گردد: اگر  ­باشد، مسیر حرکت بهینه به­ صورت خطی و اگر   باشد، مسیر حرکت بهینه به ­طور تناوبی خواهد بود که در آن­ها شدت تغییر به وسیله­ی مقدار  تعیین می­گردد. در شرایط ناپیوسته نقطه­ی بهینه از یک موقعیت به یک موقعیت دیگر پرش می­کند. چنین رفتاری به وسیله­ی توابع چند حالته[11]
ایجاد می­گردد. به ­طورکلی مسایل با تغییرات ناپیوسته به­ مراتب سخت­تر از تغییرات پیوسته می­باشند که در این پایان­نامه تغییرات به صورت ناپیوسته اعمال می­شود.

2-3 تغییرات سراسری و مقطعی

از دیدگاهی دیگر تغییرات ایجاد شده در فضای مسئله می­تواند به طور سراسری یا مقطعی باشد. زمانی­که

مقدار شایستگی تمام نقاط موجود در فضای مسئله تغییر ­کند، تغییرات سراسری و در صورتی­که مقدار شایستگی بعضی نقاط موجود در فضای مسئله تغییر ­کند، تغییرات مقطعی خواهند بود. در این پژوهش کلیه­ی تغییرات محیطی به طور پیش فرض سراسری در نظر گرفته ­می­شوند. بدین ترتیب تنها با تست کردن یک نقطه در فضای مسئله و مقایسه­ی مقدار شایستگی بدست آمده­ با مقدار قبلی ذخیره شده­ی آن، می­توان متوجه تغییرات محیطی شد [3].

2-4 اهدف

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

 2-5 خلاصه­ی فصل

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

فصل سوم: مفاهیم پایه‌ای

مطالب این فصل در چهار بخش ارائه می­گردد که در ابتدا به معرفی الگوریتم بهینه­سازی فاخته و مفاهیم مربوط به آن پرداخته می­شود. سپس یکی از مولدهای مسائل پویا به نام تابع محک قله­های متحرک [12]که در این پژوهش مورد استفاده گردیده است، به همراه معیار کارآیی در نظر گرفته شده در بررسی نتایج، ارائه می­شوند.

3-1 الگوریتم بهینه­سازی فاخته

الگوریتم بهینه­سازی فاخته  توسط رجبیون در سال 2011 ارائه گردید [4] که این پایان­نامه بر اساس این الگوریتم می­باشد. در ادامه جزئیات این الگوریتم بیان می­شود.

3-1-1 روش زندگی و تخم­گذاری فاخته­ها

همه­ی انواع پرندگان برای مادر شدن رویه­ی تخم­گذاری را دنبال می­کنند. همه­ی آن­ها تخم گذاشته و جوجه­ی خود را بیرون از بدنشان پرورش می­دهند. هر چقدر تخم گذاشته شده بزرگتر باشد، مادر قادر به نگهداری فقط یک تخم بوده و در ضمن توانایی پرواز پرنده­ی مادر نیز سخت­تر خواهد شد. از طرفی چون تخم­ها منبع سرشار از پروتئین برای انواع شکارچیان می­باشند، پرندگان باید مکان امنی برای رشد
تخم­های خود پیدا کنند. پیدا کردن این مکان به عنوان یک چالش برای پرندگان محسوب می­گردد. لذا آن­ها از یک مهندسی پیچیده و طراحی هنرمندانه­ای برای این امر استفاده می­کنند. اکثر پرندگان
لانه­های خود را به صورت مستتر در پوشش­های گیاهی ایجاد می­کنند تا تخم­هایشان از شناسایی شکارچیان در امان باشند. در این بین پرندگانی هم وجود دارند که خود را از دردسر لانه­سازی رها کرده و بجای ساختن لانه برای تخم­های خود آن­ها را در لانه­های دیگر پرندگان قرار می­دهند و صبر می­کنند تا تخم­هایشان توسط پرندگان دیگر رشد و تغذیه نمایند. به این پرندگان «پارازیت­های اولاد[13]» گویند.

فاخته­ها بهترین نمونه­ی پارازیت­های اولادی هستند. آن­ها یک تخم از تخم­های پرنده­ی میزبان را از بین برده، تخم خود را بجای آن قرار داده و سریع از محل دور می­شوند. فاخته­ها این کار را با تقلید از رنگ و الگوی[14] تخم­های موجود در هر لانه انجام می­دهند تا تخم­های جدید لانه شبیه به تخم­های قبلی و واقعی میزبان باشند. نحوه­ی تقلید کردن از تخم­ها همچنان از اسرار طبیعت به شمار می­آید. در ضمن هر فاخته­ی ماده روی نوع خاصی از گونه­های پرندگان تخصص می­یابد. از طرفی حالتی هم وجود دارد که پرندگان میزبان تخم­های فاخته­ها را شناسایی کرده و یا آن­ها را از لانه­ی خود به بیرون پرت می­کنند یا خودشان لانه­ی لورفته را ترک کرده و لانه­ی جدیدی برپا می­کنند. فاخته­ها به طور پیوسته تقلید خود را از تخم­های لانه­های هدف بهبود می­دهند. در مقابل نیز پرندگان میزبان روش­های شناسایی تخم­های بیگانه را یاد می­گیرند. این تلاش و مبارزه بین پرندگان و فاخته­ها یک فرآیند مداوم و پیوسته است.

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

Abstract

Dynamic environments are the environments which allocate the potentiality of changes over time to themselves. These changes can occur in different ways for instance changes in parameters, objective functions or constraints of the problem. In this regard, a comprehensive domain of different sciences such as management, economics, computer, mathematics and so on is facing with these changes which are theoritically and practically posed in the real world. Accordingly, problem-solving in dynamic environments, which are known as solving dynamic optimization problems, have been raised since a few decades ago. The most important challenge in solving these kinds of problems is related to its compatibility with the newly changed environment. Therefore, there is a need to track and follow up the new optimum (optima) in the problem space. In order to meet this challenge, the researchers intended to benefit from applying the evolutionary algorithms inspired by the principle of evolutionary processes and adding a set of special mechanisms. These problems will encounter with another challenge of finding the optimum (optima) as accurately as possible. To this end, the algorithms with high convergence speed and local search ability should be used as much as possible. Cuckoo Optimization Algorithm (COA) is one of the evolutionary algorithms which has demonstrated its high convergence speed and local search ability in static environments. However, the use of this algorithm in dynamic environments has not been examined yet. Thus, this research aims to represent a new version of this algorithm which can be applied in dynamic environments. In order to accomplish this goal, firstly some changes have been made on the basic structure of standard algorithm. In addition, a self-adaptive mechanism on the cuckoos` Egg Laying Radius is exploited to increase the convergence speed and the local search ability. Then, in order to track the optimum (optima) after the environmental changes, a multi-swarm algorithm, a mechanism of creating free swarm and exclusion mechanism have been applied. Also, to meet the challenges of diversity loss and invalid memory in the converged swarms, the cuckoos of each swarm are distributed in a radius (determined according to the shift length parameter) around the best cuckoo of that swarm and then are evaluated. In non-convergent swarms, only the fitness value of the cuckoos’ position of that swarm will be re-evaluated. Deactivation mechanism is another mechanism that is applied to enhance the performance of algorithm in dynamic environments. Finally, the obtained results indicate that the proposed algorithm works efficiently in comparison with most other algorithms.

Key words: Dynamic Optimization Problems, Evolutionary Algorithms and Cuckoo Optimization Algorithm