shima3000

سلام

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

ممنون میشم اینم در کنار بقیه الگوریتما قرار بدین!

روحي

مطالب جالب و مفيد بود
متشكرم

masood

متاسفانه دیگه این وبلاگ در دسترس نیست.

__________________
یک روز یک ماشین برای انتخابات ریاست جمهوری ثبت نام می کند
چه بخواهیم چه نخواهیم این اتفاق می افتد.

srainy

سلام
دوستان کسی پروژه پیاده سازی الگوریتم های حریصانه و پویا برای کوله پشتی صفر و یک رو اگه با سی شارپ لطفا ضمیمه کنه + مقایسه پیچیدگی زمانی این دو روش

helmaa

سلام خواهش می کنم اگر کسی میتونه کد الگوریتم ژنتیک این مسٔله رو توضیح بده بد جوری نیاز دارم ممنون

serendpt

دوستان میشه بگید الگوریتم حل این سوال چی هست؟
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

عماریاسر

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

helen11

سلام
لطفا کد الگوریتم کوله پشتی و 8 وزیر با شبکه هاپفیلددرمتلب

site2017

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

الگوریتم
این مسئله یکی از پایه‌ای‌ترین مسائل برنامه‌ریزی پویا است و صورت‌های مختلفی دارد که در انتها به آن‌ها و ایده‌ی اثبات‌شان اشاره می‌شود.
برای حل مدل ساده‌ی سوال، یک آرایه دوبعدی به نام 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

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



یک الگوریتم 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;

}