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

آلگوریتم ژنتیک

4-1- مقدمه
استفاده از آلگوریتم ژنتیک برای یک پروسه بهینه یابی برای اولین بار در سال 1975م. توسط آقای"هلند " مطرح شد. ابداع این آلگوریتم به عنوان یک آلگوریتم بهینه سازی، اصولاً براساس شبیه سازی تکامل طبیعی بوده است و این الگوریتم برمبنای یک تئوری قوی ریاضی، پایه گذاری شده است.
تکامل، یک پروسه بهینه سازی، مبتنی بر تغییرات تصادفی نمونه های مختلف در یک جمعیت و انتخاب بهترین آنها است. با مدل سازی این پروسه می توان یک تکنیک بهینه سازی آماری را به دست آورد که امروزه در مسائل پیچیده مختلف کارآیی خود را نشان داده است. در این آلگوریتم نمونه هایی که در پروسه تکاملی قرار می گیرند، جوابهای مختلف در فضای جواب هستند. متناظر با هر جواب یک نمود ژنتیکی به صورت یک دنباله از ژنها نسبت داده می شودکه درشکل (4-1 ) نشان داده شده است. آلگوریتم ژنتیک در هر تکرار محاسباتی ( نسل ) جمعیتی از دنباله ها را انتخاب کرده و با انجام عملکردهای ژنتیکی روی آنها نسل جدید را تولید می کند. انتخاب طبیعی براساس نمود رفتاری هر دنباله انجام می شود. یعنی عملکرد دنباله ها توسط تابع هدف ارزیابی شده و انتخاب برمبنای این ارزیابی و تصادف انجام می شود.
ژن شکل 4-1: نمایش کروموزم و ژن
0 1 1 0 1 0 0 1 1 1
یک کروموزم
یا دنباله
آلگوریتم ژنتیک به عنوان یک آلگوریتم محاسباتی بهینه سازی، با در نظر گرفتن مجموعه ای از نقاط فضای جواب در هر تکرار محاسباتی، به نحو مؤثری، نواحی مختلف فضای جواب را جستجو می کند. در مکانیزم جستجو، گرچه مقدار تابع هدف در تمام نقاط فضای جواب محاسبه نمی شود ولی مقدار محاسبه شده تابع هدف برای هر نقطه، در متوسط گیری آماری تابع هدف در کلیه زیرفضاهایی که آن نقطه بدانها وابسته بوده، دخالت داده می شود. این زیرفضاها به طور موازی از نظر تابع هدف متوسط گیری آماری می شوند. این روند باعث می شود که جستجوی فضا به نواحیی از آن که متوسط آماری تابع هدف در آنها زیاد بوده و امکان وجود نقطه بهینه مطلق در آنها بیشتر است، سوق پیدا کند. چون در این روش برخلاف روشهای تک مسیری، فضای جواب به طور همه جانبه جستجو می شود، امکان کمتری برای همگرایی به یک نقطه بهینه محلی وجود خواهد داشت. امتیاز دیگری که این آلگوریتم دارد این است که هیچ محدودیتی برای تابع بهینه شونده، مثل مشتق پذیری و پیوستگی و غیره ندارد. در روند جستجوی خود، تنها به تعیین مقدار تابع هدف در نقاط مختلف نیاز دارد و اطلاعات کمکی دیگری مثل مشتق تابع هدف را استفاده نمی کند. لذا می تواند در مسائل مختلف اعم از خطی، غیرخطی، پیوسته و گسسته استفاده شود و به سهولت با مسائل مختلف قابل تطبیق است.

