پاورپوینت بهینه سازی و آلگاریتم ژنتیک

بخشی از پاورپوینت

اسلاید 1 :

بهينه سازي و آلگاريتم ژنتيك

درس : کاربرد فن آوری اطلاعات پزشکی

اسلاید 2 :

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

اسلاید 3 :

تاريخچه الگوريتم ژنتيك :
الگوريتم هاي ژنتيك با توجه به نظريه داروين در مورد تكامل شكل گرفتند. محاسبات تکاملي درسال 1960 به وسيله ي شخصي به نام Rechenberg مرسوم شد بعداً ايده او توسط محققان ديگر رشد يافت . ژنتيک الگوريتم (GA) توسط John Holland اختراع شد وتوسط خودش و دانشجويان او وتعدادي از همکارانش رشد و توسعه يافت Holland کتابي در اين زمينه در سال 1975 نوشت به نام "Adaption in Natural and Artificial systems" در سال 1992 John Koza از ژنتيک الگوريتم در برنامه اي استفاده کرد که کارهاي مشخصي انجام مي داد Koza نام اين روش را Genetic Programming (GP) گذاشت .

اسلاید 4 :

طرح چند مساله :
پيش از معرفي روش الگوريتم ژنتيک چند مساله ساده را كه مي توان در حل آنها از الگوريتم ژنتيك استفاده كرد را در نظر مي گيريم :

بازي بردار
جدول همگن
پيدا كردن ميزان ماكزيمم تابع F(x)=-x^2+6x-3 در بازه 0<=x<=15
نوشتن برنامه هفتگي پرسنل يك سازمان
TSP يا Traveling Salesman Problem

اسلاید 5 :

روش الگوريتم ژنتيك :
اصول كار الگوريتم ژنتيك به صورت روند زير ارائه مي گردد

گام 1 – كد گذاري
گام 2 – انتخاب تصادفي جمعيت اوليه از مجموعه پاسخ ها
گام 3 – محاسبه ميزان سازگاري گروه پاسخ با تابع هدف ( Fitness )
گام 4 – ايجاد جمعيت جديد با استفاده از عملگر هاي ژنتيك (تكثير تركيب و جهش)
گام 5 – تكرار مراحل سوم و چهارم تا هنگامي كه جواب نهايي همگرا گردد

اسلاید 6 :

مرحله 1 : كد گذاري :
نخستين مرحله در مدل سازي الگوريتم ژنتيک براي يک مسئله ، اجراي يک روش براي کد کردن ژنوم ها به زبان کامپيوتر است . يکي از روش هاي معمول کد کردن به صورت رشته هاي باينري است به صورت رشته هاي صفر و يك . يک راه حل مشابه ديگر کدکردن راه حل ها در آرايه اي از اعداد صحيح يا اعشاري است ، که دوباره هر جايگاه يک جنبه از ويژگي ها را نشان مي دهد . اين راه حل در مقايسه با قبلي پيچيده تر و مشکل تر است.

اسلاید 7 :

مرحله 2 : انتخاب تصادفي جمعيت اوليه از مجموعه پاسخ ها :
در اين مرحله موتور الگوريتم ژنتيک يک جمعيت اوليه از مجموعه پاسخ ها
ايجاد مي کند. اين انتخاب مي تواند به يكي از اين روشها انجام شود :

1 – انتخاب تصادفي از بين مجموعه جواب هاي ممكن
2 – انتخاب از بين يك جمعيت قبلي نگهداري شده
3 – يك مجموعه از راه حل ارائه شده توسط فرد خبره
4 – يك مجموعه راه حل ارائه شده توسط يك الگوريتم خلاق ديگر

اسلاید 8 :

مرحله 3 : محاسبه ميزان سازگاري گروه پاسخ با تابع هدف ( برازش يا Fitness ) :
هر فرد از گروه در برابر مجموعه اي از داده ها ي مورد آزمايش قرار مي گيرد و مناسبترين آنها شايد 10 درصد از مناسبترين ها باقي مي مانند.بقيه کنار گذاشته مي شوند.

راه حل خوب ، به خوب بودن تابع ارزيابي بستگي دارد ( معمولا“ سخت ترين قسمت است ) عملگر ارزيابي يك كروموزوم را رمزگشايي مي كند و يك مقدار برازندگي به آن نسبت مي دهد . الگوريتم ورودي هايي که به جواب بهينه نزديک ترند را نگه داشته و از بقيه صرف نظر مي کند.

