Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > مقدمات هوش مصنوعی > حل مسائل معروف هوش مصنوعي


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۰۱-۲۳-۱۳۹۲, ۱۱:۰۸ قبل از ظهر   #21 (لینک دائم)
عضو جدید
 
آواتار shima3000
 
تاريخ عضويت: فروردين ۱۳۹۲
پست ها: 2
تشكرها: 0
1 تشكر در 1 پست
پيش فرض

سلام

حل مسئله کوله پشتی با الگوریتم تپه نوردی میخاستم!!

ممنون میشم اینم در کنار بقیه الگوریتما قرار بدین!
shima3000 آفلاين است   پاسخ با نقل قول
از shima3000 تشكر كرده است:
shayan_h (۰۲-۲۴-۱۳۹۲)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۰۵-۲۶-۱۳۹۲, ۰۲:۴۰ بعد از ظهر   #22 (لینک دائم)
عضو جدید
 
آواتار روحي
 
تاريخ عضويت: مرداد ۱۳۹۲
پست ها: 1
تشكرها: 1
0 تشكر در 0 پست
Wink

مطالب جالب و مفيد بود
متشكرم
روحي آفلاين است   پاسخ با نقل قول
قديمي ۰۵-۲۸-۱۳۹۲, ۰۵:۵۷ بعد از ظهر   #23 (لینک دائم)
عضو فوق فعال
 
آواتار masood
 
تاريخ عضويت: خرداد ۱۳۸۸
محل سكونت: اسالم
پست ها: 98
تشكرها: 291
37 تشكر در 30 پست
My Mood: Khoshhal
ارسال پيغام Yahoo به masood
پيش فرض

نقل قول:
نوشته اصلي بوسيله hadiabc نمايش پست
متاسفانه دیگه این وبلاگ در دسترس نیست.
__________________
یک روز یک ماشین برای انتخابات ریاست جمهوری ثبت نام می کند
چه بخواهیم چه نخواهیم این اتفاق می افتد.
masood آفلاين است   پاسخ با نقل قول
قديمي ۱۰-۲۷-۱۳۹۲, ۱۲:۳۰ بعد از ظهر   #24 (لینک دائم)
عضو جدید
 
آواتار srainy
 
تاريخ عضويت: دي ۱۳۹۲
پست ها: 1
تشكرها: 0
0 تشكر در 0 پست
Exclamation کوله پشتی صفرویک

سلام
دوستان کسی پروژه پیاده سازی الگوریتم های حریصانه و پویا برای کوله پشتی صفر و یک رو اگه با سی شارپ لطفا ضمیمه کنه + مقایسه پیچیدگی زمانی این دو روش
srainy آفلاين است   پاسخ با نقل قول
قديمي ۱۱-۱-۱۳۹۲, ۰۹:۲۱ قبل از ظهر   #25 (لینک دائم)
عضو جدید
 
آواتار helmaa
 
تاريخ عضويت: آذر ۱۳۹۲
پست ها: 1
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

سلام خواهش می کنم اگر کسی میتونه کد الگوریتم ژنتیک این مسٔله رو توضیح بده بد جوری نیاز دارم ممنون
helmaa آفلاين است   پاسخ با نقل قول
قديمي ۰۲-۹-۱۳۹۳, ۰۸:۲۵ بعد از ظهر   #26 (لینک دائم)
عضو جدید
 
آواتار serendpt
 
تاريخ عضويت: ارديبهشت ۱۳۹۳
پست ها: 1
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

دوستان میشه بگید الگوریتم حل این سوال چی هست؟
In the 0-1 Multiple Knapsack Problem (MKP) a set of n items and a set of m knapsacks (with m  n)
are given. With each item j (j = 1; : : : ; n) are associated a pro t pj 2 Z+ and a weight wj (we assume
wj 2 Z+). A capacity ci 2 Z+ is associated with each knapsack i (i = 1; : : : ;m). The goal is to select
is to select m disjoint subsets of items so that the total pro t of the selected items is maximum and
each subset can be assigned to a dierent knapsack whose capacity is no less than the total weight of
the items in the subset.

