حل مسأله کوله پشتي 0 و 1 رابا الگوريتم (SA)

---

شرح پروژه

مسأله کوله پشتي 0 و 1 را با در نظر گرفتن شرايط زير با الگوريتم Simulated Annealing حل کنيد. ( مربوط به درس هوش مصنوعي مي باشد) از سه تابع: پنالتي وزن کالا ، تابع ارزش کالا و تابع total cost ميتوان استفاده نمود. Total cost آرايه اي را ميگيرد، تابع value را صدا ميزند، و سپس تابع پنالتي را فراخواني ميکند. و داراي سه آرايه براي نگه داشتن جواب فعلي، جواب بعدي و بهترين جواب است. براي انتخاب يا رد جواب بدست آمده، از طريق RandomGenerator ععدي را توليد کرده و با مقدار e^((-∆)/T) مقايسه ميکنيم. اگر عدد بدست آمده بزرگتر از مقدار e^((-∆)/T) باشد، انتخاب نمي شود و اگر کوچکتر بود انتخاب مي شود. ∆ : اختلاف جواب بهدي با فعلي T: از فرمول روبرو بدست مي آيد. T=αT وزن محدود کوله پشتي : k Input: Enter n (number of parts); Enter weights; Enter values; Enter k weights; (The Whole weights) Output: Initial state: N عدد را به صورت random از طريق Generator توليد ميکند، اگر عدد تصادفي بزرگتر از 0.5 بود، 1 و اگر کوچکتر از 0.5 بود 0 را چاپ کند. Penalty-weight: براي بدست آوردن اين مقدار، وزن عدد بدست آمده از Initial State را محاسبه کرده و با وزن کوله پشتي مقايسه مي کند، اگر بيشتر بود، تعداد اضافي آن را چاپ کند. مثلا: K=10, initial state=15 ….. Penalty-weight=5 Value; Total cost: value – 100 * Penalty-weight حل مسأله با SA : SA output: Best solution: Penalty-weight: Value: Total cost: اگر SA مسأله را درست حل کرده باشد: Penalty-weight=0 وtotalcost=value α: 0.99 T= αT ts=(total cost(x best) – total cost (x0))/log⁡0.9 tf=(total cost(x best) – total cost (x0))/log⁡0.01 x0 را به صورت تصادفي در نظر گرفته و با الگوريتم HillClimbing همه همسايه ها را بررسي کرده و بهترين(بيشترين) را در نظر مي گيريم. مثلا: F(x0)= 00011 از همسايه هاي زير totalcost هر کدام که بيشتر است انتخاب مي شود. 10011 01011 00111 00001 00010


زیرساخت:
ترجيحآ به زبان c# وهرچه زودتر اطلاع دهيد که ميتوانيد انجام دهيد؟ تاچه زماني؟


قابل تحویل:

مهارت ها و تخصص های مورد نیاز

---

---