اسلاید 9 :

مرحله 4 : ايجاد جمعيت جديد با استفاده از عملگر هاي ژنتيك (تكثير تركيب و جهش) :
وقتي با روش هاي انتخاب کروموزوم ها انتخاب شدند، بايد به طور تصادفي براي افزايش تناسبشان اصلاح شوند. 2 راه حل اساسي براي اين کار وجود دارد :
Crossover : کروموزوم هاي برگزيده قبلي براي معاوضه سگمنتهاي کدشان انتخاب مي شوند. اين فرآيند بر اساس فرآيند ترکيب کروموزوم ها در طول توليد مثل در موجودات زنده شبيه سازي شده.
Mutation :درست مثل جهش در موجودات زنده که عبارت است از تغيير يک ژن به ديگري ، در الگوريتم ژنتيک جهش تغيير کوچکي در يک نقطه از کد خصوصيات ايجاد مي کند.
گام مهم ديگر درالگوريتم ، تولد است که در هر دوره يکبار اتفاق مي افتد. محتويات دو کروموزومي که در فرآيند توليد شرکت مي کنند با هم ترکيب ميشوند تا 2 کروموزوم جديد که ما انها را فرزند مي ناميم ايجاد کنند.

اسلاید 10 :

مرحله 5 : تكرار مراحل دوم تا چهارم تا هنگامي كه جواب نهايي همگرا گردد :
معيارهاي زير بهعنوان معيار توقف در الگوريتم ژنتيك شمرده ميشوند :
زمان اجراي الگوريتم
تعداد نسلهايي که ايجاد ميشوند
يک راه حل راضي کننده بدست آمده باشد.
بعد از انجام تعداد معين توليد نسل هيچ پيشرفتي در کيفيت راه حلها بوجود نيايد (همگرايي معيار خطا )
بيشترين درجه برازش فرزندان حاصل شود يا ديگر نتايج بهتري حاصل نشود.
ترکيبي از معيارهاي بالا.

اسلاید 11 :

فلوچارت الگوريتم ژنتيك (1)
نقطه خروج ؟

اسلاید 12 :

فلوچارت الگوريتم ژنتيك (2)
محل شرط توقف ؟

اسلاید 13 :

فلوچارت الگوريتم ژنتيك (3)
تكرار ارزيابي راه حل ها ؟

اسلاید 14 :

فلوچارت الگوريتم ژنتيك (4)
محل خروج از حلقه تكرار ؟

اسلاید 15 :

فلوچارت الگوريتم ژنتيك (5)
قابل قبول :

اسلاید 16 :

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

اسلاید 17 :

نقاط قوت و ضعف الگوريتم هاي ژنتيک :
محدوديتهاي Gaها

يک مشکل چگونگي نوشتن عملگر Fitness است که منجر به بهترين راه حل براي مسئله شود.اگر اين کارکرد برازش به خوبي و قوي انتخاب نشود ممکن است باعث شود که راه حلي براي مسئله پيدا نکنيم يا مسئله اي ديگر را به اشتباه حل کنيم.

اسلاید 18 :

چند نمونه از کاربرد هاي الگوريتم هاي ژنتيک :
توپولوژي هاي شبکه هاي کامپيوتي توزيع شده.
بهينه سازي ساختار ملکولي شِميايي (شيمي)
مهندسي برق براي ساخت آنتنهاي Crooked-Wire Genetic Antenna
مهندسي نرم افزار
بازي هاي کامپيوتري
مهندسي مواد
مهندسي سيستم
رباتيک(Robotics)
تشخيص الگوو استخراج داده(Data mining)
آموزش شبکه هاي عصبي مصنوعي
ياددهي رفتار به رباتها با GA .
يادگيري قوانين فازي با استفاده از الگويتم هاي ژنتيک
درك زبان محاوره اي و يا خواندن متون

اسلاید 19 :

کاربرد هاي الگوريتم ژنتيک در پزشكي :
توليد برنامه هاي درماني
بهينه سازي فرمولهاي دارويي وساختارهاي مولکولي
بهبود تشخيص
بهبود کيفيت تصميم گيري