انجمنصفحه اولجستجوی انجمن

[sina_bhh]

با سلام

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

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

ولی مقاله نتایج رو بدست آورده بود و با بقیه الگوریتمها مقایسه کرده بود و نتیجه بهتری هم داشت.

یعنی توی مقاله ژورنالی تا این حد اشتباه میشه ؟؟ (منظورم یک کلمه و جمله نیست.یک قسمت کامل که مربوط به اپراتور cross over میشه)
چطوری با این اشتباه accept شده ؟؟ مگه مقاله هایی که فرستاده میشن بررسی نمیشن ؟؟

مقاله مربوط به سال ۲۰۱۱ هستش و اسم ژورنال هم Expert Systems with Applications هستش

[admin]

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

[parsaNA]

میشه مقاله رو آپلود کنین یا لینک دانلودشو بدین یا حداقل اون Cross over رو نشون بدید ؟ خیلی عجیبه ولی هر ژورنالی هم معتبر نیست . وقتی با یه نرم افزار تولید کننده مقاله !!! بچه های شریف موفق شدند از چندین نشریه پذیرش چاپ مقاله بگیرند معلوم میشه که خیلی از این ژورنال‌ها الکیه !

[luna]

این ژورنالشو من چک کردم رتبه B داره! پس احتمالا نباید ژورنال بدی باشه! ولی خوب اشتباه هست دیگه! یه بار یکی از دوستام یه مقاله از یه کنفرانس معتبر رو می گفت دو تا شکل داشته که همه مقایسه‌ها روی اون دو تا شکل انجام شده بوده! ولی دو تا شکل یکی بوده! حالا این که اشتباه ویرایشی بوده احتمالا ولی کسی‌ام نفهمیده! ولی خوب خیلیام از بی دقتی داورا استفاده می کنن دیگه!

[inteligentium]

(۰۳ بهمن ۱۳۹۰ ۰۵:۲۳ ب.ظ)luna نوشته شده توسط:  این ژورنالشو من چک کردم رتبه B داره!...

ببخشید رنکینگ ژورنال رو از کدوم سایت درآوردین؟

[luna]

رتبه بندی ERA

[Br2012]

منکر وجود اشتباه نیستم اما معمولا اشتباه کم پیش میاد ،اونم تو جورنالی که Elsevier باشه به هر حال داورهای قوی اونا رو تائید کردن و اینکه شما با یه مثال ساده پی به اشتباه بردید جای سواله

[luna]

البته اینکه Elsevier باشه صرفا به این معنا نیست که ژورنال خوبیه! رنک خود ژورنال مهمه!

[pos]

شما می توانی همین اشتباه را با ارائه یک راه حل مقاله کنیا. من شنیدم اینطور مقالات که ایراد یک مقاله دیگر را می گیره و یک راه حل را نشان میده بهتر accept میشن. به قول یکی از استادهامون خیلی وقت‌ها روی این تکیه می کنند که شما یک ایده جدید را ارائه دادین و برای ایده ارزش قائل میشن.

[sina_bhh]

ممنون از دوستان که جواب دادید.

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

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

مقاله به این صورته:

مساله در مورد Traveling Salesman Problem (مساله فروشنده دوره گرد) هستش.همونطور که میدونید وقتی این مساله با ژنتیک حل میشه کرومزوم به صورت جایگشتی از اعداد هستش(وجود جایگشت از اعداد تکراری در کرومزوم جلوگیری میکنه).
حالا برای عمل Cross over دو نوع رو در نظر گرفته بود که با یک احتمالی یکی از این دو تا رو انتخاب می کرد.یکی از اون Cross over‌ها به صورت Two Point Cross over استفاده کرده.
(خب چیزی که معلومه که Two point Cross over برای TSP اعداد تکراری تولید میکنه)

اون قسمت از مقاله رو که مربوط به اینه رو اینجا میارم.

If the random number r generated by the system is smaller than R0, then the system performs the two-point crossover operation. The system randomly generates two crossover points. Then, exchange the genes between the crossover points

فقط این رو هم بگم که R0 یک مقدار از پیش تعریف شده و بین ۰ و ۱ هستش(توی مقاله ۰/۳۳ هستش). r هم در هر مرحله توسط سیستم تولید میشه و بین ۰ و ۱ هستش

