نرخ جهش در الگوریتم ژنتیک - Artificial Intelligence

shama · ۰۲-۱۵-۱۳۹۲, ۰۵:۳۹ بعد از ظهر

سلام کسی میتونه توضیح بده که نرخ جهش تو الگوریتم یعنی چی؟جهش رو همه ی کروموزوم های حاصل از ترکیب اعمال میشه ؟برای اعمال عملگر ترکیب آیا همه کروموزوم هایی که تو چرخ رولت انتخاب میشن ترکیب میشن یا شرایطی داره ؟ممنون میشم اگه زودتر جواب بدین

**babak_1234** · ۰۲-۱۵-۱۳۹۲, ۰۸:۴۳ بعد از ظهر

نقل قول:

نوشته اصلي بوسيله shama

سلام کسی میتونه توضیح بده که نرخ جهش تو الگوریتم یعنی چی؟جهش رو همه ی کروموزوم های حاصل از ترکیب اعمال میشه ؟برای اعمال عملگر ترکیب آیا همه کروموزوم هایی که تو چرخ رولت انتخاب میشن ترکیب میشن یا شرایطی داره ؟ممنون میشم اگه زودتر جواب بدین

سلام دوست من

نرخ جهش میزان تغییراتی که توسط عملگر جهش بر روی کروموزوم اعمال میشه رو تعیین میکنه.
استراتژی های مختلفی برای تعیین کردن این پارامتر وجود داره اما در اکثر موارد این مقدار ۲۰٪ تعیین میشه. گاهی هم در ابتدای اجرای الگوریتم این مقدار زیاد هست و در طول اجرا کمتر میشه تا فضای جستجو خیلی جا به جا نشه.
عملگر جهش روی همه کروموزوم ها اعمال نمیشه و فقط ۲۰٪ اونها شامل جهش میشن. البته من دیدم که در برخی موارد با احتمال ۲۰٪ روی یک کروموزوم اعمال میشه.

موفق باشی

**raha_hakhamanesh** · ۰۲-۱۵-۱۳۹۲, ۱۰:۱۴ بعد از ظهر

نقل قول:

نوشته اصلي بوسيله shama

سلام کسی میتونه توضیح بده که نرخ جهش تو الگوریتم یعنی چی؟جهش رو همه ی کروموزوم های حاصل از ترکیب اعمال میشه ؟برای اعمال عملگر ترکیب آیا همه کروموزوم هایی که تو چرخ رولت انتخاب میشن ترکیب میشن یا شرایطی داره ؟ممنون میشم اگه زودتر جواب بدین

با سلام
جهش یک عملگر ژنتیکی است که معمولا برای حفظ تنوع ژنتیکی (Genetic diversity) مورد استفاده قرار می گیرد.
جهش مقدار یک یا چند ژن از کروموزوم را تغییر می دهد. (Mutation alters one or more gene values in a chromosome from its initial state)
نرخ جهش یعنی چه تعدادی (چند درصد) از ژن های یک کروموزوم تغییر می یابند و مسلما یک پارامتر آماری است یعنی وقتی می گوییم نرخ جهش 2% است یعنی از هر 100 ژن توقع داریم 2 ژن تغییر وضعیت داده باشند اما این کاملا به احتمال رخدادن آن 2% ربط دارد و لذا ممکن است حتی 3 ژن یا بیشتر، یا کمتر از 2 ژن تغییر وضعیت داده شود اما وقتی تعداد ژن ها به سمت بینهایت میل کنند مسلما این مقدار هم به سمت عدد 2 میل می کند. (بطور کلی یک پدیده احتمالی است نه قطعی)

اما اینکه نرخ جهش چقدر باشد، باید بگویم بر خلاف نظر دوستم بابک، توصیه می شود نرخ جهش بزرگ نباشد اگر چه این موضوع می تواند بسته به نوع مسئله تفاوت بکند ولی معمولا نرخ جهش عددی کوچکتر از 2% و حتی 1.5% درنظر گرفته می شود؛ دلیل آن هم کاملا مشخص است فرض کنید

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

هنگام ترکیب، همه کروموزوم ها ترکیب می شوند ولی در مرحله نخبه گرائی تعدادی (و نه همه) کروموزم ها بعنوان نخبه انتخاب می شوند.

موفق باشید

رجوع شود به: Multiobjective Genetic Algorithms for Clustering: Applications in Data Mining and Bioinformatics, 2011؛ صفحه 30

shama · ۰۲-۱۶-۱۳۹۲, ۰۸:۴۳ بعد از ظهر

نقل قول:

نوشته اصلي بوسيله raha_hakhamanesh

با سلام
جهش یک عملگر ژنتیکی است که معمولا برای حفظ تنوع ژنتیکی (genetic diversity) مورد استفاده قرار می گیرد.
جهش مقدار یک یا چند ژن از کروموزوم را تغییر می دهد. (mutation alters one or more gene values in a chromosome from its initial state)
نرخ جهش یعنی چه تعدادی (چند درصد) از ژن های یک کروموزوم تغییر می یابند و مسلما یک پارامتر آماری است یعنی وقتی می گوییم نرخ جهش 2% است یعنی از هر 100 ژن توقع داریم 2 ژن تغییر وضعیت داده باشند اما این کاملا به احتمال رخدادن آن 2% ربط دارد و لذا ممکن است حتی 3 ژن یا بیشتر، یا کمتر از 2 ژن تغییر وضعیت داده شود اما وقتی تعداد ژن ها به سمت بینهایت میل کنند مسلما این مقدار هم به سمت عدد 2 میل می کند. (بطور کلی یک پدیده احتمالی است نه قطعی)

اما اینکه نرخ جهش چقدر باشد، باید بگویم بر خلاف نظر دوستم بابک، توصیه می شود نرخ جهش بزرگ نباشد اگر چه این موضوع می تواند بسته به نوع مسئله تفاوت بکند ولی معمولا نرخ جهش عددی کوچکتر از 2% و حتی 1.5% درنظر گرفته می شود؛ دلیل آن هم کاملا مشخص است فرض کنید

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

هنگام ترکیب، همه کروموزوم ها ترکیب می شوند ولی در مرحله نخبه گرائی تعدادی (و نه همه) کروموزم ها بعنوان نخبه انتخاب می شوند.

موفق باشید

رجوع شود به: Multiobjective genetic algorithms for clustering: Applications in data mining and bioinformatics, 2011؛ صفحه 30

ممنون از پاسختون. پس همون طور که آقای بابک گفتن جهش روی همه ی فرزندان تولید شده اعمال نمیشه؟

aaavvv · ۰۵-۲۹-۱۳۹۲, ۰۲:۲۲ قبل از ظهر

با سلام
الگوریتم ژنتیک در طبیعت را در نظر بگیرید. هر ژن در موجود زنده، ممکن است از اجداد قبلی آن باشد ولی برای فرزندان (این موجود زنده) ممکن است جهش ژنتیکی اتفاق بیفتد نه برای اجداد آن. پس اگر موجود زنده را نخبه ها در نظر بگیریم عملگر ترکیب روی همه کروموزوم ها انجام می شود ولی جهش روی کروموزوم های نخبه