Develop a heuristic algorithm based on the Lagrangian relaxation of constraints
serendpt آفلاين است   پاسخ با نقل قول
قديمي ۰۲-۱۴-۱۳۹۳, ۰۵:۰۶ قبل از ظهر   #27 (لینک دائم)
عضو جدید
 
آواتار عماریاسر
 
تاريخ عضويت: ارديبهشت ۱۳۹۳
پست ها: 3
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

باسلام لطفا" مقاله در مورد الگوریتم های فرا ابتکاری که در اون مثال کوله پشتی را از روش مورچگان وجستجوی ممنوع وژنتیک حل شده باشه برام ایمیل کنید تا24 ساعت آینده.باتشکر
عماریاسر آفلاين است   پاسخ با نقل قول
قديمي ۰۲-۱۷-۱۳۹۳, ۰۳:۳۳ قبل از ظهر   #28 (لینک دائم)
عضو جدید
 
آواتار helen11
 
تاريخ عضويت: ارديبهشت ۱۳۹۳
پست ها: 1
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

سلام
لطفا کد الگوریتم کوله پشتی و 8 وزیر با شبکه هاپفیلددرمتلب
helen11 آفلاين است   پاسخ با نقل قول
قديمي ۰۹-۲۱-۱۳۹۶, ۰۸:۲۸ بعد از ظهر   #29 (لینک دائم)
عضو فعال
 
آواتار site2017
 
تاريخ عضويت: مهر ۱۳۹۶
پست ها: 10
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

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

الگوریتم
این مسئله یکی از پایه‌ای‌ترین مسائل برنامه‌ریزی پویا است و صورت‌های مختلفی دارد که در انتها به آن‌ها و ایده‌ی اثبات‌شان اشاره می‌شود.
برای حل مدل ساده‌ی سوال، یک آرایه دوبعدی به نام dd به ابعاد(n+1)×(W+1)(n+1)×(W+1) را در نظر بگیرید که در آن nn تعداد وسایل مختلفی که می‌توانیم در کوله‌پشتی بگذاریم وWW حجم کوله‌پشتی است.
مقدارdi,jdi,j برابر یک است اگر و تنها اگر بتوان فقط با استفاده از ii وسیله‌ی اول، دقیقا حجم jj از کوله‌پشتی را پر کرد. یعنی یک زیرمجموعه‌ از ii عضو اول وجود دارد که مجموع وزن‌شان jj است. در غیر اینصورت، مقدارش برابر صفر است.
جواب مسئله بزرگترین اندیس jj است که dn,jdn,j برابر یک باشد.
مقداردهی اولیه: با استفاده از ۰۰ وسیله‌ی اول (استفاده نکردن از وسایل) فقط می‌توان حجم ۰۰ را تولید کرد (کوله‌پشتی خالی) پس تمام خانه‌های به صورت d0,jd0,j برابر صفر اند به جز d0,0d0,0 که برابر ۱۱ است.
به روز رسانی: برای به دست آوردن di,jdi,j دو حالت وجود دارد این که خود وسیله‌ی ii ام در کوله‌پشتی نباشد که در این صورت باید برای این که مقدار یک شود، مقدار di−1,jdi−1,j برابر ۱۱ باشد. حالت دیگر این است که خود وسیله در کوله پشتی باشد. پس در این حالت مقدار در صورتی یک می‌شود که (مقدار حجم وسیله‌ی ii ام را aiai بگیریم) di−۱,j−aidi−۱,j−ai با فرض j≥aij≥ai برابر یک باشد.
شبه کد:

d = {0}
d[0][0] = 1

for i from 1 to n
for j from 0 to W
d[i][j] = d[i-1][j]
if j >= a[i] and d[i-1][j-a[i]] == 1
d[i][j] = 1
اگر دقت کنید می‌بینید احتیاج خاصی به نگه داشتن یک آرایه‌ی دوبعدی نداریم چون برای محاسبه‌ی هر ستون، فقط به ستون قبلی احتیاج داریم و فقط باید ۲ ستون را نگه‌داریم. اما حتی می‌توانیم از این هم جلوتر برویم و فقط یک ستون داشته باشیم. اما در اینجا باید حواس‌مان باشد که اشتباه زیر را انجام ندهیم.
شبه کد با آرایه‌ی یک بعدی (اشتباه):