[parsaNA]

نه دوست عزیز . Cross Over غلط نیست . البته حرف شما درسته که میگین با این روش اعداد تکراری تولید میشه‌، اما تو الگوریتم ژنتیک خیلی از مسایل هستند که کروموزومشون یه جایگشته مثل مساله هشت وزیر‌، فروشنده دوره گرد و ... / تو همه اینها Cross Over باید طوری باشه که نسل تولید شده ژن تکراری نداشته باشه . اما پس از اعمال این عملگر با احتمال بالایی این اتفاق می افته( یعنی تولید ژن تکراری ).

نکته اینجاست که از بس این مشکل ساده حل میشه‌، دیگه نویسنده این مقاله نخاسته به خودش زحمت بده و روش حل مشکل رو که تکراری هستش بگه ‌، چون که تو همه مقاله های ژنتیک بحث شده . احتمال زیاد خودتم می دونی اما اگه نمی دونی من اینجا یه مثال می زنم . فرض کن دو تا جایگشت داشته باشیم:

۶ ۷/ ۸ ۳ ۴ ۵ ۱ ۲ ۹
۲ ۴/ ۸ ۶ ۱ ۹ ۷ ۳ ۵

فرض کن میخام Single Point Cross over بزنم از همون جایی که / گذاشتم . حالا دو تا کروموزوم زیر تولید میشه:

۲ ۴/ ۸ ۳ ۴ ۵ ۱ ۲ ۹
۶ ۷/ ۸ ۶ ۱ ۹ ۷ ۳ ۵

حالا اون ژنهایی که سبزرنگه تکراری شده . با یه تکنیک خیلی ساده این ناسازگاری حذف میشه‌، اون هم این که دو تا ژن تکراری بالا رو با پایین عوض کنیم . حالا به هر ترتیب دلخواه پس کروموزوم های تولید شده ایناست:

۲ ۴/ ۸ ۳ ۶ ۵ ۱ ۷ ۹
۶ ۷/ ۸ ۴ ۱ ۹ ۲ ۳ ۵

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

[sina_bhh]

(۰۳ بهمن ۱۳۹۰ ۱۱:۴۱ ب.ظ)parsaNA نوشته شده توسط:  

نه دوست عزیز . Cross Over غلط نیست . البته حرف شما درسته که میگین با این روش اعداد تکراری تولید میشه‌، اما تو الگوریتم ژنتیک خیلی از مسایل هستند که کروموزومشون یه جایگشته مثل مساله هشت وزیر‌، فروشنده دوره گرد و ... / تو همه اینها Cross Over باید طوری باشه که نسل تولید شده ژن تکراری نداشته باشه . اما پس از اعمال این عملگر با احتمال بالایی این اتفاق می افته( یعنی تولید ژن تکراری ).

نکته اینجاست که از بس این مشکل ساده حل میشه‌، دیگه نویسنده این مقاله نخاسته به خودش زحمت بده و روش حل مشکل رو که تکراری هستش بگه ‌، چون که تو همه مقاله های ژنتیک بحث شده . احتمال زیاد خودتم می دونی اما اگه نمی دونی من اینجا یه مثال می زنم . فرض کن دو تا جایگشت داشته باشیم:

۶ ۷/ ۸ ۳ ۴ ۵ ۱ ۲ ۹
۲ ۴/ ۸ ۶ ۱ ۹ ۷ ۳ ۵

فرض کن میخام Single Point Cross over بزنم از همون جایی که / گذاشتم . حالا دو تا کروموزوم زیر تولید میشه:

۲ ۴/ ۸ ۳ ۴ ۵ ۱ ۲ ۹
۶ ۷/ ۸ ۶ ۱ ۹ ۷ ۳ ۵

حالا اون ژنهایی که سبزرنگه تکراری شده . با یه تکنیک خیلی ساده این ناسازگاری حذف میشه‌، اون هم این که دو تا ژن تکراری بالا رو با پایین عوض کنیم . حالا به هر ترتیب دلخواه پس کروموزوم های تولید شده ایناست:

۲ ۴/ ۸ ۳ ۶ ۵ ۱ ۷ ۹
۶ ۷/ ۸ ۴ ۱ ۹ ۲ ۳ ۵

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

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

