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

[امیرعلی بلورچیان]

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

پس دوستان من از فردا شب شروع میکنم شماهم .....

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

Genetic Algorithms

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

الگوریتم های ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیش بینی یا تطبیق الگو استفاده می کنند.الگوریتم های ژنتیک اغلب گزینه خوبی برای تکنیک های پیش بینی بر مبنای رگرسیون هستند.همان طور ساده،خطی وپارامتریک گفته می شود،به الگوریتم های ژنتیک می توان غیر پارامتریک گفت.
برای مثال اگر بخواهیم نوسانات قیمت نفت را با استفاده از عوامل خارجی وارزش رگرسیون خطی ساده مدل کنیم،این فرمول را تولید خواهیم کرد:قیمت نفت در زمان t=ضریب 1 نرخ بهره در زمان t+ضریب 2 نرخ بیکاری در زمان t+ثابت 1 . سپس از یک معیار برای پیدا کردن بهترین مجموعه ضرایب و ثابت ها جهت مدل کردن قیمت نفت استفاده خواهیم کرد.در این روش 2 نکته اساسی وجود دارد.اول این روش خطی است و مسئله دوم این است که ما به جای اینکه در میان "فضای پارامترها"جستجو کنیم ،پارامترهای مورد استفاده را مشخص کرده ایم.
با استفاده از الگوریتم های ژنتیک ما یک ابر فرمول یا طرح تنظیم می کنیم که چیزی شبیه"قیمت نفت در زمان t تابعی از حداکثر 4 متغیر است"را بیان می کند. سپس داده هایی برای گروهی از متغیرهای مختلف،شاید در حدود 20 متغیر فراهم خواهیم کرد.سپس الگوریتم ژنتیک اجرا خواهد شد که بهترین تابع و متغیرها را مورد جستجو قرار می دهد.روش کار الگوریتم ژنتیک به طور فریبنده ای ساده،خیلی قابل درک وبه طور قابل ملاحظه ای روشی است که ما معتقدیم حیوانات آنگونه تکامل یافته اند.هر فرمولی که از طرح داده شده بالا تبعیت کند فردی از جمعیت فرمول های ممکن تلقی می شود خیلی شبیه به این که بگوییم جرج بوش فردی از جمعیت انسان های ممکن است.
متغیر هایی که هر فرمول داده شده را مشخص می کنند به عنوان یکسری از اعداد نشان داده شده اند که معادل دی ان ای آن فرد را تشکیل می دهند.
موتور الگوریتم ژنتیک یک جمعیت آغاز از فرمول ایجاد می کند.هر فرد در برابر مجموعه ای از داده ها ی مورد آزمایش قرار می گیرند و مناسبترین آنها شاید 10 درصد از مناسبترین ها باقی می مانند.بقیه کنار گذاشته می شوند. مناسبترین افراد با هم جفتگیری (جابجایی عناصر دی ان ای)وتغییر(تغییر تصادفی عناصر دی ان ای) کرده اند.مشاهده می شود که با گذشت از میان تعدد ریادی از نسلها،الگوریتم ژنتیک به سمت ایجاد فرمول هایی که بیشتر دقیق هستند،میل می کنند.در حالی که شبکه های عصبی هم غیر خطی و غیر پارامتریک هستند،جذابیت زیاد الگوریتم های ژنتیک این است نتایج نهایی قابل ملاحظه ترند.فرمول نهایی برای کاربر انسانی قابل مشاهده خواهد بود،و برای ارائه سطح اطمینان نتایج می توان تکنیک های آماری متعارف رابر روی این فرمول ها اعمال کرد.فناوری الگوریتم های ژنتیک همواره در حال بهبود استفبرای مثال با مطرح کردن معادله ویروس ها که در کنار فرمول ها وبرای نقض کردن فرمول ها ی ضعیف تولید می شوندودر نتیجه جمعیت را کلاً قویتر می سازند.
مختصراً گفته می شود که الگوریتم ژنتیک (یا GA) یک تکنیک برنامه نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مسئله استفاده می کند.مسئله ای که باید حل شود ورودی است و راه حلها طبق یک الگو کد گذاری می شودومتریک که تابع fitness هم نام دارد هر راه حل کاندید را ارزیابی می کندکه اکثر آنها به صورت تصادفی انتخاب می شوند.

.........

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

