بخشی از مقاله
چکیده
الگوریتم ژنتیک دیپلوید، یکی از الگوریتمهاي تکاملی است که بر اساس جمعیت و جستجوي تصادفی عمل میکند و در آن هر فرد داراي دو کروموزم است. کاربرد اصلی این الگوریتم در مسائل بهینهسازي است. دراین مقاله، روشی جدید براي بهبود سرعت و عملکرد الگوریتم ژنتیک دیپلوید ارائه شده است. در این روش پیشنهادي، علاوه بر جستجوي سراسري، جستجوي محلی نیز انجام میشود. استفاده از جستجوي محلی باعث شده است که در هر تکرار، احتمال تولید راهحلهاي بهتر و تولید نقاطی با شایستگی بالاتر افزایش یابد. این امر، موجب افزایش سرعت الگوریتم در همگرایی به نقاط بهینه و تولید جوابهایی با شایستگی بالاتر شده است.
الگوریتم پیشنهادي بر روي پنج تابع استاندارد آزمایش شدهاند. این توابع، معمولا معیار سنجش الگوریتمهاي بهینهسازي در فضاهاي پیوسته و ایستا هستند. این نتایج، با نتایج حاصل از سایر الگوریتمهاي ژنتیک دیپلوید و الگوریتم گروه ذرات مقایسه شده است. نتایج عددي نشان میدهد که الگوریتم پیشنهادي، نسبت به سایر الگوریتمهاي ژنتیک دیپلوید و الگوریتم گروه ذرات عملکرد بهتري دارد و نتایج امیدبخشی را بر حسب کیفیت راهحل نشان میدهد.
-1 مقدمه
بهینهسازي به این مفهوم است که بین پارامترهاي یک تابع به دنبال مقادیري باشیم که تابع را کمینه و یا بیشینه نمایند. کلیهي مقادیر مناسب جهت این امر را، راهحلهاي ممکن و بهترین مقدار از این مقادیر را، راهحل بهینه مینامند. الگوریتمهاي بهینهسازي ، هر دو نوع مسائل بیشینهسازي و کمینهسازي را پوشش میدهند. بهینهسازي کاربردهاي زیادي دارد از جمله در تخصیص منابع، زمانبنديها، تصمیمگیريها و غیره. روشهاي مختلفی براي بهینه- سازي وجود دارد. یکی از رایجترین روشهاي بهینهسازي، الگوریتمهاي تکاملی هستند که در آنها از قوانین تکاملی موجود در طبیعت، به منظور بهینه-سازي استفاده میشود.
روند کلی الگوریتمهاي تکاملی بدین شکل است که ابتدا یک جمعیت اولیه که هر عضو آن میتواند جوابی براي مساله باشد به صورت تصادفی و در بازه مجاز تابع مورد بررسی، ایجاد و شایستگی هر عضو از این مجموعه اولیه، محاسبه میشود. سپس در هر نسل، با یک روش انتخاب، افرادي را از بین جمعیت انتخاب میکنیم. پس از این انتخاب با یک احتمال که احتمال بازترکیبی نامیده میشود بر روي افراد انتخاب شده، عمل بازترکیبی انجام میشود تا فرزندان تولید شوند. سپس بر روي تمامیفرزندان، با یک احتمال مشخص که احتمال جهش نامیده میشود عمل جهش صورت میگیرد. در نهایت با استفاده از یک روش از قبل تعیین شده براي انتخاب بازماندگان، عمل انتخاب صورت گرفته و به اندازه جمعیت، از بین فرزندان تولید شده، انتخاب انجام میشود. افراد انتخاب شده جایگزین جمعیت قبلی میشوند و الگوریتم ادامه مییابد.[3]
الگوریتم ژنتیک با تکیه بر نظریه داروین یکی از متداولترین و پرکاربردترین فرامکاشفههایی است که در بهینهسازي مورد استفاده قرار می-گیرد. الگوریتم ژنتیکی که در آن نمایش یک فرد به صورت دیپلویدي - دوتایی - بوده و همراه با مکانیزم غلبه باشد، الگوریتم ژنتیک دیپلوید نامیده میشود. هر فرد در الگوریتم ژنتیک دیپلوید، داراي دو کروموزم ژنوتایپ است که بر اساس جدول مکانیزم غلبه، به یک کروموزم فنوتایپ نگاشت میشود و میزان شایستگی فرد نیز از روي فنوتایپ آن محاسبه میگردد.
تاکنون، محققان مکانیزمهاي غلبه و نمایشهاي ژنوتایپی متفاوتی را ارائه کردهاند. در سال 1987، گلدبرگ و اسمیت گزارشی از آزمایشها خود ارائه نمودند که در آن دیپلویدي و غلبه به کار برده شده است. آنها از یک قالب سهتایی استفاده کردند که در آن هر محتواي ژنی میتوانست یکی از سه مقدار "0" یا 1"مغلوب" یا 1"غالب" باشد. در سال 1995، این روش، با نگاهی منتقدانه توسط انجی و وانگ مورد بررسی قرار گرفت. آنها بیان کردند که قالب سهتایی مطرح شده، قالبی تبعیضآمیز است.
انجی و وانگ، یک روش دیپلویدي جدیدي با چهار محتواي ژنی ارائه کردند که در آن 0 و 1 هر کدام میتوانستند غالب و یا مغلوب باشند. در سال 1997، رایان، از نمایش چندتایی افراد استفاده کرد. ویژگی فنوتایپی زمانی 1 میشد که از یک حد آستانهاي مشخص، بیشتر شود و در غیر اینصورت 0 میشد. در سال 1998، این نمودار کم کم گسترش پیدا کرد و به این صورت در آمد که ویژگی فنوتایپی زمانی 1 میشود که از یک حد آستانهي مشخصی بیشتر شود و زمانی 0 میشود که از یک حد آستانهاي دیگر کوچکتر شود و اگر بین این دو حد آستانه بود، مقدار آن به طور تصادفی مشخص میشود.[1,2,10]
الگوریتم ژنتیک دیپلوید داراي سرعت همگرایی بالایی است. با این وجود ، این الگوریتم داراي کاستیهایی نیز میباشد از آن جمله که در گامهاي نخست اجراي الگوریتم، ناحیههایی از فضاي مسئله که بهینههاي سراسري و محلی در آن واقع شدهاند، به خوبی شناسایی میشوند ولی در ادامهي مسیر به سمت بهینهي سراسري کند عمل میکند و یا پس از رسیدن به بهینهي سراسري از آن دور میشود. در این مقاله سعی در رفع این مشکلات و بهبود کارایی الگوریتم شده است. ادامهي این مقاله بدین صورت سازماندهی شده است: بخش دوم به معرفی الگوریتم ژنتیک دیپلوید میپردازد. در بخش سوم، توضیحاتی دربارهي جستجوي محلی ارائه میشود و در بخش چهارم، الگوریتم پیشنهادي شرح داده شده است. بخش پنجم، نتایج آزمایشها را ارائه میکند و بخش پایانی به نتیجهگیري میپردازد.
-2 الگوریتم ژنتیک دیپلوید
الگوریتم ژنتیکی که در آن نمایش یک فرد به صورت دیپلویدي - دوتایی - بوده و همراه با مکانیزم غلبه باشد، الگوریتم ژنتیک دیپلوید نامیده میشود. الگوریتم ژنتیک دیپلوید از دو جنبهي اساسی با الگوریتم ژنتیک متفاوت است: -1 نمایش افراد و ارزیابی -2 عملیات تولید.[11,12,13]
-1-2 نمایش افراد و ارزیابی
هر فرد در الگوریتم ژنتیک دیپلوید داراي دو کروموزم ژنوتوپیکی است. براي ارزیابی هر فرد، ابتدا باید دو کروموزم ژنوتایپیاش به یک کروموزم فنوتایپی بر طبق مکانیزم غلبه نگاشت شود. سپس فنوتایپ، مورد ارزیابی قرار گرفته و میزان شایستگی فرد مشخص میشود.[6] نمایش ژنوتوپیکی و مکانیزم غلبه، نقشی کلیدي در کارایی الگوریتم ژنتیک دیپلوید دارند. تاکنون، محققان مکانیزمهاي غلبه و نمایشهاي ژنوتوپیکی متفاوتی را ارائه نمودهاند. شاخصترین مکانیزمهاي غلبه، مدل-Ng Wong و مدل Additive میباشد. در مدل Ng-Wong چهار محتواي ژنی وجود دارد: "1" و "0" که مقادیر غالب هستند و "i" و "o" که مقادیر مغلوب میباشند. همواره مقادیر غالب در فنوتایپ بیان میشوند.
اگر رقابت بین دو مقدار غالب و یا دو مقدار مغلوب باشد، یکی از آنها به طور تصادفی انتخاب میشود و اگر یکی از مقادیر، غالب و دیگري مغلوب باشد، مقدار غالب بیان خواهد شد. جدول نگاشت ژنوتایپ به فنوتایپ Ng-Wong در شکل - 1 - نشان داده شده است. در مدل Additive، چهار محتواي ژنی وجود دارد: A، B، C و .D به ترتیب محتواهاي ژنی، مقادیر عددي مرتب شدهاي انتساب داده میشود.
به طور مثال، مقادیر 2، 3، 7 و 9 به ترتیب، به چهار محتواي ژنی A، B، C و D نسبت داده شده است. براي بدست آوردن مقدار فنوتوپیکی، بر روي جفت مقادیر عددي منسوب به محتواي ژنوتوپیکیاش، عمل جمع انجام میشود. اگر این حاصلجمع بیشتر از 10 باشد، مقدار فنوتوپیکی مربوطه، 1 میشود، در غیر اینصورت، 0 خواهد شد. جدول نگاشت ژنوتایپ به فنوتایپ Additive در شکل - 2 - نشان داده شده است.[7]
-2-2 عملیات بازترکیب
در الگوریتم زنتیک دیپلوید، عملیات بازترکیب در دو مرحله انجام میپذیرد: در مرحلهي اول، دو والد، کروموزمهایشان را به صورت تصادفی با یکدیگر جابجا میکنند تا دو فرزند موقتی ایجاد شود. در مرحلهي دوم، بر روي دو کروموزم هر فرزند، عملیات بازترکیب انجام میشود که روال آن مشابه با الگوریتم ژنتیک است. بعد از بازترکیب، بر روي هر کدام از کروموزمهاي فرزندان، به طور مستقل، عملیات جهش انجام میشود.
-3 روش پیشنهادي
در مسائل بهینهسازي، دو هدف رقابتی در انجام جستجو، به منظور رسیدن به بهینه سراسري وجود دارد که الگوریتم بهینه سازي باید مکانیزمی براي متعادل کردن این دو هدف متمایز داشته باشد:
اکتشاف: براي جستجوي کارآمد کل فضاي جستجو است که به معناي اطمینان از سراسري بودن جستجو میباشد و از آن جهت داراي اهمیت است که فضاي مسئله باید به نحو قابل توجهی براي یافتن بهینهي سراسري جستجو شود. در واقع اکتشاف به عملی گفته میشود که منجر به کشف یک پاسخ مناسب از ناحیهاي از فضاي مسئله میگردد که قبلا مورد جستجو قرار نگرفته است.
بهرهبرداري: براي متمرکز شدن بر روي بهترین پاسخهایی است که تاکنون پیدا شدهاند که احتمالا بهترین پاسخ، از همسایگان آن پاسخها خواهد بود. در واقع در بهره برداري، جستجوي محلی انجام میشود. اگر تعادل مناسبی بین قابلیت اکتشاف سراسري و بهرهبرداري محلی برقرار باشد، الگوریتم میتواند به آسانی پاسخهایی با دقت بالا تولید کند. در گامهاي نخست اجراي الگوریتم ژنتیک دیپلوید، ناحیههایی از فضاي مسئله که بهینههاي سراسري و محلی در آن واقع شدهاند، به خوبی شناسایی می-شوند ولی در ادامهي مسیر به سمت بهینهي سراسري کند عمل میکند و یا پس از رسیدن به بهینهي سراسري از آن دور میشود. براي رفع این مشکل از ترکیب الگوریتم با جستجوي محلی استفاده شده است که از این طریق می-توان فرآیندهاي جداگانهاي را براي بهبود افراد جمعیت به کار برد. از ترکیب جستجوهاي مکاشفهاي محلی با الگوریتم ژنتیک دیپلوید، میتوان در زمان کمتري، نتایجی بهتر را بدست آورد.
الگوریتم ژنتیک دیپلوید براي شناسایی بخش وسیعی از فضاي جستجو استفاده میشود، در حالی که یک جستجوي محلی در درون الگوریتم ژنتیک دیپلوید میتواند حوزهي نزدیک به هر پاسخ یافت شده توسط الگوریتم را - که به آن همسایگی گفته میشود - براي یافتن پاسخهاي بهتر مورد جستجو قرار دهد. در این الگوریتم، عملگر جستجوي محلی پس از عملگرهاي ژنتیکی، براي بهبود شایستگی استفاده میشود و پس از آن، اعمال ارزیابی و جایگزینی در جمعیت صورت میگیرد. وابسته به این که براي پیادهسازي الگوریتم از چه عملگرهایی و یا براي جستجوي محلی از کدام روش استفاده شود، نتایج بسیار متفاوتی ایجاد خواهد داشت. شکل - 3 - ، شبه کد الگوریتم ژنتیک دیپلوید بهبود یافته را نمایش میدهد.
-1 -3 مقداردهی و ارزیابی اولیه
در این الگوریتم، از نمایش دوتایی افراد استفاده میشود و هر فرد داراي دو کروموزم است. در ابتدا کروموزمها به صورت تصادفی و با 4 محتواي ژن مقداردهی اولیه میشوند. بنابراین ژنها میتوانند داراي مقادیر مشابه و یا متفاوت باشند. سپس به کمک جدول مکانیزم غلبهي Ng Wong، دو کروموزوم ژنوتایپ هر فرد، به یک کروموزم فنوتایپ باینري نگاشت میشود و بر اساس کروموزمهاي فنوتایپ، میزان شایستگی افراد محاسبه میشود.
-2-3 تولید فرزندان
با یکی از روشهاي انتخاب، افرادي از جمعیت اولیه انتخاب میشوند تا با احتمال بازترکیب، بر روي آنها عملیات بازترکیب انجام شود. این عملیات در دو مرحله صورت میگیرد:
- 1 دو والد، کروموزمهایشان را به صورت تصادفی با یکدیگر جابجا میکنند تا دو فرزند موقتی ایجاد شود. در این صورت، هر فرزند یک کروموزم از هر والد خود دارا است، پس ویژگیهاي ژنوتوپیکی والدین با یکدیگر ترکیب شده است.
-2 بر روي دو کروموزم هر فرزند، عملیات بازترکیب یکنواخت انجام میشود که روال آن مشابه با الگوریتم ژنتیک است. بعد از بازترکیب، بر روي هر کدام از کروموزمهاي فرزندان، به طور مستقل، با احتمال جهش، عملیات جهش بیتی انجام میشود. از آنجایی که جهش بر روي ژنوتایپهاي هر فرد انجام میشود، ممکن است که جهش یک ژن، فنوتایپ فرد را تغییر ندهد. در نهایت، شایستگی فرزندان بر اساس کروموزمهاي فنوتایپشان محاسبه میشود.[10,12]
-3-3 جستجوي محلی
جستجوي محلی یک فرایند تکراري ساده براي ارزیابی راهحل بالقوه بدست آمده در فضاي جستجو است. بدین صورت که به سمت راهحلی دیگر در همسایگی راهحل اصلی بدست آمده - فرزندان - میرود و آن را با راهحل اصلی مقایسه میکند. اگر راهحل جدید بهتر از راهحل اصلی بود، فرآیند جستجو با همسایههاي راهحل جدید ادامه پیدا میکند. در غیر این صورت راهحل بالقوهي دیگري در همسایگی راهحل اصلی آزمایش میشود.
برعکس جستجوي سراسري که کل فضاي جستجو را بررسی میکند، جستجوي محلی، منطقهاي است و فقط ناحیهي کوچکی از فضاي جستجو را بررسی میکند و این ناحیه وابسته به نقطه شروع و ساختار همسایگی است. ساختار همسایگی نقشی کلیدي بر تأثیرگذاري و کارایی جستجوي محلی دارد. هرچه اندازه همسایگی بزرگتر شود، کارایی الگوریتم کاهش مییابد، البته، شانس یافتن نمونههاي بهتر افزایش مییابد.[4,5,8,9] با در نظر گرفتن تنظیمات زیر، بهترین پاسخها حاصل میشوند: الف - همسایگی به اندازهي یک بیت در نظر گرفته میشود و تنها همسایگیهایی که در یک بیت با فرد مورد نظر اختلاف داشته باشند مورد بررسی قرار میگیرند.
زیرا همسایگی بزرگتر از یک بیت، زمان پردازش بسیار زیادي نیاز دارد که به صرفه نیست. ب - با توجه به اینکه هر فرد داراي دو کروموزم است، بر روي هر دو کروموزم فرد، بیت مورد نظر تغییر داده میشود. پ - با توجه به اینکه ژنوتایپها داراي 4 محتواي ژن هستند، بیت مورد نظر به اندازهي یک واحد تغییر داده میشود. به طور مثال، اگر 1 باشد تبدیل به 2 میشود، اگر 2 باشد تبدیل به 3 میشود و ... شبه کد جستجوي محلی پیشنهادي در شکل - 4 - نشان داده شده است.