اینکه چطوری یک کرومزوم بازنمایی بشه خودش یکسری محدودیت میتونه ایجاد میکنه.همین هشت وزیر که مثال زدید نحوه بازنمایی ما میتونه باعث بشه یک وزیر در یک سطر یا یک ستون قرار نگیره(همون استفاده از جایگشت) ولی این نوع بازنمایی باعث میشه که وزیرها به صورت قطری همدیگر رو تهدید کنن.این مساله از نوع Decision هستش و تابع هدف نداره.پس Fitness متناسب با پنالتی هستش.

ولی توی مساله TSP این مکانیزمی که شما میگید درست و من مشکلی باهاش ندارم.منظورم اینه که وقتی از این بازنمایی استفاده میشه برای اینه که عدد تکراری تولید نشه و متناسب با این بازنمایی هستش که Cross over تعریف میشه.ولی توی مقاله ذکر نشده که از مکانیزم Repaire (همین کاری که شما انجام دادید)استفاده شده.

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

[parsaNA]

یعنی شما میفرمایید میشه Cross over ای زد که سازگاری حفظ بشه ؟ من بعید می دونم متدی براش وجود داشته باشه که برای همه کروموزوم‌ها جواب بده / واسه همینه که چاره ای جز Repair وجود نداره !

[sina_bhh]

(۰۴ بهمن ۱۳۹۰ ۱۲:۴۲ ق.ظ)parsaNA نوشته شده توسط:  یعنی شما میفرمایید میشه Cross over ای زد که سازگاری حفظ بشه ؟ من بعید می دونم متدی براش وجود داشته باشه که برای همه کروموزوم‌ها جواب بده / واسه همینه که چاره ای جز Repair وجود نداره !

سعی میشه با هر بازنمایی Cross over و Mutation متناسب با اون تعریف بشه.مثلا برای عدد صحیح یا اعداد دودویی یا اعداد اعشاری و .... برای هر بازنمایی یک Cross over و Mutation استفاده میشه.
من نمیگم.کلی Cross over مختص به جایگشت وجود داره.شما خودتون میدونید ولی من چند تاشو میگم:
۱- Partially Mapped Cross over
۲- Edge Cross over
۳- Order Cross over
۴- Cycle Cross over

مثلا برای Order Cross over‌:
فرض کنید که دو کرومزوم زیر رو در نظر بگیرید‌:

۹ ۸ / ۷ ۶ ۵ ۴ / ۳ ۲ ۱

۴ ۱ / ۵ ۶ ۲ ۸ / ۷ ۳ ۹

دو نقطه به طور تصادفی انتخاب میشه(فرض کنید که دو / اون دو نقطه هستش)
حالا بین دو / بدون تغییر در فرزندان کپی میشه .فرض کن میخوایم فرزند اول رو ابتدا ایجاد کنیم.از نقطه دوم(دومین /) که انتخاب شده از والد دوم شروع میکنیم.و به سمت راست حرکت میکنیم(اگر به انتها رسیدیم به اولین ژن برمیگردیم . یعنی فرض کنید که اول و آخرش به هم وصله).اعدادی که در والد دوم هستش رو یکی یکی بررسی میکنیم (تا دوباره به قسمت دوم / برسیم)و اگر در والد اول (منظور بین دو / هستش که قبلا بدون تغییر کپی شده)وجود نداشت در فرزنداول جایگذای میکنیم.در غیر اینصورت رد میشیم.دومین فرزند هم همینطور ایجاد میکنیم
نتیجه به این صورت میشه:

۹ ۱ ۷ ۶ ۵ ۴ ۲ ۸ ۳

۱ ۹ ۵ ۶ ۲ ۸ ۷ ۴ ۳

[parsaNA]

بله من منظورم Cross over ای بود که فقط به صورت تصادفی ترکیب کنه و تکرار هم تولید نشه . این روش‌ها هم به نوعی برای اینکه تکرار تولید نشه دارند توی repair کردن پیش دستی می کنند( چون می دونند که به احتمال زیاد تکرار تولید میشه ). بله روشهای این چنینی زیادند و اونی هم که من عرض کردم ساده ترینشه . مرسی