الگوریتم ژنتیک GA یک تکنیک جستجو در علم کامپیوتربرای یافتن راه حل بهینه ومسائل جستجو است.الگوریتم های ژنتیک یکی از انواع الگوریتم های تکاملی اند که از علم زیست شناسی مثل وراثت، جهش،انتخاب ناگهانی ، انتخاب طبیعی و ترکیب الهام گرفته شده .
عموماً راه حلها به صورت 2 تایی 0و1 نشان داده می شوند ولی روشهای نمایش دیگری هم وجود دارد.تکامل از یک مجموعه کاملاً تصادفی از موجودیت ها شروع می شود و در نسلهای بعدی تکرار می شود.در هر نسل،مناسبترین ها انتخاب می شوند نه بهترین ها.
یک راه حل برای مسئله مورد نظر،با یک لیست از پارامترها نشان داده می شود که به آنها کروموزوم یا ژنوم می گویند.کروموزوم ها عموماً به صورت یک رشته ساده از داده ها نمایش داده می شوند،البته انواع ساختمان داده های دیگر هم می توانند مورد استفاده قرار گیرند.در ابتدا چندین مشخصه به صورت تصادفی برای ایجاد نسل اول تولید می شوند. در طول هر نسل ،هر مشخصه ارزیابی می شود وارزش تناسب(fitness) توسط تابع تناسب اندازه گیری می شود
گام بعدی ایجاد دومین نسل از جامعه است که بر پایه فرآیندهای انتخاب ،تولید از روی مشخصه های انتخاب شده با عملگرهای ژنتیکی است:اتصال کروموزوم ها به سر یکدیگر و تغییر.
برای هر فرد ،یک جفت والد انتخاب می شود.انتخابها به گونه ای اند که مناسبترین عناصر انتخاب شوند تا حتی ضعیفترین عناصر هم شانس انتخاب داشته باشند تا از نزدیک شدن به جواب محلی جلوگیری شود.چندین الگوی انتخاب وجود دارد: چرخ منگنه دار(رولت)،انتخاب مسابقه ای (Tournament) ،... .
معمولاً الگوریتم های ژنتیک یک عدد احتمال اتصال دارد که بین 0.6و1 است که احتمال به وجود آمدن فرزند را نشان می دهد.ارگانیسم ها با این احتمال با هم دوباره با هم ترکیب می شوند.اتصال 2 کروموزوم فرزند ایجاد می کند،که به نسل بعدی اضافه می شوند.این کارها انجام می شوند تا این که کاندیدهای مناسبی برای جواب،در نسل بعدی پیدا شوند. مرحله بعدی تغییر دادن فرزندان جدید است.الگوریتم های ژنتیک یک احتمال تغییر کوچک وثابت دارند که معمولاً درجه ای در حدود 0.01 یا کمتر دارد. بر اساس این احتمال ،کروموزوم های فرزند به طور تصادفی تغییر می کنند یا جهش می یابند.مخصوصاً با جهش بیتها در کروموزوم ساختمان داده مان.
این فرآیند باعث به وجود آمدن نسل جدیدی از کروموزوم ها یی می شود، که با نسل قبلی متفاوت است.کل فرآیند برای نسل بعدی هم تکرار می شود،جفتها برای ترکیب انتخاب می شوند،جمعیت نسل سوم به وجود می آیندو... .
این فرآیند تکرار می شود تا این که به آخرین مرحله برسیم.
شرایط خاتمه الگوریتم های ژنتیک عبارتند از:
• به تعداد ثابتی از نسل ها برسیم .
• بودجه اختصاص داده شده تمام شود(زمان محاسبه/پول).
• یک فرد(فرزند تولید شده) پیدا شود که مینیمم (کمترین)ملاک را برآورده کند.
• بیشترین درجه برازش فرزندان حاصل شود یا دیگر نتایج بهتری حاصل نشود.
• بازرسی دستی.
• ترکیبهای بالا.

توضیحی دیگر :
الگوریتم های ژنتیک قابلیت تبدیل فضای پیوسته به فضای گسسته را دارند. یکی از تفاوت های اصلی روش GA با روش های قدیمی بهینه سازی در این است که در GA با جمعیت یا مجموعه ای از نقاط در یک لحظه خاص کار میکنیم. در حالی که در روش های قدیمی بهینه سازی تنها برای یک نقطه خاص عمل میکردیم. این به این معنی است که GA تعداد زیادی از طرح ها را در یک زمان مورد پردازش قرار میدهد. نکته جالب دیگر این است که اصول GA بر پردازش تصادفی یا به تعبیر صحیحتر پردازش تصادفی هدایت شده (Guided Random) استوار است. بنابر این عملگرهای تصادفی فضای جستجو را را به صورت تطبیقی مورد بررسی قرار میدهند.
اصولا برای استفاده از GA باید سه مفهوم مهم زیر مشخص شوند :
* تعریف تابع هدف (Objective Function) یا تابع هزینه (Cost Function) .
* تعریف و پیاده سازی فضای ژنتیک (Genetic Representation) .
* تعریف و پیاده سازی عملگرهای GA .

