الگوريتم ژنتيك (GA)

[ravegoat]

الگوريتم ژنتيك (Genetic Algorithm) يك الگوريتم جست و جو براساس الگوي تكامل نسل ها در طبيعت است. ايده ي اين الگورتيم به شكل جدي پس از تحقيقات John Holland از دانشگاه مشيگان مطرح شد. در اين تاپيك به تدريج گام هاي استفاده از اين الگوريتم و كاربرد آن در بهينه سازي به خصوص بهينه سازي چند هدفه (Multi-Objective Optimization) مطرح خواهد شد.

نگاهي به يك مسئله ي بهينه سازي چند هدفه:
در بهينه سازي طراحي يك سيستم اگر مجموعه ي

X={x₁,x₂,..x_m}

متغير هاي طراحي (Design Variable) باشند آن گاه طراح بايد اين متغير هاي طراحي را به گونه اي تغيير دهد كه مقادير مجموعه ي توابع هدف (Cost Function) اكسترمم شود:

F={f₁,f₂,...f_n}

مثال:
در بهينه سازي طراحي يك تير طراح بايد مساحت سطح مقطع تير و طول تير را به گونه اي تغيير دهد كه اولا" تغيير شكل تير نسبت به بار وارد به تير كمينه باشد و همچنين تير كم ترين جرم را داشته باشد. در اين طراحي متغير هاي طراحي (D.V.) مساحت سطح مقطع و طول تير هستند و توابع هدف (C.F.) مقدار تغيير شكل تير و جرم آن هستند كه طراح سعي دارد مقدار آن ها را كمينه كند.


كاربرد الگوريتم ژنتيك در بهينه سازي:
الگوريتم ژنتيك يك روش جست و جوي مستقيم (Direct Search) در بهينه سازي محسوب مي شود زيرا مستقيما" با مقدار تابع هدف سر و كار دارد و برخلاف روش هاي Gradient Based از تابع هدف مشتق گيري رياضي نمي كند. در GA متغير هاي طراحي به شكل رشته هاي كروموزوم كد مي شوند و اين رشته ها فرآيند هاي تكامل طبيعي نظير توليد مثل (Crossover) و جهش (Mutation) را سپري مي كنند. در هر مرحله رشته هاي معيوب حذف شده (Termination) و رشته هاي برتر باقي مي مانند و ويژگي خود را به نسل بعد منتقل مي كنند. بدين ترتيب هر نسل جديد، برتر از نسل هاي قديمي خواهد بود. اين روند تكامل را بسته به كاربرد مسئله مي توان تا دست يابي به برترين نسل ادامه داد. در نهايت برترين رشته هاي كروموزومي به دست آمده Decode مي شوند تا بهينه ترين متغير هاي طراحي كه همان دغدغه ي طراح بودند، به دست آيند.