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

[someCoder]

در الگوریتم ژنتیک کسی دنبال تمام راهها نیست! حالتهای اولیه و حالتهای بعدی همه random انتخاب میشند! البته معمولا یک تابع fitness هم دخییل هست اما اگر قرار باشه همه راها امتحان شوند دیگه ژنتیک به چه دردی میخوره؟

[Sepidar]

حالتهای اولیه و حالتهای بعدی همه random انتخاب میشند!
فقط راه حلهای اولیه ممکن است که رندوم انتخاب بشن. راه حلهای بعدی از ازدواج راه حلهای اولیه به دست میان.

[امیر-نا]

در الگوریتم ژنتیک کسی دنبال تمام راهها نیست! حالتهای اولیه و حالتهای بعدی همه random انتخاب میشند! البته معمولا یک تابع fitness هم دخییل هست اما اگر قرار باشه همه راها امتحان شوند دیگه ژنتیک به چه دردی میخوره؟

در الگوریتم ژنتیک یکه از روش های تولید Chield ها روش انتخانی یا رندمی بر حسب همان Fith ness function است و روش های دیگری مانند روش های همبری و جانشینی هم برای اینکار وجود دارد.Mutaion and crosover method

امیر

[someCoder]

راه حلهای بعدی از ازدواج راه حلهای اولیه به دست میان.
بله! اما خود این عمل هم random است! مساله انتخاب زوجها و مساله چگونگی ترکیب اونها هیچ کدوم قطعی نیست. همه random هست.
اما خوب از روی راه حل قبلی و با توجه به همون fitness که گفتم.

برای راه حل مساله هم اول باید یه تابع fitness تعریف کنید که بتونه یک راه حل رو امتیاز بده. یعنی میزان خوبی و بدیش رو مشخص کنه.
اونوقت n تا راه حل اولیه random درست میکنین (نسل اولیه) و برای هر کدوم fitness رو حساب میکنین. سپس از روی این راهها بعضی هاشو random انتخاب میکنین ( البته با توجه به fitness، یعنی هر کدوم بهتره احتمال انتخاب شدنش بیشتر باشه. اما همه بازم شانس دارن. مثلا اگر یک 10 واحد خوبه و دیگری 2 واحد ، اولی باید 5 برابر بیشتر شانس انتخاب شدن داشته باشه) و بعد این راه حلها رو دو بدو با هم ترکیب میکنین.
برای ترکیب هم مثلا میتونین بگین از 5 تا مهندس نصفشو از یکی و نصفه دیگشو از یکیه دیگه انتخاب کنین. (البته این یه پیشنهاده که فکر هم نمیکنم خوب جواب بده.!) دقت کنین که تمام هنر توی یه مساله ژنتیک انتخاب تابع fitness و نحوه ترکیب کردن دو تا جوابه! بقیش همه مثل همه. اینجوری اینقدر ادامه میدین تا n نفر جدید داشته باشین. (نسل دوم)
حالا این ماجرای نسل ها رو اونقدر ادامه میدین تا به یه جواب مطلوب برسین. (یا حوصلتون سر بره!)
ضمنا میتونین در هنگام اجرا در درصد مشخصی از موارد (مثلا 1%) جهش هم داشته باشید. جهش یعنی اینکه یه جواب رو صرفنظر از تابع fitness بصورت random تغییر بدین. این کار باعث میشه بن بست های احتمالی از بین برن.

[hosseinzadeh]

http://www.fortunecity.com/emachines/e11/86/algo.html
http://subsimple.com/links.asp#GALinks

[.مهدی فهمیده غلامی.]

-1 عملکرد الگوریتمهای ژنتیک

اصطلاح و ابداع واژه الگوریتمهای ژنتیک را به جان هالند از دانشگاه میشیگان نسبت می‌دهند
او در کتاب خود درسال 1975 میلادی اصول الگوریتمهای ژنتیک ساده را تشریح کرد.


Adaptation in Natural and Artificial Syste
B: johm holland,1975
Michigan university


دیگر کتاب بسیار مهم در این زمینه کتاب گلدبرگ می‌باشد:

Genetic Algorithm in Search , Optimization , and Machine Learning
By David ,E . Goldberg
Adisson –Wesley 1989


یکی از بهترین و جامعترین تعاریف الگوریتمهای ژنتیک متعلق به همین کتاب است:


The genetic algorithm is a model of machine learning which derives its behaviour from a metaphor of the processes of evolution in nature.

الگوریتمهای ژنتیک مدلی از یادگیری ماشین است که نحوه رفتار آن تمثیلی از فرآیند‌های تکاملی موجود در عالم طبیعت است.


الگوریتمهای ژنتیک یکی از قویترین روشهای برگرفته ازطبیعت است که با الهام از ژنتیک وانتخاب طبیعی, یکی از بهترین اشکال بهینه سازی عددی در مسائل علوم و مهندسی را ارائه
می‌کند.با جستجوی تصادفی و البته هوشمندانه مناسب ترین رشته‌ها از میان اطلاعات کد شده
بدست خواهد آمد.

[.مهدی فهمیده غلامی.]

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

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

چنانچه در هر مرحله تولید از الگوریتم ژنتیک، بهترین جواب‌ها نگاه داشته شود الگوریتم به سمت بهینة مطلق همگرا می‌شود.این مساله به این دلیل صورت می‌گیرد که ماهیت تصادفی الگوریتمهای ژنتیک ممکن است باعث شود تا راه حلی با برازش بسیار بالا امکان حضور در نسل بعد را پیدا نکند و برای همیشه از بین برود. به همین دلیل، درصد کوچکی از نسل بعد مستقیماً از نسل قبل، کپی خواهد شد.از این فرآیند با نام <نخبه گرایی > نام برده می‌شود.

[.مهدی فهمیده غلامی.]

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


پس از تعیین سیستم کدینگ و مشخص شدن روش تبدیل هر جواب به کروموزوم، باید یک جمعیت اولیه از کروموزوم‌ها تولید نمود. در اکثر موارد، جمعیت اولیه به صورت تصادفی تولید می‌شود. اما گاهی اوقات برای بالا بردن سرعت و کیفیت الگوریتم از روش‌های ابتکاری نیز برای تولید جمعیت اولیه استفاده می‌گردد. در هر صورت عمومی‌ترین و راحت‌ترین روش، استفاه از یک رویکرد تصادفی می باشد .

اندازه جمعیت اولیه معمولاً به سایز رشته کدشده وابسته است. به عنوان مثال اگر کروموزوم ها
دریک مساله 32 بیتی هستند قطعاً باید جمعیت انتخابی اولیه بیشتر از حالتی باشد که کروموزوم ها
به عنوان مثال 16 بیتی هستند.

معمولا احتمال برش بین 80 تا 95 درصد
احتمال جهش بین نیم تا 1 درصد
و اندازه جمعیت بین 20تا 30
در نظر گرفته می‌شود.

آنگاه به کروموزوم ‌های انتخاب شده با توجه به یک تابع برازش ، مقداری حقیقی که نشاندهنده
ارزش آنها است تخصیص داده می‌شود و مراحل الگوریتمهای ژنتیک ادامه می‌یابد.

[Roshani]

یکی از بهترین روش های بهینه سازی مسایل مهندسی است که دارای مجموعه جوابهای ناپیوسته است ( مثل تعیین قطر لوله های آبرسانی در یک شبکه توضیع آب ) و در واقع قانون جنگل را شبیه سازی می کند. ( قویترین گونه از حیوانات ( که همان جوابها هستن ) باقی می مونن ) کدهای زیادی برای استفاده در اینترنت وجود دارد بهترین اوها GALIB است که توسط MIT تولید شده است.

[k.robot]

کمی اصلاحات:
نرخ آمیزش:0.4-0.8
نرخ جهش:0.01-0.2
تعداد کروموزومهای هر نسل:به فنوتایپ بستگی داره
ضمنا برنامه نویسی ژنتیکی با الگوریتم ژنتیکی فرق داره .برنامه نویسی ژنتیکی روی تکامل کدهای برنامه کار میکنه و از ساختار درخت برای کروموزومها استفاده میکنه.
هوش مصنوعی یکی از زیر شاخه هاش هوش محاسباتی که شامل شبکه عصبی و منطق فازی و پردازش تکاملی . الگوریتم ژنتیکی و برنامه نویسی ژنتیکی و استراتژی تکاملی و برنامه نویسی تکاملی زیر شاخه های پردازش تکاملی هستن.

[mohandese_hiclass]