d = {0}
d[0] = 1

for i from 1 to n
for j from 0 to W
if j >= a[i] and d[j-a[i]] == 1
d[j] = 1
کد بالا یک مشکل دارد. به نظرتان مشکلش چیست؟
فرض کنید در فقط یک وسیله داریم مثلا با حجم ۲ واحد و حجم کوله‌پشتی برابر ۴ است. پس فقط می‌توان ۲ واحد از کوله‌پشتی را پر کرد. اما اگر شبه کد بالا را برای آن اجرا کنید، می‌بینید که مقدار d4d4 برابر یک است. چون با استفاده از وسیله‌ی اول که حجم دو واحد داشت، مقدار d2d2 را یک کردیم، اما بعد از این متوقف نشدیم بلکه چون مقدار d2d2 برابر یک بود، مقدار d4d4 را نیز برابر یک قرار دادیم. پس انگار بیش از یک وسیله با حجم دو داشتیم. در واقع این کد جواب مسئله‌ی دیگری به نام خرد کردن پول است که در آن به تعداد نامتناهی از هر کدام از وسایل داریم.
حال بیایید سعی کنیم مشکل کد بالا را حل کنیم. مشکل این بود که اول با استفاده از وسیله‌ی اول (یا بقیه‌ی وسایل) مقدار خانه‌های پایین جدول را به روز رسانی کردیم و سپس دوباره با استفاده از همان وسیله، مقادیر خانه‌های بالاتر را نیز به روز رسانی کردیم. چطور می‌شود اگر خانه‌ها را به ترتیب دیگری پیمایش کنیم تا این مشکل پیش نیاید؟ حجم وسایل که نمی‌تواند منفی باشد. پس اگر بالا به پایین آرایه را به روز رسانی کنیم، این مشکل پیش نمی‌آید. خودتان هم کمی فکر کنید که چرا این روش درست است.
بر همین اساس کد را تغییر می‌دهیم. شبه کد با آرایه‌ی یک بعدی (درست):

d = {0}
d[0] = 1

for i from 1 to n
for j from W to 0
if j >= a[i] and d[j-a[i]]
d[j] = 1
پیچیدگی‌ الگوریتم
پیچیدگی زمانی که در تمام حالت‌ها از O(n×W)O(n×W) است. مقدار حافظه‌ی مورد نیاز نیز O(W)O(W) است.

ساخت سايت
site2017 آفلاين است   پاسخ با نقل قول
قديمي ۱۱-۹-۱۳۹۶, ۰۳:۰۶ قبل از ظهر   #30 (لینک دائم)
عضو فعال
 
آواتار site2017
 
تاريخ عضويت: مهر ۱۳۹۶
پست ها: 10
تشكرها: 0
0 تشكر در 0 پست
پيش فرض

پیاده سازی الگوریتم ۸ وزیر با استفاده از الگوریتم ژنتیک
طراحی وب سايت
راهکاری که برای حل یک مسئله با الگوریتم ژنتیک استفاده می شود تکامل می یابد. الگوریتم ژنتیک مثل هر الگوریتم بهینه سازی دیگر با تعریف متغیرهای بهینه سازی آغاز می شود و مانند الگوریتم های بهنیه سازی دیگر نیز خاتمه می یابد یعنی با تست همگرایی.



یک الگوریتم GA دارای پارامترهای زیر است:

: Fitnessتابعی برای ارزیابی یک فرضیه که مقداری عددی به هر فرضیه نسبت میدهد
: Fitness_threshold مقدار آستانه که شرط پایان را معین میکند
: population تعداد فرضیه هائی که باید در جمعیت در نظر گرفته شوند
: crossover rate در صدی از جمعیت که در هر مرحله توسط الگوریتم crossover جایگزین میشوند
:mutation rate نرخ mutation
الگوریتم GA به صورت زیر کار می کند:

: Initializeجمعیت را با تعداد population فرضیه بطور تصادفی مقدار دهی اولیه کنید.
: Evaluateبرای هر فرضیه h در population مقدار تابع Fitness(h) را محاسبه نمائید.
تا زمانیکه[maxh Fitness(h)] < Fitness_threshold یک جمعیت جدید ایجاد کنید.
فرضیه ای که دارای بیشترین مقدار Fitness است را برگردانید.
روش های مختلف crossover:

Single-point crossover

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

در crossover یکنواخت بیتها بصورت یکنواخت از والدین انتخاب می شوند.



اپراتورهای ژنتیکی Mutation :

اپراتور mutation برای بوجود آوردن فرزند فقط از یک والد استفاده میکند. اینکار با انجام تغییرات کوچکی در رشته اولیه بوقوع میپیوندد.
با استفاده از یک توزیع یکنواخت یک بیت بصورت تصادفی اتنخاب و مقدار آن تغییر پیدا میکند.
معمولا mutation بعد از انجام crossover اعمال میشود.


تابع fitness معیاری برای رتبه بندی فرضیه هاست که کمک میکند تا فرضیه های برتر برای نسل بعدی جمعیت انتخاب شوند. نحوه انتخاب این تابع بسته به کاربر مورد نظر دارد

در روش معرفی شده در الگوریتم ساده GA احتمال انتخاب یک فرضیه برای استفاده در جمعیت بعدی بستگی به نسبت fitness آن به fitness بقیه اعضا دارد. این روش Roulette Wheel selectionنامیده میشود.

روش جستجوی GA با روشهای دیگر مثل شبکه های عصبی تفاوت دارد:

در شبکه عصبی روش Gradient descent بصورت هموار از فرضیه ای به فرضیه مشابه دیگری حرکت میکند در حالیکه GA ممکن است بصورت ناگهانی فرضیه والد را با فرزندی جایگزین نماید که تفاوت اساسی با والد آن داشته باشد.از اینرو احتمال گیر افتادن GA در مینیمم محلی کاهش می یابد. با این وجود GA با مشکل دیگری روبروست که crowding نامیده میشود crowding پدیده ای است که در آن عضوی که سازگاری بسیاربیشتری از بقیه افراد جمعیت دارد بطور مرتب تولید نسل کرده و با تولید اعضای مشابه درصد عمده ای از جمعیت را اشغال میکند. راه حل رفع مشکل Crowdingاستفاده از ranking برای انتخاب نمونه ها است، با اختصاص رتبه به فرضیه ای که بسیار بهتر از بقیه عمل میکند.

مسئله ۸ وزیر:

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

تعریف توابع و متغیرها
تولید جمعیت اولیه
دیکد کردن کروموزوم ها
پیدا کردن هزینه برای هر کروموزوم
انتخاب جفت ها
جفت گیری
میوتیشن
بررسی همگرایی
خاتمه یا بازگشت به مرحله دیکد کردن کروموزوم ها
ژن عددی از ۰ تا n-1 است در ۸ وزیر n برابر با ۸ است بنابراین ژن عددی از ۰ تا ۷ می شود و کروموزوم آرایه ای از ژن هاست. که می تواند پاسخ مسئله باشد.

جمعیت هر نسل می تواند تعداد کروموزوم ها را تعیین کند.

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

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

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

در فرایند cross over فرزندان توسط والدین تولید می شوند که ترکیب آنها شامل ترکیب ژن های آنهاست. اگر نسل جدید حاوی کروموزومی باشد که نزدیک یا برابر با نتایج مطلوب باشد آنگاه مسئله حل شده است. در غیر اینصورت فرایند قبلی در نسل جدید هم پیاده سازی می شود مانند فرایندی که برای والدین آنها اتفاق افتاد. تا زمانی که به راه حل مناسب برسیم این روال ادامه دارد.

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

برای تولید فرزندان از والیدن نیاز به crossover داریم که تصمیم می گیرد از دو والدین کدام ژن باید انتخاب شود.

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

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

همان طور که گفته شد ژن عددی از ۰ تا ۷ است که به معنی شماره سطری است که وزیر در آن قرار گرفته است. موقعیت ژن در یک کروموزوم به معنی شماره ستون قرار گیری وزیر است. مشخص کردن مکان قرار گیری هر وزیر را باید حتما در هر سطر و ستون مشخص کرد.