4-2- اصول اساسی آلگوریتم ژنتیک
در آلگوریتم ژنتیک هر کروموزم شامل چند ژن است که در حقیقت داخل این ژنها مقادیری برای متغیرهای تابع هدف قرار دارد و کاراکترهایی که در هر ژن قرار می گیرد از مجموعه آلفابت ( مقادیر ممکن ) متغیرها انتخاب می شود. مثلاً اگر از کدگذاری باینری استفاده شود در هر ژن فقط مقادیر صفر یا یک می تواند قرار گیرد.
بنابراین هر کروموزم یا دنباله نشان دهنده یک نقطه در فضای جواب است. و در هر تکرار، هریک از P دنباله موجود در جمعیت دنباله ها دیکد شده و مقدار تابع هدف برای آن به دست می آید. براساس این مقادیر به هر دنباله یک عدد برازندگی نسبت داده می شود این عدد برازندگی احتمال انتخاب را برای هر کروموزم تعیین خواهد کرد. براساس این احتمال انتخاب، مجموعه ای از کروموزمها، انتخاب شده و با اعمال عملکردهای ژنتیکی روی آنها دنباله های جدید تولید می شوند. این دنباله های جدید جایگزین دنباله هایی از نسل قبل می شوند. بدین ترتیب تعداد دنباله ها یا کروموزمها در هر تکرار ثابت می ماند. مکانیزمهای تصادفی که روی انتخاب دنباله ها عمل می کنند به گونه ای هستند که کروموزمهایی که عدد برازندگی بیشتری دارند شانس بیشتری برای تولید نسل بعد دارند. بدین لحاظ مقدار تابع هدف دنباله ها در یک رقابت، در طی نسلهای مختلف، متکامل شده و متوسط مقدار تابع هدف در جمعیت دنباله ها افزایش می یابد.

در اجرای این آلگوریتم نیاز به سه پارامتر زیر می باشد که در آن جمعیت اولیه دنباله ها است و کاربرد و در بخش (4-2-3) بیان خواهد شد.
: جمعیت دنباله ها
: نرخ ترکیب
: نرخ جهش
قبل از بیان روند اجرای یک آلگوریتم ژنتیک لازم است نحوه تعیین عدد برازندگی برای هر کروموزم و همچنین نحوه انتخاب کروموزمها و نیز عملکردهای ژنتیکی که برروی کروموزمها عمل می کنند مورد بحث قرار گیرند.

4-2-1- تعیین عدد برازندگی دنباله ها
چنانکه گفته شد هر دنباله معرف یک نقطه در فضای جواب است و به آن یک مقدار تابع هدف نسبت داده می شود. از طرفی احتمال انتخاب هر دنباله در مکانیزم انتخاب به عدد برازندگی دنباله وابسته است. عدد برازندگی بیشتر برای یک دنباله به معنی احتمال بیشتر برای بقای آن دنباله در نسلهای مختلف و شرکت در تولید دنباله های جدید می باشد. لذا همگرایی آلگوریتم در جهت رشد دنباله های با عدد برازندگی بیشتر است. در راستای حداکثر کردن تابع هدف بایستی عدد برازندگی هر دنباله را به صورت یک تابع افزایشی از تابع هدف در نظر گرفت و در مواردی که حداقل کردن یک تابع هزینه مد نظر باشد، این رابطه بایستی به صورت یک تابع کاهشی در نظر گرفته شود.برای آنکه در هر انتخاب، احتمال انتخاب برای هر دنباله متناسب با عدد برازندگی آن باشد این عدد بایستی مقدار غیرمنفی داشته باشد. بنابراین بهتر است در هر تکرار محاسباتی متوسط مقدار تابع هدف از مقدار این تابع برای هر دنباله کم شود و در صورتی که این عدد مثبت باشد آنرا بعنوان عدد برازندگی دنباله در نظر گرفته و در صورت منفی بودن به آن دنباله عدد برازندگی صفر نسبت داده شود. با این روش دنباله هایی که مقدار تابع هدف آنها کمتر از متوسط تابع هدف دنباله های آن نسل باشد حذف می شوند.
همچنین بهتر است عدد برازندگی هر دنباله بر مجموع اعداد برازندگی تقسیم شود، تا جمع اعداد برازندگی مساوی یک باشد. این کار در مکانیزم انتخاب ( که در بخش بعد به آن پرداخته خواهد شد ) مؤثر است و باعث می شود در هر نسل جهت انتخاب، فقط لازم باشد عدد اتفاقی، بین صفر تا یک انتخاب شود ( مستقل از اینکه حداکثر عدد برازندگی چقدر است ). روابط (4-1) و (4-2) طریقه محاسبه عدد برازندگی را نشان می دهد.


