کلیدستان

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

دستور ga در متلب ، برای یافتن مقدار بهینه یک تابع (یک مسئله) بر اساس الگوریتم بهینه سازی ژنتیک به کار می رود .

یعنی متلب کدهایه اماده داره برا نوشتن ؟ فقط مسئلمونو وارد می کنیم؟
اگه هست راهنمایی می کنین چون من رشته ام برق نیست چیزی درمورد اون بهمون یاد ندادن
مرسی

برای یادگیری ، ابتدا در help متلب ، عبارت ga را جستجو کنید و اولین صفحه نمایش داده شده رو بخونید .
برای اطلاعات بیشتر ، این بار در help متلب ، عبارت Genetic Algorithm Examples را جستجو کنید که در اولین صفحه ، لینک هایی نمایش داده می شود که مفید هستند و مثال هایی نیز ارائه شده است .

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

بستگی به اون مسئله ریاضی داره .
یک مثال ساده بزنید تا بگم تابع هزینه اون چی میشه.

مثلا محاسبه معادلات درجه 2

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

مرسی ولی کامل متوجه نشدم

کدوم قسمت رو متوجه نشدید ؟

معادله درجه 2 . 3 جواب داره <=> .فقط جواب صفر رو بررسی می کنیم؟

معادله درجه 2 ، تنها 2 جواب داره .
بگذارید مثال براتون بزنم . معادله زیر رو ببینید :


ابتدا تمامی جملات غیر صفر رو به یک سمت می بریم :


اکنون تابع هزینه را به صورت زیر در نظر می گیریم :


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

ممنون بازم اگه در طول ترم سوال داشتم این بحث و ادامه میدیم
خیلی ممنونم .موفق باشین

ببخشید یه سوال دیگه چه جوری برای مسئله رنگ امیزی گراف تابع هزینه می تونم بنویسم؟

لطفا در مورد این مسئله، کمی توضیح بدید .

مي خواهيم در يك گراف همه گره ها را بگونه اي رنگ آميزي کنيم که هيچ دو گره
مجاوري يك رنگ نباشند ضمن اينكه کمترين رنگ را به کار برده باشيم .

شاید افراد مختلف ، پیشنهاد های مختلفی بدهند ، اما من این مورد به ذهنم رسید :
در این مسئله ، هر فرد نسل (هر جواب) ، آرایه ای از رنگ های تعیین شده برای هر گره است . در گراف ، مشخص است که کدام گره ها به یکدیگر متصل شده اند (مجاورند) ، بنابراین پس از مشخص شدن جواب ، باید تمامی خطوط بین گره ها را بررسی کنیم . تابع هزینه را برای آن جواب ، ابتدا صفر می گیریم سپس هر خط را که بررسی کردیم و دو گره دو سر آن خط ، هم رنگ بودند آنگاه یک واحد به تابع هزینه اضافه می کنیم . در آخر نیز تعداد رنگ به کار رفته را با این عدد جمع می کنیم .
مثلا برای یک جواب پیشنهادی برای رنگ گره ها ، فرض کنید تمامی خطوط گراف را بررسی کردیم و مشاهده کردیم که 4 خط وجود دارد که دو گره دو سر آنها ، هم رنگ می باشند و از 3 رنگ هم استفاده شده است . بنابراین برای این جواب ، تابع هزینه برابر 7 خواهد بود (جمع 4 و 3) .
بنابراین هر چه تابع هزینه یک جواب کمتر باشد ، آن جواب بهتر است .
البته می توان برای دو قسمت ((عدم هم رنگ بودن گره های مجاور)) و ((کمترین تعداد رنگ)) ، ضرایبی را تعیین کرد که ابتدا در آنها ضرب شده و سپس جمع شوند . این ضرایب می تواند پس از اجرای برنامه و بر حسب تجربه تعیین شود .

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

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

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

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

ببخشید یه سوال دیگه شما تو اولین مثالتون یه فروشنده دوره گردو مثال زدین که از همه شهرها می گذاره و گفتین تابع هزینه شو می تونیم با جمع ساده بدست بیاریم حال اگه ما بخوایم این مسئله رو یکم عوض کنیم مثلا این که بگیم از شهرهایی که عدد زوج دارن بگذره یا اینکه یه عدد به عنوان شهر مبدا بدیم و بگیم از اون عدد به بعد بررسی کنه یا برعکس اونوقت تابع هزینه اینو چه جوری می تونیم بدست بیاریم؟می تونم خواهش کنم همراه با مثال این سوالو توضیح بدین ممنون

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

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

بستگی داره برنامه رو چجوری نوشته باشید .
ببینید در کدوم مرحله از برنامه ، تولید جواب های نسل بعد صورت میگیره (یا تولید جواب های اولیه) ، سپس محدودیت ها رو اونجا بگذارید .

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

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

سلام ، من باید به برنامه ای رو بنویسم تا آخر هفته به استاد تحویل بدم میشه لطفا کمکمممممممممم کنین
صورت سوال اینه که : با استفاده از الگوریتم ژنتیک xوy را به گونه ای پیدا کنید که تابع sin(x+y2    مقدارش max شود .  
x  نه بیت است و y پنح بیت.  

سلام دوستان
برای اون مثال فروشنده دوره گرد اگه تعداد شهرها 10 تا باشه و فاصله شهرها ماتریس d باشه؛چطوری میشه حلش کرد؟
d=[0   445   631   516   389   404   649   310   232   277;445     0   614   545   491   604   706   340   159   252;631   614     0   246   635   341   496   483   621   496;516   545   246     0   687   475   316   582   616   949;389   491   635   687     0   583   776   599   622   443;404   604   341   475   583     0   567   545   429   468;649   706   496   316   776   567     0   734   378   529;310   340   483   582   599   545   734     0   437   478;232   159   621   616   622   429   378   437     0   520;277   252   496   949   443   468   529   478   520     0]