کروموزوم نیز مجموعه ای از ۸ ژن است. و این طور فرض می شود که هیچ ژنی در یک کروموزوم دوبار تکرار نشود. برای مثال اگر کروموزوم ما ۰|۱|۴|۲|۳|۶|۷|۵ باشد یعنی ۸ وزیر در خانه های زیر از ماتریس قرار گرفته اند.

(۰,۰), (۱,۱), (۲,۴), (۳,۲), (۴,۳), (۵,۶), (۶,۷), (۷,۵)



در اینجا میوتیشن با swap کردن ژنی که باید mutate شود با یک ژن تصادفی (به جز ژنی که می خواهیم میوتیشن را روی آن انجام دهیم) از همان کروموزوم انجام می شود.

در crossover ژن ها از کروموزوم های دو والدین با احتمال ۰٫۵ گرفته می شود. یک ژن از یکی از والدین گرفت می شود و به کروموزوم فرزند اضافه می شود. ژنی که تولید می شود در پرنت دیگر پاک می شود. این مرحله انقدر ادامه می یابد تا کروموزوم های پدر و مادر هر دو، خالی شود و فرزند آنها همه ژن ها را داشته باشد.

تابع فیتنس: زمانی که دو وزیر طوری قرار بگیرند که یکدیگر را تهدید کنند یعنی در یک سطر، ستون یا قطر مشابه باشند. از آنجایی که کروموزوم ها ژن های تکراری ندارند بنابراین این اطمینان وجود دارد که هیچ دو وزیری در یک ستون قرار نمی گیرند. پس تنها باید برخوردهای قطری را بررسی و محاسبه کرد. بنابراین ماکزیمم تعداد برخوردها می تواند ۲۸ باشد. تابع فیتنس مقدارش هر چه بیشتر باشد بهتر است بنابراین اگر یک راه حل ۰ برخورد (تهدید دو وزیر) داشته باشد فیتنس آن ۲۸ است که با تفریق مقدار برخوردهایی که در حالت فعلی رخ می دهند از ۲۸ به دست می آید.

در کد c# مورد استفاده :

class GeneticAlgo: کلاسی است که مسئولیت همه عملیات الگوریتم ژنتیک را بر عهده دارد.

class FitnessComparator: یک کلاس مقایسه کننده است که کروموزوم ها را با fitness value مرتب می کند تا جمعیت نهایی را در جدول نشان دهد. بیشترین فیتنس در بالای جدول قرار می گیرد و کمترین آنها در پایین جدول.

struct Chromosome: ساختاری است که کروموزومی که حاوی ژنهااست، فیتنس و مجموع میانگین فیتنس ها را نشان می دهد.

class MainFrame: این کلاس موظف به کنترل اینترفیس کاربر و ایجاد جمعیت اولیه به منظور انتقال آن به الگوریتم ژنتیک است.

class Board: این کلاس گرافیک و عملیات صفحه شطرنج را بر عهده دارد.

متغیر private const int MAX_FIT = ۲۸ بیشترین مقدار فیتنس را دارد.

توابع:



private List<chromosome> GetInitialPopulation(int population)

{

List<chromosome> initPop = new List<chromosome>();

GeneticAlgo RandomGen = new GeneticAlgo();

for (int i = 0; i < population; i++)

{

List<int> genes = new List<int>(new int[] {0, 1, 2, 3, 4, 5, 6, 7});

Chromosome chromosome = new Chromosome();

chromosome.genes = new int[8];

for (int j = 0; j < 8; j++)

{

int geneIndex = (int)(RandomGen.GetRandomVal

(۰,genes.Count-1)+0.5);//randomly select a gene

chromosome.genes[j] = genes[geneIndex];

genes.RemoveAt(geneIndex);//remove selected gene

}



initPop.Add(chromosome);

}

return initPop;

}
site2017 آفلاين است   پاسخ با نقل قول
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 
ابزارهاي تاپيک
نحوه نمايش

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۲:۵۱ بعد از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

استفاده از مطالب انجمن در سایر سایت ها، تنها با ذکر انجمن هوش مصنوعي به عنوان منبع و لینک مستقیم به خود مطلب مجاز است

Inactive Reminders By Icora Web Design