خوب در این قسمت توضیحات کلی در باره مفاهیم داده شد.

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

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

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

همنطور که گفته شد ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژنآهاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزومآهای او به نسل بعدی منتقل میآشوند. هر ژن در این کروموزومآها نماینده یک خصوصیت است. بعنوان مثال ژن 1 میآتواند رنگ چشم باشد ، ژن 2 طول قد، ژن 3 رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمیآدهد. در واقع بصورت همزمان دو اتفاق برای کروموزومآها میآافتد. اتفاق اول موتاسیون (Mutation) است. موتاسیون به این صورت است که بعضی ژنآها بصورت کاملا تصادفی تغییر میآکنند. البته تعداد این گونه ژنآها بسیار کم میآباشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلا ژن رنگ چشم میآتواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوهآای بودهآاند. علاوه بر موتاسیون اتفاق دیگری که میآافتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به موتاسیون رخ میآدهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است. این مساله با نام Crossover شناخته میآشود. این همان چیزیست که مثلا باعث میآشود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری میآکند.
در ابتدا تعداد مشخصی از ورودی ها،X1,X2,…,Xn که متعلق به فضای نمونه X هستند را انتخاب می کنیم و آنها را در یک عدد بردای X=(x1,x2,…xn) نمایش می دهیم..در مهندسی نرم افزار اصطلاحاً به آنها ارگانیسم یا کروموزوم گفته می شود.به گروه کروموزوم ها Colony یا جمعیت می گوییم.در هر دوره Colony رشد می کند و بر اساس قوانین مشخصی که حاکی از تکامل زیستی است تکامل می یابند.
برای هر کروموزوم Xi ،ما یک ارزش تناسب(Fitness) داریم که آن را f(Xi) هم می نامیم.عناصر قویتر یا کروموزوم هایی که ارزش تناسب آنها به بهینه Colony نزدیکتر است شانس بیشتری برای زنده ماندن در طول دوره های دیگر و دوباره تولید شدن را دارند و ضعیفترها محکوم به نابودی اند. به عبارت دیگر الگوریتم ورودی هایی که به جواب بهینه نزدیکترندرانگه داشته واز بقیه صرف نظر می کند.
یک گام مهم دیگر درالگوریتم،تولد است که در هر دوره یکبار اتفاق می افتد. محتویات دو کروموزومی که در فرآیند تولید شرکت می کنند با هم ترکیب میشوند تا 2 کروموزوم جدید که ما انها را فرزند می نامیم ایجاد کنند.این هیوریستیک به ما اجازه می دهد تا 2 تا از بهترین ها را برای ایجاد یکی بهتر از آنها با هم ترکیب کنیم.(evolution) به علاوه در طول هر دوره،یک سری از کروموزوم ها ممکن است جهش یابند(Mutation) .

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

الگوریتم
هر ورودی x در یک عدد برداری X=(x1,x2,..,xn) قرار دارد .برای اجرای الگوریتم ژنتیک مان باید هر ورودی را به یک کروموزوم تبدیل کنیم.می توانیم این را با داشتن log(n) بیت برای هر عنصرو تبدیل ارزش Xi انجام دهیم مثل شکل زیر .


(X1, X2,…,Xn)= (123, 87,…, 63)

می توانیم از هر روش کد کردن برای اعداد استفاده کنیم.در دوره 0، یک دسته از ورودی های X را به صورت تصادفی انتخالب می کنیم.بعد برای هر دوره iام ما ارزش مقدار Fitness را تولید،تغییر وانتخاب را اعمال می کنیم.الگوریتم وقتی پایان می یابد که به معیارمان برسیم.

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

کد کردن مقادیر

بر اساس تعریف Holland روش های متعددی برای نمایش ژن های منفرد وجود دارد. مثلا میتوان آنها را به صورت رشته (String) ، آرایه ، درخت یا لیست نشان داد که قصد داریم آنهارا به صورت رشته های بیتی مورد بررسی قرار دهیم.

1- کد مبنای دو (Binary)
مثال : کوله پشتی
در این مثاله فرض میکنیم که اشیایی با مقدار و اندازه مشخص وجود دارد و بخواهیم آنها را در یک کوله پشتی با ظرفیت مشخص قرار دهیم. نحوه انتخاب اشیا با توجه به حداقل فضایی که اشغال می کنند و استفاده بهینه از فضای کوله پشتی صورت میگیرد.
برای حل مساله فرض میکنیم هر بیت بیانگر حضور یا عدم حضور اشیا در کوله پشتی باشد. روش کد مبنای دو از روش های متداول در حل مسائل GA به شمار می آیند.

