سورس و آموزش کوله پشتی صفر و یک با الگوریتم ژنتیک


اطلاعات پروژه

فریلنسر مهدی فتحی
نام کاربری mehdi.fathi2003
دسته بندی پروژه
تاریخ ثبت ۲۳ فروردین ۱۳۹۴
تعداد نظرات ۲
قیمت ۱۲۰,۰۰۰ تومان


امکان خرید از درگاه های بانکی و کیف پول

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

انتشار پروژه ها و مطالب سایت در سایت دیگر ممنوع بوده و پیگرد قانونی دارد

سورس و آموزش کوله پشتی صفر و یک با الگوریتم ژنتیک


سورس و آموزش کوله پشتی صفر و یک با الگوریتم ژنتیک

حل مساله ی کوله پشتی 0-1 با استفاده از الگوریتم ژنتیک

1- مساله ی کوله پشتی چیست؟

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

سابقه ی کار بر روی این مساله به سال 1897 می رسد. این مساله در دنیای واقعی کاربردهای فراوانی دارد. این مساله به صورت های مختلفی بیان شده است در روش حل به صورت 0-1 فرض بر این است که هر کدام از کالاهای کاندید برای قرار گرفتن در کوله پشتی می توانند دارای دو حال باشند: یا برداشته می شوند و یا برداشته نمی شوند. این در حالی است که در روش حل دیگری به نام "کسری" مجاز هستیم تا در صورت دارا بودن شرایط، کسری از یک کالا را برای قرار گرفتن در کوله پشتی انتخاب کرده و کسر دیگری را برنداریم. به این دلیل که در روش حل 0-1 نمی توانیم قسمتی از کالا را برداریم، برای پیاده سازی این روش استفاده از الگوریتم حریصانه ممکن نیست و بایستی از الگوریتم های بهینه سازی استفاده کرد. الگوریتم ژنتیک یکی از این نوع الگوریتم ها است.

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

الگوریتم ژنتیک یکی از انواع روشهای جستجوی راه حل است که رفتار موجود در طبیعت به نام "انتخاب طبیعی" را بازسازی می کند. انتخاب طبیعی قسمتی از تئوری تکامل است که در آن ادعا می شود در طبیعت جاندارانی که بتوانند بیشتر خود را با وضعیت های گوناگون وفق دهند شانس بیشتری برای بقا و ازدیاد نسل دارند. الگوریتم ژنتیک به گروه بزرگتری از الگوریتم ها به نام الگوریتم های تکاملی تعلق دارد. این دسته از الگوریتم ها سعی در تقلید کلیه قسمت های موجود در تکامل طبیعی مثل وراثت، جهش، انتخاب و تقاطع را دارند.   

3- الگوریتم ژنتیک چگونه کار می کند؟

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

برای پیاده سازی این الگوریتم به طور عملی، از تعاریف موجود در نظریه تکامل استفاده شده و توابعی یکسان با آن ها نوشته می شود. در عکس ذیل میتوانید مراحل کار الگوریتم ژنتیک را ببینید:

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

ابتدا به طور تصادفی جمعیت اولیه ایجاد می شود، در مرحله ی دوم تابعی با عنوان Fitness مقدار برازندگی هر کدام از کروموزوم های ایجاد شده به شکل تصادفی را می سنجد و بهترین کروموزوم را انتخاب می کند. در مرحله ی بعد تعداد بیشتری از بهترین کروموزوم ها نیز انتخاب می شوند و تابع Crossover بر روی هر جفت کروموزوم انتخاب شده اجرا می شود، این تابع در واقع همان عمل لقاح جانوران در طبیعت را شبیه سازی می کند و خروجی آن تولید کروموزوم های جدید یا نسل دوم خواهد بود. سپس این نسل جدید وارد تابع Mutation می شوند. Mutation یا جهش یکی از ارکان اصلی در نظریه تکامل است، در واقع موتور محرک نسل ها و عامل اصلی تکامل را می توان عمل جهش معرفی کرد در اینجا نیز کروموزوم های جدید وارد این تابع شده و با احتمالی متغیر برخی از ژن ها جهش می یابند تا در نهایت جمعیت جدید ایجاد شود. جمعیت جدید بارها و بارها همین مراحل را تکرار می کنند تا در نهایت به جواب بهینه نزدیک شوند.

4- توضیحات مربوط به کد نوشته شده

نحوه پیاده سازی الگوریتم ژنتیک برای مساله ی کوله پشتی 0-1 بدین صورت است که ابتدا برای کوله پشتی فرضی خود محدودیت وزن 100 را در نظر گرفتیم می توانیم این مقدار را بنا به میل خود کم یا زیاد کنیم، همچنین تعداد کالاهایی که برای قرار گرفتن در کوله پشتی وجود دارند 10 عدد می باشند این عدد نیز می تواند کم یا زیاد شود. در تصویر ذیل تعداد آیتم ها یا همان کالاهای کاندید برای قرار گرفتن در کوله پشتی و وزن و ارزش معادل هر کدام را مشاهده می کنید:

درباره کروموزوم در بخش های قبل صحبت کردیم، کروموزوم به صورت اجمالی به یک حال از جواب اطلاق می شود، در تصویر ذیل یک کروموزوم را مشاهده می کنید:

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

در مساله ی ما هر کروموزوم رشته ای 10 رقمی است و هر رقم یا اصطلاحا ژن نشاندهنده ی این موضوع است که در این کروموزوم خاص کالای مرتبط با آن رقم یا ژن در کوله پشتی انتخاب خواهد شد یا خیر.

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

با توجه به توضیحات ارائه شده کروموزوم 0001101001 به معنای این است که به ترتیب از چپ به راست آیتم های چهارم، پنجم، هفتم و دهم طبق این کروموزوم باید در کوله پشتی قرار بگیرند. در صورتی که ارزش معادل این کالاها را محاسبه کنیم به عدد 155 می رسیم که این عدد بالاترین ارزشی است که می توانیم طبق تعریف مساله ی کوله پشتی 0-1 در این کوله پشتی فرضی با این مشخصات جای دهیم. بنابراین می توانیم بگوییم این کروموزوم جواب نهایی ماست که باید الگوریتم به آن برسد.

تعاریف متغیرها به صورت زیر انجام شده است: 

 

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

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

ادامه توضیحات و ادامه کدها و همچنین سورس پروژه را بعد از خرید می توانید دانلود نمایید.

پروژه های دیگر این فریلنسر
سورس کامل راه اندازی درگاه بانک سامان با استفاده از برنامه نویسی شی گرا با PHP با Api کلیک اتوماتیک ماوس در زمان خاص در نقطه ای از دسکتاپ با سی شارپ ورژن 2 آموزش فروشگاه اینترنتی با برنامه نویسی شی گرا با PHP آموزش کامل برنامه نویسی شی گرا با php آموزش طراحی وب سایت با php آموزش ارتباط با پایگاه داده MySQL در php آموزش کامل مفاهیم پایگاه داده و MySQL آموزش برنامه نویسی php سورس و آموزش راه اندازی درگاه بانک پارسیان با سیستم جدید با برنامه نویسی شی گرا در PHP سورس و آموزش راه اندازی درگاه بانک پارسیان با سیستم جدید در PHP سورس و آموزش راه اندازی درگاه بانک پارسیان با برنامه نویسی شی گرا در PHP سورس و آموزش راه اندازی درگاه بانک پارسیان با PHP لینک دانلود موقت در php سورس و آموزش راه اندازی درگاه بانک ملی با استفاده از برنامه نویسی شی گرا با PHP با web api سورس و آموزش راه اندازی درگاه بانک ملی با PHP با web api سورس کامل راه اندازی درگاه بانک ملی با استفاده از برنامه نویسی شی گرا با PHP سورس کامل راه اندازی درگاه بانک ملی با PHP سورس کامل راه اندازی درگاه بانک پاسارگاد با برنامه نوسی شی گرا با PHP سورس کامل راه اندازی درگاه بانک پاسارگاد با PHP سورس کامل اتصال به درگاه زرین پال با PHP وب سایت آموزشگاه آنلاین با php سورس کامل راه اندازی چهار درگاه پرداخت با PHP سورس کامل راه اندازی درگاه بانک سامان با استفاده از برنامه نویسی شی گرا با PHP سورس کامل راه اندازی درگاه بانک سامان با PHP سورس کامل دیکشنری با الگوی شی گرا با php پروژه مدیریت کافی نت با سی شارپ 2013 کلیک اتوماتیک ماوس در زمان خاص در نقطه ای از دسکتاپ با سی شارپ سورس حرکت اسب به 64 خانه شطرنج با C#.Net 2013 وب سایت حرفه ای با برنامه نویسی شی گرا با php فروشگاه اینترنتی کتاب با برنامه نویسی شی گرا با php فروشگاه اینترنتی با الگوی طراحی شی گرا با php فروشگاه اینترنتی کتاب با php فروشگاه اینترنتی با امکانات مدیریتی کامل و کاربران با PHP سورس و آموزش کوله پشتی صفر و یک با الگوریتم ژنتیک سورس یک وب سایت کامل با php سورس کامل وب سایت به همراه CMS با PHP آموزش و سورس کد درگاه پرداخت بانک ملت با PHP سورس کامل وب سایت باشگاه اسب سواری با php

Captcha
نظرات کاربران
  • aidin.paradox74 پاسخ

    aidin.paradox74 ۲۲:۱:۵۵   ۱۳۹۵/۱۰/۸

    با عرض سلام خسته نباشید در قسمت کد ها تابعی بنام selective موجوده که متاسفانه کد این تابع موجود نیست آیا کد دیگری در این رابطه وجود داره؟

    • مهدی فتحی پاسخ

      مهدی فتحی ۱۰:۵۰:۳۸   ۱۳۹۵/۱۰/۱۱

      سلام

      اصلا چنین تابعی وجود ندارد یک تابع به نام selection وجود دارد که کدهای آن هم هستش