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

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

اسلاید 1 :

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

الگوريتم ژنتيك يك نوع الگوريتم جستجوي مبتني بر مكانيزم انتخاب طبيعي و علم ژنتيك طبيعي است.
اين الگوريتم قدرت بقاي بهترين ساختار رشته اي (كروموزوم) را با عمل تعويض تصادفي اطلاعات تركيب كرده و الگوريتم جستجويي مشابه با قوه تشخيص ابتكاري انسان در عمل جستجو،تشكيل مي دهد.
بهينه سازی شبكه با استفاده از الگوريتم ژنتيك

اسلاید 2 :

اين الگوريتم از تاريخچه اطلاعات قبلي براي جستجو بر روي مجموعه نقاط جديد در رسيدن به يك معيار بهتر استفاده مي كند.
الگوريتم ژنتيك اولين بار توسط John Holland در سال 1975 و همكارانش در دانشگاه ميشيگان مطرح گرديد .
الگوريتم هاي ژنتيك بر اين اصل طبيعي استوارند كه موجودات زنده با شايستگي يا برازندگي بيشتر در تلاش اند تا اطلاعات ژنتيكي خود را از نسلي به نسل ديگر حفظ نمايند.

اسلاید 3 :

GA ها با يك پايگاه داده پر شده از جمعيت كار مي كنند و بطور همزمان مي توانند در طول فرآيند جستجو بطور موازي به سمت چندين نقطه ماكزيمم صعود نمايند،كه اين فرآيند احتمال افتادن در دام بهينه هاي محلي را به ميزان زيادي كاهش مي دهد.

در طبيعت هر گونه زنده براي افزايش احتمال زنده ماندن خود به حداكثر ميزان، بايستي به تغيير و تحولات محيط اطراف سازگار گردد و هر آنچه كه هر گونه در طي فرآيندهاي سازگاري بدست مي آورد در كروموزمهاي آن بصورت كدهاي ژنتيكي در مي آيد كه در حين فرآيند توليد مثل به جنين منتقل مي گردد.

اسلاید 4 :

بعد از گذشت يك پريود زماني اين تغييرات در كروموزمها باعث مي شود كه گونه ها بيشترين احتمال را براي زنده ماندن داشته و به اين ترتيب بيشترين شانس را براي انتقال اين ويژگيهاي مناسب در توليد مثلهاي آينده خواهند داشت.( البته تنها تغييراتي مفيد خواهند بود كه به مرگ منجر نشوند.)
الگوريتم ژنتيك هالند نيز تلاش مي نمايد تا الگوريتم ژنتيك طبيعي را بصورت زير شبيه سازي نمايد .

اسلاید 5 :

مرحله اول ارائه جوابهاي ممكن براي حل مسئله در قالب رشته اي از ژنها است كه مي توانند بصورت تعدادي عدد و رقم در يك بازه اعداد يا حروف الفبا باشند.
به اين رشته از ژنها كه بيانگر يك جواب براي مسئله مي باشند يك كروموزوم گوييم.
سپس به طور تصادفي جمعيت اوليه اي از كروموزومهاي قانوني ايجاد مي گردند.
درهر توليد مثل ميزان شايستگي يا برازندگي هر كروموزوم موجود درجمعيت اندازه گيري شده و كروموزومهاي با عدد شايستگي بيشتر براي توليدنوزادانتخاب مي شوند كه اين نوزاد بهترين ويژگيهاي والدين را به ارث مي برد.

اسلاید 6 :

بعد از چندين توليدمثل يك جمعيت كه با برازندگي بيشتري نسبت به جمعيت اوليه مي باشد، باقي خواهد ماند.
تمام الگوريتم هاي ژنتيك از اجزاي زير تشكيل شده اند:

1- الگوهاي كروموزومي Chromosomal Representation
هر كروموزوم بيانگر يك جواب ممكن براي حل مساله بوده و از رشته اي از ژنها تشكيل گرديده است.
هر ژن نيز مي تواند اشكال مختلفي داشته باشد كه به آن Allele گفته مي شود.

اسلاید 7 :

معمولاً براي نشان دادن اين ژنها از اعداد باينري {0 و 1} استفاده مي گردد ولي در برخي موارد بسته به كاربرد مورد نظر ميتوان از اعداد صحيح يا حقيقي استفاده نمود.
در واقع مي توان گفت كه هر الگويي كه بكار مي رود اين امكان را فراهم مي آورد تا يك جواب يا راه حل را به صورت رشته اي با طول محدود كد گذاري نمود و به صورت عدد ورقم نمايش داد.

اسلاید 8 :

2- جمعيت اوليه Initial Population
زمانيكه الگوهاي مناسبي در قالب كروموزومها تشكيل شدند لازم است تا يك جمعيت اوليه از اين كروموزمها ايجاد گردد تا به عنوان نقطه شروع الگوريتم ژنتيك عمل نمايند.
اين جمعيت اوليه اغلب به صورت تصادفي ايجاد مي شوند .
از مطالعات تجربي كه در حل مسايل بهينه سازي صورت گرفته اند چنين بر مي آيد كه اندازه جمعيت اوليه بين30 تا 100 كروموزوم مناسب است.

اسلاید 9 :

