amir6708
۴ اردیبهشت ۱۳۸۸, ۰۳:۱۸
الگوریتم ژنتیک ( GA ):
الگوریتم ژنتیک ( GA ) روش جستجوی تصادفی سراسری است که از فرآیندهای سیر تکاملی طبیعی تقلید می کند . الگوریتم ژنتیک بدون هیچ دانشی از راه حل صحیح و کاملاً وابسته به پاسخ هایی که از محیطش و عملگرهای تکاملی ( به عنوان مثال تکثیر ، همبری و جهش ) داده می شود، برای رسیدن به بهترین راه حل، شروع می کند. با شروع از چندین نقطه مستقل و جستجو به صورت موازی ، الگوریتم ژنتیک از نقاط مینیمم محلی دور شده و به بهینه سراسری همگرا می شود. الگوریتم های ژنتیک ، همان طور که نشان داده شده اند، در تعیین ناحیه های با عملکرد بالا در کل دامنه، بدون وابستگی به ابعاد بزرگ دامنه آزمایش، توانمند هستند.
یک الگوریتم ژنتیک اصولاً با یک جمعیت تصادفی که شامل 200-100 فرد است ، مقدار دهی می شود. این جمعیت (حوضچه ازدواج ) معمولاً بصورت یک عدد با ارزش حقیقی یا یک رشته باینری است که کروموزوم نامیده می شود. و به ترتیب نماینده ی الگوریتم ژنتیک باینری و الگوریتم ژنتیک حقیقی است. در ادامه این قسمت هر کروموزوم را بصورت یک رشته باینری در نظر می گیریم. میزان چگونگی عملکرد یک فرد جمعیت، به وسیله تابع هدف ارزیابی می شود. تابع هدف متناظر با هر فرد، یک عدد است که شایستگی فرد نامیده می شود. شایستگی هر کروموزوم محاسبه شده و تکنیک های برازندگی اجرا می شود. سه قسمت اصلی یک الگوریتم ژنتیک با عناوین تولید مثل(تکثیر) ، همبری و جهش شناخته می شنود.
شکل ۱. نمایی از الگوریتم ژنتیک
تولید نسل ( Reproduction ):
هنگام تولید نسل ، مقدار شایستگی هر کروموزوم محاسبه می شود که این مقدار در فرآیند انتخاب برای مشخص کردن افراد شایسته تر استفاده می شود. همانند سیر تکامل طبیعی ، کروموزوم شایسته احتمال بالاتری برای انتخاب شدن در تولید نسل دارد.
یک نوع روش معمول انتخاب ، روش انتخاب چرخ گردان است. شکل 1 به هر فرد در این جمعیت قسمتی از چرخ گردان را اختصاص داده است که اندازه آن متناسب با شایستگی فرد است. یک نشان گر وجود دارد که پس از آنکه چرخ گردان را چرخاندیم ، فردی که نشان گر به آن اشاره می کند، انتخاب می شود. این روند تا کامل شدن معیار انتخاب ( که معمولاً انتخاب تعداد مشخص فرد از جمعیت است ) ادامه پیدا می کند. احتمال آنکه هر فرد انتخاب شود به شایستگی اش وابسته است. و تضمین می کند افراد شایسته تر تمایل بیشتری برای تولید فرزند دارند.
چند رشته یکسان ممکن است برای تولید نسل انتخاب شده و رشته های شایسته تر غالب ( حکم فرما ) می شوند. اگر چه برای حالت نشان داده شده در شکل 1 نا محتمل نیست، رشته ضعیف (01001) در فرآیند انتخاب به عنوان غالب باشد.
شکل ۲. نمایی از چرخ گردان
روش های انتخاب دیگری وجود دارد و با توجه به استفاده می توان برای هر فرآیند مناسب ترین را انتخاب کرد. همه روش های انتخاب بر اساس یک اصل مشابه عمل می کنند یعنی دادن احتمال انتخاب بالاتر به کروموزوم شایسته تر.
چهار روش معمول برای انتخاب بصورت زیر است:
1. چرخ گردان (Roulette wheel)
2. نمونه برداری سراسری تصادفی (SUS)
3. انتخاب هندسی نرمال شده
4. انتخاب تورنمنتی
همبری CROSSOVER:
زمانی که فرآیند انتخاب کامل شد ، الگوریتم همبری آغاز می شود. عملگر همبری قسمت های معینی از دو رشته انتخاب شده را برای حفظ خوب کروموزوم قبلی و خلق کردن نمونه های تازه بهتر، معاوضه می کند. عمگرهای ژنتیک، پارامترهای یک کروموزوم را مستقیماً با استفاده از فرض معین بودن که درون هر فرد با مهارت بدست می آورند بطوری که بطور میانگین افراد شایسته تر تولید می شوند. احتمال همبری نشان می دهد که همبری چگونه عمل می کند.
احتمال 0% یعنی که فرزندان درست شبیه والدینشان هستند و احتمال 100% یعنی که هر تولید نسل کاملاً از فرزندان جدید تشکیل شده است. ساده ترین روش همبری، همبری تک نقطه ای است. عملگر همبری تک نقطه ای 2 مرحله دارد:
1. تعدادی از رشته های تازه تولید شده در حوضچه ازدواج به طور تصادفی جفت می شوند( تزویج می کنند.)
2. هر جفت از رشته ها بصورت زیر همبری را انجام می دهند:
یک عدد صحیح K تصادفاً بین 1 و یک واحد کمتر از طول رشته [1,L-1] انتخاب می شود. مبادله ی همه ی بیت ها بین نقطه های K-1 و L دو رشته کاملاً جدید به وجود می آورد.
بطور مثال: اگر رشته های 10000 و 01110 برای همبری انتخاب شوند و مقدار K به طور تصادفی 3 تعیین شود، رشته های جدیدی که به وجود خواهند آمد 10010 و 01100 است.
جهش(Mutation):
استفاده از انتخاب و همبری به نوبه ی خود تعداد زیادی رشته های مختلف تولید می کنند؛ هر چند که دو مشکل اصلی وجود دارد:
1. جمعیت اولیه انتخاب شده ممکن است تنوع کافی در رشته های اولیه را برای اطمینان یافتن از جستجو GA در کل فضای مسئله فراهم نکند.
2. GA ممکن است به سمت رشته های بهینه همگرا شود که ناشی از انتخاب بد جمعیت اولیه است.
این مشکلات به وسیله ی معرفی عملگر جهش در GA حل خواهد شد.
جهش تغییر مقدار یک بیت در یک رشته در یک مکان تصادفی است ، که یک عملگر مهم در الگوریتم ژنتیک به حساب می آید. احتمال جهش معمولاً کم است زیرا یک نرخ بالای جهش ، رشته شایسته را خراب و الگوریتم ژنتیک را به عنوان یک جستجوی رندم، تباه می کند. احتمال جهش به طور معمول حول و حوش %1/0 یا %01/0 است. این مقادیر نشان دهنده احتمال انتخاب یک رشته معین برای جهش است. به عنوان مثال برای احتمال %1/0 یک رشته در هزار رشته برای جهش انتخاب خواهد شد.
هنگامی که یک رشته برای جهش انتخاب می شود، بطور تصادفی یک عنصر از رشته تغییر می کند یا جهش می یابد. بطور مثال: اگر مکان بیت انتخاب شده برای جهش در رشته باینری 10000 ، 4 باشد ، نتیجه جهش 10010 خواهد شد .
الگوریتم ژنتیک ( GA ) روش جستجوی تصادفی سراسری است که از فرآیندهای سیر تکاملی طبیعی تقلید می کند . الگوریتم ژنتیک بدون هیچ دانشی از راه حل صحیح و کاملاً وابسته به پاسخ هایی که از محیطش و عملگرهای تکاملی ( به عنوان مثال تکثیر ، همبری و جهش ) داده می شود، برای رسیدن به بهترین راه حل، شروع می کند. با شروع از چندین نقطه مستقل و جستجو به صورت موازی ، الگوریتم ژنتیک از نقاط مینیمم محلی دور شده و به بهینه سراسری همگرا می شود. الگوریتم های ژنتیک ، همان طور که نشان داده شده اند، در تعیین ناحیه های با عملکرد بالا در کل دامنه، بدون وابستگی به ابعاد بزرگ دامنه آزمایش، توانمند هستند.
یک الگوریتم ژنتیک اصولاً با یک جمعیت تصادفی که شامل 200-100 فرد است ، مقدار دهی می شود. این جمعیت (حوضچه ازدواج ) معمولاً بصورت یک عدد با ارزش حقیقی یا یک رشته باینری است که کروموزوم نامیده می شود. و به ترتیب نماینده ی الگوریتم ژنتیک باینری و الگوریتم ژنتیک حقیقی است. در ادامه این قسمت هر کروموزوم را بصورت یک رشته باینری در نظر می گیریم. میزان چگونگی عملکرد یک فرد جمعیت، به وسیله تابع هدف ارزیابی می شود. تابع هدف متناظر با هر فرد، یک عدد است که شایستگی فرد نامیده می شود. شایستگی هر کروموزوم محاسبه شده و تکنیک های برازندگی اجرا می شود. سه قسمت اصلی یک الگوریتم ژنتیک با عناوین تولید مثل(تکثیر) ، همبری و جهش شناخته می شنود.
شکل ۱. نمایی از الگوریتم ژنتیک
تولید نسل ( Reproduction ):
هنگام تولید نسل ، مقدار شایستگی هر کروموزوم محاسبه می شود که این مقدار در فرآیند انتخاب برای مشخص کردن افراد شایسته تر استفاده می شود. همانند سیر تکامل طبیعی ، کروموزوم شایسته احتمال بالاتری برای انتخاب شدن در تولید نسل دارد.
یک نوع روش معمول انتخاب ، روش انتخاب چرخ گردان است. شکل 1 به هر فرد در این جمعیت قسمتی از چرخ گردان را اختصاص داده است که اندازه آن متناسب با شایستگی فرد است. یک نشان گر وجود دارد که پس از آنکه چرخ گردان را چرخاندیم ، فردی که نشان گر به آن اشاره می کند، انتخاب می شود. این روند تا کامل شدن معیار انتخاب ( که معمولاً انتخاب تعداد مشخص فرد از جمعیت است ) ادامه پیدا می کند. احتمال آنکه هر فرد انتخاب شود به شایستگی اش وابسته است. و تضمین می کند افراد شایسته تر تمایل بیشتری برای تولید فرزند دارند.
چند رشته یکسان ممکن است برای تولید نسل انتخاب شده و رشته های شایسته تر غالب ( حکم فرما ) می شوند. اگر چه برای حالت نشان داده شده در شکل 1 نا محتمل نیست، رشته ضعیف (01001) در فرآیند انتخاب به عنوان غالب باشد.
شکل ۲. نمایی از چرخ گردان
روش های انتخاب دیگری وجود دارد و با توجه به استفاده می توان برای هر فرآیند مناسب ترین را انتخاب کرد. همه روش های انتخاب بر اساس یک اصل مشابه عمل می کنند یعنی دادن احتمال انتخاب بالاتر به کروموزوم شایسته تر.
چهار روش معمول برای انتخاب بصورت زیر است:
1. چرخ گردان (Roulette wheel)
2. نمونه برداری سراسری تصادفی (SUS)
3. انتخاب هندسی نرمال شده
4. انتخاب تورنمنتی
همبری CROSSOVER:
زمانی که فرآیند انتخاب کامل شد ، الگوریتم همبری آغاز می شود. عملگر همبری قسمت های معینی از دو رشته انتخاب شده را برای حفظ خوب کروموزوم قبلی و خلق کردن نمونه های تازه بهتر، معاوضه می کند. عمگرهای ژنتیک، پارامترهای یک کروموزوم را مستقیماً با استفاده از فرض معین بودن که درون هر فرد با مهارت بدست می آورند بطوری که بطور میانگین افراد شایسته تر تولید می شوند. احتمال همبری نشان می دهد که همبری چگونه عمل می کند.
احتمال 0% یعنی که فرزندان درست شبیه والدینشان هستند و احتمال 100% یعنی که هر تولید نسل کاملاً از فرزندان جدید تشکیل شده است. ساده ترین روش همبری، همبری تک نقطه ای است. عملگر همبری تک نقطه ای 2 مرحله دارد:
1. تعدادی از رشته های تازه تولید شده در حوضچه ازدواج به طور تصادفی جفت می شوند( تزویج می کنند.)
2. هر جفت از رشته ها بصورت زیر همبری را انجام می دهند:
یک عدد صحیح K تصادفاً بین 1 و یک واحد کمتر از طول رشته [1,L-1] انتخاب می شود. مبادله ی همه ی بیت ها بین نقطه های K-1 و L دو رشته کاملاً جدید به وجود می آورد.
بطور مثال: اگر رشته های 10000 و 01110 برای همبری انتخاب شوند و مقدار K به طور تصادفی 3 تعیین شود، رشته های جدیدی که به وجود خواهند آمد 10010 و 01100 است.
جهش(Mutation):
استفاده از انتخاب و همبری به نوبه ی خود تعداد زیادی رشته های مختلف تولید می کنند؛ هر چند که دو مشکل اصلی وجود دارد:
1. جمعیت اولیه انتخاب شده ممکن است تنوع کافی در رشته های اولیه را برای اطمینان یافتن از جستجو GA در کل فضای مسئله فراهم نکند.
2. GA ممکن است به سمت رشته های بهینه همگرا شود که ناشی از انتخاب بد جمعیت اولیه است.
این مشکلات به وسیله ی معرفی عملگر جهش در GA حل خواهد شد.
جهش تغییر مقدار یک بیت در یک رشته در یک مکان تصادفی است ، که یک عملگر مهم در الگوریتم ژنتیک به حساب می آید. احتمال جهش معمولاً کم است زیرا یک نرخ بالای جهش ، رشته شایسته را خراب و الگوریتم ژنتیک را به عنوان یک جستجوی رندم، تباه می کند. احتمال جهش به طور معمول حول و حوش %1/0 یا %01/0 است. این مقادیر نشان دهنده احتمال انتخاب یک رشته معین برای جهش است. به عنوان مثال برای احتمال %1/0 یک رشته در هزار رشته برای جهش انتخاب خواهد شد.
هنگامی که یک رشته برای جهش انتخاب می شود، بطور تصادفی یک عنصر از رشته تغییر می کند یا جهش می یابد. بطور مثال: اگر مکان بیت انتخاب شده برای جهش در رشته باینری 10000 ، 4 باشد ، نتیجه جهش 10010 خواهد شد .