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