3- ارزيابي ميزان شايستگي Fitness Evaluation
ارزيابي ميزان برازندگي شامل تعيين مقدار تابع هدف يا تابع برازندگي براي هر كروموزوم درمواجهه با محيط موردنظر مي باشد.
با پيشرفت الگوريتم انتظار داريم كه ضمن افزايش شايستگي هر كروموزوم به طور جداگانه ، شايستگي كل جمعيت جديد نيز به بيشترين ميزان خود ارتقاء يابد.

اسلاید 10 :

4- انتخاب Selection
براي توليد نسل جديد نياز به انتخاب كروموزومهايي از جمعيت فعلي مي باشد.
اگر يك جمعيت با تعدادN 2كروموزوم داشته باشيم، رويه انتخابگر دو كروموزوم را بر مبناي مقدار شايستگي به عنوان والدين انتخاب مي كند كه بعداً تحت تاثير عملگرهای جابه جايي و جهش براي توليد دو نوزاد جمعيت جديد قرار خواهند گرفت.
سيكل انتخاب – جابه جايي – جهش، آنقدر تكرار مي گردد تا جمعيت جديد نيز شامل N 2كروموزوم گردد.

اسلاید 11 :

طبيعي است كه هر چه ميزان شايستگي هر كروموزوم بيشتر باشد، احتمال انتخاب آن كروموزوم براي توليد مثل بيشتر خواهد بود.

اسلاید 12 :

5- جابه جايي و جهش Cross over &Mutation
هنگامي كه يك جفت كروموزوم انتخاب شده اند از عملگر جابه جايي براي توليد نوزاد استفاده مي گردد.
چنانچه احتمال انجام عمل جابه جايي يك باشد، بيانگر اين خواهد بود كه تمام كروموزوم هاي انتخاب شده در توليد مثل بكار گرفته خواهند شد و اين به منزله اين است كه هيچ كروموزوم زنده اي باقي نخواهد ماند.
مطالعات تجربي نشان داده است كه بهترين نتايج زماني حاصل مي گردد كه احتمال انجام عمل جابه جايي 85%-65% باشد.

اسلاید 13 :

این مطلب بيانگر اين است كه احتمال اينكه يك كروموزوم انتخاب شده براي توليد مثل بعدي بدون تغيير باقي بماند. ( بدون در نظر گرفتن هر گونه تغيير حاصل از عملگر جهش) به ميزان 35%-15% تغيير می کند.
چنانچه تنها از عملگر جابه جايي براي توليد نوزاد استفاده كنيم، مشكلي كه به وجود خواهد آمد اين است كه اگرتمام كروموزومهاي موجود درجمعيت اوليه داراي مقدار مشابهي در يك موقعيت ويژه باشند پس تمام نوزادان جديد نيز داراي همين مقدار در همين موقعيت خواهند بود.

اسلاید 14 :

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

اسلاید 15 :

هر بيت در هر كروموزوم براي امكان سنجی انجام عمل جهش مورد ارزيابی قرار مي گيرد،که اين ارزيابی با توليد يک عدد تصادفی بين صفر و يک صورت می پذيرد، درصورتي كه اين عدد تصادفي كمتر مساوي مقدار احتمال انجام عمل جهش مثلاً 0/001 باشد. اين مقدار بيت تغيير خواهدنمود.

اسلاید 16 :

اين فرايند يك سيكل مربوط به يك الگوريتم ژنتيك ساده مي باشد.
ميزان شايستگي مربوط به هر كروموزوم در جمعيت جديد موردسنجش قرار گرفته و تمام رويه مجدداً تكرار مي گردد . يعني:

اسلاید 18 :

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

اسلاید 19 :

روش بكار رفته در اين تحقيق شامل مراحل ذيل به منظور يافتن طرح شبكه با حداقل هزينه می باشد:
گام اول- خواندن اطلاعات شبكه، داده هاي مربوط به هزينه، حداقل و حداكثر فشار مورد نياز و تعداد جمعيت كه همان جوابهاي ممكن مي باشند.
حداكثر تعداد باز توليد كه به صورت (Maximum Generation)MG نشان داده مي شود، ميزان پنالتي يا جريمه به ازاي تخطي از هر واحد فشار يا سرعت جريان، تولرانس يارواداري، حداكثر و حداقل سرعت درلوله ها،حداكثر تعداد تكرار براي تنظيم قطرهاMI (Maximum Iteration)
بهينه سازي شبكه لوله ها بر مبناي GA

اسلاید 20 :

گام دوم- توليد جمعيت اوليه جوابها به صورت تصادفي.
گام سوم- شمارنده I را مساوي يك قرار بده
گام چهارم- براي تمام اعضاي جمعيت مطابق ذيل عمل كن.
(i)- شمارنده J را مساوي يك قرار بده.
(ii)- براي هر كدام از اعضاي جمعيت، تحليلگر هيدروليكي را اجرا كن تا سرعتها و فشارها محاسبه گردد.
(iii)- در صورت بيشتر بودن ميزان سرعت از سرعت ماكزيمم از قبل تعيين شده، قطر لوله را به سايز قطر تجاري بعدي افزايش بده و چنانچه سرعت از سرعت حداقل از قبل تعيين شده كمتر بود، قطر را يك سايز تجاري كاهش بده واين عمل را تا زماني كه مقدار قدر مطلق ( كل تعداد دفعات افزايش و كاهش) كمتر از چهار باشد ادامه بده.