[QUOTE=enio_enio_enio]سلام دوستان لطفا اگر متن فارسی در مورد ا لگوریتم ژنتیک د ارید بگذارید:تشویق:[/QUOTE

ببین این متن به دردت می خوره این یه تکه از مقاله ای که من به سمینار بین المللی patat فرستادم

[Sadegh_S]

من یه مطلب برای الگوریتم های ژنتیک و برنامه نویسی ژنتیک نوشتم که میتونی از طریق لینک زیر به اون دسترسی داشته باشید.
البته خواهش میکنم که هر جائی استفاده کردید، مرجع اون رو هم ذکر کنید، تا ما با امید بیشتری سعی کنیم که مطالب فارسی در این زمینه رو در اختیار دوستان قرار بدیم.
http://ce.aut.ac.ir/~soleimanpour

[mohandese_hiclass]

به سایت زیر هم سری بزنید مفیده
http://www.algorithmnevis.com/forum/index.php?board=5.0

[gelareh]

عموما در مسئله های زمانبندی یا در اصطلاح JobSHop Scheduling روش شبیه سازی تبرئیدی یا در اصطلاح simulated annealing کار نتیجه بهتری میدهد.
1. اولا مسئله بشدت بدرفتار است و با یستی به هر شکل حتی با دوری جستن از نخبه گرائی از بهینه محلی جلوگیری کرد. در چنین شرایطی با وجود یک چشم انداز برازندگی بد الگوریتم ژنتیک بهترین گزینه نیست.

[k.robot]

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

[ms1024]

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

Traveling Salesman Problem Using Genetic Algorithms
مساله فروشنده دوره گرد با استفاده از الگوریتم ژنتیک:
www.lalena.com/ai/tsp (http://www.lalena.com/ai/tsp)
اون پایین هم سورس کدش وجود داره
(به زبان Microsoft Visual Studio 2005 .NET 2.0 C# Project سلیس)

[Javadxp]

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

[Mamdos]

سلام

من خودم مسلط نیستم اما چیزی که فکر می‌کنم بدانم به طور خلاصه این است که برای مسأله‌ی مورد نظر ابتدا یک جواب پیشنهادی دلخواه یا تصادفی تولید می‌شود. سپس در این جواب چند «جهش» تصادفی به وجود می‌آوریم و از آن جواب‌های جدیدی تولید می‌کنیم. این جهش‌ها در واقع با اجرای یک تابع «جهش» روی این جواب ایجاد می‌شوند، و این تابع کارش این است که یک جواب را گرفته و در آن یک یا چند تغییر تصادفی محدود به وجود آورد.

مثلا فرض کنید می‌خواهیم در یک گراف نزدیک‌ترین مسیر از یک رأس مفروض یه یک رأس مفروض دیگر را پیدا کنیم. فاصله‌ی بین هر دو رأس متصل به هم طول یالی است که آن‌ها را به هم متصل می‌کند. در این‌جا یک تابع جهش می‌تواند این طور باشد که مسیر پیشنهادی اولیه را گرفته و «زیرمسیر» بین دو رأس تصادفی موجود در این مسیر پیشنهادی را با یک زیرمسیر تصادفی دیگر عوض کند و مسیر اصلی حاصل را بازگرداند. پس در این مثال ابتدا یک مسیر دلخواه یا تصادفی بین دو رأس ابتدا و انتها برمی‌گزینیم و سپس با چند بار اجرای تابع چهش روی این مسیر پیشنهادی، چند مسیر پیشنهادی دیگر به وجود می‌آیند که از ایجاد «جهش» روی مسیر اولیه ایجاد شده‌اند و کمی با آن تفاوت دارند؛ برخی از آن‌ها جواب‌های بهتر و مسیرهای کوتاه‌تری نسبت به مسیر پیشنهادی اولیه هستند و برخی مسیرهای طولانی‌تر.

یک تابع «شایستگی» هم وجود دارد که میزان شایستگی یک جواب تولید شده را ارزیابی کرده و مثلا به آن نمره می‌دهد. در مرحله‌ی بعد جواب‌های حاصل از جهش را به تابع شایستگی می‌دهیم و یکی از آن‌ها را که بهترین نمره را آورده‌ نگه می‌داریم و بقیه‌ی جواب‌ها را دور می‌ریزیم.

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

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

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

[saraarea]

سلام به همه

میخواستم بدونم کسی میتونه در مورد کاربرد های الگوریتم ژنتیک (مثل بهینه سازی و ...)به من اطلاعاتی بده واگه مطلب جدیدتری در مورد الگوریتم ژنتیک دارید(غیر از عملگرها ی آن ومطالبی که تا حالا نوشته اید) به من بده
باتشکر

[someCoder]

http://en.wikipedia.org/wiki/Genetic_algorithm#Applications

[zehs_sha]

http://www.shabakeh-mag.com/Articles/Show.aspx?n=1003006

[FatBabe]

از همهء دوستانی که تو این تاپیک تا حالا شرکت کردن ممنونم بابت سوالها و جوابهاشون. یه پیشنهاد دارم:
بیاین با هم این مطالبو بخونیم و بحث و سوال و جواب، تا بتونیم گروهی یاد بگیریم. هر کسی هم مطلب، لینک و ... داشت بذاره اینجا تا همه استفاده کنن. هر کی پایس بسم ال...

http://lancet.mit.edu/~mbwall/presentations/IntroToGAs
http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/tcw2/report.html
http://cs.felk.cvut.cz/~xobitko/ga
http://en.wikipedia.org/wiki/Genetic_algorithm
http://www.generation5.org/content/2000/ga.asp

[FatBabe]

یه کتاب میشناسم با همچین نامی:
رهیافتی نوین بر هوش مصنوعی؛ انتشارات ناقوس.
کتاب خوبیه برای شروع.
From Artificial Integligence to Artificial Life هم کتاب خوبیه pdf اش رو برات upload میکنم همینجا.
من خودم نظرم اینه که با یکی از راه حلای فعلی که توی AI مطرح هستن شروع کنی و بعد بری سراغ اصول کلیتر. مثلا با Artificial Neural Network و یا با Genetic Algorithm شروع کن. بعد برات اونقدر سوال مطرح میشه که هم ادامهء کار برات لذت بخشتره و هم اینکه سایر ایده ها برات جالب! وگرنه از اصول که شروع کنی کلافه میشی چون هیچ وقت کاربرد نهاییی رو ارائه نمیکنن، البته من ایتطور بودم دلیل نمیشه که ... ولی خوب.
اگه پیشنهادم رو قبول کردی با GA شروع کن با همی لینکهایی که گذاشتم میتونی شروع کنی ( و در ضمن فعلا دوتا کتاب بالا رو بی خیال شو ) اگه خواستی ادامه بدی نظراتت و سوالاتت رو همینجا بنویس تا شاید یه مقدار این تاپیک گرمتر بشه. هم دیگران استفاده میکنن و هم اینکه اگه تونستیم بهت کمک میکنیم.

[FatBabe]

سلام.
لینک زیر به نظرم به دو دلیل میتونه خوب باشه:
1) برای بررسی بنیانهای تشکیل دهندهء ایدهء GA.
2) اگه به Open-Ended Evolution علاقمندین هم برای بررسی زمینه های زیستی.

از امید ممنونم بابت این لینک:
http://oxygenws.com/blog/archives/50-.html

[aminpourazadeh]

فرق بین الگوریتم ژنتیک با برنامه ژنتیک چیه؟

[afabahar]

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

[presi13]

سلام

كسي روي الگوريتم ژنتيك كار كرده؟!


ميخوام ببينم چجوري ميشه فهميد جواب‌هاي الگوريتم ژنتيك به درد بخور هستند و حول و حوش نقطه بهينه قرار دارند؟!

در حالت كلي، چطور ميشه جواب‌هاي به دست اومده رو ارزش گذاري كرد؟! چطور ميشه از نرخ جهش، نرخ انتخاب و پارامترهايي مثل اين، كه براي الگوريتم ژنتيك انتخاب كرديم دفاع كرد؟!

[Mehdi_FT]

این مقاله رو مطالعه کن.
در کل مواردی که گفتی با توجه به مسئله و راه حل باید آزمایش بشه و به صورت کلی نمی شه نظر قطعی داد

[mjal146]

اگر ممکنه یه مثال خیلی ساده از الگوریتم ژنتیک بزنید (فروشنده و 8وزیر و مینیمم تابع نباشد) مثلا حل معادله درجه 2 با کدش به زبان سی یا یس پلاس پلاس:قلب:
خیلی لازم دارم:افسرده:

[gholipour94]

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