(4-1)
(4-2)
که در این روابط:
: مقدار تابع هدف برای دنباله ام
: میانگین مقادیر برای تمام دنباله هر نسل
: مجموع مقادیر مثبت برای تمام دنباله هر نسل

4-2-2- مکانیزم انتخاب
در مرجع ]12[ به چند روش برای انتخاب تصادفی کروموزمها، اشاره شده است که مهمترین آنها از نظر اجرا و در نظر گرفتن تأثیر مقدار تابع هدف روشي است معروف به چرخ رولت. در این روش احتمال انتخاب هر کروموزم متناسب با عدد برازندگی آن است، و این باعث همگرایی در آلگوریتم می شود. این روش به این صورت است که ابتدا دنباله ها برحسب اعداد برازندگی مرتب می شوند. و پس از آن تابع چگالی احتمال ( مشابه شکل 4-2 ) برای اعداد برازندگی تشکیل می شود.

و به کمک تابع توزیع احتمال می توان تابع توزیع تجمعی احتمال ( مشابه شکل 4-3 ) را به دست آورد.

با انتخاب یک عدد اتفاقی بین صفر تا یک می توان یک کروموزم را انتخاب کرد ( مثلاً در شکل 4-3 کروموزم ام انتخاب شده است ). بنابراین به تعداد مورد نیاز می توان کروموزم، با احتمالی متناسب با عدد برازندگی آن انتخاب کرد.





4-2-3- عملگرهای ژنتیکی
فرآیندهای ژنتیکی شامل دو عمل ترکیب و جهش می باشند. نرخ ترکیب که آنرا با نشان می دهند معمولاً بین 6/0 تا 95/0 در نظر گرفته می شود. در هر دور محاسباتی تعداد کروموزم جهت ترکیب انتخاب می شوند. عملگر ترکیب روی یک زوج دنباله ( والدین ) عمل کرده و یک زوج دنباله دیگر ( فرزند ) تولید می کند. نرخ جهش را نیز با نشان می دهند. معمولاً عمل جهش در طبیعت به ندرت اتفاق می افتد بنابراین احتمال جهش را بیشتر اوقات کمتر از 01/0 در نظر می گیرند. جهش از همگرایی آلگوریتم به یک نقطه بهینه محلی جلوگیری می کند. عملگر جهش روی یک کروموزم عمل کرده و مقدار یکی از ژنهای آنرا به طور اتفاقی به یکی از کاراکترهای مجموعه آلفابت ژنها تغییر می دهد.
در مرجع ]12[ به 17 نوع عمل ترکیب اشاره شده است که مرسوم ترین آنها به قرار زیرند:
الف) ترکیب یک نقطه ای
ب) ترکیب دو نقطه ای
ج) ترکیب یکنواخت
نحوه عملکرد ترکیب یک نقطه ای بدین صورت است که در طول دو کروموزم یک نقطه مشترک، به صورت اتفاقی تعیین شده و جای ژنهای، دو دنباله، از آن به بعد تعویض می شود. و در ترکیب دو نقطه ای، چنانکه از اسم آن نیز پیداست، دو نقطه در طول دو کروموزم والد انتخاب شده و جای ژنهای بین این دو نقطه در دو کروموزم تعویض می شود که در شکل (4-4 ) نشان داده شده است.


در انجام ترکیب یکنواخت به تعداد ژنهای هر کروموزم عدد اتفاقی تولید شده و با شرط خاصی ( مثلاً اگر عدد اتفاقی زوج بود ) جای دو ژن مربوطه در دو کروموزم تعویض می شود، در غیراینصورت آن دو ژن در جای خود باقی می مانند.

