جعبه ابزار الگوريتم ژنتيک

نویسنده: مهندس محمد كريمي مريداني دانشجوي دكتري مهندسي پزشكي (بيوالكتريك)، دانشگاه آزاد اسلامي واحد علوم و تحقيقات

Karimi_bme@yahoo.com

الگوريتم ژنتيک روشي براي حل مسائل بهينه سازي است. اين الگوريتم بارها يک جمعيت را از راه حل‌هاي منفرد تغيير مي‌دهد که اين تغييرات به عنوان تکامل تعريف مي‌شود. در هر گام از اين تکامل دو عضو به عنوان جمعيت جديد به طور تصادفي به عنوان والدين انتخاب مي‌شود و فرزندان آن‌ها به عنوان نسل بعدي در نظر گرفته مي‌شود. با اين ساختار جمعيت به سمت يک راه حل بهينه تکامل مي‌يابد. بنابراين با استفاده از الگوريتم ژنتيک مي‌توان بسياري از مسائلي که نياز به بهينه سازي داشته ولي با الگوريتم‌هاي استاندارد حل نمي شود، بهينه کرد. توابع هدفي را که ناپيوسته، غير قابل شناسايي، تصادفي يا غيرخطي هستند مي‌توان با الگوريتم ژنتيک بهينه کرد. الگوريتم ژنتيک از سه گروه قانون اصلي براي توليد نسل بعد از نسل حال استفاده مي‌کند.

قوانين انتخاب (Selection)
از اين قانون براي انتخاب افرادي که بايد در نسل بعد برگزيده شوند استفاده مي‌شود.

قوانين ترکيب (Cross over)
براي ترکيب والدين و توليد فرزندان نسل بعد از اين قانون استفاده مي‌شود.

قوانين جهش (Mutation)
اين قانون يک تغيير تصادفي را بر روي جمعيت حاضر ايجاد مي‌کند و يک جمعيت جديد توليد مي‌کند.
به منظور کار با جعبه ابزار الگوريتم ژنتيک در MATLAB بايد با برخي اصطلاحات پرکاربرد آشنا شد که در ادامه به معرفي آن‌ها مي‌پردازيم.

تابع شايستگي
تابع شايستگي، تابعي است که با اين هدف تعريف مي‌شود که بايد به مقدار مطلوب يا بهينه نزديک شود. معمولا به دست آوردن مينيمم در اين تابع نقطه بهينه محسوب مي‌شود. اين تابع بايد به صورت يک mfile نوشته و ذخيره شود.

افراد
نقاطي که به تابع شايستگي اعمال مي‌شود تحت عنوان افراد معرفي مي‌شود. در حالت کلي افراد را genome و بردار افراد را gen تعريف مي‌کنند.

جمعيت و نسل
به آرايه اي از افراد جمعيت گفته مي‌شود. هر فرد مي‌تواند در سطح‌هاي متفاوت از آرايه جمعيت تکرار شود.

مقدار تابع شايستگي و بهترين مقدار تابع شايستگي
مقدار تابع شايستگي به ازاي هر فرد محاسبه شده و امتياز آن فرد محسوب مي‌شود. بديهي است چون الگوريتم ژنتيک به دنبال مينيمم کردن تابع است، کمترين مقدار تابع شايستگي، بهترين مقدار تابع شايستگي است.

پراکندگي
پراکندگي به ميانگين فاصله افراد در هر جمعيت اطلاق مي‌شود. ميانگين فاصله در صورتي که پراکندگي جمعيت زياد باشد بيشتر از زماني است که پراکندگي کم است. شکل (1) دو جمعيت با پراکندگي زياد و کم را نشان مي‌دهد.

والدين و فرزندان
الگوريتم ژنتيک به منظور ايجاد نسل بعد، تعدادي از افراد را به عنوان والدين انتخاب مي‌کند. به افراد نسل بعد که توسط والدين توليد مي‌شوند فرزندان گفته مي‌شود.

چگونگي عملکرد الگوريتم ژنتيک
ابتدا الگوريتم با انتخاب يک جمعيت اوليه تصادفي شروع به کار مي‌کند. سپس الگوريتم از نسل حاضر تعدادي افراد براي توليد نسل بعدي انتخاب مي‌کند. الگوريتم براي توليد نسل جديد مقدار تابع شايستگي هر فرد را محاسبه مي‌کند و به هر عضو از جمعيت يک امتياز اختصاص مي‌دهد. پس از نرماليزه کردن مقادير تابع شايستگي، والدين با توجه به بالاترين امتياز و مقدار شايستگي اختصاص داده شده، انتخاب مي‌شوند. در ادامه فرزندان توسط قانون جهش يا ترکيب توليد مي‌شوند و جمعيت کنوني با فرزندان جديد جايگزين و نسل جديد را تشکيل مي‌دهند. اين روند تا زماني که شرط توقف در نظر گرفته شده اجرا نشود ادامه دارد.
به منظور استفاده از الگوريتم ژنتيک در محيط MATLAB مي‌توانيد از دو روش استفاده کنيد:
• استفاده از رابطه گرافيکي الگوريتم ژنتيک
• فراخواني توابع الگوريتم ژنتيک در پنجره دستورات MATLAB

استفاده از رابطه گرافيکي الگوريتم ژنتيک

رابطه گرافيکي الگوريتم ژنتيک اين امکان را به کاربر مي‌دهد که بدون نوشتن هر گونه برنامه و کدي در محيط MATLAB از ابزارهاي موجود در جعبه ابزار الگوريتم ژنتيک استفاده کرد.
براي دسترسي به اين رابطه گرافيکي مي‌توانيد دستور gatool را در محيط Command تايپ کنيد. با انجام اين کار پنجره اي به صورت شکل (1) باز مي‌شود.

همان‌طور که از شکل (2) مشخص است، براي استفاده از اين محيط بايد اطلاعات نشان داده شده در پنجره الگوريتم ژنتيک را با توجه به مسئله مورد نظر وارد کنيد.
الف- تابع شايستگي (Fitness Function)
تابع شايستگي تابعي است که به دنبال مينيمم کردن آن هستيم. تابع شايستگي بايد به فرم fitnessfun @ در کادر مربوطه نوشته شود. fitnessfun.m يک mfile است که تابع شايستگي را محاسبه مي‌کند. اين برنامه بايد قبلاً  با پسوند m. نوشته و ذخيره شده باشد و در اين قسمت فراخواني شود. علامت @ به منظور انتقال اين mfile در نظر گرفته مي‌شود.
ب- تعداد متغيرها (number of variable) 

اندازه بردار ورودي به تابع شايستگي را مشخص مي‌کند.
شکل (3) نحوه وارد کردن عبارات مورد نظر را نشان مي‌دهد. شما مي‌توانيد برنامه تابع شايستگي را به هر اسم دلخواه ذخيره کنيد ولي توجه داشته باشيد بايد در قسمت Fitness Function همان اسم ذخيره شده را که در ابتداي آن@ قرار داده ايد تايپ کنيد.
ادامه آموزش مربوط به جعبه ابزار الگوريتم ژنتيک در شماره‌هاي آينده توضيح داده خواهد شد.

منبع
www.iran-eng.com