تبلیغات
مهندسی مکانیک و هوافضا - مطالب الگوریتم ژنتیک
منوی اصلی
مهندسی مکانیک و هوافضا
هر آنچه که یک مهندس بخواهد اینجا هست!
  • حسین اتحادی یکشنبه 20 دی 1394 07:30 ب.ظ نظرات ()
    با سلام
    جهش یک عملگر ژنتیکی است که معمولا برای حفظ تنوع ژنتیکی (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 مرتبه) بالاخره از این قله محلی فرار می کنیم بنابراین نرخ جهش را نباید بزرگ انتخاب کنیم.


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

    موفق باشید
    آخرین ویرایش: پنجشنبه 24 دی 1394 12:40 ق.ظ
    ارسال دیدگاه
  • حسین اتحادی دوشنبه 7 دی 1394 12:58 ق.ظ نظرات ()

    در دهه  ۱۹۶۰ و ۱۹۷۰ جان هالند الگوریتم ژنتیک یا Genetic algorithm را ارایه کرد و یکی از شاگردان وی به نام گلدبرگ تمامی کارهای جان هالند را گردآوری و در کتاب منتشر ساخت. الگوریتم ژنتیک الگوریتمی برای بهینه سازی است و مبتنی بر جمعیت می باشد در این الگوریتم که بر مبنای علم ژنتیک می باشد اعضای جمعیت رشد کرده و بهبود می یابند تا به جوابی بهینه دست یابند.

    تعاریف خاصی در الگوریتم ژنتیک وجود دارد:

    ۱- کروموزم : برای تبدیل هر جواب به یک جواب کدینگ شده از کروموزم استفاده می شود.

    ۲- ژن : عناصر تشکیل دهنده یک کروموزم را ژن می گویند.

    ۳- جمعیت: مجموعه ای از کروموزم ها را جمعیت می گویند.

    ۴- نسل : هر تکرار از الگوریتم را نسل می گویند.

    در الگوریتم ژنتیک انواع مختلفی از کدینگ وجود دارد به طور مثال کدینگ باینری که زن های درون یک کروموزم تنها اعداد صفر یا یک را به خود می گیرند. کدینگ عدد صحیح که ژن های درون یک کروموزم تنها اعداد صحیح را به خود می گیرند و همچنین کدینگ پیوسته که ژن های درون کروموزم می توانند هر عددی را به صورت صحیح یا اعشاری به خود بگیرند.

    برای کدینگ باینری می توان از عملگر جهشی mutation استفاده نمود بدین صورت که یک ژن انتخاب شده و مقدار آن اگر صفر است به یک و اگر یک است به صفر تغییر یابد. همچنین برای عملگر تقاطع می توان از عملگر تقاطع تک نقطه ایOne point crossover، عملگر تقاطع دو نقطه ای و یا عملگر تقاطع چند نقطه ای استفاده نمود.

    کد الگوریتم ژنتیک

    برای کدینگ به صورت عدد صحیح می توان از عملگر های زیر استفاده نمود:

    swap

    insertion

    scramble

    برای انتخاب والدین در الگوریتم ژنتیک می توان از روش های چون چرخ رولت Roulette wheel selection یا روش انتخاب تورنمنت Tournament selection استفاده نمود.

    مراحل الگوریتم ژنتیک به صورت زیر می باشد:

    * ایجاد جمعیت اولیه و ارزیابی آن ها

    * از یک عملگر انتخاب برای انتخاب والدین استفاده می شود

    * اعمال تقاطع بر روی والدین و ایجاد فرزندان

    * ایجاد جهش بر روی والدین و ایجاد فرزندان

    * ارزیابی کل جمعیت اصلی و جمعیت فرزندان و انتخاب از بین آن ها به تعداد جمعیت اصلی

    * تکرار تا رسیدن به شرط خاتمه

     

    آخرین ویرایش: دوشنبه 7 دی 1394 01:05 ق.ظ
    ارسال دیدگاه
  • حسین اتحادی پنجشنبه 19 آذر 1394 11:02 ب.ظ نظرات ()
    جعبه‌ ابزار الگوریتم ژنتیك مجموعه‌ای از تابع‌هایی هستند كه توانایی اپیتیمم كردن را با استفاده از محیط محاسبات عددی دارد. این الگوریتم قابلیت حل مسائل مختلف در زمینه بهینه‌سازی است تمام توابع این جعبه ابزار از M فایل‌های مطلب هستند كه تابع را بهینه می‌كند.البته می‌‌توانید قابلیت‌های الگوریتم ژنتیك را توسط M فایلی كه خودتان می‌نویسید یا با تركیب تابع‌های مطلب افزایش دهید.

    نوشتن ‌M فایل

    در این قسمت نشان می دهیم كه چه‌طور می‌توان یك M فایل برای تابع نوشت كه می‌خواهیم آن را بهینه كنیم فرض كنیم می‌خواهیم تابع زیر را بهینه كنیم.

     

    y1

    مراحل زیر را انجام دهید .

    ... ادامه مطلب 

    آخرین ویرایش: پنجشنبه 19 آذر 1394 11:07 ب.ظ
    ارسال دیدگاه
  • حسین اتحادی پنجشنبه 19 آذر 1394 05:14 ب.ظ نظرات ()


     

    وبسایت الگوریتم رقابت استعماری، مطلب جالبی با عنوان “استراتژی حل مسائل بهینه سازی با استفاده از الگوریتم رقابت استعماری” منتشر کرده است. با توجه به اهمیت و جذابیت این موضوع برای مخاطبین متلب سایت بر آن دیدیم تا این پست را بر روی سایت نیز قرار دهیم. با کلیک بر روی ادامه مطلب می توانید، این پست وبسایت الگوریتم رقابت استعماری را مطالعه نمایید.

     


    وبسایت الگوریتم رقابت استعماریدر بسیاری از موارد دوستان زیادی این سوال را مطرح کردند که چگونه باید الگوریتم رقابت استعماری را به مسئله بهینه سازی خود اعمال کنند. در حقیقت، برای حل یک مسئله بهینه سازی، باید تعریف دقیقی از خود مسئله و متغیرها و اهداف بهینه سازی به عمل آید. در این بخش می خواهیم استراتژی حل یک مسئله بهینه سازی را گام به گام بیان کنیم. توضیحات ارائه شده کاملاً عمومی خواهند بود و نه تنها برای استفاده از الگوریتم رقابت استعماری، بلکه برای حل مسائل بهینه سازی با استفاده از هر الگوریتمی مفید خواهند بود.

     

     

    استراتژی حل مسائل بهینه سازی را گام به گام با بیان تعاریف زیر و پاسخ به سوالات رایج در این مورد ارائه می کنیم.

    ۱) بهینه سازی چیست؟

    بهینه‌سازی، تغییر دادن ورودی‌ها و خصوصیات یک دستگاه، فرایند ریاضی و یا آزمایش تجربی است، به نحوی که بهترین خروجی یا نتیجه به دست بیاید (شکل زیر). ورودی‌ها، متغیرهای فرایند یا تابع مورد بررسی هستند که با نام‌های تابع هدف (Objective Function)، تابع هزینه (Cost Function) و یا تابع برازندگی (Fitness Function) نامیده می‌شود. خروجی‌ نیز به صورت هزینه، سود و یا برازندگی تعریف می‌شود. غالب مسائل بهینه‌سازی به صورت کمینه‌سازی مقدار یک تابع هزینه در نظر گرفته شده‌اند. به راحتی می‌توان نشان داد که هر نوع مسأله‌ی بهینه‌سازی را می‌توان در قالب یک مسأله‌ی کمینه‌سازی تعریف نمود.



    شکل: فرایند یا تابعی که بهینه‌سازی می‌شود. در بهینه‌سازی ورودی‌ها یا متغیرها به نحوی تغییر داده می‌شوند که خروجی مطلوب به دست بیاید.
    آخرین ویرایش: پنجشنبه 19 آذر 1394 05:15 ب.ظ
    ارسال دیدگاه