4-3- روند کلی اجرای آلگوریتم ژنتیک
اکنون که با اصول اساسی آلگوریتم ژنتیک آشنا شدیم می توانیم به سادگی روند اجرای یک آلگوریتم ژنتیک را بررسی کنیم. شکل (4-5) بلوکهای اساسی در اجرای این آلگوریتم را نشان می دهد.
تعیین عدد برازندگی تعیین تابع هدف تشکیل تصادفی
هر کروموزم کروموزمها P کروموزم

انتخاب مجموعه S1 انتخاب
( والد ) مجموعه S2

اعمال عملگرهای
ژنتیکی ( تولید فرزند ) نسل جدید

شکل 4- 3: بلوک دیاگرام کلی آلگوریتم ژنتیک

نحوه اجرای آلگوریتم بدین صورت است که:
1- ابتدا تعداد دنباله، در نظر گرفته شده و ژنهای آنها بطور اتفاقی، از مجموعه آلفابت ژنها پر می شود.
2- سپس مقدار تابع هدف برای تمام کروموزمها محاسبه می شود.
3- پس از آن با استفاده از روابط (4-1) و (4-2) عدد برازندگی برای هر کروموزم به دست می آید.
4- سپس با استفاده از چرخ رولت دو مجموعه و با تعداد عناصر و تشکیل می شود. تعداد عناصر این دو مجموعه از روابط (4-3 و 4-4) به دست می آیند.
در تشکیل مجموعه باید دقت کرد که هیچ دنباله ای تکرار نشود. و همچنین باید بهترین دنباله نسل قبل در این مجموعه قرار گیرد. این کار باعث می شود که روند بهینه یابی همیشه افزایشی باشد.
(4-3)
(4-4)
زیرا با این کار همیشه مطمئن خواهیم بود که بهترین کروموزم به نسل بعد انتقال یافته است. در تشکیل مجموعه محدودیتی در نظر گرفته نمی شود و این مجموعه نیز با استفاده از چرخ رولت انتخاب می شود.
5- مجموعه بدون هیچ تغییری به نسل بعد انتقال می یابد. و با اعمال عملگرهای ژنتیکی برروی مجموعه نسل آینده تکمیل می گردد.
6- اگر تعداد دور محاسبات یا وقت، به اتمام رسیده باشد برنامه متوقف می شود و در غیراینصورت به مرحله دوم می رود.در هر دور محاسباتی باید اطلاعات مورد نیاز ( از جمله بهترین کروموزم ) استخراج شود.

منبع:پایگاه اطلاع رسانی مهندسین برق

داده های خوبی بود
ولی محض اطلاع باید بگم دوره ی این ها سر اومده توی تولید علم
چراکه واسه دهه ی 60 میلادی هست
مهندس اگه وقتشو داشتی روی الگوریتم فاختر یا همون
Cuckoo search
کار کن
تازه ترین الگوریتم هست.

keeyarash گفت:

داده های خوبی بود
ولی محض اطلاع باید بگم دوره ی این ها سر اومده توی تولید علم
چراکه واسه دهه ی 60 میلادی هست
مهندس اگه وقتشو داشتی روی الگوریتم فاختر یا همون
Cuckoo search
کار کن
تازه ترین الگوریتم هست.

کلیک کنید تا باز شود...

شما بهتره در مورد الگوریتم رقابت استعماری کار کنی که خیلی جدیدتر و دقیقتره

سلام دوست عزيز
اگر امكان داره درمورد الگوريتم فاختر يا اطلاعات بيشتري به من بديد. آيا مثالي ازكاربرد اين الگوريتم جديد در مهندسي سراغ داريد؟ لطفا" راهنمايي كنيد. ممنون

