بخشی از مقاله
چکیده
الگوریتم ژنتیک - GA - 1 یک روش جستجوي تصادفی است که براي یافتن جواب هاي دقیق یا تقریبی در مسائل بهینه سازي بکار می رود. این الگوریتم با شبیه سازي مفاهیم "وراثت"، "بقا سازگارترین فرد" و "تولید مثل" برگرفته از نظریه تکامل طبیعی، مجموعه اي از جوابهاي ممکن براي مساله مورد نظر را به مجموعه جدید تبدیل می کند. این دگرگونی براساس این انتظار است که مجموعه جدید، جوابهایی تولید کند که داراي مقادیر شایستگی با میانگین بالاتري هستند. در این مقاله ابتدا الگوریتم ژنتیک بطور مختصر معرفی می شود. در ادامه مدل هاي مختلف موازي سازي GA، با هدف بهبود اجراي آن مورد بررسی قرار می گیرند. در پایان نتیجه گیري مختصري ارائه می دهیم.
مقدمه
در طی سه دهه اخیر روش هاي بهینه سازي و جستجوي تصادفی بر اساس اصل تکامل طبیعی موجودات زنده مورد توجه قرار گرفته است. الگوریتم ژنتیک که ابتدا در دهه 70توسط هلند - 1 - معرفی شد یکی از این روشهاست. در سالهاي اخیر نسخه هاي مختلفی از این الگوریتم، بطور موفقیتآمیز در حل بسیاري از مسائل بکار رفته است . - 2 - مزیت آنها در مقایسه با سایر روشهاي جستجو به اثبات رسیده است و کاربردهاي عملی متنوعی که در حوزههایی مانند بیولوژي، شیمی، فیزیک، ریاضی، مهندسی، اقتصاد و کامپیوتر پیدا کرده اند دلیلی بر این ادعاست.
از سوي دیگر همراه با پیشرفتهاي حاصل شده در تکنولوژي و بهره گیري از معماري هاي مختلف موازي، مطالعات چندي بر روي نسخههاي موازي این الگوریتم انجام شده است . - 3 - این مطالعات با انگیزههاي بهبود سرعت و کارآیی الگوریتم، بکارگیري الگوریتمهاي ژنتیک براي مسائل پیچیدهتر و بکارگیري دقیقتر مفاهیم طبیعی انجام شده اند. این مقاله به صورت زیر سازماندهی شده است. بخش 2 به معرفی الگوریتم ژنتیک اختصاص یافته است. در بخش 3، سه روش اصلی اجراي موازي GA را توصیف و به بعضی از کاربردهاي آن اشاره می کنیم. در بخش 4 نتیجه گیري مختصري ارائه می دهیم.
الگوریتم هاي ژنتیک
الگوریتم ژنتیک با جمعیتی، که اعضاي آن بطور تصادفی تولید شده اند آغاز میشود. هر عضو در این مجموعه یک جواب تقریبی ممکن براي مساله است. اعضاي مجموعه به صورت منحصر بفردي به شکل دنباله اي مرتب از نمادهاي یک مجموعه الفبا بازنمایی - رمزگذاري - می شوند. رایجترین روش، بازنمایی دودویی است که با استفاده از مجموعه الفباي 1}و {0 تعریف می شود. براي مثال دنباله هاي 100010001 و 111000111011000 دو کروموزوم دودویی با طول هاي متفاوت هستند که نشان دهنده دو جواب ممکن براي مساله مفروض می باشند. فرایند جستجو بر روي همین نمایش رمزگذاري شده از متغیرهاي واقعی مساله انجام می شود.
در طول مرحله تولید مثل1، به هر کروموزوم عددي به نام مقدار شایستگی وابسته می شود. این مقادیر بر اساس یک تابع هدف - شایستگی - که در درون مسأله نهفته است تعیین میشوند. مقدار شایستگی به عنوان میزانی براي ارزیابی عملکرد فرد در اجتماع تلقی میشود. بنابراین تابع هدف محکی براي انتخاب افرادي فراهم میکند که در طول فرایند تولید مثل از میزان شایستگی بیشتري براي جفت2 شدن با یکدیگر برخوردار هستند. شایستگی در دنیاي طبیعی بعنوان توانایی فرد براي بقا در محیط تعبیر می شود. با تعیین مقادیر شایستگی هر عضو، می توان آنها را با احتمالی متناسب با شایستگی نسبی آنها از میان جمعیت انتخاب کرد. افراد انتخاب شده با استفاده از عملگر ژنتیکی پیوند3 - تبادل - 4 با یکدیگر ترکیب شده فرزندانی را براي ایجاد نسل بعدي تولید میکنند.
عملگر پیوند که مهمترین عملگر تولید مثل بشمار می آید براي تبادل اطلاعات ژنتیکی بین یک جفت از افراد استفاده می شود. ساده ترین نوع تبادل، تبادل یک نقطه اي است اگرچه روشهاي دیگر نیز قابل استفاده هستند. در عمل تبادل یک نقطه اي، دو عضو انتخابی به عنوان والدین در نظر گرفته میشوند. سپس نقطه اي به صورت تصادفی در طول کروموزومهاي آنها انتخاب شده، اطلاعات ژنتیکی والدین در دو طرف این نقطه با یکدیگر تعویض می شوند.
بدین ترتیب از ترکیب آنها یک یا دو کروموزوم فرزند تولید میشودمثلاً. از ترکیب دو کروموزوم 11001011و 11011111کروموزوم فرزند 11001111تولید می شود. عملگر تبادللزوماً بر روي هر فرد در جمعیت اجرا نمیشود، بلکه با احتمالی که از قبل برابر با Pc در نظر گرفته شده است بر روي زوج هاي انتخاب شده براي جفت شدن انجام می شود. نتیجه این عمل تولید فرزندانی است که اطلاعات ژنتیکی خود را از والدین خود به ارث برده اند.
سپس عملگر ژنتیکی دیگري به نام جهش1 با احتمال Pm بر روي کروموزوم هاي تازه تولید شده اجرا می شود. عملگر جهش باعث می شود نمایش ژنتیکی یک عضو تغییر کند. در نمایش دودویی یک کروموزوم، این عملگر سبب خواهد شد یک بیت که به صورت تصادفی انتخاب شده از 0به 1 یا از 1 به 0تغییر مقدار دهدمثلاً. کروموزوم 11001010 به 10001010تغییر پیدا می کند. عملگر جهش به عنوان روشی براي اطمینان یافتن از اینکه احتمال جستجو یک زیرفضاي خاص از فضاي مسأله هرگز صفر نیست استفاده میشود.
بعد از عمل پیوند و جهش، اعضا بر حسب تابع هدف ارزیابی شده مقدار شایستگی هر عضو تعیین می شود. سپس افراد برحسب مقدار شایستگی شان براي جفت شدن انتخاب می شوند. این فرایند در طول نسل هاي بعدي ادامه می یابد. به این ترتیب انتظار می رود متوسط شایستگی اعضا در جمعیت افزایش یابد. عضوهاي شایسته تر بیشتر در فرایند تولید مثل شرکت کرده و افراد با شایستگی کمتر از بین می روند.
الگوریتم پس از تولید تعداد معینی از نسل ها یا وقتی نقطه خاصی در فضاي جستجو ملاحظه شود خاتمه می یابد. شکل 1 الگوریتم GA را نشان می دهد. در این شکل generation متغیر حلقه و Generation حداکثر تعداد نسل ها را نشان می دهد. الگوریتم به صورت تکراري براي ده ها یا صدها نسل اجرا می شود. قبل از اجراي الگوریتم ضروري است فضاي جستجو رمزگذاري شده، مقادیر پارامترهاي لازم از قبیل اندازه جمعیت - pop-size - و نرخ هاي تبادل - Pc - و جهش - Pm - تعیین شوند.