Chromosome A 101101100011
Choromosome B 010011001100

اصولا روش کد مبنای دو امکان تولید کروموزوم های بسیاری را با حداقل بیت ها فراهم میکند. لذا این روش کدگذاری در مسائل واقعی باید همراه با اصلاحاتی بعد از اعمال عملگرهای ژنتیکی صورت گیرد.

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

2- روش کدگذاری جایگشتی (Permutation Encoding)

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

Chromosome A 1 5 3 2 4 7 9 8 6
Choromosome B 8 5 6 7 2 3 1 4 9

3- روش کد گذاری مقدار (Value Encoding)

در این روش هر کروموزوم به صورت رشته ای از مقادیر است که این مقادیر می توانن هرچیز مرتبط با مساله باشند . مثلا اعداد اعشاری و یا اشیا کد شده که در جدول زیر مثالی از این روش نشان داده شده است

Chromosome A 1.254 2.364 9.245 3.0058
Choromosome B dfgtrgfdbynynh j
Choromosome C right left back

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

4- روش کدگذاری درختی (Tree Encoding)

یک روش دیگر که توسط John Koza توسعه یافت،برنامه نویسی ژنتیک (Genetic programming)است.که برنامه ها را به عنوان شاخه های داده در ساختار درخت نشان می دهد.در این روش تغییرات تصادفی می توانند با عوض کردن عملگرها یا تغییر دادن ارزش یک گره داده شده در درخت،یا عوض کردن یک زیر درخت با دیگری به وجود آیند.

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

روش های انتخاب

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

انتخاب Elitist :مناسبترین عضو هر اجتماع انتخاب می شود.

انتخاب Roulette : یک روش انتخاب است که در آن عنصری که عدد برازش(تناسب)بیشتری داشته باشد،انتخاب می شود.

انتخاب Scaling :به موازات افزایش متوسط عدد برازش جامعه،سنگینی انتخاب هم بیشتر می شودوجزئی تر.این روش وقتی کاربرد دارد که مجموعه دارای عناصری باشد که عدد برازش بزرگی دارند وفقط تفاوت های کوچکی آنها را از هم تفکیک می کند.

انتخاب Tournament : یک زیر مجموعه از صفات یک جامعه انتخاب می شوندواعضای آن مجموعه با هم رقابت می کنندو سرانجام فقط یک صفت از هر زیر گروه برای تولید انتخاب می شوند.

بعضی از روشهای دیگر عبارتند از:Rank Selection, Generational Selection, Steady-State Selection .Hierarchical Selection

[امیرعلی بلورچیان]

پاسخ : الگریتم های ژنتیک

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

لینک دانلود: :nerd:

http://dlc.eca.ir/index.php?act=view&id=94

اگر نظری برای ادئامه کار داشتید بگین وگرنه تا همینجا کار تموم میشه !

[stranger]

پاسخ : الگریتم های ژنتیک

این که بعد از هر نسل mution و crossover داریم و می شه بستر توضیح بدی ...
و این که GA tools Matlab خیلی بده ... می شه یه مسله ساده حل کنی ؟ مثلا xay = 20 که x و y integer و a یه اپریشن + - / * باشه مثلا ... یا هر چی که فک می کنی خوبه ... در ضمن ایول

[makhmali22]

پاسخ : الگریتم های ژنتیک

مطلب : www.electromatlab.com

[ghazivakili]

پاسخ : الگریتم های ژنتیک

اگر بخواهیم این مثال را در Matlab پیاده سازی کنیم باید چیکار کنیم.
مثال اگر بخواهیم نوسانات قیمت نفت را با استفاده از عوامل خارجی وارزش رگرسیون خطی ساده مدل کنیم،این فرمول را تولید خواهیم کرد:قیمت نفت در زمان t=ضریب 1 نرخ بهره در زمان t+ضریب 2 نرخ بیکاری در زمان t+ثابت 1 . سپس از یک معیار برای پیدا کردن بهترین مجموعه ضرایب و ثابت ها جهت مدل کردن قیمت نفت استفاده خواهیم کرد.در این روش 2 نکته اساسی وجود دارد.اول این روش خطی است و مسئله دوم این است که ما به جای اینکه در میان "فضای پارامترها"جستجو کنیم ،پارامترهای مورد استفاده را مشخص کرده ایم.