سلام دوست عزيز
اگر امكان داره درمورد الگوريتم فاختر يا Cuckoo search اطلاعات بيشتري به من بديد. آيا مثالي ازكاربرد اين الگوريتم جديد در مهندسي سراغ داريد؟ لطفا" راهنمايي كنيد. ممنون

keeyarash گفت:

چراکه واسه دهه ی 60 میلادی هست
.

کلیک کنید تا باز شود...

دورش به سر اومده؟! شما در مورد الگوریتم ژنتیک چیزی میدونی!؟
اتفاقا اون زمان به دلیل سخت افزار دوره ای نداشت و همچنین مقبولیتی

درود
از دوستان كسي در مورد كاربرد الگوريتم رقابت استعماري در سازه هاي آبي و هيدروليكي اطلاعاتي داره؟
مفاهيم اوليه رو مي دونم اما دقيقاً نمي دونم روي چه موضوعي كار كنم؟
از دوستان خواهش مي كنم كمكم كنيد
پيروز و سربلند باشيد.

یعنی الگوریتم فاخته الان در متلب تولباکس داره؟
راجع به مقدماتش بیشتر توضیح بدبد لطفا!

keeyarash گفت:

داده های خوبی بود
ولی محض اطلاع باید بگم دوره ی این ها سر اومده توی تولید علم
چراکه واسه دهه ی 60 میلادی هست
مهندس اگه وقتشو داشتی روی الگوریتم فاختر یا همون
Cuckoo search
کار کن
تازه ترین الگوریتم هست.

کلیک کنید تا باز شود...

جديد ترين و قويترين الگوريتم بهينه سازي (معرفي شده در سال 2011) رو اينجا ببينيد: http://www.coasite.info

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

الگوریتم ژنتیکو با چه الگوریتم های دیگه میشه ترکیب کرد؟

مرسی قشنگ بود ولی چرا اینقد رمطالب گنگ بود

منم گیج شدم!!!

سلام بچه ها من رشتم مهندسی مکاترونیک در مقطع ارشد هستم موضوع پایان نامم رو با عنوان ارائه یک مدل چند هدفی برای رمز نگازی تصویر با استفاده از الگوریتم ژنتیک انتخاب کردم برای پروپوزال نویسی یکم به مشکل برخورد کردم میشه کمکم کنید ؟
مشکل من اینه که چجوری میتونم رمز نگاری تصویرو با الگوریتم ژنتیک بهم وفق بدم ؟
وقت خیلی کمی دارم خواهش میکنم کمکم کنید

mina1358 گفت:

سلام بچه ها من رشتم مهندسی مکاترونیک در مقطع ارشد هستم موضوع پایان نامم رو با عنوان ارائه یک مدل چند هدفی برای رمز نگازی تصویر با استفاده از الگوریتم ژنتیک انتخاب کردم برای پروپوزال نویسی یکم به مشکل برخورد کردم میشه کمکم کنید ؟
مشکل من اینه که چجوری میتونم رمز نگاری تصویرو با الگوریتم ژنتیک بهم وفق بدم ؟
وقت خیلی کمی دارم خواهش میکنم کمکم کنید

کلیک کنید تا باز شود...

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

upfc گفت:

خود متلب داره؟

کلیک کنید تا باز شود...

دیدی؟ بهت چی گفتم؟!!!!!

جالبه! هر کس یک الگوریتم رو پیشنهاد میده!

اگر یکم کاربردی کار کنین می بینین که تو هر جایی یک الگوریتم کارکرد بهتری داره.

مهم اینه که ما در مساله پیش رومون چه داده هایی داریم و از کدوم روش ها بهتر میتونیم به جواب خوبی برسیم.

بد نیست مقالاتی که در سال 2013 در راستای رشته خودتون، با روش های، فازی- عصبی - فازی عضبی- فازی تطبیقی - فازی ژنتیک - عصبی ژنتیک و انواع بهینه سازی هایی که با الگوریتم های دیگه استفاده شده رو بررسی کنید.

لازم به ذکره هیچ روشی قدیمی نیست!