الگوریتم ژنتیک چیست؟

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

در این نوشته می خواهیم از الگوریتم ژنتیک صحبت کنیم، این بحث بسیار بسیار شیرین است.

ما می توانیم دنیای واقعی را در قالب مدل های ریاضی، مدل سازی کنیم. این مدل ها از ویژگی های خاصی برخوردار می باشند، مثلا مهمترین ویژگی این مدل ها مشتق پذیر بودن آن ها میباشد.

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

آیا نقشه برداری با پهپاد برای پروژه شما مناسب است؟

اگر بخواهیم واضح تر توضیح دهیم، برای ساختن یک ساختمان بی نهایت واریانت وجود دارد. مثلا نوع اسکلت، جایگذاری ستون ها، جنس سقف و … ، به طوریکه هر کدام از این واریانت ها تغییر کند، در نهایت یک ساختمان به دست می آید. اما ما به دنبال راه کاری هستیم که به وسیله آن ساختمان را بهینه بسازیم.

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

معرفی الگوریتم ژنتیک

دانشمندان در حوزه ژنتیک به رفتار تولید مثلی موجودات زنده نگاه می کنند، قوانین حاکم بر آن ها را پیدا می کنند و از این قوانین در رشته خود بهره می برند. در واقع دانشمندان برای رسیدن به اهداف خود از رفتار موجودات زنده استفاده می کنند. به عنوان مثال : نحوه پیداکردن غذا توسط زنبورها، اینکه پرنده ها چگونه مسیر حرکت خود را پیدا می کنند و … ، همگی رفتارهایی هستند که توسط دانشمندان زیر نظر قرار می گیرند.

الگوریتم ژنتیک نیز از طبیعت کمک گرفته، به طوریکه با استفاده از آن می توان به جواب های بهینه و مطمئنی در علوم مهندسی رسید.

ویژگی های الگوریتم ژنتیک :

• مبتنی بر توارث می باشد.
• موجودات زنده را به وجود می آورد.
• همه ما انسان ها در به وجود آمدن نسل ها از آن تبعیت می کنیم.

راز طبیعت در الگوریتم ژنتیک و (توارث) شایسته سالاری می باشد. البته این شایسته سالاری به تدریج اتفاق می افتد، به طوریکه هرچه شایستگی بیشتر باشد. احتمال بقا بیشتر است. (همیشه بهترین موجودات از حیات بهره مند می شوند)، امروزه معیارهای شایستگی برای انسان، توانایی های عقلی او می باشد.

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

نتیجه اینکه، هر موجودی که می خواهد ساخته شود، با یک کروموزوم ساخته می شود. به طوریکه تغییر محتوای درونی هر کدام از این کروموزوم ها، منجر به تغییر محصول نهایی می شود.

تولید مثل :

در فرآیند تولید مثل یک parent مادر است و یک parent پدر، حال وقتی که فرزندان می خواهند از آن ها تولید شوند، یک کروموزوم هم سایز کروموزوم قبلی ساخته می شود.

در واقع بعد از انجام لقاح یک کروموزوم به دست می آید که بخشی از آن از پدر به ارث رسیده و بخشی از مادر.

برای توضیح واضح تر موضوع به شکل ذیل توجه کنید :

والد اول :

والد دوم :

فرض کنید یک پدر داریم و یک مادر (یک رشته کروموزوم والد اول و یک رشته کروموزوم والد دوم)، به طوریکه از این دو قرار است یک فرزندی تولید شود (طی فرآیند crossover، لقاح)

crossover : به فرآیندی گفته می شود که حاصل تلفیق ژنتیکی دو والد می باشد.

طبق شکل ذیل این فرآیند انجام می شود :

طی این فرآیند ابتدا از پدر و مادر یک کروموزوم خالی درست شده، سپس بخشی از آن از طریق کروموزوم پدر و بخشی دیگر از طریق کروموزوم مادر پر می شود.

اگر به شکل فوق توجه کنید، پنج تای اول مربوط به کروموزوم والد اول و پنج تای دوم مربوط به کروموزوم والد دوم می باشد.

حال ممکن است طی این فرآیند، جهش (mutation) اتفاق افتد. ممکن است این جهش منجر به موجود شایسته تری شود و یا موجودی را تولید کند که اصلا شایسته نیست. (جهش باعث رشد در یک جامعه می شود)

چگونگی استفاده از الگوریتم ژنتیک در علوم مهندسی :

الگوریتم ژنتیک در علوم مهندسی :

• فرد می شود : تابع چند جمله ای
• کروموزوم می شود : ساختار ترم هایی از تابع چند جمله ای ، به طوریکه هر کدام از این ترم ها هم می توانند باشند و هم می توانند نباشند، اگر باشند (یک) و اگر نباشند (صفر)، حال از کنار هم قرار گرفتن این صفر و یک ها یک فرد به وجود می آید، این فرد یک شایستگی دارد.
• شایستگی می شود : RMSE
• اگر RMSE خوب بود، احتمال دارد که زاد و ولد کند و موجود جدیدی را به وجود آورد.

در واقع الگوریتم ژنتیک می گوید، یک جامعه اولیه درست کن، (به طوریکه در تولید جامعه اولیه هیچ دانش و آگاهی نسبت به ترم های خوب و بد نداریم) سپس مسائل و اهداف مورد نظر را برسی کن.

در نوشته های بعدی مطالب ذیل مورد بررسی قرار می گیرد :

1. کد نویسی الگوریتم ژنتیک
2. توضیح نحوه کدنویسی (الگوریتم ژنتیک)

بررسی و دانلود نرم افزار Global Mapper آخرین نسخه همراه با کرک [/box]

اگر به علمی رسیدیم و از آن علم در خداشناسی استفاده نکردیم، هیچ سودی در آن علم نیست.